Coverage Report

Created: 2025-08-26 06:20

/src/frr/lib/seqlock.c
Line
Count
Source (jump to first uncovered line)
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
#define _GNU_SOURCE
9
10
#ifdef HAVE_CONFIG_H
11
#include "config.h"
12
#endif
13
14
#include <string.h>
15
#include <unistd.h>
16
#include <limits.h>
17
#include <errno.h>
18
#include <sys/types.h>
19
#include <sys/time.h>
20
#include <pthread.h>
21
#include <assert.h>
22
23
#include "seqlock.h"
24
25
/****************************************
26
 * OS specific synchronization wrappers *
27
 ****************************************/
28
29
/*
30
 * Linux: sys_futex()
31
 */
32
#ifdef HAVE_SYNC_LINUX_FUTEX
33
#include <sys/syscall.h>
34
#include <linux/futex.h>
35
36
static long sys_futex(void *addr1, int op, int val1,
37
          const struct timespec *timeout, void *addr2, int val3)
38
0
{
39
0
  return syscall(SYS_futex, addr1, op, val1, timeout, addr2, val3);
40
0
}
41
42
#define wait_once(sqlo, val)  \
43
0
  sys_futex((int *)&sqlo->pos, FUTEX_WAIT, (int)val, NULL, NULL, 0)
44
#define wait_time(sqlo, val, time, reltime) \
45
0
  sys_futex((int *)&sqlo->pos, FUTEX_WAIT_BITSET, (int)val, time, \
46
0
      NULL, ~0U)
47
#define wait_poke(sqlo)   \
48
0
  sys_futex((int *)&sqlo->pos, FUTEX_WAKE, INT_MAX, NULL, NULL, 0)
49
50
/*
51
 * OpenBSD: sys_futex(), almost the same as on Linux
52
 */
53
#elif defined(HAVE_SYNC_OPENBSD_FUTEX)
54
#include <sys/syscall.h>
55
#include <sys/futex.h>
56
57
#define TIME_RELATIVE   1
58
59
#define wait_once(sqlo, val)  \
60
  futex((int *)&sqlo->pos, FUTEX_WAIT, (int)val, NULL, NULL, 0)
61
#define wait_time(sqlo, val, time, reltime) \
62
  futex((int *)&sqlo->pos, FUTEX_WAIT, (int)val, reltime, NULL, 0)
63
#define wait_poke(sqlo)   \
64
  futex((int *)&sqlo->pos, FUTEX_WAKE, INT_MAX, NULL, NULL, 0)
65
66
/*
67
 * FreeBSD: _umtx_op()
68
 */
69
#elif defined(HAVE_SYNC_UMTX_OP)
70
#include <sys/umtx.h>
71
72
#define wait_once(sqlo, val)  \
73
  _umtx_op((void *)&sqlo->pos, UMTX_OP_WAIT_UINT, val, NULL, NULL)
74
static int wait_time(struct seqlock *sqlo, uint32_t val,
75
          const struct timespec *abstime,
76
          const struct timespec *reltime)
77
{
78
  struct _umtx_time t;
79
  t._flags = UMTX_ABSTIME;
80
  t._clockid = CLOCK_MONOTONIC;
81
  memcpy(&t._timeout, abstime, sizeof(t._timeout));
82
  return _umtx_op((void *)&sqlo->pos, UMTX_OP_WAIT_UINT, val,
83
     (void *)(uintptr_t) sizeof(t), &t);
84
}
85
#define wait_poke(sqlo)   \
86
  _umtx_op((void *)&sqlo->pos, UMTX_OP_WAKE, INT_MAX, NULL, NULL)
87
88
/*
89
 * generic version.  used on NetBSD, Solaris and OSX.  really shitty.
90
 */
91
#else
92
93
#define TIME_ABS_REALTIME 1
94
95
#define wait_init(sqlo)   do { \
96
    pthread_mutex_init(&sqlo->lock, NULL); \
97
    pthread_cond_init(&sqlo->wake, NULL); \
98
  } while (0)
