lib/seqlock.c

   1 // SPDX-License-Identifier: LGPL-2.1-or-later
   2 /*
   3  * "Sequence" lock primitive
   4  *
   5  * Copyright (C) 2015  David Lamparter <equinox@diac24.net>
   6  */
   7
   8 #define _GNU_SOURCE
   9
  10 #ifdef HAVE_CONFIG_H
  11 #include "config.h"
  12 #endif
  13
  14 #include <string.h>
  15 #include <unistd.h>
  16 #include <limits.h>
  17 #include <errno.h>
  18 #include <sys/types.h>
  19 #include <sys/time.h>
  20 #include <pthread.h>
  21 #include <assert.h>
  22
  23 #include "seqlock.h"
  24
  25 /****************************************
  26  * OS specific synchronization wrappers *
  27  ****************************************/
  28
  29 /*
  30  * Linux: sys_futex()
  31  */
  32 #ifdef HAVE_SYNC_LINUX_FUTEX
  33 #include <sys/syscall.h>
  34 #include <linux/futex.h>
  35
  36 static long sys_futex(void *addr1, int op, int val1,
  37                       const struct timespec *timeout, void *addr2, int val3)
  38 {
  39         return syscall(SYS_futex, addr1, op, val1, timeout, addr2, val3);
  40 }
  41
  42 #define wait_once(sqlo, val)    \
  43         sys_futex((int *)&sqlo->pos, FUTEX_WAIT, (int)val, NULL, NULL, 0)
  44 #define wait_time(sqlo, val, time, reltime)     \
  45         sys_futex((int *)&sqlo->pos, FUTEX_WAIT_BITSET, (int)val, time, \
  46                   NULL, ~0U)
  47 #define wait_poke(sqlo)         \
  48         sys_futex((int *)&sqlo->pos, FUTEX_WAKE, INT_MAX, NULL, NULL, 0)
  49
  50 /*
  51  * OpenBSD: sys_futex(), almost the same as on Linux
  52  */
  53 #elif defined(HAVE_SYNC_OPENBSD_FUTEX)
  54 #include <sys/syscall.h>
  55 #include <sys/futex.h>
  56
  57 #define TIME_RELATIVE           1
  58
  59 #define wait_once(sqlo, val)    \
  60         futex((int *)&sqlo->pos, FUTEX_WAIT, (int)val, NULL, NULL, 0)
  61 #define wait_time(sqlo, val, time, reltime)     \
  62         futex((int *)&sqlo->pos, FUTEX_WAIT, (int)val, reltime, NULL, 0)
  63 #define wait_poke(sqlo)         \
  64         futex((int *)&sqlo->pos, FUTEX_WAKE, INT_MAX, NULL, NULL, 0)
  65
  66 /*
  67  * FreeBSD: _umtx_op()
  68  */
  69 #elif defined(HAVE_SYNC_UMTX_OP)
  70 #include <sys/umtx.h>
  71
  72 #define wait_once(sqlo, val)    \
  73         _umtx_op((void *)&sqlo->pos, UMTX_OP_WAIT_UINT, val, NULL, NULL)
  74 static int wait_time(struct seqlock *sqlo, uint32_t val,
  75                       const struct timespec *abstime,
  76                       const struct timespec *reltime)
  77 {
  78         struct _umtx_time t;
  79         t._flags = UMTX_ABSTIME;
  80         t._clockid = CLOCK_MONOTONIC;
  81         memcpy(&t._timeout, abstime, sizeof(t._timeout));
  82         return _umtx_op((void *)&sqlo->pos, UMTX_OP_WAIT_UINT, val,
  83                  (void *)(uintptr_t) sizeof(t), &t);
  84 }
  85 #define wait_poke(sqlo)         \
  86         _umtx_op((void *)&sqlo->pos, UMTX_OP_WAKE, INT_MAX, NULL, NULL)
  87
  88 /*
  89  * generic version.  used on NetBSD, Solaris and OSX.  really shitty.
  90  */
  91 #else
  92
  93 #define TIME_ABS_REALTIME       1
  94
  95 #define wait_init(sqlo)         do { \
  96                 pthread_mutex_init(&sqlo->lock, NULL); \
  97                 pthread_cond_init(&sqlo->wake, NULL); \
  98         } while (0)
  99 #define wait_prep(sqlo)         pthread_mutex_lock(&sqlo->lock)
 100 #define wait_once(sqlo, val)    pthread_cond_wait(&sqlo->wake, &sqlo->lock)
 101 #define wait_time(sqlo, val, time, reltime) \
 102                                 pthread_cond_timedwait(&sqlo->wake, \
 103                                                        &sqlo->lock, time);
 104 #define wait_done(sqlo)         pthread_mutex_unlock(&sqlo->lock)
 105 #define wait_poke(sqlo)         do { \
 106                 pthread_mutex_lock(&sqlo->lock); \
 107                 pthread_cond_broadcast(&sqlo->wake); \
 108                 pthread_mutex_unlock(&sqlo->lock); \
 109         } while (0)
 110
 111 #endif
 112
 113 #ifndef wait_init
 114 #define wait_init(sqlo)         /**/
 115 #define wait_prep(sqlo)         /**/
 116 #define wait_done(sqlo)         /**/
 117 #endif /* wait_init */
 118
 119
 120 void seqlock_wait(struct seqlock *sqlo, seqlock_val_t val)
 121 {
 122         seqlock_val_t cur, cal;
 123
 124         seqlock_assert_valid(val);
 125
 126         wait_prep(sqlo);
 127         cur = atomic_load_explicit(&sqlo->pos, memory_order_relaxed);
 128
 129         while (cur & SEQLOCK_HELD) {
 130                 cal = SEQLOCK_VAL(cur) - val - 1;
 131                 assert(cal < 0x40000000 || cal > 0xc0000000);
 132                 if (cal < 0x80000000)
 133                         break;
 134
 135                 if ((cur & SEQLOCK_WAITERS)
 136                     || atomic_compare_exchange_weak_explicit(
 137                                 &sqlo->pos, &cur, cur | SEQLOCK_WAITERS,
 138                                 memory_order_relaxed, memory_order_relaxed)) {
 139                         wait_once(sqlo, cur | SEQLOCK_WAITERS);
 140                         cur = atomic_load_explicit(&sqlo->pos,
 141                                 memory_order_relaxed);
 142                 }
 143                 /* else: we failed to swap in cur because it just changed */
 144         }
 145         wait_done(sqlo);
 146 }
 147
 148 bool seqlock_timedwait(struct seqlock *sqlo, seqlock_val_t val,
 149                        const struct timespec *abs_monotime_limit)
 150 {
 151 /*
 152  * ABS_REALTIME - used on NetBSD, Solaris and OSX
 153  */
 154 #ifdef TIME_ABS_REALTIME
 155 #define time_arg1 &abs_rt
 156 #define time_arg2 NULL
 157 #define time_prep
 158         struct timespec curmono, abs_rt;
 159
 160         clock_gettime(CLOCK_MONOTONIC, &curmono);
 161         clock_gettime(CLOCK_REALTIME, &abs_rt);
 162
 163         abs_rt.tv_nsec += abs_monotime_limit->tv_nsec - curmono.tv_nsec;
 164         if (abs_rt.tv_nsec < 0) {
 165                 abs_rt.tv_sec--;
 166                 abs_rt.tv_nsec += 1000000000;
 167         } else if (abs_rt.tv_nsec >= 1000000000) {
 168                 abs_rt.tv_sec++;
 169                 abs_rt.tv_nsec -= 1000000000;
 170         }
 171         abs_rt.tv_sec += abs_monotime_limit->tv_sec - curmono.tv_sec;
 172
 173 /*
 174  * RELATIVE - used on OpenBSD (might get a patch to get absolute monotime)
 175  */
 176 #elif defined(TIME_RELATIVE)
 177         struct timespec reltime;
 178
 179 #define time_arg1 abs_monotime_limit
 180 #define time_arg2 &reltime
 181 #define time_prep \
 182         clock_gettime(CLOCK_MONOTONIC, &reltime);                              \
 183         reltime.tv_sec = abs_monotime_limit.tv_sec - reltime.tv_sec;           \
 184         reltime.tv_nsec = abs_monotime_limit.tv_nsec - reltime.tv_nsec;        \
 185         if (reltime.tv_nsec < 0) {                                             \
 186                 reltime.tv_sec--;                                              \
 187                 reltime.tv_nsec += 1000000000;                                 \
 188         }
 189 /*
 190  * FreeBSD & Linux: absolute time re. CLOCK_MONOTONIC
 191  */
 192 #else
 193 #define time_arg1 abs_monotime_limit
 194 #define time_arg2 NULL
 195 #define time_prep
 196 #endif
 197
 198         bool ret = true;
 199         seqlock_val_t cur, cal;
 200
 201         seqlock_assert_valid(val);
 202
 203         wait_prep(sqlo);
 204         cur = atomic_load_explicit(&sqlo->pos, memory_order_relaxed);
 205
 206         while (cur & SEQLOCK_HELD) {
 207                 cal = SEQLOCK_VAL(cur) - val - 1;
 208                 assert(cal < 0x40000000 || cal > 0xc0000000);
 209                 if (cal < 0x80000000)
 210                         break;
 211
 212                 if ((cur & SEQLOCK_WAITERS)
 213                     || atomic_compare_exchange_weak_explicit(
 214                                 &sqlo->pos, &cur, cur | SEQLOCK_WAITERS,
 215                                 memory_order_relaxed, memory_order_relaxed)) {
 216                         int rv;
 217
 218                         time_prep
 219
 220                         rv = wait_time(sqlo, cur | SEQLOCK_WAITERS, time_arg1,
 221                                        time_arg2);
 222                         if (rv) {
 223                                 ret = false;
 224                                 break;
 225                         }
 226                         cur = atomic_load_explicit(&sqlo->pos,
 227                                 memory_order_relaxed);
 228                 }
 229         }
 230         wait_done(sqlo);
 231
 232         return ret;
 233 }
 234
 235 bool seqlock_check(struct seqlock *sqlo, seqlock_val_t val)
 236 {
 237         seqlock_val_t cur;
 238
 239         seqlock_assert_valid(val);
 240
 241         cur = atomic_load_explicit(&sqlo->pos, memory_order_relaxed);
 242         if (!(cur & SEQLOCK_HELD))
 243                 return true;
 244         cur = SEQLOCK_VAL(cur) - val - 1;
 245         assert(cur < 0x40000000 || cur > 0xc0000000);
 246         return cur < 0x80000000;
 247 }
 248
 249 void seqlock_acquire_val(struct seqlock *sqlo, seqlock_val_t val)
 250 {
 251         seqlock_val_t prev;
 252
 253         seqlock_assert_valid(val);
 254
 255         prev = atomic_exchange_explicit(&sqlo->pos, val, memory_order_relaxed);
 256         if (prev & SEQLOCK_WAITERS)
 257                 wait_poke(sqlo);
 258 }
 259
 260 void seqlock_release(struct seqlock *sqlo)
 261 {
 262         seqlock_val_t prev;
 263
 264         prev = atomic_exchange_explicit(&sqlo->pos, 0, memory_order_relaxed);
 265         if (prev & SEQLOCK_WAITERS)
 266                 wait_poke(sqlo);
 267 }
 268
 269 void seqlock_init(struct seqlock *sqlo)
 270 {
 271         sqlo->pos = 0;
 272         wait_init(sqlo);
 273 }
 274
 275
 276 seqlock_val_t seqlock_cur(struct seqlock *sqlo)
 277 {
 278         return SEQLOCK_VAL(atomic_load_explicit(&sqlo->pos,
 279                                                 memory_order_relaxed));
 280 }
 281
 282 seqlock_val_t seqlock_bump(struct seqlock *sqlo)
 283 {
 284         seqlock_val_t val, cur;
 285
 286         cur = atomic_load_explicit(&sqlo->pos, memory_order_relaxed);
 287         seqlock_assert_valid(cur);
 288
 289         do {
 290                 val = SEQLOCK_VAL(cur) + SEQLOCK_INCR;
 291         } while (!atomic_compare_exchange_weak_explicit(&sqlo->pos, &cur, val,
 292                         memory_order_relaxed, memory_order_relaxed));
 293
 294         if (cur & SEQLOCK_WAITERS)
 295                 wait_poke(sqlo);
 296         return val;
 297 }