Step 1 of 16 · commit 1: Add lockbench, a system call that hammers one lock

The instrument: a system call that hammers one lock

Before changing the lock, the lab builds a way to watch it. The first commit adds a system call, number 23, with the usual registrations (Tour 5: Life of a system call has the path): the #define in kernel/syscall.h, the extern and [SYS_lockbench] = sys_lockbench here, a stub from user/usys.pl, a prototype in user/user.h, and struct lbstat in kernel/lockbench.h, which the kernel and locktest both include so that they agree on its layout.

The story of this reveal is one recorded run of the finished branch, under gdb, on three harts: locktest is pid 3, and its first call, lockbench(0, 300000, 0) (reset), was caught entering sys_lockbench on hart 1. Its three children, pids 4, 5 and 6, will hammer the lock on harts 0, 2 and 1.

At that breakpoint gdb recorded the pid (3), hart 1’s sstatus (0x8000000200006022: SIE, bit 1, is set; interrupts are on since kernel/trap.c:66) and cpus[1].noff (0): a system call in progress, no lock held.

Step 2 of 16 · commit 1: Add lockbench, a system call that hammers one lock

One lock, and a score kept under it

benchlock is an ordinary struct spinlock, nothing special: whatever acquire and release do to every lock in the kernel, they do to this one. The bench struct is the data it protects: the target, the count so far, and the score. Its fields are written only with benchlock held, except by the reset, and read without it only by the spin on arrived and after the run is over; that is why plain C is enough for them.

benchreset calls initlock again, which is only safe when nobody is using the lock. Reinitializing a lock that a hart holds sets next == serving under it; the holder’s own release then fails holding and the kernel panics release. Any process can call lockbench(0, ...), so a comment is not enough: a second spinlock, runlock, protects running, the number of callers between their start line and the end of their run, and the reset refuses (returns -1) unless it is 0. (With only the comment, typing locktest 3 3000000 & and then locktest panics the kernel. Verify shows the same two commands with runlock.) runlock is never passed to initlock: a zeroed struct spinlock is a free lock under both the old and the new acquire.

The reset matters later: commit 4 makes initlock start the counters just below the wrap, and this reset is what makes every locktest run cross it.

inside and overlaps are the mutual-exclusion check: the critical section sets inside, and a hart that finds it already set counts an overlap. It cannot catch every overlap (two harts could miss each other), so locktest also checks that the counts add up.

Step 3 of 16 · commit 1: Add lockbench, a system call that hammers one lock

A start line, outside any lock

Each of the three children calls lockbench(3, 300000, &st). To compare locks, they must contend from the first acquisition, so each one counts itself in running (under runlock, which keeps a reset out until it is done), checks in (incrementing arrived under benchlock) and then spins until all three have arrived.

The start-line spin is deliberately outside any lock and with interrupts on (noff 0). The third child may not even be running yet: it may be RUNNABLE, waiting for a hart. If the first two spun with interrupts off, no timer interrupt could make them yield, and on a machine with fewer harts than callers the third would never run. With interrupts on, a timer tick can take the hart away, and nothing is held that anyone else needs.

arrived is read with __atomic_load_n(..., __ATOMIC_RELAXED): an atomic load, so the compiler must re-read it on every iteration (clinic 1 shows what a plain read in a loop becomes), and relaxed, because the start line protects no data. This state is reasoned from the code; gdb did not stop here.

Step 4 of 16 · commit 1: Add lockbench, a system call that hammers one lock

The loop: time the wait, keep score, let go

Each iteration is push_off, read the time CSR, acquire, read it again, keep score, release, pop_off. The extra push_off at line 119 keeps a timer interrupt from landing between the two r_time() calls, so the wait measured is the lock’s, not a context switch’s. The time CSR counts at 10 MHz on QEMU’s virt machine: one tick is 100 ns.

So a hart waiting for benchlock is at noff 2, SIE off, intena 1 (interrupts were on when the system call reached line 119). gdb recorded exactly that on hart 1 (cpus[1].noff = 2, intena = 1, sstatus = 0x8000000200006020, SIE bit clear).

Between iterations, after line 130, noff drops to 0 and interrupts are on again for a few instructions: that is where a timer tick can preempt the process. The stop test is made with the lock held (line 123), so every caller sees the same final count and leaves.

At this commit acquire is still the original swap loop; the state above was recorded on the finished branch, where the noff and intena values are the same.

Step 5 of 16 · commit 1: Add lockbench, a system call that hammers one lock

