Step 1 of 20

A program that never gives up the CPU

Pid 5 is the first child forked by preempt. fork returned 0 to it, so it entered for (;;) ;. In the build (user/usertests.asm) that loop is one compressed instruction at address 0x3a7a: a001, which is j 3a7a, a jump to itself.

Pid 5 executes that jump millions of times and never executes ecall. If xv6 waited for programs to enter the kernel on their own, hart 1 would belong to pid 5 forever, and so would harts 0 and 2 to its siblings. Pid 4, RUNNABLE and waiting, would never run, and the test would hang.

The only way out is an event the program cannot prevent: an interrupt. Every hart has a timer that interrupts it about ten times a second. User code cannot turn it off: the interrupt-enable bit sstatus.SIE and the timer register stimecmp are supervisor registers, and user mode cannot touch them.

Step 2 of 20

Flashback: each hart set its own alarm at boot

At boot, every hart ran start in machine mode, and timerinit set up its timer with the Sstc extension:

• Setting menvcfg.STCE lets supervisor mode use stimecmp.
• Setting bit 1 of mcounteren lets supervisor mode read time.
• stimecmp = time + 1000000 asks for the first interrupt.

The rule is simple: a supervisor timer interrupt is pending whenever time >= stimecmp. time counts at 10,000,000 per second on QEMU’s virt machine, so 1,000,000 is 0.1 seconds.

Two other lines of start matter: it delegated all interrupts to supervisor mode (mideleg, kernel/start.c:32), so the timer interrupt goes to the kernel’s supervisor-mode code rather than to machine mode, and it set sie.STIE (kernel/start.c:33), which enables the timer interrupt locally.

Step 3 of 20

The tick arrives, and hart 1 lands in the trampoline

time passes hart 1’s stimecmp. The timer interrupt is pending, sie.STIE is set, and the hart is in user mode. In user mode, supervisor interrupts are taken no matter what sstatus.SIE says (the RISC-V rule is that interrupts for a higher privilege mode than the current one are always globally enabled). So between two executions of j 3a7a, the hardware traps:

From here the path is the one Tour 5: Life of a system call follows for a system call: uservec saves all 31 user registers in pid 5’s trapframe, switches to the kernel page table and jumps to usertrap. (Tour 7: The trampoline and the trapframe covers the trampoline in detail.) The hardware does not distinguish “the program asked” from “the clock interrupted”: only scause differs.

The trap changed pc, the mode and a few CSRs, but not sp. Hart 1 is now in supervisor mode with sp still pointing into pid 5’s user stack, so uservec must not push anything. It saves the user sp into the trapframe (kernel/trampoline.S:41) and only then, at kernel/trampoline.S:76, loads a kernel stack (The stacks of xv6 has the whole picture).

Step 4 of 20

usertrap saves the interrupted pc

usertrap does its usual opening: checks the trap came from user mode, points stvec at kernelvec, finds pid 5 with myproc (hart 1’s cpus[1].proc), and saves sepc into p->trapframe->epc: 0x3a7a.

It runs on pid 5’s own kernel stack. uservec loaded sp from p->trapframe->kernel_sp, which prepare_return always sets to the top of the stack (kernel/trap.c:117). A process in user mode has nothing on its kernel stack, so usertrap’s frame is the first thing on it. Pid 5 lives in proc[4], so its kernel stack is the page KSTACK(4), mapped only in the kernel page table, with an unmapped guard page below it.

Saving sepc matters more for an interrupt than for a system call. In a moment pid 5 may be switched off hart 1 and resumed on another hart, much later. Hart 1’s sepc will be overwritten many times by then, and the other hart’s sepc has nothing to do with pid 5. The trapframe travels with the process; the CSR stays with the hart.

Notice also what will not happen: no epc += 4. That adjustment is for ecall, whose trap leaves sepc pointing at the ecall itself (kernel/trap.c:60–61); resuming there would make the system call again. An interrupt is taken before the instruction at sepc runs, so pid 5 must resume by executing j 3a7a itself.

Step 5 of 20

Not a system call, so ask devintr

scause is not 8, so the system-call branch is skipped, and with it the intr_on on line 66. Pid 5’s whole trip through the kernel runs with interrupts off, from the trap until sret returns it to user mode (on hart 0, as it turns out). The kernel work for one tick is short, so nothing is lost by keeping them off, and it means no second interrupt can arrive while this one is half handled.

