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