lib/seqlock.c

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