Step 1 of 19

A spins, and hart 2 is entirely A's

Pid 5 is the first child of preempt. Its whole remaining program is line 867: in the binary, the 2-byte instruction j 0x3a7a at user address 0x3a7a, which jumps to itself.

Start the table. Each row records one moment on hart 2:

Row 1 · hart 2 · U · A’s user stack (0x11e80) · A’s page table (satp = 0x800000000008003a in our run) · process A · locks: none

Everything a hart can be “in” is A’s right now: its registers hold A’s values, satp names A’s page table, sp points into A’s user stack. Even tp, which the kernel uses for the hart number, holds A’s own value now (0x0505050505050505: junk A inherited and never uses). What is not A’s are a few supervisor CSRs that A cannot read: stvec, which points at uservec in the trampoline page because the kernel prepared A’s last return to user mode, and stimecmp, the hart’s alarm clock, set at the last tick.

In user mode, a pending supervisor interrupt that is enabled in sie is always taken, whatever sstatus.SIE says (start enabled the timer and external bits, kernel/start.c:33). That is the whole basis of preemption: A cannot switch it off.

Step 2 of 19

T4: the tick arrives, and only three things change

Hart 2’s time passes its stimecmp, the hart sets sip.STIP, and because A is in user mode the interrupt is taken before the next j. This is transition T4. The hardware writes sepc = 0x3a7a (the jump that has not run yet), scause = 0x8000000000000005 (interrupt, code 5: supervisor timer), copies SIE into SPIE, clears SIE, sets SPP = 0 (came from U), switches to S-mode, and jumps to stvec.

Row 2 · hart 2 · S · no usable stack (sp still 0x11e80) · A’s page table · process A · locks: none

Compare with row 1: the mode changed, the pc changed, and interrupts are off. The stack and the page table did not. The hardware never touches sp or satp on a trap, which is why the very first instructions must come from a page that is mapped in the user page table: the trampoline. sp still holds A’s user value, a number the kernel must not trust, so for now this hart has no stack it can use (The stacks of xv6).

The tick went to S-mode, not M-mode, because start delegated supervisor timer interrupts with mideleg and turned on the Sstc extension (Tour 46: Boot: returning from a trap that never happened).

Step 3 of 19

uservec saves A's registers, and loads a stack it cannot use yet

uservec stores 31 registers into A’s trapframe through the address TRAPFRAME, mapped only in A’s page table. Then it loads the four kernel values that prepare_return left in the trapframe the last time A returned to user mode:

sp now holds a real stack address, but A’s page table has no mapping for it. Until csrw satp on line 92, a push would fault. So the row still says “no usable stack”:

Row 3 · hart 2 · S · none (sp = 0x3fffff6000, unmapped) · A’s page table · process A · locks: none

Then line 92 installs the kernel page table between two sfence.vma, and jalr t0 on line 98 enters usertrap. That csrw satp is the first of this slice’s page-table switches. Keep a count; it will be large.

Step 4 of 19

usertrap on an empty kernel stack

Now every answer is “kernel”: S-mode, A’s kernel stack, the kernel page table.

Row 4 · hart 2 · S · A’s kernel stack (top 0x3fffff6000) · kernel page table · process A · locks: none

The kernel stack was empty a moment ago. It always is when a process is in user mode, because kernel_sp is always the top of the page (kernel/trap.c:117). Its first contents are usertrap’s own 32-byte frame, and the very first word pushed is the return address 0x3ffffff09c: userret, at its trampoline address, because uservec reached usertrap with a jalr from that page. usertrap will “return” into the trampoline.

Then two writes that change where the next trap goes and what survives it. stvec becomes kernelvec (line 47), so a trap taken from here on lands on this stack instead of in the trampoline. And sepc, 0x3a7a, is copied to trapframe->epc (line 52) before anything can overwrite it.

Step 5 of 19

devintr says "timer", and A decides to yield

scause is not 8, so devintr runs. It recognizes 0x8000000000000005, calls clockintr, and returns 2. clockintr on hart 2 does not increment ticks, since only hart 0 counts time (kernel/trap.c:169), so tickslock is not taken here. It writes stimecmp = time + 1000000, which both clears the pending bit and sets the next alarm about 0.1 s ahead.

Line 81 asks killed, taking and releasing A’s p->lock for a moment: A has not been killed. Line 85: which_dev == 2, so yield.

Row 5 · hart 2 · S · A’s kernel stack · kernel page table · process A · locks: none (between the two p->lock sections)

Notice what has not happened: interrupts are still off. A timer or device trap enters the kernel with SIE = 0, and usertrap turns interrupts on only for system calls (line 66). This whole path, from the tick to the swtch, runs with interrupts off.

