lib/atomlist.h

   1 /*
   2  * Copyright (c) 2016-2019  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 #ifndef _FRR_ATOMLIST_H
  18 #define _FRR_ATOMLIST_H
  19
  20 #include "typesafe.h"
  21 #include "frratomic.h"
  22
  23 /* pointer with lock/deleted/invalid bit in lowest bit
  24  *
  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).
  28  *
  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.
  33  *
  34  * ATOMPTR_USER is currently unused (and available for atomic hash or skiplist
  35  * implementations.)
  36  */
  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)
  42
  43 static inline atomptr_t atomptr_i(void *val)
  44 {
  45         atomptr_t atomval = (atomptr_t)val;
  46
  47         assert(!(atomval & ATOMPTR_LOCK));
  48         return atomval;
  49 }
  50 static inline void *atomptr_p(atomptr_t val)
  51 {
  52         return (void *)(val & ATOMPTR_MASK);
  53 }
  54 static inline bool atomptr_l(atomptr_t val)
  55 {
  56         return (bool)(val & ATOMPTR_LOCK);
  57 }
  58 static inline bool atomptr_u(atomptr_t val)
  59 {
  60         return (bool)(val & ATOMPTR_USER);
  61 }
  62
  63
  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.
  68  *
  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.
  72  *
  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.
  76  *
  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
  80  * correctly.
  81  */
  82 #ifdef WNO_ATOMLIST_UNSAFE_FIND
  83 # define atomic_find_warn
  84 #else
  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")))
  89 #endif
  90
  91
  92 /* single-linked list, unsorted/arbitrary.
  93  * can be used as queue with add_tail / pop
  94  *
  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.
  98  *
  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.
 103  */
 104
 105 /* don't use these structs directly */
 106 struct atomlist_item {
 107         _Atomic atomptr_t next;
 108 };
 109 #define atomlist_itemp(val) ((struct atomlist_item *)atomptr_p(val))
 110
 111 struct atomlist_head {
 112         _Atomic atomptr_t first, last;
 113         _Atomic size_t count;
 114 };
 115
 116 /* use as:
 117  *
 118  * PREDECL_ATOMLIST(namelist)
 119  * struct name {
 120  *   struct namelist_item nlitem;
 121  * }
 122  * DECLARE_ATOMLIST(namelist, struct name, nlitem)
 123  */
 124 #define PREDECL_ATOMLIST(prefix)                                               \
 125 struct prefix ## _head { struct atomlist_head ah; };                           \
 126 struct prefix ## _item { struct atomlist_item ai; };
 127
 128 #define INIT_ATOMLIST(var) { }
 129
 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 void prefix ## _del(struct prefix##_head *h, type *item)          \
 139 {       atomlist_del_hint(&h->ah, &item->field.ai, NULL); }                    \
 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 /* ... */
 156
 157 /* add_head:
 158  * - contention on ->first pointer
 159  * - return implies completion
 160  */
 161 void atomlist_add_head(struct atomlist_head *h, struct atomlist_item *item);
 162
 163 /* add_tail:
 164  * - concurrent add_tail can cause wait but has progress guarantee
 165  * - return does NOT imply completion.  completion is only guaranteed after
 166  *   all other add_tail operations that started before this add_tail have
 167  *   completed as well.
 168  */
 169 void atomlist_add_tail(struct atomlist_head *h, struct atomlist_item *item);
 170
 171 /* del/del_hint:
 172  *
 173  * OWNER MUST HOLD REFERENCE ON ITEM TO BE DELETED, ENSURING NO OTHER THREAD
 174  * WILL TRY TO DELETE THE SAME ITEM.  DELETING INCLUDES pop().
 175  *
 176  * as with all deletions, threads that started reading earlier may still hold
 177  * pointers to the deleted item.  completion is however guaranteed for all
 178  * reads starting later.
 179  */
 180 void atomlist_del_hint(struct atomlist_head *h, struct atomlist_item *item,
 181                 _Atomic atomptr_t *hint);
 182
 183 /* 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 struct atomlist_item *atomlist_pop(struct atomlist_head *h);
 190
 191
 192
 193 struct atomsort_item {
 194         _Atomic atomptr_t next;
 195 };
 196 #define atomsort_itemp(val) ((struct atomsort_item *)atomptr_p(val))
 197
 198 struct atomsort_head {
 199         _Atomic atomptr_t first;
 200         _Atomic size_t count;
 201 };
 202
 203 #define _PREDECL_ATOMSORT(prefix)                                              \
 204 struct prefix ## _head { struct atomsort_head ah; };                           \
 205 struct prefix ## _item { struct atomsort_item ai; };
 206
 207 #define INIT_ATOMSORT_UNIQ(var)         { }
 208 #define INIT_ATOMSORT_NONUNIQ(var)      { }
 209
 210 #define _DECLARE_ATOMSORT(prefix, type, field, cmpfn_nuq, cmpfn_uq)            \
 211 macro_inline void prefix ## _init(struct prefix##_head *h)                     \
 212 {                                                                              \
 213         memset(h, 0, sizeof(*h));                                              \
 214 }                                                                              \
 215 macro_inline void prefix ## _fini(struct prefix##_head *h)                     \
 216 {                                                                              \
 217         assert(h->ah.count == 0);                                              \
 218         memset(h, 0, sizeof(*h));                                              \
 219 }                                                                              \
 220 macro_inline type *prefix ## _add(struct prefix##_head *h, type *item)         \
 221 {                                                                              \
 222         struct atomsort_item *p;                                               \
 223         p = atomsort_add(&h->ah, &item->field.ai, cmpfn_uq);                   \
 224         return container_of_null(p, type, field.ai);                           \
 225 }                                                                              \
 226 macro_inline type *prefix ## _first(struct prefix##_head *h)                   \
 227 {                                                                              \
 228         struct atomsort_item *p;                                               \
 229         p = atomptr_p(atomic_load_explicit(&h->ah.first,                       \
 230                                 memory_order_acquire));                        \
 231         return container_of_null(p, type, field.ai);                           \
 232 }                                                                              \
 233 macro_inline type *prefix ## _next(struct prefix##_head *h, type *item)        \
 234 {                                                                              \
 235         struct atomsort_item *p;                                               \
 236         p = atomptr_p(atomic_load_explicit(&item->field.ai.next,               \
 237                                 memory_order_acquire));                        \
 238         return container_of_null(p, type, field.ai);                           \
 239 }                                                                              \
 240 macro_inline type *prefix ## _next_safe(struct prefix##_head *h, type *item)   \
 241 {                                                                              \
 242         return item ? prefix##_next(h, item) : NULL;                           \
 243 }                                                                              \
 244 atomic_find_warn                                                               \
 245 macro_inline type *prefix ## _find_gteq(struct prefix##_head *h,               \
 246                 const type *item)                                              \
 247 {                                                                              \
 248         type *p = prefix ## _first(h);                                         \
 249         while (p && cmpfn_nuq(&p->field.ai, &item->field.ai) < 0)              \
 250                 p = prefix ## _next(h, p);                                     \
 251         return p;                                                              \
 252 }                                                                              \
 253 atomic_find_warn                                                               \
 254 macro_inline type *prefix ## _find_lt(struct prefix##_head *h,                 \
 255                 const type *item)                                              \
 256 {                                                                              \
 257         type *p = prefix ## _first(h), *prev = NULL;                           \
 258         while (p && cmpfn_nuq(&p->field.ai, &item->field.ai) < 0)              \
 259                 p = prefix ## _next(h, (prev = p));                            \
 260         return prev;                                                           \
 261 }                                                                              \
 262 macro_inline void prefix ## _del_hint(struct prefix##_head *h, type *item,     \
 263                 _Atomic atomptr_t *hint)                                       \
 264 {                                                                              \
 265         atomsort_del_hint(&h->ah, &item->field.ai, hint);                      \
 266 }                                                                              \
 267 macro_inline void prefix ## _del(struct prefix##_head *h, type *item)          \
 268 {                                                                              \
 269         atomsort_del_hint(&h->ah, &item->field.ai, NULL);                      \
 270 }                                                                              \
 271 macro_inline size_t prefix ## _count(struct prefix##_head *h)                  \
 272 {                                                                              \
 273         return atomic_load_explicit(&h->ah.count, memory_order_relaxed);       \
 274 }                                                                              \
 275 macro_inline type *prefix ## _pop(struct prefix##_head *h)                     \
 276 {                                                                              \
 277         struct atomsort_item *p = atomsort_pop(&h->ah);                        \
 278         return p ? container_of(p, type, field.ai) : NULL;                     \
 279 }                                                                              \
 280 /* ... */
 281
 282 #define PREDECL_ATOMSORT_UNIQ(prefix)                                          \
 283         _PREDECL_ATOMSORT(prefix)
 284 #define DECLARE_ATOMSORT_UNIQ(prefix, type, field, cmpfn)                      \
 285                                                                                \
 286 macro_inline int prefix ## __cmp(const struct atomsort_item *a,                \
 287                 const struct atomsort_item *b)                                 \
 288 {                                                                              \
 289         return cmpfn(container_of(a, type, field.ai),                          \
 290                         container_of(b, type, field.ai));                      \
 291 }                                                                              \
 292                                                                                \
 293 _DECLARE_ATOMSORT(prefix, type, field,                                         \
 294                 prefix ## __cmp, prefix ## __cmp)                              \
 295                                                                                \
 296 atomic_find_warn                                                               \
 297 macro_inline type *prefix ## _find(struct prefix##_head *h, const type *item)  \
 298 {                                                                              \
 299         type *p = prefix ## _first(h);                                         \
 300         int cmpval = 0;                                                        \
 301         while (p && (cmpval = cmpfn(p, item)) < 0)                             \
 302                 p = prefix ## _next(h, p);                                     \
 303         if (!p || cmpval > 0)                                                  \
 304                 return NULL;                                                   \
 305         return p;                                                              \
 306 }                                                                              \
 307 /* ... */
 308
 309 #define PREDECL_ATOMSORT_NONUNIQ(prefix)                                       \
 310         _PREDECL_ATOMSORT(prefix)
 311 #define DECLARE_ATOMSORT_NONUNIQ(prefix, type, field, cmpfn)                   \
 312                                                                                \
 313 macro_inline int prefix ## __cmp(const struct atomsort_item *a,                \
 314                 const struct atomsort_item *b)                                 \
 315 {                                                                              \
 316         return cmpfn(container_of(a, type, field.ai),                          \
 317                         container_of(b, type, field.ai));                      \
 318 }                                                                              \
 319 macro_inline int prefix ## __cmp_uq(const struct atomsort_item *a,             \
 320                 const struct atomsort_item *b)                                 \
 321 {                                                                              \
 322         int cmpval = cmpfn(container_of(a, type, field.ai),                    \
 323                         container_of(b, type, field.ai));                      \
 324         if (cmpval)                                                            \
 325                 return cmpval;                                                 \
 326         if (a < b)                                                             \
 327                 return -1;                                                     \
 328         if (a > b)                                                             \
 329                 return 1;                                                      \
 330         return 0;                                                              \
 331 }                                                                              \
 332                                                                                \
 333 _DECLARE_ATOMSORT(prefix, type, field,                                         \
 334                 prefix ## __cmp, prefix ## __cmp_uq)                           \
 335 /* ... */
 336
 337 struct atomsort_item *atomsort_add(struct atomsort_head *h,
 338                 struct atomsort_item *item, int (*cmpfn)(
 339                         const struct atomsort_item *,
 340                         const struct atomsort_item *));
 341
 342 void atomsort_del_hint(struct atomsort_head *h,
 343                 struct atomsort_item *item, _Atomic atomptr_t *hint);
 344
 345 struct atomsort_item *atomsort_pop(struct atomsort_head *h);
 346
 347 #endif /* _FRR_ATOMLIST_H */