aboutsummaryrefslogtreecommitdiffstats
path: root/include/linux/list.h
diff options
context:
space:
mode:
authorIngo Molnar <mingo@elte.hu>2008-07-18 13:31:12 -0400
committerIngo Molnar <mingo@elte.hu>2008-07-18 13:31:12 -0400
commit3e370b29d35fb01bfb92c2814d6f79bf6a2cb970 (patch)
tree3b8fb467d60bfe6a34686f4abdc3a60050ba40a4 /include/linux/list.h
parent88d1dce3a74367291f65a757fbdcaf17f042f30c (diff)
parent5b664cb235e97afbf34db9c4d77f08ebd725335e (diff)
Merge branch 'linus' into x86/pci-ioapic-boot-irq-quirks
Conflicts: drivers/pci/quirks.c Signed-off-by: Ingo Molnar <mingo@elte.hu>
Diffstat (limited to 'include/linux/list.h')
-rw-r--r--include/linux/list.h367
1 files changed, 0 insertions, 367 deletions
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