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 #define SEQLOCK_HELD            (1U << 0)
  65 #define SEQLOCK_WAITERS         (1U << 1)
  66 #define SEQLOCK_VAL(n)          ((n) & ~SEQLOCK_WAITERS)
  67 #define SEQLOCK_STARTVAL        1U
  68 #define SEQLOCK_INCR            4U
  69
  70 struct seqlock {
  71 /* always used */
  72         seqlock_ctr_t pos;
  73 /* used when futexes not available: (i.e. non-linux) */
  74         pthread_mutex_t lock;
  75         pthread_cond_t  wake;
  76 };
  77
  78
  79 /* sqlo = 0 - init state: not held */
  80 extern void seqlock_init(struct seqlock *sqlo);
  81
  82
  83 /* while (sqlo <= val) - wait until seqlock->pos > val, or seqlock unheld */
  84 extern void seqlock_wait(struct seqlock *sqlo, seqlock_val_t val);
  85 extern bool seqlock_check(struct seqlock *sqlo, seqlock_val_t val);
  86
  87 static inline bool seqlock_held(struct seqlock *sqlo)
  88 {
  89         return !!atomic_load_explicit(&sqlo->pos, memory_order_relaxed);
  90 }
  91
  92 /* sqlo - get seqlock position -- for the "counter" seqlock */
  93 extern seqlock_val_t seqlock_cur(struct seqlock *sqlo);
  94 /* sqlo++ - note: like x++, returns previous value, before bumping */
  95 extern seqlock_val_t seqlock_bump(struct seqlock *sqlo);
  96
  97
  98 /* sqlo = val - can be used on held seqlock. */
  99 extern void seqlock_acquire_val(struct seqlock *sqlo, seqlock_val_t val);
 100 /* sqlo = ref - standard pattern: acquire relative to other seqlock */
 101 static inline void seqlock_acquire(struct seqlock *sqlo, struct seqlock *ref)
 102 {
 103         seqlock_acquire_val(sqlo, seqlock_cur(ref));
 104 }
 105
 106 /* sqlo = 0 - set seqlock position to 0, marking as non-held */
 107 extern void seqlock_release(struct seqlock *sqlo);
 108 /* release should normally be followed by a bump on the "counter", if
 109  * anything other than reading RCU items was done
 110  */
 111
 112 #endif /* _SEQLOCK_H */