Extension labs · lab 19 · Concurrency · ★★★★☆

A hashed buffer cache

In this tree every bread and brelse, on every hart, takes one spinlock: bcache.lock (kernel/bio.c:26). While one hart scans the 30 buffers for a block, every other hart that wants any block spins. In this lab you split that lock: the buffers go into a hash table of 13 buckets, each with its own lock, so that harts working on different blocks stop waiting for each other.

Splitting a lock sounds like a mechanical change. It is not, because the old lock did more than one job. What exactly did it protect, and which of those jobs can be cut into pieces? The cache recycles the least recently used buffer: what does “least recently used” mean once there is no single list? A miss has to find a free buffer that may sit in another bucket and move it: which locks does that take, in which order, while two other harts do the same? What happens when two harts miss on the same block at the same instant? And afterwards, how do you show that the split helped, and where did the waiting go? The think section asks these questions in the order a designer meets them, and the clinic shows what the tempting wrong answers did on real runs.

The reference solution is five small commits. Measured on three harts with bcachetest, the cache’s locks made a hart wait about 105 times per run instead of about 360, with the same hit rate as before; and the measurement turned up one surprise on the way, which the last commit fixes.

Read first: Tour 15: Spinlocks from the hardware up, Tour 17: Sleep-locks, Tour 18: Lock ordering: how xv6 avoids deadlock, Tour 30: The buffer cache, Tour 51: The lock-order graph, measured · Locks and interrupt state

What this lab teaches

How to find what a lock really protects, by sorting the data it covers into what belongs to one block and what belongs to the whole cache, and how that tells you where the lock can be split.
How to take two locks of the same kind on three harts without deadlock, and what a deadlock looks like on a running machine when you get it wrong.
Why “look up, and insert if missing” must stay one atomic step after the lock that made it atomic is split, and what goes wrong on disk when it does not.
What the original rule “raise refcnt before releasing the lock” protects, and what more it has to protect once buffers can move between buckets.
How to measure lock contention (failed atomic swaps per lock) and read the result: where the waiting went after the split, and why hashing spreads blocks evenly but not accesses.
When a shared variable may be read without the lock that protects it, and how to decide.

The reference branch

ext/19-bcache-hash in ShowMeTheStack/xv6-riscv-labs, branched from the frozen commit 06aad25; 5 commits.

git clone https://github.com/ShowMeTheStack/xv6-riscv-labs
cd xv6-riscv-labs
git checkout -b my-bcache-hash 06aad25   # start your own
git diff 06aad25 origin/ext/19-bcache-hash   # only when you want the answer

1. The spec

Behaviour. The buffer cache keeps its 30 buffers (NBUF) in 13 buckets. A block can be cached only in bucket blockno % 13, and each bucket has its own spinlock.

A lookup that finds its block (a hit) takes only that block’s bucket lock.
brelse, bpin and bunpin take only the lock of the buffer’s bucket.
A miss recycles the least recently used buffer that nobody uses (refcnt == 0), from whichever bucket it is in, and moves it to the bucket of the new block.
As before, a block is never cached in two buffers at once, and a buffer with refcnt > 0 (held, waited for, or pinned by the log) is never recycled.

What must not change.

The interface: bread, bwrite, brelse, bpin, bunpin and what they mean. Nothing outside kernel/bio.c and kernel/buf.h changes.
bread still returns the buffer locked, and bget still holds no spinlock when it calls acquiresleep (sleeping with a spinlock held panics in sched).
When every buffer is in use, the kernel still panics with bget: no buffers.
usertests -q must print ALL TESTS PASSED on 3 harts.

The test program, bcachetest, runs four checks, each with three child processes at once (one per hart), and compares every byte it reads with what was written:

$ bcachetest
bcachetest: private files: OK
bcachetest: one shared file: OK
bcachetest: small files: OK
bcachetest: allocating together: OK
bcachetest: ALL OK

private files: each child writes its own 40-block file and reads it back, 4 times. 40 blocks is more than the 30 buffers, so the cache recycles buffers all the time.
one shared file: the three children read the same 40-block file at the same time, 8 times each.
small files: each child creates, checks and deletes 20 two-block files, 4 times, so the children allocate inodes and blocks at the same time.
allocating together: each child appends one block per round to its own file, in its own directory; before each round the parent waits for a clock tick and reads a big file, then releases the three children at once, so all three allocate a block at about the same moment. At the end each child checks every byte of its file. When a block is wrong, the test prints which file and block it found there instead (the first eight bytes of every block name its file and block).

The test passes on the original kernel too: it is a safety net, not a proof. It cannot see lock contention at all, and a race that it does not happen to hit stays invisible (the clinic shows how often it caught the race it was designed for). Contention is measured separately, with an instrumented kernel (see “Measure”).

2. Think first

Answer each question in your head (or on paper) before opening a hint. Hints get more specific; the reference answer comes last.

1What does bcache.lock protect, and what could be split?

Before changing anything, list what bget, brelse, bpin and bunpin read or write while they hold bcache.lock. Sort the list into facts about one buffer or block, and facts about the cache as a whole. Then commit to an answer: when a hart asks for block 46, which buffers must its lookup examine to be sure that block 46 is not cached already, and which may it safely ignore?

The reference design

bcache.lock protects four different things:

data	about	changed by
the LRU list (`prev`, `next`, `head`)	the whole cache	`brelse` (moves to the front), `binit`
each buffer’s label: `dev`, `blockno`, and `valid` when relabeling	one buffer	the recycling scan in `bget`
each buffer’s `refcnt`	one buffer	`bget`, `brelse`, `bpin`, `bunpin`
the answer to “is block n cached?”	one block, but potentially every buffer	nobody writes it; it is the scan

The last line is why one lock covers all 30 buffers: in the original, a block can be in any buffer, so a lookup must scan them all, and nothing may relabel a buffer during the scan.

Fix where a block can live and the lookup shrinks. With a hash table of 13 buckets and the rule “a buffer is always in bucket blockno % 13”, a lookup of block 46 needs only bucket 7, under bucket 7’s lock: no other bucket can hold block 46. brelse, bpin and bunpin touch one buffer’s refcnt, so they need only that buffer’s bucket. Two things remain global: the LRU order (the next question) and recycling, which takes a buffer out of one bucket and puts it into another (the question after that).

Why 13, a prime? Consecutive block numbers spread evenly over any number of buckets. A prime only protects against access patterns with a stride that shares a factor with the bucket count (with 12 buckets, blocks 0, 4, 8, … would use only 3 of them). The measurements show a different limit: hashing spreads blocks evenly, not accesses; see “Measure”.

Check yourself

1warm-upType a number

With 13 buckets and bucket = blockno % 13, which bucket holds the free-block bitmap of this file system, block 46 (sb.bmapstart, see Tour 30: The buffer cache)?

decimal, 0x hex or 0b binary

2solidChoose all that apply

After the split, which operations need the lock of only one bucket?

bget finding the block already cached (a hit)brelsebpin and bunpinbget recycling a buffer for a block that is not cached (a miss)

2Without one list, what is "least recently used"?

The original keeps all buffers on one list ordered by their last release: brelse moves a buffer to the front, a miss recycles from the back. Could each bucket keep its own list, or could you keep one global list next to the buckets? What would every brelse then have to lock? Design a way to find the least recently used free buffer that puts nothing global on the release path. What clock will you use, and what does reading it cost?

Check yourself

1solidChoose one

A miss finds exactly two unused buffers, A in bucket 9 and B in bucket 2. Both were released during the same clock tick, 41: A first, B a few microseconds later. Every other buffer is in use. Which one does the reference recycle?

Neither: the miss panics with bget: no buffersB, because the scan visits bucket 2 first and replaces its choice only for a strictly smaller stampEither one, at randomA, because it was released first

3A miss moves a buffer between buckets. Which locks, in which order?

