Implement Block Cache for Filesystem Performance

Topic Overview

Caching Below the Filesystem

Block caches keep recently used disk blocks in RAM, keyed by (device, block number). Reads hit RAM; misses fetch from media and insert with eviction policy (LRU or clock).

Cache Structure

Fields per entry:

• block_id and dirty flag
• data[BLOCK_SIZE]
• refcount or LRU timestamp

For example, scanning a 1 MB file with 4 KB blocks touches 256 distinct block IDs; a 64-entry cache captures hot sequential reuse on second pass.

Why This Matters in Production

The hash-table-plus-LRU-list design here is exactly how Linux's unified page cache accelerates every file read, and the clock algorithm mentioned is what the kernel actually uses instead of strict LRU to keep overhead low at scale. Mixing up write-through and write-back semantics is a real source of data-loss bugs: one is safe but slow, the other is fast but loses dirty data on a crash.

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 get/put with clock eviction and write-back on flush. The task asks you to count cache hits vs misses on repeated reads of the same file.

Your Task

Build a filesystem block cache (a buffer cache), the layer that makes repeated reads free and batches writes. Blocks are found through a hash table and evicted in LRU order. Two write policies are compared: write-through (every write also goes to disk) and write-back (writes only mark the cached block dirty, and the disk is updated on eviction or sync). You'll also see the price of write-back: a crash loses dirty blocks.

Input

cCopy
Loading…

The disk has blocks 0-999, all initially 0. V is an integer.

Behaviour

• read B: on a hit, move B to most-recently-used. On a miss, read B from disk (1 disk read) and insert it as MRU.
• write B V: on a miss, allocate B in the cache without reading the disk (the whole block is being overwritten). Store V and make B MRU. Under write-through, also write V to disk (1 disk write). Under write-back, mark B dirty.
• Eviction: before inserting into a full cache, evict the LRU block. A dirty block is written to disk first (1 disk write).
• sync: write every dirty block to disk in ascending block order and mark them clean.
• crash: discard the whole cache without writing anything.

Output

cCopy
Loading…

The eviction note is evicted B for a clean block and evicted B (written back) for a dirty one, placed between miss and the rest of the line. The hit rate counts reads and writes, with one decimal (0.0 with no accesses).

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. A hash table (chained or open-addressed) from block number to cache entry, plus a doubly linked LRU list, so that lookup, move-to-front and eviction are all O(1).
2. The write policy is a flag; everything else is shared.

Hidden tests cover the same workload under write-through (more disk writes, nothing lost on crash), a crash under write-back that loses data (the next read returns the old disk value), capacity 1, and repeated writes to one block that write-back absorbs.