Step 1 of 18

The shell's child needs sixteen pages

The shell forks a child to parse and run each command line (user/sh.c:172). Parsing builds a tree of command structs with malloc, and the child’s first malloc finds no free memory, so morecore asks the kernel for at least 4096 Headers: sbrk(65536), 64 KiB (user/umalloc.c:54). User sbrk is the eager kind (user/ulib.c:155), so sys_sbrk calls growproc, which calls uvmalloc.

uvmalloc loops over the new range one page at a time, and every iteration starts with kalloc: 16 pages, 16 calls. (Mapping them can call kalloc a few more times inside walk, for page-table pages.)

This thread holds no locks, and interrupts are on: usertrap turned them on before dispatching the system call. Keep those two facts in mind; the first thing acquire does is change the second one.

Step 2 of 18

One free list for the whole machine

Free physical pages are kept as a linked list threaded through the pages themselves (free-list allocator). kmem pairs the list head with the lock that protects it. In this build kmem sits at 0x8000f980 (kernel/kernel.sym): the lock’s locked word is at 0x8000f980 and freelist at 0x8000f998 (kmem+0x18).

kalloc pops the head: r = kmem.freelist; kmem.freelist = r->next. Compiled, that is a load from kmem+0x18, a load of r->next, and a store back to kmem+0x18 (0x80000b28, 0x80000b2e, 0x80000b34). Three instructions, and another hart can run its own three in between. Without a lock:

Both harts got page A. The program’s heap and a process’s saved registers now share memory. This is a textbook race condition: it needs exact timing, so it might happen once a week, and the crash comes long after the cause.

Step 3 of 18

A lock is one word

A spinlock is a uint: 0 means free, 1 means held. The other two fields are for debugging and for holding: name (here "kmem", set by initlock in kinit) and cpu, the struct cpu of the holder.

The compiled code confirms the layout: acquire swaps into offset 0 of the lock (amoswap.w.aq a5,a5,(s1)), and holding reads cpu with ld a5,16(a0). Offset 8 is name; the 4 bytes after locked are padding so that the pointer is 8-byte aligned.

All the cleverness of a spinlock is in how locked is read and written: not with ordinary C assignments, but with instructions that are indivisible and that order the hart’s other memory accesses around them. The rest of this tour is about those instructions.

Step 4 of 18

acquire starts by switching interrupts off

acquire has three phases: interrupts off (push_off), a self-check (holding), and the spin on the atomic swap. The order matters. Interrupts go off before the swap, because if they went off after it there would be a window, one or two instructions wide, in which this hart held the lock with interrupts still on.

The compiled prologue (0x80000be8) saves lk in the callee-saved register s1, so every later step can find the lock: mv s1,a0, then jal push_off.

Why interrupts at all? The comment says “to avoid deadlock”, and step 7 shows the deadlock. There is a second reason in push_off's own comment: mycpu reads the hart number from tp, and a timer interrupt could move this thread to another hart between reading tp and using the answer. With interrupts off, this thread cannot be moved, so “this hart” stays meaningful until the matching release.

Step 5 of 18

push_off: one instruction reads and clears SIE

rc_sstatus compiles to a single instruction (0x80000bb8):

csrrci  a5,sstatus,2     # a5 = old sstatus; clear bit 1 (SIE)

csrrci reads the old value of sstatus and clears the SIE bit in one step, so no interrupt can slip in between “was it on?” and “turn it off”. old is that bit (srli a5,s1,1; andi a5,a5,1).

Then the bookkeeping, in this hart’s struct cpu. cpus is at 0x8000f9d0 and each entry is 128 bytes (slli a5,a5,0x7 in mycpu), so hart 1’s is at 0x8000fa50; noff is at offset 120 and intena at 124 (lw a5,120(a0), sw a5,124(a0)).

• noff was 0: this is the outermost lock, so intena = 1 records “interrupts were on before”.
• noff becomes 1.

Only the pop_off that brings noff back to 0 may turn interrupts on again, and only if intena says so (interrupts and spinlocks (push_off / pop_off), Locks and interrupt state).

Step 6 of 18

Meanwhile hart 2 nests a second lock

On hart 2, allocproc scanned the process table taking each p->lock in turn, found an UNUSED slot and kept that slot’s lock: from line 117 on, it holds the new child’s p->lock. Its push_off found noff == 0, saved intena = 1 and set noff = 1. Interrupts on hart 2 are off.

Line 125 already nested one lock deeper and came back: allocpid took pid_lock (noff 1 → 2) and released it (noff 2 → 1), and interrupts stayed off, because noff did not reach 0.

Now line 129 calls kalloc for the trapframe, so hart 2 also heads for acquire(&kmem.lock). Its push_off reads the old SIE: 0, interrupts are already off. Because noff is 1, not 0, it leaves intena alone (still 1, from the first lock) and only increments noff to 2.

This is why push_off keeps a counter instead of a flag. A plain “off on acquire, on on release” would turn interrupts back on at the inner release, while the new child’s p->lock is still held (Locks and interrupt state).

Step 7 of 18

The deadlock push_off prevents: an interrupt on the same hart

kmem.lock is never taken by an interrupt handler, but some spinlocks are, and acquire treats every lock the same way. Here is one: the disk driver’s disk.vdisk_lock, taken by virtio_disk_rw in process context and by virtio_disk_intr in the disk’s interrupt handler.

In this step the disk interrupt is being handled on hart 0, and line 303 wants vdisk_lock. Hart 0 was idle, so the interrupt was taken in its scheduler’s interrupt window and kernelvec pushed its frame onto hart 0’s scheduler stack. If a process on hart 1 holds it, hart 0 spins until hart 1 releases it. A short wait; harmless.

Now imagine acquire did not turn interrupts off:

The stack shows it plainly. At t2 kernelvec pushes its frame onto the stack hart 1 is already using, the process’s kernel stack, directly on top of the frames of the virtio_disk_rw that holds the lock (… bread, virtio_disk_rw, kernelvec, kerneltrap, devintr, virtio_disk_intr, acquire). The holder is buried underneath the waiter on one stack, and only the waiter’s return could uncover it.

The holder cannot run until the handler returns, and the handler cannot return until the holder releases. In xv6, holding would usually catch this and panic with acquire. But if the interrupt arrived in the few instructions between the swap and lk->cpu = mycpu(), lk->cpu would still be 0 and hart 1 would spin forever, as it would in a kernel without the check, and every hart that later wanted the disk would join it. With interrupts off, the interrupt stays pending on hart 1 (or a hart with interrupts on claims it) and is taken after the release. That is the invariant: whenever noff > 0, SIE is 0, so a handler never interrupts a critical section on its own hart (Locks and interrupt state). Hart 0’s handler itself got here at noff 0, and its push_off records intena = 0, because the trap had already turned interrupts off.

Step 8 of 18

holding(): a hart waiting for itself

Back on hart 1, acquire calls holding: “does this hart already hold lk?” If it did, the spin below could never end, because the only hart that could release the lock is the one spinning. Panicking with acquire turns a silent freeze into a message.

The compiled code is short-circuited (0x80000b82): lw a5,0(a0), and if locked is 0, return 0 at once. Only if the lock is held does it load lk->cpu (ld a5,16(a0)) and compare it with mycpu.

These are plain loads, not atomics, and lk->cpu can be changing on another hart. Why is the answer still right? Only this hart ever writes this hart’s struct cpu pointer into lk->cpu, and it clears it again in release before freeing the lock. With interrupts off, nothing on this hart can run between those points. So “lk->cpu equals me” is true exactly when this hart holds the lock; another hart’s writes can only ever put its own pointer there. The comment “Interrupts must be off” on line 79 is the condition that makes this reasoning work (Locks and interrupt state).

Step 9 of 18

amoswap.w.aq decides who wins

The loop compiles to four instructions (0x80000c02–0x80000c0a), exactly as the comment predicts, with a4 = 1 loaded once before it:

mv            a5,a4           # a5 = 1
amoswap.w.aq  a5,a5,(s1)      # a5 = lk->locked; lk->locked = 1, indivisibly
sext.w        a5,a5
bnez          a5,<mv>         # old value was 1: someone holds it, try again

amoswap.w is an atomic read-modify-write from the RISC-V “A” extension. No other hart’s access to that word can come between its load and its store. When two harts swap the same word “at the same time”, the memory system puts the two swaps in some order:

In this run hart 2 wins. Which hart wins is not decided by xv6 and is not fair: a hart that just released the lock can win it straight back. Writing 1 over 1 at t2 changed nothing, so losing costs nothing but time.

Step 10 of 18

Hart 2 pops the list while hart 1 spins

Hart 2 is inside the critical section. It records itself in kmem.lock.cpu (kernel/spinlock.c:41) and pops page A off the list: r = A, kmem.freelist = A->next. Now no other hart can reach these lines until hart 2 releases the lock, so the t1–t4 interleaving from step 2 is impossible.

The critical section is three instructions of real work. That is deliberate: the memset that fills the page with junk (line 80) touches 4096 bytes, and it happens after the release, because page A is already private to hart 2 and needs no protection. Hold a spinlock for as short a time as you can: every hart that wants it is wasting its time meanwhile.

Step 11 of 18

Hart 2 releases: fence rw,w, then sw zero

release checks that hart 2 really holds the lock, clears lk->cpu (before the lock becomes free, so it never wipes out the next owner’s record), and frees it. The build matches the comment exactly (0x80000c82–0x80000c8a):

sd      zero,16(s1)     # lk->cpu = 0
fence   rw,w            # all earlier loads and stores before any later store
sw      zero,0(s1)      # lk->locked = 0

The fence is the point of __ATOMIC_RELEASE. RISC-V’s memory model (RVWMO) lets a hart make its stores visible to other harts in a different order than the program wrote them, when they go to different addresses. Without the fence:

fence rw,w forbids t2 before t1: every load and store of the critical section is ordered before the store that frees the lock. The loads matter too: a load from inside the critical section must not be satisfied late, after the next holder has changed the data. The compiler is bound by the same rule: it may not move memory accesses of the critical section below the atomic store.

Step 12 of 18

Hart 2's pop_off: noff 2 → 1, interrupts stay off

pop_off first checks two invariants: interrupts must still be off (otherwise someone turned them on inside a critical section, a bug), and noff must be at least 1 (more pops than pushes, also a bug).

Then it decrements noff, from 2 to 1 on hart 2. noff is not 0, so the csrsi sstatus,2 at 0x80000c4c is skipped: hart 2 still holds the new child’s p->lock, and interrupts must stay off until that one is released too (Locks and interrupt state).

kalloc returns page A to allocproc, which fills in the trapframe pointer and continues building the child with its p->lock held.

Step 13 of 18

Hart 1 gets the lock: what .aq promises

Hart 1’s swap returned 0. It now holds kmem.lock and records itself: lk->cpu = mycpu() (jal mycpu; sd a0,16(s1)).

The .aq (“acquire”) bit on the swap is the mirror image of the release fence. It guarantees that no later load or store of hart 1 can be seen to happen before the swap. Without it, the hart could perform the critical section’s first load early:

Together: .rl (or a fence rw,w before the store, which is what GCC emits for release) means “everything before me stays before me”; .aq means “everything after me stays after me”. A critical section is boxed in on both sides. An AMO with both bits set (.aqrl) would be a two-way barrier; xv6’s acquire needs only one.

Step 14 of 18

Hart 1's turn at the list

Hart 1 reads kmem.freelist. Thanks to hart 2’s fence rw,w and hart 1’s .aq, it is guaranteed to see B, the value hart 2 stored, not the stale A. It pops B and sets the head to B->next. If the list were empty, r would be 0 and kalloc would return 0; uvmalloc would undo its partial work and sbrk would fail.

Look at what made this correct. Not one property, but three working together:

1. Atomicity: the swap let exactly one hart see 0.
2. Ordering: release and acquire made hart 2’s writes visible to hart 1 before hart 1 could read them.
3. No preemption: interrupts off kept the holder running until it released.

Then line 77: release again, the same fence rw,w; sw zero as in step 11.

Step 15 of 18

Release, interrupts back on, junk outside the lock

In release, hart 1’s pop_off brings noff from 1 to 0. intena is 1, saved by the push_off in step 5, so it runs csrsi sstatus,2 (0x80000c4c): interrupts are on again. A timer interrupt that became pending while hart 1 spun is taken now, and this thread may be switched out right here. That is fine: it holds no locks.

memset then fills page B with the byte 5. That is 4096 stores, outside the lock: the page belongs to hart 1’s caller alone now. Junk instead of zeros catches code that forgets to initialize what it allocated; uvmalloc zeroes the page itself right after.

Count what one uncontended acquire + release costs on the outermost lock: one csrrci, one amoswap.w.aq, one fence rw,w, one sw, one csrr (the intr_get check in pop_off, 0x80000c34), one csrsi, and six calls to mycpu (three in push_off, one in acquire, one in release’s holding, one in pop_off). Contended, add one swap per spin.

Step 16 of 18

Hart 2 releases the child, and its interrupts come back

allocproc returned to kfork still holding the new child’s p->lock. kfork copies memory, registers and open files, then line 294 releases it. That pop_off takes noff from 1 to 0, finds intena == 1 (saved way back when allocproc took the lock) and turns interrupts on.

So interrupts were off on hart 2 across many nested acquire/release pairs (pid_lock, kmem.lock again and again, ftable.lock in filedup, itable.lock in idup), never more than two deep, and a whole memory copy, and came back on exactly once, at the outermost release. This is what the counter buys.

Notice too that kfork releases the child’s lock before taking wait_lock on line 296, and then takes the child’s lock again on line 300. That is not carelessness: xv6 requires wait_lock to be taken before any p->lock, and Tour 18: Lock ordering: how xv6 avoids deadlock shows the deadlock that rule prevents.

Step 17 of 18

The one lock held across a context switch

A timer interrupt finally arrives on hart 1 while the shell’s child is between two kalloc calls, holding no locks. kerneltrap calls yield, which takes the child’s own p->lock and calls sched.

The interrupt came from kernel code, so there was no stack switch: kernelvec pushed its 256-byte register frame onto the child’s kernel stack, right below uvmalloc. When swtch saves the child, that frame is frozen in the middle of the stack:

sh child's kernel stack
  top ─► usertrap
         syscall
         sys_sbrk
         growproc
         uvmalloc
         kernelvec    registers of the interrupted uvmalloc
         kerneltrap
         yield
         sched       ◄─ saved sp

Whichever hart resumes the child will unwind through it: sched returns, yield releases the lock, kerneltrap returns, and kernelvec restores the registers and srets back into uvmalloc. kernelvec deliberately does not restore tp (kernel/kernelvec.S:44), because that hart may not be hart 1.

sched checks the spinlock rules explicitly: the caller must hold p->lock, and noff must be exactly 1, meaning no other spinlock is held. This is the check that would have caught a switch inside kmem.lock’s critical section.

p->lock is special: it is acquired by this thread and released by a different thread, the scheduler, on the other side of swtch. Since intena describes this thread rather than this hart, sched saves it in a local variable across the switch and puts it back afterwards. The thread may resume on any hart, hart 0 or 2 as easily as hart 1, and it must bring its own “were interrupts on?” with it. Tour 13: swtch and the lock handed across a context switch follows that handoff. Here that value is 0, not 1: yield’s acquire ran inside kerneltrap, where the trap had already turned interrupts off. When the child resumes, yield’s release leaves them off, and kernelvec's sret turns them back on for uvmalloc from the SPIE bit the trap saved (Locks and interrupt state).

Step 18 of 18

What a spinlock is made of

Step back and look at acquire as a whole (the state shown is at line 41, the moment the lock is fully taken). Each line exists because of a specific failure:

and release mirrors it: clear cpu, fence rw,w, one store, pop_off.

A spinlock is cheap when uncontended and wasteful when contended: the waiter burns its hart with interrupts off. So xv6 uses spinlocks only for short critical sections and never waits for anything slow while holding one. For waits that can take milliseconds, such as a disk read, it builds sleep-locks on top of spinlocks (Tour 17: Sleep-locks); for “wait until something happens”, it uses sleep and wakeup (Tour 16: sleep and wakeup, and the lost-wakeup problem). Both are made of the instructions you have just seen.