lib/seqlock.h

   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 #ifndef _SEQLOCK_H
  23 #define _SEQLOCK_H
  24
  25 #include <stdbool.h>
  26 #include <stdint.h>
  27 #include <pthread.h>
  28 #include "frratomic.h"
  29
  30 #ifdef __cplusplus
  31 extern "C" {
  32 #endif
  33
  34 /*
  35  * this locking primitive is intended to use in a 1:N setup.
  36  *
  37  * - one "counter" seqlock issuing increasing numbers
  38  * - multiple seqlock users hold references on these numbers
  39  *
  40  * this is intended for implementing RCU reference-holding.  There is one
  41  * global counter, with threads locking a seqlock whenever they take a
  42  * reference.  A seqlock can also be idle/unlocked.
  43  *
  44  * The "counter" seqlock will always stay locked;  the RCU cleanup thread
  45  * continuously counts it up, waiting for threads to release or progress to a
  46  * sequence number further ahead.  If all threads are > N, references dropped
  47  * in N can be free'd.
  48  *
  49  * generally, the lock function is:
  50  *
  51  * Thread-A                  Thread-B
  52  *
  53  * seqlock_acquire(a)
  54  *    | running              seqlock_wait(b)      -- a <= b
  55  * seqlock_release()            | blocked
  56  * OR: seqlock_acquire(a')      |                 -- a' > b
  57  *                           (resumes)
  58  */
  59
  60 /* use sequentially increasing "ticket numbers".  lowest bit will always
  61  * be 1 to have a 'cleared' indication (i.e., counts 1,5,9,13,etc. )
  62  * 2nd lowest bit is used to indicate we have waiters.
  63  */
  64 typedef _Atomic uint32_t        seqlock_ctr_t;
  65 typedef uint32_t                seqlock_val_t;
  66 #define seqlock_assert_valid(val) assert((val) & SEQLOCK_HELD)
  67
  68 /* NB: SEQLOCK_WAITERS is only allowed if SEQLOCK_HELD is also set; can't
  69  * have waiters on an unheld seqlock
  70  */
  71 #define SEQLOCK_HELD            (1U << 0)
  72 #define SEQLOCK_WAITERS         (1U << 1)
  73 #define SEQLOCK_VAL(n)          ((n) & ~SEQLOCK_WAITERS)
  74 #define SEQLOCK_STARTVAL        1U
  75 #define SEQLOCK_INCR            4U
  76
  77 /* TODO: originally, this was using "atomic_fetch_add", which is the reason
  78  * bit 0 is used to indicate held state.  With SEQLOCK_WAITERS added, there's
  79  * no fetch_add anymore (cmpxchg loop instead), so we don't need to use bit 0
  80  * for this anymore & can just special-case the value 0 for it and skip it in
  81  * counting.
  82  */
  83
  84 struct seqlock {
  85 /* always used */
  86         seqlock_ctr_t pos;
  87 /* used when futexes not available: (i.e. non-linux) */
  88         pthread_mutex_t lock;
  89         pthread_cond_t  wake;
  90 };
  91
  92
  93 /* sqlo = 0 - init state: not held */
  94 extern void seqlock_init(struct seqlock *sqlo);
  95
  96
  97 /* basically: "while (sqlo <= val) wait();"
  98  * returns when sqlo > val || !seqlock_held(sqlo)
  99  */
 100 extern void seqlock_wait(struct seqlock *sqlo, seqlock_val_t val);
 101
 102 /* same, but time-limited (limit is an absolute CLOCK_MONOTONIC value) */
 103 extern bool seqlock_timedwait(struct seqlock *sqlo, seqlock_val_t val,
 104                               const struct timespec *abs_monotime_limit);
 105
 106 /* one-shot test, returns true if seqlock_wait would return immediately */
 107 extern bool seqlock_check(struct seqlock *sqlo, seqlock_val_t val);
 108
 109 static inline bool seqlock_held(struct seqlock *sqlo)
 110 {
 111         return !!atomic_load_explicit(&sqlo->pos, memory_order_relaxed);
 112 }
 113
 114 /* sqlo - get seqlock position -- for the "counter" seqlock */
 115 extern seqlock_val_t seqlock_cur(struct seqlock *sqlo);
 116
 117 /* ++sqlo (but atomic & wakes waiters) - returns value that we bumped to.
 118  *
 119  * guarantees:
 120  *  - each seqlock_bump call bumps the position by exactly one SEQLOCK_INCR.
 121  *    There are no skipped/missed or multiple increments.
 122  *  - each return value is only returned from one seqlock_bump() call
 123  */
 124 extern seqlock_val_t seqlock_bump(struct seqlock *sqlo);
 125
 126
 127 /* sqlo = val - can be used on held seqlock. */
 128 extern void seqlock_acquire_val(struct seqlock *sqlo, seqlock_val_t val);
 129
 130 /* sqlo = ref - standard pattern: acquire relative to other seqlock */
 131 static inline void seqlock_acquire(struct seqlock *sqlo, struct seqlock *ref)
 132 {
 133         seqlock_acquire_val(sqlo, seqlock_cur(ref));
 134 }
 135
 136 /* sqlo = 0 - set seqlock position to 0, marking as non-held */
 137 extern void seqlock_release(struct seqlock *sqlo);
 138 /* release should normally be followed by a bump on the "counter", if
 139  * anything other than reading RCU items was done
 140  */
 141
 142 #ifdef __cplusplus
 143 }
 144 #endif
 145
 146 #endif /* _SEQLOCK_H */