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(§or, (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 asfsck.fatcounts them);the_root_directory_lists_short_long_and_lower_case_names,names_are_found_in_any_case,the_long_name_checksum(whatchecksumcomputes 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 ofbig.binpointing 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
Vecof clusters grew until the heap was full, and the kernel panicked on a failed allocation. - The 4 reserved bits: an entry read without
FAT_MASKcan 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.txtasHELLO TXTwith the case flags, not with a long name. A reader that ignores byte 12 showsHELLO.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 beforenotes.txtwas copied, sols docsshows 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.binreads the same few FAT sectors 196 times. Chapter 19 puts a block cache in between.
Experiments
- Run
fsck.fat -v build/disk.imgandmdir -i build/disk.img -/ ::/on the host and compare withls. - Make a file with a name of more than 26 characters (three long name pieces) and
lsit. Then one with a name in Greek or with an emoji: what does UTF-16 do with characters beyond U+FFFF? - Delete a file on the host (
mdel -i build/disk.img ::/hello.txt) and boot withoutmkdisk.shmaking the disk anew.readthe root directory's sector: where is the first byte 0xE5, and what happened to the long name pieces of a deleted long name? - Keep the last FAT sector in
FatFs(a one-sector cache). How many disk commands doescat big.binsave?
Next, chapter 18 writes: new files, appended data, deleted files – and fsck.fat must still be happy.