Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

17 – Reading FAT32

Goal: turn the numbered sectors of chapter 16 into files and directories – by reading the FAT32 format, which every operating system understands and which Linux tools write for our tests. You end up with: a FAT32 volume mounted at boot, lookup, read_dir and read_file with long file names, and ls and cat in the shell. A volume whose numbers are broken gives an error, never a hang. Code: course/17-fat32/ (chapter 16 plus fat32.rs and fs.rs, a test disk made by mkdisk.sh) What changed: diff -ru course/16-ahci course/17-fat32 (in the repository) shows every line this chapter adds.

Background: a linked list on a disk

A file system answers one question: which sectors belong to /docs/notes.txt, in which order? FAT, from 1977, answers it with a table. The volume is cut into clusters – a few sectors each, here one – numbered from 2. The File Allocation Table has one 32-bit entry per cluster: 0 means free, 0x0FFFFFF8 or more means "the file ends here", any other number is the next cluster of the same file. A file is a linked list; its directory entry holds the first cluster and the size in bytes. A directory is a file too, a list of 32-byte entries.

The layout is fixed by Microsoft's specification, "FAT: General Overview of On-Disk Format" (version 1.03), and starts at sector 0:

sector 0         boot sector: the BPB says how big everything is
sectors 1..31    reserved (FSInfo, a copy of the boot sector)
sectors 32..     FAT #1, then FAT #2 (a copy)
then             the data area: cluster 2, cluster 3, ...  (cluster 2 is the root directory here)

FAT is old and simple, and that is the point: Linux formats a disk image with mkfs.fat, copies files onto it with mtools, and checks it with fsck.fat – so our reader is tested against what other systems write.

Step 1: a disk with known files

mkdisk.sh replaces chapter 16's mkdisk.py. It makes a 64 MiB FAT32 volume – the whole disk, no partition table, one sector per cluster – and copies files onto it:

mkfs.fat -F 32 -s 1 -n YAKDISK -C "$IMG" $((64 * 1024)) >/dev/null

hello.txt, a long file name.txt, an empty file, big.bin (100 000 bytes, byte i = i % 253, so 196 clusters), docs/notes.txt, docs/deeper/end.txt, and a directory many/ with 40 files whose long names do not fit into one cluster of the directory. fsck.fat says about it: "50 files, 251/129022 clusters". From this chapter on, the host needs dosfstools and mtools; the course's CI job installs them.

Step 2: the boot sector

FatFs::mount reads sector 0 and takes the numbers it needs from the BPB: bytes per sector (offset 11), sectors per cluster (13), reserved sectors (14), number of FATs (16), total sectors (32), sectors per FAT (36), the root directory's first cluster (44), the label (71). Everything else follows from them – the data area starts after the reserved sectors and every FAT, and the number of clusters is what fits after it.

These numbers come from a disk, so mount does not trust them: a sector size other than 512, zeros where sizes belong, a volume bigger than the disk, a FAT too small for its clusters, a root directory outside the volume – each is an error. The test disk has 129 022 clusters, the number fsck.fat printed.

Step 3: following a chain

The FAT entry of cluster c is the 4 bytes at offset 4c of the FAT – one sector read:

#![allow(unused)]
fn main() {
    fn next(&mut self, cluster: u32) -> Result<u32> {
        let offset = cluster as u64 * 4;
        let mut sector = [0u8; SECTOR_SIZE];
        self.disk
            .read(self.fat_start + offset / SECTOR_SIZE as u64, &mut sector)?;
        Ok(u32_at(&sector, (offset % SECTOR_SIZE as u64) as usize) & FAT_MASK)
    }
}

(The top 4 bits of an entry are reserved, hence FAT_MASK. The name FAT32 promises 32 bits; it has 28.)

A chain read from a disk can be wrong – point outside the volume, or back to a cluster it has passed, and then a loop would follow it for ever. A chain can never be longer than the volume has clusters, so that is the limit:

#![allow(unused)]
fn main() {
    fn chain(&mut self, first: u32) -> Result<Vec<u32>> {
        let mut chain = Vec::new();
        if first == 0 {
            return Ok(chain); // an empty file has no cluster at all
        }
        let mut cluster = first;
        loop {
            if !self.valid(cluster) {
                return Err(FsError::Corrupt("a cluster chain that leaves the volume"));
            }
            if chain.len() == self.clusters as usize {
                return Err(FsError::Corrupt("a cluster chain that runs in a circle"));
            }
            chain.push(cluster);
            match self.next(cluster)? {
                next if next >= END_OF_CHAIN => return Ok(chain),
                next => cluster = next,
            }
        }
    }
}