devintr decides whether the trap was a device interrupt it recognizes, and returns a code that usertrap keeps in which_dev: 2 for the timer, 1 for another device, 0 for “not mine”. If it returned 0, the next test would try the page-fault handler and, failing that, kill the process.

Step 6 of 20

devintr recognizes the timer

devintr reads scause. The first branch, 0x8000000000000009 (supervisor external interrupt), is for devices behind the PLIC, such as the UART and the disk; Tour 9: Device interrupts and the PLIC follows that path. Ours is 0x8000000000000005, the supervisor timer interrupt, so it calls clockintr and returns 2.

The timer needs no PLIC and no claim/complete handshake. It is not an external device at all: it is part of each hart, compared against that hart’s own stimecmp. That is also why a timer interrupt always lands on the hart whose timer fired. Hart 1’s tick will never be delivered to hart 0.

Step 7 of 20

clockintr on hart 1 does not count

clockintr has two jobs, and hart 1 does only the second.

The first job, lines 169–174, is to advance the kernel’s clock, ticks. Only hart 0 does that. cpuid() is 1 here, so hart 1 skips the block and never touches tickslock.

Why only one hart? Every hart gets a tick every 0.1 s. If all three counted, ticks would advance about 30 times a second instead of 10, and the rate would depend on how many CPUs QEMU was started with. One counter, fed by one hart, keeps “a tick” meaning “about a tenth of a second”. Tour 14: pause(n) and the tick counter follows the counting side: ticks++, wakeup(&ticks) and the processes sleeping in pause.

Step 8 of 20

Re-arm the alarm, or drown in interrupts

Every hart, including hart 1, does the second job: stimecmp = time + 1000000, the next tick 0.1 s from now.

This write is also what acknowledges the interrupt. With Sstc, the timer interrupt is pending exactly while time >= stimecmp. Moving stimecmp into the future makes it stop being pending. If clockintr forgot this line, the condition would still be true when pid 5 returned to user mode, and hart 1 would trap again immediately, forever, never executing another user instruction.

The new deadline is computed from the current time, not from the previous deadline. So if this hart was slow to take the interrupt (because it had interrupts off for a while), the next tick is simply later. Ticks are never “made up” in a burst; the schedule drifts a little instead.

Step 9 of 20

Back in usertrap, the decision to yield

which_dev is 2. Two more decisions:

• Was pid 5 killed? killed reads p->killed under p->lock. If someone had run kill 5, this is where a pure spinner would die, at its next tick. (Tour 23: kill follows kill.)
• It is a timer interrupt, so call yield.

This line is the whole of xv6’s preemption policy: every tick, the running process gives up its CPU. There is no priority, no measurement of how long pid 5 has run, no quantum longer than one tick. Pid 5 has run for at most 0.1 s, and now it goes to the back of the line, which in xv6 means: back in the process table as RUNNABLE, for any hart’s scheduler to find.

Step 10 of 20

yield takes pid 5's lock and marks it RUNNABLE

yield takes pid 5’s p->lock and sets p->state = RUNNABLE.

The lock is needed because p->state is read by every hart’s scheduler. The moment this write is visible, the state says “pid 5 may be run by anyone”. But pid 5 is still running: it is on hart 1, executing yield, on its own kernel stack. Its registers have not been saved yet.

So the lock must stay held until pid 5 has fully stopped. It will: sched switches to the scheduler with the lock held, and hart 1’s scheduler releases it only after the switch is complete. acquire also turns interrupts off, but they are already off, so push_off records intena = 0 in cpus[1]: when the last lock is released, interrupts should stay off. Compare a process that sleeps from a system call, where intena is 1 (Locks and interrupt state).

Step 11 of 20

sched checks the rules

sched is the only way into the scheduler, and it checks that the caller has followed the rules:

• pid 5’s p->lock is held (holding): yes.
• exactly one spinlock is held (noff == 1): yes, only p->lock.
• the state is no longer RUNNING: it is RUNNABLE.
• interrupts are off: yes.

Then it copies cpus[1].intena (0) into a local variable. That value describes pid 5’s path through the kernel, not hart 1, and pid 5 may resume on another hart, so it must travel with pid 5. Tour 13: swtch and the lock handed across a context switch explains each check and the intena rule in depth. (In this build the local lives in s3, which swtch saves: Locks and interrupt state.)

Step 12 of 20

swtch saves pid 5

sched calls swtch(&p->context, &mycpu()->context).

The first fourteen sd instructions store pid 5’s ra, sp and s0–s11 into proc[4].context. The saved ra is 0x80001e9c in this build: the instruction in sched right after its call to swtch. The saved sp points into pid 5’s kernel stack, which still holds the frames of usertrap, yield and sched:

