Step 1 of 22

cat asks for 512 bytes

cat has opened README and now calls read(fd, buf, 512). The trip into the kernel is the one in Tour 5: Life of a system call: ecall, the trampoline, usertrap, syscall, sys_read, fileread.

What matters here is what the kernel will need: the first 512 bytes of README. README is inode 2 in this build’s fs.img, 2441 bytes long, and its first data block is block 48. (These numbers come from reading the image’s superblock and root directory; mkfs placed the blocks in the order it copied the files.)

Opening the file read the root directory (block 47) and the inode block (block 33) into the buffer cache, so those are already in memory. Block 48 is not: nobody has read README since boot. So this read will go to the disk, and that means the process will have to wait for a device.

Step 2 of 22

readi needs block 48

fileread took the inode’s sleep-lock with ilock (kernel/file.c:121) and called readi with off = 0, n = 512.

readi works one block at a time. bmap turns “block 0 of this file” into a disk block number: addrs[0] of inode 2, which is 48. Then bread is asked for block 48 of device 1.

Notice the lock being held: a sleep-lock, not a spinlock. Interrupts are still on. This matters, because what follows can take milliseconds on real hardware, and cat is about to sleep while holding this lock. Sleep-locks exist for exactly that (Tour 17: Sleep-locks).

Step 3 of 22

bread misses the cache

bget searched the cache under bcache.lock, did not find block 48, recycled the least recently used free buffer, released bcache.lock and returned the buffer locked with its own sleep-lock (kernel/bio.c:83). The details are in Tour 30: The buffer cache.

The buffer’s valid flag is 0: its data array holds some other block’s old bytes. So line 98 calls virtio_disk_rw(b, 0), “read”, and will not return until b->data holds block 48.

From here on, two fields of this struct buf carry the story. b->blockno (48) says what to read. b->disk will say who owns the buffer right now: 1 while the disk is working on it, 0 when it is done (kernel/buf.h).

Step 4 of 22

Taking vdisk_lock, which turns interrupts off

The disk counts in 512-byte sectors and xv6 in 1024-byte blocks, so block 48 is sector 48 * 2 = 96, byte offset 0xC000 in fs.img.

Line 220 takes disk.vdisk_lock, the spinlock that protects the driver’s state: the descriptor table, the free[] flags, info[], and the rings it shares with the device. acquire begins with push_off, so interrupts are now off on hart 0 until the lock is released. SIE was on (this is a system call), so push_off records intena = 1 and noff becomes 1 (Locks and interrupt state).

That is not a side detail. This same lock is taken by virtio_disk_intr, which runs in interrupt context, on whatever hart happens to take the disk interrupt. If hart 0 held vdisk_lock with interrupts on, and the disk interrupt arrived on hart 0, the handler would try to acquire a lock that its own hart holds. The holder cannot run again until the handler returns, and the handler cannot return until it gets the lock: a hart deadlocked against itself. xv6’s holding check would turn this into panic("acquire") instead of a silent hang, but the rule is what prevents it.

Then alloc3_desc grabs three free descriptors. If fewer than three are free (other requests in flight), the loop sleeps on &disk.free[0] until free_desc wakes it.

Step 5 of 22

Describing the request and ringing the doorbell

The three descriptors form a chain the device will follow: a header (“read, sector 96”), the 1024-byte b->data (marked device-writable), and a one-byte status that the device sets to 0 on success. How the virtqueue works is the subject of Tour 29: A disk read, end to end. Here we care about the hand-off:

• Line 271: b->disk = 1. The disk now owns this buffer.
• Line 272: info[idx[0]].b = b, so that the interrupt handler, which only learns a descriptor number, can find the buffer again.
• Lines 275–280: put the chain’s head in the available ring and bump its index, with fences so the device never sees the new index before the entry.
• Line 284: write the queue number to QUEUE_NOTIFY, a memory-mapped register at 0x10001050. This is the doorbell.

