1 <?xml version="1.0" encoding="UTF-8"?>
2 <!DOCTYPE book PUBLIC "-//OASIS//DTD DocBook XML V4.1.2//EN"
3 "http://www.oasis-open.org/docbook/xml/4.1.2/docbookx.dtd" []>
5 <book id="LKLockingGuide">
7 <title>Unreliable Guide To Locking</title>
11 <firstname>Rusty</firstname>
12 <surname>Russell</surname>
15 <email>rusty@rustcorp.com.au</email>
23 <holder>Rusty Russell</holder>
28 This documentation is free software; you can redistribute
29 it and/or modify it under the terms of the GNU General Public
30 License as published by the Free Software Foundation; either
31 version 2 of the License, or (at your option) any later
36 This program is distributed in the hope that it will be
37 useful, but WITHOUT ANY WARRANTY; without even the implied
38 warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
39 See the GNU General Public License for more details.
43 You should have received a copy of the GNU General Public
44 License along with this program; if not, write to the Free
45 Software Foundation, Inc., 59 Temple Place, Suite 330, Boston,
50 For more details see the file COPYING in the source
51 distribution of Linux.
58 <title>Introduction</title>
60 Welcome, to Rusty's Remarkably Unreliable Guide to Kernel
61 Locking issues. This document describes the locking systems in
62 the Linux Kernel in 2.6.
65 With the wide availability of HyperThreading, and <firstterm
66 linkend="gloss-preemption">preemption </firstterm> in the Linux
67 Kernel, everyone hacking on the kernel needs to know the
68 fundamentals of concurrency and locking for
69 <firstterm linkend="gloss-smp"><acronym>SMP</acronym></firstterm>.
74 <title>The Problem With Concurrency</title>
76 (Skip this if you know what a Race Condition is).
79 In a normal program, you can increment a counter like so:
82 very_important_count++;
86 This is what they would expect to happen:
90 <title>Expected Results</title>
92 <tgroup cols="2" align="left">
96 <entry>Instance 1</entry>
97 <entry>Instance 2</entry>
103 <entry>read very_important_count (5)</entry>
107 <entry>add 1 (6)</entry>
111 <entry>write very_important_count (6)</entry>
116 <entry>read very_important_count (6)</entry>
120 <entry>add 1 (7)</entry>
124 <entry>write very_important_count (7)</entry>
132 This is what might happen:
136 <title>Possible Results</title>
138 <tgroup cols="2" align="left">
141 <entry>Instance 1</entry>
142 <entry>Instance 2</entry>
148 <entry>read very_important_count (5)</entry>
153 <entry>read very_important_count (5)</entry>
156 <entry>add 1 (6)</entry>
161 <entry>add 1 (6)</entry>
164 <entry>write very_important_count (6)</entry>
169 <entry>write very_important_count (6)</entry>
175 <sect1 id="race-condition">
176 <title>Race Conditions and Critical Regions</title>
178 This overlap, where the result depends on the
179 relative timing of multiple tasks, is called a <firstterm>race condition</firstterm>.
180 The piece of code containing the concurrency issue is called a
181 <firstterm>critical region</firstterm>. And especially since Linux starting running
182 on SMP machines, they became one of the major issues in kernel
183 design and implementation.
186 Preemption can have the same effect, even if there is only one
187 CPU: by preempting one task during the critical region, we have
188 exactly the same race condition. In this case the thread which
189 preempts might run the critical region itself.
192 The solution is to recognize when these simultaneous accesses
193 occur, and use locks to make sure that only one instance can
194 enter the critical region at any time. There are many
195 friendly primitives in the Linux kernel to help you do this.
196 And then there are the unfriendly primitives, but I'll pretend
203 <title>Locking in the Linux Kernel</title>
206 If I could give you one piece of advice: never sleep with anyone
207 crazier than yourself. But if I had to give you advice on
208 locking: <emphasis>keep it simple</emphasis>.
212 Be reluctant to introduce new locks.
216 Strangely enough, this last one is the exact reverse of my advice when
217 you <emphasis>have</emphasis> slept with someone crazier than yourself.
218 And you should think about getting a big dog.
221 <sect1 id="lock-intro">
222 <title>Three Main Types of Kernel Locks: Spinlocks, Mutexes and Semaphores</title>
225 There are three main types of kernel locks. The fundamental type
227 (<filename class="headerfile">include/asm/spinlock.h</filename>),
228 which is a very simple single-holder lock: if you can't get the
229 spinlock, you keep trying (spinning) until you can. Spinlocks are
230 very small and fast, and can be used anywhere.
233 The second type is a mutex
234 (<filename class="headerfile">include/linux/mutex.h</filename>): it
235 is like a spinlock, but you may block holding a mutex.
236 If you can't lock a mutex, your task will suspend itself, and be woken
237 up when the mutex is released. This means the CPU can do something
238 else while you are waiting. There are many cases when you simply
239 can't sleep (see <xref linkend="sleeping-things"/>), and so have to
240 use a spinlock instead.
243 The third type is a semaphore
244 (<filename class="headerfile">include/linux/semaphore.h</filename>): it
245 can have more than one holder at any time (the number decided at
246 initialization time), although it is most commonly used as a
247 single-holder lock (a mutex). If you can't get a semaphore, your
248 task will be suspended and later on woken up - just like for mutexes.
251 Neither type of lock is recursive: see
252 <xref linkend="deadlock"/>.
256 <sect1 id="uniprocessor">
257 <title>Locks and Uniprocessor Kernels</title>
260 For kernels compiled without <symbol>CONFIG_SMP</symbol>, and
261 without <symbol>CONFIG_PREEMPT</symbol> spinlocks do not exist at
262 all. This is an excellent design decision: when no-one else can
263 run at the same time, there is no reason to have a lock.
267 If the kernel is compiled without <symbol>CONFIG_SMP</symbol>,
268 but <symbol>CONFIG_PREEMPT</symbol> is set, then spinlocks
269 simply disable preemption, which is sufficient to prevent any
270 races. For most purposes, we can think of preemption as
271 equivalent to SMP, and not worry about it separately.
275 You should always test your locking code with <symbol>CONFIG_SMP</symbol>
276 and <symbol>CONFIG_PREEMPT</symbol> enabled, even if you don't have an SMP test box, because it
277 will still catch some kinds of locking bugs.
281 Semaphores still exist, because they are required for
282 synchronization between <firstterm linkend="gloss-usercontext">user
283 contexts</firstterm>, as we will see below.
287 <sect1 id="usercontextlocking">
288 <title>Locking Only In User Context</title>
291 If you have a data structure which is only ever accessed from
292 user context, then you can use a simple semaphore
293 (<filename>linux/linux/semaphore.h</filename>) to protect it. This
294 is the most trivial case: you initialize the semaphore to the number
295 of resources available (usually 1), and call
296 <function>down_interruptible()</function> to grab the semaphore, and
297 <function>up()</function> to release it. There is also a
298 <function>down()</function>, which should be avoided, because it
299 will not return if a signal is received.
303 Example: <filename>linux/net/core/netfilter.c</filename> allows
304 registration of new <function>setsockopt()</function> and
305 <function>getsockopt()</function> calls, with
306 <function>nf_register_sockopt()</function>. Registration and
307 de-registration are only done on module load and unload (and boot
308 time, where there is no concurrency), and the list of registrations
309 is only consulted for an unknown <function>setsockopt()</function>
310 or <function>getsockopt()</function> system call. The
311 <varname>nf_sockopt_mutex</varname> is perfect to protect this,
312 especially since the setsockopt and getsockopt calls may well
317 <sect1 id="lock-user-bh">
318 <title>Locking Between User Context and Softirqs</title>
321 If a <firstterm linkend="gloss-softirq">softirq</firstterm> shares
322 data with user context, you have two problems. Firstly, the current
323 user context can be interrupted by a softirq, and secondly, the
324 critical region could be entered from another CPU. This is where
325 <function>spin_lock_bh()</function>
326 (<filename class="headerfile">include/linux/spinlock.h</filename>) is
327 used. It disables softirqs on that CPU, then grabs the lock.
328 <function>spin_unlock_bh()</function> does the reverse. (The
329 '_bh' suffix is a historical reference to "Bottom Halves", the
330 old name for software interrupts. It should really be
331 called spin_lock_softirq()' in a perfect world).
335 Note that you can also use <function>spin_lock_irq()</function>
336 or <function>spin_lock_irqsave()</function> here, which stop
337 hardware interrupts as well: see <xref linkend="hardirq-context"/>.
341 This works perfectly for <firstterm linkend="gloss-up"><acronym>UP
342 </acronym></firstterm> as well: the spin lock vanishes, and this macro
343 simply becomes <function>local_bh_disable()</function>
344 (<filename class="headerfile">include/linux/interrupt.h</filename>), which
345 protects you from the softirq being run.
349 <sect1 id="lock-user-tasklet">
350 <title>Locking Between User Context and Tasklets</title>
353 This is exactly the same as above, because <firstterm
354 linkend="gloss-tasklet">tasklets</firstterm> are actually run
359 <sect1 id="lock-user-timers">
360 <title>Locking Between User Context and Timers</title>
363 This, too, is exactly the same as above, because <firstterm
364 linkend="gloss-timers">timers</firstterm> are actually run from
365 a softirq. From a locking point of view, tasklets and timers
370 <sect1 id="lock-tasklets">
371 <title>Locking Between Tasklets/Timers</title>
374 Sometimes a tasklet or timer might want to share data with
375 another tasklet or timer.
378 <sect2 id="lock-tasklets-same">
379 <title>The Same Tasklet/Timer</title>
381 Since a tasklet is never run on two CPUs at once, you don't
382 need to worry about your tasklet being reentrant (running
383 twice at once), even on SMP.
387 <sect2 id="lock-tasklets-different">
388 <title>Different Tasklets/Timers</title>
390 If another tasklet/timer wants
391 to share data with your tasklet or timer , you will both need to use
392 <function>spin_lock()</function> and
393 <function>spin_unlock()</function> calls.
394 <function>spin_lock_bh()</function> is
395 unnecessary here, as you are already in a tasklet, and
396 none will be run on the same CPU.
401 <sect1 id="lock-softirqs">
402 <title>Locking Between Softirqs</title>
405 Often a softirq might
406 want to share data with itself or a tasklet/timer.
409 <sect2 id="lock-softirqs-same">
410 <title>The Same Softirq</title>
413 The same softirq can run on the other CPUs: you can use a
414 per-CPU array (see <xref linkend="per-cpu"/>) for better
415 performance. If you're going so far as to use a softirq,
416 you probably care about scalable performance enough
417 to justify the extra complexity.
421 You'll need to use <function>spin_lock()</function> and
422 <function>spin_unlock()</function> for shared data.
426 <sect2 id="lock-softirqs-different">
427 <title>Different Softirqs</title>
430 You'll need to use <function>spin_lock()</function> and
431 <function>spin_unlock()</function> for shared data, whether it
432 be a timer, tasklet, different softirq or the same or another
433 softirq: any of them could be running on a different CPU.
439 <chapter id="hardirq-context">
440 <title>Hard IRQ Context</title>
443 Hardware interrupts usually communicate with a
444 tasklet or softirq. Frequently this involves putting work in a
445 queue, which the softirq will take out.
448 <sect1 id="hardirq-softirq">
449 <title>Locking Between Hard IRQ and Softirqs/Tasklets</title>
452 If a hardware irq handler shares data with a softirq, you have
453 two concerns. Firstly, the softirq processing can be
454 interrupted by a hardware interrupt, and secondly, the
455 critical region could be entered by a hardware interrupt on
456 another CPU. This is where <function>spin_lock_irq()</function> is
457 used. It is defined to disable interrupts on that cpu, then grab
458 the lock. <function>spin_unlock_irq()</function> does the reverse.
462 The irq handler does not to use
463 <function>spin_lock_irq()</function>, because the softirq cannot
464 run while the irq handler is running: it can use
465 <function>spin_lock()</function>, which is slightly faster. The
466 only exception would be if a different hardware irq handler uses
467 the same lock: <function>spin_lock_irq()</function> will stop
468 that from interrupting us.
472 This works perfectly for UP as well: the spin lock vanishes,
473 and this macro simply becomes <function>local_irq_disable()</function>
474 (<filename class="headerfile">include/asm/smp.h</filename>), which
475 protects you from the softirq/tasklet/BH being run.
479 <function>spin_lock_irqsave()</function>
480 (<filename>include/linux/spinlock.h</filename>) is a variant
481 which saves whether interrupts were on or off in a flags word,
482 which is passed to <function>spin_unlock_irqrestore()</function>. This
483 means that the same code can be used inside an hard irq handler (where
484 interrupts are already off) and in softirqs (where the irq
485 disabling is required).
489 Note that softirqs (and hence tasklets and timers) are run on
490 return from hardware interrupts, so
491 <function>spin_lock_irq()</function> also stops these. In that
492 sense, <function>spin_lock_irqsave()</function> is the most
493 general and powerful locking function.
497 <sect1 id="hardirq-hardirq">
498 <title>Locking Between Two Hard IRQ Handlers</title>
500 It is rare to have to share data between two IRQ handlers, but
501 if you do, <function>spin_lock_irqsave()</function> should be
502 used: it is architecture-specific whether all interrupts are
503 disabled inside irq handlers themselves.
509 <chapter id="cheatsheet">
510 <title>Cheat Sheet For Locking</title>
512 Pete Zaitcev gives the following summary:
517 If you are in a process context (any syscall) and want to
518 lock other process out, use a semaphore. You can take a semaphore
519 and sleep (<function>copy_from_user*(</function> or
520 <function>kmalloc(x,GFP_KERNEL)</function>).
525 Otherwise (== data can be touched in an interrupt), use
526 <function>spin_lock_irqsave()</function> and
527 <function>spin_unlock_irqrestore()</function>.
532 Avoid holding spinlock for more than 5 lines of code and
533 across any function call (except accessors like
534 <function>readb</function>).
539 <sect1 id="minimum-lock-reqirements">
540 <title>Table of Minimum Requirements</title>
542 <para> The following table lists the <emphasis>minimum</emphasis>
543 locking requirements between various contexts. In some cases,
544 the same context can only be running on one CPU at a time, so
545 no locking is required for that context (eg. a particular
546 thread can only run on one CPU at a time, but if it needs
547 shares data with another thread, locking is required).
550 Remember the advice above: you can always use
551 <function>spin_lock_irqsave()</function>, which is a superset
552 of all other spinlock primitives.
556 <title>Table of Locking Requirements</title>
562 <entry>IRQ Handler A</entry>
563 <entry>IRQ Handler B</entry>
564 <entry>Softirq A</entry>
565 <entry>Softirq B</entry>
566 <entry>Tasklet A</entry>
567 <entry>Tasklet B</entry>
568 <entry>Timer A</entry>
569 <entry>Timer B</entry>
570 <entry>User Context A</entry>
571 <entry>User Context B</entry>
575 <entry>IRQ Handler A</entry>
580 <entry>IRQ Handler B</entry>
586 <entry>Softirq A</entry>
593 <entry>Softirq B</entry>
601 <entry>Tasklet A</entry>
610 <entry>Tasklet B</entry>
620 <entry>Timer A</entry>
631 <entry>Timer B</entry>
643 <entry>User Context A</entry>
656 <entry>User Context B</entry>
674 <title>Legend for Locking Requirements Table</title>
680 <entry>spin_lock_irqsave</entry>
684 <entry>spin_lock_irq</entry>
688 <entry>spin_lock</entry>
692 <entry>spin_lock_bh</entry>
696 <entry>down_interruptible</entry>
706 <chapter id="trylock-functions">
707 <title>The trylock Functions</title>
709 There are functions that try to acquire a lock only once and immediately
710 return a value telling about success or failure to acquire the lock.
711 They can be used if you need no access to the data protected with the lock
712 when some other thread is holding the lock. You should acquire the lock
713 later if you then need access to the data protected with the lock.
717 <function>spin_trylock()</function> does not spin but returns non-zero if
718 it acquires the spinlock on the first try or 0 if not. This function can
719 be used in all contexts like <function>spin_lock</function>: you must have
720 disabled the contexts that might interrupt you and acquire the spin lock.
724 <function>mutex_trylock()</function> does not suspend your task
725 but returns non-zero if it could lock the mutex on the first try
726 or 0 if not. This function cannot be safely used in hardware or software
727 interrupt contexts despite not sleeping.
731 <chapter id="Examples">
732 <title>Common Examples</title>
734 Let's step through a simple example: a cache of number to name
735 mappings. The cache keeps a count of how often each of the objects is
736 used, and when it gets full, throws out the least used one.
740 <sect1 id="examples-usercontext">
741 <title>All In User Context</title>
743 For our first example, we assume that all operations are in user
744 context (ie. from system calls), so we can sleep. This means we can
745 use a mutex to protect the cache and all the objects within
750 #include <linux/list.h>
751 #include <linux/slab.h>
752 #include <linux/string.h>
753 #include <linux/mutex.h>
754 #include <asm/errno.h>
758 struct list_head list;
764 /* Protects the cache, cache_num, and the objects within it */
765 static DEFINE_MUTEX(cache_lock);
766 static LIST_HEAD(cache);
767 static unsigned int cache_num = 0;
768 #define MAX_CACHE_SIZE 10
770 /* Must be holding cache_lock */
771 static struct object *__cache_find(int id)
775 list_for_each_entry(i, &cache, list)
776 if (i->id == id) {
783 /* Must be holding cache_lock */
784 static void __cache_delete(struct object *obj)
787 list_del(&obj->list);
792 /* Must be holding cache_lock */
793 static void __cache_add(struct object *obj)
795 list_add(&obj->list, &cache);
796 if (++cache_num > MAX_CACHE_SIZE) {
797 struct object *i, *outcast = NULL;
798 list_for_each_entry(i, &cache, list) {
799 if (!outcast || i->popularity < outcast->popularity)
802 __cache_delete(outcast);
806 int cache_add(int id, const char *name)
810 if ((obj = kmalloc(sizeof(*obj), GFP_KERNEL)) == NULL)
813 strlcpy(obj->name, name, sizeof(obj->name));
815 obj->popularity = 0;
817 mutex_lock(&cache_lock);
819 mutex_unlock(&cache_lock);
823 void cache_delete(int id)
825 mutex_lock(&cache_lock);
826 __cache_delete(__cache_find(id));
827 mutex_unlock(&cache_lock);
830 int cache_find(int id, char *name)
835 mutex_lock(&cache_lock);
836 obj = __cache_find(id);
839 strcpy(name, obj->name);
841 mutex_unlock(&cache_lock);
847 Note that we always make sure we have the cache_lock when we add,
848 delete, or look up the cache: both the cache infrastructure itself and
849 the contents of the objects are protected by the lock. In this case
850 it's easy, since we copy the data for the user, and never let them
851 access the objects directly.
854 There is a slight (and common) optimization here: in
855 <function>cache_add</function> we set up the fields of the object
856 before grabbing the lock. This is safe, as no-one else can access it
857 until we put it in cache.
861 <sect1 id="examples-interrupt">
862 <title>Accessing From Interrupt Context</title>
864 Now consider the case where <function>cache_find</function> can be
865 called from interrupt context: either a hardware interrupt or a
866 softirq. An example would be a timer which deletes object from the
870 The change is shown below, in standard patch format: the
871 <symbol>-</symbol> are lines which are taken away, and the
872 <symbol>+</symbol> are lines which are added.
875 --- cache.c.usercontext 2003-12-09 13:58:54.000000000 +1100
876 +++ cache.c.interrupt 2003-12-09 14:07:49.000000000 +1100
881 -static DEFINE_MUTEX(cache_lock);
882 +static DEFINE_SPINLOCK(cache_lock);
883 static LIST_HEAD(cache);
884 static unsigned int cache_num = 0;
885 #define MAX_CACHE_SIZE 10
887 int cache_add(int id, const char *name)
890 + unsigned long flags;
892 if ((obj = kmalloc(sizeof(*obj), GFP_KERNEL)) == NULL)
896 obj->popularity = 0;
898 - mutex_lock(&cache_lock);
899 + spin_lock_irqsave(&cache_lock, flags);
901 - mutex_unlock(&cache_lock);
902 + spin_unlock_irqrestore(&cache_lock, flags);
906 void cache_delete(int id)
908 - mutex_lock(&cache_lock);
909 + unsigned long flags;
911 + spin_lock_irqsave(&cache_lock, flags);
912 __cache_delete(__cache_find(id));
913 - mutex_unlock(&cache_lock);
914 + spin_unlock_irqrestore(&cache_lock, flags);
917 int cache_find(int id, char *name)
921 + unsigned long flags;
923 - mutex_lock(&cache_lock);
924 + spin_lock_irqsave(&cache_lock, flags);
925 obj = __cache_find(id);
928 strcpy(name, obj->name);
930 - mutex_unlock(&cache_lock);
931 + spin_unlock_irqrestore(&cache_lock, flags);
937 Note that the <function>spin_lock_irqsave</function> will turn off
938 interrupts if they are on, otherwise does nothing (if we are already
939 in an interrupt handler), hence these functions are safe to call from
943 Unfortunately, <function>cache_add</function> calls
944 <function>kmalloc</function> with the <symbol>GFP_KERNEL</symbol>
945 flag, which is only legal in user context. I have assumed that
946 <function>cache_add</function> is still only called in user context,
947 otherwise this should become a parameter to
948 <function>cache_add</function>.
951 <sect1 id="examples-refcnt">
952 <title>Exposing Objects Outside This File</title>
954 If our objects contained more information, it might not be sufficient
955 to copy the information in and out: other parts of the code might want
956 to keep pointers to these objects, for example, rather than looking up
957 the id every time. This produces two problems.
960 The first problem is that we use the <symbol>cache_lock</symbol> to
961 protect objects: we'd need to make this non-static so the rest of the
962 code can use it. This makes locking trickier, as it is no longer all
966 The second problem is the lifetime problem: if another structure keeps
967 a pointer to an object, it presumably expects that pointer to remain
968 valid. Unfortunately, this is only guaranteed while you hold the
969 lock, otherwise someone might call <function>cache_delete</function>
970 and even worse, add another object, re-using the same address.
973 As there is only one lock, you can't hold it forever: no-one else would
977 The solution to this problem is to use a reference count: everyone who
978 has a pointer to the object increases it when they first get the
979 object, and drops the reference count when they're finished with it.
980 Whoever drops it to zero knows it is unused, and can actually delete it.
987 --- cache.c.interrupt 2003-12-09 14:25:43.000000000 +1100
988 +++ cache.c.refcnt 2003-12-09 14:33:05.000000000 +1100
992 struct list_head list;
993 + unsigned int refcnt;
998 static unsigned int cache_num = 0;
999 #define MAX_CACHE_SIZE 10
1001 +static void __object_put(struct object *obj)
1003 + if (--obj->refcnt == 0)
1007 +static void __object_get(struct object *obj)
1012 +void object_put(struct object *obj)
1014 + unsigned long flags;
1016 + spin_lock_irqsave(&cache_lock, flags);
1017 + __object_put(obj);
1018 + spin_unlock_irqrestore(&cache_lock, flags);
1021 +void object_get(struct object *obj)
1023 + unsigned long flags;
1025 + spin_lock_irqsave(&cache_lock, flags);
1026 + __object_get(obj);
1027 + spin_unlock_irqrestore(&cache_lock, flags);
1030 /* Must be holding cache_lock */
1031 static struct object *__cache_find(int id)
1036 list_del(&obj->list);
1037 + __object_put(obj);
1042 strlcpy(obj->name, name, sizeof(obj->name));
1044 obj->popularity = 0;
1045 + obj->refcnt = 1; /* The cache holds a reference */
1047 spin_lock_irqsave(&cache_lock, flags);
1049 @@ -79,18 +111,15 @@
1050 spin_unlock_irqrestore(&cache_lock, flags);
1053 -int cache_find(int id, char *name)
1054 +struct object *cache_find(int id)
1057 - int ret = -ENOENT;
1058 unsigned long flags;
1060 spin_lock_irqsave(&cache_lock, flags);
1061 obj = __cache_find(id);
1064 - strcpy(name, obj->name);
1067 + __object_get(obj);
1068 spin_unlock_irqrestore(&cache_lock, flags);
1075 We encapsulate the reference counting in the standard 'get' and 'put'
1076 functions. Now we can return the object itself from
1077 <function>cache_find</function> which has the advantage that the user
1078 can now sleep holding the object (eg. to
1079 <function>copy_to_user</function> to name to userspace).
1082 The other point to note is that I said a reference should be held for
1083 every pointer to the object: thus the reference count is 1 when first
1084 inserted into the cache. In some versions the framework does not hold
1085 a reference count, but they are more complicated.
1088 <sect2 id="examples-refcnt-atomic">
1089 <title>Using Atomic Operations For The Reference Count</title>
1091 In practice, <type>atomic_t</type> would usually be used for
1092 <structfield>refcnt</structfield>. There are a number of atomic
1093 operations defined in
1095 <filename class="headerfile">include/asm/atomic.h</filename>: these are
1096 guaranteed to be seen atomically from all CPUs in the system, so no
1097 lock is required. In this case, it is simpler than using spinlocks,
1098 although for anything non-trivial using spinlocks is clearer. The
1099 <function>atomic_inc</function> and
1100 <function>atomic_dec_and_test</function> are used instead of the
1101 standard increment and decrement operators, and the lock is no longer
1102 used to protect the reference count itself.
1106 --- cache.c.refcnt 2003-12-09 15:00:35.000000000 +1100
1107 +++ cache.c.refcnt-atomic 2003-12-11 15:49:42.000000000 +1100
1111 struct list_head list;
1112 - unsigned int refcnt;
1118 static unsigned int cache_num = 0;
1119 #define MAX_CACHE_SIZE 10
1121 -static void __object_put(struct object *obj)
1123 - if (--obj->refcnt == 0)
1127 -static void __object_get(struct object *obj)
1132 void object_put(struct object *obj)
1134 - unsigned long flags;
1136 - spin_lock_irqsave(&cache_lock, flags);
1137 - __object_put(obj);
1138 - spin_unlock_irqrestore(&cache_lock, flags);
1139 + if (atomic_dec_and_test(&obj->refcnt))
1143 void object_get(struct object *obj)
1145 - unsigned long flags;
1147 - spin_lock_irqsave(&cache_lock, flags);
1148 - __object_get(obj);
1149 - spin_unlock_irqrestore(&cache_lock, flags);
1150 + atomic_inc(&obj->refcnt);
1153 /* Must be holding cache_lock */
1157 list_del(&obj->list);
1158 - __object_put(obj);
1164 strlcpy(obj->name, name, sizeof(obj->name));
1166 obj->popularity = 0;
1167 - obj->refcnt = 1; /* The cache holds a reference */
1168 + atomic_set(&obj->refcnt, 1); /* The cache holds a reference */
1170 spin_lock_irqsave(&cache_lock, flags);
1173 spin_lock_irqsave(&cache_lock, flags);
1174 obj = __cache_find(id);
1176 - __object_get(obj);
1178 spin_unlock_irqrestore(&cache_lock, flags);
1185 <sect1 id="examples-lock-per-obj">
1186 <title>Protecting The Objects Themselves</title>
1188 In these examples, we assumed that the objects (except the reference
1189 counts) never changed once they are created. If we wanted to allow
1190 the name to change, there are three possibilities:
1195 You can make <symbol>cache_lock</symbol> non-static, and tell people
1196 to grab that lock before changing the name in any object.
1201 You can provide a <function>cache_obj_rename</function> which grabs
1202 this lock and changes the name for the caller, and tell everyone to
1208 You can make the <symbol>cache_lock</symbol> protect only the cache
1209 itself, and use another lock to protect the name.
1215 Theoretically, you can make the locks as fine-grained as one lock for
1216 every field, for every object. In practice, the most common variants
1222 One lock which protects the infrastructure (the <symbol>cache</symbol>
1223 list in this example) and all the objects. This is what we have done
1229 One lock which protects the infrastructure (including the list
1230 pointers inside the objects), and one lock inside the object which
1231 protects the rest of that object.
1236 Multiple locks to protect the infrastructure (eg. one lock per hash
1237 chain), possibly with a separate per-object lock.
1243 Here is the "lock-per-object" implementation:
1246 --- cache.c.refcnt-atomic 2003-12-11 15:50:54.000000000 +1100
1247 +++ cache.c.perobjectlock 2003-12-11 17:15:03.000000000 +1100
1252 + /* These two protected by cache_lock. */
1253 struct list_head list;
1258 + /* Doesn't change once created. */
1261 + spinlock_t lock; /* Protects the name */
1266 static DEFINE_SPINLOCK(cache_lock);
1269 obj->popularity = 0;
1270 atomic_set(&obj->refcnt, 1); /* The cache holds a reference */
1271 + spin_lock_init(&obj->lock);
1273 spin_lock_irqsave(&cache_lock, flags);
1278 Note that I decide that the <structfield>popularity</structfield>
1279 count should be protected by the <symbol>cache_lock</symbol> rather
1280 than the per-object lock: this is because it (like the
1281 <structname>struct list_head</structname> inside the object) is
1282 logically part of the infrastructure. This way, I don't need to grab
1283 the lock of every object in <function>__cache_add</function> when
1284 seeking the least popular.
1288 I also decided that the <structfield>id</structfield> member is
1289 unchangeable, so I don't need to grab each object lock in
1290 <function>__cache_find()</function> to examine the
1291 <structfield>id</structfield>: the object lock is only used by a
1292 caller who wants to read or write the <structfield>name</structfield>
1297 Note also that I added a comment describing what data was protected by
1298 which locks. This is extremely important, as it describes the runtime
1299 behavior of the code, and can be hard to gain from just reading. And
1300 as Alan Cox says, <quote>Lock data, not code</quote>.
1305 <chapter id="common-problems">
1306 <title>Common Problems</title>
1307 <sect1 id="deadlock">
1308 <title>Deadlock: Simple and Advanced</title>
1311 There is a coding bug where a piece of code tries to grab a
1312 spinlock twice: it will spin forever, waiting for the lock to
1313 be released (spinlocks, rwlocks and semaphores are not
1314 recursive in Linux). This is trivial to diagnose: not a
1315 stay-up-five-nights-talk-to-fluffy-code-bunnies kind of
1320 For a slightly more complex case, imagine you have a region
1321 shared by a softirq and user context. If you use a
1322 <function>spin_lock()</function> call to protect it, it is
1323 possible that the user context will be interrupted by the softirq
1324 while it holds the lock, and the softirq will then spin
1325 forever trying to get the same lock.
1329 Both of these are called deadlock, and as shown above, it can
1330 occur even with a single CPU (although not on UP compiles,
1331 since spinlocks vanish on kernel compiles with
1332 <symbol>CONFIG_SMP</symbol>=n. You'll still get data corruption
1333 in the second example).
1337 This complete lockup is easy to diagnose: on SMP boxes the
1338 watchdog timer or compiling with <symbol>DEBUG_SPINLOCKS</symbol> set
1339 (<filename>include/linux/spinlock.h</filename>) will show this up
1340 immediately when it happens.
1344 A more complex problem is the so-called 'deadly embrace',
1345 involving two or more locks. Say you have a hash table: each
1346 entry in the table is a spinlock, and a chain of hashed
1347 objects. Inside a softirq handler, you sometimes want to
1348 alter an object from one place in the hash to another: you
1349 grab the spinlock of the old hash chain and the spinlock of
1350 the new hash chain, and delete the object from the old one,
1351 and insert it in the new one.
1355 There are two problems here. First, if your code ever
1356 tries to move the object to the same chain, it will deadlock
1357 with itself as it tries to lock it twice. Secondly, if the
1358 same softirq on another CPU is trying to move another object
1359 in the reverse direction, the following could happen:
1363 <title>Consequences</title>
1365 <tgroup cols="2" align="left">
1369 <entry>CPU 1</entry>
1370 <entry>CPU 2</entry>
1376 <entry>Grab lock A -> OK</entry>
1377 <entry>Grab lock B -> OK</entry>
1380 <entry>Grab lock B -> spin</entry>
1381 <entry>Grab lock A -> spin</entry>
1388 The two CPUs will spin forever, waiting for the other to give up
1389 their lock. It will look, smell, and feel like a crash.
1393 <sect1 id="techs-deadlock-prevent">
1394 <title>Preventing Deadlock</title>
1397 Textbooks will tell you that if you always lock in the same
1398 order, you will never get this kind of deadlock. Practice
1399 will tell you that this approach doesn't scale: when I
1400 create a new lock, I don't understand enough of the kernel
1401 to figure out where in the 5000 lock hierarchy it will fit.
1405 The best locks are encapsulated: they never get exposed in
1406 headers, and are never held around calls to non-trivial
1407 functions outside the same file. You can read through this
1408 code and see that it will never deadlock, because it never
1409 tries to grab another lock while it has that one. People
1410 using your code don't even need to know you are using a
1415 A classic problem here is when you provide callbacks or
1416 hooks: if you call these with the lock held, you risk simple
1417 deadlock, or a deadly embrace (who knows what the callback
1418 will do?). Remember, the other programmers are out to get
1419 you, so don't do this.
1422 <sect2 id="techs-deadlock-overprevent">
1423 <title>Overzealous Prevention Of Deadlocks</title>
1426 Deadlocks are problematic, but not as bad as data
1427 corruption. Code which grabs a read lock, searches a list,
1428 fails to find what it wants, drops the read lock, grabs a
1429 write lock and inserts the object has a race condition.
1433 If you don't see why, please stay the fuck away from my code.
1438 <sect1 id="racing-timers">
1439 <title>Racing Timers: A Kernel Pastime</title>
1442 Timers can produce their own special problems with races.
1443 Consider a collection of objects (list, hash, etc) where each
1444 object has a timer which is due to destroy it.
1448 If you want to destroy the entire collection (say on module
1449 removal), you might do the following:
1453 /* THIS CODE BAD BAD BAD BAD: IF IT WAS ANY WORSE IT WOULD USE
1454 HUNGARIAN NOTATION */
1455 spin_lock_bh(&list_lock);
1458 struct foo *next = list->next;
1459 del_timer(&list->timer);
1464 spin_unlock_bh(&list_lock);
1468 Sooner or later, this will crash on SMP, because a timer can
1469 have just gone off before the <function>spin_lock_bh()</function>,
1470 and it will only get the lock after we
1471 <function>spin_unlock_bh()</function>, and then try to free
1472 the element (which has already been freed!).
1476 This can be avoided by checking the result of
1477 <function>del_timer()</function>: if it returns
1478 <returnvalue>1</returnvalue>, the timer has been deleted.
1479 If <returnvalue>0</returnvalue>, it means (in this
1480 case) that it is currently running, so we can do:
1485 spin_lock_bh(&list_lock);
1488 struct foo *next = list->next;
1489 if (!del_timer(&list->timer)) {
1490 /* Give timer a chance to delete this */
1491 spin_unlock_bh(&list_lock);
1498 spin_unlock_bh(&list_lock);
1502 Another common problem is deleting timers which restart
1503 themselves (by calling <function>add_timer()</function> at the end
1504 of their timer function). Because this is a fairly common case
1505 which is prone to races, you should use <function>del_timer_sync()</function>
1506 (<filename class="headerfile">include/linux/timer.h</filename>)
1507 to handle this case. It returns the number of times the timer
1508 had to be deleted before we finally stopped it from adding itself back
1515 <chapter id="Efficiency">
1516 <title>Locking Speed</title>
1519 There are three main things to worry about when considering speed of
1520 some code which does locking. First is concurrency: how many things
1521 are going to be waiting while someone else is holding a lock. Second
1522 is the time taken to actually acquire and release an uncontended lock.
1523 Third is using fewer, or smarter locks. I'm assuming that the lock is
1524 used fairly often: otherwise, you wouldn't be concerned about
1528 Concurrency depends on how long the lock is usually held: you should
1529 hold the lock for as long as needed, but no longer. In the cache
1530 example, we always create the object without the lock held, and then
1531 grab the lock only when we are ready to insert it in the list.
1534 Acquisition times depend on how much damage the lock operations do to
1535 the pipeline (pipeline stalls) and how likely it is that this CPU was
1536 the last one to grab the lock (ie. is the lock cache-hot for this
1537 CPU): on a machine with more CPUs, this likelihood drops fast.
1538 Consider a 700MHz Intel Pentium III: an instruction takes about 0.7ns,
1539 an atomic increment takes about 58ns, a lock which is cache-hot on
1540 this CPU takes 160ns, and a cacheline transfer from another CPU takes
1541 an additional 170 to 360ns. (These figures from Paul McKenney's
1542 <ulink url="http://www.linuxjournal.com/article.php?sid=6993"> Linux
1543 Journal RCU article</ulink>).
1546 These two aims conflict: holding a lock for a short time might be done
1547 by splitting locks into parts (such as in our final per-object-lock
1548 example), but this increases the number of lock acquisitions, and the
1549 results are often slower than having a single lock. This is another
1550 reason to advocate locking simplicity.
1553 The third concern is addressed below: there are some methods to reduce
1554 the amount of locking which needs to be done.
1557 <sect1 id="efficiency-rwlocks">
1558 <title>Read/Write Lock Variants</title>
1561 Both spinlocks and semaphores have read/write variants:
1562 <type>rwlock_t</type> and <structname>struct rw_semaphore</structname>.
1563 These divide users into two classes: the readers and the writers. If
1564 you are only reading the data, you can get a read lock, but to write to
1565 the data you need the write lock. Many people can hold a read lock,
1566 but a writer must be sole holder.
1570 If your code divides neatly along reader/writer lines (as our
1571 cache code does), and the lock is held by readers for
1572 significant lengths of time, using these locks can help. They
1573 are slightly slower than the normal locks though, so in practice
1574 <type>rwlock_t</type> is not usually worthwhile.
1578 <sect1 id="efficiency-read-copy-update">
1579 <title>Avoiding Locks: Read Copy Update</title>
1582 There is a special method of read/write locking called Read Copy
1583 Update. Using RCU, the readers can avoid taking a lock
1584 altogether: as we expect our cache to be read more often than
1585 updated (otherwise the cache is a waste of time), it is a
1586 candidate for this optimization.
1590 How do we get rid of read locks? Getting rid of read locks
1591 means that writers may be changing the list underneath the
1592 readers. That is actually quite simple: we can read a linked
1593 list while an element is being added if the writer adds the
1594 element very carefully. For example, adding
1595 <symbol>new</symbol> to a single linked list called
1596 <symbol>list</symbol>:
1600 new->next = list->next;
1602 list->next = new;
1606 The <function>wmb()</function> is a write memory barrier. It
1607 ensures that the first operation (setting the new element's
1608 <symbol>next</symbol> pointer) is complete and will be seen by
1609 all CPUs, before the second operation is (putting the new
1610 element into the list). This is important, since modern
1611 compilers and modern CPUs can both reorder instructions unless
1612 told otherwise: we want a reader to either not see the new
1613 element at all, or see the new element with the
1614 <symbol>next</symbol> pointer correctly pointing at the rest of
1618 Fortunately, there is a function to do this for standard
1619 <structname>struct list_head</structname> lists:
1620 <function>list_add_rcu()</function>
1621 (<filename>include/linux/list.h</filename>).
1624 Removing an element from the list is even simpler: we replace
1625 the pointer to the old element with a pointer to its successor,
1626 and readers will either see it, or skip over it.
1629 list->next = old->next;
1632 There is <function>list_del_rcu()</function>
1633 (<filename>include/linux/list.h</filename>) which does this (the
1634 normal version poisons the old object, which we don't want).
1637 The reader must also be careful: some CPUs can look through the
1638 <symbol>next</symbol> pointer to start reading the contents of
1639 the next element early, but don't realize that the pre-fetched
1640 contents is wrong when the <symbol>next</symbol> pointer changes
1641 underneath them. Once again, there is a
1642 <function>list_for_each_entry_rcu()</function>
1643 (<filename>include/linux/list.h</filename>) to help you. Of
1644 course, writers can just use
1645 <function>list_for_each_entry()</function>, since there cannot
1646 be two simultaneous writers.
1649 Our final dilemma is this: when can we actually destroy the
1650 removed element? Remember, a reader might be stepping through
1651 this element in the list right now: if we free this element and
1652 the <symbol>next</symbol> pointer changes, the reader will jump
1653 off into garbage and crash. We need to wait until we know that
1654 all the readers who were traversing the list when we deleted the
1655 element are finished. We use <function>call_rcu()</function> to
1656 register a callback which will actually destroy the object once
1657 the readers are finished.
1660 But how does Read Copy Update know when the readers are
1661 finished? The method is this: firstly, the readers always
1662 traverse the list inside
1663 <function>rcu_read_lock()</function>/<function>rcu_read_unlock()</function>
1664 pairs: these simply disable preemption so the reader won't go to
1665 sleep while reading the list.
1668 RCU then waits until every other CPU has slept at least once:
1669 since readers cannot sleep, we know that any readers which were
1670 traversing the list during the deletion are finished, and the
1671 callback is triggered. The real Read Copy Update code is a
1672 little more optimized than this, but this is the fundamental
1677 --- cache.c.perobjectlock 2003-12-11 17:15:03.000000000 +1100
1678 +++ cache.c.rcupdate 2003-12-11 17:55:14.000000000 +1100
1680 #include <linux/list.h>
1681 #include <linux/slab.h>
1682 #include <linux/string.h>
1683 +#include <linux/rcupdate.h>
1684 #include <linux/semaphore.h>
1685 #include <asm/errno.h>
1689 - /* These two protected by cache_lock. */
1690 + /* This is protected by RCU */
1691 struct list_head list;
1694 + struct rcu_head rcu;
1698 /* Doesn't change once created. */
1703 - list_for_each_entry(i, &cache, list) {
1704 + list_for_each_entry_rcu(i, &cache, list) {
1705 if (i->id == id) {
1712 +/* Final discard done once we know no readers are looking. */
1713 +static void cache_delete_rcu(void *arg)
1718 /* Must be holding cache_lock */
1719 static void __cache_delete(struct object *obj)
1722 - list_del(&obj->list);
1724 + list_del_rcu(&obj->list);
1726 + call_rcu(&obj->rcu, cache_delete_rcu, obj);
1729 /* Must be holding cache_lock */
1730 static void __cache_add(struct object *obj)
1732 - list_add(&obj->list, &cache);
1733 + list_add_rcu(&obj->list, &cache);
1734 if (++cache_num > MAX_CACHE_SIZE) {
1735 struct object *i, *outcast = NULL;
1736 list_for_each_entry(i, &cache, list) {
1738 obj->popularity = 0;
1739 atomic_set(&obj->refcnt, 1); /* The cache holds a reference */
1740 spin_lock_init(&obj->lock);
1741 + INIT_RCU_HEAD(&obj->rcu);
1743 spin_lock_irqsave(&cache_lock, flags);
1745 @@ -104,12 +114,11 @@
1746 struct object *cache_find(int id)
1749 - unsigned long flags;
1751 - spin_lock_irqsave(&cache_lock, flags);
1753 obj = __cache_find(id);
1756 - spin_unlock_irqrestore(&cache_lock, flags);
1757 + rcu_read_unlock();
1763 Note that the reader will alter the
1764 <structfield>popularity</structfield> member in
1765 <function>__cache_find()</function>, and now it doesn't hold a lock.
1766 One solution would be to make it an <type>atomic_t</type>, but for
1767 this usage, we don't really care about races: an approximate result is
1768 good enough, so I didn't change it.
1772 The result is that <function>cache_find()</function> requires no
1773 synchronization with any other functions, so is almost as fast on SMP
1774 as it would be on UP.
1778 There is a furthur optimization possible here: remember our original
1779 cache code, where there were no reference counts and the caller simply
1780 held the lock whenever using the object? This is still possible: if
1781 you hold the lock, noone can delete the object, so you don't need to
1782 get and put the reference count.
1786 Now, because the 'read lock' in RCU is simply disabling preemption, a
1787 caller which always has preemption disabled between calling
1788 <function>cache_find()</function> and
1789 <function>object_put()</function> does not need to actually get and
1790 put the reference count: we could expose
1791 <function>__cache_find()</function> by making it non-static, and
1792 such callers could simply call that.
1795 The benefit here is that the reference count is not written to: the
1796 object is not altered in any way, which is much faster on SMP
1797 machines due to caching.
1801 <sect1 id="per-cpu">
1802 <title>Per-CPU Data</title>
1805 Another technique for avoiding locking which is used fairly
1806 widely is to duplicate information for each CPU. For example,
1807 if you wanted to keep a count of a common condition, you could
1808 use a spin lock and a single counter. Nice and simple.
1812 If that was too slow (it's usually not, but if you've got a
1813 really big machine to test on and can show that it is), you
1814 could instead use a counter for each CPU, then none of them need
1815 an exclusive lock. See <function>DEFINE_PER_CPU()</function>,
1816 <function>get_cpu_var()</function> and
1817 <function>put_cpu_var()</function>
1818 (<filename class="headerfile">include/linux/percpu.h</filename>).
1822 Of particular use for simple per-cpu counters is the
1823 <type>local_t</type> type, and the
1824 <function>cpu_local_inc()</function> and related functions,
1825 which are more efficient than simple code on some architectures
1826 (<filename class="headerfile">include/asm/local.h</filename>).
1830 Note that there is no simple, reliable way of getting an exact
1831 value of such a counter, without introducing more locks. This
1832 is not a problem for some uses.
1836 <sect1 id="mostly-hardirq">
1837 <title>Data Which Mostly Used By An IRQ Handler</title>
1840 If data is always accessed from within the same IRQ handler, you
1841 don't need a lock at all: the kernel already guarantees that the
1842 irq handler will not run simultaneously on multiple CPUs.
1845 Manfred Spraul points out that you can still do this, even if
1846 the data is very occasionally accessed in user context or
1847 softirqs/tasklets. The irq handler doesn't use a lock, and
1848 all other accesses are done as so:
1852 spin_lock(&lock);
1856 spin_unlock(&lock);
1859 The <function>disable_irq()</function> prevents the irq handler
1860 from running (and waits for it to finish if it's currently
1861 running on other CPUs). The spinlock prevents any other
1862 accesses happening at the same time. Naturally, this is slower
1863 than just a <function>spin_lock_irq()</function> call, so it
1864 only makes sense if this type of access happens extremely
1870 <chapter id="sleeping-things">
1871 <title>What Functions Are Safe To Call From Interrupts?</title>
1874 Many functions in the kernel sleep (ie. call schedule())
1875 directly or indirectly: you can never call them while holding a
1876 spinlock, or with preemption disabled. This also means you need
1877 to be in user context: calling them from an interrupt is illegal.
1880 <sect1 id="sleeping">
1881 <title>Some Functions Which Sleep</title>
1884 The most common ones are listed below, but you usually have to
1885 read the code to find out if other calls are safe. If everyone
1886 else who calls it can sleep, you probably need to be able to
1887 sleep, too. In particular, registration and deregistration
1888 functions usually expect to be called from user context, and can
1896 <firstterm linkend="gloss-userspace">userspace</firstterm>:
1901 <function>copy_from_user()</function>
1906 <function>copy_to_user()</function>
1911 <function>get_user()</function>
1916 <function> put_user()</function>
1924 <function>kmalloc(GFP_KERNEL)</function>
1930 <function>down_interruptible()</function> and
1931 <function>down()</function>
1934 There is a <function>down_trylock()</function> which can be
1935 used inside interrupt context, as it will not sleep.
1936 <function>up()</function> will also never sleep.
1942 <sect1 id="dont-sleep">
1943 <title>Some Functions Which Don't Sleep</title>
1946 Some functions are safe to call from any context, or holding
1953 <function>printk()</function>
1958 <function>kfree()</function>
1963 <function>add_timer()</function> and <function>del_timer()</function>
1970 <chapter id="references">
1971 <title>Further reading</title>
1976 <filename>Documentation/spinlocks.txt</filename>:
1977 Linus Torvalds' spinlocking tutorial in the kernel sources.
1983 Unix Systems for Modern Architectures: Symmetric
1984 Multiprocessing and Caching for Kernel Programmers:
1988 Curt Schimmel's very good introduction to kernel level
1989 locking (not written for Linux, but nearly everything
1990 applies). The book is expensive, but really worth every
1991 penny to understand SMP locking. [ISBN: 0201633388]
1997 <chapter id="thanks">
1998 <title>Thanks</title>
2001 Thanks to Telsa Gwynne for DocBooking, neatening and adding
2006 Thanks to Martin Pool, Philipp Rumpf, Stephen Rothwell, Paul
2007 Mackerras, Ruedi Aschwanden, Alan Cox, Manfred Spraul, Tim
2008 Waugh, Pete Zaitcev, James Morris, Robert Love, Paul McKenney,
2009 John Ashby for proofreading, correcting, flaming, commenting.
2013 Thanks to the cabal for having no influence on this document.
2017 <glossary id="glossary">
2018 <title>Glossary</title>
2020 <glossentry id="gloss-preemption">
2021 <glossterm>preemption</glossterm>
2024 Prior to 2.5, or when <symbol>CONFIG_PREEMPT</symbol> is
2025 unset, processes in user context inside the kernel would not
2026 preempt each other (ie. you had that CPU until you have it up,
2027 except for interrupts). With the addition of
2028 <symbol>CONFIG_PREEMPT</symbol> in 2.5.4, this changed: when
2029 in user context, higher priority tasks can "cut in": spinlocks
2030 were changed to disable preemption, even on UP.
2035 <glossentry id="gloss-bh">
2036 <glossterm>bh</glossterm>
2039 Bottom Half: for historical reasons, functions with
2040 '_bh' in them often now refer to any software interrupt, e.g.
2041 <function>spin_lock_bh()</function> blocks any software interrupt
2042 on the current CPU. Bottom halves are deprecated, and will
2043 eventually be replaced by tasklets. Only one bottom half will be
2044 running at any time.
2049 <glossentry id="gloss-hwinterrupt">
2050 <glossterm>Hardware Interrupt / Hardware IRQ</glossterm>
2053 Hardware interrupt request. <function>in_irq()</function> returns
2054 <returnvalue>true</returnvalue> in a hardware interrupt handler.
2059 <glossentry id="gloss-interruptcontext">
2060 <glossterm>Interrupt Context</glossterm>
2063 Not user context: processing a hardware irq or software irq.
2064 Indicated by the <function>in_interrupt()</function> macro
2065 returning <returnvalue>true</returnvalue>.
2070 <glossentry id="gloss-smp">
2071 <glossterm><acronym>SMP</acronym></glossterm>
2074 Symmetric Multi-Processor: kernels compiled for multiple-CPU
2075 machines. (CONFIG_SMP=y).
2080 <glossentry id="gloss-softirq">
2081 <glossterm>Software Interrupt / softirq</glossterm>
2084 Software interrupt handler. <function>in_irq()</function> returns
2085 <returnvalue>false</returnvalue>; <function>in_softirq()</function>
2086 returns <returnvalue>true</returnvalue>. Tasklets and softirqs
2087 both fall into the category of 'software interrupts'.
2090 Strictly speaking a softirq is one of up to 32 enumerated software
2091 interrupts which can run on multiple CPUs at once.
2092 Sometimes used to refer to tasklets as
2093 well (ie. all software interrupts).
2098 <glossentry id="gloss-tasklet">
2099 <glossterm>tasklet</glossterm>
2102 A dynamically-registrable software interrupt,
2103 which is guaranteed to only run on one CPU at a time.
2108 <glossentry id="gloss-timers">
2109 <glossterm>timer</glossterm>
2112 A dynamically-registrable software interrupt, which is run at
2113 (or close to) a given time. When running, it is just like a
2114 tasklet (in fact, they are called from the TIMER_SOFTIRQ).
2119 <glossentry id="gloss-up">
2120 <glossterm><acronym>UP</acronym></glossterm>
2123 Uni-Processor: Non-SMP. (CONFIG_SMP=n).
2128 <glossentry id="gloss-usercontext">
2129 <glossterm>User Context</glossterm>
2132 The kernel executing on behalf of a particular process (ie. a
2133 system call or trap) or kernel thread. You can tell which
2134 process with the <symbol>current</symbol> macro.) Not to
2135 be confused with userspace. Can be interrupted by software or
2136 hardware interrupts.
2141 <glossentry id="gloss-userspace">
2142 <glossterm>Userspace</glossterm>
2145 A process executing its own code outside the kernel.
projects / GitHub / mt8127 / android_kernel_alcatel_ttab.git / blob