99
#define wait_prep(sqlo)   pthread_mutex_lock(&sqlo->lock)
100
#define wait_once(sqlo, val)  pthread_cond_wait(&sqlo->wake, &sqlo->lock)
101
#define wait_time(sqlo, val, time, reltime) \
102
        pthread_cond_timedwait(&sqlo->wake, \
103
                   &sqlo->lock, time);
104
#define wait_done(sqlo)   pthread_mutex_unlock(&sqlo->lock)
105
#define wait_poke(sqlo)   do { \
106
    pthread_mutex_lock(&sqlo->lock); \
107
    pthread_cond_broadcast(&sqlo->wake); \
108
    pthread_mutex_unlock(&sqlo->lock); \
109
  } while (0)
110
111
#endif
112
113
#ifndef wait_init
114
#define wait_init(sqlo)   /**/
115
#define wait_prep(sqlo)   /**/
116
#define wait_done(sqlo)   /**/
117
#endif /* wait_init */
118
119
120
void seqlock_wait(struct seqlock *sqlo, seqlock_val_t val)
121
0
{
122
0
  seqlock_val_t cur, cal;
123
124
0
  seqlock_assert_valid(val);
125
126
0
  wait_prep(sqlo);
127
0
  cur = atomic_load_explicit(&sqlo->pos, memory_order_relaxed);
128
129
0
  while (cur & SEQLOCK_HELD) {
130
0
    cal = SEQLOCK_VAL(cur) - val - 1;
131
0
    assert(cal < 0x40000000 || cal > 0xc0000000);
132
0
    if (cal < 0x80000000)
133
0
      break;
134
135
0
    if ((cur & SEQLOCK_WAITERS)
136
0
        || atomic_compare_exchange_weak_explicit(
137
0
        &sqlo->pos, &cur, cur | SEQLOCK_WAITERS,
138
0
        memory_order_relaxed, memory_order_relaxed)) {
139
0
      wait_once(sqlo, cur | SEQLOCK_WAITERS);
140
0
      cur = atomic_load_explicit(&sqlo->pos,
141
0
        memory_order_relaxed);
142
0
    }
143
    /* else: we failed to swap in cur because it just changed */
144
0
  }
145
0
  wait_done(sqlo);
146
0
}
147
148
bool seqlock_timedwait(struct seqlock *sqlo, seqlock_val_t val,
149
           const struct timespec *abs_monotime_limit)
