Implement Copy-on-Write Filesystem for Snapshots

Topic Overview

Snapshot-Friendly Storage

Copy-on-write filesystems (ZFS, btrfs snapshots) never overwrite live blocks; they write new blocks and update pointers, leaving old trees reachable for snapshots.

Snapshot Mechanics

On write to snapshotted file:

• Allocate new data block
• Copy-on-write metadata path to root
• Snapshot inode still references old tree

For example, volume at snapshot S0 shares 90% of blocks with live tree; after heavy writes, shared ratio drops as new branches diverge.

Why This Matters in Production

Btrfs, ZFS, and Apple's APFS all use exactly this copy-on-write-plus-reference-counting design to make snapshots instantaneous and clones nearly free, which is why zfs snapshot and Time Machine local snapshots return immediately even on multi-terabyte volumes. Forgetting to check the reference count before an in-place write is exactly the bug class that would corrupt a snapshot that's supposed to be immutable.

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 COW block pointers and create read-only snapshots referencing older roots. This exercise requires proving reads from an old snapshot see historical contents after live file changes.

Your Task

Model a copy-on-write filesystem, the design behind Btrfs, ZFS and APFS snapshots. Data blocks are never overwritten: every write goes to a freshly allocated block and the file's block pointer is switched to it. Blocks carry reference counts, so a snapshot is just a copy of the metadata (the list of files and their block pointers) that bumps every refcount. A snapshot therefore costs no data copying, and blocks are shared until one side writes.

Commands

• There are 256 blocks. Allocation takes the lowest block whose refcount is 0, and a block is free exactly when its count is 0.
• referenced counts block pointers in the live files and all snapshots.
• blocks freed counts blocks whose count dropped to 0.
• Errors: write FILE[IDX]: bad index (file has N blocks), write FILE[IDX]: no space, cat X: no such file, cat SNAP:FILE: no such snapshot, rm FILE: no such file, snapshot NAME: already exists, delsnap NAME: no such snapshot.
• Counts are always followed by the plural blocks (1 blocks freed); only the write note says 1 ref / N refs.

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. A refcount array for the block pool, and file tables (the live tree plus each snapshot) that hold only block numbers.
2. Snapshots copy metadata only; a write never modifies an existing block.

Hidden tests cover two snapshots sharing blocks with the live tree, writes that free old blocks once no snapshot holds them, deleting snapshots in a different order than they were taken, reading an old version from a snapshot after the live file changed, and every error.