After the doorbell, QEMU reads sector 96 of fs.img and copies it straight into b->data by DMA: no CPU instruction moves those bytes. When it is done it writes the status byte, puts the chain’s head in the used ring, and raises its interrupt line, interrupt source 1 at the PLIC (VIRTIO0_IRQ).

Step 6 of 22

Register, then release, then sleep

cat must now wait for b->disk to become 0. It cannot sleep holding vdisk_lock (a spinlock), because the interrupt handler needs that lock to clear b->disk. So it must let go of the lock and go to sleep, and the danger is the gap between the two.

The order is the whole trick (sleep and wakeup, Tour 16: sleep and wakeup, and the lost-wakeup problem):

1. b->disk == 1 is checked under vdisk_lock, so it is the true state.
2. sleep_prepare(b) sets p->chan = b: “I am waiting on this buffer”. It does so while still holding vdisk_lock, so no handler can have run in between.
3. Only then release(&disk.vdisk_lock). Interrupts come back on (the intena saved at step 4 says they were on before).
4. sleep().

Taking p->lock inside sleep_prepare while holding vdisk_lock sets a lock order: vdisk_lock before p->lock. The interrupt handler uses the same order, so the two cannot deadlock.

Step 7 of 22

cat leaves hart 0

sleep takes cat’s p->lock and finds p->chan still set (the disk has not finished), so it marks cat SLEEPING and calls sched, which switches to hart 0’s scheduler thread (Tour 13: swtch and the lock handed across a context switch). The ld sp inside swtch (kernel/swtch.S:26) moves hart 0 off cat’s kernel stack and onto its scheduler stack, its slice of stack0 (The stacks of xv6). cat’s kernel stack stays behind in memory, frozen, with the whole read in progress on it:

cat's kernel stack, while cat sleeps
  top ─► usertrap
         syscall
         sys_read
         fileread
         readi
         bread
         virtio_disk_rw
         sleep
         sched     ◄─ cat->context.sp

Look at what cat holds as it goes to sleep: two sleep-locks (the inode and the buffer) and one spinlock, p->lock, which the scheduler releases on its behalf. sched checks that p->lock is the only spinlock held (noff == 1, kernel/proc.c:487). Had virtio_disk_rw forgotten to release vdisk_lock, this check would panic rather than let cat sleep with the disk driver locked. sleep’s acquire found interrupts on (the release(&disk.vdisk_lock) just before had turned them back on), so intena is 1, and sched carries that 1 across the switch in a callee-saved register (Locks and interrupt state).

Hart 0 is now free. Its scheduler finds nothing runnable (the shell and init are asleep too) and settles into wfi. All three harts are now idle, and the machine is waiting for one device.

Step 8 of 22

Flashback: the PLIC's registers

Before following the disk’s signal, go back to boot and see how the PLIC was programmed. It is a memory-mapped device at 0x0c000000. Its registers come in four kinds:

A context is one hart in one privilege mode. On QEMU’s virt machine each hart has two: context 2h is hart h’s machine mode, 2h+1 its supervisor mode. Substitute ctx = 2h+1 and you get the macros here: PLIC_SENABLE(h) = PLIC + 0x2080 + h*0x100 and PLIC_SPRIORITY(h) = PLIC + 0x201000 + h*0x2000, with PLIC_SCLAIM four bytes above. For our three harts:

Every hart has its own claim register. That is what lets three harts talk to the PLIC at once without a kernel lock.

Step 9 of 22

plicinit and plicinithart

plicinit runs once, on hart 0. It gives sources 1 (disk) and 10 (UART) priority 1. Every source starts at priority 0, which the PLIC treats as “disabled”.

plicinithart runs on every hart, because enable bits and thresholds belong to a context. It writes (1 << 10) | (1 << 1) = 0x402 into this hart’s S-mode enable register, and 0 into its threshold, so any enabled source of priority 1 or more gets through.

Both devices are enabled on all three harts. xv6 does not pin the disk to one CPU. The consequence, which we will see in a moment, is that the PLIC signals every hart, and the PLIC’s claim mechanism decides which one serves the interrupt.

Neither function takes a lock. plicinit runs before the other harts are released from their wait in main. plicinithart writes only this hart’s own registers.

Step 10 of 22

The order of setup in main

Hart 0 programs the PLIC (lines 25–26) before it initializes the disk driver (line 30), and the other harts call plicinithart (line 41) only after started is set. None of this is risky, because interrupts are off on every hart during all of main: a pending interrupt simply waits.

Interrupts are first turned on in scheduler (the last line here), on each hart separately (Tour 3: main: one hart builds the kernel, the others wait). From then on, a hart takes device interrupts whenever its sstatus.SIE bit is set.

Notice what main does not do: it never tells the PLIC “send the disk to hart 0”. There is no routing table. Enabling the same sources in every context is the routing.

Step 11 of 22

Three switches between a device and a hart

The PLIC only raises a signal. Whether a hart acts on it depends on three switches, and it is worth having all three in view:

1. Delegation. w_mideleg(0xffff) hands interrupts to supervisor mode, so the supervisor external interrupt traps to the kernel’s stvec, not to machine mode.
2. sie.SEIE. Line 33, in start, sets the “supervisor external interrupt enable” bit in sie (together with STIE for the timer). It is set once and never cleared.
3. sstatus.SIE. The global on/off switch that intr_on, intr_off, push_off and pop_off flip all the time.

When the PLIC signals hart 2, the hardware sets SEIP in that hart’s sip. The trap is taken if SEIE is set and either the hart is in supervisor mode with SIE = 1, or it is in user mode (supervisor interrupts are always enabled while user code runs). Every “interrupts off” in this tour means SIE = 0: the request stays pending in sip until interrupts are turned back on, unless another hart claims it first and the PLIC lowers SEIP.

Step 12 of 22

The disk finishes; every idle hart wakes

Back to the present. QEMU has filled b->data with block 48 and raised source 1. The PLIC sets bit 1 in its pending register and, since source 1 is enabled with priority 1 > threshold 0 in contexts 1, 3 and 5, asserts SEIP on all three harts.

Hart 2 was parked in wfi at line 467, with SIE off. wfi resumes when an interrupt that is enabled in sie is pending, even if the global SIE bit is off, so hart 2 falls through, goes around the loop, and at line 441 executes intr_on. The pending interrupt is taken immediately, before the next instruction (intr_off) runs.

This is why the loop turns interrupts on and straight back off: wfi must be executed with interrupts off, or an interrupt arriving between the check and the wfi could be handled and then leave the hart asleep with work to do. The brief intr_on is the window where pending interrupts are actually taken. It is safe because the scheduler holds no spinlock here: an interrupt is only ever taken at noff 0 (Locks and interrupt state).

This scenario fixes which stack the trap will land on. Hart 2 is running no process, so sp points into its scheduler stack: its 4 KiB slice of stack0 (top 0x8000a890 in this build), the same memory it booted on.

Step 13 of 22

kerneltrap, on the scheduler's stack

The trap sets scause to 0x8000000000000009 (top bit: interrupt; 9: supervisor external interrupt), saves the PC in sepc, turns SIE off, and jumps to stvec, which in the kernel is kernelvec. The trap does not change sp. kernelvec makes room with addi sp, sp, -256 (kernel/kernelvec.S:14), saves registers in that frame on the current stack, which here is hart 2’s scheduler stack (its boot stack, reused), and calls kerneltrap. All of this is the subject of Tour 8: Traps taken inside the kernel.

hart 2's scheduler stack (stack0 slice, top 0x8000a890)
  start         16 bytes, never popped (start left by mret)
  main
  scheduler
  kernelvec    256-byte register frame
  kerneltrap   ◄─ sp

The device does not choose the stack; the hart’s situation does. xv6 has no separate interrupt stack. Had hart 2 been running a process in the kernel with interrupts on, the same kernelvec frame would have gone onto that process’s kernel stack, on top of its system call’s frames. Had it been in user mode, the trap would have gone through uservec instead, onto the process’s empty kernel stack.

What matters for us: the handler runs with interrupts off and on behalf of no process. myproc() is 0 on hart 2. A device interrupt is the machine’s business, not any process’s; the process it concerns, cat, is not running anywhere.

