[mirror_frr.git] / lib / seqlock.c

// SPDX-License-Identifier: LGPL-2.1-or-later
/*
 * "Sequence" lock primitive
 *
 * Copyright (C) 2015  David Lamparter <equinox@diac24.net>
 */

#define _GNU_SOURCE

#ifdef HAVE_CONFIG_H
#include "config.h"
#endif

#include <string.h>
#include <unistd.h>
#include <limits.h>
#include <errno.h>
#include <sys/types.h>
#include <sys/time.h>
#include <pthread.h>
#include <assert.h>

#include "seqlock.h"

/****************************************
 * OS specific synchronization wrappers *
 ****************************************/

/*
 * Linux: sys_futex()
 */
#ifdef HAVE_SYNC_LINUX_FUTEX
#include <sys/syscall.h>
#include <linux/futex.h>

static long sys_futex(void *addr1, int op, int val1,
		      const struct timespec *timeout, void *addr2, int val3)
{
	return syscall(SYS_futex, addr1, op, val1, timeout, addr2, val3);
}

#define wait_once(sqlo, val)	\
	sys_futex((int *)&sqlo->pos, FUTEX_WAIT, (int)val, NULL, NULL, 0)
#define wait_time(sqlo, val, time, reltime)	\
	sys_futex((int *)&sqlo->pos, FUTEX_WAIT_BITSET, (int)val, time, \
		  NULL, ~0U)
#define wait_poke(sqlo)		\
	sys_futex((int *)&sqlo->pos, FUTEX_WAKE, INT_MAX, NULL, NULL, 0)

/*
 * OpenBSD: sys_futex(), almost the same as on Linux
 */
#elif defined(HAVE_SYNC_OPENBSD_FUTEX)
#include <sys/syscall.h>
#include <sys/futex.h>

#define TIME_RELATIVE		1

#define wait_once(sqlo, val)	\
	futex((int *)&sqlo->pos, FUTEX_WAIT, (int)val, NULL, NULL, 0)
#define wait_time(sqlo, val, time, reltime)	\
	futex((int *)&sqlo->pos, FUTEX_WAIT, (int)val, reltime, NULL, 0)
#define wait_poke(sqlo)		\
	futex((int *)&sqlo->pos, FUTEX_WAKE, INT_MAX, NULL, NULL, 0)

/*
 * FreeBSD: _umtx_op()
 */
#elif defined(HAVE_SYNC_UMTX_OP)
#include <sys/umtx.h>

#define wait_once(sqlo, val)	\
	_umtx_op((void *)&sqlo->pos, UMTX_OP_WAIT_UINT, val, NULL, NULL)
static int wait_time(struct seqlock *sqlo, uint32_t val,
		      const struct timespec *abstime,
		      const struct timespec *reltime)
{
	struct _umtx_time t;
	t._flags = UMTX_ABSTIME;
	t._clockid = CLOCK_MONOTONIC;
	memcpy(&t._timeout, abstime, sizeof(t._timeout));
	return _umtx_op((void *)&sqlo->pos, UMTX_OP_WAIT_UINT, val,
		 (void *)(uintptr_t) sizeof(t), &t);
}
#define wait_poke(sqlo)		\
	_umtx_op((void *)&sqlo->pos, UMTX_OP_WAKE, INT_MAX, NULL, NULL)

/*
 * generic version.  used on NetBSD, Solaris and OSX.  really shitty.
 */
#else

#define TIME_ABS_REALTIME	1

#define wait_init(sqlo)		do { \
		pthread_mutex_init(&sqlo->lock, NULL); \
		pthread_cond_init(&sqlo->wake, NULL); \
	} while (0)
#define wait_prep(sqlo)		pthread_mutex_lock(&sqlo->lock)
#define wait_once(sqlo, val)	pthread_cond_wait(&sqlo->wake, &sqlo->lock)
#define wait_time(sqlo, val, time, reltime) \
				pthread_cond_timedwait(&sqlo->wake, \
						       &sqlo->lock, time);
#define wait_done(sqlo)		pthread_mutex_unlock(&sqlo->lock)
#define wait_poke(sqlo)		do { \
		pthread_mutex_lock(&sqlo->lock); \
		pthread_cond_broadcast(&sqlo->wake); \
		pthread_mutex_unlock(&sqlo->lock); \
	} while (0)

#endif

#ifndef wait_init
#define wait_init(sqlo)		/**/
#define wait_prep(sqlo)		/**/
#define wait_done(sqlo)		/**/
#endif /* wait_init */


void seqlock_wait(struct seqlock *sqlo, seqlock_val_t val)
{
	seqlock_val_t cur, cal;

	seqlock_assert_valid(val);

	wait_prep(sqlo);
	cur = atomic_load_explicit(&sqlo->pos, memory_order_relaxed);

	while (cur & SEQLOCK_HELD) {
		cal = SEQLOCK_VAL(cur) - val - 1;
		assert(cal < 0x40000000 || cal > 0xc0000000);
		if (cal < 0x80000000)
			break;

		if ((cur & SEQLOCK_WAITERS)
		    || atomic_compare_exchange_weak_explicit(
				&sqlo->pos, &cur, cur | SEQLOCK_WAITERS,
				memory_order_relaxed, memory_order_relaxed)) {
			wait_once(sqlo, cur | SEQLOCK_WAITERS);
			cur = atomic_load_explicit(&sqlo->pos,
				memory_order_relaxed);
		}
		/* else: we failed to swap in cur because it just changed */
	}
	wait_done(sqlo);
}

bool seqlock_timedwait(struct seqlock *sqlo, seqlock_val_t val,
		       const struct timespec *abs_monotime_limit)
{
/*
 * ABS_REALTIME - used on NetBSD, Solaris and OSX
 */
#ifdef TIME_ABS_REALTIME
#define time_arg1 &abs_rt
#define time_arg2 NULL
#define time_prep
	struct timespec curmono, abs_rt;

	clock_gettime(CLOCK_MONOTONIC, &curmono);
	clock_gettime(CLOCK_REALTIME, &abs_rt);

	abs_rt.tv_nsec += abs_monotime_limit->tv_nsec - curmono.tv_nsec;
	if (abs_rt.tv_nsec < 0) {
		abs_rt.tv_sec--;
		abs_rt.tv_nsec += 1000000000;
	} else if (abs_rt.tv_nsec >= 1000000000) {
		abs_rt.tv_sec++;
		abs_rt.tv_nsec -= 1000000000;
	}
	abs_rt.tv_sec += abs_monotime_limit->tv_sec - curmono.tv_sec;

/*
 * RELATIVE - used on OpenBSD (might get a patch to get absolute monotime)
 */
#elif defined(TIME_RELATIVE)
	struct timespec reltime;

#define time_arg1 abs_monotime_limit
#define time_arg2 &reltime
#define time_prep \
	clock_gettime(CLOCK_MONOTONIC, &reltime);                              \
	reltime.tv_sec = abs_monotime_limit.tv_sec - reltime.tv_sec;           \
	reltime.tv_nsec = abs_monotime_limit.tv_nsec - reltime.tv_nsec;        \
	if (reltime.tv_nsec < 0) {                                             \
		reltime.tv_sec--;                                              \
		reltime.tv_nsec += 1000000000;                                 \
	}
/*
 * FreeBSD & Linux: absolute time re. CLOCK_MONOTONIC
 */
#else
#define time_arg1 abs_monotime_limit
#define time_arg2 NULL
#define time_prep
#endif

	bool ret = true;
	seqlock_val_t cur, cal;

	seqlock_assert_valid(val);

	wait_prep(sqlo);
	cur = atomic_load_explicit(&sqlo->pos, memory_order_relaxed);

	while (cur & SEQLOCK_HELD) {
		cal = SEQLOCK_VAL(cur) - val - 1;
		assert(cal < 0x40000000 || cal > 0xc0000000);
		if (cal < 0x80000000)
			break;

		if ((cur & SEQLOCK_WAITERS)
		    || atomic_compare_exchange_weak_explicit(
				&sqlo->pos, &cur, cur | SEQLOCK_WAITERS,
				memory_order_relaxed, memory_order_relaxed)) {
			int rv;

			time_prep

			rv = wait_time(sqlo, cur | SEQLOCK_WAITERS, time_arg1,
				       time_arg2);
			if (rv) {
				ret = false;
				break;
			}
			cur = atomic_load_explicit(&sqlo->pos,
				memory_order_relaxed);
		}
	}
	wait_done(sqlo);

	return ret;
}

