Step 1 of 18

cat asks for 512 bytes

cat calls read(3, buf, 512). buf is a global array at 0x1010 in cat’s memory (user/cat.sym). The system call path into the kernel is the subject of Tour 5: Life of a system call; here it ends in sys_read, which finds the open file and calls fileread.

512 bytes is half a disk block. xv6’s file system uses 1024-byte blocks (BSIZE), while the disk itself speaks in 512-byte sectors. The kernel will fetch the whole 1024-byte block, give cat the half it asked for, and keep the rest cached for the next read.

Step 2 of 18

fileread locks the inode

README is an FD_INODE file. fileread takes the inode’s sleep lock with ilock, reads with readi at the file’s current offset (f->off = 0), advances the offset by the number of bytes read, and unlocks.

The inode lock is held across the whole read, disk wait included. That is why it is a sleep-lock: the holder is about to sleep for a disk transfer, and a spinlock holder must never sleep. It also makes the read atomic with respect to writers of the same file: nobody can change README’s size or block list while cat is in the middle.

Step 3 of 18

readi finds block 48

readi trims the request to the file’s size (2,441 bytes, so 512 is fine) and loops over the blocks the range touches. Offset 0 is in file block 0, and bmap looks it up in the inode’s addrs[] array: addrs[0] = 48.

Then bread(ip->dev, 48): “give me block 48 of device 1, locked, with its contents”. Everything below this line is the job of the buffer cache and the disk driver. readi does not know or care whether the block comes from memory or from the disk.

Step 4 of 18

bread asks the cache first

bread is two steps:

1. bget returns a buffer assigned to block 48, with its sleep-lock held.
2. If the buffer’s valid flag is 0, its data does not hold the block yet: call virtio_disk_rw to read it from the disk, then set valid = 1.

The valid check and the read happen while holding the buffer’s lock, so exactly one process reads a given block from disk, and anyone else who wants the same block waits for that lock and then finds valid = 1. Tour 30: The buffer cache follows that race in detail.

Step 5 of 18

bget misses and recycles a buffer

bget takes bcache.lock, a spinlock (interrupts off on hart 0), and scans the 30 buffers (NBUF) for device 1, block 48. None matches: nobody has read README since boot.

So it recycles the least recently used buffer that nobody holds (refcnt == 0), relabels it as block 48 with valid = 0, sets refcnt = 1, releases bcache.lock and takes the buffer’s sleep-lock with acquiresleep. Nobody else held it, so this does not wait.

After bget returns, cat holds two sleep-locks: README’s inode and block 48’s buffer. The buffer is 1024 bytes of data plus bookkeeping, inside the global bcache array (at 0x800157e8 in this build).

Step 6 of 18

virtio_disk_rw takes the disk lock

Now the driver. virtio_disk_rw first converts the block number into a sector number: 48 * (1024 / 512) = sector 96. The device addresses the disk in 512-byte sectors and will transfer two of them.

Then it takes vdisk_lock (a spinlock, so interrupts go off on hart 0). This lock protects everything in the global disk structure: the descriptor table, the free flags, the two rings and the per-request info. Every hart issuing a request, and every hart handling a disk interrupt, takes it. That second group is why interrupts must be off while it is held: if hart 0 took the disk interrupt now, virtio_disk_intr would spin on vdisk_lock, waiting for code it had itself interrupted (Locks and interrupt state).

The loop asks alloc3_desc for three free descriptors. If it cannot get them, it sleeps and retries. That case comes at the end of the tour; for cat the disk is idle and the call succeeds at once.

Step 7 of 18

Allocating three descriptors

A descriptor tells the device about one piece of memory: a physical address, a length, flags, and the index of the next descriptor in a chain. The driver has NUM = 8 of them, in a page shared with the device (virtqueue). The array disk.free[] records which are unused.

alloc_desc returns the first free index. alloc3_desc calls it three times; if any call fails, it gives back the ones it got and returns -1, so a request never holds a partial set while waiting.

In our traced run the disk was idle, so cat got descriptors 0, 1 and 2. In our traced interactive run, requests rarely overlapped, so almost every request got 0, 1, 2 (alloc_desc always returns the lowest free index).

alloc_desc and free_desc touch disk.free[] with no lock of their own. They are only ever called with vdisk_lock held.

