A Simple Filesystem

A disk is just a sequence of bytes, but filesystems read and write it in fixed-size blocks.
A superblock holds the metadata needed to interpret everything else on the disk.
A bitmap records which blocks are in use and which are free.
An inode stores a file's metadata and the numbers of the blocks holding its contents.
A directory is a file whose contents map names to inode numbers.
Paths are resolved by walking from the root directory down to the target entry.

Every program reads and writes files, but few of us ever stop to ask what happens in between. When we open a file and then read from it, some piece of software has to figure out where our data lives on a disk, find the bytes, and hand them back to us. This chapter builds a tiny filesystem to show how that piece of software works.

We will not touch a real disk. Instead, we will use an in-memory array of bytes to simulate one. As Chapter 17 explains, bytes are just numbers, so a bytearray in Python is a perfectly good stand-in for the raw storage of a physical device. The ideas we build here—blocks, superblocks, inodes, directories—are the same ones used by real filesystems such as ext4 and NTFS.

A Disk of Bytes

A physical disk stores a long sequence of bytes, but reading and writing them one at a time would be painfully slow. Real filesystems therefore group bytes into blocks of a fixed size and always read or write whole blocks at once. Our simulated disk does the same thing:

class Disk:
    """A fixed-size array of bytes divided into fixed-size blocks."""

    def __init__(self, block_size, block_count):
        self.block_size = block_size
        self.block_count = block_count
        self._data = bytearray(block_size * block_count)

    @property
    def size(self):
        """The total number of bytes on the disk."""
        return len(self._data)

    def read_block(self, block_number):
        """Return the contents of a block as a ``bytes`` object."""
        self._check_block(block_number)
        start = block_number * self.block_size
        return bytes(self._data[start : start + self.block_size])

    def write_block(self, block_number, data):
        """Overwrite a block with ``data``, padding with zero bytes as needed."""
        self._check_block(block_number)
        if len(data) > self.block_size:
            raise ValueError("data does not fit in a single block")
        start = block_number * self.block_size
        self._data[start : start + self.block_size] = b"\x00" * self.block_size
        self._data[start : start + len(data)] = data

    def _check_block(self, block_number):
        if not (0 <= block_number < self.block_count):
            raise ValueError(f"block number {block_number} out of range")

A Disk is just a bytearray of block_size * block_count bytes. read_block returns one block's worth of bytes, and write_block overwrites a block, padding with zero bytes if the data we supply is shorter than a block. The _check_block method ensures that block numbers are in the range 0 to block_count - 1.

Why Fixed-Size Blocks?

Grouping bytes into blocks trades a little wasted space for simplicity and speed. If every block is the same size, we can find block $N$ by multiplying instead of searching: it always starts at byte $N \times B$, where $B$ is the block size. The wasted space comes from files that don't fill their last block, but the trade is almost always worthwhile.

The Superblock

The first thing our filesystem needs is a way to recognize itself. If we are handed a bytearray full of bytes, how do we know whether it is one of our filesystems or just random garbage? The answer is to store some metadata in the first block:

BLOCK_SIZE = 32
NUM_BLOCKS = 64
DISK_SIZE = BLOCK_SIZE * NUM_BLOCKS

INODE_SIZE = BLOCK_SIZE
NUM_INODES = 16

SUPERBLOCK_BLOCK = 0
INODE_TABLE_START = 1
DATA_START = INODE_TABLE_START + NUM_INODES

MAX_FILE_BLOCKS = 6
NAME_LEN = 12

MAGIC = 0x53504653  # the ASCII bytes "SPFS"

SUPERBLOCK = struct.Struct(">IIII")
INODE = struct.Struct(">IIIIIIII")
DIR_ENTRY = struct.Struct(">12sI")

KIND_FREE = 0
KIND_FILE = 1
KIND_DIR = 2

ROOT_INODE = 0

The constant MAGIC is a number chosen so that when it is packed into four bytes it spells "SPFS". struct.Struct describes how to pack and unpack values; the format string ">IIII" means "four unsigned 32-bit integers in big-endian order", a topic we first met in Chapter 17. Our superblock therefore records:

the magic number used to identify the filesystem;
the block size and the number of blocks;
the number of inodes (which we will meet shortly).

The format method writes a fresh superblock and initializes everything else:

    def format(self):
        """Initialize the disk to hold an empty filesystem."""
        self.bitmap[:] = b"\x00" * NUM_BLOCKS
        for block in range(SUPERBLOCK_BLOCK, DATA_START):
            self.bitmap[block] = 1

        packed = SUPERBLOCK.pack(MAGIC, BLOCK_SIZE, NUM_BLOCKS, NUM_INODES)
        self.disk.write_block(SUPERBLOCK_BLOCK, packed)

        empty = INODE.pack(0, KIND_FREE, *([0] * MAX_FILE_BLOCKS))
        for i in range(NUM_INODES):
            self.disk.write_block(INODE_TABLE_START + i, empty)

        self._write_inode(ROOT_INODE, 0, KIND_DIR, [0] * MAX_FILE_BLOCKS)

