kernel-locking.tmpl

linux 内核源代码

+        /* This is protected by RCU */
         struct list_head list;
         int popularity;

+        struct rcu_head rcu;
+
         atomic_t refcnt;

         /* Doesn't change once created. */
@@ -40,7 +43,7 @@
 {
         struct object *i;

-        list_for_each_entry(i, &cache, list) {
+        list_for_each_entry_rcu(i, &cache, list) {
                 if (i->id == id) {
                         i->popularity++;
                         return i;
@@ -49,19 +52,25 @@
         return NULL;
 }

+/* Final discard done once we know no readers are looking. */
+static void cache_delete_rcu(void *arg)
+{
+        object_put(arg);
+}
+
 /* Must be holding cache_lock */
 static void __cache_delete(struct object *obj)
 {
         BUG_ON(!obj);
-        list_del(&obj->list);
-        object_put(obj);
+        list_del_rcu(&obj->list);
         cache_num--;
+        call_rcu(&obj->rcu, cache_delete_rcu, obj);
 }

 /* Must be holding cache_lock */
 static void __cache_add(struct object *obj)
 {
-        list_add(&obj->list, &cache);
+        list_add_rcu(&obj->list, &cache);
         if (++cache_num > MAX_CACHE_SIZE) {
                 struct object *i, *outcast = NULL;
                 list_for_each_entry(i, &cache, list) {
@@ -85,6 +94,7 @@
         obj->popularity = 0;
         atomic_set(&obj->refcnt, 1); /* The cache holds a reference */
         spin_lock_init(&obj->lock);
+        INIT_RCU_HEAD(&obj->rcu);

         spin_lock_irqsave(&cache_lock, flags);
         __cache_add(obj);
@@ -104,12 +114,11 @@
 struct object *cache_find(int id)
 {
         struct object *obj;
-        unsigned long flags;

-        spin_lock_irqsave(&cache_lock, flags);
+        rcu_read_lock();
         obj = __cache_find(id);
         if (obj)
                 object_get(obj);
-        spin_unlock_irqrestore(&cache_lock, flags);
+        rcu_read_unlock();
         return obj;
 }
</programlisting>

<para>
Note that the reader will alter the
<structfield>popularity</structfield> member in
<function>__cache_find()</function>, and now it doesn't hold a lock.
One solution would be to make it an <type>atomic_t</type>, but for
this usage, we don't really care about races: an approximate result is
good enough, so I didn't change it.
</para>

<para>
The result is that <function>cache_find()</function> requires no
synchronization with any other functions, so is almost as fast on SMP
as it would be on UP.
</para>

<para>
There is a furthur optimization possible here: remember our original
cache code, where there were no reference counts and the caller simply
held the lock whenever using the object?  This is still possible: if
you hold the lock, noone can delete the object, so you don't need to
get and put the reference count.
</para>

<para>
Now, because the 'read lock' in RCU is simply disabling preemption, a
caller which always has preemption disabled between calling
<function>cache_find()</function> and
<function>object_put()</function> does not need to actually get and
put the reference count: we could expose
<function>__cache_find()</function> by making it non-static, and
such callers could simply call that.
</para>
<para>
The benefit here is that the reference count is not written to: the
object is not altered in any way, which is much faster on SMP
machines due to caching.
</para>
  </sect1>

   <sect1 id="per-cpu">
    <title>Per-CPU Data</title>

    <para>
      Another 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.
    </para>

    <para>
      If that was too slow (it's usually not, but if you've got a
      really big machine to test on and can show that it is), you
      could instead use a counter for each CPU, then none of them need
      an exclusive lock.  See <function>DEFINE_PER_CPU()</function>,
      <function>get_cpu_var()</function> and
      <function>put_cpu_var()</function>
      (<filename class="headerfile">include/linux/percpu.h</filename>).
    </para>

    <para>
      Of particular use for simple per-cpu counters is the
      <type>local_t</type> type, and the
      <function>cpu_local_inc()</function> and related functions,
      which are more efficient than simple code on some architectures
      (<filename class="headerfile">include/asm/local.h</filename>).
    </para>

    <para>
      Note that there is no simple, reliable way of getting an exact
      value of such a counter, without introducing more locks.  This
      is not a problem for some uses.
    </para>
   </sect1>

   <sect1 id="mostly-hardirq">
    <title>Data Which Mostly Used By An IRQ Handler</title>

    <para>
      If data is always accessed from within the same IRQ handler, you
      don't need a lock at all: the kernel already guarantees that the
      irq handler will not run simultaneously on multiple CPUs.
    </para>
    <para>
      Manfred Spraul points out that you can still do this, even if
      the data is very occasionally accessed in user context or
      softirqs/tasklets.  The irq handler doesn't use a lock, and
      all other accesses are done as so:
    </para>

<programlisting>
	spin_lock(&amp;lock);
	disable_irq(irq);
	...
	enable_irq(irq);
	spin_unlock(&amp;lock);
</programlisting>
    <para>
      The <function>disable_irq()</function> prevents the irq handler
      from running (and waits for it to finish if it's currently
      running on other CPUs).  The spinlock prevents any other
      accesses happening at the same time.  Naturally, this is slower
      than just a <function>spin_lock_irq()</function> call, so it
      only makes sense if this type of access happens extremely
      rarely.
    </para>
   </sect1>
  </chapter>

 <chapter id="sleeping-things">
    <title>What Functions Are Safe To Call From Interrupts?</title>

    <para>
      Many functions in the kernel sleep (ie. call schedule())
      directly or indirectly: you can never call them while holding a
      spinlock, or with preemption disabled.  This also means you need
      to be in user context: calling them from an interrupt is illegal.
    </para>

   <sect1 id="sleeping">
    <title>Some Functions Which Sleep</title>

    <para>
      The most common ones are listed below, but you usually have to
      read the code to find out if other calls are safe.  If everyone
      else who calls it can sleep, you probably need to be able to
      sleep, too.  In particular, registration and deregistration
      functions usually expect to be called from user context, and can
      sleep.
    </para>

    <itemizedlist>
     <listitem>
      <para>
        Accesses to 
        <firstterm linkend="gloss-userspace">userspace</firstterm>:
      </para>
      <itemizedlist>
       <listitem>
        <para>
          <function>copy_from_user()</function>
        </para>
       </listitem>
       <listitem>
        <para>
          <function>copy_to_user()</function>
        </para>
       </listitem>
       <listitem>
        <para>
          <function>get_user()</function>
        </para>
       </listitem>
       <listitem>
        <para>
          <function> put_user()</function>
        </para>
       </listitem>
      </itemizedlist>
     </listitem>

     <listitem>
      <para>
        <function>kmalloc(GFP_KERNEL)</function>
      </para>
     </listitem>

     <listitem>
      <para>
      <function>down_interruptible()</function> and
      <function>down()</function>
      </para>
      <para>
       There is a <function>down_trylock()</function> which can be
       used inside interrupt context, as it will not sleep.
       <function>up()</function> will also never sleep.
      </para>
     </listitem>
    </itemizedlist>
   </sect1>

   <sect1 id="dont-sleep">
    <title>Some Functions Which Don't Sleep</title>

    <para>
     Some functions are safe to call from any context, or holding
     almost any lock.
    </para>

    <itemizedlist>
     <listitem>
      <para>
	<function>printk()</function>
      </para>
     </listitem>
     <listitem>
      <para>
        <function>kfree()</function>
      </para>
     </listitem>
     <listitem>
      <para>
	<function>add_timer()</function> and <function>del_timer()</function>
      </para>
     </listitem>
    </itemizedlist>
   </sect1>
  </chapter>

  <chapter id="references">
   <title>Further reading</title>

   <itemizedlist>
    <listitem>
     <para>
       <filename>Documentation/spinlocks.txt</filename>: 
       Linus Torvalds' spinlocking tutorial in the kernel sources.
     </para>
    </listitem>

    <listitem>
     <para>
       Unix Systems for Modern Architectures: Symmetric
       Multiprocessing and Caching for Kernel Programmers:
     </para>

     <para>
       Curt Schimmel's very good introduction to kernel level
       locking (not written for Linux, but nearly everything
       applies).  The book is expensive, but really worth every
       penny to understand SMP locking. [ISBN: 0201633388]
     </para>
    </listitem>
   </itemizedlist>
  </chapter>

  <chapter id="thanks">
    <title>Thanks</title>

    <para>
      Thanks to Telsa Gwynne for DocBooking, neatening and adding
      style.
    </para>

    <para>
      Thanks to Martin Pool, Philipp Rumpf, Stephen Rothwell, Paul
      Mackerras, Ruedi Aschwanden, Alan Cox, Manfred Spraul, Tim
      Waugh, Pete Zaitcev, James Morris, Robert Love, Paul McKenney,
      John Ashby for proofreading, correcting, flaming, commenting.
    </para>

    <para>
      Thanks to the cabal for having no influence on this document.
    </para>
  </chapter>

  <glossary id="glossary">
   <title>Glossary</title>

   <glossentry id="gloss-preemption">
    <glossterm>preemption</glossterm>
     <glossdef>
      <para>
        Prior to 2.5, or when <symbol>CONFIG_PREEMPT</symbol> is
        unset, processes in user context inside the kernel would not
        preempt each other (ie. you had that CPU until you have it up,
        except for interrupts).  With the addition of
        <symbol>CONFIG_PREEMPT</symbol> in 2.5.4, this changed: when
        in user context, higher priority tasks can "cut in": spinlocks
        were changed to disable preemption, even on UP.
     </para>
    </glossdef>
   </glossentry>

   <glossentry id="gloss-bh">
    <glossterm>bh</glossterm>
     <glossdef>
      <para>
        Bottom Half: for historical reasons, functions with
        '_bh' in them often now refer to any software interrupt, e.g.
        <function>spin_lock_bh()</function> blocks any software interrupt 
        on the current CPU.  Bottom halves are deprecated, and will 
        eventually be replaced by tasklets.  Only one bottom half will be 
        running at any time.
     </para>
    </glossdef>
   </glossentry>

   <glossentry id="gloss-hwinterrupt">
    <glossterm>Hardware Interrupt / Hardware IRQ</glossterm>
    <glossdef>
     <para>
       Hardware interrupt request.  <function>in_irq()</function> returns 
       <returnvalue>true</returnvalue> in a hardware interrupt handler.
     </para>
    </glossdef>
   </glossentry>

   <glossentry id="gloss-interruptcontext">
    <glossterm>Interrupt Context</glossterm>
    <glossdef>
     <para>
       Not user context: processing a hardware irq or software irq.
       Indicated by the <function>in_interrupt()</function> macro 
       returning <returnvalue>true</returnvalue>.
     </para>
    </glossdef>
   </glossentry>

   <glossentry id="gloss-smp">
    <glossterm><acronym>SMP</acronym></glossterm>
    <glossdef>
     <para>
       Symmetric Multi-Processor: kernels compiled for multiple-CPU
       machines.  (CONFIG_SMP=y).
     </para>
    </glossdef>
   </glossentry>

   <glossentry id="gloss-softirq">
    <glossterm>Software Interrupt / softirq</glossterm>
    <glossdef>
     <para>
       Software interrupt handler.  <function>in_irq()</function> returns
       <returnvalue>false</returnvalue>; <function>in_softirq()</function>
       returns <returnvalue>true</returnvalue>.  Tasklets and softirqs
	both fall into the category of 'software interrupts'.
     </para>
     <para>
       Strictly speaking a softirq is one of up to 32 enumerated software
       interrupts which can run on multiple CPUs at once.
       Sometimes used to refer to tasklets as
       well (ie. all software interrupts).
     </para>
    </glossdef>
   </glossentry>

   <glossentry id="gloss-tasklet">
    <glossterm>tasklet</glossterm>
    <glossdef>
     <para>
       A dynamically-registrable software interrupt,
       which is guarantee