kerneltrap calls devintr to identify and handle the interrupt. Afterwards, since which_dev will be 1 (a device, not the timer), it will not yield.

Step 14 of 22

devintr asks the PLIC who it was

scause matches the supervisor-external value, so this is “some device, via the PLIC”. scause does not say which device. Only the PLIC knows, so devintr asks it with plic_claim.

Then a two-way dispatch: UART0_IRQ (10) goes to uartintr, VIRTIO0_IRQ (1) to virtio_disk_intr. Any other non-zero number is a surprise and gets a message. An irq of 0 falls through both tests and the if (irq) before plic_complete, and devintr still returns 1: it was a device interrupt, it just was not ours to serve.

Compare the timer interrupt branch at line 213: the timer does not go through the PLIC at all. It has its own scause value (5), so it needs no claim.

Step 15 of 22

Claiming the interrupt, and the harts that lose

Hart 2 reads its claim register, 0x0c205004. That one load does three things in the PLIC, atomically: it picks the highest-priority pending source enabled for context 5, returns its number (1), and clears its pending bit. With nothing left pending, the PLIC drops SEIP on the other harts.

A read with side effects is normal for memory-mapped I/O, and the side effect is what makes the claim safe. In one run under gdb, the read of block 48 went exactly like this: hart 2’s claim returned 1, and hart 1’s claim, a moment later, returned 0. Over the whole run, about one claim in five returned 0 (most of those were UART interrupts; for disk completions an empty claim is much rarer).

cpuid reads tp, and that is reliable here: interrupts are off, so the handler cannot be moved to another hart between reading the hart number and using its claim register.

Step 16 of 22

virtio_disk_intr takes vdisk_lock and acknowledges the device

virtio_disk_intr takes vdisk_lock, the same lock cat held in virtio_disk_rw. Interrupts are already off (a trap turns them off), so acquire's push_off finds noff 0 and records intena = 0: the matching release will leave them off. Compare step 4, where cat took the same lock with interrupts on (intena = 1). And this handler could only start because hart 2 held no spinlock: an interrupt never lands inside a critical section on its own hart (Locks and interrupt state).

Line 311 is a conversation with the device, not with the PLIC. It reads the device’s INTERRUPT_STATUS register (bit 0: “I used some buffers”; bit 1: “my configuration changed”) and writes the same bits back to INTERRUPT_ACK. That tells the virtio device to lower its interrupt line.

There are two acknowledgements in this tour, and they are different: this one quiets the device; plic_complete, later, re-opens the PLIC for this source. The device must be quieted first. If the PLIC were re-opened while the device still held its line high, the PLIC would see a new request at once and interrupt again for work already done.

Step 17 of 22

Walking the used ring; block 48 is done

The device reports completions in the used ring: it writes the head descriptor number of each finished chain and increments used->idx. The driver remembers how far it has looked in disk.used_idx. Every entry between the two is a finished request.

For block 48 there is one entry. Its id leads to info[id]: status 0 (success; a non-zero status means the disk failed, and xv6 panics) and b, the buffer recorded at step 5. Then:

• b->disk = 0: the disk is done with this buffer. b->data now holds block 48.
• wakeup(b): wake whoever waits on this buffer.

One interrupt may cover several completions, and a completion may be found by an interrupt that arrives “too early”. The source comment on lines 305–310 calls the resulting empty interrupt harmless, and it is: the loop condition is all that matters.

Note that the handler never touches b->data, never copies anything, and does not know which process asked. It only changes ownership and wakes the channel.

Step 18 of 22

wakeup makes cat runnable, from interrupt context

wakeup walks the process table, taking each p->lock in turn. At cat’s entry it finds p->chan == b, clears it, sees SLEEPING, and sets RUNNABLE.

The locks held here follow the order set at step 6: vdisk_lock first, then a p->lock. cat took them in the same order in sleep_prepare. Two code paths that take the same two locks in the same order cannot deadlock against each other (Tour 18: Lock ordering: how xv6 avoids deadlock).