Formatting first clears the bitmap (which we discuss next) and marks the blocks that hold the superblock and the inode table as being in use. It then writes the superblock into block 0, fills every inode with zeros to mark it as free, and creates the root directory in inode 0.

Free Blocks

A filesystem must remember which blocks are occupied and which are available. The simplest way to do this is a bitmap: an array with one entry per block that is 1 if the block is in use and 0 if it is free.

    def _allocate_block(self):
        for block in range(DATA_START, NUM_BLOCKS):
            if self.bitmap[block] == 0:
                self.bitmap[block] = 1
                return block
        raise OSError("disk is full")

    def _free_block(self, block):
        self.bitmap[block] = 0

    def _allocate_inode(self, kind):
        for i in range(NUM_INODES):
            if self._read_inode(i)["kind"] == KIND_FREE:
                self._write_inode(i, 0, kind, [0] * MAX_FILE_BLOCKS)
                return i
        raise OSError("no free inodes")

_allocate_block scans the bitmap for the first free block. _free_block simply marks a block as free again. _allocate_inode does the same job for inodes: it finds an inode whose kind is KIND_FREE and initializes it.

In Memory, Not on Disk

We keep the bitmap in a Python bytearray inside the FileSystem object. A real filesystem would store its bitmap in a reserved region of the disk so that it survives a restart. Turning our in-memory bitmap into an on-disk one is a good exercise.

Inodes and Files

A file is more than its contents. It also has a size, a kind (file or directory), and—crucially—a list of the blocks that hold its data. We store this metadata in a structure called an inode:

    def _read_inode(self, inode_number):
        self._check_inode(inode_number)
        raw = self.disk.read_block(INODE_TABLE_START + inode_number)
        size, kind, *blocks = INODE.unpack(raw)
        return {"size": size, "kind": kind, "blocks": blocks}

    def _write_inode(self, inode_number, size, kind, blocks):
        self._check_inode(inode_number)
        raw = INODE.pack(size, kind, *blocks)
        self.disk.write_block(INODE_TABLE_START + inode_number, raw)

    def _check_inode(self, inode_number):
        if not (0 <= inode_number < NUM_INODES):
            raise ValueError(f"inode number {inode_number} out of range")

Each inode is exactly INODE_SIZE bytes long, and because INODE_SIZE equals BLOCK_SIZE, one inode fits in one block. Inode $i$ therefore lives in block INODE_TABLE_START + i. The inode stores the file's size, its kind, and up to MAX_FILE_BLOCKS block numbers.

Reading and writing a file's contents means following those block numbers:

    def _read_data(self, inode_number):
        inode = self._read_inode(inode_number)
        chunks = []
        for block in inode["blocks"]:
            if block == 0:
                break
            chunks.append(self.disk.read_block(block))
        return b"".join(chunks)[: inode["size"]]

    def _write_data(self, inode_number, data):
        inode = self._read_inode(inode_number)
        for block in inode["blocks"]:
            if block != 0:
                self._free_block(block)

        blocks = []
        for offset in range(0, len(data), BLOCK_SIZE):
            block = self._allocate_block()
            self.disk.write_block(block, data[offset : offset + BLOCK_SIZE])
            blocks.append(block)
        blocks += [0] * (MAX_FILE_BLOCKS - len(blocks))

        self._write_inode(inode_number, len(data), inode["kind"], blocks)

_read_data reads each block listed in the inode, joins them together, and trims the result to the file's recorded size. _write_data does the reverse: it frees the file's old blocks, allocates fresh ones, and copies the data into them one block at a time.

This indirection—storing pointers to data rather than the data itself—is the heart of how filesystems work. The inode is small and fixed in size, but the file it describes can be larger and scattered across the disk.

Directories

If a file is "a list of blocks", then a directory is "a file whose contents are a list of names". Each directory entry maps a name to an inode number:

    def _pack_dir_entry(self, name, inode_number):
        name_bytes = name.encode("utf-8")
        if len(name_bytes) > NAME_LEN:
            raise ValueError(f"name too long: {name}")
        return DIR_ENTRY.pack(name_bytes, inode_number)

    def _unpack_dir_entry(self, raw):
        name_bytes, inode_number = DIR_ENTRY.unpack(raw)
        name = name_bytes.split(b"\x00")[0].decode("utf-8")
        return name, inode_number

    def _list_dir(self, inode_number):
        data = self._read_data(inode_number)
        entries = []
        for offset in range(0, len(data), DIR_ENTRY.size):
            name, child = self._unpack_dir_entry(
                data[offset : offset + DIR_ENTRY.size]
            )
            entries.append((name, child))
        return entries

    def _dir_add(self, dir_inode, name, child_inode):
        data = self._read_data(dir_inode)
        raw = self._pack_dir_entry(name, child_inode)
        self._write_data(dir_inode, data + raw)

    def _dir_remove(self, dir_inode, name):
        kept = [
            self._pack_dir_entry(n, child)
            for (n, child) in self._list_dir(dir_inode)
            if n != name
        ]
        self._write_data(dir_inode, b"".join(kept))

