]>
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 | |
57 | * be 1 to have a 'cleared' indication (i.e., counts 1,3,5,7,etc. ) | |
58 | */ | |
59 | typedef _Atomic uint32_t seqlock_ctr_t; | |
60 | typedef uint32_t seqlock_val_t; | |
61 | #define seqlock_assert_valid(val) assert(val & 1) | |
62 | ||
63 | ||
64 | struct seqlock { | |
65 | /* always used */ | |
66 | seqlock_ctr_t pos; | |
67 | /* used when futexes not available: (i.e. non-linux) */ | |
68 | pthread_mutex_t lock; | |
69 | pthread_cond_t wake; | |
70 | }; | |
71 | ||
72 | ||
73 | /* sqlo = 0 - init state: not held */ | |
74 | extern void seqlock_init(struct seqlock *sqlo); | |
75 | ||
76 | ||
77 | /* while (sqlo <= val) - wait until seqlock->pos > val, or seqlock unheld */ | |
78 | extern void seqlock_wait(struct seqlock *sqlo, seqlock_val_t val); | |
79 | extern bool seqlock_check(struct seqlock *sqlo, seqlock_val_t val); | |
80 | ||
81 | static inline bool seqlock_held(struct seqlock *sqlo) | |
82 | { | |
83 | return !!atomic_load_explicit(&sqlo->pos, memory_order_relaxed); | |
84 | } | |
85 | ||
86 | /* sqlo - get seqlock position -- for the "counter" seqlock */ | |
87 | extern seqlock_val_t seqlock_cur(struct seqlock *sqlo); | |
88 | /* sqlo++ - note: like x++, returns previous value, before bumping */ | |
89 | extern seqlock_val_t seqlock_bump(struct seqlock *sqlo); | |
90 | ||
91 | ||
92 | /* sqlo = val - can be used on held seqlock. */ | |
93 | extern void seqlock_acquire_val(struct seqlock *sqlo, seqlock_val_t val); | |
94 | /* sqlo = ref - standard pattern: acquire relative to other seqlock */ | |
95 | static inline void seqlock_acquire(struct seqlock *sqlo, struct seqlock *ref) | |
96 | { | |
97 | seqlock_acquire_val(sqlo, seqlock_cur(ref)); | |
98 | } | |
99 | ||
100 | /* sqlo = 0 - set seqlock position to 0, marking as non-held */ | |
101 | extern void seqlock_release(struct seqlock *sqlo); | |
102 | /* release should normally be followed by a bump on the "counter", if | |
103 | * anything other than reading RCU items was done | |
104 | */ | |
105 | ||
106 | #endif /* _SEQLOCK_H */ |