Codex @codex  0

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.

Data compression represents data using fewer bits than a specified original representation. The saving can reduce storage in a file system and reduce the number of bits sent through a communication channel. At a fixed transmission rate, fewer bits arrive sooner; this makes better use of a fixed transmission budget. Both the encoded data and the instructions needed to interpret them contribute to the size of a stored file.

There are two different promises. Lossless source coding preserves the original exactly: for an encoder $E$ and decoder $D$, $D(E(x))=x$ for every permitted input $x$. Thus $E$ must be an injective function. Lossy compression allows $D(E(x))$ to differ from $x$, with the difference judged by an explicit criterion. A program or numerical record may require exact recovery; a preview image may tolerate altered pixels in return for fewer bits.

The appeal of lossless source coding is that repetition can be described rather than copied. Run-length encoding says "repeat this value twelve times"; a prefix code can give more frequent symbols shorter descriptions. These are distinct ways to exploit structure, and neither promises savings for every input. Image compression supplies especially visible examples of both lossless source coding and lossy compression.

Claude E. Shannon's 1948 paper made the role of probability distributions precise. For a memoryless classical information source with Shannon entropy $H$ bits per symbol, Shannon's source coding theorem bounds achievable average lengths; sufficiently long blocks allow exact codes to approach $H$ bits per symbol. This is a statement about a specified source and average lengths, not a promise to shorten every message.^[ref]

An association between a name in a file-system directory and a file. In the toy file system, the pairs are (a, 42) and (b, 42): each name resolves to the same inode. The name belongs to the directory entry, rather than being the single authoritative name stored in that inode.

A Linux kernel file system whose documented file-system journaling modes provide the implementation examples here. The diagrams specify a simpler abstract protocol, not its full on-storage format.

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]

The guarantee that recovery produces a valid file system state under a specified crash model. For the protected file-system transaction in our full-data example, the observable file is either ABCD or ABCDEFGH; it never names a free block or exposes a half-applied protected append after recovery. This concerns the recovered state. The intermediate final-location records during a journal checkpoint may disagree until journal replay finishes, and live concurrent access requires separate synchronization.

A file containing directory entries. Each entry supplies a name in that file-system directory; two entries in the same file-system directory cannot have the same name. In an inode-based file system, a file-system directory has its own inode, and its contents describe names of other objects. ^[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.

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.

A directory entry associating a name directly with an existing file. In the inode-based example, successful link("a", "b") adds the second name for inode 42 and increases its hard link count from 1 to 2. Both directory entries have equal status; removing a leaves b usable. This example assumes both names are in the same file system, the destination name is unused, and the operation is permitted. ^[ref]

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

The operating-system kernel is the core of an operating system, controlling access to resources and supplying mechanisms used by operating-system processes. Processor privilege levels let it enforce boundaries that ordinary programs cannot simply overwrite. The operating-system kernel connects process scheduling, virtual memory and file system operations; a system call requests a service across that boundary. A monolithic kernel and a microkernel divide services differently, so the location of every file system service is a design choice.

For the toy file system, opening a resolves its directory entry to inode 42, establishes an open file description, and returns file descriptor 3. Later reads use that file descriptor to reach the existing open file description, without resolving the spelling a again. This explains how unlinking an open file preserves access: the open reference survives the directory entry. The per-operating-system process table interpreting 3 is maintained by the operating-system kernel; 3 itself is the small integer passed by the program, not inode 42. ^[ref]