The Software · Chapter 9.d
How are files stored?

Watch the opener · 1:17

Transcript

How are files stored? Memory forgets everything when the power goes. A disk keeps it for years.

I figured a file sits on the disk in one long piece, start to end. But after files come and go, the free space is scattered in holes.

So cut the file into block-size pieces, and drop each one wherever there's room. The first piece goes in block zero. Block one belongs to another file, so the next piece goes in block two, then three, then four. A table records, for each block, which block holds the next piece: zero to two, two to three, three to four. And a directory remembers where the file starts: block zero. To read it, start there and follow the links.

So a file is stored as a chain, not a single run! The disk can be a patchwork of holes, and the file is still whole.

Type your own file below, and watch its chain jump across the gaps.

The memory of Chapter 4 forgets everything when the power goes. A disk does not. But a disk is not a smooth surface to lay a file down on. It is a grid of fixed-size blocks, and a file rarely fits in a single one, nor in blocks that happen to sit next to each other once files have been written and deleted for a while. So a file is stored as a chain: its bytes are cut into block-size pieces, dropped wherever there is room, and a table off to the side records, for each block, which block holds the next piece. This is one allocation scheme; filesystems can also use indexed blocks or runs of adjacent blocks.

The Disk below simulates linked allocation in Python memory. Its byte strings retain each chunk’s length, including the last short chunk, and nothing is saved across process restarts. It models how file blocks are found, not the persistent device itself.

9.d.1 A file is a chain of blocks

Figure 9.d.2 shows a file whose four pieces landed in blocks 0, 2, 3, and 4, scattered around a block that belongs to another file. The pieces are not next to each other, but a chain links them in order, so reading the file in sequence is just following the links.

The interactive version needs the in-browser runtime.

Example 9.d-1. Writing and reading a file

class Disk:
    """A disk of fixed-size blocks, with a directory of files and a table linking
    each file's blocks into a chain."""

    def __init__(self, blocks: int, block_size: int = 4) -> None:
        self.block_size = block_size
        self.data = [b""] * blocks       # the bytes in each block
        self.fat = [_FREE] * blocks      # for each block, the next block or _END
        self.directory = {}              # file name -> its first block

    def write(self, name: str, content: bytes) -> None:
        """Store content under a name, cutting it into block-size pieces and
        chaining whatever free blocks hold them. Writing over an existing name
        frees its old chain first, so no blocks are leaked."""
        pieces = [content[i:i + self.block_size]
                  for i in range(0, len(content), self.block_size)] or [b""]
        free = [i for i, link in enumerate(self.fat) if link == _FREE]
        old_blocks = self.blocks_of(name) if name in self.directory else []
        if len(free) + len(old_blocks) < len(pieces):
            raise OSError("the disk is full")
        if name in self.directory:
            self.remove(name)
            free = [i for i, link in enumerate(self.fat) if link == _FREE]
        if len(free) < len(pieces):
            raise OSError("the disk is full")
        chain = free[:len(pieces)]
        for index, block in enumerate(chain):
            self.data[block] = pieces[index]
            self.fat[block] = chain[index + 1] if index + 1 < len(chain) else _END1
        self.directory[name] = chain[0]2

    def read(self, name: str) -> bytes:
        """Read a file back by following its chain of blocks from the directory."""
        block = self.directory[name]
        pieces = []
        while block != _END:
            pieces.append(self.data[block])3
            block = self.fat[block]
        return b"".join(pieces)

    def remove(self, name: str) -> None:
        """Delete a file, freeing every block in its chain."""
        block = self.directory.pop(name)
        while block != _END:
            following = self.fat[block]
            self.data[block] = b""
            self.fat[block] = _FREE
            block = following

    def blocks_of(self, name: str) -> list:
        """The list of blocks a file's chain occupies, in order."""
        block = self.directory[name]
        chain = []
        while block != _END:
            chain.append(block)
            block = self.fat[block]
        return chain

• writing links each block to the next free one it used, and marks the last block as the end of the chain
• the directory remembers only where the file begins, its first block
• reading starts there and follows the chain, gathering each block’s bytes, until the end

9.d.2 The two tables

Two small tables hold the whole scheme together, shown in Figure 9.d.3. The directory maps each file’s name to the first block of its chain. The file allocation table, one entry per block, says for each block which block comes next, or that it is the last. Between them, a name leads to a first block, and the table leads from there to the end.

9.d.3 The filesystem, run

Running ftb.filesystem writes three one-block files, deletes two to scatter the free blocks, then writes a larger file that must chain non-contiguous blocks, and reads it back.

after writing a, b, c (one block each):
  a: blocks [0]
  b: blocks [1]
  c: blocks [2]

deleted a and c, freeing blocks 0 and 2
wrote 'long' (13 bytes, 4 blocks): blocks [0, 2, 3, 4]
its blocks are not contiguous, but the chain links them in order

reading 'long' back: b'HELLO, FILES!'
matches what was written: True

The larger file’s chain hops across the gaps left by the deleted files, not because no four blocks sat in a row, but because the writer never looks for a row: it takes the free blocks in index order, earliest first. Yet reading it back, by following that chain, returns exactly the bytes that were written. That is the point of storing a file as a chain rather than a single run: the disk can be a patchwork of holes and a file can still be whole.

The next chapter puts these files under the program a person types at, and shows where loading fits.

Exercises

• Write two files, delete the first, then write a third and watch it reuse the freed blocks.
• What is the largest file this disk can hold? Write it, read it back, and confirm it survived.