]> git.proxmox.com Git - mirror_frr.git/blame - lib/seqlock.h
lib/seqlock: add timed-wait operation
[mirror_frr.git] / lib / seqlock.h
CommitLineData
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 */
60typedef _Atomic uint32_t seqlock_ctr_t;
61typedef 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
70struct 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 */
80extern void seqlock_init(struct seqlock *sqlo);
81
82
83/* while (sqlo <= val) - wait until seqlock->pos > val, or seqlock unheld */
84extern void seqlock_wait(struct seqlock *sqlo, seqlock_val_t val);
2a5e6235
DL
85extern bool seqlock_timedwait(struct seqlock *sqlo, seqlock_val_t val,
86 const struct timespec *abs_monotime_limit);
440d5faa
DL
87extern bool seqlock_check(struct seqlock *sqlo, seqlock_val_t val);
88
89static 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 */
95extern seqlock_val_t seqlock_cur(struct seqlock *sqlo);
96/* sqlo++ - note: like x++, returns previous value, before bumping */
97extern seqlock_val_t seqlock_bump(struct seqlock *sqlo);
98
99
100/* sqlo = val - can be used on held seqlock. */
101extern void seqlock_acquire_val(struct seqlock *sqlo, seqlock_val_t val);
102/* sqlo = ref - standard pattern: acquire relative to other seqlock */
103static 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 */
109extern 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 */