[PATCH] add an RCU version of list splicing
[linux-2.6.git] / include / linux / list.h
1 #ifndef _LINUX_LIST_H
2 #define _LINUX_LIST_H
3
4 #ifdef __KERNEL__
5
6 #include <linux/stddef.h>
7 #include <linux/poison.h>
8 #include <linux/prefetch.h>
9 #include <asm/system.h>
10
11 /*
12  * Simple doubly linked list implementation.
13  *
14  * Some of the internal functions ("__xxx") are useful when
15  * manipulating whole lists rather than single entries, as
16  * sometimes we already know the next/prev entries and we can
17  * generate better code by using them directly rather than
18  * using the generic single-entry routines.
19  */
20
21 struct list_head {
22         struct list_head *next, *prev;
23 };
24
25 #define LIST_HEAD_INIT(name) { &(name), &(name) }
26
27 #define LIST_HEAD(name) \
28         struct list_head name = LIST_HEAD_INIT(name)
29
30 static inline void INIT_LIST_HEAD(struct list_head *list)
31 {
32         list->next = list;
33         list->prev = list;
34 }
35
36 /*
37  * Insert a new entry between two known consecutive entries.
38  *
39  * This is only for internal list manipulation where we know
40  * the prev/next entries already!
41  */
42 #ifndef CONFIG_DEBUG_LIST
43 static inline void __list_add(struct list_head *new,
44                               struct list_head *prev,
45                               struct list_head *next)
46 {
47         next->prev = new;
48         new->next = next;
49         new->prev = prev;
50         prev->next = new;
51 }
52 #else
53 extern void __list_add(struct list_head *new,
54                               struct list_head *prev,
55                               struct list_head *next);
56 #endif
57
58 /**
59  * list_add - add a new entry
60  * @new: new entry to be added
61  * @head: list head to add it after
62  *
63  * Insert a new entry after the specified head.
64  * This is good for implementing stacks.
65  */
66 #ifndef CONFIG_DEBUG_LIST
67 static inline void list_add(struct list_head *new, struct list_head *head)
68 {
69         __list_add(new, head, head->next);
70 }
71 #else
72 extern void list_add(struct list_head *new, struct list_head *head);
73 #endif
74
75
76 /**
77  * list_add_tail - add a new entry
78  * @new: new entry to be added
79  * @head: list head to add it before
80  *
81  * Insert a new entry before the specified head.
82  * This is useful for implementing queues.
83  */
84 static inline void list_add_tail(struct list_head *new, struct list_head *head)
85 {
86         __list_add(new, head->prev, head);
87 }
88
89 /*
90  * Insert a new entry between two known consecutive entries.
91  *
92  * This is only for internal list manipulation where we know
93  * the prev/next entries already!
94  */
95 static inline void __list_add_rcu(struct list_head * new,
96                 struct list_head * prev, struct list_head * next)
97 {
98         new->next = next;
99         new->prev = prev;
100         smp_wmb();
101         next->prev = new;
102         prev->next = new;
103 }
104
105 /**
106  * list_add_rcu - add a new entry to rcu-protected list
107  * @new: new entry to be added
108  * @head: list head to add it after
109  *
110  * Insert a new entry after the specified head.
111  * This is good for implementing stacks.
112  *
113  * The caller must take whatever precautions are necessary
114  * (such as holding appropriate locks) to avoid racing
115  * with another list-mutation primitive, such as list_add_rcu()
116  * or list_del_rcu(), running on this same list.
117  * However, it is perfectly legal to run concurrently with
118  * the _rcu list-traversal primitives, such as
119  * list_for_each_entry_rcu().
120  */
121 static inline void list_add_rcu(struct list_head *new, struct list_head *head)
122 {
123         __list_add_rcu(new, head, head->next);
124 }
125
126 /**
127  * list_add_tail_rcu - add a new entry to rcu-protected list
128  * @new: new entry to be added
129  * @head: list head to add it before
130  *
131  * Insert a new entry before the specified head.
132  * This is useful for implementing queues.
133  *
134  * The caller must take whatever precautions are necessary
135  * (such as holding appropriate locks) to avoid racing
136  * with another list-mutation primitive, such as list_add_tail_rcu()
137  * or list_del_rcu(), running on this same list.
138  * However, it is perfectly legal to run concurrently with
139  * the _rcu list-traversal primitives, such as
140  * list_for_each_entry_rcu().
141  */
142 static inline void list_add_tail_rcu(struct list_head *new,
143                                         struct list_head *head)
144 {
145         __list_add_rcu(new, head->prev, head);
146 }
147
148 /*
149  * Delete a list entry by making the prev/next entries
150  * point to each other.
151  *
152  * This is only for internal list manipulation where we know
153  * the prev/next entries already!
154  */
155 static inline void __list_del(struct list_head * prev, struct list_head * next)
156 {
157         next->prev = prev;
158         prev->next = next;
159 }
160
161 /**
162  * list_del - deletes entry from list.
163  * @entry: the element to delete from the list.
164  * Note: list_empty on entry does not return true after this, the entry is
165  * in an undefined state.
166  */
167 #ifndef CONFIG_DEBUG_LIST
168 static inline void list_del(struct list_head *entry)
169 {
170         __list_del(entry->prev, entry->next);
171         entry->next = LIST_POISON1;
172         entry->prev = LIST_POISON2;
173 }
174 #else
175 extern void list_del(struct list_head *entry);
176 #endif
177
178 /**
179  * list_del_rcu - deletes entry from list without re-initialization
180  * @entry: the element to delete from the list.
181  *
182  * Note: list_empty on entry does not return true after this,
183  * the entry is in an undefined state. It is useful for RCU based
184  * lockfree traversal.
185  *
186  * In particular, it means that we can not poison the forward
187  * pointers that may still be used for walking the list.
188  *
189  * The caller must take whatever precautions are necessary
190  * (such as holding appropriate locks) to avoid racing
191  * with another list-mutation primitive, such as list_del_rcu()
192  * or list_add_rcu(), running on this same list.
193  * However, it is perfectly legal to run concurrently with
194  * the _rcu list-traversal primitives, such as
195  * list_for_each_entry_rcu().
196  *
197  * Note that the caller is not permitted to immediately free
198  * the newly deleted entry.  Instead, either synchronize_rcu()
199  * or call_rcu() must be used to defer freeing until an RCU
200  * grace period has elapsed.
201  */
202 static inline void list_del_rcu(struct list_head *entry)
203 {
204         __list_del(entry->prev, entry->next);
205         entry->prev = LIST_POISON2;
206 }
207
208 /**
209  * list_replace - replace old entry by new one
210  * @old : the element to be replaced
211  * @new : the new element to insert
212  * Note: if 'old' was empty, it will be overwritten.
213  */
214 static inline void list_replace(struct list_head *old,
215                                 struct list_head *new)
216 {
217         new->next = old->next;
218         new->next->prev = new;
219         new->prev = old->prev;
220         new->prev->next = new;
221 }
222
223 static inline void list_replace_init(struct list_head *old,
224                                         struct list_head *new)
225 {
226         list_replace(old, new);
227         INIT_LIST_HEAD(old);
228 }
229
230 /**
231  * list_replace_rcu - replace old entry by new one
232  * @old : the element to be replaced
233  * @new : the new element to insert
234  *
235  * The @old entry will be replaced with the @new entry atomically.
236  * Note: @old should not be empty.
237  */
238 static inline void list_replace_rcu(struct list_head *old,
239                                 struct list_head *new)
240 {
241         new->next = old->next;
242         new->prev = old->prev;
243         smp_wmb();
244         new->next->prev = new;
245         new->prev->next = new;
246         old->prev = LIST_POISON2;
247 }
248
249 /**
250  * list_del_init - deletes entry from list and reinitialize it.
251  * @entry: the element to delete from the list.
252  */
253 static inline void list_del_init(struct list_head *entry)
254 {
255         __list_del(entry->prev, entry->next);
256         INIT_LIST_HEAD(entry);
257 }
258
259 /**
260  * list_move - delete from one list and add as another's head
261  * @list: the entry to move
262  * @head: the head that will precede our entry
263  */
264 static inline void list_move(struct list_head *list, struct list_head *head)
265 {
266         __list_del(list->prev, list->next);
267         list_add(list, head);
268 }
269
270 /**
271  * list_move_tail - delete from one list and add as another's tail
272  * @list: the entry to move
273  * @head: the head that will follow our entry
274  */
275 static inline void list_move_tail(struct list_head *list,
276                                   struct list_head *head)
277 {
278         __list_del(list->prev, list->next);
279         list_add_tail(list, head);
280 }
281
282 /**
283  * list_is_last - tests whether @list is the last entry in list @head
284  * @list: the entry to test
285  * @head: the head of the list
286  */
287 static inline int list_is_last(const struct list_head *list,
288                                 const struct list_head *head)
289 {
290         return list->next == head;
291 }
292
293 /**
294  * list_empty - tests whether a list is empty
295  * @head: the list to test.
296  */
297 static inline int list_empty(const struct list_head *head)
298 {
299         return head->next == head;
300 }
301
302 /**
303  * list_empty_careful - tests whether a list is empty and not being modified
304  * @head: the list to test
305  *
306  * Description:
307  * tests whether a list is empty _and_ checks that no other CPU might be
308  * in the process of modifying either member (next or prev)
309  *
310  * NOTE: using list_empty_careful() without synchronization
311  * can only be safe if the only activity that can happen
312  * to the list entry is list_del_init(). Eg. it cannot be used
313  * if another CPU could re-list_add() it.
314  */
315 static inline int list_empty_careful(const struct list_head *head)
316 {
317         struct list_head *next = head->next;
318         return (next == head) && (next == head->prev);
319 }
320
321 static inline void __list_splice(struct list_head *list,
322                                  struct list_head *head)
323 {
324         struct list_head *first = list->next;
325         struct list_head *last = list->prev;
326         struct list_head *at = head->next;
327
328         first->prev = head;
329         head->next = first;
330
331         last->next = at;
332         at->prev = last;
333 }
334
335 /**
336  * list_splice - join two lists
337  * @list: the new list to add.
338  * @head: the place to add it in the first list.
339  */
340 static inline void list_splice(struct list_head *list, struct list_head *head)
341 {
342         if (!list_empty(list))
343                 __list_splice(list, head);
344 }
345
346 /**
347  * list_splice_init - join two lists and reinitialise the emptied list.
348  * @list: the new list to add.
349  * @head: the place to add it in the first list.
350  *
351  * The list at @list is reinitialised
352  */
353 static inline void list_splice_init(struct list_head *list,
354                                     struct list_head *head)
355 {
356         if (!list_empty(list)) {
357                 __list_splice(list, head);
358                 INIT_LIST_HEAD(list);
359         }
360 }
361
362 /**
363  * list_splice_init_rcu - splice an RCU-protected list into an existing list.
364  * @list:       the RCU-protected list to splice
365  * @head:       the place in the list to splice the first list into
366  * @sync:       function to sync: synchronize_rcu(), synchronize_sched(), ...
367  *
368  * @head can be RCU-read traversed concurrently with this function.
369  *
370  * Note that this function blocks.
371  *
372  * Important note: the caller must take whatever action is necessary to
373  *      prevent any other updates to @head.  In principle, it is possible
374  *      to modify the list as soon as sync() begins execution.
375  *      If this sort of thing becomes necessary, an alternative version
376  *      based on call_rcu() could be created.  But only if -really-
377  *      needed -- there is no shortage of RCU API members.
378  */
379 static inline void list_splice_init_rcu(struct list_head *list,
380                                         struct list_head *head,
381                                         void (*sync)(void))
382 {
383         struct list_head *first = list->next;
384         struct list_head *last = list->prev;
385         struct list_head *at = head->next;
386
387         if (list_empty(head))
388                 return;
389
390         /* "first" and "last" tracking list, so initialize it. */
391
392         INIT_LIST_HEAD(list);
393
394         /*
395          * At this point, the list body still points to the source list.
396          * Wait for any readers to finish using the list before splicing
397          * the list body into the new list.  Any new readers will see
398          * an empty list.
399          */
400
401         sync();
402
403         /*
404          * Readers are finished with the source list, so perform splice.
405          * The order is important if the new list is global and accessible
406          * to concurrent RCU readers.  Note that RCU readers are not
407          * permitted to traverse the prev pointers without excluding
408          * this function.
409          */
410
411         last->next = at;
412         smp_wmb();
413         head->next = first;
414         first->prev = head;
415         at->prev = last;
416 }
417
418 /**
419  * list_entry - get the struct for this entry
420  * @ptr:        the &struct list_head pointer.
421  * @type:       the type of the struct this is embedded in.
422  * @member:     the name of the list_struct within the struct.
423  */
424 #define list_entry(ptr, type, member) \
425         container_of(ptr, type, member)
426
427 /**
428  * list_for_each        -       iterate over a list
429  * @pos:        the &struct list_head to use as a loop cursor.
430  * @head:       the head for your list.
431  */
432 #define list_for_each(pos, head) \
433         for (pos = (head)->next; prefetch(pos->next), pos != (head); \
434                 pos = pos->next)
435
436 /**
437  * __list_for_each      -       iterate over a list
438  * @pos:        the &struct list_head to use as a loop cursor.
439  * @head:       the head for your list.
440  *
441  * This variant differs from list_for_each() in that it's the
442  * simplest possible list iteration code, no prefetching is done.
443  * Use this for code that knows the list to be very short (empty
444  * or 1 entry) most of the time.
445  */
446 #define __list_for_each(pos, head) \
447         for (pos = (head)->next; pos != (head); pos = pos->next)
448
449 /**
450  * list_for_each_prev   -       iterate over a list backwards
451  * @pos:        the &struct list_head to use as a loop cursor.
452  * @head:       the head for your list.
453  */
454 #define list_for_each_prev(pos, head) \
455         for (pos = (head)->prev; prefetch(pos->prev), pos != (head); \
456                 pos = pos->prev)
457
458 /**
459  * list_for_each_safe - iterate over a list safe against removal of list entry
460  * @pos:        the &struct list_head to use as a loop cursor.
461  * @n:          another &struct list_head to use as temporary storage
462  * @head:       the head for your list.
463  */
464 #define list_for_each_safe(pos, n, head) \
465         for (pos = (head)->next, n = pos->next; pos != (head); \
466                 pos = n, n = pos->next)
467
468 /**
469  * list_for_each_entry  -       iterate over list of given type
470  * @pos:        the type * to use as a loop cursor.
471  * @head:       the head for your list.
472  * @member:     the name of the list_struct within the struct.
473  */
474 #define list_for_each_entry(pos, head, member)                          \
475         for (pos = list_entry((head)->next, typeof(*pos), member);      \
476              prefetch(pos->member.next), &pos->member != (head);        \
477              pos = list_entry(pos->member.next, typeof(*pos), member))
478
479 /**
480  * list_for_each_entry_reverse - iterate backwards over list of given type.
481  * @pos:        the type * to use as a loop cursor.
482  * @head:       the head for your list.
483  * @member:     the name of the list_struct within the struct.
484  */
485 #define list_for_each_entry_reverse(pos, head, member)                  \
486         for (pos = list_entry((head)->prev, typeof(*pos), member);      \
487              prefetch(pos->member.prev), &pos->member != (head);        \
488              pos = list_entry(pos->member.prev, typeof(*pos), member))
489
490 /**
491  * list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue
492  * @pos:        the type * to use as a start point
493  * @head:       the head of the list
494  * @member:     the name of the list_struct within the struct.
495  *
496  * Prepares a pos entry for use as a start point in list_for_each_entry_continue.
497  */
498 #define list_prepare_entry(pos, head, member) \
499         ((pos) ? : list_entry(head, typeof(*pos), member))
500
501 /**
502  * list_for_each_entry_continue - continue iteration over list of given type
503  * @pos:        the type * to use as a loop cursor.
504  * @head:       the head for your list.
505  * @member:     the name of the list_struct within the struct.
506  *
507  * Continue to iterate over list of given type, continuing after
508  * the current position.
509  */
510 #define list_for_each_entry_continue(pos, head, member)                 \
511         for (pos = list_entry(pos->member.next, typeof(*pos), member);  \
512              prefetch(pos->member.next), &pos->member != (head);        \
513              pos = list_entry(pos->member.next, typeof(*pos), member))
514
515 /**
516  * list_for_each_entry_from - iterate over list of given type from the current point
517  * @pos:        the type * to use as a loop cursor.
518  * @head:       the head for your list.
519  * @member:     the name of the list_struct within the struct.
520  *
521  * Iterate over list of given type, continuing from current position.
522  */
523 #define list_for_each_entry_from(pos, head, member)                     \
524         for (; prefetch(pos->member.next), &pos->member != (head);      \
525              pos = list_entry(pos->member.next, typeof(*pos), member))
526
527 /**
528  * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
529  * @pos:        the type * to use as a loop cursor.
530  * @n:          another type * to use as temporary storage
531  * @head:       the head for your list.
532  * @member:     the name of the list_struct within the struct.
533  */
534 #define list_for_each_entry_safe(pos, n, head, member)                  \
535         for (pos = list_entry((head)->next, typeof(*pos), member),      \
536                 n = list_entry(pos->member.next, typeof(*pos), member); \
537              &pos->member != (head);                                    \
538              pos = n, n = list_entry(n->member.next, typeof(*n), member))
539
540 /**
541  * list_for_each_entry_safe_continue
542  * @pos:        the type * to use as a loop cursor.
543  * @n:          another type * to use as temporary storage
544  * @head:       the head for your list.
545  * @member:     the name of the list_struct within the struct.
546  *
547  * Iterate over list of given type, continuing after current point,
548  * safe against removal of list entry.
549  */
550 #define list_for_each_entry_safe_continue(pos, n, head, member)                 \
551         for (pos = list_entry(pos->member.next, typeof(*pos), member),          \
552                 n = list_entry(pos->member.next, typeof(*pos), member);         \
553              &pos->member != (head);                                            \
554              pos = n, n = list_entry(n->member.next, typeof(*n), member))
555
556 /**
557  * list_for_each_entry_safe_from
558  * @pos:        the type * to use as a loop cursor.
559  * @n:          another type * to use as temporary storage
560  * @head:       the head for your list.
561  * @member:     the name of the list_struct within the struct.
562  *
563  * Iterate over list of given type from current point, safe against
564  * removal of list entry.
565  */
566 #define list_for_each_entry_safe_from(pos, n, head, member)                     \
567         for (n = list_entry(pos->member.next, typeof(*pos), member);            \
568              &pos->member != (head);                                            \
569              pos = n, n = list_entry(n->member.next, typeof(*n), member))
570
571 /**
572  * list_for_each_entry_safe_reverse
573  * @pos:        the type * to use as a loop cursor.
574  * @n:          another type * to use as temporary storage
575  * @head:       the head for your list.
576  * @member:     the name of the list_struct within the struct.
577  *
578  * Iterate backwards over list of given type, safe against removal
579  * of list entry.
580  */
581 #define list_for_each_entry_safe_reverse(pos, n, head, member)          \
582         for (pos = list_entry((head)->prev, typeof(*pos), member),      \
583                 n = list_entry(pos->member.prev, typeof(*pos), member); \
584              &pos->member != (head);                                    \
585              pos = n, n = list_entry(n->member.prev, typeof(*n), member))
586
587 /**
588  * list_for_each_rcu    -       iterate over an rcu-protected list
589  * @pos:        the &struct list_head to use as a loop cursor.
590  * @head:       the head for your list.
591  *
592  * This list-traversal primitive may safely run concurrently with
593  * the _rcu list-mutation primitives such as list_add_rcu()
594  * as long as the traversal is guarded by rcu_read_lock().
595  */
596 #define list_for_each_rcu(pos, head) \
597         for (pos = (head)->next; \
598                 prefetch(rcu_dereference(pos)->next), pos != (head); \
599                 pos = pos->next)
600
601 #define __list_for_each_rcu(pos, head) \
602         for (pos = (head)->next; \
603                 rcu_dereference(pos) != (head); \
604                 pos = pos->next)
605
606 /**
607  * list_for_each_safe_rcu
608  * @pos:        the &struct list_head to use as a loop cursor.
609  * @n:          another &struct list_head to use as temporary storage
610  * @head:       the head for your list.
611  *
612  * Iterate over an rcu-protected list, safe against removal of list entry.
613  *
614  * This list-traversal primitive may safely run concurrently with
615  * the _rcu list-mutation primitives such as list_add_rcu()
616  * as long as the traversal is guarded by rcu_read_lock().
617  */
618 #define list_for_each_safe_rcu(pos, n, head) \
619         for (pos = (head)->next; \
620                 n = rcu_dereference(pos)->next, pos != (head); \
621                 pos = n)
622
623 /**
624  * list_for_each_entry_rcu      -       iterate over rcu list of given type
625  * @pos:        the type * to use as a loop cursor.
626  * @head:       the head for your list.
627  * @member:     the name of the list_struct within the struct.
628  *
629  * This list-traversal primitive may safely run concurrently with
630  * the _rcu list-mutation primitives such as list_add_rcu()
631  * as long as the traversal is guarded by rcu_read_lock().
632  */
633 #define list_for_each_entry_rcu(pos, head, member) \
634         for (pos = list_entry((head)->next, typeof(*pos), member); \
635                 prefetch(rcu_dereference(pos)->member.next), \
636                         &pos->member != (head); \
637                 pos = list_entry(pos->member.next, typeof(*pos), member))
638
639
640 /**
641  * list_for_each_continue_rcu
642  * @pos:        the &struct list_head to use as a loop cursor.
643  * @head:       the head for your list.
644  *
645  * Iterate over an rcu-protected list, continuing after current point.
646  *
647  * This list-traversal primitive may safely run concurrently with
648  * the _rcu list-mutation primitives such as list_add_rcu()
649  * as long as the traversal is guarded by rcu_read_lock().
650  */
651 #define list_for_each_continue_rcu(pos, head) \
652         for ((pos) = (pos)->next; \
653                 prefetch(rcu_dereference((pos))->next), (pos) != (head); \
654                 (pos) = (pos)->next)
655
656 /*
657  * Double linked lists with a single pointer list head.
658  * Mostly useful for hash tables where the two pointer list head is
659  * too wasteful.
660  * You lose the ability to access the tail in O(1).
661  */
662
663 struct hlist_head {
664         struct hlist_node *first;
665 };
666
667 struct hlist_node {
668         struct hlist_node *next, **pprev;
669 };
670
671 #define HLIST_HEAD_INIT { .first = NULL }
672 #define HLIST_HEAD(name) struct hlist_head name = {  .first = NULL }
673 #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
674 static inline void INIT_HLIST_NODE(struct hlist_node *h)
675 {
676         h->next = NULL;
677         h->pprev = NULL;
678 }
679
680 static inline int hlist_unhashed(const struct hlist_node *h)
681 {
682         return !h->pprev;
683 }
684
685 static inline int hlist_empty(const struct hlist_head *h)
686 {
687         return !h->first;
688 }
689
690 static inline void __hlist_del(struct hlist_node *n)
691 {
692         struct hlist_node *next = n->next;
693         struct hlist_node **pprev = n->pprev;
694         *pprev = next;
695         if (next)
696                 next->pprev = pprev;
697 }
698
699 static inline void hlist_del(struct hlist_node *n)
700 {
701         __hlist_del(n);
702         n->next = LIST_POISON1;
703         n->pprev = LIST_POISON2;
704 }
705
706 /**
707  * hlist_del_rcu - deletes entry from hash list without re-initialization
708  * @n: the element to delete from the hash list.
709  *
710  * Note: list_unhashed() on entry does not return true after this,
711  * the entry is in an undefined state. It is useful for RCU based
712  * lockfree traversal.
713  *
714  * In particular, it means that we can not poison the forward
715  * pointers that may still be used for walking the hash list.
716  *
717  * The caller must take whatever precautions are necessary
718  * (such as holding appropriate locks) to avoid racing
719  * with another list-mutation primitive, such as hlist_add_head_rcu()
720  * or hlist_del_rcu(), running on this same list.
721  * However, it is perfectly legal to run concurrently with
722  * the _rcu list-traversal primitives, such as
723  * hlist_for_each_entry().
724  */
725 static inline void hlist_del_rcu(struct hlist_node *n)
726 {
727         __hlist_del(n);
728         n->pprev = LIST_POISON2;
729 }
730
731 static inline void hlist_del_init(struct hlist_node *n)
732 {
733         if (!hlist_unhashed(n)) {
734                 __hlist_del(n);
735                 INIT_HLIST_NODE(n);
736         }
737 }
738
739 /**
740  * hlist_replace_rcu - replace old entry by new one
741  * @old : the element to be replaced
742  * @new : the new element to insert
743  *
744  * The @old entry will be replaced with the @new entry atomically.
745  */
746 static inline void hlist_replace_rcu(struct hlist_node *old,
747                                         struct hlist_node *new)
748 {
749         struct hlist_node *next = old->next;
750
751         new->next = next;
752         new->pprev = old->pprev;
753         smp_wmb();
754         if (next)
755                 new->next->pprev = &new->next;
756         *new->pprev = new;
757         old->pprev = LIST_POISON2;
758 }
759
760 static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
761 {
762         struct hlist_node *first = h->first;
763         n->next = first;
764         if (first)
765                 first->pprev = &n->next;
766         h->first = n;
767         n->pprev = &h->first;
768 }
769
770
771 /**
772  * hlist_add_head_rcu
773  * @n: the element to add to the hash list.
774  * @h: the list to add to.
775  *
776  * Description:
777  * Adds the specified element to the specified hlist,
778  * while permitting racing traversals.
779  *
780  * The caller must take whatever precautions are necessary
781  * (such as holding appropriate locks) to avoid racing
782  * with another list-mutation primitive, such as hlist_add_head_rcu()
783  * or hlist_del_rcu(), running on this same list.
784  * However, it is perfectly legal to run concurrently with
785  * the _rcu list-traversal primitives, such as
786  * hlist_for_each_entry_rcu(), used to prevent memory-consistency
787  * problems on Alpha CPUs.  Regardless of the type of CPU, the
788  * list-traversal primitive must be guarded by rcu_read_lock().
789  */
790 static inline void hlist_add_head_rcu(struct hlist_node *n,
791                                         struct hlist_head *h)
792 {
793         struct hlist_node *first = h->first;
794         n->next = first;
795         n->pprev = &h->first;
796         smp_wmb();
797         if (first)
798                 first->pprev = &n->next;
799         h->first = n;
800 }
801
802 /* next must be != NULL */
803 static inline void hlist_add_before(struct hlist_node *n,
804                                         struct hlist_node *next)
805 {
806         n->pprev = next->pprev;
807         n->next = next;
808         next->pprev = &n->next;
809         *(n->pprev) = n;
810 }
811
812 static inline void hlist_add_after(struct hlist_node *n,
813                                         struct hlist_node *next)
814 {
815         next->next = n->next;
816         n->next = next;
817         next->pprev = &n->next;
818
819         if(next->next)
820                 next->next->pprev  = &next->next;
821 }
822
823 /**
824  * hlist_add_before_rcu
825  * @n: the new element to add to the hash list.
826  * @next: the existing element to add the new element before.
827  *
828  * Description:
829  * Adds the specified element to the specified hlist
830  * before the specified node while permitting racing traversals.
831  *
832  * The caller must take whatever precautions are necessary
833  * (such as holding appropriate locks) to avoid racing
834  * with another list-mutation primitive, such as hlist_add_head_rcu()
835  * or hlist_del_rcu(), running on this same list.
836  * However, it is perfectly legal to run concurrently with
837  * the _rcu list-traversal primitives, such as
838  * hlist_for_each_entry_rcu(), used to prevent memory-consistency
839  * problems on Alpha CPUs.
840  */
841 static inline void hlist_add_before_rcu(struct hlist_node *n,
842                                         struct hlist_node *next)
843 {
844         n->pprev = next->pprev;
845         n->next = next;
846         smp_wmb();
847         next->pprev = &n->next;
848         *(n->pprev) = n;
849 }
850
851 /**
852  * hlist_add_after_rcu
853  * @prev: the existing element to add the new element after.
854  * @n: the new element to add to the hash list.
855  *
856  * Description:
857  * Adds the specified element to the specified hlist
858  * after the specified node while permitting racing traversals.
859  *
860  * The caller must take whatever precautions are necessary
861  * (such as holding appropriate locks) to avoid racing
862  * with another list-mutation primitive, such as hlist_add_head_rcu()
863  * or hlist_del_rcu(), running on this same list.
864  * However, it is perfectly legal to run concurrently with
865  * the _rcu list-traversal primitives, such as
866  * hlist_for_each_entry_rcu(), used to prevent memory-consistency
867  * problems on Alpha CPUs.
868  */
869 static inline void hlist_add_after_rcu(struct hlist_node *prev,
870                                        struct hlist_node *n)
871 {
872         n->next = prev->next;
873         n->pprev = &prev->next;
874         smp_wmb();
875         prev->next = n;
876         if (n->next)
877                 n->next->pprev = &n->next;
878 }
879
880 #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
881
882 #define hlist_for_each(pos, head) \
883         for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; }); \
884              pos = pos->next)
885
886 #define hlist_for_each_safe(pos, n, head) \
887         for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
888              pos = n)
889
890 /**
891  * hlist_for_each_entry - iterate over list of given type
892  * @tpos:       the type * to use as a loop cursor.
893  * @pos:        the &struct hlist_node to use as a loop cursor.
894  * @head:       the head for your list.
895  * @member:     the name of the hlist_node within the struct.
896  */
897 #define hlist_for_each_entry(tpos, pos, head, member)                    \
898         for (pos = (head)->first;                                        \
899              pos && ({ prefetch(pos->next); 1;}) &&                      \
900                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
901              pos = pos->next)
902
903 /**
904  * hlist_for_each_entry_continue - iterate over a hlist continuing after current point
905  * @tpos:       the type * to use as a loop cursor.
906  * @pos:        the &struct hlist_node to use as a loop cursor.
907  * @member:     the name of the hlist_node within the struct.
908  */
909 #define hlist_for_each_entry_continue(tpos, pos, member)                 \
910         for (pos = (pos)->next;                                          \
911              pos && ({ prefetch(pos->next); 1;}) &&                      \
912                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
913              pos = pos->next)
914
915 /**
916  * hlist_for_each_entry_from - iterate over a hlist continuing from current point
917  * @tpos:       the type * to use as a loop cursor.
918  * @pos:        the &struct hlist_node to use as a loop cursor.
919  * @member:     the name of the hlist_node within the struct.
920  */
921 #define hlist_for_each_entry_from(tpos, pos, member)                     \
922         for (; pos && ({ prefetch(pos->next); 1;}) &&                    \
923                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
924              pos = pos->next)
925
926 /**
927  * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
928  * @tpos:       the type * to use as a loop cursor.
929  * @pos:        the &struct hlist_node to use as a loop cursor.
930  * @n:          another &struct hlist_node to use as temporary storage
931  * @head:       the head for your list.
932  * @member:     the name of the hlist_node within the struct.
933  */
934 #define hlist_for_each_entry_safe(tpos, pos, n, head, member)            \
935         for (pos = (head)->first;                                        \
936              pos && ({ n = pos->next; 1; }) &&                           \
937                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
938              pos = n)
939
940 /**
941  * hlist_for_each_entry_rcu - iterate over rcu list of given type
942  * @tpos:       the type * to use as a loop cursor.
943  * @pos:        the &struct hlist_node to use as a loop cursor.
944  * @head:       the head for your list.
945  * @member:     the name of the hlist_node within the struct.
946  *
947  * This list-traversal primitive may safely run concurrently with
948  * the _rcu list-mutation primitives such as hlist_add_head_rcu()
949  * as long as the traversal is guarded by rcu_read_lock().
950  */
951 #define hlist_for_each_entry_rcu(tpos, pos, head, member)                \
952         for (pos = (head)->first;                                        \
953              rcu_dereference(pos) && ({ prefetch(pos->next); 1;}) &&     \
954                 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
955              pos = pos->next)
956
957 #else
958 #warning "don't include kernel headers in userspace"
959 #endif /* __KERNEL__ */
960 #endif