~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/include/linux/rculist.h

Version: ~ [ linux-5.9-rc6 ] ~ [ linux-5.8.10 ] ~ [ linux-5.7.19 ] ~ [ linux-5.6.19 ] ~ [ linux-5.5.19 ] ~ [ linux-5.4.66 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.146 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.198 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.236 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.236 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.19.8 ] ~ [ linux-3.18.140 ] ~ [ linux-3.17.8 ] ~ [ linux-3.16.85 ] ~ [ linux-3.15.10 ] ~ [ linux-3.14.79 ] ~ [ linux-3.13.11 ] ~ [ linux-3.12.74 ] ~ [ linux-3.11.10 ] ~ [ linux-3.10.108 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  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 static inline void INIT_LIST_HEAD_RCU(struct list_head *list)
 32 {
 33         WRITE_ONCE(list->next, list);
 34         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 static inline void __list_add_rcu(struct list_head *new,
 78                 struct list_head *prev, struct list_head *next)
 79 {
 80         if (!__list_add_valid(new, prev, next))
 81                 return;
 82 
 83         new->next = next;
 84         new->prev = prev;
 85         rcu_assign_pointer(list_next_rcu(prev), new);
 86         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 static inline void list_add_rcu(struct list_head *new, struct list_head *head)
106 {
107         __list_add_rcu(new, head, head->next);
108 }
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 static inline void list_add_tail_rcu(struct list_head *new,
127                                         struct list_head *head)
128 {
129         __list_add_rcu(new, head->prev, head);
130 }
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 static inline void list_del_rcu(struct list_head *entry)
157 {
158         __list_del_entry(entry);
159         entry->prev = LIST_POISON2;
160 }
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 static inline void hlist_del_init_rcu(struct hlist_node *n)
183 {
184         if (!hlist_unhashed(n)) {
185                 __hlist_del(n);
186                 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 static inline void list_replace_rcu(struct list_head *old,
199                                 struct list_head *new)
200 {
201         new->next = old->next;
202         new->prev = old->prev;
203         rcu_assign_pointer(list_next_rcu(new->prev), new);
204         new->next->prev = new;
205         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         ASSERT_EXCLUSIVE_ACCESS(*first);
252         ASSERT_EXCLUSIVE_ACCESS(*last);
253 
254         /*
255          * Readers are finished with the source list, so perform splice.
256          * The order is important if the new list is global and accessible
257          * to concurrent RCU readers.  Note that RCU readers are not
258          * permitted to traverse the prev pointers without excluding
259          * this function.
260          */
261 
262         last->next = next;
263         rcu_assign_pointer(list_next_rcu(prev), first);
264         first->prev = prev;
265         next->prev = last;
266 }
267 
268 /**
269  * list_splice_init_rcu - splice an RCU-protected list into an existing list,
270  *                        designed for stacks.
271  * @list:       the RCU-protected list to splice
272  * @head:       the place in the existing list to splice the first list into
273  * @sync:       synchronize_rcu, synchronize_rcu_expedited, ...
274  */
275 static inline void list_splice_init_rcu(struct list_head *list,
276                                         struct list_head *head,
277                                         void (*sync)(void))
278 {
279         if (!list_empty(list))
280                 __list_splice_init_rcu(list, head, head->next, sync);
281 }
282 
283 /**
284  * list_splice_tail_init_rcu - splice an RCU-protected list into an existing
285  *                             list, designed for queues.
286  * @list:       the RCU-protected list to splice
287  * @head:       the place in the existing list to splice the first list into
288  * @sync:       synchronize_rcu, synchronize_rcu_expedited, ...
289  */
290 static inline void list_splice_tail_init_rcu(struct list_head *list,
291                                              struct list_head *head,
292                                              void (*sync)(void))
293 {
294         if (!list_empty(list))
295                 __list_splice_init_rcu(list, head->prev, head, sync);
296 }
297 
298 /**
299  * list_entry_rcu - get the struct for this entry
300  * @ptr:        the &struct list_head pointer.
301  * @type:       the type of the struct this is embedded in.
302  * @member:     the name of the list_head within the struct.
303  *
304  * This primitive may safely run concurrently with the _rcu list-mutation
305  * primitives such as list_add_rcu() as long as it's guarded by rcu_read_lock().
306  */
307 #define list_entry_rcu(ptr, type, member) \
308         container_of(READ_ONCE(ptr), type, member)
309 
310 /*
311  * Where are list_empty_rcu() and list_first_entry_rcu()?
312  *
313  * Implementing those functions following their counterparts list_empty() and
314  * list_first_entry() is not advisable because they lead to subtle race
315  * conditions as the following snippet shows:
316  *
317  * if (!list_empty_rcu(mylist)) {
318  *      struct foo *bar = list_first_entry_rcu(mylist, struct foo, list_member);
319  *      do_something(bar);
320  * }
321  *
322  * The list may not be empty when list_empty_rcu checks it, but it may be when
323  * list_first_entry_rcu rereads the ->next pointer.
324  *
325  * Rereading the ->next pointer is not a problem for list_empty() and
326  * list_first_entry() because they would be protected by a lock that blocks
327  * writers.
328  *
329  * See list_first_or_null_rcu for an alternative.
330  */
331 
332 /**
333  * list_first_or_null_rcu - get the first element from a list
334  * @ptr:        the list head to take the element from.
335  * @type:       the type of the struct this is embedded in.
336  * @member:     the name of the list_head within the struct.
337  *
338  * Note that if the list is empty, it returns NULL.
339  *
340  * This primitive may safely run concurrently with the _rcu list-mutation
341  * primitives such as list_add_rcu() as long as it's guarded by rcu_read_lock().
342  */
343 #define list_first_or_null_rcu(ptr, type, member) \
344 ({ \
345         struct list_head *__ptr = (ptr); \
346         struct list_head *__next = READ_ONCE(__ptr->next); \
347         likely(__ptr != __next) ? list_entry_rcu(__next, type, member) : NULL; \
348 })
349 
350 /**
351  * list_next_or_null_rcu - get the first element from a list
352  * @head:       the head for the list.
353  * @ptr:        the list head to take the next element from.
354  * @type:       the type of the struct this is embedded in.
355  * @member:     the name of the list_head within the struct.
356  *
357  * Note that if the ptr is at the end of the list, NULL is returned.
358  *
359  * This primitive may safely run concurrently with the _rcu list-mutation
360  * primitives such as list_add_rcu() as long as it's guarded by rcu_read_lock().
361  */
362 #define list_next_or_null_rcu(head, ptr, type, member) \
363 ({ \
364         struct list_head *__head = (head); \
365         struct list_head *__ptr = (ptr); \
366         struct list_head *__next = READ_ONCE(__ptr->next); \
367         likely(__next != __head) ? list_entry_rcu(__next, type, \
368                                                   member) : NULL; \
369 })
370 
371 /**
372  * list_for_each_entry_rcu      -       iterate over rcu list of given type
373  * @pos:        the type * to use as a loop cursor.
374  * @head:       the head for your list.
375  * @member:     the name of the list_head within the struct.
376  * @cond:       optional lockdep expression if called from non-RCU protection.
377  *
378  * This list-traversal primitive may safely run concurrently with
379  * the _rcu list-mutation primitives such as list_add_rcu()
380  * as long as the traversal is guarded by rcu_read_lock().
381  */
382 #define list_for_each_entry_rcu(pos, head, member, cond...)             \
383         for (__list_check_rcu(dummy, ## cond, 0),                       \
384              pos = list_entry_rcu((head)->next, typeof(*pos), member);  \
385                 &pos->member != (head);                                 \
386                 pos = list_entry_rcu(pos->member.next, typeof(*pos), member))
387 
388 /**
389  * list_entry_lockless - get the struct for this entry
390  * @ptr:        the &struct list_head pointer.
391  * @type:       the type of the struct this is embedded in.
392  * @member:     the name of the list_head within the struct.
393  *
394  * This primitive may safely run concurrently with the _rcu
395  * list-mutation primitives such as list_add_rcu(), but requires some
396  * implicit RCU read-side guarding.  One example is running within a special
397  * exception-time environment where preemption is disabled and where lockdep
398  * cannot be invoked.  Another example is when items are added to the list,
399  * but never deleted.
400  */
401 #define list_entry_lockless(ptr, type, member) \
402         container_of((typeof(ptr))READ_ONCE(ptr), type, member)
403 
404 /**
405  * list_for_each_entry_lockless - iterate over rcu list of given type
406  * @pos:        the type * to use as a loop cursor.
407  * @head:       the head for your list.
408  * @member:     the name of the list_struct within the struct.
409  *
410  * This primitive may safely run concurrently with the _rcu
411  * list-mutation primitives such as list_add_rcu(), but requires some
412  * implicit RCU read-side guarding.  One example is running within a special
413  * exception-time environment where preemption is disabled and where lockdep
414  * cannot be invoked.  Another example is when items are added to the list,
415  * but never deleted.
416  */
417 #define list_for_each_entry_lockless(pos, head, member) \
418         for (pos = list_entry_lockless((head)->next, typeof(*pos), member); \
419              &pos->member != (head); \
420              pos = list_entry_lockless(pos->member.next, typeof(*pos), member))
421 
422 /**
423  * list_for_each_entry_continue_rcu - continue iteration over list of given type
424  * @pos:        the type * to use as a loop cursor.
425  * @head:       the head for your list.
426  * @member:     the name of the list_head within the struct.
427  *
428  * Continue to iterate over list of given type, continuing after
429  * the current position which must have been in the list when the RCU read
430  * lock was taken.
431  * This would typically require either that you obtained the node from a
432  * previous walk of the list in the same RCU read-side critical section, or
433  * that you held some sort of non-RCU reference (such as a reference count)
434  * to keep the node alive *and* in the list.
435  *
436  * This iterator is similar to list_for_each_entry_from_rcu() except
437  * this starts after the given position and that one starts at the given
438  * position.
439  */
440 #define list_for_each_entry_continue_rcu(pos, head, member)             \
441         for (pos = list_entry_rcu(pos->member.next, typeof(*pos), member); \
442              &pos->member != (head);    \
443              pos = list_entry_rcu(pos->member.next, typeof(*pos), member))
444 
445 /**
446  * list_for_each_entry_from_rcu - iterate over a list from current point
447  * @pos:        the type * to use as a loop cursor.
448  * @head:       the head for your list.
449  * @member:     the name of the list_node within the struct.
450  *
451  * Iterate over the tail of a list starting from a given position,
452  * which must have been in the list when the RCU read lock was taken.
453  * This would typically require either that you obtained the node from a
454  * previous walk of the list in the same RCU read-side critical section, or
455  * that you held some sort of non-RCU reference (such as a reference count)
456  * to keep the node alive *and* in the list.
457  *
458  * This iterator is similar to list_for_each_entry_continue_rcu() except
459  * this starts from the given position and that one starts from the position
460  * after the given position.
461  */
462 #define list_for_each_entry_from_rcu(pos, head, member)                 \
463         for (; &(pos)->member != (head);                                        \
464                 pos = list_entry_rcu(pos->member.next, typeof(*(pos)), member))
465 
466 /**
467  * hlist_del_rcu - deletes entry from hash list without re-initialization
468  * @n: the element to delete from the hash list.
469  *
470  * Note: list_unhashed() on entry does not return true after this,
471  * the entry is in an undefined state. It is useful for RCU based
472  * lockfree traversal.
473  *
474  * In particular, it means that we can not poison the forward
475  * pointers that may still be used for walking the hash list.
476  *
477  * The caller must take whatever precautions are necessary
478  * (such as holding appropriate locks) to avoid racing
479  * with another list-mutation primitive, such as hlist_add_head_rcu()
480  * or hlist_del_rcu(), running on this same list.
481  * However, it is perfectly legal to run concurrently with
482  * the _rcu list-traversal primitives, such as
483  * hlist_for_each_entry().
484  */
485 static inline void hlist_del_rcu(struct hlist_node *n)
486 {
487         __hlist_del(n);
488         WRITE_ONCE(n->pprev, LIST_POISON2);
489 }
490 
491 /**
492  * hlist_replace_rcu - replace old entry by new one
493  * @old : the element to be replaced
494  * @new : the new element to insert
495  *
496  * The @old entry will be replaced with the @new entry atomically.
497  */
498 static inline void hlist_replace_rcu(struct hlist_node *old,
499                                         struct hlist_node *new)
500 {
501         struct hlist_node *next = old->next;
502 
503         new->next = next;
504         WRITE_ONCE(new->pprev, old->pprev);
505         rcu_assign_pointer(*(struct hlist_node __rcu **)new->pprev, new);
506         if (next)
507                 WRITE_ONCE(new->next->pprev, &new->next);
508         WRITE_ONCE(old->pprev, LIST_POISON2);
509 }
510 
511 /**
512  * hlists_swap_heads_rcu - swap the lists the hlist heads point to
513  * @left:  The hlist head on the left
514  * @right: The hlist head on the right
515  *
516  * The lists start out as [@left  ][node1 ... ] and
517  *                        [@right ][node2 ... ]
518  * The lists end up as    [@left  ][node2 ... ]
519  *                        [@right ][node1 ... ]
520  */
521 static inline void hlists_swap_heads_rcu(struct hlist_head *left, struct hlist_head *right)
522 {
523         struct hlist_node *node1 = left->first;
524         struct hlist_node *node2 = right->first;
525 
526         rcu_assign_pointer(left->first, node2);
527         rcu_assign_pointer(right->first, node1);
528         WRITE_ONCE(node2->pprev, &left->first);
529         WRITE_ONCE(node1->pprev, &right->first);
530 }
531 
532 /*
533  * return the first or the next element in an RCU protected hlist
534  */
535 #define hlist_first_rcu(head)   (*((struct hlist_node __rcu **)(&(head)->first)))
536 #define hlist_next_rcu(node)    (*((struct hlist_node __rcu **)(&(node)->next)))
537 #define hlist_pprev_rcu(node)   (*((struct hlist_node __rcu **)((node)->pprev)))
538 
539 /**
540  * hlist_add_head_rcu
541  * @n: the element to add to the hash list.
542  * @h: the list to add to.
543  *
544  * Description:
545  * Adds the specified element to the specified hlist,
546  * while permitting racing traversals.
547  *
548  * The caller must take whatever precautions are necessary
549  * (such as holding appropriate locks) to avoid racing
550  * with another list-mutation primitive, such as hlist_add_head_rcu()
551  * or hlist_del_rcu(), running on this same list.
552  * However, it is perfectly legal to run concurrently with
553  * the _rcu list-traversal primitives, such as
554  * hlist_for_each_entry_rcu(), used to prevent memory-consistency
555  * problems on Alpha CPUs.  Regardless of the type of CPU, the
556  * list-traversal primitive must be guarded by rcu_read_lock().
557  */
558 static inline void hlist_add_head_rcu(struct hlist_node *n,
559                                         struct hlist_head *h)
560 {
561         struct hlist_node *first = h->first;
562 
563         n->next = first;
564         WRITE_ONCE(n->pprev, &h->first);
565         rcu_assign_pointer(hlist_first_rcu(h), n);
566         if (first)
567                 WRITE_ONCE(first->pprev, &n->next);
568 }
569 
570 /**
571  * hlist_add_tail_rcu
572  * @n: the element to add to the hash list.
573  * @h: the list to add to.
574  *
575  * Description:
576  * Adds the specified element to the specified hlist,
577  * while permitting racing traversals.
578  *
579  * The caller must take whatever precautions are necessary
580  * (such as holding appropriate locks) to avoid racing
581  * with another list-mutation primitive, such as hlist_add_head_rcu()
582  * or hlist_del_rcu(), running on this same list.
583  * However, it is perfectly legal to run concurrently with
584  * the _rcu list-traversal primitives, such as
585  * hlist_for_each_entry_rcu(), used to prevent memory-consistency
586  * problems on Alpha CPUs.  Regardless of the type of CPU, the
587  * list-traversal primitive must be guarded by rcu_read_lock().
588  */
589 static inline void hlist_add_tail_rcu(struct hlist_node *n,
590                                       struct hlist_head *h)
591 {
592         struct hlist_node *i, *last = NULL;
593 
594         /* Note: write side code, so rcu accessors are not needed. */
595         for (i = h->first; i; i = i->next)
596                 last = i;
597 
598         if (last) {
599                 n->next = last->next;
600                 WRITE_ONCE(n->pprev, &last->next);
601                 rcu_assign_pointer(hlist_next_rcu(last), n);
602         } else {
603                 hlist_add_head_rcu(n, h);
604         }
605 }
606 
607 /**
608  * hlist_add_before_rcu
609  * @n: the new element to add to the hash list.
610  * @next: the existing element to add the new element before.
611  *
612  * Description:
613  * Adds the specified element to the specified hlist
614  * before the specified node while permitting racing traversals.
615  *
616  * The caller must take whatever precautions are necessary
617  * (such as holding appropriate locks) to avoid racing
618  * with another list-mutation primitive, such as hlist_add_head_rcu()
619  * or hlist_del_rcu(), running on this same list.
620  * However, it is perfectly legal to run concurrently with
621  * the _rcu list-traversal primitives, such as
622  * hlist_for_each_entry_rcu(), used to prevent memory-consistency
623  * problems on Alpha CPUs.
624  */
625 static inline void hlist_add_before_rcu(struct hlist_node *n,
626                                         struct hlist_node *next)
627 {
628         WRITE_ONCE(n->pprev, next->pprev);
629         n->next = next;
630         rcu_assign_pointer(hlist_pprev_rcu(n), n);
631         WRITE_ONCE(next->pprev, &n->next);
632 }
633 
634 /**
635  * hlist_add_behind_rcu
636  * @n: the new element to add to the hash list.
637  * @prev: the existing element to add the new element after.
638  *
639  * Description:
640  * Adds the specified element to the specified hlist
641  * after the specified node while permitting racing traversals.
642  *
643  * The caller must take whatever precautions are necessary
644  * (such as holding appropriate locks) to avoid racing
645  * with another list-mutation primitive, such as hlist_add_head_rcu()
646  * or hlist_del_rcu(), running on this same list.
647  * However, it is perfectly legal to run concurrently with
648  * the _rcu list-traversal primitives, such as
649  * hlist_for_each_entry_rcu(), used to prevent memory-consistency
650  * problems on Alpha CPUs.
651  */
652 static inline void hlist_add_behind_rcu(struct hlist_node *n,
653                                         struct hlist_node *prev)
654 {
655         n->next = prev->next;
656         WRITE_ONCE(n->pprev, &prev->next);
657         rcu_assign_pointer(hlist_next_rcu(prev), n);
658         if (n->next)
659                 WRITE_ONCE(n->next->pprev, &n->next);
660 }
661 
662 #define __hlist_for_each_rcu(pos, head)                         \
663         for (pos = rcu_dereference(hlist_first_rcu(head));      \
664              pos;                                               \
665              pos = rcu_dereference(hlist_next_rcu(pos)))
666 
667 /**
668  * hlist_for_each_entry_rcu - iterate over rcu list of given type
669  * @pos:        the type * to use as a loop cursor.
670  * @head:       the head for your list.
671  * @member:     the name of the hlist_node within the struct.
672  * @cond:       optional lockdep expression if called from non-RCU protection.
673  *
674  * This list-traversal primitive may safely run concurrently with
675  * the _rcu list-mutation primitives such as hlist_add_head_rcu()
676  * as long as the traversal is guarded by rcu_read_lock().
677  */
678 #define hlist_for_each_entry_rcu(pos, head, member, cond...)            \
679         for (__list_check_rcu(dummy, ## cond, 0),                       \
680              pos = hlist_entry_safe(rcu_dereference_raw(hlist_first_rcu(head)),\
681                         typeof(*(pos)), member);                        \
682                 pos;                                                    \
683                 pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu(\
684                         &(pos)->member)), typeof(*(pos)), member))
685 
686 /**
687  * hlist_for_each_entry_rcu_notrace - iterate over rcu list of given type (for tracing)
688  * @pos:        the type * to use as a loop cursor.
689  * @head:       the head for your list.
690  * @member:     the name of the hlist_node within the struct.
691  *
692  * This list-traversal primitive may safely run concurrently with
693  * the _rcu list-mutation primitives such as hlist_add_head_rcu()
694  * as long as the traversal is guarded by rcu_read_lock().
695  *
696  * This is the same as hlist_for_each_entry_rcu() except that it does
697  * not do any RCU debugging or tracing.
698  */
699 #define hlist_for_each_entry_rcu_notrace(pos, head, member)                     \
700         for (pos = hlist_entry_safe(rcu_dereference_raw_check(hlist_first_rcu(head)),\
701                         typeof(*(pos)), member);                        \
702                 pos;                                                    \
703                 pos = hlist_entry_safe(rcu_dereference_raw_check(hlist_next_rcu(\
704                         &(pos)->member)), typeof(*(pos)), member))
705 
706 /**
707  * hlist_for_each_entry_rcu_bh - iterate over rcu list of given type
708  * @pos:        the type * to use as a loop cursor.
709  * @head:       the head for your list.
710  * @member:     the name of the hlist_node within the struct.
711  *
712  * This list-traversal primitive may safely run concurrently with
713  * the _rcu list-mutation primitives such as hlist_add_head_rcu()
714  * as long as the traversal is guarded by rcu_read_lock().
715  */
716 #define hlist_for_each_entry_rcu_bh(pos, head, member)                  \
717         for (pos = hlist_entry_safe(rcu_dereference_bh(hlist_first_rcu(head)),\
718                         typeof(*(pos)), member);                        \
719                 pos;                                                    \
720                 pos = hlist_entry_safe(rcu_dereference_bh(hlist_next_rcu(\
721                         &(pos)->member)), typeof(*(pos)), member))
722 
723 /**
724  * hlist_for_each_entry_continue_rcu - iterate over a hlist continuing after current point
725  * @pos:        the type * to use as a loop cursor.
726  * @member:     the name of the hlist_node within the struct.
727  */
728 #define hlist_for_each_entry_continue_rcu(pos, member)                  \
729         for (pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu( \
730                         &(pos)->member)), typeof(*(pos)), member);      \
731              pos;                                                       \
732              pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu( \
733                         &(pos)->member)), typeof(*(pos)), member))
734 
735 /**
736  * hlist_for_each_entry_continue_rcu_bh - iterate over a hlist continuing after current point
737  * @pos:        the type * to use as a loop cursor.
738  * @member:     the name of the hlist_node within the struct.
739  */
740 #define hlist_for_each_entry_continue_rcu_bh(pos, member)               \
741         for (pos = hlist_entry_safe(rcu_dereference_bh(hlist_next_rcu(  \
742                         &(pos)->member)), typeof(*(pos)), member);      \
743              pos;                                                       \
744              pos = hlist_entry_safe(rcu_dereference_bh(hlist_next_rcu(  \
745                         &(pos)->member)), typeof(*(pos)), member))
746 
747 /**
748  * hlist_for_each_entry_from_rcu - iterate over a hlist continuing from current point
749  * @pos:        the type * to use as a loop cursor.
750  * @member:     the name of the hlist_node within the struct.
751  */
752 #define hlist_for_each_entry_from_rcu(pos, member)                      \
753         for (; pos;                                                     \
754              pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu( \
755                         &(pos)->member)), typeof(*(pos)), member))
756 
757 #endif  /* __KERNEL__ */
758 #endif
759 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp