Documentation/lockdep-design.txt

   1 Runtime locking correctness validator
   2 =====================================
   3
   4 started by Ingo Molnar <mingo@redhat.com>
   5 additions by Arjan van de Ven <arjan@linux.intel.com>
   6
   7 Lock-class
   8 ----------
   9
  10 The basic object the validator operates upon is a 'class' of locks.
  11
  12 A class of locks is a group of locks that are logically the same with
  13 respect to locking rules, even if the locks may have multiple (possibly
  14 tens of thousands of) instantiations. For example a lock in the inode
  15 struct is one class, while each inode has its own instantiation of that
  16 lock class.
  17
  18 The validator tracks the 'state' of lock-classes, and it tracks
  19 dependencies between different lock-classes. The validator maintains a
  20 rolling proof that the state and the dependencies are correct.
  21
  22 Unlike an lock instantiation, the lock-class itself never goes away: when
  23 a lock-class is used for the first time after bootup it gets registered,
  24 and all subsequent uses of that lock-class will be attached to this
  25 lock-class.
  26
  27 State
  28 -----
  29
  30 The validator tracks lock-class usage history into 4n + 1 separate state bits:
  31
  32 - 'ever held in STATE context'
  33 - 'ever head as readlock in STATE context'
  34 - 'ever head with STATE enabled'
  35 - 'ever head as readlock with STATE enabled'
  36
  37 Where STATE can be either one of (kernel/lockdep_states.h)
  38  - hardirq
  39  - softirq
  40  - reclaim_fs
  41
  42 - 'ever used'                                       [ == !unused        ]
  43
  44 When locking rules are violated, these state bits are presented in the
  45 locking error messages, inside curlies. A contrived example:
  46
  47    modprobe/2287 is trying to acquire lock:
  48     (&sio_locks[i].lock){-.-...}, at: [<c02867fd>] mutex_lock+0x21/0x24
  49
  50    but task is already holding lock:
  51     (&sio_locks[i].lock){-.-...}, at: [<c02867fd>] mutex_lock+0x21/0x24
  52
  53
  54 The bit position indicates STATE, STATE-read, for each of the states listed
  55 above, and the character displayed in each indicates:
  56
  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.
  61
  62 Unused mutexes cannot be part of the cause of an error.
  63
  64
  65 Single-lock state rules:
  66 ------------------------
  67
  68 A softirq-unsafe lock-class is automatically hardirq-unsafe as well. The
  69 following states are exclusive, and only one of them is allowed to be
  70 set for any lock-class:
  71
  72  <hardirq-safe> and <hardirq-unsafe>
  73  <softirq-safe> and <softirq-unsafe>
  74
  75 The validator detects and reports lock usage that violate these
  76 single-lock state rules.
  77
  78 Multi-lock dependency rules:
  79 ----------------------------
  80
  81 The same lock-class must not be acquired twice, because this could lead
  82 to lock recursion deadlocks.
  83
  84 Furthermore, two locks may not be taken in different order:
  85
  86  <L1> -> <L2>
  87  <L2> -> <L1>
  88
  89 because this could lead to lock inversion deadlocks. (The validator
  90 finds such dependencies in arbitrary complexity, i.e. there can be any
  91 other locking sequence between the acquire-lock operations, the
  92 validator will still track all dependencies between locks.)
  93
  94 Furthermore, the following usage based lock dependencies are not allowed
  95 between any two lock-classes:
  96
  97    <hardirq-safe>   ->  <hardirq-unsafe>
  98    <softirq-safe>   ->  <softirq-unsafe>
  99
 100 The first rule comes from the fact the a hardirq-safe lock could be
 101 taken by a hardirq context, interrupting a hardirq-unsafe lock - and
 102 thus could result in a lock inversion deadlock. Likewise, a softirq-safe
 103 lock could be taken by an softirq context, interrupting a softirq-unsafe
 104 lock.
 105
 106 The above rules are enforced for any locking sequence that occurs in the
 107 kernel: when acquiring a new lock, the validator checks whether there is
 108 any rule violation between the new lock and any of the held locks.
 109
 110 When a lock-class changes its state, the following aspects of the above
 111 dependency rules are enforced:
 112
 113 - if a new hardirq-safe lock is discovered, we check whether it
 114   took any hardirq-unsafe lock in the past.
 115
 116 - if a new softirq-safe lock is discovered, we check whether it took
 117   any softirq-unsafe lock in the past.
 118
 119 - if a new hardirq-unsafe lock is discovered, we check whether any
 120   hardirq-safe lock took it in the past.
 121
 122 - if a new softirq-unsafe lock is discovered, we check whether any
 123   softirq-safe lock took it in the past.
 124
 125 (Again, we do these checks too on the basis that an interrupt context
 126 could interrupt _any_ of the irq-unsafe or hardirq-unsafe locks, which
 127 could lead to a lock inversion deadlock - even if that lock scenario did
 128 not trigger in practice yet.)
 129
 130 Exception: Nested data dependencies leading to nested locking
 131 -------------------------------------------------------------
 132
 133 There are a few cases where the Linux kernel acquires more than one
 134 instance of the same lock-class. Such cases typically happen when there
 135 is some sort of hierarchy within objects of the same type. In these
 136 cases there is an inherent "natural" ordering between the two objects
 137 (defined by the properties of the hierarchy), and the kernel grabs the
 138 locks in this fixed order on each of the objects.
 139
 140 An example of such an object hierarchy that results in "nested locking"
 141 is that of a "whole disk" block-dev object and a "partition" block-dev
 142 object; the partition is "part of" the whole device and as long as one
 143 always takes the whole disk lock as a higher lock than the partition
 144 lock, the lock ordering is fully correct. The validator does not
 145 automatically detect this natural ordering, as the locking rule behind
 146 the ordering is not static.
 147
 148 In order to teach the validator about this correct usage model, new
 149 versions of the various locking primitives were added that allow you to
 150 specify a "nesting level". An example call, for the block device mutex,
 151 looks like this:
 152
 153 enum bdev_bd_mutex_lock_class
 154 {
 155        BD_MUTEX_NORMAL,
 156        BD_MUTEX_WHOLE,
 157        BD_MUTEX_PARTITION
 158 };
 159
 160  mutex_lock_nested(&bdev->bd_contains->bd_mutex, BD_MUTEX_PARTITION);
 161
 162 In this case the locking is done on a bdev object that is known to be a
 163 partition.
 164
 165 The validator treats a lock that is taken in such a nested fashion as a
 166 separate (sub)class for the purposes of validation.
 167
 168 Note: When changing code to use the _nested() primitives, be careful and
 169 check really thoroughly that the hierarchy is correctly mapped; otherwise
 170 you can get false positives or false negatives.
 171
 172 Proof of 100% correctness:
 173 --------------------------
 174
 175 The validator achieves perfect, mathematical 'closure' (proof of locking
 176 correctness) in the sense that for every simple, standalone single-task
 177 locking sequence that occurred at least once during the lifetime of the
 178 kernel, the validator proves it with a 100% certainty that no
 179 combination and timing of these locking sequences can cause any class of
 180 lock related deadlock. [*]
 181
 182 I.e. complex multi-CPU and multi-task locking scenarios do not have to
 183 occur in practice to prove a deadlock: only the simple 'component'
 184 locking chains have to occur at least once (anytime, in any
 185 task/context) for the validator to be able to prove correctness. (For
 186 example, complex deadlocks that would normally need more than 3 CPUs and
 187 a very unlikely constellation of tasks, irq-contexts and timings to
 188 occur, can be detected on a plain, lightly loaded single-CPU system as
 189 well!)
 190
 191 This radically decreases the complexity of locking related QA of the
 192 kernel: what has to be done during QA is to trigger as many "simple"
 193 single-task locking dependencies in the kernel as possible, at least
 194 once, to prove locking correctness - instead of having to trigger every
 195 possible combination of locking interaction between CPUs, combined with
 196 every possible hardirq and softirq nesting scenario (which is impossible
 197 to do in practice).
 198
 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.
 206
 207 Performance:
 208 ------------
 209
 210 The above rules require _massive_ amounts of runtime checking. If we did
 211 that for every lock taken and for every irqs-enable event, it would
 212 render the system practically unusably slow. The complexity of checking
 213 is O(N^2), so even with just a few hundred lock-classes we'd have to do
 214 tens of thousands of checks for every event.
 215
 216 This problem is solved by checking any given 'locking scenario' (unique
 217 sequence of locks taken after each other) only once. A simple stack of
 218 held locks is maintained, and a lightweight 64-bit hash value is
 219 calculated, which hash is unique for every lock chain. The hash value,
 220 when the chain is validated for the first time, is then put into a hash
 221 table, which hash-table can be checked in a lockfree manner. If the
 222 locking chain occurs again later on, the hash table tells us that we
 223 dont have to validate the chain again.