Step 1 of 17

Rule 1: never acquire a lock you already hold

A spinlock has no idea who wants it. If the hart that holds it calls acquire again, the spin on line 37 waits for a release that only this same hart could perform, and this hart is busy spinning. holding on line 25 looks for exactly that case and panics instead (Locks and interrupt state).

Break 1. In sys_uptime, a copy of the kernel with acquire(&tickslock) written twice (line 108 doubled). Two boots, then lockstress up 1 at the shell. Both runs ended the same way (run 2’s console; run 1 also shows the echoed command before the panic):

init: starting sh
$ panic: acquire

gdb, stopped at the panic call (line numbers are the modified file’s; its line 109 is the added second acquire):

#0  panic (s="acquire") at kernel/printk.c:139
#1  acquire (lk=0x800157d0 <tickslock>) at kernel/spinlock.c:26
#2  sys_uptime () at kernel/sysproc.c:109
#3  syscall () at kernel/syscall.c:146
#4  usertrap () at kernel/trap.c:68
cpus[0].noff = 2, cpus[0].intena = 1

In the first run gdb also read tickslock = {locked = 1, cpu = 0x8000f9d0 <cpus>}: the owner recorded on line 41 is &cpus[0], and this is hart 0 asking. That comparison is all holding does. It records a hart, not a process, which is why the check works only because interrupts are off: the thread cannot move to another hart between the two acquire calls.

Step 2 of 17

Break 1b, with the check deleted

Now delete lines 25–26 of spinlock.c as well, keep the doubled acquire, and run the same command. Two runs, two freezes: the shell prints $ , takes the command, and nothing more appears, ever. No panic.

gdb, after interrupting the frozen machine (run 1; the modified spinlock.c is two lines shorter, so its line 35 is the spin on line 37 of the original):

hart 0: acquire (lk=<tickslock>) at spinlock.c:35
        clockintr () at trap.c:170
        devintr () at trap.c:215
        kerneltrap () at trap.c:149
        kernelvec ()
        [interrupted: scheduler () at proc.c:442]
hart 1: acquire (lk=<tickslock>) at spinlock.c:35
        sys_uptime () at sysproc.c:109        <- its own second acquire
hart 2: acquire (lk=<tickslock>) at spinlock.c:35
        sys_uptime () at sysproc.c:108
tickslock = {locked = 1, cpu = <cpus+128>}     (hart 1)
ticks = 4

Hart 1 holds tickslock and waits for itself. Hart 2’s worker waits behind it. Hart 0 was idle in its scheduler; its timer interrupt arrived in the intr_on(); intr_off(); window, and clockintr wants tickslock to count the tick. ticks stopped at 4. All three harts spin with interrupts off, so nothing can ever preempt them. The third worker sat RUNNABLE with no hart left to run it. In run 2 the holder happened to be hart 0 itself, so its own clockintr could never even be taken; the other two harts spun on line 108 just the same.

One deleted if turned an instant, one-line diagnosis into a machine that looks merely idle. That is what holding() is for.

Step 3 of 17

Rule 2: never sleep holding a spinlock

The shell reads its command line through consoleread, which waits for keystrokes under cons.lock. The pattern is the one Tour 16: sleep and wakeup, and the lost-wakeup problem walked through: register on the channel (sleep_prepare, line 104), release the condition lock (105), sleep (106), take the lock again (107). The keyboard’s interrupt handler, consoleintr, needs cons.lock to put the character in the buffer and wake the reader.

Tour 48: Breaking the invariants already broke this rule with tickslock in pause. Here is a second instance, on a lock that an interrupt handler needs. Break 2: a copy of the kernel with lines 105 and 107 deleted, so the shell sleeps holding cons.lock. Two boots; both died the moment the shell first waited for input:

init: starting sh
$ panic: sched locks

gdb on hart 2:

#0  panic (s="sched locks")
#1  sched () at kernel/proc.c:488
#2  sleep () at kernel/proc.c:569
#3  consoleread (user_dst=1, dst=20255, n=1) at kernel/console.c:106
#4  fileread ...
#5  sys_read ...
cpus[2].noff = 2, cpus[2].intena = 1
cons.lock = {locked = 1, cpu = <cpus+256>}      (hart 2)
sh: SLEEPING, chan = <cons+152> (&cons.r)

sh had already set its state to SLEEPING; sched refused the switch.

Step 4 of 17

What sched counted, and what it prevented

sched cannot see which locks a hart holds, only how many: noff, the push_off depth (Locks and interrupt state). Exactly one level is allowed, for p->lock, the lock the scheduler will release on this hart after swtch (Locks and interrupt state). Two levels means some other spinlock would stay locked while its holder is off the hart.

