Inodes and File Metadata

An inode (index node) is a fixed-size on-disk data structure, one per file, that stores everything the file system needs to know about that file except its name. This includes the file type (regular file, directory, symbolic link, device), owner and group IDs, permission bits, size in bytes, timestamps (last access, last modification, last metadata change), a link count (how many directory entries reference this inode), and a set of block pointers that locate the file's actual data on disk. Each inode is identified by an inode number, a small integer unique within its file system. A directory is itself just a special file whose data consists of a list of `(name, inode_number)` pairs. Looking up a file by path means repeatedly consulting directory data to translate a name into an inode number, then reading that inode to find its data (which, if it's itself a directory, is another list of name→inode pairs). This design cleanly separates two concerns that are easy to conflate: naming (what a file is called, which can vary per directory entry) and identity/content (what the file actually contains and who owns it, which is singular). A consequence is the hard link: two different directory entries, possibly in different directories, can list the same inode number. Both names refer to the identical file — same permissions, same size, same data — and the file's link count tracks how many names exist. Only when the link count drops to zero (and no process holds it open) does the file system reclaim the inode and its data blocks. This is precisely why deleting a file conceptually means "remove a name," not "destroy the content" — content vanishes only when the last name and last open handle disappear.

Anatomy of an inode

A classic Unix-style inode (as in early ext2, following the original BSD FFS design) contains roughly: ``` Inode { file_type // regular, directory, symlink, device, ... mode // permission bits (rwx for owner/group/other) owner_uid, group_gid size_bytes // logical size of file content link_count // number of directory entries pointing here timestamps { atime, mtime, ctime } direct_pointers[12] // block numbers, point straight at data single_indirect_pointer // points at a block full of pointers double_indirect_pointer // points at a block of pointers to // blocks of pointers triple_indirect_pointer // one more level of indirection } ``` Notice what is absent: the file's name. The inode is name-agnostic by design.

Why indirection, not one flat array?

If the inode stored, say, 10,000 direct block pointers to support large files, every inode — even one for a 4-byte file — would consume the space needed for 10,000 pointers. That wastes space badly given that most files are small. The indirect-pointer scheme is the classic engineering compromise: keep the inode itself small and fixed-size, and only pay the cost of extra pointer blocks when a file is actually large enough to need them.

• Direct pointers (e.g., 12 of them) point straight to data blocks. Small files (up to `12 × block_size`) need nothing else.
• Single indirect pointer points to one block that itself is filled entirely with data-block pointers (not inode fields — a whole block of pointers). If a block is 4 KiB and pointers are 4 bytes, that's 1024 additional data blocks addressed through one inode pointer.
• Double indirect pointer points to a block of pointers to single-indirect blocks — each of which points to 1024 data blocks. So one double-indirect pointer reaches `1024 × 1024` data blocks.
• Triple indirect pointer adds one more level: `1024 × 1024 × 1024` data blocks.

This is a tree: the inode is the root, indirect blocks are internal nodes, data blocks are leaves. Reading byte offset `X` in the file means computing which "leaf" (data block) holds it, and walking down at most 4 levels (inode → optional single → optional double → optional triple → data) to find it.

Path-to-inode resolution algorithm

Every `open("/usr/bin/ls")` call performs the following, starting from a known root inode (inode 2, by convention, in many Unix file systems): ``` function RESOLVE_PATH(path): components = split(path, "/") // ["usr", "bin", "ls"] current_inode = ROOT_INODE_NUMBER // e.g. 2 for name in components: inode = READ_INODE(current_inode) if inode.file_type != DIRECTORY: return ERROR("not a directory") entries = READ_DIRECTORY_DATA(inode) // list of (name, inum) found = null for (entry_name, entry_inum) in entries: if entry_name == name: found = entry_inum break if found == null: return ERROR("no such file or directory") current_inode = found return READ_INODE(current_inode) // the target file's inode ```

Translating a byte offset to a physical block (the tree walk)

