1 #ifndef _LINUX_RCULIST_H
2 #define _LINUX_RCULIST_H
7 * RCU-protected list version
9 #include <linux/list.h>
10 #include <linux/rcupdate.h>
13 * Why is there no list_empty_rcu()? Because list_empty() serves this
14 * purpose. The list_empty() function fetches the RCU-protected pointer
15 * and compares it to the address of the list head, but neither dereferences
16 * this pointer itself nor provides this pointer to the caller. Therefore,
17 * it is not necessary to use rcu_dereference(), so that list_empty() can
18 * be used anywhere you would want to use a list_empty_rcu().
22 * return the ->next pointer of a list_head in an rcu safe
23 * way, we must not access it directly
25 #define list_next_rcu(list) (*((struct list_head __rcu **)(&(list)->next)))
28 * Insert a new entry between two known consecutive entries.
30 * This is only for internal list manipulation where we know
31 * the prev/next entries already!
33 static inline void __list_add_rcu(struct list_head *new,
34 struct list_head *prev, struct list_head *next)
38 rcu_assign_pointer(list_next_rcu(prev), new);
43 * list_add_rcu - add a new entry to rcu-protected list
44 * @new: new entry to be added
45 * @head: list head to add it after
47 * Insert a new entry after the specified head.
48 * This is good for implementing stacks.
50 * The caller must take whatever precautions are necessary
51 * (such as holding appropriate locks) to avoid racing
52 * with another list-mutation primitive, such as list_add_rcu()
53 * or list_del_rcu(), running on this same list.
54 * However, it is perfectly legal to run concurrently with
55 * the _rcu list-traversal primitives, such as
56 * list_for_each_entry_rcu().
58 static inline void list_add_rcu(struct list_head *new, struct list_head *head)
60 __list_add_rcu(new, head, head->next);
64 * list_add_tail_rcu - add a new entry to rcu-protected list
65 * @new: new entry to be added
66 * @head: list head to add it before
68 * Insert a new entry before the specified head.
69 * This is useful for implementing queues.
71 * The caller must take whatever precautions are necessary
72 * (such as holding appropriate locks) to avoid racing
73 * with another list-mutation primitive, such as list_add_tail_rcu()
74 * or list_del_rcu(), running on this same list.
75 * However, it is perfectly legal to run concurrently with
76 * the _rcu list-traversal primitives, such as
77 * list_for_each_entry_rcu().
79 static inline void list_add_tail_rcu(struct list_head *new,
80 struct list_head *head)
82 __list_add_rcu(new, head->prev, head);
86 * list_del_rcu - deletes entry from list without re-initialization
87 * @entry: the element to delete from the list.
89 * Note: list_empty() on entry does not return true after this,
90 * the entry is in an undefined state. It is useful for RCU based
93 * In particular, it means that we can not poison the forward
94 * pointers that may still be used for walking the list.
96 * The caller must take whatever precautions are necessary
97 * (such as holding appropriate locks) to avoid racing
98 * with another list-mutation primitive, such as list_del_rcu()
99 * or list_add_rcu(), running on this same list.
100 * However, it is perfectly legal to run concurrently with
101 * the _rcu list-traversal primitives, such as
102 * list_for_each_entry_rcu().
104 * Note that the caller is not permitted to immediately free
105 * the newly deleted entry. Instead, either synchronize_rcu()
106 * or call_rcu() must be used to defer freeing until an RCU
107 * grace period has elapsed.
109 static inline void list_del_rcu(struct list_head *entry)
111 __list_del(entry->prev, entry->next);
112 entry->prev = LIST_POISON2;
116 * hlist_del_init_rcu - deletes entry from hash list with re-initialization
117 * @n: the element to delete from the hash list.
119 * Note: list_unhashed() on the node return true after this. It is
120 * useful for RCU based read lockfree traversal if the writer side
121 * must know if the list entry is still hashed or already unhashed.
123 * In particular, it means that we can not poison the forward pointers
124 * that may still be used for walking the hash list and we can only
125 * zero the pprev pointer so list_unhashed() will return true after
128 * The caller must take whatever precautions are necessary (such as
129 * holding appropriate locks) to avoid racing with another
130 * list-mutation primitive, such as hlist_add_head_rcu() or
131 * hlist_del_rcu(), running on this same list. However, it is
132 * perfectly legal to run concurrently with the _rcu list-traversal
133 * primitives, such as hlist_for_each_entry_rcu().
135 static inline void hlist_del_init_rcu(struct hlist_node *n)
137 if (!hlist_unhashed(n)) {
144 * list_replace_rcu - replace old entry by new one
145 * @old : the element to be replaced
146 * @new : the new element to insert
148 * The @old entry will be replaced with the @new entry atomically.
149 * Note: @old should not be empty.
151 static inline void list_replace_rcu(struct list_head *old,
152 struct list_head *new)
154 new->next = old->next;
155 new->prev = old->prev;
156 rcu_assign_pointer(list_next_rcu(new->prev), new);
157 new->next->prev = new;
158 old->prev = LIST_POISON2;
162 * list_splice_init_rcu - splice an RCU-protected list into an existing list.
163 * @list: the RCU-protected list to splice
164 * @head: the place in the list to splice the first list into
165 * @sync: function to sync: synchronize_rcu(), synchronize_sched(), ...
167 * @head can be RCU-read traversed concurrently with this function.
169 * Note that this function blocks.
171 * Important note: the caller must take whatever action is necessary to
172 * prevent any other updates to @head. In principle, it is possible
173 * to modify the list as soon as sync() begins execution.
174 * If this sort of thing becomes necessary, an alternative version
175 * based on call_rcu() could be created. But only if -really-
176 * needed -- there is no shortage of RCU API members.
178 static inline void list_splice_init_rcu(struct list_head *list,
179 struct list_head *head,
182 struct list_head *first = list->next;
183 struct list_head *last = list->prev;
184 struct list_head *at = head->next;
186 if (list_empty(list))
189 /* "first" and "last" tracking list, so initialize it. */
191 INIT_LIST_HEAD(list);
194 * At this point, the list body still points to the source list.
195 * Wait for any readers to finish using the list before splicing
196 * the list body into the new list. Any new readers will see
203 * Readers are finished with the source list, so perform splice.
204 * The order is important if the new list is global and accessible
205 * to concurrent RCU readers. Note that RCU readers are not
206 * permitted to traverse the prev pointers without excluding
211 rcu_assign_pointer(list_next_rcu(head), first);
217 * list_entry_rcu - get the struct for this entry
218 * @ptr: the &struct list_head pointer.
219 * @type: the type of the struct this is embedded in.
220 * @member: the name of the list_struct within the struct.
222 * This primitive may safely run concurrently with the _rcu list-mutation
223 * primitives such as list_add_rcu() as long as it's guarded by rcu_read_lock().
225 #define list_entry_rcu(ptr, type, member) \
226 ({typeof (*ptr) __rcu *__ptr = (typeof (*ptr) __rcu __force *)ptr; \
227 container_of((typeof(ptr))rcu_dereference_raw(__ptr), type, member); \
231 * list_first_entry_rcu - get the first element from a list
232 * @ptr: the list head to take the element from.
233 * @type: the type of the struct this is embedded in.
234 * @member: the name of the list_struct within the struct.
236 * Note, that list is expected to be not empty.
238 * This primitive may safely run concurrently with the _rcu list-mutation
239 * primitives such as list_add_rcu() as long as it's guarded by rcu_read_lock().
241 #define list_first_entry_rcu(ptr, type, member) \
242 list_entry_rcu((ptr)->next, type, member)
245 * list_first_or_null_rcu - get the first element from a list
246 * @ptr: the list head to take the element from.
247 * @type: the type of the struct this is embedded in.
248 * @member: the name of the list_struct within the struct.
250 * Note that if the list is empty, it returns NULL.
252 * This primitive may safely run concurrently with the _rcu list-mutation
253 * primitives such as list_add_rcu() as long as it's guarded by rcu_read_lock().
255 #define list_first_or_null_rcu(ptr, type, member) \
256 ({struct list_head *__ptr = (ptr); \
257 struct list_head *__next = ACCESS_ONCE(__ptr->next); \
258 likely(__ptr != __next) ? \
259 list_entry_rcu(__next, type, member) : NULL; \
263 * list_for_each_entry_rcu - iterate over rcu list of given type
264 * @pos: the type * to use as a loop cursor.
265 * @head: the head for your list.
266 * @member: the name of the list_struct within the struct.
268 * This list-traversal primitive may safely run concurrently with
269 * the _rcu list-mutation primitives such as list_add_rcu()
270 * as long as the traversal is guarded by rcu_read_lock().
272 #define list_for_each_entry_rcu(pos, head, member) \
273 for (pos = list_entry_rcu((head)->next, typeof(*pos), member); \
274 &pos->member != (head); \
275 pos = list_entry_rcu(pos->member.next, typeof(*pos), member))
279 * list_for_each_continue_rcu
280 * @pos: the &struct list_head to use as a loop cursor.
281 * @head: the head for your list.
283 * Iterate over an rcu-protected list, continuing after current point.
285 * This list-traversal primitive may safely run concurrently with
286 * the _rcu list-mutation primitives such as list_add_rcu()
287 * as long as the traversal is guarded by rcu_read_lock().
289 #define list_for_each_continue_rcu(pos, head) \
290 for ((pos) = rcu_dereference_raw(list_next_rcu(pos)); \
292 (pos) = rcu_dereference_raw(list_next_rcu(pos)))
295 * list_for_each_entry_continue_rcu - continue iteration over list of given type
296 * @pos: the type * to use as a loop cursor.
297 * @head: the head for your list.
298 * @member: the name of the list_struct within the struct.
300 * Continue to iterate over list of given type, continuing after
301 * the current position.
303 #define list_for_each_entry_continue_rcu(pos, head, member) \
304 for (pos = list_entry_rcu(pos->member.next, typeof(*pos), member); \
305 &pos->member != (head); \
306 pos = list_entry_rcu(pos->member.next, typeof(*pos), member))
309 * hlist_del_rcu - deletes entry from hash list without re-initialization
310 * @n: the element to delete from the hash list.
312 * Note: list_unhashed() on entry does not return true after this,
313 * the entry is in an undefined state. It is useful for RCU based
314 * lockfree traversal.
316 * In particular, it means that we can not poison the forward
317 * pointers that may still be used for walking the hash list.
319 * The caller must take whatever precautions are necessary
320 * (such as holding appropriate locks) to avoid racing
321 * with another list-mutation primitive, such as hlist_add_head_rcu()
322 * or hlist_del_rcu(), running on this same list.
323 * However, it is perfectly legal to run concurrently with
324 * the _rcu list-traversal primitives, such as
325 * hlist_for_each_entry().
327 static inline void hlist_del_rcu(struct hlist_node *n)
330 n->pprev = LIST_POISON2;
334 * hlist_replace_rcu - replace old entry by new one
335 * @old : the element to be replaced
336 * @new : the new element to insert
338 * The @old entry will be replaced with the @new entry atomically.
340 static inline void hlist_replace_rcu(struct hlist_node *old,
341 struct hlist_node *new)
343 struct hlist_node *next = old->next;
346 new->pprev = old->pprev;
347 rcu_assign_pointer(*(struct hlist_node __rcu **)new->pprev, new);
349 new->next->pprev = &new->next;
350 old->pprev = LIST_POISON2;
354 * return the first or the next element in an RCU protected hlist
356 #define hlist_first_rcu(head) (*((struct hlist_node __rcu **)(&(head)->first)))
357 #define hlist_next_rcu(node) (*((struct hlist_node __rcu **)(&(node)->next)))
358 #define hlist_pprev_rcu(node) (*((struct hlist_node __rcu **)((node)->pprev)))
362 * @n: the element to add to the hash list.
363 * @h: the list to add to.
366 * Adds the specified element to the specified hlist,
367 * while permitting racing traversals.
369 * The caller must take whatever precautions are necessary
370 * (such as holding appropriate locks) to avoid racing
371 * with another list-mutation primitive, such as hlist_add_head_rcu()
372 * or hlist_del_rcu(), running on this same list.
373 * However, it is perfectly legal to run concurrently with
374 * the _rcu list-traversal primitives, such as
375 * hlist_for_each_entry_rcu(), used to prevent memory-consistency
376 * problems on Alpha CPUs. Regardless of the type of CPU, the
377 * list-traversal primitive must be guarded by rcu_read_lock().
379 static inline void hlist_add_head_rcu(struct hlist_node *n,
380 struct hlist_head *h)
382 struct hlist_node *first = h->first;
385 n->pprev = &h->first;
386 rcu_assign_pointer(hlist_first_rcu(h), n);
388 first->pprev = &n->next;
392 * hlist_add_before_rcu
393 * @n: the new element to add to the hash list.
394 * @next: the existing element to add the new element before.
397 * Adds the specified element to the specified hlist
398 * before the specified node while permitting racing traversals.
400 * The caller must take whatever precautions are necessary
401 * (such as holding appropriate locks) to avoid racing
402 * with another list-mutation primitive, such as hlist_add_head_rcu()
403 * or hlist_del_rcu(), running on this same list.
404 * However, it is perfectly legal to run concurrently with
405 * the _rcu list-traversal primitives, such as
406 * hlist_for_each_entry_rcu(), used to prevent memory-consistency
407 * problems on Alpha CPUs.
409 static inline void hlist_add_before_rcu(struct hlist_node *n,
410 struct hlist_node *next)
412 n->pprev = next->pprev;
414 rcu_assign_pointer(hlist_pprev_rcu(n), n);
415 next->pprev = &n->next;
419 * hlist_add_after_rcu
420 * @prev: the existing element to add the new element after.
421 * @n: the new element to add to the hash list.
424 * Adds the specified element to the specified hlist
425 * after the specified node while permitting racing traversals.
427 * The caller must take whatever precautions are necessary
428 * (such as holding appropriate locks) to avoid racing
429 * with another list-mutation primitive, such as hlist_add_head_rcu()
430 * or hlist_del_rcu(), running on this same list.
431 * However, it is perfectly legal to run concurrently with
432 * the _rcu list-traversal primitives, such as
433 * hlist_for_each_entry_rcu(), used to prevent memory-consistency
434 * problems on Alpha CPUs.
436 static inline void hlist_add_after_rcu(struct hlist_node *prev,
437 struct hlist_node *n)
439 n->next = prev->next;
440 n->pprev = &prev->next;
441 rcu_assign_pointer(hlist_next_rcu(prev), n);
443 n->next->pprev = &n->next;
446 #define __hlist_for_each_rcu(pos, head) \
447 for (pos = rcu_dereference(hlist_first_rcu(head)); \
449 pos = rcu_dereference(hlist_next_rcu(pos)))
452 * hlist_for_each_entry_rcu - iterate over rcu list of given type
453 * @tpos: the type * to use as a loop cursor.
454 * @pos: the &struct hlist_node to use as a loop cursor.
455 * @head: the head for your list.
456 * @member: the name of the hlist_node within the struct.
458 * This list-traversal primitive may safely run concurrently with
459 * the _rcu list-mutation primitives such as hlist_add_head_rcu()
460 * as long as the traversal is guarded by rcu_read_lock().
462 #define hlist_for_each_entry_rcu(tpos, pos, head, member) \
463 for (pos = rcu_dereference_raw(hlist_first_rcu(head)); \
465 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1; }); \
466 pos = rcu_dereference_raw(hlist_next_rcu(pos)))
469 * hlist_for_each_entry_rcu_bh - iterate over rcu list of given type
470 * @tpos: the type * to use as a loop cursor.
471 * @pos: the &struct hlist_node to use as a loop cursor.
472 * @head: the head for your list.
473 * @member: the name of the hlist_node within the struct.
475 * This list-traversal primitive may safely run concurrently with
476 * the _rcu list-mutation primitives such as hlist_add_head_rcu()
477 * as long as the traversal is guarded by rcu_read_lock().
479 #define hlist_for_each_entry_rcu_bh(tpos, pos, head, member) \
480 for (pos = rcu_dereference_bh((head)->first); \
482 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1; }); \
483 pos = rcu_dereference_bh(pos->next))
486 * hlist_for_each_entry_continue_rcu - iterate over a hlist continuing after current point
487 * @tpos: the type * to use as a loop cursor.
488 * @pos: the &struct hlist_node to use as a loop cursor.
489 * @member: the name of the hlist_node within the struct.
491 #define hlist_for_each_entry_continue_rcu(tpos, pos, member) \
492 for (pos = rcu_dereference((pos)->next); \
494 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1; }); \
495 pos = rcu_dereference(pos->next))
498 * hlist_for_each_entry_continue_rcu_bh - iterate over a hlist continuing after current point
499 * @tpos: the type * to use as a loop cursor.
500 * @pos: the &struct hlist_node to use as a loop cursor.
501 * @member: the name of the hlist_node within the struct.
503 #define hlist_for_each_entry_continue_rcu_bh(tpos, pos, member) \
504 for (pos = rcu_dereference_bh((pos)->next); \
506 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1; }); \
507 pos = rcu_dereference_bh(pos->next))
510 #endif /* __KERNEL__ */