Step 6 of 19

yield takes A's lock and sched checks the rules

yield acquires A’s p->lock and marks A RUNNABLE. sched then checks four rules and calls swtch(&p->context, &mycpu()->context). In our build the stack holds three frames at that call:

KSTACK(4), top 0x3fffff6000
  usertrap   0x3fffff5fe0–0x3fffff6000   ra = 0x3ffffff09c (userret)
  yield      0x3fffff5fc0–0x3fffff5fe0
  sched      0x3fffff5f90–0x3fffff5fc0   ◄─ sp

Row 6 · hart 2 · S · A’s kernel stack (0x3fffff5f90) · kernel page table · process A · locks: A’s p->lock

The lock makes A RUNNABLE but untouchable. Any other hart may now see RUNNABLE, but only after it acquires this same lock, and hart 2 holds it until it is completely off A’s stack. Tour 13: swtch and the lock handed across a context switch tells that story in full; the noff == 1 and intr_get() checks are the subject of Tour 48: Breaking the invariants.

Step 7 of 19

T6, swtch #1: from A's stack to hart 2's scheduler stack

Lines 10–23 store 14 registers into proc[4].context. Lines 25–38 load 14 from cpus[2].context, and line 26 is the instant hart 2 stops being A: sp becomes 0x8000a810, inside hart 2’s slice of stack0. ret jumps to 0x80001df0, the instruction after the scheduler’s own swtch call. This is T6, the first of four in this slice.

Row 7 · hart 2 · S · scheduler stack (0x8000a810) · kernel page table · no process · locks: A’s p->lock

swtch changed no CSR: not the mode, not satp, not sstatus. The page table is the same because every kernel thread, process or scheduler, uses the one kernel page table. The scheduler stack is the boot stack hart 2 got at power-on; main called scheduler, which never returned, so that memory took on its second job (The stacks of xv6).

And look at the lock column. The lock was acquired by A’s thread on A’s stack. It is now held by the scheduler thread on another stack. A lock belongs to a hart, not to a stack.

Step 8 of 19

The scheduler lets go of A and scans on

The scheduler resumes inside the loop iteration that once picked A, with p still pointing at proc[4]. Line 456 sets intena = 0 so that releasing the lock keeps interrupts off (Locks and interrupt state); here it was A’s 0 already. Line 460 clears c->proc: from here, myproc on hart 2 returns 0, so a timer taken in the scheduler will not call yield. Line 463 releases A’s p->lock.

Row 8 · hart 2 · S · scheduler stack · kernel page table · no process · locks: none after line 463

Only now may another hart run A. Its registers are in proc[4].context and its trapframe, and no hart is using its kernel stack.

The scan continues from proc[5]: pid 6 is RUNNING on hart 1, pid 7 RUNNING on hart 0, the remaining slots are unused. Each is locked and unlocked in turn, one lock at a time. found is 1, so no wfi; the outer loop opens its one-instruction interrupt window (lines 441–442) and starts again at proc[0].

Step 9 of 19

The scheduler picks B

proc[0] (init), proc[1] (sh) and proc[2] (usertests) are SLEEPING. proc[3] is pid 4, B, RUNNABLE. Hart 2 takes its lock, sets RUNNING, sets c->proc, and calls swtch(&c->context, &p->context).

Row 9 · hart 2 · S · scheduler stack · kernel page table · B (assigned, not yet running) · locks: B’s p->lock

What hart 2 is about to load is not where B’s user program was, nor where a fresh process starts. B’s context was saved by swtch when B fell asleep in a read: ra = 0x80001e9c, the instruction after the swtch call in sched, and sp = 0x3fffff7eb0, 336 bytes down KSTACK(3). A process preempted by the timer, like A, would resume in yield; B resumes in sleep. To the scheduler it makes no difference: every suspended process is suspended at the same instruction, inside sched, and swtch neither knows nor cares how it got there.

Step 10 of 19

T6, swtch #2: onto B's kernel stack, deep inside a read

The second swtch loads B’s 14 registers. sp jumps from 0x8000a810 to 0x3fffff7eb0, and ret lands in sched after its swtch call. sched restores B’s intena and returns into sleep, which releases B’s p->lock at line 571: the lock hart 2’s scheduler took a moment ago.

B’s saved intena is 1: B called sleep from inside a system call, with interrupts on. So the release at line 571, which takes noff from 1 to 0, turns interrupts back on, while A’s resumption in row 17 will leave them off. The flag travels with the thread, not the hart (Locks and interrupt state; Tour 50: noff and intena through a sleep, a yield and an interrupt follows noff and intena through a sleep, a yield and an interrupt).

