]>
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 | ||
beaec533 AP |
95 | /** |
96 | * member_address_is_nonnull - check whether the member address is not NULL | |
97 | * @ptr: the object pointer (struct type * that contains the llist_node) | |
98 | * @member: the name of the llist_node within the struct. | |
99 | * | |
100 | * This macro is conceptually the same as | |
101 | * &ptr->member != NULL | |
102 | * but it works around the fact that compilers can decide that taking a member | |
103 | * address is never a NULL pointer. | |
104 | * | |
105 | * Real objects that start at a high address and have a member at NULL are | |
106 | * unlikely to exist, but such pointers may be returned e.g. by the | |
107 | * container_of() macro. | |
108 | */ | |
109 | #define member_address_is_nonnull(ptr, member) \ | |
110 | ((uintptr_t)(ptr) + offsetof(typeof(*(ptr)), member) != 0) | |
111 | ||
f49f23ab HY |
112 | /** |
113 | * llist_for_each - iterate over some deleted entries of a lock-less list | |
114 | * @pos: the &struct llist_node to use as a loop cursor | |
115 | * @node: the first entry of deleted list entries | |
116 | * | |
117 | * In general, some entries of the lock-less list can be traversed | |
118 | * safely only after being deleted from list, so start with an entry | |
119 | * instead of list head. | |
120 | * | |
121 | * If being used on entries deleted from lock-less list directly, the | |
122 | * traverse order is from the newest to the oldest added entry. If | |
123 | * you want to traverse from the oldest to the newest, you must | |
124 | * reverse the order by yourself before traversing. | |
125 | */ | |
126 | #define llist_for_each(pos, node) \ | |
127 | for ((pos) = (node); pos; (pos) = (pos)->next) | |
128 | ||
d714893e BP |
129 | /** |
130 | * llist_for_each_safe - iterate over some deleted entries of a lock-less list | |
131 | * safe against removal of list entry | |
132 | * @pos: the &struct llist_node to use as a loop cursor | |
133 | * @n: another &struct llist_node to use as temporary storage | |
134 | * @node: the first entry of deleted list entries | |
135 | * | |
136 | * In general, some entries of the lock-less list can be traversed | |
137 | * safely only after being deleted from list, so start with an entry | |
138 | * instead of list head. | |
139 | * | |
140 | * If being used on entries deleted from lock-less list directly, the | |
141 | * traverse order is from the newest to the oldest added entry. If | |
142 | * you want to traverse from the oldest to the newest, you must | |
143 | * reverse the order by yourself before traversing. | |
144 | */ | |
145 | #define llist_for_each_safe(pos, n, node) \ | |
146 | for ((pos) = (node); (pos) && ((n) = (pos)->next, true); (pos) = (n)) | |
147 | ||
f49f23ab HY |
148 | /** |
149 | * llist_for_each_entry - iterate over some deleted entries of lock-less list of given type | |
150 | * @pos: the type * to use as a loop cursor. | |
151 | * @node: the fist entry of deleted list entries. | |
152 | * @member: the name of the llist_node with the struct. | |
153 | * | |
154 | * In general, some entries of the lock-less list can be traversed | |
155 | * safely only after being removed from list, so start with an entry | |
156 | * instead of list head. | |
157 | * | |
158 | * If being used on entries deleted from lock-less list directly, the | |
159 | * traverse order is from the newest to the oldest added entry. If | |
160 | * you want to traverse from the oldest to the newest, you must | |
161 | * reverse the order by yourself before traversing. | |
162 | */ | |
163 | #define llist_for_each_entry(pos, node, member) \ | |
164 | for ((pos) = llist_entry((node), typeof(*(pos)), member); \ | |
beaec533 | 165 | member_address_is_nonnull(pos, member); \ |
f49f23ab HY |
166 | (pos) = llist_entry((pos)->member.next, typeof(*(pos)), member)) |
167 | ||
809850b7 PH |
168 | /** |
169 | * llist_for_each_entry_safe - iterate over some deleted entries of lock-less list of given type | |
170 | * safe against removal of list entry | |
171 | * @pos: the type * to use as a loop cursor. | |
172 | * @n: another type * to use as temporary storage | |
173 | * @node: the first entry of deleted list entries. | |
174 | * @member: the name of the llist_node with the struct. | |
175 | * | |
176 | * In general, some entries of the lock-less list can be traversed | |
177 | * safely only after being removed from list, so start with an entry | |
178 | * instead of list head. | |
179 | * | |
180 | * If being used on entries deleted from lock-less list directly, the | |
181 | * traverse order is from the newest to the oldest added entry. If | |
182 | * you want to traverse from the oldest to the newest, you must | |
183 | * reverse the order by yourself before traversing. | |
184 | */ | |
185 | #define llist_for_each_entry_safe(pos, n, node, member) \ | |
186 | for (pos = llist_entry((node), typeof(*pos), member); \ | |
beaec533 | 187 | member_address_is_nonnull(pos, member) && \ |
809850b7 PH |
188 | (n = llist_entry(pos->member.next, typeof(*n), member), true); \ |
189 | pos = n) | |
190 | ||
f49f23ab HY |
191 | /** |
192 | * llist_empty - tests whether a lock-less list is empty | |
193 | * @head: the list to test | |
194 | * | |
195 | * Not guaranteed to be accurate or up to date. Just a quick way to | |
196 | * test whether the list is empty without deleting something from the | |
197 | * list. | |
198 | */ | |
1230db8e | 199 | static inline bool llist_empty(const struct llist_head *head) |
f49f23ab HY |
200 | { |
201 | return ACCESS_ONCE(head->first) == NULL; | |
202 | } | |
203 | ||
924f8f5a PZ |
204 | static inline struct llist_node *llist_next(struct llist_node *node) |
205 | { | |
206 | return node->next; | |
207 | } | |
208 | ||
e9a17bd7 ON |
209 | extern bool llist_add_batch(struct llist_node *new_first, |
210 | struct llist_node *new_last, | |
211 | struct llist_head *head); | |
1230db8e HY |
212 | /** |
213 | * llist_add - add a new entry | |
214 | * @new: new entry to be added | |
215 | * @head: the head for your lock-less list | |
781f7fd9 | 216 | * |
fc23af34 | 217 | * Returns true if the list was empty prior to adding this entry. |
1230db8e | 218 | */ |
781f7fd9 | 219 | static inline bool llist_add(struct llist_node *new, struct llist_head *head) |
1230db8e | 220 | { |
e9a17bd7 | 221 | return llist_add_batch(new, new, head); |
1230db8e HY |
222 | } |
223 | ||
224 | /** | |
225 | * llist_del_all - delete all entries from lock-less list | |
226 | * @head: the head of lock-less list to delete all entries | |
227 | * | |
228 | * If list is empty, return NULL, otherwise, delete all entries and | |
229 | * return the pointer to the first entry. The order of entries | |
230 | * deleted is from the newest to the oldest added one. | |
231 | */ | |
232 | static inline struct llist_node *llist_del_all(struct llist_head *head) | |
233 | { | |
1230db8e HY |
234 | return xchg(&head->first, NULL); |
235 | } | |
540f41ed | 236 | |
540f41ed SR |
237 | extern struct llist_node *llist_del_first(struct llist_head *head); |
238 | ||
b89241e8 CH |
239 | struct llist_node *llist_reverse_order(struct llist_node *head); |
240 | ||
f49f23ab | 241 | #endif /* LLIST_H */ |