Inside the critical section

gdb stopped hart 2 here, at the first instruction of critical (inlined into sys_lockbench, 0x80000d54), holding benchlock with bench = {count = 237, last = 0, run = 1, maxrun = 2}: 237 acquisitions so far, the previous one by hart 0.

cpuid is safe because interrupts are off: the process cannot move to another hart in the middle. The run counter records how many acquisitions in a row the same hart made; a test-and-set lock that lets the releasing hart walk straight back in would show up as long runs. But long runs also come from waiters that are not in line at all (a process preempted between iterations, a host thread delayed), under either lock: the measured runs do not separate the two locks (Measure). The caller’s own count, per-hart tally and waits go into st, its private copy on its kernel stack, which is copied out to user space at the end.

inside is accessed with relaxed atomics so that the load and both stores stay real memory accesses. As plain C, the store of 1 followed later by the store of 0, with no read of it in between, is the kind of dead store a compiler may delete. In this build they are lw at 0x80000d5c, sw at 0x80000d6c and sw zero at 0x80000d28. It is a tripwire, not a lock: mutual exclusion is still the lock’s job.

Step 6 of 16 · commit 2: Add locktest, which runs lockbench in three processes

locktest: three processes at the start line

The test resets the benchmark (giving up if another run is in progress), makes a pipe, forks three children that call lockbench and write their struct lbstat into the pipe, and reads the three results. A struct lbstat is 80 bytes; all three fit in the pipe’s 512-byte buffer at once, and pipewrite copies each one while holding the pipe’s lock, so every read gets one whole struct.

It checks one thing: every acquisition was counted once (sum == total, count == total) and no overlap was seen. Everything else is printed for you to compare, and the last line says so. On the original lock (this commit, recorded without the reset check, which changes nothing in a single run), a recorded run:

$ locktest
locktest: 3 processes, 300000 acquisitions of one lock
locktest: process 0: 99499 acquisitions, wait mean 780 ns, longest 14 us
locktest: process 1: 100141 acquisitions, wait mean 780 ns, longest 43 us
locktest: process 2: 100360 acquisitions, wait mean 771 ns, longest 61 us
locktest: per hart: 99883 98971 101146
locktest: longest run by one hart: 22
locktest: 201 ms, 1492 acquisitions per ms
locktest: mutual exclusion (300000 counted, 0 overlaps): OK
locktest: fairness is not checked: compare the numbers above

Aggregate shares on QEMU are close to even with either lock (Measure has the numbers). Seeing the difference takes a counter inside acquire, which this lab adds only in a scratch copy, never on the branch.

Step 7 of 16 · commit 3: Turn the spinlock into a ticket lock

Two counters in the same eight bytes

locked was a 4-byte uint followed by 4 bytes of padding before the 8-byte name pointer. next and serving fill those same 8 bytes: name stays at offset 8, cpu at 16, and the struct is still 24 bytes. Every structure that embeds a spinlock (struct proc, struct pipe, every sleep-lock) keeps its layout.

In the recorded run, while hart 2 held benchlock, gdb printed it as {next = 0xfffffff2, serving = 0xfffffff0, name = 0x80007048, cpu = 0x8000fb30}: ticket 0xfffffff0 was being served (hart 2’s, and 0x8000fb30 is &cpus[2]), ticket 0xfffffff1 was hart 1’s, and 0xfffffff2 was the next to hand out. Two tickets outstanding, the holder’s and one waiter’s. (The values are near 0xffffffff because commit 4 starts the counters there; at this commit they would start at 0.)

Step 8 of 16 · commit 3: Turn the spinlock into a ticket lock

Taking a ticket

push_off still comes first, and the holding check still turns “this hart already holds it” into a panic instead of a hang: with tickets, a hart that took a second ticket for a lock it holds would wait for itself forever.

Then the ticket: __atomic_fetch_add(&lk->next, 1, __ATOMIC_RELAXED), one instruction in this build (commits 3 and 4 compile acquire identically), amoadd.w a4,a5,(s1) at 0x80000e58 (a5 = 1, s1 = lk, whose first word is next). It adds 1 to next in memory and returns the old value in a4, with no other hart able to touch the word in between.

gdb stopped hart 0 (pid 4) on that instruction with benchlock at {next = 0xfffffff2, serving = 0xfffffff0}, executed it with stepi, and read a4 = 0xfffffff2 and next = 0xfffffff3. Hart 0 is now third in line: hart 2 holds 0xfffffff0, hart 1 waits with 0xfffffff1.

Relaxed is enough: holding a ticket gives no right to touch bench. The ordering that matters comes on the next line.

Step 9 of 16 · commit 3: Turn the spinlock into a ticket lock

Waiting for your number

The loop compiled to five instructions:

80000e5e:  addi   a5,s1,4         # &lk->serving
80000e62:  lw     a5,0(a5)        # load serving
80000e64:  fence  r,rw            # acquire: later loads and stores stay after it
80000e68:  sext.w a5,a5
80000e6a:  bne    a5,a4,80000e5e  # not my number yet: again

a4 holds the ticket, 0xfffffff1 on hart 1 when gdb stopped it at 0x80000e62. Every iteration loads serving again, because __atomic_load_n is an atomic access the compiler may not hoist (clinic 1), and every iteration runs the fence. The fence matters only on the last iteration: it keeps the critical section’s loads and stores after the load that saw the ticket, and so after the release store that published the previous holder’s work.

Compare the original loop: every iteration was an amoswap, an atomic write. Here the waiters only read. And == (bne to keep waiting) is the only comparison: it is what keeps the wrap harmless (commit 4).

After the loop, lk->cpu = mycpu() records the owner, exactly as before.

Step 10 of 16 · commit 3: Turn the spinlock into a ticket lock

Release: clear the owner, then serve the next number

Release is three steps, compiled as:

80000ee4:  sd     zero,16(s1)     # lk->cpu = 0
80000ee8:  lw     a5,4(s1)        # serving
80000eea:  addiw  a5,a5,1         # + 1
80000eec:  addi   a4,s1,4         # &lk->serving
80000ef0:  fence  rw,w            # release ordering
80000ef4:  sw     a5,0(a4)        # the next ticket may enter
80000ef6:  jal    pop_off

No AMO: only the holder writes serving, so reading it with a plain lw and writing it back cannot lose an update. What the store needs is ordering, and that is the fence rw,w, the same fence the original release had: every load and store of the critical section is ordered before the sw that lets the next hart in.

The order of the first and last stores matters. lk->cpu = 0 comes first, while this hart still owns the lock. After the sw, the next hart may be inside within a few instructions and store its own cpu; clearing cpu after that would erase the new owner (clinic 4).

pop_off comes after the store: interrupts stay off until the lock is handed on. The state shown is reasoned for hart 2 releasing benchlock (the recorded snapshot of this code is at the wrap, two steps from the end).

Step 11 of 16 · commit 3: Turn the spinlock into a ticket lock

holding() without a flag

“Is the lock held?” becomes lk->next != lk->serving: some ticket has been handed out and not yet served past. “By me?” is unchanged: lk->cpu == mycpu(). The compiled code loads both counters (lw a4,0(a0), lw a5,4(a0) at 0x80000dd4) and calls mycpu only if they differ.

lk->cpu is written only by the holder, so in this code the second half alone would give the same answer; the first half keeps the meaning “held, and by me” that callers such as sched rely on (kernel/proc.c:485).

Interrupts must be off here, as the comment says: mycpu names the hart, and an interrupt that moved this thread to another hart between the load of lk->cpu and the call would compare against the wrong one. All three callers, acquire (after its push_off), release and sched, run with noff > 0.

Step 12 of 16 · commit 3: Turn the spinlock into a ticket lock

The p->lock handoff does not notice

Nothing in proc.c changes, and that is worth checking. The scheduler acquires a process’s p->lock (line 446), takes a ticket, waits its turn, and swtches to the process with the lock held. The process releases it in yield, sleep or forkret: a different thread, on the same hart. When the process gives up the hart, it acquires its own p->lock and the scheduler releases it at line 463. (Locks and interrupt state, Tour 13: swtch and the lock handed across a context switch.)

The ticket lock is fine with that. The ticket was a local variable in the scheduler’s acquire and is forgotten once the wait ends. release only checks holding() (same hart) and advances serving, whichever thread runs it.

What does change is how the scheduler waits. Every scheduler scans all 64 slots, taking each p->lock in turn; when two schedulers reach the same slot, the second now queues for it in order instead of racing. These locks are taken constantly: each of the five p->locks gdb printed had been acquired more than 1,600 times 20 seconds after boot, at an idle shell, and more than 370,000 times by the end of usertests -q. The state is reasoned from the code.

Step 13 of 16 · commit 3: Turn the spinlock into a ticket lock

Interrupts off before the ticket, not after

Line 27 did not change, but its job grew. In the original lock, interrupts had to be off while a lock was held, so that a handler on this hart could not want it. With tickets, they must be off while a hart waits, too: from the moment it takes a ticket, every later ticket depends on it.

Picture hart 0 in sys_uptime with ticket N for tickslock, spinning. If interrupts were on, the timer could interrupt it, and clockintr would take ticket N+1 (kernel/trap.c:170). Ticket N is called, but its owner is underneath the handler, and the handler is waiting for N. Clinic 3 moved push_off after the loop and caught exactly this, with the ticket in the interrupted frame equal to serving.

With push_off first, the state above holds during the whole wait: noff 1, SIE off, intena 1. The timer interrupt stays pending until release's pop_off turns interrupts back on, and clockintr then takes its ticket on a hart that holds none. (Reasoned from the code.)

Step 14 of 16 · commit 4: Start every lock's tickets just below the wrap

Starting just below the wrap

The only change of commit 4: next and serving start at 0xffffff00, 256 tickets below the wrap. Equality never cared where they start; the point is to make the wrap happen early. This is the same trick Linux plays with its tick counter: it starts the 32-bit tick count (jiffies) five minutes before it wraps.

The state shows kinit on hart 0 initializing kmem.lock, before paging is on. Then freerange frees about 32,700 pages, one kfree and one acquire/release of kmem.lock each: that lock wraps long before the shell starts. gdb, attached 20 seconds after boot at an idle shell, found kmem.lock at 0x7fb7, bcache.lock at 0x362 and the five p->locks it printed at 0x5b4 to 0x63e (all wrapped), while tickslock (0xffffffc7), wait_lock, pid_lock, cons.lock and the others had not wrapped yet. After usertests -q every lock it printed had wrapped except cons.lock.

Without this commit, a comparison that cannot handle the wrap would pass every test here and fail after about an hour of hammering one lock, once. With it, clinic 2’s bug panicked on every boot we ran, though a single locktest run catches it only if a waiter is in line at the moment of the crossing.

Step 15 of 16 · commit 4: Start every lock's tickets just below the wrap

The queue across the wrap

locktest’s reset reinitialized benchlock, so its counters started at 0xffffff00 and wrap after 256 acquisitions (3 check-ins at the start line, then 253 in the loop), with three harts contending. gdb stopped the run when hart 2 (pid 5) entered the critical section holding ticket 0xffffffff:

benchlock = {next = 0x1, serving = 0xffffffff, name = 0x80007048, cpu = 0x8000fb30}
bench.count = 252
hart 1 (pid 6): spinning at 0x80000e64, a4 = 0x0 (its ticket),
                a5 = 0xffffffffffffffff (the serving it last read)
hart 0 (pid 4): reading the time CSR, about to call acquire (noff 1)

Hart 1 took the ticket after 0xffffffff, which is 0, and next moved on to 1. There is nothing special to do: hart 1 waits for serving == 0, and the holder will store 0xffffffff + 1, which in 32 bits is 0.

An ordering test would fail right here: serving < my is 0xffffffff < 0, false, and hart 1 would walk in now (clinic 2).

Step 16 of 16 · commit 4: Start every lock's tickets just below the wrap

The handoff from 0xffffffff to 0

gdb stopped hart 2 at the fence rw,w (0x80000ef0) of that same release:

benchlock = {next = 0x1, serving = 0xffffffff, name = 0x80007048, cpu = 0x0}
hart 2: a5 = 0x0              (serving + 1, already computed)
hart 1: a4 = 0x0, spinning    hart 0: still reading the time CSR

cpu is already 0 (line 66 ran first). Then two stepis on hart 2, the fence and the sw:

benchlock = {next = 0x2, serving = 0x0, name = 0x80007048, cpu = 0x8000fab0}
hart 2 at 0x80000ef6 (the call to pop_off)
hart 1 at 0x80000e76 (in acquire, just after recording itself in lk->cpu)
hart 0 at 0x80000e5c (in acquire, just after its amoadd)

During those two steps the other harts kept running (gdb’s default): hart 1 saw serving = 0, left its loop and recorded cpu = &cpus[1] (0x8000fab0); hart 0 took ticket 1 (next is now 2) and will wait for the next release. FIFO across the wrap, by plain modular arithmetic.

Summing up what the four commits cost: acquire lost its amoswap and gained an amoadd and a fence per spin iteration; release is the same instructions as before plus a load, an add and an address computation; no struct changed size. What they bought, measured with a counter inside acquire: no waiter passed by more than the two other harts.