diff options
Diffstat (limited to 'Documentation/RCU/rculist_nulls.rst')
| -rw-r--r-- | Documentation/RCU/rculist_nulls.rst | 139 |
1 files changed, 77 insertions, 62 deletions
diff --git a/Documentation/RCU/rculist_nulls.rst b/Documentation/RCU/rculist_nulls.rst index a9fc774bc400..21e40fcc08de 100644 --- a/Documentation/RCU/rculist_nulls.rst +++ b/Documentation/RCU/rculist_nulls.rst @@ -8,29 +8,40 @@ This section describes how to use hlist_nulls to protect read-mostly linked lists and objects using SLAB_TYPESAFE_BY_RCU allocations. -Please read the basics in Documentation/RCU/listRCU.rst +Please read the basics in listRCU.rst. Using 'nulls' ============= Using special makers (called 'nulls') is a convenient way -to solve following problem : +to solve following problem. -A typical RCU linked list managing objects which are -allocated with SLAB_TYPESAFE_BY_RCU kmem_cache can -use following algos : +Without 'nulls', a typical RCU linked list managing objects which are +allocated with SLAB_TYPESAFE_BY_RCU kmem_cache can use the following +algorithms. Following examples assume 'obj' is a pointer to such +objects, which is having below type. -1) Lookup algo --------------- +:: + + struct object { + struct hlist_node obj_node; + atomic_t refcnt; + unsigned int key; + }; + +1) Lookup algorithm +------------------- :: - rcu_read_lock() begin: + rcu_read_lock(); obj = lockless_lookup(key); if (obj) { - if (!try_get_ref(obj)) // might fail for free objects + 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 @@ -38,6 +49,7 @@ use following algos : */ if (obj->key != key) { // not the object we expected put_ref(obj); + rcu_read_unlock(); goto begin; } } @@ -52,9 +64,9 @@ but a version with an additional memory barrier (smp_rmb()) { struct hlist_node *node, *next; for (pos = rcu_dereference((head)->first); - pos && ({ next = pos->next; smp_rmb(); prefetch(next); 1; }) && - ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1; }); - pos = rcu_dereference(next)) + 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; @@ -64,11 +76,11 @@ And note the traditional hlist_for_each_entry_rcu() misses this smp_rmb():: struct hlist_node *node; for (pos = rcu_dereference((head)->first); - pos && ({ prefetch(pos->next); 1; }) && - ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1; }); - pos = rcu_dereference(pos->next)) - if (obj->key == key) - return obj; + 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:: @@ -82,36 +94,32 @@ Quoting Corey Minyard:: solved by pre-fetching the "next" field (with proper barriers) before checking the key." -2) Insert algo --------------- +2) Insertion algorithm +---------------------- -We need to make sure a reader cannot read the new 'obj->obj_next' value -and previous value of 'obj->key'. Or else, an item could be deleted +We need to make sure a reader cannot read the new 'obj->obj_node.next' value +and previous value of 'obj->key'. Otherwise, an item could be deleted from a chain, and inserted into another chain. If new chain was empty -before the move, 'next' pointer is NULL, and lockless reader can -not detect it missed following items in original chain. +before the move, 'next' pointer is NULL, and lockless reader can not +detect 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. - */ + * 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; - /* - * we need to make sure obj->key is updated before obj->next - * or obj->refcnt - */ - smp_wmb(); - atomic_set(&obj->refcnt, 1); + atomic_set_release(&obj->refcnt, 1); // key before refcnt hlist_add_head_rcu(&obj->obj_node, list); unlock_chain(); // typically a spin_unlock() -3) Remove algo --------------- +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 reused very very fast (before the end of RCU grace period) @@ -132,8 +140,7 @@ very very fast (before the end of RCU grace period) Avoiding extra smp_rmb() ======================== -With hlist_nulls we can avoid extra smp_rmb() in lockless_lookup() -and extra smp_wmb() in insert function. +With hlist_nulls we can avoid extra smp_rmb() in lockless_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 detect @@ -142,59 +149,67 @@ to another chain) checking the final 'nulls' value if the lookup met the end of chain. If final 'nulls' value is not the slot number, then we must restart the lookup at the beginning. If the object was moved to the same chain, -then the reader doesn't care : It might eventually +then the reader doesn't care: It might occasionally scan the list again without harm. +Note that using hlist_nulls means the type of 'obj_node' field of +'struct object' becomes 'struct hlist_nulls_node'. -1) lookup algo --------------- + +1) lookup algorithm +------------------- :: head = &table[slot]; - rcu_read_lock(); begin: - hlist_nulls_for_each_entry_rcu(obj, node, head, member) { + 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 + 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; + 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; } - /* - * 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) - goto begin; obj = NULL; out: rcu_read_unlock(); -2) Insert function ------------------- +2) Insert algorithm +------------------- + +Same to the above one, but uses hlist_nulls_add_head_rcu() instead of +hlist_add_head_rcu(). :: /* - * Please note that new inserts are done at the head of list, - * not in the middle or end. - */ + * 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 /* - * changes to obj->key must be visible before refcnt one - */ - smp_wmb(); - atomic_set(&obj->refcnt, 1); - /* - * insert obj in RCU way (readers might be traversing chain) - */ + * 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() |