]> git.proxmox.com Git - mirror_frr.git/blob - lib/seqlock.h
Merge pull request #5895 from patrasar/2404618
[mirror_frr.git] / 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 */