Step 8 of 18

The request, in three descriptors

A virtio block request is a header, the data, and a status byte. xv6 always puts them in three separate descriptors, the arrangement the code’s comment cites from the spec’s section 5.2 for legacy devices (a modern device must accept other splits too):

VRING_DESC_F_WRITE is from the device’s point of view: “you may write here”. For a disk read, the device writes the data buffer and the status byte, and only reads the header.

The addresses are kernel virtual addresses used directly as physical addresses. That works because the kernel maps RAM one-to-one (direct map): b->data, inside the kernel’s bcache, has the same number in both spaces. The device knows nothing about page tables.

Finally the driver records, for the interrupt handler, which buffer this request is for (info[0].b = b) and marks it b->disk = 1: “the disk owns this buffer now”.

Step 9 of 18

Publish in the avail ring, fence, notify

The avail ring is how the driver hands requests to the device: an array of chain heads plus an index avail->idx that only ever counts up (it wraps at 65,536, not at NUM). In our run 34 requests had been issued since boot, so idx was 34:

1. ring[34 % 8] = ring[2] = 0, the head of our chain.
2. io_fence: fence iorw, iorw. All earlier memory writes, including the descriptors and the ring entry, become visible before any later one.
3. avail->idx = 35. The device treats the new index as “one more request is ready”.
4. Another fence, so the index is visible before step 5.
5. A 32-bit store to the QueueNotify register at 0x10001050, a memory-mapped device register: “queue 0 has work”.

Without the fences, the hart (or the compiler) could make the index or the notify visible before the descriptors were written, and the device could read a half-built request (memory barrier (fence), Tour 19: Memory ordering across harts). The order is the protocol: data, then index, then doorbell.

Step 10 of 18

cat sleeps on its buffer

The disk is slow compared with a CPU, so cat must wait without burning hart 0. While b->disk is still 1:

1. sleep_prepare(b): register as waiting on channel b, the buffer’s address.
2. release(&disk.vdisk_lock): the interrupt handler will need it.
3. sleep(): if no wakeup has arrived in the meantime, mark cat SLEEPING and switch to hart 0’s scheduler.

Registering before releasing the lock is what prevents a lost wakeup: if the interrupt arrives between steps 2 and 3, wakeup clears p->chan, and sleep returns at once instead of sleeping forever (Tour 16: sleep and wakeup, and the lost-wakeup problem).

cat sleeps still holding two sleep-locks, README’s inode and buffer 48. That is allowed for sleep-locks and is exactly why these two are sleep-locks. It holds no spinlock while asleep. On the way in it holds exactly one, its own p->lock, which is what sched demands (noff exactly 1); sleep-locks are not counted in noff at all (Locks and interrupt state).

It also leaves its whole system call behind, on its kernel stack (The stacks of xv6). sleep calls sched, sched calls swtch, and swtch stores ra, sp and s0–s11 in p->context (a save area, not the stack) and then loads hart 0’s scheduler sp (kernel/swtch.S:26). What stays behind, measured with gdb in our run:

cat's kernel stack, KSTACK(2), while cat sleeps
  0x3fffffa000  top ─► usertrap
                       syscall
                       sys_read
                       fileread
                       readi
                       bread
                       virtio_disk_rw   ← idx[] = {0, 1, 2} lives here
                       sleep
                       sched
  0x3fffff9e10         sp saved in p->context  (496 bytes used)
                       … about 3.5 KiB free …
  0x3fffff9000  bottom; unmapped guard page below

The user’s registers are not on it: they are in the trapframe, saved by uservec. Nothing touches this stack until some scheduler switches back to cat.

Step 11 of 18

The device does the transfer by DMA

Now the device works on its own. These are the structures it reads and writes, in the pages the driver gave it at boot (virtio_disk_init):

1. It sees avail->idx = 35, one more than it has handled, and reads ring[2] = 0.
2. It follows the chain: descriptor 0 (the header: read, sector 96), descriptor 1 (1024 bytes at b->data), descriptor 2 (one status byte).
3. It reads 1024 bytes from the disk image at byte offset 96 * 512 = 49,152, which is 48 * 1024, and writes them directly into b->data in RAM. No hart copies them. This is DMA (direct memory access).
4. It writes 0 (“OK”) into the status byte.
5. It adds an entry to the used ring: {id = 0} (the chain head), and increments used->idx, which we infer went from 34 to 35 (every earlier request had completed, so the device’s count matched the 34 requests issued).
6. It raises its interrupt line, IRQ 1 (VIRTIO0_IRQ).

