Appending one byte can require more than one byte of work. If a file has exhausted its direct block pointers, the append may allocate an indirect block, allocate a data block, set a bitmap bit, install two pointers, extend the inode size, dirty several cache entries, and arrange for all of those changes to become recoverable. A design that models write as “copy bytes to disk” cannot explain either its cost or its failure modes.
The implementation problem is to maintain one connected graph across several representations:
Every cache duplicates part of that graph in memory. Every allocator mutates its ownership relation. Correctness therefore depends less on individual helper functions than on invariants spanning layers.
Every xv6-specific constant and control-path trace below is pinned to official tag xv6-riscv-rev5, commit 7d7adbb1b0acbd67c9766a20d0f9900fef2789fa. A moving branch may change the format or helper behavior and is not evidence for these derivations.
A layered contract, not a call-stack accident
The concrete model uses one block device, fixed-size blocks, one filesystem, inodes, fixed-size directory entries, a bitmap allocator, and a write-back buffer cache. System calls may execute concurrently. Device completion can sleep and wake a process. The model makes no crash-ordering assumption.
Each arrow is a contract boundary:
- the name layer returns a referenced inode identity, not an unprotected pointer into an on-disk block;
- the inode layer maps a logical byte range to blocks without exposing allocator internals;
- the allocator owns the rule that one block cannot belong to two live allocations;
- the buffer cache serializes access to a cached block and prevents two divergent in-memory copies of the same device block; and
- the device layer reports completion or error rather than deciding filesystem policy.
Production kernels add virtual-filesystem dispatch, page-cache integration, writeback policy, extents, per-CPU structures, and many caches. The compact layers remain useful because their invariants can be enumerated completely.
Deriving the disk map
Freeze these parameters for the traces:
| parameter | value | consequence |
|---|---|---|
| block size | 1024 bytes | every region is addressed in 1 KiB units |
| disk-block number | 32-bit unsigned | one indirect block stores 256 pointers |
| on-disk inode size | 64 bytes | 16 inodes fit in one block |
| direct addresses | 12 | logical blocks 0 through 11 are direct |
| directory name bytes | 14 | one entry is a 2-byte inode number plus 14 name bytes |
The disk regions are ordered:
block 0 boot
block 1 superblock
next nlog recovery log
next ... inode blocks
next ... free-space bitmap blocks
remainder file and directory data blocks
The superblock records region starts and sizes. Derived constants are
and
For inode number and data block
Worked trace: locate two pieces of metadata
Let inodeStart = 32 and bitmapStart = 48.
- Inode 37 is in block slot
- Data block 9000 is represented in bitmap block bit of that block. Byte contains the bit; mask selects it.
The formulas reveal a boundary condition: inode 16 starts a new inode block, and data block 8192 starts a new bitmap block. Tests that use only zero and small identifiers will not exercise those transitions.
Derivation checkpoint: resize the model
The block size becomes 4096 bytes, inode size remains 64 bytes, and block numbers remain 32 bits. Compute IPB, BPB, and NINDIRECT. Then state which values are format commitments rather than values the kernel may change while mounting an existing image.
Reveal the derivation and diagnosisExpandCollapse
and Block size, on-disk inode layout, pointer width, region locations, and interpretation of bitmap bits are format commitments: changing them without a versioned migration changes the meaning of existing bytes. An in-memory cache capacity can change without rewriting the disk format, provided all observable behavior and invariants remain intact.
A response giving BPB=4096 has counted bytes rather than bits. A response treating sizeof(struct dinode) as automatically stable across compilers has missed why on-disk layouts need fixed-width fields, layout checks, and versioning.
On-disk layout arithmetic and inode invariants
With 1024-byte blocks, 64-byte inodes, inodeStart = 32, and bitmapStart = 48, evaluate each structural mapping claim:
Classify each option as correct or incorrect, or leave uncertain options unanswered (“I don't know”) and verify at any time.
Inodes split identity from residency
An on-disk inode stores persistent metadata: object type, device identifiers where applicable, link count, byte size, and block addresses. An in-memory inode adds transient state: device and inode identity, reference count, validity, and a sleepable lock protecting loaded metadata.
These states must not be conflated:
ref > 0means kernel code holds an in-memory reference; it does not mean a directory names the inode.nlink > 0means namespace entries name the object; it does not count open descriptors.- “valid in cache” means metadata has been read from disk; it does not mean a caller currently holds the inode lock.
- the inode number identifies the object within a filesystem; the address of an in-memory cache slot is not persistent identity.
The inode cache should return the same in-memory entry for a live (device, inode-number) pair. Otherwise two locks could protect two copies of one object’s size and block map, making both updates appear locally synchronized while losing one globally.
Cache-identity invariant. At most one active in-memory inode entry represents a given
(dev, inum). Its reference count prevents reuse; its inode lock serializes metadata inspection and mutation.
Worked trace: why reference and link counts differ
Object 52 has two names, a and b, and one open descriptor. Its state is nlink=2, with at least one in-memory reference from the open file.
unlink("a")removes one directory entry and decrementsnlinkto 1.unlink("b")removes the other and decrementsnlinkto 0.- The open descriptor still holds an inode reference, so truncation and inode reuse are postponed.
- Closing the descriptor drops the final reference. The implementation may then free data blocks and mark the inode unused inside an appropriate recoverable operation.
Freeing at step 2 would let the allocator hand a still-open block to another file. Deferring forever because nlink==0 but ignoring the reference transition would leak it.
Boundary checkpoint: detect the alias bug
An inode cache searches without a lock, finds no entry for (1,52), and two CPUs each install that identity into a different free slot. Each slot has its own sleep lock. Explain why adding locks around writei cannot repair the design.
Reveal the invariant failureExpandCollapse
The first failure is cache identity, before either writei begins. The two locks guard different memory objects, so both writers can hold a lock while independently reading and overwriting inode 52’s size or block pointers. The lookup-and-reserve transition must be atomic under a cache-level lock or equivalent uniqueness mechanism. Per-inode locking is meaningful only after identity uniqueness has been established.
Mapping byte offsets to blocks
With 12 direct pointers and one single-indirect pointer, logical block number maps as follows:
The maximum representable file is bytes in this model. The maximum valid byte offset is one less than that value. A zero pointer denotes a hole or an unallocated block according to the filesystem’s policy; a growing write may allocate it, while a read from a sparse hole may return zeros in a filesystem that supports sparse files. Compact xv6 allocation eagerly allocates blocks reached by writes and is not a complete sparse-file implementation.
Worked trace: offset through the indirect block
Translate byte offset
- Logical block is
- In-block offset is
- Since consult indirect entry
- If the inode’s indirect pointer names block 700 and word 1 of block 700 contains
912, the requested byte is byte 37 of device block 912.
This access can require two cache lookups: one for indirect block 700 and one for data block 912. Caching the inode does not cache the indirect block’s contents inside the inode.
Application checkpoint: boundary test set
Choose the smallest set of byte offsets that distinguishes direct mapping, the direct-to-indirect transition, the last representable byte, and the first rejected byte.
Reveal a minimal discriminating setExpandCollapse
One suitable set is:
0: first byte of direct logical block 0;12*1024 - 1 = 12287: final byte reachable through the last direct pointer;12*1024 = 12288: first byte requiring indirect entry 0;268*1024 - 1 = 274431: final representable byte;268*1024 = 274432: first out-of-range byte.
Adding offsets around an inode-block and bitmap-block boundary tests different mechanisms and is valuable, but it is not required to distinguish the block-map branches themselves.
Directory files implement the namespace edge
In the compact format, a directory is a file whose data is an array of fixed-size entries:
struct dirent {
uint16_t inum;
char name[14];
};
An entry with inode number zero is free. Lookup scans entries, compares bounded names, and returns a referenced inode for the matched number. Insertion must reject duplicate names, find or append a free slot, and update the directory inode’s size if it grows. Removal clears an entry and adjusts the target’s link count under the operation’s locking and recovery protocol.
Fixed entries make traversal easy to inspect, but impose a severe name limit and linear lookup. Production directories commonly use hashed or tree indexes and variable-length records. Those structures optimize lookup; they do not change the abstract requirement that each live directory edge targets a valid object under the filesystem’s rules.
Worked trace: /usr/log to a data byte
Assume root inode 1, and directory contents:
inode 1: "." -> 1, ".." -> 1, "usr" -> 18
inode 18: "." -> 18, ".." -> 1, "log" -> 37
inode 37: regular file, size 1500, direct[0] = 620, direct[1] = 777
Resolving byte 1200 of /usr/log performs this conceptual trace:
| stage | state transition |
|---|---|
| root selection | acquire reference to inode 1 |
component usr | lock inode 1, scan its directory blocks, obtain referenced inode 18, release inode 1 |
component log | lock inode 18, scan entries, obtain referenced inode 37, release inode 18 |
| type and range check | lock inode 37; verify regular file and 1200 < size |
| block map | logical block 1, in-block offset 176, direct pointer 777 |
| data access | acquire buffer (device,777) and copy from byte 176 |
The trace elides permission checks and mount traversal by assumption. It still exposes every identity and lock handoff needed to inspect a bug.
Allocation and the buffer cache
Allocation scans bitmap blocks for a zero bit, sets one bit while synchronized, and normally zeroes the selected data block before exposing it to a file. Zeroing is a confidentiality and determinism obligation: otherwise a new file could read bytes left by a previous owner.
The core allocation invariants are:
- each allocated block has its bitmap bit set;
- no live metadata path assigns one block to two owners unless the format explicitly supports sharing;
- a block is initialized before user-visible reads can reach it;
- freeing removes all live metadata references before clearing ownership; and
- allocator changes and pointer changes belong to one recoverable update protocol.
The buffer cache maps (device, block-number) to one in-memory buffer. A cache lock protects the identity map and replacement metadata; a per-buffer sleep lock protects the bytes. Holding a global spinlock across device I/O would block unrelated CPUs and may sleep in an invalid context. Releasing all identity protection before marking a victim reserved can create duplicate buffers.
Worked mutation: crossing into indirect addressing
A file is exactly 12 KiB long, with all direct blocks allocated and no indirect block. One byte is written at offset 12 KiB. Ignoring recovery order, a correct growth path must make these logical changes:
- allocate and zero an indirect block;
- store its block number in the inode’s indirect slot;
- allocate and zero a data block;
- place the data-block number in indirect entry 0;
- copy the byte into that data block;
- set inode size to 12 KiB + 1.
On rev5, FSSIZE=2000 is smaller than BPB=8192, so both allocations necessarily dirty the filesystem’s single bitmap block; the remaining unique blocks are the indirect block, data block, and inode block. A larger image using the same bitmap format could place the two allocations in different BPB ranges and dirty two bitmap blocks. Rewriting the same buffer twice should not consume two logical log slots in a log that absorbs duplicate block updates.
Ordering these writes directly to home locations is unsafe: publishing the inode pointer before initializing its target exposes stale data; publishing a data allocation but never linking it leaks a block; growing size without a block pointer exposes an unmapped logical range. A transaction or copy-on-write publication mechanism must constrain the crash-visible states.
Transfer checkpoint: construct a killing test
A faulty allocator sets the bitmap bit and returns the block but does not zero it. A prior file filled that block with SECRET, then was removed. Design a deterministic test that distinguishes the faulty allocator from a correct one without assuming which numeric block will be reused.
Reveal a test strategy and its limitationExpandCollapse
Fill the filesystem sufficiently to control the free set, create a file whose allocated blocks contain a repeated nonzero pattern, delete it, then allocate a new file into the now-constrained free space. Extend the new file in a way that makes newly allocated bytes readable without overwriting the full block—if the filesystem supports sparse extension—or instrument the teaching kernel immediately after allocation and before caller writes. Assert that every exposed byte in the new allocation is zero.
On compact xv6, ordinary writes copy caller bytes into the written range, and its interface does not provide a rich sparse-file operation. A pure user-space test may therefore be unable to observe unwritten bytes deterministically. The honest solution is a kernel test hook or a scoped sparse-extension feature, not a claim that one lucky block reuse proves zeroing. The test must also restore or rebuild the image so free-space history is controlled.
Deep Practice
Solve these problems to test and consolidate your understanding. Complete worked solutions and diagnostic hints are available for each problem.
Exercise 6.2.1: Calculating Inode and Bitmap Block Locations
A filesystem layout defines:
- Block size:
- On-disk inode size:
- Superblock specifies:
inodestart = 32,bmapstart = 48.
- Calculate the number of inodes per block and the number of bits tracked per bitmap block
- Determine the exact disk block number and intra-block slot index for inode 45.
- Determine the exact bitmap disk block number and intra-block bit offset for data block 18,432.
HintExpandCollapse
Use integer division and modulo with IPB and BPB.
Worked solutionExpandCollapse
- Parameters:
- Inodes per block:
- Bits per bitmap block:
- Inode 45 location:
- Inode block number:
- Inode slot index within block 34:
- Data block 18,432 bitmap location:
- Bitmap block number:
- Bit offset within block 50:
Exercise 6.2.2: Maximum Representable File Size Under Direct and Indirect Pointers
An on-disk inode structure contains 12 direct block pointers and 1 singly-indirect block pointer. Block size is and disk block addresses are 32-bit unsigned integers.
- Calculate the maximum number of data blocks that can be addressed by a single file.
- Calculate the maximum file size in KiB and bytes.
- If an engineer adds 1 doubly-indirect block pointer to the inode, calculate the new maximum file size.
HintExpandCollapse
One indirect block contains B / 4 pointers = 256 block addresses.
Worked solutionExpandCollapse
- Maximum blocks with singly-indirect pointer:
- Direct pointers: 12 blocks.
- Singly-indirect pointers: blocks.
- Total blocks:
- Maximum file size:
- With doubly-indirect pointer added:
- Doubly-indirect pointer addresses data blocks.
- Total blocks =
- New maximum file size:
Exercise 6.2.3: Tracing Logical File Offsets to Physical Disk Blocks via bmap
A process writes to file offset byte 15,000 on an xv6 filesystem with 1024-byte blocks. The inode contains direct pointers and indirect block pointer 700. Indirect block 700 contains entries
- Determine the logical block index and intra-block byte offset corresponding to byte offset 15,000.
- State whether this logical block is direct or indirect, and identify its entry index.
- Compute the physical disk block number where this byte will be written.
HintExpandCollapse
Divide byte offset by 1024. Direct blocks cover indices 0 to 11.
Worked solutionExpandCollapse
- Logical block and offset:
- Logical block index:
- In-block byte offset:
- Direct vs Indirect lookup:
- Indices (12 blocks) are direct.
- Since the block resides in the indirect range.
- Indirect entry index:
- Physical block translation:
- The kernel fetches indirect block 700.
- It reads entry at index 2, which contains physical block pointer 802.
- The byte is written to physical block 802 at byte offset 664.
Exercise 6.2.4: Proving Buffer Cache Uniqueness and Preventing Split-Brain Aliasing
Prove that the operating system buffer cache must enforce the invariant:
Show how allowing two concurrent in-memory struct buf instances for the same disk block causes split-brain data loss.
HintExpandCollapse
Show that two threads modifying different fields in separate buffer copies overwrite each other on writeback.
Worked solutionExpandCollapse
Assume for contradiction that two distinct in-memory buffer instances and exist simultaneously in the buffer cache for the identical disk block
- Suppose Thread 1 acquires to update directory entry within block and writes its changes into ‘s memory.
- Concurrently, Thread 2 acquires to update directory entry in the same block and writes its changes into ‘s memory.
- Thread 1 commits its modification: the buffer cache writes ‘s 1024 bytes to disk. The disk block now contains updated but stale
- Subsequently, Thread 2 commits its modification: the buffer cache writes ‘s 1024 bytes to disk.
- Because was modified independently without observing ‘s changes, ‘s writeback completely overwrites the physical disk block, silently destroying Thread 1’s update to
Therefore, the buffer cache must maintain a global lock across lookup and allocation (bcache.lock) ensuring that any request for returns a pointer to the single existing in-memory buffer, incrementing its reference count rather than instantiating a duplicate.
Exercise 6.2.5: Data Block Zeroing and Elimination of Residual Data Leaks
Explain why the block allocator balloc() must synchronously zero newly allocated disk blocks before attaching them to an inode block map. Describe the security vulnerability that arises if a newly allocated block is published to user space with uninitialized contents.
HintExpandCollapse
Consider prior file deletions leaving unencrypted sensitive data on deallocated blocks.
Worked solutionExpandCollapse
- The confidentiality vulnerability:
When a file is deleted, the filesystem marks its blocks free in the bitmap (
bfree()) but does not immediately wipe the physical bytes on magnetic media or flash chips to avoid disk write latency. As a result, freed blocks retain residual data (e.g., plaintext passwords, private cryptographic keys, user emails, or database records). If a newly created file allocates a block and attaches it to its inode without zeroing:- An unprivileged user can create a large file, immediately extend its length or read its contents without writing, and read the raw residual bytes left behind by prior processes or administrative files.
- This constitutes an information disclosure vulnerability (residual data leakage across security domains).
- Enforcement:
balloc()acquires a buffer for the allocated block, executesmemset(bp->data, 0, BSIZE), dirties the buffer in the active log transaction, and commits it. This guarantees that user-mode readers observe only zeroes until authorized writes occur.
References & Further Reading
- MIT PDOS, xv6 RISC-V source and book — official entry point for the licensed teaching kernel and text.
- MIT PDOS, xv6-rev5
kernel/fs.h— immutable on-disk format and mapping constants used by the concrete model. - MIT PDOS, xv6-rev5
kernel/fs.c— immutable block allocation, inode cache, block mapping, directories, and pathname traversal source. - MIT PDOS, xv6-rev5
kernel/sysfile.c— immutable filesystem system-call validation and transaction boundaries. - MIT PDOS, xv6-rev5
kernel/param.h— immutableFSSIZE, per-operation log reservation, and cache-capacity constants used to bound rev5-specific traces. - Linux kernel documentation, Overview of the Virtual File System — production VFS object and operation boundaries.
- Linux kernel documentation, ext4 data structures — a production-format contrast for superblocks, block groups, inodes, extents, and directories.