Lab 19 · reveal · 15 steps · 5 commits
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.
Each step shows one change on the branch ext/19-bcache-hash, the code around it, and the state of the machine when that code runs.
user/bcachetest.cStep 1 of 15 · commit 1: Add bcachetest, a parallel buffer-cache stress test
The story of this tour: bcachetest 1 (pid 3) recorded on the finished branch with gdb
attached, in its first check, where its children pids 4, 5 and 6 create and fill the
files bcp0, bcp1 and bcp2. Most states below come from that run; where a step’s
state is reasoned from the code instead, it says so.
Commit 1 is the test alone, and it passes on the original kernel. Three of its four checks are plain stress: big private files, one shared file, many small files, every byte compared. The fourth, shown here, is aimed at the one race this lab can create: two harts missing on the same block at the same moment.
That is harder to provoke than it sounds. Most blocks are only ever read under one
inode’s sleep-lock, which serializes the readers before they reach the cache: three
readers of one file never miss on its blocks together. The free-block bitmap is
different. Every process that grows a file calls balloc, which reads the bitmap
while holding only its own file’s inode lock. So: three children, each appending to
its own file in its own directory (its working directory, so that path lookups do not
share a directory lock either). Before each round the parent waits for a clock tick and
reads a 40-block file, which pushes the bitmap out of the 30-buffer cache; then it
writes one byte into each child’s pipe, and all three allocate a block at once. In the
end each child reads its file back and compares every byte; the first eight bytes of
each block name the file and block it belongs to.
Clinic 2 shows how often this catches the race when the code has it: sometimes. A test that passes is evidence, not proof.
Step 2 of 15 · commit 2: Recycle the buffer with the oldest release time
The LRU list says “how recently was this buffer used” by its position, and keeping
positions up to date means touching the global list on every release. Commit 2 says it
with a number instead: lastuse, the value of ticks when the buffer’s refcnt last
dropped to 0.
This commit still has one lock and one list; it changes only the policy’s
representation, so that the next commits can break the list apart. The prev/next
links stay for now (commit 3 replaces them with one next per bucket).
the directory's ip->lock (sleep-lock)bcache.lockkernel/bio.cStep 3 of 15 · commit 2: Recycle the buffer with the oldest release time
The six lines that moved the buffer to the front of the list are gone; when refcnt
reaches 0, brelse stores the time instead. (State reasoned from the code: this
commit was not traced, but the recorded run at commit 5 passes through this same
brelse from the same call, a dirlookup inside create.)
Two locks are taken one after the other, never nested: tickslock for three lines to
read ticks (kernel/trap.c:10), as sys_uptime does, then bcache.lock for the
decrement. Reading the clock before bcache.lock keeps the two locks from ever being
held together, so this adds no spinlock-to-spinlock edge. (The caller’s sleep-locks, an
inode’s or a buffer’s, are held during brelse, so it does add sleep-lock →
tickslock edges, which cannot form a cycle: nothing holding tickslock ever waits
for a sleep-lock.)
The stamp is written only when refcnt reaches 0, the moment the buffer becomes a
candidate for recycling. A buffer released while the log still pins it keeps its old
stamp until the last release after the commit (install_trans unpins, then
brelse brings it to 0).
bcp1's ip->lock (sleep-lock)bcache.lockkernel/bio.cStep 4 of 15 · commit 2: Recycle the buffer with the oldest release time
The recycling scan now visits all 30 buffers and keeps the unused one with the
smallest stamp, instead of walking backwards from the list’s tail and taking the first
unused buffer. Same idea, different bookkeeping: the work moves from every release to
the rare miss. (State reasoned from the code: a miss in balloc on the bitmap, as in
the traced run later.)
Two details that matter later:
<, so among equal stamps the first one in scan order wins. With
a clock that ticks 10 times a second, ties are common.bcache.lock: the lookup, the scan and the
relabeling are one critical section, which is what keeps a block from being cached
twice. The next two commits will break that critical section apart and have to
rebuild the guarantee.stack0hart 0’s slice of stack0kernel/bio.cStep 5 of 15 · commit 3: Hash the buffers into 13 buckets
The list becomes a hash table. Bucket i holds every buffer whose blockno % 13 is
i, linked through next (struct buf loses prev in this commit). That rule is
the invariant everything else leans on: a buffer is always in the bucket of its
current blockno.
binit puts all 30 buffers into bucket 0, which is right because their blockno
starts at 0 (bcache is a global, zeroed at boot). Over time, recycling moves them
where their blocks hash.
gdb stopped in this loop at boot (in the commit 5 build, whose loop is the same): hart
0, no process yet, noff 0, on the boot stack, with paging already on. main calls
binit before the other harts are released, so no lock is needed here.
Still one lock, bcache.lock: this commit changes only the data structure, so a bug
here is a list bug, not a race.
bcp1's ip->lock (sleep-lock)bcache.lockkernel/bio.cStep 6 of 15 · commit 3: Hash the buffers into 13 buckets
A lookup now searches one bucket (line 94 calls bfind on bucket
blockno % 13). A miss still scans every bucket for the oldest unused buffer, then
bunlinks it from its bucket and pushes it onto the front of the new block’s bucket.
(State reasoned from the code.)
Under one lock all of this is atomic, so nothing new can go wrong yet. Read the miss as a list of things that will need protection once there are 13 locks:
bk;bk.Steps 1 and 4 involve one bucket, steps 2 and 3 others. That is the whole problem of commit 4.
kernel/bio.cStep 7 of 15 · commit 4: Give each bucket its own lock
Each bucket gets a spinlock, named bcache.bucket; bcache.lock becomes
bcache.evict, now held only by misses. The comments state the two rules the rest of
the commit follows:
dev, blockno, refcnt and lastuse of
every buffer on it.evict first, then bucket locks in increasing index order.In this build bcache is at 0x800157f8: evict (24 bytes), the 30 buffers (1,104
bytes each, one less pointer than before), then the 13 buckets of 32 bytes from
0x8001d970. The bucket locks are 32 bytes apart, so several share a 64-byte cache
line (see “Further”).
sp = 0x3fffff7d70the root directory's ip->lock (sleep-lock)bucket 8's lockkernel/bio.cStep 8 of 15 · commit 4: Give each bucket its own lock
Recorded with gdb (in the commit 5 build; bget is unchanged since this commit): pid
4, creating its file, looks up a name in the root directory. dirlookup reads block
47, the root directory’s first data block, which hashes to bucket 8. Buffer 14 holds
it with refcnt 0: a hit. The hart holds bucket 8’s lock and nothing else: noff 1,
intena 1 (taken in a system call after usertrap's intr_on).
Same five steps as the original hit, with the bucket lock in place of
bcache.lock: lock, find, refcnt++, unlock, acquiresleep. The order of the
middle two is the rule from Tour 30: The buffer cache: once the lock is released, only the raised
refcnt keeps a miss on another hart from recycling this buffer.
Note the comment on line 97: “Only its own bucket can hold it.” That sentence is the reason a hit needs no other lock.
sp = 0x3fffff5dd0bcp1's ip->lock (sleep-lock)bcache.evictbucket 7's lockStep 9 of 15 · commit 4: Give each bucket its own lock
pid 5 appends to its file; balloc reads block 46, the bitmap, which hashes to
bucket 7, and the lookup misses. Line 105 releases bucket 7 before anything else:
the miss is about to lock other buckets, and holding bucket 7 meanwhile is exactly
the out-of-order hold that deadlocked in Clinic 1.
Then evict (line 108), and the second look (lines 114-121). While pid 5 held no lock,
another hart could have missed on block 46 too and inserted it; if so, this look finds
it and uses it like a hit. Only a hart holding evict can insert, so the answer of
this look stays true until pid 5 releases evict. (The state shown, at line 115, is
reasoned from the code: evict and bucket 7, noff 2. In our traced runs the second
look never found the block; gdb recorded the same depth a few lines later, at the
start of the search, with bucket 0 held instead of bucket 7.)
bcp1's ip->lock (sleep-lock)bcache.evictbucket 0's lockbucket 1's lockStep 10 of 15 · commit 4: Give each bucket its own lock
gdb stopped pid 5 at line 132 with i = 1 and vi = 0: bucket 0 held because it
contains the best candidate so far (buffer 17, holding block 1014, stamp 2), bucket 1
just acquired. cpus[2].noff = 3, intena 1, SIE 0. That ties the deepest nesting this
kernel had before (3, in kwait; Tour 51: The lock-order graph, measured), and now it happens on most misses.
The loop’s discipline:
vi only ever
waits for a bucket with a higher index;vi and i;i makes i the new vi and releases the old one;
otherwise i is released at once.Holding vi is not optional. Without it, a hit on another hart could take the
candidate between “its refcnt is 0” and the unlink below.
bcp1's ip->lock (sleep-lock)bcache.evictbucket 7's lockStep 11 of 15 · commit 4: Give each bucket its own lock
The search ended with vi = 7: the oldest unused buffer was buffer 13, holding block
189 with stamp 1, which happens to live in bucket 7, the destination too (189 % 13 =
7). gdb recorded the unlink with evict and bucket 7 held (noff 2), then the insert at
line 157 with evict and bucket 7 again, then line 164 with only evict (noff 1) and
buffer 13 relabeled: block 46, refcnt 1.
Between line 153 and line 156 the buffer is on no list, and the hart holds no bucket
lock at all. That is safe: no lookup can find a buffer that is on no list, nobody
holds it (its refcnt was 0), and no other miss can run (this hart holds evict).
Line 164 releases evict before acquiresleep, for the same reason as
bcache.lock in the original: acquiresleep may sleep, and sched panics if a
process sleeps holding a spinlock. The raised refcnt keeps the buffer safe in the
gap.
sp = 0x3fffff7db0the root directory's ip->lock (sleep-lock)bucket 8's lockkernel/bio.cStep 12 of 15 · commit 4: Give each bucket its own lock
brelse reads b->blockno before it holds any bucket lock and uses it to pick the
lock. The comment says why that is safe: the caller still holds the buffer (refcnt ≥
1), and a miss only recycles buffers with refcnt 0, so blockno and therefore the
bucket cannot change before the decrement on line 214.
Recorded: pid 4 releasing block 47 after the hit two steps back, bucket 8 held, noff 1, intena 1 (in the commit 5 build, whose lines here are the same except for the clock read just above).
In this commit the clock is still read under tickslock (lines 206-208). That is what
the measurement after this commit caught.
the root directory's ip->lock (sleep-lock)inode block 34's b->lock (sleep-lock)log.lockbucket 8's lockStep 13 of 15 · commit 4: Give each bucket its own lock
log_write pins a block the first time it joins a transaction, holding log.lock.
gdb recorded pid 4 (now on hart 2: it had given up the CPU in between and resumed on
another hart) pinning block 34, the inode
block for its new file, from ialloc: log.lock and bucket 8 held, noff 2, intena 1.
The old edge log.lock → bcache.lock (Tour 51: The lock-order graph, measured, edge 13) becomes log.lock →
bcache.bucket.
Like brelse, bpin computes the bucket from blockno without a lock, safe because
log_write's caller holds the buffer. bunpin is called by install_trans,
which holds the buffer it unpins (it just read it with bread); gdb recorded pid 6
unpinning block 34 there, bucket 8 held, noff 1.
Is the new edge safe? Nothing holding a bucket lock ever takes log.lock (or anything
but another bucket, during the search). A bucket lock is a leaf apart from that one
ordered bucket-to-bucket step.
the root directory's ip->lock (sleep-lock)kernel/bio.cStep 14 of 15 · commit 5: Read the clock without tickslock in brelse
Commit 5 is one line. After commit 4, tickslock was the most contended lock on the
cache path, because every brelse on every hart took it. The stamp only chooses
among unused buffers, so a value one tick stale is harmless, and ticks is an aligned
32-bit word written only by hart 0: a relaxed atomic load is enough. In this build it
is lw s3,0(a5) at 0x80002e5c; the increment it races with in clockintr is
lw/addiw/sw at 0x8000253a-0x8000253e, under tickslock.
State at these lines (reasoned): releasesleep has just dropped its lk->lk, no
spinlock is held, so noff is 0 and interrupts are back on, as they always are in a
system call outside a critical section. The directory’s sleep-lock does not count.
An interrupt here is harmless: nothing is held.
Step 15 of 15 · commit 5: Read the clock without tickslock in brelse
What the lock-order recorder from Tour 51: The lock-order graph, measured measured on this branch (boot,
bcachetest, usertests -q, on 3 harts), compared with the same workload on the
original kernel:
| edge (A held while B acquired) | original | branch |
|---|---|---|
log.lock → bcache.lock / a bucket (bpin) |
7,797 | 8,741 |
inode sleep-lock → bcache.lock / a bucket |
728,225 | 809,134 |
buffer sleep-lock → bcache.lock / a bucket |
61,446 | 82,023 |
bcache.evict → a bucket (bget, lines 114, 131 and 156) |
121,905 | |
| a bucket → a higher bucket (line 131 only) | 81,822 | |
inode / buffer sleep-lock → bcache.evict |
6,259 / 932 |
(All bucket locks share one name, so the recorder sees “bucket → bucket”; the code guarantees the second index is higher.) The recorder found 41 distinct edges, against 37 on the original kernel: the four new ones are the last three rows.
Every new edge points from evict into a bucket, from a bucket into a higher bucket,
or from something that already preceded bcache.lock into a bucket or into evict.
No bucket lock is
ever held while anything other than a higher bucket is acquired, so no cycle can pass
through them.
The deepest spinlock nesting is still 3, but there is a new path to it: evict → bucket
→ bucket, 81,822 times in the run, every one of them in the search loop.
Lab 19 · wrap-up
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.
Keys: ← → step · Home start