Skip to content

ANNOUNCE: lock validator -V1

Ingo Molnar lkml 1 version In review

Get series with b4
b4 am [email protected]

Versions newest first

  1. v1 Latest61 patches 106 repliesIn review

Patches in v1 No applies recorded yet

#Subject and filesSizeRepliesApplied
1/61lock validator: floppy.c irq-release fixdrivers/block/floppy.c+25 -21 reply
2/61lock validator: forcedeth.c fixdrivers/net/forcedeth.c+3 -22 replies
3/61lock validator: sound/oss/emu10k1/midi.c cleanupsound/oss/emu10k1/midi.c+1 -13 replies
4/61lock validator: mutex section binutils workaroundkernel/mutex.c+1 -10 replies
5/61lock validator: introduce WARN_ON_ONCE(cond)include/asm-generic/bug.h+13 -05 replies
6/61lock validator: add __module_address() methodinclude/linux/module.h kernel/module.c+20 -03 replies
7/61lock validator: better lock debuggingdrivers/char/sysrq.c include/asm-generic/mutex-null.h include/linux/debug_locks.h +23 more+329 -7914 replies
8/61lock validator: locking API self-testsDocumentation/kernel-parameters.txt lib/Kconfig.debug lib/Makefile +15 more+1250 -00 replies
9/61lock validator: spin/rwlock init cleanupsarch/ia64/sn/kernel/irq.c arch/mips/kernel/smtc.c arch/powerpc/platforms/cell/spufs/switch.c +56 more+69 -690 replies
10/61lock validator: locking init debugging improvementarch/x86_64/kernel/smpboot.c arch/x86_64/kernel/vsyscall.c block/ll_rw_blk.c +18 more+51 -290 replies
11/61lock validator: lockdep: small xfs init_rwsem() cleanupfs/xfs/linux-2.6/mrlock.h+1 -12 replies
12/61lock validator: beautify x86_64 stacktracesarch/x86_64/kernel/traps.c include/asm-x86_64/kdebug.h+27 -301 reply
13/61lock validator: x86_64: document stack frame internalsarch/x86_64/kernel/traps.c+62 -20 replies
14/61lock validator: stacktracearch/i386/kernel/Makefile arch/i386/kernel/stacktrace.c arch/x86_64/kernel/Makefile +4 more+361 -30 replies
15/61lock validator: x86_64: use stacktrace to generate backtracesarch/x86_64/kernel/traps.c+33 -21 reply
16/61lock validator: fown locking workaroundfs/cifs/file.c fs/fcntl.c+16 -132 replies
17/61lock validator: sk_callback_lock workaroundnet/core/sock.c+12 -122 replies
18/61lock validator: irqtrace: corearch/i386/kernel/entry.S arch/i386/kernel/irq.c arch/x86_64/ia32/ia32entry.S +17 more+513 -902 replies
19/61lock validator: irqtrace: cleanup: include/asm-i386/irqflags.hinclude/asm-i386/irqflags.h+83 -120 replies
20/61lock validator: irqtrace: cleanup: include/asm-x86_64/irqflags.harch/x86_64/lib/thunk.S include/asm-x86_64/irqflags.h+128 -360 replies
21/61lock validator: lockdep: add local_irq_enable_in_hardirq() API.arch/i386/kernel/nmi.c arch/x86_64/kernel/nmi.c drivers/ide/ide-io.c +4 more+12 -84 replies
22/61lock validator: add per_cpu_offset()include/asm-generic/percpu.h include/asm-x86_64/percpu.h+4 -02 replies
23/61lock validator: coreinclude/linux/init_task.h include/linux/lockdep.h include/linux/sched.h +10 more+3064 -50 replies
24/61lock validator: procfskernel/Makefile kernel/lockdep_proc.c+348 -00 replies
25/61lock validator: design docsDocumentation/lockdep-design.txt+224 -01 reply
26/61lock validator: prove rwsem locking correctnessinclude/asm-i386/rwsem.h include/linux/rwsem-spinlock.h include/linux/rwsem.h +2 more+135 -160 replies
27/61lock validator: prove spinlock/rwlock locking correctnessinclude/asm-i386/spinlock.h include/linux/spinlock.h include/linux/spinlock_api_smp.h +9 more+269 -362 replies
28/61lock validator: prove mutex locking correctnessinclude/linux/mutex-debug.h include/linux/mutex.h kernel/mutex-debug.c +3 more+109 -120 replies
29/61lock validator: print all lock-types on SysRq-Ddrivers/char/sysrq.c+3 -10 replies
30/61lock validator: x86_64 early initarch/x86_64/kernel/head64.c+5 -00 replies
31/61lock validator: SMP alternatives workaroundarch/i386/kernel/alternative.c+10 -00 replies
32/61lock validator: do not recurse in printk()kernel/printk.c+16 -40 replies
33/61lock validator: disable NMI watchdog if CONFIG_LOCKDEParch/x86_64/kernel/nmi.c+12 -01 reply
34/61lock validator: special locking: bdevdrivers/md/md.c fs/block_dev.c include/linux/fs.h+112 -164 replies
35/61lock validator: special locking: direct-IOfs/direct-io.c+4 -20 replies
36/61lock validator: special locking: serialdrivers/serial/serial_core.c+8 -24 replies
37/61lock validator: special locking: dcachefs/dcache.c include/linux/dcache.h+15 -34 replies
38/61lock validator: special locking: i_mutexdrivers/usb/core/inode.c fs/namei.c include/linux/fs.h+27 -132 replies
39/61lock validator: special locking: s_lockfs/super.c include/linux/fs.h+10 -40 replies
40/61lock validator: special locking: futexkernel/futex.c+26 -180 replies
41/61lock validator: special locking: genirqkernel/irq/handle.c+13 -00 replies
42/61lock validator: special locking: kgdbkernel/kgdb.c+2 -20 replies
43/61lock validator: special locking: completionsinclude/linux/completion.h kernel/sched.c+9 -50 replies
44/61lock validator: special locking: waitqueuesinclude/linux/wait.h kernel/wait.c+18 -20 replies
45/61lock validator: special locking: mmmm/memory.c mm/mremap.c+2 -20 replies
46/61lock validator: special locking: slabmm/slab.c+48 -112 replies
47/61lock validator: special locking: skb_queue_head_init()include/linux/skbuff.h net/core/skbuff.c+10 -60 replies
48/61lock validator: special locking: timer.ckernel/timer.c+8 -10 replies
49/61lock validator: special locking: sched.ckernel/sched.c+8 -80 replies
50/61lock validator: special locking: hrtimer.ckernel/hrtimer.c+1 -16 replies
51/61lock validator: special locking: sock_lock_init()include/net/sock.h net/core/sock.c+23 -102 replies
52/61lock validator: special locking: af_unixinclude/net/af_unix.h net/unix/af_unix.c net/unix/garbage.c+12 -92 replies
53/61lock validator: special locking: bh_lock_sock()include/net/sock.h net/ipv4/tcp_ipv4.c+4 -10 replies
54/61lock validator: special locking: mmap_semkernel/exit.c kernel/fork.c+5 -20 replies
55/61lock validator: special locking: sb->s_umountfs/dcache.c+2 -12 replies
56/61lock validator: special locking: jbdfs/jbd/checkpoint.c fs/jbd/commit.c+2 -20 replies
57/61lock validator: special locking: posix-timerskernel/posix-timers.c+1 -10 replies
58/61lock validator: special locking: sch_generic.cnet/sched/sch_generic.c+1 -10 replies
59/61lock validator: special locking: xfrmnet/xfrm/xfrm_policy.c net/xfrm/xfrm_state.c+2 -21 reply
60/61lock validator: special locking: sound/core/seq/seq_ports.csound/core/seq/seq_ports.c+2 -20 replies
61/61lock validator: enable lock validator in Kconfiglib/Kconfig.debug+167 -04 replies

