Line data    Source code

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