Bugs in a teaching ext2 simulator, and the tests that keep them fixed

A teaching file system can look correct for years, because the demos only ever create a few small files. The bugs show up when you count: free blocks against the bitmap, bytes written against bytes read, entries created against entries listed. This post goes through the bugs I fixed in an ext2-style simulator written in C and what each one teaches about block file systems. Then it covers the three kinds of tests that now keep them fixed: a consistency check modelled on e2fsck, fault injection at every disk operation, and a fuzzer that compares every result with an in-memory model.

The code is my ext2-filesystem-simulator, a C23 rewrite of an open-source emulator that grew out of example code for a Linux kernel internals book: a 256 MiB disk held in memory and a small shell (format, mkdir, fill, cat, rm...). I first copied it in 2023 and rewrote it in October 2026, eleven fixes in all, each with a regression test. The original authors are credited in the repository; the code was meant to illustrate the layout, not to survive heavy use.

The layout in one table

The disk is 262,145 blocks of 1 KiB, split into 32 groups of 8,192 blocks. A group is 8,192 blocks because one 1 KiB bitmap block tracks 8 × 1,024 blocks. Every group starts with the same metadata, as in ext2's own layout:

Two facts from this table explain most of the bugs below. Free space is recorded three times: in the bitmaps, in each group descriptor's free count, and in the superblock's total. And every block number has to be translated into "which group, which bit", which is exactly where arithmetic goes wrong.

A macro without outer parentheses wrote into a data block

Removing a file has to clear each of its blocks in the block bitmap of the right group. The original code found that bitmap like this:

#define GET_DATA_GROUP(x) ((x) - 1)/(BLOCKS_PER_GROUP)

block_read(disk, BLOCKS_PER_GROUP * GET_DATA_GROUP(b) + BLOCK_BITMAP_BASE, block);

The macro has no parentheses around its whole body, so after expansion the multiplication runs first: BLOCKS_PER_GROUP * ((b) - 1) / BLOCKS_PER_GROUP, which is just b - 1. Instead of the bitmap block of the file's group, rm read block b - 1 + 3, the data block two past the one being freed, flipped one bit in it and wrote it back. The file system did not crash: it corrupted another file's contents and left the freed block marked as used, while the superblock counted it as free.

This is the classic reason the GCC preprocessor manual recommends parenthesizing both the arguments and the whole expansion. The rewrite does both, and computes groups in one place:

#define GET_DATA_GROUP(x) ((x) / BLOCKS_PER_GROUP)

The allocator only knew about 2,048 blocks

The disk reported itself full after about 1.5 MiB. The block allocator scanned the bitmap with this loop:

for (i = 0; i < fs->sb.block_per_group && i < MAX_BLOCK_SIZE / 4; i++)

MAX_BLOCK_SIZE / 4 is 256 bytes of bitmap, which is 2,048 bits. The bitmap it read was always the one of the superblock's group, group 0. With 517 metadata blocks at the start of that group, about 1,500 data blocks were ever reachable on a disk of 262,145. When those ran out, the function returned 0, which callers took as a valid block number: block 0 of the disk.

The fix searches every group, and running out of space returns an error. Its regression test writes 12 directories × 300 files × 12 KiB, about 42 MiB, and checks that the last file's first block lands in group 5.

Freeing with XOR is not idempotent

Bits were set and cleared with the same operation:

b_bitmap->block_bitmap[index] ^= (0x80 >> (bit % 8));

XOR toggles. Freeing a block that is already free marks it used again, and nothing reports it. With the macro bug above, that was not hypothetical. The rewrite has separate set_bit and clear_bit, and freeing refuses a block that is already free:

if (!test_bit(bitmap, bit))
    return EXT2_ERROR; /* already free: refuse instead of flipping it back to used */
clear_bit(bitmap, bit);

A double free is a symptom that the metadata is already inconsistent. Reporting it is more useful than silently making it worse.

The other fixes

The rest were smaller, but each would have been a long debugging session on a real disk:

