rcu: split list.h and move rcu-protected lists into rculist.h
[linux-3.10.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
11 /*
12  * Insert a new entry between two known consecutive entries.
13  *
14  * This is only for internal list manipulation where we know
15  * the prev/next entries already!
16  */
17 static inline void __list_add_rcu(struct list_head *new,
18                 struct list_head *prev, struct list_head *next)
19 {
20         new->next = next;
21         new->prev = prev;
22         smp_wmb();
23         next->prev = new;
24         prev->next = new;
25 }
26
27 /**
28  * list_add_rcu - add a new entry to rcu-protected list
29  * @new: new entry to be added
30  * @head: list head to add it after
31  *
32  * Insert a new entry after the specified head.
33  * This is good for implementing stacks.
34  *
35  * The caller must take whatever precautions are necessary
36  * (such as holding appropriate locks) to avoid racing
37  * with another list-mutation primitive, such as list_add_rcu()
38  * or list_del_rcu(), running on this same list.
39  * However, it is perfectly legal to run concurrently with
40  * the _rcu list-traversal primitives, such as
41  * list_for_each_entry_rcu().
42  */
43 static inline void list_add_rcu(struct list_head *new, struct list_head *head)
44 {
45         __list_add_rcu(new, head, head->next);
46 }
47
48 /**
49  * list_add_tail_rcu - add a new entry to rcu-protected list
50  * @new: new entry to be added
51  * @head: list head to add it before
52  *
53  * Insert a new entry before the specified head.
54  * This is useful for implementing queues.
55  *
56  * The caller must take whatever precautions are necessary
57  * (such as holding appropriate locks) to avoid racing
58  * with another list-mutation primitive, such as list_add_tail_rcu()
59  * or list_del_rcu(), running on this same list.
60  * However, it is perfectly legal to run concurrently with
61  * the _rcu list-traversal primitives, such as
62  * list_for_each_entry_rcu().
63  */
64 static inline void list_add_tail_rcu(struct list_head *new,
65                                         struct list_head *head)
66 {
67         __list_add_rcu(new, head->prev, head);
68 }
69
70 /**
71  * list_del_rcu - deletes entry from list without re-initialization
72  * @entry: the element to delete from the list.
73  *
74  * Note: list_empty() on entry does not return true after this,
75  * the entry is in an undefined state. It is useful for RCU based
76  * lockfree traversal.
77  *
78  * In particular, it means that we can not poison the forward
79  * pointers that may still be used for walking the list.
80  *
81  * The caller must take whatever precautions are necessary
82  * (such as holding appropriate locks) to avoid racing
83  * with another list-mutation primitive, such as list_del_rcu()
84  * or list_add_rcu(), running on this same list.
85  * However, it is perfectly legal to run concurrently with
86  * the _rcu list-traversal primitives, such as
87  * list_for_each_entry_rcu().
88  *
89  * Note that the caller is not permitted to immediately free
90  * the newly deleted entry.  Instead, either synchronize_rcu()
91  * or call_rcu() must be used to defer freeing until an RCU
92  * grace period has elapsed.
93  */
94 static inline void list_del_rcu(struct list_head *entry)
95 {
96         __list_del(entry->prev, entry->next);
97         entry->prev = LIST_POISON2;
98 }
99
100 /**
101  * list_replace_rcu - replace old entry by new one
102  * @old : the element to be replaced
103  * @new : the new element to insert
104  *
105  * The @old entry will be replaced with the @new entry atomically.
106  * Note: @old should not be empty.
107  */
108 static inline void list_replace_rcu(struct list_head *old,
109                                 struct list_head *new)
110 {
111         new->next = old->next;
112         new->prev = old->prev;
113         smp_wmb();
114         new->next->prev = new;
115         new->prev->next = new;
116         old->prev = LIST_POISON2;
117 }
118
119 /**
120  * list_splice_init_rcu - splice an RCU-protected list into an existing list.
121  * @list:       the RCU-protected list to splice
122  * @head:       the place in the list to splice the first list into
123  * @sync:       function to sync: synchronize_rcu(), synchronize_sched(), ...
124  *
125  * @head can be RCU-read traversed concurrently with this function.
126  *
127  * Note that this function blocks.
128  *
129  * Important note: the caller must take whatever action is necessary to
130  *      prevent any other updates to @head.  In principle, it is possible
131  *      to modify the list as soon as sync() begins execution.
132  *      If this sort of thing becomes necessary, an alternative version
133  *      based on call_rcu() could be created.  But only if -really-
134  *      needed -- there is no shortage of RCU API members.
135  */
136 static inline void list_splice_init_rcu(struct list_head *list,
137                                         struct list_head *head,
138                                         void (*sync)(void))
139 {
140         struct list_head *first = list->next;
141         struct list_head *last = list->prev;
142         struct list_head *at = head->next;
143
144         if (list_empty(head))
145                 return;
146
147         /* "first" and "last" tracking list, so initialize it. */
148
149         INIT_LIST_HEAD(list);
150
151         /*
152          * At this point, the list body still points to the source list.
153          * Wait for any readers to finish using the list before splicing
154          * the list body into the new list.  Any new readers will see
155          * an empty list.
156          */
157
158         sync();
159
160         /*
161          * Readers are finished with the source list, so perform splice.
162          * The order is important if the new list is global and accessible
163          * to concurrent RCU readers.  Note that RCU readers are not
164          * permitted to traverse the prev pointers without excluding
165          * this function.
166          */
167
168         last->next = at;
169         smp_wmb();
170         head->next = first;
171         first->prev = head;
172         at->prev = last;
173 }
174
175 /**
176  * list_for_each_rcu    -       iterate over an rcu-protected list
177  * @pos:        the &struct list_head to use as a loop cursor.
178  * @head:       the head for your list.
179  *
180  * This list-traversal primitive may safely run concurrently with
181  * the _rcu list-mutation primitives such as list_add_rcu()
182  * as long as the traversal is guarded by rcu_read_lock().
183  */
184 #define list_for_each_rcu(pos, head) \
185         for (pos = (head)->next; \
186                 prefetch(rcu_dereference(pos)->next), pos != (head); \
187                 pos = pos->next)
188
189 #define __list_for_each_rcu(pos, head) \
190         for (pos = (head)->next; \
191                 rcu_dereference(pos) != (head); \
192                 pos = pos->next)
193
194 /**
195  * list_for_each_safe_rcu
196  * @pos:        the &struct list_head to use as a loop cursor.
197  * @n:          another &struct list_head to use as temporary storage
198  * @head:       the head for your list.
199  *
200  * Iterate over an rcu-protected list, safe against removal of list entry.
201  *
202  * This list-traversal primitive may safely run concurrently with
203  * the _rcu list-mutation primitives such as list_add_rcu()
204  * as long as the traversal is guarded by rcu_read_lock().
205  */
206 #define list_for_each_safe_rcu(pos, n, head) \
207         for (pos = (head)->next; \
208                 n = rcu_dereference(pos)->next, pos != (head); \
209                 pos = n)
210
211 /**
212  * list_for_each_entry_rcu      -       iterate over rcu list of given type
213  * @pos:        the type * to use as a loop cursor.
214  * @head:       the head for your list.
215  * @member:     the name of the list_struct within the struct.
216  *
217  * This list-traversal primitive may safely run concurrently with
218  * the _rcu list-mutation primitives such as list_add_rcu()
219  * as long as the traversal is guarded by rcu_read_lock().
220  */
221 #define list_for_each_entry_rcu(pos, head, member) \
222         for (pos = list_entry((head)->next, typeof(*pos), member); \
223                 prefetch(rcu_dereference(pos)->member.next), \
224                         &pos->member != (head); \
225                 pos = list_entry(pos->member.next, typeof(*pos), member))
226
227
228 /**
229  * list_for_each_continue_rcu
230  * @pos:        the &struct list_head to use as a loop cursor.
231  * @head:       the head for your list.
232  *
233  * Iterate over an rcu-protected list, continuing after current point.
234  *
235  * This list-traversal primitive may safely run concurrently with
236  * the _rcu list-mutation primitives such as list_add_rcu()
237  * as long as the traversal is guarded by rcu_read_lock().
238  */
239 #define list_for_each_continue_rcu(pos, head) \
240         for ((pos) = (pos)->next; \
241                 prefetch(rcu_dereference((pos))->next), (pos) != (head); \
242                 (pos) = (pos)->next)
243
244 /**
245  * hlist_del_rcu - deletes entry from hash list without re-initialization
246  * @n: the element to delete from the hash list.
247  *
248  * Note: list_unhashed() on entry does not return true after this,
249  * the entry is in an undefined state. It is useful for RCU based
250  * lockfree traversal.
251  *
252  * In particular, it means that we can not poison the forward
253  * pointers that may still be used for walking the hash list.
254  *
255  * The caller must take whatever precautions are necessary
256  * (such as holding appropriate locks) to avoid racing
257  * with another list-mutation primitive, such as hlist_add_head_rcu()
258  * or hlist_del_rcu(), running on this same list.
259  * However, it is perfectly legal to run concurrently with
260  * the _rcu list-traversal primitives, such as
261  * hlist_for_each_entry().
262  */
263 static inline void hlist_del_rcu(struct hlist_node *n)
264 {
265         __hlist_del(n);
266         n->pprev = LIST_POISON2;
267 }
268
269 /**
270  * hlist_replace_rcu - replace old entry by new one
271  * @old : the element to be replaced
272  * @new : the new element to insert
273  *
274  * The @old entry will be replaced with the @new entry atomically.
275  */
276 static inline void hlist_replace_rcu(struct hlist_node *old,
277                                         struct hlist_node *new)
278 {
279         struct hlist_node *next = old->next;
280
281         new->next = next;
282         new->pprev = old->pprev;
283         smp_wmb();
284         if (next)
285                 new->next->pprev = &new->next;
286         *new->pprev = new;
287         old->pprev = LIST_POISON2;
288 }
289
290 /**
291  * hlist_add_head_rcu
292  * @n: the element to add to the hash list.
293  * @h: the list to add to.
294  *
295  * Description:
296  * Adds the specified element to the specified hlist,
297  * while permitting racing traversals.
298  *
299  * The caller must take whatever precautions are necessary
300  * (such as holding appropriate locks) to avoid racing
301  * with another list-mutation primitive, such as hlist_add_head_rcu()
302  * or hlist_del_rcu(), running on this same list.
303  * However, it is perfectly legal to run concurrently with
304  * the _rcu list-traversal primitives, such as
305  * hlist_for_each_entry_rcu(), used to prevent memory-consistency
306  * problems on Alpha CPUs.  Regardless of the type of CPU, the
307  * list-traversal primitive must be guarded by rcu_read_lock().
308  */
309 static inline void hlist_add_head_rcu(struct hlist_node *n,
310                                         struct hlist_head *h)
311 {
312         struct hlist_node *first = h->first;
313         n->next = first;
314         n->pprev = &h->first;
315         smp_wmb();
316         if (first)
317                 first->pprev = &n->next;
318         h->first = n;
319 }
320
321 /**
322  * hlist_add_before_rcu
323  * @n: the new element to add to the hash list.
324  * @next: the existing element to add the new element before.
325  *
326  * Description:
327  * Adds the specified element to the specified hlist
328  * before the specified node while permitting racing traversals.
329  *
330  * The caller must take whatever precautions are necessary
331  * (such as holding appropriate locks) to avoid racing
332  * with another list-mutation primitive, such as hlist_add_head_rcu()
333  * or hlist_del_rcu(), running on this same list.
334  * However, it is perfectly legal to run concurrently with
335  * the _rcu list-traversal primitives, such as
336  * hlist_for_each_entry_rcu(), used to prevent memory-consistency
337  * problems on Alpha CPUs.
338  */
339 static inline void hlist_add_before_rcu(struct hlist_node *n,
340                                         struct hlist_node *next)
341 {
342         n->pprev = next->pprev;
343         n->next = next;
344         smp_wmb();
345         next->pprev = &n->next;
346         *(n->pprev) = n;
347 }
348
349 /**
350  * hlist_add_after_rcu
351  * @prev: the existing element to add the new element after.
352  * @n: the new element to add to the hash list.
353  *
354  * Description:
355  * Adds the specified element to the specified hlist
356  * after the specified node while permitting racing traversals.
357  *
358  * The caller must take whatever precautions are necessary
359  * (such as holding appropriate locks) to avoid racing
360  * with another list-mutation primitive, such as hlist_add_head_rcu()
361  * or hlist_del_rcu(), running on this same list.
362  * However, it is perfectly legal to run concurrently with
363  * the _rcu list-traversal primitives, such as
364  * hlist_for_each_entry_rcu(), used to prevent memory-consistency
365  * problems on Alpha CPUs.
366  */
367 static inline void hlist_add_after_rcu(struct hlist_node *prev,
368                                        struct hlist_node *n)
369 {
370         n->next = prev->next;
371         n->pprev = &prev->next;
372         smp_wmb();
373         prev->next = n;
374         if (n->next)
375                 n->next->pprev = &n->next;
376 }
377
378 /**
379  * hlist_for_each_entry_rcu - iterate over rcu list of given type
380  * @tpos:       the type * to use as a loop cursor.
381  * @pos:        the &struct hlist_node to use as a loop cursor.
382  * @head:       the head for your list.
383  * @member:     the name of the hlist_node within the struct.
384  *
385  * This list-traversal primitive may safely run concurrently with
386  * the _rcu list-mutation primitives such as hlist_add_head_rcu()
387  * as long as the traversal is guarded by rcu_read_lock().
388  */
389 #define hlist_for_each_entry_rcu(tpos, pos, head, member)                \
390         for (pos = (head)->first;                                        \
391              rcu_dereference(pos) && ({ prefetch(pos->next); 1; }) &&    \
392                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1; }); \
393              pos = pos->next)
394
395 #endif  /* __KERNEL__ */
396 #endif