]>
git.proxmox.com Git - mirror_frr.git/blob - lib/atomlist.h
2 * Copyright (c) 2016-2019 David Lamparter, for NetDEF, Inc.
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.
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.
17 #ifndef _FRR_ATOMLIST_H
18 #define _FRR_ATOMLIST_H
21 #include "frratomic.h"
23 /* pointer with lock/deleted/invalid bit in lowest bit
25 * for atomlist/atomsort, "locked" means "this pointer can't be updated, the
26 * item is being deleted". it is permissible to assume the item will indeed
27 * be deleted (as there are no replace/etc. ops in this).
29 * in general, lowest 2/3 bits on 32/64bit architectures are available for
30 * uses like this; the only thing that will really break this is putting an
31 * atomlist_item in a struct with "packed" attribute. (it'll break
32 * immediately and consistently.) -- don't do that.
34 * ATOMPTR_USER is currently unused (and available for atomic hash or skiplist
37 typedef uintptr_t atomptr_t
;
38 #define ATOMPTR_MASK (UINTPTR_MAX - 3)
39 #define ATOMPTR_LOCK (1)
40 #define ATOMPTR_USER (2)
41 #define ATOMPTR_NULL (0)
43 static inline atomptr_t
atomptr_i(void *val
)
45 atomptr_t atomval
= (atomptr_t
)val
;
47 assert(!(atomval
& ATOMPTR_LOCK
));
50 static inline void *atomptr_p(atomptr_t val
)
52 return (void *)(val
& ATOMPTR_MASK
);
54 static inline bool atomptr_l(atomptr_t val
)
56 return (bool)(val
& ATOMPTR_LOCK
);
58 static inline bool atomptr_u(atomptr_t val
)
60 return (bool)(val
& ATOMPTR_USER
);
64 /* the problem with, find(), find_gteq() and find_lt() on atomic lists is that
65 * they're neither an "acquire" nor a "release" operation; the element that
66 * was found is still on the list and doesn't change ownership. Therefore,
67 * an atomic transition in ownership state can't be implemented.
69 * Contrast this with add() or pop(): both function calls atomically transfer
70 * ownership of an item to or from the list, which makes them "acquire" /
71 * "release" operations.
73 * What can be implemented atomically is a "find_pop()", i.e. try to locate an
74 * item and atomically try to remove it if found. It's not currently
75 * implemented but can be added when needed.
77 * Either way - for find(), generally speaking, if you need to use find() on
78 * a list then the whole thing probably isn't well-suited to atomic
79 * implementation and you'll need to have extra locks around to make it work
82 #ifdef WNO_ATOMLIST_UNSAFE_FIND
83 # define atomic_find_warn
85 # define atomic_find_warn __attribute__((_DEPRECATED( \
86 "WARNING: find() on atomic lists cannot be atomic by principle; " \
87 "check code to make sure usage pattern is OK and if it is, use " \
88 "#define WNO_ATOMLIST_UNSAFE_FIND")))
92 /* single-linked list, unsorted/arbitrary.
93 * can be used as queue with add_tail / pop
95 * all operations are lock-free, but not neccessarily wait-free. this means
96 * that there is no state where the system as a whole stops making process,
97 * but it *is* possible that a *particular* thread is delayed by some time.
99 * the only way for this to happen is for other threads to continuously make
100 * updates. an inactive / blocked / deadlocked other thread cannot cause such
101 * delays, and to cause such delays a thread must be heavily hitting the list -
102 * it's a rather theoretical concern.
105 /* don't use these structs directly */
106 struct atomlist_item
{
107 _Atomic atomptr_t next
;
109 #define atomlist_itemp(val) ((struct atomlist_item *)atomptr_p(val))
111 struct atomlist_head
{
112 _Atomic atomptr_t first
, last
;
113 _Atomic
size_t count
;
118 * PREDECL_ATOMLIST(namelist)
120 * struct namelist_item nlitem;
122 * DECLARE_ATOMLIST(namelist, struct name, nlitem)
124 #define PREDECL_ATOMLIST(prefix) \
125 struct prefix ## _head { struct atomlist_head ah; }; \
126 struct prefix ## _item { struct atomlist_item ai; };
128 #define INIT_ATOMLIST(var) { }
130 #define DECLARE_ATOMLIST(prefix, type, field) \
131 macro_inline void prefix ## _add_head(struct prefix##_head *h, type *item) \
132 { atomlist_add_head(&h->ah, &item->field.ai); } \
133 macro_inline void prefix ## _add_tail(struct prefix##_head *h, type *item) \
134 { atomlist_add_tail(&h->ah, &item->field.ai); } \
135 macro_inline void prefix ## _del_hint(struct prefix##_head *h, type *item, \
136 _Atomic atomptr_t *hint) \
137 { atomlist_del_hint(&h->ah, &item->field.ai, hint); } \
138 macro_inline type *prefix ## _del(struct prefix##_head *h, type *item) \
139 { atomlist_del_hint(&h->ah, &item->field.ai, NULL); \
140 /* TODO: Return NULL if not found */ \
142 macro_inline type *prefix ## _pop(struct prefix##_head *h) \
143 { char *p = (char *)atomlist_pop(&h->ah); \
144 return p ? (type *)(p - offsetof(type, field)) : NULL; } \
145 macro_inline type *prefix ## _first(struct prefix##_head *h) \
146 { char *p = atomptr_p(atomic_load_explicit(&h->ah.first, \
147 memory_order_acquire)); \
148 return p ? (type *)(p - offsetof(type, field)) : NULL; } \
149 macro_inline type *prefix ## _next(struct prefix##_head *h, type *item) \
150 { char *p = atomptr_p(atomic_load_explicit(&item->field.ai.next, \
151 memory_order_acquire)); \
152 return p ? (type *)(p - offsetof(type, field)) : NULL; } \
153 macro_inline type *prefix ## _next_safe(struct prefix##_head *h, type *item) \
154 { return item ? prefix##_next(h, item) : NULL; } \
155 macro_inline size_t prefix ## _count(struct prefix##_head *h) \
156 { return atomic_load_explicit(&h->ah.count, memory_order_relaxed); } \
157 macro_inline void prefix ## _init(struct prefix##_head *h) \
159 memset(h, 0, sizeof(*h)); \
161 macro_inline void prefix ## _fini(struct prefix##_head *h) \
163 assert(prefix ## _count(h) == 0); \
164 memset(h, 0, sizeof(*h)); \
169 * - contention on ->first pointer
170 * - return implies completion
172 void atomlist_add_head(struct atomlist_head
*h
, struct atomlist_item
*item
);
175 * - concurrent add_tail can cause wait but has progress guarantee
176 * - return does NOT imply completion. completion is only guaranteed after
177 * all other add_tail operations that started before this add_tail have
180 void atomlist_add_tail(struct atomlist_head
*h
, struct atomlist_item
*item
);
184 * OWNER MUST HOLD REFERENCE ON ITEM TO BE DELETED, ENSURING NO OTHER THREAD
185 * WILL TRY TO DELETE THE SAME ITEM. DELETING INCLUDES pop().
187 * as with all deletions, threads that started reading earlier may still hold
188 * pointers to the deleted item. completion is however guaranteed for all
189 * reads starting later.
191 void atomlist_del_hint(struct atomlist_head
*h
, struct atomlist_item
*item
,
192 _Atomic atomptr_t
*hint
);
196 * as with all deletions, threads that started reading earlier may still hold
197 * pointers to the deleted item. completion is however guaranteed for all
198 * reads starting later.
200 struct atomlist_item
*atomlist_pop(struct atomlist_head
*h
);
204 struct atomsort_item
{
205 _Atomic atomptr_t next
;
207 #define atomsort_itemp(val) ((struct atomsort_item *)atomptr_p(val))
209 struct atomsort_head
{
210 _Atomic atomptr_t first
;
211 _Atomic
size_t count
;
214 #define _PREDECL_ATOMSORT(prefix) \
215 struct prefix ## _head { struct atomsort_head ah; }; \
216 struct prefix ## _item { struct atomsort_item ai; };
218 #define INIT_ATOMSORT_UNIQ(var) { }
219 #define INIT_ATOMSORT_NONUNIQ(var) { }
221 #define _DECLARE_ATOMSORT(prefix, type, field, cmpfn_nuq, cmpfn_uq) \
222 macro_inline void prefix ## _init(struct prefix##_head *h) \
224 memset(h, 0, sizeof(*h)); \
226 macro_inline void prefix ## _fini(struct prefix##_head *h) \
228 assert(h->ah.count == 0); \
229 memset(h, 0, sizeof(*h)); \
231 macro_inline type *prefix ## _add(struct prefix##_head *h, type *item) \
233 struct atomsort_item *p; \
234 p = atomsort_add(&h->ah, &item->field.ai, cmpfn_uq); \
235 return container_of_null(p, type, field.ai); \
237 macro_inline type *prefix ## _first(struct prefix##_head *h) \
239 struct atomsort_item *p; \
240 p = atomptr_p(atomic_load_explicit(&h->ah.first, \
241 memory_order_acquire)); \
242 return container_of_null(p, type, field.ai); \
244 macro_inline type *prefix ## _next(struct prefix##_head *h, type *item) \
246 struct atomsort_item *p; \
247 p = atomptr_p(atomic_load_explicit(&item->field.ai.next, \
248 memory_order_acquire)); \
249 return container_of_null(p, type, field.ai); \
251 macro_inline type *prefix ## _next_safe(struct prefix##_head *h, type *item) \
253 return item ? prefix##_next(h, item) : NULL; \
256 macro_inline type *prefix ## _find_gteq(struct prefix##_head *h, \
259 type *p = prefix ## _first(h); \
260 while (p && cmpfn_nuq(&p->field.ai, &item->field.ai) < 0) \
261 p = prefix ## _next(h, p); \
265 macro_inline type *prefix ## _find_lt(struct prefix##_head *h, \
268 type *p = prefix ## _first(h), *prev = NULL; \
269 while (p && cmpfn_nuq(&p->field.ai, &item->field.ai) < 0) \
270 p = prefix ## _next(h, (prev = p)); \
273 macro_inline void prefix ## _del_hint(struct prefix##_head *h, type *item, \
274 _Atomic atomptr_t *hint) \
276 atomsort_del_hint(&h->ah, &item->field.ai, hint); \
278 macro_inline type *prefix ## _del(struct prefix##_head *h, type *item) \
280 atomsort_del_hint(&h->ah, &item->field.ai, NULL); \
281 /* TODO: Return NULL if not found */ \
284 macro_inline size_t prefix ## _count(struct prefix##_head *h) \
286 return atomic_load_explicit(&h->ah.count, memory_order_relaxed); \
288 macro_inline type *prefix ## _pop(struct prefix##_head *h) \
290 struct atomsort_item *p = atomsort_pop(&h->ah); \
291 return p ? container_of(p, type, field.ai) : NULL; \
295 #define PREDECL_ATOMSORT_UNIQ(prefix) \
296 _PREDECL_ATOMSORT(prefix)
297 #define DECLARE_ATOMSORT_UNIQ(prefix, type, field, cmpfn) \
299 macro_inline int prefix ## __cmp(const struct atomsort_item *a, \
300 const struct atomsort_item *b) \
302 return cmpfn(container_of(a, type, field.ai), \
303 container_of(b, type, field.ai)); \
306 _DECLARE_ATOMSORT(prefix, type, field, \
307 prefix ## __cmp, prefix ## __cmp) \
310 macro_inline type *prefix ## _find(struct prefix##_head *h, const type *item) \
312 type *p = prefix ## _first(h); \
314 while (p && (cmpval = cmpfn(p, item)) < 0) \
315 p = prefix ## _next(h, p); \
316 if (!p || cmpval > 0) \
322 #define PREDECL_ATOMSORT_NONUNIQ(prefix) \
323 _PREDECL_ATOMSORT(prefix)
324 #define DECLARE_ATOMSORT_NONUNIQ(prefix, type, field, cmpfn) \
326 macro_inline int prefix ## __cmp(const struct atomsort_item *a, \
327 const struct atomsort_item *b) \
329 return cmpfn(container_of(a, type, field.ai), \
330 container_of(b, type, field.ai)); \
332 macro_inline int prefix ## __cmp_uq(const struct atomsort_item *a, \
333 const struct atomsort_item *b) \
335 int cmpval = cmpfn(container_of(a, type, field.ai), \
336 container_of(b, type, field.ai)); \
346 _DECLARE_ATOMSORT(prefix, type, field, \
347 prefix ## __cmp, prefix ## __cmp_uq) \
350 struct atomsort_item
*atomsort_add(struct atomsort_head
*h
,
351 struct atomsort_item
*item
, int (*cmpfn
)(
352 const struct atomsort_item
*,
353 const struct atomsort_item
*));
355 void atomsort_del_hint(struct atomsort_head
*h
,
356 struct atomsort_item
*item
, _Atomic atomptr_t
*hint
);
358 struct atomsort_item
*atomsort_pop(struct atomsort_head
*h
);
360 #endif /* _FRR_ATOMLIST_H */