]>
git.proxmox.com Git - mirror_frr.git/blob - lib/seqlock.h
1 // SPDX-License-Identifier: LGPL-2.1-or-later
3 * "Sequence" lock primitive
5 * Copyright (C) 2015 David Lamparter <equinox@diac24.net>
14 #include "frratomic.h"
21 * this locking primitive is intended to use in a 1:N setup.
23 * - one "counter" seqlock issuing increasing numbers
24 * - multiple seqlock users hold references on these numbers
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.
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
35 * generally, the lock function is:
40 * | running seqlock_wait(b) -- a <= b
41 * seqlock_release() | blocked
42 * OR: seqlock_acquire(a') | -- a' > b
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.
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)
54 /* NB: SEQLOCK_WAITERS is only allowed if SEQLOCK_HELD is also set; can't
55 * have waiters on an unheld seqlock
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
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
73 /* used when futexes not available: (i.e. non-linux) */
79 /* sqlo = 0 - init state: not held */
80 extern void seqlock_init(struct seqlock
*sqlo
);
83 /* basically: "while (sqlo <= val) wait();"
84 * returns when sqlo > val || !seqlock_held(sqlo)
86 extern void seqlock_wait(struct seqlock
*sqlo
, seqlock_val_t val
);
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
);
92 /* one-shot test, returns true if seqlock_wait would return immediately */
93 extern bool seqlock_check(struct seqlock
*sqlo
, seqlock_val_t val
);
95 static inline bool seqlock_held(struct seqlock
*sqlo
)
97 return !!atomic_load_explicit(&sqlo
->pos
, memory_order_relaxed
);
100 /* sqlo - get seqlock position -- for the "counter" seqlock */
101 extern seqlock_val_t
seqlock_cur(struct seqlock
*sqlo
);
103 /* ++sqlo (but atomic & wakes waiters) - returns value that we bumped to.
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
110 extern seqlock_val_t
seqlock_bump(struct seqlock
*sqlo
);
113 /* sqlo = val - can be used on held seqlock. */
114 extern void seqlock_acquire_val(struct seqlock
*sqlo
, seqlock_val_t val
);
116 /* sqlo = ref - standard pattern: acquire relative to other seqlock */
117 static inline void seqlock_acquire(struct seqlock
*sqlo
, struct seqlock
*ref
)
119 seqlock_acquire_val(sqlo
, seqlock_cur(ref
));
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
132 #endif /* _SEQLOCK_H */