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

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

Version: ~ [ linux-5.13-rc5 ] ~ [ linux-5.12.9 ] ~ [ linux-5.11.22 ] ~ [ linux-5.10.42 ] ~ [ linux-5.9.16 ] ~ [ linux-5.8.18 ] ~ [ linux-5.7.19 ] ~ [ linux-5.6.19 ] ~ [ linux-5.5.19 ] ~ [ linux-5.4.124 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.193 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.235 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.271 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.271 ] ~ [ 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 #ifndef _LINUX_RCULIST_H
  2 #define _LINUX_RCULIST_H
  3 
  4 #ifdef __KERNEL__
  5 
  6 /*
  7  * RCU-protected list version
  8  */
  9 #include <linux/list.h>
 10 #include <linux/rcupdate.h>
 11 
 12 /*
 13  * Why is there no list_empty_rcu()?  Because list_empty() serves this
 14  * purpose.  The list_empty() function fetches the RCU-protected pointer
 15  * and compares it to the address of the list head, but neither dereferences
 16  * this pointer itself nor provides this pointer to the caller.  Therefore,
 17  * it is not necessary to use rcu_dereference(), so that list_empty() can
 18  * be used anywhere you would want to use a list_empty_rcu().
 19  */
 20 
 21 /*
 22  * INIT_LIST_HEAD_RCU - Initialize a list_head visible to RCU readers
 23  * @list: list to be initialized
 24  *
 25  * You should instead use INIT_LIST_HEAD() for normal initialization and
 26  * cleanup tasks, when readers have no access to the list being initialized.
 27  * However, if the list being initialized is visible to readers, you
 28  * need to keep the compiler from being too mischievous.
 29  */
 30 static inline void INIT_LIST_HEAD_RCU(struct list_head *list)
 31 {
 32         ACCESS_ONCE(list->next) = list;
 33         ACCESS_ONCE(list->prev) = list;
 34 }
 35 
 36 /*
 37  * return the ->next pointer of a list_head in an rcu safe
 38  * way, we must not access it directly
 39  */
 40 #define list_next_rcu(list)     (*((struct list_head __rcu **)(&(list)->next)))
 41 
 42 /*
 43  * Insert a new entry between two known consecutive entries.
 44  *
 45  * This is only for internal list manipulation where we know
 46  * the prev/next entries already!
 47  */
 48 #ifndef CONFIG_DEBUG_LIST
 49 static inline void __list_add_rcu(struct list_head *new,
 50                 struct list_head *prev, struct list_head *next)
 51 {
 52         new->next = next;
 53         new->prev = prev;
 54         rcu_assign_pointer(list_next_rcu(prev), new);
 55         next->prev = new;
 56 }
 57 #else
 58 void __list_add_rcu(struct list_head *new,
 59                     struct list_head *prev, struct list_head *next);
 60 #endif
 61 
 62 /**
 63  * list_add_rcu - add a new entry to rcu-protected list
 64  * @new: new entry to be added
 65  * @head: list head to add it after
 66  *
 67  * Insert a new entry after the specified head.
 68  * This is good for implementing stacks.
 69  *
 70  * The caller must take whatever precautions are necessary
 71  * (such as holding appropriate locks) to avoid racing
 72  * with another list-mutation primitive, such as list_add_rcu()
 73  * or list_del_rcu(), running on this same list.
 74  * However, it is perfectly legal to run concurrently with
 75  * the _rcu list-traversal primitives, such as
 76  * list_for_each_entry_rcu().
 77  */
 78 static inline void list_add_rcu(struct list_head *new, struct list_head *head)
 79 {
 80         __list_add_rcu(new, head, head->next);
 81 }
 82 
 83 /**
 84  * list_add_tail_rcu - add a new entry to rcu-protected list
 85  * @new: new entry to be added
 86  * @head: list head to add it before
 87  *
 88  * Insert a new entry before the specified head.
 89  * This is useful for implementing queues.
 90  *
 91  * The caller must take whatever precautions are necessary
 92  * (such as holding appropriate locks) to avoid racing
 93  * with another list-mutation primitive, such as list_add_tail_rcu()
 94  * or list_del_rcu(), running on this same list.
 95  * However, it is perfectly legal to run concurrently with
 96  * the _rcu list-traversal primitives, such as
 97  * list_for_each_entry_rcu().
 98  */
 99 static inline void list_add_tail_rcu(struct list_head *new,
100                                         struct list_head *head)
101 {
102         __list_add_rcu(new, head->prev, head);
103 }
104 
105 /**
106  * list_del_rcu - deletes entry from list without re-initialization
107  * @entry: the element to delete from the list.
108  *
109  * Note: list_empty() on entry does not return true after this,
110  * the entry is in an undefined state. It is useful for RCU based
111  * lockfree traversal.
112  *
113  * In particular, it means that we can not poison the forward
114  * pointers that may still be used for walking the list.
115  *
116  * The caller must take whatever precautions are necessary
117  * (such as holding appropriate locks) to avoid racing
118  * with another list-mutation primitive, such as list_del_rcu()
119  * or list_add_rcu(), running on this same list.
120  * However, it is perfectly legal to run concurrently with
121  * the _rcu list-traversal primitives, such as
122  * list_for_each_entry_rcu().
123  *
124  * Note that the caller is not permitted to immediately free
125  * the newly deleted entry.  Instead, either synchronize_rcu()
126  * or call_rcu() must be used to defer freeing until an RCU
127  * grace period has elapsed.
128  */
129 static inline void list_del_rcu(struct list_head *entry)
130 {
131         __list_del_entry(entry);
132         entry->prev = LIST_POISON2;
133 }
134 
135 /**
136  * hlist_del_init_rcu - deletes entry from hash list with re-initialization
137  * @n: the element to delete from the hash list.
138  *
139  * Note: list_unhashed() on the node return true after this. It is
140  * useful for RCU based read lockfree traversal if the writer side
141  * must know if the list entry is still hashed or already unhashed.
142  *
143  * In particular, it means that we can not poison the forward pointers
144  * that may still be used for walking the hash list and we can only
145  * zero the pprev pointer so list_unhashed() will return true after
146  * this.
147  *
148  * The caller must take whatever precautions are necessary (such as
149  * holding appropriate locks) to avoid racing with another
150  * list-mutation primitive, such as hlist_add_head_rcu() or
151  * hlist_del_rcu(), running on this same list.  However, it is
152  * perfectly legal to run concurrently with the _rcu list-traversal
153  * primitives, such as hlist_for_each_entry_rcu().
154  */
155 static inline void hlist_del_init_rcu(struct hlist_node *n)
156 {
157         if (!hlist_unhashed(n)) {
158                 __hlist_del(n);
159                 n->pprev = NULL;
160         }
161 }
162 
163 /**
164  * list_replace_rcu - replace old entry by new one
165  * @old : the element to be replaced
166  * @new : the new element to insert
167  *
168  * The @old entry will be replaced with the @new entry atomically.
169  * Note: @old should not be empty.
170  */
171 static inline void list_replace_rcu(struct list_head *old,
172                                 struct list_head *new)
173 {
174         new->next = old->next;
175         new->prev = old->prev;
176         rcu_assign_pointer(list_next_rcu(new->prev), new);
177         new->next->prev = new;
178         old->prev = LIST_POISON2;
179 }
180 
181 /**
182  * list_splice_init_rcu - splice an RCU-protected list into an existing list.
183  * @list:       the RCU-protected list to splice
184  * @head:       the place in the list to splice the first list into
185  * @sync:       function to sync: synchronize_rcu(), synchronize_sched(), ...
186  *
187  * @head can be RCU-read traversed concurrently with this function.
188  *
189  * Note that this function blocks.
190  *
191  * Important note: the caller must take whatever action is necessary to
192  *      prevent any other updates to @head.  In principle, it is possible
193  *      to modify the list as soon as sync() begins execution.
194  *      If this sort of thing becomes necessary, an alternative version
195  *      based on call_rcu() could be created.  But only if -really-
196  *      needed -- there is no shortage of RCU API members.
197  */
198 static inline void list_splice_init_rcu(struct list_head *list,
199                                         struct list_head *head,
200                                         void (*sync)(void))
201 {
202         struct list_head *first = list->next;
203         struct list_head *last = list->prev;
204         struct list_head *at = head->next;
205 
206         if (list_empty(list))
207                 return;
208 
209         /*
210          * "first" and "last" tracking list, so initialize it.  RCU readers
211          * have access to this list, so we must use INIT_LIST_HEAD_RCU()
212          * instead of INIT_LIST_HEAD().
213          */
214 
215         INIT_LIST_HEAD_RCU(list);
216 
217         /*
218          * At this point, the list body still points to the source list.
219          * Wait for any readers to finish using the list before splicing
220          * the list body into the new list.  Any new readers will see
221          * an empty list.
222          */
223 
224         sync();
225 
226         /*
227          * Readers are finished with the source list, so perform splice.
228          * The order is important if the new list is global and accessible
229          * to concurrent RCU readers.  Note that RCU readers are not
230          * permitted to traverse the prev pointers without excluding
231          * this function.
232          */
233 
234         last->next = at;
235         rcu_assign_pointer(list_next_rcu(head), first);
236         first->prev = head;
237         at->prev = last;
238 }
239 
240 /**
241  * list_entry_rcu - get the struct for this entry
242  * @ptr:        the &struct list_head pointer.
243  * @type:       the type of the struct this is embedded in.
244  * @member:     the name of the list_head within the struct.
245  *
246  * This primitive may safely run concurrently with the _rcu list-mutation
247  * primitives such as list_add_rcu() as long as it's guarded by rcu_read_lock().
248  */
249 #define list_entry_rcu(ptr, type, member) \
250 ({ \
251         typeof(*ptr) __rcu *__ptr = (typeof(*ptr) __rcu __force *)ptr; \
252         container_of((typeof(ptr))rcu_dereference_raw(__ptr), type, member); \
253 })
254 
255 /**
256  * Where are list_empty_rcu() and list_first_entry_rcu()?
257  *
258  * Implementing those functions following their counterparts list_empty() and
259  * list_first_entry() is not advisable because they lead to subtle race
260  * conditions as the following snippet shows:
261  *
262  * if (!list_empty_rcu(mylist)) {
263  *      struct foo *bar = list_first_entry_rcu(mylist, struct foo, list_member);
264  *      do_something(bar);
265  * }
266  *
267  * The list may not be empty when list_empty_rcu checks it, but it may be when
268  * list_first_entry_rcu rereads the ->next pointer.
269  *
270  * Rereading the ->next pointer is not a problem for list_empty() and
271  * list_first_entry() because they would be protected by a lock that blocks
272  * writers.
273  *
274  * See list_first_or_null_rcu for an alternative.
275  */
276 
277 /**
278  * list_first_or_null_rcu - get the first element from a list
279  * @ptr:        the list head to take the element from.
280  * @type:       the type of the struct this is embedded in.
281  * @member:     the name of the list_head within the struct.
282  *
283  * Note that if the list is empty, it returns NULL.
284  *
285  * This primitive may safely run concurrently with the _rcu list-mutation
286  * primitives such as list_add_rcu() as long as it's guarded by rcu_read_lock().
287  */
288 #define list_first_or_null_rcu(ptr, type, member) \
289 ({ \
290         struct list_head *__ptr = (ptr); \
291         struct list_head *__next = ACCESS_ONCE(__ptr->next); \
292         likely(__ptr != __next) ? list_entry_rcu(__next, type, member) : NULL; \
293 })
294 
295 /**
296  * list_for_each_entry_rcu      -       iterate over rcu list of given type
297  * @pos:        the type * to use as a loop cursor.
298  * @head:       the head for your list.
299  * @member:     the name of the list_head within the struct.
300  *
301  * This list-traversal primitive may safely run concurrently with
302  * the _rcu list-mutation primitives such as list_add_rcu()
303  * as long as the traversal is guarded by rcu_read_lock().
304  */
305 #define list_for_each_entry_rcu(pos, head, member) \
306         for (pos = list_entry_rcu((head)->next, typeof(*pos), member); \
307                 &pos->member != (head); \
308                 pos = list_entry_rcu(pos->member.next, typeof(*pos), member))
309 
310 /**
311  * list_for_each_entry_continue_rcu - continue iteration over list of given type
312  * @pos:        the type * to use as a loop cursor.
313  * @head:       the head for your list.
314  * @member:     the name of the list_head within the struct.
315  *
316  * Continue to iterate over list of given type, continuing after
317  * the current position.
318  */
319 #define list_for_each_entry_continue_rcu(pos, head, member)             \
320         for (pos = list_entry_rcu(pos->member.next, typeof(*pos), member); \
321              &pos->member != (head);    \
322              pos = list_entry_rcu(pos->member.next, typeof(*pos), member))
323 
324 /**
325  * hlist_del_rcu - deletes entry from hash list without re-initialization
326  * @n: the element to delete from the hash list.
327  *
328  * Note: list_unhashed() on entry does not return true after this,
329  * the entry is in an undefined state. It is useful for RCU based
330  * lockfree traversal.
331  *
332  * In particular, it means that we can not poison the forward
333  * pointers that may still be used for walking the hash list.
334  *
335  * The caller must take whatever precautions are necessary
336  * (such as holding appropriate locks) to avoid racing
337  * with another list-mutation primitive, such as hlist_add_head_rcu()
338  * or hlist_del_rcu(), running on this same list.
339  * However, it is perfectly legal to run concurrently with
340  * the _rcu list-traversal primitives, such as
341  * hlist_for_each_entry().
342  */
343 static inline void hlist_del_rcu(struct hlist_node *n)
344 {
345         __hlist_del(n);
346         n->pprev = LIST_POISON2;
347 }
348 
349 /**
350  * hlist_replace_rcu - replace old entry by new one
351  * @old : the element to be replaced
352  * @new : the new element to insert
353  *
354  * The @old entry will be replaced with the @new entry atomically.
355  */
356 static inline void hlist_replace_rcu(struct hlist_node *old,
357                                         struct hlist_node *new)
358 {
359         struct hlist_node *next = old->next;
360 
361         new->next = next;
362         new->pprev = old->pprev;
363         rcu_assign_pointer(*(struct hlist_node __rcu **)new->pprev, new);
364         if (next)
365                 new->next->pprev = &new->next;
366         old->pprev = LIST_POISON2;
367 }
368 
369 /*
370  * return the first or the next element in an RCU protected hlist
371  */
372 #define hlist_first_rcu(head)   (*((struct hlist_node __rcu **)(&(head)->first)))
373 #define hlist_next_rcu(node)    (*((struct hlist_node __rcu **)(&(node)->next)))
374 #define hlist_pprev_rcu(node)   (*((struct hlist_node __rcu **)((node)->pprev)))
375 
376 /**
377  * hlist_add_head_rcu
378  * @n: the element to add to the hash list.
379  * @h: the list to add to.
380  *
381  * Description:
382  * Adds the specified element to the specified hlist,
383  * while permitting racing traversals.
384  *
385  * The caller must take whatever precautions are necessary
386  * (such as holding appropriate locks) to avoid racing
387  * with another list-mutation primitive, such as hlist_add_head_rcu()
388  * or hlist_del_rcu(), running on this same list.
389  * However, it is perfectly legal to run concurrently with
390  * the _rcu list-traversal primitives, such as
391  * hlist_for_each_entry_rcu(), used to prevent memory-consistency
392  * problems on Alpha CPUs.  Regardless of the type of CPU, the
393  * list-traversal primitive must be guarded by rcu_read_lock().
394  */
395 static inline void hlist_add_head_rcu(struct hlist_node *n,
396                                         struct hlist_head *h)
397 {
398         struct hlist_node *first = h->first;
399 
400         n->next = first;
401         n->pprev = &h->first;
402         rcu_assign_pointer(hlist_first_rcu(h), n);
403         if (first)
404                 first->pprev = &n->next;
405 }
406 
407 /**
408  * hlist_add_before_rcu
409  * @n: the new element to add to the hash list.
410  * @next: the existing element to add the new element before.
411  *
412  * Description:
413  * Adds the specified element to the specified hlist
414  * before the specified node while permitting racing traversals.
415  *
416  * The caller must take whatever precautions are necessary
417  * (such as holding appropriate locks) to avoid racing
418  * with another list-mutation primitive, such as hlist_add_head_rcu()
419  * or hlist_del_rcu(), running on this same list.
420  * However, it is perfectly legal to run concurrently with
421  * the _rcu list-traversal primitives, such as
422  * hlist_for_each_entry_rcu(), used to prevent memory-consistency
423  * problems on Alpha CPUs.
424  */
425 static inline void hlist_add_before_rcu(struct hlist_node *n,
426                                         struct hlist_node *next)
427 {
428         n->pprev = next->pprev;
429         n->next = next;
430         rcu_assign_pointer(hlist_pprev_rcu(n), n);
431         next->pprev = &n->next;
432 }
433 
434 /**
435  * hlist_add_behind_rcu
436  * @n: the new element to add to the hash list.
437  * @prev: the existing element to add the new element after.
438  *
439  * Description:
440  * Adds the specified element to the specified hlist
441  * after the specified node while permitting racing traversals.
442  *
443  * The caller must take whatever precautions are necessary
444  * (such as holding appropriate locks) to avoid racing
445  * with another list-mutation primitive, such as hlist_add_head_rcu()
446  * or hlist_del_rcu(), running on this same list.
447  * However, it is perfectly legal to run concurrently with
448  * the _rcu list-traversal primitives, such as
449  * hlist_for_each_entry_rcu(), used to prevent memory-consistency
450  * problems on Alpha CPUs.
451  */
452 static inline void hlist_add_behind_rcu(struct hlist_node *n,
453                                         struct hlist_node *prev)
454 {
455         n->next = prev->next;
456         n->pprev = &prev->next;
457         rcu_assign_pointer(hlist_next_rcu(prev), n);
458         if (n->next)
459                 n->next->pprev = &n->next;
460 }
461 
462 #define __hlist_for_each_rcu(pos, head)                         \
463         for (pos = rcu_dereference(hlist_first_rcu(head));      \
464              pos;                                               \
465              pos = rcu_dereference(hlist_next_rcu(pos)))
466 
467 /**
468  * hlist_for_each_entry_rcu - iterate over rcu list of given type
469  * @pos:        the type * to use as a loop cursor.
470  * @head:       the head for your list.
471  * @member:     the name of the hlist_node within the struct.
472  *
473  * This list-traversal primitive may safely run concurrently with
474  * the _rcu list-mutation primitives such as hlist_add_head_rcu()
475  * as long as the traversal is guarded by rcu_read_lock().
476  */
477 #define hlist_for_each_entry_rcu(pos, head, member)                     \
478         for (pos = hlist_entry_safe (rcu_dereference_raw(hlist_first_rcu(head)),\
479                         typeof(*(pos)), member);                        \
480                 pos;                                                    \
481                 pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu(\
482                         &(pos)->member)), typeof(*(pos)), member))
483 
484 /**
485  * hlist_for_each_entry_rcu_notrace - iterate over rcu list of given type (for tracing)
486  * @pos:        the type * to use as a loop cursor.
487  * @head:       the head for your list.
488  * @member:     the name of the hlist_node within the struct.
489  *
490  * This list-traversal primitive may safely run concurrently with
491  * the _rcu list-mutation primitives such as hlist_add_head_rcu()
492  * as long as the traversal is guarded by rcu_read_lock().
493  *
494  * This is the same as hlist_for_each_entry_rcu() except that it does
495  * not do any RCU debugging or tracing.
496  */
497 #define hlist_for_each_entry_rcu_notrace(pos, head, member)                     \
498         for (pos = hlist_entry_safe (rcu_dereference_raw_notrace(hlist_first_rcu(head)),\
499                         typeof(*(pos)), member);                        \
500                 pos;                                                    \
501                 pos = hlist_entry_safe(rcu_dereference_raw_notrace(hlist_next_rcu(\
502                         &(pos)->member)), typeof(*(pos)), member))
503 
504 /**
505  * hlist_for_each_entry_rcu_bh - iterate over rcu list of given type
506  * @pos:        the type * to use as a loop cursor.
507  * @head:       the head for your list.
508  * @member:     the name of the hlist_node within the struct.
509  *
510  * This list-traversal primitive may safely run concurrently with
511  * the _rcu list-mutation primitives such as hlist_add_head_rcu()
512  * as long as the traversal is guarded by rcu_read_lock().
513  */
514 #define hlist_for_each_entry_rcu_bh(pos, head, member)                  \
515         for (pos = hlist_entry_safe(rcu_dereference_bh(hlist_first_rcu(head)),\
516                         typeof(*(pos)), member);                        \
517                 pos;                                                    \
518                 pos = hlist_entry_safe(rcu_dereference_bh(hlist_next_rcu(\
519                         &(pos)->member)), typeof(*(pos)), member))
520 
521 /**
522  * hlist_for_each_entry_continue_rcu - iterate over a hlist continuing after current point
523  * @pos:        the type * to use as a loop cursor.
524  * @member:     the name of the hlist_node within the struct.
525  */
526 #define hlist_for_each_entry_continue_rcu(pos, member)                  \
527         for (pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu( \
528                         &(pos)->member)), typeof(*(pos)), member);      \
529              pos;                                                       \
530              pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu( \
531                         &(pos)->member)), typeof(*(pos)), member))
532 
533 /**
534  * hlist_for_each_entry_continue_rcu_bh - iterate over a hlist continuing after current point
535  * @pos:        the type * to use as a loop cursor.
536  * @member:     the name of the hlist_node within the struct.
537  */
538 #define hlist_for_each_entry_continue_rcu_bh(pos, member)               \
539         for (pos = hlist_entry_safe(rcu_dereference_bh(hlist_next_rcu(  \
540                         &(pos)->member)), typeof(*(pos)), member);      \
541              pos;                                                       \
542              pos = hlist_entry_safe(rcu_dereference_bh(hlist_next_rcu(  \
543                         &(pos)->member)), typeof(*(pos)), member))
544 
545 /**
546  * hlist_for_each_entry_from_rcu - iterate over a hlist continuing from current point
547  * @pos:        the type * to use as a loop cursor.
548  * @member:     the name of the hlist_node within the struct.
549  */
550 #define hlist_for_each_entry_from_rcu(pos, member)                      \
551         for (; pos;                                                     \
552              pos = hlist_entry_safe(rcu_dereference((pos)->member.next),\
553                         typeof(*(pos)), member))
554 
555 #endif  /* __KERNEL__ */
556 #endif
557 

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