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

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

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

~ [ 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