Commentary: toy-filesystem

An inode table, a block bitmap and 32 data blocks inside one flat file — where deleting a file writes nothing at all, and a three-byte file you own hands you 61 bytes of it back through read(). A study guide for tinyfs.py.

cd toy-filesystem
python3 demo.py         # the aha (§6)
python3 test_tinyfs.py  # pins every number this page claims
xxd disk.img | less     # the entire filesystem, after a demo run

1. Orientation

This toy is a filesystem: a superblock, an inode table, a free-space bitmap and an array of fixed-size data blocks, all laid out inside one ordinary file. It supports write, read, ls, rm and truncate, and it has no directories, no permissions and no journal.

The shortest path to the result is the CLI:

python3 tinyfs.py format
printf 'ROOT PASSWORD: hunter2-correct-horse\nSSN: 123-45-6789\nCARD: 4111 1111 1111 1111 exp 09/29 cvv 402\n' | python3 tinyfs.py write secret.txt
python3 tinyfs.py ls
python3 tinyfs.py rm secret.txt
printf 'ok\n' | python3 tinyfs.py write notes.txt
python3 tinyfs.py ls
python3 tinyfs.py read notes.txt
python3 tinyfs.py truncate notes.txt 64
python3 tinyfs.py read notes.txt

notes.txt is a file you created, you own, and never wrote anything into except ok\n. The last command is read. That is the toy.

By the end you should be able to:

• lay out a filesystem on a flat file — superblock, inode table, block bitmap, data blocks — and compute any byte's address by hand;
• say exactly which disk writes rm performs (none) and why that is a deliberate choice rather than an oversight;
• explain slack space: the gap between a file's length and the end of its last block, and why that gap is not empty;
• state what access is needed to read it here (the filesystem's own read(), on your own file) versus what you'd need on a real system (a raw device and root);
• price the two obvious fixes in disk writes, and name the third one that real filesystems actually ship.

2. The problem this mechanism exists to solve

A filesystem has to answer one question fast: given a name and an offset, which bytes on the device? Everything in the layout serves that. Fixed-size inodes mean inode 5 is at a computable address. A block bitmap means "find free space" is a scan of 32 bytes rather than a walk of the whole disk. Fixed-size blocks mean the file's nth byte is at data_start + blocks[n // block_size] * block_size + n % block_size — one multiply, no search.

Fixed-size blocks buy that speed with a specific waste: a file's last block is almost never full. A 3-byte file in a 64-byte-block filesystem occupies a whole block; 61 bytes go unused. That gap has a name — slack — and the usual thing said about it is that it wastes disk. This toy is about the other thing about it.

The competing goals that make more than one design defensible:

• rm should be instant. Users delete a 10 GB directory and expect the prompt back. Making delete proportional to file size rather than to metadata size is a real cost users would notice.
• Reads should never see another file's bytes. POSIX makes this a contract, not a nicety: ftruncate growing a file says the extended part "reads as null bytes." A filesystem that hands back whatever was there before has broken a documented promise, not merely been untidy.
• Blocks should be reused promptly. An allocator that avoids recently freed blocks fragments the disk and eventually has nowhere left to go.

You cannot have all three for free. Something has to write zeros somewhere, and the entire design question is where you put that cost. This toy puts it nowhere by default, so you can watch what falls out.

3. Background you need

The two that carry the result are slack and ftruncate semantics. Slack is where the old bytes physically survive; ftruncate is the legal, unprivileged operation that moves a file's length over them. Neither is exotic. The result is what happens when a system implements the first without honouring the second.

4. The mental model

Before any code. The whole disk, as laid out by format() with the default geometry:

5. Reading the source

275 lines, two classes and a main. Read it in this order.

5.1 rm — the four lines that write nothing

    def rm(self, name):
        """Free the blocks, clear the inode. Note what is missing: any write
        to the data region at all, unless zero_on_free is set.
        """
        i, ino = self.lookup(name)
        if ino is None:
            raise FileNotFoundError(name)
        for b in ino.blocks[:self.nblocks(ino.size)]:
            self.free_block(b)
        self.put_inode(i, Inode())

put_inode(i, Inode()) writes 45 zero bytes over the inode record, and free_block writes one byte in the bitmap per block. Both are metadata. Nothing in this function touches the data region, and that is not an omission — it is the reason rm is O(1) in the file's size. Deleting a 2 GB file costs the same as deleting a 2-byte one.

Watch what the disk looks like immediately afterwards (§6.2 has the run): the inode is 45 zero bytes, the bitmap is all zeros, and block 0 is still the password.

5.2 alloc_block and free_block — the bitmap, and first fit

    def alloc_block(self):
        """First fit: the lowest-numbered free block wins. Deterministic,
        two lines, and the reason a just-freed block comes straight back.
        """
        bm = self.bitmap()
        for b in range(self.num_blocks):
            if not bm[b]:
                bm[b] = 1
                self.put_bitmap(bm)
                if self.zero_on_alloc:
                    self.put_block(b, b"\0" * self.block_size)
                return b
        raise OSError("no free blocks")

    def free_block(self, b):
        bm = self.bitmap()
        bm[b] = 0
        self.put_bitmap(bm)
        if self.zero_on_free:
            self.put_block(b, b"\0" * self.block_size)

These are a matched pair, and the two if statements are the toy's only policy knobs. Both default to off, and off is what every mainstream filesystem does literally — see §7.4 for what they do instead.

The for b in range(self.num_blocks) is first fit, and it is doing more work in the story than it looks. It guarantees the lowest free block wins, which means the block you just freed is the block you get next. That is excellent for locality and terrible for secrets, and §6.5 shows an allocator that makes the same demo leak nothing at all without any zeroing — by refusing to reuse.

5.3 write — where the slack is created

        blocks = []
        for off in range(0, len(data), self.block_size):
            b = self.alloc_block()
            blocks.append(b)
            # Only len(data)-off bytes are written. Whatever sat in the rest
            # of this block is still sitting there. That is the whole toy.
            self.put_block(b, data[off:off + self.block_size])
        self.put_inode(i, Inode(1, len(data), name.encode(), blocks))

data[off:off + self.block_size] is a Python slice, so for the last block it is short: writing b"ok\n" writes exactly three bytes at the start of block 0 and leaves bytes 3–63 alone.

This is the single most important divergence from a real disk, and it cuts against the toy's own result — a real block device cannot write three bytes. The smallest unit it accepts is a sector (512 B, or 4 KiB on modern drives), so the kernel must assemble a full block in memory and write all of it. What it assembles from is a page-cache page, and a page handed to a file for the first time is zero-filled. That, not any explicit erase, is why the tail of a short file on a real system reads as zeros. §6.6 measures it.

5.4 read — the cap that makes the leak need a second step

    def read(self, name):
        i, ino = self.lookup(name)
        if ino is None:
            raise FileNotFoundError(name)
        out = b"".join(self.block(ino.blocks[n])
                       for n in range(self.nblocks(ino.size)))
        return out[:ino.size]      # the cap that hides the tail

read fetches whole blocks — it cannot do otherwise, the device is block-addressed — and then throws the tail away. Delete the [:ino.size] and the toy leaks with no truncate at all; that is the counterfactual in §6.4, and it returns 64 bytes for a 3-byte file.

So the cap is load-bearing, and it is also the only thing standing between a fresh write and a disclosure. It is a correct line. It is just not a sufficient one, because it derives its authority entirely from ino.size being trustworthy — and the next function is the one that sets ino.size.

5.5 truncate — the crack

    def truncate(self, name, newsize):
        """POSIX `ftruncate`: any owner may resize their own file, and the
        bytes a grow exposes are required to read back as zeros. This
        implementation just moves the size field -- which is the bug.
        """
        i, ino = self.lookup(name)
        if ino is None:
            raise FileNotFoundError(name)
        need, have = self.nblocks(newsize), self.nblocks(ino.size)
        if need > self.direct:
            raise OSError("file too large: %d direct blocks" % self.direct)
        # Trim first: unpack always hands back `direct` entries, and the ones
        # past the file's length are whatever the last, longer file left.
        blocks = ino.blocks[:have]
        for _ in range(have, need):
            blocks.append(self.alloc_block())
        for b in blocks[need:]:
            self.free_block(b)
        ino.blocks = blocks[:need]
        ino.size = newsize
        self.put_inode(i, ino)

Every line here is defensible on its own. Growing a file should allocate the blocks it now needs; shrinking should free them; ino.size = newsize is what "truncate" means. What is missing is the one thing ftruncate(2) promises: "If the file previously was shorter, it is extended, and the extended part reads as null bytes." Nothing in this function writes a null byte anywhere.

The fix is three lines and costs one block write, no matter how large the grow — §6.7. It is not here because the toy's job is to show you what its absence looks like.

One aside worth having, since it is a bug I actually hit while building this: the blocks = ino.blocks[:have] trim. Inode.unpack always returns direct block numbers, because the record is fixed-size, and the entries past the file's real length are whatever the previous, longer file left in that inode. Growing without trimming appends after the stale entries, and the new blocks land past index 3 where nothing reads them. It is the same "leftover bytes in a fixed-size container" bug as the one the toy is about, one level up in the metadata.

6. The demo, and what it proves

python3 demo.py. Sections A–E below are its real output, in order.

6.1 The trace, and the 61 bytes

The arithmetic, so no number here is unexplained:

• secret.txt is 98 bytes. ⌈98 / 64⌉ = 2 blocks, so it takes blocks 0 and 1 (first fit on an empty disk). Block 1 holds 98 − 64 = 34 bytes and has 30 bytes of its own slack, which on a freshly formatted image is zeros.
• rm frees both: free blocks go 30 → 32, at a cost of 0 block writes.
• notes.txt is 3 bytes. ⌈3 / 64⌉ = 1 block, and first fit returns block 0 — the front of the password.
• The write covers bytes 0–2. Slack is 64 − 3 = 61 bytes, holding SECRET[3:64] unchanged.
• truncate sets size = 64, so read returns out[:64] instead of out[:3], and 3 + 61 = 64.

6.2 The control: without the truncate there is no leak

test_the_honest_read_path_leaks_nothing in test_tinyfs.py does exactly the steps above, stops before the truncate, and asserts:

    got = fs.read("notes.txt")
    assert got == b"ok\n" and len(got) == 3            # capped at inode.size

Three bytes, zero leaked. Step 5 in the transcript is that same check inside the demo. The disclosure is not "reading a file shows you old data" — the read path is correct. It is that the length is metadata a user controls, and the read path trusts it.

Meanwhile, the disk after step 3:

Forty-five zero bytes of inode, an all-zero bitmap, and the file. That is what "deleted" means. The same script counts what is left:

(2,472 = 32 superblock + 8 × 45 inode table + 32 bitmap + 32 × 64 data.)

6.3 Both fixes work, and the bill is on different lines

Demo sections B, C and D:

61 → 0 either way. The difference is entirely in who pays:

• zero_on_free makes rm proportional to the file's size: 4096 / 64 = 64 blocks, so 64 writes on an operation that previously did none. Deleting a 1 TB file now writes 1 TB. This is shred(1)'s bill, and it is why rm(1) doesn't do it.
• zero_on_alloc doubles the write path: 64 → 128, because every block is written twice, once with zeros and once with data. It is the wrong place to pay in this toy, since the very next line usually overwrites the whole block. On real hardware it is nearly free precisely because the block is written once anyway (§5.3), which is why the real answer looks like this one.

Neither fix is retroactive. Mount with zero_on_free after the delete already happened and you get nothing:

6.4 Counterfactual: delete the [:ino.size] cap

read rewritten to return the whole blocks:

The truncate becomes unnecessary — a plain read of a 3-byte file returns 64 bytes. This is worth running because it locates the bug precisely: the toy has two independent ways to expose slack, read ignoring the size and truncate moving it, and only the second one is present in the shipped code. A real filesystem must get both right.

6.5 Counterfactual: the allocator decides whether there is anything to leak

Bump is a subclass whose allocator keeps a cursor and never hands back a block below it:

Same rm writing nothing, same missing zero in truncate, same 61 bytes of slack — and no disclosure, because notes.txt landed on block 2, which nothing had ever written. This is the counterfactual that reframes the result: the leak is not caused by rm leaving data behind. It is caused by rm leaving data behind and the allocator being eager to reuse.

It is also a fix nobody would ship: never reusing blocks means running out of disk with a mostly-empty filesystem. Log-structured filesystems come closest to it, and pay for it with a cleaner.

6.6 The same trace against the real filesystem underneath

The identical sequence through real syscalls (write, fsync, unlink, ftruncate, read) on the host's APFS volume, with a 6,272-byte secret and a 4,096-byte grow:

Zero non-zero bytes in 4,093 bytes of exposed tail. The real system honours the contract the toy breaks. It does not do it by zeroing on free — APFS is copy-on-write and its rm is also cheap — it does it by never letting an uninitialised block reach a read, which is §7.4.

6.7 The third fix: zero only what the grow exposes

A subclass that zeroes the tail of the last block inside truncate, before moving the size:

One block write, on an operation nobody performs in a hot loop, versus 64 on every rm. This is the fix a real implementation ships, and the reason it was left out of tinyfs.py is only that its absence is the demo.

6.8 The boundary condition — where the effect vanishes

Demo section E runs the whole trace again for four different lengths of the new file:

So a reader can place their own system by asking four questions:

1. Is the write block-aligned? A database writing 8 KiB pages onto 4 KiB blocks has no slack, ever. This whole class of bug is invisible to it.
2. Does the allocator reuse eagerly? §6.5 — a bump or log-structured allocator removes the recycled block from the story.
3. Does something zero the block before a read can reach it? On Linux and macOS, yes, always, and by a cheaper route than either flag here (§7.4). This is where the toy is a museum piece rather than a warning.
4. Is the data encrypted at rest with a key that dies with the file? Then the recycled block is ciphertext under a discarded key.

And where the boundary is not. SSD TRIM is orthogonal, and it is worth saying so because it gets offered as a defence. TRIM tells the drive that a freed block need no longer be preserved, which protects against someone desoldering the flash and reading the raw cells. It does nothing about the case above, where the filesystem hands you the block back through read() — at that point the block is allocated, live, and yours; there is nothing for TRIM to discard.

7. Design decisions and roads not taken

7.1 Why the leak needs a truncate rather than just a read

The strongest possible version of this demo would be a plain read that returns the neighbours' bytes, and it was available: drop [:ino.size] (§6.4) and the toy leaks 64 bytes on a 3-byte file. It was rejected because it makes the toy prove nothing. Every filesystem caps reads at the file length; a toy that omits the cap is demonstrating its own bug, not the mechanism's. Requiring the truncate keeps the read path correct and puts the whole weight of the result on the interaction between recycled blocks and a user-controlled length, which is the real thing.

7.2 One byte per block in the bitmap, not one bit

A real bitmap is bits — that's the whole point of the name, and 32 blocks would fit in 4 bytes rather than 32. Bytes were chosen because bitmap()[b] is readable in a transcript ([0, 0, 0, 0, 0, 0, 0, 0] in §6.2) and bit twiddling adds three lines that teach nothing about this mechanism. The cost is the only thing lost: at 1 bit/block, a 1 TiB disk with 4 KiB blocks needs 32 MiB of bitmap; at 1 byte/block, 256 MiB. That ratio is why real ones use bits.

7.3 Four direct block pointers, no indirect blocks

direct=4 caps a file at 256 bytes. Real inodes have 12 direct pointers plus single, double and triple indirect blocks (or, in ext4 and APFS, extents — an (offset, length) pair, so a contiguous file needs one entry instead of thousands). Indirect blocks would double the toy's length and add nothing: the aha needs one block to be recycled, and the recycling machinery is identical whether the block number came from inode.blocks[2] or from a pointer block. §9 Q1 shows the leak scaling to the whole file anyway.

7.4 Why neither shipped flag is what real filesystems do

Both flags work (§6.3) and both are the wrong shape:

• Zeroing on free makes delete O(size). This is what shred and diskutil secureErase are for, and they exist as separate commands precisely because nobody wants that on every rm.
• Zeroing on allocate doubles the write path in this toy. On real hardware the equivalent is nearly free, because a partial write already has to assemble a full block in a page-cache page and that page is zero-filled — the zeroing happens in RAM, and the disk write happens once.

What ext4 does for the preallocation case is better than either: an extent whose length field exceeds 32768 is flagged unwritten, and a read of it returns zeros from the flag, with no disk traffic at all. fallocate(2) documents the same trick for FALLOC_FL_ZERO_RANGE: the range is "not physically zeroed out on the device (except for partial blocks at the either end of the range)" — note the parenthesis, which is precisely the slack case in this toy, and precisely the case that is physically zeroed.

The road genuinely not taken is the one someone proposed. In 2012 Zheng Liu sent an RFC adding FALLOC_FL_NO_HIDE_STALE, letting an application ask for preallocated blocks without the zero guarantee, because the unwritten→written conversion was expensive: a random-write benchmark went from 76 seconds to 18. The patch's own posting conceded that "the malicious user could use this flag to get other user's data if (s)he doesn't do a initialization before reading this file." Ric Wheeler's reply was "I really, really don't like exposing stale data to users and applications"; Ted Ts'o was more open but wanted it behind CAP_SYS_RAWIO. The flag is not in fallocate(2) today. Someone offered to sell exactly this toy's behaviour for a 4× speedup, and the answer was no.

7.5 Names in the inode, no directories

A real directory is a file whose contents are name → inode-number pairs, which is elegant and, for this toy, entirely beside the point: it would add a level of indirection to every operation and not change a single byte of the result. The 24-byte name field in the inode is the cheat that buys ls for one line — at the price of a hard 24-byte limit on names, and of making a rename a write to the inode rather than to a directory.

8. What's simplified vs. the real thing

9. Check yourself

Answer before expanding. Each answer is derivable from the source, and each was verified by running it.

10. Further reading

Every link below was fetched and confirmed live when this was written.

• ftruncate(2) — the one sentence the toy breaks: "If the file previously was shorter, it is extended, and the extended part reads as null bytes ('\0')." Read it next to §5.5.
• fallocate(2) — the flag list, with no FALLOC_FL_NO_HIDE_STALE in it, and the FALLOC_FL_ZERO_RANGE note that blocks are "not physically zeroed out on the device (except for partial blocks at the either end of the range)". That parenthesis is this toy's 61 bytes, in production wording.
• LWN: Allocating uninitialized file blocks — the 2012 argument in full: 76 s → 18 s on the benchmark, Ric Wheeler's "I really, really don't like exposing stale data to users and applications," Ted Ts'o's CAP_SYS_RAWIO compromise. §7.4's story.
• The RFC patch itself — Zheng Liu's posting, including the author's own note that a malicious user could use the flag to read other users' data.
• ext4 inode extents — where the unwritten bit actually lives: "If the value of this field is > 32768, the extent is uninitialized." One bit of metadata doing the job that costs the toy 64 block writes.
• Data remanence — the general phenomenon, and the clearest statement of the everyday version: filesystems "simply remove the file's entry from the file system directory because this requires less work and is therefore faster, and the contents of the file — the actual data — remain on the storage medium."
• Apple: Volume encryption with FileVault — why §6.6's APFS run is doubly safe: "all APFS volumes are created with a volume encryption key by default," and deleting a volume securely deletes that key in the Secure Enclave rather than erasing any blocks. Deletion by key destruction, which is §9 Q6's answer.
• inode — if the fixed-size record in §5 was new, this is the orientation, including the real fields this toy dropped.