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 * INIT_LIST_HEAD_RCU - Initialize a list_head visible to RCU readers
23 * @list: list to be initialized
25 * You should instead use INIT_LIST_HEAD() for normal initialization and
26 * cleanup tasks, when readers have no access to the list being initialized.
27 * However, if the list being initialized is visible to readers, you
28 * need to keep the compiler from being too mischievous.
30 static inline void INIT_LIST_HEAD_RCU(struct list_head
*list
)
32 WRITE_ONCE(list
->next
, list
);
33 WRITE_ONCE(list
->prev
, list
);
37 * return the ->next pointer of a list_head in an rcu safe
38 * way, we must not access it directly
40 #define list_next_rcu(list) (*((struct list_head __rcu **)(&(list)->next)))
43 * Insert a new entry between two known consecutive entries.
45 * This is only for internal list manipulation where we know
46 * the prev/next entries already!
48 #ifndef CONFIG_DEBUG_LIST
49 static inline void __list_add_rcu(struct list_head
*new,
50 struct list_head
*prev
, struct list_head
*next
)
54 rcu_assign_pointer(list_next_rcu(prev
), new);
58 void __list_add_rcu(struct list_head
*new,
59 struct list_head
*prev
, struct list_head
*next
);
63 * list_add_rcu - add a new entry to rcu-protected list
64 * @new: new entry to be added
65 * @head: list head to add it after
67 * Insert a new entry after the specified head.
68 * This is good for implementing stacks.
70 * The caller must take whatever precautions are necessary
71 * (such as holding appropriate locks) to avoid racing
72 * with another list-mutation primitive, such as list_add_rcu()
73 * or list_del_rcu(), running on this same list.
74 * However, it is perfectly legal to run concurrently with
75 * the _rcu list-traversal primitives, such as
76 * list_for_each_entry_rcu().
78 static inline void list_add_rcu(struct list_head
*new, struct list_head
*head
)
80 __list_add_rcu(new, head
, head
->next
);
84 * list_add_tail_rcu - add a new entry to rcu-protected list
85 * @new: new entry to be added
86 * @head: list head to add it before
88 * Insert a new entry before the specified head.
89 * This is useful for implementing queues.
91 * The caller must take whatever precautions are necessary
92 * (such as holding appropriate locks) to avoid racing
93 * with another list-mutation primitive, such as list_add_tail_rcu()
94 * or list_del_rcu(), running on this same list.
95 * However, it is perfectly legal to run concurrently with
96 * the _rcu list-traversal primitives, such as
97 * list_for_each_entry_rcu().
99 static inline void list_add_tail_rcu(struct list_head
*new,
100 struct list_head
*head
)
102 __list_add_rcu(new, head
->prev
, head
);
106 * list_del_rcu - deletes entry from list without re-initialization
107 * @entry: the element to delete from the list.
109 * Note: list_empty() on entry does not return true after this,
110 * the entry is in an undefined state. It is useful for RCU based
111 * lockfree traversal.
113 * In particular, it means that we can not poison the forward
114 * pointers that may still be used for walking the list.
116 * The caller must take whatever precautions are necessary
117 * (such as holding appropriate locks) to avoid racing
118 * with another list-mutation primitive, such as list_del_rcu()
119 * or list_add_rcu(), running on this same list.
120 * However, it is perfectly legal to run concurrently with
121 * the _rcu list-traversal primitives, such as
122 * list_for_each_entry_rcu().
124 * Note that the caller is not permitted to immediately free
125 * the newly deleted entry. Instead, either synchronize_rcu()
126 * or call_rcu() must be used to defer freeing until an RCU
127 * grace period has elapsed.
129 static inline void list_del_rcu(struct list_head
*entry
)
131 __list_del_entry(entry
);
132 entry
->prev
= LIST_POISON2
;
136 * hlist_del_init_rcu - deletes entry from hash list with re-initialization
137 * @n: the element to delete from the hash list.
139 * Note: list_unhashed() on the node return true after this. It is
140 * useful for RCU based read lockfree traversal if the writer side
141 * must know if the list entry is still hashed or already unhashed.
143 * In particular, it means that we can not poison the forward pointers
144 * that may still be used for walking the hash list and we can only
145 * zero the pprev pointer so list_unhashed() will return true after
148 * The caller must take whatever precautions are necessary (such as
149 * holding appropriate locks) to avoid racing with another
150 * list-mutation primitive, such as hlist_add_head_rcu() or
151 * hlist_del_rcu(), running on this same list. However, it is
152 * perfectly legal to run concurrently with the _rcu list-traversal
153 * primitives, such as hlist_for_each_entry_rcu().
155 static inline void hlist_del_init_rcu(struct hlist_node
*n
)
157 if (!hlist_unhashed(n
)) {
164 * list_replace_rcu - replace old entry by new one
165 * @old : the element to be replaced
166 * @new : the new element to insert
168 * The @old entry will be replaced with the @new entry atomically.
169 * Note: @old should not be empty.
171 static inline void list_replace_rcu(struct list_head
*old
,
172 struct list_head
*new)
174 new->next
= old
->next
;
175 new->prev
= old
->prev
;
176 rcu_assign_pointer(list_next_rcu(new->prev
), new);
177 new->next
->prev
= new;
178 old
->prev
= LIST_POISON2
;
182 * __list_splice_init_rcu - join an RCU-protected list into an existing list.
183 * @list: the RCU-protected list to splice
184 * @prev: points to the last element of the existing list
185 * @next: points to the first element of the existing list
186 * @sync: function to sync: synchronize_rcu(), synchronize_sched(), ...
188 * The list pointed to by @prev and @next can be RCU-read traversed
189 * concurrently with this function.
191 * Note that this function blocks.
193 * Important note: the caller must take whatever action is necessary to prevent
194 * any other updates to the existing list. In principle, it is possible to
195 * modify the list as soon as sync() begins execution. If this sort of thing
196 * becomes necessary, an alternative version based on call_rcu() could be
197 * created. But only if -really- needed -- there is no shortage of RCU API
200 static inline void __list_splice_init_rcu(struct list_head
*list
,
201 struct list_head
*prev
,
202 struct list_head
*next
,
205 struct list_head
*first
= list
->next
;
206 struct list_head
*last
= list
->prev
;
209 * "first" and "last" tracking list, so initialize it. RCU readers
210 * have access to this list, so we must use INIT_LIST_HEAD_RCU()
211 * instead of INIT_LIST_HEAD().
214 INIT_LIST_HEAD_RCU(list
);
217 * At this point, the list body still points to the source list.
218 * Wait for any readers to finish using the list before splicing
219 * the list body into the new list. Any new readers will see
226 * Readers are finished with the source list, so perform splice.
227 * The order is important if the new list is global and accessible
228 * to concurrent RCU readers. Note that RCU readers are not
229 * permitted to traverse the prev pointers without excluding
234 rcu_assign_pointer(list_next_rcu(prev
), first
);
240 * list_splice_init_rcu - splice an RCU-protected list into an existing list,
241 * designed for stacks.
242 * @list: the RCU-protected list to splice
243 * @head: the place in the existing list to splice the first list into
244 * @sync: function to sync: synchronize_rcu(), synchronize_sched(), ...
246 static inline void list_splice_init_rcu(struct list_head
*list
,
247 struct list_head
*head
,
250 if (!list_empty(list
))
251 __list_splice_init_rcu(list
, head
, head
->next
, sync
);
255 * list_splice_tail_init_rcu - splice an RCU-protected list into an existing
256 * list, designed for queues.
257 * @list: the RCU-protected list to splice
258 * @head: the place in the existing list to splice the first list into
259 * @sync: function to sync: synchronize_rcu(), synchronize_sched(), ...
261 static inline void list_splice_tail_init_rcu(struct list_head
*list
,
262 struct list_head
*head
,
265 if (!list_empty(list
))
266 __list_splice_init_rcu(list
, head
->prev
, head
, sync
);
270 * list_entry_rcu - get the struct for this entry
271 * @ptr: the &struct list_head pointer.
272 * @type: the type of the struct this is embedded in.
273 * @member: the name of the list_head within the struct.
275 * This primitive may safely run concurrently with the _rcu list-mutation
276 * primitives such as list_add_rcu() as long as it's guarded by rcu_read_lock().
278 #define list_entry_rcu(ptr, type, member) \
279 container_of(lockless_dereference(ptr), type, member)
282 * Where are list_empty_rcu() and list_first_entry_rcu()?
284 * Implementing those functions following their counterparts list_empty() and
285 * list_first_entry() is not advisable because they lead to subtle race
286 * conditions as the following snippet shows:
288 * if (!list_empty_rcu(mylist)) {
289 * struct foo *bar = list_first_entry_rcu(mylist, struct foo, list_member);
293 * The list may not be empty when list_empty_rcu checks it, but it may be when
294 * list_first_entry_rcu rereads the ->next pointer.
296 * Rereading the ->next pointer is not a problem for list_empty() and
297 * list_first_entry() because they would be protected by a lock that blocks
300 * See list_first_or_null_rcu for an alternative.
304 * list_first_or_null_rcu - get the first element from a list
305 * @ptr: the list head to take the element from.
306 * @type: the type of the struct this is embedded in.
307 * @member: the name of the list_head within the struct.
309 * Note that if the list is empty, it returns NULL.
311 * This primitive may safely run concurrently with the _rcu list-mutation
312 * primitives such as list_add_rcu() as long as it's guarded by rcu_read_lock().
314 #define list_first_or_null_rcu(ptr, type, member) \
316 struct list_head *__ptr = (ptr); \
317 struct list_head *__next = READ_ONCE(__ptr->next); \
318 likely(__ptr != __next) ? list_entry_rcu(__next, type, member) : NULL; \
322 * list_for_each_entry_rcu - iterate over rcu list of given type
323 * @pos: the type * to use as a loop cursor.
324 * @head: the head for your list.
325 * @member: the name of the list_head within the struct.
327 * This list-traversal primitive may safely run concurrently with
328 * the _rcu list-mutation primitives such as list_add_rcu()
329 * as long as the traversal is guarded by rcu_read_lock().
331 #define list_for_each_entry_rcu(pos, head, member) \
332 for (pos = list_entry_rcu((head)->next, typeof(*pos), member); \
333 &pos->member != (head); \
334 pos = list_entry_rcu(pos->member.next, typeof(*pos), member))
337 * list_entry_lockless - get the struct for this entry
338 * @ptr: the &struct list_head pointer.
339 * @type: the type of the struct this is embedded in.
340 * @member: the name of the list_head within the struct.
342 * This primitive may safely run concurrently with the _rcu list-mutation
343 * primitives such as list_add_rcu(), but requires some implicit RCU
344 * read-side guarding. One example is running within a special
345 * exception-time environment where preemption is disabled and where
346 * lockdep cannot be invoked (in which case updaters must use RCU-sched,
347 * as in synchronize_sched(), call_rcu_sched(), and friends). Another
348 * example is when items are added to the list, but never deleted.
350 #define list_entry_lockless(ptr, type, member) \
351 container_of((typeof(ptr))lockless_dereference(ptr), type, member)
354 * list_for_each_entry_lockless - iterate over rcu list of given type
355 * @pos: the type * to use as a loop cursor.
356 * @head: the head for your list.
357 * @member: the name of the list_struct within the struct.
359 * This primitive may safely run concurrently with the _rcu list-mutation
360 * primitives such as list_add_rcu(), but requires some implicit RCU
361 * read-side guarding. One example is running within a special
362 * exception-time environment where preemption is disabled and where
363 * lockdep cannot be invoked (in which case updaters must use RCU-sched,
364 * as in synchronize_sched(), call_rcu_sched(), and friends). Another
365 * example is when items are added to the list, but never deleted.
367 #define list_for_each_entry_lockless(pos, head, member) \
368 for (pos = list_entry_lockless((head)->next, typeof(*pos), member); \
369 &pos->member != (head); \
370 pos = list_entry_lockless(pos->member.next, typeof(*pos), member))
373 * list_for_each_entry_continue_rcu - continue iteration over list of given type
374 * @pos: the type * to use as a loop cursor.
375 * @head: the head for your list.
376 * @member: the name of the list_head within the struct.
378 * Continue to iterate over list of given type, continuing after
379 * the current position.
381 #define list_for_each_entry_continue_rcu(pos, head, member) \
382 for (pos = list_entry_rcu(pos->member.next, typeof(*pos), member); \
383 &pos->member != (head); \
384 pos = list_entry_rcu(pos->member.next, typeof(*pos), member))
387 * hlist_del_rcu - deletes entry from hash list without re-initialization
388 * @n: the element to delete from the hash list.
390 * Note: list_unhashed() on entry does not return true after this,
391 * the entry is in an undefined state. It is useful for RCU based
392 * lockfree traversal.
394 * In particular, it means that we can not poison the forward
395 * pointers that may still be used for walking the hash list.
397 * The caller must take whatever precautions are necessary
398 * (such as holding appropriate locks) to avoid racing
399 * with another list-mutation primitive, such as hlist_add_head_rcu()
400 * or hlist_del_rcu(), running on this same list.
401 * However, it is perfectly legal to run concurrently with
402 * the _rcu list-traversal primitives, such as
403 * hlist_for_each_entry().
405 static inline void hlist_del_rcu(struct hlist_node
*n
)
408 n
->pprev
= LIST_POISON2
;
412 * hlist_replace_rcu - replace old entry by new one
413 * @old : the element to be replaced
414 * @new : the new element to insert
416 * The @old entry will be replaced with the @new entry atomically.
418 static inline void hlist_replace_rcu(struct hlist_node
*old
,
419 struct hlist_node
*new)
421 struct hlist_node
*next
= old
->next
;
424 new->pprev
= old
->pprev
;
425 rcu_assign_pointer(*(struct hlist_node __rcu
**)new->pprev
, new);
427 new->next
->pprev
= &new->next
;
428 old
->pprev
= LIST_POISON2
;
432 * return the first or the next element in an RCU protected hlist
434 #define hlist_first_rcu(head) (*((struct hlist_node __rcu **)(&(head)->first)))
435 #define hlist_next_rcu(node) (*((struct hlist_node __rcu **)(&(node)->next)))
436 #define hlist_pprev_rcu(node) (*((struct hlist_node __rcu **)((node)->pprev)))
440 * @n: the element to add to the hash list.
441 * @h: the list to add to.
444 * Adds the specified element to the specified hlist,
445 * while permitting racing traversals.
447 * The caller must take whatever precautions are necessary
448 * (such as holding appropriate locks) to avoid racing
449 * with another list-mutation primitive, such as hlist_add_head_rcu()
450 * or hlist_del_rcu(), running on this same list.
451 * However, it is perfectly legal to run concurrently with
452 * the _rcu list-traversal primitives, such as
453 * hlist_for_each_entry_rcu(), used to prevent memory-consistency
454 * problems on Alpha CPUs. Regardless of the type of CPU, the
455 * list-traversal primitive must be guarded by rcu_read_lock().
457 static inline void hlist_add_head_rcu(struct hlist_node
*n
,
458 struct hlist_head
*h
)
460 struct hlist_node
*first
= h
->first
;
463 n
->pprev
= &h
->first
;
464 rcu_assign_pointer(hlist_first_rcu(h
), n
);
466 first
->pprev
= &n
->next
;
470 * hlist_add_before_rcu
471 * @n: the new element to add to the hash list.
472 * @next: the existing element to add the new element before.
475 * Adds the specified element to the specified hlist
476 * before the specified node while permitting racing traversals.
478 * The caller must take whatever precautions are necessary
479 * (such as holding appropriate locks) to avoid racing
480 * with another list-mutation primitive, such as hlist_add_head_rcu()
481 * or hlist_del_rcu(), running on this same list.
482 * However, it is perfectly legal to run concurrently with
483 * the _rcu list-traversal primitives, such as
484 * hlist_for_each_entry_rcu(), used to prevent memory-consistency
485 * problems on Alpha CPUs.
487 static inline void hlist_add_before_rcu(struct hlist_node
*n
,
488 struct hlist_node
*next
)
490 n
->pprev
= next
->pprev
;
492 rcu_assign_pointer(hlist_pprev_rcu(n
), n
);
493 next
->pprev
= &n
->next
;
497 * hlist_add_behind_rcu
498 * @n: the new element to add to the hash list.
499 * @prev: the existing element to add the new element after.
502 * Adds the specified element to the specified hlist
503 * after the specified node while permitting racing traversals.
505 * The caller must take whatever precautions are necessary
506 * (such as holding appropriate locks) to avoid racing
507 * with another list-mutation primitive, such as hlist_add_head_rcu()
508 * or hlist_del_rcu(), running on this same list.
509 * However, it is perfectly legal to run concurrently with
510 * the _rcu list-traversal primitives, such as
511 * hlist_for_each_entry_rcu(), used to prevent memory-consistency
512 * problems on Alpha CPUs.
514 static inline void hlist_add_behind_rcu(struct hlist_node
*n
,
515 struct hlist_node
*prev
)
517 n
->next
= prev
->next
;
518 n
->pprev
= &prev
->next
;
519 rcu_assign_pointer(hlist_next_rcu(prev
), n
);
521 n
->next
->pprev
= &n
->next
;
524 #define __hlist_for_each_rcu(pos, head) \
525 for (pos = rcu_dereference(hlist_first_rcu(head)); \
527 pos = rcu_dereference(hlist_next_rcu(pos)))
530 * hlist_for_each_entry_rcu - iterate over rcu list of given type
531 * @pos: the type * to use as a loop cursor.
532 * @head: the head for your list.
533 * @member: the name of the hlist_node within the struct.
535 * This list-traversal primitive may safely run concurrently with
536 * the _rcu list-mutation primitives such as hlist_add_head_rcu()
537 * as long as the traversal is guarded by rcu_read_lock().
539 #define hlist_for_each_entry_rcu(pos, head, member) \
540 for (pos = hlist_entry_safe (rcu_dereference_raw(hlist_first_rcu(head)),\
541 typeof(*(pos)), member); \
543 pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu(\
544 &(pos)->member)), typeof(*(pos)), member))
547 * hlist_for_each_entry_rcu_notrace - iterate over rcu list of given type (for tracing)
548 * @pos: the type * to use as a loop cursor.
549 * @head: the head for your list.
550 * @member: the name of the hlist_node within the struct.
552 * This list-traversal primitive may safely run concurrently with
553 * the _rcu list-mutation primitives such as hlist_add_head_rcu()
554 * as long as the traversal is guarded by rcu_read_lock().
556 * This is the same as hlist_for_each_entry_rcu() except that it does
557 * not do any RCU debugging or tracing.
559 #define hlist_for_each_entry_rcu_notrace(pos, head, member) \
560 for (pos = hlist_entry_safe (rcu_dereference_raw_notrace(hlist_first_rcu(head)),\
561 typeof(*(pos)), member); \
563 pos = hlist_entry_safe(rcu_dereference_raw_notrace(hlist_next_rcu(\
564 &(pos)->member)), typeof(*(pos)), member))
567 * hlist_for_each_entry_rcu_bh - iterate over rcu list of given type
568 * @pos: the type * to use as a loop cursor.
569 * @head: the head for your list.
570 * @member: the name of the hlist_node within the struct.
572 * This list-traversal primitive may safely run concurrently with
573 * the _rcu list-mutation primitives such as hlist_add_head_rcu()
574 * as long as the traversal is guarded by rcu_read_lock().
576 #define hlist_for_each_entry_rcu_bh(pos, head, member) \
577 for (pos = hlist_entry_safe(rcu_dereference_bh(hlist_first_rcu(head)),\
578 typeof(*(pos)), member); \
580 pos = hlist_entry_safe(rcu_dereference_bh(hlist_next_rcu(\
581 &(pos)->member)), typeof(*(pos)), member))
584 * hlist_for_each_entry_continue_rcu - iterate over a hlist continuing after current point
585 * @pos: the type * to use as a loop cursor.
586 * @member: the name of the hlist_node within the struct.
588 #define hlist_for_each_entry_continue_rcu(pos, member) \
589 for (pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu( \
590 &(pos)->member)), typeof(*(pos)), member); \
592 pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu( \
593 &(pos)->member)), typeof(*(pos)), member))
596 * hlist_for_each_entry_continue_rcu_bh - iterate over a hlist continuing after current point
597 * @pos: the type * to use as a loop cursor.
598 * @member: the name of the hlist_node within the struct.
600 #define hlist_for_each_entry_continue_rcu_bh(pos, member) \
601 for (pos = hlist_entry_safe(rcu_dereference_bh(hlist_next_rcu( \
602 &(pos)->member)), typeof(*(pos)), member); \
604 pos = hlist_entry_safe(rcu_dereference_bh(hlist_next_rcu( \
605 &(pos)->member)), typeof(*(pos)), member))
608 * hlist_for_each_entry_from_rcu - iterate over a hlist continuing from current point
609 * @pos: the type * to use as a loop cursor.
610 * @member: the name of the hlist_node within the struct.
612 #define hlist_for_each_entry_from_rcu(pos, member) \
614 pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu( \
615 &(pos)->member)), typeof(*(pos)), member))
617 #endif /* __KERNEL__ */
This page took 0.053799 seconds and 5 git commands to generate.