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