• A directory past one block lost entries. When a directory's first block filled up, a new block was allocated but never linked into the directory's inode, so entries past the 29th disappeared from ls and lookup.
• The superblock struct was 1,020 bytes but copied as 1,024, overwriting the next field. Struct sizes are now checked at compile time: static_assert(sizeof(EXT2_SUPER_BLOCK) == MAX_BLOCK_SIZE, ...), and the same for inodes, descriptors and entries.
• cat crashed, because the read path passed the file system where the disk was expected. Reads and writes now handle any offset and length.
• Uninitialized memory: the root inode was built from stack garbage, format wrote one inode bitmap at a group chosen by an uninitialized variable, and names longer than 8.3 overflowed a buffer.
• The shell: exit called _exit and lost buffered output, and end of input repeated the last command forever.

Compiling with -Wall -Wextra -Wpedantic -Wconversion as errors, [[nodiscard]] on every status-returning function, and AddressSanitizer plus UBSan in the debug preset closes off whole categories of these.

Test 1: recount every bitmap after every test

e2fsck checks a file system in passes; pass 5 compares the bitmaps with the counts the metadata claims. The simulator's tests end with the same comparison:

bitmapFreeBlocks = BLOCKS_PER_GROUP - count_bits(block, BLOCKS_PER_GROUP);
if (gd->free_blocks_count != bitmapFreeBlocks || gd->free_inodes_count != bitmapFreeInodes)
    ok = false;
/* ...then the sum over all groups must equal the superblock's totals */

It is about 60 lines, and it would have caught the macro bug on the first test that removed a file, because the freed block stayed set in the bitmap while the superblock counted it as free. Asserting on an invariant catches bugs no one wrote a test for, which is why every test calls it, not just the ones about allocation.

Test 2: fail the disk at each operation in turn

The disk sits behind a read/write interface, so a test can swap in one that fails after a budget of sector operations. A scenario of ordinary steps (format, mount, mkdir, create, write, read, remove) is first run once to count its operations, then replayed with the failure placed at operation 0, 1, 2 and so on up to the total:

for (budget = 0; budget < total; budget++) {
    g_budget = -1;                    /* format on a healthy disk */
    CHECK(ext2_format(&disk) == EXT2_SUCCESS);
    g_budget = budget;                /* then fail at this operation */
    steps = run_scenario(&disk);
    CHECK(steps < completeSteps);     /* the failure must surface as an error */
}

Every step must return an error instead of crashing, and the sanitizers watch for reads of memory the code should not touch. This matters because the original code ignored most results of block_read and block_write; set_block_bitmap, declared to return int, had no return statement at all.

Test 3: a fuzzer with a model of what should be there

The fuzzer reads its input as a sequence of operations (mkdir, rmdir, create, write, read back, rm) on four directory names and eight file names. Next to the real file system it keeps a model: which directories exist, and for each file its size and bytes. After every operation it checks two things.

First, success and failure must both match the model. Creating a file must succeed exactly when the parent exists and the file does not:

FUZZ_ASSERT((result == EXT2_SUCCESS) == (parentExists && !file->exists), "create %u/%s", p, name);

Checking only that successes are correct misses the bugs where an operation fails when it should not, or succeeds when it should have refused, such as writing past the 12 KiB a file can hold.

Second, the bitmaps must still agree with the counts, using the same check as above. Reads compare every byte with the model.

Under ctest the fuzzer replays a small corpus of saved inputs and 200 random ones; with Clang it builds as a libFuzzer target, and CI fuzzes for two minutes on each run.

What these tests do not cover

• Consistency after a failure. Fault injection checks that errors are reported, not that the disk is still consistent afterwards. Without a journal, a write that fails halfway through an operation can leave the counts wrong, as it could on ext2 itself.
• Only counts, not reachability. The checker does pass 5's job. It does not walk the directory tree to find blocks that are marked used but belong to no inode, which is what earlier e2fsck passes do.
• The model only knows what it tracks. Names, sizes and contents are checked; timestamps and link counts are not.
• It is not ext2 on disk. Directory entries are fixed 32-byte records with 8.3 names, and files use direct blocks only, so a file holds at most 12 KiB.

Summary

If you have tested a storage layer with a model-based fuzzer, I'd love to compare notes on what your model tracked. My email is on the home page.