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