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