Mmmm… delicious fatty goodness…

Array

Do you know what this means? It means I’ve got our little FAT driver reading the entire FAT32 boot sector. What’s more, this is the very first ever run of this code; not a single error [that I can see]!

Needless to say, I’m pretty much glowing right now. 😀

[Session started at 2006-05-11 12:28:42 +1000.]
GNU gdb 6.1-20040303 (Apple version gdb-434) (Wed Nov 2 17:28:16 GMT 2005)
Copyright 2004 Free Software Foundation, Inc.
GDB is free software, covered by the GNU General Public License, and you are
welcome to change it and/or distribute copies of it under certain conditions.
Type "show copying" to see the conditions.
There is absolutely no warranty for GDB. Type "show warranty" for details.
This GDB was configured as "powerpc-apple-darwin".
Loading program into debugger…

tty /dev/ttyp2
Program loaded.
sharedlibrary apply-load-rules all
run
[Switching to process 643 local thread 0xf03]
Running…
Unable to open file "/Users/wadetregaskis/Documents/School/Fifth Year/PRJ/Project/Flash Disk Image" as writable; reverting to read-only.
..i.k$.....YU.J..r.y.b..9...e...O.:N.h......&...|...Bjl.i.........u.7.[.Kv.1`...*...A`...=.61[.....b.SO5...U+..J...uO.
...b.b^9...N....c&.!.3`....HP..K:...3.s..u.b.....d01...Q.h..g...^..X..**f...}...yf......ke.....mh...e............x*..f
.~E.[6V.6.f.[....aH.g[..Tk0.."....#R.....jQ...Wq<-EEm=...#.C....s.....R..gUs.{P#V-cp.....%_^q.0mZ...b...d.._...&..7...
`?]z.."....,.~.q...[1.}..`sn&...*n.Vl.jn.{z.dLi..ES....4..*..%...:q..(.....a....B44O...P....e.....T.."#......j.*..<..
...C<...6.}.78D.K(....I._..!..9.,..7....
(gdb) continue
/Users/wadetregaskis/Documents/School/Fifth Year/PRJ/Project/FATShell/FATDriver.c:599 (FATCreateVolume) - FATVolume:
/Users/wadetregaskis/Documents/School/Fifth Year/PRJ/Project/FATShell/FATDriver.c:600 (FATCreateVolume) - volume = 0xb380
/Users/wadetregaskis/Documents/School/Fifth Year/PRJ/Project/FATShell/FATDriver.c:601 (FATCreateVolume) - FATOffset = 523776
/Users/wadetregaskis/Documents/School/Fifth Year/PRJ/Project/FATShell/FATDriver.c:602 (FATCreateVolume) - DataOffset = 1532416

/Users/wadetregaskis/Documents/School/Fifth Year/PRJ/Project/FATShell/FATDriver.c:603 (FATCreateVolume) - bytesPerSector = 512
/Users/wadetregaskis/Documents/School/Fifth Year/PRJ/Project/FATShell/FATDriver.c:604 (FATCreateVolume) - sectorsPerCluster = 1
/Users/wadetregaskis/Documents/School/Fifth Year/PRJ/Project/FATShell/FATDriver.c:605 (FATCreateVolume) - reservedSectorCount = 38
/Users/wadetregaskis/Documents/School/Fifth Year/PRJ/Project/FATShell/FATDriver.c:606 (FATCreateVolume) - numberOfFATs = 2

/Users/wadetregaskis/Documents/School/Fifth Year/PRJ/Project/FATShell/FATDriver.c:620 (FATCreateVolume) - FAT32:
/Users/wadetregaskis/Documents/School/Fifth Year/PRJ/Project/FATShell/FATDriver.c:621 (FATCreateVolume) - FATInUse = 0
/Users/wadetregaskis/Documents/School/Fifth Year/PRJ/Project/FATShell/FATDriver.c:622 (FATCreateVolume) - mirroringDisabled = 0
/Users/wadetregaskis/Documents/School/Fifth Year/PRJ/Project/FATShell/FATDriver.c:623 (FATCreateVolume) - majorVersion = 0
/Users/wadetregaskis/Documents/School/Fifth Year/PRJ/Project/FATShell/FATDriver.c:624 (FATCreateVolume) - minorVersion = 0
/Users/wadetregaskis/Documents/School/Fifth Year/PRJ/Project/FATShell/FATDriver.c:625 (FATCreateVolume) - rootCluster = 2
/Users/wadetregaskis/Documents/School/Fifth Year/PRJ/Project/FATShell/FATDriver.c:626 (FATCreateVolume) - fileSystemInformationSector = 1
/Users/wadetregaskis/Documents/School/Fifth Year/PRJ/Project/FATShell/FATDriver.c:627 (FATCreateVolume) - backupBootSector = 6
/Users/wadetregaskis/Documents/School/Fifth Year/PRJ/Project/FATShell/FATDriver.c:628 (FATCreateVolume) - logicalDriveNumber = 0
/Users/wadetregaskis/Documents/School/Fifth Year/PRJ/Project/FATShell/FATDriver.c:629 (FATCreateVolume) - extendedSignature = 41
/Users/wadetregaskis/Documents/School/Fifth Year/PRJ/Project/FATShell/FATDriver.c:630 (FATCreateVolume) - serialNumber = 1149524418

/Users/wadetregaskis/Documents/School/Fifth Year/PRJ/Project/FATShell/FATDriver.c:636 (FATCreateVolume) - totalSectors = 128000
/Users/wadetregaskis/Documents/School/Fifth Year/PRJ/Project/FATShell/FATDriver.c:637 (FATCreateVolume) - mediaDescriptor = 248
/Users/wadetregaskis/Documents/School/Fifth Year/PRJ/Project/FATShell/FATDriver.c:638 (FATCreateVolume) - sectorsPerFAT = 985
/Users/wadetregaskis/Documents/School/Fifth Year/PRJ/Project/FATShell/FATDriver.c:639 (FATCreateVolume) - sectorsPerTrack = 63
/Users/wadetregaskis/Documents/School/Fifth Year/PRJ/Project/FATShell/FATDriver.c:640 (FATCreateVolume) - numberOfHeads = 255
/Users/wadetregaskis/Documents/School/Fifth Year/PRJ/Project/FATShell/FATDriver.c:641 (FATCreateVolume) - hiddenSectors = 0
/Users/wadetregaskis/Documents/School/Fifth Year/PRJ/Project/FATShell/VolumeInterface.c:125 (createVolume) - Successfully opened volume starting at logical address 0 (0), length 4294967295 (0xffffffff), suggestedFormat 3 (actual format 3).
/Users/wadetregaskis/Documents/School/Fifth Year/PRJ/Project/FATShell/VolumeInterface.c:155 (destroyVolume) - Successfully destroyed volume (handle = 0, ptr = 0xb380) starting at logical address 0 (0), length 0 (0), format 3.

Debugger stopped.
Program exited with status value:0.

FAT detection

Array

To introduce with the conclusion, I’ve finally got my little disk driver – for the electronics project – detecting FAT formatted volumes (non-partitioned), and determining whether they’re FAT12, FAT16 or FAT32.

This is a surprisingly difficult thing to do, it seems. There’s not any handy flag anywhere that says what format the volume is. If it’s FAT, it has a two-byte signature, which isn’t a particularly unique one (0x55 0xAA, used frequently as a marker value, and thus not nearly as unlikely as you might think), at offset 510 (i.e. the last two bytes of the boot sector). While the boot sector’s meant to start with a jump instruction, I’m not sure if it’s unique, so I can’t directly validate that either. There are plenty of other fields, but it’s hard to be deterministic about the format based on them; many can have virtually any value, since a lot of them are ignored in numerous conditions.

The whole thing’s even more complicated than just that, because there’s some big differences between FAT12/16 and FAT32 in terms of what fields are in the boot sector, and where they are. For example, there’s a FAT name, which contains something like “FAT32 ” (the extra spaces are important; it’s an opaque 8-byte field). But, for FAT12/16, it’s in a different spot. Duh. Why have a field who’s only purpose, surely, is to distinguish between formats, if in each different format it’s in a different spot?

This is why Microsoft should have as much freedom for defining standards as Rob has naming them. 😛

And to make things worse, while I cannot find a single statement as to how you’re meant to distinguish between them, I’ve found many which say things like not to rely on even the presence of the FAT name, let alone that it’ll be correct.

So, I’m just winging it for the moment. We can keep this as a pretty restricted system, so we only have to support the exact volume format we want to use, but still… I’d like to think we’re pretty flexible, in so far as handling all the FATs fine… but perhaps not.

It’s interesting to note that Microsoft states that Windows will never partition removable media (e.g. floppy disks, zip disks, USB disks, etc). So in theory you couldn’t possibly get an MBR (Master Boot Record) on an SD memory card, in Microsoft-land. Of course MacOS X, conversely, does not allow you to create an unpartitioned USB disk… both OS’s handle each other’s volumes perfectly well, as far as my testing has seen, yet claim that the other is doing it wrong. Hmph.

So for the moment there’s no partitioned-volume support, because it’s extra work we don’t need at this point. It leads to the land of MBR, EMBR, GPT, and many more acronyms – all created by Microsoft, and like the FAT boot sector, all completely and absolutely rooted. It’s like they had a million monkeys at a million typewriters, and didn’t even just pick the best one – they just merged all of them.

But things are looking good, anyway, with the volume driver. FAT is at least a trivial format to use…. disgustingly slow and inefficient, but simple. Except, of course, when you start supporting things like long file names, and all the bizarre behaviours accrued by 20 years of use and abuse.

In hindsight, perhaps we should have just used ext2 or something. 😉

Or HFS. 😀

But HFS is a very complicate format, because it’s very efficient and very powerful; HFS+ even more so. I wouldn’t like to try to implement it on an AVR. I think I’d definitely run out of resources. I’m still not entirely sure how FAT support is going to turn out.

What we could have done is have our own partition type, and write to it as basically a single stream. I could then perhaps have mustered up a MacOS X file system plugin to read it. But that wouldn’t make Rob very happy, stuck in Windowsland.

In fact, we wouldn’t even need a driver on MacOS X, since like all real OS’s it mounts raw volumes in /dev, so I could just read directly from the SD memory card, skipping the boot sector. Hmm. That may be how it ends up… we’ll see.

Oh the wasted cycles

Array

An assignment I have at the moment is a simple cache simulator, as I think I’ve said before. Anyway, I thought the code was all done – all good. The results made sense, and it seemed to correspond with what dineroIV (a popular and powerful open source cache simulator, which we’re using as our reference, presuming it’s totally accurate) was saying. I emphasise seemed, because as it turns out I’d only tested the few cases where it did… for the vast majority, it didn’t. D’oh.

Long story short, I have two arrays – one of elements actually loaded into the given cache set, one of all elements that have at any time been in cache (i.e. a history). Now, when a miss occurs for an entry that’s been loaded before, you copy one of the elements from the ‘history’ into the ‘current’ array. I was doing this, of course. What I wasn’t doing was updating it’s access times for read/write/etc…. so when LRU or similar algorithms were applied they were forever seeing the stale values from when it was loaded into the cache the very first time. D’oh d’oh d’oh d’oh!!

So now it’s fixed… and now I have to run all 14100 simulations again, repopulate my PostgreSQL results database, and restart pulling my results selectively into Excel. Oh the humanity. Luckily it’s pretty fast, if I do say so myself, and those 14100 simulations only take half an hour or so. The front end for the app is extremely powerful, so I can just give it ranges for all the variables and it’ll automagically perform every valid permutation of those… saves typing in the parameters by hand 14100 times. 🙂

The morale of this story – get it right the first time!