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

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

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

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