Subversion Repositories or1k

    Paul

    Rusty

    Russell

      rusty@rustcorp.com.au

   2000

   Paul Russell

     This documentation is free software; you can redistribute

     it and/or modify it under the terms of the GNU General Public

     License as published by the Free Software Foundation; either

     version 2 of the License, or (at your option) any later

     version.

     This program is distributed in the hope that it will be

     useful, but WITHOUT ANY WARRANTY; without even the implied

     warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

     See the GNU General Public License for more details.

     You should have received a copy of the GNU General Public

     License along with this program; if not, write to the Free

     Software Foundation, Inc., 59 Temple Place, Suite 330, Boston,

     MA 02111-1307 USA

     For more details see the file COPYING in the source

     distribution of Linux.

     Welcome, to Rusty's Remarkably Unreliable Guide to Kernel

     Locking issues.  This document describes the locking systems in

     the Linux Kernel as we approach 2.4.

     It looks like SMP

      is here to stay; so everyone hacking on the kernel

     these days needs to know the fundamentals of concurrency and locking

     for SMP.

      (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:

    

      
      

         
87
         

         

         
     
      
      

         
88
         

         

         
 
      
      

         
89
         

         

         
     
      
      

         
90
         

         

         
 
      
      

         
91
         

         

         
      

      
      

         
92
         

         

         
       
      
      

         
93
         

         

         
        Instance 1
      
      

         
94
         

         

         
        Instance 2
      
      

         
95
         

         

         
       
      
      

         
96
         

         

         
      
      
      

         
97
         

         

         
 
      
      

         
98
         

         

         
      

      
      

         
99
         

         

         
       
      
      

         
100
         

         

         
        read very_important_count (5)
      
      

         
101
         

         

         
        
      
      

         
102
         

         

         
       
      
      

         
103
         

         

         
       
      
      

         
104
         

         

         
        add 1 (6)
      
      

         
105
         

         

         
        
      
      

         
106
         

         

         
       
      
      

         
107
         

         

         
       
      
      

         
108
         

         

         
        write very_important_count (6)
      
      

         
109
         

         

         
        
      
      

         
110
         

         

         
       
      
      

         
111
         

         

         
       
      
      

         
112
         

         

         
        
      
      

         
113
         

         

         
        read very_important_count (6)
      
      

         
114
         

         

         
       
      
      

         
115
         

         

         
       
      
      

         
116
         

         

         
        
      
      

         
117
         

         

         
        add 1 (7)
      
      

         
118
         

         

         
       
      
      

         
119
         

         

         
       
      
      

         
120
         

         

         
        
      
      

         
121
         

         

         
        write very_important_count (7)
      
      

         
122
         

         

         
       
      
      

         
123
         

         

         
      
      
      

         
124
         

         

         
 
      
      

         
125
         

         

         
     
      
      

         
126
         

         

         
    

     This is what might happen:

    

      
      

         
133
         

         

         
     
      
      

         
134
         

         

         
 
      
      

         
135
         

         

         
     
      
      

         
136
         

         

         
      

      
      

         
137
         

         

         
       
      
      

         
138
         

         

         
        Instance 1
      
      

         
139
         

         

         
        Instance 2
      
      

         
140
         

         

         
       
      
      

         
141
         

         

         
      
      
      

         
142
         

         

         
 
      
      

         
143
         

         

         
      

      
      

         
144
         

         

         
       
      
      

         
145
         

         

         
        read very_important_count (5)
      
      

         
146
         

         

         
        
      
      

         
147
         

         

         
       
      
      

         
148
         

         

         
       
      
      

         
149
         

         

         
        
      
      

         
150
         

         

         
        read very_important_count (5)
      
      

         
151
         

         

         
       
      
      

         
152
         

         

         
       
      
      

         
153
         

         

         
        add 1 (6)
      
      

         
154
         

         

         
        
      
      

         
155
         

         

         
       
      
      

         
156
         

         

         
       
      
      

         
157
         

         

         
        
      
      

         
158
         

         

         
        add 1 (6)
      
      

         
159
         

         

         
       
      
      

         
160
         

         

         
       
      
      

         
161
         

         

         
        write very_important_count (6)
      
      

         
162
         

         

         
        
      
      

         
163
         

         

         
       
      
      

         
164
         

         

         
       
      
      

         
165
         

         

         
        
      
      

         
166
         

         

         
        write very_important_count (6)
      
      

         
167
         

         

         
       
      
      

         
168
         

         

         
      
      
      

         
169
         

         

         
     
      
      

         
170
         

         

         
    

      This overlap, where what actually happens depends on the

      relative timing of multiple tasks, is called a race condition.

      The piece of code containing the concurrency issue is called a

      critical region.  And especially since Linux starting running

      on SMP machines, they became one of the major issues in kernel

      design and implementation.

      The solution is to recognize when these simultaneous accesses

      occur, and use locks to make sure that only one instance can

      enter the critical region at any time.  There are many

      friendly primitives in the Linux kernel to help you do this.

      And then there are the unfriendly primitives, but I'll pretend

      they don't exist.

     There are two main types of kernel locks.  The fundamental type

     is the spinlock

     (include/asm/spinlock.h),

     which is a very simple single-holder lock: if you can't get the

     spinlock, you keep trying (spinning) until you can.  Spinlocks are

     very small and fast, and can be used anywhere.

     The second type is a semaphore

     (include/asm/semaphore.h): it

     can have more than one holder at any time (the number decided at

     initialization time), although it is most commonly used as a

     single-holder lock (a mutex).  If you can't get a semaphore,

     your task will put itself on the queue, and be woken up when the

     semaphore is released.  This means the CPU will do something

     else while you are waiting, but there are many cases when you

     simply can't sleep (see ), and so

     have to use a spinlock instead.

     Neither type of lock is recursive: see

     .

      For kernels compiled without CONFIG_SMP, spinlocks

      do not exist at all.  This is an excellent design decision: when

      no-one else can run at the same time, there is no reason to

      have a lock at all.

      You should always test your locking code with CONFIG_SMP

      enabled, even if you don't have an SMP test box, because it

      will still catch some (simple) kinds of deadlock.

      Semaphores still exist, because they are required for

      synchronization between user

      contexts, as we will see below.

      Both spinlocks and semaphores have read/write variants:

      rwlock_t and struct rw_semaphore.

      These divide users into two classes: the readers and the writers.  If

      you are only reading the data, you can get a read lock, but to write to

      the data you need the write lock.  Many people can hold a read lock,

      but a writer must be sole holder.

      This means much smoother locking if your code divides up

      neatly along reader/writer lines.  All the discussions below

      also apply to read/write variants.

       If you have a data structure which is only ever accessed from

       user context, then you can use a simple semaphore

       (linux/asm/semaphore.h) to protect it.  This

       is the most trivial case: you initialize the semaphore to the number

       of resources available (usually 1), and call

       down_interruptible() to grab the semaphore, and

       up() to release it.  There is also a

       down(), which should be avoided, because it

       will not return if a signal is received.

       Example: linux/net/core/netfilter.c allows

       registration of new setsockopt() and

       getsockopt() calls, with

       nf_register_sockopt().  Registration and

       de-registration are only done on module load and unload (and boot

       time, where there is no concurrency), and the list of registrations

       is only consulted for an unknown setsockopt()

       or getsockopt() system call.  The

       nf_sockopt_mutex is perfect to protect this,

       especially since the setsockopt and getsockopt calls may well

       sleep.

      If a bottom half shares

      data with user context, you have two problems.  Firstly, the current

      user context can be interrupted by a bottom half, and secondly, the

      critical region could be entered from another CPU.  This is where

      spin_lock_bh()

      (include/linux/spinlock.h) is

      used.  It disables bottom halves on that CPU, then grabs the lock.

      spin_unlock_bh() does the reverse.

      This works perfectly for UP

       as well: the spin lock vanishes, and this macro

      simply becomes local_bh_disable()

      (include/asm/softirq.h), which

      protects you from the bottom half being run.

      This is exactly the same as above, because

      local_bh_disable() actually disables all

      softirqs and tasklets

      on that CPU as well.  It should really be

      called `local_softirq_disable()', but the name has been preserved

      for historical reasons.  Similarly,

      spin_lock_bh() would now be called

      spin_lock_softirq() in a perfect world.

      Sometimes a bottom half might want to share data with

      another bottom half (especially remember that timers are run

      off a bottom half).

       Since a bottom half is never run on two CPUs at once, you

       don't need to worry about your bottom half being run twice

       at once, even on SMP.

       Since only one bottom half ever runs at a time once, you

       don't need to worry about race conditions with other bottom

       halves.  Beware that things might change under you, however,

       if someone changes your bottom half to a tasklet.  If you

       want to make your code future-proof, pretend you're already

       running from a tasklet (see below), and doing the extra

       locking.  Of course, if it's five years before that happens,

       you're gonna look like a damn fool.

      Sometimes a tasklet might want to share data with another

      tasklet, or a bottom half.

       Since a tasklet is never run on two CPUs at once, you don't

       need to worry about your tasklet being reentrant (running

       twice at once), even on SMP.

       If another tasklet (or bottom half, such as a timer) wants

       to share data with your tasklet, you will both need to use

       spin_lock() and

       spin_unlock() calls.

       spin_lock_bh() is

       unnecessary here, as you are already in a tasklet, and

       none will be run on the same CPU.

      Often a softirq might

      want to share data with itself, a tasklet, or a bottom half.

       The same softirq can run on the other CPUs: you can use a

       per-CPU array (see ) for better

       performance.  If you're going so far as to use a softirq,

       you probably care about scalable performance enough

       to justify the extra complexity.

       You'll need to use spin_lock() and

       spin_unlock() for shared data.

       You'll need to use spin_lock() and

       spin_unlock() for shared data, whether it

       be a timer (which can be running on a different CPU), bottom half,

       tasklet or the same or another softirq.

     Hardware interrupts usually communicate with a bottom half,

     tasklet or softirq.  Frequently this involves putting work in a

     queue, which the BH/softirq will take out.

      If a hardware irq handler shares data with a softirq, you have

      two concerns.  Firstly, the softirq processing can be

      interrupted by a hardware interrupt, and secondly, the

      critical region could be entered by a hardware interrupt on

      another CPU.  This is where spin_lock_irq() is

      used.  It is defined to disable interrupts on that cpu, then grab

      the lock. spin_unlock_irq() does the reverse.

      This works perfectly for UP as well: the spin lock vanishes,

      and this macro simply becomes local_irq_disable()

      (include/asm/smp.h), which

      protects you from the softirq/tasklet/BH being run.

      spin_lock_irqsave()

      (include/linux/spinlock.h) is a variant

      which saves whether interrupts were on or off in a flags word,

      which is passed to spin_lock_irqrestore().  This

      means that the same code can be used inside an hard irq handler (where

      interrupts are already off) and in softirqs (where the irq

      disabling is required).

     This section lists some common dilemmas and the standard

     solutions used in the Linux kernel code.  If you use these,

     people will find your code simpler to understand.

     If I could give you one piece of advice: never sleep with anyone

     crazier than yourself.  But if I had to give you advice on

     locking: keep it simple.

     Lock data, not code.

     Be reluctant to introduce new locks.

     Strangely enough, this is the exact reverse of my advice when

     you have slept with someone crazier than yourself.

      There is a fairly common case where an interrupt handler needs

      access to a critical region, but does not need write access.

      In this case, you do not need to use

      read_lock_irq(), but only

      read_lock() everywhere (since if an interrupt

      occurs, the irq handler will only try to grab a read lock, which

      won't deadlock).  You will still need to use

      write_lock_irq().

      Similar logic applies to locking between softirqs/tasklets/BHs

      which never need a write lock, and user context:

      read_lock() and

      write_lock_bh().

      There is a coding bug where a piece of code tries to grab a

      spinlock twice: it will spin forever, waiting for the lock to

      be released (spinlocks, rwlocks and semaphores are not

      recursive in Linux).  This is trivial to diagnose: not a

      stay-up-five-nights-talk-to-fluffy-code-bunnies kind of

      problem.

      For a slightly more complex case, imagine you have a region

      shared by a bottom half and user context.  If you use a

      spin_lock() call to protect it, it is

      possible that the user context will be interrupted by the bottom

      half while it holds the lock, and the bottom half will then spin

      forever trying to get the same lock.

      Both of these are called deadlock, and as shown above, it can

      occur even with a single CPU (although not on UP compiles,

      since spinlocks vanish on kernel compiles with

      CONFIG_SMP=n. You'll still get data corruption

      in the second example).

      This complete lockup is easy to diagnose: on SMP boxes the

      watchdog timer or compiling with DEBUG_SPINLOCKS set

      (include/linux/spinlock.h) will show this up

      immediately when it happens.

      A more complex problem is the so-called `deadly embrace',

      involving two or more locks.  Say you have a hash table: each

      entry in the table is a spinlock, and a chain of hashed

      objects.  Inside a softirq handler, you sometimes want to

      alter an object from one place in the hash to another: you

      grab the spinlock of the old hash chain and the spinlock of

      the new hash chain, and delete the object from the old one,

      and insert it in the new one.

      There are two problems here.  First, if your code ever

      tries to move the object to the same chain, it will deadlock

      with itself as it tries to lock it twice.  Secondly, if the

      same softirq on another CPU is trying to move another object

      in the reverse direction, the following could happen:

    

      
      

         
580
         

         

         
     
      
      

         
581
         

         

         
 
      
      

         
582
         

         

         
     
      
      

         
583
         

         

         
 
      
      

         
584
         

         

         
      

      
      

         
585
         

         

         
       
      
      

         
586
         

         

         
        CPU 1
      
      

         
587
         

         

         
        CPU 2
      
      

         
588
         

         

         
       
      
      

         
589
         

         

         
      
      
      

         
590
         

         

         
 
      
      

         
591
         

         

         
      

      
      

         
592
         

         

         
       
      
      

         
593
         

         

         
        Grab lock A -> OK
      
      

         
594
         

         

         
        Grab lock B -> OK
      
      

         
595
         

         

         
       
      
      

         
596
         

         

         
       
      
      

         
597
         

         

         
        Grab lock B -> spin
      
      

         
598
         

         

         
        Grab lock A -> spin
      
      

         
599
         

         

         
       
      
      

         
600
         

         

         
      
      
      

         
601
         

         

         
     
      
      

         
602
         

         

         
    

      The two CPUs will spin forever, waiting for the other to give up

      their lock.  It will look, smell, and feel like a crash.

       Textbooks will tell you that if you always lock in the same

       order, you will never get this kind of deadlock.  Practice

       will tell you that this approach doesn't scale: when I

       create a new lock, I don't understand enough of the kernel

       to figure out where in the 5000 lock hierarchy it will fit.

       The best locks are encapsulated: they never get exposed in

       headers, and are never held around calls to non-trivial

       functions outside the same file.  You can read through this

       code and see that it will never deadlock, because it never

       tries to grab another lock while it has that one.  People

       using your code don't even need to know you are using a

       lock.

       A classic problem here is when you provide callbacks or

       hooks: if you call these with the lock held, you risk simple

       deadlock, or a deadly embrace (who knows what the callback

       will do?).  Remember, the other programmers are out to get

       you, so don't do this.

       Deadlocks are problematic, but not as bad as data

       corruption.  Code which grabs a read lock, searches a list,

       fails to find what it wants, drops the read lock, grabs a

       write lock and inserts the object has a race condition.

       If you don't see why, please stay the fuck away from my code.

      A great technique for avoiding locking which is used fairly

      widely is to duplicate information for each CPU.  For example,

      if you wanted to keep a count of a common condition, you could

      use a spin lock and a single counter.  Nice and simple.

      If that was too slow [it's probably not], you could instead

      use a counter for each CPU [don't], then none of them need an

      exclusive lock [you're wasting your time here].  To make sure

      the CPUs don't have to synchronize caches all the time, align

      the counters to cache boundaries by appending

      `__cacheline_aligned' to the declaration

      (include/linux/cache.h).

      [Can't you think of anything better to do?]

      They will need a read lock to access their own counters,

      however.  That way you can use a write lock to grant exclusive

      access to all of them at once, to tally them up.

      A classic example of per-CPU information is Ingo's `big

      reader' locks

      (linux/include/brlock.h).  These

      use the Per-CPU Data techniques described above to create a lock which

      is very fast to get a read lock, but agonizingly slow for a write

      lock.

      Fortunately, there are a limited number of these locks

      available: you have to go through a strict interview process

      to get one.

      Sometimes it is possible to avoid locking.  Consider the

      following case from the 2.2 firewall code, which inserted an

      element into a single linked list in user context:

        new->next = i->next;

        i->next = new;

      Here the author (Alan Cox, who knows what he's doing) assumes

      that the pointer assignments are atomic.  This is important,

      because networking packets would traverse this list on bottom

      halves without a lock.  Depending on their exact timing, they

      would either see the new element in the list with a valid

      next pointer, or it would not be in the

      list yet.  A lock is still required against other CPUs inserting

      or deleting from the list, of course.

      Of course, the writes must be in this

      order, otherwise the new element appears in the list with an

      invalid next pointer, and any other

      CPU iterating at the wrong time will jump through it into garbage.

      Because modern CPUs reorder, Alan's code actually read as follows:

        new->next = i->next;

        wmb();

        i->next = new;

      The wmb() is a write memory barrier

      (include/asm/system.h): neither

      the compiler nor the CPU will allow any writes to memory after the

      wmb() to be visible to other hardware

      before any of the writes before the wmb().

      As i386 does not do write reordering, this bug would never

      show up on that platform.  On other SMP platforms, however, it

      will.

      There is also rmb() for read ordering: to ensure

      any previous variable reads occur before following reads.  The simple

      mb() macro combines both

      rmb() and wmb().

      Some atomic operations are defined to act as a memory barrier

      (ie. as per the mb() macro, but if in

      doubt, be explicit.

      Also,

      spinlock operations act as partial barriers: operations after

      gaining a spinlock will never be moved to precede the

      spin_lock() call, and operations before

      releasing a spinlock will never be moved after the

      spin_unlock() call.

      There are a number of atomic operations defined in

      include/asm/atomic.h: these

      are guaranteed to be seen atomically from all CPUs in the system, thus

      avoiding races. If your shared data consists of a single counter, say,

      these operations might be simpler than using spinlocks (although for

      anything non-trivial using spinlocks is clearer).

      Note that the atomic operations do in general not act as memory

      barriers. Instead you can insert a memory barrier before or

      after atomic_inc() or

      atomic_dec() by inserting

      smp_mb__before_atomic_inc(),

      smp_mb__after_atomic_inc(),

      smp_mb__before_atomic_dec() or

      smp_mb__after_atomic_dec()

      respectively. The advantage of using those macros instead of

      smp_mb() is, that they are cheaper on some

      platforms.

      Locking a collection of objects is fairly easy: you get a

      single spinlock, and you make sure you grab it before

      searching, adding or deleting an object.

      The purpose of this lock is not to protect the individual

      objects: you might have a separate lock inside each one for

      that.  It is to protect the data structure

      containing the objects from race conditions.  Often

      the same lock is used to protect the contents of all the

      objects as well, for simplicity, but they are inherently

      orthogonal (and many other big words designed to confuse).

      Changing this to a read-write lock will often help markedly if

      reads are far more common that writes.  If not, there is

      another approach you can use to reduce the time the lock is

      held: reference counts.

      In this approach, an object has an owner, who sets the

      reference count to one.  Whenever you get a pointer to the

      object, you increment the reference count (a `get' operation).

      Whenever you relinquish a pointer, you decrement the reference

      count (a `put' operation).  When the owner wants to destroy

      it, they mark it dead, and do a put.

      Whoever drops the reference count to zero (usually implemented

      with atomic_dec_and_test()) actually cleans

      up and frees the object.

      This means that you are guaranteed that the object won't

      vanish underneath you, even though you no longer have a lock

      for the collection.

      Here's some skeleton code:

        void create_foo(struct foo *x)

        {

                atomic_set(&x->use, 1);

                spin_lock_bh(&list_lock);

                ... insert in list ...

                spin_unlock_bh(&list_lock);

        }

        struct foo *get_foo(int desc)

        {

                struct foo *ret;

                spin_lock_bh(&list_lock);

                ... find in list ...

                if (ret) atomic_inc(&ret->use);

                spin_unlock_bh(&list_lock);

                return ret;

        }

        void put_foo(struct foo *x)

        {

                if (atomic_dec_and_test(&x->use))

                        kfree(foo);

        }

        void destroy_foo(struct foo *x)

        {

                spin_lock_bh(&list_lock);

                ... remove from list ...

                spin_unlock_bh(&list_lock);

                put_foo(x);

        }