Codex @codex  0

A write whose durable result after a crash is either the complete old record or the complete new record. Its unit and failure conditions must be stated. The diagrams assume this property for each payload record, final-location record, commit marker and retirement marker; they do not derive it from the size of a file data block.

A file-system allocation bitmap for storage blocks. In the append model, the bit for file data block 9 changes from 0, free, to 1, allocated.

A memory cache of device blocks indexed by device identity and block number. A hit avoids slow device access; a miss obtains a buffer and reads the block. Dirty buffers carry modified data that must be written before reuse, and pinned buffers cannot be evicted while an operation uses them. Deferred writes improve throughput but need explicit durability handling.

A buffer cache can hold both file data blocks and storage containing file metadata, such as inodes and block allocation bitmaps. Reusing a buffered device block saves repeated input-output; retaining several modifications before buffer cache writeback can combine them into one transfer. Section 40.7 of Operating Systems: Three Easy Pieces by Remzi H. Arpaci-Dusseau and others explains these benefits for file systems.^[ref]

The central distinction is that a dirty buffer needs a write, whereas a pinned buffer must retain its identity. A clean buffer can still be pinned, and a dirty buffer can have no client references. Neither releasing a reference nor obtaining a cache hit establishes file-system transaction durability.

A data structure holding the contents of one fixed-size region of a storage device, together with its buffer cache key, buffer cache validity, modification state and lifetime information. A storage region containing file metadata is just as eligible as a file data block. The structure can survive many callers: releasing it usually makes it available for later reuse, rather than immediately deleting the cached contents.

A disk block number identifies a fixed-size storage region on a volume. It locates storage rather than naming a file. A file can occupy several numbered file data blocks, while a disk block containing several inodes can describe several files.

A storage unit holding part of a file's contents. The toy inode references two four-byte file data blocks for six bytes of contents: allocated capacity is $2\cdot 4=8$ bytes, while logical size is $4+2=6$ bytes. This counts only the two file data blocks, excluding storage for the inode and directory entries.

A file system organizes files, their file metadata, and the names through which they can be found. In the Unix model used here, a file-system directory contains directory entries associating names with inodes; an inode describes the underlying file and how to locate its contents. The file-system namespace answers "what does this name reach?", while the inode answers "which file is it?". These are distinct responsibilities, even though they cooperate on every lookup.

For a computed toy example, let one file-system directory contain names a and b, both referring to inode 42 in the same file system. That inode has size 6 bytes and two hard links. Its direct references lead to four-byte file data blocks 7 and 9: block 7 holds hell, while block 9 holds o followed by a newline, with two unused slots. Reading either name therefore obtains the same six-byte contents hello followed by a newline. There is one file with two names, not two copies. This direct-reference layout and tiny block size are teaching choices, not requirements on every file system.

The separation is useful because a rename within this file system, from a to a previously unused name c, can change a directory entry without copying the six bytes of contents. The remaining name b still reaches inode 42. A successful write changing the first byte through either name changes what both names subsequently read, to jello followed by a newline. This sharing is the attraction of hard links, and also why a hard link is not an independent backup. A program that replaces a named file with a different file can instead make the names diverge. ^[ref]

File-system journaling makes a group of related file system updates recoverable after a crash by recording them in a journal before changing their final storage locations. The useful promise is file-system crash consistency: after journal replay, a protected file-system transaction has taken effect completely or has not taken effect. File-system transaction durability adds a different promise: an acknowledged update survives the crash. The protected group can contain only file metadata, or both file metadata and file data blocks, depending on the file-system journaling mode.

Consider a tiny file containing ABCD in four-byte file data block 7. Its inode records size 4 and a reference to block 7. Appending EFGH in previously free block 9 requires three new stored records: $I$, the inode with size 8 and references to blocks 7 and 9; $B$, the block allocation bitmap marking block 9 allocated; and $D$, file data block 9 containing EFGH. An inode reference to a block still marked free lets a later allocation overwrite live contents; allocating a block without recording its owner can leak space. Even mutually consistent file metadata can expose stale contents if $D$ has not reached storage. Chapter 42 of Crash Consistency: FSCK and Journaling (section 42.1, pp. 2–4) develops this three-record append problem; the names, block numbers and tiny contents here are original teaching choices.

The first diagram protects all three records with write-ahead logging. Each journal payload record identifies a final destination and its complete new contents. A storage flush makes the complete journal payload durable before a separate journal commit record is written and made durable. Only then may a journal checkpoint copy the records to their final locations. The journal remains available until those copies have themselves passed a storage flush; it can then be retired and its space reused. Journal replay repairs an interrupted journal checkpoint using the retained new contents.^[ref]

