~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/Documentation/locking/lockdep-design.rst

Version: ~ [ linux-6.12-rc7 ] ~ [ linux-6.11.7 ] ~ [ linux-6.10.14 ] ~ [ linux-6.9.12 ] ~ [ linux-6.8.12 ] ~ [ linux-6.7.12 ] ~ [ linux-6.6.60 ] ~ [ linux-6.5.13 ] ~ [ linux-6.4.16 ] ~ [ linux-6.3.13 ] ~ [ linux-6.2.16 ] ~ [ linux-6.1.116 ] ~ [ linux-6.0.19 ] ~ [ linux-5.19.17 ] ~ [ linux-5.18.19 ] ~ [ linux-5.17.15 ] ~ [ linux-5.16.20 ] ~ [ linux-5.15.171 ] ~ [ linux-5.14.21 ] ~ [ linux-5.13.19 ] ~ [ linux-5.12.19 ] ~ [ linux-5.11.22 ] ~ [ linux-5.10.229 ] ~ [ linux-5.9.16 ] ~ [ linux-5.8.18 ] ~ [ linux-5.7.19 ] ~ [ linux-5.6.19 ] ~ [ linux-5.5.19 ] ~ [ linux-5.4.285 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.323 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.336 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.337 ] ~ [ linux-4.4.302 ] ~ [ linux-3.10.108 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.12 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

Diff markup

Differences between /Documentation/locking/lockdep-design.rst (Version linux-6.12-rc7) and /Documentation/locking/lockdep-design.rst (Version linux-6.6.60)


  1 Runtime locking correctness validator               1 Runtime locking correctness validator
  2 =====================================               2 =====================================
  3                                                     3 
  4 started by Ingo Molnar <mingo@redhat.com>            4 started by Ingo Molnar <mingo@redhat.com>
  5                                                     5 
  6 additions by Arjan van de Ven <arjan@linux.inte      6 additions by Arjan van de Ven <arjan@linux.intel.com>
  7                                                     7 
  8 Lock-class                                          8 Lock-class
  9 ----------                                          9 ----------
 10                                                    10 
 11 The basic object the validator operates upon i     11 The basic object the validator operates upon is a 'class' of locks.
 12                                                    12 
 13 A class of locks is a group of locks that are      13 A class of locks is a group of locks that are logically the same with
 14 respect to locking rules, even if the locks ma     14 respect to locking rules, even if the locks may have multiple (possibly
 15 tens of thousands of) instantiations. For exam     15 tens of thousands of) instantiations. For example a lock in the inode
 16 struct is one class, while each inode has its      16 struct is one class, while each inode has its own instantiation of that
 17 lock class.                                        17 lock class.
 18                                                    18 
 19 The validator tracks the 'usage state' of lock     19 The validator tracks the 'usage state' of lock-classes, and it tracks
 20 the dependencies between different lock-classe     20 the dependencies between different lock-classes. Lock usage indicates
 21 how a lock is used with regard to its IRQ cont     21 how a lock is used with regard to its IRQ contexts, while lock
 22 dependency can be understood as lock order, wh     22 dependency can be understood as lock order, where L1 -> L2 suggests that
 23 a task is attempting to acquire L2 while holdi     23 a task is attempting to acquire L2 while holding L1. From lockdep's
 24 perspective, the two locks (L1 and L2) are not     24 perspective, the two locks (L1 and L2) are not necessarily related; that
 25 dependency just means the order ever happened.     25 dependency just means the order ever happened. The validator maintains a
 26 continuing effort to prove lock usages and dep     26 continuing effort to prove lock usages and dependencies are correct or
 27 the validator will shoot a splat if incorrect.     27 the validator will shoot a splat if incorrect.
 28                                                    28 
 29 A lock-class's behavior is constructed by its      29 A lock-class's behavior is constructed by its instances collectively:
 30 when the first instance of a lock-class is use     30 when the first instance of a lock-class is used after bootup the class
 31 gets registered, then all (subsequent) instanc     31 gets registered, then all (subsequent) instances will be mapped to the
 32 class and hence their usages and dependencies      32 class and hence their usages and dependencies will contribute to those of
 33 the class. A lock-class does not go away when      33 the class. A lock-class does not go away when a lock instance does, but
 34 it can be removed if the memory space of the l     34 it can be removed if the memory space of the lock class (static or
 35 dynamic) is reclaimed, this happens for exampl     35 dynamic) is reclaimed, this happens for example when a module is
 36 unloaded or a workqueue is destroyed.              36 unloaded or a workqueue is destroyed.
 37                                                    37 
 38 State                                              38 State
 39 -----                                              39 -----
 40                                                    40 
 41 The validator tracks lock-class usage history      41 The validator tracks lock-class usage history and divides the usage into
 42 (4 usages * n STATEs + 1) categories:              42 (4 usages * n STATEs + 1) categories:
 43                                                    43 
 44 where the 4 usages can be:                         44 where the 4 usages can be:
 45                                                    45 
 46 - 'ever held in STATE context'                     46 - 'ever held in STATE context'
 47 - 'ever held as readlock in STATE context'         47 - 'ever held as readlock in STATE context'
 48 - 'ever held with STATE enabled'                   48 - 'ever held with STATE enabled'
 49 - 'ever held as readlock with STATE enabled'       49 - 'ever held as readlock with STATE enabled'
 50                                                    50 
 51 where the n STATEs are coded in kernel/locking     51 where the n STATEs are coded in kernel/locking/lockdep_states.h and as of
 52 now they include:                                  52 now they include:
 53                                                    53 
 54 - hardirq                                          54 - hardirq
 55 - softirq                                          55 - softirq
 56                                                    56 
 57 where the last 1 category is:                      57 where the last 1 category is:
 58                                                    58 
 59 - 'ever used'                                      59 - 'ever used'                                       [ == !unused        ]
 60                                                    60 
 61 When locking rules are violated, these usage b     61 When locking rules are violated, these usage bits are presented in the
 62 locking error messages, inside curlies, with a     62 locking error messages, inside curlies, with a total of 2 * n STATEs bits.
 63 A contrived example::                              63 A contrived example::
 64                                                    64 
 65    modprobe/2287 is trying to acquire lock:        65    modprobe/2287 is trying to acquire lock:
 66     (&sio_locks[i].lock){-.-.}, at: [<c02867fd     66     (&sio_locks[i].lock){-.-.}, at: [<c02867fd>] mutex_lock+0x21/0x24
 67                                                    67 
 68    but task is already holding lock:               68    but task is already holding lock:
 69     (&sio_locks[i].lock){-.-.}, at: [<c02867fd     69     (&sio_locks[i].lock){-.-.}, at: [<c02867fd>] mutex_lock+0x21/0x24
 70                                                    70 
 71                                                    71 
 72 For a given lock, the bit positions from left      72 For a given lock, the bit positions from left to right indicate the usage
 73 of the lock and readlock (if exists), for each     73 of the lock and readlock (if exists), for each of the n STATEs listed
 74 above respectively, and the character displaye     74 above respectively, and the character displayed at each bit position
 75 indicates:                                         75 indicates:
 76                                                    76 
 77    ===  ======================================     77    ===  ===================================================
 78    '.'  acquired while irqs disabled and not i     78    '.'  acquired while irqs disabled and not in irq context
 79    '-'  acquired in irq context                    79    '-'  acquired in irq context
 80    '+'  acquired with irqs enabled                 80    '+'  acquired with irqs enabled
 81    '?'  acquired in irq context with irqs enab     81    '?'  acquired in irq context with irqs enabled.
 82    ===  ======================================     82    ===  ===================================================
 83                                                    83 
 84 The bits are illustrated with an example::         84 The bits are illustrated with an example::
 85                                                    85 
 86     (&sio_locks[i].lock){-.-.}, at: [<c02867fd     86     (&sio_locks[i].lock){-.-.}, at: [<c02867fd>] mutex_lock+0x21/0x24
 87                          ||||                      87                          ||||
 88                          ||| \-> softirq disab     88                          ||| \-> softirq disabled and not in softirq context
 89                          || \--> acquired in s     89                          || \--> acquired in softirq context
 90                          | \---> hardirq disab     90                          | \---> hardirq disabled and not in hardirq context
 91                           \----> acquired in h     91                           \----> acquired in hardirq context
 92                                                    92 
 93                                                    93 
 94 For a given STATE, whether the lock is ever ac     94 For a given STATE, whether the lock is ever acquired in that STATE
 95 context and whether that STATE is enabled yiel     95 context and whether that STATE is enabled yields four possible cases as
 96 shown in the table below. The bit character is     96 shown in the table below. The bit character is able to indicate which
 97 exact case is for the lock as of the reporting     97 exact case is for the lock as of the reporting time.
 98                                                    98 
 99   +--------------+-------------+--------------     99   +--------------+-------------+--------------+
100   |              | irq enabled | irq disabled     100   |              | irq enabled | irq disabled |
101   +--------------+-------------+--------------    101   +--------------+-------------+--------------+
102   | ever in irq  |     '?'     |      '-'         102   | ever in irq  |     '?'     |      '-'     |
103   +--------------+-------------+--------------    103   +--------------+-------------+--------------+
104   | never in irq |     '+'     |      '.'         104   | never in irq |     '+'     |      '.'     |
105   +--------------+-------------+--------------    105   +--------------+-------------+--------------+
106                                                   106 
107 The character '-' suggests irq is disabled bec    107 The character '-' suggests irq is disabled because if otherwise the
108 character '?' would have been shown instead. S    108 character '?' would have been shown instead. Similar deduction can be
109 applied for '+' too.                              109 applied for '+' too.
110                                                   110 
111 Unused locks (e.g., mutexes) cannot be part of    111 Unused locks (e.g., mutexes) cannot be part of the cause of an error.
112                                                   112 
113                                                   113 
114 Single-lock state rules:                          114 Single-lock state rules:
115 ------------------------                          115 ------------------------
116                                                   116 
117 A lock is irq-safe means it was ever used in a    117 A lock is irq-safe means it was ever used in an irq context, while a lock
118 is irq-unsafe means it was ever acquired with     118 is irq-unsafe means it was ever acquired with irq enabled.
119                                                   119 
120 A softirq-unsafe lock-class is automatically h    120 A softirq-unsafe lock-class is automatically hardirq-unsafe as well. The
121 following states must be exclusive: only one o    121 following states must be exclusive: only one of them is allowed to be set
122 for any lock-class based on its usage::           122 for any lock-class based on its usage::
123                                                   123 
124  <hardirq-safe> or <hardirq-unsafe>               124  <hardirq-safe> or <hardirq-unsafe>
125  <softirq-safe> or <softirq-unsafe>               125  <softirq-safe> or <softirq-unsafe>
126                                                   126 
127 This is because if a lock can be used in irq c    127 This is because if a lock can be used in irq context (irq-safe) then it
128 cannot be ever acquired with irq enabled (irq-    128 cannot be ever acquired with irq enabled (irq-unsafe). Otherwise, a
129 deadlock may happen. For example, in the scena    129 deadlock may happen. For example, in the scenario that after this lock
130 was acquired but before released, if the conte    130 was acquired but before released, if the context is interrupted this
131 lock will be attempted to acquire twice, which    131 lock will be attempted to acquire twice, which creates a deadlock,
132 referred to as lock recursion deadlock.           132 referred to as lock recursion deadlock.
133                                                   133 
134 The validator detects and reports lock usage t    134 The validator detects and reports lock usage that violates these
135 single-lock state rules.                          135 single-lock state rules.
136                                                   136 
137 Multi-lock dependency rules:                      137 Multi-lock dependency rules:
138 ----------------------------                      138 ----------------------------
139                                                   139 
140 The same lock-class must not be acquired twice    140 The same lock-class must not be acquired twice, because this could lead
141 to lock recursion deadlocks.                      141 to lock recursion deadlocks.
142                                                   142 
143 Furthermore, two locks can not be taken in inv    143 Furthermore, two locks can not be taken in inverse order::
144                                                   144 
145  <L1> -> <L2>                                     145  <L1> -> <L2>
146  <L2> -> <L1>                                     146  <L2> -> <L1>
147                                                   147 
148 because this could lead to a deadlock - referr    148 because this could lead to a deadlock - referred to as lock inversion
149 deadlock - as attempts to acquire the two lock    149 deadlock - as attempts to acquire the two locks form a circle which
150 could lead to the two contexts waiting for eac    150 could lead to the two contexts waiting for each other permanently. The
151 validator will find such dependency circle in     151 validator will find such dependency circle in arbitrary complexity,
152 i.e., there can be any other locking sequence     152 i.e., there can be any other locking sequence between the acquire-lock
153 operations; the validator will still find whet    153 operations; the validator will still find whether these locks can be
154 acquired in a circular fashion.                   154 acquired in a circular fashion.
155                                                   155 
156 Furthermore, the following usage based lock de    156 Furthermore, the following usage based lock dependencies are not allowed
157 between any two lock-classes::                    157 between any two lock-classes::
158                                                   158 
159    <hardirq-safe>   ->  <hardirq-unsafe>          159    <hardirq-safe>   ->  <hardirq-unsafe>
160    <softirq-safe>   ->  <softirq-unsafe>          160    <softirq-safe>   ->  <softirq-unsafe>
161                                                   161 
162 The first rule comes from the fact that a hard    162 The first rule comes from the fact that a hardirq-safe lock could be
163 taken by a hardirq context, interrupting a har    163 taken by a hardirq context, interrupting a hardirq-unsafe lock - and
164 thus could result in a lock inversion deadlock    164 thus could result in a lock inversion deadlock. Likewise, a softirq-safe
165 lock could be taken by an softirq context, int    165 lock could be taken by an softirq context, interrupting a softirq-unsafe
166 lock.                                             166 lock.
167                                                   167 
168 The above rules are enforced for any locking s    168 The above rules are enforced for any locking sequence that occurs in the
169 kernel: when acquiring a new lock, the validat    169 kernel: when acquiring a new lock, the validator checks whether there is
170 any rule violation between the new lock and an    170 any rule violation between the new lock and any of the held locks.
171                                                   171 
172 When a lock-class changes its state, the follo    172 When a lock-class changes its state, the following aspects of the above
173 dependency rules are enforced:                    173 dependency rules are enforced:
174                                                   174 
175 - if a new hardirq-safe lock is discovered, we    175 - if a new hardirq-safe lock is discovered, we check whether it
176   took any hardirq-unsafe lock in the past.       176   took any hardirq-unsafe lock in the past.
177                                                   177 
178 - if a new softirq-safe lock is discovered, we    178 - if a new softirq-safe lock is discovered, we check whether it took
179   any softirq-unsafe lock in the past.            179   any softirq-unsafe lock in the past.
180                                                   180 
181 - if a new hardirq-unsafe lock is discovered,     181 - if a new hardirq-unsafe lock is discovered, we check whether any
182   hardirq-safe lock took it in the past.          182   hardirq-safe lock took it in the past.
183                                                   183 
184 - if a new softirq-unsafe lock is discovered,     184 - if a new softirq-unsafe lock is discovered, we check whether any
185   softirq-safe lock took it in the past.          185   softirq-safe lock took it in the past.
186                                                   186 
187 (Again, we do these checks too on the basis th    187 (Again, we do these checks too on the basis that an interrupt context
188 could interrupt _any_ of the irq-unsafe or har    188 could interrupt _any_ of the irq-unsafe or hardirq-unsafe locks, which
189 could lead to a lock inversion deadlock - even    189 could lead to a lock inversion deadlock - even if that lock scenario did
190 not trigger in practice yet.)                     190 not trigger in practice yet.)
191                                                   191 
192 Exception: Nested data dependencies leading to    192 Exception: Nested data dependencies leading to nested locking
193 ----------------------------------------------    193 -------------------------------------------------------------
194                                                   194 
195 There are a few cases where the Linux kernel a    195 There are a few cases where the Linux kernel acquires more than one
196 instance of the same lock-class. Such cases ty    196 instance of the same lock-class. Such cases typically happen when there
197 is some sort of hierarchy within objects of th    197 is some sort of hierarchy within objects of the same type. In these
198 cases there is an inherent "natural" ordering     198 cases there is an inherent "natural" ordering between the two objects
199 (defined by the properties of the hierarchy),     199 (defined by the properties of the hierarchy), and the kernel grabs the
200 locks in this fixed order on each of the objec    200 locks in this fixed order on each of the objects.
201                                                   201 
202 An example of such an object hierarchy that re    202 An example of such an object hierarchy that results in "nested locking"
203 is that of a "whole disk" block-dev object and    203 is that of a "whole disk" block-dev object and a "partition" block-dev
204 object; the partition is "part of" the whole d    204 object; the partition is "part of" the whole device and as long as one
205 always takes the whole disk lock as a higher l    205 always takes the whole disk lock as a higher lock than the partition
206 lock, the lock ordering is fully correct. The     206 lock, the lock ordering is fully correct. The validator does not
207 automatically detect this natural ordering, as    207 automatically detect this natural ordering, as the locking rule behind
208 the ordering is not static.                       208 the ordering is not static.
209                                                   209 
210 In order to teach the validator about this cor    210 In order to teach the validator about this correct usage model, new
211 versions of the various locking primitives wer    211 versions of the various locking primitives were added that allow you to
212 specify a "nesting level". An example call, fo    212 specify a "nesting level". An example call, for the block device mutex,
213 looks like this::                                 213 looks like this::
214                                                   214 
215   enum bdev_bd_mutex_lock_class                   215   enum bdev_bd_mutex_lock_class
216   {                                               216   {
217        BD_MUTEX_NORMAL,                           217        BD_MUTEX_NORMAL,
218        BD_MUTEX_WHOLE,                            218        BD_MUTEX_WHOLE,
219        BD_MUTEX_PARTITION                         219        BD_MUTEX_PARTITION
220   };                                              220   };
221                                                   221 
222   mutex_lock_nested(&bdev->bd_contains->bd_mut    222   mutex_lock_nested(&bdev->bd_contains->bd_mutex, BD_MUTEX_PARTITION);
223                                                   223 
224 In this case the locking is done on a bdev obj    224 In this case the locking is done on a bdev object that is known to be a
225 partition.                                        225 partition.
226                                                   226 
227 The validator treats a lock that is taken in s    227 The validator treats a lock that is taken in such a nested fashion as a
228 separate (sub)class for the purposes of valida    228 separate (sub)class for the purposes of validation.
229                                                   229 
230 Note: When changing code to use the _nested()     230 Note: When changing code to use the _nested() primitives, be careful and
231 check really thoroughly that the hierarchy is     231 check really thoroughly that the hierarchy is correctly mapped; otherwise
232 you can get false positives or false negatives    232 you can get false positives or false negatives.
233                                                   233 
234 Annotations                                       234 Annotations
235 -----------                                       235 -----------
236                                                   236 
237 Two constructs can be used to annotate and che    237 Two constructs can be used to annotate and check where and if certain locks
238 must be held: lockdep_assert_held*(&lock) and     238 must be held: lockdep_assert_held*(&lock) and lockdep_*pin_lock(&lock).
239                                                   239 
240 As the name suggests, lockdep_assert_held* fam    240 As the name suggests, lockdep_assert_held* family of macros assert that a
241 particular lock is held at a certain time (and    241 particular lock is held at a certain time (and generate a WARN() otherwise).
242 This annotation is largely used all over the k    242 This annotation is largely used all over the kernel, e.g. kernel/sched/
243 core.c::                                          243 core.c::
244                                                   244 
245   void update_rq_clock(struct rq *rq)             245   void update_rq_clock(struct rq *rq)
246   {                                               246   {
247         s64 delta;                                247         s64 delta;
248                                                   248 
249         lockdep_assert_held(&rq->lock);           249         lockdep_assert_held(&rq->lock);
250         [...]                                     250         [...]
251   }                                               251   }
252                                                   252 
253 where holding rq->lock is required to safely u    253 where holding rq->lock is required to safely update a rq's clock.
254                                                   254 
255 The other family of macros is lockdep_*pin_loc    255 The other family of macros is lockdep_*pin_lock(), which is admittedly only
256 used for rq->lock ATM. Despite their limited a    256 used for rq->lock ATM. Despite their limited adoption these annotations
257 generate a WARN() if the lock of interest is "    257 generate a WARN() if the lock of interest is "accidentally" unlocked. This turns
258 out to be especially helpful to debug code wit    258 out to be especially helpful to debug code with callbacks, where an upper
259 layer assumes a lock remains taken, but a lowe    259 layer assumes a lock remains taken, but a lower layer thinks it can maybe drop
260 and reacquire the lock ("unwittingly" introduc    260 and reacquire the lock ("unwittingly" introducing races). lockdep_pin_lock()
261 returns a 'struct pin_cookie' that is then use    261 returns a 'struct pin_cookie' that is then used by lockdep_unpin_lock() to check
262 that nobody tampered with the lock, e.g. kerne    262 that nobody tampered with the lock, e.g. kernel/sched/sched.h::
263                                                   263 
264   static inline void rq_pin_lock(struct rq *rq    264   static inline void rq_pin_lock(struct rq *rq, struct rq_flags *rf)
265   {                                               265   {
266         rf->cookie = lockdep_pin_lock(&rq->loc    266         rf->cookie = lockdep_pin_lock(&rq->lock);
267         [...]                                     267         [...]
268   }                                               268   }
269                                                   269 
270   static inline void rq_unpin_lock(struct rq *    270   static inline void rq_unpin_lock(struct rq *rq, struct rq_flags *rf)
271   {                                               271   {
272         [...]                                     272         [...]
273         lockdep_unpin_lock(&rq->lock, rf->cook    273         lockdep_unpin_lock(&rq->lock, rf->cookie);
274   }                                               274   }
275                                                   275 
276 While comments about locking requirements migh    276 While comments about locking requirements might provide useful information,
277 the runtime checks performed by annotations ar    277 the runtime checks performed by annotations are invaluable when debugging
278 locking problems and they carry the same level    278 locking problems and they carry the same level of details when inspecting
279 code.  Always prefer annotations when in doubt    279 code.  Always prefer annotations when in doubt!
280                                                   280 
281 Proof of 100% correctness:                        281 Proof of 100% correctness:
282 --------------------------                        282 --------------------------
283                                                   283 
284 The validator achieves perfect, mathematical '    284 The validator achieves perfect, mathematical 'closure' (proof of locking
285 correctness) in the sense that for every simpl    285 correctness) in the sense that for every simple, standalone single-task
286 locking sequence that occurred at least once d    286 locking sequence that occurred at least once during the lifetime of the
287 kernel, the validator proves it with a 100% ce    287 kernel, the validator proves it with a 100% certainty that no
288 combination and timing of these locking sequen    288 combination and timing of these locking sequences can cause any class of
289 lock related deadlock. [1]_                       289 lock related deadlock. [1]_
290                                                   290 
291 I.e. complex multi-CPU and multi-task locking     291 I.e. complex multi-CPU and multi-task locking scenarios do not have to
292 occur in practice to prove a deadlock: only th    292 occur in practice to prove a deadlock: only the simple 'component'
293 locking chains have to occur at least once (an    293 locking chains have to occur at least once (anytime, in any
294 task/context) for the validator to be able to     294 task/context) for the validator to be able to prove correctness. (For
295 example, complex deadlocks that would normally    295 example, complex deadlocks that would normally need more than 3 CPUs and
296 a very unlikely constellation of tasks, irq-co    296 a very unlikely constellation of tasks, irq-contexts and timings to
297 occur, can be detected on a plain, lightly loa    297 occur, can be detected on a plain, lightly loaded single-CPU system as
298 well!)                                            298 well!)
299                                                   299 
300 This radically decreases the complexity of loc    300 This radically decreases the complexity of locking related QA of the
301 kernel: what has to be done during QA is to tr    301 kernel: what has to be done during QA is to trigger as many "simple"
302 single-task locking dependencies in the kernel    302 single-task locking dependencies in the kernel as possible, at least
303 once, to prove locking correctness - instead o    303 once, to prove locking correctness - instead of having to trigger every
304 possible combination of locking interaction be    304 possible combination of locking interaction between CPUs, combined with
305 every possible hardirq and softirq nesting sce    305 every possible hardirq and softirq nesting scenario (which is impossible
306 to do in practice).                               306 to do in practice).
307                                                   307 
308 .. [1]                                            308 .. [1]
309                                                   309 
310     assuming that the validator itself is 100%    310     assuming that the validator itself is 100% correct, and no other
311     part of the system corrupts the state of t    311     part of the system corrupts the state of the validator in any way.
312     We also assume that all NMI/SMM paths [whi    312     We also assume that all NMI/SMM paths [which could interrupt
313     even hardirq-disabled codepaths] are corre    313     even hardirq-disabled codepaths] are correct and do not interfere
314     with the validator. We also assume that th    314     with the validator. We also assume that the 64-bit 'chain hash'
315     value is unique for every lock-chain in th    315     value is unique for every lock-chain in the system. Also, lock
316     recursion must not be higher than 20.         316     recursion must not be higher than 20.
317                                                   317 
318 Performance:                                      318 Performance:
319 ------------                                      319 ------------
320                                                   320 
321 The above rules require **massive** amounts of    321 The above rules require **massive** amounts of runtime checking. If we did
322 that for every lock taken and for every irqs-e    322 that for every lock taken and for every irqs-enable event, it would
323 render the system practically unusably slow. T    323 render the system practically unusably slow. The complexity of checking
324 is O(N^2), so even with just a few hundred loc    324 is O(N^2), so even with just a few hundred lock-classes we'd have to do
325 tens of thousands of checks for every event.      325 tens of thousands of checks for every event.
326                                                   326 
327 This problem is solved by checking any given '    327 This problem is solved by checking any given 'locking scenario' (unique
328 sequence of locks taken after each other) only    328 sequence of locks taken after each other) only once. A simple stack of
329 held locks is maintained, and a lightweight 64    329 held locks is maintained, and a lightweight 64-bit hash value is
330 calculated, which hash is unique for every loc    330 calculated, which hash is unique for every lock chain. The hash value,
331 when the chain is validated for the first time    331 when the chain is validated for the first time, is then put into a hash
332 table, which hash-table can be checked in a lo    332 table, which hash-table can be checked in a lockfree manner. If the
333 locking chain occurs again later on, the hash     333 locking chain occurs again later on, the hash table tells us that we
334 don't have to validate the chain again.           334 don't have to validate the chain again.
335                                                   335 
336 Troubleshooting:                                  336 Troubleshooting:
337 ----------------                                  337 ----------------
338                                                   338 
339 The validator tracks a maximum of MAX_LOCKDEP_    339 The validator tracks a maximum of MAX_LOCKDEP_KEYS number of lock classes.
340 Exceeding this number will trigger the followi    340 Exceeding this number will trigger the following lockdep warning::
341                                                   341 
342         (DEBUG_LOCKS_WARN_ON(id >= MAX_LOCKDEP    342         (DEBUG_LOCKS_WARN_ON(id >= MAX_LOCKDEP_KEYS))
343                                                   343 
344 By default, MAX_LOCKDEP_KEYS is currently set     344 By default, MAX_LOCKDEP_KEYS is currently set to 8191, and typical
345 desktop systems have less than 1,000 lock clas    345 desktop systems have less than 1,000 lock classes, so this warning
346 normally results from lock-class leakage or fa    346 normally results from lock-class leakage or failure to properly
347 initialize locks.  These two problems are illu    347 initialize locks.  These two problems are illustrated below:
348                                                   348 
349 1.      Repeated module loading and unloading     349 1.      Repeated module loading and unloading while running the validator
350         will result in lock-class leakage.  Th    350         will result in lock-class leakage.  The issue here is that each
351         load of the module will create a new s    351         load of the module will create a new set of lock classes for
352         that module's locks, but module unload    352         that module's locks, but module unloading does not remove old
353         classes (see below discussion of reuse    353         classes (see below discussion of reuse of lock classes for why).
354         Therefore, if that module is loaded an    354         Therefore, if that module is loaded and unloaded repeatedly,
355         the number of lock classes will eventu    355         the number of lock classes will eventually reach the maximum.
356                                                   356 
357 2.      Using structures such as arrays that h    357 2.      Using structures such as arrays that have large numbers of
358         locks that are not explicitly initiali    358         locks that are not explicitly initialized.  For example,
359         a hash table with 8192 buckets where e    359         a hash table with 8192 buckets where each bucket has its own
360         spinlock_t will consume 8192 lock clas    360         spinlock_t will consume 8192 lock classes -unless- each spinlock
361         is explicitly initialized at runtime,     361         is explicitly initialized at runtime, for example, using the
362         run-time spin_lock_init() as opposed t    362         run-time spin_lock_init() as opposed to compile-time initializers
363         such as __SPIN_LOCK_UNLOCKED().  Failu    363         such as __SPIN_LOCK_UNLOCKED().  Failure to properly initialize
364         the per-bucket spinlocks would guarant    364         the per-bucket spinlocks would guarantee lock-class overflow.
365         In contrast, a loop that called spin_l    365         In contrast, a loop that called spin_lock_init() on each lock
366         would place all 8192 locks into a sing    366         would place all 8192 locks into a single lock class.
367                                                   367 
368         The moral of this story is that you sh    368         The moral of this story is that you should always explicitly
369         initialize your locks.                    369         initialize your locks.
370                                                   370 
371 One might argue that the validator should be m    371 One might argue that the validator should be modified to allow
372 lock classes to be reused.  However, if you ar    372 lock classes to be reused.  However, if you are tempted to make this
373 argument, first review the code and think thro    373 argument, first review the code and think through the changes that would
374 be required, keeping in mind that the lock cla    374 be required, keeping in mind that the lock classes to be removed are
375 likely to be linked into the lock-dependency g    375 likely to be linked into the lock-dependency graph.  This turns out to
376 be harder to do than to say.                      376 be harder to do than to say.
377                                                   377 
378 Of course, if you do run out of lock classes,     378 Of course, if you do run out of lock classes, the next thing to do is
379 to find the offending lock classes.  First, th    379 to find the offending lock classes.  First, the following command gives
380 you the number of lock classes currently in us    380 you the number of lock classes currently in use along with the maximum::
381                                                   381 
382         grep "lock-classes" /proc/lockdep_stat    382         grep "lock-classes" /proc/lockdep_stats
383                                                   383 
384 This command produces the following output on     384 This command produces the following output on a modest system::
385                                                   385 
386         lock-classes:                             386         lock-classes:                          748 [max: 8191]
387                                                   387 
388 If the number allocated (748 above) increases     388 If the number allocated (748 above) increases continually over time,
389 then there is likely a leak.  The following co    389 then there is likely a leak.  The following command can be used to
390 identify the leaking lock classes::               390 identify the leaking lock classes::
391                                                   391 
392         grep "BD" /proc/lockdep                   392         grep "BD" /proc/lockdep
393                                                   393 
394 Run the command and save the output, then comp    394 Run the command and save the output, then compare against the output from
395 a later run of this command to identify the le    395 a later run of this command to identify the leakers.  This same output
396 can also help you find situations where runtim    396 can also help you find situations where runtime lock initialization has
397 been omitted.                                     397 been omitted.
398                                                   398 
399 Recursive read locks:                             399 Recursive read locks:
400 ---------------------                             400 ---------------------
401 The whole of the rest document tries to prove     401 The whole of the rest document tries to prove a certain type of cycle is equivalent
402 to deadlock possibility.                          402 to deadlock possibility.
403                                                   403 
404 There are three types of lockers: writers (i.e    404 There are three types of lockers: writers (i.e. exclusive lockers, like
405 spin_lock() or write_lock()), non-recursive re    405 spin_lock() or write_lock()), non-recursive readers (i.e. shared lockers, like
406 down_read()) and recursive readers (recursive     406 down_read()) and recursive readers (recursive shared lockers, like rcu_read_lock()).
407 And we use the following notations of those lo    407 And we use the following notations of those lockers in the rest of the document:
408                                                   408 
409         W or E: stands for writers (exclusive     409         W or E: stands for writers (exclusive lockers).
410         r:      stands for non-recursive reade    410         r:      stands for non-recursive readers.
411         R:      stands for recursive readers.     411         R:      stands for recursive readers.
412         S:      stands for all readers (non-re    412         S:      stands for all readers (non-recursive + recursive), as both are shared lockers.
413         N:      stands for writers and non-rec    413         N:      stands for writers and non-recursive readers, as both are not recursive.
414                                                   414 
415 Obviously, N is "r or W" and S is "r or R".       415 Obviously, N is "r or W" and S is "r or R".
416                                                   416 
417 Recursive readers, as their name indicates, ar    417 Recursive readers, as their name indicates, are the lockers allowed to acquire
418 even inside the critical section of another re    418 even inside the critical section of another reader of the same lock instance,
419 in other words, allowing nested read-side crit    419 in other words, allowing nested read-side critical sections of one lock instance.
420                                                   420 
421 While non-recursive readers will cause a self     421 While non-recursive readers will cause a self deadlock if trying to acquire inside
422 the critical section of another reader of the     422 the critical section of another reader of the same lock instance.
423                                                   423 
424 The difference between recursive readers and n    424 The difference between recursive readers and non-recursive readers is because:
425 recursive readers get blocked only by a write     425 recursive readers get blocked only by a write lock *holder*, while non-recursive
426 readers could get blocked by a write lock *wai    426 readers could get blocked by a write lock *waiter*. Considering the follow
427 example::                                         427 example::
428                                                   428 
429         TASK A:                 TASK B:           429         TASK A:                 TASK B:
430                                                   430 
431         read_lock(X);                             431         read_lock(X);
432                                 write_lock(X);    432                                 write_lock(X);
433         read_lock_2(X);                           433         read_lock_2(X);
434                                                   434 
435 Task A gets the reader (no matter whether recu    435 Task A gets the reader (no matter whether recursive or non-recursive) on X via
436 read_lock() first. And when task B tries to ac    436 read_lock() first. And when task B tries to acquire writer on X, it will block
437 and become a waiter for writer on X. Now if re    437 and become a waiter for writer on X. Now if read_lock_2() is recursive readers,
438 task A will make progress, because writer wait    438 task A will make progress, because writer waiters don't block recursive readers,
439 and there is no deadlock. However, if read_loc    439 and there is no deadlock. However, if read_lock_2() is non-recursive readers,
440 it will get blocked by writer waiter B, and ca    440 it will get blocked by writer waiter B, and cause a self deadlock.
441                                                   441 
442 Block conditions on readers/writers of the sam    442 Block conditions on readers/writers of the same lock instance:
443 ----------------------------------------------    443 --------------------------------------------------------------
444 There are simply four block conditions:           444 There are simply four block conditions:
445                                                   445 
446 1.      Writers block other writers.              446 1.      Writers block other writers.
447 2.      Readers block writers.                    447 2.      Readers block writers.
448 3.      Writers block both recursive readers a    448 3.      Writers block both recursive readers and non-recursive readers.
449 4.      And readers (recursive or not) don't b    449 4.      And readers (recursive or not) don't block other recursive readers but
450         may block non-recursive readers (becau    450         may block non-recursive readers (because of the potential co-existing
451         writer waiters)                           451         writer waiters)
452                                                   452 
453 Block condition matrix, Y means the row blocks    453 Block condition matrix, Y means the row blocks the column, and N means otherwise.
454                                                   454 
455         +---+---+---+---+                         455         +---+---+---+---+
456         |   | W | r | R |                         456         |   | W | r | R |
457         +---+---+---+---+                         457         +---+---+---+---+
458         | W | Y | Y | Y |                         458         | W | Y | Y | Y |
459         +---+---+---+---+                         459         +---+---+---+---+
460         | r | Y | Y | N |                         460         | r | Y | Y | N |
461         +---+---+---+---+                         461         +---+---+---+---+
462         | R | Y | Y | N |                         462         | R | Y | Y | N |
463         +---+---+---+---+                         463         +---+---+---+---+
464                                                   464 
465         (W: writers, r: non-recursive readers,    465         (W: writers, r: non-recursive readers, R: recursive readers)
466                                                   466 
467                                                   467 
468 acquired recursively. Unlike non-recursive rea    468 acquired recursively. Unlike non-recursive read locks, recursive read locks
469 only get blocked by current write lock *holder    469 only get blocked by current write lock *holders* other than write lock
470 *waiters*, for example::                          470 *waiters*, for example::
471                                                   471 
472         TASK A:                 TASK B:           472         TASK A:                 TASK B:
473                                                   473 
474         read_lock(X);                             474         read_lock(X);
475                                                   475 
476                                 write_lock(X);    476                                 write_lock(X);
477                                                   477 
478         read_lock(X);                             478         read_lock(X);
479                                                   479 
480 is not a deadlock for recursive read locks, as    480 is not a deadlock for recursive read locks, as while the task B is waiting for
481 the lock X, the second read_lock() doesn't nee    481 the lock X, the second read_lock() doesn't need to wait because it's a recursive
482 read lock. However if the read_lock() is non-r    482 read lock. However if the read_lock() is non-recursive read lock, then the above
483 case is a deadlock, because even if the write_    483 case is a deadlock, because even if the write_lock() in TASK B cannot get the
484 lock, but it can block the second read_lock()     484 lock, but it can block the second read_lock() in TASK A.
485                                                   485 
486 Note that a lock can be a write lock (exclusiv    486 Note that a lock can be a write lock (exclusive lock), a non-recursive read
487 lock (non-recursive shared lock) or a recursiv    487 lock (non-recursive shared lock) or a recursive read lock (recursive shared
488 lock), depending on the lock operations used t    488 lock), depending on the lock operations used to acquire it (more specifically,
489 the value of the 'read' parameter for lock_acq    489 the value of the 'read' parameter for lock_acquire()). In other words, a single
490 lock instance has three types of acquisition d    490 lock instance has three types of acquisition depending on the acquisition
491 functions: exclusive, non-recursive read, and     491 functions: exclusive, non-recursive read, and recursive read.
492                                                   492 
493 To be concise, we call that write locks and no    493 To be concise, we call that write locks and non-recursive read locks as
494 "non-recursive" locks and recursive read locks    494 "non-recursive" locks and recursive read locks as "recursive" locks.
495                                                   495 
496 Recursive locks don't block each other, while     496 Recursive locks don't block each other, while non-recursive locks do (this is
497 even true for two non-recursive read locks). A    497 even true for two non-recursive read locks). A non-recursive lock can block the
498 corresponding recursive lock, and vice versa.     498 corresponding recursive lock, and vice versa.
499                                                   499 
500 A deadlock case with recursive locks involved     500 A deadlock case with recursive locks involved is as follow::
501                                                   501 
502         TASK A:                 TASK B:           502         TASK A:                 TASK B:
503                                                   503 
504         read_lock(X);                             504         read_lock(X);
505                                 read_lock(Y);     505                                 read_lock(Y);
506         write_lock(Y);                            506         write_lock(Y);
507                                 write_lock(X);    507                                 write_lock(X);
508                                                   508 
509 Task A is waiting for task B to read_unlock()     509 Task A is waiting for task B to read_unlock() Y and task B is waiting for task
510 A to read_unlock() X.                             510 A to read_unlock() X.
511                                                   511 
512 Dependency types and strong dependency paths:     512 Dependency types and strong dependency paths:
513 ---------------------------------------------     513 ---------------------------------------------
514 Lock dependencies record the orders of the acq    514 Lock dependencies record the orders of the acquisitions of a pair of locks, and
515 because there are 3 types for lockers, there a    515 because there are 3 types for lockers, there are, in theory, 9 types of lock
516 dependencies, but we can show that 4 types of     516 dependencies, but we can show that 4 types of lock dependencies are enough for
517 deadlock detection.                               517 deadlock detection.
518                                                   518 
519 For each lock dependency::                        519 For each lock dependency::
520                                                   520 
521         L1 -> L2                                  521         L1 -> L2
522                                                   522 
523 , which means lockdep has seen L1 held before     523 , which means lockdep has seen L1 held before L2 held in the same context at runtime.
524 And in deadlock detection, we care whether we     524 And in deadlock detection, we care whether we could get blocked on L2 with L1 held,
525 IOW, whether there is a locker L3 that L1 bloc    525 IOW, whether there is a locker L3 that L1 blocks L3 and L2 gets blocked by L3. So
526 we only care about 1) what L1 blocks and 2) wh    526 we only care about 1) what L1 blocks and 2) what blocks L2. As a result, we can combine
527 recursive readers and non-recursive readers fo    527 recursive readers and non-recursive readers for L1 (as they block the same types) and
528 we can combine writers and non-recursive reade    528 we can combine writers and non-recursive readers for L2 (as they get blocked by the
529 same types).                                      529 same types).
530                                                   530 
531 With the above combination for simplification,    531 With the above combination for simplification, there are 4 types of dependency edges
532 in the lockdep graph:                             532 in the lockdep graph:
533                                                   533 
534 1) -(ER)->:                                       534 1) -(ER)->:
535             exclusive writer to recursive read    535             exclusive writer to recursive reader dependency, "X -(ER)-> Y" means
536             X -> Y and X is a writer and Y is     536             X -> Y and X is a writer and Y is a recursive reader.
537                                                   537 
538 2) -(EN)->:                                       538 2) -(EN)->:
539             exclusive writer to non-recursive     539             exclusive writer to non-recursive locker dependency, "X -(EN)-> Y" means
540             X -> Y and X is a writer and Y is     540             X -> Y and X is a writer and Y is either a writer or non-recursive reader.
541                                                   541 
542 3) -(SR)->:                                       542 3) -(SR)->:
543             shared reader to recursive reader     543             shared reader to recursive reader dependency, "X -(SR)-> Y" means
544             X -> Y and X is a reader (recursiv    544             X -> Y and X is a reader (recursive or not) and Y is a recursive reader.
545                                                   545 
546 4) -(SN)->:                                       546 4) -(SN)->:
547             shared reader to non-recursive loc    547             shared reader to non-recursive locker dependency, "X -(SN)-> Y" means
548             X -> Y and X is a reader (recursiv    548             X -> Y and X is a reader (recursive or not) and Y is either a writer or
549             non-recursive reader.                 549             non-recursive reader.
550                                                   550 
551 Note that given two locks, they may have multi    551 Note that given two locks, they may have multiple dependencies between them,
552 for example::                                     552 for example::
553                                                   553 
554         TASK A:                                   554         TASK A:
555                                                   555 
556         read_lock(X);                             556         read_lock(X);
557         write_lock(Y);                            557         write_lock(Y);
558         ...                                       558         ...
559                                                   559 
560         TASK B:                                   560         TASK B:
561                                                   561 
562         write_lock(X);                            562         write_lock(X);
563         write_lock(Y);                            563         write_lock(Y);
564                                                   564 
565 , we have both X -(SN)-> Y and X -(EN)-> Y in     565 , we have both X -(SN)-> Y and X -(EN)-> Y in the dependency graph.
566                                                   566 
567 We use -(xN)-> to represent edges that are eit    567 We use -(xN)-> to represent edges that are either -(EN)-> or -(SN)->, the
568 similar for -(Ex)->, -(xR)-> and -(Sx)->          568 similar for -(Ex)->, -(xR)-> and -(Sx)->
569                                                   569 
570 A "path" is a series of conjunct dependency ed    570 A "path" is a series of conjunct dependency edges in the graph. And we define a
571 "strong" path, which indicates the strong depe    571 "strong" path, which indicates the strong dependency throughout each dependency
572 in the path, as the path that doesn't have two    572 in the path, as the path that doesn't have two conjunct edges (dependencies) as
573 -(xR)-> and -(Sx)->. In other words, a "strong    573 -(xR)-> and -(Sx)->. In other words, a "strong" path is a path from a lock
574 walking to another through the lock dependenci    574 walking to another through the lock dependencies, and if X -> Y -> Z is in the
575 path (where X, Y, Z are locks), and the walk f    575 path (where X, Y, Z are locks), and the walk from X to Y is through a -(SR)-> or
576 -(ER)-> dependency, the walk from Y to Z must     576 -(ER)-> dependency, the walk from Y to Z must not be through a -(SN)-> or
577 -(SR)-> dependency.                               577 -(SR)-> dependency.
578                                                   578 
579 We will see why the path is called "strong" in    579 We will see why the path is called "strong" in next section.
580                                                   580 
581 Recursive Read Deadlock Detection:                581 Recursive Read Deadlock Detection:
582 ----------------------------------                582 ----------------------------------
583                                                   583 
584 We now prove two things:                          584 We now prove two things:
585                                                   585 
586 Lemma 1:                                          586 Lemma 1:
587                                                   587 
588 If there is a closed strong path (i.e. a stron    588 If there is a closed strong path (i.e. a strong circle), then there is a
589 combination of locking sequences that causes d    589 combination of locking sequences that causes deadlock. I.e. a strong circle is
590 sufficient for deadlock detection.                590 sufficient for deadlock detection.
591                                                   591 
592 Lemma 2:                                          592 Lemma 2:
593                                                   593 
594 If there is no closed strong path (i.e. strong    594 If there is no closed strong path (i.e. strong circle), then there is no
595 combination of locking sequences that could ca    595 combination of locking sequences that could cause deadlock. I.e.  strong
596 circles are necessary for deadlock detection.     596 circles are necessary for deadlock detection.
597                                                   597 
598 With these two Lemmas, we can easily say a clo    598 With these two Lemmas, we can easily say a closed strong path is both sufficient
599 and necessary for deadlocks, therefore a close    599 and necessary for deadlocks, therefore a closed strong path is equivalent to
600 deadlock possibility. As a closed strong path     600 deadlock possibility. As a closed strong path stands for a dependency chain that
601 could cause deadlocks, so we call it "strong",    601 could cause deadlocks, so we call it "strong", considering there are dependency
602 circles that won't cause deadlocks.               602 circles that won't cause deadlocks.
603                                                   603 
604 Proof for sufficiency (Lemma 1):                  604 Proof for sufficiency (Lemma 1):
605                                                   605 
606 Let's say we have a strong circle::               606 Let's say we have a strong circle::
607                                                   607 
608         L1 -> L2 ... -> Ln -> L1                  608         L1 -> L2 ... -> Ln -> L1
609                                                   609 
610 , which means we have dependencies::              610 , which means we have dependencies::
611                                                   611 
612         L1 -> L2                                  612         L1 -> L2
613         L2 -> L3                                  613         L2 -> L3
614         ...                                       614         ...
615         Ln-1 -> Ln                                615         Ln-1 -> Ln
616         Ln -> L1                                  616         Ln -> L1
617                                                   617 
618 We now can construct a combination of locking     618 We now can construct a combination of locking sequences that cause deadlock:
619                                                   619 
620 Firstly let's make one CPU/task get the L1 in     620 Firstly let's make one CPU/task get the L1 in L1 -> L2, and then another get
621 the L2 in L2 -> L3, and so on. After this, all    621 the L2 in L2 -> L3, and so on. After this, all of the Lx in Lx -> Lx+1 are
622 held by different CPU/tasks.                      622 held by different CPU/tasks.
623                                                   623 
624 And then because we have L1 -> L2, so the hold    624 And then because we have L1 -> L2, so the holder of L1 is going to acquire L2
625 in L1 -> L2, however since L2 is already held     625 in L1 -> L2, however since L2 is already held by another CPU/task, plus L1 ->
626 L2 and L2 -> L3 are not -(xR)-> and -(Sx)-> (t    626 L2 and L2 -> L3 are not -(xR)-> and -(Sx)-> (the definition of strong), which
627 means either L2 in L1 -> L2 is a non-recursive    627 means either L2 in L1 -> L2 is a non-recursive locker (blocked by anyone) or
628 the L2 in L2 -> L3, is writer (blocking anyone    628 the L2 in L2 -> L3, is writer (blocking anyone), therefore the holder of L1
629 cannot get L2, it has to wait L2's holder to r    629 cannot get L2, it has to wait L2's holder to release.
630                                                   630 
631 Moreover, we can have a similar conclusion for    631 Moreover, we can have a similar conclusion for L2's holder: it has to wait L3's
632 holder to release, and so on. We now can prove    632 holder to release, and so on. We now can prove that Lx's holder has to wait for
633 Lx+1's holder to release, and note that Ln+1 i    633 Lx+1's holder to release, and note that Ln+1 is L1, so we have a circular
634 waiting scenario and nobody can get progress,     634 waiting scenario and nobody can get progress, therefore a deadlock.
635                                                   635 
636 Proof for necessary (Lemma 2):                    636 Proof for necessary (Lemma 2):
637                                                   637 
638 Lemma 2 is equivalent to: If there is a deadlo    638 Lemma 2 is equivalent to: If there is a deadlock scenario, then there must be a
639 strong circle in the dependency graph.            639 strong circle in the dependency graph.
640                                                   640 
641 According to Wikipedia[1], if there is a deadl    641 According to Wikipedia[1], if there is a deadlock, then there must be a circular
642 waiting scenario, means there are N CPU/tasks,    642 waiting scenario, means there are N CPU/tasks, where CPU/task P1 is waiting for
643 a lock held by P2, and P2 is waiting for a loc    643 a lock held by P2, and P2 is waiting for a lock held by P3, ... and Pn is waiting
644 for a lock held by P1. Let's name the lock Px     644 for a lock held by P1. Let's name the lock Px is waiting as Lx, so since P1 is waiting
645 for L1 and holding Ln, so we will have Ln -> L    645 for L1 and holding Ln, so we will have Ln -> L1 in the dependency graph. Similarly,
646 we have L1 -> L2, L2 -> L3, ..., Ln-1 -> Ln in    646 we have L1 -> L2, L2 -> L3, ..., Ln-1 -> Ln in the dependency graph, which means we
647 have a circle::                                   647 have a circle::
648                                                   648 
649         Ln -> L1 -> L2 -> ... -> Ln               649         Ln -> L1 -> L2 -> ... -> Ln
650                                                   650 
651 , and now let's prove the circle is strong:       651 , and now let's prove the circle is strong:
652                                                   652 
653 For a lock Lx, Px contributes the dependency L    653 For a lock Lx, Px contributes the dependency Lx-1 -> Lx and Px+1 contributes
654 the dependency Lx -> Lx+1, and since Px is wai    654 the dependency Lx -> Lx+1, and since Px is waiting for Px+1 to release Lx,
655 so it's impossible that Lx on Px+1 is a reader    655 so it's impossible that Lx on Px+1 is a reader and Lx on Px is a recursive
656 reader, because readers (no matter recursive o    656 reader, because readers (no matter recursive or not) don't block recursive
657 readers, therefore Lx-1 -> Lx and Lx -> Lx+1 c    657 readers, therefore Lx-1 -> Lx and Lx -> Lx+1 cannot be a -(xR)-> -(Sx)-> pair,
658 and this is true for any lock in the circle, t    658 and this is true for any lock in the circle, therefore, the circle is strong.
659                                                   659 
660 References:                                       660 References:
661 -----------                                       661 -----------
662 [1]: https://en.wikipedia.org/wiki/Deadlock       662 [1]: https://en.wikipedia.org/wiki/Deadlock
663 [2]: Shibu, K. (2009). Intro To Embedded Syste    663 [2]: Shibu, K. (2009). Intro To Embedded Systems (1st ed.). Tata McGraw-Hill
                                                      

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

sflogo.php