(Simplified: in QEMU the “device” is emulator code. It does the same steps in the same order, and its “DMA” is the emulator writing into the guest’s RAM.)

Step 12 of 18

Some hart takes the interrupt

The PLIC forwards IRQ 1 to every hart that enabled it, which is all of them (plicinithart). All three see the interrupt pending. A hart parked in wfi wakes (wfi wakes even with interrupts off) and takes the trap during its scheduler’s brief intr_on. At that moment the scheduler holds no spinlock: noff is 0, the only state in which an interrupt can be taken (Locks and interrupt state). Usually only the first hart to claim does any work: once IRQ 1 is claimed, the PLIC stops signalling it to the others. In our run that was hart 1, while cat slept and hart 0 did something else.

The trap arrives in devintr (kerneltrap if hart 1 was in the kernel, as it is when idle in its scheduler; usertrap if it was running a user program). scause says “supervisor external interrupt”. plic_claim returns 1, so it calls virtio_disk_intr, and afterwards plic_complete tells the PLIC that the disk may interrupt again.

Notice whose time this is: hart 1 is doing cat’s work in the middle of something unrelated. Interrupt handlers serve the device, not the running process.

And on whose stack. xv6 has no separate interrupt stack: kernelvec subtracts 256 from whatever sp holds and saves the registers there (kernel/kernelvec.S:14). Our scenario assumes hart 1 was idle, so that is hart 1’s scheduler stack, its slice of stack0:

hart 1's scheduler stack (stack0 slice, top 0x80009890)
  top ─► start, main  (16 bytes each, never popped)
         scheduler
         kernelvec frame (256 bytes: the interrupted registers)
         kerneltrap
         devintr
         virtio_disk_intr …

Had hart 1 been running some process’s system call, the same frames would sit on that process’s kernel stack; had it been in user mode, uservec would have moved to that process’s empty kernel stack and usertrap would have called devintr. Never on cat’s stack: it is asleep, and only cat ever runs on it. (In one of our gdb runs the interrupt landed on idle hart 0: on entry to virtio_disk_intr, sp was 0x800086c0, 464 bytes below the top of hart 0’s slice.)

Step 13 of 18

virtio_disk_intr walks the used ring

virtio_disk_intr takes vdisk_lock, then acknowledges the interrupt by writing the device’s interrupt-status bits back to its InterruptACK register.

Then it catches up with the used ring. The driver’s own counter disk.used_idx is (by the same inference) 34; the device’s used->idx is 35. So there is one completion to handle:

• id = used->ring[34 % 8].id = 0, the head of cat’s chain.
• info[0].status must be 0. Anything else is a disk error, and xv6’s response is to panic.
• b = info[0].b, buffer 48. b->disk = 0: the disk is done with it.
• wakeup(b): wake whoever sleeps on this buffer.
• used_idx becomes 35.

The loop handles all new completions, not one per interrupt. As the comment explains, a completion that lands after the ACK may be handled now, and the next interrupt then finds nothing to do, which is harmless.

Step 14 of 18

wakeup makes cat runnable

wakeup visits all 64 process slots. For cat, p->chan equals b, so it clears the channel and, if cat is already SLEEPING (by now it almost certainly is; the disk is far slower than the few instructions between sleep_prepare and sleep), makes it RUNNABLE. wakeup sends no signal to other harts: a hart parked in wfi notices cat only after its next interrupt, such as its timer.

Then hart 1 releases vdisk_lock, returns from the interrupt and goes back to what it was doing. If that was idling in its scheduler, it will find cat on its next pass over the process table. In our traced run, cat’s next disk request (for block 49) was issued from hart 1. That suggests, but does not prove, that cat resumed on hart 1: between the two requests it returned to user space and wrote to the console, and a timer-driven yield could have moved it. Any hart running its scheduler loop may pick it up.

Step 15 of 18

cat resumes and frees the descriptors

