Using RCU hlist_nulls to protect list and objects

This section describes how to use hlist_nulls toprotect read-mostly linked lists andobjects using SLAB_TYPESAFE_BY_RCU allocations.

Please read the basics inUsing RCU to Protect Read-Mostly Linked Lists.

Using ‘nulls’

Using special makers (called ‘nulls’) is a convenient wayto solve following problem.

Without ‘nulls’, a typical RCU linked list managing objects which areallocated with SLAB_TYPESAFE_BY_RCU kmem_cache can use the followingalgorithms. Following examples assume ‘obj’ is a pointer to suchobjects, which is having below type.

struct object {  struct hlist_node obj_node;  atomic_t refcnt;  unsigned int key;};

1) Lookup algorithm

begin:rcu_read_lock();obj = lockless_lookup(key);if (obj) {  if (!try_get_ref(obj)) { // might fail for free objects    rcu_read_unlock();    goto begin;  }  /*  * Because a writer could delete object, and a writer could  * reuse these object before the RCU grace period, we  * must check key after getting the reference on object  */  if (obj->key != key) { // not the object we expected    put_ref(obj);    rcu_read_unlock();    goto begin;  }}rcu_read_unlock();

Beware that lockless_lookup(key) cannot use traditionalhlist_for_each_entry_rcu()but a version with an additional memory barrier (smp_rmb())

lockless_lookup(key){  struct hlist_node *node, *next;  for (pos = rcu_dereference((head)->first);       pos && ({ next = pos->next; smp_rmb(); prefetch(next); 1; }) &&       ({ obj = hlist_entry(pos, typeof(*obj), obj_node); 1; });       pos = rcu_dereference(next))    if (obj->key == key)      return obj;  return NULL;}

And note the traditionalhlist_for_each_entry_rcu() misses thissmp_rmb():

struct hlist_node *node;for (pos = rcu_dereference((head)->first);     pos && ({ prefetch(pos->next); 1; }) &&     ({ obj = hlist_entry(pos, typeof(*obj), obj_node); 1; });     pos = rcu_dereference(pos->next))  if (obj->key == key)    return obj;return NULL;

Quoting Corey Minyard:

"If the object is moved from one list to another list in-between thetime the hash is calculated and the next field is accessed, and theobject has moved to the end of a new list, the traversal will notcomplete properly on the list it should have, since the object willbe on the end of the new list and there's not a way to tell it's on anew list and restart the list traversal. I think that this can besolved by pre-fetching the "next" field (with proper barriers) beforechecking the key."

2) Insertion algorithm

We need to make sure a reader cannot read the new ‘obj->obj_node.next’ valueand previous value of ‘obj->key’. Otherwise, an item could be deletedfrom a chain, and inserted into another chain. If new chain was emptybefore the move, ‘next’ pointer is NULL, and lockless reader can notdetect the fact that it missed following items in original chain.

/* * Please note that new inserts are done at the head of list, * not in the middle or end. */obj = kmem_cache_alloc(...);lock_chain(); // typically a spin_lock()obj->key = key;atomic_set_release(&obj->refcnt, 1); // key before refcnthlist_add_head_rcu(&obj->obj_node, list);unlock_chain(); // typically a spin_unlock()

3) Removal algorithm

Nothing special here, we can use a standard RCU hlist deletion.But thanks to SLAB_TYPESAFE_BY_RCU, beware a deleted object can be reusedvery very fast (before the end of RCU grace period)

if (put_last_reference_on(obj) {  lock_chain(); // typically a spin_lock()  hlist_del_init_rcu(&obj->obj_node);  unlock_chain(); // typically a spin_unlock()  kmem_cache_free(cachep, obj);}

Avoiding extra smp_rmb()

With hlist_nulls we can avoid extrasmp_rmb() inlockless_lookup().

For example, if we choose to store the slot number as the ‘nulls’end-of-list marker for each slot of the hash table, we can detecta race (some writer did a delete and/or a move of an objectto another chain) checking the final ‘nulls’ value ifthe lookup met the end of chain. If final ‘nulls’ valueis not the slot number, then we must restart the lookup atthe beginning. If the object was moved to the same chain,then the reader doesn’t care: It might occasionallyscan the list again without harm.

Note that using hlist_nulls means the type of ‘obj_node’ field of‘structobject’ becomes ‘structhlist_nulls_node’.

1) lookup algorithm

head = &table[slot];begin:rcu_read_lock();hlist_nulls_for_each_entry_rcu(obj, node, head, obj_node) {  if (obj->key == key) {    if (!try_get_ref(obj)) { // might fail for free objects      rcu_read_unlock();      goto begin;    }    if (obj->key != key) { // not the object we expected      put_ref(obj);      rcu_read_unlock();      goto begin;    }    goto out;  }}// If the nulls value we got at the end of this lookup is// not the expected one, we must restart lookup.// We probably met an item that was moved to another chain.if (get_nulls_value(node) != slot) {  put_ref(obj);  rcu_read_unlock();  goto begin;}obj = NULL;out:rcu_read_unlock();

2) Insert algorithm

Same to the above one, but useshlist_nulls_add_head_rcu() instead ofhlist_add_head_rcu().

/* * Please note that new inserts are done at the head of list, * not in the middle or end. */obj = kmem_cache_alloc(cachep);lock_chain(); // typically a spin_lock()obj->key = key;atomic_set_release(&obj->refcnt, 1); // key before refcnt/* * insert obj in RCU way (readers might be traversing chain) */hlist_nulls_add_head_rcu(&obj->obj_node, list);unlock_chain(); // typically a spin_unlock()