Block 1161 hashes to bucket 4 and is not cached. The only unused buffers are in buckets 1 and 3. To move one into bucket 4 you change two lists and the buffer’s label while lookups and releases run on the other harts.

Here is the design most people write first: keep bucket 4 locked from the failed lookup until the insert (so no other hart can cache block 1161 meanwhile), and while holding it, visit the other buckets in index order, locking each one in turn and keeping the lock of the bucket with the best candidate so far.

At the same moment another hart misses on block 1056, which hashes to bucket 3, using the same code. What can happen? Then: what rule makes holding two bucket locks safe?

Check yourself

1solidChoose one

With the first design (own bucket held throughout, others locked in index order, keeping the best candidate’s bucket), which pair of misses can deadlock?

A miss and a hit in another bucketTwo misses on blocks in the same bucketNone: locking the other buckets in index order prevents deadlockA miss on a block in bucket 9 that holds bucket 2 as its best candidate and reaches bucket 4, and a miss on a block in bucket 4 that reaches bucket 2

2solidTrue or false, and why

True or false: in the reference design, a hart may hold two bucket locks at the same time.

TrueFalse

Why?

The search keeps the best candidate’s bucket locked while it locks the next one, always a lower index before a higher one.It holds the block’s own bucket while it searches the others.brelse locks the buffer’s old bucket and its new bucket.

4Your bucket was unlocked while you searched. What did another hart do meanwhile?

In the design from the last question, the hart that missed on block 46 releases bucket 7, searches, and later locks bucket 7 again to insert. Tour 30: The buffer cache showed two children asking for block 46 at almost the same moment. Trace two harts missing on block 46 with this design. What can bucket 7 contain afterwards? Why does that matter (think about balloc and about how the log identifies blocks)? Then: what extra step closes the gap, and which lock must be held for that step to be enough?

Check yourself

1deepFill in the machine state

Recorded with gdb on the reference branch: a bcachetest child (pid 5), on hart 2, missed on block 46 inside write. It holds bcache.evict, holds bucket 0 (the best candidate so far) and has just acquired bucket 1 in the search loop. Fill in the hart’s state at that moment.

kernel/bio.c

57static struct buf *
58bget(uint dev, uint blockno)
59{
struct buf *b;
61
acquire(&bcache.lock);
63
// Is the block already cached?
for (b = bcache.head.next; b != &bcache.head; b = b->next) {
  if (b->dev == dev && b->blockno == blockno) {
    b->refcnt++;
    release(&bcache.lock);
    acquiresleep(&b->lock);
    return b;
  }
}
73
// Not cached.
// Recycle the least recently used (LRU) unused buffer.
for (b = bcache.head.prev; b != &bcache.head; b = b->prev) {
  if (b->refcnt == 0) {
    b->dev = dev;
    b->blockno = blockno;
    b->valid = 0;
    b->refcnt = 1;
    release(&bcache.lock);
    acquiresleep(&b->lock);
    return b;
  }
}
panic("bget: no buffers");
88}

Privilege modeActive stackPage table (satp)Interrupts (sstatus.SIE)noffintena

2deepChoose one

Why must the second look happen after acquiring bcache.evict, rather than just before it?

Only a hart holding evict can insert, so a look made while holding it stays true until the insert; a look made before could be stale by the time evict is acquired.Because acquire(&bcache.evict) disables interrupts, and the look must run with interrupts off.It does not matter; one look anywhere after the first is enough.Because evict protects each buffer’s refcnt.

5brelse, bpin and bunpin get only a pointer. Which bucket, and can it change?

brelse is called with a buffer pointer b. To lock the right bucket it computes b->blockno % 13, reading blockno before it holds any bucket lock. Is that safe? What stops a miss on another hart from relabeling b, and so moving it to another bucket, between that read and the acquire? Then look at the hit path from the other side: why must refcnt be raised before the bucket lock is released, as the original does under bcache.lock (kernel/bio.c:67)?

Check yourself

1solidPut in order

Put the steps of a hit in bget in the order the reference performs them.

raise the buffer’s refcnt
acquire the block’s bucket lock
release the bucket lock
find the buffer with this dev and blockno in the bucket’s list
acquiresleep on the buffer’s sleep-lock

2solidTrue or false, and why

True or false: brelse may read b->blockno before taking any bucket lock, and use it to choose which bucket lock to take.

TrueFalse

Why?

blockno is an aligned 32-bit word, so reading it is atomic.The caller still holds a reference (refcnt ≥ 1), and a miss recycles only buffers with refcnt 0, so the label and therefore the bucket cannot change.Interrupts are off in brelse, so no other hart can relabel the buffer.

6Did it help? Count the waiting, then look at the new hottest lock.

How would you show that the split reduced waiting, rather than only believing it? What would you count, and where in the kernel? Suppose you measured after building everything above and found that one lock that never mattered in the original kernel is now the most contended lock on the buffer-cache path. Which lock is it likely to be, and why? Do you really need it?

Check yourself

1solidChoose one

In the original kernel, tickslock was almost never contended. After commit 4 it was contended between 145 and 195 times per bcachetest run (three runs). Why?

The timer interrupt fires more often with a hashed cache.Every brelse, on every hart, took tickslock to read ticks.clockintr holds tickslock while it scans the buffer cache.The bucket locks are taken inside tickslock.

2deepChoose all that apply

Which facts make the lock-free read of ticks in brelse safe in this kernel?

ticks is an aligned 32-bit word, so a load returns either the old or the new value, never a mix.ticks is declared volatile.Only one hart ever writes ticks.The value is only a hint for choosing among unused buffers; refcnt, under the bucket lock, decides what is in use.Interrupts are off on every hart while brelse runs.

3. Build it

Start.

git checkout -b my-bcache 06aad25

Write your test first (the spec’s four checks in user/bcachetest.c, and $U/_bcachetest\ in UPROGS in the Makefile) and run it on the unmodified kernel: it must print ALL OK there. A test that fails before you change anything tests your test.

Milestones, in an order that keeps the system working after each one. Run bcachetest, usertests -q and bcachetest again after every milestone, on 3 harts.

Time stamps instead of list order, still under the one bcache.lock. Add a lastuse field to struct buf; brelse stamps it when refcnt reaches 0 and no longer moves the buffer; the recycling scan picks the unused buffer with the smallest stamp. Nothing is concurrent yet that was not before.
The hash table, still under one lock. Replace the list with 13 bucket lists; a buffer always sits in the bucket of its blockno, so all 30 start in bucket 0 (their blockno is 0). Lookups search one bucket; a miss unlinks its victim from one bucket and links it into another. Still one lock: this milestone tests the data structure alone.
A lock per bucket. Hits, brelse, bpin and bunpin take one bucket lock; misses take the eviction lock, look again, and search in increasing bucket order. This is where the bugs live; the clinic below shows the common ones.
Measure (see “Measure”) and act on what you find.

Debugging advice. Run with 3 harts (-smp 3, the Makefile’s default CPUS).

A hang with no output is very likely a deadlock. Start QEMU with make qemu-gdb, attach gdb on the port it prints and continue; when it hangs, interrupt gdb (Ctrl-C) and type info threads and thread apply all bt. Two or three harts in acquire at kernel/spinlock.c:37 is a spinlock deadlock. Then print every bucket lock’s locked and cpu (the cpu pointer minus &cpus[0], divided by sizeof(struct cpu), is the hart) and draw the “holds / wants” graph.
Duplicates are silent until two files share a block. While developing, add a temporary check after the insert (with evict held, labels cannot change): scan all 30 buffers and printk if another one has the same dev and blockno. Remove it before you commit.
panic: bget: no buffers with plenty of activity usually means a lost refcnt update: an increment or decrement done without the bucket lock.
Races are probabilistic. One passing run proves little. Run bcachetest several times, on several boots; to test a suspicion, widen the window with a short delay loop in a scratch copy (Clinic 2 and 5 do that).