What the check prevented here is a deadlock with the keyboard. With cons.lock stuck, the next key press would reach consoleintr on some hart, which would spin on cons.lock with interrupts off forever. The only code that could release the lock is sh, which sleeps until that same handler wakes it. Then the next hart to touch the console would spin too. (One way out remains: a kill of sh from another hart would make it runnable, and consoleread’s killed path, lines 100–102, releases the lock.)

Sleep-locks are invisible to this count, which is exactly right: Tour 17: Sleep-locks shows processes sleeping while holding two or three of them.

Step 5 of 17

Rule 3: interrupts off while any spinlock is held

Line 97 is one instruction, csrrci a5,sstatus,2: read sstatus and clear SIE in the same step (Locks and interrupt state). From then until the matching pop_off brings noff back to 0, no interrupt can be taken on this hart. That is the invariant (Locks and interrupt state): noff > 0 ⇒ SIE = 0. It is why an interrupt handler on this hart can never find a lock this hart holds.

Break 3: a copy of the kernel whose line 97 reads sstatus without clearing SIE (r_sstatus() instead of rc_sstatus(SSTATUS_SIE)). Everything else is untouched: the counter still counts and intena is still recorded. Four boots, the same panic message every time, before the shell ever started:

hart 2 starting
panic: pop_off - interruptible

gdb, the three runs where it was attached from reset:

#0  panic (s="pop_off - interruptible")
#1  pop_off () at kernel/spinlock.c:110
#2  myproc () at kernel/proc.c:88
#3  syscall () at kernel/syscall.c:140
#4  usertrap () at kernel/trap.c:68

The process was init, making its first system call. The first lock-like section that ran with interrupts on was not even a lock: it was myproc's push_off/pop_off pair.

Step 6 of 17

pop_off is the alarm

pop_off begins by checking the invariant from the other end: if SIE is on while noff is still at least 1, something enabled interrupts inside a critical section, and it panics. In a correct kernel this never fires; only pop_off itself (at noff 0), the scheduler’s intr_on, usertrap’s intr_on and sret ever set SIE.

In break 3 the check fired on the first pop_off executed after usertrap turned interrupts on at kernel/trap.c:66. That was line 140 of syscall.c, myproc(), on init’s very first system call. The broken kernel never got a chance to deadlock; the check caught the rule being broken, not a consequence of it.

So we broke the alarm too.

Step 7 of 17

Break 3b: the alarm removed

Break 3 plus lines 109–110 of spinlock.c deleted. Now nothing complains when a lock is held with interrupts on. Six boots with gdb from reset; every one panicked before the shell started, while init was the only process (in the three runs where the backtrace reached the system call, it was init’s first mknod, creating /console):

In one sched locks run we unwound through the kernelvec frame by hand (pc ← the saved sepc, sp ← the frame’s top) to see what the timer had interrupted:

kvbt: interrupted code at sepc=0x80000bbc
#0  push_off () at kernel/spinlock.c:97
#1  acquire (lk=<proc+6120>)              proc[17].lock
#2  wakeup (chan=<bcache+16720>)
#3  releasesleep (lk=<bcache+16720>)       holding the buffer's lk->lk
#4  brelse ...
#5  readi ...
#6  dirlookup (name="console")
#7  dirlink ...
#8  create (path="console", type=3)
#9  sys_mknod ()

init held lk->lk, the spinlock inside a buffer’s sleep-lock, and was walking the process table in wakeup. The timer fired. A correct kernel would have kept it pending until release. Here kerneltrap ran at once and tried to yield; sched counted two levels and refused. Without that check the process would have left the hart still holding lk->lk. Any hart that touched that buffer would spin until init ran again, and if init resumed on another hart, its release would panic, because the lock records the hart, not the process.

Step 8 of 17

Why every interrupt handler forces the rule on every lock

It might seem enough to turn interrupts off only around locks that a handler uses: tickslock, cons.lock, disk.vdisk_lock. Break 3b shows why xv6 does not try. Every device handler can call wakeup (uartintr line 145, consoleintr, virtio_disk_intr once per finished request, and clockintr on hart 0), and wakeup takes every process’s p->lock in turn, line 581. The measured inventory agrees: p->lock was taken in interrupt context 1.37 million times in the measurement run (boot, usertests and several stress programs; Locks and interrupt state).

And many other locks are held while a p->lock is taken. The sched locks run above was holding a buffer’s lk->lk and taking proc[17].lock inside wakeup. Any lock held at a moment when a handler could run is one the hart can deadlock on. Rather than track which, acquire turns interrupts off for all of them, and pop_off and sched check that nobody turned them back on (Locks and interrupt state).

Step 9 of 17

Rule 4: intena belongs to the thread, not the hart

mycpu()->intena answers one question for the outermost pop_off: should interrupts come back on? The answer depends on the thread. A process that sleeps in a system call had interrupts on before it took p->lock (intena 1). A process that yields from a timer trap had them off (intena 0). Both go through sched on the same hart, so sched keeps the thread’s value in a local (register s3 in this build) across swtch and puts it back on line 496. The scheduler sets its own value to 0 on line 456 (Locks and interrupt state).

We measured how much work these two lines do. A copy of the kernel with counters (and no other change) ran usertests -q to ALL TESTS PASSED:

(The returns are fewer than the entries because an exiting process never comes back, and a few processes were still asleep when we stopped.) So with line 456 in place, a resumed process always finds intena 0; line 496 only ever restores 1 to processes that slept in system calls.

Step 10 of 17

Break 4: three ways to lose track of intena

Three copies of the kernel, each run through usertests -q:

A counting copy of variant c (the same changes in effect: it reads intena on line 494 for the counter but never restores it, and line 456 is gone) also passed, and recorded what each thread found in mycpu()->intena when its swtch returned:

The 652 are the case the comment above sched warns about: a thread that had interrupts off (a yield from a trap, among others) came back believing they had been on, so its release(&p->lock) turned them on. For a yield from usertrap that is harmless, because prepare_return turns them off again. For a yield from kerneltrap it is not, as the next paragraph says. Our counters could not tell the two apart.

None of these crashed, and that is an honest result, not a proof. In (a) the cost is latency: interrupts stay off for the rest of every system call that slept (about 24,000 per run, the number of times line 496 restored a 1 in our counting run). Nothing in that stretch busy-waits for an interrupt: whenever it waits, it sleeps, and the hart runs something else. In (b) the scheduler holds no lock while interrupts are on, so a handler finds nothing held on its own hart. In © the danger is a window of a few instructions in kerneltrap between w_sepc and w_sstatus: a nested trap there would overwrite sepc. kerneltrap's own check (kerneltrap: interrupts enabled) cannot see it, because the hardware clears SIE on every trap. We did not hit the window. The rule stays: intena is a property of the thread, and the comment above sched says so.

Step 11 of 17

Rule 5: register before releasing the condition lock

kwait scans for a ZOMBIE child under wait_lock. Finding none, it must sleep until a child exits. The child’s kexit takes wait_lock and calls wakeup(p->parent). The order on lines 414–416 is the lost-wakeup defence of this tree (Tour 16: sleep and wakeup, and the lost-wakeup problem, Locks and interrupt state): sleep_prepare sets p->chan while wait_lock is still held, so no child can be between “checked” and “registered”. If the child’s wakeup runs after the release but before sleep, it clears p->chan, and sleep returns at once.

Break 5: a copy of the kernel with lines 414 and 415 swapped: release wait_lock first, then sleep_prepare(p). Run lockstress fork 3000: three workers, each forking and waiting for a child 3,000 times.

Four runs, four hangs. In each, one or two workers stopped printing progress while the others finished; the shell never printed its next prompt. The machine was not frozen: ticks kept counting (1,096, 1,105, 1,378 and 1,372 when we looked), and all three harts sat idle in their schedulers.

Step 12 of 17

Break 5: a parent asleep for a wakeup that already happened

gdb’s view of the process table in run 1:

slot pid  state     name        chan                 parent
4    5    SLEEPING  lockstress  0x80010370 <proc+1440>  proc[2]
6    422  ZOMBIE    lockstress  0                    0x80010370 <proc+1440>

Worker pid 5 sleeps on channel &proc[4], its own struct proc, the channel kwait uses. Its child, pid 422, is a ZOMBIE waiting to be collected. Nothing will ever call wakeup(&proc[4]) again: pid 5 has no other children, and only an exiting child wakes that channel.

With the original order, step t5 happens before t2, so at t3 wakeup finds the channel set and clears it; sleep at t6 sees p->chan == 0 and returns. Line 567 is where the two orders differ.

From the code (we did not test it): kill 5 would unstick this worker. kkill makes it RUNNABLE, kwait’s loop rescans and collects pid 422, and the worker then exits on its way back to user space because killed is set (kernel/trap.c:81). The loop around every sleep is what makes such a wakeup safe.

Step 13 of 17

Rule 6: one global order, wait_lock before p->lock

kfork has held the new child’s p->lock since allocproc. It must now set np->parent, which wait_lock protects. The code does a small dance: release np->lock (294), take wait_lock (296), set the parent, release, then take np->lock again (300) to mark the child RUNNABLE. The comment-free reason is the global order (Tour 18: Lock ordering: how xv6 avoids deadlock, Locks and interrupt state): wait_lock is always taken before any p->lock. kexit and kwait hold wait_lock and then take process locks; the order graph we measured has the edge wait_lock → p->lock and never the reverse.

Break 6: a copy of the kernel with lines 294 and 300 deleted, so kfork takes wait_lock while still holding np->lock: a p->lock → wait_lock edge, the reverse of everyone else’s. lockstress fork 3000, four runs.

Four runs, four freezes, every one within the first dozen forks: the shell printed $ , lockstress never printed anything, and ticks stopped at 5.

Step 14 of 17

Break 6: three harts, one cycle

gdb in run 1 (the modified file is two lines shorter above kexit, so its lines 295, 342 and 351 are lines 296, 344 and 353 here):

hart 2: acquire (lk=<proc+2880>)       wants proc[8].lock
        wakeup (chan=<proc+1080>)       kexit's wakeup(p->parent)
        kexit () at proc.c:351          holds wait_lock
hart 1: acquire (lk=<wait_lock>)       wants wait_lock
        kfork () at proc.c:295          holds proc[8].lock (pid 12, state USED)
hart 0: acquire (lk=<proc+2880>)       wants proc[8].lock
        wakeup (chan=<log>)
        end_op () at log.c:181          holds log.lock
        kexit () at proc.c:342
wait_lock    = {locked = 1, cpu = <cpus+256>}    (hart 2)
proc[8].lock = {locked = 1, cpu = <cpus+128>}    (hart 1)

The cycle is two harts long. Hart 1 holds the half-built child’s lock and wants wait_lock. Hart 2 holds wait_lock and, inside wakeup, scans every process’s lock, including the half-built child’s, which hart 1 holds. Hart 0 is not part of the cycle; it is another exiting process whose own wakeup walked into the same lock, while holding log.lock. Within moments anything that touches the log, wait_lock or slot 8 joins them. All three harts spin with interrupts off, so not even the clock advances.

The other three runs had the same shape, with the roles shuffled across harts (in run 3, hart 0 held the child’s lock and hart 1 waited for wait_lock from kwait). A rule that two pieces of code obey independently is invisible until one of them breaks it; then wakeup's habit of touching every p->lock makes the collision almost certain.

Step 15 of 17

Rule 7: release publishes the critical section

__atomic_store_n(..., __ATOMIC_RELEASE) compiles to fence rw,w (0x80000c86) and sw zero,0(s1) (0x80000c8a). The fence makes every load and store of the critical section visible to other harts before the store that frees the lock. Under RISC-V’s weak memory model (RVWMO) a plain store may become visible before earlier stores, and the next holder could then read data from before the critical section finished (Locks and interrupt state, Tour 19: Memory ordering across harts).

Break 7: a copy of the kernel with __ATOMIC_RELAXED on line 73. The compiled release now has no fence at all:

80000c82:  sd  zero,16(s1)     # lk->cpu = 0
80000c86:  sw  zero,0(s1)      # lk->locked = 0, no fence
80000c8a:  jal pop_off

The compiler did not move anything here (inside release, a relaxed store would have let it swap the two stores; it happened not to). release is a separate, non-inlined function, so it has to issue every caller’s stores before the call. Whether other harts see them in that order is up to the hardware.

Step 16 of 17

Break 7: no failure, and why that proves nothing

Three runs of usertests -q: ALL TESTS PASSED each time. Two runs of lockstress fork 5000 followed by lockstress up 100000: both finished, 15,000 forks and 300,000 uptime calls per run, every one through acquire and the fence-less release of tickslock, wait_lock and dozens of p->locks.

The rule was broken; the experiment could not see it. QEMU’s TCG translates each RISC-V instruction into host code, and our desktop host is an x86-64 machine. x86 is “total store order”: its stores become visible in program order, and it never lets a store overtake an earlier load. The reordering RVWMO permits, and the fence forbids, does not happen on this host. In fact QEMU translates fence rw,w into no instruction at all on an x86 host, so with or without the fence the host ran essentially the same code. The other half of the pair is still there: amoswap.w.aq on line 37 keeps the next holder’s reads after its acquire.

On a real RISC-V core, or on a host with a weaker memory model, the same kernel could hand a lock to another hart before the protected data had arrived. Tour 48: Breaking the invariants found the same thing for the fences on started: “it worked every time” is a fact about one machine, and the memory model is the contract.

Step 17 of 17

What broke, and how loudly

Three lessons. The checks (holding in acquire, pop_off’s SIE test, the four tests on lines 485–492) turned four of these changes into panics, every run. Three of them fired on the first offence; with pop_off’s check gone, the next checks (sched, or holding) caught it a little later. Without them, the same mistakes became the worst kind of bug: a machine that looks idle. The unchecked rules (wakeup registration, lock order) failed silently, one freezing one or two processes while the rest ran on, one freezing everything. And not failing is not a pass. Of the intena variants, (a) and (b) cost only interrupt latency as far as we can tell from the code, but © has a real window in kerneltrap that we simply did not hit; the missing fence is wrong under a memory model that our runs on QEMU never exercised. Locks and interrupt state lists every panic, and Locks and interrupt state the rules.