aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--arch/ia64/sn/kernel/irq.c1
-rw-r--r--crypto/async_tx/async_tx.c1
-rw-r--r--drivers/infiniband/hw/ipath/ipath_verbs.c1
-rw-r--r--drivers/infiniband/hw/ipath/ipath_verbs_mcast.c3
-rw-r--r--drivers/net/macvlan.c2
-rw-r--r--include/linux/dcache.h1
-rw-r--r--include/linux/list.h367
-rw-r--r--include/linux/rculist.h396
-rw-r--r--kernel/pid.c1
-rw-r--r--lib/textsearch.c1
-rw-r--r--net/802/psnap.c1
-rw-r--r--net/8021q/vlan.c1
-rw-r--r--net/bridge/br_fdb.c1
-rw-r--r--net/bridge/br_stp.c1
-rw-r--r--net/netlabel/netlabel_domainhash.c3
15 files changed, 409 insertions, 372 deletions
diff --git a/arch/ia64/sn/kernel/irq.c b/arch/ia64/sn/kernel/irq.c
index 53351c3cd7b1..96c31b4180c3 100644
--- a/arch/ia64/sn/kernel/irq.c
+++ b/arch/ia64/sn/kernel/irq.c
@@ -11,6 +11,7 @@
11#include <linux/irq.h> 11#include <linux/irq.h>
12#include <linux/spinlock.h> 12#include <linux/spinlock.h>
13#include <linux/init.h> 13#include <linux/init.h>
14#include <linux/rculist.h>
14#include <asm/sn/addrs.h> 15#include <asm/sn/addrs.h>
15#include <asm/sn/arch.h> 16#include <asm/sn/arch.h>
16#include <asm/sn/intr.h> 17#include <asm/sn/intr.h>
diff --git a/crypto/async_tx/async_tx.c b/crypto/async_tx/async_tx.c
index c6e772fc5ccd..095c798d3170 100644
--- a/crypto/async_tx/async_tx.c
+++ b/crypto/async_tx/async_tx.c
@@ -23,6 +23,7 @@
23 * 51 Franklin St - Fifth Floor, Boston, MA 02110-1301 USA. 23 * 51 Franklin St - Fifth Floor, Boston, MA 02110-1301 USA.
24 * 24 *
25 */ 25 */
26#include <linux/rculist.h>
26#include <linux/kernel.h> 27#include <linux/kernel.h>
27#include <linux/async_tx.h> 28#include <linux/async_tx.h>
28 29
diff --git a/drivers/infiniband/hw/ipath/ipath_verbs.c b/drivers/infiniband/hw/ipath/ipath_verbs.c
index e0ec540042bf..5d830d87ebca 100644
--- a/drivers/infiniband/hw/ipath/ipath_verbs.c
+++ b/drivers/infiniband/hw/ipath/ipath_verbs.c
@@ -35,6 +35,7 @@
35#include <rdma/ib_user_verbs.h> 35#include <rdma/ib_user_verbs.h>
36#include <linux/io.h> 36#include <linux/io.h>
37#include <linux/utsname.h> 37#include <linux/utsname.h>
38#include <linux/rculist.h>
38 39
39#include "ipath_kernel.h" 40#include "ipath_kernel.h"
40#include "ipath_verbs.h" 41#include "ipath_verbs.h"
diff --git a/drivers/infiniband/hw/ipath/ipath_verbs_mcast.c b/drivers/infiniband/hw/ipath/ipath_verbs_mcast.c
index 9e5abf9c309d..d73e32232879 100644
--- a/drivers/infiniband/hw/ipath/ipath_verbs_mcast.c
+++ b/drivers/infiniband/hw/ipath/ipath_verbs_mcast.c
@@ -31,8 +31,7 @@
31 * SOFTWARE. 31 * SOFTWARE.
32 */ 32 */
33 33
34#include <linux/list.h> 34#include <linux/rculist.h>
35#include <linux/rcupdate.h>
36 35
37#include "ipath_verbs.h" 36#include "ipath_verbs.h"
38 37
diff --git a/drivers/net/macvlan.c b/drivers/net/macvlan.c
index c36a03ae9bfb..860d75d81f82 100644
--- a/drivers/net/macvlan.c
+++ b/drivers/net/macvlan.c
@@ -20,7 +20,7 @@
20#include <linux/errno.h> 20#include <linux/errno.h>
21#include <linux/slab.h> 21#include <linux/slab.h>
22#include <linux/string.h> 22#include <linux/string.h>
23#include <linux/list.h> 23#include <linux/rculist.h>
24#include <linux/notifier.h> 24#include <linux/notifier.h>
25#include <linux/netdevice.h> 25#include <linux/netdevice.h>
26#include <linux/etherdevice.h> 26#include <linux/etherdevice.h>
diff --git a/include/linux/dcache.h b/include/linux/dcache.h
index 2a6639407c80..1f5cebf10a23 100644
--- a/include/linux/dcache.h
+++ b/include/linux/dcache.h
@@ -3,6 +3,7 @@
3 3
4#include <asm/atomic.h> 4#include <asm/atomic.h>
5#include <linux/list.h> 5#include <linux/list.h>
6#include <linux/rculist.h>
6#include <linux/spinlock.h> 7#include <linux/spinlock.h>
7#include <linux/cache.h> 8#include <linux/cache.h>
8#include <linux/rcupdate.h> 9#include <linux/rcupdate.h>
diff --git a/include/linux/list.h b/include/linux/list.h
index 08cf4f651889..139ec41d9c2e 100644
--- a/include/linux/list.h
+++ b/include/linux/list.h
@@ -85,65 +85,6 @@ static inline void list_add_tail(struct list_head *new, struct list_head *head)
85} 85}
86 86
87/* 87/*
88 * Insert a new entry between two known consecutive entries.
89 *
90 * This is only for internal list manipulation where we know
91 * the prev/next entries already!
92 */
93static inline void __list_add_rcu(struct list_head * new,
94 struct list_head * prev, struct list_head * next)
95{
96 new->next = next;
97 new->prev = prev;
98 smp_wmb();
99 next->prev = new;
100 prev->next = new;
101}
102
103/**
104 * list_add_rcu - add a new entry to rcu-protected list
105 * @new: new entry to be added
106 * @head: list head to add it after
107 *
108 * Insert a new entry after the specified head.
109 * This is good for implementing stacks.
110 *
111 * The caller must take whatever precautions are necessary
112 * (such as holding appropriate locks) to avoid racing
113 * with another list-mutation primitive, such as list_add_rcu()
114 * or list_del_rcu(), running on this same list.
115 * However, it is perfectly legal to run concurrently with
116 * the _rcu list-traversal primitives, such as
117 * list_for_each_entry_rcu().
118 */
119static inline void list_add_rcu(struct list_head *new, struct list_head *head)
120{
121 __list_add_rcu(new, head, head->next);
122}
123
124/**
125 * list_add_tail_rcu - add a new entry to rcu-protected list
126 * @new: new entry to be added
127 * @head: list head to add it before
128 *
129 * Insert a new entry before the specified head.
130 * This is useful for implementing queues.
131 *
132 * The caller must take whatever precautions are necessary
133 * (such as holding appropriate locks) to avoid racing
134 * with another list-mutation primitive, such as list_add_tail_rcu()
135 * or list_del_rcu(), running on this same list.
136 * However, it is perfectly legal to run concurrently with
137 * the _rcu list-traversal primitives, such as
138 * list_for_each_entry_rcu().
139 */
140static inline void list_add_tail_rcu(struct list_head *new,
141 struct list_head *head)
142{
143 __list_add_rcu(new, head->prev, head);
144}
145
146/*
147 * Delete a list entry by making the prev/next entries 88 * Delete a list entry by making the prev/next entries
148 * point to each other. 89 * point to each other.
149 * 90 *
@@ -174,36 +115,6 @@ extern void list_del(struct list_head *entry);
174#endif 115#endif
175 116
176/** 117/**
177 * list_del_rcu - deletes entry from list without re-initialization
178 * @entry: the element to delete from the list.
179 *
180 * Note: list_empty() on entry does not return true after this,
181 * the entry is in an undefined state. It is useful for RCU based
182 * lockfree traversal.
183 *
184 * In particular, it means that we can not poison the forward
185 * pointers that may still be used for walking the list.
186 *
187 * The caller must take whatever precautions are necessary
188 * (such as holding appropriate locks) to avoid racing
189 * with another list-mutation primitive, such as list_del_rcu()
190 * or list_add_rcu(), running on this same list.
191 * However, it is perfectly legal to run concurrently with
192 * the _rcu list-traversal primitives, such as
193 * list_for_each_entry_rcu().
194 *
195 * Note that the caller is not permitted to immediately free
196 * the newly deleted entry. Instead, either synchronize_rcu()
197 * or call_rcu() must be used to defer freeing until an RCU
198 * grace period has elapsed.
199 */
200static inline void list_del_rcu(struct list_head *entry)
201{
202 __list_del(entry->prev, entry->next);
203 entry->prev = LIST_POISON2;
204}
205
206/**
207 * list_replace - replace old entry by new one 118 * list_replace - replace old entry by new one
208 * @old : the element to be replaced 119 * @old : the element to be replaced
209 * @new : the new element to insert 120 * @new : the new element to insert
@@ -227,25 +138,6 @@ static inline void list_replace_init(struct list_head *old,
227} 138}
228 139
229/** 140/**
230 * list_replace_rcu - replace old entry by new one
231 * @old : the element to be replaced
232 * @new : the new element to insert
233 *
234 * The @old entry will be replaced with the @new entry atomically.
235 * Note: @old should not be empty.
236 */
237static inline void list_replace_rcu(struct list_head *old,
238 struct list_head *new)
239{
240 new->next = old->next;
241 new->prev = old->prev;
242 smp_wmb();
243 new->next->prev = new;
244 new->prev->next = new;
245 old->prev = LIST_POISON2;
246}
247
248/**
249 * list_del_init - deletes entry from list and reinitialize it. 141 * list_del_init - deletes entry from list and reinitialize it.
250 * @entry: the element to delete from the list. 142 * @entry: the element to delete from the list.
251 */ 143 */
@@ -369,62 +261,6 @@ static inline void list_splice_init(struct list_head *list,
369} 261}
370 262
371/** 263/**
372 * list_splice_init_rcu - splice an RCU-protected list into an existing list.
373 * @list: the RCU-protected list to splice
374 * @head: the place in the list to splice the first list into
375 * @sync: function to sync: synchronize_rcu(), synchronize_sched(), ...
376 *
377 * @head can be RCU-read traversed concurrently with this function.
378 *
379 * Note that this function blocks.
380 *
381 * Important note: the caller must take whatever action is necessary to
382 * prevent any other updates to @head. In principle, it is possible
383 * to modify the list as soon as sync() begins execution.
384 * If this sort of thing becomes necessary, an alternative version
385 * based on call_rcu() could be created. But only if -really-
386 * needed -- there is no shortage of RCU API members.
387 */
388static inline void list_splice_init_rcu(struct list_head *list,
389 struct list_head *head,
390 void (*sync)(void))
391{
392 struct list_head *first = list->next;
393 struct list_head *last = list->prev;
394 struct list_head *at = head->next;
395
396 if (list_empty(head))
397 return;
398
399 /* "first" and "last" tracking list, so initialize it. */
400
401 INIT_LIST_HEAD(list);
402
403 /*
404 * At this point, the list body still points to the source list.
405 * Wait for any readers to finish using the list before splicing
406 * the list body into the new list. Any new readers will see
407 * an empty list.
408 */
409
410 sync();
411
412 /*
413 * Readers are finished with the source list, so perform splice.
414 * The order is important if the new list is global and accessible
415 * to concurrent RCU readers. Note that RCU readers are not
416 * permitted to traverse the prev pointers without excluding
417 * this function.
418 */
419
420 last->next = at;
421 smp_wmb();
422 head->next = first;
423 first->prev = head;
424 at->prev = last;
425}
426
427/**
428 * list_entry - get the struct for this entry 264 * list_entry - get the struct for this entry
429 * @ptr: the &struct list_head pointer. 265 * @ptr: the &struct list_head pointer.
430 * @type: the type of the struct this is embedded in. 266 * @type: the type of the struct this is embedded in.
@@ -629,57 +465,6 @@ static inline void list_splice_init_rcu(struct list_head *list,
629 &pos->member != (head); \ 465 &pos->member != (head); \
630 pos = n, n = list_entry(n->member.prev, typeof(*n), member)) 466 pos = n, n = list_entry(n->member.prev, typeof(*n), member))
631 467
632/**
633 * list_for_each_rcu - iterate over an rcu-protected list
634 * @pos: the &struct list_head to use as a loop cursor.
635 * @head: the head for your list.
636 *
637 * This list-traversal primitive may safely run concurrently with
638 * the _rcu list-mutation primitives such as list_add_rcu()
639 * as long as the traversal is guarded by rcu_read_lock().
640 */
641#define list_for_each_rcu(pos, head) \
642 for (pos = rcu_dereference((head)->next); \
643 prefetch(pos->next), pos != (head); \
644 pos = rcu_dereference(pos->next))
645
646#define __list_for_each_rcu(pos, head) \
647 for (pos = rcu_dereference((head)->next); \
648 pos != (head); \
649 pos = rcu_dereference(pos->next))
650
651/**
652 * list_for_each_entry_rcu - iterate over rcu list of given type
653 * @pos: the type * to use as a loop cursor.
654 * @head: the head for your list.
655 * @member: the name of the list_struct within the struct.
656 *
657 * This list-traversal primitive may safely run concurrently with
658 * the _rcu list-mutation primitives such as list_add_rcu()
659 * as long as the traversal is guarded by rcu_read_lock().
660 */
661#define list_for_each_entry_rcu(pos, head, member) \
662 for (pos = list_entry(rcu_dereference((head)->next), typeof(*pos), member); \
663 prefetch(pos->member.next), &pos->member != (head); \
664 pos = list_entry(rcu_dereference(pos->member.next), typeof(*pos), member))
665
666
667/**
668 * list_for_each_continue_rcu
669 * @pos: the &struct list_head to use as a loop cursor.
670 * @head: the head for your list.
671 *
672 * Iterate over an rcu-protected list, continuing after current point.
673 *
674 * This list-traversal primitive may safely run concurrently with
675 * the _rcu list-mutation primitives such as list_add_rcu()
676 * as long as the traversal is guarded by rcu_read_lock().
677 */
678#define list_for_each_continue_rcu(pos, head) \
679 for ((pos) = rcu_dereference((pos)->next); \
680 prefetch((pos)->next), (pos) != (head); \
681 (pos) = rcu_dereference((pos)->next))
682
683/* 468/*
684 * Double linked lists with a single pointer list head. 469 * Double linked lists with a single pointer list head.
685 * Mostly useful for hash tables where the two pointer list head is 470 * Mostly useful for hash tables where the two pointer list head is
@@ -730,31 +515,6 @@ static inline void hlist_del(struct hlist_node *n)
730 n->pprev = LIST_POISON2; 515 n->pprev = LIST_POISON2;
731} 516}
732 517
733/**
734 * hlist_del_rcu - deletes entry from hash list without re-initialization
735 * @n: the element to delete from the hash list.
736 *
737 * Note: list_unhashed() on entry does not return true after this,
738 * the entry is in an undefined state. It is useful for RCU based
739 * lockfree traversal.
740 *
741 * In particular, it means that we can not poison the forward
742 * pointers that may still be used for walking the hash list.
743 *
744 * The caller must take whatever precautions are necessary
745 * (such as holding appropriate locks) to avoid racing
746 * with another list-mutation primitive, such as hlist_add_head_rcu()
747 * or hlist_del_rcu(), running on this same list.
748 * However, it is perfectly legal to run concurrently with
749 * the _rcu list-traversal primitives, such as
750 * hlist_for_each_entry().
751 */
752static inline void hlist_del_rcu(struct hlist_node *n)
753{
754 __hlist_del(n);
755 n->pprev = LIST_POISON2;
756}
757
758static inline void hlist_del_init(struct hlist_node *n) 518static inline void hlist_del_init(struct hlist_node *n)
759{ 519{
760 if (!hlist_unhashed(n)) { 520 if (!hlist_unhashed(n)) {
@@ -763,27 +523,6 @@ static inline void hlist_del_init(struct hlist_node *n)
763 } 523 }
764} 524}
765 525
766/**
767 * hlist_replace_rcu - replace old entry by new one
768 * @old : the element to be replaced
769 * @new : the new element to insert
770 *
771 * The @old entry will be replaced with the @new entry atomically.
772 */
773static inline void hlist_replace_rcu(struct hlist_node *old,
774 struct hlist_node *new)
775{
776 struct hlist_node *next = old->next;
777
778 new->next = next;
779 new->pprev = old->pprev;
780 smp_wmb();
781 if (next)
782 new->next->pprev = &new->next;
783 *new->pprev = new;
784 old->pprev = LIST_POISON2;
785}
786
787static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h) 526static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
788{ 527{
789 struct hlist_node *first = h->first; 528 struct hlist_node *first = h->first;
@@ -794,38 +533,6 @@ static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
794 n->pprev = &h->first; 533 n->pprev = &h->first;
795} 534}
796 535
797
798/**
799 * hlist_add_head_rcu
800 * @n: the element to add to the hash list.
801 * @h: the list to add to.
802 *
803 * Description:
804 * Adds the specified element to the specified hlist,
805 * while permitting racing traversals.
806 *
807 * The caller must take whatever precautions are necessary
808 * (such as holding appropriate locks) to avoid racing
809 * with another list-mutation primitive, such as hlist_add_head_rcu()
810 * or hlist_del_rcu(), running on this same list.
811 * However, it is perfectly legal to run concurrently with
812 * the _rcu list-traversal primitives, such as
813 * hlist_for_each_entry_rcu(), used to prevent memory-consistency
814 * problems on Alpha CPUs. Regardless of the type of CPU, the
815 * list-traversal primitive must be guarded by rcu_read_lock().
816 */
817static inline void hlist_add_head_rcu(struct hlist_node *n,
818 struct hlist_head *h)
819{
820 struct hlist_node *first = h->first;
821 n->next = first;
822 n->pprev = &h->first;
823 smp_wmb();
824 if (first)
825 first->pprev = &n->next;
826 h->first = n;
827}
828
829/* next must be != NULL */ 536/* next must be != NULL */
830static inline void hlist_add_before(struct hlist_node *n, 537static inline void hlist_add_before(struct hlist_node *n,
831 struct hlist_node *next) 538 struct hlist_node *next)
@@ -847,63 +554,6 @@ static inline void hlist_add_after(struct hlist_node *n,
847 next->next->pprev = &next->next; 554 next->next->pprev = &next->next;
848} 555}
849 556
850/**
851 * hlist_add_before_rcu
852 * @n: the new element to add to the hash list.
853 * @next: the existing element to add the new element before.
854 *
855 * Description:
856 * Adds the specified element to the specified hlist
857 * before the specified node while permitting racing traversals.
858 *
859 * The caller must take whatever precautions are necessary
860 * (such as holding appropriate locks) to avoid racing
861 * with another list-mutation primitive, such as hlist_add_head_rcu()
862 * or hlist_del_rcu(), running on this same list.
863 * However, it is perfectly legal to run concurrently with
864 * the _rcu list-traversal primitives, such as
865 * hlist_for_each_entry_rcu(), used to prevent memory-consistency
866 * problems on Alpha CPUs.
867 */
868static inline void hlist_add_before_rcu(struct hlist_node *n,
869 struct hlist_node *next)
870{
871 n->pprev = next->pprev;
872 n->next = next;
873 smp_wmb();
874 next->pprev = &n->next;
875 *(n->pprev) = n;
876}
877
878/**
879 * hlist_add_after_rcu
880 * @prev: the existing element to add the new element after.
881 * @n: the new element to add to the hash list.
882 *
883 * Description:
884 * Adds the specified element to the specified hlist
885 * after the specified node while permitting racing traversals.
886 *
887 * The caller must take whatever precautions are necessary
888 * (such as holding appropriate locks) to avoid racing
889 * with another list-mutation primitive, such as hlist_add_head_rcu()
890 * or hlist_del_rcu(), running on this same list.
891 * However, it is perfectly legal to run concurrently with
892 * the _rcu list-traversal primitives, such as
893 * hlist_for_each_entry_rcu(), used to prevent memory-consistency
894 * problems on Alpha CPUs.
895 */
896static inline void hlist_add_after_rcu(struct hlist_node *prev,
897 struct hlist_node *n)
898{
899 n->next = prev->next;
900 n->pprev = &prev->next;
901 smp_wmb();
902 prev->next = n;
903 if (n->next)
904 n->next->pprev = &n->next;
905}
906
907#define hlist_entry(ptr, type, member) container_of(ptr,type,member) 557#define hlist_entry(ptr, type, member) container_of(ptr,type,member)
908 558
909#define hlist_for_each(pos, head) \ 559#define hlist_for_each(pos, head) \
@@ -964,21 +614,4 @@ static inline void hlist_add_after_rcu(struct hlist_node *prev,
964 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \ 614 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
965 pos = n) 615 pos = n)
966 616
967/**
968 * hlist_for_each_entry_rcu - iterate over rcu list of given type
969 * @tpos: the type * to use as a loop cursor.
970 * @pos: the &struct hlist_node to use as a loop cursor.
971 * @head: the head for your list.
972 * @member: the name of the hlist_node within the struct.
973 *
974 * This list-traversal primitive may safely run concurrently with
975 * the _rcu list-mutation primitives such as hlist_add_head_rcu()
976 * as long as the traversal is guarded by rcu_read_lock().
977 */
978#define hlist_for_each_entry_rcu(tpos, pos, head, member) \
979 for (pos = rcu_dereference((head)->first); \
980 pos && ({ prefetch(pos->next); 1;}) && \
981 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
982 pos = rcu_dereference(pos->next))
983
984#endif 617#endif
diff --git a/include/linux/rculist.h b/include/linux/rculist.h
new file mode 100644
index 000000000000..aa9b3eb15683
--- /dev/null
+++ b/include/linux/rculist.h
@@ -0,0 +1,396 @@
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 */
17static 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 */
43static 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 */
64static 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 */
94static 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 */
108static 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 */
136static 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 */
263static 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 */
276static 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 */
309static 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 */
339static 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 */
367static 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
diff --git a/kernel/pid.c b/kernel/pid.c
index 20d59fa2d493..30bd5d4b2ac7 100644
--- a/kernel/pid.c
+++ b/kernel/pid.c
@@ -30,6 +30,7 @@
30#include <linux/module.h> 30#include <linux/module.h>
31#include <linux/slab.h> 31#include <linux/slab.h>
32#include <linux/init.h> 32#include <linux/init.h>
33#include <linux/rculist.h>
33#include <linux/bootmem.h> 34#include <linux/bootmem.h>
34#include <linux/hash.h> 35#include <linux/hash.h>
35#include <linux/pid_namespace.h> 36#include <linux/pid_namespace.h>
diff --git a/lib/textsearch.c b/lib/textsearch.c
index be8bda3862f5..a3e500ad51d7 100644
--- a/lib/textsearch.c
+++ b/lib/textsearch.c
@@ -97,6 +97,7 @@
97#include <linux/types.h> 97#include <linux/types.h>
98#include <linux/string.h> 98#include <linux/string.h>
99#include <linux/init.h> 99#include <linux/init.h>
100#include <linux/rculist.h>
100#include <linux/rcupdate.h> 101#include <linux/rcupdate.h>
101#include <linux/err.h> 102#include <linux/err.h>
102#include <linux/textsearch.h> 103#include <linux/textsearch.h>
diff --git a/net/802/psnap.c b/net/802/psnap.c
index 31128cb92a23..ea4643931446 100644
--- a/net/802/psnap.c
+++ b/net/802/psnap.c
@@ -20,6 +20,7 @@
20#include <linux/mm.h> 20#include <linux/mm.h>
21#include <linux/in.h> 21#include <linux/in.h>
22#include <linux/init.h> 22#include <linux/init.h>
23#include <linux/rculist.h>
23 24
24static LIST_HEAD(snap_list); 25static LIST_HEAD(snap_list);
25static DEFINE_SPINLOCK(snap_lock); 26static DEFINE_SPINLOCK(snap_lock);
diff --git a/net/8021q/vlan.c b/net/8021q/vlan.c
index 2a739adaa92b..e7ddbfa0e02f 100644
--- a/net/8021q/vlan.c
+++ b/net/8021q/vlan.c
@@ -27,6 +27,7 @@
27#include <linux/mm.h> 27#include <linux/mm.h>
28#include <linux/in.h> 28#include <linux/in.h>
29#include <linux/init.h> 29#include <linux/init.h>
30#include <linux/rculist.h>
30#include <net/p8022.h> 31#include <net/p8022.h>
31#include <net/arp.h> 32#include <net/arp.h>
32#include <linux/rtnetlink.h> 33#include <linux/rtnetlink.h>
diff --git a/net/bridge/br_fdb.c b/net/bridge/br_fdb.c
index 72c5976a5ce3..142060f02054 100644
--- a/net/bridge/br_fdb.c
+++ b/net/bridge/br_fdb.c
@@ -15,6 +15,7 @@
15 15
16#include <linux/kernel.h> 16#include <linux/kernel.h>
17#include <linux/init.h> 17#include <linux/init.h>
18#include <linux/rculist.h>
18#include <linux/spinlock.h> 19#include <linux/spinlock.h>
19#include <linux/times.h> 20#include <linux/times.h>
20#include <linux/netdevice.h> 21#include <linux/netdevice.h>
diff --git a/net/bridge/br_stp.c b/net/bridge/br_stp.c
index e38034aa56f5..9e96ffcd29a3 100644
--- a/net/bridge/br_stp.c
+++ b/net/bridge/br_stp.c
@@ -13,6 +13,7 @@
13 * 2 of the License, or (at your option) any later version. 13 * 2 of the License, or (at your option) any later version.
14 */ 14 */
15#include <linux/kernel.h> 15#include <linux/kernel.h>
16#include <linux/rculist.h>
16 17
17#include "br_private.h" 18#include "br_private.h"
18#include "br_private_stp.h" 19#include "br_private_stp.h"
diff --git a/net/netlabel/netlabel_domainhash.c b/net/netlabel/netlabel_domainhash.c
index 02c2f7c0b255..643c032a3a57 100644
--- a/net/netlabel/netlabel_domainhash.c
+++ b/net/netlabel/netlabel_domainhash.c
@@ -30,8 +30,7 @@
30 */ 30 */
31 31
32#include <linux/types.h> 32#include <linux/types.h>
33#include <linux/rcupdate.h> 33#include <linux/rculist.h>
34#include <linux/list.h>
35#include <linux/skbuff.h> 34#include <linux/skbuff.h>
36#include <linux/spinlock.h> 35#include <linux/spinlock.h>
37#include <linux/string.h> 36#include <linux/string.h>