Implement Write-Ahead Logging for Filesystem Journaling

Topic Overview

Write-Ahead Logging

Journaling filesystems log metadata changes before applying them to the main structures. After a crash, replay brings the on-disk state to a consistent point. ext3/ext4 and xfs use variations of this pattern.

Transaction Steps

Typical metadata update:

• Journal commit: write intent record to log block
• Checkpoint: apply changes to superblock/inode tables
• Free log space after durable write

For example, creating a file might journal "allocate inode 42, insert dentry foo" before the inode table reflects inode 42 as in use.

Why This Matters in Production

Write-ahead logging is exactly how ext3, ext4, and NTFS survive power failures without running a multi-hour fsck, replaying only committed transactions and rolling back the rest. Get the commit-flag check backwards and you either lose a completed write or, worse, replay a half-written transaction and corrupt the filesystem it was supposed to protect.

Debugging Checklist

Before you call the implementation done, walk failure modes on purpose. Test empty structures, single-element edge cases, maximum concurrency, and errno paths that must not crash the program. OS code usually fails in production when happy-path tests pass but invariants break under contention or memory pressure.

Implementation Notes

Keep structures small and name fields after kernel counterparts when possible. That lets you read man pages and kernel source side by side while you work. Print observable events during development; remove noisy logs once tests pass reliably.

For This Exercise

You will implement a simple WAL with redo records for create and unlink operations. The task asks you to simulate crash mid-transaction and prove replay restores consistency.

Your Task

Implement write-ahead logging as ext3/ext4 journaling uses it. Block updates are grouped into transactions and written to a journal first, followed by a commit record. They reach their home location on disk only at a checkpoint. After a crash, recovery replays every committed transaction from the journal and discards any transaction whose commit record never made it. Transactions are therefore all-or-nothing, even if power fails halfway through.

State

• disk: blocks 0..15, all initially 0 (survives crashes).
• journal: an ordered list of transactions, each with its block writes and a commit flag (survives crashes).
• open transaction: in memory only (lost in a crash).

Commands

In checkpoint, the block count counts each write, so a block written by two transactions counts twice. checkpoint leaves uncommitted journal entries (from tornc) in place.

Errors: begin with a transaction open → error: T1 already open. write/commit/tornc without one → error: no open transaction. A block outside 0..15 → error: bad block B.

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. Keep persistent state (disk, journal) and volatile state (open transaction) in separate structures, so that crash can only clear the volatile part.
2. Replay must be idempotent: replaying a transaction twice leaves the same disk contents.

Hidden tests cover a torn commit that recovery discards while replaying the committed transactions before it, a checkpoint after several commits (including a block written twice), reads from each source, and every error.