]>
Commit | Line | Data |
---|---|---|
f49f23ab HY |
1 | #ifndef LLIST_H |
2 | #define LLIST_H | |
3 | /* | |
4 | * Lock-less NULL terminated single linked list | |
5 | * | |
d78973c3 JF |
6 | * Cases where locking is not needed: |
7 | * If there are multiple producers and multiple consumers, llist_add can be | |
8 | * used in producers and llist_del_all can be used in consumers simultaneously | |
9 | * without locking. Also a single consumer can use llist_del_first while | |
10 | * multiple producers simultaneously use llist_add, without any locking. | |
f49f23ab | 11 | * |
d78973c3 JF |
12 | * Cases where locking is needed: |
13 | * If we have multiple consumers with llist_del_first used in one consumer, and | |
14 | * llist_del_first or llist_del_all used in other consumers, then a lock is | |
15 | * needed. This is because llist_del_first depends on list->first->next not | |
16 | * changing, but without lock protection, there's no way to be sure about that | |
17 | * if a preemption happens in the middle of the delete operation and on being | |
18 | * preempted back, the list->first is the same as before causing the cmpxchg in | |
19 | * llist_del_first to succeed. For example, while a llist_del_first operation | |
20 | * is in progress in one consumer, then a llist_del_first, llist_add, | |
21 | * llist_add (or llist_del_all, llist_add, llist_add) sequence in another | |
22 | * consumer may cause violations. | |
f49f23ab | 23 | * |
d78973c3 | 24 | * This can be summarized as follows: |
f49f23ab HY |
25 | * |
26 | * | add | del_first | del_all | |
27 | * add | - | - | - | |
28 | * del_first | | L | L | |
29 | * del_all | | | - | |
30 | * | |
d78973c3 JF |
31 | * Where, a particular row's operation can happen concurrently with a column's |
32 | * operation, with "-" being no lock needed, while "L" being lock is needed. | |
f49f23ab HY |
33 | * |
34 | * The list entries deleted via llist_del_all can be traversed with | |
35 | * traversing function such as llist_for_each etc. But the list | |
36 | * entries can not be traversed safely before deleted from the list. | |
37 | * The order of deleted entries is from the newest to the oldest added | |
38 | * one. If you want to traverse from the oldest to the newest, you | |
39 | * must reverse the order by yourself before traversing. | |
40 | * | |
41 | * The basic atomic operation of this list is cmpxchg on long. On | |
42 | * architectures that don't have NMI-safe cmpxchg implementation, the | |
2c30245c IM |
43 | * list can NOT be used in NMI handlers. So code that uses the list in |
44 | * an NMI handler should depend on CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG. | |
1230db8e HY |
45 | * |
46 | * Copyright 2010,2011 Intel Corp. | |
47 | * Author: Huang Ying <ying.huang@intel.com> | |
48 | * | |
49 | * This program is free software; you can redistribute it and/or | |
50 | * modify it under the terms of the GNU General Public License version | |
51 | * 2 as published by the Free Software Foundation; | |
52 | * | |
53 | * This program is distributed in the hope that it will be useful, | |
54 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
55 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
56 | * GNU General Public License for more details. | |
57 | * | |
58 | * You should have received a copy of the GNU General Public License | |
59 | * along with this program; if not, write to the Free Software | |
60 | * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA | |
f49f23ab HY |
61 | */ |
62 | ||
cd074aea | 63 | #include <linux/atomic.h> |
1230db8e | 64 | #include <linux/kernel.h> |
1230db8e | 65 | |
f49f23ab HY |
66 | struct llist_head { |
67 | struct llist_node *first; | |
68 | }; | |
69 | ||
70 | struct llist_node { | |
71 | struct llist_node *next; | |
72 | }; | |
73 | ||
74 | #define LLIST_HEAD_INIT(name) { NULL } | |
75 | #define LLIST_HEAD(name) struct llist_head name = LLIST_HEAD_INIT(name) | |
76 | ||
77 | /** | |
78 | * init_llist_head - initialize lock-less list head | |
79 | * @head: the head for your lock-less list | |
80 | */ | |
81 | static inline void init_llist_head(struct llist_head *list) | |
82 | { | |
83 | list->first = NULL; | |
84 | } | |
85 | ||
86 | /** | |
87 | * llist_entry - get the struct of this entry | |
88 | * @ptr: the &struct llist_node pointer. | |
89 | * @type: the type of the struct this is embedded in. | |
90 | * @member: the name of the llist_node within the struct. | |
91 | */ | |
92 | #define llist_entry(ptr, type, member) \ | |
93 | container_of(ptr, type, member) | |
94 | ||
95 | /** | |
96 | * llist_for_each - iterate over some deleted entries of a lock-less list | |
97 | * @pos: the &struct llist_node to use as a loop cursor | |
98 | * @node: the first entry of deleted list entries | |
99 | * | |
100 | * In general, some entries of the lock-less list can be traversed | |
101 | * safely only after being deleted from list, so start with an entry | |
102 | * instead of list head. | |
103 | * | |
104 | * If being used on entries deleted from lock-less list directly, the | |
105 | * traverse order is from the newest to the oldest added entry. If | |
106 | * you want to traverse from the oldest to the newest, you must | |
107 | * reverse the order by yourself before traversing. | |
108 | */ | |
109 | #define llist_for_each(pos, node) \ | |
110 | for ((pos) = (node); pos; (pos) = (pos)->next) | |
111 | ||
112 | /** | |
113 | * llist_for_each_entry - iterate over some deleted entries of lock-less list of given type | |
114 | * @pos: the type * to use as a loop cursor. | |
115 | * @node: the fist entry of deleted list entries. | |
116 | * @member: the name of the llist_node with the struct. | |
117 | * | |
118 | * In general, some entries of the lock-less list can be traversed | |
119 | * safely only after being removed from list, so start with an entry | |
120 | * instead of list head. | |
121 | * | |
122 | * If being used on entries deleted from lock-less list directly, the | |
123 | * traverse order is from the newest to the oldest added entry. If | |
124 | * you want to traverse from the oldest to the newest, you must | |
125 | * reverse the order by yourself before traversing. | |
126 | */ | |
127 | #define llist_for_each_entry(pos, node, member) \ | |
128 | for ((pos) = llist_entry((node), typeof(*(pos)), member); \ | |
129 | &(pos)->member != NULL; \ | |
130 | (pos) = llist_entry((pos)->member.next, typeof(*(pos)), member)) | |
131 | ||
809850b7 PH |
132 | /** |
133 | * llist_for_each_entry_safe - iterate over some deleted entries of lock-less list of given type | |
134 | * safe against removal of list entry | |
135 | * @pos: the type * to use as a loop cursor. | |
136 | * @n: another type * to use as temporary storage | |
137 | * @node: the first entry of deleted list entries. | |
138 | * @member: the name of the llist_node with the struct. | |
139 | * | |
140 | * In general, some entries of the lock-less list can be traversed | |
141 | * safely only after being removed from list, so start with an entry | |
142 | * instead of list head. | |
143 | * | |
144 | * If being used on entries deleted from lock-less list directly, the | |
145 | * traverse order is from the newest to the oldest added entry. If | |
146 | * you want to traverse from the oldest to the newest, you must | |
147 | * reverse the order by yourself before traversing. | |
148 | */ | |
149 | #define llist_for_each_entry_safe(pos, n, node, member) \ | |
150 | for (pos = llist_entry((node), typeof(*pos), member); \ | |
151 | &pos->member != NULL && \ | |
152 | (n = llist_entry(pos->member.next, typeof(*n), member), true); \ | |
153 | pos = n) | |
154 | ||
f49f23ab HY |
155 | /** |
156 | * llist_empty - tests whether a lock-less list is empty | |
157 | * @head: the list to test | |
158 | * | |
159 | * Not guaranteed to be accurate or up to date. Just a quick way to | |
160 | * test whether the list is empty without deleting something from the | |
161 | * list. | |
162 | */ | |
1230db8e | 163 | static inline bool llist_empty(const struct llist_head *head) |
f49f23ab HY |
164 | { |
165 | return ACCESS_ONCE(head->first) == NULL; | |
166 | } | |
167 | ||
924f8f5a PZ |
168 | static inline struct llist_node *llist_next(struct llist_node *node) |
169 | { | |
170 | return node->next; | |
171 | } | |
172 | ||
e9a17bd7 ON |
173 | extern bool llist_add_batch(struct llist_node *new_first, |
174 | struct llist_node *new_last, | |
175 | struct llist_head *head); | |
1230db8e HY |
176 | /** |
177 | * llist_add - add a new entry | |
178 | * @new: new entry to be added | |
179 | * @head: the head for your lock-less list | |
781f7fd9 | 180 | * |
fc23af34 | 181 | * Returns true if the list was empty prior to adding this entry. |
1230db8e | 182 | */ |
781f7fd9 | 183 | static inline bool llist_add(struct llist_node *new, struct llist_head *head) |
1230db8e | 184 | { |
e9a17bd7 | 185 | return llist_add_batch(new, new, head); |
1230db8e HY |
186 | } |
187 | ||
188 | /** | |
189 | * llist_del_all - delete all entries from lock-less list | |
190 | * @head: the head of lock-less list to delete all entries | |
191 | * | |
192 | * If list is empty, return NULL, otherwise, delete all entries and | |
193 | * return the pointer to the first entry. The order of entries | |
194 | * deleted is from the newest to the oldest added one. | |
195 | */ | |
196 | static inline struct llist_node *llist_del_all(struct llist_head *head) | |
197 | { | |
1230db8e HY |
198 | return xchg(&head->first, NULL); |
199 | } | |
540f41ed | 200 | |
540f41ed SR |
201 | extern struct llist_node *llist_del_first(struct llist_head *head); |
202 | ||
b89241e8 CH |
203 | struct llist_node *llist_reverse_order(struct llist_node *head); |
204 | ||
f49f23ab | 205 | #endif /* LLIST_H */ |