Step 1 of 21

Power-on: pc = 0x1000, sp = 0

QEMU starts every hart in machine mode at 0x1000, a small boot ROM it provides. gdb’s first look, before a single instruction ran:

0x1000: auipc t0, 0x0
0x1004: addi  a2, t0, 40
0x1008: csrr  a0, mhartid      # a0 = this hart's number
0x100c: ld    a1, 32(t0)       # a1 = 0x87e00000, a device-tree address
0x1010: ld    t0, 24(t0)       # t0 = 0x80000000
0x1014: jr    t0

The two words after the code hold 0x80000000 and 0x87e00000. So the ROM jumps every hart to 0x80000000, where the linker put _entry (kernel/kernel.ld). xv6 ignores the device tree in a1.

At this point sp is 0, on all three harts. There is no stack: nothing may call a function or push anything. The ROM doesn’t need one, and the first five instructions of _entry don’t either. Tour 2: Power-on to main, on every hart at once tells the boot story; this tour watches sp.

Step 2 of 21

_entry gives each hart a slice of stack0

Six instructions compute sp = stack0 + (hartid + 1) * 4096. In this build stack0 is at 0x80007890 (kernel/kernel.sym), so:

Why hartid + 1? A RISC-V stack grows down: a push first subtracts from sp. So each hart’s sp starts at the top of its slice, which is the bottom of the next hart’s slice.

This is the first of the four instructions in xv6 that move sp onto a different stack (The stacks of xv6). Its stack is the boot stack.

Every hart computes its own answer from its own mhartid, so no lock and no coordination are needed: hardware gives each hart a different number.

Step 3 of 21

One array, eight slices, no guard page

stack0 is an ordinary global array: 4096 * NCPU bytes, and NCPU is 8, so 32 KiB, of which three slices are used on our three-hart machine.

Step 4 of 21

start runs in machine mode on the boot stack

call start (entry.S line 19) puts the return address in ra; RISC-V’s call pushes nothing. start's compiled prologue then takes 16 bytes of stack for itself: sp goes from 0x80008890 to 0x80008880.

start runs entirely in machine mode, with no page table (satp = 0: machine mode doesn’t translate addresses at all). It is preparing a fake trap return: MPP = S (“the trap came from supervisor mode”) and mepc = main (“…at this address”). Tour 46: Boot: returning from a trap that never happened tells that story; here, notice what start does not prepare: a new stack. The mret ahead won’t touch sp.

start also turns on two extensions in menvcfg: Svadu (line 41, the hardware updates the accessed and dirty bits in page-table entries) and Sstc (in timerinit, a supervisor timer). gdb read menvcfg = 0xa000000000000000 just before mret: bit 63 (STCE) and bit 61 (ADUE).

Step 5 of 21

mret changes the mode, and leaves sp alone

gdb on hart 0 at the mret (0x800000ca) and again at main’s first instruction:

sp is unchanged, so main starts on the same slice, just below start’s 16-byte frame. That frame stays there forever: start never returns, and main never will either.

After this instruction, no hart re-enters machine mode for the rest of the run. mtvec and mscratch are never written in this tree; gdb read both as 0 at main. Every trap is delegated to supervisor mode, and the timer is a supervisor timer.

Step 6 of 21

main, on the boot stack with paging off

main is in supervisor mode, and satp is still 0, so addresses are physical. Hart 0 now builds the kernel: console, allocator, page table, process table and the rest, all as ordinary C calls on this 4 KiB slice. Every call pushes a frame below 0x80008870 and pops it on return.

Interrupts are off (sstatus.SIE = 0; gdb read sstatus = 0x200000000), and stay off until the scheduler. Nothing can interrupt the setup, so nothing needs a stack of its own for interrupts yet.

The next three steps follow three things hart 0 builds that decide where sp will go later.

Step 7 of 21

The kernel stacks exist before any process does

kvminit → kvmmake → proc_mapstacks allocates 64 pages, one per process slot, and maps each at KSTACK(i) in the kernel page table it is building:

KSTACK(i) is TRAMPOLINE - (i+1) * 2 * 4096 (kernel/memlayout.h:52): the stacks are two pages apart, and the page below each one is never mapped. That unmapped page is the guard page: an overflow faults instead of corrupting the next stack.

These stacks are allocated once, at boot, and never freed. They belong to the slot, not to a process. allocproc doesn’t allocate a kernel stack; it finds one waiting. (The stacks of xv6)

Step 8 of 21

Paging turns on, and the boot stack survives it

kvminithart writes satp = 0x8000000000087fff (measured): Sv39, root page table at physical 0x87fff000. From the next instruction on, every address hart 0 uses, including sp and the pc, goes through that table.

Why doesn’t the stack vanish? Because kvmmake mapped all of the kernel’s data and free RAM at the same virtual address as its physical address (kernel/vm.c:42), read-write. stack0 lives at 0x80007890, inside that range, so sp = 0x8000886x means the same bytes before and after the switch. The kernel’s own code is mapped the same way, which is why the pc survives too.

This csrw satp is the only satp write outside the trampoline (apart from start’s w_satp(0)), and it runs once per hart. The trampoline will do the rest.

Step 9 of 21

allocproc forges a context that points at an empty stack

userinit calls allocproc, which takes slot 0 for pid 1, init. Lines 145–147 are the most important lines for this tour:

p->context.ra = forkret          (0x8000193a)
p->context.sp = p->kstack + 4096 (0x3fffffe000)

Nothing has run on this process yet, so there is no real context to save. allocproc writes one by hand. When a scheduler later switches to it, swtch will “return” to forkret with sp at the top of slot 0’s kernel stack: empty.

The process also gets a trapframe page from kalloc, filled with the junk byte 0x05. gdb printed every field of init’s trapframe as 0x0505050505050505 at this point. That will matter at the very end.

allocproc returns holding init’s p->lock; userinit marks it RUNNABLE and releases it.

Step 10 of 21

main calls scheduler, and the boot stack changes its job

main calls scheduler, which never returns. No instruction moved sp to a new stack: gdb read 0x80008870 at scheduler’s first instruction, just below main’s 16-byte frame. Same memory, new role. From now on this slice is hart 0’s scheduler stack.

hart 0's slice of stack0
  0x80008890 ─ top
  0x80008880   start's frame   (16 bytes, dead)
  0x80008870   main's frame    (16 bytes, dead)
  0x80008810   scheduler's frame (96 bytes, live forever)
  0x80007890 ─ bottom

This is why the scheduler stack isn’t part of struct cpu and isn’t allocated anywhere: it is simply the stack the hart was already standing on. The frame is 96 bytes because the prologue saves ra and s0–s9, the callee-saved registers in which the loop keeps all its variables. The functions it calls (acquire, release, swtch) push their own frames briefly below it.

Step 11 of 21

Hart 0's scheduler picks init

The loop opens the interrupt window (lines 441–442, the subject of Tour 44: One interrupt, three landing sites), then scans the table. Slot 0 is RUNNABLE. Under init’s p->lock, the scheduler marks it RUNNING, sets c->proc, and calls swtch(&c->context, &p->context).

In our run hart 0 got there first. That isn’t guaranteed: hart 0 set started and walked straight into scheduler(), while harts 1 and 2 still had to print “hart N starting” and set up paging, so hart 0 has a head start, but only a head start.

The lock is held across the switch. It will be released on the other side, by code running on a different stack (Tour 13: swtch and the lock handed across a context switch).

Step 12 of 21

swtch saves where the scheduler stands

Fourteen stores into cpus[0].context. gdb printed the result later, from forkret:

This is all the scheduler needs to continue later: where to return, which stack, and its callee-saved registers. struct context is a save area, not a stack (The stacks of xv6).

swtch is plain code: no CSR, no mode change, no page-table change. It is S-mode on the kernel page table before, during and after.

Step 13 of 21

One load, and sp is on init's kernel stack

ld sp, 8(a1) loads the forged p->context.sp: 0x3fffffe000. This is the third of the four stack-switching instructions. The remaining loads fill s0–s11 with zeros (allocproc cleared the context), and ret jumps to ra, which is forkret.

gdb at forkret’s first instruction:

forkret has no caller. Its stack is empty, and its ra points at itself. It can never return; it must leave some other way, and it will, through the trampoline.

Step 14 of 21

forkret releases the lock; interrupts stay off

Line 520 releases the p->lock that hart 0’s scheduler took. release calls pop_off, which turns interrupts on only if intena is 1. It is 0: when the scheduler did acquire, interrupts were already off (line 442). The lock and its noff level crossed swtch together, and the release brings noff from 1 to 0 without touching SIE (Locks and interrupt state, Locks and interrupt state). So interrupts stay off, and they will stay off for the whole of forkret on this first run (gdb later read SIE = 0 inside kexec too).

Then the one-time work: fsinit reads the superblock and recovers the log, and kexec loads /init. Both need the disk, and the disk means sleeping, which needs a process with a kernel stack. That is why this happens here and not in main (kernel/proc.c:525).

Step 15 of 21

init sleeps, and hart 0 goes back to its own stack

readsb → bread → virtio_disk_rw starts a read of block 1 and must wait. In sleep, init marks itself SLEEPING and calls sched. gdb at sched’s entry read sp = 0x3fffffdf00 on hart 0. Then swtch loads cpus[0].context, and hart 0’s sp goes back to 0x80008810, its scheduler stack, exactly where step 12 left it.

Here the tour has to choose between the hart and the stack. Hart 0 now loops in its scheduler. init’s kernel stack holds five frames (readsb is inlined into fsinit), six once sched pushes its own, and waits. When the disk interrupt wakes init, whichever hart’s scheduler finds it first loads init’s saved sp and continues on this stack.

In our run init went to sleep 19 times before it reached user mode (disk reads in fsinit and kexec), and resumed on harts 0, 1 and 2 in turn. Its final stretch ran on hart 1. (In another run it was hart 2.) The stack is the thread; the hart is only where it happens to run.

Step 16 of 21

kexec builds init's user stack

kexec runs on init’s kernel stack (on hart 1, in our run) and builds a whole new address space in a page table that isn’t installed anywhere. After loading the program (which ends below 0x2000), it allocates two more pages and makes the lower one a guard by clearing PTE_U (uvmclear). gdb at line 137:

0x3fe0 holds the argv array: argv[0] = 0x3ff0 (the string "/init", 6 bytes rounded to 16), argv[1] = 0. Lines 136–137 store 0xbc and 0x3fe0 into the trapframe. Nothing runs on this stack yet: it is a promise, written into memory that only init’s new page table can reach.

Step 17 of 21

prepare_return, on whatever hart this is

Back in forkret, prepare_return fills in what the trap hardware and the trampoline will need (Tour 43: A system call, CSR by CSR walks through it CSR by CSR). On hart 1 (the CSR rows measured; the trapframe rows follow from lines 117 and 119 and the junk kalloc left):

sepc held 0x80001e10 before: an address inside hart 1’s scheduler, left by the last interrupt hart 1 took there. CSRs belong to the hart, and they hold whatever that hart did last.

kernel_sp is the top again, 0x3fffffe000. The next time init traps, its kernel stack will be empty, whatever is on it now.

Step 18 of 21

forkret jumps into the trampoline

A process returning from a trap gets to userret because usertrap returns there (its ra was set by jalr in uservec). forkret has no such return address, so it calls userret directly, through a function pointer:

The jump lands on the trampoline’s high address. The kernel page table maps it there too (kernel/vm.c:47), which is what lets the very next instruction survive the switch to init’s page table. We checked what happens if it doesn’t: with line 47 removed, the first thing to fail is this jump. The fetch at 0x3ffffff09c faults (scause = 12), and the hart loops on faults at stvec forever (quiz, Tour 41: Every transition: mode, stack and page table).

Step 19 of 21

The page table switches; sp points at nothing

sp didn’t change, but its meaning did. init’s page table has the trampoline and the trapframe at the top, and the program from 0 to 0x4000. Nothing at 0x3fffffdfd0. From here until sret hart 1 has no usable stack (for five instructions this unmapped address, then, from line 118, the user’s sp), and userret uses none.

The frames still sitting on slot 0’s kernel stack (forkret’s, prepare_return’s) are simply abandoned. Nobody pops them. The next trap reloads sp from kernel_sp, the top, and writes over them.

Step 20 of 21

ld sp, and init has a stack of its own

The fourth and last stack switch: ld sp, 48(a0) loads trapframe->sp, the value kexec stored, 0x3fe0. gdb at the sret (0x3ffffff120):

sp now points into init’s user stack, but the hart is still in supervisor mode, which cannot use user pages, so until sret there is no usable stack and the code pushes nothing. This is the mirror of uservec's line 76: the address is loaded first, and something else (there csrw satp, here sret) makes it usable.

Every user register except sp, a0 and a1 is junk on init’s first entry. That’s harmless: start and main set what they use. The tp junk is inherited by every process init forks, which is why the user tp we see in Tour 43: A system call, CSR by CSR has the same value.

Step 21 of 21

sret, and the first user instruction

sret sets the mode to U, SIE to 1, and the pc to 0xbc, and leaves sp alone; the change of mode is what makes the user stack usable. gdb, one instruction after sret: pc = 0xbc, priv = 0, sp = 0x3fe0, and the instruction there is addi sp, sp, -16. The first thing init does in user mode is push a frame onto the stack kexec built for it.

Almost. In a second run, without single-stepping, the first event at 0xbc was a timer interrupt: sepc = 0xbc, scause = 0x8000000000000005. Interrupts had been off on this thread for its entire trip through forkret, so the tick was already pending. In user mode, supervisor interrupts are taken regardless of SIE, so it fired before 0xbc executed even once. init went straight back through uservec onto its empty kernel stack, then on to yield.

The figure above shows the whole journey, as sp saw it.