kernel-locking.tmpl

linux 内核源代码

    </para>
    </sect1>

   <sect1 id="examples-interrupt">
    <title>Accessing From Interrupt Context</title>
    <para>
Now consider the case where <function>cache_find</function> can be
called from interrupt context: either a hardware interrupt or a
softirq.  An example would be a timer which deletes object from the
cache.
    </para>
    <para>
The change is shown below, in standard patch format: the
<symbol>-</symbol> are lines which are taken away, and the
<symbol>+</symbol> are lines which are added.
    </para>
<programlisting>
--- cache.c.usercontext	2003-12-09 13:58:54.000000000 +1100
+++ cache.c.interrupt	2003-12-09 14:07:49.000000000 +1100
@@ -12,7 +12,7 @@
         int popularity;
 };

-static DECLARE_MUTEX(cache_lock);
+static spinlock_t cache_lock = SPIN_LOCK_UNLOCKED;
 static LIST_HEAD(cache);
 static unsigned int cache_num = 0;
 #define MAX_CACHE_SIZE 10
@@ -55,6 +55,7 @@
 int cache_add(int id, const char *name)
 {
         struct object *obj;
+        unsigned long flags;

         if ((obj = kmalloc(sizeof(*obj), GFP_KERNEL)) == NULL)
                 return -ENOMEM;
@@ -63,30 +64,33 @@
         obj-&gt;id = id;
         obj-&gt;popularity = 0;

-        down(&amp;cache_lock);
+        spin_lock_irqsave(&amp;cache_lock, flags);
         __cache_add(obj);
-        up(&amp;cache_lock);
+        spin_unlock_irqrestore(&amp;cache_lock, flags);
         return 0;
 }

 void cache_delete(int id)
 {
-        down(&amp;cache_lock);
+        unsigned long flags;
+
+        spin_lock_irqsave(&amp;cache_lock, flags);
         __cache_delete(__cache_find(id));
-        up(&amp;cache_lock);
+        spin_unlock_irqrestore(&amp;cache_lock, flags);
 }

 int cache_find(int id, char *name)
 {
         struct object *obj;
         int ret = -ENOENT;
+        unsigned long flags;

-        down(&amp;cache_lock);
+        spin_lock_irqsave(&amp;cache_lock, flags);
         obj = __cache_find(id);
         if (obj) {
                 ret = 0;
                 strcpy(name, obj-&gt;name);
         }
-        up(&amp;cache_lock);
+        spin_unlock_irqrestore(&amp;cache_lock, flags);
         return ret;
 }
</programlisting>

    <para>
Note that the <function>spin_lock_irqsave</function> will turn off
interrupts if they are on, otherwise does nothing (if we are already
in an interrupt handler), hence these functions are safe to call from
any context.
    </para>
    <para>
Unfortunately, <function>cache_add</function> calls
<function>kmalloc</function> with the <symbol>GFP_KERNEL</symbol>
flag, which is only legal in user context.  I have assumed that
<function>cache_add</function> is still only called in user context,
otherwise this should become a parameter to
<function>cache_add</function>.
    </para>
  </sect1>
   <sect1 id="examples-refcnt">
    <title>Exposing Objects Outside This File</title>
    <para>
If our objects contained more information, it might not be sufficient
to copy the information in and out: other parts of the code might want
to keep pointers to these objects, for example, rather than looking up
the id every time.  This produces two problems.
    </para>
    <para>
The first problem is that we use the <symbol>cache_lock</symbol> to
protect objects: we'd need to make this non-static so the rest of the
code can use it.  This makes locking trickier, as it is no longer all
in one place.
    </para>
    <para>
The second problem is the lifetime problem: if another structure keeps
a pointer to an object, it presumably expects that pointer to remain
valid.  Unfortunately, this is only guaranteed while you hold the
lock, otherwise someone might call <function>cache_delete</function>
and even worse, add another object, re-using the same address.
    </para>
    <para>
As there is only one lock, you can't hold it forever: no-one else would
get any work done.
    </para>
    <para>
The solution to this problem is to use a reference count: everyone who
has a pointer to the object increases it when they first get the
object, and drops the reference count when they're finished with it.
Whoever drops it to zero knows it is unused, and can actually delete it.
    </para>
    <para>
Here is the code:
    </para>

<programlisting>
--- cache.c.interrupt	2003-12-09 14:25:43.000000000 +1100
+++ cache.c.refcnt	2003-12-09 14:33:05.000000000 +1100
@@ -7,6 +7,7 @@
 struct object
 {
         struct list_head list;
+        unsigned int refcnt;
         int id;
         char name[32];
         int popularity;
@@ -17,6 +18,35 @@
 static unsigned int cache_num = 0;
 #define MAX_CACHE_SIZE 10

+static void __object_put(struct object *obj)
+{
+        if (--obj-&gt;refcnt == 0)
+                kfree(obj);
+}
+
+static void __object_get(struct object *obj)
+{
+        obj-&gt;refcnt++;
+}
+
+void object_put(struct object *obj)
+{
+        unsigned long flags;
+
+        spin_lock_irqsave(&amp;cache_lock, flags);
+        __object_put(obj);
+        spin_unlock_irqrestore(&amp;cache_lock, flags);
+}
+
+void object_get(struct object *obj)
+{
+        unsigned long flags;
+
+        spin_lock_irqsave(&amp;cache_lock, flags);
+        __object_get(obj);
+        spin_unlock_irqrestore(&amp;cache_lock, flags);
+}
+
 /* Must be holding cache_lock */
 static struct object *__cache_find(int id)
 {
@@ -35,6 +65,7 @@
 {
         BUG_ON(!obj);
         list_del(&amp;obj-&gt;list);
+        __object_put(obj);
         cache_num--;
 }

@@ -63,6 +94,7 @@
         strlcpy(obj-&gt;name, name, sizeof(obj-&gt;name));
         obj-&gt;id = id;
         obj-&gt;popularity = 0;
+        obj-&gt;refcnt = 1; /* The cache holds a reference */

         spin_lock_irqsave(&amp;cache_lock, flags);
         __cache_add(obj);
@@ -79,18 +111,15 @@
         spin_unlock_irqrestore(&amp;cache_lock, flags);
 }

-int cache_find(int id, char *name)
+struct object *cache_find(int id)
 {
         struct object *obj;
-        int ret = -ENOENT;
         unsigned long flags;

         spin_lock_irqsave(&amp;cache_lock, flags);
         obj = __cache_find(id);
-        if (obj) {
-                ret = 0;
-                strcpy(name, obj-&gt;name);
-        }
+        if (obj)
+                __object_get(obj);
         spin_unlock_irqrestore(&amp;cache_lock, flags);
-        return ret;
+        return obj;
 }
</programlisting>

<para>
We encapsulate the reference counting in the standard 'get' and 'put'
functions.  Now we can return the object itself from
<function>cache_find</function> which has the advantage that the user
can now sleep holding the object (eg. to
<function>copy_to_user</function> to name to userspace).
</para>
<para>
The other point to note is that I said a reference should be held for
every pointer to the object: thus the reference count is 1 when first
inserted into the cache.  In some versions the framework does not hold
a reference count, but they are more complicated.
</para>

   <sect2 id="examples-refcnt-atomic">
    <title>Using Atomic Operations For The Reference Count</title>
<para>
In practice, <type>atomic_t</type> would usually be used for
<structfield>refcnt</structfield>.  There are a number of atomic
operations defined in

<filename class="headerfile">include/asm/atomic.h</filename>: these are
guaranteed to be seen atomically from all CPUs in the system, so no
lock is required.  In this case, it is simpler than using spinlocks,
although for anything non-trivial using spinlocks is clearer.  The
<function>atomic_inc</function> and
<function>atomic_dec_and_test</function> are used instead of the
standard increment and decrement operators, and the lock is no longer
used to protect the reference count itself.
</para>

<programlisting>
--- cache.c.refcnt	2003-12-09 15:00:35.000000000 +1100
+++ cache.c.refcnt-atomic	2003-12-11 15:49:42.000000000 +1100
@@ -7,7 +7,7 @@
 struct object
 {
         struct list_head list;
-        unsigned int refcnt;
+        atomic_t refcnt;
         int id;
         char name[32];
         int popularity;
@@ -18,33 +18,15 @@
 static unsigned int cache_num = 0;
 #define MAX_CACHE_SIZE 10

-static void __object_put(struct object *obj)
-{
-        if (--obj-&gt;refcnt == 0)
-                kfree(obj);
-}
-
-static void __object_get(struct object *obj)
-{
-        obj-&gt;refcnt++;
-}
-
 void object_put(struct object *obj)
 {
-        unsigned long flags;
-
-        spin_lock_irqsave(&amp;cache_lock, flags);
-        __object_put(obj);
-        spin_unlock_irqrestore(&amp;cache_lock, flags);
+        if (atomic_dec_and_test(&amp;obj-&gt;refcnt))
+                kfree(obj);
 }

 void object_get(struct object *obj)
 {
-        unsigned long flags;
-
-        spin_lock_irqsave(&amp;cache_lock, flags);
-        __object_get(obj);
-        spin_unlock_irqrestore(&amp;cache_lock, flags);
+        atomic_inc(&amp;obj-&gt;refcnt);
 }

 /* Must be holding cache_lock */
@@ -65,7 +47,7 @@
 {
         BUG_ON(!obj);
         list_del(&amp;obj-&gt;list);
-        __object_put(obj);
+        object_put(obj);
         cache_num--;
 }

@@ -94,7 +76,7 @@
         strlcpy(obj-&gt;name, name, sizeof(obj-&gt;name));
         obj-&gt;id = id;
         obj-&gt;popularity = 0;
-        obj-&gt;refcnt = 1; /* The cache holds a reference */
+        atomic_set(&amp;obj-&gt;refcnt, 1); /* The cache holds a reference */

         spin_lock_irqsave(&amp;cache_lock, flags);
         __cache_add(obj);
@@ -119,7 +101,7 @@
         spin_lock_irqsave(&amp;cache_lock, flags);
         obj = __cache_find(id);
         if (obj)
-                __object_get(obj);
+                object_get(obj);
         spin_unlock_irqrestore(&amp;cache_lock, flags);
         return obj;
 }
</programlisting>
</sect2>
</sect1>

   <sect1 id="examples-lock-per-obj">
    <title>Protecting The Objects Themselves</title>
    <para>
In these examples, we assumed that the objects (except the reference
counts) never changed once they are created.  If we wanted to allow
the name to change, there are three possibilities:
    </para>
    <itemizedlist>
      <listitem>
	<para>
You can make <symbol>cache_lock</symbol> non-static, and tell people
to grab that lock before changing the name in any object.
        </para>
      </listitem>
      <listitem>
        <para>
You can provide a <function>cache_obj_rename</function> which grabs
this lock and changes the name for the caller, and tell everyone to
use that function.
        </para>
      </listitem>
      <listitem>
        <para>
You can make the <symbol>cache_lock</symbol> protect only the cache
itself, and use another lock to protect the name.
        </para>
      </listitem>
    </itemizedlist>

      <para>
Theoretically, you can make the locks as fine-grained as one lock for
every field, for every object.  In practice, the most common variants
are:
</para>
    <itemizedlist>
      <listitem>
	<para>
One lock which protects the infrastructure (the <symbol>cache</symbol>
list in this example) and all the objects.  This is what we have done
so far.
	</para>
      </listitem>
      <listitem>
        <para>
One lock which protects the infrastructure (including the list
pointers inside the objects), and one lock inside the object which
protects the rest of that object.
        </para>
      </listitem>
      <listitem>
        <para>
Multiple locks to protect the infrastructure (eg. one lock per hash
chain), possibly with a separate per-object lock.
        </para>
      </listitem>
    </itemizedlist>

<para>
Here is the "lock-per-object" implementation:
</para>
<programlisting>
--- cache.c.refcnt-atomic	2003-12-11 15:50:54.000000000 +1100
+++ cache.c.perobjectlock	2003-12-11 17:15:03.000000000 +1100
@@ -6,11 +6,17 @@

 struct object
 {
+        /* These two protected by cache_lock. */
         struct list_head list;
+        int popularity;
+
         atomic_t refcnt;
+
+        /* Doesn't change once created. */
         int id;
+
+        spinlock_t lock; /* Protects the name */
         char name[32];
-        int popularity;
 };

 static spinlock_t cache_lock = SPIN_LOCK_UNLOCKED;
@@ -77,6 +84,7 @@
         obj-&gt;id = id;
         obj-&gt;popularity = 0;
         atomic_set(&amp;obj-&gt;refcnt, 1); /* The cache holds a reference */
+        spin_lock_init(&amp;obj-&gt;lock);

         spin_lock_irqsave(&amp;cache_lock, flags);