§40.4–40.6Directories, Free Space, and Access Paths

Now that files and inodes are on disk, we fill in directories, free-space tracking, and the access paths that reads and writes actually follow.

40.4 Directory Organization

A directory is stored simply: its data blocks hold a list of directory entries, each a (name → inode number) directory entry One record in a directory's data blocks mapping a name to an inode number, typically with a record length (reclen) and string length. The reclen lets a deleted entry's space be reused. Every directory also has '.' and '..' entries. Directories are just files whose inode type is 'directory'. defined in ch. 40 — open in glossary pair with a record length (reclen) and string length (strlen):

Every directory has . (itself) and .. (its parent). Deleting a file leaves a gap — often marked with a reserved inode number (like 0) — and the reclen lets a later, smaller entry reuse that space. Crucially, a directory is just a file: it has an inode (with its type field set to “directory”) whose data blocks hold these entries. So the on-disk structure needs nothing new. (Other designs are possible — XFS stores directories as B-trees to speed up lookups; FAT uses linked lists and has no inodes at all.)

40.5 Free Space Management

To allocate a new inode or data block, the FS consults a bitmap. Creating a file, for instance, means scanning the inode bitmap for a free slot (a 0), marking it used (1), and writing the updated bitmap back to disk:

A refinement is pre-allocation pre-allocation An allocation heuristic (ext2/ext3) that grabs a run of consecutive free blocks (e.g. 8) for a new file at once, so part of the file lands contiguously on disk and reads/writes faster. defined in ch. 40 — open in glossary : ext2/ext3 look for a run of, say, 8 consecutive free blocks when a file is created, so part of the file lands contiguously on disk and is faster to read and write later.

40.6 Access Paths: Reading and Writing

The second half of understanding a file system is the access path access path The sequence of on-disk structures a file system reads and writes to carry out an operation. Opening /foo/bar walks the path from the root inode down (reading each directory's inode and data); reading a block consults the inode then the block; an allocating write touches the bitmap, inode, and data block. I/O cost grows with pathname length. defined in ch. 40 — open in glossary — which structures get read and written for each operation. Assume the FS is mounted (superblock in memory) but inodes and directories are still on disk. Watch what open("/foo/bar") then reading it actually does:

Writing is worse, because it may allocate. Each allocating write turns into five I/Os, and creating a file — which must allocate an inode and update its directory — costs around ten: