The disk driver and the buffer cache

1warm-upType a number

cat needs file-system block 48, so virtio_disk_rw builds a request for it. Which sector number does it put in the request header?

kernel/virtio_disk.c

215void
216virtio_disk_rw(struct buf *b, int write)
217{
218  uint64 sector = b->blockno * (BSIZE / 512);

decimal, 0x hex or 0b binary

2solidType a number

The driver has NUM = 8 descriptors, and every request uses exactly three. At most how many disk requests can be in flight (handed to the device and not yet freed) at once?

kernel/virtio_disk.c

199// allocate three descriptors (they need not be contiguous).
200// disk transfers always use three descriptors.
201static int
202alloc3_desc(int *idx)
203{
204  for (int i = 0; i < 3; i++) {
205    idx[i] = alloc_desc();
206    if (idx[i] < 0) {
207      for (int j = 0; j < i; j++)
208        free_desc(idx[j]);
209      return -1;
210    }
211  }
212  return 0;
213}

decimal, 0x hex or 0b binary

3warm-upChoose one

In bread, what does it mean when bget returns a buffer with valid == 0?

kernel/bio.c

90// Return a locked buf with the contents of the indicated block.
91struct buf *
92bread(uint dev, uint blockno)
93{
94  struct buf *b;
95
96  b = bget(dev, blockno);
97  if (!b->valid) {
98    virtio_disk_rw(b, 0);
99    b->valid = 1;
100  }
101  return b;
102}

The buffer has been modified and must be written back to disk before reuse.The buffer is free, so nobody else is using it.The buffer’s data does not hold the block’s contents yet, so bread must read it from the disk.The disk currently owns the buffer and is transferring into it.

4warm-upChoose one

Why is each buffer’s lock (b->lock) a sleep-lock rather than a spinlock?

kernel/buf.h

1struct buf {
int valid; // has data been read from disk?
int disk;  // does disk "own" buf?
uint dev;
uint blockno;
struct sleeplock lock;
uint refcnt;
struct buf *prev; // LRU cache list
struct buf *next;
uchar data[BSIZE];
11};

So that the disk interrupt handler can take it when the transfer completes.Its holder may wait for a disk transfer, and a process must not sleep while holding a spinlock.Sleep-locks are faster than spinlocks for short critical sections.So that several processes can read the same buffer at once.

5warm-upTrue or false, and why

True or false: virtio_disk_rw holds disk.vdisk_lock while it sleeps waiting for the disk to finish.

kernel/virtio_disk.c

// Wait for virtio_disk_intr() to say request has finished.
while (b->disk == 1) {
  sleep_prepare(b);
  release(&disk.vdisk_lock);
  sleep();
  acquire(&disk.vdisk_lock);
}
293
disk.info[idx[0]].b = 0;
free_chain(idx[0]);
296
release(&disk.vdisk_lock);
298}

TrueFalse

Why?

It keeps it, so that no other hart can use the descriptors while the device works.It hands it to sleep(), which releases it after marking the process SLEEPING.It releases vdisk_lock between sleep_prepare(b) and sleep(), because the interrupt handler needs that lock to mark the request done, and sched forbids sleeping with a spinlock other than p->lock.

6solidPut in order

Put the steps of a disk read in virtio_disk_rw in order.

fill in the header, data and status descriptors
get three free descriptors with alloc3_desc
compute the sector and acquire disk.vdisk_lock
record b in disk.info[idx[0]] and set b->disk = 1
write idx[0] into the avail ring, fence, then increment avail->idx
store to the QUEUE_NOTIFY register
sleep until b->disk == 0, then free the chain

7solidClick the line

Most of the driver talks to the device through ordinary RAM that both share. Click the one line in this excerpt that writes to a device register (memory-mapped I/O): the doorbell.

kernel/virtio_disk.c

// record struct buf for virtio_disk_intr().
b->disk = 1;
disk.info[idx[0]].b = b;
273
// tell the device the first index in our chain of descriptors.
disk.avail->ring[disk.avail->idx % NUM] = idx[0];
276
io_fence();
278
// tell the device another avail ring entry is available.
disk.avail->idx += 1; // not % NUM ...
281
io_fence();
283
*R(VIRTIO_MMIO_QUEUE_NOTIFY) = 0; // value is queue number
285
// Wait for virtio_disk_intr() to say request has finished.
while (b->disk == 1) {
  sleep_prepare(b);
  release(&disk.vdisk_lock);
  sleep();
  acquire(&disk.vdisk_lock);
}

Your pick: none yet (click a line in the code)

8solidDecode the bits

While a request is in flight, gdb shows one of its three descriptors with flags = 0x3. Decode it (VRING_DESC_F_NEXT = 1, VRING_DESC_F_WRITE = 2).

Value: 0x3

VRING_DESC_F_NEXT (bit 0)VRING_DESC_F_WRITE (bit 1)Which descriptor of xv6’s chain is it?Is this request a disk read or a disk write?

9solidFill in the machine state

Hart 1 is idle in its scheduler loop when the disk interrupt arrives. It traps through kernelvec and kerneltrap into devintr, which calls virtio_disk_intr. What is hart 1’s state just after acquire(&disk.vdisk_lock) returns?

kernel/virtio_disk.c

300void
301virtio_disk_intr()
302{
303  acquire(&disk.vdisk_lock);
304
305  // the device won't raise another interrupt until we tell it
306  // we've seen this interrupt, which the following line does.
307  // this may race with the device writing new entries to
308  // the "used" ring, in which case we may process the new
309  // completion entries in this interrupt, and have nothing to do
310  // in the next interrupt, which is harmless.
311  *R(VIRTIO_MMIO_INTERRUPT_ACK) = *R(VIRTIO_MMIO_INTERRUPT_STATUS) & 0x3;

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

10solidFill in the machine state

cat’s read system call has reached virtio_disk_rw (through fileread, readi and bread). It holds README’s inode lock and the buffer’s sleep-lock, and is at line 284, about to ring the doorbell. What is the state of its hart?

kernel/virtio_disk.c

// record struct buf for virtio_disk_intr().
b->disk = 1;
disk.info[idx[0]].b = b;
273
// tell the device the first index in our chain of descriptors.
disk.avail->ring[disk.avail->idx % NUM] = idx[0];
276
io_fence();
278
// tell the device another avail ring entry is available.
disk.avail->idx += 1; // not % NUM ...
281
io_fence();
283
*R(VIRTIO_MMIO_QUEUE_NOTIFY) = 0; // value is queue number
285
// Wait for virtio_disk_intr() to say request has finished.
while (b->disk == 1) {
  sleep_prepare(b);
  release(&disk.vdisk_lock);
  sleep();
  acquire(&disk.vdisk_lock);
}

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

11solidType a number

Right after boot, binit has built the LRU list and every buffer has refcnt == 0. The first bget miss scans from bcache.head.prev. Which index i of bcache.buf[i] does it recycle?

kernel/bio.c

35void
36binit(void)
37{
38  struct buf *b;
39
40  initlock(&bcache.lock, "bcache");
41
42  // Create linked list of buffers
43  bcache.head.prev = &bcache.head;
44  bcache.head.next = &bcache.head;
45  for (b = bcache.buf; b < bcache.buf + NBUF; b++) {
46    b->next = bcache.head.next;
47    b->prev = &bcache.head;
48    initsleeplock(&b->lock, "buffer");
49    bcache.head.next->prev = b;
50    bcache.head.next = b;
51  }
52}

decimal, 0x hex or 0b binary

12solidChoose all that apply

Which fields of a struct buf are protected by bcache.lock (the spinlock), rather than by the buffer’s own sleep-lock or by the disk lock?

kernel/buf.h

1struct buf {
int valid; // has data been read from disk?
int disk;  // does disk "own" buf?
uint dev;
uint blockno;
struct sleeplock lock;
uint refcnt;
struct buf *prev; // LRU cache list
struct buf *next;
uchar data[BSIZE];
11};

13warm-upMatch the pairs

Match each lock with what it protects.

bcache.lockb->lockdisk.vdisk_locklk->lk inside a sleep-lock

14deepChoose one

On a cache hit, bget increments b->refcnt before releasing bcache.lock and calling acquiresleep. What could go wrong if it released bcache.lock first and incremented refcnt afterwards?

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}

In the gap, another hart’s bget could see refcnt == 0, relabel the buffer for a different block, and this thread would then use the wrong block’s data.acquiresleep would deadlock, because it needs bcache.lock to be held.brelse would move the buffer to the head of the LRU list too early.Nothing, because refcnt is protected by b->lock, which this thread is about to take anyway.

15deepChoose one

When bget recycles a buffer, it overwrites dev, blockno and valid without ever writing the old data back to disk. Why can’t that lose a modification?

kernel/bio.c

// 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}

Every modified buffer is pinned by log_write (refcnt > 0) until install_trans has written it home and unpinned it, so a buffer with refcnt == 0 is always clean.bget does write it back, inside virtio_disk_rw, before relabeling.Modified buffers have valid set to 0, so the recycling scan skips them.brelse writes every buffer to disk when its refcnt drops to zero.

16solidChoose one

log_write calls bpin the first time a block joins the current transaction. What is the pin for?

kernel/log.c

223void
224log_write(struct buf *b)
225{
int i;
227
acquire(&log.lock);
if (log.lh.n >= LOGBLOCKS)
  panic("too big a transaction");
if (log.outstanding < 1)
  panic("log_write outside of trans");
233
for (i = 0; i < log.lh.n; i++) {
  if (log.lh.block[i] == b->blockno) // log absorption
    break;
}
log.lh.block[i] = b->blockno;
if (i == log.lh.n) { // Add new block to log?
  bpin(b);
  log.lh.n++;
}
release(&log.lock);
244}

It keeps refcnt above zero so the buffer, which now holds the only up-to-date copy of the block, cannot be recycled before the commit.It stops the disk interrupt handler from touching the buffer while the log writes it.It marks the buffer dirty so that bget will write it back before reusing it.It locks the buffer so that no other process can read or change it until the commit.

17deepChoose all that apply

Child A (hart 1) and child B (hart 2) both need block 46 at once. A’s bget misses, relabels a buffer as 46 with valid = 0, and releases bcache.lock; then B’s bget runs while A is reading the block from disk. Which statements are true?

kernel/bio.c

57static struct buf *
58bget(uint dev, uint blockno)
59{
60  struct buf *b;
61
62  acquire(&bcache.lock);
63
64  // 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    }
72  }
73
74  // 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    }
86  }
87  panic("bget: no buffers");
88}
89
90// Return a locked buf with the contents of the indicated block.
91struct buf *
92bread(uint dev, uint blockno)
93{
94  struct buf *b;
95
96  b = bget(dev, blockno);
97  if (!b->valid) {
98    virtio_disk_rw(b, 0);
99    b->valid = 1;
100  }
101  return b;
102}

B spins on hart 2 with interrupts off until A’s disk read completes.The disk reads block 46 only once.B finds the buffer labelled 46 in its first (hit) scan, although its data is not there yet.B sleeps in acquiresleep until A releases the buffer’s sleep-lock.B gets a second buffer labelled 46, because A’s buffer has valid == 0.

18deepChoose one

When alloc3_desc gets only one or two descriptors, it gives them back before virtio_disk_rw sleeps. Why not keep them and wait only for the missing ones?

kernel/virtio_disk.c

199// allocate three descriptors (they need not be contiguous).
200// disk transfers always use three descriptors.
201static int
202alloc3_desc(int *idx)
203{
204  for (int i = 0; i < 3; i++) {
205    idx[i] = alloc_desc();
206    if (idx[i] < 0) {
207      for (int j = 0; j < i; j++)
208        free_desc(idx[j]);
209      return -1;
210    }
211  }
212  return 0;
213}
214
215void
216virtio_disk_rw(struct buf *b, int write)
217{
218  uint64 sector = b->blockno * (BSIZE / 512);
219
220  acquire(&disk.vdisk_lock);
221
222  // the spec's Section 5.2 says that legacy block operations use
223  // three descriptors: one for type/reserved/sector, one for the
224  // data, one for a 1-byte status result.
225
226  // allocate the three descriptors.
227  int idx[3];
228  while (1) {
229    if (alloc3_desc(idx) == 0) {
230      break;
231    }
232    sleep_prepare(&disk.free[0]);
233    release(&disk.vdisk_lock);
234    sleep();
235    acquire(&disk.vdisk_lock);
236  }

The device requires the three descriptors of a chain to be contiguous.Waiters holding partial sets could together own all 8 descriptors while none has 3; with no request in flight, nobody would ever free one.Descriptors cannot be held across sleep(), because they are protected by a spinlock.free_desc must be called so that wakeup(&disk.free[0]) runs and the waiter is woken.

19warm-upChoose one

cat issued a request on hart 0 and is asleep. The completion interrupt is taken on hart 1. How does virtio_disk_intr know which buffer, and so which sleeper, the completion is for?

kernel/virtio_disk.c

300void
301virtio_disk_intr()
302{
303  acquire(&disk.vdisk_lock);
304
305  // the device won't raise another interrupt until we tell it
306  // we've seen this interrupt, which the following line does.
307  // this may race with the device writing new entries to
308  // the "used" ring, in which case we may process the new
309  // completion entries in this interrupt, and have nothing to do
310  // in the next interrupt, which is harmless.
311  *R(VIRTIO_MMIO_INTERRUPT_ACK) = *R(VIRTIO_MMIO_INTERRUPT_STATUS) & 0x3;
312
313  io_fence();
314
315  // the device increments disk.used->idx when it
316  // adds an entry to the used ring.
317
318  while (disk.used_idx != disk.used->idx) {
319    io_fence();
320    int id = disk.used->ring[disk.used_idx % NUM].id;
321
322    if (disk.info[id].status != 0)
323      panic("virtio_disk_intr status");
324
325    struct buf *b = disk.info[id].b;
326    b->disk = 0; // disk is done with buf
327    wakeup(b);
328
329    disk.used_idx += 1;
330  }
331
332  release(&disk.vdisk_lock);
333}

The used ring gives the head descriptor of the finished chain, and disk.info[id].b records the buffer for that chain; it calls wakeup(b).It wakes every process sleeping in virtio_disk_rw, and each checks whether its own request is done.It wakes the process that last ran on the hart that issued the request.The device reports the block number, and the handler searches the buffer cache for it.

20deepChoose one

virtio_disk_rw waits with while (b->disk == 1) { sleep_prepare(b); release; sleep(); acquire; } instead of sleeping once. When can sleep() return while the disk is still working on the request?

kernel/virtio_disk.c

// Wait for virtio_disk_intr() to say request has finished.
while (b->disk == 1) {
  sleep_prepare(b);
  release(&disk.vdisk_lock);
  sleep();
  acquire(&disk.vdisk_lock);
}

When the interrupt for the first of the two sectors arrives, before the second is done.When the interrupt is handled on a different hart from the one the request was issued on.When the wakeup arrives between release and sleep(), since that wakeup is lost.When another process kills this one; kkill makes a SLEEPING process RUNNABLE without any wakeup on b.

21warm-upChoose one

During a disk read, who copies the 1024 bytes of the block into b->data?

readi, using either_copyout.virtio_disk_intr, with a memmove from the device’s buffer.The device itself, by DMA, while no hart runs any instruction for it.The hart that called virtio_disk_rw, by reading the device’s data register in a loop.

22warm-upClick the line

Process B is asleep in acquiresleep, waiting for a buffer that process A holds. Click the line of A’s brelse that lets B continue.

kernel/bio.c

114// Release a locked buffer.
115// Move to the head of the most-recently-used list.
116void
117brelse(struct buf *b)
118{
119  if (!holdingsleep(&b->lock))
120    panic("brelse");
121
122  releasesleep(&b->lock);
123
124  acquire(&bcache.lock);
125  b->refcnt--;
126  if (b->refcnt == 0) {
127    // 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;
134  }
135
136  release(&bcache.lock);
137}

Your pick: none yet (click a line in the code)

23deepTrue or false, and why

True or false: panic("bget: no buffers") can only happen while a log transaction has pinned buffers; with no transaction running, every buffer is eventually free.

kernel/bio.c

// 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}

TrueFalse

Why?

bget sleeps until some buffer is released, so it panics only during a commit, when the log itself needs buffers.Readers count too; if 30 processes each hold a buffer for a different block while waiting for the disk (or for descriptors), a 31st block finds no buffer with refcnt == 0.Only pinned buffers have refcnt > 0, so without a transaction all 30 buffers are recyclable.

24solidChoose all that apply

Which of these are done by the hart that takes the disk completion interrupt (in devintr and virtio_disk_intr), rather than by the process that issued the request?

kernel/virtio_disk.c

300void
301virtio_disk_intr()
302{
303  acquire(&disk.vdisk_lock);
304
305  // the device won't raise another interrupt until we tell it
306  // we've seen this interrupt, which the following line does.
307  // this may race with the device writing new entries to
308  // the "used" ring, in which case we may process the new
309  // completion entries in this interrupt, and have nothing to do
310  // in the next interrupt, which is harmless.
311  *R(VIRTIO_MMIO_INTERRUPT_ACK) = *R(VIRTIO_MMIO_INTERRUPT_STATUS) & 0x3;
312
313  io_fence();
314
315  // the device increments disk.used->idx when it
316  // adds an entry to the used ring.
317
318  while (disk.used_idx != disk.used->idx) {
319    io_fence();
320    int id = disk.used->ring[disk.used_idx % NUM].id;
321
322    if (disk.info[id].status != 0)
323      panic("virtio_disk_intr status");
324
325    struct buf *b = disk.info[id].b;
326    b->disk = 0; // disk is done with buf
327    wakeup(b);
328
329    disk.used_idx += 1;
330  }
331
332  release(&disk.vdisk_lock);
333}

freeing the request’s three descriptorssetting b->disk = 0 and calling wakeup(b)acknowledging the interrupt in the device’s INTERRUPT_ACK registersetting b->valid = 1claiming the interrupt from the PLIC

25solidChoose one

Why is there an io_fence between writing avail->ring[...] and incrementing avail->idx?

kernel/virtio_disk.c

274  // tell the device the first index in our chain of descriptors.
275  disk.avail->ring[disk.avail->idx % NUM] = idx[0];
276
277  io_fence();
278
279  // tell the device another avail ring entry is available.
280  disk.avail->idx += 1; // not % NUM ...
281
282  io_fence();
283
284  *R(VIRTIO_MMIO_QUEUE_NOTIFY) = 0; // value is queue number

So that other harts cannot take vdisk_lock until the request is published.To wait until the device has finished the previous request.To flush b->data out to the disk before the request starts.So the device cannot see the new idx before the ring entry and the descriptors are visible in memory.