Reviews trailers per patch

1 of 61 patches has a Reviewed-by or Acked-by.

PatchTakashi Iwai
1/61
2/61
3/61A-b
4/61
5/61
6/61
7/61
8/61
9/61
10/61
11/61
12/61
13/61
14/61
15/61
16/61
17/61
18/61
19/61
20/61
21/61
22/61
23/61
24/61
25/61
26/61
27/61
28/61
29/61
30/61
31/61
32/61
33/61
34/61
35/61
36/61
37/61
38/61
39/61
40/61
41/61
42/61
43/61
44/61
45/61
46/61
47/61
48/61
49/61
50/61
51/61
52/61
53/61
54/61
55/61
56/61
57/61
58/61
59/61
60/61
61/61

Trailers given in replies are filled; those carried in the patches from earlier versions are outlined with dashes.

Read the v1 thread

Cover letter [patch 00/61] ANNOUNCE: lock validator -V1

We are pleased to announce the first release of the "lock dependency correctness validator" kernel debugging feature, which can be downloaded from:

http://redhat.com/~mingo/lockdep-patches/

The easiest way to try lockdep on a testbox is to apply the combo patch to 2.6.17-rc4-mm3. The patch order is:

http://kernel.org/pub/linux/kernel/v2.6/testing/linux-2.6.17-rc4.tar.bz2
http://kernel.org/pub/linux/kernel/people/akpm/patches/2.6/2.6.17-rc4/2.6.17-rc4-mm3/2.6.17-rc4-mm3.bz2
http://redhat.com/~mingo/lockdep-patches/lockdep-combo.patch

