.. _kernel_hacking_lock: ===========================Unreliable Guide To Locking=========================== :Author: Rusty Russell Introduction============ Welcome, to Rusty's Remarkably Unreliable Guide to Kernel Lockingissues. This document describes the locking systems in the Linux Kernelin 2.6. With the wide availability of HyperThreading, and preemption in theLinux Kernel, everyone hacking on the kernel needs to know thefundamentals of concurrency and locking for SMP. The Problem With Concurrency============================ (Skip this if you know what a Race Condition is). In a normal program, you can increment a counter like so: ::           very_important_count++;  This is what they would expect to happen:  .. table:: Expected Results   +------------------------------------+------------------------------------+  | Instance 1                         | Instance 2                         |  +====================================+====================================+  | read very_important_count (5)      |                                    |  +------------------------------------+------------------------------------+  | add 1 (6)                          |                                    |  +------------------------------------+------------------------------------+  | write very_important_count (6)     |                                    |  +------------------------------------+------------------------------------+  |                                    | read very_important_count (6)      |  +------------------------------------+------------------------------------+  |                                    | add 1 (7)                          |  +------------------------------------+------------------------------------+  |                                    | write very_important_count (7)     |  +------------------------------------+------------------------------------+ This is what might happen: .. table:: Possible Results   +------------------------------------+------------------------------------+  | Instance 1                         | Instance 2                         |  +====================================+====================================+  | read very_important_count (5)      |                                    |  +------------------------------------+------------------------------------+  |                                    | read very_important_count (5)      |  +------------------------------------+------------------------------------+  | add 1 (6)                          |                                    |  +------------------------------------+------------------------------------+  |                                    | add 1 (6)                          |  +------------------------------------+------------------------------------+  | write very_important_count (6)     |                                    |  +------------------------------------+------------------------------------+  |                                    | write very_important_count (6)     |  +------------------------------------+------------------------------------+  Race Conditions and Critical Regions------------------------------------ This overlap, where the result depends on the relative timing ofmultiple tasks, is called a race condition. The piece of code containingthe concurrency issue is called a critical region. And especially sinceLinux starting running on SMP machines, they became one of the majorissues in kernel design and implementation. Preemption can have the same effect, even if there is only one CPU: bypreempting one task during the critical region, we have exactly the samerace condition. In this case the thread which preempts might run thecritical region itself. The solution is to recognize when these simultaneous accesses occur, anduse locks to make sure that only one instance can enter the criticalregion at any time. There are many friendly primitives in the Linuxkernel to help you do this. And then there are the unfriendlyprimitives, but I'll pretend they don't exist. Locking in the Linux Kernel=========================== If I could give you one piece of advice: never sleep with anyone crazierthan yourself. But if I had to give you advice on locking: **keep itsimple**. Be reluctant to introduce new locks. Strangely enough, this last one is the exact reverse of my advice whenyou **have** slept with someone crazier than yourself. And you shouldthink about getting a big dog. Two Main Types of Kernel Locks: Spinlocks and Mutexes----------------------------------------------------- There are two main types of kernel locks. The fundamental type is thespinlock (``include/asm/spinlock.h``), which is a very simplesingle-holder lock: if you can't get the spinlock, you keep trying(spinning) until you can. Spinlocks are very small and fast, and can beused anywhere. The second type is a mutex (``include/linux/mutex.h``): it is like aspinlock, but you may block holding a mutex. If you can't lock a mutex,your task will suspend itself, and be woken up when the mutex isreleased. This means the CPU can do something else while you arewaiting. There are many cases when you simply can't sleep (see`What Functions Are Safe To Call From Interrupts? <#sleeping-things>`__),and so have to use a spinlock instead. Neither type of lock is recursive: see`Deadlock: Simple and Advanced <#deadlock>`__. Locks and Uniprocessor Kernels------------------------------ For kernels compiled without ``CONFIG_SMP``, and without``CONFIG_PREEMPT`` spinlocks do not exist at all. This is an excellentdesign decision: when no-one else can run at the same time, there is noreason to have a lock. If the kernel is compiled without ``CONFIG_SMP``, but ``CONFIG_PREEMPT``is set, then spinlocks simply disable preemption, which is sufficient toprevent any races. For most purposes, we can think of preemption asequivalent to SMP, and not worry about it separately. You should always test your locking code with ``CONFIG_SMP`` and``CONFIG_PREEMPT`` enabled, even if you don't have an SMP test box,because it will still catch some kinds of locking bugs. Mutexes still exist, because they are required for synchronizationbetween user contexts, as we will see below. Locking Only In User Context---------------------------- If you have a data structure which is only ever accessed from usercontext, then you can use a simple mutex (``include/linux/mutex.h``) toprotect it. This is the most trivial case: you initialize the mutex.Then you can call mutex_lock_interruptible() to grab themutex, and mutex_unlock() to release it. There is also amutex_lock(), which should be avoided, because it willnot return if a signal is received. Example: ``net/netfilter/nf_sockopt.c`` allows registration of newsetsockopt() and getsockopt() calls, withnf_register_sockopt(). Registration and de-registrationare only done on module load and unload (and boot time, where there isno concurrency), and the list of registrations is only consulted for anunknown setsockopt() or getsockopt() systemcall. The ``nf_sockopt_mutex`` is perfect to protect this, especiallysince the setsockopt and getsockopt calls may well sleep. Locking Between User Context and Softirqs----------------------------------------- If a softirq shares data with user context, you have two problems.Firstly, the current user context can be interrupted by a softirq, andsecondly, the critical region could be entered from another CPU. This iswhere spin_lock_bh() (``include/linux/spinlock.h``) isused. It disables softirqs on that CPU, then grabs the lock.spin_unlock_bh() does the reverse. (The '_bh' suffix isa historical reference to "Bottom Halves", the old name for softwareinterrupts. It should really be called spin_lock_softirq()' in aperfect world). Note that you can also use spin_lock_irq() orspin_lock_irqsave() here, which stop hardware interruptsas well: see `Hard IRQ Context <#hard-irq-context>`__. This works perfectly for UP as well: the spin lock vanishes, and thismacro simply becomes local_bh_disable()(``include/linux/interrupt.h``), which protects you from the softirqbeing run. Locking Between User Context and Tasklets----------------------------------------- This is exactly the same as above, because tasklets are actually runfrom a softirq. Locking Between User Context and Timers--------------------------------------- This, too, is exactly the same as above, because timers are actually runfrom a softirq. From a locking point of view, tasklets and timers areidentical. Locking Between Tasklets/Timers------------------------------- Sometimes a tasklet or timer might want to share data with anothertasklet or timer. The Same Tasklet/Timer~~~~~~~~~~~~~~~~~~~~~~ Since a tasklet is never run on two CPUs at once, you don't need toworry about your tasklet being reentrant (running twice at once), evenon SMP. Different Tasklets/Timers~~~~~~~~~~~~~~~~~~~~~~~~~ If another tasklet/timer wants to share data with your tasklet or timer, you will both need to use spin_lock() andspin_unlock() calls. spin_lock_bh() isunnecessary here, as you are already in a tasklet, and none will be runon the same CPU. Locking Between Softirqs------------------------ Often a softirq might want to share data with itself or a tasklet/timer. The Same Softirq~~~~~~~~~~~~~~~~ The same softirq can run on the other CPUs: you can use a per-CPU array(see `Per-CPU Data <#per-cpu-data>`__) for better performance. If you'regoing so far as to use a softirq, you probably care about scalableperformance enough to justify the extra complexity. You'll need to use spin_lock() andspin_unlock() for shared data. Different Softirqs~~~~~~~~~~~~~~~~~~ You'll need to use spin_lock() andspin_unlock() for shared data, whether it be a timer,tasklet, different softirq or the same or another softirq: any of themcould be running on a different CPU. Hard IRQ Context================ Hardware interrupts usually communicate with a tasklet or softirq.Frequently this involves putting work in a queue, which the softirq willtake out. Locking Between Hard IRQ and Softirqs/Tasklets---------------------------------------------- If a hardware irq handler shares data with a softirq, you have twoconcerns. Firstly, the softirq processing can be interrupted by ahardware interrupt, and secondly, the critical region could be enteredby a hardware interrupt on another CPU. This is wherespin_lock_irq() is used. It is defined to disableinterrupts on that cpu, then grab the lock.spin_unlock_irq() does the reverse. The irq handler does not need to use spin_lock_irq(), becausethe softirq cannot run while the irq handler is running: it can usespin_lock(), which is slightly faster. The only exceptionwould be if a different hardware irq handler uses the same lock:spin_lock_irq() will stop that from interrupting us. This works perfectly for UP as well: the spin lock vanishes, and thismacro simply becomes local_irq_disable()(``include/asm/smp.h``), which protects you from the softirq/tasklet/BHbeing run. spin_lock_irqsave() (``include/linux/spinlock.h``) is avariant which saves whether interrupts were on or off in a flags word,which is passed to spin_unlock_irqrestore(). This meansthat the same code can be used inside an hard irq handler (whereinterrupts are already off) and in softirqs (where the irq disabling isrequired). Note that softirqs (and hence tasklets and timers) are run on returnfrom hardware interrupts, so spin_lock_irq() also stopsthese. In that sense, spin_lock_irqsave() is the mostgeneral and powerful locking function. Locking Between Two Hard IRQ Handlers------------------------------------- It is rare to have to share data between two IRQ handlers, but if youdo, spin_lock_irqsave() should be used: it isarchitecture-specific whether all interrupts are disabled inside irqhandlers themselves. Cheat Sheet For Locking======================= Pete Zaitcev gives the following summary: -  If you are in a process context (any syscall) and want to lock other   process out, use a mutex. You can take a mutex and sleep   (``copy_from_user*(`` or ``kmalloc(x,GFP_KERNEL)``). -  Otherwise (== data can be touched in an interrupt), use   spin_lock_irqsave() and   spin_unlock_irqrestore(). -  Avoid holding spinlock for more than 5 lines of code and across any   function call (except accessors like readb()). Table of Minimum Requirements----------------------------- The following table lists the **minimum** locking requirements betweenvarious contexts. In some cases, the same context can only be running onone CPU at a time, so no locking is required for that context (eg. aparticular thread can only run on one CPU at a time, but if it needsshares data with another thread, locking is required). Remember the advice above: you can always usespin_lock_irqsave(), which is a superset of all otherspinlock primitives. ============== ============= ============= ========= ========= ========= ========= ======= ======= ============== ==============.              IRQ Handler A IRQ Handler B Softirq A Softirq B Tasklet A Tasklet B Timer A Timer B User Context A User Context B============== ============= ============= ========= ========= ========= ========= ======= ======= ============== ==============IRQ Handler A  NoneIRQ Handler B  SLIS          NoneSoftirq A      SLI           SLI           SLSoftirq B      SLI           SLI           SL        SLTasklet A      SLI           SLI           SL        SL        NoneTasklet B      SLI           SLI           SL        SL        SL        NoneTimer A        SLI           SLI           SL        SL        SL        SL        NoneTimer B        SLI           SLI           SL        SL        SL        SL        SL      NoneUser Context A SLI           SLI           SLBH      SLBH      SLBH      SLBH      SLBH    SLBH    NoneUser Context B SLI           SLI           SLBH      SLBH      SLBH      SLBH      SLBH    SLBH    MLI            None============== ============= ============= ========= ========= ========= ========= ======= ======= ============== ============== Table: Table of Locking Requirements +--------+----------------------------+| SLIS   | spin_lock_irqsave          |+--------+----------------------------+| SLI    | spin_lock_irq              |+--------+----------------------------+| SL     | spin_lock                  |+--------+----------------------------+| SLBH   | spin_lock_bh               |+--------+----------------------------+| MLI    | mutex_lock_interruptible   |+--------+----------------------------+ Table: Legend for Locking Requirements Table The trylock Functions===================== There are functions that try to acquire a lock only once and immediatelyreturn a value telling about success or failure to acquire the lock.They can be used if you need no access to the data protected with thelock when some other thread is holding the lock. You should acquire thelock later if you then need access to the data protected with the lock. spin_trylock() does not spin but returns non-zero if itacquires the spinlock on the first try or 0 if not. This function can beused in all contexts like spin_lock(): you must havedisabled the contexts that might interrupt you and acquire the spinlock. mutex_trylock() does not suspend your task but returnsnon-zero if it could lock the mutex on the first try or 0 if not. Thisfunction cannot be safely used in hardware or software interruptcontexts despite not sleeping. Common Examples=============== Let's step through a simple example: a cache of number to name mappings.The cache keeps a count of how often each of the objects is used, andwhen it gets full, throws out the least used one. All In User Context------------------- For our first example, we assume that all operations are in user context(ie. from system calls), so we can sleep. This means we can use a mutexto protect the cache and all the objects within it. Here's the code::     #include <linux/list.h>    #include <linux/slab.h>    #include <linux/string.h>    #include <linux/mutex.h>    #include <asm/errno.h>     struct object    {            struct list_head list;            int id;            char name[32];            int popularity;    };     /* Protects the cache, cache_num, and the objects within it */    static DEFINE_MUTEX(cache_lock);    static LIST_HEAD(cache);    static unsigned int cache_num = 0;    #define MAX_CACHE_SIZE 10     /* Must be holding cache_lock */    static struct object *__cache_find(int id)    {            struct object *i;             list_for_each_entry(i, &cache, list)                    if (i->id == id) {                            i->popularity++;                            return i;                    }            return NULL;    }     /* Must be holding cache_lock */    static void __cache_delete(struct object *obj)    {            BUG_ON(!obj);            list_del(&obj->list);            kfree(obj);            cache_num--;    }     /* Must be holding cache_lock */    static void __cache_add(struct object *obj)    {            list_add(&obj->list, &cache);            if (++cache_num > MAX_CACHE_SIZE) {                    struct object *i, *outcast = NULL;                    list_for_each_entry(i, &cache, list) {                            if (!outcast || i->popularity < outcast->popularity)                                    outcast = i;                    }                    __cache_delete(outcast);            }    }     int cache_add(int id, const char *name)    {            struct object *obj;             if ((obj = kmalloc(sizeof(*obj), GFP_KERNEL)) == NULL)                    return -ENOMEM;             strscpy(obj->name, name, sizeof(obj->name));            obj->id = id;            obj->popularity = 0;             mutex_lock(&cache_lock);            __cache_add(obj);            mutex_unlock(&cache_lock);            return 0;    }     void cache_delete(int id)    {            mutex_lock(&cache_lock);            __cache_delete(__cache_find(id));            mutex_unlock(&cache_lock);    }     int cache_find(int id, char *name)    {            struct object *obj;            int ret = -ENOENT;             mutex_lock(&cache_lock);            obj = __cache_find(id);            if (obj) {                    ret = 0;                    strcpy(name, obj->name);            }            mutex_unlock(&cache_lock);            return ret;    } Note that we always make sure we have the cache_lock when we add,delete, or look up the cache: both the cache infrastructure itself andthe contents of the objects are protected by the lock. In this case it'seasy, since we copy the data for the user, and never let them access theobjects directly. There is a slight (and common) optimization here: incache_add() we set up the fields of the object beforegrabbing the lock. This is safe, as no-one else can access it until weput it in cache. Accessing From Interrupt Context-------------------------------- Now consider the case where cache_find() can be called

Lines 1–500 of 1448. Load more