wakeup is safe to call from an interrupt handler because it never sleeps and takes only spinlocks, and interrupts are already off. A handler that called sleep would be a disaster: there is no process to put to sleep.

Step 19 of 22

Meanwhile, a keystroke on hart 1

Suppose instead that you press a key just as the disk finishes (a variation on the gdb run, not what happened there). The UART raises source 10. Now two sources are pending at once, both with priority 1. The PLIC breaks the tie by number: the lower ID wins, so the first claim returns 1 (the disk) and the next returns 10.

uartintr reads the UART’s ISR to acknowledge it (the device-side ack again), wakes any writer waiting for the transmitter, and passes each received byte to consoleintr, which takes cons.lock to update the line buffer and echo it. The keystroke’s full story is Tour 37: A keystroke's journey.

The two handlers share nothing: different devices, different locks, different claim registers. They can run truly in parallel on harts 1 and 2.

Step 20 of 22

plic_complete re-opens source 1

virtio_disk_intr has released vdisk_lock and returned. Back in devintr, plic_complete writes 1 to hart 2’s claim/complete register, 0x0c205004.

Between claim and completion the PLIC will not forward another interrupt from source 1, even if the device raises its line again. Completion re-arms it. Since the device’s line was lowered at step 16, nothing new is pending, and the next disk interrupt will come with the next completed request.

It is written to the same context that claimed it, so the claim and complete happen on one hart with interrupts off the whole time. Nothing between them could move this code to another hart.

Then kerneltrap restores sepc and sstatus, kernelvec restores the registers and pops its 256-byte frame, and sret returns hart 2 to its scheduler, on the same stack, with sp back where it was, just after the intr_on where the interrupt struck. With SIE restored from SPIE, interrupts are on again for an instant; then intr_off(), the scan, and perhaps wfi once more.

Step 21 of 22

cat wakes on hart 0 and re-checks

Hart 0’s scheduler found cat RUNNABLE and switched to it, from its scheduler stack back onto cat’s kernel stack, where the frames from usertrap down to sched had waited unchanged. In the gdb run, too, the request went out on hart 0, the interrupt was served on hart 2, and cat resumed on hart 0; it could just as well have been hart 1. cat returns out of sleep (which releases its p->lock), then line 291 re-acquires vdisk_lock, and interrupts go off again.

Why loop and re-check b->disk, instead of trusting the wakeup? Because sleep can return while b->disk is still 1: kkill sets killed and makes a SLEEPING process RUNNABLE without any wakeup on b; the loop simply registers and sleeps again (the disk still owns the buffer, so cat must not abandon it). sleep also returns at once when the wakeup came between sleep_prepare and sleep; in that case the re-check finds 0.

b->disk is 0, so the loop ends. Line 294 forgets the buffer, free_chain returns the three descriptors (each free_desc calls wakeup(&disk.free[0]), in case a request is waiting for descriptors), and line 297 releases vdisk_lock.

Step 22 of 22

The data reaches cat, and what it cost

bread marks the buffer valid and returns it. readi copies the first 512 bytes of block 48 into cat’s buf with either_copyout and releases the buffer with brelse. fileread unlocks the inode and returns 512, and cat heads back to user mode as in Tour 5: Life of a system call. The next read of README finds block 48 in the cache and never touches the disk.

What one disk interrupt took:

• one doorbell write and one DMA transfer, during which no CPU touched the data;
• one PLIC signal to three harts; in this run two harts trapped and claimed, and one claim returned 0 (often only one hart traps at all);
• two acknowledgements: the device’s (INTERRUPT_ACK) and the PLIC’s (plic_complete);
• one spinlock, vdisk_lock, shared between a process and an interrupt handler, and held with interrupts off on both sides;
• one sleep and one wakeup, ordered so the wakeup cannot be lost.

The ideas generalize to every driver: the device tells the PLIC, the PLIC tells the harts, the hardware arbitrates the claim, the handler changes ownership and wakes a channel, and the sleeping thread re-checks its condition under the lock.