[mirror_frr.git] / lib / seqlock.c

/*
 * "Sequence" lock primitive
 *
 * Copyright (C) 2015  David Lamparter <equinox@diac24.net>
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the
 * Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
 * Boston, MA  02110-1301  USA
 */

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