Step 4: directory entries and their names

An entry has the 8.3 name in bytes 0–10 (8 for the name, 3 for the extension, filled with spaces), attributes in byte 11 (0x10: a directory, 0x08: the volume label), the first cluster in two halves (bytes 20 and 26) and the size (28). A first byte 0xE5 marks a deleted entry, 0 the end of the directory.

Two things make names more than 11 bytes. Case: "hello.txt" is stored as HELLO TXT; byte 12 says "base name and extension are lower case" (0x08 and 0x10, set by Windows NT and by mtools – a short name has no other place for it):

#![allow(unused)]
fn main() {
fn short_name(raw: &[u8], case: u8) -> String {
    let part = |bytes: &[u8], lower: bool| {
        let text = String::from_utf8_lossy(bytes);
        let text = text.trim_end();
        if lower {
            text.to_ascii_lowercase()
        } else {
            String::from(text)
        }
    };
    let mut name = part(&raw[..8], case & LOWER_CASE_BASE != 0);
    let extension = part(&raw[8..11], case & LOWER_CASE_EXT != 0);
    if !extension.is_empty() {
        name.push('.');
        name.push_str(&extension);
    }
    name
}
}

Long names (VFAT, Windows 95): "a long file name.txt" gets an 8.3 alias, ALONGF~1.TXT, and before it extra entries with the attributes 0x0F – read-only, hidden, system and volume label, a combination no old system expected, so they skipped these entries. Each holds 13 UTF-16 characters at scattered offsets, a number (the piece with the highest number comes first on the disk, marked with 0x40) and a checksum of the 8.3 name:

#![allow(unused)]
fn main() {
fn checksum(raw: &[u8]) -> u8 {
    raw[..11]
        .iter()
        .fold(0u8, |sum, &byte| sum.rotate_right(1).wrapping_add(byte))
}
}

The checksum protects against an old system that deleted or renamed the 8.3 entry and left the pieces behind: a long name counts only if it matches the 8.3 entry that follows it. The loop collects the pieces by their number:

#![allow(unused)]
fn main() {
                if attributes & ATTR_LONG_NAME == ATTR_LONG_NAME {
                    // the pieces come last one first: the first piece on the disk says how many there are
                    let number = (raw[0] & 0x1F) as usize;
                    if raw[0] & LAST_LONG_NAME_PIECE != 0 {
                        pieces = vec![[0xFFFF; 13]; number];
                        expected = raw[13];
                    }
                    if number == 0 || number > pieces.len() || raw[13] != expected {
                        pieces.clear(); // a piece without the others: ignore the long name
                        continue;
                    }
                    for (i, &offset) in LONG_NAME_CHARS.iter().enumerate() {
                        pieces[number - 1][i] = u16_at(raw, offset);
                    }
                    continue;
                }
}

and at the 8.3 entry decodes them, if the checksum fits – the name ends at a 0 or at the 0xFFFF padding:

#![allow(unused)]
fn main() {
                // the long name counts only if its checksum matches this 8.3 name - else it belonged to a deleted one
                let name = if !long.is_empty() && checksum(raw) == expected {
                    let units = long.iter().flatten().copied().take_while(|&u| u != 0 && u != 0xFFFF);
                    char::decode_utf16(units).map(|c| c.unwrap_or('?')).collect()
                } else {
                    short_name(&raw[..11], raw[12])
                };
}

Step 5: paths and files

lookup starts at the root directory and looks for each part of the path in turn – without regard to case, as FAT does: /HELLO.TXT is /hello.txt. read_file follows the file's chain and takes size bytes from it; the last cluster is only partly used:

#![allow(unused)]
fn main() {
    pub fn read_file(&mut self, path: &str) -> Result<Vec<u8>> {
        let file = self.lookup(path)?;
        if file.is_dir {
            return Err(FsError::IsADirectory);
        }
        let size = file.size as usize;
        let mut data = Vec::with_capacity(size);
        let mut buf = vec![0u8; self.cluster_size()];
        for cluster in self.chain(file.cluster)? {
            if data.len() == size {
                break; // a chain longer than the file: the rest is not ours to read
            }
            self.read_cluster(cluster, &mut buf)?;
            let take = (size - data.len()).min(buf.len());
            data.extend_from_slice(&buf[..take]);
        }
        if data.len() < size {
            return Err(FsError::Corrupt("a file whose chain is shorter than its size"));
        }
        Ok(data)
    }
}

Step 6: wiring it in

