]>
Commit | Line | Data |
---|---|---|
440d5faa DL |
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 | |
6046b690 DL |
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. | |
440d5faa DL |
59 | */ |
60 | typedef _Atomic uint32_t seqlock_ctr_t; | |
61 | typedef uint32_t seqlock_val_t; | |
6046b690 | 62 | #define seqlock_assert_valid(val) assert((val) & SEQLOCK_HELD) |
440d5faa | 63 | |
6046b690 DL |
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 | |
440d5faa DL |
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); | |
2a5e6235 DL |
85 | extern bool seqlock_timedwait(struct seqlock *sqlo, seqlock_val_t val, |
86 | const struct timespec *abs_monotime_limit); | |
440d5faa DL |
87 | extern bool seqlock_check(struct seqlock *sqlo, seqlock_val_t val); |
88 | ||
89 | static inline bool seqlock_held(struct seqlock *sqlo) | |
90 | { | |
91 | return !!atomic_load_explicit(&sqlo->pos, memory_order_relaxed); | |
92 | } | |
93 | ||
94 | /* sqlo - get seqlock position -- for the "counter" seqlock */ | |
95 | extern seqlock_val_t seqlock_cur(struct seqlock *sqlo); | |
96 | /* sqlo++ - note: like x++, returns previous value, before bumping */ | |
97 | extern seqlock_val_t seqlock_bump(struct seqlock *sqlo); | |
98 | ||
99 | ||
100 | /* sqlo = val - can be used on held seqlock. */ | |
101 | extern void seqlock_acquire_val(struct seqlock *sqlo, seqlock_val_t val); | |
102 | /* sqlo = ref - standard pattern: acquire relative to other seqlock */ | |
103 | static inline void seqlock_acquire(struct seqlock *sqlo, struct seqlock *ref) | |
104 | { | |
105 | seqlock_acquire_val(sqlo, seqlock_cur(ref)); | |
106 | } | |
107 | ||
108 | /* sqlo = 0 - set seqlock position to 0, marking as non-held */ | |
109 | extern void seqlock_release(struct seqlock *sqlo); | |
110 | /* release should normally be followed by a bump on the "counter", if | |
111 | * anything other than reading RCU items was done | |
112 | */ | |
113 | ||
114 | #endif /* _SEQLOCK_H */ |