[IPV6]: Fix kernel OOPs when setting sticky socket options.
[linux-2.6] / Documentation / DocBook / kernel-locking.tmpl
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" []>
4
5 <book id="LKLockingGuide">
6  <bookinfo>
7   <title>Unreliable Guide To Locking</title>
8   
9   <authorgroup>
10    <author>
11     <firstname>Rusty</firstname>
12     <surname>Russell</surname>
13     <affiliation>
14      <address>
15       <email>rusty@rustcorp.com.au</email>
16      </address>
17     </affiliation>
18    </author>
19   </authorgroup>
20
21   <copyright>
22    <year>2003</year>
23    <holder>Rusty Russell</holder>
24   </copyright>
25
26   <legalnotice>
27    <para>
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
32      version.
33    </para>
34       
35    <para>
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.
40    </para>
41       
42    <para>
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,
46      MA 02111-1307 USA
47    </para>
48       
49    <para>
50      For more details see the file COPYING in the source
51      distribution of Linux.
52    </para>
53   </legalnotice>
54  </bookinfo>
55
56  <toc></toc>
57   <chapter id="intro">
58    <title>Introduction</title>
59    <para>
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.
63    </para>
64    <para>
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>.
70    </para>
71   </chapter>
72
73    <chapter id="races">
74     <title>The Problem With Concurrency</title>
75     <para>
76       (Skip this if you know what a Race Condition is).
77     </para>
78     <para>
79       In a normal program, you can increment a counter like so:
80     </para>
81     <programlisting>
82       very_important_count++;
83     </programlisting>
84
85     <para>
86       This is what they would expect to happen:
87     </para>
88
89     <table>
90      <title>Expected Results</title>
91
92      <tgroup cols="2" align="left">
93
94       <thead>
95        <row>
96         <entry>Instance 1</entry>
97         <entry>Instance 2</entry>
98        </row>
99       </thead>
100
101       <tbody>
102        <row>
103         <entry>read very_important_count (5)</entry>
104         <entry></entry>
105        </row>
106        <row>
107         <entry>add 1 (6)</entry>
108         <entry></entry>
109        </row>
110        <row>
111         <entry>write very_important_count (6)</entry>
112         <entry></entry>
113        </row>
114        <row>
115         <entry></entry>
116         <entry>read very_important_count (6)</entry>
117        </row>
118        <row>
119         <entry></entry>
120         <entry>add 1 (7)</entry>
121        </row>
122        <row>
123         <entry></entry>
124         <entry>write very_important_count (7)</entry>
125        </row>
126       </tbody>
127
128      </tgroup>
129     </table>
130
131     <para>
132      This is what might happen:
133     </para>
134
135     <table>
136      <title>Possible Results</title>
137
138      <tgroup cols="2" align="left">
139       <thead>
140        <row>
141         <entry>Instance 1</entry>
142         <entry>Instance 2</entry>
143        </row>
144       </thead>
145
146       <tbody>
147        <row>
148         <entry>read very_important_count (5)</entry>
149         <entry></entry>
150        </row>
151        <row>
152         <entry></entry>
153         <entry>read very_important_count (5)</entry>
154        </row>
155        <row>
156         <entry>add 1 (6)</entry>
157         <entry></entry>
158        </row>
159        <row>
160         <entry></entry>
161         <entry>add 1 (6)</entry>
162        </row>
163        <row>
164         <entry>write very_important_count (6)</entry>
165         <entry></entry>
166        </row>
167        <row>
168         <entry></entry>
169         <entry>write very_important_count (6)</entry>
170        </row>
171       </tbody>
172      </tgroup>
173     </table>
174
175     <sect1 id="race-condition">
176     <title>Race Conditions and Critical Regions</title>
177     <para>
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.
184     </para>
185     <para>
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.
190     </para>
191     <para>
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
197       they don't exist.
198     </para>
199     </sect1>
200   </chapter>
201
202   <chapter id="locks">
203    <title>Locking in the Linux Kernel</title>
204
205    <para>
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>.
209    </para>
210
211    <para>
212      Be reluctant to introduce new locks.
213    </para>
214
215    <para>
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.
219    </para>
220
221    <sect1 id="lock-intro">
222    <title>Two Main Types of Kernel Locks: Spinlocks and Semaphores</title>
223
224    <para>
225      There are three main types of kernel locks.  The fundamental type
226      is the spinlock 
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.
231    </para>
232    <para>
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.
241    </para>
242    <para>
243      The third type is a semaphore
244      (<filename class="headerfile">include/asm/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.
249    </para>
250    <para>
251      Neither type of lock is recursive: see
252      <xref linkend="deadlock"/>.
253    </para>
254    </sect1>
255  
256    <sect1 id="uniprocessor">
257     <title>Locks and Uniprocessor Kernels</title>
258
259     <para>
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.
264     </para>
265
266     <para>
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.
272     </para>
273
274     <para>
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.
278     </para>
279
280     <para>
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.
284     </para>
285    </sect1>
286
287     <sect1 id="usercontextlocking">
288      <title>Locking Only In User Context</title>
289
290      <para>
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/asm/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.
300      </para>
301
302      <para>
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
313        sleep.
314      </para>
315    </sect1>
316
317    <sect1 id="lock-user-bh">
318     <title>Locking Between User Context and Softirqs</title>
319
320     <para>
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).
332     </para>
333
334     <para>
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"/>.
338     </para>
339
340     <para>
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.
346     </para>
347    </sect1>
348
349    <sect1 id="lock-user-tasklet">
350     <title>Locking Between User Context and Tasklets</title>
351
352     <para>
353       This is exactly the same as above, because <firstterm
354       linkend="gloss-tasklet">tasklets</firstterm> are actually run
355       from a softirq.
356     </para>
357    </sect1>
358
359    <sect1 id="lock-user-timers">
360     <title>Locking Between User Context and Timers</title>
361
362     <para>
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
366       are identical.
367     </para>
368    </sect1>
369
370    <sect1 id="lock-tasklets">
371     <title>Locking Between Tasklets/Timers</title>
372
373     <para>
374       Sometimes a tasklet or timer might want to share data with
375       another tasklet or timer.
376     </para>
377
378     <sect2 id="lock-tasklets-same">
379      <title>The Same Tasklet/Timer</title>
380      <para>
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.
384      </para>
385     </sect2>
386
387     <sect2 id="lock-tasklets-different">
388      <title>Different Tasklets/Timers</title>
389      <para>
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.
397      </para>
398     </sect2>
399    </sect1>
400
401    <sect1 id="lock-softirqs">
402     <title>Locking Between Softirqs</title>
403
404     <para>
405       Often a softirq might
406       want to share data with itself or a tasklet/timer.
407     </para>
408
409     <sect2 id="lock-softirqs-same">
410      <title>The Same Softirq</title>
411
412      <para>
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.
418      </para>
419
420      <para>
421        You'll need to use <function>spin_lock()</function> and 
422        <function>spin_unlock()</function> for shared data.
423      </para>
424     </sect2>
425
426     <sect2 id="lock-softirqs-different">
427      <title>Different Softirqs</title>
428
429      <para>
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.
434      </para>
435     </sect2>
436    </sect1>
437   </chapter>
438
439   <chapter id="hardirq-context">
440    <title>Hard IRQ Context</title>
441
442    <para>
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.
446    </para>
447
448    <sect1 id="hardirq-softirq">
449     <title>Locking Between Hard IRQ and Softirqs/Tasklets</title>
450
451     <para>
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.
459     </para>
460
461     <para>
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.
469     </para>
470
471     <para>
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.
476     </para>
477
478     <para>
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).
486     </para>
487
488     <para>
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.
494     </para>
495
496    </sect1>
497    <sect1 id="hardirq-hardirq">
498     <title>Locking Between Two Hard IRQ Handlers</title>
499     <para>
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.
504     </para>
505    </sect1>
506
507   </chapter>
508
509   <chapter id="cheatsheet">
510    <title>Cheat Sheet For Locking</title>
511    <para>
512      Pete Zaitcev gives the following summary:
513    </para>
514    <itemizedlist>
515       <listitem>
516         <para>
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>).
521       </para>
522       </listitem>
523       <listitem>
524         <para>
525         Otherwise (== data can be touched in an interrupt), use
526         <function>spin_lock_irqsave()</function> and
527         <function>spin_unlock_irqrestore()</function>.
528         </para>
529       </listitem>
530       <listitem>
531         <para>
532         Avoid holding spinlock for more than 5 lines of code and
533         across any function call (except accessors like
534         <function>readb</function>).
535         </para>
536       </listitem>
537     </itemizedlist>
538
539    <sect1 id="minimum-lock-reqirements">
540    <title>Table of Minimum Requirements</title>
541
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).
548    </para>
549    <para>
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.
553    </para>
554    <table>
555 <title>Table of Locking Requirements</title>
556 <tgroup cols="11">
557 <tbody>
558 <row>
559 <entry></entry>
560 <entry>IRQ Handler A</entry>
561 <entry>IRQ Handler B</entry>
562 <entry>Softirq A</entry>
563 <entry>Softirq B</entry>
564 <entry>Tasklet A</entry>
565 <entry>Tasklet B</entry>
566 <entry>Timer A</entry>
567 <entry>Timer B</entry>
568 <entry>User Context A</entry>
569 <entry>User Context B</entry>
570 </row>
571
572 <row>
573 <entry>IRQ Handler A</entry>
574 <entry>None</entry>
575 </row>
576
577 <row>
578 <entry>IRQ Handler B</entry>
579 <entry>spin_lock_irqsave</entry>
580 <entry>None</entry>
581 </row>
582
583 <row>
584 <entry>Softirq A</entry>
585 <entry>spin_lock_irq</entry>
586 <entry>spin_lock_irq</entry>
587 <entry>spin_lock</entry>
588 </row>
589
590 <row>
591 <entry>Softirq B</entry>
592 <entry>spin_lock_irq</entry>
593 <entry>spin_lock_irq</entry>
594 <entry>spin_lock</entry>
595 <entry>spin_lock</entry>
596 </row>
597
598 <row>
599 <entry>Tasklet A</entry>
600 <entry>spin_lock_irq</entry>
601 <entry>spin_lock_irq</entry>
602 <entry>spin_lock</entry>
603 <entry>spin_lock</entry>
604 <entry>None</entry>
605 </row>
606
607 <row>
608 <entry>Tasklet B</entry>
609 <entry>spin_lock_irq</entry>
610 <entry>spin_lock_irq</entry>
611 <entry>spin_lock</entry>
612 <entry>spin_lock</entry>
613 <entry>spin_lock</entry>
614 <entry>None</entry>
615 </row>
616
617 <row>
618 <entry>Timer A</entry>
619 <entry>spin_lock_irq</entry>
620 <entry>spin_lock_irq</entry>
621 <entry>spin_lock</entry>
622 <entry>spin_lock</entry>
623 <entry>spin_lock</entry>
624 <entry>spin_lock</entry>
625 <entry>None</entry>
626 </row>
627
628 <row>
629 <entry>Timer B</entry>
630 <entry>spin_lock_irq</entry>
631 <entry>spin_lock_irq</entry>
632 <entry>spin_lock</entry>
633 <entry>spin_lock</entry>
634 <entry>spin_lock</entry>
635 <entry>spin_lock</entry>
636 <entry>spin_lock</entry>
637 <entry>None</entry>
638 </row>
639
640 <row>
641 <entry>User Context A</entry>
642 <entry>spin_lock_irq</entry>
643 <entry>spin_lock_irq</entry>
644 <entry>spin_lock_bh</entry>
645 <entry>spin_lock_bh</entry>
646 <entry>spin_lock_bh</entry>
647 <entry>spin_lock_bh</entry>
648 <entry>spin_lock_bh</entry>
649 <entry>spin_lock_bh</entry>
650 <entry>None</entry>
651 </row>
652
653 <row>
654 <entry>User Context B</entry>
655 <entry>spin_lock_irq</entry>
656 <entry>spin_lock_irq</entry>
657 <entry>spin_lock_bh</entry>
658 <entry>spin_lock_bh</entry>
659 <entry>spin_lock_bh</entry>
660 <entry>spin_lock_bh</entry>
661 <entry>spin_lock_bh</entry>
662 <entry>spin_lock_bh</entry>
663 <entry>down_interruptible</entry>
664 <entry>None</entry>
665 </row>
666
667 </tbody>
668 </tgroup>
669 </table>
670 </sect1>
671 </chapter>
672
673   <chapter id="Examples">
674    <title>Common Examples</title>
675     <para>
676 Let's step through a simple example: a cache of number to name
677 mappings.  The cache keeps a count of how often each of the objects is
678 used, and when it gets full, throws out the least used one.
679
680     </para>
681
682    <sect1 id="examples-usercontext">
683     <title>All In User Context</title>
684     <para>
685 For our first example, we assume that all operations are in user
686 context (ie. from system calls), so we can sleep.  This means we can
687 use a semaphore to protect the cache and all the objects within
688 it.  Here's the code:
689     </para>
690
691     <programlisting>
692 #include &lt;linux/list.h&gt;
693 #include &lt;linux/slab.h&gt;
694 #include &lt;linux/string.h&gt;
695 #include &lt;asm/semaphore.h&gt;
696 #include &lt;asm/errno.h&gt;
697
698 struct object
699 {
700         struct list_head list;
701         int id;
702         char name[32];
703         int popularity;
704 };
705
706 /* Protects the cache, cache_num, and the objects within it */
707 static DECLARE_MUTEX(cache_lock);
708 static LIST_HEAD(cache);
709 static unsigned int cache_num = 0;
710 #define MAX_CACHE_SIZE 10
711
712 /* Must be holding cache_lock */
713 static struct object *__cache_find(int id)
714 {
715         struct object *i;
716
717         list_for_each_entry(i, &amp;cache, list)
718                 if (i-&gt;id == id) {
719                         i-&gt;popularity++;
720                         return i;
721                 }
722         return NULL;
723 }
724
725 /* Must be holding cache_lock */
726 static void __cache_delete(struct object *obj)
727 {
728         BUG_ON(!obj);
729         list_del(&amp;obj-&gt;list);
730         kfree(obj);
731         cache_num--;
732 }
733
734 /* Must be holding cache_lock */
735 static void __cache_add(struct object *obj)
736 {
737         list_add(&amp;obj-&gt;list, &amp;cache);
738         if (++cache_num > MAX_CACHE_SIZE) {
739                 struct object *i, *outcast = NULL;
740                 list_for_each_entry(i, &amp;cache, list) {
741                         if (!outcast || i-&gt;popularity &lt; outcast-&gt;popularity)
742                                 outcast = i;
743                 }
744                 __cache_delete(outcast);
745         }
746 }
747
748 int cache_add(int id, const char *name)
749 {
750         struct object *obj;
751
752         if ((obj = kmalloc(sizeof(*obj), GFP_KERNEL)) == NULL)
753                 return -ENOMEM;
754
755         strlcpy(obj-&gt;name, name, sizeof(obj-&gt;name));
756         obj-&gt;id = id;
757         obj-&gt;popularity = 0;
758
759         down(&amp;cache_lock);
760         __cache_add(obj);
761         up(&amp;cache_lock);
762         return 0;
763 }
764
765 void cache_delete(int id)
766 {
767         down(&amp;cache_lock);
768         __cache_delete(__cache_find(id));
769         up(&amp;cache_lock);
770 }
771
772 int cache_find(int id, char *name)
773 {
774         struct object *obj;
775         int ret = -ENOENT;
776
777         down(&amp;cache_lock);
778         obj = __cache_find(id);
779         if (obj) {
780                 ret = 0;
781                 strcpy(name, obj-&gt;name);
782         }
783         up(&amp;cache_lock);
784         return ret;
785 }
786 </programlisting>
787
788     <para>
789 Note that we always make sure we have the cache_lock when we add,
790 delete, or look up the cache: both the cache infrastructure itself and
791 the contents of the objects are protected by the lock.  In this case
792 it's easy, since we copy the data for the user, and never let them
793 access the objects directly.
794     </para>
795     <para>
796 There is a slight (and common) optimization here: in
797 <function>cache_add</function> we set up the fields of the object
798 before grabbing the lock.  This is safe, as no-one else can access it
799 until we put it in cache.
800     </para>
801     </sect1>
802
803    <sect1 id="examples-interrupt">
804     <title>Accessing From Interrupt Context</title>
805     <para>
806 Now consider the case where <function>cache_find</function> can be
807 called from interrupt context: either a hardware interrupt or a
808 softirq.  An example would be a timer which deletes object from the
809 cache.
810     </para>
811     <para>
812 The change is shown below, in standard patch format: the
813 <symbol>-</symbol> are lines which are taken away, and the
814 <symbol>+</symbol> are lines which are added.
815     </para>
816 <programlisting>
817 --- cache.c.usercontext 2003-12-09 13:58:54.000000000 +1100
818 +++ cache.c.interrupt   2003-12-09 14:07:49.000000000 +1100
819 @@ -12,7 +12,7 @@
820          int popularity;
821  };
822
823 -static DECLARE_MUTEX(cache_lock);
824 +static spinlock_t cache_lock = SPIN_LOCK_UNLOCKED;
825  static LIST_HEAD(cache);
826  static unsigned int cache_num = 0;
827  #define MAX_CACHE_SIZE 10
828 @@ -55,6 +55,7 @@
829  int cache_add(int id, const char *name)
830  {
831          struct object *obj;
832 +        unsigned long flags;
833
834          if ((obj = kmalloc(sizeof(*obj), GFP_KERNEL)) == NULL)
835                  return -ENOMEM;
836 @@ -63,30 +64,33 @@
837          obj-&gt;id = id;
838          obj-&gt;popularity = 0;
839
840 -        down(&amp;cache_lock);
841 +        spin_lock_irqsave(&amp;cache_lock, flags);
842          __cache_add(obj);
843 -        up(&amp;cache_lock);
844 +        spin_unlock_irqrestore(&amp;cache_lock, flags);
845          return 0;
846  }
847
848  void cache_delete(int id)
849  {
850 -        down(&amp;cache_lock);
851 +        unsigned long flags;
852 +
853 +        spin_lock_irqsave(&amp;cache_lock, flags);
854          __cache_delete(__cache_find(id));
855 -        up(&amp;cache_lock);
856 +        spin_unlock_irqrestore(&amp;cache_lock, flags);
857  }
858
859  int cache_find(int id, char *name)
860  {
861          struct object *obj;
862          int ret = -ENOENT;
863 +        unsigned long flags;
864
865 -        down(&amp;cache_lock);
866 +        spin_lock_irqsave(&amp;cache_lock, flags);
867          obj = __cache_find(id);
868          if (obj) {
869                  ret = 0;
870                  strcpy(name, obj-&gt;name);
871          }
872 -        up(&amp;cache_lock);
873 +        spin_unlock_irqrestore(&amp;cache_lock, flags);
874          return ret;
875  }
876 </programlisting>
877
878     <para>
879 Note that the <function>spin_lock_irqsave</function> will turn off
880 interrupts if they are on, otherwise does nothing (if we are already
881 in an interrupt handler), hence these functions are safe to call from
882 any context.
883     </para>
884     <para>
885 Unfortunately, <function>cache_add</function> calls
886 <function>kmalloc</function> with the <symbol>GFP_KERNEL</symbol>
887 flag, which is only legal in user context.  I have assumed that
888 <function>cache_add</function> is still only called in user context,
889 otherwise this should become a parameter to
890 <function>cache_add</function>.
891     </para>
892   </sect1>
893    <sect1 id="examples-refcnt">
894     <title>Exposing Objects Outside This File</title>
895     <para>
896 If our objects contained more information, it might not be sufficient
897 to copy the information in and out: other parts of the code might want
898 to keep pointers to these objects, for example, rather than looking up
899 the id every time.  This produces two problems.
900     </para>
901     <para>
902 The first problem is that we use the <symbol>cache_lock</symbol> to
903 protect objects: we'd need to make this non-static so the rest of the
904 code can use it.  This makes locking trickier, as it is no longer all
905 in one place.
906     </para>
907     <para>
908 The second problem is the lifetime problem: if another structure keeps
909 a pointer to an object, it presumably expects that pointer to remain
910 valid.  Unfortunately, this is only guaranteed while you hold the
911 lock, otherwise someone might call <function>cache_delete</function>
912 and even worse, add another object, re-using the same address.
913     </para>
914     <para>
915 As there is only one lock, you can't hold it forever: no-one else would
916 get any work done.
917     </para>
918     <para>
919 The solution to this problem is to use a reference count: everyone who
920 has a pointer to the object increases it when they first get the
921 object, and drops the reference count when they're finished with it.
922 Whoever drops it to zero knows it is unused, and can actually delete it.
923     </para>
924     <para>
925 Here is the code:
926     </para>
927
928 <programlisting>
929 --- cache.c.interrupt   2003-12-09 14:25:43.000000000 +1100
930 +++ cache.c.refcnt      2003-12-09 14:33:05.000000000 +1100
931 @@ -7,6 +7,7 @@
932  struct object
933  {
934          struct list_head list;
935 +        unsigned int refcnt;
936          int id;
937          char name[32];
938          int popularity;
939 @@ -17,6 +18,35 @@
940  static unsigned int cache_num = 0;
941  #define MAX_CACHE_SIZE 10
942
943 +static void __object_put(struct object *obj)
944 +{
945 +        if (--obj-&gt;refcnt == 0)
946 +                kfree(obj);
947 +}
948 +
949 +static void __object_get(struct object *obj)
950 +{
951 +        obj-&gt;refcnt++;
952 +}
953 +
954 +void object_put(struct object *obj)
955 +{
956 +        unsigned long flags;
957 +
958 +        spin_lock_irqsave(&amp;cache_lock, flags);
959 +        __object_put(obj);
960 +        spin_unlock_irqrestore(&amp;cache_lock, flags);
961 +}
962 +
963 +void object_get(struct object *obj)
964 +{
965 +        unsigned long flags;
966 +
967 +        spin_lock_irqsave(&amp;cache_lock, flags);
968 +        __object_get(obj);
969 +        spin_unlock_irqrestore(&amp;cache_lock, flags);
970 +}
971 +
972  /* Must be holding cache_lock */
973  static struct object *__cache_find(int id)
974  {
975 @@ -35,6 +65,7 @@
976  {
977          BUG_ON(!obj);
978          list_del(&amp;obj-&gt;list);
979 +        __object_put(obj);
980          cache_num--;
981  }
982
983 @@ -63,6 +94,7 @@
984          strlcpy(obj-&gt;name, name, sizeof(obj-&gt;name));
985          obj-&gt;id = id;
986          obj-&gt;popularity = 0;
987 +        obj-&gt;refcnt = 1; /* The cache holds a reference */
988
989          spin_lock_irqsave(&amp;cache_lock, flags);
990          __cache_add(obj);
991 @@ -79,18 +111,15 @@
992          spin_unlock_irqrestore(&amp;cache_lock, flags);
993  }
994
995 -int cache_find(int id, char *name)
996 +struct object *cache_find(int id)
997  {
998          struct object *obj;
999 -        int ret = -ENOENT;
1000          unsigned long flags;
1001
1002          spin_lock_irqsave(&amp;cache_lock, flags);
1003          obj = __cache_find(id);
1004 -        if (obj) {
1005 -                ret = 0;
1006 -                strcpy(name, obj-&gt;name);
1007 -        }
1008 +        if (obj)
1009 +                __object_get(obj);
1010          spin_unlock_irqrestore(&amp;cache_lock, flags);
1011 -        return ret;
1012 +        return obj;
1013  }
1014 </programlisting>
1015
1016 <para>
1017 We encapsulate the reference counting in the standard 'get' and 'put'
1018 functions.  Now we can return the object itself from
1019 <function>cache_find</function> which has the advantage that the user
1020 can now sleep holding the object (eg. to
1021 <function>copy_to_user</function> to name to userspace).
1022 </para>
1023 <para>
1024 The other point to note is that I said a reference should be held for
1025 every pointer to the object: thus the reference count is 1 when first
1026 inserted into the cache.  In some versions the framework does not hold
1027 a reference count, but they are more complicated.
1028 </para>
1029
1030    <sect2 id="examples-refcnt-atomic">
1031     <title>Using Atomic Operations For The Reference Count</title>
1032 <para>
1033 In practice, <type>atomic_t</type> would usually be used for
1034 <structfield>refcnt</structfield>.  There are a number of atomic
1035 operations defined in
1036
1037 <filename class="headerfile">include/asm/atomic.h</filename>: these are
1038 guaranteed to be seen atomically from all CPUs in the system, so no
1039 lock is required.  In this case, it is simpler than using spinlocks,
1040 although for anything non-trivial using spinlocks is clearer.  The
1041 <function>atomic_inc</function> and
1042 <function>atomic_dec_and_test</function> are used instead of the
1043 standard increment and decrement operators, and the lock is no longer
1044 used to protect the reference count itself.
1045 </para>
1046
1047 <programlisting>
1048 --- cache.c.refcnt      2003-12-09 15:00:35.000000000 +1100
1049 +++ cache.c.refcnt-atomic       2003-12-11 15:49:42.000000000 +1100
1050 @@ -7,7 +7,7 @@
1051  struct object
1052  {
1053          struct list_head list;
1054 -        unsigned int refcnt;
1055 +        atomic_t refcnt;
1056          int id;
1057          char name[32];
1058          int popularity;
1059 @@ -18,33 +18,15 @@
1060  static unsigned int cache_num = 0;
1061  #define MAX_CACHE_SIZE 10
1062
1063 -static void __object_put(struct object *obj)
1064 -{
1065 -        if (--obj-&gt;refcnt == 0)
1066 -                kfree(obj);
1067 -}
1068 -
1069 -static void __object_get(struct object *obj)
1070 -{
1071 -        obj-&gt;refcnt++;
1072 -}
1073 -
1074  void object_put(struct object *obj)
1075  {
1076 -        unsigned long flags;
1077 -
1078 -        spin_lock_irqsave(&amp;cache_lock, flags);
1079 -        __object_put(obj);
1080 -        spin_unlock_irqrestore(&amp;cache_lock, flags);
1081 +        if (atomic_dec_and_test(&amp;obj-&gt;refcnt))
1082 +                kfree(obj);
1083  }
1084
1085  void object_get(struct object *obj)
1086  {
1087 -        unsigned long flags;
1088 -
1089 -        spin_lock_irqsave(&amp;cache_lock, flags);
1090 -        __object_get(obj);
1091 -        spin_unlock_irqrestore(&amp;cache_lock, flags);
1092 +        atomic_inc(&amp;obj-&gt;refcnt);
1093  }
1094
1095  /* Must be holding cache_lock */
1096 @@ -65,7 +47,7 @@
1097  {
1098          BUG_ON(!obj);
1099          list_del(&amp;obj-&gt;list);
1100 -        __object_put(obj);
1101 +        object_put(obj);
1102          cache_num--;
1103  }
1104
1105 @@ -94,7 +76,7 @@
1106          strlcpy(obj-&gt;name, name, sizeof(obj-&gt;name));
1107          obj-&gt;id = id;
1108          obj-&gt;popularity = 0;
1109 -        obj-&gt;refcnt = 1; /* The cache holds a reference */
1110 +        atomic_set(&amp;obj-&gt;refcnt, 1); /* The cache holds a reference */
1111
1112          spin_lock_irqsave(&amp;cache_lock, flags);
1113          __cache_add(obj);
1114 @@ -119,7 +101,7 @@
1115          spin_lock_irqsave(&amp;cache_lock, flags);
1116          obj = __cache_find(id);
1117          if (obj)
1118 -                __object_get(obj);
1119 +                object_get(obj);
1120          spin_unlock_irqrestore(&amp;cache_lock, flags);
1121          return obj;
1122  }
1123 </programlisting>
1124 </sect2>
1125 </sect1>
1126
1127    <sect1 id="examples-lock-per-obj">
1128     <title>Protecting The Objects Themselves</title>
1129     <para>
1130 In these examples, we assumed that the objects (except the reference
1131 counts) never changed once they are created.  If we wanted to allow
1132 the name to change, there are three possibilities:
1133     </para>
1134     <itemizedlist>
1135       <listitem>
1136         <para>
1137 You can make <symbol>cache_lock</symbol> non-static, and tell people
1138 to grab that lock before changing the name in any object.
1139         </para>
1140       </listitem>
1141       <listitem>
1142         <para>
1143 You can provide a <function>cache_obj_rename</function> which grabs
1144 this lock and changes the name for the caller, and tell everyone to
1145 use that function.
1146         </para>
1147       </listitem>
1148       <listitem>
1149         <para>
1150 You can make the <symbol>cache_lock</symbol> protect only the cache
1151 itself, and use another lock to protect the name.
1152         </para>
1153       </listitem>
1154     </itemizedlist>
1155
1156       <para>
1157 Theoretically, you can make the locks as fine-grained as one lock for
1158 every field, for every object.  In practice, the most common variants
1159 are:
1160 </para>
1161     <itemizedlist>
1162       <listitem>
1163         <para>
1164 One lock which protects the infrastructure (the <symbol>cache</symbol>
1165 list in this example) and all the objects.  This is what we have done
1166 so far.
1167         </para>
1168       </listitem>
1169       <listitem>
1170         <para>
1171 One lock which protects the infrastructure (including the list
1172 pointers inside the objects), and one lock inside the object which
1173 protects the rest of that object.
1174         </para>
1175       </listitem>
1176       <listitem>
1177         <para>
1178 Multiple locks to protect the infrastructure (eg. one lock per hash
1179 chain), possibly with a separate per-object lock.
1180         </para>
1181       </listitem>
1182     </itemizedlist>
1183
1184 <para>
1185 Here is the "lock-per-object" implementation:
1186 </para>
1187 <programlisting>
1188 --- cache.c.refcnt-atomic       2003-12-11 15:50:54.000000000 +1100
1189 +++ cache.c.perobjectlock       2003-12-11 17:15:03.000000000 +1100
1190 @@ -6,11 +6,17 @@
1191
1192  struct object
1193  {
1194 +        /* These two protected by cache_lock. */
1195          struct list_head list;
1196 +        int popularity;
1197 +
1198          atomic_t refcnt;
1199 +
1200 +        /* Doesn't change once created. */
1201          int id;
1202 +
1203 +        spinlock_t lock; /* Protects the name */
1204          char name[32];
1205 -        int popularity;
1206  };
1207
1208  static spinlock_t cache_lock = SPIN_LOCK_UNLOCKED;
1209 @@ -77,6 +84,7 @@
1210          obj-&gt;id = id;
1211          obj-&gt;popularity = 0;
1212          atomic_set(&amp;obj-&gt;refcnt, 1); /* The cache holds a reference */
1213 +        spin_lock_init(&amp;obj-&gt;lock);
1214
1215          spin_lock_irqsave(&amp;cache_lock, flags);
1216          __cache_add(obj);
1217 </programlisting>
1218
1219 <para>
1220 Note that I decide that the <structfield>popularity</structfield>
1221 count should be protected by the <symbol>cache_lock</symbol> rather
1222 than the per-object lock: this is because it (like the
1223 <structname>struct list_head</structname> inside the object) is
1224 logically part of the infrastructure.  This way, I don't need to grab
1225 the lock of every object in <function>__cache_add</function> when
1226 seeking the least popular.
1227 </para>
1228
1229 <para>
1230 I also decided that the <structfield>id</structfield> member is
1231 unchangeable, so I don't need to grab each object lock in
1232 <function>__cache_find()</function> to examine the
1233 <structfield>id</structfield>: the object lock is only used by a
1234 caller who wants to read or write the <structfield>name</structfield>
1235 field.
1236 </para>
1237
1238 <para>
1239 Note also that I added a comment describing what data was protected by
1240 which locks.  This is extremely important, as it describes the runtime
1241 behavior of the code, and can be hard to gain from just reading.  And
1242 as Alan Cox says, <quote>Lock data, not code</quote>.
1243 </para>
1244 </sect1>
1245 </chapter>
1246
1247    <chapter id="common-problems">
1248     <title>Common Problems</title>
1249     <sect1 id="deadlock">
1250     <title>Deadlock: Simple and Advanced</title>
1251
1252     <para>
1253       There is a coding bug where a piece of code tries to grab a
1254       spinlock twice: it will spin forever, waiting for the lock to
1255       be released (spinlocks, rwlocks and semaphores are not
1256       recursive in Linux).  This is trivial to diagnose: not a
1257       stay-up-five-nights-talk-to-fluffy-code-bunnies kind of
1258       problem.
1259     </para>
1260
1261     <para>
1262       For a slightly more complex case, imagine you have a region
1263       shared by a softirq and user context.  If you use a
1264       <function>spin_lock()</function> call to protect it, it is 
1265       possible that the user context will be interrupted by the softirq
1266       while it holds the lock, and the softirq will then spin
1267       forever trying to get the same lock.
1268     </para>
1269
1270     <para>
1271       Both of these are called deadlock, and as shown above, it can
1272       occur even with a single CPU (although not on UP compiles,
1273       since spinlocks vanish on kernel compiles with 
1274       <symbol>CONFIG_SMP</symbol>=n. You'll still get data corruption 
1275       in the second example).
1276     </para>
1277
1278     <para>
1279       This complete lockup is easy to diagnose: on SMP boxes the
1280       watchdog timer or compiling with <symbol>DEBUG_SPINLOCKS</symbol> set
1281       (<filename>include/linux/spinlock.h</filename>) will show this up 
1282       immediately when it happens.
1283     </para>
1284
1285     <para>
1286       A more complex problem is the so-called 'deadly embrace',
1287       involving two or more locks.  Say you have a hash table: each
1288       entry in the table is a spinlock, and a chain of hashed
1289       objects.  Inside a softirq handler, you sometimes want to
1290       alter an object from one place in the hash to another: you
1291       grab the spinlock of the old hash chain and the spinlock of
1292       the new hash chain, and delete the object from the old one,
1293       and insert it in the new one.
1294     </para>
1295
1296     <para>
1297       There are two problems here.  First, if your code ever
1298       tries to move the object to the same chain, it will deadlock
1299       with itself as it tries to lock it twice.  Secondly, if the
1300       same softirq on another CPU is trying to move another object
1301       in the reverse direction, the following could happen:
1302     </para>
1303
1304     <table>
1305      <title>Consequences</title>
1306
1307      <tgroup cols="2" align="left">
1308
1309       <thead>
1310        <row>
1311         <entry>CPU 1</entry>
1312         <entry>CPU 2</entry>
1313        </row>
1314       </thead>
1315
1316       <tbody>
1317        <row>
1318         <entry>Grab lock A -&gt; OK</entry>
1319         <entry>Grab lock B -&gt; OK</entry>
1320        </row>
1321        <row>
1322         <entry>Grab lock B -&gt; spin</entry>
1323         <entry>Grab lock A -&gt; spin</entry>
1324        </row>
1325       </tbody>
1326      </tgroup>
1327     </table>
1328
1329     <para>
1330       The two CPUs will spin forever, waiting for the other to give up
1331       their lock.  It will look, smell, and feel like a crash.
1332     </para>
1333     </sect1>
1334
1335     <sect1 id="techs-deadlock-prevent">
1336      <title>Preventing Deadlock</title>
1337
1338      <para>
1339        Textbooks will tell you that if you always lock in the same
1340        order, you will never get this kind of deadlock.  Practice
1341        will tell you that this approach doesn't scale: when I
1342        create a new lock, I don't understand enough of the kernel
1343        to figure out where in the 5000 lock hierarchy it will fit.
1344      </para>
1345
1346      <para>
1347        The best locks are encapsulated: they never get exposed in
1348        headers, and are never held around calls to non-trivial
1349        functions outside the same file.  You can read through this
1350        code and see that it will never deadlock, because it never
1351        tries to grab another lock while it has that one.  People
1352        using your code don't even need to know you are using a
1353        lock.
1354      </para>
1355
1356      <para>
1357        A classic problem here is when you provide callbacks or
1358        hooks: if you call these with the lock held, you risk simple
1359        deadlock, or a deadly embrace (who knows what the callback
1360        will do?).  Remember, the other programmers are out to get
1361        you, so don't do this.
1362      </para>
1363
1364     <sect2 id="techs-deadlock-overprevent">
1365      <title>Overzealous Prevention Of Deadlocks</title>
1366
1367      <para>
1368        Deadlocks are problematic, but not as bad as data
1369        corruption.  Code which grabs a read lock, searches a list,
1370        fails to find what it wants, drops the read lock, grabs a
1371        write lock and inserts the object has a race condition.
1372      </para>
1373
1374      <para>
1375        If you don't see why, please stay the fuck away from my code.
1376      </para>
1377     </sect2>
1378     </sect1>
1379
1380    <sect1 id="racing-timers">
1381     <title>Racing Timers: A Kernel Pastime</title>
1382
1383     <para>
1384       Timers can produce their own special problems with races.
1385       Consider a collection of objects (list, hash, etc) where each
1386       object has a timer which is due to destroy it.
1387     </para>
1388
1389     <para>
1390       If you want to destroy the entire collection (say on module
1391       removal), you might do the following:
1392     </para>
1393
1394     <programlisting>
1395         /* THIS CODE BAD BAD BAD BAD: IF IT WAS ANY WORSE IT WOULD USE
1396            HUNGARIAN NOTATION */
1397         spin_lock_bh(&amp;list_lock);
1398
1399         while (list) {
1400                 struct foo *next = list-&gt;next;
1401                 del_timer(&amp;list-&gt;timer);
1402                 kfree(list);
1403                 list = next;
1404         }
1405
1406         spin_unlock_bh(&amp;list_lock);
1407     </programlisting>
1408
1409     <para>
1410       Sooner or later, this will crash on SMP, because a timer can
1411       have just gone off before the <function>spin_lock_bh()</function>,
1412       and it will only get the lock after we
1413       <function>spin_unlock_bh()</function>, and then try to free
1414       the element (which has already been freed!).
1415     </para>
1416
1417     <para>
1418       This can be avoided by checking the result of
1419       <function>del_timer()</function>: if it returns
1420       <returnvalue>1</returnvalue>, the timer has been deleted.
1421       If <returnvalue>0</returnvalue>, it means (in this
1422       case) that it is currently running, so we can do:
1423     </para>
1424
1425     <programlisting>
1426         retry:
1427                 spin_lock_bh(&amp;list_lock);
1428
1429                 while (list) {
1430                         struct foo *next = list-&gt;next;
1431                         if (!del_timer(&amp;list-&gt;timer)) {
1432                                 /* Give timer a chance to delete this */
1433                                 spin_unlock_bh(&amp;list_lock);
1434                                 goto retry;
1435                         }
1436                         kfree(list);
1437                         list = next;
1438                 }
1439
1440                 spin_unlock_bh(&amp;list_lock);
1441     </programlisting>
1442
1443     <para>
1444       Another common problem is deleting timers which restart
1445       themselves (by calling <function>add_timer()</function> at the end
1446       of their timer function).  Because this is a fairly common case
1447       which is prone to races, you should use <function>del_timer_sync()</function>
1448       (<filename class="headerfile">include/linux/timer.h</filename>)
1449       to handle this case.  It returns the number of times the timer
1450       had to be deleted before we finally stopped it from adding itself back
1451       in.
1452     </para>
1453    </sect1>
1454
1455   </chapter>
1456
1457  <chapter id="Efficiency">
1458     <title>Locking Speed</title>
1459
1460     <para>
1461 There are three main things to worry about when considering speed of
1462 some code which does locking.  First is concurrency: how many things
1463 are going to be waiting while someone else is holding a lock.  Second
1464 is the time taken to actually acquire and release an uncontended lock.
1465 Third is using fewer, or smarter locks.  I'm assuming that the lock is
1466 used fairly often: otherwise, you wouldn't be concerned about
1467 efficiency.
1468 </para>
1469     <para>
1470 Concurrency depends on how long the lock is usually held: you should
1471 hold the lock for as long as needed, but no longer.  In the cache
1472 example, we always create the object without the lock held, and then
1473 grab the lock only when we are ready to insert it in the list.
1474 </para>
1475     <para>
1476 Acquisition times depend on how much damage the lock operations do to
1477 the pipeline (pipeline stalls) and how likely it is that this CPU was
1478 the last one to grab the lock (ie. is the lock cache-hot for this
1479 CPU): on a machine with more CPUs, this likelihood drops fast.
1480 Consider a 700MHz Intel Pentium III: an instruction takes about 0.7ns,
1481 an atomic increment takes about 58ns, a lock which is cache-hot on
1482 this CPU takes 160ns, and a cacheline transfer from another CPU takes
1483 an additional 170 to 360ns.  (These figures from Paul McKenney's
1484 <ulink url="http://www.linuxjournal.com/article.php?sid=6993"> Linux
1485 Journal RCU article</ulink>).
1486 </para>
1487     <para>
1488 These two aims conflict: holding a lock for a short time might be done
1489 by splitting locks into parts (such as in our final per-object-lock
1490 example), but this increases the number of lock acquisitions, and the
1491 results are often slower than having a single lock.  This is another
1492 reason to advocate locking simplicity.
1493 </para>
1494     <para>
1495 The third concern is addressed below: there are some methods to reduce
1496 the amount of locking which needs to be done.
1497 </para>
1498
1499   <sect1 id="efficiency-rwlocks">
1500    <title>Read/Write Lock Variants</title>
1501
1502    <para>
1503       Both spinlocks and semaphores have read/write variants:
1504       <type>rwlock_t</type> and <structname>struct rw_semaphore</structname>.
1505       These divide users into two classes: the readers and the writers.  If
1506       you are only reading the data, you can get a read lock, but to write to
1507       the data you need the write lock.  Many people can hold a read lock,
1508       but a writer must be sole holder.
1509     </para>
1510
1511    <para>
1512       If your code divides neatly along reader/writer lines (as our
1513       cache code does), and the lock is held by readers for
1514       significant lengths of time, using these locks can help.  They
1515       are slightly slower than the normal locks though, so in practice
1516       <type>rwlock_t</type> is not usually worthwhile.
1517     </para>
1518    </sect1>
1519
1520    <sect1 id="efficiency-read-copy-update">
1521     <title>Avoiding Locks: Read Copy Update</title>
1522
1523     <para>
1524       There is a special method of read/write locking called Read Copy
1525       Update.  Using RCU, the readers can avoid taking a lock
1526       altogether: as we expect our cache to be read more often than
1527       updated (otherwise the cache is a waste of time), it is a
1528       candidate for this optimization.
1529     </para>
1530
1531     <para>
1532       How do we get rid of read locks?  Getting rid of read locks
1533       means that writers may be changing the list underneath the
1534       readers.  That is actually quite simple: we can read a linked
1535       list while an element is being added if the writer adds the
1536       element very carefully.  For example, adding
1537       <symbol>new</symbol> to a single linked list called
1538       <symbol>list</symbol>:
1539     </para>
1540
1541     <programlisting>
1542         new-&gt;next = list-&gt;next;
1543         wmb();
1544         list-&gt;next = new;
1545     </programlisting>
1546
1547     <para>
1548       The <function>wmb()</function> is a write memory barrier.  It
1549       ensures that the first operation (setting the new element's
1550       <symbol>next</symbol> pointer) is complete and will be seen by
1551       all CPUs, before the second operation is (putting the new
1552       element into the list).  This is important, since modern
1553       compilers and modern CPUs can both reorder instructions unless
1554       told otherwise: we want a reader to either not see the new
1555       element at all, or see the new element with the
1556       <symbol>next</symbol> pointer correctly pointing at the rest of
1557       the list.
1558     </para>
1559     <para>
1560       Fortunately, there is a function to do this for standard
1561       <structname>struct list_head</structname> lists:
1562       <function>list_add_rcu()</function>
1563       (<filename>include/linux/list.h</filename>).
1564     </para>
1565     <para>
1566       Removing an element from the list is even simpler: we replace
1567       the pointer to the old element with a pointer to its successor,
1568       and readers will either see it, or skip over it.
1569     </para>
1570     <programlisting>
1571         list-&gt;next = old-&gt;next;
1572     </programlisting>
1573     <para>
1574       There is <function>list_del_rcu()</function>
1575       (<filename>include/linux/list.h</filename>) which does this (the
1576       normal version poisons the old object, which we don't want).
1577     </para>
1578     <para>
1579       The reader must also be careful: some CPUs can look through the
1580       <symbol>next</symbol> pointer to start reading the contents of
1581       the next element early, but don't realize that the pre-fetched
1582       contents is wrong when the <symbol>next</symbol> pointer changes
1583       underneath them.  Once again, there is a
1584       <function>list_for_each_entry_rcu()</function>
1585       (<filename>include/linux/list.h</filename>) to help you.  Of
1586       course, writers can just use
1587       <function>list_for_each_entry()</function>, since there cannot
1588       be two simultaneous writers.
1589     </para>
1590     <para>
1591       Our final dilemma is this: when can we actually destroy the
1592       removed element?  Remember, a reader might be stepping through
1593       this element in the list right now: if we free this element and
1594       the <symbol>next</symbol> pointer changes, the reader will jump
1595       off into garbage and crash.  We need to wait until we know that
1596       all the readers who were traversing the list when we deleted the
1597       element are finished.  We use <function>call_rcu()</function> to
1598       register a callback which will actually destroy the object once
1599       the readers are finished.
1600     </para>
1601     <para>
1602       But how does Read Copy Update know when the readers are
1603       finished?  The method is this: firstly, the readers always
1604       traverse the list inside
1605       <function>rcu_read_lock()</function>/<function>rcu_read_unlock()</function>
1606       pairs: these simply disable preemption so the reader won't go to
1607       sleep while reading the list.
1608     </para>
1609     <para>
1610       RCU then waits until every other CPU has slept at least once:
1611       since readers cannot sleep, we know that any readers which were
1612       traversing the list during the deletion are finished, and the
1613       callback is triggered.  The real Read Copy Update code is a
1614       little more optimized than this, but this is the fundamental
1615       idea.
1616     </para>
1617
1618 <programlisting>
1619 --- cache.c.perobjectlock       2003-12-11 17:15:03.000000000 +1100
1620 +++ cache.c.rcupdate    2003-12-11 17:55:14.000000000 +1100
1621 @@ -1,15 +1,18 @@
1622  #include &lt;linux/list.h&gt;
1623  #include &lt;linux/slab.h&gt;
1624  #include &lt;linux/string.h&gt;
1625 +#include &lt;linux/rcupdate.h&gt;
1626  #include &lt;asm/semaphore.h&gt;
1627  #include &lt;asm/errno.h&gt;
1628
1629  struct object
1630  {
1631 -        /* These two protected by cache_lock. */
1632 +        /* This is protected by RCU */
1633          struct list_head list;
1634          int popularity;
1635
1636 +        struct rcu_head rcu;
1637 +
1638          atomic_t refcnt;
1639
1640          /* Doesn't change once created. */
1641 @@ -40,7 +43,7 @@
1642  {
1643          struct object *i;
1644
1645 -        list_for_each_entry(i, &amp;cache, list) {
1646 +        list_for_each_entry_rcu(i, &amp;cache, list) {
1647                  if (i-&gt;id == id) {
1648                          i-&gt;popularity++;
1649                          return i;
1650 @@ -49,19 +52,25 @@
1651          return NULL;
1652  }
1653
1654 +/* Final discard done once we know no readers are looking. */
1655 +static void cache_delete_rcu(void *arg)
1656 +{
1657 +        object_put(arg);
1658 +}
1659 +
1660  /* Must be holding cache_lock */
1661  static void __cache_delete(struct object *obj)
1662  {
1663          BUG_ON(!obj);
1664 -        list_del(&amp;obj-&gt;list);
1665 -        object_put(obj);
1666 +        list_del_rcu(&amp;obj-&gt;list);
1667          cache_num--;
1668 +        call_rcu(&amp;obj-&gt;rcu, cache_delete_rcu, obj);
1669  }
1670
1671  /* Must be holding cache_lock */
1672  static void __cache_add(struct object *obj)
1673  {
1674 -        list_add(&amp;obj-&gt;list, &amp;cache);
1675 +        list_add_rcu(&amp;obj-&gt;list, &amp;cache);
1676          if (++cache_num > MAX_CACHE_SIZE) {
1677                  struct object *i, *outcast = NULL;
1678                  list_for_each_entry(i, &amp;cache, list) {
1679 @@ -85,6 +94,7 @@
1680          obj-&gt;popularity = 0;
1681          atomic_set(&amp;obj-&gt;refcnt, 1); /* The cache holds a reference */
1682          spin_lock_init(&amp;obj-&gt;lock);
1683 +        INIT_RCU_HEAD(&amp;obj-&gt;rcu);
1684
1685          spin_lock_irqsave(&amp;cache_lock, flags);
1686          __cache_add(obj);
1687 @@ -104,12 +114,11 @@
1688  struct object *cache_find(int id)
1689  {
1690          struct object *obj;
1691 -        unsigned long flags;
1692
1693 -        spin_lock_irqsave(&amp;cache_lock, flags);
1694 +        rcu_read_lock();
1695          obj = __cache_find(id);
1696          if (obj)
1697                  object_get(obj);
1698 -        spin_unlock_irqrestore(&amp;cache_lock, flags);
1699 +        rcu_read_unlock();
1700          return obj;
1701  }
1702 </programlisting>
1703
1704 <para>
1705 Note that the reader will alter the
1706 <structfield>popularity</structfield> member in
1707 <function>__cache_find()</function>, and now it doesn't hold a lock.
1708 One solution would be to make it an <type>atomic_t</type>, but for
1709 this usage, we don't really care about races: an approximate result is
1710 good enough, so I didn't change it.
1711 </para>
1712
1713 <para>
1714 The result is that <function>cache_find()</function> requires no
1715 synchronization with any other functions, so is almost as fast on SMP
1716 as it would be on UP.
1717 </para>
1718
1719 <para>
1720 There is a furthur optimization possible here: remember our original
1721 cache code, where there were no reference counts and the caller simply
1722 held the lock whenever using the object?  This is still possible: if
1723 you hold the lock, noone can delete the object, so you don't need to
1724 get and put the reference count.
1725 </para>
1726
1727 <para>
1728 Now, because the 'read lock' in RCU is simply disabling preemption, a
1729 caller which always has preemption disabled between calling
1730 <function>cache_find()</function> and
1731 <function>object_put()</function> does not need to actually get and
1732 put the reference count: we could expose
1733 <function>__cache_find()</function> by making it non-static, and
1734 such callers could simply call that.
1735 </para>
1736 <para>
1737 The benefit here is that the reference count is not written to: the
1738 object is not altered in any way, which is much faster on SMP
1739 machines due to caching.
1740 </para>
1741   </sect1>
1742
1743    <sect1 id="per-cpu">
1744     <title>Per-CPU Data</title>
1745
1746     <para>
1747       Another technique for avoiding locking which is used fairly
1748       widely is to duplicate information for each CPU.  For example,
1749       if you wanted to keep a count of a common condition, you could
1750       use a spin lock and a single counter.  Nice and simple.
1751     </para>
1752
1753     <para>
1754       If that was too slow (it's usually not, but if you've got a
1755       really big machine to test on and can show that it is), you
1756       could instead use a counter for each CPU, then none of them need
1757       an exclusive lock.  See <function>DEFINE_PER_CPU()</function>,
1758       <function>get_cpu_var()</function> and
1759       <function>put_cpu_var()</function>
1760       (<filename class="headerfile">include/linux/percpu.h</filename>).
1761     </para>
1762
1763     <para>
1764       Of particular use for simple per-cpu counters is the
1765       <type>local_t</type> type, and the
1766       <function>cpu_local_inc()</function> and related functions,
1767       which are more efficient than simple code on some architectures
1768       (<filename class="headerfile">include/asm/local.h</filename>).
1769     </para>
1770
1771     <para>
1772       Note that there is no simple, reliable way of getting an exact
1773       value of such a counter, without introducing more locks.  This
1774       is not a problem for some uses.
1775     </para>
1776    </sect1>
1777
1778    <sect1 id="mostly-hardirq">
1779     <title>Data Which Mostly Used By An IRQ Handler</title>
1780
1781     <para>
1782       If data is always accessed from within the same IRQ handler, you
1783       don't need a lock at all: the kernel already guarantees that the
1784       irq handler will not run simultaneously on multiple CPUs.
1785     </para>
1786     <para>
1787       Manfred Spraul points out that you can still do this, even if
1788       the data is very occasionally accessed in user context or
1789       softirqs/tasklets.  The irq handler doesn't use a lock, and
1790       all other accesses are done as so:
1791     </para>
1792
1793 <programlisting>
1794         spin_lock(&amp;lock);
1795         disable_irq(irq);
1796         ...
1797         enable_irq(irq);
1798         spin_unlock(&amp;lock);
1799 </programlisting>
1800     <para>
1801       The <function>disable_irq()</function> prevents the irq handler
1802       from running (and waits for it to finish if it's currently
1803       running on other CPUs).  The spinlock prevents any other
1804       accesses happening at the same time.  Naturally, this is slower
1805       than just a <function>spin_lock_irq()</function> call, so it
1806       only makes sense if this type of access happens extremely
1807       rarely.
1808     </para>
1809    </sect1>
1810   </chapter>
1811
1812  <chapter id="sleeping-things">
1813     <title>What Functions Are Safe To Call From Interrupts?</title>
1814
1815     <para>
1816       Many functions in the kernel sleep (ie. call schedule())
1817       directly or indirectly: you can never call them while holding a
1818       spinlock, or with preemption disabled.  This also means you need
1819       to be in user context: calling them from an interrupt is illegal.
1820     </para>
1821
1822    <sect1 id="sleeping">
1823     <title>Some Functions Which Sleep</title>
1824
1825     <para>
1826       The most common ones are listed below, but you usually have to
1827       read the code to find out if other calls are safe.  If everyone
1828       else who calls it can sleep, you probably need to be able to
1829       sleep, too.  In particular, registration and deregistration
1830       functions usually expect to be called from user context, and can
1831       sleep.
1832     </para>
1833
1834     <itemizedlist>
1835      <listitem>
1836       <para>
1837         Accesses to 
1838         <firstterm linkend="gloss-userspace">userspace</firstterm>:
1839       </para>
1840       <itemizedlist>
1841        <listitem>
1842         <para>
1843           <function>copy_from_user()</function>
1844         </para>
1845        </listitem>
1846        <listitem>
1847         <para>
1848           <function>copy_to_user()</function>
1849         </para>
1850        </listitem>
1851        <listitem>
1852         <para>
1853           <function>get_user()</function>
1854         </para>
1855        </listitem>
1856        <listitem>
1857         <para>
1858           <function> put_user()</function>
1859         </para>
1860        </listitem>
1861       </itemizedlist>
1862      </listitem>
1863
1864      <listitem>
1865       <para>
1866         <function>kmalloc(GFP_KERNEL)</function>
1867       </para>
1868      </listitem>
1869
1870      <listitem>
1871       <para>
1872       <function>down_interruptible()</function> and
1873       <function>down()</function>
1874       </para>
1875       <para>
1876        There is a <function>down_trylock()</function> which can be
1877        used inside interrupt context, as it will not sleep.
1878        <function>up()</function> will also never sleep.
1879       </para>
1880      </listitem>
1881     </itemizedlist>
1882    </sect1>
1883
1884    <sect1 id="dont-sleep">
1885     <title>Some Functions Which Don't Sleep</title>
1886
1887     <para>
1888      Some functions are safe to call from any context, or holding
1889      almost any lock.
1890     </para>
1891
1892     <itemizedlist>
1893      <listitem>
1894       <para>
1895         <function>printk()</function>
1896       </para>
1897      </listitem>
1898      <listitem>
1899       <para>
1900         <function>kfree()</function>
1901       </para>
1902      </listitem>
1903      <listitem>
1904       <para>
1905         <function>add_timer()</function> and <function>del_timer()</function>
1906       </para>
1907      </listitem>
1908     </itemizedlist>
1909    </sect1>
1910   </chapter>
1911
1912   <chapter id="references">
1913    <title>Further reading</title>
1914
1915    <itemizedlist>
1916     <listitem>
1917      <para>
1918        <filename>Documentation/spinlocks.txt</filename>: 
1919        Linus Torvalds' spinlocking tutorial in the kernel sources.
1920      </para>
1921     </listitem>
1922
1923     <listitem>
1924      <para>
1925        Unix Systems for Modern Architectures: Symmetric
1926        Multiprocessing and Caching for Kernel Programmers:
1927      </para>
1928
1929      <para>
1930        Curt Schimmel's very good introduction to kernel level
1931        locking (not written for Linux, but nearly everything
1932        applies).  The book is expensive, but really worth every
1933        penny to understand SMP locking. [ISBN: 0201633388]
1934      </para>
1935     </listitem>
1936    </itemizedlist>
1937   </chapter>
1938
1939   <chapter id="thanks">
1940     <title>Thanks</title>
1941
1942     <para>
1943       Thanks to Telsa Gwynne for DocBooking, neatening and adding
1944       style.
1945     </para>
1946
1947     <para>
1948       Thanks to Martin Pool, Philipp Rumpf, Stephen Rothwell, Paul
1949       Mackerras, Ruedi Aschwanden, Alan Cox, Manfred Spraul, Tim
1950       Waugh, Pete Zaitcev, James Morris, Robert Love, Paul McKenney,
1951       John Ashby for proofreading, correcting, flaming, commenting.
1952     </para>
1953
1954     <para>
1955       Thanks to the cabal for having no influence on this document.
1956     </para>
1957   </chapter>
1958
1959   <glossary id="glossary">
1960    <title>Glossary</title>
1961
1962    <glossentry id="gloss-preemption">
1963     <glossterm>preemption</glossterm>
1964      <glossdef>
1965       <para>
1966         Prior to 2.5, or when <symbol>CONFIG_PREEMPT</symbol> is
1967         unset, processes in user context inside the kernel would not
1968         preempt each other (ie. you had that CPU until you have it up,
1969         except for interrupts).  With the addition of
1970         <symbol>CONFIG_PREEMPT</symbol> in 2.5.4, this changed: when
1971         in user context, higher priority tasks can "cut in": spinlocks
1972         were changed to disable preemption, even on UP.
1973      </para>
1974     </glossdef>
1975    </glossentry>
1976
1977    <glossentry id="gloss-bh">
1978     <glossterm>bh</glossterm>
1979      <glossdef>
1980       <para>
1981         Bottom Half: for historical reasons, functions with
1982         '_bh' in them often now refer to any software interrupt, e.g.
1983         <function>spin_lock_bh()</function> blocks any software interrupt 
1984         on the current CPU.  Bottom halves are deprecated, and will 
1985         eventually be replaced by tasklets.  Only one bottom half will be 
1986         running at any time.
1987      </para>
1988     </glossdef>
1989    </glossentry>
1990
1991    <glossentry id="gloss-hwinterrupt">
1992     <glossterm>Hardware Interrupt / Hardware IRQ</glossterm>
1993     <glossdef>
1994      <para>
1995        Hardware interrupt request.  <function>in_irq()</function> returns 
1996        <returnvalue>true</returnvalue> in a hardware interrupt handler.
1997      </para>
1998     </glossdef>
1999    </glossentry>
2000
2001    <glossentry id="gloss-interruptcontext">
2002     <glossterm>Interrupt Context</glossterm>
2003     <glossdef>
2004      <para>
2005        Not user context: processing a hardware irq or software irq.
2006        Indicated by the <function>in_interrupt()</function> macro 
2007        returning <returnvalue>true</returnvalue>.
2008      </para>
2009     </glossdef>
2010    </glossentry>
2011
2012    <glossentry id="gloss-smp">
2013     <glossterm><acronym>SMP</acronym></glossterm>
2014     <glossdef>
2015      <para>
2016        Symmetric Multi-Processor: kernels compiled for multiple-CPU
2017        machines.  (CONFIG_SMP=y).
2018      </para>
2019     </glossdef>
2020    </glossentry>
2021
2022    <glossentry id="gloss-softirq">
2023     <glossterm>Software Interrupt / softirq</glossterm>
2024     <glossdef>
2025      <para>
2026        Software interrupt handler.  <function>in_irq()</function> returns
2027        <returnvalue>false</returnvalue>; <function>in_softirq()</function>
2028        returns <returnvalue>true</returnvalue>.  Tasklets and softirqs
2029         both fall into the category of 'software interrupts'.
2030      </para>
2031      <para>
2032        Strictly speaking a softirq is one of up to 32 enumerated software
2033        interrupts which can run on multiple CPUs at once.
2034        Sometimes used to refer to tasklets as
2035        well (ie. all software interrupts).
2036      </para>
2037     </glossdef>
2038    </glossentry>
2039
2040    <glossentry id="gloss-tasklet">
2041     <glossterm>tasklet</glossterm>
2042     <glossdef>
2043      <para>
2044        A dynamically-registrable software interrupt,
2045        which is guaranteed to only run on one CPU at a time.
2046      </para>
2047     </glossdef>
2048    </glossentry>
2049
2050    <glossentry id="gloss-timers">
2051     <glossterm>timer</glossterm>
2052     <glossdef>
2053      <para>
2054        A dynamically-registrable software interrupt, which is run at
2055        (or close to) a given time.  When running, it is just like a
2056        tasklet (in fact, they are called from the TIMER_SOFTIRQ).
2057      </para>
2058     </glossdef>
2059    </glossentry>
2060
2061    <glossentry id="gloss-up">
2062     <glossterm><acronym>UP</acronym></glossterm>
2063     <glossdef>
2064      <para>
2065        Uni-Processor: Non-SMP.  (CONFIG_SMP=n).
2066      </para>
2067     </glossdef>
2068    </glossentry>
2069
2070    <glossentry id="gloss-usercontext">
2071     <glossterm>User Context</glossterm>
2072     <glossdef>
2073      <para>
2074        The kernel executing on behalf of a particular process (ie. a
2075        system call or trap) or kernel thread.  You can tell which
2076        process with the <symbol>current</symbol> macro.)  Not to
2077        be confused with userspace.  Can be interrupted by software or
2078        hardware interrupts.
2079      </para>
2080     </glossdef>
2081    </glossentry>
2082
2083    <glossentry id="gloss-userspace">
2084     <glossterm>Userspace</glossterm>
2085     <glossdef>
2086      <para>
2087        A process executing its own code outside the kernel.
2088      </para>
2089     </glossdef>
2090    </glossentry>      
2091
2092   </glossary>
2093 </book>
2094