Documentation/RCU/rculist_nulls.rst

   1 .. SPDX-License-Identifier: GPL-2.0
   2
   3 =================================================
   4 Using RCU hlist_nulls to protect list and objects
   5 =================================================
   6
   7 This section describes how to use hlist_nulls to
   8 protect read-mostly linked lists and
   9 objects using SLAB_TYPESAFE_BY_RCU allocations.
  10
  11 Please read the basics in listRCU.rst.
  12
  13 Using 'nulls'
  14 =============
  15
  16 Using special makers (called 'nulls') is a convenient way
  17 to solve following problem.
  18
  19 Without 'nulls', a typical RCU linked list managing objects which are
  20 allocated with SLAB_TYPESAFE_BY_RCU kmem_cache can use the following
  21 algorithms.  Following examples assume 'obj' is a pointer to such
  22 objects, which is having below type.
  23
  24 ::
  25
  26   struct object {
  27     struct hlist_node obj_node;
  28     atomic_t refcnt;
  29     unsigned int key;
  30   };
  31
  32 1) Lookup algorithm
  33 -------------------
  34
  35 ::
  36
  37   begin:
  38   rcu_read_lock();
  39   obj = lockless_lookup(key);
  40   if (obj) {
  41     if (!try_get_ref(obj)) { // might fail for free objects
  42       rcu_read_unlock();
  43       goto begin;
  44     }
  45     /*
  46     * Because a writer could delete object, and a writer could
  47     * reuse these object before the RCU grace period, we
  48     * must check key after getting the reference on object
  49     */
  50     if (obj->key != key) { // not the object we expected
  51       put_ref(obj);
  52       rcu_read_unlock();
  53       goto begin;
  54     }
  55   }
  56   rcu_read_unlock();
  57
  58 Beware that lockless_lookup(key) cannot use traditional hlist_for_each_entry_rcu()
  59 but a version with an additional memory barrier (smp_rmb())
  60
  61 ::
  62
  63   lockless_lookup(key)
  64   {
  65     struct hlist_node *node, *next;
  66     for (pos = rcu_dereference((head)->first);
  67          pos && ({ next = pos->next; smp_rmb(); prefetch(next); 1; }) &&
  68          ({ obj = hlist_entry(pos, typeof(*obj), obj_node); 1; });
  69          pos = rcu_dereference(next))
  70       if (obj->key == key)
  71         return obj;
  72     return NULL;
  73   }
  74
  75 And note the traditional hlist_for_each_entry_rcu() misses this smp_rmb()::
  76
  77   struct hlist_node *node;
  78   for (pos = rcu_dereference((head)->first);
  79        pos && ({ prefetch(pos->next); 1; }) &&
  80        ({ obj = hlist_entry(pos, typeof(*obj), obj_node); 1; });
  81        pos = rcu_dereference(pos->next))
  82     if (obj->key == key)
  83       return obj;
  84   return NULL;
  85
  86 Quoting Corey Minyard::
  87
  88   "If the object is moved from one list to another list in-between the
  89   time the hash is calculated and the next field is accessed, and the
  90   object has moved to the end of a new list, the traversal will not
  91   complete properly on the list it should have, since the object will
  92   be on the end of the new list and there's not a way to tell it's on a
  93   new list and restart the list traversal. I think that this can be
  94   solved by pre-fetching the "next" field (with proper barriers) before
  95   checking the key."
  96
  97 2) Insertion algorithm
  98 ----------------------
  99
 100 We need to make sure a reader cannot read the new 'obj->obj_node.next' value
 101 and previous value of 'obj->key'. Otherwise, an item could be deleted
 102 from a chain, and inserted into another chain. If new chain was empty
 103 before the move, 'next' pointer is NULL, and lockless reader can not
 104 detect the fact that it missed following items in original chain.
 105
 106 ::
 107
 108   /*
 109    * Please note that new inserts are done at the head of list,
 110    * not in the middle or end.
 111    */
 112   obj = kmem_cache_alloc(...);
 113   lock_chain(); // typically a spin_lock()
 114   obj->key = key;
 115   atomic_set_release(&obj->refcnt, 1); // key before refcnt
 116   hlist_add_head_rcu(&obj->obj_node, list);
 117   unlock_chain(); // typically a spin_unlock()
 118
 119
 120 3) Removal algorithm
 121 --------------------
 122
 123 Nothing special here, we can use a standard RCU hlist deletion.
 124 But thanks to SLAB_TYPESAFE_BY_RCU, beware a deleted object can be reused
 125 very very fast (before the end of RCU grace period)
 126
 127 ::
 128
 129   if (put_last_reference_on(obj) {
 130     lock_chain(); // typically a spin_lock()
 131     hlist_del_init_rcu(&obj->obj_node);
 132     unlock_chain(); // typically a spin_unlock()
 133     kmem_cache_free(cachep, obj);
 134   }
 135
 136
 137
 138 --------------------------------------------------------------------------
 139
 140 Avoiding extra smp_rmb()
 141 ========================
 142
 143 With hlist_nulls we can avoid extra smp_rmb() in lockless_lookup().
 144
 145 For example, if we choose to store the slot number as the 'nulls'
 146 end-of-list marker for each slot of the hash table, we can detect
 147 a race (some writer did a delete and/or a move of an object
 148 to another chain) checking the final 'nulls' value if
 149 the lookup met the end of chain. If final 'nulls' value
 150 is not the slot number, then we must restart the lookup at
 151 the beginning. If the object was moved to the same chain,
 152 then the reader doesn't care: It might occasionally
 153 scan the list again without harm.
 154
 155 Note that using hlist_nulls means the type of 'obj_node' field of
 156 'struct object' becomes 'struct hlist_nulls_node'.
 157
 158
 159 1) lookup algorithm
 160 -------------------
 161
 162 ::
 163
 164   head = &table[slot];
 165   begin:
 166   rcu_read_lock();
 167   hlist_nulls_for_each_entry_rcu(obj, node, head, obj_node) {
 168     if (obj->key == key) {
 169       if (!try_get_ref(obj)) { // might fail for free objects
 170         rcu_read_unlock();
 171         goto begin;
 172       }
 173       if (obj->key != key) { // not the object we expected
 174         put_ref(obj);
 175         rcu_read_unlock();
 176         goto begin;
 177       }
 178       goto out;
 179     }
 180   }
 181
 182   // If the nulls value we got at the end of this lookup is
 183   // not the expected one, we must restart lookup.
 184   // We probably met an item that was moved to another chain.
 185   if (get_nulls_value(node) != slot) {
 186     put_ref(obj);
 187     rcu_read_unlock();
 188     goto begin;
 189   }
 190   obj = NULL;
 191
 192   out:
 193   rcu_read_unlock();
 194
 195 2) Insert algorithm
 196 -------------------
 197
 198 Same to the above one, but uses hlist_nulls_add_head_rcu() instead of
 199 hlist_add_head_rcu().
 200
 201 ::
 202
 203   /*
 204    * Please note that new inserts are done at the head of list,
 205    * not in the middle or end.
 206    */
 207   obj = kmem_cache_alloc(cachep);
 208   lock_chain(); // typically a spin_lock()
 209   obj->key = key;
 210   atomic_set_release(&obj->refcnt, 1); // key before refcnt
 211   /*
 212    * insert obj in RCU way (readers might be traversing chain)
 213    */
 214   hlist_nulls_add_head_rcu(&obj->obj_node, list);
 215   unlock_chain(); // typically a spin_unlock()