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_for_each_entry_rcu - iterate over rcu list of given type
246 * @pos: the type * to use as a loop cursor.
247 * @head: the head for your list.
248 * @member: the name of the list_struct within the struct.
250 * This list-traversal primitive may safely run concurrently with
251 * the _rcu list-mutation primitives such as list_add_rcu()
252 * as long as the traversal is guarded by rcu_read_lock().
254 #define list_for_each_entry_rcu(pos, head, member) \
255 for (pos = list_entry_rcu((head)->next, typeof(*pos), member); \
256 &pos->member != (head); \
257 pos = list_entry_rcu(pos->member.next, typeof(*pos), member))
261 * list_for_each_continue_rcu
262 * @pos: the &struct list_head to use as a loop cursor.
263 * @head: the head for your list.
265 * Iterate over an rcu-protected list, continuing after current point.
267 * This list-traversal primitive may safely run concurrently with
268 * the _rcu list-mutation primitives such as list_add_rcu()
269 * as long as the traversal is guarded by rcu_read_lock().
271 #define list_for_each_continue_rcu(pos, head) \
272 for ((pos) = rcu_dereference_raw(list_next_rcu(pos)); \
274 (pos) = rcu_dereference_raw(list_next_rcu(pos)))
277 * list_for_each_entry_continue_rcu - continue iteration over list of given type
278 * @pos: the type * to use as a loop cursor.
279 * @head: the head for your list.
280 * @member: the name of the list_struct within the struct.
282 * Continue to iterate over list of given type, continuing after
283 * the current position.
285 #define list_for_each_entry_continue_rcu(pos, head, member) \
286 for (pos = list_entry_rcu(pos->member.next, typeof(*pos), member); \
287 &pos->member != (head); \
288 pos = list_entry_rcu(pos->member.next, typeof(*pos), member))
291 * hlist_del_rcu - deletes entry from hash list without re-initialization
292 * @n: the element to delete from the hash list.
294 * Note: list_unhashed() on entry does not return true after this,
295 * the entry is in an undefined state. It is useful for RCU based
296 * lockfree traversal.
298 * In particular, it means that we can not poison the forward
299 * pointers that may still be used for walking the hash list.
301 * The caller must take whatever precautions are necessary
302 * (such as holding appropriate locks) to avoid racing
303 * with another list-mutation primitive, such as hlist_add_head_rcu()
304 * or hlist_del_rcu(), running on this same list.
305 * However, it is perfectly legal to run concurrently with
306 * the _rcu list-traversal primitives, such as
307 * hlist_for_each_entry().
309 static inline void hlist_del_rcu(struct hlist_node
*n
)
312 n
->pprev
= LIST_POISON2
;
316 * hlist_replace_rcu - replace old entry by new one
317 * @old : the element to be replaced
318 * @new : the new element to insert
320 * The @old entry will be replaced with the @new entry atomically.
322 static inline void hlist_replace_rcu(struct hlist_node
*old
,
323 struct hlist_node
*new)
325 struct hlist_node
*next
= old
->next
;
328 new->pprev
= old
->pprev
;
329 rcu_assign_pointer(*(struct hlist_node __rcu
**)new->pprev
, new);
331 new->next
->pprev
= &new->next
;
332 old
->pprev
= LIST_POISON2
;
336 * return the first or the next element in an RCU protected hlist
338 #define hlist_first_rcu(head) (*((struct hlist_node __rcu **)(&(head)->first)))
339 #define hlist_next_rcu(node) (*((struct hlist_node __rcu **)(&(node)->next)))
340 #define hlist_pprev_rcu(node) (*((struct hlist_node __rcu **)((node)->pprev)))
344 * @n: the element to add to the hash list.
345 * @h: the list to add to.
348 * Adds the specified element to the specified hlist,
349 * while permitting racing traversals.
351 * The caller must take whatever precautions are necessary
352 * (such as holding appropriate locks) to avoid racing
353 * with another list-mutation primitive, such as hlist_add_head_rcu()
354 * or hlist_del_rcu(), running on this same list.
355 * However, it is perfectly legal to run concurrently with
356 * the _rcu list-traversal primitives, such as
357 * hlist_for_each_entry_rcu(), used to prevent memory-consistency
358 * problems on Alpha CPUs. Regardless of the type of CPU, the
359 * list-traversal primitive must be guarded by rcu_read_lock().
361 static inline void hlist_add_head_rcu(struct hlist_node
*n
,
362 struct hlist_head
*h
)
364 struct hlist_node
*first
= h
->first
;
367 n
->pprev
= &h
->first
;
368 rcu_assign_pointer(hlist_first_rcu(h
), n
);
370 first
->pprev
= &n
->next
;
374 * hlist_add_before_rcu
375 * @n: the new element to add to the hash list.
376 * @next: the existing element to add the new element before.
379 * Adds the specified element to the specified hlist
380 * before the specified node while permitting racing traversals.
382 * The caller must take whatever precautions are necessary
383 * (such as holding appropriate locks) to avoid racing
384 * with another list-mutation primitive, such as hlist_add_head_rcu()
385 * or hlist_del_rcu(), running on this same list.
386 * However, it is perfectly legal to run concurrently with
387 * the _rcu list-traversal primitives, such as
388 * hlist_for_each_entry_rcu(), used to prevent memory-consistency
389 * problems on Alpha CPUs.
391 static inline void hlist_add_before_rcu(struct hlist_node
*n
,
392 struct hlist_node
*next
)
394 n
->pprev
= next
->pprev
;
396 rcu_assign_pointer(hlist_pprev_rcu(n
), n
);
397 next
->pprev
= &n
->next
;
401 * hlist_add_after_rcu
402 * @prev: the existing element to add the new element after.
403 * @n: the new element to add to the hash list.
406 * Adds the specified element to the specified hlist
407 * after the specified node while permitting racing traversals.
409 * The caller must take whatever precautions are necessary
410 * (such as holding appropriate locks) to avoid racing
411 * with another list-mutation primitive, such as hlist_add_head_rcu()
412 * or hlist_del_rcu(), running on this same list.
413 * However, it is perfectly legal to run concurrently with
414 * the _rcu list-traversal primitives, such as
415 * hlist_for_each_entry_rcu(), used to prevent memory-consistency
416 * problems on Alpha CPUs.
418 static inline void hlist_add_after_rcu(struct hlist_node
*prev
,
419 struct hlist_node
*n
)
421 n
->next
= prev
->next
;
422 n
->pprev
= &prev
->next
;
423 rcu_assign_pointer(hlist_next_rcu(prev
), n
);
425 n
->next
->pprev
= &n
->next
;
428 #define __hlist_for_each_rcu(pos, head) \
429 for (pos = rcu_dereference(hlist_first_rcu(head)); \
431 pos = rcu_dereference(hlist_next_rcu(pos)))
434 * hlist_for_each_entry_rcu - iterate over rcu list of given type
435 * @tpos: the type * to use as a loop cursor.
436 * @pos: the &struct hlist_node to use as a loop cursor.
437 * @head: the head for your list.
438 * @member: the name of the hlist_node within the struct.
440 * This list-traversal primitive may safely run concurrently with
441 * the _rcu list-mutation primitives such as hlist_add_head_rcu()
442 * as long as the traversal is guarded by rcu_read_lock().
444 #define hlist_for_each_entry_rcu(tpos, pos, head, member) \
445 for (pos = rcu_dereference_raw(hlist_first_rcu(head)); \
447 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1; }); \
448 pos = rcu_dereference_raw(hlist_next_rcu(pos)))
451 * hlist_for_each_entry_rcu_bh - iterate over rcu list of given type
452 * @tpos: the type * to use as a loop cursor.
453 * @pos: the &struct hlist_node to use as a loop cursor.
454 * @head: the head for your list.
455 * @member: the name of the hlist_node within the struct.
457 * This list-traversal primitive may safely run concurrently with
458 * the _rcu list-mutation primitives such as hlist_add_head_rcu()
459 * as long as the traversal is guarded by rcu_read_lock().
461 #define hlist_for_each_entry_rcu_bh(tpos, pos, head, member) \
462 for (pos = rcu_dereference_bh((head)->first); \
464 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1; }); \
465 pos = rcu_dereference_bh(pos->next))
468 * hlist_for_each_entry_continue_rcu - iterate over a hlist continuing after current point
469 * @tpos: the type * to use as a loop cursor.
470 * @pos: the &struct hlist_node to use as a loop cursor.
471 * @member: the name of the hlist_node within the struct.
473 #define hlist_for_each_entry_continue_rcu(tpos, pos, member) \
474 for (pos = rcu_dereference((pos)->next); \
476 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1; }); \
477 pos = rcu_dereference(pos->next))
480 * hlist_for_each_entry_continue_rcu_bh - iterate over a hlist continuing after current point
481 * @tpos: the type * to use as a loop cursor.
482 * @pos: the &struct hlist_node to use as a loop cursor.
483 * @member: the name of the hlist_node within the struct.
485 #define hlist_for_each_entry_continue_rcu_bh(tpos, pos, member) \
486 for (pos = rcu_dereference_bh((pos)->next); \
488 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1; }); \
489 pos = rcu_dereference_bh(pos->next))
492 #endif /* __KERNEL__ */
This page took 0.039971 seconds and 5 git commands to generate.