Documentation/RCU/rcuref.txt

   1 Refcounter framework for elements of lists/arrays protected by
   2 RCU.
   3
   4 Refcounting on elements of  lists which are protected by traditional
   5 reader/writer spinlocks or semaphores are straight forward as in:
   6
   7 1.                                      2.
   8 add()                                   search_and_reference()
   9 {                                       {
  10         alloc_object                            read_lock(&list_lock);
  11         ...                                     search_for_element
  12         atomic_set(&el->rc, 1);                 atomic_inc(&el->rc);
  13         write_lock(&list_lock);                 ...
  14         add_element                             read_unlock(&list_lock);
  15         ...                                     ...
  16         write_unlock(&list_lock);       }
  17 }
  18
  19 3.                                      4.
  20 release_referenced()                    delete()
  21 {                                       {
  22         ...                             write_lock(&list_lock);
  23         atomic_dec(&el->rc, relfunc)    ...
  24         ...                             delete_element
  25 }                                       write_unlock(&list_lock);
  26                                         ...
  27                                         if (atomic_dec_and_test(&el->rc))
  28                                                 kfree(el);
  29                                         ...
  30                                         }
  31
  32 If this list/array is made lock free using rcu as in changing the
  33 write_lock in add() and delete() to spin_lock and changing read_lock
  34 in search_and_reference to rcu_read_lock(), the rcuref_get in
  35 search_and_reference could potentially hold reference to an element which
  36 has already been deleted from the list/array.  rcuref_lf_get_rcu takes
  37 care of this scenario. search_and_reference should look as;
  38
  39 1.                                      2.
  40 add()                                   search_and_reference()
  41 {                                       {
  42         alloc_object                            rcu_read_lock();
  43         ...                                     search_for_element
  44         atomic_set(&el->rc, 1);                 if (rcuref_inc_lf(&el->rc)) {
  45         write_lock(&list_lock);                         rcu_read_unlock();
  46                                                         return FAIL;
  47         add_element                             }
  48         ...                                     ...
  49         write_unlock(&list_lock);               rcu_read_unlock();
  50 }                                       }
  51 3.                                      4.
  52 release_referenced()                    delete()
  53 {                                       {
  54         ...                             write_lock(&list_lock);
  55         rcuref_dec(&el->rc, relfunc)    ...
  56         ...                             delete_element
  57 }                                       write_unlock(&list_lock);
  58                                         ...
  59                                         if (rcuref_dec_and_test(&el->rc))
  60                                                 call_rcu(&el->head, el_free);
  61                                         ...
  62                                         }
  63
  64 Sometimes, reference to the element need to be obtained in the
  65 update (write) stream.  In such cases, rcuref_inc_lf might be an overkill
  66 since the spinlock serialising list updates are held. rcuref_inc
  67 is to be used in such cases.
  68 For arches which do not have cmpxchg rcuref_inc_lf
  69 api uses a hashed spinlock implementation and the same hashed spinlock
  70 is acquired in all rcuref_xxx primitives to preserve atomicity.
  71 Note: Use rcuref_inc api only if you need to use rcuref_inc_lf on the
  72 refcounter atleast at one place.  Mixing rcuref_inc and atomic_xxx api
  73 might lead to races. rcuref_inc_lf() must be used in lockfree
  74 RCU critical sections only.