As of last Thursday, I’m no longer a land owner, so you guys are on your own with that whole voting thing.
Bits
Now that I’ve relearned Booth’s algorithm, I now understand this particular silliness. Are there still any machines where this is fast?
Turing
I’ve been going over a lot of old textbooks while studying for my upcoming CS GRE. I forgot how good the Hennessy and Patterson books are. Also I’ve read the dragon book cover-to-cover for the first time (the new edition with the lame CGI dragon on the cover), various parts of TAOCP, and Sedgewick’s Graph Algorithms in C. Time will tell whether I’ve digested any of that.
When I was in the bookstore the other day, I saw Petzold’s The Annotated Turing. I still blame Petzold for the worst book in my computing library, Programming Windows 95. But I needed to fill in some gaps on formal logic and it was 30% off so I thought I’d give it a go. One nice thing is that it presents in full the paper “On Computable Numbers, with an Application to the Entscheidungsproblem,” with corrections inline. I found a number of the annotations on the machines themselves to be superfluous to the original, while the background on Cantor sets and formal logic were absolutely worthwhile. The main problem is that the book sometimes cites large sections of material from another work, which just makes me wish I had read the other work instead. Conspicuously absent from citation but appearing in the bibliography is the mind-altering but lengthy Gödel, Escher, Bach, which in my opinion better tackles the philosophical angles. I give The Annotated Turing a B: nice explanation of the paper but Chuck loses a letter grade for citing his own book twice and for having a Windows tattoo.
Buy my stuff
If you’ve always wanted to own a piece of history, now’s your chance. Since I’m just over two weeks away from having to vacate my house for good, I’m selling all my crap. Oh, it’s wonderful crap, such as my couch, beds, bookshelves, small kitchen appliances, propane tanks, lawn mowers, chainsaws[1], and various electronics. Actually, assuming I get it all in order in the next day or two, you can drop by my house on Saturday to paw through the meaningful effects of a great living legend[2].
[1] Only one lawn mower, propane tank, and chainsaw. Two broken leaf blowers though.
[2] Great and legend not guaranteed. Living hoped for.
Ads
Anyone in the interweb know why my LJ now has an ad sidebar, when I’ve explicitly opted out of the ad-supported-for-useless-goodies account? May it be time to move/shutter this thing?
Update:
Oh. 🙁
Mainlandy
Ange & I are back from our brief tour of the Carribean. PR was nice: wonderful weather and warm ocean water. We somehow lucked out and missed all three hurricanes that went through the area during our stay. The local cuisine left a lot to be desired, and the area just outside of the resorts was pretty sketch, but otherwise it’s a decent little island.
I did find time during the traveling downtime to complete my Gstreamer FS. I’m rather proud of the fruits of that two-day hack, though I’ve yet to see if it works well enough to trick iTunes.
Islandy
Angeline and I are Puerto Rico bound on Sunday! Here’s hoping for an absence of hurricanes. We’re also in ATL for two days next weekend.
I have a new FUSE filesystem in the prototype stage: gstfs. The idea is to mirror a directory of music files and automatically transcode them at read() time using a gstreamer pipeline. This is so my lovingly cultivated ogg collection is friendly with Angeline’s iPod. It seems to work so far but is still a dirty hack.
This post encrypted with the one-time-pad of all zeros
I only made 770 (67th percentile) on the practice GRE CS subject exam I took today. I guess I need to study up on graph theory and grammars over the next month. The computer architecture questions were all fun though.
Stupidest question of the exam, which I “missed”:
Which is the closest to a perfectly secure encryption scheme:
a) Caesar cipher (heh)
b) DES
c) Enigma
d) One time pad
e) RSA
I take issue with the supposedly correct answer of “D”, since yes, in principle, it is perfect encryption, but in practice, it sucks. Knowing OTP is flawed has to be more useful than knowing that it could be perfect in circumstances that are never true. If only there were an option in the list which provided good encryption and also solved the key distribution problem!
The engineer in me is at times in conflict with the “computer science == astronomy” crowd (yeah, I’m looking at you Dijkstra). Which is why every time I read someone’s article on here’s-how-to-do-X-in-unreadable-haskell my eyes glaze over. Maybe I’m not smart enough, but I would take the fact that there are now a zillion blogs trying to explain monads as evidence that the functional people made pipes too confusing.
Oh, by the way, here’s a secret: CPUs are imperative!
I can do 1000 now
In addition to doing as little cardio as I can get away with, Angeline and I have been following the 100 pushups training program for the last 4 weeks. That’s almost 1800 pushups between us so far. Ow, my arms.
Oops
I am finally getting the hang of debugging kernel crashes. None too soon as I got my first OOPS report from the -rc kernel with OMFS, from a gentleman who is intentionally corrupting his FS (“fuzzing” in the infosec lingo). After a frustrating weekend in which I had inadvertantly fixed the bug but didn’t realize it because I was testing the wrong module, I can now claim success. One down, several more to go.
Detective work after the jump if you care for the nerdy stuff.
Oops report:
BUG: unable to handle kernel paging request at c978e004 IP: [(c032298e)] omfs_readdir+0x18e/0x32f Oops: 0000 [#1] PREEMPT DEBUG_PAGEALLOC [...] EIP: 0060:[(c032298e)] EFLAGS: 00010287 CPU: 0 EIP is at omfs_readdir+0x18e/0x32f EAX: c978d000 EBX: 00000000 ECX: cbfcfaf8 EDX: cb2cf100 ESI: 00001000 EDI: 00000800 EBP: cb2d3f68 ESP: cb2d3f0c DS: 007b ES: 007b FS: 0000 GS: 0033 SS: 0068 [...] [(c018a820)] ? filldir64+0x0/0xcd [(c018a9f2)] ? vfs_readdir+0x56/0x82 [(c018a820)] ? filldir64+0x0/0xcd [(c018aa7c)] ? sys_getdents64+0x5e/0xa0 [(c01038bd)] ? sysenter_do_call+0x12/0x31 ======================= Code: 00 89 f0 89 f3 0f ac f8 14 81 e3 ff ff 0f 00 48 8d 14 c5 b8 01 00 00 89 45 cc 89 55 f0 e9 8c 01 00 00 8b 4d c8 8b 75 f0 8b 41 18 (8b) 54 30 04 8b 04 30 31 f6 89 5d dc 89 d1 8b 55 b8 0f c8 0f c9
First step is to look at the faulting instruction. Running the “Code:” part through ~/linux/scripts/decodecode yields the disassembly:
8b 4d c8 mov -0x38(%ebp),%ecx 8b 75 f0 mov -0x10(%ebp),%esi 8b 41 18 mov 0x18(%ecx),%eax 8b 54 30 04 mov 0x4(%eax,%esi,1),%edx <=== here 8b 04 30 mov (%eax,%esi,1),%eax 31 f6 xor %esi,%esi
So the instruction is dereferencing the address [(eax+esi)*1+4]. From the register dump, EAX=c978d000. That looks like a pointer. ESI is 00001000, which is probably the index to an array. 0x1000 happens to be PAGE_SIZE which explains the page fault (kernel paging request) at the top of the oops.
Next, let’s look at the C code. There are two ways:
$ gdb omfs.ko (gdb) l *(omfs_readdir+0x18e)
Or (and I find this a little more obvious since it has mixed C and assembly):
$ objdump -S omfs.ko > foo.S # now look for instruction opcodes in foo.S: "8b 54 30 04"
From the output of the above commands, it’s apparent that the +4 index in the instruction comes from be64_to_cpu() converting a 64-bit big-endian number to little-endian. And we do that when reading directory pointers in omfs_readdir, specifically:
fsblock = be64_to_cpu(*((__be64 *) &bh->b_data[offset]));
EAX is bh->b_data so ESI must be offset. I happen to know it should never be above 2048, but it is 4096 in the register dump. Since the range is ultimately controlled by the directory inode size, I immediately suspected that that size got corrupted. For some reason I chased a bunch of other dead ends until I finally did look at the disk image and saw that the directory size was all wrong. Rule one of debugging: go with your gut.
Oh well. I guess all that assembly coding from years ago was useful after all.