cat returns from sleep() inside virtio_disk_rw (kernel/virtio_disk.c:290), re-acquires vdisk_lock, and re-checks the loop condition: b->disk is 0 (the re-check is needed because kkill can make a sleeping process RUNNABLE without any wakeup on b). It clears info[0].b and calls free_chain(0).

free_chain follows the NEXT links (0 → 1 → 2) and calls free_desc on each, which zeroes the descriptor, marks it free and calls wakeup(&disk.free[0]), in case some request is waiting for descriptors (the last step of this tour). That is three calls to wakeup, each visiting every process slot, for one request.

Then virtio_disk_rw releases vdisk_lock and returns. cat still holds its two sleep-locks; it never let go of them while asleep.

Its kernel stack is the same one it went to sleep with, so virtio_disk_rw’s local idx[] still says {0, 1, 2}, even if, as we infer, the function now continues on hart 1. Getting back onto it took one instruction: hart 1’s scheduler called swtch, whose ld sp, 8(a1) (kernel/swtch.S:26) loaded the sp saved in cat’s p->context, and swtch’s ret returned into sched on cat’s stack. Then sched and sleep returned, popping their frames. A process’s kernel stack is not tied to a hart: whichever hart switches to it carries on from there.

Step 16 of 18

Back in bread, then into cat's buffer

bread sets valid = 1 and returns. From now on, until this buffer is recycled, any bread(1, 48) is a cache hit with no disk I/O. That will be true for cat’s second read, which wants bytes 512–1023 of the same block.

In readi, m = min(512, 1024 - 0) = 512, and either_copyout copies 512 bytes from bp->data to user address 0x1010 in cat’s memory (copyout walks cat’s page table, as in Tour 28: Crossing the user/kernel boundary in memory). Then brelse drops the buffer’s lock and moves it to the front of the LRU list.

readi returns 512, fileread advances f->off to 512 and calls iunlock, and the system call returns 512 to cat, which writes the bytes to the console (Tour 5: Life of a system call).

Step 17 of 18

Three requests, eight descriptors

What if several harts issue requests at once? Each request needs 3 descriptors and there are only 8, so at most two requests can be in flight (6 descriptors), with 2 left over. Running logstress f1 f2 f3, three processes writing files in parallel, we saw two requests in flight (the second using descriptors 3, 4, 5) 122 times, but never a third request having to wait for descriptors. A third request can arrive, though, and then it must wait:

The channel &disk.free[0] is just an agreed-on address; any descriptor being freed wakes the waiters. And because alloc3_desc gives back partial allocations, a sleeping request holds no descriptors, so every allocated descriptor belongs to a request the device will finish and free. If waiters kept partial sets, four waiters holding two each could own all eight with nothing in flight, and nobody would ever free one.

(In the state box, the call stack is shortened to the driver; C could be any file system operation, and its lock list shows only the driver-level locks.)

Step 18 of 18

What one block cost

cat has its first 512 bytes. To get them, the kernel:

• took 2 sleep-locks (README’s inode, buffer 48) and 2 kinds of spinlock besides the p->locks and the sleep-locks’ own internal spinlocks (bcache.lock twice, in bget and brelse; vdisk_lock three times: to issue, in the interrupt handler, and on resuming),
• built 3 descriptors and 1 ring entry, and issued the request with 2 io_fences and a single doorbell store (the interrupt handler added 2 more io_fences, a read of the device’s interrupt status, a write to its InterruptACK register, and the PLIC claim and complete),
• slept once, while 1,024 bytes moved by DMA with no hart executing a single instruction to copy them,
• took 1 interrupt on a different hart, and called wakeup 4 times in the driver alone (once for cat, three times for freed descriptors), each visiting all 64 process slots.

The next read will cost almost nothing: block 48 is in the cache. So will block 49’s second half, after the first read of block 49 brings it in. The buffer cache turns three disk reads into the whole file.

The key ideas:

• The disk is driven by shared memory (descriptors and rings) plus one doorbell register; the fences make the order of writes part of the protocol.
• A request sleeps holding sleep-locks but no spinlock. vdisk_lock is released before sleeping, because the interrupt handler needs it.
• The completion can be handled by any hart, and the requester can resume on any hart; the buffer address is the meeting point.
• Eight descriptors allow two requests in flight; a third waits on disk.free[0].