10. File Systems

The previous chapter ended with a flat array of numbered blocks on a device that forgets nothing but understands nothing either. This chapter is about the software that turns that array into named, growable, permission-checked objects that survive crashes — the interface users see, the on-disk structures that implement it, the allocation strategies that decide where bytes actually land, and the recovery machinery that keeps the whole thing consistent when the power fails mid-write. It matters because the file system is the most-used abstraction the kernel provides, and because almost every durability bug in production software comes from misunderstanding what it does and does not promise.

<a id="101-file-system-interface"></a>

10.1 File System Interface

This section covers what a file system looks like from the outside: what a file is to the operating system, the operations defined on it, how programs address bytes inside it, how files are organised into namespaces, how separate file systems are grafted into one tree, and what happens when several processes want the same file at once.

File Attributes and Operations

Theory

Start with the problem the file abstraction solves. A storage device offers a numbered array of fixed-size blocks. If applications used it directly, every program would need to know which blocks belong to it, how to grow a region without colliding with a neighbour, and how to find its data again after a reboot. Two programs sharing a device would need a shared agreement about all of this. That agreement, made once and enforced by the kernel, is the file system.

A file is the unit of that agreement: a named, persistent sequence of bytes, plus metadata describing it. The definition is deliberately minimal. To the operating system a file is just bytes — the interpretation of those bytes is entirely the application's business. A JPEG and a Python script differ only in what reads them.

The metadata is called the file's attributes, and it is stored separately from the data itself:

Attribute	Meaning	Typical storage
Name	Human-readable label	In the directory entry, not the file
Identifier	Unique number within the file system (inode number)	Directory entry
Type	Regular, directory, symlink, device, FIFO, socket	Mode bits in the inode
Size	Current length in bytes	Inode
Location	Pointers to the data blocks	Inode
Protection	Owner, group, permission bits, ACLs	Inode
Timestamps	Created, last modified (mtime), last accessed (atime), metadata changed (ctime)	Inode
Link count	How many names refer to this file	Inode

The split between "name" and "everything else" is the single most important structural decision in UNIX file systems, and it is worth pausing on. The name lives in a directory; the attributes and block pointers live in an inode. A directory entry is therefore just a (name, inode number) pair. This is why one file can have several names (hard links), why renaming a 4 GB file is instant, and why deleting a name that another process still has open does not free the data — the file survives until both its link count and its open count reach zero.

The operations defined on a file are few, and each maps to a system call:

• Create — allocate an inode, insert a directory entry.
• Open — resolve a path to an inode, check permissions once, and return a small integer (file descriptor) that indexes a per-process table. Everything afterwards uses that integer, so path resolution and permission checking are not repeated per byte.
• Read / Write — transfer bytes at the current file offset, which the kernel maintains per open-file-description and advances automatically.
• Seek — reposition the offset without transferring data.
• Truncate — set the length (usually to zero) while keeping attributes and the descriptor valid.
• Close — release the descriptor and drop a reference on the open-file description.
• Stat — read attributes without reading data.

The "open once, then use a handle" pattern is a performance decision, not a stylistic one. Resolving /home/user/projects/os/notes.md means reading and searching five directories. Doing that per read() would be absurd; doing it once at open() and caching the result in the descriptor table is the whole point.

Example

   THE THREE TABLES BEHIND ONE OPEN FILE

   Process A                  System-wide                  File system
   fd table                   open-file table              inode cache
   +----+-------+             +--------+--------+          +---------------+
   | 0  | ------+---------->  | offset | 1024   |          | inode 8721    |
   | 1  |       |      +--->  | flags  | O_RDWR |  ----->  | size   4096   |
   | 2  |       |      |      | inode  | 8721   |          | uid    1000   |
   | 3  | ------+------+      +--------+--------+          | mode   0644   |
   +----+-------+                                          | nlink  2      |
                              +--------+--------+          | blocks [...]  |
   Process B                  | offset | 0      |  ----->  +---------------+
   +----+-------+             | flags  | O_RDONLY|              ^
   | 3  | ------+---------->  | inode  | 8721   |               |
   +----+-------+             +--------+--------+ --------------+

   fd 0 and fd 3 in A SHARE an offset (they came from dup()/fork()).
   B has its OWN offset onto the SAME inode.
   The inode is shared by everyone: there is exactly one per file.

import os, stat, time

path = "demo.txt"

# --- create + write: one descriptor, offset advances implicitly ---
fd = os.open(path, os.O_CREAT | os.O_WRONLY | os.O_TRUNC, 0o644)
os.write(fd, b"hello ")            # offset 0 -> 6
os.write(fd, b"world")             # offset 6 -> 11 (no seek needed)
os.close(fd)

# --- stat: attributes live apart from the data ---
st = os.stat(path)
print(f"inode   : {st.st_ino}")            # identifier, not the name
print(f"size    : {st.st_size}")           # 11
print(f"mode    : {stat.filemode(st.st_mode)}")   # -rw-r--r--
print(f"links   : {st.st_nlink}")          # 1
print(f"mtime   : {time.ctime(st.st_mtime)}")

# --- a second NAME for the same inode: attributes are not duplicated ---
os.link(path, "alias.txt")
print(os.stat("alias.txt").st_ino == st.st_ino)   # True: same file
print(os.stat(path).st_nlink)                     # 2

# --- the deleted-but-open trick: data survives while a descriptor holds it ---
fd = os.open(path, os.O_RDONLY)
os.unlink(path)                     # name gone, link count 2 -> 1
os.unlink("alias.txt")              # link count 1 -> 0, but open count is 1
print(os.read(fd, 11))              # b'hello world'  -- still readable
os.close(fd)                        # NOW the blocks are freed

# Attributes, and the three timestamps that confuse everyone.
stat notes.md
#   Access: 2026-09-11 09:14:02   <- atime, updated on read (often 'relatime')
#   Modify: 2026-09-10 22:31:55   <- mtime, data last changed
#   Change: 2026-09-10 22:31:55   <- ctime, INODE last changed (chmod bumps this)

ls -li notes.md            # -i shows the inode number
lsof -p $$                 # every descriptor this shell holds open

# A file whose name is gone but whose blocks are not: the classic
# "df says full, du says empty" situation.
sudo lsof +L1              # open files with link count 0

Key takeaways

• A file is a named sequence of bytes plus attributes; the OS never interprets the bytes, only the metadata.
• The name lives in a directory entry, everything else lives in the inode — that separation enables hard links, instant rename, and delete-while-open.
• open() pays path resolution and permission checking once and returns a descriptor; all later operations use the descriptor.
• Three tables are involved: per-process descriptors, system-wide open-file descriptions (which hold the offset and flags), and inodes (one per file).
• A file's blocks are freed only when link count and open count both reach zero.
• mtime tracks data changes, ctime tracks inode changes, atime tracks reads and is usually dampened (relatime) because updating it turns every read into a write.

🧪 Practice

1. Create a file, hard-link it twice, and predict st_nlink after each step and after deleting one name. Verify with stat.
2. Two processes open the same file; one was produced by fork() from the other. Describe which of them share a file offset and which do not, and explain why using the three-table diagram.
3. Interview-style: "df reports the disk is 100% full but du -sh / accounts for only half of it. What is going on and how do you fix it without rebooting?" Hint: think about what keeps blocks allocated after the last name is removed, and which tool lists those files.

File Types and Structure

Theory

If the OS treats a file as bytes, who decides that a file is a PNG? The answer differs by system, and the choice has consequences.

There are three strategies for type indication:

1. Extension convention (Windows, and by habit everywhere). The name suffix declares the type, and the system maintains a registry mapping suffixes to applications. Simple and visible, but the type is a hint that anyone can lie about — invoice.pdf.exe exploits exactly this.
2. Magic numbers (UNIX). The first few bytes of the file identify it: \x7fELF for executables, %PDF- for PDFs, \x89PNG for PNGs. The kernel uses this for one purpose only — deciding how to execute a file — and leaves the rest to user space (file(1), libmagic, MIME databases).
3. Structured metadata (classic Mac OS resource forks, and modern extended attributes). The type is stored as an attribute alongside the file. Robust, but it does not survive copying through systems that do not understand the attribute.

Separately from type, there is internal structure: does the file system impose any shape on the bytes?

UNIX answers no. A file is an unstructured byte stream, and any record structure is the application's invention. This was a genuinely radical simplification in 1970, when systems such as OS/VS offered fixed-length records, variable-length records, indexed sequential files, and more, each with its own access methods baked into the OS. The UNIX bet — one structure (the byte stream) plus good tools — won decisively, because every structured format can be layered on top, while the reverse is not true.

Some structure is unavoidable, though, and it lives at the edges:

• The OS must understand executables well enough to load them (ELF, PE, Mach-O headers).
• The OS must understand directories, which are files with a kernel-defined format that user space may not write directly.
• The device beneath imposes block granularity: a 1-byte file occupies a whole block (4 KB typically), so the "byte stream" is an illusion maintained above a block-structured medium.

UNIX also generalises "file" to cover things that are not stored data at all, unified under the same descriptor-based API:

Type	ls -l	What it is
Regular	-	Ordinary data
Directory	d	Name-to-inode mapping
Symbolic link	l	A file whose contents are a path
Character device	c	Unbuffered byte-at-a-time device (/dev/tty)
Block device	b	Block-addressed device (/dev/sda)
FIFO (named pipe)	p	In-kernel byte queue with a filesystem name
Socket	s	Endpoint for local IPC

The payoff for this generalisation is the "everything is a file" property: read(), write(), select(), and redirection work unchanged across all seven. A program that writes to standard output does not care whether it lands in a regular file, a pipe, or a terminal.

Two link types deserve distinguishing, because they fail differently:

• A hard link is a second directory entry pointing at the same inode. It is indistinguishable from the "original", cannot cross file system boundaries (inode numbers are per-file-system), and cannot point at a directory (that would allow cycles the tree walkers cannot handle).
• A symbolic link is a small file containing a path string, resolved at every use. It can cross file systems, can point at directories, and can dangle when the target disappears.

Example

   HARD LINK vs SYMBOLIC LINK

   HARD LINK                         SYMBOLIC LINK
   dir entries                       dir entries
   +--------------+                  +--------------+
   | "a.txt" 8721 |----+             | "a.txt" 8721 |-----> inode 8721
   | "b.txt" 8721 |----+--> inode    | "s.txt" 9002 |---+   (data)
   +--------------+         8721     +--------------+   |
                           nlink=2                      v
   Delete "a.txt":                                 inode 9002
     nlink 2 -> 1, data intact,                    type: symlink
     "b.txt" still works.                          data: "a.txt"
                                                        |
                                     Delete "a.txt": ---+--> DANGLES
                                     s.txt now points at nothing.

# Type is determined by content, not by name.
cp /bin/ls ./notanexe.txt
file notanexe.txt
#   notanexe.txt: ELF 64-bit LSB pie executable, x86-64, dynamically linked
xxd -l 4 notanexe.txt
#   00000000: 7f45 4c46                                .ELF

# The seven file types, all through one API.
ls -l /dev/null /dev/sda /tmp /etc/passwd
#   crw-rw-rw- 1 root root 1, 3 /dev/null      <- character device
#   brw-rw---- 1 root disk 8, 0 /dev/sda       <- block device
#   drwxrwxrwt 1 root root      /tmp           <- directory
#   -rw-r--r-- 1 root root      /etc/passwd    <- regular

mkfifo pipe && ls -l pipe        # prw-r--r--  : a FIFO
echo hi > pipe &                  # blocks until a reader appears
cat pipe                          # hi

# Hard vs symbolic, demonstrated by breaking them.
echo data > a.txt
ln   a.txt hard.txt               # same inode
ln -s a.txt soft.txt              # a path string
rm a.txt
cat hard.txt                      # data      -- survives
cat soft.txt                      # No such file or directory -- dangles

import os, stat

def describe(path):
    st = os.lstat(path)                      # lstat: do NOT follow symlinks
    m = st.st_mode
    kind = ("directory" if stat.S_ISDIR(m) else
            "symlink"   if stat.S_ISLNK(m) else
            "fifo"      if stat.S_ISFIFO(m) else
            "chardev"   if stat.S_ISCHR(m) else
            "blockdev"  if stat.S_ISBLK(m) else
            "socket"    if stat.S_ISSOCK(m) else
            "regular")
    return f"{path:<14} {kind:<10} inode={st.st_ino}"

for p in ["/etc/passwd", "/tmp", "/dev/null", "/dev/sda"]:
    try:
        print(describe(p))
    except FileNotFoundError:
        pass

# Magic-number sniffing: what `file` does, in three lines.
MAGIC = {b"\x7fELF": "ELF binary", b"%PDF": "PDF", b"\x89PNG": "PNG"}
with open("/bin/ls", "rb") as f:
    head = f.read(4)
print(MAGIC.get(head, "unknown"))            # ELF binary

Key takeaways

• Type can be signalled by extension (a lie-able hint), by magic number (content-based, the UNIX way), or by stored metadata (robust but non-portable).
• UNIX files have no OS-imposed internal structure: they are byte streams, and record formats are an application concern.
• The kernel does understand a few structures it must: executable headers and directory entries.
• "Everything is a file" means seven object types share one descriptor-based API, so redirection and pipelines work uniformly.
• A hard link is another name for the same inode: same file system only, no directories, data survives while any link remains.
• A symbolic link is a path string resolved at each use: crosses file systems, can point at directories, and can dangle.

🧪 Practice

1. Create a file, a hard link, and a symlink to it. Record inode numbers and link counts before and after deleting the original, and explain each observed value.
2. Explain why hard links to directories are forbidden while symlinks to directories are allowed. What breaks if the restriction is lifted?
3. Interview-style: "A user renames report.txt to report.jpg and the image viewer refuses to open it. On another machine it opens fine. Explain both behaviours." Hint: two different type-determination strategies are in play; think about which one each platform trusts.

Access Methods

Theory

Once a file is open, how do you get at the bytes inside it? The access method is the pattern of addressing, and it determines how well the pattern maps onto the storage device underneath.

Sequential access reads or writes from the current position forward, advancing the offset as it goes. This is the dominant real-world pattern — it covers compiling, copying, streaming, log appending, and most of grep — and it is the pattern storage hardware is happiest with. On a disk it exploits track locality; on flash it amortises per-request overhead; on both it makes read-ahead effective, because the kernel can confidently prefetch the next blocks while the application is still consuming the current ones.

Direct (random) access treats the file as a numbered array of records or bytes and jumps to any position. The lseek() call sets the offset explicitly; pread()/pwrite() do the same atomically as part of the transfer, which matters when descriptors are shared between threads. Random access is what databases, virtual memory swap, and any index structure need. On an HDD it costs a seek per jump; on an SSD the penalty largely disappears, which is precisely why B-trees and hash indexes became cheap enough to use everywhere.

Indexed access builds a second structure — an index mapping a key to a file offset — and consults it before touching the data. Classic mainframe systems (ISAM, VSAM) built this into the OS. Modern systems build it in user space instead: a database's B-tree, a key-value store's LSM index, a .idx file next to a .tar. The OS's role is reduced to providing efficient random access, which is exactly the simplification discussed in the previous topic.

Memory mapping deserves separate mention because it is an access method disguised as memory. mmap() maps file pages into the address space, so reading the file is just dereferencing a pointer and the page-fault machinery of Chapter 8 does the I/O. It eliminates the copy between kernel buffer and user buffer, makes random access syntactically free, and lets several processes share one physical copy of the pages. Its costs are real too: faults are not free, errors surface as SIGBUS rather than a return code, and the mapping's size is fixed at map time, so growing files need re-mapping.

The kernel is not a passive participant. It watches the access pattern and adapts: detected sequential reads trigger aggressive read-ahead, while detected random reads suppress it (prefetching would waste bandwidth and cache). Applications can announce their intent instead of leaving it to inference, with posix_fadvise() or madvise().

Example

   ACCESS PATTERNS AGAINST ONE FILE (blocks 0..9)

   SEQUENTIAL   read 0,1,2,3,4,5,...      offset advances implicitly
                [0][1][2][3][4][5][6][7][8][9]
                 ->  ->  ->  ->  ->       read-ahead loads 6,7,8 early

   DIRECT       seek(7); read;  seek(2); read;  seek(9); read
                [0][1][2][3][4][5][6][7][8][9]
                         ^           ^        ^
                         3rd         1st      2nd      no useful prefetch

   INDEXED      index: "smith" -> byte 40960 -> block 10
                +-------------+        +-------------------+
                | key -> off  | -----> | data file         |
                +-------------+        +-------------------+

   MEMORY-MAPPED   ptr = mmap(fd, ...);  x = ptr[40960]
                   page fault -> kernel reads block -> maps frame
                   no read() call, no copy into a user buffer

import os, mmap, time

path = "data.bin"
BLOCK = 4096
with open(path, "wb") as f:                  # 64 MB of predictable content
    for i in range(16384):
        f.write(bytes([i % 256]) * BLOCK)

# --- sequential: one pass, offsets advance on their own ---
t0 = time.perf_counter()
with open(path, "rb") as f:
    while f.read(BLOCK):
        pass
seq = time.perf_counter() - t0

# --- direct/random: same byte count, scattered offsets ---
import random
offsets = [random.randrange(16384) * BLOCK for _ in range(16384)]
t0 = time.perf_counter()
with open(path, "rb") as f:
    for off in offsets:
        f.seek(off)                          # explicit repositioning
        f.read(BLOCK)
rnd = time.perf_counter() - t0

print(f"sequential {seq:.3f}s   random {rnd:.3f}s   ratio {rnd/seq:.1f}x")
# On an HDD this ratio is 50-200x; on NVMe it is closer to 2-5x;
# fully cached in page cache it approaches 1x. The hardware decides.

# --- pread: offset passed per call, safe to share a descriptor ---
fd = os.open(path, os.O_RDONLY)
a = os.pread(fd, 16, 4096)                   # does NOT move the file offset
b = os.pread(fd, 16, 8192)                   # so threads cannot race here
os.close(fd)

# --- memory mapping: the file as an array ---
with open(path, "r+b") as f:
    mm = mmap.mmap(f.fileno(), 0)
    print(mm[4096:4100])                     # a read, served by a page fault
    mm[0:4] = b"HEAD"                        # a write, marks the page dirty
    mm.flush()                               # force it to storage
    mm.close()

# Tell the kernel what you are about to do, instead of letting it guess.
#   POSIX_FADV_SEQUENTIAL -> doubles read-ahead window
#   POSIX_FADV_RANDOM     -> disables read-ahead
#   POSIX_FADV_DONTNEED   -> drop these pages from the cache

# Observe read-ahead adapting, with real I/O only (bypassing the page cache).
fio --name=seq --rw=read     --bs=128k --size=1G --direct=1 --filename=data.bin
fio --name=rnd --rw=randread --bs=4k   --size=1G --direct=1 --filename=data.bin
# Compare the two IOPS/bandwidth lines: same device, different access method.

blockdev --getra /dev/sda        # read-ahead in 512-byte sectors (often 256 = 128 KB)

Key takeaways

• Sequential access advances an implicit offset, matches hardware behaviour, and enables read-ahead — it is the common case and the fast one.
• Direct access repositions explicitly with lseek(), or per-call with pread/pwrite, which are the thread-safe forms.
• Indexed access adds a key-to-offset structure; modern systems build it in user space rather than in the OS.
• Memory mapping turns file access into pointer dereferences, removing a copy and simplifying random access, at the cost of SIGBUS error reporting and fixed mapping size.
• The kernel infers the pattern to decide read-ahead; posix_fadvise/madvise let an application state it explicitly.
• The sequential-versus-random gap is a property of the device, not the file system: enormous on HDD, modest on NVMe, negligible when cached.

🧪 Practice

1. Write a program that reads a 100 MB file sequentially and then in random 4 KB chunks, dropping caches between runs. Report both timings and explain the ratio you observe on your hardware.
2. Give two concrete situations where mmap() is the wrong choice, and say what you would use instead in each.
3. Interview-style: "A log-processing job got 5x slower after we changed it to sample random lines instead of reading the whole file. Disk utilisation went down. Explain." Hint: think about what the kernel stopped doing once the pattern stopped looking sequential.

Directory Structures

Theory

A directory is a file whose contents are name-to-inode mappings. Its purpose is to make files findable by humans and to give names a scope, so two projects can each have a README.md. How directories relate to one another has evolved through several designs, each fixing a problem in the last.

Single-level. One directory for the entire system. Every file needs a globally unique name. This works for a single user with a handful of files and collapses immediately beyond that: two users cannot both have notes.

Two-level. One directory per user, plus a master file directory listing users. Names are now unique per user, and a path becomes user/file. Sharing becomes awkward — there is no place for files that belong to everybody — and there is still no way to organise one user's thousand files.

