linux - Documentation/kernel-hacking/locking.rst

1454 lines · 52.0 KiB

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