pid 5's kernel stack (KSTACK(4), one page)
  top ─► usertrap
         yield
         sched     ◄─ sp, saved in proc[4].context.sp

(swtch itself is a leaf in assembly and pushes no frame.)

After these stores, pid 5’s kernel thread is a frozen snapshot: a stack in memory and 112 bytes of registers. It will “return” from this same call when some hart switches back to it. (Tour 13: swtch and the lock handed across a context switch takes swtch apart.)

Step 13 of 20

swtch loads hart 1's scheduler

The next fourteen ld instructions load cpus[1].context, saved the last time hart 1’s scheduler switched away. Line 25 loads its ra, 0x80001df0, the instruction in scheduler right after its call to swtch. Line 26 loads its sp, which points into hart 1’s scheduler stack.

The ld sp on line 26 is the moment hart 1 changes threads: before it, sp pointed into pid 5’s kernel stack; after it, into the scheduler’s. ret jumps to ra, and the scheduler thread “returns” from a swtch call it made long ago. c->proc still names pid 5 until line 460 clears it.

The scheduler stack is not new memory. It is hart 1’s 4 KiB slice of stack0, the very stack kernel/entry.S:17 gave hart 1 at power-on: main called scheduler, which never returns, so the boot stack simply became the scheduler stack (The stacks of xv6). In this build the slice is 0x80008890–0x80009890, and its top 128 bytes hold three frames: start’s 16 (never popped, because start leaves by mret), main’s 16 and scheduler’s 96:

hart 1 now                          pid 5, frozen
stack0 slice (top 0x80009890)       KSTACK(4) (top 0x3fffff6000)
  start (left by mret)                usertrap
  main                                yield
  scheduler  ◄─ sp 0x80009810         sched   (sp in proc[4].context)

swtch never goes from one process’s kernel stack straight to another’s: every switch passes through a scheduler stack.

Step 14 of 20

Hart 1's scheduler lets go of pid 5

The scheduler resumes just after line 453, inside the loop iteration that picked pid 5 in the first place, with p still pointing at proc[4].

• Line 456 sets cpus[1].intena = 0, so that releasing the lock leaves interrupts off. Here it was 0 already (pid 5’s value), but a process that slept from a system call would have left 1 behind (Locks and interrupt state).
• Line 460: c->proc = 0. Hart 1 runs no process now; myproc on hart 1 returns 0.
• Line 463 releases pid 5’s p->lock, the one yield took on this hart a few hundred instructions ago, in a different thread.

Only now, at line 463, may another hart run pid 5. Its registers are safely in proc[4].context, and no CPU is using its kernel stack.

Step 15 of 20

Hart 1 keeps scanning and finds pid 4

The loop goes on from where it was: proc[5] (pid 6, RUNNING on hart 0: skip), proc[6] (pid 7, RUNNING on hart 2: skip), then the unused slots up to proc[63], each locked and unlocked in turn. At the end of the table, found is 1, so there is no wfi; the outer loop opens and closes the interrupt window and starts again at proc[0].

proc[0] (init), proc[1] (sh) and proc[2] (usertests) are SLEEPING in wait. proc[3] is pid 4, RUNNABLE since pid 7’s write. Hart 1 takes its lock, sets RUNNING, sets c->proc, and switches to it.

This is what the preempt test checks: three spinners on three harts cannot starve a fourth process, because every tick sends one of them back to the table. Pid 4 will return from read, then kill its three children.

Step 16 of 20

Hart 0's tick, and pid 5 is picked up

Some time later (anything up to 0.1 s, since the harts’ timers are not synchronized), and in our run before hart 2’s, hart 0’s own timer fires while pid 6 spins. Hart 0 goes through every step you have just seen: trampoline, usertrap, devintr, clockintr (and, being hart 0, it also does ticks++ under tickslock), yield, sched, swtch. Hart 0’s scheduler releases pid 6 and continues its scan from proc[6].

Pid 7 is running; the rest of the table is unused or sleeping; the scan wraps to proc[0]. At proc[3], pid 4 is now RUNNING on hart 1: skip. At proc[4], pid 5: RUNNABLE. Hart 0 takes proc[4].lock, sets RUNNING and cpus[0].proc, and calls swtch(&cpus[0].context, &proc[4].context).

Pid 5 is moving from hart 1 to hart 0. Nothing about pid 5 belongs to hart 1: its registers are in its trapframe and its context, its kernel stack is its own, and its page table is its own.