``` function BLOCK_FOR_OFFSET(inode, byte_offset, block_size, ptrs_per_block): block_index = byte_offset / block_size // integer division N = 12 // number of direct pointers P = ptrs_per_block // e.g. 1024 if block_index < N: return inode.direct_pointers[block_index] block_index -= N if block_index < P: indirect_block = READ_BLOCK(inode.single_indirect_pointer) return indirect_block.pointers[block_index] block_index -= P if block_index < P P: outer = READ_BLOCK(inode.double_indirect_pointer) outer_index = block_index / P inner_index = block_index % P inner_block = READ_BLOCK(outer.pointers[outer_index]) return inner_block.pointers[inner_index] block_index -= P P if block_index < P P P: outer = READ_BLOCK(inode.triple_indirect_pointer) i1 = block_index / (P P) rem = block_index % (P P) mid = READ_BLOCK(outer.pointers[i1]) i2 = rem / P i3 = rem % P leaf_ptrs = READ_BLOCK(mid.pointers[i2]) return leaf_ptrs.pointers[i3] return ERROR("offset exceeds max file size") ```

Path resolution time. For a path with `k` components, `RESOLVE_PATH` performs `k` directory reads. Each directory read scans a directory's entries linearly (in simple designs) or via a hashed/B-tree index (in modern file systems like ext4's htree or XFS's B+trees). Linear scan of a directory with `m` entries costs `O(m)`; with indexing it is `O(log m)` or expected `O(1)`. Total: `O(k · m)` naive, or `O(k · log m)` with directory indexing. Since `k` is bounded by path depth (typically small, a few dozen at most) and file systems cache recently resolved directory entries (the dentry cache), the amortized cost of path resolution is very low — often just cache hits.

Block-offset lookup time. `BLOCK_FOR_OFFSET` does at most 4 block reads (inode is already in memory; then 0–3 indirect-block reads depending on which region the offset falls in) — this is `O(1)` in the number of disk accesses, independent of file size. This is the entire point of the indirection scheme: a file of any size supported by the scheme is reached in constant, small number of I/Os, not a number proportional to file size.

Maximum file size — derivation. Let `B` = block size in bytes, `p` = pointer size in bytes, so `P = B / p` pointers fit in one block. With `N` direct pointers, the maximum number of addressable blocks is: ``` max_blocks = N + P + P^2 + P^3 max_file_size = max_blocks × B ``` Concretely, with the classic ext2 parameters `N = 12`, `B = 4096` bytes, `p = 4` bytes, so `P = 1024`: ``` max_blocks = 12 + 1024 + 1024² + 1024³ = 12 + 1,024 + 1,048,576 + 1,073,741,824 ≈ 1,073,791,436 blocks max_file_size ≈ 1,073,791,436 × 4096 bytes ≈ 4.398 TiB ``` (In practice ext2/ext3 capped file size lower, at 2 TiB, due to a 32-bit block-count field elsewhere in the on-disk format — a reminder that multiple limits compose, and the smallest one binds.)

Space overhead — correctness of the "small inode" claim. A single inode with 12 direct pointers, 3 indirect pointers, and the metadata fields above fits comfortably in 128–256 bytes, a size fixed regardless of file size. This is the load-bearing correctness property: the inode's size never grows even as the file it describes grows from 1 byte to several terabytes, because growth is absorbed by additional (dynamically allocated) indirect blocks, not by the inode itself.

Correctness invariant of the tree walk. The `BLOCK_FOR_OFFSET` algorithm is correct because the address space it enumerates is partitioned into four disjoint, contiguous ranges — direct (`[0, N)`), single-indirect (`[N, N+P)`), double-indirect (`[N+P, N+P+P²)`), triple-indirect (`[N+P+P², N+P+P²+P³)`) — and the algorithm subtracts off each range's size before checking the next, so `block_index` is always re-based to be a valid local index into whichever level it lands in. This is the same pattern as converting a flat index into mixed-radix (base-`P`) digits for the double/triple cases: `outer_index` and `inner_index` are exactly the base-`P` digits of the offset within the double-indirect region, which is why `outer_index = block_index / P` and `inner_index = block_index % P` correctly recover them (division/modulo is the standard way to decompose an integer into digits of a fixed radix).