bool seqlock_check(struct seqlock *sqlo, seqlock_val_t val)
{
	seqlock_val_t cur;

	seqlock_assert_valid(val);

	cur = atomic_load_explicit(&sqlo->pos, memory_order_relaxed);
	if (!(cur & SEQLOCK_HELD))
		return true;
	cur = SEQLOCK_VAL(cur) - val - 1;
	assert(cur < 0x40000000 || cur > 0xc0000000);
	return cur < 0x80000000;
}

void seqlock_acquire_val(struct seqlock *sqlo, seqlock_val_t val)
{
	seqlock_val_t prev;

	seqlock_assert_valid(val);

	prev = atomic_exchange_explicit(&sqlo->pos, val, memory_order_relaxed);
	if (prev & SEQLOCK_WAITERS)
		wait_poke(sqlo);
}

void seqlock_release(struct seqlock *sqlo)
{
	seqlock_val_t prev;

	prev = atomic_exchange_explicit(&sqlo->pos, 0, memory_order_relaxed);
	if (prev & SEQLOCK_WAITERS)
		wait_poke(sqlo);
}

void seqlock_init(struct seqlock *sqlo)
{
	sqlo->pos = 0;
	wait_init(sqlo);
}


seqlock_val_t seqlock_cur(struct seqlock *sqlo)
{
	return SEQLOCK_VAL(atomic_load_explicit(&sqlo->pos,
						memory_order_relaxed));
}

seqlock_val_t seqlock_bump(struct seqlock *sqlo)
{
	seqlock_val_t val, cur;

	cur = atomic_load_explicit(&sqlo->pos, memory_order_relaxed);
	seqlock_assert_valid(cur);

	do {
		val = SEQLOCK_VAL(cur) + SEQLOCK_INCR;
	} while (!atomic_compare_exchange_weak_explicit(&sqlo->pos, &cur, val,
			memory_order_relaxed, memory_order_relaxed));

	if (cur & SEQLOCK_WAITERS)
		wait_poke(sqlo);
	return val;
}
Commit	Line	Data
47a3a827	1	// SPDX-License-Identifier: LGPL-2.1-or-later
440d5faa DL	2	/*
	3	* "Sequence" lock primitive
	4	*
	5	* Copyright (C) 2015 David Lamparter <equinox@diac24.net>
440d5faa DL	6	*/
	7
	8	#define _GNU_SOURCE
	9
	10	#ifdef HAVE_CONFIG_H
	11	#include "config.h"
	12	#endif
	13
2a5e6235	14	#include <string.h>
440d5faa DL	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
30ef834a DL	25	/****************************************
	26	* OS specific synchronization wrappers *
	27	****************************************/
	28
	29	/*
	30	* Linux: sys_futex()
	31	*/
440d5faa	32	#ifdef HAVE_SYNC_LINUX_FUTEX
440d5faa DL	33	#include <sys/syscall.h>
	34	#include <linux/futex.h>
	35
2a5e6235 DL	36	static long sys_futex(void *addr1, int op, int val1,
2a5e6235 DL	37	const struct timespec timeout, void addr2, int val3)
440d5faa DL	38	{
	39	return syscall(SYS_futex, addr1, op, val1, timeout, addr2, val3);
	40	}
	41
	42	#define wait_once(sqlo, val) \
	43	sys_futex((int *)&sqlo->pos, FUTEX_WAIT, (int)val, NULL, NULL, 0)
2a5e6235 DL	44	#define wait_time(sqlo, val, time, reltime) \
	45	sys_futex((int *)&sqlo->pos, FUTEX_WAIT_BITSET, (int)val, time, \
	46	NULL, ~0U)
440d5faa DL	47	#define wait_poke(sqlo) \
	48	sys_futex((int *)&sqlo->pos, FUTEX_WAKE, INT_MAX, NULL, NULL, 0)
	49
30ef834a DL	50	/*
	51	* OpenBSD: sys_futex(), almost the same as on Linux
	52	*/
440d5faa	53	#elif defined(HAVE_SYNC_OPENBSD_FUTEX)
440d5faa DL	54	#include <sys/syscall.h>
	55	#include <sys/futex.h>
	56
2a5e6235 DL	57	#define TIME_RELATIVE 1
2a5e6235 DL	58
440d5faa DL	59	#define wait_once(sqlo, val) \
440d5faa DL	60	futex((int *)&sqlo->pos, FUTEX_WAIT, (int)val, NULL, NULL, 0)
2a5e6235 DL	61	#define wait_time(sqlo, val, time, reltime) \
2a5e6235 DL	62	futex((int *)&sqlo->pos, FUTEX_WAIT, (int)val, reltime, NULL, 0)
440d5faa DL	63	#define wait_poke(sqlo) \
	64	futex((int *)&sqlo->pos, FUTEX_WAKE, INT_MAX, NULL, NULL, 0)
	65
30ef834a DL	66	/*
	67	* FreeBSD: _umtx_op()
	68	*/
440d5faa	69	#elif defined(HAVE_SYNC_UMTX_OP)
440d5faa DL	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)
2a5e6235 DL	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	}
440d5faa DL	85	#define wait_poke(sqlo) \
	86	_umtx_op((void *)&sqlo->pos, UMTX_OP_WAKE, INT_MAX, NULL, NULL)
	87
30ef834a DL	88	/*
30ef834a DL	89	* generic version. used on NetBSD, Solaris and OSX. really shitty.
440d5faa	90	*/
30ef834a	91	#else
440d5faa	92
2a5e6235 DL	93	#define TIME_ABS_REALTIME 1
2a5e6235 DL	94
440d5faa DL	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)
2a5e6235 DL	101	#define wait_time(sqlo, val, time, reltime) \
	102	pthread_cond_timedwait(&sqlo->wake, \
	103	&sqlo->lock, time);
440d5faa DL	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	{
	122	seqlock_val_t cur, cal;
	123
	124	seqlock_assert_valid(val);
	125
	126	wait_prep(sqlo);
6046b690 DL	127	cur = atomic_load_explicit(&sqlo->pos, memory_order_relaxed);
	128
	129	while (cur & SEQLOCK_HELD) {
	130	cal = SEQLOCK_VAL(cur) - val - 1;
440d5faa DL	131	assert(cal < 0x40000000 \|\| cal > 0xc0000000);
	132	if (cal < 0x80000000)
	133	break;
	134
6046b690 DL	135	if ((cur & SEQLOCK_WAITERS)
	136	\|\| atomic_compare_exchange_weak_explicit(
	137	&sqlo->pos, &cur, cur \| SEQLOCK_WAITERS,
	138	memory_order_relaxed, memory_order_relaxed)) {
	139	wait_once(sqlo, cur \| SEQLOCK_WAITERS);
	140	cur = atomic_load_explicit(&sqlo->pos,
	141	memory_order_relaxed);
	142	}
	143	/* else: we failed to swap in cur because it just changed */
440d5faa DL	144	}
	145	wait_done(sqlo);
	146	}
	147
2a5e6235 DL	148	bool seqlock_timedwait(struct seqlock *sqlo, seqlock_val_t val,
	149	const struct timespec *abs_monotime_limit)
	150	{
30ef834a DL	151	/*
	152	* ABS_REALTIME - used on NetBSD, Solaris and OSX
	153	*/
1e20238a	154	#ifdef TIME_ABS_REALTIME
2a5e6235 DL	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
30ef834a DL	173	/*
	174	* RELATIVE - used on OpenBSD (might get a patch to get absolute monotime)
	175	*/
1e20238a	176	#elif defined(TIME_RELATIVE)
2a5e6235 DL	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	}
30ef834a DL	189	/*
	190	* FreeBSD & Linux: absolute time re. CLOCK_MONOTONIC
	191	*/
