Line | Count | Source |
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 | 16 | #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 | 0 | #define SEQLOCK_HELD (1U << 0) |
58 | 16 | #define SEQLOCK_WAITERS (1U << 1) |
59 | 0 | #define SEQLOCK_VAL(n) ((n) & ~SEQLOCK_WAITERS) |
60 | 16 | #define SEQLOCK_STARTVAL 1U |
61 | 0 | #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 | | static inline bool seqlock_held(struct seqlock *sqlo) |
96 | 0 | { |
97 | 0 | return !!atomic_load_explicit(&sqlo->pos, memory_order_relaxed); |
98 | 0 | } Unexecuted instantiation: frrcu.c:seqlock_held Unexecuted instantiation: seqlock.c:seqlock_held |
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 | | static inline void seqlock_acquire(struct seqlock *sqlo, struct seqlock *ref) |
118 | 0 | { |
119 | 0 | seqlock_acquire_val(sqlo, seqlock_cur(ref)); |
120 | 0 | } Unexecuted instantiation: frrcu.c:seqlock_acquire Unexecuted instantiation: seqlock.c:seqlock_acquire |
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 */ |