- 03 Jul, 2006 40 commits
-
-
Ingo Molnar authored
Use the lock validator framework to prove spinlock and rwlock locking correctness. Signed-off-by:
Ingo Molnar <mingo@elte.hu> Signed-off-by:
Arjan van de Ven <arjan@linux.intel.com> Signed-off-by:
Andrew Morton <akpm@osdl.org> Signed-off-by:
Linus Torvalds <torvalds@osdl.org>
-
Ingo Molnar authored
Use the lock validator framework to prove rwsem locking correctness. Signed-off-by:
-
Ingo Molnar authored
Lock validator /proc/lockdep and /proc/lockdep_stats support. (FIXME: should go into debugfs) Signed-off-by:
-
Ingo Molnar authored
Lock validator design documentation. Signed-off-by:
-
Ingo Molnar authored
From: Ingo Molnar <mingo@elte.hu> lockdep so far only allowed read-recursion for the same lock instance. This is enough in the overwhelming majority of cases, but a hostap case triggered and reported by Miles Lane relies on same-class different-instance recursion. So we relax the restriction on read-lock recursion. (This change does not allow rwsem read-recursion, which is still forbidden.) Signed-off-by:
-
Ingo Molnar authored
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-class". 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-class. The advantage of the lock-class 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-classes: 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 [bunk@stusta.de: cleanups] Signed-off-by:
Adrian Bunk <bunk@stusta.de> Signed-off-by:
-
Ingo Molnar authored
Introduce DEBUG_LOCKING_API_SELFTESTS, which uses the generic lock debugging code's silent-failure feature to run a matrix of testcases. There are 210 testcases currently: +----------------------- | Locking API testsuite: +------------------------------+------+------+------+------+------+------+ | spin |wlock |rlock |mutex | wsem | rsem | -------------------------------+------+------+------+------+------+------+ A-A deadlock: ok | ok | ok | ok | ok | ok | A-B-B-A deadlock: ok | ok | ok | ok | ok | ok | A-B-B-C-C-A deadlock: ok | ok | ok | ok | ok | ok | A-B-C-A-B-C deadlock: ok | ok | ok | ok | ok | ok | A-B-B-C-C-D-D-A deadlock: ok | ok | ok | ok | ok | ok | A-B-C-D-B-D-D-A deadlock: ok | ok | ok | ok | ok | ok | A-B-C-D-B-C-D-A deadlock: ok | ok | ok | ok | ok | ok | double unlock: ok | ok | ok | ok | ok | ok | bad unlock order: ok | ok | ok | ok | ok | ok | --------------------------------------+------+------+------+------+------+ recursive read-lock: | ok | | ok | --------------------------------------+------+------+------+------+------+ non-nested unlock: ok | ok | ok | ok | --------------------------------------+------+------+------+ hard-irqs-on + irq-safe-A/12: ok | ok | ok | soft-irqs-on + irq-safe-A/12: ok | ok | ok | hard-irqs-on + irq-safe-A/21: ok | ok | ok | soft-irqs-on + irq-safe-A/21: ok | ok | ok | sirq-safe-A => hirqs-on/12: ok | ok | ok | sirq-safe-A => hirqs-on/21: ok | ok | ok | hard-safe-A + irqs-on/12: ok | ok | ok | soft-safe-A + irqs-on/12: ok | ok | ok | hard-safe-A + irqs-on/21: ok | ok | ok | soft-safe-A + irqs-on/21: ok | ok | ok | hard-safe-A + unsafe-B #1/123: ok | ok | ok | soft-safe-A + unsafe-B #1/123: ok | ok | ok | hard-safe-A + unsafe-B #1/132: ok | ok | ok | soft-safe-A + unsafe-B #1/132: ok | ok | ok | hard-safe-A + unsafe-B #1/213: ok | ok | ok | soft-safe-A + unsafe-B #1/213: ok | ok | ok | hard-safe-A + unsafe-B #1/231: ok | ok | ok | soft-safe-A + unsafe-B #1/231: ok | ok | ok | hard-safe-A + unsafe-B #1/312: ok | ok | ok | soft-safe-A + unsafe-B #1/312: ok | ok | ok | hard-safe-A + unsafe-B #1/321: ok | ok | ok | soft-safe-A + unsafe-B #1/321: ok | ok | ok | hard-safe-A + unsafe-B #2/123: ok | ok | ok | soft-safe-A + unsafe-B #2/123: ok | ok | ok | hard-safe-A + unsafe-B #2/132: ok | ok | ok | soft-safe-A + unsafe-B #2/132: ok | ok | ok | hard-safe-A + unsafe-B #2/213: ok | ok | ok | soft-safe-A + unsafe-B #2/213: ok | ok | ok | hard-safe-A + unsafe-B #2/231: ok | ok | ok | soft-safe-A + unsafe-B #2/231: ok | ok | ok | hard-safe-A + unsafe-B #2/312: ok | ok | ok | soft-safe-A + unsafe-B #2/312: ok | ok | ok | hard-safe-A + unsafe-B #2/321: ok | ok | ok | soft-safe-A + unsafe-B #2/321: ok | ok | ok | hard-irq lock-inversion/123: ok | ok | ok | soft-irq lock-inversion/123: ok | ok | ok | hard-irq lock-inversion/132: ok | ok | ok | soft-irq lock-inversion/132: ok | ok | ok | hard-irq lock-inversion/213: ok | ok | ok | soft-irq lock-inversion/213: ok | ok | ok | hard-irq lock-inversion/231: ok | ok | ok | soft-irq lock-inversion/231: ok | ok | ok | hard-irq lock-inversion/312: ok | ok | ok | soft-irq lock-inversion/312: ok | ok | ok | hard-irq lock-inversion/321: ok | ok | ok | soft-irq lock-inversion/321: ok | ok | ok | hard-irq read-recursion/123: ok | soft-irq read-recursion/123: ok | hard-irq read-recursion/132: ok | soft-irq read-recursion/132: ok | hard-irq read-recursion/213: ok | soft-irq read-recursion/213: ok | hard-irq read-recursion/231: ok | soft-irq read-recursion/231: ok | hard-irq read-recursion/312: ok | soft-irq read-recursion/312: ok | hard-irq read-recursion/321: ok | soft-irq read-recursion/321: ok | --------------------------------+-----+---------------- Good, all 210 testcases passed! | --------------------------------+ Signed-off-by: -
Heiko Carstens authored
irqtrace support for s390. Signed-off-by:
Heiko Carstens <heiko.carstens@de.ibm.com> Signed-off-by:
-
Ingo Molnar authored
Clean up the x86-64 irqflags.h file: - macro => inline function transformation - simplifications - style fixes Signed-off-by:
-
Ingo Molnar authored
Add irqflags-tracing support to x86_64. [akpm@osdl.org: build fix] Signed-off-by:
-
Ingo Molnar authored
Clean up the x86 irqflags.h file: - macro => inline function transformation - simplifications - style fixes Signed-off-by:
-
Ingo Molnar authored
Add irqflags-tracing support to i386. Signed-off-by:
-
Ingo Molnar authored
Add Documentation/irqflags-tracing.txt. Signed-off-by:
-
Ingo Molnar authored
Accurate hard-IRQ-flags and softirq-flags state tracing. This allows us to attach extra functionality to IRQ flags on/off events (such as trace-on/off). Signed-off-by:
-
Heiko Carstens authored
stacktrace interface for s390 as needed by lock validator. [clg@fr.ibm.com: build fix] Signed-off-by:
Cedric Le Goater <clg@fr.ibm.com> Signed-off-by:
-
Ingo Molnar authored
Framework to generate and save stacktraces quickly, without printing anything to the console. x86_64 support. Signed-off-by:
-
Ingo Molnar authored
Framework to generate and save stacktraces quickly, without printing anything to the console. i386 support. Signed-off-by:
-
Heiko Carstens authored
CONFIG_FRAME_POINTER support for s390. Signed-off-by:
-
Ingo Molnar authored
Framework to generate and save stacktraces quickly, without printing anything to the console. Signed-off-by:
-
Ingo Molnar authored
Remove CONFIG_STACK_BACKTRACE_COLS. This feature didnt work out: instead of making kernel debugging more efficient, it produces much harder to read stacktraces! Check out this trace for example: http://static.flickr.com/47/158326090_35d0129147_b_d.jpg That backtrace could have been printed much nicer as a one-entry-per-line thing, taking the same amount of screen real-estate. Plus we remove 30 lines of kernel code as well. Signed-off-by:
-
Ingo Molnar authored
Document stack frame nesting internals some more. Signed-off-by:
-
Ingo Molnar authored
Beautify x86_64 stacktraces to be more readable. Signed-off-by:
Andi Kleen <ak@muc.de> Signed-off-by:
-
Ingo Molnar authored
Locking init improvement: - introduce and use __SPIN_LOCK_UNLOCKED for array initializations, to pass in the name string of locks, used by debugging Signed-off-by:
-
Ingo Molnar authored
Work around weird section nesting build bug causing smp-alternatives failures under certain circumstances. Signed-off-by:
-
Ingo Molnar authored
Generic lock debugging: - generalized lock debugging framework. For example, a bug in one lock subsystem turns off debugging in all lock subsystems. - got rid of the caller address passing (__IP__/__IP_DECL__/etc.) from the mutex/rtmutex debugging code: it caused way too much prototype hackery, and lockdep will give the same information anyway. - ability to do silent tests - check lock freeing in vfree too. - more finegrained debugging options, to allow distributions to turn off more expensive debugging features. There's no separate 'held mutexes' list anymore - but there's a 'held locks' stack within lockdep, which unifies deadlock detection across all lock classes. (this is independent of the lockdep validation stuff - lockdep first checks whether we are holding a lock already) Here are the current debugging options: CONFIG_DEBUG_MUTEXES=y CONFIG_DEBUG_LOCK_ALLOC=y which do: config DEBUG_MUTEXES bool "Mutex debugging, basic checks" config DEBUG_LOCK_ALLOC bool "Detect incorrect freeing of live mutexes" Signed-off-by: -
Ingo Molnar authored
With the lock validator we detect mutex deadlocks (and more), the mutex deadlock checking code is both redundant and slower. So remove it. Signed-off-by:
-
Ingo Molnar authored
cleanup: remove unused DEBUG_BUG_ON() defines. Signed-off-by:
-
Ingo Molnar authored
Rename DEBUG_WARN_ON() to the less generic DEBUG_LOCKS_WARN_ON() name, so that it's clear that this is a lock-debugging internal mechanism. Signed-off-by:
-
Ingo Molnar authored
RWSEM_DEBUG used to be a printk based 'tracing' facility, probably used for very early prototypes of the rwsem code. Remove it. Signed-off-by:
-
Ingo Molnar authored
Clean up rwsems. Signed-off-by:
-
Ingo Molnar authored
lockdep needs to have the waitqueue lock initialized for on-stack waitqueues implicitly initialized by DECLARE_COMPLETION(). Introduce the API. Signed-off-by:
-
Ingo Molnar authored
Introduce local_irq_enable_in_hardirq() API. It is currently aliased to local_irq_enable(), hence has no functional effects. This API will be used by lockdep, but even without lockdep this will better document places in the kernel where a hardirq context enables hardirqs. Signed-off-by:
-
Ingo Molnar authored
lockdep wants to use the disable_irq()/enable_irq() prototypes before they are provied by the platform's asm/irq.h. So move them out of the CONFIG_GENERIC_HARDIRQS define - all architectures have a common prototype for this anyway. Add special lockdep variants of irq line disabling/enabling. These should be used for locking constructs that know that a particular irq context which is disabled, and which is the only irq-context user of a lock, that it's safe to take the lock in the irq-disabled section without disabling hardirqs. [akpm@osdl.org: build fix] Signed-off-by:
-
Ingo Molnar authored
Add the per_cpu_offset() generic method. (used by the lock validator) Signed-off-by:
-
Heiko Carstens authored
Provide a common print_ip_sym() function that prints the passed instruction pointer as well as the symbol belonging to it. Avoids adding a bunch of #ifdef CONFIG_64BIT in order to get the printk format right on 32/64 bit platforms. Acked-by:
-
Ingo Molnar authored
Add is_module_address() method - to be used by lockdep. Signed-off-by:
-
Heiko Carstens authored
s390's console_init must enable interrupts, but early_boot_irqs_on() gets called later. To avoid problems move console_init() after local_irq_enable(). Signed-off-by:
-
Ingo Molnar authored
The lock validator triggered a number of bugs in the floppy driver, all related to the floppy driver allocating and freeing irq and dma resources from interrupt context. The initial solution was to use schedule_work() to push this into process context, but this caused further problems: for example the current floppy driver in -mm2 is totally broken and all floppy commands time out with an error. (as reported by Barry K. Nathan) This patch tries another solution: simply get rid of all that dynamic IRQ and DMA allocation/freeing. I doubt it made much sense back in the heydays of floppies (if two devices raced for DMA or IRQ resources then we didnt handle those cases too gracefully anyway), and today it makes near zero sense. So the new code does the simplest and most straightforward thing: allocate IRQ and DMA resources at module init time, and free them at module removal time. Dont try to release while the driver is operational. This, besides making the floppy driver functional again has an added bonus, floppy IRQ stats are finally persistent and visible in /proc/interrupts: 6: 63 XT-PIC-level floppy Besides normal floppy IO i have also tested IO error handling, motor-off timeouts, etc. - and everything seems to be working fine. Signed-off-by:
-
Andrew Morton authored
sound/sparc/amd7930.c: In function 'amd7930_attach_common': sound/sparc/amd7930.c:1040: warning: format '%08lx' expects type 'long unsigned int', but argument 5 has type 'resource_size_t' sound/sparc/cs4231.c:2043: warning: format '%016lx' expects type 'long unsigned int', but argument 5 has type 'resource_size_t' sound/sparc/dbri.c: In function 'dbri_attach': sound/sparc/dbri.c:2650: warning: format '%016lx' expects type 'long unsigned int', but argument 5 has type 'resource_size_t' Signed-off-by:
-
Andrew Morton authored
drivers/input/serio/i8042-sparcio.h:91: error: '__mod_of_device_table' aliased to undefined symbol 'i8042_match' Cc: Dmitry Torokhov <dtor_core@ameritech.net> DESC sparc: resource warning fix EDESC From: Andrew Morton <akpm@osdl.org> sound/sparc/amd7930.c: In function 'amd7930_attach_common': sound/sparc/amd7930.c:1040: warning: format '%08lx' expects type 'long unsigned int', but argument 5 has type 'resource_size_t' Signed-off-by:
-
