lib/atomlist.h

   1 // SPDX-License-Identifier: ISC
   2 /*
   3  * Copyright (c) 2016-2019  David Lamparter, for NetDEF, Inc.
   4  */
   5
   6 #ifndef _FRR_ATOMLIST_H
   7 #define _FRR_ATOMLIST_H
   8
   9 #include "typesafe.h"
  10 #include "frratomic.h"
  11
  12 #ifdef __cplusplus
  13 extern "C" {
  14 #endif
  15
  16 /* pointer with lock/deleted/invalid bit in lowest bit
  17  *
  18  * for atomlist/atomsort, "locked" means "this pointer can't be updated, the
  19  * item is being deleted".  it is permissible to assume the item will indeed
  20  * be deleted (as there are no replace/etc. ops in this).
  21  *
  22  * in general, lowest 2/3 bits on 32/64bit architectures are available for
  23  * uses like this; the only thing that will really break this is putting an
  24  * atomlist_item in a struct with "packed" attribute.  (it'll break
  25  * immediately and consistently.) -- don't do that.
  26  *
  27  * ATOMPTR_USER is currently unused (and available for atomic hash or skiplist
  28  * implementations.)
  29  */
  30
  31 /* atomic_atomptr_t may look a bit odd, it's for the sake of C++ compat */
  32 typedef uintptr_t               atomptr_t;
  33 typedef atomic_uintptr_t        atomic_atomptr_t;
  34
  35 #define ATOMPTR_MASK (UINTPTR_MAX - 3)
  36 #define ATOMPTR_LOCK (1)
  37 #define ATOMPTR_USER (2)
  38 #define ATOMPTR_NULL (0)
  39
  40 static inline atomptr_t atomptr_i(void *val)
  41 {
  42         atomptr_t atomval = (atomptr_t)val;
  43
  44         assert(!(atomval & ATOMPTR_LOCK));
  45         return atomval;
  46 }
  47 static inline void *atomptr_p(atomptr_t val)
  48 {
  49         return (void *)(val & ATOMPTR_MASK);
  50 }
  51 static inline bool atomptr_l(atomptr_t val)
  52 {
  53         return (bool)(val & ATOMPTR_LOCK);
  54 }
  55 static inline bool atomptr_u(atomptr_t val)
  56 {
  57         return (bool)(val & ATOMPTR_USER);
  58 }
  59
  60
  61 /* the problem with, find(), find_gteq() and find_lt() on atomic lists is that
  62  * they're neither an "acquire" nor a "release" operation;  the element that
  63  * was found is still on the list and doesn't change ownership.  Therefore,
  64  * an atomic transition in ownership state can't be implemented.
  65  *
  66  * Contrast this with add() or pop(): both function calls atomically transfer
  67  * ownership of an item to or from the list, which makes them "acquire" /
  68  * "release" operations.
  69  *
  70  * What can be implemented atomically is a "find_pop()", i.e. try to locate an
  71  * item and atomically try to remove it if found.  It's not currently
  72  * implemented but can be added when needed.
  73  *
  74  * Either way - for find(), generally speaking, if you need to use find() on
  75  * a list then the whole thing probably isn't well-suited to atomic
  76  * implementation and you'll need to have extra locks around to make it work
  77  * correctly.
  78  */
  79 #ifdef WNO_ATOMLIST_UNSAFE_FIND
  80 # define atomic_find_warn
  81 #else
  82 # define atomic_find_warn __attribute__((_DEPRECATED( \
  83         "WARNING: find() on atomic lists cannot be atomic by principle; " \
  84         "check code to make sure usage pattern is OK and if it is, use " \
  85         "#define WNO_ATOMLIST_UNSAFE_FIND")))
  86 #endif
  87
  88
  89 /* single-linked list, unsorted/arbitrary.
  90  * can be used as queue with add_tail / pop
  91  *
  92  * all operations are lock-free, but not necessarily wait-free.  this means
  93  * that there is no state where the system as a whole stops making process,
  94  * but it *is* possible that a *particular* thread is delayed by some time.
  95  *
  96  * the only way for this to happen is for other threads to continuously make
  97  * updates.  an inactive / blocked / deadlocked other thread cannot cause such
  98  * delays, and to cause such delays a thread must be heavily hitting the list -
  99  * it's a rather theoretical concern.
 100  */
 101
 102 /* don't use these structs directly */
 103 struct atomlist_item {
 104         atomic_uintptr_t next;
 105 };
 106 #define atomlist_itemp(val) ((struct atomlist_item *)atomptr_p(val))
 107
 108 struct atomlist_head {
 109         atomic_uintptr_t first, last;
 110         atomic_size_t count;
 111 };
 112
 113 /* use as:
 114  *
 115  * PREDECL_ATOMLIST(namelist);
 116  * struct name {
 117  *   struct namelist_item nlitem;
 118  * }
 119  * DECLARE_ATOMLIST(namelist, struct name, nlitem);
 120  */
 121 #define PREDECL_ATOMLIST(prefix)                                               \
 122 struct prefix ## _head { struct atomlist_head ah; };                           \
 123 struct prefix ## _item { struct atomlist_item ai; };                           \
 124 MACRO_REQUIRE_SEMICOLON() /* end */
 125
 126 #define INIT_ATOMLIST(var) { }
 127
 128 #define DECLARE_ATOMLIST(prefix, type, field)                                  \
 129 macro_inline void prefix ## _add_head(struct prefix##_head *h, type *item)     \
 130 {       atomlist_add_head(&h->ah, &item->field.ai); }                          \
 131 macro_inline void prefix ## _add_tail(struct prefix##_head *h, type *item)     \
 132 {       atomlist_add_tail(&h->ah, &item->field.ai); }                          \
 133 macro_inline void prefix ## _del_hint(struct prefix##_head *h, type *item,     \
 134                 atomic_atomptr_t *hint)                                        \
 135 {       atomlist_del_hint(&h->ah, &item->field.ai, hint); }                    \
 136 macro_inline type *prefix ## _del(struct prefix##_head *h, type *item)         \
 137 {       atomlist_del_hint(&h->ah, &item->field.ai, NULL);                      \
 138         /* TODO: Return NULL if not found */                                   \
 139         return item; }                                                         \
 140 macro_inline type *prefix ## _pop(struct prefix##_head *h)                     \
 141 {       char *p = (char *)atomlist_pop(&h->ah);                                \
 142         return p ? (type *)(p - offsetof(type, field)) : NULL; }               \
 143 macro_inline type *prefix ## _first(struct prefix##_head *h)                   \
 144 {       char *p = atomptr_p(atomic_load_explicit(&h->ah.first,                 \
 145                                 memory_order_acquire));                        \
 146         return p ? (type *)(p - offsetof(type, field)) : NULL; }               \
 147 macro_inline type *prefix ## _next(struct prefix##_head *h, type *item)        \
 148 {       char *p = atomptr_p(atomic_load_explicit(&item->field.ai.next,         \
 149                                 memory_order_acquire));                        \
 150         return p ? (type *)(p - offsetof(type, field)) : NULL; }               \
 151 macro_inline type *prefix ## _next_safe(struct prefix##_head *h, type *item)   \
 152 {       return item ? prefix##_next(h, item) : NULL; }                         \
 153 macro_inline size_t prefix ## _count(struct prefix##_head *h)                  \
 154 {       return atomic_load_explicit(&h->ah.count, memory_order_relaxed); }     \
 155 macro_inline void prefix ## _init(struct prefix##_head *h)                     \
 156 {                                                                              \
 157         memset(h, 0, sizeof(*h));                                              \
 158 }                                                                              \
 159 macro_inline void prefix ## _fini(struct prefix##_head *h)                     \
 160 {                                                                              \
 161         assert(prefix ## _count(h) == 0);                                      \
 162         memset(h, 0, sizeof(*h));                                              \
 163 }                                                                              \
 164 MACRO_REQUIRE_SEMICOLON() /* end */
 165
 166 /* add_head:
 167  * - contention on ->first pointer
 168  * - return implies completion
 169  */
 170 void atomlist_add_head(struct atomlist_head *h, struct atomlist_item *item);
 171
 172 /* add_tail:
 173  * - concurrent add_tail can cause wait but has progress guarantee
 174  * - return does NOT imply completion.  completion is only guaranteed after
 175  *   all other add_tail operations that started before this add_tail have
 176  *   completed as well.
 177  */
 178 void atomlist_add_tail(struct atomlist_head *h, struct atomlist_item *item);
 179
 180 /* del/del_hint:
 181  *
 182  * OWNER MUST HOLD REFERENCE ON ITEM TO BE DELETED, ENSURING NO OTHER THREAD
 183  * WILL TRY TO DELETE THE SAME ITEM.  DELETING INCLUDES pop().
 184  *
 185  * as with all deletions, threads that started reading earlier may still hold
 186  * pointers to the deleted item.  completion is however guaranteed for all
 187  * reads starting later.
 188  */
 189 void atomlist_del_hint(struct atomlist_head *h, struct atomlist_item *item,
 190                 atomic_atomptr_t *hint);
 191
 192 /* pop:
 193  *
 194  * as with all deletions, threads that started reading earlier may still hold
 195  * pointers to the deleted item.  completion is however guaranteed for all
 196  * reads starting later.
 197  */
 198 struct atomlist_item *atomlist_pop(struct atomlist_head *h);
 199
 200
 201
 202 struct atomsort_item {
 203         atomic_atomptr_t next;
 204 };
 205 #define atomsort_itemp(val) ((struct atomsort_item *)atomptr_p(val))
 206
 207 struct atomsort_head {
 208         atomic_atomptr_t first;
 209         atomic_size_t count;
 210 };
 211
 212 #define _PREDECL_ATOMSORT(prefix)                                              \
 213 struct prefix ## _head { struct atomsort_head ah; };                           \
 214 struct prefix ## _item { struct atomsort_item ai; };                           \
 215 MACRO_REQUIRE_SEMICOLON() /* end */
 216
 217 #define INIT_ATOMSORT_UNIQ(var)         { }
 218 #define INIT_ATOMSORT_NONUNIQ(var)      { }
 219
 220 #define _DECLARE_ATOMSORT(prefix, type, field, cmpfn_nuq, cmpfn_uq)            \
 221 macro_inline void prefix ## _init(struct prefix##_head *h)                     \
 222 {                                                                              \
 223         memset(h, 0, sizeof(*h));                                              \
 224 }                                                                              \
 225 macro_inline void prefix ## _fini(struct prefix##_head *h)                     \
 226 {                                                                              \
 227         assert(h->ah.count == 0);                                              \
 228         memset(h, 0, sizeof(*h));                                              \
 229 }                                                                              \
 230 macro_inline type *prefix ## _add(struct prefix##_head *h, type *item)         \
 231 {                                                                              \
 232         struct atomsort_item *p;                                               \
 233         p = atomsort_add(&h->ah, &item->field.ai, cmpfn_uq);                   \
 234         return container_of_null(p, type, field.ai);                           \
 235 }                                                                              \
 236 macro_inline type *prefix ## _first(struct prefix##_head *h)                   \
 237 {                                                                              \
 238         struct atomsort_item *p;                                               \
 239         p = atomptr_p(atomic_load_explicit(&h->ah.first,                       \
 240                                 memory_order_acquire));                        \
 241         return container_of_null(p, type, field.ai);                           \
 242 }                                                                              \
 243 macro_inline type *prefix ## _next(struct prefix##_head *h, type *item)        \
 244 {                                                                              \
 245         struct atomsort_item *p;                                               \
 246         p = atomptr_p(atomic_load_explicit(&item->field.ai.next,               \
 247                                 memory_order_acquire));                        \
 248         return container_of_null(p, type, field.ai);                           \
 249 }                                                                              \
 250 macro_inline type *prefix ## _next_safe(struct prefix##_head *h, type *item)   \
 251 {                                                                              \
 252         return item ? prefix##_next(h, item) : NULL;                           \
 253 }                                                                              \
 254 atomic_find_warn                                                               \
 255 macro_inline type *prefix ## _find_gteq(struct prefix##_head *h,               \
 256                 const type *item)                                              \
 257 {                                                                              \
 258         type *p = prefix ## _first(h);                                         \
 259         while (p && cmpfn_nuq(&p->field.ai, &item->field.ai) < 0)              \
 260                 p = prefix ## _next(h, p);                                     \
 261         return p;                                                              \
 262 }                                                                              \
 263 atomic_find_warn                                                               \
 264 macro_inline type *prefix ## _find_lt(struct prefix##_head *h,                 \
 265                 const type *item)                                              \
 266 {                                                                              \
 267         type *p = prefix ## _first(h), *prev = NULL;                           \
 268         while (p && cmpfn_nuq(&p->field.ai, &item->field.ai) < 0)              \
 269                 p = prefix ## _next(h, (prev = p));                            \
 270         return prev;                                                           \
 271 }                                                                              \
 272 macro_inline void prefix ## _del_hint(struct prefix##_head *h, type *item,     \
 273                 atomic_atomptr_t *hint)                                        \
 274 {                                                                              \
 275         atomsort_del_hint(&h->ah, &item->field.ai, hint);                      \
 276 }                                                                              \
 277 macro_inline type *prefix ## _del(struct prefix##_head *h, type *item)         \
 278 {                                                                              \
 279         atomsort_del_hint(&h->ah, &item->field.ai, NULL);                      \
 280         /* TODO: Return NULL if not found */                                   \
 281         return item;                                                           \
 282 }                                                                              \
 283 macro_inline size_t prefix ## _count(struct prefix##_head *h)                  \
 284 {                                                                              \
 285         return atomic_load_explicit(&h->ah.count, memory_order_relaxed);       \
 286 }                                                                              \
 287 macro_inline type *prefix ## _pop(struct prefix##_head *h)                     \
 288 {                                                                              \
 289         struct atomsort_item *p = atomsort_pop(&h->ah);                        \
 290         return p ? container_of(p, type, field.ai) : NULL;                     \
 291 }                                                                              \
 292 MACRO_REQUIRE_SEMICOLON() /* end */
 293
 294 #define PREDECL_ATOMSORT_UNIQ(prefix)                                          \
 295         _PREDECL_ATOMSORT(prefix)
 296 #define DECLARE_ATOMSORT_UNIQ(prefix, type, field, cmpfn)                      \
 297                                                                                \
 298 macro_inline int prefix ## __cmp(const struct atomsort_item *a,                \
 299                 const struct atomsort_item *b)                                 \
 300 {                                                                              \
 301         return cmpfn(container_of(a, type, field.ai),                          \
 302                         container_of(b, type, field.ai));                      \
 303 }                                                                              \
 304                                                                                \
 305 _DECLARE_ATOMSORT(prefix, type, field,                                         \
 306                 prefix ## __cmp, prefix ## __cmp);                             \
 307                                                                                \
 308 atomic_find_warn                                                               \
 309 macro_inline type *prefix ## _find(struct prefix##_head *h, const type *item)  \
 310 {                                                                              \
 311         type *p = prefix ## _first(h);                                         \
 312         int cmpval = 0;                                                        \
 313         while (p && (cmpval = cmpfn(p, item)) < 0)                             \
 314                 p = prefix ## _next(h, p);                                     \
 315         if (!p || cmpval > 0)                                                  \
 316                 return NULL;                                                   \
 317         return p;                                                              \
 318 }                                                                              \
 319 MACRO_REQUIRE_SEMICOLON() /* end */
 320
 321 #define PREDECL_ATOMSORT_NONUNIQ(prefix)                                       \
 322         _PREDECL_ATOMSORT(prefix)
 323 #define DECLARE_ATOMSORT_NONUNIQ(prefix, type, field, cmpfn)                   \
 324                                                                                \
 325 macro_inline int prefix ## __cmp(const struct atomsort_item *a,                \
 326                 const struct atomsort_item *b)                                 \
 327 {                                                                              \
 328         return cmpfn(container_of(a, type, field.ai),                          \
 329                         container_of(b, type, field.ai));                      \
 330 }                                                                              \
 331 macro_inline int prefix ## __cmp_uq(const struct atomsort_item *a,             \
 332                 const struct atomsort_item *b)                                 \
 333 {                                                                              \
 334         int cmpval = cmpfn(container_of(a, type, field.ai),                    \
 335                         container_of(b, type, field.ai));                      \
 336         if (cmpval)                                                            \
 337                 return cmpval;                                                 \
 338         if (a < b)                                                             \
 339                 return -1;                                                     \
 340         if (a > b)                                                             \
 341                 return 1;                                                      \
 342         return 0;                                                              \
 343 }                                                                              \
 344                                                                                \
 345 _DECLARE_ATOMSORT(prefix, type, field,                                         \
 346                 prefix ## __cmp, prefix ## __cmp_uq);                          \
 347 MACRO_REQUIRE_SEMICOLON() /* end */
 348
 349 struct atomsort_item *atomsort_add(struct atomsort_head *h,
 350                 struct atomsort_item *item, int (*cmpfn)(
 351                         const struct atomsort_item *,
 352                         const struct atomsort_item *));
 353
 354 void atomsort_del_hint(struct atomsort_head *h,
 355                 struct atomsort_item *item, atomic_atomptr_t *hint);
 356
 357 struct atomsort_item *atomsort_pop(struct atomsort_head *h);
 358
 359 #ifdef __cplusplus
 360 }
 361 #endif
 362
 363 #endif /* _FRR_ATOMLIST_H */