Branch data Line data Source code
1 : : /* SPDX-License-Identifier: GPL-2.0 */
2 : : #ifndef _LINUX_RCULIST_H
3 : : #define _LINUX_RCULIST_H
4 : :
5 : : #ifdef __KERNEL__
6 : :
7 : : /*
8 : : * RCU-protected list version
9 : : */
10 : : #include <linux/list.h>
11 : : #include <linux/rcupdate.h>
12 : :
13 : : /*
14 : : * Why is there no list_empty_rcu()? Because list_empty() serves this
15 : : * purpose. The list_empty() function fetches the RCU-protected pointer
16 : : * and compares it to the address of the list head, but neither dereferences
17 : : * this pointer itself nor provides this pointer to the caller. Therefore,
18 : : * it is not necessary to use rcu_dereference(), so that list_empty() can
19 : : * be used anywhere you would want to use a list_empty_rcu().
20 : : */
21 : :
22 : : /*
23 : : * INIT_LIST_HEAD_RCU - Initialize a list_head visible to RCU readers
24 : : * @list: list to be initialized
25 : : *
26 : : * You should instead use INIT_LIST_HEAD() for normal initialization and
27 : : * cleanup tasks, when readers have no access to the list being initialized.
28 : : * However, if the list being initialized is visible to readers, you
29 : : * need to keep the compiler from being too mischievous.
30 : : */
31 : 1740 : static inline void INIT_LIST_HEAD_RCU(struct list_head *list)
32 : : {
33 : 1740 : WRITE_ONCE(list->next, list);
34 : 1740 : WRITE_ONCE(list->prev, list);
35 : : }
36 : :
37 : : /*
38 : : * return the ->next pointer of a list_head in an rcu safe
39 : : * way, we must not access it directly
40 : : */
41 : : #define list_next_rcu(list) (*((struct list_head __rcu **)(&(list)->next)))
42 : :
43 : : /**
44 : : * list_tail_rcu - returns the prev pointer of the head of the list
45 : : * @head: the head of the list
46 : : *
47 : : * Note: This should only be used with the list header, and even then
48 : : * only if list_del() and similar primitives are not also used on the
49 : : * list header.
50 : : */
51 : : #define list_tail_rcu(head) (*((struct list_head __rcu **)(&(head)->prev)))
52 : :
53 : : /*
54 : : * Check during list traversal that we are within an RCU reader
55 : : */
56 : :
57 : : #define check_arg_count_one(dummy)
58 : :
59 : : #ifdef CONFIG_PROVE_RCU_LIST
60 : : #define __list_check_rcu(dummy, cond, extra...) \
61 : : ({ \
62 : : check_arg_count_one(extra); \
63 : : RCU_LOCKDEP_WARN(!cond && !rcu_read_lock_any_held(), \
64 : : "RCU-list traversed in non-reader section!"); \
65 : : })
66 : : #else
67 : : #define __list_check_rcu(dummy, cond, extra...) \
68 : : ({ check_arg_count_one(extra); })
69 : : #endif
70 : :
71 : : /*
72 : : * Insert a new entry between two known consecutive entries.
73 : : *
74 : : * This is only for internal list manipulation where we know
75 : : * the prev/next entries already!
76 : : */
77 : 28467 : static inline void __list_add_rcu(struct list_head *new,
78 : : struct list_head *prev, struct list_head *next)
79 : : {
80 : 28467 : if (!__list_add_valid(new, prev, next))
81 : : return;
82 : :
83 : 28467 : new->next = next;
84 : 14394 : new->prev = prev;
85 [ + + ]: 28347 : rcu_assign_pointer(list_next_rcu(prev), new);
86 [ + + ]: 26361 : next->prev = new;
87 : : }
88 : :
89 : : /**
90 : : * list_add_rcu - add a new entry to rcu-protected list
91 : : * @new: new entry to be added
92 : : * @head: list head to add it after
93 : : *
94 : : * Insert a new entry after the specified head.
95 : : * This is good for implementing stacks.
96 : : *
97 : : * The caller must take whatever precautions are necessary
98 : : * (such as holding appropriate locks) to avoid racing
99 : : * with another list-mutation primitive, such as list_add_rcu()
100 : : * or list_del_rcu(), running on this same list.
101 : : * However, it is perfectly legal to run concurrently with
102 : : * the _rcu list-traversal primitives, such as
103 : : * list_for_each_entry_rcu().
104 : : */
105 : 2748 : static inline void list_add_rcu(struct list_head *new, struct list_head *head)
106 : : {
107 : 2748 : __list_add_rcu(new, head, head->next);
108 : 1536 : }
109 : :
110 : : /**
111 : : * list_add_tail_rcu - add a new entry to rcu-protected list
112 : : * @new: new entry to be added
113 : : * @head: list head to add it before
114 : : *
115 : : * Insert a new entry before the specified head.
116 : : * This is useful for implementing queues.
117 : : *
118 : : * The caller must take whatever precautions are necessary
119 : : * (such as holding appropriate locks) to avoid racing
120 : : * with another list-mutation primitive, such as list_add_tail_rcu()
121 : : * or list_del_rcu(), running on this same list.
122 : : * However, it is perfectly legal to run concurrently with
123 : : * the _rcu list-traversal primitives, such as
124 : : * list_for_each_entry_rcu().
125 : : */
126 : 25719 : static inline void list_add_tail_rcu(struct list_head *new,
127 : : struct list_head *head)
128 : : {
129 : 25599 : __list_add_rcu(new, head->prev, head);
130 : 870 : }
131 : :
132 : : /**
133 : : * list_del_rcu - deletes entry from list without re-initialization
134 : : * @entry: the element to delete from the list.
135 : : *
136 : : * Note: list_empty() on entry does not return true after this,
137 : : * the entry is in an undefined state. It is useful for RCU based
138 : : * lockfree traversal.
139 : : *
140 : : * In particular, it means that we can not poison the forward
141 : : * pointers that may still be used for walking the list.
142 : : *
143 : : * The caller must take whatever precautions are necessary
144 : : * (such as holding appropriate locks) to avoid racing
145 : : * with another list-mutation primitive, such as list_del_rcu()
146 : : * or list_add_rcu(), running on this same list.
147 : : * However, it is perfectly legal to run concurrently with
148 : : * the _rcu list-traversal primitives, such as
149 : : * list_for_each_entry_rcu().
150 : : *
151 : : * Note that the caller is not permitted to immediately free
152 : : * the newly deleted entry. Instead, either synchronize_rcu()
153 : : * or call_rcu() must be used to defer freeing until an RCU
154 : : * grace period has elapsed.
155 : : */
156 : 29040 : static inline void list_del_rcu(struct list_head *entry)
157 : : {
158 [ - + # # ]: 16890 : __list_del_entry(entry);
159 [ - + # # ]: 16890 : entry->prev = LIST_POISON2;
160 : 0 : }
161 : :
162 : : /**
163 : : * hlist_del_init_rcu - deletes entry from hash list with re-initialization
164 : : * @n: the element to delete from the hash list.
165 : : *
166 : : * Note: list_unhashed() on the node return true after this. It is
167 : : * useful for RCU based read lockfree traversal if the writer side
168 : : * must know if the list entry is still hashed or already unhashed.
169 : : *
170 : : * In particular, it means that we can not poison the forward pointers
171 : : * that may still be used for walking the hash list and we can only
172 : : * zero the pprev pointer so list_unhashed() will return true after
173 : : * this.
174 : : *
175 : : * The caller must take whatever precautions are necessary (such as
176 : : * holding appropriate locks) to avoid racing with another
177 : : * list-mutation primitive, such as hlist_add_head_rcu() or
178 : : * hlist_del_rcu(), running on this same list. However, it is
179 : : * perfectly legal to run concurrently with the _rcu list-traversal
180 : : * primitives, such as hlist_for_each_entry_rcu().
181 : : */
182 : 3539 : static inline void hlist_del_init_rcu(struct hlist_node *n)
183 : : {
184 [ + - + - : 3539 : if (!hlist_unhashed(n)) {
# # ]
185 [ + + + + : 3539 : __hlist_del(n);
# # ]
186 : 3539 : WRITE_ONCE(n->pprev, NULL);
187 : : }
188 : : }
189 : :
190 : : /**
191 : : * list_replace_rcu - replace old entry by new one
192 : : * @old : the element to be replaced
193 : : * @new : the new element to insert
194 : : *
195 : : * The @old entry will be replaced with the @new entry atomically.
196 : : * Note: @old should not be empty.
197 : : */
198 : 0 : static inline void list_replace_rcu(struct list_head *old,
199 : : struct list_head *new)
200 : : {
201 : 0 : new->next = old->next;
202 : 0 : new->prev = old->prev;
203 [ # # ]: 0 : rcu_assign_pointer(list_next_rcu(new->prev), new);
204 : 0 : new->next->prev = new;
205 [ # # ]: 0 : old->prev = LIST_POISON2;
206 : : }
207 : :
208 : : /**
209 : : * __list_splice_init_rcu - join an RCU-protected list into an existing list.
210 : : * @list: the RCU-protected list to splice
211 : : * @prev: points to the last element of the existing list
212 : : * @next: points to the first element of the existing list
213 : : * @sync: synchronize_rcu, synchronize_rcu_expedited, ...
214 : : *
215 : : * The list pointed to by @prev and @next can be RCU-read traversed
216 : : * concurrently with this function.
217 : : *
218 : : * Note that this function blocks.
219 : : *
220 : : * Important note: the caller must take whatever action is necessary to prevent
221 : : * any other updates to the existing list. In principle, it is possible to
222 : : * modify the list as soon as sync() begins execution. If this sort of thing
223 : : * becomes necessary, an alternative version based on call_rcu() could be
224 : : * created. But only if -really- needed -- there is no shortage of RCU API
225 : : * members.
226 : : */
227 : : static inline void __list_splice_init_rcu(struct list_head *list,
228 : : struct list_head *prev,
229 : : struct list_head *next,
230 : : void (*sync)(void))
231 : : {
232 : : struct list_head *first = list->next;
233 : : struct list_head *last = list->prev;
234 : :
235 : : /*
236 : : * "first" and "last" tracking list, so initialize it. RCU readers
237 : : * have access to this list, so we must use INIT_LIST_HEAD_RCU()
238 : : * instead of INIT_LIST_HEAD().
239 : : */
240 : :
241 : : INIT_LIST_HEAD_RCU(list);
242 : :
243 : : /*
244 : : * At this point, the list body still points to the source list.
245 : : * Wait for any readers to finish using the list before splicing
246 : : * the list body into the new list. Any new readers will see
247 : : * an empty list.
248 : : */
249 : :
250 : : sync();
251 : :
252 : : /*
253 : : * Readers are finished with the source list, so perform splice.
254 : : * The order is important if the new list is global and accessible
255 : : * to concurrent RCU readers. Note that RCU readers are not
256 : : * permitted to traverse the prev pointers without excluding
257 : : * this function.
258 : : */
259 : :
260 : : last->next = next;
261 : : rcu_assign_pointer(list_next_rcu(prev), first);
262 : : first->prev = prev;
263 : : next->prev = last;
264 : : }
265 : :
266 : : /**
267 : : * list_splice_init_rcu - splice an RCU-protected list into an existing list,
268 : : * designed for stacks.
269 : : * @list: the RCU-protected list to splice
270 : : * @head: the place in the existing list to splice the first list into
271 : : * @sync: synchronize_rcu, synchronize_rcu_expedited, ...
272 : : */
273 : : static inline void list_splice_init_rcu(struct list_head *list,
274 : : struct list_head *head,
275 : : void (*sync)(void))
276 : : {
277 : : if (!list_empty(list))
278 : : __list_splice_init_rcu(list, head, head->next, sync);
279 : : }
280 : :
281 : : /**
282 : : * list_splice_tail_init_rcu - splice an RCU-protected list into an existing
283 : : * list, designed for queues.
284 : : * @list: the RCU-protected list to splice
285 : : * @head: the place in the existing list to splice the first list into
286 : : * @sync: synchronize_rcu, synchronize_rcu_expedited, ...
287 : : */
288 : : static inline void list_splice_tail_init_rcu(struct list_head *list,
289 : : struct list_head *head,
290 : : void (*sync)(void))
291 : : {
292 : : if (!list_empty(list))
293 : : __list_splice_init_rcu(list, head->prev, head, sync);
294 : : }
295 : :
296 : : /**
297 : : * list_entry_rcu - get the struct for this entry
298 : : * @ptr: the &struct list_head pointer.
299 : : * @type: the type of the struct this is embedded in.
300 : : * @member: the name of the list_head within the struct.
301 : : *
302 : : * This primitive may safely run concurrently with the _rcu list-mutation
303 : : * primitives such as list_add_rcu() as long as it's guarded by rcu_read_lock().
304 : : */
305 : : #define list_entry_rcu(ptr, type, member) \
306 : : container_of(READ_ONCE(ptr), type, member)
307 : :
308 : : /*
309 : : * Where are list_empty_rcu() and list_first_entry_rcu()?
310 : : *
311 : : * Implementing those functions following their counterparts list_empty() and
312 : : * list_first_entry() is not advisable because they lead to subtle race
313 : : * conditions as the following snippet shows:
314 : : *
315 : : * if (!list_empty_rcu(mylist)) {
316 : : * struct foo *bar = list_first_entry_rcu(mylist, struct foo, list_member);
317 : : * do_something(bar);
318 : : * }
319 : : *
320 : : * The list may not be empty when list_empty_rcu checks it, but it may be when
321 : : * list_first_entry_rcu rereads the ->next pointer.
322 : : *
323 : : * Rereading the ->next pointer is not a problem for list_empty() and
324 : : * list_first_entry() because they would be protected by a lock that blocks
325 : : * writers.
326 : : *
327 : : * See list_first_or_null_rcu for an alternative.
328 : : */
329 : :
330 : : /**
331 : : * list_first_or_null_rcu - get the first element from a list
332 : : * @ptr: the list head to take the element from.
333 : : * @type: the type of the struct this is embedded in.
334 : : * @member: the name of the list_head within the struct.
335 : : *
336 : : * Note that if the list is empty, it returns NULL.
337 : : *
338 : : * This primitive may safely run concurrently with the _rcu list-mutation
339 : : * primitives such as list_add_rcu() as long as it's guarded by rcu_read_lock().
340 : : */
341 : : #define list_first_or_null_rcu(ptr, type, member) \
342 : : ({ \
343 : : struct list_head *__ptr = (ptr); \
344 : : struct list_head *__next = READ_ONCE(__ptr->next); \
345 : : likely(__ptr != __next) ? list_entry_rcu(__next, type, member) : NULL; \
346 : : })
347 : :
348 : : /**
349 : : * list_next_or_null_rcu - get the first element from a list
350 : : * @head: the head for the list.
351 : : * @ptr: the list head to take the next element from.
352 : : * @type: the type of the struct this is embedded in.
353 : : * @member: the name of the list_head within the struct.
354 : : *
355 : : * Note that if the ptr is at the end of the list, NULL is returned.
356 : : *
357 : : * This primitive may safely run concurrently with the _rcu list-mutation
358 : : * primitives such as list_add_rcu() as long as it's guarded by rcu_read_lock().
359 : : */
360 : : #define list_next_or_null_rcu(head, ptr, type, member) \
361 : : ({ \
362 : : struct list_head *__head = (head); \
363 : : struct list_head *__ptr = (ptr); \
364 : : struct list_head *__next = READ_ONCE(__ptr->next); \
365 : : likely(__next != __head) ? list_entry_rcu(__next, type, \
366 : : member) : NULL; \
367 : : })
368 : :
369 : : /**
370 : : * list_for_each_entry_rcu - iterate over rcu list of given type
371 : : * @pos: the type * to use as a loop cursor.
372 : : * @head: the head for your list.
373 : : * @member: the name of the list_head within the struct.
374 : : * @cond...: optional lockdep expression if called from non-RCU protection.
375 : : *
376 : : * This list-traversal primitive may safely run concurrently with
377 : : * the _rcu list-mutation primitives such as list_add_rcu()
378 : : * as long as the traversal is guarded by rcu_read_lock().
379 : : */
380 : : #define list_for_each_entry_rcu(pos, head, member, cond...) \
381 : : for (__list_check_rcu(dummy, ## cond, 0), \
382 : : pos = list_entry_rcu((head)->next, typeof(*pos), member); \
383 : : &pos->member != (head); \
384 : : pos = list_entry_rcu(pos->member.next, typeof(*pos), member))
385 : :
386 : : /**
387 : : * list_entry_lockless - get the struct for this entry
388 : : * @ptr: the &struct list_head pointer.
389 : : * @type: the type of the struct this is embedded in.
390 : : * @member: the name of the list_head within the struct.
391 : : *
392 : : * This primitive may safely run concurrently with the _rcu
393 : : * list-mutation primitives such as list_add_rcu(), but requires some
394 : : * implicit RCU read-side guarding. One example is running within a special
395 : : * exception-time environment where preemption is disabled and where lockdep
396 : : * cannot be invoked. Another example is when items are added to the list,
397 : : * but never deleted.
398 : : */
399 : : #define list_entry_lockless(ptr, type, member) \
400 : : container_of((typeof(ptr))READ_ONCE(ptr), type, member)
401 : :
402 : : /**
403 : : * list_for_each_entry_lockless - iterate over rcu list of given type
404 : : * @pos: the type * to use as a loop cursor.
405 : : * @head: the head for your list.
406 : : * @member: the name of the list_struct within the struct.
407 : : *
408 : : * This primitive may safely run concurrently with the _rcu
409 : : * list-mutation primitives such as list_add_rcu(), but requires some
410 : : * implicit RCU read-side guarding. One example is running within a special
411 : : * exception-time environment where preemption is disabled and where lockdep
412 : : * cannot be invoked. Another example is when items are added to the list,
413 : : * but never deleted.
414 : : */
415 : : #define list_for_each_entry_lockless(pos, head, member) \
416 : : for (pos = list_entry_lockless((head)->next, typeof(*pos), member); \
417 : : &pos->member != (head); \
418 : : pos = list_entry_lockless(pos->member.next, typeof(*pos), member))
419 : :
420 : : /**
421 : : * list_for_each_entry_continue_rcu - continue iteration over list of given type
422 : : * @pos: the type * to use as a loop cursor.
423 : : * @head: the head for your list.
424 : : * @member: the name of the list_head within the struct.
425 : : *
426 : : * Continue to iterate over list of given type, continuing after
427 : : * the current position which must have been in the list when the RCU read
428 : : * lock was taken.
429 : : * This would typically require either that you obtained the node from a
430 : : * previous walk of the list in the same RCU read-side critical section, or
431 : : * that you held some sort of non-RCU reference (such as a reference count)
432 : : * to keep the node alive *and* in the list.
433 : : *
434 : : * This iterator is similar to list_for_each_entry_from_rcu() except
435 : : * this starts after the given position and that one starts at the given
436 : : * position.
437 : : */
438 : : #define list_for_each_entry_continue_rcu(pos, head, member) \
439 : : for (pos = list_entry_rcu(pos->member.next, typeof(*pos), member); \
440 : : &pos->member != (head); \
441 : : pos = list_entry_rcu(pos->member.next, typeof(*pos), member))
442 : :
443 : : /**
444 : : * list_for_each_entry_from_rcu - iterate over a list from current point
445 : : * @pos: the type * to use as a loop cursor.
446 : : * @head: the head for your list.
447 : : * @member: the name of the list_node within the struct.
448 : : *
449 : : * Iterate over the tail of a list starting from a given position,
450 : : * which must have been in the list when the RCU read lock was taken.
451 : : * This would typically require either that you obtained the node from a
452 : : * previous walk of the list in the same RCU read-side critical section, or
453 : : * that you held some sort of non-RCU reference (such as a reference count)
454 : : * to keep the node alive *and* in the list.
455 : : *
456 : : * This iterator is similar to list_for_each_entry_continue_rcu() except
457 : : * this starts from the given position and that one starts from the position
458 : : * after the given position.
459 : : */
460 : : #define list_for_each_entry_from_rcu(pos, head, member) \
461 : : for (; &(pos)->member != (head); \
462 : : pos = list_entry_rcu(pos->member.next, typeof(*(pos)), member))
463 : :
464 : : /**
465 : : * hlist_del_rcu - deletes entry from hash list without re-initialization
466 : : * @n: the element to delete from the hash list.
467 : : *
468 : : * Note: list_unhashed() on entry does not return true after this,
469 : : * the entry is in an undefined state. It is useful for RCU based
470 : : * lockfree traversal.
471 : : *
472 : : * In particular, it means that we can not poison the forward
473 : : * pointers that may still be used for walking the hash list.
474 : : *
475 : : * The caller must take whatever precautions are necessary
476 : : * (such as holding appropriate locks) to avoid racing
477 : : * with another list-mutation primitive, such as hlist_add_head_rcu()
478 : : * or hlist_del_rcu(), running on this same list.
479 : : * However, it is perfectly legal to run concurrently with
480 : : * the _rcu list-traversal primitives, such as
481 : : * hlist_for_each_entry().
482 : : */
483 : 52932 : static inline void hlist_del_rcu(struct hlist_node *n)
484 : : {
485 [ + + # # : 52932 : __hlist_del(n);
# # # # #
# # # #
# ]
486 [ # # # # : 52932 : WRITE_ONCE(n->pprev, LIST_POISON2);
# # # # #
# ]
487 : 0 : }
488 : :
489 : : /**
490 : : * hlist_replace_rcu - replace old entry by new one
491 : : * @old : the element to be replaced
492 : : * @new : the new element to insert
493 : : *
494 : : * The @old entry will be replaced with the @new entry atomically.
495 : : */
496 : 0 : static inline void hlist_replace_rcu(struct hlist_node *old,
497 : : struct hlist_node *new)
498 : : {
499 : 0 : struct hlist_node *next = old->next;
500 : :
501 : 0 : new->next = next;
502 : 0 : WRITE_ONCE(new->pprev, old->pprev);
503 [ # # # # ]: 0 : rcu_assign_pointer(*(struct hlist_node __rcu **)new->pprev, new);
504 [ # # # # ]: 0 : if (next)
505 : 0 : WRITE_ONCE(new->next->pprev, &new->next);
506 : 0 : WRITE_ONCE(old->pprev, LIST_POISON2);
507 : : }
508 : :
509 : : /*
510 : : * return the first or the next element in an RCU protected hlist
511 : : */
512 : : #define hlist_first_rcu(head) (*((struct hlist_node __rcu **)(&(head)->first)))
513 : : #define hlist_next_rcu(node) (*((struct hlist_node __rcu **)(&(node)->next)))
514 : : #define hlist_pprev_rcu(node) (*((struct hlist_node __rcu **)((node)->pprev)))
515 : :
516 : : /**
517 : : * hlist_add_head_rcu
518 : : * @n: the element to add to the hash list.
519 : : * @h: the list to add to.
520 : : *
521 : : * Description:
522 : : * Adds the specified element to the specified hlist,
523 : : * while permitting racing traversals.
524 : : *
525 : : * The caller must take whatever precautions are necessary
526 : : * (such as holding appropriate locks) to avoid racing
527 : : * with another list-mutation primitive, such as hlist_add_head_rcu()
528 : : * or hlist_del_rcu(), running on this same list.
529 : : * However, it is perfectly legal to run concurrently with
530 : : * the _rcu list-traversal primitives, such as
531 : : * hlist_for_each_entry_rcu(), used to prevent memory-consistency
532 : : * problems on Alpha CPUs. Regardless of the type of CPU, the
533 : : * list-traversal primitive must be guarded by rcu_read_lock().
534 : : */
535 : 80322 : static inline void hlist_add_head_rcu(struct hlist_node *n,
536 : : struct hlist_head *h)
537 : : {
538 : 80322 : struct hlist_node *first = h->first;
539 : :
540 : 80322 : n->next = first;
541 : 80322 : WRITE_ONCE(n->pprev, &h->first);
542 [ + + + + : 80322 : rcu_assign_pointer(hlist_first_rcu(h), n);
- + - - -
+ # # # #
# # # # ]
543 [ + + + + : 80322 : if (first)
- + - - -
+ # # # #
# # # # ]
544 : 30605 : WRITE_ONCE(first->pprev, &n->next);
545 : : }
546 : :
547 : : /**
548 : : * hlist_add_tail_rcu
549 : : * @n: the element to add to the hash list.
550 : : * @h: the list to add to.
551 : : *
552 : : * Description:
553 : : * Adds the specified element to the specified hlist,
554 : : * while permitting racing traversals.
555 : : *
556 : : * The caller must take whatever precautions are necessary
557 : : * (such as holding appropriate locks) to avoid racing
558 : : * with another list-mutation primitive, such as hlist_add_head_rcu()
559 : : * or hlist_del_rcu(), running on this same list.
560 : : * However, it is perfectly legal to run concurrently with
561 : : * the _rcu list-traversal primitives, such as
562 : : * hlist_for_each_entry_rcu(), used to prevent memory-consistency
563 : : * problems on Alpha CPUs. Regardless of the type of CPU, the
564 : : * list-traversal primitive must be guarded by rcu_read_lock().
565 : : */
566 : 5940 : static inline void hlist_add_tail_rcu(struct hlist_node *n,
567 : : struct hlist_head *h)
568 : : {
569 : 5940 : struct hlist_node *i, *last = NULL;
570 : :
571 : : /* Note: write side code, so rcu accessors are not needed. */
572 [ + + # # ]: 6330 : for (i = h->first; i; i = i->next)
573 : 390 : last = i;
574 : :
575 [ + + # # ]: 5940 : if (last) {
576 : 390 : n->next = last->next;
577 : 390 : WRITE_ONCE(n->pprev, &last->next);
578 : 390 : rcu_assign_pointer(hlist_next_rcu(last), n);
579 : : } else {
580 : 5550 : hlist_add_head_rcu(n, h);
581 : : }
582 : : }
583 : :
584 : : /**
585 : : * hlist_add_before_rcu
586 : : * @n: the new element to add to the hash list.
587 : : * @next: the existing element to add the new element before.
588 : : *
589 : : * Description:
590 : : * Adds the specified element to the specified hlist
591 : : * before the specified node while permitting racing traversals.
592 : : *
593 : : * The caller must take whatever precautions are necessary
594 : : * (such as holding appropriate locks) to avoid racing
595 : : * with another list-mutation primitive, such as hlist_add_head_rcu()
596 : : * or hlist_del_rcu(), running on this same list.
597 : : * However, it is perfectly legal to run concurrently with
598 : : * the _rcu list-traversal primitives, such as
599 : : * hlist_for_each_entry_rcu(), used to prevent memory-consistency
600 : : * problems on Alpha CPUs.
601 : : */
602 : 486 : static inline void hlist_add_before_rcu(struct hlist_node *n,
603 : : struct hlist_node *next)
604 : : {
605 : 486 : WRITE_ONCE(n->pprev, next->pprev);
606 : 486 : n->next = next;
607 : 486 : rcu_assign_pointer(hlist_pprev_rcu(n), n);
608 : 486 : WRITE_ONCE(next->pprev, &n->next);
609 : 0 : }
610 : :
611 : : /**
612 : : * hlist_add_behind_rcu
613 : : * @n: the new element to add to the hash list.
614 : : * @prev: the existing element to add the new element after.
615 : : *
616 : : * Description:
617 : : * Adds the specified element to the specified hlist
618 : : * after the specified node while permitting racing traversals.
619 : : *
620 : : * The caller must take whatever precautions are necessary
621 : : * (such as holding appropriate locks) to avoid racing
622 : : * with another list-mutation primitive, such as hlist_add_head_rcu()
623 : : * or hlist_del_rcu(), running on this same list.
624 : : * However, it is perfectly legal to run concurrently with
625 : : * the _rcu list-traversal primitives, such as
626 : : * hlist_for_each_entry_rcu(), used to prevent memory-consistency
627 : : * problems on Alpha CPUs.
628 : : */
629 : 54 : static inline void hlist_add_behind_rcu(struct hlist_node *n,
630 : : struct hlist_node *prev)
631 : : {
632 : 54 : n->next = prev->next;
633 : 54 : WRITE_ONCE(n->pprev, &prev->next);
634 [ - + # # : 54 : rcu_assign_pointer(hlist_next_rcu(prev), n);
# # # # #
# ]
635 [ - + # # : 54 : if (n->next)
# # # # #
# ]
636 : 0 : WRITE_ONCE(n->next->pprev, &n->next);
637 : : }
638 : :
639 : : #define __hlist_for_each_rcu(pos, head) \
640 : : for (pos = rcu_dereference(hlist_first_rcu(head)); \
641 : : pos; \
642 : : pos = rcu_dereference(hlist_next_rcu(pos)))
643 : :
644 : : /**
645 : : * hlist_for_each_entry_rcu - iterate over rcu list of given type
646 : : * @pos: the type * to use as a loop cursor.
647 : : * @head: the head for your list.
648 : : * @member: the name of the hlist_node within the struct.
649 : : * @cond...: optional lockdep expression if called from non-RCU protection.
650 : : *
651 : : * This list-traversal primitive may safely run concurrently with
652 : : * the _rcu list-mutation primitives such as hlist_add_head_rcu()
653 : : * as long as the traversal is guarded by rcu_read_lock().
654 : : */
655 : : #define hlist_for_each_entry_rcu(pos, head, member, cond...) \
656 : : for (__list_check_rcu(dummy, ## cond, 0), \
657 : : pos = hlist_entry_safe(rcu_dereference_raw(hlist_first_rcu(head)),\
658 : : typeof(*(pos)), member); \
659 : : pos; \
660 : : pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu(\
661 : : &(pos)->member)), typeof(*(pos)), member))
662 : :
663 : : /**
664 : : * hlist_for_each_entry_rcu_notrace - iterate over rcu list of given type (for tracing)
665 : : * @pos: the type * to use as a loop cursor.
666 : : * @head: the head for your list.
667 : : * @member: the name of the hlist_node within the struct.
668 : : *
669 : : * This list-traversal primitive may safely run concurrently with
670 : : * the _rcu list-mutation primitives such as hlist_add_head_rcu()
671 : : * as long as the traversal is guarded by rcu_read_lock().
672 : : *
673 : : * This is the same as hlist_for_each_entry_rcu() except that it does
674 : : * not do any RCU debugging or tracing.
675 : : */
676 : : #define hlist_for_each_entry_rcu_notrace(pos, head, member) \
677 : : for (pos = hlist_entry_safe(rcu_dereference_raw_check(hlist_first_rcu(head)),\
678 : : typeof(*(pos)), member); \
679 : : pos; \
680 : : pos = hlist_entry_safe(rcu_dereference_raw_check(hlist_next_rcu(\
681 : : &(pos)->member)), typeof(*(pos)), member))
682 : :
683 : : /**
684 : : * hlist_for_each_entry_rcu_bh - iterate over rcu list of given type
685 : : * @pos: the type * to use as a loop cursor.
686 : : * @head: the head for your list.
687 : : * @member: the name of the hlist_node within the struct.
688 : : *
689 : : * This list-traversal primitive may safely run concurrently with
690 : : * the _rcu list-mutation primitives such as hlist_add_head_rcu()
691 : : * as long as the traversal is guarded by rcu_read_lock().
692 : : */
693 : : #define hlist_for_each_entry_rcu_bh(pos, head, member) \
694 : : for (pos = hlist_entry_safe(rcu_dereference_bh(hlist_first_rcu(head)),\
695 : : typeof(*(pos)), member); \
696 : : pos; \
697 : : pos = hlist_entry_safe(rcu_dereference_bh(hlist_next_rcu(\
698 : : &(pos)->member)), typeof(*(pos)), member))
699 : :
700 : : /**
701 : : * hlist_for_each_entry_continue_rcu - iterate over a hlist continuing after current point
702 : : * @pos: the type * to use as a loop cursor.
703 : : * @member: the name of the hlist_node within the struct.
704 : : */
705 : : #define hlist_for_each_entry_continue_rcu(pos, member) \
706 : : for (pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu( \
707 : : &(pos)->member)), typeof(*(pos)), member); \
708 : : pos; \
709 : : pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu( \
710 : : &(pos)->member)), typeof(*(pos)), member))
711 : :
712 : : /**
713 : : * hlist_for_each_entry_continue_rcu_bh - iterate over a hlist continuing after current point
714 : : * @pos: the type * to use as a loop cursor.
715 : : * @member: the name of the hlist_node within the struct.
716 : : */
717 : : #define hlist_for_each_entry_continue_rcu_bh(pos, member) \
718 : : for (pos = hlist_entry_safe(rcu_dereference_bh(hlist_next_rcu( \
719 : : &(pos)->member)), typeof(*(pos)), member); \
720 : : pos; \
721 : : pos = hlist_entry_safe(rcu_dereference_bh(hlist_next_rcu( \
722 : : &(pos)->member)), typeof(*(pos)), member))
723 : :
724 : : /**
725 : : * hlist_for_each_entry_from_rcu - iterate over a hlist continuing from current point
726 : : * @pos: the type * to use as a loop cursor.
727 : : * @member: the name of the hlist_node within the struct.
728 : : */
729 : : #define hlist_for_each_entry_from_rcu(pos, member) \
730 : : for (; pos; \
731 : : pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu( \
732 : : &(pos)->member)), typeof(*(pos)), member))
733 : :
734 : : #endif /* __KERNEL__ */
735 : : #endif
|
