Lab 21 · reveal · 20 steps · 12 commits
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).
Each step shows one change on the branch ext/21-lockdep, the code around it, and the state of the machine when that code runs.
stack0Step 1 of 20 · commit 1: Give every lock a lockdep class
The checker reasons about classes, so every lock carries its class number. locked is
a 4-byte uint followed by 4 bytes of padding before the 8-byte name pointer; cls
fills the padding. struct spinlock stays 24 bytes, struct sleeplock (the same change)
stays 48, and nothing that embeds a lock (struct proc, struct pipe, every buffer and
inode) moves.
initlock now ends with lk->cls = lockdep_class(name, 0), and initsleeplock with
lockdep_class(name, 1). gdb, stopped at the first call on the finished branch: hart 0,
in main → consoleinit → initlock(&cons.lock, "cons"), with no lock held and
sstatus = 0x200000000 (SIE clear). So cons is class 1.
stack0kernel/lockdep.cStep 2 of 20 · commit 1: Give every lock a lockdep class
The table maps a class number to its name; class 0 means “none”, so a lock never passed
to initlock is noticed. Lookup compares the strings, so every initlock(&p->lock, "proc") in procinit gets the same class.
The table needs a lock: pipes create classes at any time, on any hart. It cannot be a
struct spinlock. The next commit makes acquire call the checker, and a checker that
called acquire would recurse (clinic 1 recorded the result). ldlock is a bare word:
ldlk() is the swap loop that acquire uses, ldunlk() the release store, with nothing
else.
What it keeps from a spinlock is the rule about interrupts: whoever holds ldlock must
have them off, or a handler on the same hart could need it and spin forever. Here
lockdep_class calls push_off itself (line 56), because pipealloc calls
initlock with interrupts on.
stack0p->lock (proc[0], being built)kernel/spinlock.cStep 3 of 20 · commit 2: Track the spinlocks each hart holds
acquire calls lockdep_acquire(lk) after push_off and the holding check,
and before the swap loop. A deadlocked hart never leaves that loop, so a check placed
after it would never speak about the one acquisition that matters. release calls
lockdep_release(lk) after its own holding check.
The state is the first nested acquisition of the boot, which gdb stopped at on the
finished branch: userinit → allocproc holds the new process’s p->lock (taken at
kernel/proc.c:115) and allocpid acquires pid_lock. cpus[0].noff = 2, intena 0,
no process yet. At this commit the checker only lists the lock; the next one turns
“proc held while nextpid is acquired” into an edge.
stack0p->lock (proc[0], being built)kernel/lockdep.cStep 4 of 20 · commit 2: Track the spinlocks each hart holds
A report is useless without “where”. xv6 is compiled with -fno-omit-frame-pointer, so
every function keeps s0 pointing at the top of its frame, with its return address at
s0-8 and the caller’s s0 at s0-16. trace() starts from the checker’s own frame,
skips acquire’s, and copies up to five return addresses (NTRACE): the function that
called acquire, its caller, and so on. It stops at the edge of the current stack page.
For a process’s kernel stack (one page) that is the stack’s edge; the boot stacks in
stack0 are not page-aligned (stack0 is at 0x80009be0 in this build), so there a
walk may read a few words of a neighbouring slice, which is harmless. (Lab 2, the kernel backtrace, builds the
same walk.)
gdb printed the entry for proc[0].lock on hart 0’s list: pc0 0x800031e2 pc1 0x80003274, which addr2line turns into allocproc (kernel/proc.c:115) and
userinit. Each entry is the lock, its class and five addresses: 56 bytes, up to eight
per hart (MAXHELD; the deepest real nesting is three).
p->lock (pid 1, acquired by the scheduler)Step 5 of 20 · commit 2: Track the spinlocks each hart holds
gdb stopped hart 2 at forkret's release(&p->lock) (kernel/proc.c:520), pid 1’s
first moment as a process, on the finished branch:
hart 2 noff 1 intena 0 sstatus 0x200000020
proc pid 1 name
nheld[2] = 1
held[0]: lk 0x80023898 cls 8 (proc) pc0 0x80003474 pc1 0x8000253c
(gdb) info symbol held[$tp][0].pc[0]
scheduler + 98 in section .text
The process is about to release a lock that the scheduler acquired, a different
thread on the same hart (Locks and interrupt state). The entry is on hart 2’s list,
and lockdep_release searches that list for the lock, finds it and removes it. The
search matters for a second reason: locks are not always released in reverse order
(kexit releases wait_lock before its own p->lock).
This is why the list is per hart. A list per thread would have the scheduler’s acquire on one list and this release on another (clinic 3).
stack0p->lock (proc[0], being built)kernel/lockdep.cStep 6 of 20 · commit 3: Record the lock order between classes
lockdep_acquire now calls order(h, c) for every lock h the hart holds. An edge “a
before b” is bit b of after[a]. Fast path: load after[h->cls] without any lock;
if the bit is set, this order is known, and that is all. Bits are only ever set, so a set
bit read without the lock is still true. Slow path: take ldlock, test again (another
hart may have just added it), and add the edge: the bit, plus a record in edges[] with
the hart, the pid, and the traces of both acquisitions, for the report later.
gdb stopped the first newedge of the boot, the acquisition of the previous steps:
h->cls = 8 (proc), c = 6 (nextpid), with 15 classes registered so far. Ctrl-P
now prints the graph from procdump; after usertests -q it had 46 edges, close to
Tour 51: The lock-order graph, measured's measured graph.
How fast is fast? In our runs of usertests -q the checker examined about 27 million
acquisitions and took the slow path 46 times. About three quarters of those acquisitions
had something else held, so they made about 42 million order() calls; all but 46 ended
at the bit test.
itable.lockkernel/lockdep.cStep 7 of 20 · commit 4: Report the first acquisition that closes a cycle
A new edge a -> b closes a cycle exactly when b already reaches a. reach() is a
depth-first search over the bitmaps, from b, recording in prev[] where it came from.
At most 64 classes, run only for a new edge, under ldlock: its cost does not matter. If
a == b it answers yes at once: two locks of one class, nested.
The state is the first report this commit produced (next step): rm (pid 4) in iput,
holding itable.lock, acquiring the inner spinlock of the inode’s sleep-lock. At this
commit sleep-locks are not tracked yet, but their inner spinlocks are: every one of them
is class sleep lock.
itable.lockStep 8 of 20 · commit 4: Report the first acquisition that closes a cycle
report() walks prev[] back into a path and prints the acquisition that would close
the cycle, then each edge of the path with what was recorded when it was learned. Then
the checker switches itself off (lockdep_on = 0), as Linux’s does. busy[id] makes the
checker ignore this hart while it prints: printk acquires pr.lock, and the checker
holds ldlock.
This commit’s kernel, at the first rm of a file:
$ rm x
lockdep: acquiring sleep lock while holding itable may deadlock
hart 0, pid 4 (rm):
holds itable at 0x80003d66 0x80003e36 0x80005a3e 0x8000328c 0x80003012
wants sleep lock at 0x80004974 0x80003dac 0x80003e36 0x80005a3e 0x8000328c
but this order has been seen before:
hart 2, pid 1:
holds sleep lock at 0x800049c8 0x8000365c 0x80003f38 0x80002304 0x800022d8
wants proc at 0x8000295a 0x800049d6 0x8000365c 0x80003f38 0x80002304
hart 0, no process:
holds proc at 0x800024e4 0x80002576 0x8000189e 0x800000c2 0x8000001a
wants itable at 0x8000397a 0x800042b0 0x8000446a 0x8000258c 0x8000189e
lockdep: turning off the checker
Decoded with addr2line: iput holds itable.lock (fs.c:352 in this commit) and its
acquiresleep takes the inode’s inner lock (fs.c:362). The path back: pid 1, in
fsinit from forkret, released a buffer: releasesleep holds the buffer’s inner
lock and calls wakeup, which takes p->locks; and at boot, userinit held the new
process’s p->lock while namei("/") called iget (itable). This is exactly
the class cycle that Locks and interrupt state measured: p->lock -> itable -> lk->lk -> p->lock. It cannot deadlock: commit 9 explains why (iput only does this for an inode
nobody else references) and writes it into the code.
root directory inode (sleep-lock)kernel/sleeplock.cStep 9 of 20 · commit 5: Track sleep-locks per process
acquiresleep calls lockdep_acquiresleep() before it can sleep, and
releasesleep calls lockdep_releasesleep() first, so the sleep-lock leaves the list
before its own inner lock is taken. The lists are per process, by proc[] slot
(sheld[NPROC][8]): a process may sleep holding a buffer and resume on another hart, and
only the process itself changes its list. Ordering now looks at both lists: the hart’s
spinlocks and the running process’s sleep-locks.
gdb on the finished branch, the first time a process acquired a sleep-lock while holding
one: pid 1, in forkret's kexec("/init"), holds the root directory’s inode lock
(taken in ilock) and asks for block 33’s buffer:
lockdep_acquiresleep (lk=lk@entry=0x80029b88 <bcache+2264>, sub=sub@entry=0, try=try@entry=0)
#2 bget (dev=1, blockno=33, sub=0) at kernel/bio.c:69
[...]
#5 ilock_nested (ip=ip@entry=0x800319a8 <itable+24>, sub=sub@entry=0) at kernel/fs.c:317
$6 = 0x800096b0 "buffer"
$8 = 1
$9 = 0x80009740 "inode"
One entry on pid 1’s list, class inode, so the edge inode -> buffer. The hart’s own
list is empty (nheld[1] = 0): no spinlock is held.
/ (directory inode, sleep-lock)kernel/lockdep.cStep 10 of 20 · commit 5: Track sleep-locks per process
orderall() orders the new class after the hart’s spinlocks and the process’s
sleep-locks. With sleep-locks tracked, this commit’s kernel reported at boot, when init
creates /console with mknod:
lockdep: acquiring inode while holding inode may deadlock
hart 2, pid 1 (init):
holds inode at 0x80003f30 0x80005904 0x8000601e 0x800035d6 0x8000335c
wants inode at 0x80003f30 0x8000598e 0x8000601e 0x800035d6 0x8000335c
both locks are of class inode
lockdep: turning off the checker
Decoded: both from ilock, called by create at sysfile.c:267 (the directory) and
sysfile.c:294 (the new file), under sys_mknod. Two locks of one class, nested: a
cycle of length one. It is safe because of a rule the class graph cannot see: a
directory is always locked before a file in it. Commit 7 writes that rule down.
The iput report of the previous commit is still there, but the checker turns off after the first report, and this one comes earlier.
an inode (sleep-lock, init's)kernel/trap.cStep 11 of 20 · commit 6: Know when a hart is running an interrupt handler
devintr brackets each handler with lockdep_irq_enter() and lockdep_irq_exit(),
which count per hart. While the count is non-zero, orderall leaves out the process’s
sleep-locks: the handler runs on that process’s stack, but no cycle can pass through
them (below).
gdb on the finished branch: hart 0 took a timer interrupt while init (pid 1) was in the
kernel holding an inode’s sleep-lock; in clockintr, acquire(&tickslock) reached the
checker with inirq[0] = 1, nheld[0] = 0 and nsheld for pid 1 equal to 1. So no edge
inode -> time is learned. Recording it would be true but useless: whoever holds
tickslock holds a spinlock, and a spinlock holder can never wait for a sleep-lock
(sched would panic sched locks). So no cycle can run through the interrupted
process’s sleep-locks; leaving them out loses nothing and keeps the graph to orders that
can close.
The hart’s own list is empty, as it always is when a handler starts: an interrupt is taken only at noff 0 (Locks and interrupt state).
kernel/lockdep.cStep 12 of 20 · commit 6: Know when a hart is running an interrupt handler
use() records per class “taken in an interrupt handler” (USE_IRQ) and “held with
interrupts on” (USE_IRQON), with where each was first seen, and reports a class that
has both. Such a lock could be held by code that a handler interrupts on its own hart,
and the handler would spin forever.
For spinlocks the test on line 335 can never be true: acquire calls push_off
before the checker, so SIE is always clear here. Linux needs the check because Linux lets
a spinlock be held with interrupts on; xv6 does not. For sleep-locks (this commit adds the
same call to the previous commit’s hook) USE_IRQON is recorded on every acquisition, because a sleep-lock’s holder runs
with interrupts on; a sleep-lock taken in a handler would be reported.
We checked that the test works by breaking the order in a scratch copy: acquire calling
the checker before push_off. Both boots stopped at once:
lockdep: proc is taken in interrupt handlers and held with interrupts on
in a handler: proc at 0x80003656 0x80003be4 0x80003c72 0x80003db0 0x80006d78
interrupts on: proc at 0x8000381c 0x80003d26 0x3ffffff09c
panic: lockdep
Decoded: wakeup from clockintr, and killed from usertrap line 81, which
runs after intr_on(). (The last address, 0x3ffffff09c, is in the trampoline page:
uservec called usertrap.)
/ (directory inode, sleep-lock)kernel/lockdep.cStep 13 of 20 · commit 7: Let inodes nest inside their own class, by role
acquiresleep_nested(lk, sub) and ilock_nested(ip, sub) take a role. subclass(c, sub) turns role 1 of class inode into a class of its own, named inode/1, created the
first time it is used; role 0 is the class itself. The graph then learns inode -> inode/1 (a directory, then a file in it): an order between two classes, checked like
any other. A path that locked a file and then a directory would close a cycle with it, or
nest inode in inode again.
Linux has the same mechanism (mutex_lock_nested(&inode->i_mutex, I_MUTEX_CHILD)).
acquiresleep(lk) is now acquiresleep_nested(lk, 0).
/ (directory inode, sleep-lock)Step 14 of 20 · commit 7: Let inodes nest inside their own class, by role
create locks the new inode with ilock_nested(ip, SUB_CHILD) while it holds the
directory, and sys_unlink does the same for the file it removes (line 226). Note line 282:
when the file already exists, create releases the directory before locking the file,
so that ilock needs no role.
The next boot of this commit’s kernel got past mknod and reported in the first log
commit:
lockdep: acquiring buffer while holding buffer may deadlock
hart 0, pid 1 (init):
holds buffer at 0x8000507c 0x80003c8c 0x80004e42 0x800063b2 0x80003930
wants buffer at 0x8000507c 0x80003c3a 0x80004e50 0x800063b2 0x80003930
both locks are of class buffer
lockdep: turning off the checker
Decoded: write_log (log.c:193 and log.c:194, inlined into commit and end_op)
holds a log block and reads the home copy of a block. Another nesting with fixed roles.
a log block (buffer sleep-lock)Step 15 of 20 · commit 8: Give nested buffers a role too
bread becomes bread_nested(dev, blockno, 0), and five reads that happen while
another buffer is held use SUB_INNER: the home copy in write_log and
install_trans (under a log block), the bitmap block in balloc and bfree (under
an indirect block, from bmap or itrunc), and the new block in bzero (under an
indirect block, from bmap). In each case the outer buffer is a different kind of block,
and no code takes them the other way round.
With this commit the boot was silent. The first rm reported:
lockdep: acquiring inode while holding itable may deadlock
hart 0, pid 4 (rm):
holds itable at 0x8000444e 0x8000451e 0x80006152 0x80003930 0x800036b6
wants inode at 0x800050b4 0x80004494 0x8000451e 0x80006152 0x80003930
but this order has been seen before:
hart 0, pid 1:
holds inode at 0x800042b8 0x8000435a 0x80004a0e 0x80004b52 0x800058d4
wants itable at 0x80003e0c 0x8000492e 0x80004a30 0x80004b52 0x800058d4
lockdep: turning off the checker
iput takes an inode’s lock under itable.lock; namex, in pid 1’s
kexec("/init"), called iget under the root directory’s lock. The second class cycle
of Locks and interrupt state.
itable.lockkernel/spinlock.cStep 16 of 20 · commit 9: Take iput's inode lock with a trylock
tryacquire() makes one attempt and never spins. If it gets the lock it tells the checker
with try = 1: the lock goes on the held list (so what is taken under it is still
checked) but no order is recorded for it. A lock that is never waited for cannot be one
of the waits in a deadlock. tryacquiresleep() does the same for a sleep-lock: a try on
the inner lock, give up if the sleep-lock is taken, and never sleep.
itable.lockkernel/fs.cStep 17 of 20 · commit 9: Take iput's inode lock with a trylock
iput takes the inode’s lock only for the last reference to an unlinked inode
(last). ip->ref == 1 means nobody else references it, so nobody holds its lock or is
inside acquiresleep or releasesleep on it: the lock is free. That is exactly a
trylock, and if it ever fails the kernel panics. (The original would not have waited
silently either: sleeping with itable.lock held panics sched locks. The trylock’s
gain is that the checker now knows this acquisition never waits, and the panic names
the assumption.)
gdb on the finished branch, rm x: hart 1, pid 4, at tryacquiresleep called from
fs.c:377, with ip->ref = 1, ip->nlink = 0, inode 25, itable.lock on hart 1’s list
(pc0 in iput), no sleep-lock on pid 4’s list.
Both class cycles of Locks and interrupt state went through this one acquisition, so both
are gone. usertests -q on this commit’s kernel: ALL TESTS PASSED, no report.
wait_lockkernel/lockdep.cStep 18 of 20 · commit 10: Panic at a report, now that xv6 runs clean
With xv6 clean, a report now means somebody just introduced a new order. stop() panics
(LOCKDEP_PANIC 1 in param.h) after printing, and releases ldlock first, so the other
harts are not left spinning on it; with 0 it prints and turns the checker off, as before.
The state is the panic of the verify section’s demonstration, in which kfork takes
wait_lock while still holding the child’s p->lock: init’s first wait() (kwait)
acquires a p->lock while holding wait_lock, and the checker stops the machine there,
at boot.
test Bkernel/lockdep.cStep 19 of 20 · commit 11: Add the lockdep system call and self-tests
A checker that never reports is easy to write, so the kernel can test it on demand.
lockdep(n, 0) runs self-test n on locks named test A, test B, and so on, whose
classes are marked as test classes: a report about them is printed and counted, but does
not panic or stop the checker, and forget() clears their edges before each test. The
six tests are a two-lock cycle, a three-lock cycle, two locks of one class nested, the
same with the inner one as SUB_CHILD in both directions (no report), a role inversion,
and a trylock against the order (no report).
Test 4 shows the price of a role. Its two nestsleeps are a real AB-BA between two
instances: two processes running them at the same time would deadlock, and the checker
says nothing, because it trusts the roles. Only the directory tree makes the inode roles
safe (no directory is its own ancestor, and unlink refuses . and ..).
In test 1 the second nest() acquires test A while holding test B. The report comes
before the acquisition, and the acquisition then goes ahead: one thread cannot deadlock
with itself on two free locks. The checker spoke about a deadlock that did not, and
here could not, happen.
lockdep(0, &st) copies out the statistics: whether the checker is on, classes, orders,
reports about real locks, acquisitions checked, and slow paths.
user/lockdeptest.cStep 20 of 20 · commit 12: Add lockdeptest
The program prints the statistics, runs the six self-tests, compares each count of
reports with the expected one, then checks that the checker is still on and has made no
report about the kernel’s own locks. One OK or FAIL per check, seven in all.
What it does not check is what each report says: those lines come from the kernel. The last line says so. Read the reports for tests 1, 2, 3 and 5: each must name the acquisition that closes the cycle and every edge of the path back.
Lab 21 · wrap-up
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.
Keys: ← → step · Home start