Tree-structured. Directories may contain directories, recursively. This is the design that stuck. It gives arbitrary-depth grouping, natural namespacing, and a clean notion of absolute path (from the root, /etc/ssh/sshd_config) versus relative path (from the process's current working directory, ../src/main.c). Every process carries a CWD, which is why cd is a shell builtin that changes kernel state rather than a program.

Acyclic graph. Allow a file — or a subtree — to appear in more than one directory, via hard links. The graph is no longer a tree but must remain acyclic, because deletion by reference counting cannot reclaim cycles and tree walkers would loop forever. UNIX enforces acyclicity crudely but effectively: hard links to directories are forbidden, so only leaf sharing is possible.

General graph. Allow cycles, which symbolic links do allow. Now deletion cannot use reference counts alone (a cycle keeps itself alive) and traversal needs cycle detection. UNIX accepts the risk because symlinks are resolved by path, not by reference, and imposes a hard limit (typically 40) on chained resolutions — which is what ELOOP means.

Two directory entries always exist and are not decoration: . refers to the directory itself and .. to its parent (in the root, .. is the root). They are what make relative paths and .. traversal work without the kernel keeping a separate parent pointer, and they are why a freshly created empty directory has a link count of 2, and gains one more for every subdirectory it contains.

Path resolution is the operation that turns a string into an inode, and it is worth spelling out because its cost and its security properties both come up constantly. The kernel starts at the root (absolute) or the CWD (relative), then for each component: check execute permission on the current directory, look up the component in it, follow symlinks if any (decrementing a budget), and repeat. Execute permission on a directory means exactly "may traverse", which is distinct from read permission, which means "may list".

Example

   TREE-STRUCTURED NAMESPACE WITH A HARD LINK AND A SYMLINK

                          / (root, inode 2)
                          |
          +---------------+---------------+
          |               |               |
        /etc            /home           /var
          |               |               |
      passwd (i:41)    /home/ana       /var/log
                          |               |
              +-----------+------+     syslog (i:77)
              |                  |
          notes.md (i:88)    backup.md (i:88)   <- HARD LINK: same inode
                                                    nlink = 2

          /home/ana/latest ---> "/var/log/syslog"  <- SYMLINK: a path string

   RESOLVING /home/ana/notes.md
     start at inode 2 (root)
     -> need x on /          -> look up "home"  -> inode 12
     -> need x on /home      -> look up "ana"   -> inode 40
     -> need x on /home/ana  -> look up "notes.md" -> inode 88
     4 directory lookups, 3 permission checks, then open the inode.

   LINK COUNTS
     an empty dir has nlink 2  :  its own name + its own "."
     each subdirectory adds 1  :  the subdirectory's ".."

# Link counts explain themselves once you know about "." and "..".
mkdir -p demo/sub1 demo/sub2
stat -c '%n nlink=%h' demo demo/sub1
#   demo      nlink=4     <- "demo" + "demo/." + sub1/.. + sub2/..
#   demo/sub1 nlink=2     <- its name + its own "."

# Traverse vs list: two different permissions on a directory.
mkdir private && echo secret > private/file.txt
chmod 111 private                 # --x: traversable, not listable
ls private                        # Permission denied
cat private/file.txt              # secret        <- traversal works
chmod 444 private                 # r--: listable, not traversable
ls private                        # file.txt
cat private/file.txt              # Permission denied

# Symlink cycles are caught by the resolution budget.
ln -s loop_b loop_a && ln -s loop_a loop_b
cat loop_a                        # Too many levels of symbolic links (ELOOP)

# Where a process's CWD actually lives.
ls -l /proc/$$/cwd                # a symlink into the kernel's view

import os

# Path resolution, written out as the kernel does it (simplified: no symlinks).
def resolve(path, cwd="/"):
    start = "/" if path.startswith("/") else cwd
    parts = [p for p in path.split("/") if p not in ("", ".")]
    stack = [p for p in start.split("/") if p]
    for p in parts:
        if p == "..":
            if stack:            # ".." in the root is the root: no underflow
                stack.pop()
        else:
            stack.append(p)      # a real lookup happens here per component
    return "/" + "/".join(stack)

print(resolve("../src/main.c", cwd="/home/ana/docs"))   # /home/ana/src/main.c
print(resolve("/etc/../etc/passwd"))                     # /etc/passwd
print(resolve("../../../..", cwd="/home/ana"))           # /

# The per-process CWD is kernel state, changed by a system call.
print(os.getcwd())
os.chdir("/tmp")
print(os.getcwd())              # /tmp -- affects every later relative path

Key takeaways

• A directory is a file containing (name, inode) entries; names live in directories, attributes live in inodes.
• The structures evolved single-level, two-level, tree, acyclic graph, general graph — each step buying sharing or organisation at the cost of harder deletion and traversal.
• Trees plus hard links give an acyclic graph; UNIX keeps it acyclic by forbidding hard links to directories.
• Symbolic links permit cycles, so resolution is bounded by a link budget (ELOOP at roughly 40).
• . and .. are real entries; they explain why an empty directory has link count 2 and gains one per subdirectory.
• Execute permission on a directory means "may traverse"; read permission means "may list" — they are independent.

🧪 Practice

1. Create a directory with three subdirectories and predict its link count before running stat. Explain each contribution.
2. Given CWD /home/ana/projects/os, resolve ../../docs/./notes.md and ../../../.. by hand, then verify with readlink -f.
3. Interview-style: "A directory is chmod 711. Users report they can cat a file inside it if they know the name, but ls fails. Bug or correct behaviour?" Hint: separate the two permission bits and state what each one authorises.

Mounting

Theory

A machine has several storage devices and several file systems, but users want one namespace, not a drive letter per device. Mounting is the operation that grafts one file system's root onto a directory in an existing tree, producing a single unified hierarchy.

The mechanism is simple and elegant. A mount point is an ordinary directory in the already-mounted tree. When a file system is mounted there, the kernel records a mapping in its mount table; from then on, path resolution that reaches that directory jumps into the new file system's root instead of reading the directory's own contents. Those original contents are not destroyed — they are hidden, and they reappear on unmount. (This is the usual explanation for "I copied files into /mnt/backup and they vanished when the disk was attached": they were written to the underlying directory, which the mount then covered.)

Mounting is what makes the tree device-independent. /home may be a separate NVMe partition, /var/log a network share, and /proc an entirely synthetic file system generated on demand by the kernel — yet a program opening /home/ana/.bashrc needs to know none of that. The Virtual File System layer (Section 10.2) is the machinery that dispatches each operation to the right implementation.

Mounts carry options that change semantics, and several are security-relevant rather than merely performance-relevant:

Option	Effect	Why it exists
ro / rw	Read-only or read-write	Forensics, immutable system images
noexec	Refuse to execute binaries from here	Stop payloads running from /tmp
nosuid	Ignore setuid/setgid bits	Stop privilege escalation via removable media
nodev	Ignore device nodes	Stop a crafted /dev/mem on a USB stick
noatime / relatime	Suppress or dampen access-time updates	Avoid turning reads into writes
sync / async	Write-through or write-back metadata	Durability versus throughput

Several arrangements go beyond the basic case. A bind mount makes an existing directory visible at a second location without copying (the mechanism behind container volume mounts). An overlay mount stacks a writable upper layer over one or more read-only lower layers, so writes go to the upper layer via copy-on-write — this is how container images work. A mount namespace gives a process group its own private mount table, which is how a container sees a different root file system from the host without any virtualisation of the hardware.

Unmounting can fail, and the reason is instructive: umount returns EBUSY if any process holds an open descriptor or has its CWD inside the file system, because tearing it down would strand those references. lsof or fuser identifies the holder; a lazy unmount (umount -l) detaches the subtree from the namespace immediately and completes the teardown when the last reference goes away.

Example

   MOUNTING: GRAFTING ONE TREE ONTO ANOTHER

   BEFORE                             AFTER  mount /dev/sdb1 /home
   root fs (/dev/sda1)                unified namespace
        /                                  /
        |-- etc                            |-- etc
        |-- home  (empty dir, on sda1)     |-- home  ===> /dev/sdb1 root
        |-- var                            |     |-- ana
        +-- mnt                            |     +-- ben
                                           |-- var
   sdb1 (unmounted)                        +-- mnt
        /
        |-- ana                      Path resolution reaching "home"
        +-- ben                      CROSSES into sdb1. The old (empty)
                                     /home is hidden, not deleted.

   COVERED FILES: if /home had contained "leftover.txt" before the
   mount, it is invisible while mounted and returns on umount.

   OVERLAY MOUNT (containers)
        merged view  ------------------+
        upper (rw)   [ app.log, cfg ]  |  writes land here (copy-up)
        lower (ro)   [ /usr /lib /bin ]|  image layers, shared, untouched

# What is mounted, and with which semantics.
findmnt                                  # tree view of the mount table
findmnt -o TARGET,SOURCE,FSTYPE,OPTIONS /home
cat /proc/self/mountinfo | head          # the kernel's own view

# Mount with security-relevant options.
sudo mount -o rw,noexec,nosuid,nodev /dev/sdb1 /mnt/usb
#   noexec: a binary copied here cannot be run, even with +x
#   nosuid: a setuid-root binary here runs as the invoking user

# Covered files: the classic confusion, demonstrated.
sudo mkdir -p /mnt/demo && echo hidden | sudo tee /mnt/demo/underneath.txt
sudo mount -t tmpfs none /mnt/demo
ls /mnt/demo                             # empty -- underneath.txt is covered
sudo umount /mnt/demo
ls /mnt/demo                             # underneath.txt  -- it was never lost

# Bind mount: one file system, two places in the namespace.
sudo mount --bind /var/log /mnt/logs     # not a copy; same inodes

# EBUSY and its diagnosis.
sudo umount /mnt/usb                     # target is busy
sudo fuser -vm /mnt/usb                  # who holds it
sudo umount -l /mnt/usb                  # detach now, clean up later

# Persistent mounts. Prefer UUID: device names are not stable across boots.
blkid /dev/sdb1
#   /dev/sdb1: UUID="8f3c..." TYPE="ext4"
# /etc/fstab:
#   UUID=8f3c...  /home  ext4  defaults,relatime  0  2

import os

# Detecting a mount point without consulting the mount table:
# a mount point's device number differs from its parent's.
def is_mount_point(path):
    try:
        st  = os.lstat(path)
        par = os.lstat(os.path.join(path, ".."))
    except OSError:
        return False
    return st.st_dev != par.st_dev or st.st_ino == par.st_ino   # st_ino test catches "/"

for p in ["/", "/home", "/proc", "/tmp", "/etc"]:
    print(f"{p:<8} mount point: {is_mount_point(p)}")

# Why st_dev matters elsewhere: hard links cannot cross it.
a, b = os.stat("/tmp"), os.stat("/")
print("same file system:", a.st_dev == b.st_dev)

Key takeaways

• Mounting grafts a file system's root onto a directory, so many devices present as one namespace.
• Files already in the mount point are hidden, not deleted, and reappear after unmount.
• Mount options such as noexec, nosuid, and nodev are security controls, not just tuning knobs.
• Bind mounts expose one directory at a second path; overlay mounts stack a writable layer over read-only ones — together they are the basis of container file systems.
• Mount namespaces give a process group a private mount table, which is how containers get a different root without hardware virtualisation.
• umount fails with EBUSY while any descriptor or CWD is inside; lsof/fuser find the holder, umount -l defers the teardown.

🧪 Practice

1. Create a directory, put a file in it, mount a tmpfs over it, and observe the file's disappearance and return. Explain what happened to the inode in each step.
2. Write an /etc/fstab line mounting a USB device at /mnt/usb read-write but hostile to malware, and justify each option.
3. Interview-style: "umount /data reports the target is busy, but lsof /data shows nothing. What else could hold it?" Hint: open descriptors are not the only kind of reference a process can have into a file system, and other mounts can nest inside it.

File Sharing and Locking

Theory

The moment two processes can open the same file, the file system inherits every problem from Chapter 5. Two writers can interleave, a reader can observe a half-written record, and a check-then-act sequence can be invalidated between the check and the act. The file system's answers are of two kinds: rules about what concurrent operations guarantee, and locks for the cases where the rules are not enough.

Start with what is guaranteed without any locking. POSIX requires that a single read() or write() on a regular file is atomic with respect to other reads and writes on the same file: a reader never sees a write half-applied. This is weaker than it sounds. A large write() may be split into several by the implementation, O_APPEND is atomic in its seek-and-write pair but a manual lseek()+write() is not, and nothing at all is guaranteed across two separate calls. Any invariant spanning more than one system call needs a lock.

Advisory locks are the normal mechanism, and the adjective is the important part: the kernel tracks the lock but does not enforce it on processes that do not ask. Cooperating programs must all take the lock; a program that ignores it writes freely. This is a deliberate design choice — mandatory locking lets one buggy process make a file permanently unusable to everybody.

Two POSIX families exist, and they differ in ways that cause real bugs:

Property	flock() (BSD)	fcntl() / POSIX record locks
Granularity	Whole file	Byte range
Associated with	The open file description	The (process, inode) pair
Survives fork()	Yes, shared with the child	Lock is not inherited
Effect of closing any fd to the file	No effect on other fds	Releases all the process's locks on that file
Works over NFS	Historically no, now sometimes	Yes, via the lock manager
Upgrade/downgrade	Atomic	Atomic, but with release windows in some cases

That fourth row is the classic trap: with POSIX record locks, opening and closing an unrelated descriptor to the same file silently drops the lock you were relying on. Linux's OFD locks (F_OFD_SETLK) fix this by attaching the lock to the open file description, as flock does, while keeping byte-range granularity. They are the right default for new code on Linux.

Locks come in shared (read) and exclusive (write) modes, with the familiar rule: any number of shared holders, or one exclusive holder. And because a lock is held while a process may block, deadlock is possible — two processes locking two byte ranges in opposite orders is exactly the Chapter 6 scenario. The kernel detects simple cases of this for fcntl blocking locks and returns EDEADLK, but do not depend on it: impose a lock ordering.

The lock-free alternative is worth knowing because it is often better. Atomic rename exploits the fact that rename() within a file system is atomic: write a complete new version to a temporary file, fsync() it, then rename() it over the target. Readers see either the whole old file or the whole new one, never a mixture, and no reader needs to cooperate. The same trick with O_EXCL creation gives a lock file: open(..., O_CREAT|O_EXCL) succeeds for exactly one process.

Finally, sharing across machines changes the semantics themselves. Local file systems provide UNIX semantics: a write is visible to other openers immediately. NFS historically provided close-to-open consistency: changes are guaranteed visible only after the writer closes and the reader subsequently opens. Code that is correct locally can be subtly wrong on a network share for exactly this reason.

Example

   LOST UPDATE WITHOUT A LOCK              WITH AN EXCLUSIVE LOCK

   P1: read counter  -> 5                  P1: lock  ---------------+
   P2: read counter  -> 5                  P1: read  -> 5           |
   P1: write 6                             P1: write 6              |
   P2: write 6       <- P1's increment     P1: unlock --------------+
       is lost; result 6, not 7            P2: lock (waited here)
                                           P2: read  -> 6
                                           P2: write 7   correct

   SHARED / EXCLUSIVE COMPATIBILITY

               requested
               shared   exclusive
   held  none    OK        OK
       shared    OK        BLOCK
    exclusive   BLOCK      BLOCK

   THE POSIX-LOCK FOOTGUN

     fd1 = open("f")        # take lock via fd1
     lock(fd1, WRITE)
     fd2 = open("f")        # unrelated read elsewhere in the program
     close(fd2)             # <-- RELEASES THE LOCK held via fd1
     ...                    # still writing, now unprotected

import fcntl, os, struct, time

# --- whole-file advisory lock (flock): simple and fork-friendly ---
def with_flock(path, exclusive=True):
    f = open(path, "r+b")
    fcntl.flock(f, fcntl.LOCK_EX if exclusive else fcntl.LOCK_SH)
    return f                                     # released on close or unlock

# --- byte-range lock (fcntl): lock only the record you touch ---
def lock_range(fd, start, length, write=True, blocking=True):
    lock_type = fcntl.F_WRLCK if write else fcntl.F_RDLCK
    #            type    whence  start   len    pid
    flock = struct.pack("hhllh", lock_type, os.SEEK_SET, start, length, 0)
    cmd = fcntl.F_SETLKW if blocking else fcntl.F_SETLK
    fcntl.fcntl(fd, cmd, flock)                  # raises OSError(EAGAIN) if held

# --- a correct read-modify-write on a shared counter ---
def increment(path):
    with open(path, "r+b") as f:
        fcntl.flock(f, fcntl.LOCK_EX)            # hold across BOTH operations
        f.seek(0)
        value = int(f.read() or b"0")
        f.seek(0); f.truncate()
        f.write(str(value + 1).encode())
        f.flush(); os.fsync(f.fileno())          # durable before unlocking
        fcntl.flock(f, fcntl.LOCK_UN)
    return value + 1

# --- the lock-free alternative: atomic replace, no cooperation needed ---
def atomic_write(path, data: bytes):
    tmp = f"{path}.tmp.{os.getpid()}"
    fd = os.open(tmp, os.O_CREAT | os.O_WRONLY | os.O_EXCL, 0o644)
    try:
        os.write(fd, data)
        os.fsync(fd)                             # data durable BEFORE rename
    finally:
        os.close(fd)
    os.rename(tmp, path)                         # atomic: readers see old or new
    dir_fd = os.open(os.path.dirname(path) or ".", os.O_RDONLY)
    os.fsync(dir_fd)                             # make the RENAME durable too
    os.close(dir_fd)

# --- O_EXCL as a mutual-exclusion primitive ---
def try_acquire_lockfile(path):
    try:
        fd = os.open(path, os.O_CREAT | os.O_EXCL | os.O_WRONLY)
        os.write(fd, str(os.getpid()).encode())
        os.close(fd)
        return True                              # exactly one process wins
    except FileExistsError:
        return False                             # note: stale locks need a policy

# Who holds which locks, system-wide.
cat /proc/locks
#   1: FLOCK  ADVISORY  WRITE 3412 08:01:917 0 EOF
#   2: POSIX  ADVISORY  WRITE 3510 08:01:918 0 1023
#      ^type  ^mandatory?      ^pid ^maj:min:inode  ^range

# Shell-level locking: serialise a cron job against itself.
flock -n /var/lock/backup.lock -c '/usr/local/bin/backup.sh' \
  || echo "another run is in progress"

# Demonstrate the shared/exclusive rule interactively.
flock -s /tmp/f -c 'sleep 5' &      # shared holder
flock -s /tmp/f -c 'echo second shared: granted'   # granted immediately
flock -x /tmp/f -c 'echo exclusive: granted'       # waits for the shared holder

Key takeaways

• A single read() or write() is atomic against other reads and writes, but nothing spanning two system calls is — that is where locks are required.
• POSIX locks are advisory: they bind only processes that ask for them, which is a deliberate robustness choice.
• flock locks whole files and is tied to the open file description; fcntl locks byte ranges and is tied to the process, so closing any descriptor to the file drops them.
• Linux OFD locks (F_OFD_SETLK) combine byte-range granularity with open-file-description lifetime and are the sane modern default.
• Shared locks coexist; an exclusive lock excludes everything — and lock ordering still matters, because file locks can deadlock.
• Write-temp + fsync + rename gives atomic updates with no cooperation from readers, and O_CREAT|O_EXCL gives mutual exclusion without a lock manager.
• Network file systems may offer only close-to-open consistency, so locally correct sharing code can break over NFS.

🧪 Practice

1. Write two processes that each increment a counter in a shared file 1,000 times without locking, and measure the final value. Add flock and confirm the result becomes 2,000.
2. Demonstrate the POSIX-lock footgun: take an fcntl write lock via one descriptor, open and close a second descriptor to the same file, then show from /proc/locks that the lock is gone.
3. Interview-style: "A config-reloading daemon occasionally reads a truncated config file. Nobody wants to add locking to the editor. Fix it." Hint: the writer can make the update indivisible from the reader's point of view without the reader participating at all.

<a id="102-file-system-implementation"></a>

10.2 File System Implementation

This section goes underneath the interface: the layers that turn read(fd, buf, 4096) into a request for a physical block, the on-disk record that describes a file, the abstraction that lets one kernel support forty different file systems at once, how directories are actually searched, and what a formatted volume contains.

Layered File System Design

Theory

A file system implementation is a stack of translations, each converting one addressing scheme into a simpler one. Layering here is not architectural decoration — it exists because the translations are genuinely independent, and because the same lower layers serve many upper ones.

Work from the top down:

1. Application / library layer. fopen, fprintf, fread in the C standard library. This layer's job is buffering: it accumulates small writes so the layer below sees few large calls instead of many tiny ones. It is user space, which is why a printf that has not been flushed is lost when a process crashes.
2. System-call interface. open, read, write, close. The boundary crossing of Chapter 1: arguments are validated, the descriptor is resolved, and control passes to the kernel.
3. Virtual File System (VFS). Dispatches the operation to the correct file system implementation based on which file system the inode belongs to. This is what lets /home be ext4 and /mnt/share be NFS with no caller-visible difference.
4. Logical file system. The file-system-specific logic: metadata management, directory structures, permission checks, and the mapping from a file's logical block number to a physical block number on the volume. This is where ext4, XFS, and NTFS actually differ from each other.
5. Buffer / page cache. Caches blocks in RAM, absorbs re-reads, batches writes, and issues read-ahead. Most requests stop here and never reach a device.
6. Block layer / I/O scheduler. Merges adjacent requests, orders them (Chapter 9), and maintains the request queues.
7. Device driver. Turns a block request into register writes and DMA descriptors for the specific controller.
8. Device. Executes it.

The central translation is layer 4's: logical block N of this file to physical block M of this volume. Everything above layer 4 thinks in terms of a file's own numbering, starting at zero; everything below thinks in terms of the volume's numbering. Allocation methods (Section 10.3) are precisely the different answers to how that mapping is stored.

Layering has a cost, and it is not hypothetical: each layer copies or at least re-describes the data, and each has its own metadata to maintain. This is why performance-sensitive paths have carved shortcuts through it — O_DIRECT skips the page cache, sendfile() and splice() avoid the copy into user space entirely, and io_uring removes the per-operation system-call crossing. Each is a deliberate hole in the abstraction, taken in exchange for a specific cost.

Example

   ONE read() CALL, ALL THE WAY DOWN

   fread(buf, 1, 100, fp)        user space, stdio buffer (4 KB)
     |  buffer miss
     v
   read(fd, kbuf, 4096)          SYSTEM CALL BOUNDARY  <<< mode switch
     |
     v
   VFS: vfs_read()               which file system owns this inode?
     |  dispatch via inode->i_fop->read_iter
     v
   ext4_file_read_iter()         logical file block 3 -> physical block 91,447
     |  (extent tree lookup)
     v
   page cache lookup             HIT  -> copy out, DONE (~100 ns)
     |  MISS
     v
   block layer: submit_bio()     merge + schedule (mq-deadline / none)
     |
     v
   nvme driver                   build command, ring doorbell, DMA
     |
     v
   device                        ~80 us ... completion interrupt

   THE COST OF DEPTH, AND THE SHORTCUTS

   normal:      device -> page cache -> kernel buf -> user buf -> socket
   sendfile():  device -> page cache -----------------------------> socket
   O_DIRECT:    device -----------------------------> user buf   (no cache)

# The layer-1 (library buffering) effect, made visible.
import os, time

N = 200_000

# Buffered: stdio accumulates, so few system calls reach the kernel.
t0 = time.perf_counter()
with open("buffered.txt", "w") as f:              # default buffer ~8 KB
    for i in range(N):
        f.write("x")
buffered = time.perf_counter() - t0

# Unbuffered: one system call per byte -- one boundary crossing per byte.
t0 = time.perf_counter()
fd = os.open("raw.txt", os.O_CREAT | os.O_WRONLY | os.O_TRUNC, 0o644)
for i in range(N):
    os.write(fd, b"x")                            # ~200,000 mode switches
os.close(fd)
unbuffered = time.perf_counter() - t0

print(f"buffered   {buffered:.3f}s")
print(f"unbuffered {unbuffered:.3f}s  ({unbuffered/buffered:.1f}x slower)")
# The work is identical; the difference is purely layer crossings.

# Count the crossings rather than guessing at them.
strace -c -e trace=write python3 buffered_vs_raw.py
#   calls  syscall
#      25  write      <- buffered path
# 200000  write       <- unbuffered path

# Watch a single read descend the stack.
sudo bpftrace -e '
  tracepoint:syscalls:sys_enter_read /comm=="cat"/ { printf("syscall\n"); }
  kprobe:vfs_read                    /comm=="cat"/ { printf("  vfs\n");   }
  kprobe:ext4_file_read_iter         /comm=="cat"/ { printf("    ext4\n");}
  kprobe:submit_bio                  /comm=="cat"/ { printf("      bio\n");}'

# Where requests actually stop: cache hit ratio.
cat /proc/meminfo | grep -E 'Cached|Dirty|Writeback'

Key takeaways

• The implementation is a stack of translations: library buffering, system calls, VFS dispatch, file-system logic, page cache, block layer, driver, device.
• The defining translation is logical-file-block to physical-volume-block; allocation methods are the different ways of storing that mapping.
• Library buffering exists to reduce system calls; kernel caching exists to reduce device I/O. They are separate and both matter.
• Most reads never reach a device — the page cache is where the majority of requests are answered.
• Layers cost copies and metadata work, which is why O_DIRECT, sendfile, splice, and io_uring exist as deliberate bypasses.
• Knowing which layer a slowdown lives in is the first diagnostic step; strace, cache statistics, and block-layer tracing each look at a different one.

🧪 Practice

1. Write the same 1 MB using 1-byte buffered writes and 1-byte raw os.write calls. Measure both and use strace -c to explain the difference by system-call count.
2. For each layer in the stack, name one tool that observes it and one symptom that would point you there.
3. Interview-style: "A service copies files from disk to a socket and is CPU-bound at 40% of line rate, with most time in memcpy. What do you change?" Hint: count how many times the data is copied on the normal path, and find the call that removes most of those copies.

File Control Block and Inodes

Theory

Every file needs a record holding its attributes and the location of its data. In the abstract this is the File Control Block (FCB); in UNIX it is the inode ("index node"), and in NTFS it is a record in the Master File Table. The idea is identical: a fixed-size structure, stored in a known place, reachable by number.

The inode is fixed-size (typically 128 or 256 bytes on ext4), and that constraint drives its most interesting design feature. An inode must describe a file that might be 12 bytes or 12 terabytes, using a fixed budget. The classic UNIX answer is a multi-level index: a handful of direct block pointers for small files, then indirect pointers for larger ones.

With 4 KB blocks and 4-byte block pointers, one indirect block holds 1,024 pointers, which gives the following ladder:

Pointer class	Blocks addressed	Bytes addressed	Cumulative max file size
12 direct	12	48 KB	48 KB
1 single indirect	1,024	4 MB	~4 MB
1 double indirect	1,024² = 1,048,576	4 GB	~4 GB
1 triple indirect	1,024³ ≈ 1.07 × 10⁹	4 TB	~4 TB

The elegance is that small files — which are the overwhelming majority — need no indirect blocks at all, so accessing any byte of them costs one inode read plus one data read. Large files pay progressively more indirection, but only where it is needed. The cost is that a byte near the end of a 100 GB file needs four block reads to locate (triple indirect, double, single, then data), which is why extent-based designs (Section 10.3) replaced this scheme for large files.

Crucially, the inode does not contain the file's name. The name is in the directory entry. This is what makes the following behaviours make sense:

• One file, many names (hard links), with a nlink counter in the inode.
• Rename is a directory operation; the inode is untouched, so renaming a huge file is instant.
• stat on a path does two lookups: the directory to find the inode number, then the inode.

Inodes live in a fixed-size inode table created at mkfs time. On classic ext-family file systems, the number of inodes is fixed forever at format time, which produces a genuinely surprising failure: a file system can run out of inodes while having free space, if it holds millions of tiny files. df -i is the tool that reveals it; the fix is reformatting with a higher inode density or switching to a file system that allocates inodes dynamically (XFS, Btrfs, ZFS).

Modern file systems add refinements worth knowing:

• Inline data. A file small enough to fit inside the inode's pointer area (roughly 60 bytes on ext4, up to the inode size on others) is stored in the inode. Zero data blocks, one read.
• Extended attributes. Key-value metadata (security.selinux, user.*) stored in the inode's spare space or a dedicated block.
• Nanosecond timestamps and 64-bit fields, because 32-bit second-resolution timestamps overflow in 2038.

Example

   ext2/ext3-STYLE INODE: A FIXED-SIZE RECORD ADDRESSING A HUGE FILE

   inode 8721 (256 bytes)
   +---------------------------+
   | mode  0100644             |  type + permission bits
   | uid/gid 1000/1000         |
   | size  5,242,880           |
   | nlink 1                   |
   | atime/mtime/ctime         |
   +---------------------------+
   | direct[0]  -> block 1201  |---> [ data ]   file block 0
   | direct[1]  -> block 1202  |---> [ data ]   file block 1
   |    ...    (12 total)      |                ... up to file block 11
   | direct[11] -> block 1212  |
   +---------------------------+
   | single indirect -> 1213   |---> [ 1024 pointers ] -> file blocks 12..1035
   +---------------------------+
   | double indirect -> 1214   |---> [ 1024 ptrs ] -+-> [1024 ptrs] -> data
   +---------------------------+                    +-> [1024 ptrs] -> data
   | triple indirect -> 1215   |                        ... 1,048,576 blocks
   +---------------------------+

   READS NEEDED TO REACH ONE DATA BLOCK
     file block 5          : inode + data                     = 2
     file block 500        : inode + single + data             = 3
     file block 500,000    : inode + double + single + data    = 4
     file block 900,000,000: inode + triple + double + single + data = 5
   (caching flattens this in practice, but the asymmetry is real.)

# Model the classic UNIX index and answer: how many reads to reach block N?
BLOCK      = 4096
PTR        = 4
PTRS_PER   = BLOCK // PTR              # 1024 pointers per indirect block
DIRECT     = 12

single_cap = PTRS_PER                            # 1,024
double_cap = PTRS_PER ** 2                       # 1,048,576
triple_cap = PTRS_PER ** 3                       # 1,073,741,824

def reads_for(file_block):
    """Block reads (excluding the inode) needed to locate one data block."""
    if file_block < DIRECT:
        return 1                                   # data only
    file_block -= DIRECT
    if file_block < single_cap:
        return 2                                   # indirect + data
    file_block -= single_cap
    if file_block < double_cap:
        return 3                                   # double + single + data
    file_block -= double_cap
    if file_block < triple_cap:
        return 4                                   # triple + double + single + data
    raise ValueError("beyond the file system's maximum file size")

max_bytes = (DIRECT + single_cap + double_cap + triple_cap) * BLOCK
print(f"max file size: {max_bytes / 1024**4:.2f} TiB")     # ~4.00 TiB

for b in [0, 11, 12, 1035, 1036, 60_000, 2_000_000]:
    print(f"file block {b:>10,}: {reads_for(b)} read(s)")

# Metadata overhead of the indirect blocks themselves, for a 4 GB file.
data_blocks     = (4 * 1024**3) // BLOCK                   # 1,048,576
indirect_blocks = 1 + (data_blocks - DIRECT - single_cap + PTRS_PER - 1) // PTRS_PER
print(f"data {data_blocks:,} blocks, index ~{indirect_blocks:,} blocks "
      f"({indirect_blocks/data_blocks:.2%} overhead)")      # ~0.10%

# Inode contents, in the raw.
stat -c 'inode=%i size=%s blocks=%b links=%h mode=%a' /etc/passwd
sudo debugfs -R "stat <$(stat -c %i /etc/passwd)" /dev/sda1
#   Inode: 41  Type: regular  Mode: 0644  Flags: 0x80000
#   Size: 2891
#   EXTENTS:  (0):918273           <- ext4 uses extents, not indirect blocks

# The failure everyone meets exactly once: out of inodes, not out of space.
df -h  /home        # Use%  61%
df -i  /home        # IUse% 100%   <- no more files can be created
# Root cause: millions of tiny files. Check with:
sudo find /home -xdev -printf '%h\n' | sort | uniq -c | sort -rn | head

# Inode density is fixed at format time.
sudo mkfs.ext4 -i 8192 /dev/sdb1     # one inode per 8 KB (dense: many small files)
sudo mkfs.ext4 -T largefile /dev/sdb1 # one inode per 1 MB (sparse: few huge files)
sudo tune2fs -l /dev/sda1 | grep -i 'inode count\|free inodes\|inode size'

Key takeaways

• An inode (or FCB) is a fixed-size record holding a file's attributes and the location of its data — but never its name.
• The classic UNIX layout uses 12 direct pointers plus single, double, and triple indirect blocks, so small files need no indirection and huge files remain addressable.
• Locating a block costs 1 to 4 extra reads depending on depth; caching hides most of it, but the asymmetry drove the move to extents.
• Because names live in directories, hard links, instant rename, and delete-while-open all follow naturally.
• ext-family file systems fix the inode count at mkfs time, so a volume can exhaust inodes with free space remaining — df -i diagnoses it.
• Modern refinements include inline data for tiny files, extended attributes, and 64-bit nanosecond timestamps.

🧪 Practice

1. With 8 KB blocks and 4-byte pointers, recompute the ladder: how many pointers per indirect block, and what maximum file size do 12 direct plus three indirect levels give?
2. A file system has 1 million inodes and 500 GB free. Explain how touch newfile can fail with ENOSPC, and how you would confirm the diagnosis.
3. Interview-style: "Why is renaming a 50 GB file instantaneous, while copying it to a sibling directory takes minutes?" Hint: identify exactly which structures each operation modifies, and how many bytes move in each case.

Virtual File System Layer

Theory

Linux supports over sixty file systems. Without a common abstraction, every system call would need a switch statement over all of them, and adding a new file system would mean editing the core kernel. The Virtual File System (VFS) is the indirection layer that prevents this: a set of object types and operation tables that every file system implements, so the rest of the kernel programs against the interface rather than the implementations.

If you have seen an interface with multiple implementations dispatched through a vtable, you already know the design — VFS is polymorphism implemented in C with structs of function pointers. vfs_read() does not know what ext4 is; it calls file->f_op->read_iter() and lets the pointer decide.

Four objects carry the abstraction:

Object	Represents	Key operations
superblock	A mounted file system instance	alloc_inode, write_inode, sync_fs, statfs
inode	A file (any type)	create, lookup, link, unlink, mkdir, rename, setattr
dentry	A name-to-inode binding (a path component)	d_revalidate, d_compare, d_hash
file	An open file description	read_iter, write_iter, mmap, llseek, fsync

The dentry is the one without an on-disk counterpart, and it is there for performance. Resolving /usr/share/doc/x/y.txt means six lookups, each of which would otherwise be a directory read. The dentry cache memoises name-to-inode bindings, including negative entries recording that a name does not exist — which is what makes a failing open() in a long $PATH cheap. In practice the dcache is one of the highest-hit-rate caches in the kernel.

The VFS pays off three times over:

1. Uniformity. One set of system calls works across ext4, XFS, NFS, FAT, and the synthetic file systems.
2. Extensibility. A new file system is a module implementing the operation tables; nothing above it changes. FUSE goes further and forwards the operations to a user-space process, so a file system can be written in Python without kernel code at all.
3. Virtual file systems that are not storage at all. /proc and /sys expose kernel state as files, tmpfs is RAM presented as a file system, devtmpfs holds device nodes. cat /proc/meminfo reads no disk; it calls a function that formats a string on demand. This is why "everything is a file" is an implementation strategy and not just a slogan.

Example

   VFS DISPATCH: ONE CALL, MANY IMPLEMENTATIONS

                       read(fd, buf, n)
                             |
                       +-----v------+
                       |    VFS     |   file->f_op->read_iter(...)
                       +-----+------+
          +------------+-----+-----+------------+-------------+
          |            |           |            |             |
      ext4_file_   xfs_file_   nfs_file_    proc_reg_     fuse_file_
      read_iter    read_iter   read_iter    read          read_iter
          |            |           |            |             |
       block dev   block dev   network    kernel func    user process
                                request    (no I/O)      (via /dev/fuse)

   THE FOUR OBJECTS, FOR ONE OPEN FILE

   file  (offset, flags, f_op)  ---> dentry ("notes.md", parent, d_op)
                                        |
                                        v
                                     inode (8721, i_op, i_fop, size, mode)
                                        |
                                        v
                                  superblock (ext4 on /dev/sda1, s_op)

   PATH RESOLUTION USES THE DCACHE
     /usr/share/doc/x/y.txt   -> 5 dentry lookups
     cached   : hash-table hits, no disk I/O
     uncached : a directory block read per component
     negative dentry: "this name does NOT exist here" -- also cached

# A FUSE file system: proof that the VFS interface is the whole contract.
# The kernel calls these methods; they could read a database, an API, anything.
import os, stat, errno
from fuse import FUSE, Operations          # pip install fusepy

class HelloFS(Operations):
    """A read-only file system with exactly one file: /hello"""
    CONTENT = b"VFS dispatched a read() here.\n"

    def getattr(self, path, fh=None):      # backs stat()/ls
        now = 0
        if path == "/":
            return dict(st_mode=(stat.S_IFDIR | 0o555), st_nlink=2)
        if path == "/hello":
            return dict(st_mode=(stat.S_IFREG | 0o444), st_nlink=1,
                        st_size=len(self.CONTENT), st_mtime=now)
        raise OSError(errno.ENOENT, "")

    def readdir(self, path, fh):           # backs ls
        return [".", "..", "hello"]

    def read(self, path, size, offset, fh):  # backs read()
        return self.CONTENT[offset:offset + size]

if __name__ == "__main__":
    FUSE(HelloFS(), "/mnt/hello", foreground=True, ro=True)

# $ cat /mnt/hello
# VFS dispatched a read() here.
# The kernel's read() path is unchanged; only the bottom implementation differs.

# Every file system the kernel currently knows how to mount.
cat /proc/filesystems
#   nodev   proc        <- "nodev": needs no block device
#   nodev   tmpfs
#           ext4
#           xfs

# Synthetic file systems: files with no storage behind them.
cat /proc/self/status | head -3     # generated on read, not stored
ls -l /proc/self/fd                 # symlinks into the kernel's fd table
mount -t tmpfs -o size=64M none /mnt/ram    # a file system living in RAM

# The dentry cache, observed.
grep -E 'dentry|inode_cache' /proc/slabinfo | awk '{print $1, $2, $3}'
#   dentry  <active objects> <total objects>

sudo sysctl vm.vfs_cache_pressure     # how aggressively dentries are reclaimed
sudo bpftrace -e 'kprobe:d_lookup { @[comm] = count(); }'   # dcache lookups by process

Key takeaways

• VFS is an interface layer: four object types (superblock, inode, dentry, file) each with an operation table of function pointers.
• System calls program against VFS, so a new file system is a module and nothing above it changes.
• The dentry cache memoises path-component lookups, including negative entries, and is critical to path-resolution performance.
• The abstraction covers non-storage file systems: /proc and /sys synthesise content on read, tmpfs lives in RAM.
• FUSE forwards VFS operations to a user-space process, letting a file system be written in any language without kernel code.
• The cost is one indirect call per operation — negligible against the I/O it guards, and it buys the entire pluggability of the storage stack.

🧪 Practice

1. List the four VFS objects and, for each, name a system call whose implementation must touch it.
2. Explain what a negative dentry is and give a workload where caching them measurably helps.
3. Interview-style: "Design an interface that makes an S3 bucket appear as a mounted directory. What are the three hardest semantics to emulate?" Hint: think about operations a byte-stream file system offers cheaply that an object store does not — partial writes, rename, and directory semantics are good places to start.

Directory Implementation

Theory

A directory is a file, so the question "how is a directory implemented" is really "what data structure is stored inside that file, and how is it searched". The answer determines whether a directory with a million entries is usable.

Linear list. Entries are stored one after another; lookup is a scan. This is what original UNIX and ext2 did, and it is fine up to a few hundred entries. Beyond that the O(n) scan dominates: creating N files costs O(N²), because each creation scans the whole directory to check the name does not already exist. Deletion leaves holes that must be reused or compacted. The one virtue is simplicity — and that a scan is a sequential read, which storage likes.

Hash table. Hash the name to find a bucket, so lookup is O(1) on average. This is much better for lookups, but it must handle collisions and, more awkwardly, it must handle growth: a fixed bucket count degrades as the directory fills. It also destroys ordering, so readdir returns names in hash order — which is why ls sorts, and why reading files in readdir order can produce terrible inode-access locality.

B-tree / B+-tree. Entries are kept in a balanced tree keyed by name or by name hash, giving O(log n) lookup with a very small base — a tree of depth 2 or 3 covers millions of entries. It handles growth gracefully, supports ordered traversal, and is what every serious modern file system uses: ext4's htree (a hashed B-tree, usually depth 1 or 2), XFS's B+-trees, NTFS's B+-trees indexed by filename, Btrfs and ZFS with their own variants.

A separate design axis is what the entry contains. Storing only (name, inode number) keeps entries small, so more fit per block and scans are fast; but then ls -l, which needs every file's size and mode, must read N inodes scattered across the volume. Storing attributes in the directory entry makes ls -l a single sequential read but bloats the directory and duplicates data that hard links must keep consistent. UNIX chose small entries; some file systems cache a few fields (ext4 stores the file type in the entry, so ls -F and find -type avoid the inode reads).

Entry layout in practice is variable-length, because names are. ext4's classic entry is a record with inode, rec_len, name_len, file_type, and the name bytes. Deletion is implemented by extending the previous entry's rec_len over the deleted one, which is why deleted names are often still visible in a raw directory block — a fact both forensics and undelete tools rely on.

Example

   LINEAR DIRECTORY BLOCK (ext2-style, 4 KB)

   off 0    +-------------------------------------------+
            | inode 8721 | rec_len 12 | len 1 | "."     |
   off 12   +-------------------------------------------+
            | inode    2 | rec_len 12 | len 2 | ".."    |
   off 24   +-------------------------------------------+
            | inode 9001 | rec_len 20 | len 8 | "main.c"|
   off 44   +-------------------------------------------+
            | inode 9002 | rec_len 4052| len 5| "notes" |   <- rec_len extended
            +-------------------------------------------+      to cover a
              DELETED "old.txt" used to live here;             deleted entry
              its bytes are still on disk.

   LOOKUP COST BY STRUCTURE (directory with 100,000 entries)

   linear     : ~50,000 entry comparisons average, many block reads    O(n)
   hash       : 1 hash + 1 bucket read (+ collision chain)             O(1)
   htree/B+   : 1 index block + 1 leaf block                           O(log n)

   ext4 HTREE (hashed B-tree, depth 1)

                  root index block
                  [ hash<0x2f -> blk 7 | hash<0x91 -> blk 12 | ... ]
                          |                    |
                  leaf block 7           leaf block 12
                  [ linear entries ]     [ linear entries ]
              (leaves are still linear scans -- but of ONE block)

import time, os, shutil

# Demonstrate the quadratic behaviour of linear directories -- and its absence
# once an htree kicks in. ext4 converts to htree automatically past one block.
def create_n(dirpath, n):
    os.makedirs(dirpath, exist_ok=True)
    t0 = time.perf_counter()
    for i in range(n):
        open(f"{dirpath}/file_{i:07d}", "w").close()   # each create checks for
    return time.perf_counter() - t0                    # an existing name

def lookup_n(dirpath, n, probes=2000):
    t0 = time.perf_counter()
    for i in range(probes):
        os.stat(f"{dirpath}/file_{(i * 7919) % n:07d}")  # scattered probes
    return (time.perf_counter() - t0) / probes * 1e6     # microseconds each

for n in (1_000, 10_000, 100_000):
    d = f"/tmp/dirtest_{n}"
    shutil.rmtree(d, ignore_errors=True)
    create = create_n(d, n)
    lookup = lookup_n(d, n)
    print(f"n={n:>7,}  create {create:6.2f}s  lookup {lookup:6.2f} us/op")
    shutil.rmtree(d, ignore_errors=True)
# With htree, lookup stays roughly flat as n grows by 100x.
# On a linear-directory file system it would grow roughly linearly.

# readdir order is NOT sorted, and NOT inode order.
d = "/tmp/dirtest_order"; os.makedirs(d, exist_ok=True)
for name in ["zebra", "apple", "mango", "kiwi"]:
    open(f"{d}/{name}", "w").close()
print(os.listdir(d))          # hash order, e.g. ['mango','zebra','apple','kiwi']
# Sorting by inode before stat()ing improves locality on large directories:
entries = sorted(os.scandir(d), key=lambda e: e.inode())

# Is this directory using an htree?
sudo debugfs -R "stat /home/ana/maildir" /dev/sda1 | grep -i 'flags\|htree'
#   Flags: 0x81000   (0x1000 = EXT4_INDEX_FL, i.e. hashed tree)
sudo tune2fs -l /dev/sda1 | grep -i 'filesystem features'
#   ... dir_index dir_nlink ...    <- dir_index enables htree

# A directory file is a file: it has a size that only grows.
mkdir big && touch big/{1..50000}
stat -c '%n size=%s' big           # size=1077248 -- the directory's own data
rm big/*
stat -c '%n size=%s' big           # size=1077248 -- ext4 does NOT shrink it
# The fix is to recreate the directory, not to delete its contents.

# Tools that suffer from readdir-order access.
ls -U big | head        # -U: raw readdir order, no sort (fast on huge dirs)
ls big | head           # sorts: reads the whole directory first

Key takeaways

• A directory is a file whose contents are entries; the structure inside it decides lookup cost.
• Linear lists are simple but O(n) per lookup, making N creations O(N²) — fine for small directories, disastrous for large ones.
• Hash tables give O(1) lookup but lose ordering and need a growth strategy; B-trees give O(log n) with ordered traversal and graceful growth.
• ext4's htree, XFS's and NTFS's B+-trees are the modern answer; ext4 converts a directory to htree automatically once it outgrows one block.
• Entries store (name, inode) plus a little; putting full attributes in the entry speeds ls -l but duplicates state and bloats the directory.
• Deletion typically merges the entry's space into its predecessor, leaving the old bytes recoverable, and directory files generally do not shrink after mass deletion.

🧪 Practice

1. Compute the average number of entry comparisons for a linear directory of 50,000 entries, and the number of block reads for an htree of depth 1 over the same directory.
2. Create 100,000 files in one directory, delete them all, and show that the directory's own size does not shrink. Explain why and give the remedy.
3. Interview-style: "A mail server slowed down as one spool directory grew to 300,000 files, even though total data was unchanged. Diagnose and propose two fixes." Hint: consider both the directory structure in use and the access order a naive readdir loop produces.

Partition and Volume Layout

Theory

Before a file system exists there is a raw device; before files exist there is a layout. This topic is about what occupies a formatted volume and in what order, because that layout determines both how the file system is found at boot and how well it performs afterwards.

Three levels stack up:

1. The device, presenting logical blocks 0..N-1.
2. The partition table, dividing the device into partitions. MBR (four primary entries, 32-bit block addresses, 2 TB limit) has been replaced by GPT (128 entries by default, 64-bit addresses, a CRC-protected header with a backup copy at the end of the disk).
3. The volume, either one partition or a logical volume assembled from several by LVM, RAID, or ZFS's pooling — and formatted with one file system.

Inside a formatted volume, the classic layout is fixed and knowable:

• Boot block. The first block(s), reserved for bootstrap code. Under UEFI this role has largely moved to a FAT-formatted EFI System Partition holding .efi files, which is far easier to manage than raw sectors.
• Superblock. The file system's own descriptor: magic number, block size, total blocks, free counts, inode count, the location of everything else, the mount count, and a clean/dirty flag. It is small, essential, and therefore replicated — losing the primary copy without a backup would render the volume unreadable, so mkfs scatters spares through the volume.
• Inode table / MFT. The array of file records.
• Free-space maps. Bitmaps or trees recording which blocks and inodes are free (Section 10.3).
• Data blocks. Everything else.

A crucial refinement is locality grouping. Putting one inode table at the start of a 4 TB volume would mean every file access seeks between the far end (data) and the start (metadata). The Berkeley Fast File System introduced cylinder groups — later block groups in ext2/3/4 and allocation groups in XFS — dividing the volume into regions, each with its own superblock copy, inode table, bitmaps, and data area. A file's inode and its data then live in the same group, and a directory's files are placed in the same group as the directory. On rotating media this cut seek distance dramatically; on flash it still helps by improving metadata locality and reducing contention, since XFS allocation groups can be updated in parallel.

Two modern wrinkles are worth stating. First, alignment: a partition must start on a boundary that matches the device's physical block size and, on SSDs, the erase-block granularity — a misaligned partition turns each 4 KB write into a read-modify-write of two physical blocks. Modern tools align to 1 MiB by default, which satisfies every plausible geometry. Second, pooled storage: ZFS and Btrfs abandon the fixed-partition model altogether, managing a pool of devices and carving datasets from it dynamically, so "how big should /home be" stops being a decision made at install time.

Example

   DISK -> PARTITIONS -> FORMATTED VOLUME

   /dev/sda  (GPT)
   +--------+------------------+--------------------------------+--------+
   | GPT hdr|  ESP (FAT32)     |   /dev/sda2  (ext4)            | backup |
   | + table|  /dev/sda1 512M  |   ...                          | GPT hdr|
   +--------+------------------+--------------------------------+--------+
       LBA 1        aligned to 1 MiB boundaries                   last LBA

   INSIDE /dev/sda2: ext4 WITH BLOCK GROUPS

   +-------+=========== block group 0 ===========+=== group 1 ===+ ...
   | boot  | SB | GDT | blk bmp | ino bmp | inode|  (same layout, |
   | block |    |     |         |         | table|   SB is a      |
   |       |    |     |         |         |      |   BACKUP copy) |
   +-------+----+-----+---------+---------+------+----------------+
                                          | data blocks          |
                                          +----------------------+

   WHY GROUPS: a file's inode and data land in the SAME group.
     one table at LBA 0 : metadata read at 0, data read at 3.9 TB -> long seek
     per-group tables   : both reads inside one group             -> short seek

   MISALIGNMENT (why 1 MiB alignment is the default)

   aligned    | 4K phys | 4K phys | 4K phys |     one write -> one block
   partition  ^start
   misaligned    | 4K logical write spans TWO physical blocks |
              ^start (off by 512B)   -> read both, modify, write both

# Level 2: the partition table.
sudo gdisk -l /dev/sda
#   Number  Start (sector)  End (sector)  Size     Code  Name
#      1            2048       1050623    512.0 MiB EF00  EFI System
#      2         1050624    1953523711    931.0 GiB 8300  Linux filesystem
# Start=2048 sectors x 512 B = 1 MiB: correctly aligned.

sudo blockdev --getpbsz --getss /dev/sda    # physical and logical sector size
lsblk -o NAME,ALIGNMENT,PHY-SEC,LOG-SEC     # ALIGNMENT 0 means aligned

# Level 3: what mkfs wrote.
sudo dumpe2fs /dev/sda2 | head -40
#   Filesystem magic number:  0xEF53
#   Block size:               4096
#   Blocks per group:         32768        <- one group covers 128 MiB
#   Inodes per group:         8192
#   Reserved block count:     ...          <- 5% reserved for root by default

sudo dumpe2fs /dev/sda2 | grep -i superblock | head
#   Primary superblock at 0, Group descriptors at 1-1
#   Backup superblock at 32768, Group descriptors at 32769-32769
#   Backup superblock at 98304, ...

# Recovering from a destroyed primary superblock.
sudo fsck.ext4 -b 32768 /dev/sda2          # mount using a backup copy

# XFS: allocation groups, sized for parallelism rather than seek distance.
sudo xfs_info /mnt/data
#   data     =  bsize=4096  blocks=244190646  agcount=4  agsize=61047661
# More allocation groups -> more parallel metadata updates, more fragmentation risk.

# Why block groups reduce seek distance, quantified.
VOLUME_BLOCKS   = 1_000_000_000          # 4 TB of 4 KB blocks
GROUPS          = 30_000                 # ext4: one group per 128 MiB
BLOCKS_PER_GROUP = VOLUME_BLOCKS // GROUPS

# Layout A: a single inode table at the front of the volume.
def seek_distance_single(data_block):
    return abs(data_block - 0)           # inode at block 0, data far away

# Layout B: per-group inode tables, inode placed with its data.
def seek_distance_grouped(data_block):
    group_start = (data_block // BLOCKS_PER_GROUP) * BLOCKS_PER_GROUP
    return abs(data_block - group_start) # never leaves the group

for block in (5_000, 500_000_000, 999_000_000):
    a = seek_distance_single(block)
    b = seek_distance_grouped(block)
    print(f"data at {block:>13,}: single-table {a:>13,} blocks, "
          f"grouped {b:>7,} blocks  ({a/max(b,1):,.0f}x closer)")
# The grouped distance is bounded by the group size, regardless of volume size.

Key takeaways

• A device carries a partition table (GPT, with a CRC-protected backup header, having replaced MBR), and each partition or logical volume is formatted with one file system.
• A formatted volume holds a boot block, a superblock, inode and free-space metadata, and data blocks.
• The superblock describes everything else and is replicated, so a damaged primary copy is recoverable with fsck -b.
• Block groups (ext), cylinder groups (FFS), and allocation groups (XFS) keep a file's metadata near its data, bounding seek distance by group size rather than volume size.
• Partition alignment to 1 MiB avoids turning every write into a read-modify-write on 4 KB-sector devices and SSDs.
• Pooled designs (ZFS, Btrfs) replace fixed partitions with datasets carved from a device pool, removing the sizing decision from install time.

🧪 Practice

1. Run dumpe2fs on a volume and report the block size, blocks per group, inodes per group, and the location of the first three backup superblocks. Explain how you would use one.
2. A partition starts at sector 63 on a drive with 4,096-byte physical sectors. Show what happens on a 4 KB write and quantify the extra I/O.
3. Interview-style: "Why does XFS let you choose the number of allocation groups, and what goes wrong at both extremes?" Hint: allocation groups are units of independent metadata locking, but each one manages its own free space.

<a id="103-allocation-and-free-space"></a>

10.3 Allocation and Free Space

Every file system must answer two questions: given a file's logical block number, which physical block holds it, and where do free blocks come from. This section works through the three classical allocation strategies and the modern one that replaced them, then covers the structures that track free space and the block-size trade-off that underlies all of it.

Contiguous Allocation

Theory

The simplest possible answer to "where are this file's blocks" is: all in a row. Contiguous allocation stores a file in consecutive physical blocks, so the inode needs exactly two numbers — the starting block and the length.

The advantages are substantial and worth taking seriously, because this scheme keeps returning in new clothing:

• Minimal metadata. Two integers describe a file of any size. No index blocks, no pointer chasing.
• Direct access is trivial. Logical block i is physical block start + i, computed with one addition. Sequential and random access are equally cheap to locate.
• Best possible I/O performance. The whole file is one extent, so reading it is one sequential transfer with one positioning cost. On an HDD this is the difference between 150 MB/s and 1 MB/s.

The problem is allocation itself, and it is the same problem as contiguous memory allocation in Chapter 7 — with one extra difficulty that makes it worse. Finding a run of n free blocks requires a first-fit, best-fit, or worst-fit search, and repeated allocation and deletion produces external fragmentation: plenty of free space, no single run large enough. Compaction fixes it, but compacting a terabyte volume means rewriting it, offline.

The extra difficulty is growth. Memory allocations usually know their size; files usually do not. A log file, a download, a database — all start small and grow unpredictably. Contiguous allocation must therefore either know the final size at creation (which is how mainframe systems did it, requiring the user to declare it and failing hard when the estimate was too small) or over-allocate and waste space, or relocate the whole file when it outgrows its run.

So pure contiguous allocation is not used for general-purpose file systems. But the idea survives everywhere, because the performance argument never stopped being true:

• Extents (later in this section) are contiguous runs, just many per file — contiguous allocation applied piecewise.
• Preallocation (fallocate, posix_fallocate) reserves a contiguous run in advance, which is exactly how databases and VM images avoid fragmentation.
• CD-ROM, DVD, and archive formats use contiguous allocation outright, because the content is written once and never grows.

Example

   CONTIGUOUS ALLOCATION AND ITS FAILURE MODE

   directory                     volume blocks 0..24
   +--------+-------+-------+
   | file   | start | len   |   0  1  2  3  4  5  6  7  8  9 10 11 12
   +--------+-------+-------+  [A][A][A][ ][ ][B][B][B][B][ ][C][C][C]
   | a.txt  |   0   |   3   |
   | b.bin  |   5   |   4   |   13 14 15 16 17 18 19 20 21 22 23 24
   | c.dat  |  10   |   3   |  [ ][ ][D][D][ ][ ][ ][E][E][E][ ][ ]
   | d.log  |  15   |   2   |
   | e.img  |  20   |   3   |   free: 3,4  9  13,14  18,19,20  23,24
   +--------+-------+-------+         = 10 free blocks, LARGEST RUN = 3

   REQUEST: a new 5-block file.
     Total free 10 >= 5, but no run of 5 exists.  ALLOCATION FAILS.
     This is EXTERNAL FRAGMENTATION.

   REQUEST: d.log grows from 2 to 4 blocks.
     Blocks 17 is free but 18,19 belong to nobody... wait, 18,19 ARE free,
     so it can extend to 4. Grow to 6 and it cannot: E sits at 20.
     The file must be RELOCATED entirely, or fail.

   ADDRESSING IS TRIVIAL, THOUGH:
     logical block i of b.bin  ->  physical block 5 + i     (one addition)

# A contiguous allocator, and a measurement of how fast it fragments.
import random

class ContiguousVolume:
    def __init__(self, nblocks):
        self.free = [True] * nblocks
        self.files = {}                       # name -> (start, length)

    def _first_fit(self, n):
        run = 0
        for i, is_free in enumerate(self.free):
            run = run + 1 if is_free else 0
            if run == n:
                return i - n + 1              # start of the run
        return None                           # no run large enough

    def create(self, name, n):
        start = self._first_fit(n)
        if start is None:
            return False                      # external fragmentation
        for b in range(start, start + n):
            self.free[b] = False
        self.files[name] = (start, n)
        return True

    def delete(self, name):
        start, n = self.files.pop(name)
        for b in range(start, start + n):
            self.free[b] = True

    def block_of(self, name, logical):
        start, n = self.files[name]
        assert logical < n
        return start + logical                # O(1) direct access

    def stats(self):
        total_free = sum(self.free)
        largest, run = 0, 0
        for f in self.free:
            run = run + 1 if f else 0
            largest = max(largest, run)
        return total_free, largest

vol = ContiguousVolume(10_000)
random.seed(7)
names, failures = [], 0

for step in range(20_000):
    if names and random.random() < 0.45:          # churn: delete something
        vol.delete(names.pop(random.randrange(len(names))))
    else:
        name, size = f"f{step}", random.randint(1, 40)
        if vol.create(name, size):
            names.append(name)
        else:
            failures += 1

free, largest = vol.stats()
print(f"failed allocations : {failures}")
print(f"free blocks        : {free}")
print(f"largest free run   : {largest}")
print(f"fragmentation      : {1 - largest/max(free,1):.1%} of free space unusable "
      f"for a single max-size request")
# Typical output: thousands of free blocks, a largest run far smaller.

# Contiguous allocation, deliberately requested: preallocation.
fallocate -l 10G /var/lib/vm/disk.img         # reserve 10 GB, ideally in few extents
filefrag -v /var/lib/vm/disk.img
#   File size of disk.img is 10737418240 (2621440 blocks of 4096 bytes)
#   ext:  logical_offset:  physical_offset: length:  flags:
#     0:        0..2621439: 918273..3539712: 2621440: last,eof
#   disk.img: 1 extent found         <- one contiguous run: ideal

# The same file grown by appending, for contrast.
for i in $(seq 200); do dd if=/dev/zero of=grown.img bs=1M count=10 \
    oflag=append conv=notrunc status=none; done
filefrag grown.img
#   grown.img: 137 extents found     <- interleaved with other writes

# Media that use contiguous allocation for real.
mkisofs -o archive.iso ./data/       # ISO 9660: write-once, so contiguity is free

Key takeaways

• Contiguous allocation stores a file in consecutive blocks, so the metadata is just (start, length) and block lookup is one addition.
• It gives the best possible I/O performance, because the whole file is one sequential transfer.
• It suffers external fragmentation exactly as contiguous memory allocation does, and compaction requires rewriting the volume.
• Its fatal flaw for general use is growth: files rarely know their final size, so the scheme forces over-allocation, declaration, or relocation.
• The idea survives in extents (many contiguous runs per file), in preallocation (fallocate), and in write-once media.
• When a workload does know its size — database files, VM images — preallocating is the practical way to buy contiguity back.

🧪 Practice

1. Given the free list [0-2, 7-9, 14-20, 25-26], show first-fit, best-fit, and worst-fit placement for a 3-block request, and give the resulting free list in each case.
2. Run the fragmentation simulation above with different churn rates and report how the largest free run degrades. At what point do allocations begin to fail?
3. Interview-style: "Why do database vendors tell you to preallocate the data file to its expected final size?" Hint: think about what happens to physical layout when a file grows by small increments while other files are also being written.

Linked Allocation

Theory

If contiguity is impossible to maintain, drop the requirement entirely: let a file's blocks be scattered anywhere, and have each block point to the next. Linked allocation stores a head pointer (and usually a tail pointer) in the directory entry, and reserves a few bytes in each data block for the next-block pointer.

This solves every problem contiguous allocation had. There is no external fragmentation, because any free block will do. Files grow by allocating one more block anywhere and updating one pointer. No declaration of size is needed, and no relocation ever happens.

It introduces one problem, and the problem is fatal for general use: random access is O(n). To read logical block 5,000 you must read blocks 0 through 4,999 first, because each one contains the address of the next. There is no way to shortcut the chain. For a purely sequential workload this is acceptable; for anything that seeks, it is catastrophic.

Two lesser problems compound it:

• Reliability. One corrupted pointer loses the entire remainder of the file, and there is no redundant information from which to reconstruct it. Doubly-linked variants and storing the file number in each block help, at the cost of more space.
• Space overhead and awkward arithmetic. If a 4,096-byte block reserves 4 bytes for a pointer, usable capacity is 4,092 bytes — a number that no longer divides nicely into memory pages, so applications that assume power-of-two block boundaries misalign.

The important refinement is the File Allocation Table (FAT), used by MS-DOS and still in use today on removable media. FAT pulls the pointers out of the data blocks and gathers them into one table at the start of the volume, indexed by block number. Entry i holds the number of the block following block i in whatever file contains it, or a marker for end-of-chain, free, or bad.

This one change fixes most of the practical objections. Data blocks are again a clean power of two. The whole chain for a file can be walked in memory once the FAT is cached, so random access becomes a memory traversal rather than a disk traversal. And the table doubles as the free-space map, since free blocks are marked as such in the same array.

FAT's remaining weaknesses are exactly the ones that limit it today: the table must be cached to perform, and it grows with volume size (a 2 TB FAT32 volume needs a ~500 MB table at 4 KB clusters); a corrupted FAT damages every file at once, which is why two copies are kept; and traversal is still O(n) in the table, which shows up on very large files.

Example

   LINKED ALLOCATION (pointers inside data blocks)

   directory: file.dat  start=9  end=25

   block 9            block 16           block 4            block 25
   +------------+     +------------+     +------------+     +------------+
   | data 4092B |     | data 4092B |     | data 4092B |     | data 4092B |
   | next -> 16 |---->| next ->  4 |---->| next -> 25 |---->| next -> -1 |
   +------------+     +------------+     +------------+     +------------+

   To read LOGICAL BLOCK 3 you must read 9, 16, 4, then 25: FOUR reads,
   three of them pure overhead.  For logical block 5,000: 5,001 reads.

   FAT: THE SAME CHAIN, BUT THE POINTERS LIVE IN ONE TABLE

   File Allocation Table (one entry per cluster, cached in RAM)
   index:   0   1   2   3   4   5  ...  9  ...  16  ...  25
   value: [ - ][ - ][FREE][BAD][ 25][FREE][16][ 4][EOF]
                                  ^        ^   ^    ^
   directory: file.dat start=9    |        |   |    |
     9 -> 16 -> 4 -> 25 -> EOF ---+--------+---+----+

   Data blocks now hold 4096 bytes of DATA (no embedded pointer).
   Chain walking touches only the cached table: memory speed, not disk.
   The same table records FREE and BAD clusters -> it is also the free map.

   FAT SIZE GROWS WITH THE VOLUME
     FAT32, 4 KB clusters, 2 TB volume -> 536,870,912 clusters
                                       x 4 bytes = ~2 GB of table
     (which is why FAT32 uses large clusters on large volumes -- and why
      internal fragmentation on FAT volumes is often severe.)

# Linked allocation with in-block pointers vs FAT, and the access-cost difference.

class LinkedVolume:
    """Pointers live in the blocks: every hop is a device read."""
    def __init__(self):
        self.next = {}                      # block -> next block (-1 = end)
        self.reads = 0

    def block_of(self, start, logical):
        b = start
        for _ in range(logical):
            self.reads += 1                 # MUST read the block to learn the next
            b = self.next[b]
        self.reads += 1                      # and read the target itself
        return b

class FatVolume:
    """Pointers live in one table, cached in RAM: hops are memory accesses."""
    def __init__(self, nclusters):
        self.fat = [0] * nclusters           # the whole table, in memory
        self.reads = 0

    def block_of(self, start, logical):
        c = start
        for _ in range(logical):
            c = self.fat[c]                  # memory lookup, no device read
        self.reads += 1                      # only the DATA block is read
        return c

# Build the same 5,000-block chain in both.
chain = list(range(1000, 6000))
linked = LinkedVolume()
for a, b in zip(chain, chain[1:]):
    linked.next[a] = b
linked.next[chain[-1]] = -1

fat = FatVolume(20_000)
for a, b in zip(chain, chain[1:]):
    fat.fat[a] = b
fat.fat[chain[-1]] = -1

linked.block_of(chain[0], 4999)
fat.block_of(chain[0], 4999)
print(f"linked (in-block ptrs): {linked.reads:,} device reads")   # 5,000
print(f"FAT    (cached table) : {fat.reads:,} device reads")      # 1

# FAT table size as a function of volume size and cluster size.
for cluster_kb in (4, 16, 32, 64):
    clusters = (2 * 1024**4) // (cluster_kb * 1024)
    table_mb = clusters * 4 / 1024**2
    print(f"2 TB volume, {cluster_kb:>2} KB clusters: "
          f"{clusters:>12,} clusters, FAT = {table_mb:>8,.0f} MB, "
          f"avg internal frag/file = {cluster_kb/2} KB")

# Inspect a real FAT volume.
sudo fsck.vfat -v /dev/sdb1
#   Boot sector contents:
#   ...
#   FAT size is 4084 sectors, fat_size = 2091008 bytes
#   2 FATs                               <- the second is a mirror copy

sudo dosfsck -n /dev/sdb1 | grep -i cluster
sudo minfo -i /dev/sdb1 ::               # cluster size, FAT copies, total clusters

# The internal-fragmentation consequence of big clusters.
sudo mkfs.vfat -F 32 -s 128 /dev/sdb1    # 128 sectors/cluster = 64 KB clusters
for i in $(seq 1000); do echo x > /mnt/usb/tiny_$i; done
du -sh --apparent-size /mnt/usb          # ~2 KB of actual content
du -sh /mnt/usb                          # ~64 MB of allocated space

Key takeaways

• Linked allocation chains a file's blocks with a next-pointer in each block: no external fragmentation and effortless growth.
• Random access is O(n) — reaching logical block i requires reading all i blocks before it — which disqualifies it for general use.
• A single corrupted pointer orphans the rest of the file, and the in-block pointer breaks power-of-two block sizes.
• FAT moves all pointers into one table indexed by cluster number, restoring clean block sizes and letting chains be walked in cached memory.
• The FAT doubles as the free-space map, marking free, bad, and end-of-chain entries in the same array; two copies are kept because losing it loses everything.
• FAT's table grows with volume size, which forces large clusters on large volumes and therefore substantial internal fragmentation.

🧪 Practice

1. A file occupies blocks 12, 47, 3, 88, 21 in that order. Draw both representations — in-block pointers and a FAT — and count the device reads needed to read logical block 4 under each.
2. Compute the FAT size for a 32 GB volume at 4 KB, 16 KB, and 32 KB clusters, and the average internal fragmentation per file in each case.
3. Interview-style: "Why does FAT32 remain the format of choice for USB sticks and camera cards despite being decades old?" Hint: the answer is not technical merit — think about what has to be true for a device with no operating system to read a card.

Indexed Allocation

Theory

Linked allocation fails at random access because the pointers are distributed through the chain. Contiguous allocation fails at growth because it demands one run. Indexed allocation takes the obvious third path: gather all of a file's block pointers into one index block, and store the index block's address in the inode.

This gives direct access with no chain walking — logical block i is simply index[i] — while keeping the freedom to place blocks anywhere, so there is no external fragmentation and files grow by appending a pointer. It is the scheme the classic UNIX inode implements, and it is the conceptual ancestor of nearly everything that followed.

The design question is what to do when a file needs more pointers than one index block holds. With 4 KB blocks and 4-byte pointers an index block holds 1,024 pointers, addressing 4 MB. Files are bigger than that. Three answers exist:

1. Linked scheme. Chain index blocks together: the last entry of each points to the next index block. Simple, but reintroduces linear traversal of the index.
2. Multilevel index. An outer index block points to inner index blocks, which point to data. Two levels give 1,024 × 1,024 = ~1 million blocks (4 GB); three levels give 4 TB. Access cost is one read per level.
3. Combined scheme. The UNIX answer: put a few direct pointers in the inode itself, then a single indirect, a double indirect, and a triple indirect. Small files pay no index overhead at all; large files pay progressively more, and only for the parts that need it.

The combined scheme is worth appreciating as a piece of engineering. It is explicitly tuned to the observed file-size distribution: the overwhelming majority of files are small, so the common case is optimised to zero index reads, while the tail remains addressable. It is a static, hand-tuned approximation of an adaptive structure — and its weakness is exactly that staticness. A 100 GB file needs three levels of indirection for every access, and its index blocks alone consume tens of megabytes.

The costs of indexed allocation in general:

• Space overhead for small files. A 1-block file under pure indexed allocation still needs an index block, doubling its footprint. The combined scheme's direct pointers exist precisely to avoid this.
• Index reads on the path to data. Each level is a potential extra I/O, mitigated heavily by caching (index blocks are hot and small).
• Poor description of contiguity. This is the deep one. If a file's 1 million blocks happen to be perfectly contiguous, indexed allocation still stores 1 million pointers describing them one at a time. It cannot say "blocks 5,000 through 1,005,000". That observation is what motivates extents, the next topic.

Example

   PURE INDEXED ALLOCATION

   inode ---> index block 71
              +-----------+
              | [0] -> 19 |----> [ data: logical block 0 ]
              | [1] ->  4 |----> [ data: logical block 1 ]
              | [2] -> 88 |----> [ data: logical block 2 ]
              | [3] -> 12 |----> [ data: logical block 3 ]
              |  ...      |
              +-----------+
   Logical block 2?  index[2] = 88.  ONE index read, ONE data read.
   No chain. Blocks may be anywhere. Growth = append a pointer.

   THE THREE WAYS TO EXCEED ONE INDEX BLOCK

   (1) LINKED INDEX          (2) MULTILEVEL           (3) COMBINED (UNIX)
   [idx]->[idx]->[idx]       [outer]                  inode
     |      |      |          | | |                   +-- 12 direct ---> data
    data   data   data      [i][i][i]                 +-- single ------> [idx]
   traversal is linear        | | |                   +-- double ------> [idx]->[idx]
   again                     data...                  +-- triple ------> [idx]->[idx]->[idx]

   COST OF THE COMBINED SCHEME (4 KB blocks, 1024 ptrs/index block)

   file size      pointers stored     index blocks    reads to reach a block
   4 KB           1 direct            0               1
   48 KB          12 direct           0               1
   4 MB           +1024 single        1               2
   4 GB           +1,048,576 double   ~1,025          3
   4 TB           +1.07e9 triple      ~1,049,601      4

   AND THE WEAKNESS THAT KILLED IT:
     a perfectly contiguous 4 GB file still stores 1,048,576 separate
     pointers -- 4 MB of index describing "the blocks are in a row".

# Combined indexed allocation: index-block overhead as files grow,
# and the contiguity the scheme cannot express.
BLOCK, PTR = 4096, 4
PPB        = BLOCK // PTR          # 1024 pointers per index block
DIRECT     = 12

def index_blocks_for(data_blocks):
    """How many INDEX blocks a file of this many data blocks consumes."""
    remaining = data_blocks - DIRECT
    if remaining <= 0:
        return 0
    total = 0
    # single indirect: one index block covering up to PPB data blocks
    take = min(remaining, PPB)
    total += 1
    remaining -= take
    if remaining <= 0:
        return total
    # double indirect: one outer + ceil(n/PPB) inner
    take = min(remaining, PPB * PPB)
    inner = -(-take // PPB)                  # ceiling division
    total += 1 + inner
    remaining -= take
    if remaining <= 0:
        return total
    # triple indirect: one outer + middles + inners
    inner  = -(-remaining // PPB)
    middle = -(-inner // PPB)
    total += 1 + middle + inner
    return total

for size_mb in (0.004, 0.048, 4, 100, 4096, 102_400):
    data = max(1, int(size_mb * 1024**2) // BLOCK)
    idx  = index_blocks_for(data)
    print(f"{size_mb:>10,.3f} MB: {data:>10,} data blocks, "
          f"{idx:>9,} index blocks ({idx/data:>6.2%} overhead)")

# The contiguity problem, stated numerically.
data = (4 * 1024**3) // BLOCK                     # 4 GB file
print(f"\ncontiguous 4 GB file:")
print(f"  indexed : {data:,} pointers = {data*PTR/1024**2:.1f} MB of index")
print(f"  extents : 1 record (start, length) = 12 bytes")

# ext4 can still be told to use the old indirect scheme, for comparison.
sudo mkfs.ext4 -O ^extent /dev/sdb1      # disable extents: indirect blocks
sudo mount /dev/sdb1 /mnt/old
dd if=/dev/zero of=/mnt/old/big bs=1M count=1024 status=none
filefrag -v /mnt/old/big | tail -3
#   many small extents: each indirect block boundary shows up

sudo mkfs.ext4 /dev/sdc1                 # extents enabled (the default)
sudo mount /dev/sdc1 /mnt/new
dd if=/dev/zero of=/mnt/new/big bs=1M count=1024 status=none
filefrag /mnt/new/big
#   /mnt/new/big: 9 extents found        <- vs thousands of indirect pointers

# Count the metadata a file actually consumes (blocks vs apparent size).
stat -c 'apparent=%s allocated_512b_blocks=%b' /mnt/old/big
# The gap includes the index blocks.

Key takeaways

• Indexed allocation collects a file's block pointers into an index block, giving direct access without chaining and growth without contiguity.
• Exceeding one index block is handled by linking index blocks, by a multilevel index, or by UNIX's combined scheme.
• The combined scheme is tuned to the real file-size distribution: small files need zero index blocks, large ones pay per level.
• Access cost grows by one read per indirection level, though index blocks cache extremely well.
• Index overhead is negligible in percentage terms (~0.1%) but the absolute size matters for very large files.
• The fundamental weakness is that a pointer-per-block index cannot express contiguity — which is precisely what extents fix.

🧪 Practice

1. With 2 KB blocks and 4-byte pointers, compute the maximum file size under a combined scheme with 10 direct pointers plus single, double, and triple indirect.
2. Compute the number of index blocks and the percentage overhead for a 10 GB file under the combined scheme with 4 KB blocks.
3. Interview-style: "A file system stores a perfectly contiguous 8 GB video as 2 million individual block pointers. What is wrong with that, and what would you change?" Hint: consider both the metadata size and the number of reads needed before the first byte of data arrives.

Extents

Theory

An extent is a contiguous run of blocks described by a single record: (logical offset, physical start, length). Extent-based allocation replaces the per-block pointer with a per-run record, and that single change is the most consequential file system improvement of the last thirty years.

The motivation is direct. Allocators already try hard to place files contiguously — the placement is usually good. Indexed allocation then throws that information away, storing one pointer per block regardless of whether the blocks are adjacent. Extents preserve it. A contiguous 1 GB file needs 262,144 pointers under indexed allocation and one extent record under extent allocation.

The benefits follow mechanically:

• Metadata shrinks by orders of magnitude for well-laid-out files, so it fits in the inode, so locating data costs no extra reads at all.
• Fewer I/O requests. The block layer can issue one large request per extent instead of merging thousands of small ones.
• Faster deletion. Freeing a file means freeing a handful of ranges, not walking a million pointers. This is why deleting a huge file on ext4 or XFS is near-instant while on ext3 it could take seconds.
• Cheap sparse and preallocated regions. An extent can be marked uninitialised: space is reserved and contiguous, but reads return zeros until it is written. This is what makes fallocate fast and what lets sparse files skip unwritten ranges entirely.

The structure is hierarchical. ext4 stores up to 4 extent records directly in the inode (60 bytes of what used to be block pointers), which covers most files completely; when a file needs more, the inode holds the root of an extent tree (a B+-tree) whose leaves are extent records. XFS uses B+-trees of extents throughout. Btrfs and ZFS store extents in their general-purpose B-trees.

There is a size limit per record — ext4 uses a 15-bit length field, capping one extent at 32,768 blocks (128 MB at 4 KB), so a 1 GB contiguous file is 8 extents, not 1. Not a problem: 8 records versus 262,144 pointers.

Extents make allocation quality visible, which changes how file systems allocate. Delayed allocation is the key partner technique: rather than choosing blocks when a write() arrives, the file system keeps the data in the page cache and decides placement at writeback, when it knows the total size. It can then pick one large run instead of many scattered ones. This is why ext4 and XFS produce far less fragmentation than ext3 — and also why a crash between write() and writeback can lose more data, which is the trade-off discussed in Section 10.4.

Example

   EXTENT TREE IN AN ext4 INODE

   inode (the 60 bytes formerly holding block pointers)
   +---------------------------------------------------------+
   | eh_magic F30A | eh_entries 3 | eh_max 4 | eh_depth 0     |  <- header
   +---------------------------------------------------------+
   | logical 0      | len 32768 | physical 918,272            |  extent 0
   | logical 32768  | len 32768 | physical 1,204,224          |  extent 1
   | logical 65536  | len  1024 | physical   77,824           |  extent 2
   +---------------------------------------------------------+
   Whole 260 MB file described IN THE INODE. Zero extra metadata reads.

   WHEN 4 EXTENTS ARE NOT ENOUGH: depth becomes > 0

   inode (eh_depth 1)
   +--------------------------------+
   | logical 0      -> index blk 501|
   | logical 200000 -> index blk 502|
   +--------------------------------+
            |                |
      +-----v------+   +-----v------+
      | extents... |   | extents... |     leaves hold the (log, phys, len)
      +------------+   +------------+     records

   THE SAME FILE, BOTH SCHEMES (1 GB, perfectly contiguous, 4 KB blocks)

   indexed : 262,144 pointers, ~1 MB of index blocks, 2-3 extra reads/access
   extents :       8 records,  ~96 bytes, IN THE INODE, 0 extra reads
                   (8 because ext4 caps one extent at 32,768 blocks)

   UNINITIALISED EXTENTS (what fallocate creates)
   | logical 0 | len 2621440 | physical 918272 | UNINIT |
     space reserved and contiguous; reads return zeros; no data written.

# Extent records vs per-block pointers for the same physical layout.
BLOCK       = 4096
MAX_EXTENT  = 32_768                 # ext4: 15-bit length field
PTR         = 4
EXTENT_REC  = 12                     # bytes per extent record

def describe(file_bytes, runs):
    """runs = list of contiguous run lengths in blocks."""
    blocks = file_bytes // BLOCK
    pointer_bytes = blocks * PTR
    extent_count = sum(-(-r // MAX_EXTENT) for r in runs)   # split at the cap
    return blocks, pointer_bytes, extent_count, extent_count * EXTENT_REC

# Case 1: a perfectly contiguous 1 GB file.
blocks, pb, ec, eb = describe(1024**3, [1024**3 // BLOCK])
print(f"contiguous 1 GB : {blocks:,} blocks | indexed {pb/1024:>9,.0f} KB "
      f"| extents {ec} recs = {eb} B")

# Case 2: the same file in 500 fragments.
frag = [ (1024**3 // BLOCK) // 500 ] * 500
blocks, pb, ec, eb = describe(1024**3, frag)
print(f"500 fragments   : {blocks:,} blocks | indexed {pb/1024:>9,.0f} KB "
      f"| extents {ec} recs = {eb} B")

# Case 3: pathological -- every block separate (worst case for extents).
frag = [1] * (1024**3 // BLOCK)
blocks, pb, ec, eb = describe(1024**3, frag)
print(f"fully fragmented: {blocks:,} blocks | indexed {pb/1024:>9,.0f} KB "
      f"| extents {ec:,} recs = {eb/1024:,.0f} KB")
# Note case 3: extents are WORSE than pointers when nothing is contiguous
# (12 bytes per block vs 4). Extents bet on the allocator doing its job.

# Look at a file's actual extents.
filefrag -v /var/lib/vm/disk.img
#   ext  logical_offset  physical_offset  length  flags
#     0:       0..32767:   918272..951039:  32768:
#     1:   32768..65535:  1204224..1236991: 32768: 
#     2:   65536..66559:    77824..78847:    1024: last,eof
#   disk.img: 3 extents found

# Uninitialised extents: reserved but unwritten.
fallocate -l 1G sparse_prealloc.img
filefrag -v sparse_prealloc.img | grep -i unwritten
du -h --apparent-size sparse_prealloc.img   # 1.0G  (logical size)
du -h sparse_prealloc.img                   # 1.0G  (reserved on disk)

# A truly sparse file: no extents for the hole at all.
dd if=/dev/zero of=hole.img bs=1 count=1 seek=1G status=none
du -h --apparent-size hole.img              # 1.1G
du -h hole.img                              # 4.0K   <- the hole costs nothing

# Measuring and fixing fragmentation.
sudo e4defrag -c /home                      # report fragmentation score
sudo e4defrag /home/ana/big.db              # defragment one file online
sudo xfs_bmap -v /mnt/data/big.db           # XFS's equivalent of filefrag
sudo xfs_fsr /mnt/data                      # XFS online reorganiser

Key takeaways

• An extent is (logical offset, physical start, length) — one record for a whole contiguous run instead of one pointer per block.
• Well-laid-out files need only a few extents, which fit in the inode, so locating data costs zero extra reads.
• Extents shrink metadata by orders of magnitude, cut I/O request counts, and make deleting huge files near-instant.
• Uninitialised extents make preallocation cheap, and holes in sparse files cost no metadata at all.
• When one extent record is insufficient, file systems use an extent tree (ext4's B+-tree, XFS's, Btrfs's).
• Extents assume the allocator achieves contiguity: on a fully fragmented file they are larger than per-block pointers, which is why delayed allocation is their essential partner.

🧪 Practice

1. A 512 MB file is laid out in 4 contiguous runs. Compute the number of ext4 extent records (remembering the 32,768-block cap) and compare the metadata size against per-block pointers.
2. Create a sparse file and a preallocated file of the same logical size, then compare du with du --apparent-size and filefrag output for both. Explain each difference.
3. Interview-style: "Explain how delayed allocation reduces fragmentation, and name the durability risk it introduces." Hint: think about what extra information the file system has at writeback time that it did not have at write() time, and what is in the page cache in between.

Bit Vectors and Free Lists

Theory

Allocation needs a supply. Whichever scheme maps files to blocks, something must track which blocks are available, answer "give me n contiguous free blocks" quickly, and survive a crash without losing count.

Bit vector (bitmap). One bit per block: 1 free, 0 allocated (or the reverse). The appeal is compactness and the fact that finding contiguous runs is a bit-scanning problem, which hardware does very well — ffs/__builtin_ctzll finds the first set bit in a 64-bit word in one instruction, so scanning gigabytes of bitmap is fast. The overhead is precisely 1 / (block_size × 8) of the volume: with 4 KB blocks, 1 bit per 32,768 bits of data, or about 0.003%. A 4 TB volume needs a 128 MB bitmap — small enough to keep the relevant parts cached, too big to keep entirely resident, which is why bitmaps are split per block group.

Linked free list. Chain the free blocks together, each pointing to the next. Zero space overhead (the pointers live in blocks that are free anyway) but it is nearly useless for finding contiguity — the chain is in whatever order blocks were freed — and traversing it costs one I/O per block.

Grouping. Store n free block addresses in the first free block, with the last entry pointing to the next group block. One read yields many free blocks instead of one, which makes bulk allocation practical.

Counting. Since free blocks tend to appear in runs (a deleted file frees its whole extent), store (first_block, count) pairs instead of individual addresses. This is the free-space analogue of extents, and it is dramatically more compact when the volume is not badly fragmented.

B-trees of free extents. The modern answer, used by XFS and Btrfs. XFS keeps two B+-trees per allocation group over the same free extents — one keyed by starting block, one keyed by length. The first answers "what is free near here" (for locality); the second answers "where is a run of at least n blocks" (for size-fitting) in O(log n) without scanning. That pairing is the reason XFS handles very large, very full volumes well.

Two practical issues cut across all designs:

Consistency. The free map and the file metadata must agree. If a crash occurs between marking a block allocated and recording it in the inode, the block is lost (leaked); the reverse order risks the far worse outcome of two files sharing a block. Ordering, journalling, or copy-on-write is required — Section 10.4.

Reservation and TRIM. Most file systems reserve a percentage (5% by default on ext4) for root and to keep allocation from degrading: allocators need slack to find contiguous runs, and a volume above roughly 90% full fragments badly. On SSDs, freeing blocks in the file system means nothing to the device unless it is told, so discard/TRIM forwards deallocation down to the FTL; batching it (fstrim weekly) is usually better than the per-delete discard mount option.

Example

   THE FOUR REPRESENTATIONS OF THE SAME FREE SPACE
   free blocks: 2,3,4,5, 8, 11,12,13, 20,21,22,23,24

   BIT VECTOR (1 = free)
     block  0  1  2  3  4  5  6  7  8  9 10 11 12 13 ... 20 21 22 23 24
            0  0  1  1  1  1  0  0  1  0  0  1  1  1 ...  1  1  1  1  1
     -> 00111100 10011100 ... : 1 bit/block, scan with word operations

   LINKED LIST
     head -> [2] -> [3] -> [4] -> [5] -> [8] -> [11] -> ... -> [24] -> nil
     finding 4 contiguous blocks requires walking and sorting the whole chain

   GROUPING (n=4 addresses per group block)
     [2: 3,4,5,8 | next=11] -> [11: 12,13,20,21 | next=22] -> [22: 23,24,-,-]
     one read yields four free addresses

   COUNTING  (the free-space analogue of extents)
     (2,4)  (8,1)  (11,3)  (20,5)          <- 4 records for 13 free blocks

   XFS: TWO B+-TREES OVER THE SAME EXTENTS
     by-block  : 2 -> 8 -> 11 -> 20        "what is free near block 10?"
     by-size   : 8(1) -> 11(3) -> 2(4) -> 20(5)   "find a run of >= 4"
     both O(log n); neither requires a scan.

   OVERHEAD COMPARISON, 4 TB VOLUME, 4 KB BLOCKS (1,073,741,824 blocks)
     bit vector : 134,217,728 bits = 128 MB          (0.003% of volume)
     counting   : 12 B x number of free RUNS         (tiny if unfragmented,
                                                      large if fragmented)

# A bitmap allocator with first-fit contiguous search, the way real ones work.
class BitmapAllocator:
    def __init__(self, nblocks):
        self.nblocks = nblocks
        self.bits = bytearray((nblocks + 7) // 8)     # all zero = all allocated
        for b in range(nblocks):
            self.set_free(b, True)

    def set_free(self, block, free):
        byte, bit = divmod(block, 8)
        if free:
            self.bits[byte] |= (1 << bit)
        else:
            self.bits[byte] &= ~(1 << bit) & 0xFF

    def is_free(self, block):
        byte, bit = divmod(block, 8)
        return bool(self.bits[byte] & (1 << bit))

    def alloc_contiguous(self, n, near=0):
        """First-fit starting from a hint, so related files land close together."""
        run_start, run = None, 0
        for i in list(range(near, self.nblocks)) + list(range(0, near)):
            if self.is_free(i) and (run_start is None or i == run_start + run):
                if run == 0:
                    run_start = i
                run += 1
                if run == n:
                    for b in range(run_start, run_start + n):
                        self.set_free(b, False)
                    return run_start
            else:
                run_start, run = (i, 1) if self.is_free(i) else (None, 0)
        return None

    def free_stats(self):
        total = sum(self.is_free(b) for b in range(self.nblocks))
        largest = run = 0
        for b in range(self.nblocks):
            run = run + 1 if self.is_free(b) else 0
            largest = max(largest, run)
        return total, largest

alloc = BitmapAllocator(1024)
print(alloc.alloc_contiguous(8))              # 0
print(alloc.alloc_contiguous(16, near=500))   # 500  -- the locality hint works
print(f"free={alloc.free_stats()[0]} largest_run={alloc.free_stats()[1]}")

# Bitmap overhead is a fixed fraction of the volume, independent of usage.
for block_kb in (1, 4, 16, 64):
    for vol_tb in (1, 4, 100):
        blocks = vol_tb * 1024**4 // (block_kb * 1024)
        print(f"{vol_tb:>3} TB @ {block_kb:>2} KB blocks: "
              f"bitmap {blocks/8/1024**2:>10,.1f} MB "
              f"({blocks/8/(vol_tb*1024**4):.5%} of volume)")

# Free-space metadata on a real volume.
sudo dumpe2fs /dev/sda2 | grep -A4 'Group 0:'
#   Group 0: (Blocks 0-32767)
#     Block bitmap at 1025 (+1025)
#     Inode bitmap at 1041 (+1041)
#     4821 free blocks, 7 free inodes, 2 directories
# One bitmap PER GROUP: only the relevant part needs caching.

df -h /            # blocks free
df -i /            # inodes free -- a separate pool, exhausted separately

# Reserved space: why a "full" disk still lets root write.
sudo tune2fs -l /dev/sda2 | grep -i 'reserved block'
sudo tune2fs -m 1 /dev/sda2      # cut the reserve from 5% to 1% on a data volume
# Do NOT do this on the root filesystem: the reserve keeps the system bootable
# and gives the allocator slack to find contiguous runs.

# Telling the SSD about freed blocks.
sudo fstrim -av                  # batch TRIM: preferred
#   /: 41.2 GiB (44234563584 bytes) trimmed
systemctl status fstrim.timer    # usually weekly
mount | grep discard             # per-delete TRIM: simpler, often slower

# XFS free-space trees, and fragmentation of FREE SPACE (not files).
sudo xfs_db -r -c "freesp -s" /dev/sdb1
#   from      to  extents   blocks    pct
#      1       1     1823     1823   0.01
#   ...
#   total free extents 20341  -> many small runs = allocation will struggle

Key takeaways

• A bit vector uses one bit per block (about 0.003% overhead at 4 KB blocks) and finds contiguous runs efficiently with word-level bit scanning.
• Linked free lists cost no space but cannot find contiguity; grouping and counting improve on them, counting being the free-space analogue of extents.
• XFS keeps two B+-trees per allocation group over free extents — by block for locality, by size for fitting — giving O(log n) answers to both questions.
• Bitmaps are split per block group so only the active parts need caching, and so allocation can proceed in parallel.
• The free map and file metadata must be updated consistently; the safe ordering leaks blocks on a crash rather than sharing them between files.
• Reserved space (5% by default) keeps the allocator's options open; above roughly 90% utilisation, fragmentation rises sharply.
• On SSDs, freeing a block is invisible to the device without TRIM; batched fstrim is usually preferable to the discard mount option.

🧪 Practice

1. Compute the bitmap size for a 16 TB volume at 4 KB blocks, and again at 64 KB blocks. State the percentage overhead in each case and one drawback of the larger block size.
2. Represent the free set {2,3,4,5,8,11,12,13,20,21,22,23,24} as a bit vector, a counting list, and a grouped list with 4 addresses per group block. Which is smallest, and under what conditions does that change?
3. Interview-style: "A 4 TB volume is 94% full and write throughput has collapsed, though the device benchmarks fine. Explain and fix." Hint: think about what the allocator has to do to satisfy a large write when only small free runs remain.

Block Size Trade-offs

Theory

The block (or cluster, or allocation unit) is the smallest amount of space a file system will allocate. Choosing its size trades three things against one another — wasted space, metadata volume, and I/O efficiency — and the right answer depends entirely on the file-size distribution of the workload.

Internal fragmentation is the cost of rounding up. A file of any size occupies a whole number of blocks, so on average each file wastes half a block. With 4 KB blocks that is 2 KB per file; with 64 KB blocks it is 32 KB per file. For a mail spool with a million 3 KB messages, 4 KB blocks waste about 1 GB while 64 KB blocks waste 61 GB — and store only 3 GB of actual mail. This is the argument for small blocks, and it is decisive for small-file workloads.

Metadata volume pushes the other way. Halving the block size doubles the number of blocks, which doubles the bitmap, doubles the pointers or extent records needed to describe a large file, and doubles the number of I/O requests to read it if the extent allocator does not achieve contiguity. It also halves the maximum file size under any fixed-depth indexed scheme.

I/O efficiency also favours larger blocks, though less than it once did. Every request has fixed overhead — a request structure, a queue entry, an interrupt or completion. Reading 1 MB as 256 4 KB requests costs 256 times that overhead; as 16 64 KB requests, sixteen times. Extents and request merging in the block layer recover most of this, which is why 4 KB remains a good default on modern systems despite the larger physical units underneath.

There is also a hardware floor: the device's physical sector size (4,096 bytes on essentially all modern drives) and, on SSDs, the flash page size. A file system block smaller than the physical sector forces read-modify-write on every partial write, so 4 KB is the sensible minimum regardless of the workload. The page size of the CPU (4 KB on x86-64) matters too, because the page cache works in pages: a file system block larger than a page is workable but a block smaller than a page wastes cache granularity, and Linux historically did not support block sizes above the page size at all.

Several designs escape the single-choice constraint:

• Block suballocation / fragments. BSD FFS used large blocks (8 KB) but let the last block of a small file be a fragment (1 KB) shared with other files' tails. Complexity in exchange for both benefits.
• Inline data. Store very small files inside the inode, costing zero blocks (ext4, Btrfs, NTFS's resident attributes).
• Tail packing. Btrfs and ReiserFS pack small files and file tails together into shared blocks.
• Variable block sizes. ZFS chooses a record size per dataset (up to 1 MB) and lets small files use smaller records, so a database dataset and a media dataset on one pool can each get what they need.

Example

   INTERNAL FRAGMENTATION: THE SAME FILES, DIFFERENT BLOCK SIZES

   A 5,000-byte file:
     1 KB blocks : 5 blocks = 5,120 B    waste   120 B   (2.3%)
     4 KB blocks : 2 blocks = 8,192 B    waste 3,192 B  (38.9%)
    16 KB blocks : 1 block  = 16,384 B   waste 11,384 B (69.5%)
    64 KB blocks : 1 block  = 65,536 B   waste 60,536 B (92.4%)

   [####|####|####|####|#-- ]   1 KB blocks: little waste, 5 pointers
   [########|#---------------]   4 KB blocks: 1 nearly-empty block
   [#####-------------------- ]  64 KB blocks: mostly emptiness

   1,000,000 MAIL MESSAGES AVERAGING 3 KB (3 GB of real content)

   block size   blocks/file   allocated   wasted    bitmap (4 TB vol)
      1 KB           3          3.0 GB     0.0 GB      512 MB
      4 KB           1          4.0 GB     1.0 GB      128 MB
     16 KB           1         16.0 GB    13.0 GB       32 MB
     64 KB           1         64.0 GB    61.0 GB        8 MB

   ONE 100 GB DATABASE FILE

   block size   blocks        extent records   requests for a 1 MB read
      1 KB      104,857,600      ~3,200            1,024
      4 KB       26,214,400        ~800              256
     64 KB        1,638,400         ~50               16

   The two tables point in OPPOSITE directions. That is the trade-off.

import math

def analyse(file_sizes, block_size):
    allocated = sum(math.ceil(s / block_size) * block_size for s in file_sizes)
    actual    = sum(file_sizes)
    blocks    = sum(math.ceil(s / block_size) for s in file_sizes)
    return allocated, actual, blocks

# Workload A: many small files (mail, source code, web assets)
small = [3 * 1024] * 100_000
# Workload B: few large files (video, databases, VM images)
large = [2 * 1024**3] * 50

print(f"{'block':>8} | {'small: alloc':>13} {'waste':>7} | {'large: blocks':>14}")
for bs in (1024, 4096, 16384, 65536, 262144):
    a1, r1, _  = analyse(small, bs)
    _,  _,  b2 = analyse(large, bs)
    print(f"{bs//1024:>6} KB | {a1/1024**3:>10.2f} GB {(a1-r1)/a1:>6.1%} | "
          f"{b2:>14,}")

# The crossover: what block size minimises TOTAL cost for a mixed workload,
# counting both wasted space and per-block metadata?
METADATA_BYTES_PER_BLOCK = 4          # bitmap bit + share of extent records

def total_cost(file_sizes, block_size):
    allocated, actual, blocks = analyse(file_sizes, block_size)
    return (allocated - actual) + blocks * METADATA_BYTES_PER_BLOCK

mixed = small[:20_000] + [50 * 1024**2] * 200     # 20k small + 200 x 50 MB
best = min((total_cost(mixed, bs), bs) for bs in (1024, 2048, 4096, 8192, 16384))
print(f"\nlowest total cost at {best[1]//1024} KB blocks "
      f"({best[0]/1024**2:,.0f} MB of waste + metadata)")

# What block size is in use, and the hardware floor beneath it.
sudo tune2fs -l /dev/sda2 | grep -i 'block size'     # Block size: 4096
sudo xfs_info /mnt/data | head -2                    # bsize=4096
stat -f /                                            # Block size: 4096
sudo blockdev --getpbsz /dev/sda                     # 4096 physical sector size
getconf PAGE_SIZE                                    # 4096: the cache granularity

# Choosing at format time.
sudo mkfs.ext4 -b 1024 /dev/sdb1       # many small files (max 16 TB volume)
sudo mkfs.ext4 -b 4096 /dev/sdb1       # the default, sane for almost everything
sudo mkfs.xfs  -b size=4096 /dev/sdb1

# ZFS: per-dataset record size, chosen to match the workload.
sudo zfs set recordsize=8k   tank/postgres     # match the DB page size
sudo zfs set recordsize=1M   tank/media        # large sequential reads
sudo zfs get recordsize tank/postgres tank/media

# Measure the gap on a real tree: apparent size vs allocated size.
du -sh --apparent-size /var/mail      # real content
du -sh /var/mail                      # space actually consumed
# The ratio between them IS the internal fragmentation of this workload.

# Small-file savings from inline data.
sudo tune2fs -l /dev/sda2 | grep -i 'inline_data'
echo hi > tiny.txt && stat -c '%s bytes, %b x 512B blocks allocated' tiny.txt
#   3 bytes, 0 x 512B blocks allocated   <- stored inside the inode

Key takeaways

• Block size trades internal fragmentation (favours small blocks) against metadata volume and I/O efficiency (favour large blocks).
• Average waste is half a block per file, so small-file workloads are punished severely by large blocks.
• Halving the block size doubles bitmap size, pointer or extent counts, and request counts for a large file, and halves the maximum file size in fixed-depth schemes.
• The practical floor is the device's physical sector size (4 KB) and the CPU page size, below which every partial write becomes a read-modify-write.
• 4 KB is the right default on general-purpose systems; deviate only with a measured file-size distribution.
• Fragments (FFS), inline data, tail packing (Btrfs), and per-dataset record sizes (ZFS) all exist to avoid committing to one size for everything.

🧪 Practice

1. A file system holds 500,000 files averaging 6 KB. Compute total allocated space and total waste at 4 KB and at 32 KB block sizes.
2. Using du -sh and du -sh --apparent-size, measure the internal fragmentation of /usr/share on your machine and express it as a percentage.
3. Interview-style: "You are formatting a volume that will hold one 20 TB media archive of 4 GB files. What block size do you choose and what do you give up?" Hint: compute the number of blocks and extent records at each candidate size, and ask how much internal fragmentation 4 GB files can possibly incur.

<a id="104-consistency-and-recovery"></a>

10.4 Consistency and Recovery

A file system operation such as "create a file" touches several independent structures, but a device only writes one block at a time and a crash can happen between any two writes. This section covers the caching that makes the gap wide, and the four families of technique — journalling, log-structuring, copy-on-write, and offline checking — that keep the result consistent anyway.

Buffer Cache and Write-Back Policies

Theory

Storage is thousands of times slower than RAM, so the kernel keeps a cache of file blocks in memory. On Linux this is the page cache, and it is not a small optimisation: on a typical machine, most of the "free" memory is page cache, and the large majority of reads are served from it without touching a device.

It does three distinct jobs.

Read caching. A block read once stays resident until memory pressure evicts it, so re-reads cost a memory copy (~100 ns) instead of an I/O (~80 microseconds on NVMe, ~8 ms on HDD). Because the cache is unified with virtual memory, a page mapped by mmap and a page read by read() are the same physical page — no double caching.

Read-ahead. On detecting sequential access, the kernel fetches blocks the application has not asked for yet, so the next read() hits the cache. The window grows while the pattern holds and collapses when it breaks.

Write buffering. This is where the policy decision lives. A write() copies into a page, marks it dirty, and returns — the data is in volatile memory, not on the device. Writeback happens later, and the delay buys three things: writes to the same block coalesce, adjacent dirty pages merge into large sequential requests, and a file written and deleted quickly (a compiler temporary) may never be written at all.

The cost is equally clear: write() returning does not mean the data is durable. Losing power with dirty pages outstanding loses them. The controls are:

Call	Guarantees
write()	The data is in the page cache; visible to other readers; not durable
fsync(fd)	This file's data and metadata are on stable storage
fdatasync(fd)	Data and only the metadata needed to read it back (skips timestamps)
sync()	Schedules all dirty pages; historically did not wait
O_SYNC	Every write() behaves as if followed by fsync
O_DIRECT	Bypasses the page cache entirely — not the same as durable

Two traps catch people repeatedly. First, fsync on a file does not guarantee the file's directory entry is durable: after creating a new file, you must also fsync the containing directory, or a crash can leave a durable file with no name. Second, a device's own volatile write cache can acknowledge a write that is still in the drive's DRAM; fsync issues a FLUSH (or writes with FUA) to force it through, which is why fsync is expensive and why disabling a drive's cache flushing "for performance" silently breaks durability.

Writeback is also governed by tunables that shape latency. Linux's dirty_background_ratio sets when background writeback starts, and dirty_ratio sets the point at which a writing process is throttled — forced to do writeback itself. Setting these too high produces the classic pathology: gigabytes of dirty data accumulate, then a sync or memory pressure triggers a huge flush and the system stalls for seconds.

Example

   THE LIFE OF A write()

   app: write(fd, buf, 4096)
     |
     +--> copy into a page cache page, mark DIRTY, return   <- ~1 us, NOT durable
                    |
                    |  ... seconds pass; the page may be overwritten
                    |      again, or deleted, or merged with neighbours
                    v
          writeback thread (dirty_expire_centisecs, or dirty_ratio pressure)
                    |
                    v
          block layer -> device write cache (still volatile!)
                    |
                    |  fsync() adds:  FLUSH command
                    v
                 PLATTER / NAND    <- NOW durable

   WHAT A CRASH LOSES AT EACH STAGE

   crash after write()            : up to 30 s of data, silently
   crash after fsync() returns    : nothing of that file's data
   crash after fsync(file) but not fsync(dir) for a NEW file:
                                    the data survives, the NAME may not

   THE DURABLE-CREATE RECIPE
     1. write(tmp)                 5. fsync(dirfd)     <- makes the rename durable
     2. fsync(tmpfd)               ------------------------------
     3. close(tmpfd)               Skip step 5 and a crash can leave
     4. rename(tmp, final)         BOTH names absent despite fsync in step 2.

import os, time

# --- how long does each durability level actually take? ---
DATA = b"x" * 4096
N = 500

def timed(label, fn):
    t0 = time.perf_counter()
    fn()
    dt = time.perf_counter() - t0
    print(f"{label:<28} {dt*1000:8.1f} ms  ({N/dt:>10,.0f} ops/s)")

def buffered():
    fd = os.open("t1", os.O_CREAT | os.O_WRONLY | os.O_TRUNC, 0o644)
    for _ in range(N):
        os.write(fd, DATA)                 # page cache only
    os.close(fd)

def with_fdatasync():
    fd = os.open("t2", os.O_CREAT | os.O_WRONLY | os.O_TRUNC, 0o644)
    for _ in range(N):
        os.write(fd, DATA)
        os.fdatasync(fd)                   # data durable, timestamps skipped
    os.close(fd)

def with_fsync():
    fd = os.open("t3", os.O_CREAT | os.O_WRONLY | os.O_TRUNC, 0o644)
    for _ in range(N):
        os.write(fd, DATA)
        os.fsync(fd)                       # data + all metadata durable
    os.close(fd)

timed("buffered (not durable)", buffered)
timed("fdatasync per write", with_fdatasync)
timed("fsync per write", with_fsync)
# Typical NVMe: buffered ~2 ms total; fsync ~500-2000 ms. Three orders of magnitude.
# That gap is exactly why databases batch commits into group commits.

# --- the correct durable-create sequence, including the directory ---
def durable_create(path, data: bytes):
    d = os.path.dirname(os.path.abspath(path))
    tmp = os.path.join(d, f".{os.path.basename(path)}.tmp")
    fd = os.open(tmp, os.O_CREAT | os.O_WRONLY | os.O_EXCL, 0o644)
    try:
        os.write(fd, data)
        os.fsync(fd)                        # (1) file contents durable
    finally:
        os.close(fd)
    os.rename(tmp, path)                    # (2) atomic publish
    dfd = os.open(d, os.O_RDONLY)
    try:
        os.fsync(dfd)                       # (3) THE STEP EVERYONE FORGETS
    finally:
        os.close(dfd)

# How much dirty data is outstanding right now.
grep -E 'Dirty|Writeback' /proc/meminfo
#   Dirty:            184320 kB     <- would be lost on power failure
#   Writeback:             0 kB     <- currently in flight

# Writeback tunables: when background flushing starts, and when writers stall.
sysctl vm.dirty_background_ratio      # default 10 (% of available memory)
sysctl vm.dirty_ratio                 # default 20 -- writers are throttled here
sysctl vm.dirty_expire_centisecs      # default 3000 = 30 s before a page must go
sysctl vm.dirty_writeback_centisecs   # default 500  = flusher wakes every 5 s

# Lower them on a machine with lots of RAM to avoid multi-second flush stalls.
sudo sysctl -w vm.dirty_background_bytes=134217728   # 128 MB
sudo sysctl -w vm.dirty_bytes=536870912              # 512 MB

# Does the drive honour flushes? (If it lies, fsync guarantees nothing.)
sudo hdparm -W /dev/sda               # 1 = write cache on
sudo smartctl -a /dev/sda | grep -i 'write cache'

# Measure the cache-hit effect directly.
sync && echo 3 | sudo tee /proc/sys/vm/drop_caches    # cold
time cat bigfile > /dev/null                          # real 3.2s   (device)
time cat bigfile > /dev/null                          # real 0.09s  (page cache)

# Watch fsync latency in production.
sudo bpftrace -e 'kprobe:vfs_fsync { @start[tid]=nsecs; }
  kretprobe:vfs_fsync /@start[tid]/ {
    @us = hist((nsecs-@start[tid])/1000); delete(@start[tid]); }'

Key takeaways

• The page cache serves most reads from memory, unifies read() and mmap pages, and buffers writes so they can be coalesced and merged.
• A returning write() means "in volatile memory", not "durable" — up to dirty_expire seconds of data are at risk.
• fsync forces a file's data and metadata out, including a device cache flush; fdatasync skips metadata that is not needed to read the data back.
• After creating or renaming a file, the containing directory must also be fsynced, or the name can vanish while the data survives.
• O_DIRECT bypasses the cache but does not by itself provide durability; it still needs a flush unless the device is configured otherwise.
• dirty_ratio and dirty_background_ratio control writeback timing; leaving them high on a large-memory machine causes multi-second stalls when the flush finally happens.

🧪 Practice

1. Benchmark 1,000 4 KB writes buffered, with fdatasync per write, and with fsync per write. Report the ratio and explain each gap.
2. Write the complete durable-file-creation sequence as a numbered list of system calls, and say precisely what is lost if each fsync is omitted.
3. Interview-style: "A database says it commits durably, but a power cut lost the last 40 seconds of transactions. Where do you look?" Hint: durability is a chain — the application, the file system, and the device each have a cache, and any one of them can be configured to acknowledge early.

Journaling File Systems

Theory

Consider creating a file. The file system must: allocate an inode (write the inode bitmap), initialise it (write the inode), allocate a data block (write the block bitmap), write the data, and add a directory entry (write the directory block). That is five independent writes, and a crash can occur between any two of them.

The resulting inconsistencies are not symmetric. If the directory entry is written but the inode bitmap is not, two files may later claim the same inode — corruption. If the bitmap is written but the entry is not, an inode is marked in use with no name — a leak, which wastes space but destroys nothing. The whole game of consistency is to ensure that every crash lands you in a recoverable state, never a corrupt one.

The pre-journalling answer was to check the whole volume at boot (fsck, next topic but one). That works, but the time to scan every inode and block scales with volume size, and on a multi-terabyte volume it means hours of downtime after every unclean shutdown. That cost is what made journalling universal.

Journalling applies the database technique of write-ahead logging. Before modifying the file system's real structures, write a description of the intended change to a dedicated journal area, then mark it committed, then apply the change to the real locations ("checkpointing"), then free the journal entry. After a crash, recovery reads the journal: transactions that were fully committed are replayed (applied again — the operations are idempotent), and transactions not committed are discarded. Recovery time is proportional to journal size — seconds — not volume size.

The key insight is that the journal turns several non-atomic writes into one atomic decision: the commit record either made it to stable storage or it did not.

What to journal is a policy with a clear trade-off, and ext4 exposes all three:

Mode	What is journalled	Crash guarantee	Cost
journal	Metadata and data	No stale data ever visible; strongest	Every byte written twice
ordered (default)	Metadata only, but data is forced to disk before the metadata that references it	Metadata consistent; a file never exposes another file's old blocks	Modest
writeback	Metadata only, no ordering	Metadata consistent; a file can briefly show stale garbage after a crash	Fastest, weakest

ordered is the default because it delivers the property people actually care about — you never read someone else's deleted data out of your newly extended file — without doubling write volume.

Two refinements matter in practice. Batching: the journal groups many operations into one transaction committed every few seconds (commit=5 by default on ext4), because a commit costs a device flush and doing one per operation would be ruinous. And the journal itself is a circular buffer with its own checkpointing: entries can be reused only after their changes have been applied to the real structures, so a journal that is too small throttles the file system.

Example

   WITHOUT A JOURNAL: FIVE WRITES, FOUR PLACES TO CRASH

   1 inode bitmap  [....1....]
   2 inode         [ mode, size, block ptr ]
   3 block bitmap  [....1....]
   4 data block    [ "hello" ]
   5 dir entry     [ "f.txt" -> inode 41 ]

   crash after 1 : inode marked used, no file          -> LEAK (safe)
   crash after 2 : inode initialised, unreachable      -> LEAK (safe)
   crash after 3 : block marked used, unreferenced     -> LEAK (safe)
   crash after 4 : data written, unreachable           -> LEAK (safe)
   crash BEFORE 1 but after 5 (different order):
                   dir entry -> uninitialised inode    -> CORRUPTION

   WITH A JOURNAL: ONE ATOMIC DECISION

   journal area (circular)
   +---------------------------------------------------------------+
   | TxB 17 | ibmap | inode | bbmap | data | dirent | TxE 17 (COMMIT)|
   +---------------------------------------------------------------+
      ^ descriptor         ^ the blocks to be written    ^ commit record
      |
      crash HERE (before TxE) -> transaction incomplete -> DISCARD
      crash AFTER TxE         -> transaction committed  -> REPLAY

   Then CHECKPOINT: copy the journalled blocks to their real homes,
   and only then free the journal space for reuse.

   RECOVERY TIME
     fsck        : O(volume size)   -- 4 TB volume, hours
     journal replay: O(journal size) -- 128 MB journal, seconds

   ext4 DATA MODES

   data=journal   : [journal: meta+DATA] then [real: meta+data]  2x writes
   data=ordered   : [real: DATA] -> [journal: meta] -> [real: meta]
   data=writeback : [journal: meta] -> [real: meta] and data whenever
                    ^ after a crash, a newly appended file may show
                      blocks whose contents were never written: stale bytes.

# A journalling scheme in miniature: the write-ahead protocol and replay.
import json, os

class JournalledStore:
    """Illustrates commit-then-checkpoint and crash recovery."""
    def __init__(self, data_path="store.json", journal_path="store.jnl"):
        self.data_path, self.journal_path = data_path, journal_path
        self.state = self._load()

    def _load(self):
        try:
            with open(self.data_path) as f:
                return json.load(f)
        except FileNotFoundError:
            return {}

    def transaction(self, updates: dict):
        # --- 1. WRITE AHEAD: describe the change, then commit it ---
        with open(self.journal_path, "w") as j:
            json.dump({"updates": updates}, j)
            j.write("\nCOMMIT\n")          # the commit record: the atomic decision
            j.flush()
            os.fsync(j.fileno())           # MUST be durable before step 2

        # --- crash here: recovery finds COMMIT and replays ---

        # --- 2. CHECKPOINT: apply to the real structure ---
        self.state.update(updates)
        with open(self.data_path, "w") as f:
            json.dump(self.state, f)
            f.flush(); os.fsync(f.fileno())

        # --- 3. the journal entry is now redundant ---
        os.remove(self.journal_path)

    def recover(self):
        """Run at mount time. Idempotent: replaying twice is harmless."""
        if not os.path.exists(self.journal_path):
            return "clean"
        with open(self.journal_path) as j:
            content = j.read()
        if "COMMIT" not in content:
            os.remove(self.journal_path)
            return "incomplete transaction DISCARDED"
        updates = json.loads(content.split("\nCOMMIT")[0])["updates"]
        self.state.update(updates)                       # REPLAY
        with open(self.data_path, "w") as f:
            json.dump(self.state, f); f.flush(); os.fsync(f.fileno())
        os.remove(self.journal_path)
        return f"transaction REPLAYED: {updates}"

store = JournalledStore()
print(store.recover())                       # clean
store.transaction({"inode_41": "allocated", "dirent_f.txt": 41})
print(store.state)
# Replaying is safe because setting a key to the same value twice is idempotent
# -- the same reason file system journal replay can be run repeatedly.

# Which journalling mode is in effect.
mount | grep ' / '
sudo tune2fs -l /dev/sda2 | grep -i 'features\|journal'
#   Filesystem features: has_journal ext_attr ... 
#   Journal size:        128M
#   Default mount options: user_xattr acl

# Change the data mode (requires a remount, and 'journal' needs the mount option).
sudo mount -o remount,data=ordered   /              # the default
sudo mount -o remount,commit=5 /                    # transaction interval, seconds

# Put the journal on a separate, fast device (a classic database-server layout).
sudo mke2fs -O journal_dev /dev/nvme0n1p3
sudo mkfs.ext4 -J device=/dev/nvme0n1p3 /dev/sdb1

# Inspect journal contents and recovery.
sudo dumpe2fs /dev/sda2 | grep -i 'journal backup\|journal features'
sudo debugfs -R "logdump -a" /dev/sdb1 | head -30
dmesg | grep -i 'ext4.*recovery'
#   EXT4-fs (sda2): recovery complete
#   EXT4-fs (sda2): mounted filesystem with ordered data mode

# A file system with no journal, for comparison (ext2, or ext4 without one).
sudo tune2fs -O ^has_journal /dev/sdb1      # removes it: faster, no fast recovery

Key takeaways

• A single logical operation touches several structures, and a crash between them can leak space (safe) or corrupt structures (unsafe); the goal is to make only safe outcomes possible.
• Journalling writes the intended change to a log and commits it before touching the real structures; recovery replays committed transactions and discards incomplete ones.
• Recovery time becomes proportional to journal size rather than volume size — seconds instead of hours.
• data=ordered, the ext4 default, journals metadata only but forces data out first, so a crash never exposes another file's stale blocks.
• data=journal protects data fully at the cost of writing everything twice; data=writeback is fastest and can expose garbage after a crash.
• Transactions are batched (every few seconds) because each commit costs a device flush, and the journal is circular, so its size bounds outstanding work.

🧪 Practice

1. List the five structure updates involved in creating a one-block file, and for each ordering of the first two, state whether a crash leaks or corrupts.
2. Explain what data=writeback allows a user to observe after a crash that data=ordered does not, and construct the sequence of events that produces it.
3. Interview-style: "Journalling writes metadata twice. Why is the file system still faster after unclean shutdowns than one without a journal?" Hint: compare the steady-state write cost against the recovery cost, and consider how large modern volumes are.

Log-Structured File Systems

Theory

Journalling writes metadata twice: once to the journal and once to its real home. A log-structured file system asks the obvious follow-up question — if the log is written sequentially and is already a complete description of every change, why keep the second copy at all? Make the log the file system.

In a log-structured file system (LFS), all writes — data, inodes, directories, everything — append to the end of one large sequential log. Nothing is ever overwritten in place. Modifying a block means writing a new version at the log head and writing a new version of the inode pointing at it.

The motivation, argued by Rosenblum and Ousterhout in 1991, came from a prediction that turned out to be correct: caches keep growing, so reads increasingly hit memory, so the disk workload becomes dominated by writes — and the one thing a disk does well is sequential writing. Converting every write, however scattered, into an append is therefore the single largest available win. On modern flash the argument is even stronger, because sequential writes align with erase blocks and minimise write amplification.

Two problems must be solved.

Finding inodes. Inodes no longer live at fixed locations — a new copy is appended on every change. LFS adds an inode map mapping inode number to the current on-log location. The map is itself logged, and a small fixed checkpoint region at a known location points to the most recent map. Reading a file means: checkpoint region, inode map, inode, data.

Reclaiming space. The log is finite and superseded blocks accumulate as garbage. A cleaner (segment garbage collector) must run: the log is divided into large segments, the cleaner reads segments, identifies which blocks are still live (via a per-segment summary block recording which file and offset each block belongs to), copies the live ones to the log head, and frees the segment.

The cleaner is the whole difficulty. It consumes bandwidth precisely when the system is busy, and its cost depends on segment utilisation: cleaning a segment that is 90% live to recover 10% free space is dreadful. LFS uses a cost-benefit policy that prefers cold, mostly-dead segments and defers hot ones on the assumption that more of their blocks will die soon. Anyone who has tuned SSD over-provisioning has met the same trade-off — this is garbage collection with the same mathematics.

LFS's descendants are everywhere even though the original saw limited deployment: NetApp's WAFL, flash translation layers inside every SSD, LSM-tree stores (LevelDB, RocksDB, Cassandra), F2FS for flash, and the copy-on-write file systems of the next topic. The idea also shows its worst case clearly: a random-update workload on a nearly-full volume, where every write triggers cleaning of nearly-live segments.

Example

   UPDATE-IN-PLACE vs LOG-STRUCTURED

   TRADITIONAL: modify block 3 of file A
     seek to inode -> write inode; seek to block -> write data
     [ inode A ] .......... [ A0 ][ A1 ][ A2 ][ A3* ] ..........
     two scattered writes, two positioning costs

   LOG-STRUCTURED: modify block 3 of file A
     append everything at the log head; nothing is overwritten
     log: ... [ A3' ][ inode A' ][ imap chunk ] -> HEAD
                ^ new data   ^ new inode pointing at A3'
     ONE sequential write. The old A3 and old inode A are now garbage.

   READING A FILE (the extra indirection LFS must pay)

     checkpoint region (fixed location)
              |
              v
        inode map  --(inode 41)--> log offset 918,272
                                        |
                                        v
                                  inode 41 (current version) --> data blocks

   SEGMENT CLEANING

   before: segment 12 (1 MB), 8 blocks, 3 still live
     [ live ][ dead ][ live ][ dead ][ dead ][ live ][ dead ][ dead ]
   cleaner: copy the 3 live blocks to the log head, free segment 12
   after:  segment 12 = FREE ; log head grew by 3 blocks

   CLEANING COST DEPENDS ON UTILISATION u
     write cost = 2 / (1 - u)     (read the segment + rewrite live data)
       u = 0.3 -> 2.9x     comfortable
       u = 0.7 -> 6.7x     noticeable
       u = 0.9 -> 20x      the volume feels broken
     This is why LFS (and SSDs) need free space to perform.

# A log-structured store with an inode map and a cost-benefit cleaner.
class LogFS:
    SEGMENT = 8                                   # blocks per segment (tiny, for clarity)

    def __init__(self):
        self.log = []                             # append-only list of (ino, blk, data)
        self.imap = {}                            # (ino, blk) -> log position
        self.free_segments = 0

    def write(self, ino, blk, data):
        self.log.append((ino, blk, data))         # ALWAYS append; never overwrite
        self.imap[(ino, blk)] = len(self.log) - 1 # old position becomes garbage
        return len(self.log) - 1

    def read(self, ino, blk):
        pos = self.imap.get((ino, blk))           # one indirection through the map
        return None if pos is None else self.log[pos][2]

    def live_map(self):
        return set(self.imap.values())

    def utilisation(self):
        segs = {}
        live = self.live_map()
        for pos in range(len(self.log)):
            segs.setdefault(pos // self.SEGMENT, [0, 0])
            segs[pos // self.SEGMENT][1] += 1
            if pos in live:
                segs[pos // self.SEGMENT][0] += 1
        return {s: (l / t) for s, (l, t) in segs.items()}

    def clean(self, threshold=0.5):
        """Copy live blocks out of low-utilisation segments, then free them."""
        copied = 0
        for seg, u in sorted(self.utilisation().items(), key=lambda kv: kv[1]):
            if u >= threshold or seg == (len(self.log) - 1) // self.SEGMENT:
                continue                          # skip full segments and the head
            for pos in range(seg * self.SEGMENT, min((seg+1)*self.SEGMENT, len(self.log))):
                if pos in self.live_map():
                    ino, blk, data = self.log[pos]
                    self.write(ino, blk, data)    # copy forward to the head
                    copied += 1
            self.free_segments += 1
        return copied

fs = LogFS()
for i in range(24):                                # initial writes
    fs.write(ino=1, blk=i % 6, data=f"v{i}")       # 6 blocks, repeatedly updated
print("log entries :", len(fs.log))                # 24 -- most are now garbage
print("live blocks :", len(fs.live_map()))         # 6
print("utilisation :", {s: f"{u:.0%}" for s, u in fs.utilisation().items()})
print("copied by cleaner:", fs.clean())
print("segments freed   :", fs.free_segments)

# Cleaning write-amplification as a function of segment utilisation.
for u in (0.1, 0.3, 0.5, 0.7, 0.9, 0.95):
    print(f"utilisation {u:>4.0%} -> write cost {2/(1-u):>5.1f}x")

# F2FS: a production log-structured file system designed for flash.
sudo mkfs.f2fs -l flashvol /dev/sdb1
sudo mount -t f2fs /dev/sdb1 /mnt/flash
cat /sys/fs/f2fs/sdb1/gc_idle           # garbage collection policy
cat /sys/fs/f2fs/sdb1/reclaim_segments
sudo cat /proc/fs/f2fs/sdb1/status | head -20
#   Utilization: 43% ...
#   Main area: ... segments
#   GC calls: 120 (BG: 118)             <- the cleaner, running in the background

# The same idea inside every SSD: the FTL is a log-structured mapping layer,
# and over-provisioning is the free space its cleaner needs.
sudo nvme smart-log /dev/nvme0 | grep -i 'percentage_used\|data_units_written'
sudo smartctl -a /dev/sda | grep -i 'wear\|write amplification'

# Keeping utilisation low is not optional on either.
df -h /mnt/flash          # above ~85% full, GC cost climbs sharply
sudo fstrim -v /mnt/flash # tell the device which blocks are dead

Key takeaways

• A log-structured file system appends every write — data and metadata — to one sequential log and never updates in place.
• The motivating bet is that caches absorb reads, so the device workload is write-dominated, and sequential writing is what devices do best.
• Inodes move on every write, so an inode map plus a fixed checkpoint region is needed to find them, adding one indirection to reads.
• A cleaner must reclaim segments by copying live blocks forward; its cost is governed by segment utilisation, roughly 2/(1-u).
• Performance therefore depends on keeping free space available: at 90% utilisation, cleaning can multiply write traffic twentyfold.
• The design lives on in WAFL, F2FS, LSM-tree databases, copy-on-write file systems, and inside every SSD's flash translation layer.

🧪 Practice

1. Compute the cleaning write cost at utilisations of 20%, 60%, and 85%, and explain in one sentence why the curve is shaped that way.
2. Trace the reads needed to fetch block 0 of inode 41 in an LFS, naming each structure touched, and compare with a traditional inode-based file system.
3. Interview-style: "Why is a log-structured design a natural fit for SSDs, and where does it still hurt?" Hint: relate the log's append-only behaviour to the erase-block constraint, then ask what happens when the workload is random updates on a nearly-full device.

Copy-on-Write File Systems

Theory

Copy-on-write takes the log-structured insight — never overwrite live data — and applies it to a tree rather than a log. When a block changes, write the new version to a new location, then update the parent to point at it; but the parent must also not be overwritten, so write a new parent too, and so on up to the root. The final step is to atomically switch a single pointer, the uberblock or superblock, to the new root.

The consequence is enormous: the file system is always consistent on disk. The old tree remains completely intact until the root pointer flips, and the flip is a single-block atomic write. There is no window in which a crash leaves a half-applied change, so there is no journal, no replay, and no fsck in the traditional sense. A crash simply leaves the previous root in place, and the file system mounts instantly at the last consistent state.

Once nothing is overwritten, several features become nearly free:

• Snapshots. Keep a reference to an old root. That entire tree is preserved, sharing every unchanged block with the live file system. Creating a snapshot is O(1) and costs nothing until blocks diverge. Deleting one means dropping references.
• Clones. A writable snapshot: start from an old root and let it diverge. This is how VM templates and container images are provisioned instantly.
• Cheap replication. The difference between two snapshots is exactly the set of blocks written between them, so zfs send/btrfs send can ship incremental changes without scanning anything.
• End-to-end checksums. Since a parent is rewritten whenever a child changes, the parent can store the child's checksum. Verifying on read detects silent corruption and, with redundancy, repairs it. This closes the gap RAID leaves — RAID detects a missing drive, not a drive that returns wrong bytes.

The costs are equally characteristic:

• Fragmentation from random updates. Overwriting a block in the middle of a large file relocates it, so a randomly-updated database file becomes progressively scattered. ZFS and Btrfs both offer nodatacow for such files, which trades checksums and snapshot granularity for in-place updates.
• Write amplification up the tree. Changing one 4 KB block may rewrite several ancestor blocks. Batching (ZFS's transaction groups, committed every few seconds) amortises this heavily.
• Space accounting is confusing. A file deleted from the live file system frees nothing if a snapshot still references its blocks, which is the most common ZFS support question in existence.
• Free space matters even more than usual. Above roughly 80% full, the allocator struggles to find contiguous space for new versions and performance degrades sharply.

Example

   COPY-ON-WRITE UPDATE: WRITE NEW, THEN FLIP ONE POINTER

   BEFORE                              DURING (old tree still intact)
        [root]                              [root]      [root']
        /    \                              /    \      /     \
    [A]      [B]                        [A]      [B]  [A]     [B']
    / \      / \                        / \      / \          /  \
  [d1][d2] [d3][d4]                   [d1][d2][d3][d4]     [d3] [d4']
                                                                  ^ new block
  update d4:
    1. write d4'  (new location)      AFTER: uberblock -> root'
    2. write B'   pointing at d4'          [root']
    3. write root' pointing at B'          /     \
    4. ATOMIC: uberblock -> root'       [A]      [B']
                                        / \      /  \
  crash before step 4  -> old root      [d1][d2][d3][d4']
  is still current: NOTHING to repair.
                                      d4, B, root are now free (unless a
                                      SNAPSHOT still references them).

   SNAPSHOTS ARE JUST RETAINED ROOTS

   snapshot@monday -> [root]     shares [A],[d1],[d2],[d3] with the live tree
   live            -> [root']    only d4' and B' and root' are extra
   cost of the snapshot: ONE pointer + the blocks that later diverge

   END-TO-END CHECKSUMS

   [root'] { ptr->B', cksum(B')=0x9f3a }
              |
           [B'] { ptr->d4', cksum(d4')=0x2b71 }
                    |
                  [d4']  read it, hash it, compare with 0x2b71
                         mismatch -> the mirror copy is read and the
                         bad copy is REWRITTEN automatically (self-healing)

# Copy-on-write with structural sharing, and snapshots as retained roots.
class CowTree:
    """Each 'write' produces a NEW root; old roots remain valid snapshots."""
    def __init__(self):
        self.blocks = {}                   # block id -> content (never mutated)
        self.next_id = 0
        self.root = self._alloc({})        # root maps filename -> block id
        self.snapshots = {}

    def _alloc(self, content):
        bid = self.next_id
        self.next_id += 1
        self.blocks[bid] = content         # immutable once written
        return bid

    def write(self, name, data):
        new_data_block = self._alloc(data)                 # 1. new data block
        table = dict(self.blocks[self.root])               # 2. copy the parent
        table[name] = new_data_block
        self.root = self._alloc(table)                     # 3. new root
        return self.root                                   # 4. "flip" the pointer

    def read(self, name, root=None):
        table = self.blocks[root if root is not None else self.root]
        bid = table.get(name)
        return None if bid is None else self.blocks[bid]

    def snapshot(self, label):
        self.snapshots[label] = self.root                  # O(1): keep a root
        return self.root

    def live_blocks(self):
        """Blocks reachable from the live root or any snapshot."""
        roots = [self.root] + list(self.snapshots.values())
        live = set()
        for r in roots:
            live.add(r)
            live.update(self.blocks[r].values())
        return live

fs = CowTree()
fs.write("config", "version=1")
fs.write("data",   "aaa")
fs.snapshot("monday")                       # costs one reference
fs.write("config", "version=2")             # config diverges
fs.write("data",   "bbb")

print("live  config :", fs.read("config"))                       # version=2
print("monday config:", fs.read("config", fs.snapshots["monday"]))# version=1
print(f"blocks allocated : {len(fs.blocks)}")
print(f"blocks reachable : {len(fs.live_blocks())}")
print(f"blocks freeable  : {len(fs.blocks) - len(fs.live_blocks())}")
# Deleting the snapshot would make the old config/data blocks freeable --
# which is why "rm" on a snapshotted dataset frees no space.

# ZFS: snapshots, clones, and self-healing.
sudo zpool create tank mirror /dev/sdb /dev/sdc
sudo zfs create tank/projects
sudo zfs snapshot tank/projects@before-upgrade      # instant, no space used
sudo zfs list -t snapshot -o name,used,refer
#   tank/projects@before-upgrade   0B   1.2G     <- USED grows only as data diverges

sudo zfs rollback tank/projects@before-upgrade      # undo everything since
sudo zfs clone tank/projects@before-upgrade tank/test  # writable copy, instant
sudo zfs send -i @monday tank/projects@tuesday | ssh backup zfs recv tank/projects

# Checksums catching what RAID cannot.
sudo zpool status -v tank
#   scan: scrub repaired 128K in 00:12:31 with 0 errors
#   NAME  STATE  READ WRITE CKSUM
#   sdb   ONLINE    0     0     3     <- three blocks returned WRONG data
# RAID would have served the corrupt bytes; ZFS detected and repaired them.
sudo zpool scrub tank                  # verify every block against its checksum

# Btrfs equivalents.
sudo btrfs subvolume create /mnt/data/projects
sudo btrfs subvolume snapshot -r /mnt/data/projects /mnt/data/.snap/2026-09-11
sudo btrfs filesystem df /mnt/data     # why df's numbers look strange
sudo btrfs scrub start /mnt/data

# The CoW fragmentation problem, and the escape hatch.
sudo filefrag /var/lib/mysql/ibdata1   # thousands of extents after months
sudo chattr +C /var/lib/mysql/         # disable CoW for new files here
# Trade-off: no checksums, no snapshot granularity for those files.

Key takeaways

• Copy-on-write never overwrites live data: new versions are written elsewhere and the change is published by atomically updating one root pointer.
• The on-disk state is therefore always consistent, so no journal and no fsck are needed — a crash simply leaves the previous root current.
• Snapshots are retained roots: O(1) to create, and they consume space only as blocks diverge.
• Clones are writable snapshots, and snapshot differences give efficient incremental replication (zfs send, btrfs send).
• Rewriting parents makes it natural to store a child's checksum in its parent, giving end-to-end integrity and self-healing when redundancy exists.
• Costs are fragmentation under random overwrite, write amplification up the tree, confusing space accounting while snapshots hold blocks, and sharp degradation above roughly 80% full.

🧪 Practice

1. Draw a four-level tree and mark every block that must be rewritten when one leaf changes. Count them, and state the write amplification for a 4 KB logical write.
2. Explain why deleting a 100 GB file on a ZFS dataset can free zero bytes, and give the command sequence that actually reclaims the space.
3. Interview-style: "Why can ZFS detect and repair corruption that a RAID-5 array serves silently?" Hint: ask what information each system has about what the data is supposed to be, and where that information is stored relative to the data.

Consistency Checking

Theory

Journalling and copy-on-write prevent inconsistency from ordinary crashes. They do not cover everything: a firmware bug, a failing cable, a cosmic-ray bit flip in a cached metadata block, an administrator writing to a mounted device, or a bug in the file system itself can all produce structures that violate invariants. For those cases the offline checker — fsck on UNIX, chkdsk on Windows — remains the last line of defence.

A checker verifies the file system's invariants and repairs violations, typically in several passes:

1. Blocks and sizes. Walk every inode's block pointers. Build a map of which blocks are claimed and by whom. Detect blocks claimed by two files (cross-linked), blocks claimed but marked free, and inode sizes disagreeing with the blocks actually allocated.
2. Directory structure. Walk the directory tree from the root. Check that every entry's inode number is valid and in use, that . and .. are correct, and that the tree is acyclic.
3. Connectivity. Any inode with a nonzero link count that no directory entry references is orphaned; it is linked into lost+found under its inode number so the data is not lost.
4. Reference counts. Compare each inode's stored nlink against the number of directory entries actually found, and correct discrepancies.
5. Free maps. Rebuild the block and inode bitmaps from what the scan actually found, since the maps are derivable from the authoritative structures.

Note the asymmetry in repairs. A leaked block is repaired perfectly — mark it free. A wrong link count is repaired perfectly — recompute it. But a cross-linked block cannot be repaired correctly: the checker cannot know which file the data belongs to. The usual action is to duplicate the block into both files, leaving one of them with wrong contents, and report it. This is why "fsck completed successfully" does not mean "no data was lost".

The practical problems with checking are its cost and its danger.

Cost. The scan is O(number of inodes + number of blocks). On a volume with hundreds of millions of files it can take hours, all of them downtime, and it needs memory proportional to the inode count — large checks have been known to run out of RAM. This is the entire motivation for journalling, and why a clean-shutdown flag exists: the checker skips the scan if the superblock says the volume was unmounted cleanly.

Danger. A checker in repair mode modifies damaged structures based on inference. If the damage is not what it assumes — for example, if the wrong superblock copy is being used — repairs can destroy recoverable data. The standing rule is: run read-only first (fsck -n), and take an image of the device (ddrescue) before any repair of a volume whose contents matter.

Modern systems reduce reliance on checking without abandoning it. ext4 tracks per-group "unused inode" counts so fsck can skip regions entirely. XFS's xfs_repair is heavily parallelised, and XFS added online scrubbing (xfs_scrub) that verifies a mounted volume. ZFS and Btrfs replace the concept with scrub: read every block, verify its checksum, repair from redundancy — which runs online, finds silent corruption that a structural checker cannot detect, and is expected to run routinely rather than after a disaster.

Example

   INVARIANTS A CHECKER VERIFIES, AND THE DAMAGE EACH CATCHES

   1. every block is claimed by AT MOST ONE inode
        inode 41 -> blocks {100, 101, 102}
        inode 77 -> blocks {102, 103}          <- 102 CROSS-LINKED
        repair: duplicate 102 into both; ONE OF THEM IS NOW WRONG.

   2. the block bitmap matches the blocks actually claimed
        bitmap says 500 used; scan finds 480 claimed
        -> 20 LEAKED blocks.  repair: mark them free.  (lossless)

   3. every in-use inode is reachable from the root
        inode 93: nlink=1, no directory entry anywhere
        -> ORPHAN. repair: link into /lost+found/#93. (data preserved)

   4. stored nlink == number of directory entries found
        inode 41: nlink=3, but only 2 entries reference it
        -> repair: set nlink=2.  (lossless; the reverse leaks the inode)

   5. directory invariants
        "." points to self, ".." points to parent, no cycles
        a directory whose ".." is wrong detaches a whole subtree.

   REPAIR QUALITY IS NOT UNIFORM
     leaked block        -> perfect repair
     wrong nlink         -> perfect repair
     orphan inode        -> data preserved, name lost
     cross-linked block  -> IMPOSSIBLE to repair correctly
     corrupt superblock  -> use a backup copy (fsck -b)

   COST
     fsck:   O(inodes + blocks), offline, hours on a large volume
     journal replay: O(journal), seconds
     zfs scrub: O(USED data), ONLINE, and finds corruption fsck cannot

# A checker's core passes over a toy file system image.
def check(inodes, dirents, block_bitmap, nblocks):
    """
    inodes:       {ino: {"nlink": n, "blocks": [...]}}
    dirents:      [(parent_ino, name, ino), ...]
    block_bitmap: set of blocks marked USED
    """
    problems = []

    # PASS 1: block ownership -- cross-links and leaks
    owner = {}
    claimed = set()
    for ino, meta in inodes.items():
        for b in meta["blocks"]:
            if b in owner:
                problems.append(
                    f"CROSS-LINKED block {b}: inodes {owner[b]} and {ino} "
                    f"(cannot be repaired correctly)")
            owner[b] = ino
            claimed.add(b)

    leaked = block_bitmap - claimed
    if leaked:
        problems.append(f"LEAKED {len(leaked)} blocks marked used but unclaimed: "
                        f"{sorted(leaked)} -> repair: mark free")

    unmarked = claimed - block_bitmap
    if unmarked:
        problems.append(f"CLAIMED but marked FREE: {sorted(unmarked)} "
                        f"-> a future allocation would corrupt a live file")

    # PASS 2/3: connectivity -- orphans
    referenced = {ino for _, _, ino in dirents}
    for ino, meta in inodes.items():
        if meta["nlink"] > 0 and ino not in referenced:
            problems.append(f"ORPHAN inode {ino} -> link into /lost+found/#{ino}")

    # PASS 4: link counts
    from collections import Counter
    actual = Counter(ino for _, _, ino in dirents)
    for ino, meta in inodes.items():
        if ino in referenced and actual[ino] != meta["nlink"]:
            problems.append(f"inode {ino}: nlink={meta['nlink']} but "
                            f"{actual[ino]} entries found -> repair: set to {actual[ino]}")
    return problems

inodes = {
    41: {"nlink": 3, "blocks": [100, 101, 102]},   # nlink wrong
    77: {"nlink": 1, "blocks": [102, 103]},        # 102 cross-linked with 41
    93: {"nlink": 1, "blocks": [104]},             # orphan: no dirent
}
dirents = [(2, "a.txt", 41), (2, "b.txt", 41), (2, "c.txt", 77)]
bitmap  = {100, 101, 102, 103, 104, 200, 201}      # 200,201 leaked

for p in check(inodes, dirents, bitmap, nblocks=1024):
    print("-", p)

# ALWAYS check read-only first. A repair pass modifies damaged structures.
sudo fsck -n /dev/sdb1                  # -n: answer "no" to every repair prompt
sudo e2fsck -fn /dev/sdb1               # -f: force even if marked clean

# Image the device before repairing anything you care about.
sudo ddrescue /dev/sdb1 /backup/sdb1.img /backup/sdb1.log
sudo e2fsck -fy /backup/sdb1.img        # practise the repair on the COPY

# Then repair for real.
sudo e2fsck -fy /dev/sdb1               # -y: assume yes
sudo e2fsck -b 32768 /dev/sdb1          # damaged primary superblock: use a backup
ls -l /lost+found/                      # orphaned inodes end up here, named by number

# Force a check at the next boot, or schedule one by mount count.
sudo touch /forcefsck
sudo tune2fs -c 30 -i 6m /dev/sda2      # check every 30 mounts or 6 months
sudo tune2fs -l /dev/sda2 | grep -i 'filesystem state\|mount count'
#   Filesystem state:  clean            <- why a normal boot skips the scan

# XFS: repair is a separate tool, and online scrub exists.
sudo xfs_repair -n /dev/sdb1            # dry run
sudo xfs_repair /dev/sdb1               # must be UNMOUNTED
sudo xfs_scrub /mnt/data                # ONLINE verification

# Checksum-based file systems replace checking with scrubbing.
sudo zpool scrub tank && sudo zpool status tank
sudo btrfs scrub start -B /mnt/data
# These are ONLINE, routine, and detect silent corruption that fsck cannot.

Key takeaways

• Consistency checkers verify structural invariants — block ownership, directory structure, connectivity, link counts, free maps — in successive passes.
• Repair quality varies: leaked blocks and wrong link counts are fixed perfectly, orphans keep their data but lose their names, and cross-linked blocks cannot be repaired correctly.
• Checking costs O(inodes + blocks) and is offline, which is why journalling and a clean-shutdown flag exist to avoid it.
• A repair pass modifies data based on inference, so run read-only first and image the device before repairing anything valuable.
• Backup superblocks make a damaged primary copy recoverable with fsck -b.
• Checksumming file systems replace the concept with online scrubbing, which runs on a mounted volume and detects silent corruption that a structural check cannot see.

🧪 Practice

1. Given inode 20 claiming blocks {5,6,7} and inode 31 claiming {7,8}, state the invariant violated, the repair a checker performs, and why the result is still wrong.
2. Explain why an orphaned inode appears in lost+found under a numeric name, and describe how you would identify what the file originally was.
3. Interview-style: "A 60 TB volume with 400 million files needs an unclean-shutdown recovery. Estimate the downtime and propose an architecture that avoids it next time." Hint: compare the cost model of a full structural scan against journal replay and against a checksumming file system's mount path.

Backup and Restore

Theory

Every technique so far protects against crashes. None of them protects against deletion, ransomware, a bad deployment, a failed upgrade, fire, or theft. Redundancy and snapshots are not backups: RAID faithfully mirrors rm -rf, and a snapshot on the same pool dies with the pool. A backup is a copy that is independent of the original's failure modes.

The standard rule of thumb is 3-2-1: three copies of the data, on two different media types, with one off-site. The modern amendment adds "one offline or immutable", because ransomware specifically seeks out and encrypts reachable backups.

Backups come in three kinds, and the choice is a trade between backup time and restore time:

Type	Copies	Backup cost	Restore cost
Full	Everything	Highest	One archive
Incremental	Changes since the last backup of any kind	Lowest	Last full + every incremental since
Differential	Changes since the last full	Middle, grows daily	Last full + one differential

The typical schedule — weekly full, daily incremental — restores from up to seven archives, and every one of them must be readable. That is the argument for differentials when restore time matters more than backup window.

Two definitions drive the design, and they should be set before choosing tools:

• RPO (Recovery Point Objective): how much data you can afford to lose, which sets backup frequency.
• RTO (Recovery Time Objective): how long you can afford to be down, which sets restore mechanism — a tape restore of 40 TB will not meet a two-hour RTO regardless of how good the backups are.

File-system features make good backups cheaper. Taking a backup from a snapshot rather than the live file system gives a consistent point-in-time view, so the archive does not contain a file copied half-before and half-after a change. zfs send/btrfs send ship exactly the blocks that changed between two snapshots, making incrementals proportional to change volume rather than to tree size. Tools like rsync --link-dest and Borg/restic achieve similar results through hard links and content-defined chunking with deduplication.

Application consistency is a separate concern from file-system consistency. A snapshot of a running database gives a crash-consistent image — the database will recover from its own journal on restore, usually fine — but the safe path is to quiesce the application (FLUSH TABLES WITH READ LOCK, pg_start_backup, VSS on Windows) for the instant the snapshot is taken.

Finally, the rule that supersedes all the others: an untested backup is not a backup. Restore drills catch the failures that matter — missing encryption keys, an incremental chain with a hole in it, a backup that silently stopped six weeks ago, an archive format no longer readable by the current tooling. Schedule them.

Example

   BACKUP TYPES OVER ONE WEEK (Sunday full, daily thereafter)

   INCREMENTAL: each day copies changes since THE PREVIOUS BACKUP
     Sun [FULL 500 GB]  Mon[8G] Tue[6G] Wed[9G] Thu[7G] Fri[8G] Sat[5G]
     backup volume: 543 GB    restore on Sat: FULL + 6 archives (all required)
     one unreadable archive breaks the chain from that point on.

   DIFFERENTIAL: each day copies changes since THE LAST FULL
     Sun [FULL 500 GB]  Mon[8G] Tue[14G] Wed[23G] Thu[30G] Fri[38G] Sat[43G]
     backup volume: 656 GB    restore on Sat: FULL + 1 archive

   3-2-1 (plus immutability)

     copy 1: live volume          (NVMe, on-line)
     copy 2: local backup server  (HDD, different medium, hourly)
     copy 3: object storage       (off-site, versioned + object lock)
                                   ^ immutable: ransomware cannot delete it

   RPO / RTO DRIVE THE DESIGN

     RPO 24 h, RTO 48 h -> nightly to tape is fine
     RPO  1 h, RTO  4 h -> hourly snapshots + replicated off-site copy
     RPO  0,   RTO  0   -> not a backup problem: synchronous replication

   WHAT IS *NOT* A BACKUP
     RAID          : mirrors your deletion instantly
     snapshots     : die with the pool they live on
     replication   : replicates the corruption too
     "it's in git" : only if everything you need is committed AND pushed

# --- snapshot-based, incremental, consistent: the cheap modern path ---
sudo zfs snapshot -r tank/projects@$(date +%F-%H%M)
sudo zfs send -i @2026-09-10-0300 tank/projects@2026-09-11-0300 \
  | ssh backup-host zfs recv -F backup/projects
# Ships only the blocks changed between the two snapshots.

sudo btrfs subvolume snapshot -r /data /data/.snap/$(date +%F)
sudo btrfs send -p /data/.snap/2026-09-10 /data/.snap/2026-09-11 \
  | ssh backup-host btrfs receive /backup/

# --- rsync with hard-linked history: full-looking, incremental-costing ---
rsync -aH --delete --link-dest=/backup/2026-09-10 \
      /data/ /backup/2026-09-11/
# Unchanged files are hard links to yesterday's copy: each dated directory
# LOOKS like a full backup but costs only the changed files.

# --- deduplicating, encrypted, verifiable ---
borg init --encryption=repokey-blake2 /backup/repo
borg create --stats --compression zstd /backup/repo::{hostname}-{now} /data
borg check --verify-data /backup/repo        # actually read and verify
borg list /backup/repo                       # is the chain complete?

# --- application consistency around the snapshot ---
mysql -e "FLUSH TABLES WITH READ LOCK;" &     # hold the lock...
sudo zfs snapshot tank/mysql@backup           # ...take the snapshot...
kill %1                                       # ...release immediately

# --- classic incremental/differential with tar ---
tar -czf full.tar.gz --listed-incremental=snapshot.snar /data    # Sunday: full
tar -czf inc-mon.tar.gz --listed-incremental=snapshot.snar /data # Monday: changes
# The .snar file IS the chain state. Lose it and incrementals become fulls.

# --- THE PART PEOPLE SKIP: restore drills ---
borg extract --dry-run /backup/repo::hostname-2026-09-11
sudo zfs recv -n backup/test < stream          # verify the stream parses
restic restore latest --target /tmp/restore-test && diff -r /tmp/restore-test/data /data
# Put this in cron. An untested backup is a hypothesis, not a backup.

# --- verify backups are actually happening ---
find /backup -maxdepth 1 -mtime -1 | wc -l     # something written today?
borg list /backup/repo | tail -1               # most recent archive date

# Backup volume and restore complexity: incremental vs differential.
DAILY_CHANGE_GB = [8, 6, 9, 7, 8, 5]        # Mon..Sat
FULL_GB = 500

incremental = DAILY_CHANGE_GB[:]                                  # each day: delta
differential = []
cumulative = 0
for d in DAILY_CHANGE_GB:
    cumulative += d                                               # since the full
    differential.append(cumulative)

print(f"{'day':<5}{'incr GB':>9}{'diff GB':>9}")
for i, day in enumerate(["Mon","Tue","Wed","Thu","Fri","Sat"]):
    print(f"{day:<5}{incremental[i]:>9}{differential[i]:>9}")

print(f"\nweek backup volume : incremental {FULL_GB+sum(incremental):>5} GB, "
      f"differential {FULL_GB+sum(differential):>5} GB")
print(f"archives to restore Saturday: incremental {1+len(incremental)}, "
      f"differential 2")

# RTO feasibility: can the restore mechanism meet the objective?
RESTORE_GB  = 500 + sum(incremental)
for medium, mb_s in [("LTO-8 tape", 360), ("1 GbE network", 110),
                     ("10 GbE network", 1100), ("local NVMe", 2000)]:
    hours = RESTORE_GB * 1024 / mb_s / 3600
    print(f"{medium:<16} restore of {RESTORE_GB} GB: {hours:>5.1f} h "
          f"{'-- misses a 4 h RTO' if hours > 4 else ''}")

Key takeaways

• RAID, snapshots, and replication protect against device failure, not against deletion, corruption, or ransomware — only an independent copy does.
• 3-2-1 means three copies, two media types, one off-site; add one offline or immutable copy against ransomware.
• Incremental backups minimise backup time but require the full plus every increment to restore; differentials cost more daily and restore from two archives.
• RPO sets backup frequency and RTO sets the restore mechanism; a restore that cannot physically move the data in time fails regardless of backup quality.
• Snapshots give a consistent point-in-time source, and send/receive or --link-dest makes incrementals proportional to change volume.
• Crash-consistent snapshots usually suffice for databases that journal, but quiescing the application first is the safe path.
• Backups that are never restored are untested hypotheses; schedule restore drills and monitor that backups are still running.

🧪 Practice

1. Given a 2 TB full backup and daily changes of 30 GB, compute a week's total backup volume and the number of archives needed for a Friday restore, under incremental and under differential schedules.
2. Design a backup plan for a 5 TB database with RPO 15 minutes and RTO 2 hours. Name the mechanisms and justify that each objective is physically achievable.
3. Interview-style: "We have hourly snapshots, RAID-6, and off-site replication. Are we protected against ransomware?" Hint: consider what an attacker with administrative credentials can reach, and what property a copy needs in order to be beyond their reach.

<a id="105-real-world-file-systems"></a>

10.5 Real-World File Systems

Every design decision in the previous sections appears in shipping file systems, combined differently according to what each was built for. This section reads six of them as case studies — what each chose, why, and what it costs.

ext4

Theory

ext4 is the default Linux file system on most distributions and the direct descendant of a lineage: ext2 (1993, no journal), ext3 (2001, added journalling while keeping ext2's on-disk layout), ext4 (2008, added extents, larger limits, and better allocation). That continuity is the key to understanding it — ext4 is a carefully evolved design, not a clean-sheet one, and its strengths and limits both follow from that.

Its structure is exactly the classical one from Section 10.2: a volume divided into block groups, each holding a superblock copy, group descriptors, block and inode bitmaps, an inode table, and data blocks. A file's inode is placed in the same group as its parent directory, and its data in the same group as its inode, so metadata and data stay close.

The improvements ext4 added over ext3 are a good summary of this chapter's themes:

• Extents replaced indirect blocks. Four extent records live in the inode; beyond that an extent tree. This cut metadata drastically and made deleting large files near-instant.
• Delayed allocation. Blocks are chosen at writeback rather than at write(), so the allocator knows the final size and can pick one large run. This is the main reason ext4 fragments far less than ext3.
• Multiblock allocation (mballoc) allocates many blocks in one operation with a buddy-style structure, instead of one at a time.
• Persistent preallocation via fallocate with uninitialised extents.
• htree directories giving O(log n) lookup, enabled by the dir_index feature.
• Journal checksums, so a torn journal write is detected rather than replayed as valid.
• Larger limits: 1 EB volumes, 16 TB files, and 64-bit block numbers with the 64bit feature.

Its enduring limitations are equally characteristic of an evolved design. The inode count is fixed at mkfs time, so a volume can exhaust inodes with free space remaining. There are no data checksums, so silent corruption in file data is neither detected nor repaired (metadata is checksummed with metadata_csum). There are no snapshots at the file system level — LVM snapshots are the usual substitute, at a performance cost. And a file system cannot be shrunk while mounted, though it can be grown.

The reason ext4 remains the default despite newer options is unglamorous and entirely valid: two decades of production exposure, the most mature repair tooling in Linux (e2fsck, debugfs, e2image), predictable behaviour, and performance that is good across almost every workload without tuning. It is the safe choice, and for most systems the right one.

Example

   ext4 VOLUME LAYOUT

   +-------+========= block group 0 =========+===== group 1 =====+ ...
   | boot  | SB | GD | blk | ino | inode tbl | (backup SB in some|
   | block |    |    | bmp | bmp |           |  groups only)     |
   +-------+----+----+-----+-----+-----------+-------------------+
                                 |   data blocks                 |
                                 +-------------------------------+
   flex_bg groups several block groups' metadata together, so metadata
   is contiguous and data areas are larger.

   ext3 -> ext4 FOR ONE 1 GB FILE

   ext3 (indirect blocks)            ext4 (extents)
     262,144 block pointers            8 extent records (32,768-block cap)
     ~1 MB of indirect blocks          96 bytes, IN THE INODE
     3 reads to locate a far block     0 extra reads
     delete: walk 262,144 pointers     delete: free 8 ranges

   THE ext4 INODE (256 bytes)
   +------------------------------------------+
   | mode | uid | size | atime/mtime/ctime/crtime |
   | links | blocks | flags | ...               |
   +------------------------------------------+
   | i_block[60 bytes]:  extent header + 4 extents  (or inline data)   |
   +------------------------------------------+
   | extra: nanosecond timestamps, checksum, project id                |
   +------------------------------------------+

# Create and inspect.
sudo mkfs.ext4 -L data -E lazy_itable_init=0 /dev/sdb1
sudo tune2fs -l /dev/sdb1
#   Filesystem features: has_journal ext_attr resize_inode dir_index filetype
#                        extent 64bit flex_bg sparse_super large_file huge_file
#                        dir_nlink extra_isize metadata_csum
#   Inode count:         6553600        <- FIXED at mkfs time
#   Block size:          4096
#   Journal size:        128M

# Feature flags can be toggled after the fact (some need an unmounted fs).
sudo tune2fs -O metadata_csum /dev/sdb1      # add metadata checksums
sudo tune2fs -O ^has_journal  /dev/sdb1      # remove the journal
sudo tune2fs -m 1 /dev/sdb1                  # reduce the 5% root reserve

# Extents and delayed allocation, observed.
dd if=/dev/zero of=/mnt/data/f bs=1M count=1024 status=none
filefrag /mnt/data/f                          # a handful of extents
sync; grep Dirty /proc/meminfo                # delayed allocation drains here

# Growing (online) and shrinking (offline only).
sudo resize2fs /dev/sdb1                      # grow to fill the partition
sudo umount /mnt/data && sudo e2fsck -f /dev/sdb1 && sudo resize2fs /dev/sdb1 100G

# Repair and forensics tooling: ext4's real advantage.
sudo e2fsck -fn /dev/sdb1                     # read-only check
sudo debugfs -R "stat <12>" /dev/sdb1         # dump inode 12
sudo debugfs -R "ncheck 12" /dev/sdb1         # inode -> path
sudo e2image -r /dev/sdb1 /backup/meta.img    # metadata-only image for analysis

# The two limits that bite in production.
df -i /mnt/data                               # inode exhaustion
sudo e4defrag -c /mnt/data                    # fragmentation score

# ext4 sizing: choosing inode density from a known file-size distribution.
VOLUME_TB   = 4
BLOCK       = 4096
INODE_SIZE  = 256

def plan(bytes_per_inode, avg_file_kb):
    volume_bytes = VOLUME_TB * 1024**4
    inodes = volume_bytes // bytes_per_inode
    inode_table_gb = inodes * INODE_SIZE / 1024**3
    files_storable = volume_bytes // max(avg_file_kb * 1024, BLOCK)
    return inodes, inode_table_gb, files_storable

print(f"{'-i value':>10}{'inodes':>14}{'table':>10}{'files @4KB avg':>17}{'verdict':>12}")
for bpi in (4096, 8192, 16384, 65536, 1048576):        # mkfs.ext4 -i
    inodes, table_gb, files = plan(bpi, avg_file_kb=4)
    verdict = "inode-bound" if inodes < files else "space-bound"
    print(f"{bpi:>10,}{inodes:>14,}{table_gb:>9.1f}G{files:>17,}{verdict:>12}")
# Default (-i 16384) suits mixed workloads. A maildir or a node_modules tree
# needs -i 4096 or 8192; a media archive can use -T largefile and reclaim
# gigabytes of inode table.

Key takeaways

• ext4 is an evolutionary design: ext2's block-group layout, ext3's journal, plus extents, delayed allocation, multiblock allocation, and htree directories.
• Extents and delayed allocation are the two changes that most improved it, cutting metadata volume and fragmentation together.
• Block groups keep a file's inode near its parent directory and its data near its inode.
• Its fixed inode count, absence of data checksums, and lack of native snapshots are its real limitations.
• It remains the default because of maturity, uniquely good repair and forensic tooling, and solid untuned performance across workloads.
• Sizing decisions made at mkfs time — inode density, block size, journal size — cannot be changed later, so they deserve thought.

🧪 Practice

1. Run tune2fs -l on an ext4 volume and explain what extent, dir_index, flex_bg, and metadata_csum each provide.
2. Compute the inode count and inode table size for a 2 TB ext4 volume at -i 4096 and at -i 65536, and say which workload suits each.
3. Interview-style: "Would you choose ext4 or XFS for a 40 TB volume holding millions of small files?" Hint: compare how each handles inode allocation, parallel metadata updates, and repair time at that scale.

NTFS

Theory

NTFS has been the Windows file system since NT 3.1 in 1993, and its design decisions diverge from the UNIX tradition in ways that are worth understanding rather than dismissing.

Its organising idea is that everything is a file, and every file is a set of attributes. The volume's own metadata lives in files with reserved names: $MFT (the Master File Table), $Bitmap (free space), $LogFile (the journal), $BadClus, $Secure (the security descriptor database). Formatting a volume means creating these files.

The MFT is the analogue of the inode table, but with a crucial difference: it is itself a file, so it grows dynamically. NTFS does not exhaust "inodes" the way ext4 can. Each MFT record is typically 1 KB and contains a sequence of typed attributes:

Attribute	Contents
$STANDARD_INFORMATION	Timestamps, DOS attributes
$FILE_NAME	The name and parent directory reference (one per name)
$DATA	The file's contents — resident if small, otherwise a run list of extents
$INDEX_ROOT / $INDEX_ALLOCATION	B+-tree of entries (for directories)
$SECURITY_DESCRIPTOR	ACL reference into $Secure

That $DATA attribute carries two consequences. First, a small file's contents are resident in the MFT record itself — a file under roughly 700 bytes costs zero data clusters and one read. Second, a file may have multiple named $DATA streams ("alternate data streams"): file.txt:hidden is real, stored, and invisible to normal directory listings. This is a genuine feature (macOS resource forks map onto it, Windows marks downloaded files with a Zone.Identifier stream) and a genuine security concern, since malware has used it to hide payloads.

The rest of NTFS's feature set is a list of things added early and used heavily:

• Journalling via $LogFile, metadata-only, with recovery at mount.
• ACLs — full discretionary access control lists rather than owner/group/other bits, with inheritance rules.
• Compression and encryption per file or directory (EFS), transparent to applications.
• Sparse files and hard links, plus junctions and symbolic links (the latter requiring privilege by default).
• Volume Shadow Copy (VSS) providing snapshots for backup and "Previous Versions".
• Change journal (USN), a log of every change to the volume, which is what makes indexing and incremental backup tools efficient.
• B+-tree directories from the start, so large directories never had ext2's linear-scan problem.

Its weaknesses: no data checksums (metadata only, and NTFS relies on chkdsk plus self-healing NTFS for repair), MFT fragmentation on volumes that fill up, the specification is not public so third-party implementations are reverse-engineered (Linux's ntfs3 driver is now reasonably solid, but historically this made cross-platform use risky), and per-file compression that behaves poorly on large or random-access files.

Example

   NTFS: THE VOLUME IS MADE OF FILES

   $MFT record 0  : $MFT itself (so the MFT can grow like any file)
   $MFT record 1  : $MFTMirr   (backup of the first records)
   $MFT record 2  : $LogFile   (the journal)
   $MFT record 3  : $Volume
   $MFT record 5  : .          (the root directory)
   $MFT record 6  : $Bitmap    (free cluster map)
   $MFT record 9  : $Secure    (ACL database, shared descriptors)
   ...
   $MFT record N  : your file

   ONE MFT RECORD (1 KB)
   +---------------------------------------------------------+
   | header: record number, sequence, link count, flags       |
   +---------------------------------------------------------+
   | $STANDARD_INFORMATION  (timestamps, attributes)          |
   | $FILE_NAME             ("report.docx", parent ref)       |
   | $SECURITY_DESCRIPTOR   (ACL reference)                   |
   | $DATA                  <-- HERE IS THE CHOICE:           |
   |     small file : the BYTES THEMSELVES, resident          |
   |     large file : a RUN LIST  [(vcn 0, lcn 918272, 64),   |
   |                               (vcn 64, lcn 204800, 128)] |
   | $DATA:"Zone.Identifier"  <-- an ALTERNATE DATA STREAM    |
   +---------------------------------------------------------+

   RESIDENT vs NON-RESIDENT
     700-byte file  : 1 MFT record, 0 clusters, ONE read to get the data
     700 KB file    : 1 MFT record + run list -> clusters elsewhere

   ACLs vs UNIX MODE BITS
     UNIX : rwx r-x r-x  owner/group/other -- 9 bits, 3 principals
     NTFS : an ordered list of (principal, allow/deny, rights, inheritance)
            Deny entries are evaluated first; inheritance flows down the tree.

# --- On Windows (PowerShell) ---
# Volume and MFT details.
fsutil fsinfo ntfsinfo C:
#   Bytes Per Cluster : 4096
#   Mft Valid Data Length : 0x0000000012c00000
#   Total Reserved Clusters : ...

# Alternate data streams: real, stored, and not shown by dir.
Get-Content -Path .\report.docx -Stream Zone.Identifier
Get-Item .\report.docx -Stream *            # list every stream
dir /r report.docx                          # cmd: shows streams
Remove-Item .\report.docx -Stream Zone.Identifier   # unblock a download

# ACLs, which have no direct UNIX equivalent.
Get-Acl C:\data | Format-List
icacls C:\data /grant "Domain\Analysts:(OI)(CI)R"   # inheritable read
icacls C:\data /deny  "Domain\Interns:(OI)(CI)W"    # deny wins over allow

# Snapshots via VSS; the change journal for incremental tooling.
vssadmin list shadows
fsutil usn queryjournal C:
fsutil usn readjournal C: | Select-Object -First 20

# Repair.
chkdsk C: /scan          # online scan
chkdsk C: /f             # offline repair at next boot

# --- On Linux, reading the same volume ---
sudo mount -t ntfs3 /dev/sdb1 /mnt/win
sudo ntfsinfo -m /dev/sdb1
#   Cluster Size: 4096
#   MFT Record Size: 1024
sudo ntfscluster -f /dev/sdb1
getfattr -d -m '' /mnt/win/report.docx     # alternate streams appear as xattrs

# Resident vs non-resident: the size threshold and what it saves.
MFT_RECORD = 1024
HEADER_AND_ATTRS = 350          # approximate overhead before $DATA
CLUSTER = 4096

resident_max = MFT_RECORD - HEADER_AND_ATTRS
print(f"resident threshold ~ {resident_max} bytes\n")

def cost(size):
    if size <= resident_max:
        return ("resident", 0, 1)              # 0 clusters, 1 read
    clusters = -(-size // CLUSTER)
    return ("non-resident", clusters, 2)        # MFT record + data read(s)

for size in (100, 600, 700, 4096, 1_000_000):
    kind, clusters, reads = cost(size)
    print(f"{size:>10,} B: {kind:<13} clusters={clusters:<6} reads={reads}")

# What resident storage saves on a source tree of many tiny files.
files = [200] * 50_000 + [5000] * 20_000
res  = sum(1 for s in files if s <= resident_max)
nonres_clusters = sum(-(-s // CLUSTER) for s in files if s > resident_max)
print(f"\n{res:,} files stored resident (0 clusters each)")
print(f"{nonres_clusters:,} clusters used by the rest "
      f"({nonres_clusters*CLUSTER/1024**2:,.0f} MB)")

Key takeaways

• NTFS makes the volume's own metadata into files ($MFT, $Bitmap, $LogFile, $Secure), so the MFT grows dynamically and NTFS does not run out of file records the way ext4 runs out of inodes.
• Each MFT record is a set of typed attributes; a small file's $DATA is resident in the record, costing zero clusters and one read.
• Multiple named $DATA streams per file are supported, which is useful (download zone marking, resource forks) and a known hiding place for malware.
• It has had B+-tree directories, metadata journalling, ACLs with inheritance, compression, encryption, and sparse files since early versions.
• The USN change journal and VSS snapshots are what make Windows backup and indexing tools efficient.
• Weaknesses are the absence of data checksums, MFT fragmentation on full volumes, and a closed specification that made third-party support a long-running problem.

🧪 Practice

1. Explain why a 500-byte file on NTFS may occupy zero clusters, and compute how much space this saves for 100,000 such files at a 4 KB cluster size.
2. Create a file with an alternate data stream and show that dir hides it while dir /r reveals it. Explain one legitimate and one malicious use.
3. Interview-style: "Compare NTFS ACLs with UNIX mode bits. What can each express that the other cannot?" Hint: think about the number of principals, deny semantics, and what happens to permissions when a new file is created inside a directory.

ZFS and Btrfs

Theory

ZFS (Sun, 2005) and Btrfs (Oracle, 2009) belong to a generation that rejected the layering of the previous thirty years. Traditional systems stack a volume manager under a file system under a RAID layer, each unaware of the others — so RAID rebuilds every block of a disk whether or not it holds data, and the file system cannot ask which mirror has the correct copy. ZFS and Btrfs merge the layers, and nearly everything distinctive about them follows from that merge.

Both are copy-on-write (Section 10.4), which gives always-consistent on-disk state, instant snapshots, and writable clones. Both add end-to-end checksums stored in the parent block, so corruption is detected on every read and — when redundancy exists — repaired automatically from a good copy. Both manage a pool of devices rather than fixed partitions, so file systems are carved from shared free space instead of sized at install time.

ZFS is the more ambitious and the more rigid:

• Pools and vdevs. A pool is built from vdevs (mirror, raidz1/2/3, or single devices). Redundancy is a property of the vdev; losing a vdev loses the pool.
• RAID-Z solves the RAID-5 write hole by making every write a full-stripe write of variable width — no read-modify-write, so no partial-stripe corruption window, and no need for a battery-backed cache.
• ARC, an adaptive replacement cache that tracks both recency and frequency, generally outperforming a plain LRU page cache, with an optional SSD second level (L2ARC) and a separate log device (SLOG) for synchronous writes.
• Datasets with per-dataset properties: recordsize, compression, quota, atime, encryption. Changing a property applies to new writes immediately.
• Scrub reads and verifies every allocated block online.
• The rigidity: until recently a raidz vdev could not be expanded by adding a disk, zfs send requires compatible feature flags, and ZFS's memory appetite (especially with deduplication, which is rarely worth it) is substantial. Licensing (CDDL) keeps it out of the mainline Linux kernel, so it ships as a separate module.

Btrfs is more flexible and historically less predictable:

• Everything lives in B-trees — extent tree, subvolume trees, checksum tree — which makes the design uniform and the implementation intricate.
• Subvolumes are independently snapshottable namespaces within one file system, far lighter than ZFS datasets.
• Flexible RAID. Devices of different sizes can be added and removed online, and the profile (single, raid1, raid10) can be changed on a live file system with a rebalance.
• Online everything: grow, shrink, add devices, convert profiles, defragment — all mounted.
• The caveat: raid5/raid6 profiles still carry a write hole and are not recommended for production. Btrfs is the default on openSUSE and Fedora, and raid1/single profiles are widely trusted; parity profiles are not.

For both, the CoW cost is fragmentation under random overwrite, which is why database and VM-image directories get nodatacow (chattr +C) or a matched recordsize.

Example

   TRADITIONAL STACK vs INTEGRATED

   TRADITIONAL                          ZFS / Btrfs
   +---------------+                    +--------------------------+
   |  file system  |  ext4              |  file system + volume    |
   +---------------+                    |  manager + RAID, merged  |
   |  volume mgr   |  LVM               |                          |
   +---------------+                    |  knows WHICH blocks are  |
   |  RAID         |  mdadm             |  in use and WHICH copy   |
   +---------------+                    |  is correct              |
   |  disks        |                    +--------------------------+
   +---------------+                    |  disks                   |
                                        +--------------------------+
   rebuild: every block on the disk,    resilver: only ALLOCATED blocks
   whether used or not                  checksums say which copy is right

   SILENT CORRUPTION: WHAT EACH LAYER CAN DO

   RAID-1 (mdadm) : two copies differ -> no way to know which is correct
                    (a scrub picks one arbitrarily)
   ZFS mirror     : parent block holds cksum(child)
                    read -> hash -> mismatch -> read the OTHER copy ->
                    verify -> return good data AND REWRITE the bad copy

   ZFS POOL STRUCTURE
     pool "tank"
       +-- vdev mirror-0 : sda sdb          redundancy lives HERE
       +-- vdev mirror-1 : sdc sdd          data is striped ACROSS vdevs
       +-- log (SLOG)    : nvme0n1p1        synchronous write latency
       +-- cache (L2ARC) : nvme0n1p2        second-level read cache
     lose ANY vdev entirely -> lose the pool.

   RAID-5 WRITE HOLE, AND RAID-Z's ANSWER
     RAID-5 : write data block, then parity. Crash between them ->
              stripe parity is wrong, and NOTHING RECORDS THAT.
     RAID-Z : every write is a full stripe of variable width, committed
              by the same CoW transaction -> no partial-stripe window.

# --- ZFS ---
sudo zpool create tank mirror sda sdb mirror sdc sdd
sudo zpool add tank log /dev/nvme0n1p1 cache /dev/nvme0n1p2
sudo zpool status tank

sudo zfs create -o compression=zstd -o recordsize=1M tank/media
sudo zfs create -o compression=lz4  -o recordsize=8k tank/postgres
sudo zfs set quota=500G tank/media
sudo zfs get all tank/postgres | grep -E 'recordsize|compress|atime'

sudo zfs snapshot tank/postgres@pre-migration     # instant
sudo zfs clone tank/postgres@pre-migration tank/pgtest   # writable copy
sudo zfs rollback tank/postgres@pre-migration
sudo zfs send -i @mon tank/postgres@tue | ssh backup zfs recv tank/postgres

sudo zpool scrub tank && sudo zpool status -v tank
#   CKSUM column non-zero = silent corruption found (and repaired)
sudo zpool iostat -v tank 5
arc_summary | head -20                            # ARC hit rate

# --- Btrfs ---
sudo mkfs.btrfs -d raid1 -m raid1 /dev/sdb /dev/sdc
sudo mount /dev/sdb /mnt/data
sudo btrfs subvolume create /mnt/data/@home
sudo btrfs subvolume snapshot -r /mnt/data/@home /mnt/data/.snap/$(date +%F)
sudo btrfs subvolume list /mnt/data

sudo btrfs device add /dev/sdd /mnt/data          # online, different size is fine
sudo btrfs balance start -dconvert=raid1 -mconvert=raid1 /mnt/data
sudo btrfs filesystem usage /mnt/data             # the honest space report
sudo btrfs scrub start -B /mnt/data

# --- the CoW fragmentation escape hatch, on both ---
sudo chattr +C /var/lib/mysql                     # Btrfs: no CoW for new files
sudo zfs set recordsize=16k tank/mysql            # ZFS: match the DB page size
sudo zfs set logbias=throughput tank/mysql

# --- what NOT to do ---
# sudo mkfs.btrfs -d raid5 ...     <- write hole; not production-ready
# sudo zfs set dedup=on tank       <- needs ~5 GB RAM per TB; rarely worth it

# Why an integrated stack resilvers faster, and why checksums decide correctness.
DISK_TB, USED_FRACTION, REBUILD_MB_S = 16, 0.35, 180

raw_hours  = DISK_TB * 1024**2 / REBUILD_MB_S / 3600           # every block
used_hours = raw_hours * USED_FRACTION                          # allocated only
print(f"mdadm rebuild (whole disk) : {raw_hours:5.1f} h")
print(f"ZFS resilver (used blocks) : {used_hours:5.1f} h")
print(f"exposure window reduced by : {raw_hours - used_hours:5.1f} h\n")

# Probability of a second failure during the rebuild window (simplified).
AFR = 0.02                                       # 2% annual failure rate per disk
for hours, label in ((raw_hours, "mdadm"), (used_hours, "ZFS")):
    p = 1 - (1 - AFR) ** (hours / 8760)
    print(f"{label:<6} P(second disk fails during rebuild) = {p:.5%}")

# The checksum argument, stated plainly.
print("""
mirror without checksums: copy A says 0x41, copy B says 0x00.
  -> the array knows they DIFFER; it does not know which is RIGHT.
mirror with checksums: the parent block says cksum(child) = 0x9f3a.
  -> hash A: 0x9f3a  MATCH   -> return A, rewrite B. Corruption repaired.
""")

Key takeaways

• ZFS and Btrfs merge the file system, volume manager, and RAID layers, so redundancy operations act on allocated data and can identify which copy is correct.
• Both are copy-on-write with end-to-end checksums, giving always-consistent state, instant snapshots and clones, and self-healing when redundancy exists.
• ZFS organises pools from vdevs; RAID-Z avoids the RAID-5 write hole via variable-width full-stripe writes, and the ARC outperforms a plain LRU cache.
• ZFS datasets carry per-dataset properties (recordsize, compression, quota, encryption) applied to new writes immediately.
• Btrfs is more flexible — online device add/remove, profile conversion, subvolumes — but its raid5/raid6 profiles still have a write hole and should not be used in production.
• Both fragment under random overwrite, so database and VM files need nodatacow or a matched record size.

🧪 Practice

1. Explain, with reference to where the checksum is stored, why a ZFS mirror can repair a block that an mdadm mirror can only report as inconsistent.
2. Design a ZFS layout for a 12-disk server holding VM images with good random-write performance, and justify the vdev choice, recordsize, and any SLOG or L2ARC.
3. Interview-style: "Why does RAID-Z not need a battery-backed write cache while a hardware RAID-5 controller does?" Hint: identify the exact window in which a RAID-5 stripe can become inconsistent, and what full-stripe copy-on-write writes does to that window.

FAT and exFAT

Theory

FAT is the oldest file system still in wide use, dating to 1977, and it survives not because it is good but because it is universal. A camera, a car stereo, a printer, a UEFI firmware, and a thirty-year-old computer can all read a FAT volume. That interoperability is the entire value proposition, and every design flaw below is the price.

The structure is the linked allocation of Section 10.3: a File Allocation Table near the start of the volume, one entry per cluster, each entry naming the next cluster in the file's chain or marking end-of-chain, free, or bad. The directory is a flat array of 32-byte entries holding the name, attributes, first cluster, and size.

The variants differ mainly in the width of a FAT entry, which caps the cluster count:

Variant	Entry width	Max clusters	Max file	Typical use
FAT12	12 bits	4,084	32 MB	Floppies
FAT16	16 bits	65,524	2 GB	Old volumes, small cards
FAT32	28 bits	~268 M	4 GB − 1 byte	USB sticks, SD cards, EFI System Partition
exFAT	32 bits	~4 G	16 EB	SDXC cards, large removable media

The 4 GB file limit on FAT32 is the single most-encountered limitation in consumer computing — it is why a video file refuses to copy to a USB stick that has 200 GB free.

FAT's weaknesses are structural, not incidental:

• No journal. An interrupted write leaves an inconsistent FAT, which is why removable media must be ejected properly and why fsck.vfat is needed after a yank.
• No permissions, no ownership. There is an archive/hidden/system/read-only attribute byte and nothing more. Copying a UNIX tree to FAT loses every mode bit and every symlink.
• Linear directory search — O(n) lookup, so large directories are slow.
• Fragmentation with no online defragmentation and an allocator with no locality strategy.
• Large clusters on large volumes. Because the FAT's size grows with the cluster count, big volumes force big clusters (32 KB or 64 KB), and internal fragmentation follows: a million 2 KB files on 32 KB clusters consume 32 GB to store 2 GB.
• Long filenames are a retrofit. VFAT stores names over 8.3 characters in a chain of pseudo-entries, with a checksum tying them to the real entry — functional, but a patch.

exFAT (2006, and since 2019 openly documented and in the Linux kernel) keeps the model and removes the worst limits: 64-bit sizes, a free-space bitmap alongside the FAT so allocation does not scan the table, contiguous-file optimisation that skips FAT chains entirely for unfragmented files, and support for very large clusters. It still has no journal and no permissions. It is the right choice for large removable media; it is not a general-purpose file system.

The rule that follows: use FAT32 or exFAT when something other than your own OS must read the media, and nothing else. For a Linux-only external drive use ext4; for cross-platform use with large files use exFAT and eject it properly.

Example

   FAT32 LAYOUT

   +--------+--------+--------+------------------+---------------------------+
   | boot   | FS     | FAT #1 | FAT #2 (mirror)  | data area (clusters 2..N) |
   | sector | info   |        |                  |                           |
   +--------+--------+--------+------------------+---------------------------+
              ^ free count hint    ^ two copies, because losing the FAT
                                     loses EVERY file at once

   A 32-BYTE DIRECTORY ENTRY (8.3 form)
   +----------+-----+-----+--------+--------+-------+--------+
   | name 8.3 | att | ... | time   | date   | clus  | size   |
   | REPORT~1 DOC| A|     |        |        | 0x0C3 | 40960  |
   +----------+-----+-----+--------+--------+-------+--------+
   Long names ("Quarterly Report Final.docx") are stored in PRECEDING
   pseudo-entries (attribute 0x0F) holding 13 UTF-16 chars each, plus a
   checksum of the 8.3 name to bind them together.

   FOLLOWING A FILE
     dirent says first cluster = 0x0C3
     FAT[0x0C3] = 0x0C4 -> FAT[0x0C4] = 0x0F1 -> FAT[0x0F1] = 0x0FFFFFFF (EOC)
     file occupies clusters 0x0C3, 0x0C4, 0x0F1

   WHY BIG VOLUMES GET BIG CLUSTERS
     FAT32, 4 KB clusters, 2 TB -> 536,870,912 entries x 4 B = 2 GB of FAT
     so tools pick 32 KB or 64 KB clusters instead:
       1,000,000 files x 2 KB each = 2 GB of content
       at 32 KB clusters           = 32 GB consumed  (94% wasted)

   exFAT's IMPROVEMENTS
     + 64-bit sizes (no 4 GB file limit)
     + a free-space BITMAP: allocation no longer scans the FAT
     + "no-FAT-chain" flag for contiguous files: read the extent directly
     - still no journal, still no permissions

# Formatting for interoperability.
sudo mkfs.vfat -F 32 -n PORTABLE /dev/sdb1        # FAT32: maximum compatibility
sudo mkfs.exfat -n BIGCARD /dev/sdb1              # exFAT: large files, modern devices
sudo mkfs.vfat -F 32 -s 8 /dev/sdb1               # 8 sectors/cluster = 4 KB clusters

# Inspecting.
sudo fsck.vfat -v /dev/sdb1 | head -20
#   Boot sector contents:
#   System ID "mkfs.fat"
#   Media byte 0xf8
#          512 bytes per logical sector
#        32768 bytes per cluster
#            2 FATs
sudo exfatlabel /dev/sdb1
sudo dumpexfat /dev/sdb1 2>/dev/null | head

# The 4 GB wall, demonstrated.
dd if=/dev/zero of=/mnt/usb/big.bin bs=1M count=5000
#   dd: error writing '/mnt/usb/big.bin': File too large
#   4096+0 records out                       <- stopped at exactly 4 GiB

# Internal fragmentation from large clusters.
for i in $(seq 2000); do dd if=/dev/urandom of=/mnt/usb/f$i bs=2k count=1 \
    status=none; done
du -sh --apparent-size /mnt/usb    # 3.9M   real content
du -sh /mnt/usb                    # 62M    allocated (32 KB clusters)

# Repair after an improper eject.
sudo fsck.vfat -a /dev/sdb1
#   Filesystem has 3 clusters marked in use but no corresponding file
#   Reclaiming unconnected clusters.
sudo fsck.exfat /dev/sdb1

# Mount options that fake the missing permission model.
sudo mount -o uid=1000,gid=1000,umask=022,utf8 /dev/sdb1 /mnt/usb
# uid/gid/umask are applied to EVERY file: the volume stores none of this.

# Cluster size, FAT size, and internal fragmentation: the FAT32 trade-off.
import math

def fat32_plan(volume_gb, cluster_kb, file_count, avg_file_kb):
    clusters   = (volume_gb * 1024**3) // (cluster_kb * 1024)
    fat_mb     = clusters * 4 / 1024**2                  # x2 for the mirror copy
    per_file   = math.ceil(avg_file_kb / cluster_kb) * cluster_kb
    allocated  = file_count * per_file / 1024**2         # MB
    actual     = file_count * avg_file_kb / 1024
    return clusters, fat_mb * 2, allocated, actual

print(f"{'cluster':>8}{'clusters':>14}{'FATs':>10}{'alloc':>11}{'waste':>9}")
for ck in (4, 8, 16, 32, 64):
    c, fat, alloc, actual = fat32_plan(volume_gb=256, cluster_kb=ck,
                                       file_count=200_000, avg_file_kb=3)
    print(f"{ck:>6} KB{c:>14,}{fat:>9,.0f}M{alloc:>10,.0f}M{1-actual/alloc:>8.0%}")
# Small clusters: a huge FAT that must be cached. Large clusters: huge waste.
# There is no good answer -- which is the real argument for exFAT or ext4.

# The 4 GB limit, in the field.
FAT32_MAX = 4 * 1024**3 - 1
for name, size in [("1080p 2h film", 8*1024**3), ("phone video 10min", 3*1024**3),
                   ("VM disk image", 40*1024**3), ("DSLR raw burst", 500*1024**2)]:
    print(f"{name:<20} {size/1024**3:>6.1f} GB  "
          f"{'FITS' if size <= FAT32_MAX else 'REFUSED by FAT32'}")

Key takeaways

• FAT persists because of universal interoperability, not technical merit: firmware, cameras, and embedded devices all read it.
• It is linked allocation with the chain pointers gathered into a table, plus a flat array of 32-byte directory entries.
• FAT32's hard 4 GB file limit and 8.3-name retrofit are its most visible flaws; it has no journal, no permissions, and O(n) directory lookup.
• The FAT grows with cluster count, so large volumes are forced into large clusters, producing severe internal fragmentation for small files.
• exFAT lifts the size limits and adds a free-space bitmap and a contiguous-file optimisation, but still has no journal and no permissions.
• Use FAT32 or exFAT only when a foreign device must read the media; use a journalled file system for anything you rely on.

🧪 Practice

1. Compute the FAT size and total internal fragmentation for a 128 GB FAT32 volume holding 50,000 files averaging 5 KB, at 4 KB and at 32 KB clusters.
2. Explain precisely what happens on a FAT32 volume if power is lost after the directory entry is written but before the FAT chain is updated, and what fsck.vfat will do about it.
3. Interview-style: "Why does the EFI System Partition have to be FAT32?" Hint: ask what software must read it, when it runs, and how much of a file system implementation can reasonably live in firmware.

NFS

Theory

The Network File System (Sun, 1984) answered a specific question: can a remote file system be made to look exactly like a local one, so that unmodified programs work over the network? The answer is "almost", and the places where it is only "almost" are the interesting part.

NFS sits under the VFS. A mounted NFS export appears as an ordinary directory; open, read, and write on it are dispatched by the VFS to the NFS client, which turns them into RPCs to the server. Applications need no changes.

The design's defining choice was statelessness in NFSv2 and v3. The server kept no record of who had what open; every request carried everything needed to serve it — a file handle (an opaque identifier, typically encoding device, inode number, and a generation count), an offset, and a length. The payoff is crash resilience: if the server reboots, clients simply retry and the operations succeed, because nothing was remembered that could be lost. This is why NFS clients block indefinitely on a hard mount rather than returning errors — from their point of view the server is merely slow.

Statelessness forced two consequences. Every operation must be idempotent, because a retried request may be a duplicate — which works for read and write at offset but not for create or remove, handled by duplicate-request caches and by tolerating some anomalies. And there is no server-side locking, so locking was a separate protocol (NLM), which was a persistent source of trouble.

The consistency model is the other place the illusion leaks. Local file systems give UNIX semantics: a write is immediately visible to every other opener. NFS gives close-to-open consistency: the client flushes on close() and revalidates on open(), so a reader that opens after a writer closes sees the new data — but two processes writing the same file concurrently on different clients get no guarantee at all. Client attribute caching (typically a few seconds) means even stat results can be stale. Code that is correct locally can be subtly wrong here, and the usual symptom is a lock file or a "is the job done" marker that two machines disagree about.

NFSv4 (2003, refined in 4.1 and 4.2) reworked this substantially:

• Stateful again, with leases and delegations: the server can delegate a file to a client, which may then cache aggressively and skip revalidation until the delegation is recalled.
• Integrated locking, so NLM is gone.
• Compound operations batching several calls into one round trip, which matters enormously over a WAN.
• One port (2049), making firewalling practical, and no more portmapper.
• Strong security via Kerberos (krb5, krb5i, krb5p) instead of trusting client-supplied UIDs — which is what sec=sys does, and it is exactly as weak as it sounds.
• Parallel NFS (pNFS) in 4.1, separating metadata from data servers so bandwidth scales.

The operational knobs that matter most: hard versus soft mounts (hard retries forever and preserves data integrity, soft returns errors and can corrupt applications that do not check them — use hard with intr), sync versus async exports (async acknowledges writes before they are durable, which is fast and loses data on server crash), and root_squash (map remote root to nobody, on by default for good reason).

Example

   NFS IN THE STACK

   client                                  server
   +------------------+                    +------------------+
   | application      |                    | local file system|
   +------------------+                    | (ext4 / ZFS)     |
   | VFS              |                    +------------------+
   +--------+---------+                    | NFS server (nfsd)|
   | ext4   | NFS     |                    +------------------+
   +--------+----+----+                    | RPC              |
                | RPC over TCP 2049        +--------+---------+
                +-----------------------------------+

   Identical system calls; the VFS routes by which file system owns the inode.

   CLOSE-TO-OPEN CONSISTENCY: THE TRAP

   client A                    client B
   open("f")                   
   write("new data")           open("f")
                               read() -> OLD data     (A has not closed)
   close()          <- flush
                               close(); open("f")
                               read() -> new data     (revalidated on open)

   Two writers on different clients, no locking: LAST CLOSE WINS,
   and the loser's writes are gone with no error reported anywhere.

   v3 STATELESS vs v4 STATEFUL

   v3: every request self-contained (handle, offset, length)
       server reboot -> client retries -> success, no recovery protocol
       locking is a SEPARATE protocol (NLM), and it shows
   v4: leases + delegations
       server grants a delegation -> client caches hard, no revalidation
       server recalls it when another client wants the file
       server reboot -> a grace period while clients reclaim state

   COMPOUND OPERATIONS (why v4 is faster over a WAN)
     v3: LOOKUP "a" | LOOKUP "b" | LOOKUP "c" | OPEN | READ   = 5 round trips
     v4: COMPOUND{ PUTFH, LOOKUP a, LOOKUP b, LOOKUP c, OPEN, READ } = 1
     At 80 ms RTT that is 400 ms versus 80 ms.

# --- server ---
sudo apt install nfs-kernel-server
cat /etc/exports
#   /srv/data  10.0.0.0/24(rw,sync,no_subtree_check,root_squash)
#   /srv/ro    10.0.0.0/24(ro,sync,all_squash,anonuid=65534)
#   rw/ro     : access mode
#   sync      : do not acknowledge a write until it is durable (slower, safe)
#   root_squash: remote root becomes 'nobody' -- keep this
sudo exportfs -ra && sudo exportfs -v
sudo systemctl restart nfs-server

# --- client ---
showmount -e nfs-server                       # what is exported (v3 style)
sudo mount -t nfs4 -o rw,hard,intr,rsize=1048576,wsize=1048576,vers=4.2 \
     nfs-server:/srv/data /mnt/data
# hard  : retry forever -- the application blocks but data is never lost
# soft  : return EIO after retries -- FAST FAILURE, and silent corruption in
#         applications that ignore write errors. Use hard unless you are sure.

# /etc/fstab
#   nfs-server:/srv/data /mnt/data nfs4 rw,hard,intr,_netdev,noatime 0 0

# --- observing and diagnosing ---
nfsstat -c                                    # client RPC counts by operation
mountstats /mnt/data | head -30               # per-operation latency
cat /proc/self/mountstats | grep -A8 'device nfs-server'
sudo nfsiostat 2                              # live throughput and latency

# The consistency model, made visible.
# terminal A:                          terminal B:
#   exec 3> /mnt/data/f                  cat /mnt/data/f     # old contents
#   echo hello >&3                       cat /mnt/data/f     # STILL old
#   exec 3>&-      # close               cat /mnt/data/f     # now "hello"

# Kerberos instead of trusting client UIDs.
sudo mount -t nfs4 -o sec=krb5p nfs-server:/srv/data /mnt/data
#   sec=sys  : the client TELLS the server its UID. Anyone with root on any
#              client can become any user. Only acceptable on a trusted LAN.
#   sec=krb5 : authentication;  krb5i: + integrity;  krb5p: + encryption

# Tuning that actually matters.
#   rsize/wsize : 1 MB on a modern LAN (default negotiation is often smaller)
#   nconnect=4  : multiple TCP connections, big win on 10 GbE
#   actimeo     : attribute cache lifetime; lower = fresher stat, more RPCs

# Why compound operations dominate over a WAN, and what caching buys.
RTT_MS = {"LAN 0.2ms": 0.2, "metro 5ms": 5, "WAN 80ms": 80}

def v3_open_read(rtt, path_depth):
    return (path_depth + 2) * rtt          # a LOOKUP per component, + OPEN + READ

def v4_open_read(rtt, path_depth):
    return 1 * rtt                         # all of it in one COMPOUND

print(f"{'link':<12}{'v3 (depth 5)':>16}{'v4 compound':>14}{'speedup':>10}")
for label, rtt in RTT_MS.items():
    a, b = v3_open_read(rtt, 5), v4_open_read(rtt, 5)
    print(f"{label:<12}{a:>14.1f}ms{b:>12.1f}ms{a/b:>9.1f}x")

# Attribute caching: freshness vs RPC volume.
STATS_PER_SEC = 500
for actimeo in (0, 1, 3, 30):
    rpcs = STATS_PER_SEC if actimeo == 0 else STATS_PER_SEC / (actimeo * STATS_PER_SEC)
    staleness = actimeo
    print(f"actimeo={actimeo:>3}s -> ~{rpcs:>8.2f} GETATTR RPC/s, "
          f"up to {staleness}s stale")
# actimeo=0 gives local-like freshness and floods the server. The default
# (3-60s adaptive) is a compromise, and the reason `ls -l` can lie briefly.

Key takeaways

• NFS sits under the VFS, so remote files use the same system calls as local ones and applications need no changes.
• NFSv2/v3 were stateless: every request self-contained, so a server reboot needs no recovery protocol, at the cost of requiring idempotent operations and a separate locking protocol.
• The consistency model is close-to-open, not UNIX semantics: concurrent writers on different clients get no guarantee, and cached attributes can be stale for seconds.
• NFSv4 is stateful with leases and delegations, integrated locking, compound operations, a single port, and Kerberos security.
• Compound operations collapse a path lookup plus open plus read into one round trip, which dominates performance over high-latency links.
• hard mounts block but never lose data; soft mounts return errors that many applications ignore. sec=sys trusts client-supplied UIDs entirely, and root_squash should stay on.

🧪 Practice

1. Describe a concrete sequence of operations on two NFS clients that produces a lost update, and explain why no error is reported.
2. Compare hard and soft mounts: give one scenario where each is the right choice, and name the failure mode of the wrong one.
3. Interview-style: "A build over NFS takes 6 minutes locally and 50 minutes on a remote site with 80 ms latency, though bandwidth is ample. What do you change?" Hint: count round trips rather than bytes, and consider what protocol version and mount options affect that count.

Distributed File Systems

Theory

NFS puts one server's file system on the network. A distributed file system goes further: spread data across many machines so that capacity, bandwidth, and fault tolerance all scale with the number of nodes, and no single machine's failure loses anything. This is the storage layer under essentially every large-scale system.

The constraints are different from anything earlier in this chapter, because now the network is part of the file system, and networks partition. The CAP theorem applies directly: when a partition occurs, a system must choose between remaining available and remaining consistent. Different systems choose differently, and knowing which choice a system made tells you most of what you need to know about it.

Three architectural patterns recur:

Central metadata, distributed data (GFS, HDFS). One metadata server holds the namespace and the block map; data lives on many chunk servers, replicated (classically three ways). A client asks the metadata server where a block is, then reads it directly from a data node, so the metadata server never touches bulk data and does not become a bandwidth bottleneck. It does remain a single point of failure and a limit on file count — HDFS's NameNode keeps the whole namespace in RAM, which is why HDFS is hostile to millions of small files. This design targets huge files read sequentially, and it deliberately gives up POSIX semantics (HDFS files are write-once, append-only).

Fully distributed metadata (Ceph, GlusterFS). No central lookup. Ceph's CRUSH algorithm computes an object's location from its name and the cluster map, so clients contact the right node directly with no metadata round trip, and adding or removing nodes moves only the data that must move. Ceph layers a block interface (RBD), an object interface (RGW), and a POSIX file system (CephFS, which does use metadata servers) over one object store (RADOS).

Object stores (S3, Azure Blob, GCS). Give up the file system model entirely: flat namespace, whole-object PUT/GET, no partial writes, no rename (a "rename" is a copy plus a delete), eventual or strong consistency depending on the service. The simplification is what allows near-unlimited scale and the durability figures these services quote. Most "cloud-native" data systems target this model directly rather than pretending it is a file system.

Two problems cut across all of them:

Replication versus erasure coding. Three-way replication costs 200% overhead and makes recovery a simple copy. Erasure coding (say 10 data + 4 parity) costs 40% overhead for better fault tolerance, but reconstruction reads from many nodes and burns CPU and network. The usual arrangement is replication for hot data and erasure coding for cold.

Consistency. Strong consistency requires coordination (Paxos or Raft for metadata), which costs latency and stalls during partitions. Eventual consistency is faster and stays available but makes read-after-write a property the application must handle. Many systems split the difference: strongly consistent metadata, eventually consistent data.

Example

   THREE ARCHITECTURES

   (1) CENTRAL METADATA (GFS / HDFS)
       client ---(1) "where is /logs/2026.gz block 3?"---> NameNode
              <--(2) "nodes 7, 19, 44"--------------------
              ---(3) read the bytes directly-------------> DataNode 7
       metadata server never carries bulk data; it IS a SPOF and
       an upper bound on file count (namespace lives in RAM).

   (2) COMPUTED PLACEMENT (Ceph / CRUSH)
       client: location = CRUSH(object_name, cluster_map)
               -> contacts the OSD directly.  ZERO metadata round trips.
       adding a node changes the map -> only the affected objects move.

   (3) OBJECT STORE (S3)
       PUT /bucket/key   (whole object)     no partial writes
       GET /bucket/key   (whole object)     no rename: copy + delete
       flat namespace; "directories" are a prefix convention

   REPLICATION vs ERASURE CODING (10 TB of data)

                       raw stored   overhead   survives   recovery cost
   3x replication         30 TB       200%     2 failures  copy 1 replica
   EC 10+4                14 TB        40%     4 failures  read 10 shards,
                                                            recompute
   EC 6+3                 15 TB        50%     3 failures  read 6 shards

   CAP IN PRACTICE: WHAT HAPPENS DURING A PARTITION

   CP (HDFS NameNode, Ceph mons, etcd):
       minority side REFUSES writes -> consistent, unavailable
   AP (S3 historically, Dynamo-style):
       both sides accept writes -> available, reconcile later
   The choice is not a quality ranking; it is a statement about which
   failure your application can tolerate.

# --- HDFS: central metadata, huge files, write-once ---
hdfs dfs -put bigfile.gz /data/                 # split into 128 MB blocks, 3x replicated
hdfs fsck /data/bigfile.gz -files -blocks -locations
#   /data/bigfile.gz 5368709120 bytes, 40 block(s):  OK
#   0. BP-...:blk_1073741900 len=134217728 Live_repl=3 [DN 10.0.0.7, 10.0.0.19, ...]
hdfs dfsadmin -report                           # per-DataNode capacity and health
hdfs dfs -setrep -w 2 /data/cold/               # reduce replication for cold data

# --- Ceph: computed placement, unified object/block/file ---
ceph -s                                         # cluster health, PG states
ceph osd tree                                   # the CRUSH hierarchy
ceph osd map mypool myobject
#   osdmap e128 pool 'mypool' object 'myobject' -> pg 3.7a -> up [7,19,44]
#   The client computes this too -- no lookup was needed.
ceph osd pool create cold 128 128 erasure ec-10-4-profile
sudo mount -t ceph mon1,mon2,mon3:/ /mnt/cephfs -o name=admin,secretfile=/etc/ceph/key

# --- Object storage: a different model, not a file system ---
aws s3 cp bigfile.gz s3://bucket/data/          # whole-object PUT (multipart internally)
aws s3 mv s3://bucket/a s3://bucket/b           # a COPY plus a DELETE, not a rename
aws s3api put-object-lock-configuration ...     # immutability: ransomware defence

# Mounting an object store as a file system: know what you are giving up.
s3fs bucket /mnt/s3 -o iam_role=auto
# Every "partial write" becomes read-whole-object, modify, write-whole-object.
# rename of a large object copies it. Use the object API where you can.

# --- GlusterFS ---
sudo gluster volume create data replica 3 node{1,2,3}:/bricks/data
sudo gluster volume info data
sudo mount -t glusterfs node1:/data /mnt/gluster

# Durability and cost: replication vs erasure coding, with real arithmetic.
from math import comb

def survives(n_total, n_needed, node_failure_prob):
    """P(at least n_needed of n_total nodes survive)."""
    p_up = 1 - node_failure_prob
    return sum(comb(n_total, k) * p_up**k * (1-p_up)**(n_total-k)
               for k in range(n_needed, n_total + 1))

AFR = 0.02                    # 2% annual node failure probability
DATA_TB = 10

schemes = [("3x replication", 3, 1), ("EC 10+4", 14, 10), ("EC 6+3", 9, 6)]
print(f"{'scheme':<16}{'raw TB':>8}{'overhead':>10}{'annual durability':>20}")
for name, total, needed in schemes:
    raw = DATA_TB * total / needed
    durability = survives(total, needed, AFR)
    print(f"{name:<16}{raw:>8.1f}{(raw/DATA_TB - 1):>9.0%}{durability:>20.6%}")

# Recovery traffic: what rebuilding one failed node costs the network.
NODE_TB = 16
print(f"\nrebuilding one failed {NODE_TB} TB node:")
print(f"  3x replication : read {NODE_TB} TB from ONE surviving replica set")
print(f"  EC 10+4        : read {NODE_TB * 10} TB from 10 nodes, "
      f"recompute, write {NODE_TB} TB")
# EC saves capacity and costs recovery bandwidth and CPU. That trade is the
# reason hot tiers replicate and cold tiers erasure-code.

Key takeaways

• Distributed file systems scale capacity, bandwidth, and fault tolerance across many nodes, and must make an explicit CAP choice because networks partition.
• Central-metadata designs (GFS, HDFS) keep the metadata server out of the data path but make it a single point of failure and cap the file count by its memory.
• Computed-placement designs (Ceph's CRUSH) remove the metadata lookup entirely and limit data movement when the cluster changes.
• Object stores abandon file semantics — no partial writes, no rename — in exchange for near-unlimited scale, and most cloud-native systems target that model directly.
• Replication costs capacity and recovers cheaply; erasure coding saves capacity and costs recovery bandwidth and CPU, which is why hot and cold tiers usually differ.
• Many systems keep metadata strongly consistent (via Raft or Paxos) while letting data be eventually consistent, so applications must still handle read-after-write themselves.

🧪 Practice

1. Compute the raw capacity and storage overhead needed for 100 TB of data under 3x replication, EC 10+4, and EC 6+3, and state which you would choose for an archive and which for a hot working set.
2. Explain why HDFS performs badly with 50 million 10 KB files but well with 50 thousand 10 GB files, naming the specific resource that runs out.
3. Interview-style: "An application that works on NFS breaks when moved to an S3-backed mount. Name three semantic differences that could be responsible." Hint: think about operations a POSIX file system guarantees cheaply — in-place partial writes, atomic rename, and immediate read-after-write visibility.

---

<a id="11-inputoutput-systems"></a>