Row 10 · hart 2 · S · B’s kernel stack (KSTACK(3)) · kernel page table · B · locks: B’s p->lock, released at line 571

B’s stack has been waiting, untouched, since B slept:

KSTACK(3), top 0x3fffff8000          (gdb, this build)
  usertrap  ra → userret
  syscall
  sys_read
  fileread
  piperead  (pipe.c:127, after sleep())
  sleep
  sched     ◄─ sp 0x3fffff7eb0

Now B unwinds. piperead re-takes pi->lock, finds one byte, copies 'x' to the user buffer with copyout, and returns 1. The frames pop one by one up to usertrap. The stack shrinks back toward its empty state.

Step 11 of 19

B's way out, prepared with interrupts off

B’s read was a system call, so usertrap had turned interrupts on before it slept, and they came back on with B’s intena when sleep released its lock. prepare_return turns them off again first: line 112 is about to point stvec at the trampoline, and a kernel interrupt from then on would land in user-trap code (Tour 48: Breaking the invariants breaks this).

Then it writes the four kernel fields of B’s trapframe for B’s next trap: kernel_satp, kernel_sp = 0x3fffff8000, kernel_trap, and kernel_hartid = 2. B slept on hart 2 and woke on hart 2 in this run, so 2 overwrites 2; had it woken elsewhere, this line would be what keeps its next tp right. Finally sstatus gets SPP = 0, SPIE = 1, and sepc gets 0x5772, the ret just after read’s ecall in the binary.

Row 11 · hart 2 · S · B’s kernel stack · kernel page table · B · locks: none · stvec = uservec already

usertrap returns B’s satp value, 0x8000000000080022 in our run, in a0, and returns into the trampoline.

Step 12 of 19

T5: userret, and the moment with no stack

userret runs fence.i, then switches to B’s page table with csrw satp, a0 between two sfence.vma: the slice’s second page-table switch. sp still holds 0x3fffff8000, the top of B’s kernel stack, but B’s page table does not map it. From here until sret hart 2 again has no usable stack: for a few instructions this address, then B’s user sp, which supervisor code cannot use.

Row 12 · hart 2 · S · none (sp = 0x3fffff8000, unmapped) · B’s page table · B · locks: none

This row is the mirror of row 3. On the way in, uservec changed sp first and satp second. On the way out, userret changes satp first and sp second. The order is forced by the trapframe: both ld sp instructions read through TRAPFRAME, which only user page tables map. As a consequence, the user’s sp value is never paired with the kernel page table, and the kernel’s C code never runs with a user page table. The trampoline covers both gaps, and it uses no stack at all.

Step 13 of 19

ld sp, sret, and B is in user mode

Line 118 loads B’s user sp, 0x11e80, from the trapframe; lines 117–146 restore the other user registers, and line 149 loads a0 last: the value 1, read’s result. Then sret: the mode becomes U (from SPP = 0), SIE becomes 1 (from SPIE), and pc becomes sepc = 0x5772. That is T5. Between line 118 and the sret, sp already holds B’s user stack pointer, but the hart is still in supervisor mode, which cannot use user pages, so there is no usable stack (the state above); the sret makes it B’s user stack.

Row 13 · hart 2 · S → U at sret · B’s user stack (0x11e80) · B’s page table · B · locks: none

Seven rows ago hart 2 was all A’s. Now it is all B’s: B’s registers, B’s page table, B’s user stack, and an sepc that pointed into B’s code. Only stvec and stimecmp are the hart’s again. Between rows 1 and 13, hart 2 stood on four different stacks: A’s user stack, A’s kernel stack, its own scheduler stack and B’s kernel stack. It is now on a fifth, B’s user stack.

Step 14 of 19

B's twenty quick system calls

read returned 1, so B goes on: close, printf("kill... "), three kills, printf("wait... "). User-space printf writes one byte per write call (user/printf.c:12), so that is 1 + 8 + 3 + 8 = 20 system calls, none of which slept in our run. Each is a complete T1 and T5, exactly like Tour 5: Life of a system call:

Row 14 (×20) · hart 2 · U ↔ S · B’s user stack ↔ B’s kernel stack · B’s page table ↔ kernel page table · B · locks: various, all released before sret

In our run, each of the 16 one-byte writes was followed by a UART interrupt that hart 2 took inside that write, with interrupts on: transition T7, a 256-byte kernelvec frame pushed onto B’s kernel stack and popped again, with no change of mode, stack or page table. The 3 kills set killed = 1 in A, pid 6 and pid 7, under each one’s p->lock (kkill). A is RUNNABLE, not SLEEPING, so kill does not change A’s state.

Step 15 of 19

wait sleeps, and swtch

