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

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

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

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