150
0
{
151
/*
152
 * ABS_REALTIME - used on NetBSD, Solaris and OSX
153
 */
154
#ifdef TIME_ABS_REALTIME
155
#define time_arg1 &abs_rt
156
#define time_arg2 NULL
157
#define time_prep
158
  struct timespec curmono, abs_rt;
159
160
  clock_gettime(CLOCK_MONOTONIC, &curmono);
161
  clock_gettime(CLOCK_REALTIME, &abs_rt);
162
163
  abs_rt.tv_nsec += abs_monotime_limit->tv_nsec - curmono.tv_nsec;
164
  if (abs_rt.tv_nsec < 0) {
165
    abs_rt.tv_sec--;
166
    abs_rt.tv_nsec += 1000000000;
167
  } else if (abs_rt.tv_nsec >= 1000000000) {
168
    abs_rt.tv_sec++;
169
    abs_rt.tv_nsec -= 1000000000;
170
  }
171
  abs_rt.tv_sec += abs_monotime_limit->tv_sec - curmono.tv_sec;
172
173
/*
174
 * RELATIVE - used on OpenBSD (might get a patch to get absolute monotime)
175
 */
176
#elif defined(TIME_RELATIVE)
177
  struct timespec reltime;
178
179
#define time_arg1 abs_monotime_limit
180
#define time_arg2 &reltime
181
#define time_prep \
182
  clock_gettime(CLOCK_MONOTONIC, &reltime);                              \
183
  reltime.tv_sec = abs_monotime_limit.tv_sec - reltime.tv_sec;           \
184
  reltime.tv_nsec = abs_monotime_limit.tv_nsec - reltime.tv_nsec;        \
185
  if (reltime.tv_nsec < 0) {                                             \
186
    reltime.tv_sec--;                                              \
187
    reltime.tv_nsec += 1000000000;                                 \
188
  }
189
/*
190
 * FreeBSD & Linux: absolute time re. CLOCK_MONOTONIC
191
 */
192
#else
193
0
#define time_arg1 abs_monotime_limit
194
0
#define time_arg2 NULL
195
0
#define time_prep
196
0
#endif
197
198
0
  bool ret = true;
199
0
  seqlock_val_t cur, cal;
200
201
0
  seqlock_assert_valid(val);
202
203
0
  wait_prep(sqlo);
204
0
  cur = atomic_load_explicit(&sqlo->pos, memory_order_relaxed);
205
206
0
  while (cur & SEQLOCK_HELD) {
207
0
    cal = SEQLOCK_VAL(cur) - val - 1;
208
0
    assert(cal < 0x40000000 || cal > 0xc0000000);
209
0
    if (cal < 0x80000000)
210
0
      break;
211
212
0
    if ((cur & SEQLOCK_WAITERS)
213
0
        || atomic_compare_exchange_weak_explicit(
214
0
        &sqlo->pos, &cur, cur | SEQLOCK_WAITERS,
215
0
        memory_order_relaxed, memory_order_relaxed)) {
216
0
      int rv;
217
218
      time_prep
219
220
0
      rv = wait_time(sqlo, cur | SEQLOCK_WAITERS, time_arg1,
221
0
               time_arg2);
222
0
      if (rv) {
223
0
        ret = false;
224
0
        break;
225
0
      }
226
0
      cur = atomic_load_explicit(&sqlo->pos,
227
0
        memory_order_relaxed);
228
0
    }
229
0
  }
230
0
  wait_done(sqlo);
231
232
0
  return ret;
233
0
}
234
235
bool seqlock_check(struct seqlock *sqlo, seqlock_val_t val)
236
0
{
237
0
  seqlock_val_t cur;
238
239
0
  seqlock_assert_valid(val);
240
241
0
  cur = atomic_load_explicit(&sqlo->pos, memory_order_relaxed);
242
0
  if (!(cur & SEQLOCK_HELD))
243
0
    return true;
244
0
  cur = SEQLOCK_VAL(cur) - val - 1;
245
0
  assert(cur < 0x40000000 || cur > 0xc0000000);
246
0
  return cur < 0x80000000;
247
0
}
248
249
void seqlock_acquire_val(struct seqlock *sqlo, seqlock_val_t val)
250
12
{
251
12
  seqlock_val_t prev;
252
253
12
  seqlock_assert_valid(val);
254
255
12
  prev = atomic_exchange_explicit(&sqlo->pos, val, memory_order_relaxed);
256
12
  if (prev & SEQLOCK_WAITERS)
257
0
    wait_poke(sqlo);
258
12
}
259
260
void seqlock_release(struct seqlock *sqlo)
261
0
{
262
0
  seqlock_val_t prev;
263
264
0
  prev = atomic_exchange_explicit(&sqlo->pos, 0, memory_order_relaxed);
265
0
  if (prev & SEQLOCK_WAITERS)
266
0
    wait_poke(sqlo);
267
0
}
268
269
void seqlock_init(struct seqlock *sqlo)
270
12
{
271
12
  sqlo->pos = 0;
272
12
  wait_init(sqlo);
273
12
}
274
275
276
seqlock_val_t seqlock_cur(struct seqlock *sqlo)
277
0
{
278
0
  return SEQLOCK_VAL(atomic_load_explicit(&sqlo->pos,
279
0
            memory_order_relaxed));
280
0
}
281
282
seqlock_val_t seqlock_bump(struct seqlock *sqlo)
283
0
{
284
0
  seqlock_val_t val, cur;
285
286
0
  cur = atomic_load_explicit(&sqlo->pos, memory_order_relaxed);
287
0
  seqlock_assert_valid(cur);
288
289
0
  do {
290
0
    val = SEQLOCK_VAL(cur) + SEQLOCK_INCR;
291
0
  } while (!atomic_compare_exchange_weak_explicit(&sqlo->pos, &cur, val,
292
0
      memory_order_relaxed, memory_order_relaxed));
293
294
0
  if (cur & SEQLOCK_WAITERS)
295
0
    wait_poke(sqlo);
296
0
  return val;
297
0
}