do 'make oldconfig' and accept all the defaults for new config options - reboot into the kernel and if everything goes well it should boot up fine and you should have /proc/lockdep and /proc/lockdep_stats files.

Typically if the lock validator finds some problem it will print out voluminous debug output that begins with "BUG: ..." and which syslog output can be used by kernel developers to figure out the precise locking scenario.

What does the lock validator do? It "observes" and maps all locking rules as they occur dynamically (as triggered by the kernel's natural use of spinlocks, rwlocks, mutexes and rwsems). Whenever the lock validator subsystem detects a new locking scenario, it validates this new rule against the existing set of rules. If this new rule is consistent with the existing set of rules then the new rule is added transparently and the kernel continues as normal. If the new rule could create a deadlock scenario then this condition is printed out.

When determining validity of locking, all possible "deadlock scenarios" are considered: assuming arbitrary number of CPUs, arbitrary irq context and task context constellations, running arbitrary combinations of all the existing locking scenarios. In a typical system this means millions of separate scenarios. This is why we call it a "locking correctness" validator - for all rules that are observed the lock validator proves it with mathematical certainty that a deadlock could not occur (assuming that the lock validator implementation itself is correct and its internal data structures are not corrupted by some other kernel subsystem). [see more details and conditionals of this statement in include/linux/lockdep.h and Documentation/lockdep-design.txt]

Furthermore, this "all possible scenarios" property of the validator also enables the finding of complex, highly unlikely multi-CPU multi-context races via single single-context rules, increasing the likelyhood of finding bugs drastically. In practical terms: the lock validator already found a bug in the upstream kernel that could only occur on systems with 3 or more CPUs, and which needed 3 very unlikely code sequences to occur at once on the 3 CPUs. That bug was found and reported on a single-CPU system (!). So in essence a race will be found "piecemail-wise", triggering all the necessary components for the race, without having to reproduce the race scenario itself! In its short existence the lock validator found and reported many bugs before they actually caused a real deadlock.

To further increase the efficiency of the validator, the mapping is not per "lock instance", but per "lock-type". For example, all struct inode objects in the kernel have inode->inotify_mutex. If there are 10,000 inodes cached, then there are 10,000 lock objects. But ->inotify_mutex is a single "lock type", and all locking activities that occur against ->inotify_mutex are "unified" into this single lock-type. The advantage of the lock-type approach is that all historical ->inotify_mutex uses are mapped into a single (and as narrow as possible) set of locking rules - regardless of how many different tasks or inode structures it took to build this set of rules. The set of rules persist during the lifetime of the kernel.

To see the rough magnitude of checking that the lock validator does, here's a portion of /proc/lockdep_stats, fresh after bootup:

lock-types: 694 [max: 2048]
direct dependencies: 1598 [max: 8192]
indirect dependencies: 17896
all direct dependencies: 16206
dependency chains: 1910 [max: 8192]
in-hardirq chains: 17
in-softirq chains: 105
in-process chains: 1065
stack-trace entries: 38761 [max: 131072]
combined max dependencies: 2033928
hardirq-safe locks: 24
hardirq-unsafe locks: 176
softirq-safe locks: 53
softirq-unsafe locks: 137
irq-safe locks: 59
irq-unsafe locks: 176

The lock validator has observed 1598 actual single-thread locking patterns, and has validated all possible 2033928 distinct locking scenarios.

More details about the design of the lock validator can be found in Documentation/lockdep-design.txt, which can also found at:

http://redhat.com/~mingo/lockdep-patches/lockdep-design.txt

The patchqueue consists of 61 patches, and the changes are quite extensive:

 215 files changed, 7693 insertions(+), 1247 deletions(-)

So be careful when testing.

We only plan to post the queue to lkml this time, we'll try to not flood lkml with future releases. The finegrained patch-queue can be also seen at:

http://redhat.com/~mingo/lockdep-patches/patches/

(the series file, with explanations about splitup categories of the patches can be found attached below.)

The lock validator has been build-tested with allyesconfig, and booted on x86 and x86_64. (Other architectures probably dont build/work yet.)

Comments, test-results, bug fixes, and improvements are welcome!

Ingo

# locking fixes (for bugs found by lockdep), not yet in mainline or -mm:

floppy-release-fix.patch
forcedeth-deadlock-fix.patch

# fixes for upstream that only triggers on lockdep:

sound_oss_emu10k1_midi-fix.patch
mutex-section-bug.patch

# locking subsystem debugging improvements:

warn-once.patch
add-module-address.patch

generic-lock-debugging.patch
locking-selftests.patch

spinlock-init-cleanups.patch
lock-init-improvement.patch
xfs-improve-mrinit-macro.patch

# stacktrace:

x86_64-beautify-stack-backtrace.patch
x86_64-document-stack-backtrace.patch
stacktrace.patch

x86_64-use-stacktrace-for-backtrace.patch

# irq-flags state tracing:

lockdep-fown-fixes.patch
lockdep-sk-callback-lock-fixes.patch
trace-irqflags.patch
trace-irqflags-cleanups-x86.patch
trace-irqflags-cleanups-x86_64.patch
local-irq-enable-in-hardirq.patch

# percpu subsystem feature needed for lockdep:

add-per-cpu-offset.patch

# lockdep subsystem core bits:

lockdep-core.patch
lockdep-proc.patch
lockdep-docs.patch

# make use of lockdep in locking subsystems:

lockdep-prove-rwsems.patch
lockdep-prove-spin_rwlocks.patch
lockdep-prove-mutexes.patch

# lockdep utility patches:

lockdep-print-types-in-sysrq.patch
lockdep-x86_64-early-init.patch
lockdep-i386-alternatives-off.patch
lockdep-printk-recursion.patch
lockdep-disable-nmi-watchdog.patch

# map all the locking details and quirks to lockdep:

lockdep-blockdev.patch
lockdep-direct-io.patch
lockdep-serial.patch
lockdep-dcache.patch
lockdep-namei.patch
lockdep-super.patch
lockdep-futex.patch
lockdep-genirq.patch
lockdep-kgdb.patch
lockdep-completions.patch
lockdep-waitqueue.patch
lockdep-mm.patch
lockdep-slab.patch

lockdep-skb_queue_head_init.patch
lockdep-timer.patch
lockdep-sched.patch
lockdep-hrtimer.patch
lockdep-sock.patch
lockdep-af_unix.patch
lockdep-lock_sock.patch
lockdep-mmap_sem.patch

lockdep-prune_dcache-workaround.patch
lockdep-jbd.patch
lockdep-posix-timers.patch
lockdep-sch_generic.patch
lockdep-xfrm.patch
lockdep-sound-seq-ports.patch

lockdep-enable-Kconfig.patch