• Ingo Molnar's avatar
    [PATCH] lockdep: core · fbb9ce95
    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: default avatarIngo Molnar <mingo@elte.hu>
    Signed-off-by: default avatarArjan van de Ven <arjan@linux.intel.com>
    Signed-off-by: default avatarAdrian Bunk <bunk@stusta.de>
    Signed-off-by: default avatarAndrew Morton <akpm@osdl.org>
    Signed-off-by: default avatarLinus Torvalds <torvalds@osdl.org>
    fbb9ce95
sched.h 47.5 KB