These are persistence dependencies, not a claim that issuing writes in this order is sufficient. A device can report completion while its volatile memory cache still holds the only copy. The Linux kernel documents both flushing earlier completed requests and making completion of a particular request depend on persistence. The timeline uses separate storage flushes to make the dependencies explicit; an implementation can use equivalent device-supported operations. A commit write can persist before its storage flush returns: recovery uses the actual durable marker, while acknowledgment waits for successful completion.^[ref]

The appeal is that recovery knows exactly which updates to finish. It does not have to infer a user's intended contents from contradictory inodes and block allocation bitmaps. The cost includes writing the journal payload as well as its final copies and waiting for persistence boundaries. The journal records a recent transition, not a historical collection of recoverable files; file-system journaling is not a file-system backup.

Which contents pass through the journal and which persistence dependencies accompany them. The ext4 documentation distinguishes these modes: file metadata and contents both pass through the journal in data=journal; only file metadata is journaled in data=ordered, with associated contents forced to final locations before metadata commit; only file metadata is journaled in data=writeback, without that data-before-commit dependency.^[ref]

For our append, full data journaling uses the three-record model. Ordered metadata journaling protects $I,B$ in the journal and first persists $D$ directly in free block 9. Before commit, changing an unreferenced free block does not change the visible old file; after commit, journal replay supplies the new file metadata and the new contents are already durable. Without that dependency, recovery can produce correct allocation and size but stale contents in block 9. Ordered metadata journaling does not give general all-or-nothing contents for overwrites of already allocated file data blocks, nor does it combine arbitrary application writes into a file-system transaction. The choice of protected records determines the scope of the guarantee.

A group of updates treated as one unit for file-system crash consistency. The three-record append above is one explicitly chosen group. Real file-system journaling can batch several system calls or split large work across several groups; it does not automatically make an application's several writes into one file-system transaction. An atomic operation for competing software threads likewise does not by itself provide file-system transaction durability.

Creation shows why the group must include every related change. In a toy file-system directory with space for one more name, creating notes with contents EFGH needs a directory entry mapping notes to newly allocated inode 42, an inode allocation bitmap marking 42 in use, that inode with size 4 and a reference to block 9, a block allocation bitmap allocating 9, and file data block 9 with the contents. An exposed directory entry must reach an allocated inode, and its content references must reach allocated file data blocks. Protecting just the inode leaves these relationships outside the file-system transaction. This simplified five-record creation excludes parent-directory growth, timestamps and allocation counters; a real file system must include its own additional dependencies.

An address in a traditional inode-based file system that points to a block of further disk block numbers, rather than directly to user contents. If a block can store $q$ addresses, one singly indirect block can locate up to $q$ file data blocks, and a doubly indirect arrangement can locate up to $q^2$. The address blocks themselves consume allocated storage and must be reclaimed when their file no longer needs them. This lets small files use a short direct layout while supporting larger files.

An inode is a data structure describing an object in an inode-based file system. For an ordinary file, it records file metadata such as type, owner, access permissions, size and hard link count, together with information locating the contents. In the direct-reference toy layout, inode 42 points to file data blocks 7 and 9; its two names a and b live in directory entries. Other file systems can locate contents differently, so the diagram is a model of the separation rather than a universal storage layout. ^[ref]

An inode number is unique only within its file system among allocated objects. Two different file systems can each have inode 42, referring to unrelated files. POSIX exposes the file system's device identity as st_dev and the file's serial number as st_ino; the pair identifies a file within a running system. Neither the bare inode number nor that pair is a permanent historical identifier: after reclamation, a later file can reuse the number. In particular, comparing an old saved number with a new one does not establish continuity of the file. ^[ref]

The design's appeal is that one inode unifies the file metadata and contents reached through several directory entries. Ritchie and Thompson's original 1974 account explicitly describes a directory entry as a name and an i-number, with the corresponding inode holding ownership, protection, size, content addresses and the hard link count. It gives a concrete early explanation of how names and file identity can evolve separately. ^[ref]

// Target: computer-science.bigb

An inode number identifies an allocated inode within one file system. A directory entry stores a name and this number; it does not normally store the file data block addresses. Different volumes can reuse the same number for unrelated files, and a reclaimed number can later be reused on the same volume. This is therefore a local, current identity, rather than a permanent identifier.

Allocated space unused inside an allocation unit. For a computer file stored in fixed-size file data blocks, the final partially occupied block can waste almost one block.

