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.

Let $A,B,C$ be three distinct buffer cache keys on one device. Use two initially empty slots, LRU replacement refreshed at each completed request, and synchronous successful buffer cache writeback of a dirty victim. Each request acquires its target, finishes any fill, reads or partially modifies it, and releases the client reference. An explicit pin on $A$ remains after request 2 through request 7; pin and unpin do not refresh recency. No other references, invalidations, background writes or durability operations occur. Initial backing contents are represented by the integers $A=10,B=20,C=30$; partial writes change the tracked value of $A$ to 11 and then 12 while preserving the unshown remainder.

The eight data requests are read $A$, write $A=11$, read $B$, read $C$, read $A$, write $A=12$, read $C$, and read $B$ after unpinning $A$. They yield four cache hits, four cache misses, four device reads and one device write. The pin and unpin are lifetime operations, excluded from the data-request count. At the read of $C$, $A$ is older than $B$ but pinned, so the clean buffer for $B$ is evicted instead. Reading $A$ then returns 11 without device access even though its backing value is still 10. The second write supersedes 11; reading $C$ makes $A$ the older entry again. After unpinning, the final read of $B$ writes back 12 before evicting $A$. After that request, backing $A$ contains 12, while the resident keys are $C,B$.

This example exposes the value of retaining modified contents: a cache hit can return a newer value than a device read would. It also exposes the cost of reference counting constraints: a pinned older entry forces a different victim. An independent capacity sweep gives two cache hits, six cache misses and two device writes with one slot and no pin, but three cache hits, five cache misses and two device writes with two slots and no pin. With one slot and the stipulated pin, the read of $B$ cannot proceed. With three slots, both pin choices give five cache hits, three cache misses and no eviction-triggered write; $A$ remains dirty with value 12, so the absence of a device write does not establish file-system transaction durability.

The identity used to find a buffered device block. In the fixed-block-size model, $d$ identifies the device and $b$ its block number; $(d_1,7)$ and $(d_2,7)$ are different keys if $d_1\ne d_2$. A file's pathname or its logical block offset alone is insufficient for this device-indexed model. Interfaces supporting different transfer sizes need to specify the size and overlap rules too.

Maintain at most one logical buffered device block for each buffer cache key within this buffer cache. Otherwise two callers could modify different copies and later overwrite one another's changes. Lookup and reservation must therefore be coordinated by synchronization: even before contents are ready, a reserved key directs a second caller to the same structure. This invariant concerns the participating cache, not every copy of those bytes anywhere in the machine.

A store of selected information kept for faster reuse. A translation lookaside buffer is a memory cache of address translations; a buffer cache instead holds device-block contents.

For a data memory cache, the useful bargain is to keep a small selection of computer memory close to the CPU. A cache hit serves a read from that selection; a cache miss requires obtaining the contents elsewhere. Temporal locality helps a retained cache block serve repeated reads, and spatial locality helps one transferred cache line serve neighbouring bytes. Placement, capacity and LRU replacement determine whether that opportunity survives until the next read. ^[ref]

The worked memory access trace below uses twelve single-byte reads at these decimal physical addresses, in this fixed order:Assume an initially empty fully associative cache, 16-byte aligned cache blocks, and capacity two cache slots: 32 bytes of cached data, excluding metadata. Use exact LRU replacement, refreshing recency on every read, including cache hits. Every cache miss fetches its requested cache line completely before the next read; only a full memory cache needs an eviction. There are no writes, fetching ahead of requests, external invalidations, or overlapping reads. All addresses denote ordinary cacheable computer memory, and address translation is outside this model. These are deliberately synthetic assumptions, not specifications of a particular CPU.

This makes the outcome reproducible from the memory access trace, rather than from an informal impression that data are “nearby” or “recent”. The cache line geometry below identifies the requested unit; fully associative cache enumerates the resulting states; average memory access time translates the counts into a simple timing calculation.

An acknowledged file-system transaction remains recoverable after a crash under the stated storage assumptions. In the full-data timeline, durable journal payload and a durable journal commit record suffice even before the journal checkpoint. A crash before durable commit can lose the append while still preserving file-system crash consistency. A successful ordinary write may only have reached a buffer cache; an application requiring persistence must use its documented interface and check errors. On Linux kernel-based systems, fsync on a file descriptor persists the associated file contents and file metadata, but persisting a newly created name also requires fsync on the containing file-system directory.^[ref]

Evict the least recently accessed eligible item. Exact recency tracking on every memory reference can be expensive, whereas accesses to a buffer cache already pass through software. Recency captures temporal locality but a long scan can evict frequently reused items before their next use.