Tradeoffs. The indirection scheme optimizes for the common case (small files, cheap metadata) at a modest cost for large files (up to 3 extra disk reads per block access, though these are heavily cached in practice and often prefetched). Modern file systems (ext4, XFS, Btrfs) largely replace deep indirect-pointer chains with extents — `(start_block, length)` pairs describing runs of contiguous blocks — which represent large contiguous files with far fewer metadata entries and reduce the number of indirection levels needed in the common case of low fragmentation. The inode's core role — fixed-size per-file metadata plus some map to data — persists; only the shape of that map has evolved.

Suppose `block_size = 4096` bytes, `pointer_size = 4` bytes, so `P = 1024` pointers per indirect block, and `N = 12` direct pointers. Trace `BLOCK_FOR_OFFSET` for a file needing the block containing byte offset `5,000,000`.

So the file system: (1) reads the inode (already cached from the `open()` call), (2) reads the block pointed to by `double_indirect_pointer` — call it the "outer" block — (3) reads pointer 0 of that outer block, obtaining the address of a "middle" indirect block, (4) reads pointer 184 of that middle block, obtaining the actual data block's address, (5) reads that data block and extracts byte `5,000,000 mod 4096 = 5,000,000 - 1220×4096 = 4,480` within it. Total disk reads for this access (assuming nothing cached beyond the inode): 3 (outer indirect + middle indirect + data block) — matching the "at most 3 indirect reads plus 1 data read" bound for the double-indirect region, confirming the `O(1)`-disk-access claim independent of the fact that offset 5,000,000 is deep inside a multi-gigabyte file.

A second trace — path resolution with a hard link. Suppose `/home/alice/report.txt` and `/home/alice/backup/report_copy.txt` are hard-linked (same inode number, say inode 88431). Resolving the first path: root(inode 2) → `home` entry → inode 40 → `alice` entry → inode 512 → `report.txt` entry → inode 88431. Resolving the second: root(inode 2) → `home` → inode 40 → `alice` → inode 512 → `backup` entry → inode 900 → `report_copy.txt` entry → inode 88431. Both paths terminate at the same inode 88431; reading that inode once yields identical size, permissions, and timestamps regardless of which path was used, and inode 88431's `link_count` field equals 2 — correctly reflecting that two directory entries reference it. Deleting one name (`unlink("/home/alice/report.txt")`) decrements `link_count` to 1 and removes only that directory entry; the data, and the other name, survive untouched.

The inode concept traces to the earliest Unix implementations at Bell Labs, where the need for a compact, name-independent metadata record — decoupled from the tree of directory names above it — was recognized as central to a clean file system design. The indirect-block scheme for addressing large files with a small, fixed-size metadata record was refined through the Berkeley Fast File System (FFS) work, which also introduced ideas like cylinder groups to keep inodes physically near their data.

Every Unix-family operating system — Linux (ext2/3/4, XFS, Btrfs), macOS (APFS, historically HFS+), the BSDs (UFS/FFS) — implements some variant of the inode concept, even where the on-disk representation has evolved to extents or B-trees. Systems administrators diagnose "disk full" incidents by checking inode exhaustion (`df -i`) as a distinct resource from block exhaustion. Backup and sync tools (`rsync`, `cp --preserve=links`) must understand hard links and inode numbers to avoid duplicating data unnecessarily or breaking link relationships. Container and virtualization file systems (overlayfs, union mounts) manipulate inode-like metadata layers to implement copy-on-write efficiently. Even network file systems (NFS) expose file handles that function analogously to inode numbers, letting a client reference a file's identity independent of the path used to reach it. Any systems engineer debugging "why does this file show link count 2" or "why is `df` fine but `open()` fails" is, in effect, reasoning directly about inode mechanics.

Ask the tutor: How would the maximum file-size formula change if a file system used 8-byte block pointers instead of 4-byte ones, and why?