4. Debugging clinic

Each of these bugs was put into the reference solution on purpose and run on three harts. The symptom is exactly what happened. Try to explain it before revealing why.

1The miss keeps its own bucket locked while it searches the others

The first design from think question 3: no evict lock and no second look; the block’s own bucket bk stays locked from the failed lookup to the insert, and the search skips it (it is already held):

   if ((b = bfind(bk, dev, blockno)) != 0) {
     ...
   }
-  release(&bk->lock);
-
-  // Not cached. Only one miss at a time may recycle a buffer.
-  acquire(&bcache.evict);
-  [... the second look, lines 110-122 ...]
+  // Not cached. Keep bk locked, so no other hart can cache the
+  // same block meanwhile.
   ...
   for (i = 0; i < NBUCKET; i++) {
-    acquire(&bcache.bucket[i].lock);
+    if (&bcache.bucket[i] != bk)
+      acquire(&bcache.bucket[i].lock);

(and the matching releases skip bk; bk is released after the insert.)

What happened when we ran it

$ bcachetest
[... nothing more: the console stays silent. After 120 s, gdb attached and ran
 info threads, thread apply all bt, and a Python loop over the bucket locks ...]
[...]
  Id   Target Id                    Frame 
* 1    Thread 1.1 (CPU#0 [running]) acquire (lk=lk@entry=0x8001d9f0 <bcache+33272>) at kernel/spinlock.c:37
  2    Thread 1.2 (CPU#1 [running]) acquire (lk=lk@entry=0x8001d9b0 <bcache+33208>) at kernel/spinlock.c:37
  3    Thread 1.3 (CPU#2 [running]) acquire (lk=lk@entry=0x8001d9b0 <bcache+33208>) at kernel/spinlock.c:37

Thread 3 (Thread 1.3 (CPU#2 [running])):
#0  acquire (lk=lk@entry=0x8001d9b0 <bcache+33208>) at kernel/spinlock.c:37
#1  0x0000000080002cd0 in bget (dev=1, blockno=1109) at kernel/bio.c:117
#2  bread (dev=1, blockno=blockno@entry=1109) at kernel/bio.c:160
[...]

Thread 2 (Thread 1.2 (CPU#1 [running])):
#0  acquire (lk=lk@entry=0x8001d9b0 <bcache+33208>) at kernel/spinlock.c:37
#1  0x0000000080002c06 in bget (dev=1, blockno=2) at kernel/bio.c:98
#2  bread (dev=1, blockno=2) at kernel/bio.c:160
#3  0x0000000080003ce8 in write_head () at kernel/log.c:107
#4  0x0000000080004008 in commit () at kernel/log.c:207
[...]

Thread 1 (Thread 1.1 (CPU#0 [running])):
#0  acquire (lk=lk@entry=0x8001d9f0 <bcache+33272>) at kernel/spinlock.c:37
#1  0x0000000080002cd0 in bget (dev=1, blockno=1153) at kernel/bio.c:117
#2  bread (dev=1, blockno=1153) at kernel/bio.c:160
[...]
bucket 2 lock: locked=1 held by hart 0
bucket 4 lock: locked=1 held by hart 2
bucket 9 lock: locked=1 held by hart 0
hart 0: proc bcachetest pid 4 noff 3 intena 1
hart 1: proc bcachetest pid 5 noff 1 intena 1
hart 2: proc bcachetest pid 6 noff 2 intena 1

It hung in the very first check of the first run, on two boots out of two. The addresses decode with the layout from the reveal (buckets of 32 bytes from bcache+33144): bcache+33208 is bucket 2 and bcache+33272 is bucket 4. Line 117 of this copy is the acquire inside the search loop; line 98 is the first acquire of a lookup.

hart	process	missed on	own bucket (held)	also holds	spinning for
0	pid 4, reading `bcp0`	block 1153	9	2 (best candidate)	4
2	pid 6, reading `bcp2`	block 1109	4		2
1	pid 5, committing the log	(block 2, a lookup)			2

Hart 0 holds 2 and waits for 4; hart 2 holds 4 and waits for 2: a cycle of length two. Hart 1 is not part of the cycle; it waits behind it for bucket 2 (block 2 is the log header), and since it is in commit, every other process’s end_op would wait for it in turn. noff confirms it: acquire pushes before it spins, so noff counts the lock being waited for too: 2 held + 1 = 3 on hart 0, 1 + 1 = 2 on hart 2, 0 + 1 = 1 on hart 1.

Why the whole machine is silent: a hart spinning in acquire has interrupts off, so it takes no timer interrupt, never yields, and never runs anything else. All three harts are spinning; the console, the shell and every process are stopped for good. Nothing panics, because nothing in xv6 detects a deadlock (lab 21 adds a checker).

The cause is the order. Each hart’s search visits buckets in index order, but each also holds its own bucket from the start, whatever its index. Hart 2’s own bucket (4) is in the middle of hart 0’s scan, and hart 0’s best candidate (2) is in the middle of hart 2’s scan. Releasing the own bucket before the search, as the reference does, leaves only ordered acquisitions; evict makes the cycle impossible a second way.

2No second look after taking evict

The miss takes bcache.evict but goes straight to the search:

   // Not cached. Only one miss at a time may recycle a buffer.
   acquire(&bcache.evict);

-  // Look again: while this hart held no lock, another hart may
-  // have missed on the same block and cached it. Only a miss adds
-  // a block to a bucket, so while evict is held, the answer stays
-  // true.
-  acquire(&bk->lock);
-  if ((b = bfind(bk, dev, blockno)) != 0) {
-    b->refcnt++;
-    release(&bk->lock);
-    release(&bcache.evict);
-    acquiresleep(&b->lock);
-    return b;
-  }
-  release(&bk->lock);

We also built a copy with the window widened (a 20,000-iteration delay loop between the failed lookup and acquire(&bcache.evict)), and one with a detector: after each insert, with evict held, it scans all 30 buffers and prints DUP if another buffer carries the same block number.

What happened when we ran it

# without the delay: three boots, each meant to run bcachetest three times and
# usertests -q once; boots 1 and 2 passed everything, boot 3 went wrong:
[... boot 3, first run: bcachetest: ALL OK ...]
$ bcachetest
bcachetest: private files: OK
bcachetest: one shared file: OK
bcachetest: small files: OK
bcachetest: f: block 35 should be (1, 35) but is (0, 35)
bcachetest: allocating together: FAIL
bcachetest: SOME TESTS FAILED
$ bcachetest
panic: virtio_disk_intr status

# with the delay and the detector (another boot):
$ bcachetest
bcachetest: private files: OK
bcachetest: one shared file: OK
bcachetest: small files: OK
DUP block 46: buffers 19 and 5 (refcnt 1 valid 0)
DUP block 46: buffers 27 and 28 (refcnt 1 valid 0)
DUP block 46: buffers 27 and 11 (refcnt 1 valid 0)
DUP block 46: buffers 28 and 27 (refcnt 1 valid 0)
[... two children's error lines, interleaved character by character ...]
bcachetest: f: block 44 should be (1, 44) but is (0, 44)
bcachetest: allocating together: FAIL
bcachetest: SOME TESTS FAILED

Honest summary first: without the delay this bug is rare. On 3 boots, 7 runs of bcachetest and 2 of usertests -q passed; only boot 3 went wrong, in its second run, and it panicked in its third. In another set of runs, with a slightly different version of the test and the computer busier with other work, 9 runs caught it twice. With the delay, the first run on each of 2 boots failed. (Their second runs failed too, but only because the first run’s failing children had left their directories behind, so mkdir failed and nothing was checked; the branch’s bcachetest removes such leftovers at startup.) The detector shows what happens: every duplicate was block 46, the free-block bitmap, and both copies were fresh (valid 0, refcnt 1): two harts had missed on block 46, both found it missing, and both inserted a buffer for it.

The chain from there to the symptom:

Children 0 and 1 each balloc from their own copy of the bitmap. Both find the same first free bit, both set it, and both get the same block for their files.
log_write records blocks by number: the second bitmap change is absorbed into the first entry, and only the first copy is pinned. At commit, write_log logs whichever copy bread finds first in bucket 7. One of the two allocations never reaches the disk.
Two files now point at one data block. Child 1 writes its block 35 into it, child 0 overwrites it with its own block 35. When child 1 reads its file back, the block’s first eight bytes say “file 0, block 35”: should be (1, 35) but is (0, 35).

The panic on the next run is reasoned, not traced. When blocks are shared, a block that one file uses as its indirect block can be another file’s data block; bmap then reads “block numbers” that are really test data, the disk is asked for a block far beyond its end, the device reports an error, and virtio_disk_intr panics on the non-zero status.

Three lessons. A missing re-check after a lock is dropped and retaken is invisible in most runs. The damage appears far from the cause: in user data, then in the disk driver. And widening the window, plus a detector that checks the invariant directly, turns a once-in-a-while failure into a near-certain one. One more lesson about tests: a test that leaves state behind after failing can make every later run fail without checking anything, which is a false claim of its own.

3Not a bug: reading the clock with a plain load and no lock

In commit 5’s brelse, a plain read instead of the atomic one (and still no tickslock), the way most people first write it:

-  now = __atomic_load_n(&ticks, __ATOMIC_RELAXED);
+  now = ticks;

What happened when we ran it

$ bcachetest
bcachetest: private files: OK
bcachetest: one shared file: OK
bcachetest: small files: OK
bcachetest: allocating together: OK
bcachetest: ALL OK
$ usertests -q
usertests starting
[...]
ALL TESTS PASSED
$ bcachetest
[...]
bcachetest: ALL OK

# objdump -d of brelse in three builds (tabs expanded):
# commit 4, ticks read under tickslock:
    80002e5c:   d8dfd0ef                jal     80000be8 <acquire>
    80002e60:   00005997                auipc   s3,0x5
    80002e64:   a309a983                lw      s3,-1488(s3) # 80007890 <ticks>
    80002e68:   00013517                auipc   a0,0x13
[...]
    80002e70:   e01fd0ef                jal     80000c70 <release>
# commit 5, the atomic load:
    80002e54:   00005797                auipc   a5,0x5
    80002e58:   a3c78793                addi    a5,a5,-1476 # 80007890 <ticks>
    80002e5c:   0007a983                lw      s3,0(a5)
# this change, a plain load:
    80002e54:   00005997                auipc   s3,0x5
    80002e58:   a3c9a983                lw      s3,-1476(s3) # 80007890 <ticks>

4brelse never updates the time stamp

The stamp is never written; every buffer keeps lastuse 0 forever:

   acquire(&bk->lock);
   b->refcnt--;
-  if (b->refcnt == 0) {
-    // no one is waiting for it.
-    b->lastuse = now;
-  }
   release(&bk->lock);

(With -Werror that alone does not build, because now is then set but never used; declaring it uint now __attribute__((unused)); makes it build.)

What happened when we ran it

# a measurement copy counts bread calls ("gets") and disk reads in bread;
# Ctrl-P prints and resets the counters. Boot 1 of 3:
$ bcachetest
bcachetest: private files: OK
bcachetest: one shared file: OK
bcachetest: small files: OK
bcachetest: allocating together: OK
bcachetest: ALL OK
[... Ctrl-P ...]
BC gets 120617 reads 12483
$ usertests -q
[...]
ALL TESTS PASSED
[... Ctrl-P ...]
BC gets 203860 reads 18497

# the same workload on the reference branch, boot 1 of 3:
BC gets 116211 reads 7489
BC gets 205427 reads 1097

Nothing fails: the cache still returns the right data, because correctness never depended on the policy, only on refcnt and the bucket locks. What breaks is the cache’s first job, saving disk reads. With every stamp equal to 0, the search’s tie-breaking decides alone: the victim is always the first unused buffer in bucket order, starting at bucket 0. Hot blocks that happen to hash to low buckets, like the log header (block 2, bucket 2), are thrown out again and again, while blocks in high buckets stay cached long after anyone wants them. (That explanation is reasoned from the scan order; the measurement counted only totals.)

Over three boots of each kernel (both passing bcachetest and usertests -q every time):

disk reads	boot + `bcachetest`	`usertests -q`
reference branch	7,489, 7,563, 7,606	1,097, 1,115, 1,075
this bug	12,483, 13,050, 12,202	18,497, 18,419, 15,418

About 65% more disk reads in bcachetest and about 16 times as many in usertests -q, for about the same number of bread calls (116,000 to 122,000 and 201,000 to 209,000 per run in both kernels). On QEMU with a RAM-backed disk that costs little time; on a real disk every extra read is a wait of milliseconds.

A policy bug is invisible to a correctness test. Only a measurement catches it, which is one reason “Measure” counts disk reads as well as lock waits.

5refcnt is raised after the bucket lock is released

In the hit path, the increment moves one line down, outside the critical section:

   acquire(&bk->lock);
   if ((b = bfind(bk, dev, blockno)) != 0) {
-    b->refcnt++;
     release(&bk->lock);
+    b->refcnt++;
     acquiresleep(&b->lock);
     return b;
   }

We also built a copy with a 20,000-iteration delay loop between the release and the refcnt++, and as a control, the reference with the same delay placed after a correct refcnt++ and release.

What happened when we ran it

# as written: 2 boots, each bcachetest twice and usertests -q once: all passed.

# with the delay (boot 1):
$ bcachetest
[...]
bcachetest: ALL OK
$ bcachetest
panic: virtio_disk_intr status

# with the delay (another boot, in a copy with extra checks):
$ bcachetest
bcachetest: bcp1: block 37 should be (101, 37) but is (1, 37)
bcachetest: private files: FAIL
bcachetest: one shared file: OK
bcachetest: small files: OK
bcachetest: allocating together: FAIL
bcachetest: SOME TESTS FAILED

# the control (delay after a correct increment): 2 boots, bcachetest twice each:
bcachetest: ALL OK

# a third copy: the same delay, plus a check right after the
# hit's acquiresleep that the buffer still holds the block it looked up:
[... earlier runs: ALL OK ...]
$ bcachetest
bcachetest: private files: OK
bcachetest: one shared file: OK
bcachetest: small files: OK
FC WRONG: hit on 1145 returns buffer labeled 1240
panic: virtio_disk_intr status

As written, the window is a few instructions wide and we never saw it fail. With the delay, 7 of 7 boots in our runs went wrong (2 of the plain copy, 5 of copies with extra checks): lost file data, panic: freeing free block, panic: log_write outside of trans, or the disk driver’s panic. The control rules out the delay itself: with the increment in the right place, the same delay changed nothing. How often the delay copy fails depends on what else the computer is doing: the third copy failed visibly on 1 boot of 3.

Why the order matters: between the release and the refcnt++, the buffer looks unused to everyone else.

A miss on another hart may pick it as its victim in that gap, relabel it for another block and start reading that block into it. The hit then raises refcnt on a buffer that is no longer the block it looked up.
Even when no miss intervenes, refcnt++ is now a load, an add and a store done without the lock that every other update of refcnt holds. A concurrent brelse, bpin or relabel on another hart can be lost in between, leaving the count one too low or too high. Too low, and a buffer that someone still holds, or that the log still has pinned, can be recycled; too high, and it can never be recycled again.

The first path was observed. The third copy checked the label right after the hit’s acquiresleep and printed FC WRONG: hit on 1145 returns buffer labeled 1240, followed by panic: virtio_disk_intr status: a miss had recycled the buffer in the gap, and the hit went on with a buffer holding block 1240 as if it were block 1145. On another boot it printed FC WRONG: hit on 47 returns buffer labeled 1080 in a run that still ended ALL OK: wrong data that no check happened to read. Whether the lost-update path also occurred was not observed. (The other copies had similar checks in bread, but which checks ran on each of their logged boots was not recorded reliably, so their silence is not relied on.)

The rule from Tour 30: The buffer cache stands: whatever makes a buffer “wanted” must be recorded under the same lock that the recycler checks, before that lock is released.

5. The reference solution

Take the guided tour through the reference solution, one commit at a time, with the machine state at every step:

Open the reveal tour →

Or read the commits

02acb9a Add bcachetest, a parallel buffer-cache stress test
Makefile
@@ -149,8 +149,9 @@ UPROGS=\
149149 $U/_logstress\
150150 $U/_forphan\
151151 $U/_dorphan\
152152 $U/_sync\
153 $U/_bcachetest\
153154
154155fs.img: mkfs/mkfs README $(UPROGS)
155156 mkfs/mkfs fs.img README $(UPROGS)
156157
user/bcachetest.c
@@ -0,0 +1,242 @@
1// bcachetest: stress the buffer cache from three processes at once.
2//
3// Every check reads back what was written and compares it byte by
4// byte, so a block that was lost, written twice or mixed up with
5// another block shows up as FAIL.
6
7#include "kernel/types.h"
8#include "kernel/stat.h"
9#include "kernel/fcntl.h"
10#include "kernel/fs.h"
11#include "user/user.h"
12
13#define NCHILD 3 // one per hart
14#define NBLK 40 // blocks per big file: more than the 30 buffers
15#define NSMALL 20
16
17static int rounds = 4;
18static char buf[BSIZE];
19
20// a block's contents name the file (who) and the block number.
21static void
22fill(int who, int blk)
23{
24 ((int *)buf)[0] = who;
25 ((int *)buf)[1] = blk;
26 for (int i = 8; i < BSIZE; i++)
27 buf[i] = who + blk + i;
28}
29
30static int
31check(int who, int blk)
32{
33 if (((int *)buf)[0] != who || ((int *)buf)[1] != blk)
34 return 0;
35 for (int i = 8; i < BSIZE; i++)
36 if (buf[i] != (char)(who + blk + i))
37 return 0;
38 return 1;
39}
40
41static int
42writefile(char *name, int who, int nblk)
43{
44 int fd = open(name, O_CREATE | O_TRUNC | O_RDWR);
45 if (fd < 0)
46 return 0;
47 for (int b = 0; b < nblk; b++) {
48 fill(who, b);
49 if (write(fd, buf, BSIZE) != BSIZE) {
50 close(fd);
51 return 0;
52 }
53 }
54 close(fd);
55 return 1;
56}
57
58static int
59readfile(char *name, int who, int nblk)
60{
61 struct stat st;
62 int fd = open(name, O_RDONLY);
63 if (fd < 0)
64 return 0;
65 if (fstat(fd, &st) < 0 || st.size != nblk * BSIZE) {
66 printf("bcachetest: %s: size %d, expected %d\n", name, (int)st.size, nblk * BSIZE);
67 close(fd);
68 return 0;
69 }
70 for (int b = 0; b < nblk; b++) {
71 if (read(fd, buf, BSIZE) != BSIZE || !check(who, b)) {
72 // the first 8 bytes of every block name its file and block.
73 printf("bcachetest: %s: block %d should be (%d, %d) but is (%d, %d)\n", name, b, who, b,
74 ((int *)buf)[0], ((int *)buf)[1]);
75 close(fd);
76 return 0;
77 }
78 }
79 close(fd);
80 return 1;
81}
82
83// run f(child) in NCHILD processes at once; 1 if all of them succeed.
84static int
85parallel(int (*f)(int))
86{
87 int ok = 1, xs;
88 for (int c = 0; c < NCHILD; c++) {
89 int pid = fork();
90 if (pid < 0) {
91 printf("bcachetest: fork failed\n");
92 return 0;
93 }
94 if (pid == 0)
95 exit(f(c) ? 0 : 1);
96 }
97 for (int c = 0; c < NCHILD; c++)
98 if (wait(&xs) < 0 || xs != 0)
99 ok = 0;
100 return ok;
101}
102
103// each child writes and rereads its own big file.
104static int
105private(int c)
106{
107 char name[] = "bcp0";
108 name[3] += c;
109 for (int r = 0; r < rounds; r++)
110 if (!writefile(name, 100 * c + r, NBLK) || !readfile(name, 100 * c + r, NBLK))
111 return 0;
112 return unlink(name) == 0;
113}
114
115// all children read the same file at the same time.
116static int
117shared(int c)
118{
119 for (int r = 0; r < 2 * rounds; r++)
120 if (!readfile("bcshared", 999, NBLK))
121 return 0;
122 return 1;
123}
124
125// each child creates, checks and deletes many small files, so the
126// children allocate inodes and blocks from the same bitmap and inode
127// blocks at the same time.
128static int
129small(int c)
130{
131 char name[] = "bcs0_00";
132 name[3] += c;
133 for (int r = 0; r < rounds; r++) {
134 for (int i = 0; i < NSMALL; i++) {
135 name[5] = '0' + i / 10;
136 name[6] = '0' + i % 10;
137 if (!writefile(name, 1000 * c + i, 2))
138 return 0;
139 }
140 for (int i = 0; i < NSMALL; i++) {
141 name[5] = '0' + i / 10;
142 name[6] = '0' + i % 10;
143 if (!readfile(name, 1000 * c + i, 2) || unlink(name) != 0)
144 return 0;
145 }
146 }
147 return 1;
148}
149
150// remove what together() leaves behind, also after a failed run,
151// so that every run starts from the same state.
152static void
153cleanup(void)
154{
155 char f[] = "bct0/f";
156 for (int c = 0; c < NCHILD; c++) {
157 f[3] = '0' + c;
158 unlink(f);
159 f[4] = 0;
160 unlink(f);
161 f[4] = '/';
162 }
163}
164
165// Each child appends one block per round to its own file, working in
166// its own directory, so that no inode lock keeps them apart. Before
167// each round the parent waits for a clock tick and reads a big file,
168// which pushes the free-block bitmap out of the cache; then it lets
169// the three children go at once. All three allocate a block, so all
170// three need the bitmap block at about the same moment. At the end
171// each child checks every byte of its file.
172static int
173together(void)
174{
175 int go[NCHILD][2], done[2], fd, ok = 1, xs;
176 int n = 15 * rounds;
177 char dir[] = "bct0", x;
178
179 if (pipe(done) < 0)
180 return 0;
181 for (int c = 0; c < NCHILD; c++) {
182 dir[3] = '0' + c;
183 if (mkdir(dir) < 0 || pipe(go[c]) < 0)
184 return 0;
185 }
186 for (int c = 0; c < NCHILD; c++) {
187 if (fork() == 0) {
188 dir[3] = '0' + c;
189 if (chdir(dir) < 0 || (fd = open("f", O_CREATE | O_RDWR)) < 0)
190 exit(1);
191 for (int r = 0; r < n; r++) {
192 if (read(go[c][0], &x, 1) != 1)
193 exit(1);
194 fill(c, r);
195 if (write(fd, buf, BSIZE) != BSIZE)
196 exit(1);
197 write(done[1], "d", 1);
198 }
199 close(fd);
200 exit(readfile("f", c, n) && unlink("f") == 0 ? 0 : 1);
201 }
202 }
203 close(done[1]); // so that read(done[0]) returns 0 if all children die
204 for (int r = 0; r < n; r++) {
205 pause(1);
206 if (!readfile("bcshared", 999, NBLK))
207 ok = 0;
208 for (int c = 0; c < NCHILD; c++)
209 write(go[c][1], "g", 1);
210 for (int c = 0; c < NCHILD; c++)
211 read(done[0], &x, 1);
212 }
213 for (int c = 0; c < NCHILD; c++)
214 if (wait(&xs) < 0 || xs != 0)
215 ok = 0;
216 cleanup();
217 return ok;
218}
219
220static int
221report(char *what, int ok)
222{
223 printf("bcachetest: %s: %s\n", what, ok ? "OK" : "FAIL");
224 return ok;
225}
226
227int
228main(int argc, char *argv[])
229{
230 int ok = 1;
231
232 if (argc > 1)
233 rounds = atoi(argv[1]);
234 cleanup();
235 ok &= report("private files", parallel(private));
236 ok &= report("one shared file", writefile("bcshared", 999, NBLK) && parallel(shared));
237 ok &= report("small files", parallel(small));
238 ok &= report("allocating together", together());
239 unlink("bcshared");
240 printf("bcachetest: %s\n", ok ? "ALL OK" : "SOME TESTS FAILED");
241 exit(ok ? 0 : 1);
242}
303e87e Recycle the buffer with the oldest release time
kernel/bio.c
@@ -26,10 +26,10 @@ struct {
2626 struct spinlock lock;
2727 struct buf buf[NBUF];
2828
2929 // Linked list of all buffers, through prev/next.
30 // Sorted by how recently the buffer was used.
31 // head.next is most recent, head.prev is least.
30 // Its order no longer matters: each buffer's lastuse
31 // says how recently it was used.
3232 struct buf head;
3333} bcache;
3434
3535void
@@ -56,9 +56,9 @@ binit(void)
5656// In either case, return locked buffer.
5757static struct buf *
5858bget(uint dev, uint blockno)
5959{
60 struct buf *b;
60 struct buf *b, *victim;
6161
6262 acquire(&bcache.lock);
6363
6464 // Is the block already cached?
@@ -71,21 +71,24 @@ bget(uint dev, uint blockno)
7171 }
7272 }
7373
7474 // Not cached.
75 // Recycle the least recently used (LRU) unused buffer.
76 for (b = bcache.head.prev; b != &bcache.head; b = b->prev) {
77 if (b->refcnt == 0) {
78 b->dev = dev;
79 b->blockno = blockno;
80 b->valid = 0;
81 b->refcnt = 1;
82 release(&bcache.lock);
83 acquiresleep(&b->lock);
84 return b;
85 }
75 // Recycle the least recently used (LRU) unused buffer:
76 // the one whose last release has the oldest time stamp.
77 victim = 0;
78 for (b = bcache.head.next; b != &bcache.head; b = b->next) {
79 if (b->refcnt == 0 && (victim == 0 || b->lastuse < victim->lastuse))
80 victim = b;
8681 }
87 panic("bget: no buffers");
82 if (victim == 0)
83 panic("bget: no buffers");
84 victim->dev = dev;
85 victim->blockno = blockno;
86 victim->valid = 0;
87 victim->refcnt = 1;
88 release(&bcache.lock);
89 acquiresleep(&victim->lock);
90 return victim;
8891}
8992
9093// Return a locked buf with the contents of the indicated block.
9194struct buf *
@@ -111,29 +114,29 @@ bwrite(struct buf *b)
111114 virtio_disk_rw(b, 1);
112115}
113116
114117// Release a locked buffer.
115// Move to the head of the most-recently-used list.
118// If no one else wants it, record when it was last used.
116119void
117120brelse(struct buf *b)
118121{
122 uint now;
123
119124 if (!holdingsleep(&b->lock))
120125 panic("brelse");
121126
122127 releasesleep(&b->lock);
123128
129 acquire(&tickslock);
130 now = ticks;
131 release(&tickslock);
132
124133 acquire(&bcache.lock);
125134 b->refcnt--;
126135 if (b->refcnt == 0) {
127136 // no one is waiting for it.
128 b->next->prev = b->prev;
129 b->prev->next = b->next;
130 b->next = bcache.head.next;
131 b->prev = &bcache.head;
132 bcache.head.next->prev = b;
133 bcache.head.next = b;
137 b->lastuse = now;
134138 }
135
136139 release(&bcache.lock);
137140}
138141
139142void
kernel/buf.h
@@ -4,8 +4,9 @@ struct buf {
44 uint dev;
55 uint blockno;
66 struct sleeplock lock;
77 uint refcnt;
8 uint lastuse; // ticks when refcnt last dropped to 0
89 struct buf *prev; // LRU cache list
910 struct buf *next;
1011 uchar data[BSIZE];
1112};
9d2a714 Hash the buffers into 13 buckets
kernel/bio.c
@@ -1,7 +1,7 @@
11// Buffer cache.
22//
3// The buffer cache is a linked list of buf structures holding
3// The buffer cache is a hash table of buf structures holding
44// cached copies of disk block contents. Caching disk blocks
55// in memory reduces the number of disk reads and also provides
66// a synchronization point for disk blocks used by multiple processes.
77//
@@ -21,16 +21,19 @@
2121#include "defs.h"
2222#include "fs.h"
2323#include "buf.h"
2424
25#define NBUCKET 13 // a prime, so block numbers spread over all buckets
26
27// A block can only be cached in bucket[blockno % NBUCKET].
28struct bucket {
29 struct buf *first; // list of buffers, through buf.next
30};
31
2532struct {
2633 struct spinlock lock;
2734 struct buf buf[NBUF];
28
29 // Linked list of all buffers, through prev/next.
30 // Its order no longer matters: each buffer's lastuse
31 // says how recently it was used.
32 struct buf head;
35 struct bucket bucket[NBUCKET];
3336} bcache;
3437
3538void
3639binit(void)
@@ -38,54 +41,88 @@ binit(void)
3841 struct buf *b;
3942
4043 initlock(&bcache.lock, "bcache");
4144
42 // Create linked list of buffers
43 bcache.head.prev = &bcache.head;
44 bcache.head.next = &bcache.head;
45 // Every buffer starts with blockno 0, so in bucket 0.
4546 for (b = bcache.buf; b < bcache.buf + NBUF; b++) {
46 b->next = bcache.head.next;
47 b->prev = &bcache.head;
4847 initsleeplock(&b->lock, "buffer");
49 bcache.head.next->prev = b;
50 bcache.head.next = b;
48 b->next = bcache.bucket[0].first;
49 bcache.bucket[0].first = b;
5150 }
5251}
5352
53// Return the buffer holding block (dev, blockno) if bucket bk
54// has one, or 0. The caller holds the lock that protects bk.
55static struct buf *
56bfind(struct bucket *bk, uint dev, uint blockno)
57{
58 struct buf *b;
59
60 for (b = bk->first; b != 0; b = b->next)
61 if (b->dev == dev && b->blockno == blockno)
62 return b;
63 return 0;
64}
65
66// Remove b from bucket bk's list.
67static void
68bunlink(struct bucket *bk, struct buf *b)
69{
70 struct buf *p;
71
72 if (bk->first == b) {
73 bk->first = b->next;
74 return;
75 }
76 for (p = bk->first; p->next != b; p = p->next)
77 ;
78 p->next = b->next;
79}
80
5481// Look through buffer cache for block on device dev.
5582// If not found, allocate a buffer.
5683// In either case, return locked buffer.
5784static struct buf *
5885bget(uint dev, uint blockno)
5986{
87 struct bucket *bk = &bcache.bucket[blockno % NBUCKET];
6088 struct buf *b, *victim;
89 int i, vi;
6190
6291 acquire(&bcache.lock);
6392
6493 // Is the block already cached?
65 for (b = bcache.head.next; b != &bcache.head; b = b->next) {
66 if (b->dev == dev && b->blockno == blockno) {
67 b->refcnt++;
68 release(&bcache.lock);
69 acquiresleep(&b->lock);
70 return b;
71 }
94 if ((b = bfind(bk, dev, blockno)) != 0) {
95 b->refcnt++;
96 release(&bcache.lock);
97 acquiresleep(&b->lock);
98 return b;
7299 }
73100
74101 // Not cached.
75 // Recycle the least recently used (LRU) unused buffer:
76 // the one whose last release has the oldest time stamp.
102 // Recycle the least recently used (LRU) unused buffer,
103 // in whichever bucket it is.
77104 victim = 0;
78 for (b = bcache.head.next; b != &bcache.head; b = b->next) {
79 if (b->refcnt == 0 && (victim == 0 || b->lastuse < victim->lastuse))
80 victim = b;
105 vi = 0;
106 for (i = 0; i < NBUCKET; i++) {
107 for (b = bcache.bucket[i].first; b != 0; b = b->next) {
108 if (b->refcnt == 0 && (victim == 0 || b->lastuse < victim->lastuse)) {
109 victim = b;
110 vi = i;
111 }
112 }
81113 }
82114 if (victim == 0)
83115 panic("bget: no buffers");
116
117 // Move it to the bucket of the block it will hold.
118 bunlink(&bcache.bucket[vi], victim);
84119 victim->dev = dev;
85120 victim->blockno = blockno;
86121 victim->valid = 0;
87122 victim->refcnt = 1;
123 victim->next = bk->first;
124 bk->first = victim;
88125 release(&bcache.lock);
89126 acquiresleep(&victim->lock);
90127 return victim;
91128}
kernel/buf.h
@@ -5,8 +5,7 @@ struct buf {
55 uint blockno;
66 struct sleeplock lock;
77 uint refcnt;
88 uint lastuse; // ticks when refcnt last dropped to 0
9 struct buf *prev; // LRU cache list
10 struct buf *next;
9 struct buf *next; // next buffer in the same hash bucket
1110 uchar data[BSIZE];
1211};
00401be Give each bucket its own lock
kernel/bio.c
@@ -24,14 +24,18 @@
2424
2525#define NBUCKET 13 // a prime, so block numbers spread over all buckets
2626
2727// A block can only be cached in bucket[blockno % NBUCKET].
28// A bucket's lock protects its list and the dev, blockno, refcnt
29// and lastuse of every buffer on it.
2830struct bucket {
31 struct spinlock lock;
2932 struct buf *first; // list of buffers, through buf.next
3033};
3134
35// Lock order: evict, then bucket locks in increasing index order.
3236struct {
33 struct spinlock lock;
37 struct spinlock evict; // held by a miss while it recycles a buffer
3438 struct buf buf[NBUF];
3539 struct bucket bucket[NBUCKET];
3640} bcache;
3741
@@ -39,9 +43,11 @@ void
3943binit(void)
4044{
4145 struct buf *b;
4246
43 initlock(&bcache.lock, "bcache");
47 initlock(&bcache.evict, "bcache.evict");
48 for (int i = 0; i < NBUCKET; i++)
49 initlock(&bcache.bucket[i].lock, "bcache.bucket");
4450
4551 // Every buffer starts with blockno 0, so in bucket 0.
4652 for (b = bcache.buf; b < bcache.buf + NBUF; b++) {
4753 initsleeplock(&b->lock, "buffer");
@@ -50,9 +56,9 @@ binit(void)
5056 }
5157}
5258
5359// Return the buffer holding block (dev, blockno) if bucket bk
54// has one, or 0. The caller holds the lock that protects bk.
60// has one, or 0. The caller holds bk's lock.
5561static struct buf *
5662bfind(struct bucket *bk, uint dev, uint blockno)
5763{
5864 struct buf *b;
@@ -62,9 +68,9 @@ bfind(struct bucket *bk, uint dev, uint blockno)
6268 return b;
6369 return 0;
6470}
6571
66// Remove b from bucket bk's list.
72// Remove b from bucket bk's list. The caller holds bk's lock.
6773static void
6874bunlink(struct bucket *bk, struct buf *b)
6975{
7076 struct buf *p;
@@ -85,45 +91,78 @@ static struct buf *
8591bget(uint dev, uint blockno)
8692{
8793 struct bucket *bk = &bcache.bucket[blockno % NBUCKET];
8894 struct buf *b, *victim;
89 int i, vi;
95 int i, vi, better;
96
97 // Is the block already cached? Only its own bucket can hold it.
98 acquire(&bk->lock);
99 if ((b = bfind(bk, dev, blockno)) != 0) {
100 b->refcnt++;
101 release(&bk->lock);
102 acquiresleep(&b->lock);
103 return b;
104 }
105 release(&bk->lock);
90106
91 acquire(&bcache.lock);
107 // Not cached. Only one miss at a time may recycle a buffer.
108 acquire(&bcache.evict);
92109
93 // Is the block already cached?
110 // Look again: while this hart held no lock, another hart may
111 // have missed on the same block and cached it. Only a miss adds
112 // a block to a bucket, so while evict is held, the answer stays
113 // true.
114 acquire(&bk->lock);
94115 if ((b = bfind(bk, dev, blockno)) != 0) {
95116 b->refcnt++;
96 release(&bcache.lock);
117 release(&bk->lock);
118 release(&bcache.evict);
97119 acquiresleep(&b->lock);
98120 return b;
99121 }
122 release(&bk->lock);
100123
101 // Not cached.
102124 // Recycle the least recently used (LRU) unused buffer,
103 // in whichever bucket it is.
125 // in whichever bucket it is. Keep holding the lock of the
126 // bucket with the best buffer so far, so that no lookup can
127 // take that buffer while the later buckets are searched.
104128 victim = 0;
105 vi = 0;
129 vi = -1;
106130 for (i = 0; i < NBUCKET; i++) {
131 acquire(&bcache.bucket[i].lock);
132 better = 0;
107133 for (b = bcache.bucket[i].first; b != 0; b = b->next) {
108134 if (b->refcnt == 0 && (victim == 0 || b->lastuse < victim->lastuse)) {
109135 victim = b;
110 vi = i;
136 better = 1;
111137 }
112138 }
139 if (better) {
140 if (vi >= 0)
141 release(&bcache.bucket[vi].lock);
142 vi = i;
143 } else {
144 release(&bcache.bucket[i].lock);
145 }
113146 }
114147 if (victim == 0)
115148 panic("bget: no buffers");
116149
117 // Move it to the bucket of the block it will hold.
150 // Take it out of its bucket. Now no lookup can find it, and
151 // nobody holds it (refcnt is 0), so it is ours alone.
118152 bunlink(&bcache.bucket[vi], victim);
153 release(&bcache.bucket[vi].lock);
154
155 // Put it in the bucket of the block it will hold.
156 acquire(&bk->lock);
119157 victim->dev = dev;
120158 victim->blockno = blockno;
121159 victim->valid = 0;
122160 victim->refcnt = 1;
123161 victim->next = bk->first;
124162 bk->first = victim;
125 release(&bcache.lock);
163 release(&bk->lock);
164 release(&bcache.evict);
126165 acquiresleep(&victim->lock);
127166 return victim;
128167}
129168
@@ -155,8 +194,9 @@ bwrite(struct buf *b)
155194// If no one else wants it, record when it was last used.
156195void
157196brelse(struct buf *b)
158197{
198 struct bucket *bk;
159199 uint now;
160200
161201 if (!holdingsleep(&b->lock))
162202 panic("brelse");
@@ -166,28 +206,36 @@ brelse(struct buf *b)
166206 acquire(&tickslock);
167207 now = ticks;
168208 release(&tickslock);
169209
170 acquire(&bcache.lock);
210 // b cannot move to another bucket before the decrement:
211 // a miss recycles only buffers with refcnt 0.
212 bk = &bcache.bucket[b->blockno % NBUCKET];
213 acquire(&bk->lock);
171214 b->refcnt--;
172215 if (b->refcnt == 0) {
173216 // no one is waiting for it.
174217 b->lastuse = now;
175218 }
176 release(&bcache.lock);
219 release(&bk->lock);
177220}
178221
222// The caller holds b (refcnt > 0), so b stays in its bucket.
179223void
180224bpin(struct buf *b)
181225{
182 acquire(&bcache.lock);
226 struct bucket *bk = &bcache.bucket[b->blockno % NBUCKET];
227
228 acquire(&bk->lock);
183229 b->refcnt++;
184 release(&bcache.lock);
230 release(&bk->lock);
185231}
186232
187233void
188234bunpin(struct buf *b)
189235{
190 acquire(&bcache.lock);
236 struct bucket *bk = &bcache.bucket[b->blockno % NBUCKET];
237
238 acquire(&bk->lock);
191239 b->refcnt--;
192 release(&bcache.lock);
240 release(&bk->lock);
193241}
ace999b Read the clock without tickslock in brelse
kernel/bio.c
@@ -202,11 +202,13 @@ brelse(struct buf *b)
202202 panic("brelse");
203203
204204 releasesleep(&b->lock);
205205
206 acquire(&tickslock);
207 now = ticks;
208 release(&tickslock);
206 // Read the clock without tickslock, which every brelse on
207 // every hart would otherwise take. A value one tick old only
208 // makes the LRU choice a little less exact. The atomic load is
209 // a single 32-bit load that the compiler cannot split or repeat.
210 now = __atomic_load_n(&ticks, __ATOMIC_RELAXED);
209211
210212 // b cannot move to another bucket before the decrement:
211213 // a miss recycles only buffers with refcnt 0.
212214 bk = &bcache.bucket[b->blockno % NBUCKET];

6. Verify and measure

On the branch (ext/19-bcache-hash, 5 commits), built with the project toolchain and run on 3 harts (-smp 3 -m 128M), one boot:

$ bcachetest
bcachetest: private files: OK
bcachetest: one shared file: OK
bcachetest: small files: OK
bcachetest: allocating together: OK
bcachetest: ALL OK
$ usertests -q
usertests starting
test copyin: OK
test copyout: OK
[...]
test kernmem: usertrap(): unexpected scause 0xd pid=6489
[...]
ALL TESTS PASSED
$ bcachetest
bcachetest: private files: OK
bcachetest: one shared file: OK
bcachetest: small files: OK
bcachetest: allocating together: OK
bcachetest: ALL OK

The usertrap() lines are usertests checking that bad accesses kill the process, as on the original kernel. The same sequence (bcachetest, usertests -q, bcachetest) passed at every commit of the branch, each built on its own, and the original kernel with only commit 1’s test passes it too. Instrumented copies of the head passed the same bcachetest and usertests -q on the 4 boots used for “Measure” and the lock-order run, and bcachetest 1 on the 2 boots traced with gdb for the reveal.

What this demonstrates: the cache still returns the right bytes for every block under heavy concurrent use (every block of every file is compared), usertests -q sees no difference, and nothing leaks (usertests checks free pages; a leaked refcnt would end in bget: no buffers). It does not demonstrate the absence of races: Clinic 2 shows the test missing a real race in most runs. The lock-order argument and the measurements below carry that part.

How. A measurement copy of each kernel (not on the branch) counts, in acquire, how many times amoswap found the lock taken before it got it, per lock and per hart, in per-hart tables that need no lock of their own. Ctrl-P prints the totals and resets them. The same copy counts bread calls and disk reads. Each kernel was booted three times, three harts each, on a computer busy with other work (your numbers will differ). Workload: boot plus one bcachetest, then usertests -q. “Contended” counts acquisitions that had to spin at least once; total spins are dominated by a few long waits (a holder whose QEMU thread the host paused), so they are given only for comparison within a run.

Lock waits during boot + bcachetest (contended acquisitions, three boots):

lock	original	commit 4	branch (commit 5)
`bcache.lock`	387, 286, 397
the 13 bucket locks		71, 63, 78	75, 84, 70
`bcache.evict`		22, 33, 33	30, 29, 28
`tickslock` (`time`)	19, 19, 0	145, 153, 195	12, 8, 11
for scale: `disk.vdisk_lock`	8,810, 9,215, 9,492	9,701, 10,161, 9,491	9,367, 9,316, 9,208

The split works. Waits on the cache’s own locks fell from about 360 per run to about 105 (bucket locks plus evict), although the locks are taken more often: about 357,000 bucket and 7,500 evict acquisitions against 244,000 of bcache.lock, because every miss now locks all 13 buckets in turn.
Waits moved, they did not vanish. Bucket waits are short (about 5,000 spins per run against 14,000 to 19,000 for bcache.lock), but a miss that waits on evict waits for another miss’s whole search: about 20,000 spins per run over only about 30 waits.
Commit 4 created a new hot lock. tickslock, taken by every brelse, was waited for more often than all bucket locks together. Commit 5 removed tickslock from that read, and tickslock went back to what the original kernel shows.
Hashing spreads blocks, not accesses. Bucket 8 alone took 161,533, 166,769 and 162,816 of the bucket acquisitions (about 46%) and 50, 64 and 54 of the waits (about 70%). Two of the hottest blocks hash there: block 47, the root directory’s data, read by every lookup of a name in the root directory, and block 34, the inode block that holds the test’s first new files (inodes 16 to 31). They share bucket 8 only because of the modulus (with 17 buckets they would land in 13 and 0), so more buckets or another hash could separate them, but not the waits on block 47 itself: a block that everybody wants needs a different idea (see “Further”).
The cache was never the bottleneck here. The disk lock is waited for about 9,000 times per run in every kernel, roughly 25 times more than bcache.lock was. On three QEMU harts with a RAM-backed disk, splitting bcache.lock removes a real but small queue; we did not measure a change in run time.

During usertests -q there is little to remove: its tests mostly run one at a time. bcache.lock was waited for 2, 4 and 11 times; the bucket locks 1, 0 and 11 times, and evict never.

Hit rate. The time-stamp LRU behaves like the original list: disk reads were 7,538 to 7,599 (original) and 7,489 to 7,606 (branch) for boot + bcachetest, out of about 120,000 bread calls, and 1,082 to 1,091 against 1,075 to 1,115 for usertests -q, out of about 210,000. Without the stamp (Clinic 4) the same workloads needed 12,202 to 13,050 and 15,418 to 18,497 reads.

Lock order. The recorder from Tour 51: The lock-order graph, measured on the same workload: every new edge goes from evict into a bucket, from a bucket into a higher bucket (81,822 times, all in the search loop), or from something that already came before bcache.lock into a bucket or evict. Maximum spinlock nesting is still 3, with one new path to it (evict → bucket → bucket); maximum sleep-locks held at once is still 3. The last reveal step has the table.

7. Go further

A finer clock. ticks advances 10 times a second, so most stamps tie. The time register is readable from S-mode in this tree (start sets mcounteren, and clockintr reads it with r_time()), ticks at 10 MHz and needs no lock at all. Use it for lastuse and measure the hit rate again: does real LRU beat “first in bucket order within a tick” on these workloads?
Misses in parallel. bcache.evict makes misses wait for each other’s whole search. Remove it: lock the victim’s bucket and the destination bucket in index order, look again, and start over if the victim was taken meanwhile. Then argue that duplicates and deadlock are still impossible, and measure whether the extra complexity buys anything.
Hot buckets. Bucket 8 took 70% of the bucket waits because two hot blocks live there. Try a different hash, more buckets, or caching the root directory’s block outside the table, and measure which helps; then explain which part of the waiting none of them can remove.
False sharing. The 13 bucket locks are 32 bytes apart, two per 64-byte cache line. Pad each bucket to a full line and measure whether a hart spinning on one lock slows the hart that owns its neighbour (on QEMU, perhaps not; on real hardware, yes).
Wait instead of panic. When every buffer is in use, bget still panics. Make a miss sleep until some buffer’s refcnt drops to 0, and find the lock and the channel that make the wakeup impossible to lose.