Step 1 of 27

allocproc claims a slot under its lock

userinit begins with allocproc, the same function kfork will use for every later process. It walks the table, taking each p->lock in turn, looking for UNUSED. proc[0] is free, so it jumps to found still holding proc[0].lock.

allocpid takes pid_lock for an instant to hand out the next pid: 1. Then p->state = USED: the slot is reserved but not yet runnable.

Holding p->lock from the check to the claim is what makes “find a free slot” safe. Right now no other hart can compete, but later two harts forking at once will both run this loop, and without the lock both could see the same UNUSED slot and both take it.

Step 2 of 27

A trapframe, a page table and a kernel context

Still under the lock, allocproc gives the process what it needs to run in the kernel. In this build, gdb shows:

The four pages (trapframe, page-table root, and two lower-level page-table pages for the top of the address space) cost four trips through kmem.lock.

The context is the trick that starts every process. swtch restores ra and sp and executes ret, which jumps to ra. So the first time any scheduler switches to this process, it will “return” into forkret on this process’s own kernel stack, as if the process had been running there all along.

Step 3 of 27

userinit marks process 1 runnable

Back in userinit, three short lines and one remarkable omission.

• initproc = p: the kernel remembers process 1. Orphans will be given to it.
• p->cwd = namei("/"): the working directory is the root. This only reserves an in-memory inode slot for inode 1 under itable.lock; it does not read the disk.
• p->state = RUNNABLE, then release the lock.

The omission: no user memory. p->sz is 0. There is no program in this address space, not even a tiny bootstrap. Older versions of xv6 copied a hand-assembled initcode here; this version does not. Process 1 will get its program the same way every other process does, from the file system with kexec, and it will do that from inside the kernel before ever reaching user mode.

Line 33 of main then sets started (Tour 3: main: one hart builds the kernel, the others wait), and all three harts head for their schedulers.

Step 4 of 27

Three schedulers race for process 1

Each hart’s scheduler scans proc[0] through proc[63], taking each p->lock and checking for RUNNABLE. Only proc[0] qualifies. In the run this tour follows, hart 0 got there first; in other runs, hart 1 did.

Each hart scans on its own scheduler stack: the same slice of stack0 it booted on, which became the scheduler stack when main called scheduler and never got control back (Tour 3: main: one hart builds the kernel, the others wait).

The winner, holding proc[0].lock:

1. sets p->state = RUNNING, so that other schedulers will skip it;
2. sets cpus[0].proc = p, so that myproc on this hart returns process 1;
3. calls swtch to switch from the scheduler’s context to the process’s.

It does not release proc[0].lock before switching. The lock travels with the switch, and the process releases it, in forkret here, or after sched() returns in yield or sleep for a process that stopped earlier. The same hand-off in the other direction is the one that matters: a process giving up the hart keeps p->lock until the scheduler is running on its own stack, so no other hart can resume it while its registers are still being saved (Tour 13: swtch and the lock handed across a context switch). The scheduler took the lock right after intr_off() on line 442, so hart 0 has noff = 1, intena = 0, and that one push_off level crosses the switch together with the lock (Locks and interrupt state).

Step 5 of 27

swtch saves the scheduler

swtch saves the scheduler’s callee-saved registers (ra, sp, s0–s11) into cpus[0].context, then starts loading the process’s from proc[0].context: line 25 loads ra = forkret.

Line 11 is the one to watch: sd sp, 8(a0) records where hart 0’s scheduler stack stands, 0x80008810, just below scheduler’s frame. cpus[0].context is only a save area, not a stack; the scheduler’s frames stay where they are, in hart 0’s slice of stack0, and the saved sp is the way back to them.

Step 6 of 27

ld sp: onto process 1's empty kernel stack

Line 26, ld sp, 8(a1), is the moment hart 0 leaves its scheduler stack. Only two of the values loaded from proc[0].context are non-zero, and allocproc put both there: ra = forkret and sp = 0x3fffffe000, the top of KSTACK(0).

hart 0's stack0 slice                process 1's kernel stack, KSTACK(0)
  start (abandoned), main,             0x3fffffe000 top ◄─ sp
  scheduler                            … nothing: never used …
  (saved sp 0x80008810                 0x3fffffd000 bottom, guard page below
   in cpus[0].context)

The final ret jumps to ra. Hart 0 is now running forkret, on process 1’s kernel stack, as process 1. Nothing was “returned to”: this is the first time this kernel thread has ever run, and its stack is empty. That is why the call stack above shows only swtch: the scheduler’s frames are still in hart 0’s slice of stack0, but they are no longer on the stack sp points into. This ld sp is one of only four instructions in xv6 that switch stacks (The stacks of xv6); it never goes from one process’s stack straight to another’s, only between a process and a scheduler.

Step 7 of 27

forkret, the first code process 1 runs

forkret first releases p->lock, the lock the scheduler acquired on this process’s behalf. Now other schedulers may look at proc[0] again (they will see RUNNING and skip it).

Then the static int first. Process 1 is the only process that will ever see it set. It clears it and calls fsinit, with a comment that says why this could not happen in main: reading the disk means sleeping, and only a process can sleep.

Part of the reason is the stack. gdb shows sp = 0x3fffffe000 at forkret’s first instruction; its prologue pushes the first frame process 1’s kernel stack has ever held (48 bytes). A sleeping thread leaves its frames on its own stack while the hart goes off to run something else. main had only the hart’s boot stack, which the hart itself keeps using, so it had nowhere to leave them.

Interrupts stay off here, and that surprises people. The scheduler’s acquire recorded “interrupts were off” in cpus[0].intena, so the release on line 520 leaves them off (Locks and interrupt state). Process 1 will run fsinit and kexec with interrupts off on its hart, and no timer can preempt it until it reaches user mode. Its disk interrupts are taken by a hart that is idling in its scheduler loop, which briefly enables interrupts on every pass. That includes process 1’s own hart once process 1 is asleep.

Step 8 of 27

fsinit reads block 1

fsinit reads the superblock, block 1 of fs.img, the block mkfs wrote in Tour 1: From make qemu to a disk image and a kernel. bread asks the buffer cache: block 1 is not cached, so bget takes bcache.lock, recycles a free buffer, releases bcache.lock, and acquires the buffer’s sleep-lock. Then virtio_disk_rw sends a read request to the disk.

When the data arrives, readsb copies it into the global sb: magic = 0x10203040, size = 2000, nlog = 31, logstart = 2, inodestart = 33, bmapstart = 46. The magic number check on line 45 is the kernel’s only defense against booting from a disk that is not an xv6 file system.

Then initlog (next step but one) and ireclaim, which reads all 13 inode blocks (33–45) looking for inodes that were orphaned by a crash. On a fresh image it finds none.

Step 9 of 27

Waiting for the disk, and waking up somewhere else

The disk is a separate device. After virtio_disk_rw notifies it (line 284), the process must wait for the completion interrupt. It registers on the channel b with sleep_prepare, releases disk.vdisk_lock, and calls sleep, which marks it SLEEPING under p->lock and switches back to hart 0’s scheduler (Tour 16: sleep and wakeup, and the lost-wakeup problem).

Process 1 is now frozen inside virtio_disk_rw, still holding the buffer’s sleep-lock, which is allowed: sleep-locks may be held while sleeping. It must not hold vdisk_lock (a spinlock) while asleep, because the interrupt handler needs it. sched saves process 1’s intena, 0 (it has had interrupts off since forkret), and puts it back on whichever hart resumes it, so process 1 keeps running with interrupts off there too (Locks and interrupt state).

Frozen means: its frames stay on its kernel stack, and the ld sp, 8(a1) in swtch, called from sched, moves hart 0’s sp back to the scheduler stack.

process 1's kernel stack, KSTACK(0), while it sleeps
  0x3fffffe000 top
               forkret
               fsinit     (readsb is inlined here in this build: no frame of its own)
               bread
               virtio_disk_rw
               sleep
               sched      ◄─ p->context.sp (saved by swtch)

The disk finishes. Its interrupt goes to whichever hart claims it at the PLIC. virtio_disk_intr takes vdisk_lock, sets b->disk = 0, and calls wakeup(b), which makes process 1 RUNNABLE. Then any scheduler may pick it up. In the traced run, fsinit started on hart 0, and by the time it reached ireclaim process 1 was running on hart 2.

Step 10 of 27

initlog creates the last boot lock

initlog creates log.lock, the one lock main did not create, and points the log at block 2.

recover_from_log then does what a file system must do on every boot before anything else touches the disk: read the log header (block 2), and if it describes a committed transaction that may not have reached its home blocks, copy those blocks into place (Tour 32: Crash recovery). On a fresh image the header says n = 0: nothing to do. Then it writes the empty header back.

Doing this here, before kexec reads a single file, guarantees that no process ever sees a half-applied transaction from before a crash. It is the second reason fsinit must run in a process: these reads and the write all sleep for the disk.

Step 11 of 27

kexec opens /init

Line 532 of forkret calls kexec("/init", {"/init", 0}), the kernel half of the exec system call, called directly. It is the same code that will later replace the shell’s child with ls or cat (Tour 22: exec).

• begin_op joins a file-system transaction (log.lock held briefly).
• namei("/init") locks the root inode (inode 1, block 33), reads the root directory (block 47), finds the entry init → inode 7.
• ilock takes inode 7’s sleep-lock and copies the inode out of block 33 (already in the buffer cache from ireclaim).
• readi reads the ELF header from the file’s first block, 189. Magic number OK, entry point 0xbc, 4 program headers.
• proc_pagetable builds a new page table. The old one, from allocproc, stays in use until the new image is complete.

Each of those reads may sleep on the disk, and each sleep is another chance for process 1 to change harts.

Step 12 of 27

Loading the two segments

Of the 4 program headers, 2 are LOAD (the other two describe RISC-V attributes and the stack and are skipped):

For each, uvmalloc allocates zeroed pages (under kmem.lock) and maps them with PTE_U plus the segment’s permissions, then loadseg reads the bytes from the file into those pages through their kernel addresses. After both, sz = 0x1030.

iunlockput releases inode 7’s sleep-lock and end_op ends the transaction. Nothing was written to the disk, so the commit has nothing to do.

Step 13 of 27

The user stack and the point of no return

kexec rounds sz up to 0x2000 and adds two pages: a guard page at 0x2000–0x3000 (made inaccessible to user mode by uvmclear) and the stack page 0x3000–0x4000. Then it builds main’s arguments at the top of the stack:

Lines 133–138 commit: the process gets the new page table, sz = 0x4000, saved epc = 0xbc (start), saved sp = 0x3fe0, and a1 = 0x3fe0 (argv). The empty page table from allocproc is freed. kexec returns argc = 1, which forkret stores in a0.

Two stacks are involved here, and only one is in use. The hart is running kexec on process 1’s kernel stack. The new user stack is just a page in the new page table: kexec writes the strings and argv into it with copyout, through that table, and nobody’s sp points into it yet. Line 137 only prepares a future sp: the value in the trapframe that userret will load (The stacks of xv6).

Everything up to line 133 can fail and leave the process unchanged. After it, the old image is gone. For process 1 the old image was empty, but for every later exec this ordering is what lets a failed exec return -1 to a program that still exists.

Step 14 of 27

forkret heads for user mode

The last disk read in kexec slept, and in the traced run process 1 woke up on hart 0 again. So the remaining lines of forkret run on hart 0.

Lines 539–542 do by hand what usertrap does at the end of every system call:

1. prepare_return sets up the trapframe and the CSRs for the trip to user mode (next step).
2. MAKE_SATP(p->pagetable): the satp value for process 1’s new page table.
3. Compute the address of userret in the trampoline page, TRAMPOLINE + (userret - trampoline) = 0x3ffffff09c, and call it as a function with satp as its argument.

Why not call userret at its kernel address, 0x8000609c? Because userret switches to the user page table, and the kernel address is not mapped there. The trampoline address is mapped in both, so the instruction after the satp switch can still be fetched.

Step 15 of 27

prepare_return records hart 0 in the trapframe

prepare_return fills in the trapframe fields the trampoline will need the next time process 1 traps into the kernel:

and the registers sret will use: stvec = uservec in the trampoline, sstatus.SPP = 0 (return to user mode), sstatus.SPIE = 1 (interrupts on in user mode), sepc = 0xbc.

kernel_sp is the top of the stack, not the current sp (which is 0x3fffffdfc0, below the frames of forkret and prepare_return). userret never returns, so forkret’s frame is simply abandoned, and the next trap from user mode starts on an empty kernel stack. That is true of every trap: a process in user mode has nothing on its kernel stack.

kernel_hartid = 0 is correct because a process in user mode never changes hart: it will trap back into the kernel on hart 0. After that trap, the kernel may move it, and the next prepare_return records the new hart (Tour 5: Life of a system call).

Interrupts were already off (forkret never turned them on), and the intr_off on line 108 keeps them off while stvec points at user-trap code.

Step 16 of 27

userret switches to init's page table

userret, running from the trampoline page:

• fence.i (line 107) makes this hart’s instruction fetches see the code that was just written to memory. init’s code was written by loadseg as ordinary data stores, perhaps on another hart, and is about to be executed as instructions. (xv6 runs fence.i on every return to user, needed or not.)
• sfence.vma, csrw satp, a0, sfence.vma: switch hart 0 to process 1’s page table. The trampoline is mapped at 0x3ffffff000 there too, so execution continues.

Now look at sp. It still holds 0x3fffffdfd0, an address inside process 1’s kernel stack, but the page table that was just installed does not map the kernel stacks. From here until sret the hart has no usable stack at all: first this address, then, from line 118, the user’s sp, which supervisor code cannot use. That is fine because the trampoline never pushes anything; it only loads from TRAPFRAME, which this table does map.

Step 17 of 27

ld sp, then sret: user mode for the first time

• Restore every user register from the trapframe. Only three were set by the kernel: sp = 0x3fe0, a0 = 1, a1 = 0x3fe0. The rest still hold the junk byte that kalloc filled the trapframe page with (0x0505050505050505). That is harmless, because start never reads a register before writing it.
• sret (line 153): mode becomes user, interrupts are enabled (from SPIE), and pc = sepc = 0xbc.

Line 118, ld sp, 48(a0), moves sp to init’s user stack: sp = 0x3fe0, pointing at the argv array that kexec built. From here to sret the hart is still in supervisor mode with the user page table, and supervisor code cannot use user pages, so the strip says no usable stack and nothing is pushed. sret does not touch sp; by changing the mode to user it makes the stack usable, so the first user instruction finds it ready.

init's user stack page (0x3000–0x4000)
  0x4000 top
  0x3ff0 "/init"
  0x3fe0 argv[0] = 0x3ff0, argv[1] = 0   ◄─ sp
         … free …
  0x3000 bottom; guard page 0x2000–0x3000 below

Process 1’s kernel stack is left with nothing that matters on it: forkret’s frame is abandoned, and the next trap will start at its top again.

After the sret, process 1 is in user mode, with interrupts on, on hart 0, at the first instruction of start: the first user instruction this machine has run. (The state above shows the highlighted lines, after ld sp and before the sret.)

Step 18 of 27

init looks for the console and does not find it

start calls main(1, argv). The first thing init does is open console, a relative path, so it is looked up in the working directory, /.

On a fresh fs.img it fails. mkfs creates only directories and regular files (Tour 1: From make qemu to a disk image and a kernel), so there is no console entry. sys_open returns -1, and init creates the device file with mknod: a file of type T_DEVICE with major number CONSOLE (1). Then it opens it again.

This happens once per disk image. The next boot finds /console already there, and the first open succeeds.

From here on, every action of init is a system call, each with the full journey of Tour 5: Life of a system call, and each a chance to continue on a different hart.

Step 19 of 27

mknod creates inode 23

sys_mknod runs inside a file-system transaction (begin_op … end_op), because creating a file changes several disk blocks that must change together or not at all. create:

1. locks the root directory inode (sleep-lock) and checks that console does not exist;
2. ialloc scans the inode blocks for a free inode and finds 23, the first one after sync (22), in block 34;
3. locks the new inode, sets major = 1, minor = 0, nlink = 1, writes it;
4. dirlink adds the entry console → 23 to the root directory, in block 47;
5. unlocks the directory and returns the new inode still locked.

Line 428 releases inode 23. At end_op the transaction commits. Stopping in commit shows the log header listing 3 blocks: 34 (inode 23), 47 (the root directory) and 33 (the root inode, rewritten by writei). They are written to the log, the header is written, and then they are copied to their home locations (Tour 31: The log: begin_op, commit and group commit).

Step 20 of 27

open returns descriptor 0

The second open("console", O_RDWR) finds inode 23, locks it, and sees T_DEVICE.

• filealloc takes ftable.lock and claims the first free struct file: ftable.file[0], with ref = 1.
• fdalloc puts it in the first free slot of process 1’s ofile[]: 0.
• The file is FD_DEVICE, major 1. Reads and writes on it will go through devsw[1], set up by consoleinit in Tour 3: main: one hart builds the kernel, the others wait.

Descriptor 0 is standard input (standard input, output and error). init never says “make this standard input”: it is simply the lowest free number, and on a process with no open files that is 0. Every Unix shell relies on this lowest-free rule for redirection.

Step 21 of 27

dup, dup: three descriptors, one file

init calls dup(0) twice (user/init.c:23). Each sys_dup puts the same struct file * in the next free descriptor (1, then 2) and calls filedup, which increments ref under ftable.lock. Now:

Standard input, output and error are one open file. Every process from now on inherits these three descriptors through fork.

In the traced run, the open ran on hart 0 and the two dups on hart 2. The open itself never waited for the disk: blocks 34 and 47 were still in the buffer cache from mknod, and its transaction wrote nothing. What moved process 1 was a timer interrupt. User code and system calls run with interrupts on, so a tick can make the process yield (Tour 11: From a timer tick to a context switch), and then any hart’s scheduler can pick it up. A user program never notices which hart it is on.

Step 22 of 27

init: starting sh, then fork

printf("init: starting sh\n") writes to descriptor 1. The user-space printf sends each character with its own write(fd, &c, 1), so this one line is 18 system calls, each the full journey of Tour 5: Life of a system call. They reach consolewrite and the UART, and the line appears on your terminal.

Then fork. The parent (init, pid > 0) goes on to wait. The child (pid == 0) will exec("sh", argv) with argv = {"sh", 0}. The name is relative: it works because the child inherits init’s working directory, /, where mkfs put sh as inode 13.

If the shell ever exits, the outer for loop starts a new one. init itself must never exit: kexit panics if it tries.

Step 23 of 27

kfork and the lock dance

kfork calls allocproc (proc[1], pid 2, returned locked), copies init’s 4 pages of user memory with uvmcopy, copies the trapframe and sets the child’s a0 = 0 (so fork returns 0 in the child), and filedups descriptors 0–2: ftable.file[0].ref goes from 3 to 6.

What the child does not get is a copy of init’s kernel stack. allocproc gave it proc[1]'s own, KSTACK(1) (0x3fffffb000–0x3fffffc000), empty, with context.ra = forkret and context.sp = 0x3fffffc000, exactly as for process 1. Only the user stack is copied, as one of the 4 pages uvmcopy duplicates. Right now hart 2 is on init’s kernel stack, with usertrap … kfork on it.

Then a dance with three locks:

1. release(&np->lock);
2. acquire(&wait_lock), set np->parent = p, release;
3. acquire(&np->lock) again, set RUNNABLE, release.

Why not keep np->lock the whole time? Because xv6’s lock order says wait_lock must be taken before any p->lock (kernel/proc.c:26). kexit and kwait take them in that order; taking them in the opposite order here could deadlock against them, for example kexit on another hart holds wait_lock while its wakeup call acquires every p->lock, including np’s (Tour 18: Lock ordering: how xv6 avoids deadlock). The highlighted line is step 3, holding proc[1].lock with interrupts off. This acquire ran inside a system call with interrupts on, so push_off recorded intena = 1 and the release on line 302 turns them back on, unlike the release in forkret (step 7) (Locks and interrupt state).