1 .. _kernel_hacking_lock: <<
2 <<
3 =========================== 1 ===========================
4 Unreliable Guide To Locking 2 Unreliable Guide To Locking
5 =========================== 3 ===========================
6 4
7 :Author: Rusty Russell 5 :Author: Rusty Russell
8 6
9 Introduction 7 Introduction
10 ============ 8 ============
11 9
12 Welcome, to Rusty's Remarkably Unreliable Guid 10 Welcome, to Rusty's Remarkably Unreliable Guide to Kernel Locking
13 issues. This document describes the locking sy 11 issues. This document describes the locking systems in the Linux Kernel
14 in 2.6. 12 in 2.6.
15 13
16 With the wide availability of HyperThreading, 14 With the wide availability of HyperThreading, and preemption in the
17 Linux Kernel, everyone hacking on the kernel n 15 Linux Kernel, everyone hacking on the kernel needs to know the
18 fundamentals of concurrency and locking for SM 16 fundamentals of concurrency and locking for SMP.
19 17
20 The Problem With Concurrency 18 The Problem With Concurrency
21 ============================ 19 ============================
22 20
23 (Skip this if you know what a Race Condition i 21 (Skip this if you know what a Race Condition is).
24 22
25 In a normal program, you can increment a count 23 In a normal program, you can increment a counter like so:
26 24
27 :: 25 ::
28 26
29 very_important_count++; 27 very_important_count++;
30 28
31 29
32 This is what they would expect to happen: 30 This is what they would expect to happen:
33 31
34 32
35 .. table:: Expected Results 33 .. table:: Expected Results
36 34
37 +------------------------------------+------ 35 +------------------------------------+------------------------------------+
38 | Instance 1 | Insta 36 | Instance 1 | Instance 2 |
39 +====================================+====== 37 +====================================+====================================+
40 | read very_important_count (5) | 38 | read very_important_count (5) | |
41 +------------------------------------+------ 39 +------------------------------------+------------------------------------+
42 | add 1 (6) | 40 | add 1 (6) | |
43 +------------------------------------+------ 41 +------------------------------------+------------------------------------+
44 | write very_important_count (6) | 42 | write very_important_count (6) | |
45 +------------------------------------+------ 43 +------------------------------------+------------------------------------+
46 | | read 44 | | read very_important_count (6) |
47 +------------------------------------+------ 45 +------------------------------------+------------------------------------+
48 | | add 1 46 | | add 1 (7) |
49 +------------------------------------+------ 47 +------------------------------------+------------------------------------+
50 | | write 48 | | write very_important_count (7) |
51 +------------------------------------+------ 49 +------------------------------------+------------------------------------+
52 50
53 This is what might happen: 51 This is what might happen:
54 52
55 .. table:: Possible Results 53 .. table:: Possible Results
56 54
57 +------------------------------------+------ 55 +------------------------------------+------------------------------------+
58 | Instance 1 | Insta 56 | Instance 1 | Instance 2 |
59 +====================================+====== 57 +====================================+====================================+
60 | read very_important_count (5) | 58 | read very_important_count (5) | |
61 +------------------------------------+------ 59 +------------------------------------+------------------------------------+
62 | | read 60 | | read very_important_count (5) |
63 +------------------------------------+------ 61 +------------------------------------+------------------------------------+
64 | add 1 (6) | 62 | add 1 (6) | |
65 +------------------------------------+------ 63 +------------------------------------+------------------------------------+
66 | | add 1 64 | | add 1 (6) |
67 +------------------------------------+------ 65 +------------------------------------+------------------------------------+
68 | write very_important_count (6) | 66 | write very_important_count (6) | |
69 +------------------------------------+------ 67 +------------------------------------+------------------------------------+
70 | | write 68 | | write very_important_count (6) |
71 +------------------------------------+------ 69 +------------------------------------+------------------------------------+
72 70
73 71
74 Race Conditions and Critical Regions 72 Race Conditions and Critical Regions
75 ------------------------------------ 73 ------------------------------------
76 74
77 This overlap, where the result depends on the 75 This overlap, where the result depends on the relative timing of
78 multiple tasks, is called a race condition. Th 76 multiple tasks, is called a race condition. The piece of code containing
79 the concurrency issue is called a critical reg 77 the concurrency issue is called a critical region. And especially since
80 Linux starting running on SMP machines, they b 78 Linux starting running on SMP machines, they became one of the major
81 issues in kernel design and implementation. 79 issues in kernel design and implementation.
82 80
83 Preemption can have the same effect, even if t 81 Preemption can have the same effect, even if there is only one CPU: by
84 preempting one task during the critical region 82 preempting one task during the critical region, we have exactly the same
85 race condition. In this case the thread which 83 race condition. In this case the thread which preempts might run the
86 critical region itself. 84 critical region itself.
87 85
88 The solution is to recognize when these simult 86 The solution is to recognize when these simultaneous accesses occur, and
89 use locks to make sure that only one instance 87 use locks to make sure that only one instance can enter the critical
90 region at any time. There are many friendly pr 88 region at any time. There are many friendly primitives in the Linux
91 kernel to help you do this. And then there are 89 kernel to help you do this. And then there are the unfriendly
92 primitives, but I'll pretend they don't exist. 90 primitives, but I'll pretend they don't exist.
93 91
94 Locking in the Linux Kernel 92 Locking in the Linux Kernel
95 =========================== 93 ===========================
96 94
97 If I could give you one piece of advice on loc !! 95 If I could give you one piece of advice: never sleep with anyone crazier
>> 96 than yourself. But if I had to give you advice on locking: **keep it
>> 97 simple**.
98 98
99 Be reluctant to introduce new locks. 99 Be reluctant to introduce new locks.
100 100
>> 101 Strangely enough, this last one is the exact reverse of my advice when
>> 102 you **have** slept with someone crazier than yourself. And you should
>> 103 think about getting a big dog.
>> 104
101 Two Main Types of Kernel Locks: Spinlocks and 105 Two Main Types of Kernel Locks: Spinlocks and Mutexes
102 ---------------------------------------------- 106 -----------------------------------------------------
103 107
104 There are two main types of kernel locks. The 108 There are two main types of kernel locks. The fundamental type is the
105 spinlock (``include/asm/spinlock.h``), which i 109 spinlock (``include/asm/spinlock.h``), which is a very simple
106 single-holder lock: if you can't get the spinl 110 single-holder lock: if you can't get the spinlock, you keep trying
107 (spinning) until you can. Spinlocks are very s 111 (spinning) until you can. Spinlocks are very small and fast, and can be
108 used anywhere. 112 used anywhere.
109 113
110 The second type is a mutex (``include/linux/mu 114 The second type is a mutex (``include/linux/mutex.h``): it is like a
111 spinlock, but you may block holding a mutex. I 115 spinlock, but you may block holding a mutex. If you can't lock a mutex,
112 your task will suspend itself, and be woken up 116 your task will suspend itself, and be woken up when the mutex is
113 released. This means the CPU can do something 117 released. This means the CPU can do something else while you are
114 waiting. There are many cases when you simply 118 waiting. There are many cases when you simply can't sleep (see
115 `What Functions Are Safe To Call From Interrup !! 119 `What Functions Are Safe To Call From Interrupts? <#sleeping-things>`__),
116 and so have to use a spinlock instead. 120 and so have to use a spinlock instead.
117 121
118 Neither type of lock is recursive: see 122 Neither type of lock is recursive: see
119 `Deadlock: Simple and Advanced`_. !! 123 `Deadlock: Simple and Advanced <#deadlock>`__.
120 124
121 Locks and Uniprocessor Kernels 125 Locks and Uniprocessor Kernels
122 ------------------------------ 126 ------------------------------
123 127
124 For kernels compiled without ``CONFIG_SMP``, a 128 For kernels compiled without ``CONFIG_SMP``, and without
125 ``CONFIG_PREEMPT`` spinlocks do not exist at a 129 ``CONFIG_PREEMPT`` spinlocks do not exist at all. This is an excellent
126 design decision: when no-one else can run at t 130 design decision: when no-one else can run at the same time, there is no
127 reason to have a lock. 131 reason to have a lock.
128 132
129 If the kernel is compiled without ``CONFIG_SMP 133 If the kernel is compiled without ``CONFIG_SMP``, but ``CONFIG_PREEMPT``
130 is set, then spinlocks simply disable preempti 134 is set, then spinlocks simply disable preemption, which is sufficient to
131 prevent any races. For most purposes, we can t 135 prevent any races. For most purposes, we can think of preemption as
132 equivalent to SMP, and not worry about it sepa 136 equivalent to SMP, and not worry about it separately.
133 137
134 You should always test your locking code with 138 You should always test your locking code with ``CONFIG_SMP`` and
135 ``CONFIG_PREEMPT`` enabled, even if you don't 139 ``CONFIG_PREEMPT`` enabled, even if you don't have an SMP test box,
136 because it will still catch some kinds of lock 140 because it will still catch some kinds of locking bugs.
137 141
138 Mutexes still exist, because they are required 142 Mutexes still exist, because they are required for synchronization
139 between user contexts, as we will see below. 143 between user contexts, as we will see below.
140 144
141 Locking Only In User Context 145 Locking Only In User Context
142 ---------------------------- 146 ----------------------------
143 147
144 If you have a data structure which is only eve 148 If you have a data structure which is only ever accessed from user
145 context, then you can use a simple mutex (``in 149 context, then you can use a simple mutex (``include/linux/mutex.h``) to
146 protect it. This is the most trivial case: you 150 protect it. This is the most trivial case: you initialize the mutex.
147 Then you can call mutex_lock_interruptible() t !! 151 Then you can call :c:func:`mutex_lock_interruptible()` to grab the
148 mutex, and mutex_unlock() to release it. There !! 152 mutex, and :c:func:`mutex_unlock()` to release it. There is also a
149 mutex_lock(), which should be avoided, because !! 153 :c:func:`mutex_lock()`, which should be avoided, because it will
150 not return if a signal is received. 154 not return if a signal is received.
151 155
152 Example: ``net/netfilter/nf_sockopt.c`` allows 156 Example: ``net/netfilter/nf_sockopt.c`` allows registration of new
153 setsockopt() and getsockopt() calls, with !! 157 :c:func:`setsockopt()` and :c:func:`getsockopt()` calls, with
154 nf_register_sockopt(). Registration and de-reg !! 158 :c:func:`nf_register_sockopt()`. Registration and de-registration
155 are only done on module load and unload (and b 159 are only done on module load and unload (and boot time, where there is
156 no concurrency), and the list of registrations 160 no concurrency), and the list of registrations is only consulted for an
157 unknown setsockopt() or getsockopt() system !! 161 unknown :c:func:`setsockopt()` or :c:func:`getsockopt()` system
158 call. The ``nf_sockopt_mutex`` is perfect to p 162 call. The ``nf_sockopt_mutex`` is perfect to protect this, especially
159 since the setsockopt and getsockopt calls may 163 since the setsockopt and getsockopt calls may well sleep.
160 164
161 Locking Between User Context and Softirqs 165 Locking Between User Context and Softirqs
162 ----------------------------------------- 166 -----------------------------------------
163 167
164 If a softirq shares data with user context, yo 168 If a softirq shares data with user context, you have two problems.
165 Firstly, the current user context can be inter 169 Firstly, the current user context can be interrupted by a softirq, and
166 secondly, the critical region could be entered 170 secondly, the critical region could be entered from another CPU. This is
167 where spin_lock_bh() (``include/linux/spinlock !! 171 where :c:func:`spin_lock_bh()` (``include/linux/spinlock.h``) is
168 used. It disables softirqs on that CPU, then g 172 used. It disables softirqs on that CPU, then grabs the lock.
169 spin_unlock_bh() does the reverse. (The '_bh' !! 173 :c:func:`spin_unlock_bh()` does the reverse. (The '_bh' suffix is
170 a historical reference to "Bottom Halves", the 174 a historical reference to "Bottom Halves", the old name for software
171 interrupts. It should really be called spin_lo 175 interrupts. It should really be called spin_lock_softirq()' in a
172 perfect world). 176 perfect world).
173 177
174 Note that you can also use spin_lock_irq() or !! 178 Note that you can also use :c:func:`spin_lock_irq()` or
175 spin_lock_irqsave() here, which stop hardware !! 179 :c:func:`spin_lock_irqsave()` here, which stop hardware interrupts
176 as well: see `Hard IRQ Context`_. !! 180 as well: see `Hard IRQ Context <#hardirq-context>`__.
177 181
178 This works perfectly for UP as well: the spin 182 This works perfectly for UP as well: the spin lock vanishes, and this
179 macro simply becomes local_bh_disable() !! 183 macro simply becomes :c:func:`local_bh_disable()`
180 (``include/linux/interrupt.h``), which protect 184 (``include/linux/interrupt.h``), which protects you from the softirq
181 being run. 185 being run.
182 186
183 Locking Between User Context and Tasklets 187 Locking Between User Context and Tasklets
184 ----------------------------------------- 188 -----------------------------------------
185 189
186 This is exactly the same as above, because tas 190 This is exactly the same as above, because tasklets are actually run
187 from a softirq. 191 from a softirq.
188 192
189 Locking Between User Context and Timers 193 Locking Between User Context and Timers
190 --------------------------------------- 194 ---------------------------------------
191 195
192 This, too, is exactly the same as above, becau 196 This, too, is exactly the same as above, because timers are actually run
193 from a softirq. From a locking point of view, 197 from a softirq. From a locking point of view, tasklets and timers are
194 identical. 198 identical.
195 199
196 Locking Between Tasklets/Timers 200 Locking Between Tasklets/Timers
197 ------------------------------- 201 -------------------------------
198 202
199 Sometimes a tasklet or timer might want to sha 203 Sometimes a tasklet or timer might want to share data with another
200 tasklet or timer. 204 tasklet or timer.
201 205
202 The Same Tasklet/Timer 206 The Same Tasklet/Timer
203 ~~~~~~~~~~~~~~~~~~~~~~ 207 ~~~~~~~~~~~~~~~~~~~~~~
204 208
205 Since a tasklet is never run on two CPUs at on 209 Since a tasklet is never run on two CPUs at once, you don't need to
206 worry about your tasklet being reentrant (runn 210 worry about your tasklet being reentrant (running twice at once), even
207 on SMP. 211 on SMP.
208 212
209 Different Tasklets/Timers 213 Different Tasklets/Timers
210 ~~~~~~~~~~~~~~~~~~~~~~~~~ 214 ~~~~~~~~~~~~~~~~~~~~~~~~~
211 215
212 If another tasklet/timer wants to share data w 216 If another tasklet/timer wants to share data with your tasklet or timer
213 , you will both need to use spin_lock() and !! 217 , you will both need to use :c:func:`spin_lock()` and
214 spin_unlock() calls. spin_lock_bh() is !! 218 :c:func:`spin_unlock()` calls. :c:func:`spin_lock_bh()` is
215 unnecessary here, as you are already in a task 219 unnecessary here, as you are already in a tasklet, and none will be run
216 on the same CPU. 220 on the same CPU.
217 221
218 Locking Between Softirqs 222 Locking Between Softirqs
219 ------------------------ 223 ------------------------
220 224
221 Often a softirq might want to share data with 225 Often a softirq might want to share data with itself or a tasklet/timer.
222 226
223 The Same Softirq 227 The Same Softirq
224 ~~~~~~~~~~~~~~~~ 228 ~~~~~~~~~~~~~~~~
225 229
226 The same softirq can run on the other CPUs: yo 230 The same softirq can run on the other CPUs: you can use a per-CPU array
227 (see `Per-CPU Data`_) for better performance. !! 231 (see `Per-CPU Data <#per-cpu>`__) for better performance. If you're
228 going so far as to use a softirq, you probably 232 going so far as to use a softirq, you probably care about scalable
229 performance enough to justify the extra comple 233 performance enough to justify the extra complexity.
230 234
231 You'll need to use spin_lock() and !! 235 You'll need to use :c:func:`spin_lock()` and
232 spin_unlock() for shared data. !! 236 :c:func:`spin_unlock()` for shared data.
233 237
234 Different Softirqs 238 Different Softirqs
235 ~~~~~~~~~~~~~~~~~~ 239 ~~~~~~~~~~~~~~~~~~
236 240
237 You'll need to use spin_lock() and !! 241 You'll need to use :c:func:`spin_lock()` and
238 spin_unlock() for shared data, whether it be a !! 242 :c:func:`spin_unlock()` for shared data, whether it be a timer,
239 tasklet, different softirq or the same or anot 243 tasklet, different softirq or the same or another softirq: any of them
240 could be running on a different CPU. 244 could be running on a different CPU.
241 245
242 Hard IRQ Context 246 Hard IRQ Context
243 ================ 247 ================
244 248
245 Hardware interrupts usually communicate with a 249 Hardware interrupts usually communicate with a tasklet or softirq.
246 Frequently this involves putting work in a que 250 Frequently this involves putting work in a queue, which the softirq will
247 take out. 251 take out.
248 252
249 Locking Between Hard IRQ and Softirqs/Tasklets 253 Locking Between Hard IRQ and Softirqs/Tasklets
250 ---------------------------------------------- 254 ----------------------------------------------
251 255
252 If a hardware irq handler shares data with a s 256 If a hardware irq handler shares data with a softirq, you have two
253 concerns. Firstly, the softirq processing can 257 concerns. Firstly, the softirq processing can be interrupted by a
254 hardware interrupt, and secondly, the critical 258 hardware interrupt, and secondly, the critical region could be entered
255 by a hardware interrupt on another CPU. This i 259 by a hardware interrupt on another CPU. This is where
256 spin_lock_irq() is used. It is defined to disa !! 260 :c:func:`spin_lock_irq()` is used. It is defined to disable
257 interrupts on that cpu, then grab the lock. 261 interrupts on that cpu, then grab the lock.
258 spin_unlock_irq() does the reverse. !! 262 :c:func:`spin_unlock_irq()` does the reverse.
259 263
260 The irq handler does not need to use spin_lock !! 264 The irq handler does not to use :c:func:`spin_lock_irq()`, because
261 the softirq cannot run while the irq handler i 265 the softirq cannot run while the irq handler is running: it can use
262 spin_lock(), which is slightly faster. The onl !! 266 :c:func:`spin_lock()`, which is slightly faster. The only exception
263 would be if a different hardware irq handler u 267 would be if a different hardware irq handler uses the same lock:
264 spin_lock_irq() will stop that from interrupti !! 268 :c:func:`spin_lock_irq()` will stop that from interrupting us.
265 269
266 This works perfectly for UP as well: the spin 270 This works perfectly for UP as well: the spin lock vanishes, and this
267 macro simply becomes local_irq_disable() !! 271 macro simply becomes :c:func:`local_irq_disable()`
268 (``include/asm/smp.h``), which protects you fr 272 (``include/asm/smp.h``), which protects you from the softirq/tasklet/BH
269 being run. 273 being run.
270 274
271 spin_lock_irqsave() (``include/linux/spinlock. !! 275 :c:func:`spin_lock_irqsave()` (``include/linux/spinlock.h``) is a
272 variant which saves whether interrupts were on 276 variant which saves whether interrupts were on or off in a flags word,
273 which is passed to spin_unlock_irqrestore(). T !! 277 which is passed to :c:func:`spin_unlock_irqrestore()`. This means
274 that the same code can be used inside an hard 278 that the same code can be used inside an hard irq handler (where
275 interrupts are already off) and in softirqs (w 279 interrupts are already off) and in softirqs (where the irq disabling is
276 required). 280 required).
277 281
278 Note that softirqs (and hence tasklets and tim 282 Note that softirqs (and hence tasklets and timers) are run on return
279 from hardware interrupts, so spin_lock_irq() a !! 283 from hardware interrupts, so :c:func:`spin_lock_irq()` also stops
280 these. In that sense, spin_lock_irqsave() is t !! 284 these. In that sense, :c:func:`spin_lock_irqsave()` is the most
281 general and powerful locking function. 285 general and powerful locking function.
282 286
283 Locking Between Two Hard IRQ Handlers 287 Locking Between Two Hard IRQ Handlers
284 ------------------------------------- 288 -------------------------------------
285 289
286 It is rare to have to share data between two I 290 It is rare to have to share data between two IRQ handlers, but if you
287 do, spin_lock_irqsave() should be used: it is !! 291 do, :c:func:`spin_lock_irqsave()` should be used: it is
288 architecture-specific whether all interrupts a 292 architecture-specific whether all interrupts are disabled inside irq
289 handlers themselves. 293 handlers themselves.
290 294
291 Cheat Sheet For Locking 295 Cheat Sheet For Locking
292 ======================= 296 =======================
293 297
294 Pete Zaitcev gives the following summary: 298 Pete Zaitcev gives the following summary:
295 299
296 - If you are in a process context (any syscal 300 - If you are in a process context (any syscall) and want to lock other
297 process out, use a mutex. You can take a mu 301 process out, use a mutex. You can take a mutex and sleep
298 (``copy_from_user()`` or ``kmalloc(x,GFP_KE !! 302 (``copy_from_user*(`` or ``kmalloc(x,GFP_KERNEL)``).
299 303
300 - Otherwise (== data can be touched in an int 304 - Otherwise (== data can be touched in an interrupt), use
301 spin_lock_irqsave() and !! 305 :c:func:`spin_lock_irqsave()` and
302 spin_unlock_irqrestore(). !! 306 :c:func:`spin_unlock_irqrestore()`.
303 307
304 - Avoid holding spinlock for more than 5 line 308 - Avoid holding spinlock for more than 5 lines of code and across any
305 function call (except accessors like readb( !! 309 function call (except accessors like :c:func:`readb()`).
306 310
307 Table of Minimum Requirements 311 Table of Minimum Requirements
308 ----------------------------- 312 -----------------------------
309 313
310 The following table lists the **minimum** lock 314 The following table lists the **minimum** locking requirements between
311 various contexts. In some cases, the same cont 315 various contexts. In some cases, the same context can only be running on
312 one CPU at a time, so no locking is required f 316 one CPU at a time, so no locking is required for that context (eg. a
313 particular thread can only run on one CPU at a 317 particular thread can only run on one CPU at a time, but if it needs
314 shares data with another thread, locking is re 318 shares data with another thread, locking is required).
315 319
316 Remember the advice above: you can always use 320 Remember the advice above: you can always use
317 spin_lock_irqsave(), which is a superset of al !! 321 :c:func:`spin_lock_irqsave()`, which is a superset of all other
318 spinlock primitives. 322 spinlock primitives.
319 323
320 ============== ============= ============= === 324 ============== ============= ============= ========= ========= ========= ========= ======= ======= ============== ==============
321 . IRQ Handler A IRQ Handler B Sof 325 . IRQ Handler A IRQ Handler B Softirq A Softirq B Tasklet A Tasklet B Timer A Timer B User Context A User Context B
322 ============== ============= ============= === 326 ============== ============= ============= ========= ========= ========= ========= ======= ======= ============== ==============
323 IRQ Handler A None 327 IRQ Handler A None
324 IRQ Handler B SLIS None 328 IRQ Handler B SLIS None
325 Softirq A SLI SLI SL 329 Softirq A SLI SLI SL
326 Softirq B SLI SLI SL 330 Softirq B SLI SLI SL SL
327 Tasklet A SLI SLI SL 331 Tasklet A SLI SLI SL SL None
328 Tasklet B SLI SLI SL 332 Tasklet B SLI SLI SL SL SL None
329 Timer A SLI SLI SL 333 Timer A SLI SLI SL SL SL SL None
330 Timer B SLI SLI SL 334 Timer B SLI SLI SL SL SL SL SL None
331 User Context A SLI SLI SLB 335 User Context A SLI SLI SLBH SLBH SLBH SLBH SLBH SLBH None
332 User Context B SLI SLI SLB 336 User Context B SLI SLI SLBH SLBH SLBH SLBH SLBH SLBH MLI None
333 ============== ============= ============= === 337 ============== ============= ============= ========= ========= ========= ========= ======= ======= ============== ==============
334 338
335 Table: Table of Locking Requirements 339 Table: Table of Locking Requirements
336 340
337 +--------+----------------------------+ 341 +--------+----------------------------+
338 | SLIS | spin_lock_irqsave | 342 | SLIS | spin_lock_irqsave |
339 +--------+----------------------------+ 343 +--------+----------------------------+
340 | SLI | spin_lock_irq | 344 | SLI | spin_lock_irq |
341 +--------+----------------------------+ 345 +--------+----------------------------+
342 | SL | spin_lock | 346 | SL | spin_lock |
343 +--------+----------------------------+ 347 +--------+----------------------------+
344 | SLBH | spin_lock_bh | 348 | SLBH | spin_lock_bh |
345 +--------+----------------------------+ 349 +--------+----------------------------+
346 | MLI | mutex_lock_interruptible | 350 | MLI | mutex_lock_interruptible |
347 +--------+----------------------------+ 351 +--------+----------------------------+
348 352
349 Table: Legend for Locking Requirements Table 353 Table: Legend for Locking Requirements Table
350 354
351 The trylock Functions 355 The trylock Functions
352 ===================== 356 =====================
353 357
354 There are functions that try to acquire a lock 358 There are functions that try to acquire a lock only once and immediately
355 return a value telling about success or failur 359 return a value telling about success or failure to acquire the lock.
356 They can be used if you need no access to the 360 They can be used if you need no access to the data protected with the
357 lock when some other thread is holding the loc 361 lock when some other thread is holding the lock. You should acquire the
358 lock later if you then need access to the data 362 lock later if you then need access to the data protected with the lock.
359 363
360 spin_trylock() does not spin but returns non-z !! 364 :c:func:`spin_trylock()` does not spin but returns non-zero if it
361 acquires the spinlock on the first try or 0 if 365 acquires the spinlock on the first try or 0 if not. This function can be
362 used in all contexts like spin_lock(): you mus !! 366 used in all contexts like :c:func:`spin_lock()`: you must have
363 disabled the contexts that might interrupt you 367 disabled the contexts that might interrupt you and acquire the spin
364 lock. 368 lock.
365 369
366 mutex_trylock() does not suspend your task but !! 370 :c:func:`mutex_trylock()` does not suspend your task but returns
367 non-zero if it could lock the mutex on the fir 371 non-zero if it could lock the mutex on the first try or 0 if not. This
368 function cannot be safely used in hardware or 372 function cannot be safely used in hardware or software interrupt
369 contexts despite not sleeping. 373 contexts despite not sleeping.
370 374
371 Common Examples 375 Common Examples
372 =============== 376 ===============
373 377
374 Let's step through a simple example: a cache o 378 Let's step through a simple example: a cache of number to name mappings.
375 The cache keeps a count of how often each of t 379 The cache keeps a count of how often each of the objects is used, and
376 when it gets full, throws out the least used o 380 when it gets full, throws out the least used one.
377 381
378 All In User Context 382 All In User Context
379 ------------------- 383 -------------------
380 384
381 For our first example, we assume that all oper 385 For our first example, we assume that all operations are in user context
382 (ie. from system calls), so we can sleep. This 386 (ie. from system calls), so we can sleep. This means we can use a mutex
383 to protect the cache and all the objects withi 387 to protect the cache and all the objects within it. Here's the code::
384 388
385 #include <linux/list.h> 389 #include <linux/list.h>
386 #include <linux/slab.h> 390 #include <linux/slab.h>
387 #include <linux/string.h> 391 #include <linux/string.h>
388 #include <linux/mutex.h> 392 #include <linux/mutex.h>
389 #include <asm/errno.h> 393 #include <asm/errno.h>
390 394
391 struct object 395 struct object
392 { 396 {
393 struct list_head list; 397 struct list_head list;
394 int id; 398 int id;
395 char name[32]; 399 char name[32];
396 int popularity; 400 int popularity;
397 }; 401 };
398 402
399 /* Protects the cache, cache_num, and the 403 /* Protects the cache, cache_num, and the objects within it */
400 static DEFINE_MUTEX(cache_lock); 404 static DEFINE_MUTEX(cache_lock);
401 static LIST_HEAD(cache); 405 static LIST_HEAD(cache);
402 static unsigned int cache_num = 0; 406 static unsigned int cache_num = 0;
403 #define MAX_CACHE_SIZE 10 407 #define MAX_CACHE_SIZE 10
404 408
405 /* Must be holding cache_lock */ 409 /* Must be holding cache_lock */
406 static struct object *__cache_find(int id) 410 static struct object *__cache_find(int id)
407 { 411 {
408 struct object *i; 412 struct object *i;
409 413
410 list_for_each_entry(i, &cache, lis 414 list_for_each_entry(i, &cache, list)
411 if (i->id == id) { 415 if (i->id == id) {
412 i->popularity++; 416 i->popularity++;
413 return i; 417 return i;
414 } 418 }
415 return NULL; 419 return NULL;
416 } 420 }
417 421
418 /* Must be holding cache_lock */ 422 /* Must be holding cache_lock */
419 static void __cache_delete(struct object * 423 static void __cache_delete(struct object *obj)
420 { 424 {
421 BUG_ON(!obj); 425 BUG_ON(!obj);
422 list_del(&obj->list); 426 list_del(&obj->list);
423 kfree(obj); 427 kfree(obj);
424 cache_num--; 428 cache_num--;
425 } 429 }
426 430
427 /* Must be holding cache_lock */ 431 /* Must be holding cache_lock */
428 static void __cache_add(struct object *obj 432 static void __cache_add(struct object *obj)
429 { 433 {
430 list_add(&obj->list, &cache); 434 list_add(&obj->list, &cache);
431 if (++cache_num > MAX_CACHE_SIZE) 435 if (++cache_num > MAX_CACHE_SIZE) {
432 struct object *i, *outcast 436 struct object *i, *outcast = NULL;
433 list_for_each_entry(i, &ca 437 list_for_each_entry(i, &cache, list) {
434 if (!outcast || i- 438 if (!outcast || i->popularity < outcast->popularity)
435 outcast = 439 outcast = i;
436 } 440 }
437 __cache_delete(outcast); 441 __cache_delete(outcast);
438 } 442 }
439 } 443 }
440 444
441 int cache_add(int id, const char *name) 445 int cache_add(int id, const char *name)
442 { 446 {
443 struct object *obj; 447 struct object *obj;
444 448
445 if ((obj = kmalloc(sizeof(*obj), G 449 if ((obj = kmalloc(sizeof(*obj), GFP_KERNEL)) == NULL)
446 return -ENOMEM; 450 return -ENOMEM;
447 451
448 strscpy(obj->name, name, sizeof(ob !! 452 strlcpy(obj->name, name, sizeof(obj->name));
449 obj->id = id; 453 obj->id = id;
450 obj->popularity = 0; 454 obj->popularity = 0;
451 455
452 mutex_lock(&cache_lock); 456 mutex_lock(&cache_lock);
453 __cache_add(obj); 457 __cache_add(obj);
454 mutex_unlock(&cache_lock); 458 mutex_unlock(&cache_lock);
455 return 0; 459 return 0;
456 } 460 }
457 461
458 void cache_delete(int id) 462 void cache_delete(int id)
459 { 463 {
460 mutex_lock(&cache_lock); 464 mutex_lock(&cache_lock);
461 __cache_delete(__cache_find(id)); 465 __cache_delete(__cache_find(id));
462 mutex_unlock(&cache_lock); 466 mutex_unlock(&cache_lock);
463 } 467 }
464 468
465 int cache_find(int id, char *name) 469 int cache_find(int id, char *name)
466 { 470 {
467 struct object *obj; 471 struct object *obj;
468 int ret = -ENOENT; 472 int ret = -ENOENT;
469 473
470 mutex_lock(&cache_lock); 474 mutex_lock(&cache_lock);
471 obj = __cache_find(id); 475 obj = __cache_find(id);
472 if (obj) { 476 if (obj) {
473 ret = 0; 477 ret = 0;
474 strcpy(name, obj->name); 478 strcpy(name, obj->name);
475 } 479 }
476 mutex_unlock(&cache_lock); 480 mutex_unlock(&cache_lock);
477 return ret; 481 return ret;
478 } 482 }
479 483
480 Note that we always make sure we have the cach 484 Note that we always make sure we have the cache_lock when we add,
481 delete, or look up the cache: both the cache i 485 delete, or look up the cache: both the cache infrastructure itself and
482 the contents of the objects are protected by t 486 the contents of the objects are protected by the lock. In this case it's
483 easy, since we copy the data for the user, and 487 easy, since we copy the data for the user, and never let them access the
484 objects directly. 488 objects directly.
485 489
486 There is a slight (and common) optimization he 490 There is a slight (and common) optimization here: in
487 cache_add() we set up the fields of the object !! 491 :c:func:`cache_add()` we set up the fields of the object before
488 grabbing the lock. This is safe, as no-one els 492 grabbing the lock. This is safe, as no-one else can access it until we
489 put it in cache. 493 put it in cache.
490 494
491 Accessing From Interrupt Context 495 Accessing From Interrupt Context
492 -------------------------------- 496 --------------------------------
493 497
494 Now consider the case where cache_find() can b !! 498 Now consider the case where :c:func:`cache_find()` can be called
495 from interrupt context: either a hardware inte 499 from interrupt context: either a hardware interrupt or a softirq. An
496 example would be a timer which deletes object 500 example would be a timer which deletes object from the cache.
497 501
498 The change is shown below, in standard patch f 502 The change is shown below, in standard patch format: the ``-`` are lines
499 which are taken away, and the ``+`` are lines 503 which are taken away, and the ``+`` are lines which are added.
500 504
501 :: 505 ::
502 506
503 --- cache.c.usercontext 2003-12-09 13:58:5 507 --- cache.c.usercontext 2003-12-09 13:58:54.000000000 +1100
504 +++ cache.c.interrupt 2003-12-09 14:07:4 508 +++ cache.c.interrupt 2003-12-09 14:07:49.000000000 +1100
505 @@ -12,7 +12,7 @@ 509 @@ -12,7 +12,7 @@
506 int popularity; 510 int popularity;
507 }; 511 };
508 512
509 -static DEFINE_MUTEX(cache_lock); 513 -static DEFINE_MUTEX(cache_lock);
510 +static DEFINE_SPINLOCK(cache_lock); 514 +static DEFINE_SPINLOCK(cache_lock);
511 static LIST_HEAD(cache); 515 static LIST_HEAD(cache);
512 static unsigned int cache_num = 0; 516 static unsigned int cache_num = 0;
513 #define MAX_CACHE_SIZE 10 517 #define MAX_CACHE_SIZE 10
514 @@ -55,6 +55,7 @@ 518 @@ -55,6 +55,7 @@
515 int cache_add(int id, const char *name) 519 int cache_add(int id, const char *name)
516 { 520 {
517 struct object *obj; 521 struct object *obj;
518 + unsigned long flags; 522 + unsigned long flags;
519 523
520 if ((obj = kmalloc(sizeof(*obj), 524 if ((obj = kmalloc(sizeof(*obj), GFP_KERNEL)) == NULL)
521 return -ENOMEM; 525 return -ENOMEM;
522 @@ -63,30 +64,33 @@ 526 @@ -63,30 +64,33 @@
523 obj->id = id; 527 obj->id = id;
524 obj->popularity = 0; 528 obj->popularity = 0;
525 529
526 - mutex_lock(&cache_lock); 530 - mutex_lock(&cache_lock);
527 + spin_lock_irqsave(&cache_lock, fl 531 + spin_lock_irqsave(&cache_lock, flags);
528 __cache_add(obj); 532 __cache_add(obj);
529 - mutex_unlock(&cache_lock); 533 - mutex_unlock(&cache_lock);
530 + spin_unlock_irqrestore(&cache_loc 534 + spin_unlock_irqrestore(&cache_lock, flags);
531 return 0; 535 return 0;
532 } 536 }
533 537
534 void cache_delete(int id) 538 void cache_delete(int id)
535 { 539 {
536 - mutex_lock(&cache_lock); 540 - mutex_lock(&cache_lock);
537 + unsigned long flags; 541 + unsigned long flags;
538 + 542 +
539 + spin_lock_irqsave(&cache_lock, fl 543 + spin_lock_irqsave(&cache_lock, flags);
540 __cache_delete(__cache_find(id)); 544 __cache_delete(__cache_find(id));
541 - mutex_unlock(&cache_lock); 545 - mutex_unlock(&cache_lock);
542 + spin_unlock_irqrestore(&cache_loc 546 + spin_unlock_irqrestore(&cache_lock, flags);
543 } 547 }
544 548
545 int cache_find(int id, char *name) 549 int cache_find(int id, char *name)
546 { 550 {
547 struct object *obj; 551 struct object *obj;
548 int ret = -ENOENT; 552 int ret = -ENOENT;
549 + unsigned long flags; 553 + unsigned long flags;
550 554
551 - mutex_lock(&cache_lock); 555 - mutex_lock(&cache_lock);
552 + spin_lock_irqsave(&cache_lock, fl 556 + spin_lock_irqsave(&cache_lock, flags);
553 obj = __cache_find(id); 557 obj = __cache_find(id);
554 if (obj) { 558 if (obj) {
555 ret = 0; 559 ret = 0;
556 strcpy(name, obj->name); 560 strcpy(name, obj->name);
557 } 561 }
558 - mutex_unlock(&cache_lock); 562 - mutex_unlock(&cache_lock);
559 + spin_unlock_irqrestore(&cache_loc 563 + spin_unlock_irqrestore(&cache_lock, flags);
560 return ret; 564 return ret;
561 } 565 }
562 566
563 Note that the spin_lock_irqsave() will turn of !! 567 Note that the :c:func:`spin_lock_irqsave()` will turn off
564 interrupts if they are on, otherwise does noth 568 interrupts if they are on, otherwise does nothing (if we are already in
565 an interrupt handler), hence these functions a 569 an interrupt handler), hence these functions are safe to call from any
566 context. 570 context.
567 571
568 Unfortunately, cache_add() calls kmalloc() !! 572 Unfortunately, :c:func:`cache_add()` calls :c:func:`kmalloc()`
569 with the ``GFP_KERNEL`` flag, which is only le 573 with the ``GFP_KERNEL`` flag, which is only legal in user context. I
570 have assumed that cache_add() is still only ca !! 574 have assumed that :c:func:`cache_add()` is still only called in
571 user context, otherwise this should become a p 575 user context, otherwise this should become a parameter to
572 cache_add(). !! 576 :c:func:`cache_add()`.
573 577
574 Exposing Objects Outside This File 578 Exposing Objects Outside This File
575 ---------------------------------- 579 ----------------------------------
576 580
577 If our objects contained more information, it 581 If our objects contained more information, it might not be sufficient to
578 copy the information in and out: other parts o 582 copy the information in and out: other parts of the code might want to
579 keep pointers to these objects, for example, r 583 keep pointers to these objects, for example, rather than looking up the
580 id every time. This produces two problems. 584 id every time. This produces two problems.
581 585
582 The first problem is that we use the ``cache_l 586 The first problem is that we use the ``cache_lock`` to protect objects:
583 we'd need to make this non-static so the rest 587 we'd need to make this non-static so the rest of the code can use it.
584 This makes locking trickier, as it is no longe 588 This makes locking trickier, as it is no longer all in one place.
585 589
586 The second problem is the lifetime problem: if 590 The second problem is the lifetime problem: if another structure keeps a
587 pointer to an object, it presumably expects th 591 pointer to an object, it presumably expects that pointer to remain
588 valid. Unfortunately, this is only guaranteed 592 valid. Unfortunately, this is only guaranteed while you hold the lock,
589 otherwise someone might call cache_delete() an !! 593 otherwise someone might call :c:func:`cache_delete()` and even
590 worse, add another object, re-using the same a 594 worse, add another object, re-using the same address.
591 595
592 As there is only one lock, you can't hold it f 596 As there is only one lock, you can't hold it forever: no-one else would
593 get any work done. 597 get any work done.
594 598
595 The solution to this problem is to use a refer 599 The solution to this problem is to use a reference count: everyone who
596 has a pointer to the object increases it when 600 has a pointer to the object increases it when they first get the object,
597 and drops the reference count when they're fin 601 and drops the reference count when they're finished with it. Whoever
598 drops it to zero knows it is unused, and can a 602 drops it to zero knows it is unused, and can actually delete it.
599 603
600 Here is the code:: 604 Here is the code::
601 605
602 --- cache.c.interrupt 2003-12-09 14:25:4 606 --- cache.c.interrupt 2003-12-09 14:25:43.000000000 +1100
603 +++ cache.c.refcnt 2003-12-09 14:33:05.00 607 +++ cache.c.refcnt 2003-12-09 14:33:05.000000000 +1100
604 @@ -7,6 +7,7 @@ 608 @@ -7,6 +7,7 @@
605 struct object 609 struct object
606 { 610 {
607 struct list_head list; 611 struct list_head list;
608 + unsigned int refcnt; 612 + unsigned int refcnt;
609 int id; 613 int id;
610 char name[32]; 614 char name[32];
611 int popularity; 615 int popularity;
612 @@ -17,6 +18,35 @@ 616 @@ -17,6 +18,35 @@
613 static unsigned int cache_num = 0; 617 static unsigned int cache_num = 0;
614 #define MAX_CACHE_SIZE 10 618 #define MAX_CACHE_SIZE 10
615 619
616 +static void __object_put(struct object *o 620 +static void __object_put(struct object *obj)
617 +{ 621 +{
618 + if (--obj->refcnt == 0) 622 + if (--obj->refcnt == 0)
619 + kfree(obj); 623 + kfree(obj);
620 +} 624 +}
621 + 625 +
622 +static void __object_get(struct object *o 626 +static void __object_get(struct object *obj)
623 +{ 627 +{
624 + obj->refcnt++; 628 + obj->refcnt++;
625 +} 629 +}
626 + 630 +
627 +void object_put(struct object *obj) 631 +void object_put(struct object *obj)
628 +{ 632 +{
629 + unsigned long flags; 633 + unsigned long flags;
630 + 634 +
631 + spin_lock_irqsave(&cache_lock, fl 635 + spin_lock_irqsave(&cache_lock, flags);
632 + __object_put(obj); 636 + __object_put(obj);
633 + spin_unlock_irqrestore(&cache_loc 637 + spin_unlock_irqrestore(&cache_lock, flags);
634 +} 638 +}
635 + 639 +
636 +void object_get(struct object *obj) 640 +void object_get(struct object *obj)
637 +{ 641 +{
638 + unsigned long flags; 642 + unsigned long flags;
639 + 643 +
640 + spin_lock_irqsave(&cache_lock, fl 644 + spin_lock_irqsave(&cache_lock, flags);
641 + __object_get(obj); 645 + __object_get(obj);
642 + spin_unlock_irqrestore(&cache_loc 646 + spin_unlock_irqrestore(&cache_lock, flags);
643 +} 647 +}
644 + 648 +
645 /* Must be holding cache_lock */ 649 /* Must be holding cache_lock */
646 static struct object *__cache_find(int id 650 static struct object *__cache_find(int id)
647 { 651 {
648 @@ -35,6 +65,7 @@ 652 @@ -35,6 +65,7 @@
649 { 653 {
650 BUG_ON(!obj); 654 BUG_ON(!obj);
651 list_del(&obj->list); 655 list_del(&obj->list);
652 + __object_put(obj); 656 + __object_put(obj);
653 cache_num--; 657 cache_num--;
654 } 658 }
655 659
656 @@ -63,6 +94,7 @@ 660 @@ -63,6 +94,7 @@
657 strscpy(obj->name, name, sizeof(o !! 661 strlcpy(obj->name, name, sizeof(obj->name));
658 obj->id = id; 662 obj->id = id;
659 obj->popularity = 0; 663 obj->popularity = 0;
660 + obj->refcnt = 1; /* The cache hol 664 + obj->refcnt = 1; /* The cache holds a reference */
661 665
662 spin_lock_irqsave(&cache_lock, fl 666 spin_lock_irqsave(&cache_lock, flags);
663 __cache_add(obj); 667 __cache_add(obj);
664 @@ -79,18 +111,15 @@ 668 @@ -79,18 +111,15 @@
665 spin_unlock_irqrestore(&cache_loc 669 spin_unlock_irqrestore(&cache_lock, flags);
666 } 670 }
667 671
668 -int cache_find(int id, char *name) 672 -int cache_find(int id, char *name)
669 +struct object *cache_find(int id) 673 +struct object *cache_find(int id)
670 { 674 {
671 struct object *obj; 675 struct object *obj;
672 - int ret = -ENOENT; 676 - int ret = -ENOENT;
673 unsigned long flags; 677 unsigned long flags;
674 678
675 spin_lock_irqsave(&cache_lock, fl 679 spin_lock_irqsave(&cache_lock, flags);
676 obj = __cache_find(id); 680 obj = __cache_find(id);
677 - if (obj) { 681 - if (obj) {
678 - ret = 0; 682 - ret = 0;
679 - strcpy(name, obj->name); 683 - strcpy(name, obj->name);
680 - } 684 - }
681 + if (obj) 685 + if (obj)
682 + __object_get(obj); 686 + __object_get(obj);
683 spin_unlock_irqrestore(&cache_loc 687 spin_unlock_irqrestore(&cache_lock, flags);
684 - return ret; 688 - return ret;
685 + return obj; 689 + return obj;
686 } 690 }
687 691
688 We encapsulate the reference counting in the s 692 We encapsulate the reference counting in the standard 'get' and 'put'
689 functions. Now we can return the object itself 693 functions. Now we can return the object itself from
690 cache_find() which has the advantage that the !! 694 :c:func:`cache_find()` which has the advantage that the user can
691 now sleep holding the object (eg. to copy_to_u !! 695 now sleep holding the object (eg. to :c:func:`copy_to_user()` to
692 name to userspace). 696 name to userspace).
693 697
694 The other point to note is that I said a refer 698 The other point to note is that I said a reference should be held for
695 every pointer to the object: thus the referenc 699 every pointer to the object: thus the reference count is 1 when first
696 inserted into the cache. In some versions the 700 inserted into the cache. In some versions the framework does not hold a
697 reference count, but they are more complicated 701 reference count, but they are more complicated.
698 702
699 Using Atomic Operations For The Reference Coun 703 Using Atomic Operations For The Reference Count
700 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 704 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
701 705
702 In practice, :c:type:`atomic_t` would usually 706 In practice, :c:type:`atomic_t` would usually be used for refcnt. There are a
703 number of atomic operations defined in ``inclu 707 number of atomic operations defined in ``include/asm/atomic.h``: these
704 are guaranteed to be seen atomically from all 708 are guaranteed to be seen atomically from all CPUs in the system, so no
705 lock is required. In this case, it is simpler 709 lock is required. In this case, it is simpler than using spinlocks,
706 although for anything non-trivial using spinlo 710 although for anything non-trivial using spinlocks is clearer. The
707 atomic_inc() and atomic_dec_and_test() !! 711 :c:func:`atomic_inc()` and :c:func:`atomic_dec_and_test()`
708 are used instead of the standard increment and 712 are used instead of the standard increment and decrement operators, and
709 the lock is no longer used to protect the refe 713 the lock is no longer used to protect the reference count itself.
710 714
711 :: 715 ::
712 716
713 --- cache.c.refcnt 2003-12-09 15:00:35.00 717 --- cache.c.refcnt 2003-12-09 15:00:35.000000000 +1100
714 +++ cache.c.refcnt-atomic 2003-12-11 15: 718 +++ cache.c.refcnt-atomic 2003-12-11 15:49:42.000000000 +1100
715 @@ -7,7 +7,7 @@ 719 @@ -7,7 +7,7 @@
716 struct object 720 struct object
717 { 721 {
718 struct list_head list; 722 struct list_head list;
719 - unsigned int refcnt; 723 - unsigned int refcnt;
720 + atomic_t refcnt; 724 + atomic_t refcnt;
721 int id; 725 int id;
722 char name[32]; 726 char name[32];
723 int popularity; 727 int popularity;
724 @@ -18,33 +18,15 @@ 728 @@ -18,33 +18,15 @@
725 static unsigned int cache_num = 0; 729 static unsigned int cache_num = 0;
726 #define MAX_CACHE_SIZE 10 730 #define MAX_CACHE_SIZE 10
727 731
728 -static void __object_put(struct object *o 732 -static void __object_put(struct object *obj)
729 -{ 733 -{
730 - if (--obj->refcnt == 0) 734 - if (--obj->refcnt == 0)
731 - kfree(obj); 735 - kfree(obj);
732 -} 736 -}
733 - 737 -
734 -static void __object_get(struct object *o 738 -static void __object_get(struct object *obj)
735 -{ 739 -{
736 - obj->refcnt++; 740 - obj->refcnt++;
737 -} 741 -}
738 - 742 -
739 void object_put(struct object *obj) 743 void object_put(struct object *obj)
740 { 744 {
741 - unsigned long flags; 745 - unsigned long flags;
742 - 746 -
743 - spin_lock_irqsave(&cache_lock, fl 747 - spin_lock_irqsave(&cache_lock, flags);
744 - __object_put(obj); 748 - __object_put(obj);
745 - spin_unlock_irqrestore(&cache_loc 749 - spin_unlock_irqrestore(&cache_lock, flags);
746 + if (atomic_dec_and_test(&obj->ref 750 + if (atomic_dec_and_test(&obj->refcnt))
747 + kfree(obj); 751 + kfree(obj);
748 } 752 }
749 753
750 void object_get(struct object *obj) 754 void object_get(struct object *obj)
751 { 755 {
752 - unsigned long flags; 756 - unsigned long flags;
753 - 757 -
754 - spin_lock_irqsave(&cache_lock, fl 758 - spin_lock_irqsave(&cache_lock, flags);
755 - __object_get(obj); 759 - __object_get(obj);
756 - spin_unlock_irqrestore(&cache_loc 760 - spin_unlock_irqrestore(&cache_lock, flags);
757 + atomic_inc(&obj->refcnt); 761 + atomic_inc(&obj->refcnt);
758 } 762 }
759 763
760 /* Must be holding cache_lock */ 764 /* Must be holding cache_lock */
761 @@ -65,7 +47,7 @@ 765 @@ -65,7 +47,7 @@
762 { 766 {
763 BUG_ON(!obj); 767 BUG_ON(!obj);
764 list_del(&obj->list); 768 list_del(&obj->list);
765 - __object_put(obj); 769 - __object_put(obj);
766 + object_put(obj); 770 + object_put(obj);
767 cache_num--; 771 cache_num--;
768 } 772 }
769 773
770 @@ -94,7 +76,7 @@ 774 @@ -94,7 +76,7 @@
771 strscpy(obj->name, name, sizeof(o !! 775 strlcpy(obj->name, name, sizeof(obj->name));
772 obj->id = id; 776 obj->id = id;
773 obj->popularity = 0; 777 obj->popularity = 0;
774 - obj->refcnt = 1; /* The cache hol 778 - obj->refcnt = 1; /* The cache holds a reference */
775 + atomic_set(&obj->refcnt, 1); /* T 779 + atomic_set(&obj->refcnt, 1); /* The cache holds a reference */
776 780
777 spin_lock_irqsave(&cache_lock, fl 781 spin_lock_irqsave(&cache_lock, flags);
778 __cache_add(obj); 782 __cache_add(obj);
779 @@ -119,7 +101,7 @@ 783 @@ -119,7 +101,7 @@
780 spin_lock_irqsave(&cache_lock, fl 784 spin_lock_irqsave(&cache_lock, flags);
781 obj = __cache_find(id); 785 obj = __cache_find(id);
782 if (obj) 786 if (obj)
783 - __object_get(obj); 787 - __object_get(obj);
784 + object_get(obj); 788 + object_get(obj);
785 spin_unlock_irqrestore(&cache_loc 789 spin_unlock_irqrestore(&cache_lock, flags);
786 return obj; 790 return obj;
787 } 791 }
788 792
789 Protecting The Objects Themselves 793 Protecting The Objects Themselves
790 --------------------------------- 794 ---------------------------------
791 795
792 In these examples, we assumed that the objects 796 In these examples, we assumed that the objects (except the reference
793 counts) never changed once they are created. I 797 counts) never changed once they are created. If we wanted to allow the
794 name to change, there are three possibilities: 798 name to change, there are three possibilities:
795 799
796 - You can make ``cache_lock`` non-static, and 800 - You can make ``cache_lock`` non-static, and tell people to grab that
797 lock before changing the name in any object 801 lock before changing the name in any object.
798 802
799 - You can provide a cache_obj_rename() which !! 803 - You can provide a :c:func:`cache_obj_rename()` which grabs this
800 lock and changes the name for the caller, a 804 lock and changes the name for the caller, and tell everyone to use
801 that function. 805 that function.
802 806
803 - You can make the ``cache_lock`` protect onl 807 - You can make the ``cache_lock`` protect only the cache itself, and
804 use another lock to protect the name. 808 use another lock to protect the name.
805 809
806 Theoretically, you can make the locks as fine- 810 Theoretically, you can make the locks as fine-grained as one lock for
807 every field, for every object. In practice, th 811 every field, for every object. In practice, the most common variants
808 are: 812 are:
809 813
810 - One lock which protects the infrastructure 814 - One lock which protects the infrastructure (the ``cache`` list in
811 this example) and all the objects. This is 815 this example) and all the objects. This is what we have done so far.
812 816
813 - One lock which protects the infrastructure 817 - One lock which protects the infrastructure (including the list
814 pointers inside the objects), and one lock 818 pointers inside the objects), and one lock inside the object which
815 protects the rest of that object. 819 protects the rest of that object.
816 820
817 - Multiple locks to protect the infrastructur 821 - Multiple locks to protect the infrastructure (eg. one lock per hash
818 chain), possibly with a separate per-object 822 chain), possibly with a separate per-object lock.
819 823
820 Here is the "lock-per-object" implementation: 824 Here is the "lock-per-object" implementation:
821 825
822 :: 826 ::
823 827
824 --- cache.c.refcnt-atomic 2003-12-11 15: 828 --- cache.c.refcnt-atomic 2003-12-11 15:50:54.000000000 +1100
825 +++ cache.c.perobjectlock 2003-12-11 17: 829 +++ cache.c.perobjectlock 2003-12-11 17:15:03.000000000 +1100
826 @@ -6,11 +6,17 @@ 830 @@ -6,11 +6,17 @@
827 831
828 struct object 832 struct object
829 { 833 {
830 + /* These two protected by cache_l 834 + /* These two protected by cache_lock. */
831 struct list_head list; 835 struct list_head list;
832 + int popularity; 836 + int popularity;
833 + 837 +
834 atomic_t refcnt; 838 atomic_t refcnt;
835 + 839 +
836 + /* Doesn't change once created. * 840 + /* Doesn't change once created. */
837 int id; 841 int id;
838 + 842 +
839 + spinlock_t lock; /* Protects the 843 + spinlock_t lock; /* Protects the name */
840 char name[32]; 844 char name[32];
841 - int popularity; 845 - int popularity;
842 }; 846 };
843 847
844 static DEFINE_SPINLOCK(cache_lock); 848 static DEFINE_SPINLOCK(cache_lock);
845 @@ -77,6 +84,7 @@ 849 @@ -77,6 +84,7 @@
846 obj->id = id; 850 obj->id = id;
847 obj->popularity = 0; 851 obj->popularity = 0;
848 atomic_set(&obj->refcnt, 1); /* T 852 atomic_set(&obj->refcnt, 1); /* The cache holds a reference */
849 + spin_lock_init(&obj->lock); 853 + spin_lock_init(&obj->lock);
850 854
851 spin_lock_irqsave(&cache_lock, fl 855 spin_lock_irqsave(&cache_lock, flags);
852 __cache_add(obj); 856 __cache_add(obj);
853 857
854 Note that I decide that the popularity count s 858 Note that I decide that the popularity count should be protected by the
855 ``cache_lock`` rather than the per-object lock 859 ``cache_lock`` rather than the per-object lock: this is because it (like
856 the :c:type:`struct list_head <list_head>` ins 860 the :c:type:`struct list_head <list_head>` inside the object)
857 is logically part of the infrastructure. This 861 is logically part of the infrastructure. This way, I don't need to grab
858 the lock of every object in __cache_add() when !! 862 the lock of every object in :c:func:`__cache_add()` when seeking
859 the least popular. 863 the least popular.
860 864
861 I also decided that the id member is unchangea 865 I also decided that the id member is unchangeable, so I don't need to
862 grab each object lock in __cache_find() to exa !! 866 grab each object lock in :c:func:`__cache_find()` to examine the
863 id: the object lock is only used by a caller w 867 id: the object lock is only used by a caller who wants to read or write
864 the name field. 868 the name field.
865 869
866 Note also that I added a comment describing wh 870 Note also that I added a comment describing what data was protected by
867 which locks. This is extremely important, as i 871 which locks. This is extremely important, as it describes the runtime
868 behavior of the code, and can be hard to gain 872 behavior of the code, and can be hard to gain from just reading. And as
869 Alan Cox says, “Lock data, not code”. 873 Alan Cox says, “Lock data, not code”.
870 874
871 Common Problems 875 Common Problems
872 =============== 876 ===============
873 877
874 Deadlock: Simple and Advanced 878 Deadlock: Simple and Advanced
875 ----------------------------- 879 -----------------------------
876 880
877 There is a coding bug where a piece of code tr 881 There is a coding bug where a piece of code tries to grab a spinlock
878 twice: it will spin forever, waiting for the l 882 twice: it will spin forever, waiting for the lock to be released
879 (spinlocks, rwlocks and mutexes are not recurs 883 (spinlocks, rwlocks and mutexes are not recursive in Linux). This is
880 trivial to diagnose: not a 884 trivial to diagnose: not a
881 stay-up-five-nights-talk-to-fluffy-code-bunnie 885 stay-up-five-nights-talk-to-fluffy-code-bunnies kind of problem.
882 886
883 For a slightly more complex case, imagine you 887 For a slightly more complex case, imagine you have a region shared by a
884 softirq and user context. If you use a spin_lo !! 888 softirq and user context. If you use a :c:func:`spin_lock()` call
885 to protect it, it is possible that the user co 889 to protect it, it is possible that the user context will be interrupted
886 by the softirq while it holds the lock, and th 890 by the softirq while it holds the lock, and the softirq will then spin
887 forever trying to get the same lock. 891 forever trying to get the same lock.
888 892
889 Both of these are called deadlock, and as show 893 Both of these are called deadlock, and as shown above, it can occur even
890 with a single CPU (although not on UP compiles 894 with a single CPU (although not on UP compiles, since spinlocks vanish
891 on kernel compiles with ``CONFIG_SMP``\ =n. Yo 895 on kernel compiles with ``CONFIG_SMP``\ =n. You'll still get data
892 corruption in the second example). 896 corruption in the second example).
893 897
894 This complete lockup is easy to diagnose: on S 898 This complete lockup is easy to diagnose: on SMP boxes the watchdog
895 timer or compiling with ``DEBUG_SPINLOCK`` set 899 timer or compiling with ``DEBUG_SPINLOCK`` set
896 (``include/linux/spinlock.h``) will show this 900 (``include/linux/spinlock.h``) will show this up immediately when it
897 happens. 901 happens.
898 902
899 A more complex problem is the so-called 'deadl 903 A more complex problem is the so-called 'deadly embrace', involving two
900 or more locks. Say you have a hash table: each 904 or more locks. Say you have a hash table: each entry in the table is a
901 spinlock, and a chain of hashed objects. Insid 905 spinlock, and a chain of hashed objects. Inside a softirq handler, you
902 sometimes want to alter an object from one pla 906 sometimes want to alter an object from one place in the hash to another:
903 you grab the spinlock of the old hash chain an 907 you grab the spinlock of the old hash chain and the spinlock of the new
904 hash chain, and delete the object from the old 908 hash chain, and delete the object from the old one, and insert it in the
905 new one. 909 new one.
906 910
907 There are two problems here. First, if your co 911 There are two problems here. First, if your code ever tries to move the
908 object to the same chain, it will deadlock wit 912 object to the same chain, it will deadlock with itself as it tries to
909 lock it twice. Secondly, if the same softirq o 913 lock it twice. Secondly, if the same softirq on another CPU is trying to
910 move another object in the reverse direction, 914 move another object in the reverse direction, the following could
911 happen: 915 happen:
912 916
913 +-----------------------+--------------------- 917 +-----------------------+-----------------------+
914 | CPU 1 | CPU 2 918 | CPU 1 | CPU 2 |
915 +=======================+===================== 919 +=======================+=======================+
916 | Grab lock A -> OK | Grab lock B -> OK 920 | Grab lock A -> OK | Grab lock B -> OK |
917 +-----------------------+--------------------- 921 +-----------------------+-----------------------+
918 | Grab lock B -> spin | Grab lock A -> spin 922 | Grab lock B -> spin | Grab lock A -> spin |
919 +-----------------------+--------------------- 923 +-----------------------+-----------------------+
920 924
921 Table: Consequences 925 Table: Consequences
922 926
923 The two CPUs will spin forever, waiting for th 927 The two CPUs will spin forever, waiting for the other to give up their
924 lock. It will look, smell, and feel like a cra 928 lock. It will look, smell, and feel like a crash.
925 929
926 Preventing Deadlock 930 Preventing Deadlock
927 ------------------- 931 -------------------
928 932
929 Textbooks will tell you that if you always loc 933 Textbooks will tell you that if you always lock in the same order, you
930 will never get this kind of deadlock. Practice 934 will never get this kind of deadlock. Practice will tell you that this
931 approach doesn't scale: when I create a new lo 935 approach doesn't scale: when I create a new lock, I don't understand
932 enough of the kernel to figure out where in th 936 enough of the kernel to figure out where in the 5000 lock hierarchy it
933 will fit. 937 will fit.
934 938
935 The best locks are encapsulated: they never ge 939 The best locks are encapsulated: they never get exposed in headers, and
936 are never held around calls to non-trivial fun 940 are never held around calls to non-trivial functions outside the same
937 file. You can read through this code and see t 941 file. You can read through this code and see that it will never
938 deadlock, because it never tries to grab anoth 942 deadlock, because it never tries to grab another lock while it has that
939 one. People using your code don't even need to 943 one. People using your code don't even need to know you are using a
940 lock. 944 lock.
941 945
942 A classic problem here is when you provide cal 946 A classic problem here is when you provide callbacks or hooks: if you
943 call these with the lock held, you risk simple 947 call these with the lock held, you risk simple deadlock, or a deadly
944 embrace (who knows what the callback will do?) !! 948 embrace (who knows what the callback will do?). Remember, the other
>> 949 programmers are out to get you, so don't do this.
945 950
946 Overzealous Prevention Of Deadlocks 951 Overzealous Prevention Of Deadlocks
947 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 952 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
948 953
949 Deadlocks are problematic, but not as bad as d 954 Deadlocks are problematic, but not as bad as data corruption. Code which
950 grabs a read lock, searches a list, fails to f 955 grabs a read lock, searches a list, fails to find what it wants, drops
951 the read lock, grabs a write lock and inserts 956 the read lock, grabs a write lock and inserts the object has a race
952 condition. 957 condition.
953 958
>> 959 If you don't see why, please stay the fuck away from my code.
>> 960
954 Racing Timers: A Kernel Pastime 961 Racing Timers: A Kernel Pastime
955 ------------------------------- 962 -------------------------------
956 963
957 Timers can produce their own special problems 964 Timers can produce their own special problems with races. Consider a
958 collection of objects (list, hash, etc) where 965 collection of objects (list, hash, etc) where each object has a timer
959 which is due to destroy it. 966 which is due to destroy it.
960 967
961 If you want to destroy the entire collection ( 968 If you want to destroy the entire collection (say on module removal),
962 you might do the following:: 969 you might do the following::
963 970
964 /* THIS CODE BAD BAD BAD BAD: IF I 971 /* THIS CODE BAD BAD BAD BAD: IF IT WAS ANY WORSE IT WOULD USE
965 HUNGARIAN NOTATION */ 972 HUNGARIAN NOTATION */
966 spin_lock_bh(&list_lock); 973 spin_lock_bh(&list_lock);
967 974
968 while (list) { 975 while (list) {
969 struct foo *next = list->n 976 struct foo *next = list->next;
970 timer_delete(&list->timer) !! 977 del_timer(&list->timer);
971 kfree(list); 978 kfree(list);
972 list = next; 979 list = next;
973 } 980 }
974 981
975 spin_unlock_bh(&list_lock); 982 spin_unlock_bh(&list_lock);
976 983
977 984
978 Sooner or later, this will crash on SMP, becau 985 Sooner or later, this will crash on SMP, because a timer can have just
979 gone off before the spin_lock_bh(), and it wil !! 986 gone off before the :c:func:`spin_lock_bh()`, and it will only get
980 the lock after we spin_unlock_bh(), and then t !! 987 the lock after we :c:func:`spin_unlock_bh()`, and then try to free
981 the element (which has already been freed!). 988 the element (which has already been freed!).
982 989
983 This can be avoided by checking the result of 990 This can be avoided by checking the result of
984 timer_delete(): if it returns 1, the timer has !! 991 :c:func:`del_timer()`: if it returns 1, the timer has been deleted.
985 If 0, it means (in this case) that it is curre 992 If 0, it means (in this case) that it is currently running, so we can
986 do:: 993 do::
987 994
988 retry: 995 retry:
989 spin_lock_bh(&list_lock); 996 spin_lock_bh(&list_lock);
990 997
991 while (list) { 998 while (list) {
992 struct foo *next = 999 struct foo *next = list->next;
993 if (!timer_delete( !! 1000 if (!del_timer(&list->timer)) {
994 /* Give ti 1001 /* Give timer a chance to delete this */
995 spin_unloc 1002 spin_unlock_bh(&list_lock);
996 goto retry 1003 goto retry;
997 } 1004 }
998 kfree(list); 1005 kfree(list);
999 list = next; 1006 list = next;
1000 } 1007 }
1001 1008
1002 spin_unlock_bh(&list_lock 1009 spin_unlock_bh(&list_lock);
1003 1010
1004 1011
1005 Another common problem is deleting timers whi 1012 Another common problem is deleting timers which restart themselves (by
1006 calling add_timer() at the end of their timer !! 1013 calling :c:func:`add_timer()` at the end of their timer function).
1007 Because this is a fairly common case which is 1014 Because this is a fairly common case which is prone to races, you should
1008 use timer_delete_sync() (``include/linux/time !! 1015 use :c:func:`del_timer_sync()` (``include/linux/timer.h``) to
1009 !! 1016 handle this case. It returns the number of times the timer had to be
1010 Before freeing a timer, timer_shutdown() or t !! 1017 deleted before we finally stopped it from adding itself back in.
1011 called which will keep it from being rearmed. <<
1012 rearm the timer will be silently ignored by t <<
1013 <<
1014 1018
1015 Locking Speed 1019 Locking Speed
1016 ============= 1020 =============
1017 1021
1018 There are three main things to worry about wh 1022 There are three main things to worry about when considering speed of
1019 some code which does locking. First is concur 1023 some code which does locking. First is concurrency: how many things are
1020 going to be waiting while someone else is hol 1024 going to be waiting while someone else is holding a lock. Second is the
1021 time taken to actually acquire and release an 1025 time taken to actually acquire and release an uncontended lock. Third is
1022 using fewer, or smarter locks. I'm assuming t 1026 using fewer, or smarter locks. I'm assuming that the lock is used fairly
1023 often: otherwise, you wouldn't be concerned a 1027 often: otherwise, you wouldn't be concerned about efficiency.
1024 1028
1025 Concurrency depends on how long the lock is u 1029 Concurrency depends on how long the lock is usually held: you should
1026 hold the lock for as long as needed, but no l 1030 hold the lock for as long as needed, but no longer. In the cache
1027 example, we always create the object without 1031 example, we always create the object without the lock held, and then
1028 grab the lock only when we are ready to inser 1032 grab the lock only when we are ready to insert it in the list.
1029 1033
1030 Acquisition times depend on how much damage t 1034 Acquisition times depend on how much damage the lock operations do to
1031 the pipeline (pipeline stalls) and how likely 1035 the pipeline (pipeline stalls) and how likely it is that this CPU was
1032 the last one to grab the lock (ie. is the loc 1036 the last one to grab the lock (ie. is the lock cache-hot for this CPU):
1033 on a machine with more CPUs, this likelihood 1037 on a machine with more CPUs, this likelihood drops fast. Consider a
1034 700MHz Intel Pentium III: an instruction take 1038 700MHz Intel Pentium III: an instruction takes about 0.7ns, an atomic
1035 increment takes about 58ns, a lock which is c 1039 increment takes about 58ns, a lock which is cache-hot on this CPU takes
1036 160ns, and a cacheline transfer from another 1040 160ns, and a cacheline transfer from another CPU takes an additional 170
1037 to 360ns. (These figures from Paul McKenney's 1041 to 360ns. (These figures from Paul McKenney's `Linux Journal RCU
1038 article <http://www.linuxjournal.com/article. 1042 article <http://www.linuxjournal.com/article.php?sid=6993>`__).
1039 1043
1040 These two aims conflict: holding a lock for a 1044 These two aims conflict: holding a lock for a short time might be done
1041 by splitting locks into parts (such as in our 1045 by splitting locks into parts (such as in our final per-object-lock
1042 example), but this increases the number of lo 1046 example), but this increases the number of lock acquisitions, and the
1043 results are often slower than having a single 1047 results are often slower than having a single lock. This is another
1044 reason to advocate locking simplicity. 1048 reason to advocate locking simplicity.
1045 1049
1046 The third concern is addressed below: there a 1050 The third concern is addressed below: there are some methods to reduce
1047 the amount of locking which needs to be done. 1051 the amount of locking which needs to be done.
1048 1052
1049 Read/Write Lock Variants 1053 Read/Write Lock Variants
1050 ------------------------ 1054 ------------------------
1051 1055
1052 Both spinlocks and mutexes have read/write va 1056 Both spinlocks and mutexes have read/write variants: ``rwlock_t`` and
1053 :c:type:`struct rw_semaphore <rw_semaphore>`. 1057 :c:type:`struct rw_semaphore <rw_semaphore>`. These divide
1054 users into two classes: the readers and the w 1058 users into two classes: the readers and the writers. If you are only
1055 reading the data, you can get a read lock, bu 1059 reading the data, you can get a read lock, but to write to the data you
1056 need the write lock. Many people can hold a r 1060 need the write lock. Many people can hold a read lock, but a writer must
1057 be sole holder. 1061 be sole holder.
1058 1062
1059 If your code divides neatly along reader/writ 1063 If your code divides neatly along reader/writer lines (as our cache code
1060 does), and the lock is held by readers for si 1064 does), and the lock is held by readers for significant lengths of time,
1061 using these locks can help. They are slightly 1065 using these locks can help. They are slightly slower than the normal
1062 locks though, so in practice ``rwlock_t`` is 1066 locks though, so in practice ``rwlock_t`` is not usually worthwhile.
1063 1067
1064 Avoiding Locks: Read Copy Update 1068 Avoiding Locks: Read Copy Update
1065 -------------------------------- 1069 --------------------------------
1066 1070
1067 There is a special method of read/write locki 1071 There is a special method of read/write locking called Read Copy Update.
1068 Using RCU, the readers can avoid taking a loc 1072 Using RCU, the readers can avoid taking a lock altogether: as we expect
1069 our cache to be read more often than updated 1073 our cache to be read more often than updated (otherwise the cache is a
1070 waste of time), it is a candidate for this op 1074 waste of time), it is a candidate for this optimization.
1071 1075
1072 How do we get rid of read locks? Getting rid 1076 How do we get rid of read locks? Getting rid of read locks means that
1073 writers may be changing the list underneath t 1077 writers may be changing the list underneath the readers. That is
1074 actually quite simple: we can read a linked l 1078 actually quite simple: we can read a linked list while an element is
1075 being added if the writer adds the element ve 1079 being added if the writer adds the element very carefully. For example,
1076 adding ``new`` to a single linked list called 1080 adding ``new`` to a single linked list called ``list``::
1077 1081
1078 new->next = list->next; 1082 new->next = list->next;
1079 wmb(); 1083 wmb();
1080 list->next = new; 1084 list->next = new;
1081 1085
1082 1086
1083 The wmb() is a write memory barrier. It ensur !! 1087 The :c:func:`wmb()` is a write memory barrier. It ensures that the
1084 first operation (setting the new element's `` 1088 first operation (setting the new element's ``next`` pointer) is complete
1085 and will be seen by all CPUs, before the seco 1089 and will be seen by all CPUs, before the second operation is (putting
1086 the new element into the list). This is impor 1090 the new element into the list). This is important, since modern
1087 compilers and modern CPUs can both reorder in 1091 compilers and modern CPUs can both reorder instructions unless told
1088 otherwise: we want a reader to either not see 1092 otherwise: we want a reader to either not see the new element at all, or
1089 see the new element with the ``next`` pointer 1093 see the new element with the ``next`` pointer correctly pointing at the
1090 rest of the list. 1094 rest of the list.
1091 1095
1092 Fortunately, there is a function to do this f 1096 Fortunately, there is a function to do this for standard
1093 :c:type:`struct list_head <list_head>` lists: 1097 :c:type:`struct list_head <list_head>` lists:
1094 list_add_rcu() (``include/linux/list.h``). !! 1098 :c:func:`list_add_rcu()` (``include/linux/list.h``).
1095 1099
1096 Removing an element from the list is even sim 1100 Removing an element from the list is even simpler: we replace the
1097 pointer to the old element with a pointer to 1101 pointer to the old element with a pointer to its successor, and readers
1098 will either see it, or skip over it. 1102 will either see it, or skip over it.
1099 1103
1100 :: 1104 ::
1101 1105
1102 list->next = old->next; 1106 list->next = old->next;
1103 1107
1104 1108
1105 There is list_del_rcu() (``include/linux/list !! 1109 There is :c:func:`list_del_rcu()` (``include/linux/list.h``) which
1106 does this (the normal version poisons the old 1110 does this (the normal version poisons the old object, which we don't
1107 want). 1111 want).
1108 1112
1109 The reader must also be careful: some CPUs ca 1113 The reader must also be careful: some CPUs can look through the ``next``
1110 pointer to start reading the contents of the 1114 pointer to start reading the contents of the next element early, but
1111 don't realize that the pre-fetched contents i 1115 don't realize that the pre-fetched contents is wrong when the ``next``
1112 pointer changes underneath them. Once again, 1116 pointer changes underneath them. Once again, there is a
1113 list_for_each_entry_rcu() (``include/linux/li !! 1117 :c:func:`list_for_each_entry_rcu()` (``include/linux/list.h``)
1114 to help you. Of course, writers can just use 1118 to help you. Of course, writers can just use
1115 list_for_each_entry(), since there cannot be !! 1119 :c:func:`list_for_each_entry()`, since there cannot be two
1116 simultaneous writers. 1120 simultaneous writers.
1117 1121
1118 Our final dilemma is this: when can we actual 1122 Our final dilemma is this: when can we actually destroy the removed
1119 element? Remember, a reader might be stepping 1123 element? Remember, a reader might be stepping through this element in
1120 the list right now: if we free this element a 1124 the list right now: if we free this element and the ``next`` pointer
1121 changes, the reader will jump off into garbag 1125 changes, the reader will jump off into garbage and crash. We need to
1122 wait until we know that all the readers who w 1126 wait until we know that all the readers who were traversing the list
1123 when we deleted the element are finished. We 1127 when we deleted the element are finished. We use
1124 call_rcu() to register a callback which will !! 1128 :c:func:`call_rcu()` to register a callback which will actually
1125 destroy the object once all pre-existing read 1129 destroy the object once all pre-existing readers are finished.
1126 Alternatively, synchronize_rcu() may be used !! 1130 Alternatively, :c:func:`synchronize_rcu()` may be used to block
1127 until all pre-existing are finished. 1131 until all pre-existing are finished.
1128 1132
1129 But how does Read Copy Update know when the r 1133 But how does Read Copy Update know when the readers are finished? The
1130 method is this: firstly, the readers always t 1134 method is this: firstly, the readers always traverse the list inside
1131 rcu_read_lock()/rcu_read_unlock() pairs: !! 1135 :c:func:`rcu_read_lock()`/:c:func:`rcu_read_unlock()` pairs:
1132 these simply disable preemption so the reader 1136 these simply disable preemption so the reader won't go to sleep while
1133 reading the list. 1137 reading the list.
1134 1138
1135 RCU then waits until every other CPU has slep 1139 RCU then waits until every other CPU has slept at least once: since
1136 readers cannot sleep, we know that any reader 1140 readers cannot sleep, we know that any readers which were traversing the
1137 list during the deletion are finished, and th 1141 list during the deletion are finished, and the callback is triggered.
1138 The real Read Copy Update code is a little mo 1142 The real Read Copy Update code is a little more optimized than this, but
1139 this is the fundamental idea. 1143 this is the fundamental idea.
1140 1144
1141 :: 1145 ::
1142 1146
1143 --- cache.c.perobjectlock 2003-12-11 17 1147 --- cache.c.perobjectlock 2003-12-11 17:15:03.000000000 +1100
1144 +++ cache.c.rcupdate 2003-12-11 17:55: 1148 +++ cache.c.rcupdate 2003-12-11 17:55:14.000000000 +1100
1145 @@ -1,15 +1,18 @@ 1149 @@ -1,15 +1,18 @@
1146 #include <linux/list.h> 1150 #include <linux/list.h>
1147 #include <linux/slab.h> 1151 #include <linux/slab.h>
1148 #include <linux/string.h> 1152 #include <linux/string.h>
1149 +#include <linux/rcupdate.h> 1153 +#include <linux/rcupdate.h>
1150 #include <linux/mutex.h> 1154 #include <linux/mutex.h>
1151 #include <asm/errno.h> 1155 #include <asm/errno.h>
1152 1156
1153 struct object 1157 struct object
1154 { 1158 {
1155 - /* These two protected by cache_ 1159 - /* These two protected by cache_lock. */
1156 + /* This is protected by RCU */ 1160 + /* This is protected by RCU */
1157 struct list_head list; 1161 struct list_head list;
1158 int popularity; 1162 int popularity;
1159 1163
1160 + struct rcu_head rcu; 1164 + struct rcu_head rcu;
1161 + 1165 +
1162 atomic_t refcnt; 1166 atomic_t refcnt;
1163 1167
1164 /* Doesn't change once created. 1168 /* Doesn't change once created. */
1165 @@ -40,7 +43,7 @@ 1169 @@ -40,7 +43,7 @@
1166 { 1170 {
1167 struct object *i; 1171 struct object *i;
1168 1172
1169 - list_for_each_entry(i, &cache, l 1173 - list_for_each_entry(i, &cache, list) {
1170 + list_for_each_entry_rcu(i, &cach 1174 + list_for_each_entry_rcu(i, &cache, list) {
1171 if (i->id == id) { 1175 if (i->id == id) {
1172 i->popularity++; 1176 i->popularity++;
1173 return i; 1177 return i;
1174 @@ -49,19 +52,25 @@ 1178 @@ -49,19 +52,25 @@
1175 return NULL; 1179 return NULL;
1176 } 1180 }
1177 1181
1178 +/* Final discard done once we know no re 1182 +/* Final discard done once we know no readers are looking. */
1179 +static void cache_delete_rcu(void *arg) 1183 +static void cache_delete_rcu(void *arg)
1180 +{ 1184 +{
1181 + object_put(arg); 1185 + object_put(arg);
1182 +} 1186 +}
1183 + 1187 +
1184 /* Must be holding cache_lock */ 1188 /* Must be holding cache_lock */
1185 static void __cache_delete(struct object 1189 static void __cache_delete(struct object *obj)
1186 { 1190 {
1187 BUG_ON(!obj); 1191 BUG_ON(!obj);
1188 - list_del(&obj->list); 1192 - list_del(&obj->list);
1189 - object_put(obj); 1193 - object_put(obj);
1190 + list_del_rcu(&obj->list); 1194 + list_del_rcu(&obj->list);
1191 cache_num--; 1195 cache_num--;
1192 + call_rcu(&obj->rcu, cache_delete 1196 + call_rcu(&obj->rcu, cache_delete_rcu);
1193 } 1197 }
1194 1198
1195 /* Must be holding cache_lock */ 1199 /* Must be holding cache_lock */
1196 static void __cache_add(struct object *o 1200 static void __cache_add(struct object *obj)
1197 { 1201 {
1198 - list_add(&obj->list, &cache); 1202 - list_add(&obj->list, &cache);
1199 + list_add_rcu(&obj->list, &cache) 1203 + list_add_rcu(&obj->list, &cache);
1200 if (++cache_num > MAX_CACHE_SIZE 1204 if (++cache_num > MAX_CACHE_SIZE) {
1201 struct object *i, *outca 1205 struct object *i, *outcast = NULL;
1202 list_for_each_entry(i, & 1206 list_for_each_entry(i, &cache, list) {
1203 @@ -104,12 +114,11 @@ 1207 @@ -104,12 +114,11 @@
1204 struct object *cache_find(int id) 1208 struct object *cache_find(int id)
1205 { 1209 {
1206 struct object *obj; 1210 struct object *obj;
1207 - unsigned long flags; 1211 - unsigned long flags;
1208 1212
1209 - spin_lock_irqsave(&cache_lock, f 1213 - spin_lock_irqsave(&cache_lock, flags);
1210 + rcu_read_lock(); 1214 + rcu_read_lock();
1211 obj = __cache_find(id); 1215 obj = __cache_find(id);
1212 if (obj) 1216 if (obj)
1213 object_get(obj); 1217 object_get(obj);
1214 - spin_unlock_irqrestore(&cache_lo 1218 - spin_unlock_irqrestore(&cache_lock, flags);
1215 + rcu_read_unlock(); 1219 + rcu_read_unlock();
1216 return obj; 1220 return obj;
1217 } 1221 }
1218 1222
1219 Note that the reader will alter the popularit 1223 Note that the reader will alter the popularity member in
1220 __cache_find(), and now it doesn't hold a loc !! 1224 :c:func:`__cache_find()`, and now it doesn't hold a lock. One
1221 solution would be to make it an ``atomic_t``, 1225 solution would be to make it an ``atomic_t``, but for this usage, we
1222 don't really care about races: an approximate 1226 don't really care about races: an approximate result is good enough, so
1223 I didn't change it. 1227 I didn't change it.
1224 1228
1225 The result is that cache_find() requires no !! 1229 The result is that :c:func:`cache_find()` requires no
1226 synchronization with any other functions, so 1230 synchronization with any other functions, so is almost as fast on SMP as
1227 it would be on UP. 1231 it would be on UP.
1228 1232
1229 There is a further optimization possible here 1233 There is a further optimization possible here: remember our original
1230 cache code, where there were no reference cou 1234 cache code, where there were no reference counts and the caller simply
1231 held the lock whenever using the object? This 1235 held the lock whenever using the object? This is still possible: if you
1232 hold the lock, no one can delete the object, 1236 hold the lock, no one can delete the object, so you don't need to get
1233 and put the reference count. 1237 and put the reference count.
1234 1238
1235 Now, because the 'read lock' in RCU is simply 1239 Now, because the 'read lock' in RCU is simply disabling preemption, a
1236 caller which always has preemption disabled b 1240 caller which always has preemption disabled between calling
1237 cache_find() and object_put() does not !! 1241 :c:func:`cache_find()` and :c:func:`object_put()` does not
1238 need to actually get and put the reference co 1242 need to actually get and put the reference count: we could expose
1239 __cache_find() by making it non-static, and s !! 1243 :c:func:`__cache_find()` by making it non-static, and such
1240 callers could simply call that. 1244 callers could simply call that.
1241 1245
1242 The benefit here is that the reference count 1246 The benefit here is that the reference count is not written to: the
1243 object is not altered in any way, which is mu 1247 object is not altered in any way, which is much faster on SMP machines
1244 due to caching. 1248 due to caching.
1245 1249
1246 Per-CPU Data 1250 Per-CPU Data
1247 ------------ 1251 ------------
1248 1252
1249 Another technique for avoiding locking which 1253 Another technique for avoiding locking which is used fairly widely is to
1250 duplicate information for each CPU. For examp 1254 duplicate information for each CPU. For example, if you wanted to keep a
1251 count of a common condition, you could use a 1255 count of a common condition, you could use a spin lock and a single
1252 counter. Nice and simple. 1256 counter. Nice and simple.
1253 1257
1254 If that was too slow (it's usually not, but i 1258 If that was too slow (it's usually not, but if you've got a really big
1255 machine to test on and can show that it is), 1259 machine to test on and can show that it is), you could instead use a
1256 counter for each CPU, then none of them need 1260 counter for each CPU, then none of them need an exclusive lock. See
1257 DEFINE_PER_CPU(), get_cpu_var() and !! 1261 :c:func:`DEFINE_PER_CPU()`, :c:func:`get_cpu_var()` and
1258 put_cpu_var() (``include/linux/percpu.h``). !! 1262 :c:func:`put_cpu_var()` (``include/linux/percpu.h``).
1259 1263
1260 Of particular use for simple per-cpu counters 1264 Of particular use for simple per-cpu counters is the ``local_t`` type,
1261 and the cpu_local_inc() and related functions !! 1265 and the :c:func:`cpu_local_inc()` and related functions, which are
1262 more efficient than simple code on some archi 1266 more efficient than simple code on some architectures
1263 (``include/asm/local.h``). 1267 (``include/asm/local.h``).
1264 1268
1265 Note that there is no simple, reliable way of 1269 Note that there is no simple, reliable way of getting an exact value of
1266 such a counter, without introducing more lock 1270 such a counter, without introducing more locks. This is not a problem
1267 for some uses. 1271 for some uses.
1268 1272
1269 Data Which Mostly Used By An IRQ Handler 1273 Data Which Mostly Used By An IRQ Handler
1270 ---------------------------------------- 1274 ----------------------------------------
1271 1275
1272 If data is always accessed from within the sa 1276 If data is always accessed from within the same IRQ handler, you don't
1273 need a lock at all: the kernel already guaran 1277 need a lock at all: the kernel already guarantees that the irq handler
1274 will not run simultaneously on multiple CPUs. 1278 will not run simultaneously on multiple CPUs.
1275 1279
1276 Manfred Spraul points out that you can still 1280 Manfred Spraul points out that you can still do this, even if the data
1277 is very occasionally accessed in user context 1281 is very occasionally accessed in user context or softirqs/tasklets. The
1278 irq handler doesn't use a lock, and all other 1282 irq handler doesn't use a lock, and all other accesses are done as so::
1279 1283
1280 mutex_lock(&lock); !! 1284 spin_lock(&lock);
1281 disable_irq(irq); 1285 disable_irq(irq);
1282 ... 1286 ...
1283 enable_irq(irq); 1287 enable_irq(irq);
1284 mutex_unlock(&lock); !! 1288 spin_unlock(&lock);
1285 1289
1286 The disable_irq() prevents the irq handler fr !! 1290 The :c:func:`disable_irq()` prevents the irq handler from running
1287 (and waits for it to finish if it's currently 1291 (and waits for it to finish if it's currently running on other CPUs).
1288 The spinlock prevents any other accesses happ 1292 The spinlock prevents any other accesses happening at the same time.
1289 Naturally, this is slower than just a spin_lo !! 1293 Naturally, this is slower than just a :c:func:`spin_lock_irq()`
1290 call, so it only makes sense if this type of 1294 call, so it only makes sense if this type of access happens extremely
1291 rarely. 1295 rarely.
1292 1296
1293 What Functions Are Safe To Call From Interrup 1297 What Functions Are Safe To Call From Interrupts?
1294 ============================================= 1298 ================================================
1295 1299
1296 Many functions in the kernel sleep (ie. call 1300 Many functions in the kernel sleep (ie. call schedule()) directly or
1297 indirectly: you can never call them while hol 1301 indirectly: you can never call them while holding a spinlock, or with
1298 preemption disabled. This also means you need 1302 preemption disabled. This also means you need to be in user context:
1299 calling them from an interrupt is illegal. 1303 calling them from an interrupt is illegal.
1300 1304
1301 Some Functions Which Sleep 1305 Some Functions Which Sleep
1302 -------------------------- 1306 --------------------------
1303 1307
1304 The most common ones are listed below, but yo 1308 The most common ones are listed below, but you usually have to read the
1305 code to find out if other calls are safe. If 1309 code to find out if other calls are safe. If everyone else who calls it
1306 can sleep, you probably need to be able to sl 1310 can sleep, you probably need to be able to sleep, too. In particular,
1307 registration and deregistration functions usu 1311 registration and deregistration functions usually expect to be called
1308 from user context, and can sleep. 1312 from user context, and can sleep.
1309 1313
1310 - Accesses to userspace: 1314 - Accesses to userspace:
1311 1315
1312 - copy_from_user() !! 1316 - :c:func:`copy_from_user()`
1313 1317
1314 - copy_to_user() !! 1318 - :c:func:`copy_to_user()`
1315 1319
1316 - get_user() !! 1320 - :c:func:`get_user()`
1317 1321
1318 - put_user() !! 1322 - :c:func:`put_user()`
1319 1323
1320 - kmalloc(GP_KERNEL) <kmalloc>` !! 1324 - :c:func:`kmalloc(GFP_KERNEL) <kmalloc>`
1321 1325
1322 - mutex_lock_interruptible() and !! 1326 - :c:func:`mutex_lock_interruptible()` and
1323 mutex_lock() !! 1327 :c:func:`mutex_lock()`
1324 1328
1325 There is a mutex_trylock() which does not !! 1329 There is a :c:func:`mutex_trylock()` which does not sleep.
1326 Still, it must not be used inside interrup 1330 Still, it must not be used inside interrupt context since its
1327 implementation is not safe for that. mutex !! 1331 implementation is not safe for that. :c:func:`mutex_unlock()`
1328 will also never sleep. It cannot be used i 1332 will also never sleep. It cannot be used in interrupt context either
1329 since a mutex must be released by the same 1333 since a mutex must be released by the same task that acquired it.
1330 1334
1331 Some Functions Which Don't Sleep 1335 Some Functions Which Don't Sleep
1332 -------------------------------- 1336 --------------------------------
1333 1337
1334 Some functions are safe to call from any cont 1338 Some functions are safe to call from any context, or holding almost any
1335 lock. 1339 lock.
1336 1340
1337 - printk() !! 1341 - :c:func:`printk()`
1338 1342
1339 - kfree() !! 1343 - :c:func:`kfree()`
1340 1344
1341 - add_timer() and timer_delete() !! 1345 - :c:func:`add_timer()` and :c:func:`del_timer()`
1342 1346
1343 Mutex API reference 1347 Mutex API reference
1344 =================== 1348 ===================
1345 1349
1346 .. kernel-doc:: include/linux/mutex.h 1350 .. kernel-doc:: include/linux/mutex.h
1347 :internal: 1351 :internal:
1348 1352
1349 .. kernel-doc:: kernel/locking/mutex.c 1353 .. kernel-doc:: kernel/locking/mutex.c
1350 :export: 1354 :export:
1351 1355
1352 Futex API reference 1356 Futex API reference
1353 =================== 1357 ===================
1354 1358
1355 .. kernel-doc:: kernel/futex/core.c !! 1359 .. kernel-doc:: kernel/futex.c
1356 :internal: <<
1357 <<
1358 .. kernel-doc:: kernel/futex/futex.h <<
1359 :internal: <<
1360 <<
1361 .. kernel-doc:: kernel/futex/pi.c <<
1362 :internal: <<
1363 <<
1364 .. kernel-doc:: kernel/futex/requeue.c <<
1365 :internal: <<
1366 <<
1367 .. kernel-doc:: kernel/futex/waitwake.c <<
1368 :internal: 1360 :internal:
1369 1361
1370 Further reading 1362 Further reading
1371 =============== 1363 ===============
1372 1364
1373 - ``Documentation/locking/spinlocks.rst``: L !! 1365 - ``Documentation/locking/spinlocks.txt``: Linus Torvalds' spinlocking
1374 tutorial in the kernel sources. 1366 tutorial in the kernel sources.
1375 1367
1376 - Unix Systems for Modern Architectures: Sym 1368 - Unix Systems for Modern Architectures: Symmetric Multiprocessing and
1377 Caching for Kernel Programmers: 1369 Caching for Kernel Programmers:
1378 1370
1379 Curt Schimmel's very good introduction to 1371 Curt Schimmel's very good introduction to kernel level locking (not
1380 written for Linux, but nearly everything a 1372 written for Linux, but nearly everything applies). The book is
1381 expensive, but really worth every penny to 1373 expensive, but really worth every penny to understand SMP locking.
1382 [ISBN: 0201633388] 1374 [ISBN: 0201633388]
1383 1375
1384 Thanks 1376 Thanks
1385 ====== 1377 ======
1386 1378
1387 Thanks to Telsa Gwynne for DocBooking, neaten 1379 Thanks to Telsa Gwynne for DocBooking, neatening and adding style.
1388 1380
1389 Thanks to Martin Pool, Philipp Rumpf, Stephen 1381 Thanks to Martin Pool, Philipp Rumpf, Stephen Rothwell, Paul Mackerras,
1390 Ruedi Aschwanden, Alan Cox, Manfred Spraul, T 1382 Ruedi Aschwanden, Alan Cox, Manfred Spraul, Tim Waugh, Pete Zaitcev,
1391 James Morris, Robert Love, Paul McKenney, Joh 1383 James Morris, Robert Love, Paul McKenney, John Ashby for proofreading,
1392 correcting, flaming, commenting. 1384 correcting, flaming, commenting.
1393 1385
1394 Thanks to the cabal for having no influence o 1386 Thanks to the cabal for having no influence on this document.
1395 1387
1396 Glossary 1388 Glossary
1397 ======== 1389 ========
1398 1390
1399 preemption 1391 preemption
1400 Prior to 2.5, or when ``CONFIG_PREEMPT`` is 1392 Prior to 2.5, or when ``CONFIG_PREEMPT`` is unset, processes in user
1401 context inside the kernel would not preempt 1393 context inside the kernel would not preempt each other (ie. you had that
1402 CPU until you gave it up, except for interr 1394 CPU until you gave it up, except for interrupts). With the addition of
1403 ``CONFIG_PREEMPT`` in 2.5.4, this changed: 1395 ``CONFIG_PREEMPT`` in 2.5.4, this changed: when in user context, higher
1404 priority tasks can "cut in": spinlocks were 1396 priority tasks can "cut in": spinlocks were changed to disable
1405 preemption, even on UP. 1397 preemption, even on UP.
1406 1398
1407 bh 1399 bh
1408 Bottom Half: for historical reasons, functi 1400 Bottom Half: for historical reasons, functions with '_bh' in them often
1409 now refer to any software interrupt, e.g. s !! 1401 now refer to any software interrupt, e.g. :c:func:`spin_lock_bh()`
1410 blocks any software interrupt on the curren 1402 blocks any software interrupt on the current CPU. Bottom halves are
1411 deprecated, and will eventually be replaced 1403 deprecated, and will eventually be replaced by tasklets. Only one bottom
1412 half will be running at any time. 1404 half will be running at any time.
1413 1405
1414 Hardware Interrupt / Hardware IRQ 1406 Hardware Interrupt / Hardware IRQ
1415 Hardware interrupt request. in_hardirq() re !! 1407 Hardware interrupt request. :c:func:`in_irq()` returns true in a
1416 hardware interrupt handler. 1408 hardware interrupt handler.
1417 1409
1418 Interrupt Context 1410 Interrupt Context
1419 Not user context: processing a hardware irq 1411 Not user context: processing a hardware irq or software irq. Indicated
1420 by the in_interrupt() macro returning true. !! 1412 by the :c:func:`in_interrupt()` macro returning true.
1421 1413
1422 SMP 1414 SMP
1423 Symmetric Multi-Processor: kernels compiled 1415 Symmetric Multi-Processor: kernels compiled for multiple-CPU machines.
1424 (``CONFIG_SMP=y``). 1416 (``CONFIG_SMP=y``).
1425 1417
1426 Software Interrupt / softirq 1418 Software Interrupt / softirq
1427 Software interrupt handler. in_hardirq() re !! 1419 Software interrupt handler. :c:func:`in_irq()` returns false;
1428 in_softirq() returns true. Tasklets and sof !! 1420 :c:func:`in_softirq()` returns true. Tasklets and softirqs both
1429 fall into the category of 'software interru 1421 fall into the category of 'software interrupts'.
1430 1422
1431 Strictly speaking a softirq is one of up to 1423 Strictly speaking a softirq is one of up to 32 enumerated software
1432 interrupts which can run on multiple CPUs a 1424 interrupts which can run on multiple CPUs at once. Sometimes used to
1433 refer to tasklets as well (ie. all software 1425 refer to tasklets as well (ie. all software interrupts).
1434 1426
1435 tasklet 1427 tasklet
1436 A dynamically-registrable software interrup 1428 A dynamically-registrable software interrupt, which is guaranteed to
1437 only run on one CPU at a time. 1429 only run on one CPU at a time.
1438 1430
1439 timer 1431 timer
1440 A dynamically-registrable software interrup 1432 A dynamically-registrable software interrupt, which is run at (or close
1441 to) a given time. When running, it is just 1433 to) a given time. When running, it is just like a tasklet (in fact, they
1442 are called from the ``TIMER_SOFTIRQ``). 1434 are called from the ``TIMER_SOFTIRQ``).
1443 1435
1444 UP 1436 UP
1445 Uni-Processor: Non-SMP. (``CONFIG_SMP=n``). 1437 Uni-Processor: Non-SMP. (``CONFIG_SMP=n``).
1446 1438
1447 User Context 1439 User Context
1448 The kernel executing on behalf of a particu 1440 The kernel executing on behalf of a particular process (ie. a system
1449 call or trap) or kernel thread. You can tel 1441 call or trap) or kernel thread. You can tell which process with the
1450 ``current`` macro.) Not to be confused with 1442 ``current`` macro.) Not to be confused with userspace. Can be
1451 interrupted by software or hardware interru 1443 interrupted by software or hardware interrupts.
1452 1444
1453 Userspace 1445 Userspace
1454 A process executing its own code outside th 1446 A process executing its own code outside the kernel.
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.