Step 1 of 19

Both children need a free block

f1 is empty, so writei asks bmap for file block 0, and bmap finds no block there and calls balloc. To find a free disk block, balloc reads the free-block bitmap, one bit per block (free bitmap). With 2,000 blocks and 8,192 bits per block, the whole bitmap fits in one block: BBLOCK(0, sb) = sb.bmapstart = 46.

So child A calls bread(1, 46), holding only its own inode’s sleep lock.

At almost the same moment, child B on hart 2 does exactly the same thing for f2. The two children hold different inode locks (inodes 24 and 25), so nothing has serialized them yet. The bitmap block is the first thing they share.

Step 2 of 19

Thirty buffers and a list

The whole cache is one global structure, bcache (at 0x800157e8 in this build):

• buf[NBUF]: 30 buffers (NBUF = MAXOPBLOCKS * 3), each holding one block.
• head: a dummy buffer that anchors a circular doubly linked list through all 30. head.next is the most recently used, head.prev the least recently used.
• lock: one spinlock for the cache’s bookkeeping.

There is no hash table: finding a block means walking the list. With 30 entries that is cheap, and it keeps the code short.

The 30 buffers are statically allocated; there is no kalloc here. If all 30 are in use, the cache cannot grow. That is the source of the panic at the end of this tour.

Step 3 of 19

What a buffer knows

Each buf has two kinds of fields, protected by two different locks:

This split is the key to the whole file. The spinlock bcache.lock is held for a few instructions, to look things up and count users. The sleep-lock b->lock is held for a long time, possibly across a disk read, by the one thread using the block’s contents.

Step 4 of 19

At boot, the list is built backwards

Long before our scenario, hart 0 ran binit during boot. It makes head point to itself, then inserts each buffer at the front of the list, from buf[0] to buf[29]. The result: head.next is buf[29] and head.prev (the least recently used end) is buf[0].

All buffers start with refcnt = 0 and valid = 0 (bcache is a global with no initializer, so it starts zeroed), so the first miss after boot recycles buf[0], the second buf[1], and so on. Each buffer also gets its sleep-lock initialized, named “buffer”.

Step 5 of 19

Child A scans the cache

bget takes bcache.lock (interrupts off on hart 1) and walks the list from the most recently used end, looking for device 1, block 46.

Block 46 is not there. Since boot, the cache has held the superblock, the log header, the inode blocks, the root directory and pieces of programs, but nobody has allocated a block yet, so nobody has needed the bitmap.

Searching from the most recent end is a small optimization: blocks that were just used are the ones most likely to be wanted again.

Step 6 of 19

A miss recycles the least recently used free buffer

Now bget walks backwards from head.prev, the least recently used buffer, looking for one with refcnt == 0: a buffer nobody holds, nobody waits for and the log has not pinned. The first one found becomes block 46:

• dev = 1, blockno = 46: from now on, any scan finds this buffer as block 46.
• valid = 0: its data still holds the old block’s bytes, which must not be mistaken for the bitmap.
• refcnt = 1: child A’s claim.

All of this happens under bcache.lock, so no other hart can see a half-relabeled buffer. Then line 82 releases bcache.lock, and line 83 takes the buffer’s sleep-lock with acquiresleep. The order is forced: acquiresleep may sleep, and sleeping with bcache.lock held would leave noff at 2 and trip sched's sched locks panic. The raised refcnt keeps the buffer from being recycled in the gap (Locks and interrupt state). In our timing child A gets it at once: the buffer had refcnt == 0, so nobody held its sleep-lock (step 15 shows why). Nothing forces A to win, though. If A were preempted between lines 82 and 83, B could take the sleep-lock first, see valid == 0, and do the disk read itself. The result would be the same: whoever gets the lock first reads the block.

Recycling a buffer never writes the old contents to disk. In xv6 a buffer with unwritten changes is always pinned by the log (refcnt > 0), so a recyclable buffer is always clean.

Step 7 of 19

Child B finds A's buffer

Hart 2 gets bcache.lock as soon as hart 1 releases it, and scans. This time block 46 is in the list: child A labeled it a moment ago, even though its data has not been read yet.

Child B increments refcnt to 2, releases bcache.lock, and calls acquiresleep.

The increment happens before the spinlock is released, and that ordering matters. refcnt is how the recycler knows a buffer is wanted. If B released bcache.lock first and incremented later, there would be a window where B is about to use the buffer but refcnt does not show it.

Step 8 of 19

Child B sleeps on the buffer's lock

Inside acquiresleep, child B takes the sleep-lock’s own small spinlock, lk->lk, and finds locked == 1: child A owns the buffer. So B registers to wait with sleep_prepare(lk), releases lk->lk, and calls sleep. Hart 2 is free to run something else (Tour 17: Sleep-locks). Sleeping is legal because B’s only spinlock, lk->lk, was released first; f2’s inode lock is a sleep-lock, which noff does not count (Locks and interrupt state).

This is the moment a sleep-lock earns its keep. Child A is about to wait for the disk, which takes far longer than a context switch. If buffers were protected by spinlocks, child B would burn hart 2, with interrupts off, for the whole disk read.

Notice what B is holding while it sleeps: f2’s inode lock. That is fine. Anybody who wants f2 will wait for B, and B waits for A, and A waits only for the disk. Waiting chains are safe as long as they never form a cycle, and xv6 always takes an inode lock before the buffer locks under it, never the other way around.

What B leaves behind is its half-finished write, on its own kernel stack (The stacks of xv6). sleep calls sched, and swtch saves B’s registers in p->context and loads hart 2’s scheduler stack (kernel/swtch.S:26). B’s stack keeps every frame:

child B's kernel stack, while it sleeps on the buffer's lock
  top ─► usertrap · syscall · sys_write · filewrite · writei
         bmap · balloc · bread (bget is inlined into it in this build) · acquiresleep
         sleep · sched                ← p->context.sp points here

A sleep-lock costs no hart while it waits precisely because a whole call chain can be parked on a kernel stack like this. Hart 2 moves on with nothing of B’s on its own stack.

Step 9 of 19

Child A reads the bitmap from disk

Back on hart 1, bread sees valid == 0 and calls virtio_disk_rw to read block 46. Tour 29: A disk read, end to end follows that read in full: child A sleeps until the disk interrupt, still holding the buffer’s sleep-lock, and wakes with the bitmap in data. bread sets valid = 1.

Now there are two sleepers involving this buffer: child A, waiting for the disk (channel: the buffer), and child B, waiting for child A (channel: the buffer’s sleep-lock). They are woken by different events.

While A waits for the disk, two kernel stacks are frozen at once, each in its own slot’s page: A’s ends in bread · virtio_disk_rw · sleep · sched, B’s in bread · acquiresleep · sleep · sched (bget is inlined into bread in this build). Harts 1 and 2 have switched to their scheduler stacks and are free for other work, and the disk interrupt will be taken on whatever stack some hart happens to be using (Tour 29: A disk read, end to end), never on A’s or B’s.

Step 10 of 19

Child A takes a block and pins the bitmap

In balloc, child A finds the first clear bit, bit 1006 in a fresh image (blocks 0–1005 were filled by mkfs), sets it in data, and calls log_write instead of writing the block to disk (Tour 31: The log: begin_op, commit and group commit).

log_write records “block 46 is part of this transaction” and, since 46 is new to the transaction, calls bpin: refcnt++ under bcache.lock. Now refcnt is 3: child A, child B, and the pin.

Why pin? The modified bitmap now exists only in this buffer. The disk still has the old bitmap until the transaction commits. If the buffer were recycled before then, the change would be lost. The pin is an extra reference that no process owns: it keeps refcnt above zero, so bget will not recycle the buffer, until the commit calls bunpin.

Lock order here: log.lock (taken in log_write), then bcache.lock. Nothing in xv6 takes them in the opposite order. (Locks and interrupt state)

Step 11 of 19

Child A releases the sleep-lock first

balloc is done with the bitmap and calls brelse. The first thing brelse does (kernel/bio.c:122) is releasesleep: clear locked and call wakeup(lk). Child B, asleep on that channel, becomes RUNNABLE.

Only after that does brelse touch refcnt. The order is deliberate: it keeps the rule that a buffer with refcnt == 0 is never locked (step 15).

Step 12 of 19

refcnt goes down, but the buffer stays put

Under bcache.lock, brelse decrements refcnt from 3 to 2. Only when it reaches 0, meaning nobody holds it, nobody waits for it and the log has not pinned it, does brelse move the buffer to the front of the list (lines 128–133): unlink it, then insert it right after head.

Here it is still 2 (child B and the pin), so the buffer stays where it is. That is harmless: bget only recycles buffers with refcnt == 0, so the list position of a buffer in use does not matter. What matters is where it lands when it is finally released.

When brelse returns, balloc calls bzero(dev, 1006), which reads block 1006 into another buffer, clears it and logs it: a second buffer pinned by the same transaction.

Step 13 of 19

Child B wakes to a valid buffer

Child B’s sleep returns, possibly on a different hart (hart 0, say). acquiresleep loops, finds locked == 0, takes the buffer, and bget returns.

Moving to hart 0 costs nothing, because B’s state was never on hart 2. Hart 0’s scheduler ran swtch, whose ld sp, 8(a1) (kernel/swtch.S:26) pointed sp at B’s parked kernel stack; sched and sleep returned on it, and the frames below them are exactly as B left them.

In bread, valid is now 1: child A’s read filled the buffer. No second disk read. That is the cache’s first job done: two processes wanted block 46 at the same time, and the disk was asked once.

In balloc, child B scans the bitmap as child A left it: bit 1006 is set, so it takes 1007. That is the cache’s second job: because there is only one copy of block 46 and only one holder at a time, B sees A’s change, and the two children cannot both take 1006.

B’s log_write finds 46 already in the transaction (log absorption), so it does not pin again. refcnt stays 2 (B and the pin).

Step 14 of 19

Child B releases; the pin keeps the buffer

Child B’s brelse releases the sleep-lock (nobody is waiting), then decrements refcnt from 2 to 1. The 1 is the pin. Nobody holds the buffer, but it still cannot be recycled, and brelse still does not move it to the head.

This is the state of block 46 until the commit: unlocked, unowned, dirty, pinned. Any process that calls bread(1, 46) before then, for example a third balloc, finds it with a quick scan, gets the modified data, and adds its own change on top. That is how a single transaction gathers changes from several processes (Tour 31: The log: begin_op, commit and group commit).

Step 15 of 19

Why a buffer with refcnt 0 is never locked

The recycler in bget relies on one invariant: if refcnt == 0, nobody holds, waits for, or is about to take the buffer’s sleep-lock. That is what lets it relabel a buffer without asking anyone.

Two orderings keep it true:

• Every thread increments refcnt under bcache.lock before it releases that lock and calls acquiresleep (lines 67–69 here, and 81–83 on the miss path).
• Every thread calls releasesleep before it decrements refcnt (lines 122 and 125 in brelse).

So each thread’s share of refcnt covers the whole time it holds or waits for the sleep-lock, and a recyclable buffer’s lock is always free. Now break the first rule: suppose child B released bcache.lock and only then incremented refcnt.

Child B would allocate blocks from a “bitmap” that is really some other block, and log it as block 46. Incrementing before releasing closes the t1–t2 window: from the moment B’s scan finds the buffer, refcnt counts B.

Step 16 of 19

The commit unpins and the buffer moves to the head

Later, when the transaction commits (Tour 31: The log: begin_op, commit and group commit), install_trans copies each logged block to its home location. For block 46:

1. bread(dev, 46): a cache hit (it was pinned), refcnt 1 → 2.
2. Copy in the data from the log block and bwrite it to block 46 on disk.
3. bunpin: refcnt 2 → 1. The disk now has the change, so the pin’s job is done.
4. brelse: refcnt 1 → 0, and now the buffer finally moves to the front of the LRU list.

A dirty buffer reaches refcnt == 0 only after it has been written home. That is why bget can recycle a zero-count buffer without ever writing it back.

Step 17 of 19

LRU in action

Every time a buffer’s count drops to zero, it goes to the front. So the list is always ordered by the time of each buffer’s last release:

The next miss anywhere takes the buffer at the tail with refcnt == 0, the least recently released one: an approximation of “the block least likely to be needed soon”. The first scan (for hits) starts at the front, where recently used blocks are; the recycling scan starts at the back.

Blocks 1006, 1007 and inode block 34 are still pinned at this instant (they come later in the log), so they have not moved; each jumps to the front as install_trans releases it.

(Simplified: buffers that are pinned or held are skipped by the recycling scan but keep their old list position, so the list is ordered by last release, not by last use.)

Step 18 of 19

When every buffer is busy

If the recycling scan reaches head again without finding refcnt == 0, all 30 buffers are held, waited for, or pinned, and xv6 gives up: panic("bget: no buffers"). There is no waiting for a buffer to free up.

What keeps this from happening? Partly sizing, partly luck. A running transaction pins at most LOGBLOCKS = 30 blocks, and each file-system operation holds only a few buffers at once (writei holds one data buffer, balloc one bitmap buffer). In a traced run of logstress f1 f2 f3 in this build, most commits pinned 12 to 16 buffers (never more than 16), and the panic never happened.

Notice that NBUF and LOGBLOCKS are both 30. A transaction that filled all 30 log slots would pin every buffer, and the commit’s own write_log would panic asking for a 31st. begin_op prevents that only indirectly. It admits an operation only while lh.n + 10 × (running operations) ≤ 30, so lh.n reaches 30 only if the operations running at the end each log a full 10 new blocks. By our count, no xv6 operation logs more than 7 (a 3,072-byte filewrite chunk: up to 4 data blocks, the bitmap, an indirect block and the inode block), so in this build a commit pins at most 27. Nothing bounds readers, though. read takes no begin_op, so 31 processes each waiting for a disk read of a different block would also hit this panic. The code relies on these margins; it does not enforce them.

Step 19 of 19

What the cache bought

Two children asked for block 46 at the same time. The cache read it from disk once, handed it to them one at a time, and kept the changed bitmap in memory, pinned, until the log made the change durable.

The cost: one pass for a hit and two for a miss, over a 30-entry list, under a global spinlock for every bread, and a sleep whenever another process holds the block you want. On three harts this is rarely a bottleneck. Larger systems split bcache.lock into per-bucket locks over a hash table, which is a well-known xv6 lab exercise.

The key ideas:

• At most one buffer per block, enforced by doing lookup and relabeling under one spinlock.
• Two locks with two jobs: bcache.lock (short, spinning) for the cache’s bookkeeping; b->lock (long, sleeping) for a block’s contents.
• refcnt counts claims, taken before the sleep-lock and dropped after it, so a zero count means nobody holds or waits for the buffer.
• Pins keep dirty buffers in the cache until the log has written them home.
• LRU: released buffers go to the front; misses recycle from the back.