Line data Source code
1 : /*
2 : * Copyright (c) 2016-2018 David Lamparter, for NetDEF, Inc.
3 : *
4 : * Permission to use, copy, modify, and distribute this software for any
5 : * purpose with or without fee is hereby granted, provided that the above
6 : * copyright notice and this permission notice appear in all copies.
7 : *
8 : * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
9 : * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
10 : * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
11 : * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
12 : * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
13 : * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
14 : * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
15 : */
16 :
17 : #ifdef HAVE_CONFIG_H
18 : #include "config.h"
19 : #endif
20 :
21 : #include <assert.h>
22 :
23 : #include "atomlist.h"
24 :
25 0 : void atomlist_add_head(struct atomlist_head *h, struct atomlist_item *item)
26 : {
27 0 : atomptr_t prevval;
28 0 : atomptr_t i = atomptr_i(item);
29 :
30 0 : atomic_fetch_add_explicit(&h->count, 1, memory_order_relaxed);
31 :
32 : /* updating ->last is possible here, but makes the code considerably
33 : * more complicated... let's not.
34 : */
35 0 : prevval = ATOMPTR_NULL;
36 0 : item->next = ATOMPTR_NULL;
37 :
38 : /* head-insert atomically
39 : * release barrier: item + item->next writes must be completed
40 : */
41 0 : while (!atomic_compare_exchange_weak_explicit(&h->first, &prevval, i,
42 : memory_order_release, memory_order_relaxed))
43 0 : atomic_store_explicit(&item->next, prevval,
44 : memory_order_relaxed);
45 0 : }
46 :
47 3969 : void atomlist_add_tail(struct atomlist_head *h, struct atomlist_item *item)
48 : {
49 3969 : atomptr_t prevval = ATOMPTR_NULL;
50 3969 : atomptr_t i = atomptr_i(item);
51 3969 : atomptr_t hint;
52 3969 : struct atomlist_item *prevptr;
53 3969 : _Atomic atomptr_t *prev;
54 :
55 3969 : item->next = ATOMPTR_NULL;
56 :
57 3969 : atomic_fetch_add_explicit(&h->count, 1, memory_order_relaxed);
58 :
59 : /* place new item into ->last
60 : * release: item writes completed; acquire: DD barrier on hint
61 : */
62 3969 : hint = atomic_exchange_explicit(&h->last, i, memory_order_acq_rel);
63 :
64 3969 : while (1) {
65 3969 : if (atomptr_p(hint) == NULL)
66 593 : prev = &h->first;
67 : else
68 3376 : prev = &atomlist_itemp(hint)->next;
69 :
70 3969 : do {
71 3969 : prevval = atomic_load_explicit(prev,
72 : memory_order_consume);
73 3969 : prevptr = atomlist_itemp(prevval);
74 3969 : if (prevptr == NULL)
75 : break;
76 :
77 0 : prev = &prevptr->next;
78 0 : } while (prevptr);
79 :
80 : /* last item is being deleted - start over */
81 3969 : if (atomptr_l(prevval)) {
82 0 : hint = ATOMPTR_NULL;
83 0 : continue;
84 : }
85 :
86 : /* no barrier - item->next is NULL and was so in xchg above */
87 3969 : if (!atomic_compare_exchange_strong_explicit(prev, &prevval, i,
88 : memory_order_consume,
89 : memory_order_consume)) {
90 0 : hint = prevval;
91 0 : continue;
92 : }
93 3969 : break;
94 : }
95 3969 : }
96 :
97 3081 : static void atomlist_del_core(struct atomlist_head *h,
98 : struct atomlist_item *item,
99 : _Atomic atomptr_t *hint,
100 : atomptr_t next)
101 : {
102 3081 : _Atomic atomptr_t *prev = hint ? hint : &h->first, *upd;
103 3081 : atomptr_t prevval, updval;
104 3081 : struct atomlist_item *prevptr;
105 :
106 : /* drop us off "last" if needed. no r/w to barrier. */
107 3081 : prevval = atomptr_i(item);
108 3081 : atomic_compare_exchange_strong_explicit(&h->last, &prevval,
109 : ATOMPTR_NULL,
110 : memory_order_relaxed, memory_order_relaxed);
111 :
112 3081 : atomic_fetch_sub_explicit(&h->count, 1, memory_order_relaxed);
113 :
114 : /* the following code should be identical (except sort<>list) to
115 : * atomsort_del_hint()
116 : */
117 3083 : while (1) {
118 3083 : upd = NULL;
119 3083 : updval = ATOMPTR_LOCK;
120 :
121 4095 : do {
122 4095 : prevval = atomic_load_explicit(prev,
123 : memory_order_consume);
124 :
125 : /* track the beginning of a chain of deleted items
126 : * this is necessary to make this lock-free; we can
127 : * complete deletions started by other threads.
128 : */
129 4095 : if (!atomptr_l(prevval)) {
130 4094 : updval = prevval;
131 4094 : upd = prev;
132 : }
133 :
134 4095 : prevptr = atomlist_itemp(prevval);
135 4095 : if (prevptr == item)
136 : break;
137 :
138 1012 : prev = &prevptr->next;
139 1012 : } while (prevptr);
140 :
141 3083 : if (prevptr != item)
142 : /* another thread completed our deletion */
143 3080 : return;
144 :
145 3083 : if (!upd || atomptr_l(updval)) {
146 : /* failed to find non-deleted predecessor...
147 : * have to try again
148 : */
149 1 : prev = &h->first;
150 1 : continue;
151 : }
152 :
153 3082 : if (!atomic_compare_exchange_strong_explicit(upd, &updval,
154 : next, memory_order_consume,
155 : memory_order_consume)) {
156 : /* prev doesn't point to item anymore, something
157 : * was inserted. continue at same position forward.
158 : */
159 1 : continue;
160 : }
161 : break;
162 : }
163 : }
164 :
165 933 : void atomlist_del_hint(struct atomlist_head *h, struct atomlist_item *item,
166 : _Atomic atomptr_t *hint)
167 : {
168 933 : atomptr_t next;
169 :
170 : /* mark ourselves in-delete - full barrier */
171 933 : next = atomic_fetch_or_explicit(&item->next, ATOMPTR_LOCK,
172 : memory_order_acquire);
173 933 : assert(!atomptr_l(next)); /* delete race on same item */
174 :
175 933 : atomlist_del_core(h, item, hint, next);
176 933 : }
177 :
178 2289 : struct atomlist_item *atomlist_pop(struct atomlist_head *h)
179 : {
180 2289 : struct atomlist_item *item;
181 2289 : atomptr_t next;
182 :
183 : /* grab head of the list - and remember it in replval for the
184 : * actual delete below. No matter what, the head of the list is
185 : * where we start deleting because either it's our item, or it's
186 : * some delete-marked items and then our item.
187 : */
188 2289 : next = atomic_load_explicit(&h->first, memory_order_consume);
189 :
190 2289 : do {
191 2289 : item = atomlist_itemp(next);
192 2289 : if (!item)
193 : return NULL;
194 :
195 : /* try to mark deletion */
196 2148 : next = atomic_fetch_or_explicit(&item->next, ATOMPTR_LOCK,
197 : memory_order_acquire);
198 :
199 2148 : } while (atomptr_l(next));
200 : /* if loop is taken: delete race on same item (another pop or del)
201 : * => proceed to next item
202 : * if loop exited here: we have our item selected and marked
203 : */
204 2148 : atomlist_del_core(h, item, &h->first, next);
205 2148 : return item;
206 : }
207 :
208 0 : struct atomsort_item *atomsort_add(struct atomsort_head *h,
209 : struct atomsort_item *item, int (*cmpfn)(
210 : const struct atomsort_item *,
211 : const struct atomsort_item *))
212 : {
213 0 : _Atomic atomptr_t *prev;
214 0 : atomptr_t prevval;
215 0 : atomptr_t i = atomptr_i(item);
216 0 : struct atomsort_item *previtem;
217 0 : int cmpval;
218 :
219 0 : do {
220 0 : prev = &h->first;
221 :
222 0 : do {
223 0 : prevval = atomic_load_explicit(prev,
224 : memory_order_acquire);
225 0 : previtem = atomptr_p(prevval);
226 :
227 0 : if (!previtem || (cmpval = cmpfn(previtem, item)) > 0)
228 : break;
229 0 : if (cmpval == 0)
230 0 : return previtem;
231 :
232 0 : prev = &previtem->next;
233 : } while (1);
234 :
235 0 : if (atomptr_l(prevval))
236 0 : continue;
237 :
238 0 : item->next = prevval;
239 0 : if (atomic_compare_exchange_strong_explicit(prev, &prevval, i,
240 : memory_order_release, memory_order_relaxed))
241 : break;
242 : } while (1);
243 :
244 0 : atomic_fetch_add_explicit(&h->count, 1, memory_order_relaxed);
245 0 : return NULL;
246 : }
247 :
248 0 : static void atomsort_del_core(struct atomsort_head *h,
249 : struct atomsort_item *item, _Atomic atomptr_t *hint,
250 : atomptr_t next)
251 : {
252 0 : _Atomic atomptr_t *prev = hint ? hint : &h->first, *upd;
253 0 : atomptr_t prevval, updval;
254 0 : struct atomsort_item *prevptr;
255 :
256 0 : atomic_fetch_sub_explicit(&h->count, 1, memory_order_relaxed);
257 :
258 : /* the following code should be identical (except sort<>list) to
259 : * atomlist_del_core()
260 : */
261 0 : while (1) {
262 0 : upd = NULL;
263 0 : updval = ATOMPTR_LOCK;
264 :
265 0 : do {
266 0 : prevval = atomic_load_explicit(prev,
267 : memory_order_consume);
268 :
269 : /* track the beginning of a chain of deleted items
270 : * this is necessary to make this lock-free; we can
271 : * complete deletions started by other threads.
272 : */
273 0 : if (!atomptr_l(prevval)) {
274 0 : updval = prevval;
275 0 : upd = prev;
276 : }
277 :
278 0 : prevptr = atomsort_itemp(prevval);
279 0 : if (prevptr == item)
280 : break;
281 :
282 0 : prev = &prevptr->next;
283 0 : } while (prevptr);
284 :
285 0 : if (prevptr != item)
286 : /* another thread completed our deletion */
287 0 : return;
288 :
289 0 : if (!upd || atomptr_l(updval)) {
290 : /* failed to find non-deleted predecessor...
291 : * have to try again
292 : */
293 0 : prev = &h->first;
294 0 : continue;
295 : }
296 :
297 0 : if (!atomic_compare_exchange_strong_explicit(upd, &updval,
298 : next, memory_order_relaxed,
299 : memory_order_relaxed)) {
300 : /* prev doesn't point to item anymore, something
301 : * was inserted. continue at same position forward.
302 : */
303 0 : continue;
304 : }
305 : break;
306 : }
307 : }
308 :
309 0 : void atomsort_del_hint(struct atomsort_head *h, struct atomsort_item *item,
310 : _Atomic atomptr_t *hint)
311 : {
312 0 : atomptr_t next;
313 :
314 : /* mark ourselves in-delete - full barrier */
315 0 : next = atomic_fetch_or_explicit(&item->next, ATOMPTR_LOCK,
316 : memory_order_seq_cst);
317 0 : assert(!atomptr_l(next)); /* delete race on same item */
318 :
319 0 : atomsort_del_core(h, item, hint, next);
320 0 : }
321 :
322 0 : struct atomsort_item *atomsort_pop(struct atomsort_head *h)
323 : {
324 0 : struct atomsort_item *item;
325 0 : atomptr_t next;
326 :
327 : /* grab head of the list - and remember it in replval for the
328 : * actual delete below. No matter what, the head of the list is
329 : * where we start deleting because either it's our item, or it's
330 : * some delete-marked items and then our item.
331 : */
332 0 : next = atomic_load_explicit(&h->first, memory_order_consume);
333 :
334 0 : do {
335 0 : item = atomsort_itemp(next);
336 0 : if (!item)
337 : return NULL;
338 :
339 : /* try to mark deletion */
340 0 : next = atomic_fetch_or_explicit(&item->next, ATOMPTR_LOCK,
341 : memory_order_acquire);
342 :
343 0 : } while (atomptr_l(next));
344 : /* if loop is taken: delete race on same item (another pop or del)
345 : * => proceed to next item
346 : * if loop exited here: we have our item selected and marked
347 : */
348 0 : atomsort_del_core(h, item, &h->first, next);
349 0 : return item;
350 : }
|
