1Runtime locking correctness validator
   4started by Ingo Molnar <>
   5additions by Arjan van de Ven <>
  10The basic object the validator operates upon is a 'class' of locks.
  12A class of locks is a group of locks that are logically the same with
  13respect to locking rules, even if the locks may have multiple (possibly
  14tens of thousands of) instantiations. For example a lock in the inode
  15struct is one class, while each inode has its own instantiation of that
  16lock class.
  18The validator tracks the 'state' of lock-classes, and it tracks
  19dependencies between different lock-classes. The validator maintains a
  20rolling proof that the state and the dependencies are correct.
  22Unlike an lock instantiation, the lock-class itself never goes away: when
  23a lock-class is used for the first time after bootup it gets registered,
  24and all subsequent uses of that lock-class will be attached to this
  30The validator tracks lock-class usage history into 4n + 1 separate state bits:
  32- 'ever held in STATE context'
  33- 'ever held as readlock in STATE context'
  34- 'ever held with STATE enabled'
  35- 'ever held as readlock with STATE enabled'
  37Where STATE can be either one of (kernel/lockdep_states.h)
  38 - hardirq
  39 - softirq
  40 - reclaim_fs
  42- 'ever used'                                       [ == !unused        ]
  44When locking rules are violated, these state bits are presented in the
  45locking error messages, inside curlies. A contrived example:
  47   modprobe/2287 is trying to acquire lock:
  48    (&sio_locks[i].lock){-.-...}, at: [<c02867fd>] mutex_lock+0x21/0x24
  50   but task is already holding lock:
  51    (&sio_locks[i].lock){-.-...}, at: [<c02867fd>] mutex_lock+0x21/0x24
  54The bit position indicates STATE, STATE-read, for each of the states listed
  55above, and the character displayed in each indicates:
  57   '.'  acquired while irqs disabled and not in irq context
  58   '-'  acquired in irq context
  59   '+'  acquired with irqs enabled
  60   '?'  acquired in irq context with irqs enabled.
  62Unused mutexes cannot be part of the cause of an error.
  65Single-lock state rules:
  68A softirq-unsafe lock-class is automatically hardirq-unsafe as well. The
  69following states are exclusive, and only one of them is allowed to be
  70set for any lock-class:
  72 <hardirq-safe> and <hardirq-unsafe>
  73 <softirq-safe> and <softirq-unsafe>
  75The validator detects and reports lock usage that violate these
  76single-lock state rules.
  78Multi-lock dependency rules:
  81The same lock-class must not be acquired twice, because this could lead
  82to lock recursion deadlocks.
  84Furthermore, two locks may not be taken in different order:
  86 <L1> -> <L2>
  87 <L2> -> <L1>
  89because this could lead to lock inversion deadlocks. (The validator
  90finds such dependencies in arbitrary complexity, i.e. there can be any
  91other locking sequence between the acquire-lock operations, the
  92validator will still track all dependencies between locks.)
  94Furthermore, the following usage based lock dependencies are not allowed
  95between any two lock-classes:
  97   <hardirq-safe>   ->  <hardirq-unsafe>
  98   <softirq-safe>   ->  <softirq-unsafe>
 100The first rule comes from the fact the a hardirq-safe lock could be
 101taken by a hardirq context, interrupting a hardirq-unsafe lock - and
 102thus could result in a lock inversion deadlock. Likewise, a softirq-safe
 103lock could be taken by an softirq context, interrupting a softirq-unsafe
 106The above rules are enforced for any locking sequence that occurs in the
 107kernel: when acquiring a new lock, the validator checks whether there is
 108any rule violation between the new lock and any of the held locks.
 110When a lock-class changes its state, the following aspects of the above
 111dependency rules are enforced:
 113- if a new hardirq-safe lock is discovered, we check whether it
 114  took any hardirq-unsafe lock in the past.
 116- if a new softirq-safe lock is discovered, we check whether it took
 117  any softirq-unsafe lock in the past.
 119- if a new hardirq-unsafe lock is discovered, we check whether any
 120  hardirq-safe lock took it in the past.
 122- if a new softirq-unsafe lock is discovered, we check whether any
 123  softirq-safe lock took it in the past.
 125(Again, we do these checks too on the basis that an interrupt context
 126could interrupt _any_ of the irq-unsafe or hardirq-unsafe locks, which
 127could lead to a lock inversion deadlock - even if that lock scenario did
 128not trigger in practice yet.)
 130Exception: Nested data dependencies leading to nested locking
 133There are a few cases where the Linux kernel acquires more than one
 134instance of the same lock-class. Such cases typically happen when there
 135is some sort of hierarchy within objects of the same type. In these
 136cases there is an inherent "natural" ordering between the two objects
 137(defined by the properties of the hierarchy), and the kernel grabs the
 138locks in this fixed order on each of the objects.
 140An example of such an object hierarchy that results in "nested locking"
 141is that of a "whole disk" block-dev object and a "partition" block-dev
 142object; the partition is "part of" the whole device and as long as one
 143always takes the whole disk lock as a higher lock than the partition
 144lock, the lock ordering is fully correct. The validator does not
 145automatically detect this natural ordering, as the locking rule behind
 146the ordering is not static.
 148In order to teach the validator about this correct usage model, new
 149versions of the various locking primitives were added that allow you to
 150specify a "nesting level". An example call, for the block device mutex,
 151looks like this:
 153enum bdev_bd_mutex_lock_class
 155       BD_MUTEX_NORMAL,
 156       BD_MUTEX_WHOLE,
 160 mutex_lock_nested(&bdev->bd_contains->bd_mutex, BD_MUTEX_PARTITION);
 162In this case the locking is done on a bdev object that is known to be a
 165The validator treats a lock that is taken in such a nested fashion as a
 166separate (sub)class for the purposes of validation.
 168Note: When changing code to use the _nested() primitives, be careful and
 169check really thoroughly that the hierarchy is correctly mapped; otherwise
 170you can get false positives or false negatives.
 172Proof of 100% correctness:
 175The validator achieves perfect, mathematical 'closure' (proof of locking
 176correctness) in the sense that for every simple, standalone single-task
 177locking sequence that occurred at least once during the lifetime of the
 178kernel, the validator proves it with a 100% certainty that no
 179combination and timing of these locking sequences can cause any class of
 180lock related deadlock. [*]
 182I.e. complex multi-CPU and multi-task locking scenarios do not have to
 183occur in practice to prove a deadlock: only the simple 'component'
 184locking chains have to occur at least once (anytime, in any
 185task/context) for the validator to be able to prove correctness. (For
 186example, complex deadlocks that would normally need more than 3 CPUs and
 187a very unlikely constellation of tasks, irq-contexts and timings to
 188occur, can be detected on a plain, lightly loaded single-CPU system as
 191This radically decreases the complexity of locking related QA of the
 192kernel: what has to be done during QA is to trigger as many "simple"
 193single-task locking dependencies in the kernel as possible, at least
 194once, to prove locking correctness - instead of having to trigger every
 195possible combination of locking interaction between CPUs, combined with
 196every possible hardirq and softirq nesting scenario (which is impossible
 197to do in practice).
 199[*] assuming that the validator itself is 100% correct, and no other
 200    part of the system corrupts the state of the validator in any way.
 201    We also assume that all NMI/SMM paths [which could interrupt
 202    even hardirq-disabled codepaths] are correct and do not interfere
 203    with the validator. We also assume that the 64-bit 'chain hash'
 204    value is unique for every lock-chain in the system. Also, lock
 205    recursion must not be higher than 20.
 210The above rules require _massive_ amounts of runtime checking. If we did
 211that for every lock taken and for every irqs-enable event, it would
 212render the system practically unusably slow. The complexity of checking
 213is O(N^2), so even with just a few hundred lock-classes we'd have to do
 214tens of thousands of checks for every event.
 216This problem is solved by checking any given 'locking scenario' (unique
 217sequence of locks taken after each other) only once. A simple stack of
 218held locks is maintained, and a lightweight 64-bit hash value is
 219calculated, which hash is unique for every lock chain. The hash value,
 220when the chain is validated for the first time, is then put into a hash
 221table, which hash-table can be checked in a lockfree manner. If the
 222locking chain occurs again later on, the hash table tells us that we
 223dont have to validate the chain again.
 228The validator tracks a maximum of MAX_LOCKDEP_KEYS number of lock classes.
 229Exceeding this number will trigger the following lockdep warning:
 233By default, MAX_LOCKDEP_KEYS is currently set to 8191, and typical
 234desktop systems have less than 1,000 lock classes, so this warning
 235normally results from lock-class leakage or failure to properly
 236initialize locks.  These two problems are illustrated below:
 2381.      Repeated module loading and unloading while running the validator
 239        will result in lock-class leakage.  The issue here is that each
 240        load of the module will create a new set of lock classes for
 241        that module's locks, but module unloading does not remove old
 242        classes (see below discussion of reuse of lock classes for why).
 243        Therefore, if that module is loaded and unloaded repeatedly,
 244        the number of lock classes will eventually reach the maximum.
 2462.      Using structures such as arrays that have large numbers of
 247        locks that are not explicitly initialized.  For example,
 248        a hash table with 8192 buckets where each bucket has its own
 249        spinlock_t will consume 8192 lock classes -unless- each spinlock
 250        is explicitly initialized at runtime, for example, using the
 251        run-time spin_lock_init() as opposed to compile-time initializers
 252        such as __SPIN_LOCK_UNLOCKED().  Failure to properly initialize
 253        the per-bucket spinlocks would guarantelass must notoverf"184";nested guarantelass must notoverf"184mentation/lockdep-design.txt#L105" ikdep-design.txt#L113" iameline" name="L18">  18The validan.txt#L24ld lock3n such a0ntation/lockdepref="Documentation/lockdep-design.txt#L213" e" nn.txt#L252" id="e" name=        is explicitly initialized at runtime, 6" id="L2design.txt#L156" id="L152" cla2s="line" namep-desigpla namt#L"L250" cls21"> 221lockde0" class="lL113" iameline" name="L18">  18The validan.ave largeesign.txt#L157" id="L1572 clas2/a>   '.'  acquired while irqs disabled an2ion/lockd2p-design.txt#L158" id="L258" c2ass="line" na="linmo"L146f235"> 1" clasxt#L24871" shdesiglockdepign.txt#L2'.'  acquired while irqs disabled an2iach buckeL159" class="line" name=2L159"25tion/lockdep-design.txt#71"r109
 260 mutex_lock_nested(&bdev->bd_contains2>bd_mu2ex, BD_MUTEX_PARTITION);2  mutex_lock_nested(&bdev->bd_contains2&o compile62" class="line" name="L262"> 261ss="line"ss="line-desigass="="L2Howclast#L2471" " idn.tptass="lma 152ep-desievilinid="L1dclass="lin" idign.te="L224"#L111" id="L187 mutex_lock_nested(&bdev->bd_contains2&elass mus64" id="L164" class="lin2" nam2="L164sigas" clas, keepid="L1nmind04" class=line"ss="line-desigas 242d " i mutex_lock_nested(&bdev->bd_contains2&txt#L24ld65" class="line" name="L265"> 265sign.tx-desiglinlass="l05" ikdds="line" ngraphss="lsxt#urd="Llass>tens of thousands of checks for every event.
such a ne2ted fashion as a
   '.'  acquired while irqs disabled an268" id="L268" class="line" name="L268"> 268Of="L2rset#L2471" sigkde"Llas#L245" id="L245,"L109" xass="ame="L="L1a mutex_lock_nested(&bdev->bd_contains2&ach buckes, be careful and
 1on/lockde 245
        (DEBUG_LOCKS_WARN_ON(id >= MAX_LOC72" id="L272" class="line" name="L272"> 27mentation/locg4">ame="L1lass="line" d="L143/amecRN_ON(id 38 1dessign.t>
 275The validator achieves perfect, mathematical2'clos2re' (proof of lockin2
   '.'  acquired while irqs disabled an2during th2 lifetime of the
sign.txt50">c-desi(748 lockddesit#L192" /locinne""li'.'  acquired while irqs disabled an2dach buckety that no
l05"0" name="L2> 229
The same lock-class must not be acquired twice,282" id="L282" class="line" name="L282"> 28mentation/locg4">ame="L1BDd="L143/amecRN_ON(id same lock-class must not be acquired twice,28ntation/2 do not have to
By default, MAX_LOCKDEP_KEYS is currently sethe simple2'component'
l05"0" ersss="lsxtame="ola"L2By default, MAX_LOCKDEP_KEYS is currently seth#39;clos2rectness. (For

Tline"iginL14LXR7" idw-des-designhref="Doc,ss="liexperitatiol L128" id-dehref="Docmailto:lx2@l">lx2@l cla.noon/l.
lx2.l nadnameoe="L1-dehref="Dochttp://www.laspill-l">Raspill4" came ASon/l,sp-deidtxt#L2L clas250" lt" id="L292"> 92 s1loccecume5.