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