FatFs works on any BlockDevice and owns it. The kernel's one is fs::SystemDisk, which takes the lock of ahci::DISK for each access – so the disk stays where chapter 16 put it, and read in the shell still works:

#![allow(unused)]
fn main() {
impl BlockDevice for SystemDisk {
    fn sector_count(&self) -> u64 {
        ahci::DISK.lock().as_ref().map_or(0, |disk| disk.sector_count())
    }

    fn read(&mut self, lba: u64, buf: &mut [u8]) -> Result<(), BlockError> {
        ahci::DISK.lock().as_mut().ok_or(BlockError::Device)?.read(lba, buf)
    }
}
}

fs::mount() puts the volume into fs::FS. show_disk in main.rs calls it after ahci::init() and prints the volume, the root directory and /hello.txt; the test kernel mounts it before the tests:

#![allow(unused)]
fn main() {
    fs::mount().expect("a FAT32 volume on the disk");
}

The shell gets ls [dir] and cat <file> (shell.rs); without a current directory yet, a path without a leading / starts at the root. run-qemu.sh runs ./mkdisk.sh build/disk.img instead of mkdisk.py, and the AHCI tests of chapter 16 now check the boot sector instead of numbered sectors.

The tests

make test runs 122 tests in the kernel; new:

  • the_boot_sector_is_read (label, cluster size, 129 022 clusters as fsck.fat counts them);
  • the_root_directory_lists_short_long_and_lower_case_names, names_are_found_in_any_case, the_long_name_checksum (what checksum computes is what mtools wrote);
  • files_are_read (three levels deep, and the empty file), a_big_file_follows_its_chain (all 100 000 bytes checked), a_directory_can_span_clusters (many/: more than one cluster, 40 entries);
  • wrong_paths_are_errors, a_disk_without_fat32_is_refused, a_chain_in_a_circle_is_an_error_not_a_hang – the last two mount the test disk with a few sectors replaced in RAM (Patched): a zeroed boot sector, and a FAT entry of big.bin pointing back to its first cluster;
  • ls_and_cat_show_the_disk (the shell).

The boot check types ls and cat docs/notes.txt.

Run it

cd course/17-fat32
make run

After the PCI and AHCI lines:

Disk: QEMU HARDDISK on port 0, 131072 sectors (64 MiB)
FAT32: volume YAKDISK, 129022 clusters of 512 bytes
FAT32: / holds hello.txt, a long file name.txt, empty.txt, big.bin, docs/, many/
FAT32: /hello.txt says: Hello from the disk!

and in the shell:

yak> ls
      21  hello.txt
      38  a long file name.txt
       0  empty.txt
  100000  big.bin
   <dir>  docs/
   <dir>  many/
yak> cat docs/notes.txt
Notes, one directory down.

What can go wrong

  • Trusting the disk: a FAT entry that points back makes a naive loop run for ever – on a disk that came from somewhere else, or one a crash left half written. The chain limit turns it into an error. Without it, the test with the circular chain did not hang for ever here but ended worse: the Vec of clusters grew until the heap was full, and the kernel panicked on a failed allocation.
  • The 4 reserved bits: an entry read without FAT_MASK can look like a huge cluster number.
  • Clusters count from 2: cluster 2 is the first one of the data area. An off-by-two reads the wrong directory – and it may even look like one.
  • Lower case without byte 12: mtools stored hello.txt as HELLO TXT with the case flags, not with a long name. A reader that ignores byte 12 shows HELLO.TXT – still found, because names compare without case, but not what was written.
  • The order of a directory: entries come in the order they were made, not sorted – deeper/ was made before notes.txt was copied, so ls docs shows it first. My first version of the shell test expected the other order.
  • Slow by design: every FAT entry is one sector read, and cat big.bin reads the same few FAT sectors 196 times. Chapter 19 puts a block cache in between.

Experiments

  1. Run fsck.fat -v build/disk.img and mdir -i build/disk.img -/ ::/ on the host and compare with ls.
  2. Make a file with a name of more than 26 characters (three long name pieces) and ls it. Then one with a name in Greek or with an emoji: what does UTF-16 do with characters beyond U+FFFF?
  3. Delete a file on the host (mdel -i build/disk.img ::/hello.txt) and boot without mkdisk.sh making the disk anew. read the root directory's sector: where is the first byte 0xE5, and what happened to the long name pieces of a deleted long name?
  4. Keep the last FAT sector in FatFs (a one-sector cache). How many disk commands does cat big.bin save?

Next, chapter 18 writes: new files, appended data, deleted files – and fsck.fat must still be happy.