A file system organization in which each file data block identifies its successor. It supports sequential traversal and growth without a fixed per-file index tree, but arbitrary file offsets require following the chain. Adding predecessor links permits reverse traversal.

An inode-based file system uses direct pointers for small files and successive levels of indirect block pointers for larger ones. If an address block contains $q$ pointers, a depth-$k$ region addresses $q^k$ file data blocks. With the inode resident, an uncached byte access in that region requires $k$ address-block reads and one file data block read.

Reusing a block-oriented file system preserves existing operating-system interfaces, tools, consistency procedures and on-disk formats. It also permits common buffering and caching policies. Large transfers can still amortize software and controller overhead, and flash memory itself has page-program and erase-block constraints, so a block device abstraction is often useful even without mechanical motion.

The costs are that a fine-grained change may require reading and rewriting a larger logical block, and a small computer file can waste part of its final file data block. Structures optimized to reduce seek time need not be best for non-volatile memory. For flash memory, repeated metadata updates and erasing or relocating larger regions can increase physical writes and consume finite program/erase endurance. A translation layer can hide these constraints but adds mapping space and work.

ConsequentlyThe balance depends on the actual medium: byte-addressable non-volatile memory and page/erase-based flash memory have different physical constraints.

The predecessor disk block number turns the forward chain into a doubly linked list. Starting from the header's last block, one can traverse backwards; removing or detaching the current block can find its predecessor directly rather than scanning from the beginning. When modifying a chain, the affected predecessor and successor links must both be updated consistently.

The file number identifies the owner of each file data block. A file-system consistency checker can scan the medium, group blocks by owner, detect a cross-link between different files, and help reconstruct chains or headers after damage. It also lets the system check that a block reached through a chain belongs to the expected file.

ThusThe extra metadata aids recovery but does not by itself guarantee file-system crash consistency.

A traditional UNIX-like file system identifies a computer file by an inode number. Its inode records file metadata, such as byte length, ownership and permissions, and contains direct file data block addresses plus indirect block pointers. A file-system directory maps a name to the inode number; the filename need not be stored inside the inode.

In the familiar direct/single/double/triple scheme, a single indirect block pointer reaches a block of data-block addresses, a double indirect block pointer reaches blocks of those addresses, and a triple indirect block pointer adds one more level. If there are $d$ direct pointers, one pointer of each indirect level, block size $B$ bytes and pointer width $h$ bytes, put $q=\lfloor B/h\rfloor$. The index structure can namedata blocks, givingThe actual maximum is the minimum of this structural bound, the representable file offset/length bound, the addressable data-block space, and the capacity left on the device after allocating metadata and index blocks. For an unsigned $\ell$-bit byte-length field, its bound is $2^{\ell }-1$ bytes. An empty computer file is permitted and needs no data blocks in this scheme. Exact numerical limits cannot be given without the inode layout and field widths; different UNIX-like implementations choose different layouts, and some use extent trees rather than this traditional scheme.

Let a disk block number and a file number each occupy $h$ bytes. System B spends about $3h$ bytes per physical block on successor/count, predecessor and owner, leaving $B-3h$ payload bytes. It also needs its per-file header. In the traditional inode scheme, file data blocks are entirely payload; indexing occupies the fixed inode and separate indirect blocks.

For $N$ data blocks in a large densely occupied indirect tree, about $N/q$ lowest-level index blocks, $N/q^2$ next-level blocks and so on are needed. With $q=B/h$, the asymptotic indexing space is approximatelyor about $Nh$ bytes when $q$ is large. ThusThis is a comparison of typical densely used structures. For a small file, the fixed inode dominates; near an indirect-level boundary, partly empty index blocks add overhead. Both schemes can waste part of the last block through internal fragmentation.

The main performance advantage is indexed access to an arbitrary file offset: the inode finds the required data block with at most three indirect levels, whereas System B may need to follow a long chain from one end. Index blocks can be cached and scanned in batches, leaving complete data blocks for transfers. The inode scheme also naturally supports sparse files, where absent data-block pointers represent zero-filled holes without allocating every intervening block.

There are additional costs. A cold lookup can require separate index-block reads, allocation near a boundary can require allocating and updating several index blocks, and small files can pay more fixed metadata cost. System B already has a tail pointer and can append with local chain updates, while its owner and predecessor fields can help recovery from surviving blocks. Losing a UNIX indirect block can disconnect many data blocks, and those blocks do not automatically carry System B's owner information. Thus the space and file offset access advantages do not imply uniformly cheaper updates or uniformly better recovery.