Step 17 of 20

Pid 5 wakes up inside sched, on hart 0

swtch loads proc[4].context and returns to 0x80001e9c: the line after the swtch call in sched. From pid 5’s point of view, the call that began on hart 1 has just returned. Its stack, its local variables and its callee-saved registers are exactly as it left them.

The ld sp in that swtch moved hart 0 from its scheduler stack onto pid 5’s kernel stack: the same page, KSTACK(4), at the same virtual address, with the same three frames hart 1 left behind. Kernel stacks are mapped in the one kernel page table that every hart uses, so the stack does not need to move for the process to move; only the sp register changes, and that register belongs to whichever hart loads it.

Line 496 calls mycpu again, and this time it returns &cpus[0], because the tp register, which swtch does not touch, holds this hart’s number, 0. It stores pid 5’s saved intena (0) there (Locks and interrupt state). A pointer to cpus[1] kept from before the switch would now be wrong: hart 1 is busy running pid 4.

Step 18 of 20

yield releases the lock hart 0's scheduler took

sched returns into yield, which releases p->lock. This is the lock that hart 0’s scheduler acquired at proc[4] a moment ago; pid 5’s thread releases it.

release calls pop_off: cpus[0].noff drops to 0, and cpus[0].intena is 0, so interrupts stay off. That is correct: pid 5 entered the kernel through a trap with interrupts off and never turned them on. They come back on only at sret, from the SPIE bit that prepare_return sets (Locks and interrupt state).

Look at the symmetry. On hart 1, yield acquired the lock and the scheduler released it. On hart 0, the scheduler acquired it and yield released it. Each acquire and its release happen on the same hart, but in different threads.

Step 19 of 20

prepare_return records hart 0

yield returns to usertrap, which calls prepare_return exactly as after a system call. Two of its lines matter especially after a migration:

• Line 119 stores kernel_hartid = 0. When pid 5 next traps (on hart 0, because a process in user mode stays on its hart), uservec will load tp = 0. The value written on hart 1 is now stale and is overwritten.
• Line 131 writes sepc = p->trapframe->epc, which is still 0x3a7a. Hart 0’s sepc had held pid 6’s address when hart 0’s tick arrived; now it holds pid 5’s.

Line 117 rewrites kernel_sp with the same value it always has, the top of KSTACK(4). By the time pid 5 next traps, usertrap’s frame will have been popped and its kernel stack will be empty again, so the next trap can start from the top.

Then userret executes fence.i (it runs on every return to user space; this time it actually matters, because pid 5 has never run on hart 0 before), switches satp to pid 5’s page table between two sfence.vma, restores its 31 registers from the trapframe, and executes sret. Between csrw satp (kernel/trampoline.S:111) and ld sp, 48(a0) (kernel/trampoline.S:118) hart 0 has no usable stack: sp still holds a kernel-stack address that the user page table does not map. Line 118 loads pid 5’s user sp from the trapframe, where uservec saved it on hart 1; supervisor code cannot use that stack, so it becomes usable only when sret returns to user mode.

Step 20 of 20

The jump executes, on a different CPU

sret drops to user mode at 0x3a7a, with interrupts enabled. Pid 5 executes j 3a7a, and goes on spinning, now on hart 0. It cannot tell anything happened, except that the clock on the wall moved more than its own work explains.

What this one tick cost, counted for this run. On hart 1: one trap; 31 user registers saved by uservec, with one csrw satp and two sfence.vma; pid 5’s p->lock taken twice (in killed and in yield); two swtch calls (pid 5 → scheduler, scheduler → pid 4) of 28 memory operations each; and a scan that acquired 63 p->locks (proc[5]…proc[63], then proc[0]…proc[3]). Pid 5’s own thread ran with interrupts off the whole time; hart 1’s scheduler opened its interrupt window once, at the wrap-around. Hart 0 paid the second half to resume pid 5: after its own tick, a swtch into pid 5, then fence.i, one csrw satp, two sfence.vma, 31 registers restored by userret, and one sret.

The key ideas:

• The timer is what makes xv6 preemptive: usertrap calls yield on every tick, so no process can keep a CPU.
• p->lock is held across the switch, from yield until the scheduler has finished switching away, so no hart can run a process that another hart has not finished leaving.
• Everything a process needs travels with it (trapframe, context, kernel stack); everything a hart owns (tp, sepc, stimecmp, cpus[i]) stays put and is rewritten for whoever runs next.