Extension labs · lab 21 · Concurrency · ★★★★☆

Lockdep-lite: a runtime lock-order checker

Two harts deadlock when each holds a lock the other wants. Tour 52: Breaking the lock rules built one on purpose: a copy of the kernel whose kfork takes wait_lock while it still holds the new child’s p->lock. The bug froze the machine, but only under a stress test, and when it froze all three harts spun with interrupts off and printed nothing. In this lab you build a checker that finds that bug at boot, on the first run, before any deadlock, and prints the two code paths that disagree.

The idea is Linux’s lockdep, cut down to fit xv6. Every time a lock is acquired, note which locks are already held: an order “this before that”, an edge in a graph. A deadlock needs two paths that take the same two locks in opposite orders (or a longer ring of them), so the first acquisition that would close a cycle in that graph is a warning, even if the two paths have never run at the same time. The checker does not wait for the unlucky timing. It needs the paths only to run once each, in any order.

Every design decision is a question about xv6’s locks. What is a class, and what does a class graph get wrong? Whose locks are “held”: a hart’s or a process’s, when p->lock is acquired by the scheduler and released by the process on the other side of swtch, and a sleep-lock’s holder may wake up on another hart? How can the checker protect its own graph when it runs inside acquire? What about interrupt handlers? And what do you do when the checker, on its first real run, reports cycles in code that has never deadlocked and never will? This tree has three of them, all of them known (the concept page measured them), and the lab handles each one honestly: by writing down, in code the checker can use, the rule that makes it safe, and checking that rule at run time where possible.

The reference solution is twelve commits. With it, boot and usertests -q run with no report while the checker examines about 27 million acquisitions, at a cost of 16 to 38 percent in run time (measured while the computer was busy with other work; your times will differ).

Read first: Tour 13: swtch and the lock handed across a context switch, Tour 18: Lock ordering: how xv6 avoids deadlock, Tour 51: The lock-order graph, measured, Tour 52: Breaking the lock rules · Locks and interrupt state

What this lab teaches

Why a deadlock between two locks needs two code paths that take them in opposite orders, and why a graph of lock classes can report that from one run of each path, before the deadlock ever happens.
What a class graph over-approximates: why iput’s inode lock under itable.lock, a directory and a file in it, and a log block and its home block all look like cycles to a class graph, and what knowledge of the code makes each one safe.
How can knowledge that only the code has (which instance, which role) be written into the code so that a checker can use it, and how can such an annotation fail loudly when it is wrong?
What must “held” mean when p->lock is acquired by one thread and released by another across swtch, and when a sleep-lock’s holder wakes up on another hart?
How can a checker that runs inside acquire protect its own data, and what must it still have in common with a spinlock?
What is the interrupt rule for locks, and does xv6 need a checker for it?
What run-time checking costs, and which part of it is worth optimising.

The reference branch

ext/21-lockdep in ShowMeTheStack/xv6-riscv-labs, branched from the frozen commit 06aad25; 12 commits.

git clone https://github.com/ShowMeTheStack/xv6-riscv-labs
cd xv6-riscv-labs
git checkout -b my-lockdep 06aad25   # start your own
git diff 06aad25 origin/ext/21-lockdep   # only when you want the answer

1. The spec

The checker. Add kernel/lockdep.c, a lock-order checker that runs from boot and is called by every acquire, release, acquiresleep and releasesleep.

Locks that play the same part must be treated alike: the 64 p->locks created by one loop in procinit, the 50 inodes, every pipe’s lock.
For every acquisition the checker learns what the acquirer already holds, and keeps the order “held before new” in a graph.
An acquisition whose order would close a cycle in that graph is reported, whether or not a deadlock happens, with both orders: where each of the two (or more) locks on each path was acquired, on which hart, by which process.
It also checks the interrupt rule: a lock class used inside an interrupt handler must never be held with interrupts on.
It must handle what this tree really does: p->lock acquired by the scheduler and released by a process on the same hart, sleep-locks held across sleep and released on another hart, and locks taken inside interrupt handlers.
After a report it panics (a kernel option may let it print the report and switch itself off instead).

What must not change. No struct that embeds a lock changes size. Every existing lock rule and check stays. Boot and usertests -q must run on three harts with the checker on and silent, and print ALL TESTS PASSED. Where the checker reports a cycle that cannot deadlock, the fix is an annotation in the code that explains why, not a switch that turns the checker off.

The test program, lockdeptest, uses a new system call lockdep(int cmd, struct ldstat *st): lockdep(0, &st) copies out the checker’s statistics, and lockdep(n, 0) runs kernel self-test n (locks of its own, acquired in a right or a wrong order) and returns how many reports it caused. The program checks each count, and that the kernel’s own locks have caused no report:

$ lockdeptest
lockdeptest: 18 classes, 39 orders, 101086 acquisitions checked, 39 of them slowly
lockdeptest: test 1: A then B; later B then A
lockdep: acquiring test A while holding test B may deadlock
[... the kernel's report ...]
lockdeptest: test 1: 1 report(s), as expected: OK
[... tests 2 to 6 ...]
lockdeptest: checker on, no report about the kernel's locks: OK
lockdeptest: 7 of 7 checks OK; read the reports above to see that each names both orders

The program counts reports; it does not check what they say. The last line says so.

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 checker reason about, a lock or a kind of lock?

There are 64 p->locks, 30 buffer locks, 50 inode locks, and a new lock for every pipe. The checker will remember “B was acquired while A was held” and look for cycles. Should A and B be individual locks, or groups of locks? If groups, how would you decide which lock belongs to which group, using only what xv6 already has? What would each choice catch, and what would it get wrong? Commit to an answer before the hints.

2Whose locks are "held"?

When a lock is acquired, the checker must know what is already held, to record the edges. Is that a property of a hart, of a process, or of a thread? Think about two cases before you answer: the scheduler acquires a process’s p->lock and switches to it, and the process releases it; and a process holding a buffer’s sleep-lock sleeps in virtio_disk_rw and later wakes up on another hart. What must your bookkeeping do in each case?

Check yourself

1solidFill in the machine state

The reference checker, at the moment forkret (its line 520) is about to release p->lock for the first process. gdb recorded this on hart 2. Fill in that hart’s state.

Privilege modeActive stackInterrupts (sstatus.SIE)noffintena

3When does the checker run, and what must it cost?

acquire is called tens of millions of times in usertests. Where in acquire should the checker look at the order: before the spin, or once the lock is held? And what must the common case cost, given that almost every order it will ever see, it has seen before?

Check yourself

1solidChoose one

A learner calls the checker at the end of acquire, after the spin loop and after lk->cpu = mycpu(). Now inject the kfork bug from Tour 52: Breaking the lock rules and run a stress test until the two harts collide. What does the learner’s checker print at that moment?

A report with both chains, just before the freeze.A report from the third hart, which is not deadlocked.Nothing: both harts are spinning in acquire and never reach the check.panic: acquire, because the checker notices the lock is held.

2solidType a number

In one of our runs of usertests -q with the reference checker, lockdeptest (run right after it) reported 19 classes, 46 orders, 27161729 acquisitions checked, N of them slowly. What was N? (The slow path is the one that takes the checker’s lock.)

decimal, 0x hex or 0b binary

4How does the checker protect its own graph?

The class table and the edge bitmaps are shared by all three harts, and pipes create classes at any time. They need a lock. Can it be a struct spinlock taken with acquire? If not, what exactly goes wrong, and what must the replacement still do that acquire does?

Check yourself

1solidChoose one

Why must ldlock be taken with interrupts off, even though it is not a struct spinlock?

Because amoswap only works with interrupts off.An interrupt handler on this hart would call the checker for its own locks and spin on ldlock, which this hart holds.To keep other harts out while the graph changes.It need not be: the checker is only called with interrupts off anyway.

5What is a cycle, and when do you look for one?

A new edge a -> b has just appeared. How do you decide whether it closes a cycle, and how much work may that take? And when the answer is yes, what should the report contain so that a person can act on it? What about a -> a, a lock acquired while another lock of the same class is held?

Check yourself

1solidPut in order

Put in order what the reference does in order() when a hart that holds wait_lock acquires a p->lock, and the edge wait_lock -> proc is not known yet.

check the bit again under ldlock
load after[wait_lock] without a lock; the proc bit is clear
release ldlock
search from proc for a path back to wait_lock
no path: record the edge with both traces and set the bit
take ldlock

6What do interrupt handlers change?

A disk interrupt arrives on hart 0 while process 7 is in the kernel holding an inode’s sleep-lock. virtio_disk_intr takes disk.vdisk_lock and wakes a process (taking p->locks). Should the checker record “inode before virtio_disk”? And Linux’s lockdep checks a second rule: a lock taken in an interrupt handler must never be held with interrupts on. Why is that rule needed, can xv6 break it, and where would you check it?

The reference design

The process’s sleep-locks are left out inside a handler. The order “inode, then vdisk_lock” is real in a sense: process 7 cannot let go of its inode until the handler returns, and the handler may wait for vdisk_lock. But it can never be part of a cycle. A handler only ever waits for spinlocks, and a spinlock holder can never wait for a sleep-lock: it would have to sleep holding a spinlock, and sched panics sched locks (noff above 1). So no chain of waits that starts in the handler can come back to process 7’s sleep-locks; and a sleep-lock taken in a handler is caught by the interrupt rule below. Recording such edges would add nothing (the same orders are learned from process context anyway: Ctrl-P shows inode -> ... virtio_disk). The reference brackets every handler in devintr with lockdep_irq_enter()/lockdep_irq_exit(), and inside a handler only the hart’s own spinlocks count. That list is empty when the handler starts: an interrupt is taken only at noff 0 (Locks and interrupt state). gdb caught exactly this case: hart 0 interrupted init while it held an inode’s lock, and clockintr acquired tickslock with inirq[0] = 1 and an empty list.

The interrupt rule. If code held lock L with interrupts on and a handler on the same hart wanted L, the handler would spin forever on a lock whose holder cannot run until the handler returns. Linux allows spinlocks with interrupts on (spin_lock versus spin_lock_irqsave), so its lockdep records, per class, “taken in a handler” and “held with interrupts on”, and reports a class that is both. In xv6 acquire turns interrupts off before anything else (push_off, kernel/spinlock.c:24), and pop_off and sched panic if they find interrupts on while a lock is held, so no spinlock is ever held with interrupts on. The rule is satisfied by construction.

The reference still records both uses, because one kind of lock is held with interrupts on: a sleep-lock. Taking one in a handler would be the bug (and would try to sleep in a handler). To see the check work on spinlocks, we called the checker before push_off in a scratch copy: the first boot reported proc is taken in interrupt handlers and held with interrupts on, from wakeup in clockintr and from killed in usertrap (which runs after intr_on).

Check yourself

1solidTrue or false, and why

True or false: in the reference kernel (unmodified), the interrupt-rule check can fire for a spinlock class.

TrueFalse

Why?

True: tickslock is taken both in clockintr and in sys_uptime, which runs with interrupts on.False: the checker skips interrupt handlers entirely.True: every p->lock is taken in wakeup from handlers and in system calls.False: acquire calls push_off, which clears SIE, before the checker runs, so the checker never sees a spinlock acquired with interrupts on.

7The first real run reports cycles that are not bugs. Now what?

With sleep-locks tracked, the checker’s first boot reports “inode while holding inode” (create locks a directory, then the file it is creating). Fix that, and the next run reports “buffer while holding buffer” (write_log). Fix that, and rm of any file reports “inode while holding itable” (iput) against “itable while holding inode” (namex). None of these has ever deadlocked. What do you change? (Deleting the check, or ignoring a class, is not an answer.)

Check yourself

1deepChoose one

Why is a trylock that records no order a correct way to silence the iput report, and not merely a convenient one?

Because itable.lock is a spinlock and the inode lock is a sleep-lock, so they cannot deadlock.Because a trylock is faster.Because iput runs rarely, so a deadlock there is unlikely.A deadlock is a ring of harts each waiting; an acquisition that never waits cannot be one of the waits, and iput’s try panics if it would have to.

2solidMatch the pairs

Match each report from the reference’s development runs with what made it safe.

inode while holding inode (create)buffer while holding buffer (write_log)inode while holding itable (iput)

3. Build it

Start from the frozen commit, in your own clone of xv6:

git checkout -b my-lockdep 06aad25

Milestones, each one booting:

Classes. A class table in a new kernel/lockdep.c (add $K/lockdep.o to OBJS), a cls field in struct spinlock and struct sleeplock (in the padding after locked: check with sizeof that nothing grew), set by initlock and initsleeplock. Its lock is a bare word with an atomic swap, taken with interrupts off.
Held lists. Hook acquire (after the holding check, before the spin) and release. Per-hart lists; release searches. Run usertests -q: if the handoff is wrong you will know at the first forkret.
Edges. A bitmap per class; Ctrl-P prints them (from procdump). Compare what you see after ls with Tour 51: The lock-order graph, measured's graph.
Cycles and reports. Search on new edges only, print both orders, turn off after one report. Run echo hi > x then rm x: you should get your first report (the iput one, already visible with spinlocks alone).
Sleep-locks, per process, then interrupt handlers.
Annotations, one report at a time, until boot and usertests -q are silent.
Panic on a report, the system call, the self-tests and lockdeptest.

Reading a report. It prints return addresses. On the host, in your xv6 directory:

${TOOLPREFIX}addr2line -f -i -e kernel/kernel 0x80003d66

A return address points just after the call, so decoding it as is can print a line well after the call (in one report, five lines later). Subtract 2 to land inside the call instruction: addr2line ... 0x80003d64. -i also shows functions that were inlined there.

Debugging (QEMU with -smp 3, and gdb). Break on panic and look at the checker’s state: p nheld, p held[$tp], p cls[3], p/x after. $tp is the hart number in the kernel. A conditional breakpoint on a hot function (lockdep_acquire) slows QEMU a lot; put it on something rarer (newedge, lockdep_irq_enter, a line in forkret) and set the hot one from there. Test your checker on wrong orders you write on purpose (the self-tests), not only on xv6: a checker that never reports is easy to write.

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.

1The checker’s lock is an ordinary spinlock

ldlock becomes a struct spinlock (never given a class) and the “lock without a class” panic is deleted:

-static uint ldlock;
+static struct spinlock ldlock;

 static void
 ldlk(void)
 {
-  while (__atomic_exchange_n(&ldlock, 1, __ATOMIC_ACQUIRE) != 0)
-    ;
+  acquire(&ldlock);
 }
 [... ldunlk: release(&ldlock) ...]
-  if (lk->cls == 0)
-    panic("lockdep: lock without a class");

What happened when we ran it

xv6 kernel is booting

hart 2 starting
hart 1 starting

(nothing more; gdb attached 25 seconds after boot:)
  Id   Target Id                    Frame
* 1    Thread 1.1 (CPU#0 [running]) kernelvec () at kernel/kernelvec.S:14
  2    Thread 1.2 (CPU#1 [running]) 0x0000000000000000 in ?? ()
  3    Thread 1.3 (CPU#2 [running]) 0x0000000000000000 in ?? ()
[...]
$1 = 0xfffffffe87c9dbb0
[...]
$2 = (char (*)[32768]) 0x80009bc0 <stack0>

(another boot, gdb from reset, breakpoint on lockdep_acquire if $sp < 0x80009d00:)
Thread 1 hit Breakpoint 1, lockdep_acquire (lk=lk@entry=0x80011cd0 <ldlock>, try=try@entry=0) at kernel/lockdep.c:384
[...]
$1 = 0x80009bd0
$2 = 1
#0  lockdep_acquire (lk=lk@entry=0x80011cd0 <ldlock>, try=try@entry=0) at kernel/lockdep.c:384
#1  0x0000000080000c18 in acquire (lk=lk@entry=0x80011cd0 <ldlock>) at kernel/spinlock.c:28
#2  0x0000000080000d90 in ldlk () at kernel/lockdep.c:53
#3  0x0000000080001020 in order (h=h@entry=0x80020260 <held>, c=c@entry=0, pc=pc@entry=0x80009da8 <stack0+488>) at kernel/lockdep.c:305
#4  0x0000000080001484 in orderall (c=0, pc=pc@entry=0x80009da8 <stack0+488>) at kernel/lockdep.c:335
#5  0x0000000080001794 in lockdep_acquire (lk=lk@entry=0x80011cd0 <ldlock>, try=try@entry=0) at kernel/lockdep.c:397
#6  0x0000000080000c18 in acquire (lk=lk@entry=0x80011cd0 <ldlock>) at kernel/spinlock.c:28
#7  0x0000000080000d90 in ldlk () at kernel/lockdep.c:53
#8  0x0000000080001020 in order (h=h@entry=0x80020260 <held>, c=c@entry=0, pc=pc@entry=0x80009fd8 <stack0+1048>) at kernel/lockdep.c:305
[...]
#33 0x0000000080001020 in order (h=h@entry=0x80020260 <held>, c=c@entry=6, pc=pc@entry=0x8000aac8 <stack0+3848>) at kernel/lockdep.c:305
#34 0x0000000080001484 in orderall (c=6, pc=pc@entry=0x8000aac8 <stack0+3848>) at kernel/lockdep.c:335
#35 0x0000000080001794 in lockdep_acquire (lk=lk@entry=0x80023460 <pid_lock>, try=try@entry=0) at kernel/lockdep.c:397
#36 0x0000000080000c18 in acquire (lk=lk@entry=0x80023460 <pid_lock>) at kernel/spinlock.c:28
#37 0x0000000080003062 in allocpid () at kernel/proc.c:97
#38 0x00000000800031dc in allocproc () at kernel/proc.c:125
#39 0x0000000080003254 in userinit () at kernel/proc.c:223
#40 0x000000008000257c in main () at kernel/main.c:31

2One class per lock instead of one per name

lockdep_class() makes a new class on every call instead of looking the name up:

-  for (c = 1; c < nclass; c++)
-    if (cls[c].sleep == sleep && strncmp(cls[c].name, name, 32) == 0)
-      break;
+  c = nclass; // every lock its own class
   if (c == nclass) {

What happened when we ran it

xv6 kernel is booting

panic: lockdep: too many classes

(gdb from reset, at the panic:)
#0  panic (s=s@entry=0x800091f0 "lockdep: too many classes") at kernel/printk.c:139
#1  0x0000000080001606 in lockdep_class (name=name@entry=0x80009470 "proc", sleep=sleep@entry=0) at kernel/lockdep.c:75
#2  0x0000000080000b86 in initlock (lk=lk@entry=0x80028758 <proc+20160>, name=name@entry=0x80009470 "proc") at kernel/spinlock.c:17
#3  0x0000000080002ece in procinit () at kernel/proc.c:55
#4  0x000000008000250c in main () at kernel/main.c:22
$1 = 64

3Spinlocks listed per process instead of per hart

A per-thread list, as Linux keeps: the running process’s list if there is one, otherwise (scheduler, boot) the hart’s:

+static struct ldheld pheld[NPROC][MAXHELD]; // per process
+static int npheld[NPROC];
+
+static struct ldheld *
+mylist(int **n)
+{
+  struct proc *p = mycpu()->proc;
+
+  if (p) {
+    *n = &npheld[p - proc];
+    return pheld[p - proc];
+  }
+  *n = &nheld[cpuid()];
+  return held[cpuid()];
+}
[... lockdep_acquire, lockdep_release and orderall use mylist() ...]
-    panic("lockdep: release of a lock this hart does not hold");
+    panic("lockdep: release of a lock this thread does not hold");

What happened when we ran it

xv6 kernel is booting

hart 2 starting
hart 1 starting
panic: lockdep: release of a lock this thread does not hold

(gdb from reset, at the panic:)
Thread 2 hit Breakpoint 1, panic (s=s@entry=0x80009250 "lockdep: release of a lock this thread does not hold") at kernel/printk.c:139
[...]
#0  panic (s=s@entry=0x80009250 "lockdep: release of a lock this thread does not hold") at kernel/printk.c:139
#1  0x0000000080001882 in lockdep_release (lk=lk@entry=0x8002a998 <proc>) at kernel/lockdep.c:445
#2  0x0000000080000cf6 in release (lk=lk@entry=0x8002a998 <proc>) at kernel/spinlock.c:69
#3  0x0000000080002ffc in forkret () at kernel/proc.c:520
#4  0x0000000080002fe8 in myproc () at kernel/proc.c:90
Backtrace stopped: frame did not save the PC
[...]
$4 = {1, 1, 1, 0, 0, 0, 0, 0}

4The report forgets that printk takes a lock

The busy flag is not set while the report prints. To have something to report, the copy also contains the kfork bug of the verify section (kfork takes wait_lock while holding the child’s p->lock):

     if (reach(c, h->cls)) {
-      busy[id] = 1; // printk() acquires pr.lock: don't check it
       report(h, c, pc);

What happened when we ran it

xv6 kernel is booting

hart 2 starting
hart 1 starting
init: starting sh
$

(nothing more, and `ls` typed at the prompt never ran; a second boot, gdb attached after
20 seconds:)
  Id   Target Id                    Frame
* 1    Thread 1.1 (CPU#0 [running]) 0x0000000080000dd4 in ldlk () at kernel/lockdep.c:53
  2    Thread 1.2 (CPU#1 [halted ]) s_sstatus (x=2) at kernel/riscv.h:67
  3    Thread 1.3 (CPU#2 [running]) 0x0000000080000dd4 in ldlk () at kernel/lockdep.c:53

Thread 3 (Thread 1.3 (CPU#2 [running])):
#0  0x0000000080000dd4 in ldlk () at kernel/lockdep.c:53
#1  0x0000000080000ffa in order (h=h@entry=0x800205e8 <held+896>, c=c@entry=8, pc=pc@entry=0x3fffffbe68) at kernel/lockdep.c:306
[...]
#5  0x0000000080003800 in killed (p=0x80023a00 <proc+360>) at kernel/proc.c:634
#6  0x00000000800001c8 in consoleread (user_dst=1, dst=20255, n=1) at kernel/console.c:100
[...]

Thread 1 (Thread 1.1 (CPU#0 [running])):
#0  0x0000000080000dd4 in ldlk () at kernel/lockdep.c:53
#1  0x0000000080000ffa in order (h=h@entry=0x80020268 <held>, c=c@entry=4, pc=pc@entry=0x3fffffdbf8) at kernel/lockdep.c:306
#2  0x000000008000144c in orderall (c=4, pc=pc@entry=0x3fffffdbf8) at kernel/lockdep.c:335
#3  0x00000000800017a0 in lockdep_acquire (lk=lk@entry=0x80011c88 <pr>, try=try@entry=0) at kernel/lockdep.c:399
#4  0x0000000080000c18 in acquire (lk=lk@entry=0x80011c88 <pr>) at kernel/spinlock.c:28
#5  0x000000008000057a in printk (fmt=fmt@entry=0x80009148 "lockdep: acquiring %s while holding %s may deadlock\n") at kernel/printk.c:71
#6  0x000000008000112a in report (h=0x80020268 <held>, c=8, pc=0x3fffffded8) at kernel/lockdep.c:261
#7  order (h=h@entry=0x80020268 <held>, c=c@entry=8, pc=pc@entry=0x3fffffded8) at kernel/lockdep.c:310
[...]
#11 0x00000000800038d6 in kwait (addr=0) at kernel/proc.c:381
$1 = 1
$2 = 1

5The sleep-lock hook does not turn interrupts off

lockdep_acquiresleep without its push_off/pop_off. Its callers run with interrupts on (a sleep-lock is taken in a system call), so the hook now uses the hart’s lists and may take ldlock with interrupts on:

-  push_off(); // stay on this hart while using its list
   p = mycpu()->proc;
   if (lockdep_on && !busy[cpuid()]) {
[...]
       push(&sheld[s][nsheld[s]++], lk, c, pc);
   }
-  pop_off();
 }

What happened when we ran it

$ echo hi > x
$ rm x
$ usertests -q
usertests starting
[...]
ALL TESTS PASSED

(a second boot, `usertests -q` twice: both ALL TESTS PASSED, no report, no panic)

6Not a bug: the iput cycle, reported as one

The reference with iput taking the lock with acquiresleep again, as in the original tree:

-    if (!tryacquiresleep(&ip->lock))
-      panic("iput: inode locked");
+    acquiresleep(&ip->lock);

What happened when we ran it

$ echo hi > x
$ rm x
lockdep: acquiring inode while holding itable may deadlock
hart 0, pid 4 (rm):
  holds itable at 0x80004aba 0x80004b8a 0x80006812 0x80003f9c 0x80003d22
  wants inode at 0x80005722 0x80004b00 0x80004b8a 0x80006812 0x80003f9c
but this order has been seen before:
hart 0, pid 1:
  holds inode at 0x80004924 0x800049c6 0x8000507a 0x800051be 0x80005f94
  wants itable at 0x80004478 0x80004f9a 0x8000509c 0x800051be 0x80005f94
panic: lockdep

(the addresses, each decoded at address - 2 with ${TOOLPREFIX}addr2line -f -i:)
holds itable:  iput fs.c:363, iunlockput fs.c:400, sys_unlink sysfile.c:246, syscall, usertrap
wants inode:   acquiresleep sleeplock.c:25, iput fs.c:377, iunlockput, sys_unlink, syscall
holds inode:   ilock_nested fs.c:314, ilock fs.c:300, namex fs.c:717, namei fs.c:749, kexec exec.c:42
wants itable:  iget fs.c:256, dirlookup fs.c:625, namex fs.c:731, namei, kexec

5. The reference solution

Take the guided tour through the reference solution, one commit at a time, with the machine state at every step:

Open the reveal tour →

Or read the commits

1d23964 Give every lock a lockdep class
Makefile
@@ -8,8 +8,9 @@ OBJS = \
88 $K/printk.o \
99 $K/uart.o \
1010 $K/kalloc.o \
1111 $K/spinlock.o \
12 $K/lockdep.o \
1213 $K/string.o \
1314 $K/main.o \
1415 $K/vm.o \
1516 $K/proc.o \
kernel/defs.h
@@ -60,8 +60,11 @@ void ireclaim(int);
6060void* kalloc(void);
6161void kfree(void *);
6262void kinit(void);
6363
64// lockdep.c
65int lockdep_class(char*, int);
66
6467// log.c
6568void initlog(int, struct superblock*);
6669void log_write(struct buf*);
6770void begin_op(void);
kernel/lockdep.c
@@ -0,0 +1,71 @@
1// Lockdep-lite: a run-time lock-order checker.
2//
3// Every lock belongs to a class: the name it was given in
4// initlock() or initsleeplock(). All 64 p->locks are one class,
5// "proc"; every pipe's lock is "pipe". The checker learns, while
6// the kernel runs, which classes are acquired while which others
7// are held, and complains about the first acquisition that would
8// make that order inconsistent, before any deadlock happens.
9
10#include "types.h"
11#include "param.h"
12#include "memlayout.h"
13#include "riscv.h"
14#include "spinlock.h"
15#include "sleeplock.h"
16#include "proc.h"
17#include "defs.h"
18
19#define MAXCLASS 64 // lock classes; class 0 means "none"
20
21struct ldclass {
22 char *name;
23 int sleep; // 1 for a sleep-lock class
24};
25
26static struct ldclass cls[MAXCLASS];
27static int nclass = 1;
28
29// The checker's own lock. It cannot be a struct spinlock:
30// acquire() calls the checker, which would call acquire()
31// again, forever. Callers must have interrupts off, so that
32// an interrupt handler on this hart cannot spin on it while
33// it is held underneath.
34static uint ldlock;
35
36static void
37ldlk(void)
38{
39 while (__atomic_exchange_n(&ldlock, 1, __ATOMIC_ACQUIRE) != 0)
40 ;
41}
42
43static void
44ldunlk(void)
45{
46 __atomic_store_n(&ldlock, 0, __ATOMIC_RELEASE);
47}
48
49// Return the class for locks named name (sleep: a sleep-lock),
50// making a new one the first time the name is seen.
51int
52lockdep_class(char *name, int sleep)
53{
54 int c;
55
56 push_off();
57 ldlk();
58 for (c = 1; c < nclass; c++)
59 if (cls[c].sleep == sleep && strncmp(cls[c].name, name, 32) == 0)
60 break;
61 if (c == nclass) {
62 if (nclass == MAXCLASS)
63 panic("lockdep: too many classes");
64 cls[c].name = name;
65 cls[c].sleep = sleep;
66 nclass++;
67 }
68 ldunlk();
69 pop_off();
70 return c;
71}
kernel/sleeplock.c
@@ -15,8 +15,9 @@ initsleeplock(struct sleeplock *lk, char *name)
1515 initlock(&lk->lk, "sleep lock");
1616 lk->name = name;
1717 lk->locked = 0;
1818 lk->pid = 0;
19 lk->cls = lockdep_class(name, 1);
1920}
2021
2122void
2223acquiresleep(struct sleeplock *lk)
kernel/sleeplock.h
@@ -1,7 +1,8 @@
11// Long-term locks for processes
22struct sleeplock {
33 uint locked; // Is the lock held?
4 int cls; // lockdep class (see lockdep.c)
45 struct spinlock lk; // spinlock protecting this sleep lock
56
67 // For debugging:
78 char *name; // Name of lock.
kernel/spinlock.c
@@ -13,8 +13,9 @@ initlock(struct spinlock *lk, char *name)
1313{
1414 lk->name = name;
1515 lk->locked = 0;
1616 lk->cpu = 0;
17 lk->cls = lockdep_class(name, 0);
1718}
1819
1920// Acquire the lock.
2021// Loops (spins) until the lock is acquired.
kernel/spinlock.h
@@ -1,7 +1,8 @@
11// Mutual exclusion lock.
22struct spinlock {
33 uint locked; // Is the lock held?
4 int cls; // lockdep class (see lockdep.c)
45
56 // For debugging:
67 char *name; // Name of lock.
78 struct cpu *cpu; // The cpu holding the lock.
6fd0385 Track the spinlocks each hart holds
kernel/defs.h
@@ -62,8 +62,10 @@ void kfree(void *);
6262void kinit(void);
6363
6464// lockdep.c
6565int lockdep_class(char*, int);
66void lockdep_acquire(struct spinlock*);
67void lockdep_release(struct spinlock*);
6668
6769// log.c
6870void initlog(int, struct superblock*);
6971void log_write(struct buf*);
kernel/lockdep.c
@@ -16,8 +16,10 @@
1616#include "proc.h"
1717#include "defs.h"
1818
1919#define MAXCLASS 64 // lock classes; class 0 means "none"
20#define MAXHELD 8 // spinlocks one hart can hold at once
21#define NTRACE 5 // return addresses kept per acquisition
2022
2123struct ldclass {
2224 char *name;
2325 int sleep; // 1 for a sleep-lock class
@@ -68,4 +70,77 @@ lockdep_class(char *name, int sleep)
6870 ldunlk();
6971 pop_off();
7072 return c;
7173}
74
75// One acquisition: which lock, its class, and where it happened.
76struct ldheld {
77 void *lk;
78 int cls;
79 uint64 pc[NTRACE];
80};
81
82// The spinlocks each hart holds, oldest first. Per hart, not per
83// process: the scheduler acquires a p->lock and the process it
84// switches to releases it, on the same hart.
85static struct ldheld held[NCPU][MAXHELD];
86static int nheld[NCPU];
87
88int lockdep_on = 1;
89
90// Fill pc[] with return addresses: the caller of acquire() and
91// the callers above it. fp is the checker's own frame pointer
92// (s0). In each frame, ra is saved at fp-8 and the caller's fp at
93// fp-16. Stop at the edge of the stack page.
94static void
95trace(uint64 fp, uint64 *pc)
96{
97 uint64 lo = PGROUNDDOWN(fp), hi = lo + PGSIZE;
98 int i = 0;
99
100 fp = *(uint64 *)(fp - 16); // the frame of acquire() itself
101 while (i < NTRACE && fp >= lo + 16 && fp <= hi) {
102 pc[i++] = *(uint64 *)(fp - 8);
103 fp = *(uint64 *)(fp - 16);
104 }
105 while (i < NTRACE)
106 pc[i++] = 0;
107}
108
109// Called by acquire() before it spins, with interrupts off.
110void
111lockdep_acquire(struct spinlock *lk)
112{
113 int id = cpuid();
114 struct ldheld *h;
115
116 if (!lockdep_on)
117 return;
118 if (lk->cls == 0)
119 panic("lockdep: lock without a class");
120 if (nheld[id] == MAXHELD)
121 panic("lockdep: too many locks held");
122 h = &held[id][nheld[id]++];
123 h->lk = lk;
124 h->cls = lk->cls;
125 trace((uint64)__builtin_frame_address(0), h->pc);
126}
127
128// Called by release(), with interrupts off. The lock was acquired
129// on this hart (holding() checked that), but maybe by another
130// thread: p->lock crosses swtch(). So search, don't just pop.
131void
132lockdep_release(struct spinlock *lk)
133{
134 int id = cpuid(), i;
135
136 if (!lockdep_on)
137 return;
138 for (i = nheld[id] - 1; i >= 0; i--)
139 if (held[id][i].lk == lk)
140 break;
141 if (i < 0)
142 panic("lockdep: release of a lock this hart does not hold");
143 for (; i + 1 < nheld[id]; i++)
144 held[id][i] = held[id][i + 1];
145 nheld[id]--;
146}
kernel/spinlock.c
@@ -24,8 +24,9 @@ acquire(struct spinlock *lk)
2424{
2525 push_off(); // disable interrupts to avoid deadlock.
2626 if (holding(lk))
2727 panic("acquire");
28 lockdep_acquire(lk); // check the order before waiting
2829
2930 // On RISC-V, __atomic_exchange_n turns into an atomic swap:
3031 // a5 = 1
3132 // s1 = &lk->locked
@@ -47,8 +48,9 @@ void
4748release(struct spinlock *lk)
4849{
4950 if (!holding(lk))
5051 panic("release");
52 lockdep_release(lk);
5153
5254 lk->cpu = 0;
5355
5456 // Release the lock, equivalent to lk->locked = 0.
e7932b6 Record the lock order between classes
kernel/defs.h
@@ -64,8 +64,9 @@ void kinit(void);
6464// lockdep.c
6565int lockdep_class(char*, int);
6666void lockdep_acquire(struct spinlock*);
6767void lockdep_release(struct spinlock*);
68void lockdep_print(void);
6869
6970// log.c
7071void initlog(int, struct superblock*);
7172void log_write(struct buf*);
kernel/lockdep.c
@@ -18,8 +18,9 @@
1818
1919#define MAXCLASS 64 // lock classes; class 0 means "none"
2020#define MAXHELD 8 // spinlocks one hart can hold at once
2121#define NTRACE 5 // return addresses kept per acquisition
22#define MAXEDGE 256
2223
2324struct ldclass {
2425 char *name;
2526 int sleep; // 1 for a sleep-lock class
@@ -64,9 +65,9 @@ lockdep_class(char *name, int sleep)
6465 if (nclass == MAXCLASS)
6566 panic("lockdep: too many classes");
6667 cls[c].name = name;
6768 cls[c].sleep = sleep;
68 nclass++;
69 __atomic_store_n(&nclass, c + 1, __ATOMIC_RELEASE); // for lockdep_print
6970 }
7071 ldunlk();
7172 pop_off();
7273 return c;
@@ -105,25 +106,75 @@ trace(uint64 fp, uint64 *pc)
105106 while (i < NTRACE)
106107 pc[i++] = 0;
107108}
108109
110// An edge a -> b: a lock of class b was acquired while a lock
111// of class a was held. Kept with where both were acquired.
112struct ldedge {
113 int a, b;
114 int hart, pid; // who did it first
115 uint64 apc[NTRACE]; // where the held lock was acquired
116 uint64 bpc[NTRACE]; // where the new one was
117};
118
119static uint64 after[MAXCLASS]; // bit b of after[a]: edge a -> b
120static struct ldedge edges[MAXEDGE];
121static int nedges;
122
123// Record the edge h's class -> c. Caller holds ldlock.
124static void
125newedge(struct ldheld *h, int c, uint64 *pc)
126{
127 struct proc *p = mycpu()->proc;
128 struct ldedge *e;
129
130 if (nedges == MAXEDGE)
131 panic("lockdep: too many edges");
132 e = &edges[nedges++];
133 e->a = h->cls;
134 e->b = c;
135 e->hart = cpuid();
136 e->pid = p ? p->pid : 0;
137 memmove(e->apc, h->pc, sizeof(e->apc));
138 memmove(e->bpc, pc, sizeof(e->bpc));
139 __atomic_or_fetch(&after[h->cls], 1UL << c, __ATOMIC_RELEASE);
140}
141
142// Learn that class c is acquired while h is held. Edges are only
143// ever added, so a bit seen set without the lock can be trusted:
144// the common case costs one load and no lock.
145static void
146order(struct ldheld *h, int c, uint64 *pc)
147{
148 if (__atomic_load_n(&after[h->cls], __ATOMIC_RELAXED) & (1UL << c))
149 return;
150 ldlk();
151 if ((after[h->cls] & (1UL << c)) == 0)
152 newedge(h, c, pc);
153 ldunlk();
154}
155
109156// Called by acquire() before it spins, with interrupts off.
110157void
111158lockdep_acquire(struct spinlock *lk)
112159{
113 int id = cpuid();
160 int id = cpuid(), i;
161 uint64 pc[NTRACE];
114162 struct ldheld *h;
115163
116164 if (!lockdep_on)
117165 return;
118166 if (lk->cls == 0)
119167 panic("lockdep: lock without a class");
168 trace((uint64)__builtin_frame_address(0), pc);
169 for (i = 0; i < nheld[id]; i++)
170 order(&held[id][i], lk->cls, pc);
120171 if (nheld[id] == MAXHELD)
121172 panic("lockdep: too many locks held");
122173 h = &held[id][nheld[id]++];
123174 h->lk = lk;
124175 h->cls = lk->cls;
125 trace((uint64)__builtin_frame_address(0), h->pc);
176 memmove(h->pc, pc, sizeof(h->pc));
126177}
127178
128179// Called by release(), with interrupts off. The lock was acquired
129180// on this hart (holding() checked that), but maybe by another
@@ -143,4 +194,25 @@ lockdep_release(struct spinlock *lk)
143194 for (; i + 1 < nheld[id]; i++)
144195 held[id][i] = held[id][i + 1];
145196 nheld[id]--;
146197}
198
199// Print the order learned so far (Ctrl-P). Without ldlock:
200// printk() acquires pr.lock, and the checker may need ldlock for
201// that. Classes and edges are only ever added.
202void
203lockdep_print(void)
204{
205 int a, b, n = __atomic_load_n(&nclass, __ATOMIC_ACQUIRE);
206 uint64 m;
207
208 for (a = 1; a < n; a++) {
209 m = __atomic_load_n(&after[a], __ATOMIC_ACQUIRE);
210 if (m == 0)
211 continue;
212 printk("lockdep: %s ->", cls[a].name);
213 for (b = 1; b < n; b++)
214 if (m & (1UL << b))
215 printk(" %s", cls[b].name);
216 printk("\n");
217 }
218}
kernel/proc.c
@@ -699,5 +699,6 @@ procdump(void)
699699 state = "???";
700700 printk("%d %s %s", p->pid, state, p->name);
701701 printk("\n");
702702 }
703 lockdep_print();
703704}
b3c7bd6 Report the first acquisition that closes a cycle
kernel/lockdep.c
@@ -86,8 +86,9 @@ struct ldheld {
8686static struct ldheld held[NCPU][MAXHELD];
8787static int nheld[NCPU];
8888
8989int lockdep_on = 1;
90static int busy[NCPU]; // this hart is printing a report
9091
9192// Fill pc[] with return addresses: the caller of acquire() and
9293// the callers above it. fp is the checker's own frame pointer
9394// (s0). In each frame, ra is saved at fp-8 and the caller's fp at
@@ -111,8 +112,9 @@ trace(uint64 fp, uint64 *pc)
111112// of class a was held. Kept with where both were acquired.
112113struct ldedge {
113114 int a, b;
114115 int hart, pid; // who did it first
116 char name[16]; // and the process's name
115117 uint64 apc[NTRACE]; // where the held lock was acquired
116118 uint64 bpc[NTRACE]; // where the new one was
117119};
118120
@@ -133,24 +135,117 @@ newedge(struct ldheld *h, int c, uint64 *pc)
133135 e->a = h->cls;
134136 e->b = c;
135137 e->hart = cpuid();
136138 e->pid = p ? p->pid : 0;
139 safestrcpy(e->name, p ? p->name : "", sizeof(e->name));
137140 memmove(e->apc, h->pc, sizeof(e->apc));
138141 memmove(e->bpc, pc, sizeof(e->bpc));
139142 __atomic_or_fetch(&after[h->cls], 1UL << c, __ATOMIC_RELEASE);
140143}
141144
145// Is there a path of edges from class a to class b? Depth-first
146// search; on success prev[] holds the path, backwards from b.
147// Caller holds ldlock.
148static int prev[MAXCLASS];
149
150static int
151reach(int a, int b)
152{
153 int stack[MAXCLASS], n = 0, x, y;
154 uint64 seen = 1UL << a;
155
156 if (a == b)
157 return 1;
158 stack[n++] = a;
159 while (n > 0) {
160 x = stack[--n];
161 for (y = 1; y < nclass; y++) {
162 if ((after[x] & (1UL << y)) == 0 || (seen & (1UL << y)) != 0)
163 continue;
164 seen |= 1UL << y;
165 prev[y] = x;
166 if (y == b)
167 return 1;
168 stack[n++] = y;
169 }
170 }
171 return 0;
172}
173
174static void
175who(int hart, int pid, char *name)
176{
177 if (pid == 0)
178 printk("hart %d, no process:\n", hart);
179 else if (name[0] == 0)
180 printk("hart %d, pid %d:\n", hart, pid);
181 else
182 printk("hart %d, pid %d (%s):\n", hart, pid, name);
183}
184
185static void
186where(char *what, int c, uint64 *pc)
187{
188 printk(" %s %s at", what, cls[c].name);
189 for (int i = 0; i < NTRACE && pc[i]; i++)
190 printk(" 0x%lx", pc[i]);
191 printk("\n");
192}
193
194// Acquiring class c while holding h would close a cycle: the path
195// in prev[] already leads from c to h's class. Print both orders.
196static void
197report(struct ldheld *h, int c, uint64 *pc)
198{
199 struct proc *p = mycpu()->proc;
200 int path[MAXCLASS], n = 0, i, k;
201 struct ldedge *e;
202
203 for (k = h->cls; k != c; k = prev[k])
204 path[n++] = k;
205 path[n++] = c; // path[n-1] -> ... -> path[0] is c -> ... -> h's class
206
207 printk("lockdep: acquiring %s while holding %s may deadlock\n",
208 cls[c].name, cls[h->cls].name);
209 who(cpuid(), p ? p->pid : 0, p ? p->name : "");
210 where("holds", h->cls, h->pc);
211 where("wants", c, pc);
212 if (n == 1)
213 printk("both locks are of class %s\n", cls[c].name);
214 else
215 printk("but this order has been seen before:\n");
216 for (i = n - 1; i > 0; i--) {
217 for (e = edges; e->a != path[i] || e->b != path[i - 1]; e++)
218 ;
219 who(e->hart, e->pid, e->name);
220 where("holds", e->a, e->apc);
221 where("wants", e->b, e->bpc);
222 }
223}
224
142225// Learn that class c is acquired while h is held. Edges are only
143226// ever added, so a bit seen set without the lock can be trusted:
144// the common case costs one load and no lock.
227// the common case costs one load and no lock. A new edge is
228// checked for a cycle before it is added.
145229static void
146230order(struct ldheld *h, int c, uint64 *pc)
147231{
232 int id = cpuid();
233
148234 if (__atomic_load_n(&after[h->cls], __ATOMIC_RELAXED) & (1UL << c))
149235 return;
150236 ldlk();
151 if ((after[h->cls] & (1UL << c)) == 0)
152 newedge(h, c, pc);
237 if ((after[h->cls] & (1UL << c)) == 0) {
238 if (reach(c, h->cls)) {
239 busy[id] = 1; // printk() acquires pr.lock: don't check it
240 report(h, c, pc);
241 printk("lockdep: turning off the checker\n");
242 lockdep_on = 0;
243 busy[id] = 0;
244 } else {
245 newedge(h, c, pc);
246 }
247 }
153248 ldunlk();
154249}
155250
156251// Called by acquire() before it spins, with interrupts off.
@@ -160,15 +255,17 @@ lockdep_acquire(struct spinlock *lk)
160255 int id = cpuid(), i;
161256 uint64 pc[NTRACE];
162257 struct ldheld *h;
163258
164 if (!lockdep_on)
259 if (!lockdep_on || busy[id])
165260 return;
166261 if (lk->cls == 0)
167262 panic("lockdep: lock without a class");
168263 trace((uint64)__builtin_frame_address(0), pc);
169 for (i = 0; i < nheld[id]; i++)
264 for (i = 0; i < nheld[id] && lockdep_on; i++)
170265 order(&held[id][i], lk->cls, pc);
266 if (!lockdep_on)
267 return;
171268 if (nheld[id] == MAXHELD)
172269 panic("lockdep: too many locks held");
173270 h = &held[id][nheld[id]++];
174271 h->lk = lk;
@@ -183,9 +280,9 @@ void
183280lockdep_release(struct spinlock *lk)
184281{
185282 int id = cpuid(), i;
186283
187 if (!lockdep_on)
284 if (!lockdep_on || busy[id])
188285 return;
189286 for (i = nheld[id] - 1; i >= 0; i--)
190287 if (held[id][i].lk == lk)
191288 break;
2192c24 Track sleep-locks per process
kernel/defs.h
@@ -65,8 +65,10 @@ void kinit(void);
6565int lockdep_class(char*, int);
6666void lockdep_acquire(struct spinlock*);
6767void lockdep_release(struct spinlock*);
6868void lockdep_print(void);
69void lockdep_acquiresleep(struct sleeplock*);
70void lockdep_releasesleep(struct sleeplock*);
6971
7072// log.c
7173void initlog(int, struct superblock*);
7274void log_write(struct buf*);
kernel/lockdep.c
@@ -17,8 +17,9 @@
1717#include "defs.h"
1818
1919#define MAXCLASS 64 // lock classes; class 0 means "none"
2020#define MAXHELD 8 // spinlocks one hart can hold at once
21#define MAXSLEEP 8 // sleep-locks one process can hold at once
2122#define NTRACE 5 // return addresses kept per acquisition
2223#define MAXEDGE 256
2324
2425struct ldclass {
@@ -85,8 +86,15 @@ struct ldheld {
8586// switches to releases it, on the same hart.
8687static struct ldheld held[NCPU][MAXHELD];
8788static int nheld[NCPU];
8889
90// The sleep-locks each process holds, by proc[] slot. A process
91// can sleep holding them and wake up on another hart, so they
92// belong to the process. Only the process changes its own list.
93static struct ldheld sheld[NPROC][MAXSLEEP];
94static int nsheld[NPROC];
95extern struct proc proc[NPROC];
96
8997int lockdep_on = 1;
9098static int busy[NCPU]; // this hart is printing a report
9199
92100// Fill pc[] with return addresses: the caller of acquire() and
@@ -247,31 +255,51 @@ order(struct ldheld *h, int c, uint64 *pc)
247255 }
248256 ldunlk();
249257}
250258
259// Order class c after every lock this hart holds and, if a
260// process is running, every sleep-lock it holds.
261static void
262orderall(int c, uint64 *pc)
263{
264 int id = cpuid(), i, s;
265 struct proc *p = mycpu()->proc;
266
267 for (i = 0; i < nheld[id] && lockdep_on; i++)
268 order(&held[id][i], c, pc);
269 if (p) {
270 s = p - proc;
271 for (i = 0; i < nsheld[s] && lockdep_on; i++)
272 order(&sheld[s][i], c, pc);
273 }
274}
275
276static void
277push(struct ldheld *h, void *lk, int c, uint64 *pc)
278{
279 h->lk = lk;
280 h->cls = c;
281 memmove(h->pc, pc, sizeof(h->pc));
282}
283
251284// Called by acquire() before it spins, with interrupts off.
252285void
253286lockdep_acquire(struct spinlock *lk)
254287{
255 int id = cpuid(), i;
288 int id = cpuid();
256289 uint64 pc[NTRACE];
257 struct ldheld *h;
258290
259291 if (!lockdep_on || busy[id])
260292 return;
261293 if (lk->cls == 0)
262294 panic("lockdep: lock without a class");
263295 trace((uint64)__builtin_frame_address(0), pc);
264 for (i = 0; i < nheld[id] && lockdep_on; i++)
265 order(&held[id][i], lk->cls, pc);
296 orderall(lk->cls, pc);
266297 if (!lockdep_on)
267298 return;
268299 if (nheld[id] == MAXHELD)
269300 panic("lockdep: too many locks held");
270 h = &held[id][nheld[id]++];
271 h->lk = lk;
272 h->cls = lk->cls;
273 memmove(h->pc, pc, sizeof(h->pc));
301 push(&held[id][nheld[id]++], lk, lk->cls, pc);
274302}
275303
276304// Called by release(), with interrupts off. The lock was acquired
277305// on this hart (holding() checked that), but maybe by another
@@ -292,8 +320,58 @@ lockdep_release(struct spinlock *lk)
292320 held[id][i] = held[id][i + 1];
293321 nheld[id]--;
294322}
295323
324// Called by acquiresleep() before it waits.
325void
326lockdep_acquiresleep(struct sleeplock *lk)
327{
328 uint64 pc[NTRACE];
329 struct proc *p;
330 int s;
331
332 push_off(); // stay on this hart while using its list
333 p = mycpu()->proc;
334 if (lockdep_on && !busy[cpuid()]) {
335 if (lk->cls == 0 || p == 0)
336 panic("lockdep: acquiresleep");
337 trace((uint64)__builtin_frame_address(0), pc);
338 orderall(lk->cls, pc);
339 s = p - proc;
340 if (nsheld[s] == MAXSLEEP)
341 panic("lockdep: too many sleep-locks held");
342 if (lockdep_on)
343 push(&sheld[s][nsheld[s]++], lk, lk->cls, pc);
344 }
345 pop_off();
346}
347
348// Called by releasesleep(). Sleep-locks are released by the
349// process that holds them, whatever hart it is on now.
350void
351lockdep_releasesleep(struct sleeplock *lk)
352{
353 struct proc *p;
354 int s, i;
355
356 push_off();
357 p = mycpu()->proc;
358 if (lockdep_on && !busy[cpuid()]) {
359 if (p == 0)
360 panic("lockdep: releasesleep");
361 s = p - proc;
362 for (i = nsheld[s] - 1; i >= 0; i--)
363 if (sheld[s][i].lk == lk)
364 break;
365 if (i < 0)
366 panic("lockdep: release of a sleep-lock this process does not hold");
367 for (; i + 1 < nsheld[s]; i++)
368 sheld[s][i] = sheld[s][i + 1];
369 nsheld[s]--;
370 }
371 pop_off();
372}
373
296374// Print the order learned so far (Ctrl-P). Without ldlock:
297375// printk() acquires pr.lock, and the checker may need ldlock for
298376// that. Classes and edges are only ever added.
299377void
kernel/sleeplock.c
@@ -21,8 +21,9 @@ initsleeplock(struct sleeplock *lk, char *name)
2121
2222void
2323acquiresleep(struct sleeplock *lk)
2424{
25 lockdep_acquiresleep(lk); // check the order before waiting
2526 acquire(&lk->lk);
2627 while (lk->locked) {
2728 sleep_prepare(lk);
2829 release(&lk->lk);
@@ -36,8 +37,9 @@ acquiresleep(struct sleeplock *lk)
3637
3738void
3839releasesleep(struct sleeplock *lk)
3940{
41 lockdep_releasesleep(lk);
4042 acquire(&lk->lk);
4143 lk->locked = 0;
4244 lk->pid = 0;
4345 wakeup(lk);
1d0aee7 Know when a hart is running an interrupt handler
kernel/defs.h
@@ -67,8 +67,10 @@ void lockdep_acquire(struct spinlock*);
6767void lockdep_release(struct spinlock*);
6868void lockdep_print(void);
6969void lockdep_acquiresleep(struct sleeplock*);
7070void lockdep_releasesleep(struct sleeplock*);
71void lockdep_irq_enter(void);
72void lockdep_irq_exit(void);
7173
7274// log.c
7375void initlog(int, struct superblock*);
7476void log_write(struct buf*);
kernel/lockdep.c
@@ -21,11 +21,16 @@
2121#define MAXSLEEP 8 // sleep-locks one process can hold at once
2222#define NTRACE 5 // return addresses kept per acquisition
2323#define MAXEDGE 256
2424
25#define USE_IRQ 1 // taken in an interrupt handler
26#define USE_IRQON 2 // held with interrupts on
27
2528struct ldclass {
2629 char *name;
27 int sleep; // 1 for a sleep-lock class
30 int sleep; // 1 for a sleep-lock class
31 int use; // USE_IRQ, USE_IRQON
32 uint64 usepc[2][NTRACE]; // where each use was first seen
2833};
2934
3035static struct ldclass cls[MAXCLASS];
3136static int nclass = 1;
@@ -94,9 +99,10 @@ static struct ldheld sheld[NPROC][MAXSLEEP];
9499static int nsheld[NPROC];
95100extern struct proc proc[NPROC];
96101
97102int lockdep_on = 1;
98static int busy[NCPU]; // this hart is printing a report
103static int busy[NCPU]; // this hart is printing a report
104static int inirq[NCPU]; // this hart is running an interrupt handler
99105
100106// Fill pc[] with return addresses: the caller of acquire() and
101107// the callers above it. fp is the checker's own frame pointer
102108// (s0). In each frame, ra is saved at fp-8 and the caller's fp at
@@ -256,24 +262,55 @@ order(struct ldheld *h, int c, uint64 *pc)
256262 ldunlk();
257263}
258264
259265// Order class c after every lock this hart holds and, if a
260// process is running, every sleep-lock it holds.
266// process is running, every sleep-lock it holds. Not in an
267// interrupt handler: it runs on top of whatever process it
268// interrupted, but does not act for it.
261269static void
262270orderall(int c, uint64 *pc)
263271{
264272 int id = cpuid(), i, s;
265273 struct proc *p = mycpu()->proc;
266274
267275 for (i = 0; i < nheld[id] && lockdep_on; i++)
268276 order(&held[id][i], c, pc);
269 if (p) {
277 if (p && inirq[id] == 0) {
270278 s = p - proc;
271279 for (i = 0; i < nsheld[s] && lockdep_on; i++)
272280 order(&sheld[s][i], c, pc);
273281 }
274282}
275283
284// Class c is used in a way how. A lock that is taken in an
285// interrupt handler (USE_IRQ) must never be held with interrupts
286// on (USE_IRQON): the handler could interrupt the holder on its
287// own hart and spin forever on the lock underneath it.
288static void
289use(int c, int how, uint64 *pc)
290{
291 int id = cpuid();
292
293 if (cls[c].use & how)
294 return;
295 ldlk();
296 if ((cls[c].use & how) == 0) {
297 cls[c].use |= how;
298 memmove(cls[c].usepc[how - 1], pc, sizeof(cls[c].usepc[0]));
299 if (cls[c].use == (USE_IRQ | USE_IRQON)) {
300 busy[id] = 1;
301 printk("lockdep: %s is taken in interrupt handlers and held "
302 "with interrupts on\n", cls[c].name);
303 where("in a handler:", c, cls[c].usepc[USE_IRQ - 1]);
304 where("interrupts on:", c, cls[c].usepc[USE_IRQON - 1]);
305 printk("lockdep: turning off the checker\n");
306 lockdep_on = 0;
307 busy[id] = 0;
308 }
309 }
310 ldunlk();
311}
312
276313static void
277314push(struct ldheld *h, void *lk, int c, uint64 *pc)
278315{
279316 h->lk = lk;
@@ -292,8 +329,12 @@ lockdep_acquire(struct spinlock *lk)
292329 return;
293330 if (lk->cls == 0)
294331 panic("lockdep: lock without a class");
295332 trace((uint64)__builtin_frame_address(0), pc);
333 if (inirq[id])
334 use(lk->cls, USE_IRQ, pc);
335 if (intr_get()) // never: acquire() turned them off first
336 use(lk->cls, USE_IRQON, pc);
296337 orderall(lk->cls, pc);
297338 if (!lockdep_on)
298339 return;
299340 if (nheld[id] == MAXHELD)
@@ -334,8 +375,10 @@ lockdep_acquiresleep(struct sleeplock *lk)
334375 if (lockdep_on && !busy[cpuid()]) {
335376 if (lk->cls == 0 || p == 0)
336377 panic("lockdep: acquiresleep");
337378 trace((uint64)__builtin_frame_address(0), pc);
379 // a sleep-lock's holder runs with interrupts on, and sleeps
380 use(lk->cls, inirq[cpuid()] ? USE_IRQ : USE_IRQON, pc);
338381 orderall(lk->cls, pc);
339382 s = p - proc;
340383 if (nsheld[s] == MAXSLEEP)
341384 panic("lockdep: too many sleep-locks held");
@@ -370,8 +413,22 @@ lockdep_releasesleep(struct sleeplock *lk)
370413 }
371414 pop_off();
372415}
373416
417// devintr() calls these around each interrupt handler, with
418// interrupts off.
419void
420lockdep_irq_enter(void)
421{
422 inirq[cpuid()]++;
423}
424
425void
426lockdep_irq_exit(void)
427{
428 inirq[cpuid()]--;
429}
430
374431// Print the order learned so far (Ctrl-P). Without ldlock:
375432// printk() acquires pr.lock, and the checker may need ldlock for
376433// that. Classes and edges are only ever added.
377434void
kernel/trap.c
@@ -194,15 +194,17 @@ devintr()
194194
195195 // irq indicates which device interrupted.
196196 int irq = plic_claim();
197197
198 lockdep_irq_enter();
198199 if (irq == UART0_IRQ) {
199200 uartintr();
200201 } else if (irq == VIRTIO0_IRQ) {
201202 virtio_disk_intr();
202203 } else if (irq) {
203204 printk("unexpected interrupt irq=%d\n", irq);
204205 }
206 lockdep_irq_exit();
205207
206208 // the PLIC allows each device to raise at most one
207209 // interrupt at a time; tell the PLIC the device is
208210 // now allowed to interrupt again.
@@ -211,9 +213,11 @@ devintr()
211213
212214 return 1;
213215 } else if (scause == 0x8000000000000005L) {
214216 // timer interrupt.
217 lockdep_irq_enter();
215218 clockintr();
219 lockdep_irq_exit();
216220 return 2;
217221 } else {
218222 return 0;
219223 }
43a3a1f Let inodes nest inside their own class, by role
kernel/defs.h
@@ -42,8 +42,9 @@ struct inode* dirlookup(struct inode*, char*, uint*);
4242struct inode* ialloc(uint, short);
4343struct inode* idup(struct inode*);
4444void iinit();
4545void ilock(struct inode*);
46void ilock_nested(struct inode*, int);
4647void iput(struct inode*);
4748void iunlock(struct inode*);
4849void iunlockput(struct inode*);
4950void iupdate(struct inode*);
@@ -65,9 +66,9 @@ void kinit(void);
6566int lockdep_class(char*, int);
6667void lockdep_acquire(struct spinlock*);
6768void lockdep_release(struct spinlock*);
6869void lockdep_print(void);
69void lockdep_acquiresleep(struct sleeplock*);
70void lockdep_acquiresleep(struct sleeplock*, int);
7071void lockdep_releasesleep(struct sleeplock*);
7172void lockdep_irq_enter(void);
7273void lockdep_irq_exit(void);
7374
@@ -126,8 +127,9 @@ void push_off(void);
126127void pop_off(void);
127128
128129// sleeplock.c
129130void acquiresleep(struct sleeplock*);
131void acquiresleep_nested(struct sleeplock*, int);
130132void releasesleep(struct sleeplock*);
131133int holdingsleep(struct sleeplock*);
132134void initsleeplock(struct sleeplock*, char*);
133135
kernel/fs.c
@@ -292,16 +292,24 @@ idup(struct inode *ip)
292292// Lock the given inode.
293293// Reads the inode from disk if necessary.
294294void
295295ilock(struct inode *ip)
296{
297 ilock_nested(ip, 0);
298}
299
300// Lock ip in role sub (see acquiresleep_nested), for an inode
301// locked while another inode is locked.
302void
303ilock_nested(struct inode *ip, int sub)
296304{
297305 struct buf *bp;
298306 struct dinode *dip;
299307
300308 if (ip == 0 || ip->ref < 1)
301309 panic("ilock");
302310
303 acquiresleep(&ip->lock);
311 acquiresleep_nested(&ip->lock, sub);
304312
305313 if (ip->valid == 0) {
306314 bp = bread(ip->dev, IBLOCK(ip->inum, sb));
307315 dip = (struct dinode *)bp->data + ip->inum % IPB;
kernel/lockdep.c
@@ -19,8 +19,9 @@
1919#define MAXCLASS 64 // lock classes; class 0 means "none"
2020#define MAXHELD 8 // spinlocks one hart can hold at once
2121#define MAXSLEEP 8 // sleep-locks one process can hold at once
2222#define NTRACE 5 // return addresses kept per acquisition
23#define NSUB 4 // subclasses per class (acquiresleep_nested)
2324#define MAXEDGE 256
2425
2526#define USE_IRQ 1 // taken in an interrupt handler
2627#define USE_IRQON 2 // held with interrupts on
@@ -29,8 +30,10 @@ struct ldclass {
2930 char *name;
3031 int sleep; // 1 for a sleep-lock class
3132 int use; // USE_IRQ, USE_IRQON
3233 uint64 usepc[2][NTRACE]; // where each use was first seen
34 int sub[NSUB]; // the class of each subclass, if made
35 char subname[24]; // "inode/1", for a subclass
3336};
3437
3538static struct ldclass cls[MAXCLASS];
3639static int nclass = 1;
@@ -78,8 +81,39 @@ lockdep_class(char *name, int sleep)
7881 pop_off();
7982 return c;
8083}
8184
85// Return the class for role sub of class c (sub 0 is c itself):
86// a class of its own, so that the order between roles can be
87// learned and checked like any other order.
88static int
89subclass(int c, int sub)
90{
91 int s, n;
92
93 if (sub == 0)
94 return c;
95 if (sub < 0 || sub >= NSUB)
96 panic("lockdep: bad subclass");
97 if ((s = __atomic_load_n(&cls[c].sub[sub], __ATOMIC_ACQUIRE)) != 0)
98 return s;
99 ldlk();
100 if ((s = cls[c].sub[sub]) == 0) {
101 if (nclass == MAXCLASS)
102 panic("lockdep: too many classes");
103 s = nclass;
104 n = strlen(safestrcpy(cls[s].subname, cls[c].name, 20));
105 cls[s].subname[n] = '/';
106 cls[s].subname[n + 1] = '0' + sub;
107 cls[s].name = cls[s].subname;
108 cls[s].sleep = cls[c].sleep;
109 __atomic_store_n(&nclass, s + 1, __ATOMIC_RELEASE);
110 __atomic_store_n(&cls[c].sub[sub], s, __ATOMIC_RELEASE);
111 }
112 ldunlk();
113 return s;
114}
115
82116// One acquisition: which lock, its class, and where it happened.
83117struct ldheld {
84118 void *lk;
85119 int cls;
@@ -361,30 +395,31 @@ lockdep_release(struct spinlock *lk)
361395 held[id][i] = held[id][i + 1];
362396 nheld[id]--;
363397}
364398
365// Called by acquiresleep() before it waits.
399// Called by acquiresleep_nested() before it waits.
366400void
367lockdep_acquiresleep(struct sleeplock *lk)
401lockdep_acquiresleep(struct sleeplock *lk, int sub)
368402{
369403 uint64 pc[NTRACE];
370404 struct proc *p;
371 int s;
405 int s, c;
372406
373407 push_off(); // stay on this hart while using its list
374408 p = mycpu()->proc;
375409 if (lockdep_on && !busy[cpuid()]) {
376410 if (lk->cls == 0 || p == 0)
377411 panic("lockdep: acquiresleep");
412 c = subclass(lk->cls, sub);
378413 trace((uint64)__builtin_frame_address(0), pc);
379414 // a sleep-lock's holder runs with interrupts on, and sleeps
380 use(lk->cls, inirq[cpuid()] ? USE_IRQ : USE_IRQON, pc);
381 orderall(lk->cls, pc);
415 use(c, inirq[cpuid()] ? USE_IRQ : USE_IRQON, pc);
416 orderall(c, pc);
382417 s = p - proc;
383418 if (nsheld[s] == MAXSLEEP)
384419 panic("lockdep: too many sleep-locks held");
385420 if (lockdep_on)
386 push(&sheld[s][nsheld[s]++], lk, lk->cls, pc);
421 push(&sheld[s][nsheld[s]++], lk, c, pc);
387422 }
388423 pop_off();
389424}
390425
kernel/sleeplock.c
@@ -21,9 +21,19 @@ initsleeplock(struct sleeplock *lk, char *name)
2121
2222void
2323acquiresleep(struct sleeplock *lk)
2424{
25 lockdep_acquiresleep(lk); // check the order before waiting
25 acquiresleep_nested(lk, 0);
26}
27
28// Acquire lk, maybe while holding another lock of its class.
29// sub names lk's role there (see sleeplock.h). The checker gives
30// each role a class of its own, so "a directory, then a file in
31// it" is an order it can check, not inode nested in inode.
32void
33acquiresleep_nested(struct sleeplock *lk, int sub)
34{
35 lockdep_acquiresleep(lk, sub); // check the order before waiting
2636 acquire(&lk->lk);
2737 while (lk->locked) {
2838 sleep_prepare(lk);
2939 release(&lk->lk);
kernel/sleeplock.h
@@ -7,4 +7,8 @@ struct sleeplock {
77 // For debugging:
88 char *name; // Name of lock.
99 int pid; // Process holding lock
1010};
11
12// Roles for acquiresleep_nested(): a sleep-lock taken while
13// another lock of its class is held. Role 0 is the default.
14#define SUB_CHILD 1 // an inode, while its directory is locked
kernel/sysfile.c
@@ -222,9 +222,9 @@ sys_unlink(void)
222222 goto bad;
223223
224224 if ((ip = dirlookup(dp, name, &off)) == 0)
225225 goto bad;
226 ilock(ip);
226 ilock_nested(ip, SUB_CHILD);
227227
228228 if (ip->nlink < 1)
229229 panic("unlink: nlink < 1");
230230 if (ip->type == T_DIR && !isdirempty(ip)) {
@@ -290,9 +290,9 @@ create(char *path, short type, short major, short minor)
290290 iunlockput(dp);
291291 return 0;
292292 }
293293
294 ilock(ip);
294 ilock_nested(ip, SUB_CHILD);
295295 ip->major = major;
296296 ip->minor = minor;
297297 ip->nlink = 1;
298298 iupdate(ip);
32208af Give nested buffers a role too
kernel/bio.c
@@ -54,9 +54,9 @@ binit(void)
5454// Look through buffer cache for block on device dev.
5555// If not found, allocate a buffer.
5656// In either case, return locked buffer.
5757static struct buf *
58bget(uint dev, uint blockno)
58bget(uint dev, uint blockno, int sub)
5959{
6060 struct buf *b;
6161
6262 acquire(&bcache.lock);
@@ -65,9 +65,9 @@ bget(uint dev, uint blockno)
6565 for (b = bcache.head.next; b != &bcache.head; b = b->next) {
6666 if (b->dev == dev && b->blockno == blockno) {
6767 b->refcnt++;
6868 release(&bcache.lock);
69 acquiresleep(&b->lock);
69 acquiresleep_nested(&b->lock, sub);
7070 return b;
7171 }
7272 }
7373
@@ -79,9 +79,9 @@ bget(uint dev, uint blockno)
7979 b->blockno = blockno;
8080 b->valid = 0;
8181 b->refcnt = 1;
8282 release(&bcache.lock);
83 acquiresleep(&b->lock);
83 acquiresleep_nested(&b->lock, sub);
8484 return b;
8585 }
8686 }
8787 panic("bget: no buffers");
@@ -89,12 +89,20 @@ bget(uint dev, uint blockno)
8989
9090// Return a locked buf with the contents of the indicated block.
9191struct buf *
9292bread(uint dev, uint blockno)
93{
94 return bread_nested(dev, blockno, 0);
95}
96
97// bread, for a block read while another buffer is held; sub is
98// its role (see acquiresleep_nested).
99struct buf *
100bread_nested(uint dev, uint blockno, int sub)
93101{
94102 struct buf *b;
95103
96 b = bget(dev, blockno);
104 b = bget(dev, blockno, sub);
97105 if (!b->valid) {
98106 virtio_disk_rw(b, 0);
99107 b->valid = 1;
100108 }
kernel/defs.h
@@ -12,8 +12,9 @@ struct superblock;
1212
1313// bio.c
1414void binit(void);
1515struct buf* bread(uint, uint);
16struct buf* bread_nested(uint, uint, int);
1617void brelse(struct buf*);
1718void bwrite(struct buf*);
1819void bpin(struct buf*);
1920void bunpin(struct buf*);
kernel/fs.c
@@ -53,9 +53,10 @@ static void
5353bzero(int dev, int bno)
5454{
5555 struct buf *bp;
5656
57 bp = bread(dev, bno);
57 // bmap() may hold an indirect block here.
58 bp = bread_nested(dev, bno, SUB_INNER);
5859 memset(bp->data, 0, BSIZE);
5960 log_write(bp);
6061 brelse(bp);
6162}
@@ -71,9 +72,10 @@ balloc(uint dev)
7172 struct buf *bp;
7273
7374 bp = 0;
7475 for (b = 0; b < sb.size; b += BPB) {
75 bp = bread(dev, BBLOCK(b, sb));
76 // bmap() may hold an indirect block here.
77 bp = bread_nested(dev, BBLOCK(b, sb), SUB_INNER);
7678 for (bi = 0; bi < BPB && b + bi < sb.size; bi++) {
7779 m = 1 << (bi % 8);
7880 if ((bp->data[bi / 8] & m) == 0) { // Is block free?
7981 bp->data[bi / 8] |= m; // Mark block in use.
@@ -95,9 +97,10 @@ bfree(int dev, uint b)
9597{
9698 struct buf *bp;
9799 int bi, m;
98100
99 bp = bread(dev, BBLOCK(b, sb));
101 // itrunc() may hold the indirect block here.
102 bp = bread_nested(dev, BBLOCK(b, sb), SUB_INNER);
100103 bi = b % BPB;
101104 m = 1 << (bi % 8);
102105 if ((bp->data[bi / 8] & m) == 0)
103106 panic("freeing free block");
kernel/log.c
@@ -73,9 +73,10 @@ install_trans(int recovering)
7373 if (recovering) {
7474 printk("recovering tail %d dst %d\n", tail, log.lh.block[tail]);
7575 }
7676 struct buf *lbuf = bread(log.dev, log.start + tail + 1); // read log block
77 struct buf *dbuf = bread(log.dev, log.lh.block[tail]); // read dst
77 struct buf *dbuf =
78 bread_nested(log.dev, log.lh.block[tail], SUB_INNER); // read dst
7879 memmove(dbuf->data, lbuf->data, BSIZE); // copy block to dst
7980 bwrite(dbuf); // write dst to disk
8081 if (recovering == 0)
8182 bunpin(dbuf);
@@ -190,9 +191,10 @@ write_log(void)
190191 int tail;
191192
192193 for (tail = 0; tail < log.lh.n; tail++) {
193194 struct buf *to = bread(log.dev, log.start + tail + 1); // log block
194 struct buf *from = bread(log.dev, log.lh.block[tail]); // cache block
195 struct buf *from =
196 bread_nested(log.dev, log.lh.block[tail], SUB_INNER); // cache block
195197 memmove(to->data, from->data, BSIZE);
196198 bwrite(to); // write the log
197199 brelse(from);
198200 brelse(to);
kernel/sleeplock.h
@@ -11,4 +11,5 @@ struct sleeplock {
1111
1212// Roles for acquiresleep_nested(): a sleep-lock taken while
1313// another lock of its class is held. Role 0 is the default.
1414#define SUB_CHILD 1 // an inode, while its directory is locked
15#define SUB_INNER 1 // a buffer, while an indirect or log block is held
5036577 Take iput's inode lock with a trylock
kernel/defs.h
@@ -64,12 +64,12 @@ void kfree(void *);
6464void kinit(void);
6565
6666// lockdep.c
6767int lockdep_class(char*, int);
68void lockdep_acquire(struct spinlock*);
68void lockdep_acquire(struct spinlock*, int);
6969void lockdep_release(struct spinlock*);
7070void lockdep_print(void);
71void lockdep_acquiresleep(struct sleeplock*, int);
71void lockdep_acquiresleep(struct sleeplock*, int, int);
7272void lockdep_releasesleep(struct sleeplock*);
7373void lockdep_irq_enter(void);
7474void lockdep_irq_exit(void);
7575
@@ -123,14 +123,16 @@ void swtch(struct context*, struct context*);
123123void acquire(struct spinlock*);
124124int holding(struct spinlock*);
125125void initlock(struct spinlock*, char*);
126126void release(struct spinlock*);
127int tryacquire(struct spinlock*);
127128void push_off(void);
128129void pop_off(void);
129130
130131// sleeplock.c
131132void acquiresleep(struct sleeplock*);
132133void acquiresleep_nested(struct sleeplock*, int);
134int tryacquiresleep(struct sleeplock*);
133135void releasesleep(struct sleeplock*);
134136int holdingsleep(struct sleeplock*);
135137void initsleeplock(struct sleeplock*, char*);
136138
kernel/fs.c
@@ -368,10 +368,15 @@ iput(struct inode *ip)
368368 int last = (ip->ref == 1 && ip->valid && ip->nlink == 0);
369369 uint dev = ip->dev, inum = ip->inum;
370370
371371 if (last) {
372 // ip->ref == 1 means no other process can have ip locked.
373 acquiresleep(&ip->lock);
372 // ip->ref == 1 means no other process can have ip locked,
373 // so this never waits (and never sleeps holding itable.lock).
374 // Saying so with a try keeps the checker from recording
375 // itable -> inode, which with the usual inode -> itable
376 // would look like a cycle.
377 if (!tryacquiresleep(&ip->lock))
378 panic("iput: inode locked");
374379 release(&itable.lock);
375380
376381 itrunc(ip); // free the data blocks (type stays nonzero on disk)
377382 ip->valid = 0;
kernel/lockdep.c
@@ -351,11 +351,14 @@ push(struct ldheld *h, void *lk, int c, uint64 *pc)
351351 h->cls = c;
352352 memmove(h->pc, pc, sizeof(h->pc));
353353}
354354
355// Called by acquire() before it spins, with interrupts off.
355// Called by acquire() before it spins, with interrupts off, or
356// by tryacquire() (try = 1) once it has the lock. A lock that is
357// never waited for cannot be one of the waits in a deadlock, so a
358// try records no order: it is only added to the held list.
356359void
357lockdep_acquire(struct spinlock *lk)
360lockdep_acquire(struct spinlock *lk, int try)
358361{
359362 int id = cpuid();
360363 uint64 pc[NTRACE];
361364
@@ -367,9 +370,10 @@ lockdep_acquire(struct spinlock *lk)
367370 if (inirq[id])
368371 use(lk->cls, USE_IRQ, pc);
369372 if (intr_get()) // never: acquire() turned them off first
370373 use(lk->cls, USE_IRQON, pc);
371 orderall(lk->cls, pc);
374 if (!try)
375 orderall(lk->cls, pc);
372376 if (!lockdep_on)
373377 return;
374378 if (nheld[id] == MAXHELD)
375379 panic("lockdep: too many locks held");
@@ -395,11 +399,12 @@ lockdep_release(struct spinlock *lk)
395399 held[id][i] = held[id][i + 1];
396400 nheld[id]--;
397401}
398402
399// Called by acquiresleep_nested() before it waits.
403// Called by acquiresleep_nested() before it waits, or by
404// tryacquiresleep() (try = 1) once it has the lock.
400405void
401lockdep_acquiresleep(struct sleeplock *lk, int sub)
406lockdep_acquiresleep(struct sleeplock *lk, int sub, int try)
402407{
403408 uint64 pc[NTRACE];
404409 struct proc *p;
405410 int s, c;
@@ -412,9 +417,10 @@ lockdep_acquiresleep(struct sleeplock *lk, int sub)
412417 c = subclass(lk->cls, sub);
413418 trace((uint64)__builtin_frame_address(0), pc);
414419 // a sleep-lock's holder runs with interrupts on, and sleeps
415420 use(c, inirq[cpuid()] ? USE_IRQ : USE_IRQON, pc);
416 orderall(c, pc);
421 if (!try)
422 orderall(c, pc);
417423 s = p - proc;
418424 if (nsheld[s] == MAXSLEEP)
419425 panic("lockdep: too many sleep-locks held");
420426 if (lockdep_on)
kernel/sleeplock.c
@@ -31,9 +31,9 @@ acquiresleep(struct sleeplock *lk)
3131// it" is an order it can check, not inode nested in inode.
3232void
3333acquiresleep_nested(struct sleeplock *lk, int sub)
3434{
35 lockdep_acquiresleep(lk, sub); // check the order before waiting
35 lockdep_acquiresleep(lk, sub, 0); // check the order before waiting
3636 acquire(&lk->lk);
3737 while (lk->locked) {
3838 sleep_prepare(lk);
3939 release(&lk->lk);
@@ -44,8 +44,26 @@ acquiresleep_nested(struct sleeplock *lk, int sub)
4444 lk->pid = myproc()->pid;
4545 release(&lk->lk);
4646}
4747
48// Acquire lk only if no one holds it; never sleep.
49// Returns 1 if it was acquired.
50int
51tryacquiresleep(struct sleeplock *lk)
52{
53 if (!tryacquire(&lk->lk))
54 return 0;
55 if (lk->locked) {
56 release(&lk->lk);
57 return 0;
58 }
59 lk->locked = 1;
60 lk->pid = myproc()->pid;
61 lockdep_acquiresleep(lk, 0, 1); // held now, but never waited for
62 release(&lk->lk);
63 return 1;
64}
65
4866void
4967releasesleep(struct sleeplock *lk)
5068{
5169 lockdep_releasesleep(lk);
kernel/spinlock.c
@@ -24,9 +24,9 @@ acquire(struct spinlock *lk)
2424{
2525 push_off(); // disable interrupts to avoid deadlock.
2626 if (holding(lk))
2727 panic("acquire");
28 lockdep_acquire(lk); // check the order before waiting
28 lockdep_acquire(lk, 0); // check the order before waiting
2929
3030 // On RISC-V, __atomic_exchange_n turns into an atomic swap:
3131 // a5 = 1
3232 // s1 = &lk->locked
@@ -42,8 +42,25 @@ acquire(struct spinlock *lk)
4242 // Record info about lock acquisition for holding() and debugging.
4343 lk->cpu = mycpu();
4444}
4545
46// Acquire the lock only if it is free; never spin.
47// Returns 1 if it was acquired.
48int
49tryacquire(struct spinlock *lk)
50{
51 push_off();
52 if (holding(lk))
53 panic("tryacquire");
54 if (__atomic_exchange_n(&lk->locked, 1, __ATOMIC_ACQUIRE) != 0) {
55 pop_off();
56 return 0;
57 }
58 lk->cpu = mycpu();
59 lockdep_acquire(lk, 1); // held now, but never waited for
60 return 1;
61}
62
4663// Release the lock.
4764void
4865release(struct spinlock *lk)
4966{
1a27d5d Panic at a report, now that xv6 runs clean
kernel/lockdep.c
@@ -269,8 +269,23 @@ report(struct ldheld *h, int c, uint64 *pc)
269269 where("wants", e->b, e->bpc);
270270 }
271271}
272272
273// After a report, printed by this hart with ldlock held: panic,
274// or (LOCKDEP_PANIC 0) carry on without the checker. Once the
275// graph has a cycle, more reports would mostly be echoes of it.
276static void
277stop(void)
278{
279 if (LOCKDEP_PANIC) {
280 ldunlk();
281 panic("lockdep");
282 }
283 printk("lockdep: turning off the checker\n");
284 lockdep_on = 0;
285 busy[cpuid()] = 0;
286}
287
273288// Learn that class c is acquired while h is held. Edges are only
274289// ever added, so a bit seen set without the lock can be trusted:
275290// the common case costs one load and no lock. A new edge is
276291// checked for a cycle before it is added.
@@ -285,11 +300,9 @@ order(struct ldheld *h, int c, uint64 *pc)
285300 if ((after[h->cls] & (1UL << c)) == 0) {
286301 if (reach(c, h->cls)) {
287302 busy[id] = 1; // printk() acquires pr.lock: don't check it
288303 report(h, c, pc);
289 printk("lockdep: turning off the checker\n");
290 lockdep_on = 0;
291 busy[id] = 0;
304 stop();
292305 } else {
293306 newedge(h, c, pc);
294307 }
295308 }
@@ -335,11 +348,9 @@ use(int c, int how, uint64 *pc)
335348 printk("lockdep: %s is taken in interrupt handlers and held "
336349 "with interrupts on\n", cls[c].name);
337350 where("in a handler:", c, cls[c].usepc[USE_IRQ - 1]);
338351 where("interrupts on:", c, cls[c].usepc[USE_IRQON - 1]);
339 printk("lockdep: turning off the checker\n");
340 lockdep_on = 0;
341 busy[id] = 0;
352 stop();
342353 }
343354 }
344355 ldunlk();
345356}
kernel/param.h
@@ -11,4 +11,5 @@
1111#define NBUF (MAXOPBLOCKS * 3) // size of disk block cache
1212#define FSSIZE 2000 // size of file system in blocks
1313#define MAXPATH 128 // maximum file path name
1414#define USERSTACK 1 // user stack pages
15#define LOCKDEP_PANIC 1 // panic at a lockdep report (0: warn once)
4154908 Add the lockdep system call and self-tests
kernel/lockdep.c
@@ -14,8 +14,9 @@
1414#include "spinlock.h"
1515#include "sleeplock.h"
1616#include "proc.h"
1717#include "defs.h"
18#include "lockdep.h"
1819
1920#define MAXCLASS 64 // lock classes; class 0 means "none"
2021#define MAXHELD 8 // spinlocks one hart can hold at once
2122#define MAXSLEEP 8 // sleep-locks one process can hold at once
@@ -32,8 +33,9 @@ struct ldclass {
3233 int use; // USE_IRQ, USE_IRQON
3334 uint64 usepc[2][NTRACE]; // where each use was first seen
3435 int sub[NSUB]; // the class of each subclass, if made
3536 char subname[24]; // "inode/1", for a subclass
37 int test; // a self-test class (see selftest)
3638};
3739
3840static struct ldclass cls[MAXCLASS];
3941static int nclass = 1;
@@ -105,8 +107,9 @@ subclass(int c, int sub)
105107 cls[s].subname[n] = '/';
106108 cls[s].subname[n + 1] = '0' + sub;
107109 cls[s].name = cls[s].subname;
108110 cls[s].sleep = cls[c].sleep;
111 cls[s].test = cls[c].test;
109112 __atomic_store_n(&nclass, s + 1, __ATOMIC_RELEASE);
110113 __atomic_store_n(&cls[c].sub[sub], s, __ATOMIC_RELEASE);
111114 }
112115 ldunlk();
@@ -135,8 +138,11 @@ extern struct proc proc[NPROC];
135138
136139int lockdep_on = 1;
137140static int busy[NCPU]; // this hart is printing a report
138141static int inirq[NCPU]; // this hart is running an interrupt handler
142static uint64 nchecks[NCPU]; // acquisitions checked, per hart
143static uint64 nslow; // checks that took ldlock
144static int nreports, ntestreports;
139145
140146// Fill pc[] with return addresses: the caller of acquire() and
141147// the callers above it. fp is the checker's own frame pointer
142148// (s0). In each frame, ra is saved at fp-8 and the caller's fp at
@@ -275,8 +281,9 @@ report(struct ldheld *h, int c, uint64 *pc)
275281// graph has a cycle, more reports would mostly be echoes of it.
276282static void
277283stop(void)
278284{
285 nreports++;
279286 if (LOCKDEP_PANIC) {
280287 ldunlk();
281288 panic("lockdep");
282289 }
@@ -296,13 +303,19 @@ order(struct ldheld *h, int c, uint64 *pc)
296303
297304 if (__atomic_load_n(&after[h->cls], __ATOMIC_RELAXED) & (1UL << c))
298305 return;
299306 ldlk();
307 nslow++;
300308 if ((after[h->cls] & (1UL << c)) == 0) {
301309 if (reach(c, h->cls)) {
302310 busy[id] = 1; // printk() acquires pr.lock: don't check it
303311 report(h, c, pc);
304 stop();
312 if (cls[c].test) { // a self-test: count it and go on
313 ntestreports++;
314 busy[id] = 0;
315 } else {
316 stop();
317 }
305318 } else {
306319 newedge(h, c, pc);
307320 }
308321 }
@@ -376,8 +389,9 @@ lockdep_acquire(struct spinlock *lk, int try)
376389 if (!lockdep_on || busy[id])
377390 return;
378391 if (lk->cls == 0)
379392 panic("lockdep: lock without a class");
393 nchecks[id]++;
380394 trace((uint64)__builtin_frame_address(0), pc);
381395 if (inirq[id])
382396 use(lk->cls, USE_IRQ, pc);
383397 if (intr_get()) // never: acquire() turned them off first
@@ -425,8 +439,9 @@ lockdep_acquiresleep(struct sleeplock *lk, int sub, int try)
425439 if (lockdep_on && !busy[cpuid()]) {
426440 if (lk->cls == 0 || p == 0)
427441 panic("lockdep: acquiresleep");
428442 c = subclass(lk->cls, sub);
443 nchecks[cpuid()]++;
429444 trace((uint64)__builtin_frame_address(0), pc);
430445 // a sleep-lock's holder runs with interrupts on, and sleeps
431446 use(c, inirq[cpuid()] ? USE_IRQ : USE_IRQON, pc);
432447 if (!try)
@@ -499,4 +514,142 @@ lockdep_print(void)
499514 printk(" %s", cls[b].name);
500515 printk("\n");
501516 }
502517}
518
519// Self-tests: lock orders, right and wrong, on locks of their own,
520// whose classes are marked "test". A report about a test class is
521// printed and counted, but neither panics nor stops the checker.
522static struct spinlock ta, tb, tc, ts1, ts2;
523static struct sleeplock tsa, tsb;
524static uint testbusy;
525
526// Forget every order that involves a test class.
527static void
528forget(void)
529{
530 int a, b, i, j;
531
532 ldlk();
533 for (a = 1; a < nclass; a++)
534 for (b = 1; b < nclass; b++)
535 if (cls[a].test || cls[b].test)
536 after[a] &= ~(1UL << b);
537 for (i = j = 0; i < nedges; i++)
538 if (!cls[edges[i].a].test && !cls[edges[i].b].test)
539 edges[j++] = edges[i];
540 nedges = j;
541 ldunlk();
542}
543
544// Acquire a, then b inside it; release both.
545static void
546nest(struct spinlock *a, struct spinlock *b)
547{
548 acquire(a);
549 acquire(b);
550 release(b);
551 release(a);
552}
553
554// The same for sleep-locks, each in a role.
555static void
556nestsleep(struct sleeplock *a, int asub, struct sleeplock *b, int bsub)
557{
558 acquiresleep_nested(a, asub);
559 acquiresleep_nested(b, bsub);
560 releasesleep(b);
561 releasesleep(a);
562}
563
564static int
565selftest(int n)
566{
567 int before;
568
569 if (ta.cls == 0) {
570 initlock(&ta, "test A");
571 initlock(&tb, "test B");
572 initlock(&tc, "test C");
573 initlock(&ts1, "test S");
574 initlock(&ts2, "test S");
575 initsleeplock(&tsa, "test T");
576 initsleeplock(&tsb, "test T");
577 cls[ta.cls].test = cls[tb.cls].test = cls[tc.cls].test = 1;
578 cls[ts1.cls].test = cls[tsa.cls].test = 1;
579 }
580 push_off();
581 forget();
582 pop_off();
583 before = ntestreports;
584 switch (n) {
585 case 1: // A then B; later B then A
586 nest(&ta, &tb);
587 nest(&tb, &ta);
588 break;
589 case 2: // A then B, B then C; later C then A
590 nest(&ta, &tb);
591 nest(&tb, &tc);
592 nest(&tc, &ta);
593 break;
594 case 3: // two locks of one class, one inside the other
595 nest(&ts1, &ts2);
596 break;
597 case 4: // the same with sleep-locks, the inner one as SUB_CHILD;
598 // later the same two locks the other way round
599 nestsleep(&tsa, 0, &tsb, SUB_CHILD);
600 nestsleep(&tsb, 0, &tsa, SUB_CHILD);
601 break;
602 case 5: // role 0 then SUB_CHILD; later SUB_CHILD then role 0
603 nestsleep(&tsa, 0, &tsb, SUB_CHILD);
604 nestsleep(&tsb, SUB_CHILD, &tsa, 0);
605 break;
606 case 6: // A then B; later B then a trylock of A
607 nest(&ta, &tb);
608 acquire(&tb);
609 if (tryacquire(&ta))
610 release(&ta);
611 release(&tb);
612 break;
613 default:
614 return -1;
615 }
616 return ntestreports - before;
617}
618
619// lockdep(0, st): copy the checker's statistics to st.
620// lockdep(n, 0): run self-test n and return how many reports it
621// caused; -1 if there is no such test, the checker is off, or
622// another self-test is running.
623uint64
624sys_lockdep(void)
625{
626 int cmd, i, r;
627 uint64 addr;
628 struct ldstat st;
629
630 argint(0, &cmd);
631 argaddr(1, &addr);
632 if (cmd == 0) {
633 memset(&st, 0, sizeof(st));
634 push_off();
635 ldlk();
636 st.on = lockdep_on;
637 for (i = 1; i < nclass; i++)
638 st.classes += !cls[i].test;
639 for (i = 0; i < nedges; i++)
640 st.edges += !cls[edges[i].a].test && !cls[edges[i].b].test;
641 st.reports = nreports;
642 for (i = 0; i < NCPU; i++)
643 st.checks += nchecks[i];
644 st.slow = nslow;
645 ldunlk();
646 pop_off();
647 return copyout(myproc()->pagetable, myproc()->sz, addr, (char *)&st,
648 sizeof(st));
649 }
650 if (!lockdep_on || __atomic_exchange_n(&testbusy, 1, __ATOMIC_ACQUIRE))
651 return -1;
652 r = selftest(cmd);
653 __atomic_store_n(&testbusy, 0, __ATOMIC_RELEASE);
654 return r;
655}
kernel/lockdep.h
@@ -0,0 +1,9 @@
1// What lockdep(0, &st) reports; shared with user programs.
2struct ldstat {
3 int on; // 1 while the checker runs
4 int classes; // lock classes and subclasses seen
5 int edges; // lock orders learned
6 int reports; // reports about the kernel's own locks
7 uint64 checks; // acquisitions checked
8 uint64 slow; // checks that took the checker's lock
9};
kernel/syscall.c
@@ -102,8 +102,9 @@ extern uint64 sys_unlink(void);
102102extern uint64 sys_link(void);
103103extern uint64 sys_mkdir(void);
104104extern uint64 sys_close(void);
105105extern uint64 sys_sync(void);
106extern uint64 sys_lockdep(void);
106107
107108// An array mapping syscall numbers from syscall.h
108109// to the function that handles the system call.
109110static uint64 (*syscalls[])(void) = {
@@ -129,8 +130,9 @@ static uint64 (*syscalls[])(void) = {
129130 [SYS_link] = sys_link,
130131 [SYS_mkdir] = sys_mkdir,
131132 [SYS_close] = sys_close,
132133 [SYS_sync] = sys_sync,
134 [SYS_lockdep] = sys_lockdep,
133135 // clang-format on
134136};
135137
136138void
kernel/syscall.h
@@ -20,4 +20,5 @@
2020#define SYS_link 19
2121#define SYS_mkdir 20
2222#define SYS_close 21
2323#define SYS_sync 22
24#define SYS_lockdep 23
user/user.h
@@ -1,7 +1,8 @@
11#define SBRK_ERROR ((char *)-1)
22
33struct stat;
4struct ldstat;
45
56// system calls
67int fork(void);
78int exit(int) __attribute__((noreturn));
@@ -24,8 +25,9 @@ int getpid(void);
2425char *sys_sbrk(int, int);
2526int pause(int);
2627int uptime(void);
2728int sync(void);
29int lockdep(int, struct ldstat *);
2830
2931// ulib.c
3032int stat(const char *, struct stat *);
3133char *strcpy(char *, const char *);
user/usys.pl
@@ -42,4 +42,5 @@ entry("getpid");
4242entry("sbrk");
4343entry("pause");
4444entry("uptime");
4545entry("sync");
46entry("lockdep");
1de7f16 Add lockdeptest
Makefile
@@ -150,8 +150,9 @@ UPROGS=\
150150 $U/_logstress\
151151 $U/_forphan\
152152 $U/_dorphan\
153153 $U/_sync\
154 $U/_lockdeptest\
154155
155156fs.img: mkfs/mkfs README $(UPROGS)
156157 mkfs/mkfs fs.img README $(UPROGS)
157158
user/lockdeptest.c
@@ -0,0 +1,58 @@
1// Test the lock-order checker: run its self-tests, each a lock
2// order that should or should not be reported, and check that the
3// kernel's own locks have caused no report.
4
5#include "kernel/types.h"
6#include "kernel/lockdep.h"
7#include "user/user.h"
8
9struct test {
10 char *what;
11 int reports; // reports expected
12} tests[] = {
13 {"A then B; later B then A", 1},
14 {"A then B, B then C; later C then A", 1},
15 {"two locks of one class, one inside the other", 1},
16 {"two sleep-locks of one class, the inner one SUB_CHILD, both ways round", 0},
17 {"role 0 then SUB_CHILD; later SUB_CHILD then role 0", 1},
18 {"A then B; later B then a trylock of A", 0},
19};
20
21int
22main(void)
23{
24 struct ldstat st;
25 int i, r, ok = 0, n = 0;
26
27 if (lockdep(0, &st) < 0) {
28 printf("lockdeptest: lockdep(0) failed\n");
29 exit(1);
30 }
31 printf("lockdeptest: %d classes, %d orders, %ld acquisitions checked, "
32 "%ld of them slowly\n", st.classes, st.edges, st.checks, st.slow);
33
34 for (i = 0; i < sizeof(tests) / sizeof(tests[0]); i++) {
35 printf("lockdeptest: test %d: %s\n", i + 1, tests[i].what);
36 r = lockdep(i + 1, 0);
37 n++;
38 if (r == tests[i].reports) {
39 ok++;
40 printf("lockdeptest: test %d: %d report(s), as expected: OK\n", i + 1, r);
41 } else {
42 printf("lockdeptest: test %d: %d report(s), expected %d: FAIL\n", i + 1, r,
43 tests[i].reports);
44 }
45 }
46
47 lockdep(0, &st);
48 n++;
49 if (st.on && st.reports == 0) {
50 ok++;
51 printf("lockdeptest: checker on, no report about the kernel's locks: OK\n");
52 } else {
53 printf("lockdeptest: checker on %d, reports %d: FAIL\n", st.on, st.reports);
54 }
55 printf("lockdeptest: %d of %d checks OK; read the reports above to see that "
56 "each names both orders\n", ok, n);
57 exit(ok == n ? 0 : 1);
58}

6. Verify and measure

On the branch (ext/21-lockdep, 12 commits), built with the project toolchain and run on three harts (-smp 3 -m 128M), in one boot (reports trimmed):

$ lockdeptest
lockdeptest: 18 classes, 39 orders, 101086 acquisitions checked, 39 of them slowly
lockdeptest: test 1: A then B; later B then A
lockdep: acquiring test A while holding test B may deadlock
hart 0, pid 3 (lockdeptest):
  holds test B at 0x80001534 0x80002218 0x80003f9c 0x80003d22 0x3ffffff09c
  wants test A at 0x8000153a 0x80002218 0x80003f9c 0x80003d22 0x3ffffff09c
but this order has been seen before:
hart 0, pid 3 (lockdeptest):
  holds test A at 0x80001534 0x80002204 0x80003f9c 0x80003d22 0x3ffffff09c
  wants test B at 0x8000153a 0x80002204 0x80003f9c 0x80003d22 0x3ffffff09c
lockdeptest: test 1: 1 report(s), as expected: OK
[... tests 2 and 3 ...]
lockdeptest: test 4: two sleep-locks of one class, the inner one SUB_CHILD, both ways round
lockdeptest: test 4: 0 report(s), as expected: OK
lockdeptest: test 5: role 0 then SUB_CHILD; later SUB_CHILD then role 0
lockdep: acquiring test T while holding test T/1 may deadlock
[...]
lockdeptest: test 5: 1 report(s), as expected: OK
lockdeptest: test 6: A then B; later B then a trylock of A
lockdeptest: test 6: 0 report(s), as expected: OK
lockdeptest: checker on, no report about the kernel's locks: OK
lockdeptest: 7 of 7 checks OK; read the reports above to see that each names both orders
$ usertests -q
usertests starting
[...]
test unlinkcwd: OK
ALL TESTS PASSED
$ lockdeptest
lockdeptest: 19 classes, 46 orders, 28158293 acquisitions checked, 63 of them slowly
[... the same seven checks, all OK ...]
lockdeptest: 7 of 7 checks OK; read the reports above to see that each names both orders

usertests -q passed with the checker on and silent: about 28 million acquisitions checked, 46 orders learned, no report. “Slowly” counts the self-tests’ own slow paths too: 39 before the first lockdeptest (the program prints its statistics before it runs the self-tests), 63 after usertests and one round of self-tests (the first lockdeptest’s 17). In nine other runs with lockdeptest only after usertests, it was 46: one slow path per order. Every commit builds, and every commit’s kernel passed usertests -q on three harts (commits 4 to 8 print one report first and then run with the checker off).

The kfork bug from Tour 52: Breaking the lock rules, caught at boot. A copy of the branch with the two lines removed that make kfork release the child’s p->lock before taking wait_lock. Two boots, the same report before the shell’s first prompt:

init: starting sh
lockdep: acquiring proc while holding wait_lock may deadlock
hart 1, pid 1 (init):
  holds wait_lock at 0x80003854 0x80004022 0x80003f90 0x80003d16 0x3ffffff09c
  wants proc at 0x800038e8 0x80004022 0x80003f90 0x80003d16 0x3ffffff09c
but this order has been seen before:
hart 1, pid 1 (init):
  holds proc at 0x800031e2 0x8000331a 0x80004000 0x80003f90 0x80003d16
  wants wait_lock at 0x800033d2 0x80004000 0x80003f90 0x80003d16 0x3ffffff09c
panic: lockdep

Decoded (this copy’s line numbers): kwait holds wait_lock (proc.c:373) and acquires a child’s p->lock (proc.c:381); earlier, init’s fork() held the child’s p->lock from allocproc (proc.c:115, via kfork proc.c:266) and acquired wait_lock (proc.c:294). gdb at the panic found hart 1 in lockdep_acquire ← acquire ← kwait ← sys_wait with cpus[1].noff = 2, and the other harts busy elsewhere (hart 2 looking up sh in a directory for exec, hart 0 in uartintr). One process, one fork, one wait: no concurrency was needed. The same change on the original kernel booted, ran ls, echo hi and forktest, and then froze in usertests’ forkfork test. A second boot running only usertests forkfork froze the same way; gdb, attached after 90 seconds, found the cycle of tour 52:

Thread 3 (Thread 1.3 (CPU#2 [running])):
#0  acquire (lk=lk@entry=0x8000f9b8 <wait_lock>) at kernel/spinlock.c:37
#1  0x000000008000227c in kwait (addr=0) at kernel/proc.c:414
[...]

Thread 2 (Thread 1.2 (CPU#1 [running])):
#0  acquire (lk=lk@entry=0x80010640 <proc+2160>) at kernel/spinlock.c:37
#1  0x0000000080001fb0 in wakeup (chan=0x800104d8 <proc+1800>) at kernel/proc.c:578
#2  0x00000000800020a8 in kexit (status=0) at kernel/proc.c:350
[...]

Thread 1 (Thread 1.1 (CPU#0 [running])):
#0  acquire (lk=lk@entry=0x8000f9b8 <wait_lock>) at kernel/spinlock.c:37
#1  0x0000000080001d36 in kfork () at kernel/proc.c:294
[...]
$1 = {locked = 1, name = 0x80007168 "wait_lock", cpu = 0x8000fa50 <cpus+128>}
$2 = 9

wait_lock held by hart 1 (in kexit, waiting for a p->lock in wakeup), hart 0 in kfork waiting for wait_lock (it holds the new child’s lock, by the code: we did not print proc+2160’s owner), and ticks at 9, which cannot advance while every hart spins with interrupts off.

A rename-style inode inversion. A copy of the branch whose sys_link keeps the file locked while it looks up and locks the target directory (the original releases the file first, line 153). That is the inversion rename must avoid: one path holds a file and wants its directory, sys_unlink holds the directory and wants the file. At the first ln:

$ ln f g
lockdep: acquiring inode while holding inode may deadlock
hart 1, pid 4 (ln):
  holds inode at 0x80004924 0x800049c6 0x80006676 0x80003f9c 0x80003d22
  wants inode at 0x80004924 0x800049c6 0x80005092 0x800051ee 0x800066a6
both locks are of class inode
panic: lockdep

(sys_link holds f, and namex under nameiparent locks /.) If the programmer annotates honestly and locks the file as a child (ilock_nested(ip, SUB_CHILD)), the report names the two orders, against create at boot:

lockdep: acquiring inode while holding inode/1 may deadlock
hart 0, pid 4 (ln):
  holds inode/1 at 0x80004924 0x80006678 0x80003f9c 0x80003d22 0x3ffffff09c
  wants inode at 0x80004924 0x800049c6 0x80005092 0x800051ee 0x800066a8
but this order has been seen before:
hart 1, pid 1 (init):
  holds inode at 0x80004924 0x800049c6 0x8000639a 0x80006aae 0x80003f9c
  wants inode/1 at 0x80004924 0x80006426 0x80006aae 0x80003f9c 0x80003d22
panic: lockdep

On the original kernel with the same change, a short program (in the scratch copy only) with one process looping link("d/x", "d/y") and another unlink("d/y") stopped after u0 l0 l100 u100 u200 l200 u300: gdb found both processes SLEEPING, pid 3 (the unlink loop) holding directory d (inode 25) and asleep on file x’s lock, pid 4 (the link loop) holding x (inode 26) and asleep on d’s, while all three harts sat idle and ticks kept counting (6,146). A deadlock of sleep-locks: nothing spins, two processes are gone.

Run time. usertests -q on three harts, wall-clock time measured by the script that drives QEMU (measured while the computer was busy with other work; your times will differ, since timings on QEMU depend on what else the computer is doing). To make the comparison fair, the kernels of each round started at the same moment, so they shared whatever else the computer was doing:

round	original kernel	branch head	head / original
1	80.3 s	93.2 s	1.16
2	60.1 s	81.7 s	1.36
3	54.3 s	65.4 s	1.20
4	55.2 s	72.3 s	1.31
5	49.4 s	68.4 s	1.38
6	54.6 s	66.3 s	1.21
7	50.6 s	62.6 s	1.24
8	50.9 s	59.7 s	1.17
9	60.6 s	71.5 s	1.18

With the checker, usertests -q took 16 to 38 percent longer (median 21 percent). How much of the spread is noise? In rounds 1 to 6 a second copy of the same head kernel ran alongside; the two copies differed by 0 to 4.3 percent (97.2 against 93.2 s in round 1).

What the time goes on. The checker examined 25.7 to 28.9 million acquisitions per run and took its own lock 46 times. So the cost is the per-acquisition bookkeeping, not the graph: a call, the five-frame trace, the push on a held list, and the search on release. To see what the lock-free fast path is worth, a scratch copy took ldlock on every call to order() (rounds 7 to 9 ran it alongside the other two): it took the lock 39.7 to 42.0 million times per run (more than the acquisitions: an acquisition with two locks held makes two calls) and was 7 to 11 percent slower than the head (69.1, 64.1 and 79.6 s against 62.6, 59.7 and 71.5 s). Worth having, but most of the checker’s cost is elsewhere.

What it learned. After boot, ls and usertests -q: 19 classes (including the subclasses inode/1 and buffer/1) and 46 orders, close to Tour 51: The lock-order graph, measured's measured graph. Ctrl-P prints them; for example lockdep: proc -> kmem nextpid itable ftable and lockdep: inode -> sleep lock kmem proc bcache buffer itable ftable virtio_disk log inode/1 buffer/1.

What QEMU hides. The times are QEMU’s, on a busy computer; they say “about a fifth slower”, not a cycle count. On real hardware the shared after[] words would be read by every hart and almost never written, which caches handle well. The per-hart arrays are another matter: nheld, nchecks, inirq and busy are small arrays indexed by hart, written on every acquisition, so neighbouring harts’ entries share cache lines.

7. Go further

The log as a lock. begin_op can make a process wait for a commit, and the committing process holds buffers: it behaves like a lock the checker cannot see (Tour 51: The lock-order graph, measured makes the same point). Give it a class of its own (Linux does this for its journal with a lockdep_map) and see which orders appear.
Check the buffer roles. SUB_INNER is a claim. Add a check that a SUB_INNER read really happens while a buffer is held, or make the roles per block type (log, bitmap, indirect, data) and let the checker learn their order.
Irq-safe before irq-unsafe. Linux also reports an edge from a class used in a handler to a class held with interrupts on, through any path. In xv6 only sleep-locks can be the second; add the check and explain why it never fires.
Hold times. Record how long each class is held (the time CSR at acquire and release) and print the longest, per class. Which spinlock is held longest, and is it one a handler waits for?
Sleeping holding a spinlock, by name. sched panics sched locks without saying which lock. Make it print the hart’s held list first.