FreeBSD/Linux Kernel Cross Reference
sys/Documentation/lockdep-design.txt

     Runtime locking correctness validator
     =====================================
     
     started by Ingo Molnar <mingo@redhat.com>
     additions by Arjan van de Ven <arjan@linux.intel.com>
     
     Lock-class
     ----------
     
    The basic object the validator operates upon is a 'class' of locks.
    
    A class of locks is a group of locks that are logically the same with
    respect to locking rules, even if the locks may have multiple (possibly
    tens of thousands of) instantiations. For example a lock in the inode
    struct is one class, while each inode has its own instantiation of that
    lock class.
    
    The validator tracks the 'state' of lock-classes, and it tracks
    dependencies between different lock-classes. The validator maintains a
    rolling proof that the state and the dependencies are correct.
    
    Unlike an lock instantiation, the lock-class itself never goes away: when
    a lock-class is used for the first time after bootup it gets registered,
    and all subsequent uses of that lock-class will be attached to this
    lock-class.
    
    State
    -----
    
    The validator tracks lock-class usage history into 4n + 1 separate state bits:
    
    - 'ever held in STATE context'
    - 'ever held as readlock in STATE context'
    - 'ever held with STATE enabled'
    - 'ever held as readlock with STATE enabled'
    
    Where STATE can be either one of (kernel/lockdep_states.h)
     - hardirq
     - softirq
     - reclaim_fs
    
    - 'ever used'                                       [ == !unused        ]
    
    When locking rules are violated, these state bits are presented in the
    locking error messages, inside curlies. A contrived example:
    
       modprobe/2287 is trying to acquire lock:
        (&sio_locks[i].lock){-.-...}, at: [<c02867fd>] mutex_lock+0x21/0x24
    
       but task is already holding lock:
        (&sio_locks[i].lock){-.-...}, at: [<c02867fd>] mutex_lock+0x21/0x24
    
    
    The bit position indicates STATE, STATE-read, for each of the states listed
    above, and the character displayed in each indicates:
    
       '.'  acquired while irqs disabled and not in irq context
       '-'  acquired in irq context
       '+'  acquired with irqs enabled
       '?'  acquired in irq context with irqs enabled.
    
    Unused mutexes cannot be part of the cause of an error.
    
    
    Single-lock state rules:
    ------------------------
    
    A softirq-unsafe lock-class is automatically hardirq-unsafe as well. The
    following states are exclusive, and only one of them is allowed to be
    set for any lock-class:
    
     <hardirq-safe> and <hardirq-unsafe>
     <softirq-safe> and <softirq-unsafe>
    
    The validator detects and reports lock usage that violate these
    single-lock state rules.
    
    Multi-lock dependency rules:
    ----------------------------
    
    The same lock-class must not be acquired twice, because this could lead
    to lock recursion deadlocks.
    
    Furthermore, two locks may not be taken in different order:
    
     <L1> -> <L2>
     <L2> -> <L1>
    
    because this could lead to lock inversion deadlocks. (The validator
    finds such dependencies in arbitrary complexity, i.e. there can be any
    other locking sequence between the acquire-lock operations, the
    validator will still track all dependencies between locks.)
    
    Furthermore, the following usage based lock dependencies are not allowed
    between any two lock-classes:
    
       <hardirq-safe>   ->  <hardirq-unsafe>
       <softirq-safe>   ->  <softirq-unsafe>
    
   The first rule comes from the fact the a hardirq-safe lock could be
   taken by a hardirq context, interrupting a hardirq-unsafe lock - and
   thus could result in a lock inversion deadlock. Likewise, a softirq-safe
   lock could be taken by an softirq context, interrupting a softirq-unsafe
   lock.
   
   The above rules are enforced for any locking sequence that occurs in the
   kernel: when acquiring a new lock, the validator checks whether there is
   any rule violation between the new lock and any of the held locks.
   
   When a lock-class changes its state, the following aspects of the above
   dependency rules are enforced:
   
   - if a new hardirq-safe lock is discovered, we check whether it
     took any hardirq-unsafe lock in the past.
   
   - if a new softirq-safe lock is discovered, we check whether it took
     any softirq-unsafe lock in the past.
   
   - if a new hardirq-unsafe lock is discovered, we check whether any
     hardirq-safe lock took it in the past.
   
   - if a new softirq-unsafe lock is discovered, we check whether any
     softirq-safe lock took it in the past.
   
   (Again, we do these checks too on the basis that an interrupt context
   could interrupt _any_ of the irq-unsafe or hardirq-unsafe locks, which
   could lead to a lock inversion deadlock - even if that lock scenario did
   not trigger in practice yet.)
   
   Exception: Nested data dependencies leading to nested locking
   -------------------------------------------------------------
   
   There are a few cases where the Linux kernel acquires more than one
   instance of the same lock-class. Such cases typically happen when there
   is some sort of hierarchy within objects of the same type. In these
   cases there is an inherent "natural" ordering between the two objects
   (defined by the properties of the hierarchy), and the kernel grabs the
   locks in this fixed order on each of the objects.
   
   An example of such an object hierarchy that results in "nested locking"
   is that of a "whole disk" block-dev object and a "partition" block-dev
   object; the partition is "part of" the whole device and as long as one
   always takes the whole disk lock as a higher lock than the partition
   lock, the lock ordering is fully correct. The validator does not
   automatically detect this natural ordering, as the locking rule behind
   the ordering is not static.
   
   In order to teach the validator about this correct usage model, new
   versions of the various locking primitives were added that allow you to
   specify a "nesting level". An example call, for the block device mutex,
   looks like this:
   
   enum bdev_bd_mutex_lock_class
   {
          BD_MUTEX_NORMAL,
          BD_MUTEX_WHOLE,
          BD_MUTEX_PARTITION
   };
   
    mutex_lock_nested(&bdev->bd_contains->bd_mutex, BD_MUTEX_PARTITION);
   
   In this case the locking is done on a bdev object that is known to be a
   partition.
   
   The validator treats a lock that is taken in such a nested fashion as a
   separate (sub)class for the purposes of validation.
   
   Note: When changing code to use the _nested() primitives, be careful and
   check really thoroughly that the hierarchy is correctly mapped; otherwise
   you can get false positives or false negatives.
   
   Proof of 100% correctness:
   --------------------------
   
   The validator achieves perfect, mathematical 'closure' (proof of locking
   correctness) in the sense that for every simple, standalone single-task
   locking sequence that occurred at least once during the lifetime of the
   kernel, the validator proves it with a 100% certainty that no
   combination and timing of these locking sequences can cause any class of
   lock related deadlock. [*]
   
   I.e. complex multi-CPU and multi-task locking scenarios do not have to
   occur in practice to prove a deadlock: only the simple 'component'
   locking chains have to occur at least once (anytime, in any
   task/context) for the validator to be able to prove correctness. (For
   example, complex deadlocks that would normally need more than 3 CPUs and
   a very unlikely constellation of tasks, irq-contexts and timings to
   occur, can be detected on a plain, lightly loaded single-CPU system as
   well!)
   
   This radically decreases the complexity of locking related QA of the
   kernel: what has to be done during QA is to trigger as many "simple"
   single-task locking dependencies in the kernel as possible, at least
   once, to prove locking correctness - instead of having to trigger every
   possible combination of locking interaction between CPUs, combined with
   every possible hardirq and softirq nesting scenario (which is impossible
   to do in practice).
   
   [*] assuming that the validator itself is 100% correct, and no other
       part of the system corrupts the state of the validator in any way.
       We also assume that all NMI/SMM paths [which could interrupt
       even hardirq-disabled codepaths] are correct and do not interfere
       with the validator. We also assume that the 64-bit 'chain hash'
       value is unique for every lock-chain in the system. Also, lock
       recursion must not be higher than 20.
   
   Performance:
   ------------
   
   The above rules require _massive_ amounts of runtime checking. If we did
   that for every lock taken and for every irqs-enable event, it would
   render the system practically unusably slow. The complexity of checking
   is O(N^2), so even with just a few hundred lock-classes we'd have to do
   tens of thousands of checks for every event.
   
   This problem is solved by checking any given 'locking scenario' (unique
   sequence of locks taken after each other) only once. A simple stack of
   held locks is maintained, and a lightweight 64-bit hash value is
   calculated, which hash is unique for every lock chain. The hash value,
   when the chain is validated for the first time, is then put into a hash
   table, which hash-table can be checked in a lockfree manner. If the
   locking chain occurs again later on, the hash table tells us that we
   dont have to validate the chain again.
   
   Troubleshooting:
   ----------------
   
   The validator tracks a maximum of MAX_LOCKDEP_KEYS number of lock classes.
   Exceeding this number will trigger the following lockdep warning:
   
           (DEBUG_LOCKS_WARN_ON(id >= MAX_LOCKDEP_KEYS))
   
   By default, MAX_LOCKDEP_KEYS is currently set to 8191, and typical
   desktop systems have less than 1,000 lock classes, so this warning
   normally results from lock-class leakage or failure to properly
   initialize locks.  These two problems are illustrated below:
   
   1.      Repeated module loading and unloading while running the validator
           will result in lock-class leakage.  The issue here is that each
           load of the module will create a new set of lock classes for
           that module's locks, but module unloading does not remove old
           classes (see below discussion of reuse of lock classes for why).
           Therefore, if that module is loaded and unloaded repeatedly,
           the number of lock classes will eventually reach the maximum.
   
   2.      Using structures such as arrays that have large numbers of
           locks that are not explicitly initialized.  For example,
           a hash table with 8192 buckets where each bucket has its own
           spinlock_t will consume 8192 lock classes -unless- each spinlock
           is explicitly initialized at runtime, for example, using the
           run-time spin_lock_init() as opposed to compile-time initializers
           such as __SPIN_LOCK_UNLOCKED().  Failure to properly initialize
           the per-bucket spinlocks would guarantee lock-class overflow.
           In contrast, a loop that called spin_lock_init() on each lock
           would place all 8192 locks into a single lock class.
   
           The moral of this story is that you should always explicitly
           initialize your locks.
   
   One might argue that the validator should be modified to allow
   lock classes to be reused.  However, if you are tempted to make this
   argument, first review the code and think through the changes that would
   be required, keeping in mind that the lock classes to be removed are
   likely to be linked into the lock-dependency graph.  This turns out to
   be harder to do than to say.
   
   Of course, if you do run out of lock classes, the next thing to do is
   to find the offending lock classes.  First, the following command gives
   you the number of lock classes currently in use along with the maximum:
   
           grep "lock-classes" /proc/lockdep_stats
   
   This command produces the following output on a modest system:
   
            lock-classes:                          748 [max: 8191]
   
   If the number allocated (748 above) increases continually over time,
   then there is likely a leak.  The following command can be used to
   identify the leaking lock classes:
   
           grep "BD" /proc/lockdep
   
   Run the command and save the output, then compare against the output from
   a later run of this command to identify the leakers.  This same output
   can also help you find situations where runtime lock initialization has
   been omitted.

Cache object: b76fad9d7c7c59d3b550737f43cb710a