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