2a5e6235 DL	192	#else
	193	#define time_arg1 abs_monotime_limit
	194	#define time_arg2 NULL
	195	#define time_prep
	196	#endif
	197
	198	bool ret = true;
	199	seqlock_val_t cur, cal;
	200
	201	seqlock_assert_valid(val);
	202
	203	wait_prep(sqlo);
	204	cur = atomic_load_explicit(&sqlo->pos, memory_order_relaxed);
	205
	206	while (cur & SEQLOCK_HELD) {
	207	cal = SEQLOCK_VAL(cur) - val - 1;
	208	assert(cal < 0x40000000 \|\| cal > 0xc0000000);
	209	if (cal < 0x80000000)
	210	break;
	211
	212	if ((cur & SEQLOCK_WAITERS)
	213	\|\| atomic_compare_exchange_weak_explicit(
	214	&sqlo->pos, &cur, cur \| SEQLOCK_WAITERS,
	215	memory_order_relaxed, memory_order_relaxed)) {
	216	int rv;
	217
	218	time_prep
	219
	220	rv = wait_time(sqlo, cur \| SEQLOCK_WAITERS, time_arg1,
	221	time_arg2);
	222	if (rv) {
	223	ret = false;
	224	break;
	225	}
	226	cur = atomic_load_explicit(&sqlo->pos,
	227	memory_order_relaxed);
	228	}
	229	}
	230	wait_done(sqlo);
	231
	232	return ret;
	233	}
	234
440d5faa DL	235	bool seqlock_check(struct seqlock *sqlo, seqlock_val_t val)
	236	{
	237	seqlock_val_t cur;
	238
	239	seqlock_assert_valid(val);
	240
6046b690 DL	241	cur = atomic_load_explicit(&sqlo->pos, memory_order_relaxed);
6046b690 DL	242	if (!(cur & SEQLOCK_HELD))
f06c4576	243	return true;
6046b690	244	cur = SEQLOCK_VAL(cur) - val - 1;
440d5faa DL	245	assert(cur < 0x40000000 \|\| cur > 0xc0000000);
	246	return cur < 0x80000000;
	247	}
	248
	249	void seqlock_acquire_val(struct seqlock *sqlo, seqlock_val_t val)
	250	{
6046b690 DL	251	seqlock_val_t prev;
6046b690 DL	252
440d5faa DL	253	seqlock_assert_valid(val);
440d5faa DL	254
6046b690 DL	255	prev = atomic_exchange_explicit(&sqlo->pos, val, memory_order_relaxed);
	256	if (prev & SEQLOCK_WAITERS)
	257	wait_poke(sqlo);
440d5faa DL	258	}
	259
	260	void seqlock_release(struct seqlock *sqlo)
	261	{
6046b690 DL	262	seqlock_val_t prev;
	263
	264	prev = atomic_exchange_explicit(&sqlo->pos, 0, memory_order_relaxed);
	265	if (prev & SEQLOCK_WAITERS)
	266	wait_poke(sqlo);
440d5faa DL	267	}
	268
	269	void seqlock_init(struct seqlock *sqlo)
	270	{
	271	sqlo->pos = 0;
	272	wait_init(sqlo);
	273	}
	274
	275
	276	seqlock_val_t seqlock_cur(struct seqlock *sqlo)
	277	{
6046b690 DL	278	return SEQLOCK_VAL(atomic_load_explicit(&sqlo->pos,
6046b690 DL	279	memory_order_relaxed));
440d5faa DL	280	}
	281
	282	seqlock_val_t seqlock_bump(struct seqlock *sqlo)
	283	{
6046b690 DL	284	seqlock_val_t val, cur;
	285
	286	cur = atomic_load_explicit(&sqlo->pos, memory_order_relaxed);
	287	seqlock_assert_valid(cur);
	288
	289	do {
	290	val = SEQLOCK_VAL(cur) + SEQLOCK_INCR;
	291	} while (!atomic_compare_exchange_weak_explicit(&sqlo->pos, &cur, val,
	292	memory_order_relaxed, memory_order_relaxed));
440d5faa	293
6046b690 DL	294	if (cur & SEQLOCK_WAITERS)
6046b690 DL	295	wait_poke(sqlo);
440d5faa DL	296	return val;
440d5faa DL	297	}