For page replacement, update recency on hits as well as misses; evict only when a miss requires a page frame and all eligible page frames are occupied. The four-page cycle in memory thrashing shows how exact LRU replacement behaves at capacities three and four.^[ref]

The LRU stack property compares different capacities on one fixed page-reference trace; it does not say that LRU replacement always beats FIFO page replacement. On the displayed sequence, three-page frame LRU replacement has ten misses, versus nine for FIFO page replacement, while four-page frame LRU replacement has only eight.

Caching file contents in units based on memory pages, commonly by a file mapping and an offset, rather than necessarily by the device-and-block buffer cache key used above. A file's offset must be mapped to storage before device access; the two naming systems describe different layers. How page cache and buffer cache storage relate depends on the operating system and file system. A separate duplicate copy at each layer is not a universal requirement.

For the Linux kernel interfaces documented in Buffer Heads by The kernel development community, per-block state can be attached to larger cached memory units called Linux folios; mark_buffer_dirty also marks the backing page dirty in the page cache. The documented reclamation checks include dirty state, pending buffer cache writeback and elevated reference counts. That documentation deprecates Linux buffer heads for new file systems in favour of iomap. These are platform-specific interfaces, not a definition that every page cache has Linux buffer heads or that every buffer cache has its own disjoint allocation. ^[ref]

A buffer cache keeps copies of device blocks in main memory, indexed by device identity and block number. It reduces expensive repeated device reads and can combine several modifications into one write. It also gives software a controlled place to hold data while requests are in progress.

On a read, the operating system looks up the block. A valid cached copy gives a hit and supplies the data; a miss reserves an eligible buffer, writes its old contents first if dirty, issues the device read, and marks the new contents valid when the transfer completes. A write modifies the buffer and marks it dirty. Under a write-back policy, a later flush or eviction sends it to the device; under write-through, completion also waits for the required device write. Dirty state differs from “currently in use”: a pinned or locked buffer cannot simply be reused while a request depends on it.

A buffer cache needs synchronization for concurrent readers, writers and in-flight transfers, and should avoid inconsistent independent copies of the same block. Explicit flushes and ordering are needed when durable storage is required; caching alone does not guarantee that an acknowledged in-memory update survives a crash. Replacement chooses among eligible buffers, preserving dirty data before reuse.

Use LRU replacement, or a modest recency-based approximation, for eligible buffer-cache entries. Unlike individual memory accesses, buffer cache lookups already pass through operating system code. Updating an LRU replacement list on each lookup is therefore practical: remove the accessed entry from its old position and put it at the most-recent end; choose the oldest unpinned entry as victim. A hash lookup plus a doubly linked recency list makes this bookkeeping constant time.

Good temporal locality favors retaining recently used blocks. FIFO page replacement's arrival-only criterion can evict a block used moments ago. CLOCK page replacement can save bookkeeping, but the difficulty of observing arbitrary memory references that motivates it is absent for software-mediated block accesses. Dirty victims require write-back, so a policy can favor an old clean buffer or arrange background cleaning without discarding recent hot data. A long one-pass scan can pollute pure LRU replacement; scan-resistant variants are useful refinements rather than a reason to ignore recency altogether.

The logical file data block index and within-block file offset areDirect pointers cover logical indices 0 through 9. The singly indirect region covers 10 through $10+512-1=521$. The requested file data block therefore lies in the doubly indirect region, at relative indexFollow the doubly indirect block pointer in the inode, read its top address block and select entry 14, read that second address block and select entry 511, then read the resulting file data block and take byte offset 1568. These entry indices are zero-based.This assumes a resident inode and no useful buffer cache entries for the three blocks; an uncached inode adds one read. Under one-based byte numbering the last offset is 1567, without changing either address-block index or the read count.

With a resident inode, the deepest allowed path uses two address blocks and one file data block, so every byte through the end of the doubly indirect region meets the three-read bound. There are ten directly addressed file data blocks, 512 singly addressed ones and $512^2$ doubly addressed ones. Therefore the largest contiguous file satisfying this bound isThe next byte requires the triply indirect region, with three address-block reads and a fourth read for the file data block.

The resident-inode convention is essential. If the question's three reads must also include fetching a previously uncached inode, only two further reads remain; the maximum is thenNeither figure includes arbitrary pathname-resolution reads. These are worst-case counts in the traditional fully allocated multilevel inode indexing model; existing buffer cache entries can reduce them.