A typical UNIX filesystem, in block order: ┌────────────┬────────────┬─────────┬───────────┬─────────┐ │ BOOT BLOCK │ SUPERBLOCK │ BLOCK │ INODE │ DATA │ │ │ │ BITMAP │ TABLE │ BLOCKS │ └────────────┴────────────┴─────────┴───────────┴─────────┘ BOOT BLOCK block 0. Code to load the OS. Present even on non-bootable filesystems, for uniformity. SUPERBLOCK the filesystem's own metadata: total blocks, block size, free-block count inode count and free-inode count pointers to the bitmaps and inode table mount state, last-check time, magic number → CRITICAL. Corrupt it and the filesystem is unreadable, which is why BACKUP copies are written at known offsets. BLOCK BITMAP one bit per data block: free or allocated. COMPUTED for a 1 TB disk with 4096-byte blocks: 1 TB / 4 KB = 268,435,456 blocks bitmap = 268,435,456 bits = 32 MB → 32 MB to track a terabyte. Cheap. INODE TABLE a fixed array of inodes, sized at format time. → THE CONSEQUENCE: a filesystem can run out of INODES while having free space. Millions of tiny files exhaust the table and writes fail with ENOSPC even though `df` shows space free; `df -i` reveals it. Modern filesystems (APFS, btrfs, XFS) allocate inodes dynamically. DATA BLOCKS the file contents. IN-MEMORY STRUCTURES the OS also maintains: mount table which filesystems are mounted where system-wide open-file table one entry per open FILE per-process open-file table one entry per file DESCRIPTOR buffer cache / page cache cached blocks THE TWO-LEVEL OPEN-FILE TABLE matters: two processes opening the same file get separate descriptors with separate FILE POINTERS but share one inode entry. That is why two processes can read the same file at different positions — and why a descriptor inherited across fork() SHARES the position, since both point at the same system-wide entry. MEASURED ON THIS MACHINE: filesystem APFS block size 4096 bytes allocation 4096 bytes

1. CONTIGUOUS ALLOCATION each file occupies a consecutive run of blocks. The directory stores START BLOCK and LENGTH. ✔ FASTEST sequential access — no seeks between blocks ✔ direct access is trivial: block = start + n ✗ EXTERNAL FRAGMENTATION, exactly as with contiguous memory ✗ the file size must be known at creation ✗ growing a file may require moving it entirely Used by CD-ROM/DVD (write-once, size known), and in a relaxed form by extent-based filesystems. 2. LINKED ALLOCATION each block contains a pointer to the next. The directory stores only the FIRST block. ✔ NO external fragmentation — any free block will do ✔ files grow freely ✗ DIRECT ACCESS IS O(n): to reach block 50 you must read blocks 0..49 to follow the chain ✗ a pointer consumes space in every block, so the usable size is not a power of two — awkward for aligned I/O ✗ ONE CORRUPTED POINTER loses the rest of the file FAT VARIANT: move all pointers into one File Allocation Table at the start of the disk. ✔ the FAT can be cached, so traversal happens in memory ✔ direct access becomes feasible ✗ a single point of failure — hence FAT keeps two copies 3. INDEXED ALLOCATION each file has an INDEX BLOCK listing all its block numbers. ✔ NO external fragmentation ✔ DIRECT ACCESS in O(1): look up entry n in the index ✗ the index block is overhead even for a tiny file ✗ a single index block LIMITS the file size MAXIMUM FILE SIZE with one index block: block 4 KB, pointer 4 bytes → 4096/4 = 1024 pointers max file = 1024 × 4 KB = 4 MB 4 MB is far too small, which forces the multilevel scheme below. THE UNIX INODE — indexed allocation, made practical: 12 DIRECT pointers → 12 blocks 1 SINGLE INDIRECT pointer → a block full of pointers 1 DOUBLE INDIRECT pointer → a block of blocks of pointers 1 TRIPLE INDIRECT pointer → three levels MAXIMUM FILE SIZE, 4 KB blocks, 4-byte pointers (1024 pointers per block) — all values COMPUTED: direct 12 × 4 KB = 48 KB single indirect 1024 × 4 KB = 4 MB double indirect 1024² × 4 KB = 4 GB triple indirect 1024³ × 4 KB = 4 TB ───────────────── TOTAL ≈ 4 TB + 4 GB + 4 MB + 48 KB THE ELEGANCE: a small file uses only the 12 direct pointers, so it costs ONE inode read and ONE data read — two I/Os. A huge file remains addressable, paying extra indirection only for its distant blocks. ACCESS COST BY FILE POSITION: first 48 KB 1 extra read (the inode) → fastest up to 4 MB + 1 read (single indirect) up to 4 GB + 2 reads (double indirect) beyond + 3 reads (triple indirect) A deliberate optimisation for the common case: most files are small.

FREE-SPACE TRACKING: BIT VECTOR one bit per block. A hardware bit-scan finds the first free block quickly. 32 MB tracks a 1 TB disk at 4 KB blocks. LINKED LIST each free block points to the next free block. ✔ no extra space at all ✗ finding n contiguous blocks needs n disk reads GROUPING the first free block holds the addresses of n free blocks, the last pointing to the next group. Fewer reads. COUNTING store (first block, count) pairs, exploiting the fact that free blocks are usually contiguous. CONSISTENCY — the problem journaling solves: Creating a file touches several structures: 1. allocate an inode (inode bitmap) 2. write the inode (inode table) 3. allocate data blocks (block bitmap) 4. write the data 5. add the directory entry A crash between any two leaves the filesystem INCONSISTENT — an allocated inode nothing points to (a leak), or a directory entry pointing at a free inode (corruption). fsck SCANS THE WHOLE FILESYSTEM to find and repair these. ✗ time proportional to filesystem SIZE, not to the damage. Hours for a large volume. JOURNALING writes the intended changes to a LOG first: 1. write "I am about to do steps 1–5" to the journal 2. commit the journal entry 3. perform the real updates 4. mark the journal entry complete After a crash, replay any committed-but-incomplete entries. ✔ recovery time depends on the JOURNAL size, not the disk size — seconds instead of hours → this is EXACTLY the write-ahead logging of ACtE0704. Same problem, same solution, different layer. JOURNALING MODES (ext4): journal metadata AND data journalled — safest, slowest ordered metadata journalled, data written first (the default) writeback metadata journalled, data unordered — fastest, can expose stale data after a crash COPY-ON-WRITE FILESYSTEMS (ZFS, btrfs, APFS) take another route: never overwrite in place. Write new blocks, then atomically update the pointer. There is no inconsistent intermediate state to repair, and snapshots become nearly free — which is how APFS on this machine makes a snapshot instantly.