A file grows from one block to two. The kernel must initialize a new data block, mark it allocated, and publish its address and the new size in the inode. Power fails after the inode reaches stable storage but before the data and bitmap. After reboot, the inode exposes a block the allocator considers free; another file can receive the same block, and the first read may disclose stale bytes.
Locks cannot repair this failure. They constrain live interleavings, but a crash erases lock state and volatile memory. Recovery correctness requires a protocol over persistence order: which subsets of writes may survive, which subset becomes authoritative, and how reboot code distinguishes complete from incomplete updates.
The crash model is part of the theorem
Use a bounded block-device model unless a problem states otherwise:
- a block write may be delayed or reordered before stable acknowledgement;
- after an acknowledged flush or equivalent barrier, preceding writes in the specified domain are stable;
- a sector write is atomic: recovery observes its old or new value, not a torn mixture;
- volatile kernel and controller state disappears at the crash;
- the device does not silently lose a write it acknowledged as stable; and
- recovery itself may crash and run again.
These are assumptions, not universal hardware facts. A controller without protected write-back power, a filesystem mounted with weaker barriers, or a device that violates flush semantics invalidates the proof. Checksums and duplicated headers can detect some torn writes; they cannot manufacture durability from a device that lies about persistence.
Define four properties separately:
| property | question |
|---|---|
| runtime atomicity | can another live operation observe an intermediate namespace state? |
| crash atomicity | after recovery, is the update entirely absent or entirely present? |
| durability | after the documented success/barrier point, must the update survive the modeled crash? |
| recovery idempotence | does running recovery twice produce the same authoritative state as running it once? |
A filesystem may provide one without all four. An atomic rename constrains concurrent name visibility; it does not, by itself, state that the renamed data or directory entry is durable.
Crash consistency, write ordering, and journaling invariants
Evaluate each statement regarding filesystem crash consistency, journaling, and recovery idempotence:
Classify each option as correct or incorrect, or leave uncertain options unanswered (“I don't know”) and verify at any time.
Derive invariants before ordering writes
Model one append with Boolean state
- new block contains the intended bytes;
- allocation bitmap marks the block owned;
- inode size and block map expose the block.
The minimum safety invariants are
is unreachable allocated space: a leak, but not cross-file aliasing. is an unreachable overwrite of a free block and can destroy data if the allocator had concurrently assigned it; the single-operation model assumes the allocator reserved the block in volatile state while the operation ran. is dangerous because the same block can be reallocated. exposes stale or partial content.
Worked crash trace: metadata-first append
Suppose home-location writes reach stable storage in this order: inode, bitmap, data. Crashes produce:
| crash cut | durable tuple | diagnosis |
|---|---|---|
| before any write | (0,0,0) | complete pre-state |
| after inode | (0,0,1) | dangling reference and stale-data exposure |
| after bitmap | (0,1,1) | inode exposes uninitialized content |
| after data | (1,1,1) | complete post-state |
Reversing the writes to data, bitmap, inode avoids an exposed uninitialized block in this one append:
| crash cut | durable tuple | diagnosis |
|---|---|---|
| after data | (1,0,0) | namespace remains old; new bytes unreachable |
| after bitmap | (1,1,0) | leaked allocation |
| after inode | (1,1,1) | complete post-state |
Ordering reduces damage but does not give crash atomicity: the leak is neither the complete pre-state nor post-state. More complex operations have cyclic dependencies. Replacing a file can require the new directory edge before removing the old to avoid loss, while link counts and replacement targets require another order. A general mechanism needs a commit point separate from home locations.
Application checkpoint: derive, do not memorize
A directory insertion requires a new directory data block. The operation changes bitmap bit directory-inode pointer directory size and entry bytes State necessary implications for a visible new name, then propose a data-before-metadata order and identify its remaining non-atomic state.
Reveal the dependency analysisExpandCollapse
If lookup can reach the new entry, then the directory’s block pointer and size must expose the block, the block must be allocated, and the entry bytes must be initialized. One compact set is
A conservative home-write order is initialize persist then publish and together if they occupy one atomically written inode block. Crashing after but before publication leaks the block. If and can tear or occupy different atomic units, more intermediate states exist. The correct diagnosis is “ordered but not atomic,” not “safe because metadata was last.”
Prediction before the recovery model
The journal contains a complete redo image for every block in transaction 9. Its commit record is stable. None of transaction 9’s home-location writes is stable when power fails. Predict the recovered state and name the ordering rule your answer relies on.
Pull the power during a file-system update
Append block B to a one-block file. Move the crash point through unsafe ordering, ordered metadata, write-ahead journaling, and copy-on-write publication; then inspect what recovery can prove.
- 1. journal records the complete transaction
- 2. journal commit record reaches stable storage
- 3. home data block is written
- 4. home bitmap is written
- 5. home inode is written
- 6. journal transaction is checkpointed
On disk when power fails
Visible after recovery
Model scope: one append, atomic sector writes, stable write order once acknowledged, and no torn writes. Real file systems must also handle caches that reorder or lose writes, checksums, concurrent transactions, device flush semantics, and recovery idempotence.
On disk when power fails
Visible after recovery
Static state: power fails after a durable journal commit but before home-location writes. Recovery replays the committed transaction and restores the complete post-state.
The modeled answer is the complete post-state: recovery recognizes the durable commit and replays every logged block to its home location. The conclusion depends on all transaction records becoming stable before the commit record and on the commit record being atomically recognizable. Move the crash point to one step before commit; the same records are ignored because no authoritative commit exists.
Transfer after changing one assumption
Replace the atomic-sector assumption with “a commit sector may tear into a mixture of old and new bytes.” What additional evidence must recovery require before replay?
Reveal the strengthened commit ruleExpandCollapse
Recovery needs a commit representation whose validity can be distinguished from every relevant torn state—for example a checksummed, versioned record with redundancy or an atomic write unit guaranteed by the actual device. The checksum domain must cover transaction identity and the record set it commits; otherwise a valid old commit could be paired with unrelated new records. Recovery must reject an invalid or incomplete commit and preserve the pre-state.
A checksum makes corruption detectable with a quantified residual collision risk; it does not force preceding records to stable storage. Ordering/barrier semantics and commit integrity solve different obligations.
Write-ahead logging from three obligations
A physical redo log stores intended new block images in a reserved region before installing them at home locations. Let be all records for transaction and its commit record. The protocol follows from three obligations:
- Write ahead: every member of is stable before may become stable.
- Publish once: is the sole recovery-visible decision that is committed.
- Do not overwrite evidence early: log space for is reusable only after its committed records are installed at home and that checkpoint state is stable.
The home installation may write A, B, and C in any order after commit because the log retains a complete post-state. If power fails midway, recovery replays all three. Replaying a physical block image twice is idempotent: writing the same final bytes again does not change the result.
Recovery proof obligation. For every crash cut, recovery returns a state observationally equivalent to the pre-state of every uncommitted transaction and the post-state of every committed transaction, while preserving filesystem invariants.
This statement requires a transaction-serialization model. If two committed transactions update the same block, recovery must respect their log order or replay the latest committed image. If a log record is reused before all earlier home writes are stable, the only repair evidence may be destroyed.
Worked trace: atomic name replacement
Transaction 12 replaces directory entry config -> inode 40 with config -> inode 71 and decrements inode 40’s link count from 1 to 0. Its physical log contains new images for directory block D and inode block I.
| durable log/home state at crash | recovery action | visible result |
|---|---|---|
| D record stable, I record absent, no commit | ignore transaction 12 | old name and old link count |
| both records stable, no commit | ignore transaction 12 | old name and old link count |
| both records and commit stable, no home writes | replay D and I | new name; old inode unlinked |
| commit stable, only home D installed | replay both | new name; old inode unlinked |
| commit stable, both home blocks installed, log not cleared | replay both harmlessly | same complete post-state |
Replaying only the missing-looking inode block would require recovery to infer which home bytes are current, a harder protocol. Whole-transaction redo keeps the decision local: valid commit means install every record.
Proof checkpoint: idempotence is not optional
Recovery replays transaction 12’s directory block, then power fails before it replays the inode block. Explain why restarting recovery must replay the directory block again and why an increment-style log record would be dangerous.
Reveal the proof stepExpandCollapse
The commit is still present, so the restarted scan cannot assume that any subset reached home. A physical redo record says “set block D to these bytes”; applying it twice yields the same D. An operation record saying “decrement inode 40’s link count” is not idempotent: replaying it twice decrements twice unless the protocol carries transaction identity and per-object application state. Logical logging can be correct, but it needs a stronger replay design than blind repetition.
Concurrency changes transaction admission
Compact xv6 brackets filesystem system calls with begin_op and end_op. It reserves enough log capacity for worst-case operations before admitting more work. Modified buffers are registered with log_write; repeated modifications to one block are absorbed into one transaction entry. A commit occurs only when no filesystem operations remain active, preventing a commit from installing a block that still contains another operation’s uncommitted update.
This design is intentionally restrictive:
- several system calls may share one log transaction;
- long operations must fit the bounded log reservation model;
- one outstanding commit simplifies ordering but limits throughput; and
- a syscall joining other active operations may return before their shared transaction commits, depending on the exact implementation path and completion timing.
Therefore a user-visible “write returned” claim must not be silently upgraded to “power-safe.” The documented synchronization interface and the implementation’s actual commit semantics determine that boundary.
Application checkpoint: reservation arithmetic
A log has 30 data slots. Each admitted operation reserves a worst-case 10 slots, although duplicate-block absorption often makes actual use smaller. Why may begin_op block the fourth concurrent operation even when the first three currently occupy only six unique slots?
Reveal the safety argumentExpandCollapse
Admission must remain safe if every active operation reaches its worst case after the check. Three operations can require all 30 slots. Admitting a fourth based on current use can deadlock or overflow later, when none can surrender partial work without violating atomicity. Conservative reservation trades concurrency for a simple capacity proof. A more concurrent design needs finer-grained preclaims, multiple transactions, abort support, or dynamically extensible log space; observed average use is not a proof.
Production contrast: ext4 modes are different contracts
Linux ext4 uses JBD2 to journal metadata updates. The journal contains descriptors, logged blocks, and a commit record; replay applies transactions with valid commits. The documented data modes differ:
| mode | journaled content | relevant promise boundary |
|---|---|---|
data=journal | file data and metadata | strongest of these modes, with additional write cost |
data=ordered | metadata; associated new data is ordered before metadata commit | default documented mode, avoiding some stale-data exposure |
data=writeback | metadata; data need not precede metadata | weaker post-crash file-content expectations |
The table is not a complete ext4 guarantee. Delayed allocation, direct I/O, fsync, directory persistence, device flushes, fast commits, checksums, and kernel versions affect a real claim. A teaching log and JBD2 share write-ahead reasoning; their scale, concurrency, record formats, and user-visible contracts are not interchangeable.
Failure boundaries that invalidate easy proofs
- Torn sectors: an apparently present header may be half old and half new.
- Reordered caches: issuing records before commit is insufficient unless stable order is enforced.
- Lost acknowledgement: a device claiming a flush completed but losing it violates the model.
- Log checksum omission: recovery may replay corrupted or mismatched records.
- Log reuse before checkpoint: a second transaction can overwrite the only redo image for the first.
- Recovery side effects: a non-idempotent replay operation can corrupt more on each boot.
- Unbounded transaction: a rename or allocation path that exceeds reserved log capacity cannot be made atomic by wishing it fit.
- Interface confusion: runtime atomicity and a successful return are not equivalent to post-crash durability.
Deep Practice
Solve these problems to test and consolidate your understanding. Complete worked solutions and diagnostic hints are available for each problem.
Exercise 6.3.1: The Three Write-Ahead Logging Ordering Rules
State the three fundamental write-ordering rules governing physical block redo journaling. For each rule, state the catastrophic crash failure mode that occurs if that rule is violated.
HintExpandCollapse
Rule 1: Log before Commit. Rule 2: Commit before Home. Rule 3: Home before Log Reuse.
Worked solutionExpandCollapse
The three write-ahead logging (WAL) invariants are:
- Rule 1 (Log records before Commit): All transaction data and metadata blocks written into the journal must reach stable storage before the commit record is written.
- Failure if violated: If the commit record arrives on disk first and power fails while journal blocks are still inflight, recovery will observe a “committed” transaction header and replay garbage or unwritten bytes into home filesystem structures, corrupting the filesystem.
- Rule 2 (Commit before Home installation): The commit record must reach stable storage before any modified block is written back to its permanent home location.
- Failure if violated: If a block is written directly to its home location before commit and power fails, home data is modified but the transaction is uncommitted. Recovery discards uncommitted transactions, leaving home structures permanently inconsistent or partially updated.
- Rule 3 (Home installation before Log reuse / checkpoint): All home-location writes for a transaction must be completely flushed to disk before the log header is updated to free that transaction’s journal slots.
- Failure if violated: If log space is reclaimed while home blocks remain buffered in volatile RAM and a crash occurs, the journal record is gone and home blocks never reached disk. Updates are silently and permanently lost.
Exercise 6.3.2: Crash Cut State Enumeration and Consistency Analysis
A filesystem appends a block to an existing file by updating three distinct structures:
- newly written data block.
- block allocation bitmap.
- inode size and pointer.
Suppose a naive filesystem writes these blocks directly to home disk locations in the order without journaling.
- Enumerate the durable disk state across all possible crash points.
- For each state, determine whether filesystem consistency and user data security are preserved or violated.
HintExpandCollapse
Check invariants: I implies B (no free block aliasing) and I implies D (no stale data exposure).
Worked solutionExpandCollapse
The sequence of writes is: (1) Inode (2) Bitmap (3) Data
- Cut 0 (Crash before is written): Durable state Evaluation: Consistent. The file retains its original size; no blocks are leaked or corrupted.
- Cut 1 (Crash after before Durable state Evaluation: Critical violation. The inode claims the block, but the bitmap marks it free A subsequent file creation will allocate the identical block, causing cross-file aliasing and corruption. Furthermore, reading the block exposes uninitialized garbage
- Cut 2 (Crash after before Durable state Evaluation: Security violation. The block is marked allocated in the bitmap and mapped in the inode, but data write never reached disk. Reading the block exposes stale disk contents left behind by prior deleted files.
- Cut 3 (Crash after Durable state Evaluation: Consistent. All metadata and data updates completed successfully.
Exercise 6.3.3: Proving Idempotence in Physical Redo Journaling
Let denote a physical redo recovery procedure that reads a valid committed log transaction containing blocks and writes each into disk block
- Prove that (idempotence).
- Explain why a logical log record of the form “increment link count of inode 12” is NOT idempotent, and show how a crash during recovery causes catastrophic corruption under logical logging.
HintExpandCollapse
Physical logging writes absolute block contents; logical logging applies relative operations.
Worked solutionExpandCollapse
- Proof of physical redo idempotence: Let denote the disk state. Physical redo logging defines the state transition: Applying the recovery procedure a second time For all other blocks does not alter Because setting fixed byte contents is an idempotent assignment executing recovery times produces the identical disk state as executing it once:
- Failure of logical logging without version numbers:
If the log records a relative transition
- Recovery starts: executes link increment, writing
- Power fails before recovery completes the transaction checkpoint.
- Upon reboot, recovery starts again from the beginning of the log. It executes the link increment again, producing
- The file now has a phantom link count, preventing it from ever being deallocated when unlinked and corrupting filesystem reference integrity.
Exercise 6.3.4: Contrasting ext4 Journal, Ordered, and Writeback Data Modes
Contrast the write ordering and durability guarantees provided by the three ext4 JBD2 journaling modes: data=journal, data=ordered, and data=writeback. Explain why data=ordered represents the default industry choice.
HintExpandCollapse
Consider performance cost of writing data twice versus stale data disclosure risks.
Worked solutionExpandCollapse
data=journal: Both file payload data and filesystem metadata are written to the JBD2 journal before being flushed to home locations.- Guarantee: Full crash atomicity for data and metadata. No stale data exposure; data modifications never roll back if metadata commits.
- Drawback: Severe performance penalty (every byte of file data is written to disk twice: once to the log, then to home).
data=ordered(Default): Only metadata is written to the journal. However, the kernel enforces a strict write-ordering barrier: dirty file data blocks must be flushed to their permanent home locations before the corresponding metadata transaction commit record is written to the journal.- Guarantee: Prevents stale data leakage. If the system crashes, recovery never replays an inode pointing to unwritten blocks. File data is written only once, providing excellent performance while preserving data integrity.
data=writeback: Only metadata is journaled. Data blocks are written back asynchronously whenever the OS page cache flushes, with no ordering dependency with respect to the metadata commit record.- Guarantee: Highest throughput, but vulnerable to data disclosure. A crash after metadata commit but before data flush leaves inodes pointing to unwritten blocks containing previous file data.
Exercise 6.3.5: Log Reservation Sizing and Concurrency Control
An xv6 filesystem log has a fixed capacity of disk blocks. Each system call must reserve its maximum worst-case block consumption in begin_op() before modifying any buffers.
- If a file append can touch at most 10 unique blocks (bitmap, indirect block, data block, inode, etc.), compute the maximum number of concurrent operations that
begin_op()can safely admit. - Explain why admitting a 4th operation when the first 3 operations have currently dirtied only 2 blocks each would risk deadlock.
HintExpandCollapse
A thread holding an active transaction cannot abort or surrender partial work on log overflow.
Worked solutionExpandCollapse
- Admissible operations: To guarantee that the log never overflows even if every admitted operation simultaneously consumes its worst-case reservation:
- Deadlock hazard of optimistic admission:
Suppose the kernel optimistically admits a 4th operation because the first 3 operations have currently modified only unique blocks:
- All 4 operations continue executing concurrently.
- Workload conditions demand that each of the 4 operations now allocates additional blocks, requiring their full 10 blocks: total demand = blocks.
- The log fills completely to 30 blocks.
- All 4 operations stall waiting for additional log space to become free in
log_write(). - However, in xv6, a log transaction cannot commit until all active operations call
end_op(). - None of the 4 operations can finish without more log space, and the log cannot commit and free space until the operations finish. The system enters an unrecoverable deadlock. Conservative reservation strictly prevents this state.
References & Further Reading
- MIT PDOS, xv6 RISC-V source and book — official teaching-kernel source and Chapter 10 filesystem/log explanation.
- MIT PDOS, xv6-rev5
kernel/log.c— immutable transaction admission, log absorption, commit, install, and recovery implementation. - MIT PDOS, xv6-rev5
kernel/fs.c— immutable metadata-update paths protected by the log. - Linux kernel documentation, ext4 Journal (JBD2) — transaction format, commits, replay, checkpoints, and data modes.
- The Open Group, POSIX.1-2024
fsync()— application-visible synchronization interface. - The Open Group, POSIX.1-2024
rename()— runtime namespace atomicity that must not be confused with persistence.