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