f31ef61f1c650b585bd6faf969f7cec754dffe2d
[linux-2.6.git] / include / linux / rculist.h
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 #define __list_for_each_rcu(pos, head) \
245         for (pos = rcu_dereference_raw(list_next_rcu(head)); \
246                 pos != (head); \
247                 pos = rcu_dereference_raw(list_next_rcu((pos)))
248
249 /**
250  * list_for_each_entry_rcu      -       iterate over rcu list of given type
251  * @pos:        the type * to use as a loop cursor.
252  * @head:       the head for your list.
253  * @member:     the name of the list_struct within the struct.
254  *
255  * This list-traversal primitive may safely run concurrently with
256  * the _rcu list-mutation primitives such as list_add_rcu()
257  * as long as the traversal is guarded by rcu_read_lock().
258  */
259 #define list_for_each_entry_rcu(pos, head, member) \
260         for (pos = list_entry_rcu((head)->next, typeof(*pos), member); \
261                 prefetch(pos->member.next), &pos->member != (head); \
262                 pos = list_entry_rcu(pos->member.next, typeof(*pos), member))
263
264
265 /**
266  * list_for_each_continue_rcu
267  * @pos:        the &struct list_head to use as a loop cursor.
268  * @head:       the head for your list.
269  *
270  * Iterate over an rcu-protected list, continuing after current point.
271  *
272  * This list-traversal primitive may safely run concurrently with
273  * the _rcu list-mutation primitives such as list_add_rcu()
274  * as long as the traversal is guarded by rcu_read_lock().
275  */
276 #define list_for_each_continue_rcu(pos, head) \
277         for ((pos) = rcu_dereference_raw(list_next_rcu(pos)); \
278                 prefetch((pos)->next), (pos) != (head); \
279                 (pos) = rcu_dereference_raw(list_next_rcu(pos)))
280
281 /**
282  * list_for_each_entry_continue_rcu - continue iteration over list of given type
283  * @pos:        the type * to use as a loop cursor.
284  * @head:       the head for your list.
285  * @member:     the name of the list_struct within the struct.
286  *
287  * Continue to iterate over list of given type, continuing after
288  * the current position.
289  */
290 #define list_for_each_entry_continue_rcu(pos, head, member)             \
291         for (pos = list_entry_rcu(pos->member.next, typeof(*pos), member); \
292              prefetch(pos->member.next), &pos->member != (head);        \
293              pos = list_entry_rcu(pos->member.next, typeof(*pos), member))
294
295 /**
296  * hlist_del_rcu - deletes entry from hash list without re-initialization
297  * @n: the element to delete from the hash list.
298  *
299  * Note: list_unhashed() on entry does not return true after this,
300  * the entry is in an undefined state. It is useful for RCU based
301  * lockfree traversal.
302  *
303  * In particular, it means that we can not poison the forward
304  * pointers that may still be used for walking the hash list.
305  *
306  * The caller must take whatever precautions are necessary
307  * (such as holding appropriate locks) to avoid racing
308  * with another list-mutation primitive, such as hlist_add_head_rcu()
309  * or hlist_del_rcu(), running on this same list.
310  * However, it is perfectly legal to run concurrently with
311  * the _rcu list-traversal primitives, such as
312  * hlist_for_each_entry().
313  */
314 static inline void hlist_del_rcu(struct hlist_node *n)
315 {
316         __hlist_del(n);
317         n->pprev = LIST_POISON2;
318 }
319
320 /**
321  * hlist_replace_rcu - replace old entry by new one
322  * @old : the element to be replaced
323  * @new : the new element to insert
324  *
325  * The @old entry will be replaced with the @new entry atomically.
326  */
327 static inline void hlist_replace_rcu(struct hlist_node *old,
328                                         struct hlist_node *new)
329 {
330         struct hlist_node *next = old->next;
331
332         new->next = next;
333         new->pprev = old->pprev;
334         rcu_assign_pointer(*(struct hlist_node __rcu **)new->pprev, new);
335         if (next)
336                 new->next->pprev = &new->next;
337         old->pprev = LIST_POISON2;
338 }
339
340 /*
341  * return the first or the next element in an RCU protected hlist
342  */
343 #define hlist_first_rcu(head)   (*((struct hlist_node __rcu **)(&(head)->first)))
344 #define hlist_next_rcu(node)    (*((struct hlist_node __rcu **)(&(node)->next)))
345 #define hlist_pprev_rcu(node)   (*((struct hlist_node __rcu **)((node)->pprev)))
346
347 /**
348  * hlist_add_head_rcu
349  * @n: the element to add to the hash list.
350  * @h: the list to add to.
351  *
352  * Description:
353  * Adds the specified element to the specified hlist,
354  * while permitting racing traversals.
355  *
356  * The caller must take whatever precautions are necessary
357  * (such as holding appropriate locks) to avoid racing
358  * with another list-mutation primitive, such as hlist_add_head_rcu()
359  * or hlist_del_rcu(), running on this same list.
360  * However, it is perfectly legal to run concurrently with
361  * the _rcu list-traversal primitives, such as
362  * hlist_for_each_entry_rcu(), used to prevent memory-consistency
363  * problems on Alpha CPUs.  Regardless of the type of CPU, the
364  * list-traversal primitive must be guarded by rcu_read_lock().
365  */
366 static inline void hlist_add_head_rcu(struct hlist_node *n,
367                                         struct hlist_head *h)
368 {
369         struct hlist_node *first = h->first;
370
371         n->next = first;
372         n->pprev = &h->first;
373         rcu_assign_pointer(hlist_first_rcu(h), n);
374         if (first)
375                 first->pprev = &n->next;
376 }
377
378 /**
379  * hlist_add_before_rcu
380  * @n: the new element to add to the hash list.
381  * @next: the existing element to add the new element before.
382  *
383  * Description:
384  * Adds the specified element to the specified hlist
385  * before the specified node while permitting racing traversals.
386  *
387  * The caller must take whatever precautions are necessary
388  * (such as holding appropriate locks) to avoid racing
389  * with another list-mutation primitive, such as hlist_add_head_rcu()
390  * or hlist_del_rcu(), running on this same list.
391  * However, it is perfectly legal to run concurrently with
392  * the _rcu list-traversal primitives, such as
393  * hlist_for_each_entry_rcu(), used to prevent memory-consistency
394  * problems on Alpha CPUs.
395  */
396 static inline void hlist_add_before_rcu(struct hlist_node *n,
397                                         struct hlist_node *next)
398 {
399         n->pprev = next->pprev;
400         n->next = next;
401         rcu_assign_pointer(hlist_pprev_rcu(n), n);
402         next->pprev = &n->next;
403 }
404
405 /**
406  * hlist_add_after_rcu
407  * @prev: the existing element to add the new element after.
408  * @n: the new element to add to the hash list.
409  *
410  * Description:
411  * Adds the specified element to the specified hlist
412  * after the specified node while permitting racing traversals.
413  *
414  * The caller must take whatever precautions are necessary
415  * (such as holding appropriate locks) to avoid racing
416  * with another list-mutation primitive, such as hlist_add_head_rcu()
417  * or hlist_del_rcu(), running on this same list.
418  * However, it is perfectly legal to run concurrently with
419  * the _rcu list-traversal primitives, such as
420  * hlist_for_each_entry_rcu(), used to prevent memory-consistency
421  * problems on Alpha CPUs.
422  */
423 static inline void hlist_add_after_rcu(struct hlist_node *prev,
424                                        struct hlist_node *n)
425 {
426         n->next = prev->next;
427         n->pprev = &prev->next;
428         rcu_assign_pointer(hlist_next_rcu(prev), n);
429         if (n->next)
430                 n->next->pprev = &n->next;
431 }
432
433 #define __hlist_for_each_rcu(pos, head)                         \
434         for (pos = rcu_dereference(hlist_first_rcu(head));      \
435              pos && ({ prefetch(pos->next); 1; });              \
436              pos = rcu_dereference(hlist_next_rcu(pos)))
437
438 /**
439  * hlist_for_each_entry_rcu - iterate over rcu list of given type
440  * @tpos:       the type * to use as a loop cursor.
441  * @pos:        the &struct hlist_node to use as a loop cursor.
442  * @head:       the head for your list.
443  * @member:     the name of the hlist_node within the struct.
444  *
445  * This list-traversal primitive may safely run concurrently with
446  * the _rcu list-mutation primitives such as hlist_add_head_rcu()
447  * as long as the traversal is guarded by rcu_read_lock().
448  */
449 #define hlist_for_each_entry_rcu(tpos, pos, head, member)               \
450         for (pos = rcu_dereference_raw(hlist_first_rcu(head));          \
451                 pos && ({ prefetch(pos->next); 1; }) &&                  \
452                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1; }); \
453                 pos = rcu_dereference_raw(hlist_next_rcu(pos)))
454
455 /**
456  * hlist_for_each_entry_rcu_bh - iterate over rcu list of given type
457  * @tpos:       the type * to use as a loop cursor.
458  * @pos:        the &struct hlist_node to use as a loop cursor.
459  * @head:       the head for your list.
460  * @member:     the name of the hlist_node within the struct.
461  *
462  * This list-traversal primitive may safely run concurrently with
463  * the _rcu list-mutation primitives such as hlist_add_head_rcu()
464  * as long as the traversal is guarded by rcu_read_lock().
465  */
466 #define hlist_for_each_entry_rcu_bh(tpos, pos, head, member)             \
467         for (pos = rcu_dereference_bh((head)->first);                    \
468                 pos && ({ prefetch(pos->next); 1; }) &&                  \
469                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1; }); \
470                 pos = rcu_dereference_bh(pos->next))
471
472 /**
473  * hlist_for_each_entry_continue_rcu - iterate over a hlist continuing after current point
474  * @tpos:       the type * to use as a loop cursor.
475  * @pos:        the &struct hlist_node to use as a loop cursor.
476  * @member:     the name of the hlist_node within the struct.
477  */
478 #define hlist_for_each_entry_continue_rcu(tpos, pos, member)            \
479         for (pos = rcu_dereference((pos)->next);                        \
480              pos && ({ prefetch(pos->next); 1; }) &&                    \
481              ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1; });  \
482              pos = rcu_dereference(pos->next))
483
484 /**
485  * hlist_for_each_entry_continue_rcu_bh - iterate over a hlist continuing after current point
486  * @tpos:       the type * to use as a loop cursor.
487  * @pos:        the &struct hlist_node to use as a loop cursor.
488  * @member:     the name of the hlist_node within the struct.
489  */
490 #define hlist_for_each_entry_continue_rcu_bh(tpos, pos, member)         \
491         for (pos = rcu_dereference_bh((pos)->next);                     \
492              pos && ({ prefetch(pos->next); 1; }) &&                    \
493              ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1; });  \
494              pos = rcu_dereference_bh(pos->next))
495
496
497 #endif  /* __KERNEL__ */
498 #endif