into an ancient filesystem...

Today I got the funny idea to write a "defrag" program. Windows uses the "FAT32" filesystem which has the property that, as it is used, files tend to get fragmented. Instead of being stored in one contiguous chunk of disk, a file's contents is stored in a number of chunks spread around on the disk. Defragmenting consolidates these pieces thus making file access faster.

It's been an hour or two and I now have a (Linux) program that can read the disk and spit out the partition table, and can read the properties of a FAT32 partition and spit out the contents of the root directory. The way it all works is remarkably rudimentary. I can just see how some hackers in the late 70's put this together as a quick hack (What became MS-DOS and later Windows was originally QDOS, "Quick and Dirty Operating System.") Unfortunately, it stuck.

The way it works is this: The usuable disk space is divided into "clusters" (of, say, 4 kilobytes), and a file spans an integer number of clusters. For every cluster of storage space, there is an associated entry in the File Allocation Table (FAT), which tells you which cluster to go to next to find the rest of the file data. next = FAT[current].

Okay, how do you find the first cluster of a file? Well, you actually must traverse the directory tree. A directory is a list of files and subdirectories where each has a name, some attributes, a size, and a starting cluster. You're given the starting sector of the root directory. So, by following this chain of subdirectory entries, you can eventually find the starting cluster of the file you want. Then you can follow the chain of clusters composing that file to read out the data.

I'd say that "QDOS" was an appropriate name...