The 21st system call is wait(0). kwait scans for B’s children under wait_lock. Pid 5, 6 and 7 have been killed, but none is a ZOMBIE yet: each must first reach a trap. So B registers on its own address as a channel (sleep_prepare), releases wait_lock, and calls sleep, which takes B’s p->lock, sets SLEEPING, and calls sched. swtch #3 moves sp from 0x3fffff7f00 to 0x8000a810.

Row 15 · hart 2 · S · B’s kernel stack → scheduler stack · kernel page table · B → none · locks: B’s p->lock (handed to the scheduler)

The frames left behind on KSTACK(3) are different from last time: usertrap, syscall, sys_wait, kwait, sleep, sched, 256 bytes in our build. A kernel stack is a record of why a process stopped, and this one now says “waiting for a child”.

B entered the kernel with ecall (T1) and will not return to user mode in this slice. That is the one system call without its T5.

Step 16 of 19

T6, swtch #4: the scheduler resumes A, where it left off

Hart 2’s scheduler returns from the swtch that started B, inside the iteration with p = proc[3]. It clears c->proc and releases B’s lock. This is the case line 456 exists for: swtch came back with B’s intena, 1, in cpus[2], and without the reset that release would have turned interrupts on in the middle of the scan (Locks and interrupt state). Then the for loop simply continues to the next slot, proc[4]: A, still RUNNABLE. The scheduler takes A’s lock, marks it RUNNING, and calls swtch #4.

Row 16 · hart 2 · S · scheduler stack · kernel page table · A (assigned) · locks: A’s p->lock

A is the only RUNNABLE process at this moment, so any scan would find it; the slot order only decides how long the scan takes. Another hart could have taken A first only if its timer had fired during B’s slice, and then hart 2 would have run someone else next.

The scheduler’s stack held the same frames at the same addresses (start’s abandoned 16 bytes, main, scheduler) through rows 7–9 and 15–16. While B ran, nothing used it: it is reserved for the moments when hart 2 runs no process at all.

Step 17 of 19

A wakes up inside sched, as if nothing happened

swtch loads proc[4].context, saved in row 7: sp = 0x3fffff5f90, ra = 0x80001e9c. The three frames A left (usertrap, yield, sched) are exactly where they were. sched restores A’s intena (0, since A came in through a timer trap), returns to yield, and yield releases the lock the scheduler took.

Row 17 · hart 2 · S · A’s kernel stack · kernel page table · A · locks: A’s p->lock, released at line 507

Something did change while A was frozen: B set A->killed = 1. A will not notice yet. After yield returns, usertrap goes straight to prepare_return (lines 85–94): there is no killed check after the yield. So A goes back to user mode, killed or not, and dies at its next trap.

Step 18 of 19

T5 again: A runs its jump

prepare_return repeats row 11 for A: interrupts off, stvec = trampoline, the trapframe’s kernel fields (kernel_sp = 0x3fffff6000, kernel_hartid = 2), SPP = 0, SPIE = 1, sepc = 0x3a7a. usertrap returns A’s satp (0x800000000008003a), and userret does rows 12 and 13 for A: csrw satp, no stack, ld sp = 0x11e80, sret.

Row 18 · hart 2 · U · A’s user stack (0x11e80) · A’s page table · A · locks: none

Row 18 is row 1 again: every register A can see holds exactly the value it held in row 1, restored from the trapframe. Only CSRs that A cannot read (stimecmp, scause, sscratch) remember that anything happened. A executes j 0x3a7a, the jump the tick interrupted. From A’s point of view one instruction took a little longer than usual; in our trace, about 51 ms. In our run A’s next tick came about 60 ms later: usertrap saw killed, and A exited (Tour 21: exit, wait and zombies).

Step 19 of 19

The grand state table, read whole

Counted literally, on hart 2, from A’s tick to A’s sret: T4 1, T1 21, T5 22, T6 4 (swtch calls), T7 16 (UART, in our run), T2, T3 and T8 0. That is 44 privilege changes (22 up, 22 down), 44 csrw satp, 88 sfence.vma, 22 fence.i, and 48 stack switches: 22 + 22 ld sp in the trampoline and 4 in swtch (kernel/swtch.S:26). It used 5 stacks and 3 page tables. And the four lock hand-offs across swtch were the only moments a lock was held while sp moved.

Which of these were forced? Each csrw satp is forced by xv6’s design: the kernel is not mapped in user page tables, and the hardware changes the mode but never the page table. Many kernels map themselves into every process’s page table and skip this switch. Each stack switch is forced too: by a new page table (the trampoline) or by a new thread (swtch). The privilege level never changed without the page table following it within a few instructions. That pairing is the dance.