§40.1–40.3vsfs: On-Disk Organization and the Inode

We know how to use a file system (ch39). Now we build one: vsfs, the Very Simple File System — a stripped-down UNIX-style FS. A file system is pure software, so the design space is enormous (AFS to ZFS); we learn by case study, starting simple.

40.1 The Way To Think

Understand two things and you understand a file system:

• Data structures — what on-disk structures organize its data and metadata (vsfs uses simple arrays of blocks; fancier systems use trees).
• Access methods — how it maps open(), read(), write() onto reads and writes of those structures.

The rest of this chapter develops both. Build your mental model: what’s on disk, and what gets touched on each call.

40.2 Overall Organization

Start by dividing the disk into fixed-size blocks block The fixed-size unit a file system divides its disk region into and allocates in (commonly 4 KB) — distinct from a hardware disk sector (usually 512 bytes). vsfs addresses its partition as blocks 0…N−1; the on-disk layout is a sequence of these blocks. defined in ch. 40 — open in glossary — 4 KB each (distinct from the drive’s 512-byte sectors). On a tiny 64-block partition, we assemble the layout region by region:

The final layout: block 0 is the superblock superblock A block (usually the first) holding file-system-wide info: how many inodes and data blocks there are, where the inode table starts, and a magic number identifying the file-system type. On mount, the OS reads the superblock first to initialize the volume. defined in ch. 40 — open in glossary (S), blocks 1–2 are the inode and data bitmaps bitmap An allocation structure: one bit per object marking it free (0) or in-use (1). vsfs keeps an inode bitmap (for the inode table) and a data bitmap (for the data region). Bitmaps are consulted and updated only when allocating or freeing — never during a plain read. defined in ch. 40 — open in glossary (i, d), blocks 3–7 are the inode table inode table The on-disk region holding an array of inodes. Because inodes are fixed-size (e.g. 256 bytes, 16 per 4 KB block), the file system computes an inode's disk location directly from its i-number: blk = (inumber · sizeof(inode)) / blockSize, offset from the table's start. defined in ch. 40 — open in glossary (I), and blocks 8–63 are the data blocks data block A block in the file system's data region that holds actual user file contents (or a directory's entries, or an indirect block of pointers). Most of a disk is data blocks; the inode records which ones belong to a file. defined in ch. 40 — open in glossary (D). A bitmap is dead simple — one bit per object, 0 = free, 1 = in-use — one bitmap for inodes, one for data.

40.3 File Organization: The Inode

The inode (“index node”) is the key structure. Each is named by its i-number, and — because inodes are fixed-size and packed in an array — the FS computes an inode’s disk location directly from that number:

For inode 32 (256 B inodes, inode table starting at 12 KB): the byte offset is 32 × 256 = 8192, so the block sits at 12 KB + 8 KB = 20 KB, i.e. disk sector 20 KB / 512 = 40. Inside the inode is the file’s metadata plus its block pointers:

The multi-level index

How does the inode record where the data blocks are? A few direct pointers direct pointer A disk address stored directly in the inode that points at one of the file's data blocks. An inode holds a small fixed number of them (e.g. 12); together they cover small files entirely — which is most files. defined in ch. 40 — open in glossary (disk addresses) live right in the inode — enough for small files. For bigger files, an indirect pointer indirect pointer An inode pointer to an indirect block — a data block full of MORE pointers to data blocks (not user data). With 4 KB blocks and 4-byte addresses, one indirect block adds 1024 pointers. Double- and triple-indirect pointers add further levels for very large files. defined in ch. 40 — open in glossary points to an indirect block filled with 1024 more pointers; a double indirect pointer adds a level (1024 × 1024 blocks), and a triple adds another. This imbalanced tree is the multi-level index multi-level index The imbalanced-tree scheme for locating a file's blocks: a few direct pointers, then single, double, and triple indirect pointers. It optimizes for the common case (most files are small → direct pointers suffice) while still supporting huge files. Used by ext2/ext3, the original UNIX FS, and WAFL. defined in ch. 40 — open in glossary :

With 12 direct + single + double indirect pointers, 4 KB blocks and 4-byte addresses, a file can reach:

Why this lopsided design? Because of a truth that holds across the decades — most files are small — so it’s worth making the common case (a handful of direct pointers) cheap, and paying the indirect-block cost only for the rare big file: