Every spinlock in this tree is one word and one atomic swap. When the holder lets go,
the next hart whose amoswap happens to reach the word first takes the lock. Nothing
remembers who has been waiting longest. In this lab you replace that loop with a ticket
lock: a hart takes a number and waits until its number is called, like at a deli counter,
so harts get the lock in the order they asked.
The change is about thirty lines in two files (spinlock.c and spinlock.h), and every line raises a question about
hardware and timing. Which of the two counters must be updated atomically, and which need
not be? What memory ordering does each step need, and which instructions does the compiler
turn them into? What happens when a 32-bit counter wraps around? Interrupts are already off
while a hart waits for a lock: was that only a convenience before, and is it still? What
exactly does holding() mean when there is no “locked” flag any more?
You also build the instrument to see the difference: a system call that makes three
processes hammer one kernel lock and keeps score. On QEMU the result is not what the
textbook predicts, and the lab shows what we measured and why.
Why the swap loop in acquire promises mutual exclusion but no order, and what a fair lock has to remember that it does not.
Which parts of a lock need an atomic read-modify-write, which need only ordering, and which need neither; and how C11 atomics with acquire and release ordering turn into RISC-V instructions in this build.
How unsigned arithmetic modulo 2^32 behaves when a counter wraps, which comparisons survive the wrap, and how to make a wrap bug show up in seconds instead of hours.
Does a hart that is only waiting for a lock, not yet holding it, need interrupts off? Is the answer the same for a free-for-all as for a queue?
What holding and lk->cpu promise, why they name a hart, and why the order of two stores in release matters.
How to measure fairness on three harts, and why aggregate numbers on an emulator can hide what a per-acquisition measurement shows.
git clone https://github.com/ShowMeTheStack/xv6-riscv-labs
cd xv6-riscv-labs
git checkout -b my-ticketlock 06aad25 # start your own
git diff 06aad25 origin/ext/20-ticketlock # only when you want the answer
1. The spec
The lock. Replace the swap loop with a lock that hands itself to waiting harts in the
order they asked for it: first come, first served (FIFO), with no hart passed over by a
later arrival. struct spinlock keeps its size and its name and cpu fields; what
replaces the locked flag is yours to design (the think section works it out).
What must not change.
acquire still calls push_off first and panics acquire if this hart already holds
the lock; release still panics release if it does not, and calls pop_off last.
holding still answers “does this hart hold the lock”, so that p->lock can still be
acquired by the scheduler and released by the process on the same hart
(Locks and interrupt state).
Use the compiler’s C11 atomic built-ins (__atomic_...), not hand-written assembly, and
read kernel/kernel.asm to see what they became.
Any counter you add must keep working when it wraps around from its largest value to 0.
usertests -q must print ALL TESTS PASSED on three harts.
The instrument. A test system call, int lockbench(int nproc, int total, struct lbstat *st). lockbench(0, total, 0) resets it, and fails with -1 while a run is in progress
(a reset reinitializes the lock under any holder). Then nproc processes call it at once; each
waits at a start line until all have arrived, then acquires and releases one kernel lock,
benchlock, until total acquisitions have been made in all. Inside the critical section
it checks that nobody else is inside and keeps score: acquisitions per caller and per hart,
the wait for each acquisition (timed with the time CSR), and the longest run of
acquisitions by one hart.
The test program, locktest [nproc [total]] (3 processes and 300,000 acquisitions by
default), prints the numbers and checks one thing, mutual exclusion:
$ locktest
locktest: 3 processes, 300000 acquisitions of one lock
locktest: process 0: 101214 acquisitions, wait mean 768 ns, longest 87 us
locktest: process 1: 98549 acquisitions, wait mean 786 ns, longest 75 us
locktest: process 2: 100237 acquisitions, wait mean 781 ns, longest 88 us
locktest: per hart: 103565 94352 102083
locktest: longest run by one hart: 24
locktest: 203 ms, 1477 acquisitions per ms
locktest: mutual exclusion (300000 counted, 0 overlaps): OK
locktest: fairness is not checked: compare the numbers above
The last line is deliberate. Fairness is something to measure, not to assert: the
numbers vary from run to run and with the load on the machine running QEMU, and the
measurement that shows the ticket lock’s real property needs a counter inside
acquire itself (see Measure).
2. Think first
Answer each question in your head (or on paper) before opening a hint. Hints get more specific; the reference answer comes last.
1What does the swap loop promise, and what does it not?
Three harts want the same lock. Hart 0 holds it; harts 1 and 2 are spinning in
acquire. Hart 0 releases it, and a moment later wants it again. Who gets the lock
next? Is there any bound on how many times hart 1 can be passed over before it gets in?
Commit to an answer before the hints.
After the sw zero that frees the lock, every spinning hart and the releasing hart
(if it calls acquire again) race to execute the next amoswap. The memory system
orders the swaps; the code does not.
Hint 3.
Compare “the lock is free, whoever swaps first wins” with “the lock goes to whoever
has waited longest”. The second needs some state that records arrival order. What
is the smallest such state?
The reference design
The swap loop promises mutual exclusion and nothing else. When hart 0 stores 0
into locked, the next amoswap.w.aq to reach that word, from any hart, wins. A
failed swap leaves no trace: hart 1’s thousand earlier attempts count for nothing.
So there is no bound. Hart 1 can lose every race, in principle forever (starvation).
The likeliest winner is often the hart that just released: it is already running, it is
a few instructions away from its next acquire, and on real multi-core hardware it
still has the lock’s cache line in its own cache, while the spinners must fetch it. Linux
met exactly this: its x86 spinlock (an atomic decrement, as unfair as a swap) was
replaced by ticket locks in Linux 2.6.25 (2008), after Nick Piggin measured threads on an
8-core, two-socket Opteron differing by up to 2× in run time, some passed over up to a
million times
(LKML,
LWN).
What QEMU shows is another matter, and worth measuring rather than assuming. In this
lab’s measurement (three processes, 300,000 acquisitions, nine runs), the swap loop
gave each process between 97,150 and 102,533 of them: close to even. But counted one
acquisition at a time, it let a waiter be passed by as many as 126 others while it
spun. The ticket lock built below never let anybody be passed by more than 2, the
number of other harts.
Check yourself
1warm-upClick the line
In the original acquire, click the line where the decision “which waiting hart
gets the lock next” is made.
True or false: with the original swap loop on three harts, a hart that has been
spinning in acquire gets the lock after at most two other acquisitions.
Why?
2How do you hand out turns?
Design the smallest data structure that lets harts get a lock in the order they asked
for it, using only one atomic instruction per acquire. Which field must be changed
with an atomic read-modify-write, and which field can be changed with an ordinary store?
Why?
Hint 1.
Think of a deli counter: a roll of numbered tickets, and a display showing the number
now being served. How does a customer know it is their turn?
Hint 2.
Two harts must never get the same number, even if they ask at the same instant. But
how many harts ever change the number on the display, and when?
Hint 3.
Two unsigned counters in struct spinlock. The one handed out needs a fetch-and-add
that returns the old value; the RISC-V “A” extension has an AMO for that. The other is
written only by one hart at a time; think about which one and why.
The reference design
Two counters, next and serving, both starting at the same value:
Take a ticket:my = fetch_and_add(&lk->next, 1). This must be one atomic
read-modify-write. With a plain load and store, two harts could both read 7, both
store 8, and both hold ticket 7: both would enter. On RISC-V the fetch-and-add is the
AMO amoadd.w, one instruction that returns the old value.
Wait: spin until lk->serving == my.
Release:lk->serving = lk->serving + 1. This needs no atomic
read-modify-write, because only one hart ever writes serving: the holder, while it
holds the lock. A load, an add and a single store are enough. (The store must still
be one indivisible store with the right ordering; that is the next question.)
The lock is free when next == serving (no ticket handed out that has not been
served). The queue is implicit: the waiting harts hold the numbers serving+1,
serving+2, … and get in in that order. With three harts, a waiter can be passed by at
most the two others.
struct spinlock keeps its size: locked was a 4-byte uint padded to 8, and two
uint counters fill the same 8 bytes, so name stays at offset 8 and cpu at 16, and
nothing else in the kernel that embeds a spinlock changes layout.
Check yourself
1solidChoose one
A learner writes the ticket step as my = lk->next; lk->next = my + 1; (plain
C, no atomics). What can go wrong on three harts?
2warm-upMatch the pairs
Match each operation of the ticket lock to what it needs.
3What ordering does each step need, and what will the compiler emit?
Before writing code, decide the memory ordering of each of the three steps: taking the
ticket, the load in the spin loop, and the store in release. Which of them must be
acquire, which release, which can be relaxed? Then predict the RISC-V instructions: will
the ticket be amoadd.w or amoadd.w.aq? Where will a fence appear, and which kind?
Hint 1.
Read Locks and interrupt state and the original lock: .aq on the swap, fence rw,w
before the freeing store. Then ask, for each step: which memory accesses must not
move across it?
Hint 2.
The critical section must not start before the load that sees your number. Taking a
ticket protects nothing by itself: before your number is called, you touch no shared
data.
Hint 3.
One of the three steps needs no ordering, one needs acquire, one needs release. Ask
which step grants the right to touch the data and which gives it up. Then look for
fence in kernel/kernel.asm and work out what each one orders.
The reference design
Ticket: relaxed.__atomic_fetch_add(&lk->next, 1, __ATOMIC_RELAXED) compiles to
amoadd.w a4,a5,(s1) at 0x80000e58 in the branch’s build (commits 3 and 4 compile
these functions to the same addresses): no .aq, no .rl. Nothing needs
ordering against it. The ticket is just a number; owning it gives no right to touch
shared data.
Spin: acquire.__atomic_load_n(&lk->serving, __ATOMIC_ACQUIRE) compiles to
lw a5,0(a5) at 0x80000e62 followed by fence r,rw at 0x80000e64, on every
iteration. The fence keeps every later load and store (the critical section) after the
load that finally sees serving == my, and so after the previous holder’s release
store.
Release: release.__atomic_store_n(&lk->serving, lk->serving + 1, __ATOMIC_RELEASE) compiles to lw a5,4(s1), addiw a5,a5,1, fence rw,w at
0x80000ef0, sw a5,0(a4) at 0x80000ef4. The fence publishes the critical
section’s accesses before the store that lets the next hart in. The plain lw that
reads serving first is fine: only this hart writes it.
Compared with the original: the old acquire put its ordering on the AMO itself
(amoswap.w.aq); the ticket lock moves it to the load that ends the wait. The release
side compiles to the same fence rw,w and a single sw.
The fence r,rw costs something on every spin iteration, not only the last. A
production lock would spin with relaxed loads and add one acquire fence after the loop;
this lab keeps the version whose C reads most directly.
Check yourself
1solidType a number
In this build, how many fence instructions does one hart execute in
acquire + release of a ticket lock if it finds the lock free (its first load
already sees its number)? Count only acquire and release themselves.
decimal, 0x hex or 0b binary
2deepChoose one
Why is it safe for the ticket’s __atomic_fetch_add to be __ATOMIC_RELAXED?
4What happens when the counters wrap?
next and serving are 32-bit uints. A busy lock hands out 2^32 tickets sooner than
you might think. When next goes from 0xffffffff to 0, does your acquire still work?
Would while (serving < my) (wait while it is not yet my turn) work as well as
while (serving != my)? What about a signed comparison? And how would you test the
wrap without waiting for four billion acquisitions?
Hint 1.
C defines unsigned arithmetic modulo 2^32: 0xffffffff + 1 == 0. Write down the
tickets around the wrap: holder 0xffffffff, waiters 0, 1.
Hint 2.
Equality only asks “is it exactly my number”. An ordering comparison asks “has the
display passed my number”, which assumes numbers only grow.
Hint 3.
Which comparison never asks which of two numbers is bigger? And to test the wrap,
where could the counters start so that it happens in seconds?
The reference design
With != the wrap is harmless. Tickets are compared only for equality, and modulo 2^32
every outstanding ticket is distinct as long as fewer than 2^32 harts wait at once
(with three harts, at most three tickets are outstanding). The holder of 0xffffffff
releases by storing 0xffffffff + 1, which is 0, and the hart holding ticket 0
sees its number. The gdb session in the reveal shows exactly that handoff.
Ordering comparisons break at the wrap:
Unsigned serving < my: when the holder has 0xffffffff and a waiter takes
ticket 0, the test 0xffffffff < 0 is false, so the waiter stops waiting and walks
in while the holder is still inside. Clinic 2 shows the result.
Signed (int)serving < (int)my:0xffffffff is −1 and 0 is 0, so the
unsigned wrap is fine; but at 0x7fffffff → 0x80000000 the signed values jump from
the largest positive to the most negative, and the same break happens there.
To make a wrap happen at once, the reference solution starts every lock’s counters at
0xffffff00, 256 tickets below the wrap, as Linux starts the 32-bit tick count
(jiffies) five minutes before it wraps. The busy locks wrap during boot. But a test only checks the
wrap you place it at: the signed comparison passes it (clinic 2).
Check yourself
1solidChoose one
The holder has ticket 0xffffffff; a waiter has ticket 0x00000000. The code waits
with while (__atomic_load_n(&lk->serving, __ATOMIC_ACQUIRE) < my) on uints. What
happens?
2deepType a number
The kernel supports up to NCPU = 8 harts. Suppose all 8 run. The counters are
32-bit and compared with !=, and a hart holds at most one ticket for a given lock
(it waits with interrupts off, and taking a second ticket for a lock it holds
panics). At most how many tickets for one lock can be outstanding at once (handed
out and not yet served past), counting the holder’s?
decimal, 0x hex or 0b binary
5Is push_off still only about interrupt handlers?
acquire calls push_off before anything else. In the original lock that stops an
interrupt handler on this hart from wanting a lock this hart holds. Suppose a learner
moves push_off() after the wait (“interrupts off only once I hold it”). With the swap
loop, how bad is that? With tickets, what can an interrupt (or a yield on a timer
tick) do to a hart that has taken a ticket but is still waiting?
A waiter in the swap loop owns nothing: if it is interrupted, the others just keep
swapping. A waiter with a ticket owns a place in the line. Every ticket after it is
served only after it.
Hint 3.
Work out the case “hart 0 holds ticket N for tickslock but has not been served; the
timer interrupts it; clockintr takes ticket N+1”. Who can make progress?
The reference design
push_off must still come first, and with tickets it matters far more.
With the swap loop and a late push_off, the danger window is only between winning the
swap and the csrrci inside push_off: a handful of instructions in which the lock is
held with interrupts on. An interrupt there whose handler wants the same lock spins
forever on its own hart.
With tickets, the window is the whole wait. A hart that has taken ticket N and is
spinning with interrupts on can be interrupted. If the handler on that hart wants the
same lock, it takes ticket N+1 and spins. Ticket N is called, but its owner is the
interrupted code underneath the handler, which cannot run until the handler returns,
and the handler waits for N to finish. Every later ticket, on every hart, waits too.
The hart need not hold the lock at all. And it need not be a device handler: a timer
interrupt in kerneltrap calls yield, which acquires the process’s own p->lock;
if the interrupted code was waiting for that very lock (in killed, say), the
process queues behind itself. Clinic 3 recorded both cases.
With interrupts off from before the ticket until the release, a hart holding a ticket
always reaches the front and gets through: noff > 0 means SIE = 0
(Locks and interrupt state). The patch that brought ticket locks to Linux makes the
same point: with tickets, a CPU can no longer re-enable interrupts while it spins on a
lock that interrupt handlers take
(LKML).
Check yourself
1solidFill in the machine state
A process is in sys_uptime on hart 0, inside the reference acquire(&tickslock),
spinning because another hart holds the lock. Interrupts were on before the system
call’s first acquire, and no other lock is held. Fill in the machine state of hart
0 while it spins.
2deepChoose one
With push_off moved after the wait, the recorded freezes all had the same shape.
Which?
6What does holding() mean now, and in what order does release write?
There is no locked flag any more. How does holding tell “this hart holds the
lock” now? Is lk->cpu == mycpu() alone enough? And release must do two writes:
clear lk->cpu and let the next ticket in. Does the order matter? What could another
hart see in between?
Once serving is advanced, the next hart may already be inside and may already have
written its own cpu into lk->cpu.
Hint 3.
“Held” needs no new field: it can be read off the two counters. Of release’s two
writes, which one hands the lock to someone else? Do everything that is yours before
it.
The reference design
holding(lk) becomes lk->next != lk->serving && lk->cpu == mycpu(). The first half
says “some ticket has been handed out and not yet served past”, i.e. the lock is held or
awaited; the second says this hart recorded itself as the holder. lk->cpu is written
only by the holder (in acquire after its wait, and to 0 in release), so in the
reference code it alone would give the same answer; the first half keeps the check
meaning what it said before (“held, and by me”), and costs two loads.
It still names a hart, not a process. That is what lets p->lock cross swtch:
the scheduler acquires it (kernel/proc.c:446) and the process releases it in
yield, sleep or forkret, on the same hart. The ticket lock does not care which
thread executes the release store.
Order in release:lk->cpu = 0 must come before the release store. After the
store, the next ticket’s hart may enter at once and set lk->cpu to itself; a late
lk->cpu = 0 from the old holder would erase it, and the new holder’s own release
would then fail holding() and panic release. The original code has the same order
for the same reason (the comment in Locks and interrupt state). In this build the window
in the wrong order is one instruction; clinic 4 widened it to see what happens.
Check yourself
1solidPut in order
Put the reference release in order.
sw the new serving
lk->cpu = 0
load serving and add 1
check holding(lk), panic “release” if this hart does not hold it
pop_off()
fence rw,w
2solidTrue or false, and why
True or false: with the ticket lock, the scheduler can still acquire a process’s
p->lock and let the process release it after swtch.
Why?
7What does fairness cost, and how will you see it?
Before measuring, predict. On real multi-core hardware, what does every spinning hart
read in a ticket lock, and what happens to those harts when the holder releases? What
happens to the line if the hart whose number is called next is slow to notice (its
thread is delayed)? And on QEMU, whose harts are host threads, which of these effects
can you expect to see at all? Design an experiment that would show the difference
between the two locks.
Hint 1.
Every waiter loads serving. One word, one cache line, read by everyone. Compare the
swap loop, where every waiter writes the word.
Hint 2.
FIFO means the lock waits for the next ticket’s hart, even if another hart is ready
and closer. What if that hart’s host thread is descheduled for a millisecond?
Hint 3.
Aggregate shares (who got how many) are easy to measure and can hide a lot. Count,
for each acquisition, how many other acquisitions happened between the moment the
hart asked and the moment it got in.
The reference design
Costs on real hardware (reasoned, not measured here). All waiters spin on the same
word. Each release is one store that invalidates every waiter’s copy of the line, and
all of them fetch it again, though only one can proceed: traffic grows with the number
of waiters. The swap loop is worse while spinning (every iteration is a write), but a
ticket lock is no cure for contention. Scalable locks (MCS, and the qspinlock Linux uses
today) give each waiter its own word to spin on.
FIFO has its own cost: the lock goes to the next ticket even if that hart is slow, so a
delayed waiter delays everyone behind it. On a virtual machine whose virtual CPUs can be
descheduled by the host, this “lock-waiter preemption” is a well-known problem for
ticket locks.
On QEMU. QEMU’s TCG runs each hart as a host thread. There is no
model of RISC-V caches, so the cache-line effects above do not appear as such, and host
scheduling adds noise of its own. We measured (see Measure): aggregate shares are close
to even with both locks, throughput differs by less than the run-to-run noise, but
a counter added inside acquire shows the property exactly: with tickets, no waiter was
ever passed by more than 2 others in 2.7 million acquisitions; with the swap loop, about 2
percent of acquisitions were passed by 2 or more, and the worst by 126. Tickets also
spun about twice as many iterations per acquisition (40–50 against about 20), because
the hart that just released now waits its turn instead of walking straight back in; but
each iteration is a load rather than an AMO, and in the same builds the mean wait was not
longer (709–905 ns against 865–1,098 ns). Iterations are not time.
Check yourself
1deepChoose all that apply
Which of these did the measurements on QEMU (three harts, three processes hammering
one lock) actually show?
3. Build it
Start from the frozen commit, in your own clone of xv6:
git checkout -b my-ticketlock 06aad25
Build the instrument first, and measure the old lock.
The system call.SYS_lockbench (23) in kernel/syscall.h, the extern and the
table entry in kernel/syscall.c, entry("lockbench") in user/usys.pl, the prototype
in user/user.h, a struct lbstat in a header both sides include, and the handler in
a new kernel/lockbench.c (add $K/lockbench.o to OBJS). The handler’s loop is
push_off, read the time CSR, acquire, read it again, keep score, release,
pop_off. Keep the start line (the barrier) outside any lock and with interrupts on.
The reset reinitializes the lock, so it must refuse while any caller is mid-run: count
the callers under a second lock and make the reset fail unless the count is 0.
The program.user/locktest.c and $U/_locktest in UPROGS. Run it on the
original lock and keep the output: that is your “before”.
Then change the lock, in an order that keeps the kernel bootable:
The struct. Replace locked with next and serving; initlock sets both. Fix
every use of locked (only kernel/spinlock.c has them: grep -n locked kernel/*.c;
the locked in sleeplock.c is a different struct).
acquire, release, holding together: the kernel cannot boot with only half of them.
Then read kernel/kernel.asm and find amoadd.w, the lw + fence r,rw loop and the
fence rw,w + sw. If the loop has no lw inside it, see clinic 1.
Test: boot, locktest, usertests -q.
The wrap. Start the counters near 0xffffffff and run everything again.
Debugging. Run QEMU with three harts (-smp 3) and attach gdb. A lock bug usually
shows as one of three things:
panic: acquire / panic: release: holding disagreed. Break on panic and print
the lock (up, then p/x *lk): next, serving and cpu tell you who was in line and
who the lock thinks holds it.
A silent freeze. Attach gdb, info threads, thread apply all bt, and print the lock
each hart is spinning on. In acquire, the ticket is in a register (a4 in this build)
and serving is in memory: if the lock’s serving equals a ticket nobody is spinning
with, its owner is stuck somewhere else, often underneath an interrupt handler on the
same hart. The frame below kernelvec is not unwound by gdb; read sepc in
kerneltrap's frame and the registers that kernelvec saved on the stack (a4 at
offset 104) to see the interrupted code’s ticket.
Nothing at all. Several real bugs in this lab never failed on QEMU (clinics 4 and 5).
When the reasoning says a bug is there, widen the window or accept that the test cannot
see it.
4. Debugging clinic
Each of these bugs was put into the reference solution on purpose and run on three harts. The symptom is exactly what happened. Try to explain it before revealing why.
1Spinning on a plain load
The wait reads serving as an ordinary C variable:
- while (__atomic_load_n(&lk->serving, __ATOMIC_ACQUIRE) != my)
+ while (lk->serving != my)
;
(The clinic kernels were built without lockbench’s reset check; spinlock.c is the
same, but their kernel addresses are lower than in the branch’s build, e.g. acquire at
0x80000db4 instead of 0x80000e3e.)
The compiler is allowed to assume no other thread changes lk->serving inside the
loop, and it does. The whole loop became:
80000dd4: lw a4,4(s1) # serving, loaded once
80000dd6: bne a4,a5,80000dd6 # branch to itself
What happened when we ran it
xv6 kernel is booting
hart 1 starting
(the console stays like this; gdb attached after 30 seconds, second boot:)
Id Target Id Frame
* 1 Thread 1.1 (CPU#0 [running]) 0x0000000080000dd6 in acquire (lk=lk@entry=0x8000fe18 <proc>) at kernel/spinlock.c:52
2 Thread 1.2 (CPU#1 [running]) 0x0000000080000dd6 in acquire (lk=lk@entry=0x8000fe18 <proc>) at kernel/spinlock.c:52
3 Thread 1.3 (CPU#2 [running]) 0x0000000080000dd6 in acquire (lk=lk@entry=0x8000f948 <pr>) at kernel/spinlock.c:52
Thread 3 (Thread 1.3 (CPU#2 [running])):
#0 0x0000000080000dd6 in acquire (lk=lk@entry=0x8000f948 <pr>) at kernel/spinlock.c:52
#1 0x000000008000057a in printk (fmt=fmt@entry=0x800070a0 "hart %d starting\n") at kernel/printk.c:71
#2 0x0000000080001064 in main () at kernel/main.c:38
Thread 2 (Thread 1.2 (CPU#1 [running])):
#0 0x0000000080000dd6 in acquire (lk=lk@entry=0x8000fe18 <proc>) at kernel/spinlock.c:52
#1 0x00000000800020fe in sleep_prepare (chan=chan@entry=0x80015848 <bcache+24>) at kernel/proc.c:551
#2 0x0000000080005c7a in virtio_disk_rw (b=b@entry=0x80015848 <bcache+24>, write=write@entry=0) at kernel/virtio_disk.c:288
[...]
Thread 1 (Thread 1.1 (CPU#0 [running])):
#0 0x0000000080000dd6 in acquire (lk=lk@entry=0x8000fe18 <proc>) at kernel/spinlock.c:52
#1 0x0000000080002190 in wakeup (chan=chan@entry=0x80007878 <tx_chan>) at kernel/proc.c:581
#2 0x0000000080000a18 in uartintr () at kernel/uart.c:145
[...]
Thread 3 (Thread 1.3 (CPU#2 [running])):
$4 = 0xffffffffffffff03
Thread 2 (Thread 1.2 (CPU#1 [running])):
$5 = 0xffffffffffffff03
Thread 1 (Thread 1.1 (CPU#0 [running])):
$6 = 0xffffffffffffff02
Thread 3 (Thread 1.3 (CPU#2 [running])):
$7 = 0xffffffffffffff04
Thread 2 (Thread 1.2 (CPU#1 [running])):
$8 = 0xffffffffffffff04
Thread 1 (Thread 1.1 (CPU#0 [running])):
$9 = 0xffffffffffffff03
[...]
Thread 3 (Thread 1.3 (CPU#2 [running])):
$13 = {next = 0xffffff05, serving = 0xffffff04, name = 0x80007028, cpu = 0x0}
Thread 2 (Thread 1.2 (CPU#1 [running])):
$14 = {next = 0xffffff05, serving = 0xffffff03, name = 0x80007180, cpu = 0x0}
Thread 1 (Thread 1.1 (CPU#0 [running])):
$15 = {next = 0xffffff05, serving = 0xffffff03, name = 0x80007180, cpu = 0x0}
Three boots, the same freeze before the shell (one without gdb, two with): the console
stopped after hart 1 starting, and gdb found all three harts at 0x80000dd6, the bne that branches to
itself. The three groups of values are thread apply all p/x $a4 (the copy of serving
each hart loaded once), p/x $a5 (each hart’s ticket) and p/x *lk (the lock in
memory). Thread 1 is hart 0, thread 3 is hart 2.
Read the memory and the registers together. On hart 2, pr.lock’s serving is
0xffffff04 in memory, and hart 2’s ticket (a5) is 0xffffff04: its turn has come.
But it compares its ticket with a4, the copy of serving it loaded once,
0xffffff03, and will compare with that copy forever. Hart 0 (in a UART interrupt, in
wakeup) is in the same state for proc[0].lock: ticket 0xffffff03, serving in
memory 0xffffff03, stale copy 0xffffff02. Hart 1 waits behind hart 0 for the same
lock, with ticket 0xffffff04. Nobody holds anything (cpu = 0x0); every lock is
merely waiting for a hart that cannot see its own number.
Without an atomic (or volatile) access, C lets the compiler assume a plain variable
does not change unless this thread writes it, and moving a loop-invariant load out of
a loop is a standard optimization even at xv6’s -O. The original swap loop could not
be broken this way: amoswap is an atomic built-in, which the compiler must execute
every time. __atomic_load_n makes every iteration a real load, and its acquire
ordering supplies the fence.
The freeze happens at the first contended lock; with three harts booting at once, the
first is during boot.
2Waiting while serving < my
An ordering comparison instead of equality, on the same uints:
- while (__atomic_load_n(&lk->serving, __ATOMIC_ACQUIRE) != my)
+ while (__atomic_load_n(&lk->serving, __ATOMIC_ACQUIRE) < my)
;
(bne became bltu at 0x80000de0.) Everything else as in the reference, including
commit 4, which starts every lock at 0xffffff00.
What happened when we ran it
$ locktest
locktest: 3 processes, 300000 acquisitions of one lock
panic: release
(gdb from reset, a second boot, at the panic:)
Thread 3 hit Breakpoint 1, panic (s=s@entry=0x80007078 "release") at kernel/printk.c:139
[...]
#1 0x0000000080000e86 in release (lk=lk@entry=0x8000f9b0 <benchlock>) at kernel/spinlock.c:64
#2 0x0000000080000ca8 in sys_lockbench () at kernel/lockbench.c:114
[...]
$15 = {next = 0x3, serving = 0x0, name = 0x80007048, cpu = 0x0}
(another boot, gdb attached from reset; the panic came before the shell:)
xv6 kernel is booting
hart 2 starting
hart 1 starting
panic: release
Four boots of this kernel: two panicked release during locktest, two during boot
(one, with gdb, in wakeup releasing proc[1].lock; one without gdb). The bug can
only fire at a wrap: away from it a waiter always has serving <= my, so < and !=
agree. The panic we stopped in locktest shows the wrap directly.
The lock was at the wrap: the holder had ticket 0xffffffff, so serving was
0xffffffff. A hart that took ticket 0 tested 0xffffffff < 0, which is false, and
walked in while the holder was still inside. Two holders; each wrote its hart into
lk->cpu. The first to release cleared lk->cpu and advanced serving to 0; the
second then called release, holding found cpu == 0, not its own hart, and
panicked. gdb shows the aftermath: serving is 0, three tickets (0, 1, 2) are
out, and nobody is recorded as the holder. Without the holding() check the damage
would have been silent: both releases would have advanced serving, the counters would
have agreed again, and the only trace would be whatever the two harts did to the
protected data while both were inside.
Without commit 4 the counters would start at 0 and this kernel would pass every test
for about an hour of hammering one lock. With the counters starting 256 below the wrap,
busy locks wrap during boot and benchlock wraps in every locktest. That still is not
certain: one locktest run crosses the wrap once and catches the bug only if a waiter
takes its ticket at that moment. In one batch, both locktest runs that reached the
wrap panicked; in another (5 boots, all of which panicked), 3 of the 8 runs that
crossed the wrap passed with 0 overlaps: OK.
The signed variant ((int)serving < (int)my) shows the limit of that test. With the
counters at 0xffffff00 it wraps from −1 to 0, which a signed comparison handles: one
boot passed locktest twice and usertests -q, another passed five locktests. Its
wrap is at 0x7fffffff → 0x80000000. Starting the counters at 0x7fffff00 instead,
it failed the same way, only less often: one boot passed two locktests and
usertests -q; the next passed three locktests and then printed panic: release in
the fourth. A wrap test checks only the wrap you put it at; equality has none.
3Turning interrupts off only once the lock is held
push_off() moved from the top of acquire to just after the wait:
acquire(struct spinlock *lk)
{
uint my;
- push_off(); // disable interrupts to avoid deadlock.
if (holding(lk))
panic("acquire");
...
while (__atomic_load_n(&lk->serving, __ATOMIC_ACQUIRE) != my)
;
+ push_off(); // disable interrupts now that we hold it.
To compare, the same change was made to the original swap-loop lock (commit 2). The
stress program was tour 52’s lockstress up 300000 (not on the branch): three
processes, each calling uptime() 300,000 times, so tickslock is hammered from all
three harts while clockintr takes it on hart 0 ten times a second.
What happened when we ran it
$ lockstress up 300000
[...]
u1.201000 u0.220000 u2.209000 u1.202000 u0.221000
(the end of the progress line: the console stopped there; 60 seconds later gdb attached)
Id Target Id Frame
* 1 Thread 1.1 (CPU#0 [running]) acquire (lk=lk@entry=0x80015818 <tickslock>) at kernel/spinlock.c:51
2 Thread 1.2 (CPU#1 [running]) acquire (lk=0x80015818 <tickslock>) at kernel/spinlock.c:51
3 Thread 1.3 (CPU#2 [running]) acquire (lk=0x80015818 <tickslock>) at kernel/spinlock.c:51
Thread 3 (Thread 1.3 (CPU#2 [running])):
#0 acquire (lk=0x80015818 <tickslock>) at kernel/spinlock.c:51
#1 0x0000000080002cc2 in sys_uptime () at kernel/sysproc.c:108
#2 0x0000000080002ac6 in syscall () at kernel/syscall.c:148
#3 0x000000008000284c in usertrap () at kernel/trap.c:68
#4 0x0000003ffffff09c in ?? ()
[...]
Thread 1 (Thread 1.1 (CPU#0 [running])):
#0 acquire (lk=lk@entry=0x80015818 <tickslock>) at kernel/spinlock.c:51
#1 0x000000008000270e in clockintr () at kernel/trap.c:170
#2 0x00000000800027a2 in devintr () at kernel/trap.c:215
#3 0x00000000800028dc in kerneltrap () at kernel/trap.c:149
#4 0x00000000800057b8 in kernelvec () at kernel/kernelvec.S:38
Backtrace stopped: frame did not save the PC
[...]
Thread 3 (Thread 1.3 (CPU#2 [running])):
$4 = 0x9aa91
Thread 2 (Thread 1.2 (CPU#1 [running])):
$5 = 0x9aa93
Thread 1 (Thread 1.1 (CPU#0 [running])):
$6 = 0x9aa92
[...]
$13 = {next = 0x9aa94, serving = 0x9aa90, name = 0x80007270, cpu = 0x0}
[...]
(the frame under kernelvec on hart 0, unwound by hand:)
kvbt: interrupted code at sepc=0x80000dce, sp=0x3fffff3f80
#0 acquire (lk=0x80015818 <tickslock>) at kernel/spinlock.c:51
#1 0x0000000080002cc2 in sys_uptime () at kernel/sysproc.c:108
#2 0x0000000080002ac6 in syscall () at kernel/syscall.c:148
#3 0x000000008000284c in usertrap () at kernel/trap.c:68
#4 0x0000003ffffff09c in ?? ()
kvbt: saved a4=0x9aa90 a5=0x9aa8f
Tickets: 8 of 15 boots froze (8 of 28 lockstress up runs). Swap loop with the
same mistake: 1 of 7 boots froze (1 of 17 runs). Pooled, those numbers are weak
evidence, because the boots ran while the computer was doing different amounts of other
work, and timings on QEMU depend on that. The fair comparison is two batches in which
both kernels booted at the same time on the same computer: 7 of 8 ticket boots froze
and 0 of 8 swap-loop boots did. Load changes how often either freezes, but not the
order.
The capture above is the textbook case. (We unwound the interrupted frame in 3 of the 8
ticket freezes; the other 5 showed the same queue: cpu 0 and a served ticket that no
spinning hart held.) tickslock is serving ticket 0x9aa90, and
nobody is recorded as holding it (cpu = 0x0). The tickets handed out are 0x9aa90 to
0x9aa93. Harts 2 and 1 spin with 0x9aa91 and 0x9aa93 in a4 (in this build the
ticket is in a4; the $4–$6 values are thread apply all p/x $a4), hart 0’s
clockintr with 0x9aa92. Ticket 0x9aa90 is in no
spinning hart’s registers: it was saved by kernelvec on hart 0’s stack, in the frame
of the sys_uptime that the timer interrupted while it waited (sepc0x80000dce is
the top of the spin loop, and its saved a5 holds the last serving it read,
0x9aa8f). Its turn came while it was underneath clockintr, and clockintr waits for
its turn after it. Harts 1 and 2 still take timer interrupts and may yield, but that
cannot help: the code that owns 0x9aa90 can only run on hart 0, underneath
clockintr.
Another freeze had the same shape without a device handler. A process on hart 2 was in
killed (kernel/trap.c:81), waiting with a ticket for its own p->lock. The timer
interrupted it; kerneltrap called yield (kernel/trap.c:158), which took a
ticket for that same p->lock (kernel/proc.c:504): the process queued behind
itself. The scheduler on hart 1 and clockintr’s wakeup on hart 0 (holding
tickslock) queued for the same lock, and the whole machine stopped.
With the swap loop, a waiter holds nothing; the only window is the few instructions
between winning the swap and the csrrci in push_off. We did not attach gdb to the
one swap-loop freeze, so where it stopped is not recorded.
Deleting push_off() outright (instead of moving it) fails at once: the first
release, in the first printk of main, reaches pop_off with noff 0 and the
console shows only panic: pop_off.
4Letting the next ticket in before clearing lk->cpu
In this build the window is one instruction: sw a5,0(a4) (the release store) is
followed directly by sd zero,16(s1).
What happened when we ran it
$ locktest
[...]
locktest: mutual exclusion (300000 counted, 0 overlaps): OK
(five locktest runs, then usertests -q:)
ALL TESTS PASSED
$ locktest
[...]
locktest: mutual exclusion (300000 counted, 0 overlaps): OK
(a copy with a 1000-iteration delay loop between the two writes, gdb from reset:)
xv6 kernel is booting
hart 1 starting
hart 2 starting
panic: release
#1 0x0000000080000eac in release (lk=lk@entry=0x80020be0 <disk+296>) at kernel/spinlock.c:64
#2 0x0000000080005d0c in virtio_disk_rw (b=b@entry=0x80015848 <bcache+24>, write=write@entry=0) at kernel/virtio_disk.c:297
[...]
$15 = {next = 0xffffff03, serving = 0xffffff02, name = 0x80007658, cpu = 0x0}
As written, the bug never showed: six locktest runs (1.8 million acquisitions of
benchlock from three harts) and usertests -q passed. For it to fail, the next hart
must see the new serving, leave its loop and store its own cpu into lk->cpu, all
between two consecutive instructions of the old holder.
The widened copy shows what the bug does when it hits. Reconstructed from the code and
the lock’s state: a virtio_disk_intr on another hart released disk.vdisk_lock and, during its delay, virtio_disk_rw on hart 0 took
the lock (ticket 0xffffff02) and recorded cpu = cpus[0]. The delayed lk->cpu = 0
then erased that. When virtio_disk_rw released, holding saw cpu == 0 and
panicked release; gdb shows serving at the panicking hart’s own ticket and cpu 0.
The original code clears cpu first for exactly this reason
(Locks and interrupt state). A test that passes says little when the window is one
instruction wide.
The compiled release loses its fence: sd zero,16(s1), lw a5,4(s1),
addiw a5,a5,1, sw a5,4(s1), then the call to pop_off.
What happened when we ran it
$ locktest
[...]
locktest: mutual exclusion (300000 counted, 0 overlaps): OK
(three locktest runs, then:)
$ usertests -q
[...]
ALL TESTS PASSED
$ lockstress up 100000
[...] lockstress up 100000 done
$ locktest
[...]
locktest: mutual exclusion (300000 counted, 0 overlaps): OK
Nothing failed: four locktest runs, usertests -q and 300,000 uptime calls from
three harts. This is the same result as Tour 52: Breaking the lock rules's break 7, and for the same reason.
The fence orders the critical section’s stores before the store that lets the next
hart in. RVWMO permits a store to become visible to other harts before an earlier store
to a different address; when QEMU’s TCG runs on an x86-64 host, stores become visible
in program order, so the reordering the fence forbids does not occur there. On real RISC-V
hardware the next holder could read bench.count (or ticks, or a p->state) as it
was before the previous critical section’s writes.
Two more things this change gives up, also invisible here. A plain lk->serving++
lets the compiler reorder the critical section’s own stores past it (inside release
it cannot see them, which is why the build happened to keep the order). And the
spinners in other harts read serving with atomic loads while this store is not
atomic: in C11 terms that is a data race, undefined behaviour, even though RISC-V’s
aligned sw is in fact a single store. Not failing is not a pass.
5. The reference solution
Take the guided tour through the reference solution, one commit at a time, with the machine state at every step:
On the branch (ext/20-ticketlock, 4 commits), built with the project toolchain and run
on three harts (-smp 3 -m 128M), in one boot:
$ locktest
locktest: 3 processes, 300000 acquisitions of one lock
locktest: process 0: 101214 acquisitions, wait mean 768 ns, longest 87 us
locktest: process 1: 98549 acquisitions, wait mean 786 ns, longest 75 us
locktest: process 2: 100237 acquisitions, wait mean 781 ns, longest 88 us
locktest: per hart: 103565 94352 102083
locktest: longest run by one hart: 24
locktest: 203 ms, 1477 acquisitions per ms
locktest: mutual exclusion (300000 counted, 0 overlaps): OK
locktest: fairness is not checked: compare the numbers above
$ usertests -q
usertests starting
[...]
test lazy_sbrk: OK
test partial_write: OK
test unlinkcwd: OK
ALL TESTS PASSED
$ locktest
locktest: 3 processes, 300000 acquisitions of one lock
locktest: process 0: 101462 acquisitions, wait mean 810 ns, longest 74 us
locktest: process 1: 102318 acquisitions, wait mean 801 ns, longest 43 us
locktest: process 2: 96220 acquisitions, wait mean 858 ns, longest 87 us
locktest: per hart: 96220 105315 98465
locktest: longest run by one hart: 32
locktest: 216 ms, 1388 acquisitions per ms
locktest: mutual exclusion (300000 counted, 0 overlaps): OK
locktest: fairness is not checked: compare the numbers above
A reset while a run is in progress is refused (another boot of the same kernel; the
background run’s output arrives after the second prompt):
$ locktest 3 3000000 &
$ locktest: 3 processes, 3000000 acquisitions of one lock
locktest
locktest: 3 processes, 300000 acquisitions of one lock
locktest: another lockbench run is in progress
$ locktest: process 0: 1005673 acquisitions, wait mean 827 ns, longest 2014 us
[...]
locktest: mutual exclusion (3000000 counted, 0 overlaps): OK
locktest: fairness is not checked: compare the numbers above
locktest
locktest: 3 processes, 300000 acquisitions of one lock
[...]
locktest: mutual exclusion (300000 counted, 0 overlaps): OK
Without runlock, the same two commands print panic: release.
usertests -q passing on three harts means every lock in the kernel, including every
p->lock handed across swtch, works as a ticket lock, and every busy one crossed the
wrap during the run (a second boot, with gdb attached after usertests, found every lock
it printed wrapped except cons.lock). locktest crosses the wrap of benchlock with three
harts contending and found every acquisition counted once. Each commit builds on its own;
commit 2 (the original lock with the instrument) also passes usertests -q.
Shares need not be equal: in another run of this lock, process 2 got 89,392
acquisitions and the others about 105,000. A FIFO lock serves whoever is in line; it does
not guarantee equal shares to a process that is sometimes not in line (preempted between
iterations, or its host thread delayed).
Aggregate numbers (three processes × 300,000 acquisitions, three boots of each kernel,
alternating, three locktest runs per boot). These kernels lacked commit 1’s reset check,
which adds only a check-in and check-out under runlock around each run and leaves the
measured loop unchanged:
swap loop (commit 2)
ticket lock (commit 4)
smallest / largest share of one process
97,150 / 102,533
97,123 / 102,545
mean wait of one process
739–902 ns
863–996 ns
longest single wait in a run
14 µs – 4,004 µs
19–144 µs
longest run by one hart (see below)
14–54
6–36
throughput (acquisitions per ms)
1,351–1,630
1,209–1,351
On QEMU both locks share the lock nearly evenly in aggregate. The swap loop does not
starve anyone here. Run lengths do not separate the locks either: other runs of the ticket
lock gave 68, 72 and 86, because a waiter that is not in line (preempted, or its host thread
delayed) lets the other harts take turn after turn under either lock. The longest waits
(milliseconds) and the throughput track what else the computer is doing more than the
lock: other builds of the same lock gave 1,115 and 1,010 acquisitions per ms, builds
differing by one line gave as little as 591 (measured while the computer was busy with
other work; your times will differ), and in the instrumented builds below the ticket lock
was the faster one (1,408–1,754 against 1,107–1,345). We do not claim a throughput
difference.
Per acquisition. A scratch copy of each kernel (never the branch) counted, inside
acquire, how many other acquisitions of the same lock happened between the moment a
hart asked and the moment it got in, and how many times it went round the spin loop
(a counter acqs in struct spinlock, incremented by each new holder, and two per-hart
fields to hand the numbers to lockbench). For the ticket lock the count starts right
after the amoadd, for the swap loop right before the first amoswap: in both cases, the
moment the hart joins the contest. Nine runs of three processes per lock:
swap loop
ticket lock
most acquisitions that passed one waiter (per run)
12, 4, 4, 126, 7, 4, 7, 14, 6
2 in every run
acquisitions passed by 2 or more (per run of 300,000)
about 4,900–7,200
47–179
acquisitions passed by 3 or more (per run)
56–216
0
mean spin iterations per acquisition
19–22
40–50
The ticket lock’s bound is exact: with three harts and interrupts off while waiting, at
most two tickets can be ahead of yours, and 2.7 million acquisitions never saw more. The
swap loop usually behaves too (about 98% of acquisitions were passed by at most one
other), but nothing stops the occasional waiter from losing 126 races in a row. With two
processes the bound for tickets is 1, and it held; the swap loop’s worst was 3.
Tickets spin about twice as many iterations per acquisition, because a hart that releases
and immediately asks again now goes to the back of the line and waits, where under the
swap loop it often walked straight back in. But iterations are not time: a ticket
iteration is a load and a fence, a swap-loop iteration an AMO, and in these same
instrumented builds the mean wait of one process was not longer with tickets (709–905 ns)
than with the swap loop (865–1,098 ns).
What QEMU cannot show. QEMU’s multi-threaded TCG runs each hart as a host thread and
does not model RISC-V caches. On real hardware
the swap loop’s unfairness comes largely from cache-line ownership, and the ticket lock’s
cost from every waiter re-fetching the serving line after each release; neither is
modelled. The FIFO property, which is a property of the code, shows exactly.
7. Go further
Spin on relaxed loads, fence once. Move the acquire ordering out of the loop: spin
with __ATOMIC_RELAXED loads and put one __atomic_thread_fence(__ATOMIC_ACQUIRE)
after it. Read the new kernel.asm and measure spin iterations again. Teaches the
difference between an acquire load and an acquire fence.
Proportional backoff. A waiter knows how many tickets are ahead of it (my - serving). Pause for that many short delays before re-reading. Teaches why ticket locks
make backoff easy and swap loops do not.
An MCS lock. Give each waiter its own node to spin on, linked into a queue with one
atomic swap. Teaches how real kernels avoid every waiter re-reading one word, and why the
node must live somewhere other than the stack of a thread that might move.
Lock statistics. Turn the measurement counters into a permanent feature, per lock
name, printed by Ctrl-P (procdump). Teaches how Linux’s lockstat finds the locks
worth fixing, and what a counter on every acquire costs.
A trylock.int tryacquire(struct spinlock *) that never waits. Work out why “take
a ticket, give it back if it is not called” is impossible, and what compare-and-swap
(LR/SC) on both counters at once would need.