rculist_nulls.rst 5.5 KB

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