A directory entry is 16 bytes: 12 for the name (padded with zero bytes if it is shorter) and 4 for the inode number. _list_dir reads the directory's data and unpacks it into a list of (name, inode) pairs. _dir_add and _dir_remove add and remove entries by rewriting the directory's contents.

Notice that we never check that a directory entry is "really" a directory: to the filesystem, a directory is just a file with a particular structure. This is a small example of a larger design idea that we first met in Chapter 16: a program is just another kind of data.

Paths and Operations

The last piece of the puzzle is turning a path like /docs/hello.txt into the file it names. We do this by walking from the root directory down through each component of the path:

    def _split(self, path):
        if not path.startswith("/"):
            raise ValueError("absolute path required")
        if path == "/":
            raise ValueError("the root directory cannot be split")
        parent, _, name = path.rpartition("/")
        return (parent if parent != "" else "/"), name

    def _lookup(self, path):
        current = ROOT_INODE
        for name in [p for p in path.split("/") if p]:
            child = None
            for (entry_name, child_inode) in self._list_dir(current):
                if entry_name == name:
                    child = child_inode
                    break
            if child is None:
                return None
            current = child
        return current

_lookup starts at ROOT_INODE and, for each name in the path, looks it up in the current directory. If any component is missing, it returns None. _split separates a path into its parent directory and final name.

The public methods are then straightforward compositions of the pieces we have already built:

    def create(self, path):
        parent, name = self._split(path)
        parent_inode = self._lookup(parent)
        inode = self._allocate_inode(KIND_FILE)
        self._dir_add(parent_inode, name, inode)
        return inode

    def mkdir(self, path):
        parent, name = self._split(path)
        parent_inode = self._lookup(parent)
        inode = self._allocate_inode(KIND_DIR)
        self._dir_add(parent_inode, name, inode)

    def read(self, path):
        inode = self._lookup(path)
        if inode is None:
            raise FileNotFoundError(path)
        return self._read_data(inode)

    def write(self, path, data):
        inode = self._lookup(path)
        if inode is None:
            inode = self.create(path)
        self._write_data(inode, data)

    def listdir(self, path):
        inode = self._lookup(path)
        if inode is None:
            raise FileNotFoundError(path)
        return [name for (name, child) in self._list_dir(inode)]

    def remove(self, path):
        parent, name = self._split(path)
        parent_inode = self._lookup(parent)
        inode = self._lookup(path)
        if inode is None:
            raise FileNotFoundError(path)
        info = self._read_inode(inode)
        for block in info["blocks"]:
            if block != 0:
                self._free_block(block)
        self._write_inode(inode, 0, KIND_FREE, [0] * MAX_FILE_BLOCKS)
        self._dir_remove(parent_inode, name)

create and mkdir allocate an inode and add an entry to the parent directory. write creates the file if it doesn't exist and then stores the data. read, listdir, and remove look up an inode and act on it. None of these methods is more than a few lines long because each one is standing on the shoulders of the ones below it.

Testing

As in earlier chapters, we test our code with small examples rather than a real disk:

def test_write_block_pads_with_zeros():
    disk = Disk(block_size=16, block_count=4)
    disk.write_block(0, b"hello")
    assert disk.read_block(0) == b"hello" + b"\x00" * 11

and:

def make_fs():
    fs = FileSystem()
    fs.format()
    return fs

def test_create_and_read_file():
    fs = make_fs()
    fs.write("/hello.txt", b"Hello, world!")
    assert fs.read("/hello.txt") == b"Hello, world!"

The tests create a filesystem in memory, format it, and then check that files can be created, read, overwritten, and removed. Because our "disk" is just a bytearray, each test runs in a few microseconds and needs no cleanup afterward.

Summary

Filesystems look complicated, but they are built from a small number of simple ideas stacked on top of each other. A disk is a sequence of bytes grouped into blocks. A superblock records how to interpret those blocks. A bitmap tracks which blocks are free. Inodes hold a file's metadata and point to its data. Directories are files that map names to inodes. And paths are just walks from the root directory down to a particular entry.

Exercises

Delete a Directory

Modify remove so that it can delete a directory by recursively deleting everything inside it first. How do you prevent the user from accidentally deleting the root directory?

Persist the Bitmap

Store the block bitmap in a reserved block on the disk instead of keeping it in memory, and update format and the allocation methods to use it.

Longer Files

Our inodes support at most MAX_FILE_BLOCKS data blocks. Add a single indirect block that stores the numbers of additional data blocks so that a file can grow much larger.

Variable-Length Names

Replace the fixed 12-byte name field in a directory entry with a length prefix and a variable-length name. What are the trade-offs between the two designs?

Hard Links

Add a link operation that creates a second name for an existing inode, and modify remove so that an inode is freed only when its last name is removed. What does this imply about where the file's size is stored?

Detect a Foreign Disk

Modify the constructor so that it refuses to work with a Disk whose magic number doesn't match. What should happen if the magic number is missing but the disk is otherwise valid?