lib: add "seqlock" wait/broadcast primitive

Manually tested rather extensively in addition to included unit tests,
should work as intended.

NB: The OpenBSD futex() code is "future"; it's not actually in OpenBSD
(yet?) and thus untested.

Signed-off-by: David Lamparter <equinox@opensourcerouting.org>

7 files changed, 477 insertions, 0 deletions

diff --git a/configure.ac b/configure.ac
index 9ae196fcb..18c16634b 100755
--- a/configure.ac
+++ b/configure.ac
@@ -926,6 +926,80 @@ AC_CHECK_HEADERS([pthread_np.h],,, [
 ])
 AC_CHECK_FUNCS([pthread_setname_np pthread_set_name_np])
 
+needsync=true
+
+AS_IF([$needsync], [
+  dnl Linux
+  AC_MSG_CHECKING([for Linux futex() support])
+  AC_LINK_IFELSE([AC_LANG_PROGRAM([
+#ifndef _GNU_SOURCE
+#define _GNU_SOURCE
+#endif
+#include <unistd.h>
+#include <limits.h>
+#include <sys/time.h>
+#include <sys/syscall.h>
+#include <linux/futex.h>
+
+int main(void);
+],
+[
+{
+  return syscall(SYS_futex, NULL, FUTEX_WAIT, 0, NULL, NULL, 0);
+}
+])], [
+    AC_MSG_RESULT([yes])
+    AC_DEFINE(HAVE_SYNC_LINUX_FUTEX,,Have Linux futex support)
+    needsync=false
+  ], [
+    AC_MSG_RESULT([no])
+  ])
+])
+
+AS_IF([$needsync], [
+  dnl FreeBSD
+  AC_MSG_CHECKING([for FreeBSD _umtx_op() support])
+  AC_LINK_IFELSE([AC_LANG_PROGRAM([
+#include <errno.h>
+#include <stdlib.h>
+#include <sys/types.h>
+#include <sys/umtx.h>
+int main(void);
+],
+[
+{
+  return _umtx_op(NULL, UMTX_OP_WAIT_UINT, 0, NULL, NULL);
+}
+])], [
+    AC_MSG_RESULT([yes])
+    AC_DEFINE(HAVE_SYNC_UMTX_OP,,Have FreeBSD _umtx_op() support)
+    needsync=false
+  ], [
+    AC_MSG_RESULT([no])
+  ])
+])
+
+AS_IF([$needsync], [
+  dnl OpenBSD patch (not upstream at the time of writing this)
+  dnl https://marc.info/?l=openbsd-tech&m=147299508409549&w=2
+  AC_MSG_CHECKING([for OpenBSD futex() support])
+  AC_LINK_IFELSE([AC_LANG_PROGRAM([
+#include <sys/futex.h>
+int main(void);
+],
+[
+{
+  return futex(NULL, FUTEX_WAIT, 0, NULL, NULL, 0);
+}
+])], [
+    AC_MSG_RESULT([yes])
+    AC_DEFINE(HAVE_SYNC_OPENBSD_FUTEX,,Have OpenBSD futex support)
+    needsync=false
+  ], [
+    AC_MSG_RESULT([no])
+  ])
+])
+
 dnl Utility macro to avoid retyping includes all the time
 m4_define([FRR_INCLUDES],
 [#ifdef SUNOS_5
diff --git a/lib/seqlock.c b/lib/seqlock.c
new file mode 100644
index 000000000..223d14952
--- /dev/null
+++ b/lib/seqlock.c
@@ -0,0 +1,167 @@
+/*
+ * "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 <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"
+
+#ifdef HAVE_SYNC_LINUX_FUTEX
+/* Linux-specific - sys_futex() */
+#include <sys/syscall.h>
+#include <linux/futex.h>
+
+static long sys_futex(void *addr1, int op, int val1, 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_poke(sqlo)		\
+	sys_futex((int *)&sqlo->pos, FUTEX_WAKE, INT_MAX, NULL, NULL, 0)
+
+#elif defined(HAVE_SYNC_OPENBSD_FUTEX)
+/* OpenBSD variant of the above.  untested, not upstream in OpenBSD. */
+#include <sys/syscall.h>
+#include <sys/futex.h>
+
+#define wait_once(sqlo, val)	\
+	futex((int *)&sqlo->pos, FUTEX_WAIT, (int)val, NULL, NULL, 0)
+#define wait_poke(sqlo)		\
+	futex((int *)&sqlo->pos, FUTEX_WAKE, INT_MAX, NULL, NULL, 0)
+
+#elif defined(HAVE_SYNC_UMTX_OP)
+/* FreeBSD-specific: umtx_op() */
+#include <sys/umtx.h>
+
+#define wait_once(sqlo, val)	\
+	_umtx_op((void *)&sqlo->pos, UMTX_OP_WAIT_UINT, val, NULL, NULL)
+#define wait_poke(sqlo)		\
+	_umtx_op((void *)&sqlo->pos, UMTX_OP_WAKE, INT_MAX, NULL, NULL)
+
+#else
+/* generic version.  used on *BSD, Solaris and OSX.
+ */
+
+#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_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);
+	while (1) {
+		cur = atomic_load_explicit(&sqlo->pos, memory_order_acquire);
+		if (!(cur & 1))
+			break;
+		cal = cur - val - 1;
+		assert(cal < 0x40000000 || cal > 0xc0000000);
+		if (cal < 0x80000000)
+			break;
+
+		wait_once(sqlo, cur);
+	}
+	wait_done(sqlo);
+}
+
+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_acquire);
+	if (!(cur & 1))
+		return 1;
+	cur -= val;
+	assert(cur < 0x40000000 || cur > 0xc0000000);
+	return cur < 0x80000000;
+}
+
+void seqlock_acquire_val(struct seqlock *sqlo, seqlock_val_t val)
+{
+	seqlock_assert_valid(val);
+
+	atomic_store_explicit(&sqlo->pos, val, memory_order_release);
+	wait_poke(sqlo);
+}
+
+void seqlock_release(struct seqlock *sqlo)
+{
+	atomic_store_explicit(&sqlo->pos, 0, memory_order_release);
+	wait_poke(sqlo);
+}
+
+void seqlock_init(struct seqlock *sqlo)
+{
+	sqlo->pos = 0;
+	wait_init(sqlo);
+}
+
+
+seqlock_val_t seqlock_cur(struct seqlock *sqlo)
+{
+	return atomic_load_explicit(&sqlo->pos, memory_order_acquire);
+}
+
+seqlock_val_t seqlock_bump(struct seqlock *sqlo)
+{
+	seqlock_val_t val;
+
+	val = atomic_fetch_add_explicit(&sqlo->pos, 2, memory_order_release);
+	wait_poke(sqlo);
+	return val;
+}
diff --git a/lib/seqlock.h b/lib/seqlock.h
new file mode 100644
index 000000000..eef05a430
--- /dev/null
+++ b/lib/seqlock.h
@@ -0,0 +1,106 @@
+/*
+ * "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
+ */
+
+#ifndef _SEQLOCK_H
+#define _SEQLOCK_H
+
+#include <stdbool.h>
+#include <stdint.h>
+#include <pthread.h>
+#include "frratomic.h"
+
+/*
+ * this locking primitive is intended to use in a 1:N setup.
+ *
+ * - one "counter" seqlock issuing increasing numbers
+ * - multiple seqlock users hold references on these numbers
+ *
+ * this is intended for implementing RCU reference-holding.  There is one
+ * global counter, with threads locking a seqlock whenever they take a
+ * reference.  A seqlock can also be idle/unlocked.
+ *
+ * The "counter" seqlock will always stay locked;  the RCU cleanup thread
+ * continuously counts it up, waiting for threads to release or progress to a
+ * sequence number further ahead.  If all threads are > N, references dropped
+ * in N can be free'd.
+ *
+ * generally, the lock function is:
+ *
+ * Thread-A                  Thread-B
+ *
+ * seqlock_acquire(a)
+ *    | running              seqlock_wait(b)      -- a <= b
+ * seqlock_release()            | blocked
+ * OR: seqlock_acquire(a')      |                 -- a' > b
+ *                           (resumes)
+ */
+
+/* use sequentially increasing "ticket numbers".  lowest bit will always
+ * be 1 to have a 'cleared' indication (i.e., counts 1,3,5,7,etc. )
+ */
+typedef _Atomic uint32_t	seqlock_ctr_t;
+typedef uint32_t		seqlock_val_t;
+#define seqlock_assert_valid(val) assert(val & 1)
+
+
+struct seqlock {
+/* always used */
+	seqlock_ctr_t pos;
+/* used when futexes not available: (i.e. non-linux) */
+	pthread_mutex_t lock;
+	pthread_cond_t  wake;
+};
+
+
+/* sqlo = 0 - init state: not held */
+extern void seqlock_init(struct seqlock *sqlo);
+
+
+/* while (sqlo <= val) - wait until seqlock->pos > val, or seqlock unheld */
+extern void seqlock_wait(struct seqlock *sqlo, seqlock_val_t val);
+extern bool seqlock_check(struct seqlock *sqlo, seqlock_val_t val);
+
+static inline bool seqlock_held(struct seqlock *sqlo)
+{
+	return !!atomic_load_explicit(&sqlo->pos, memory_order_relaxed);
+}
+
+/* sqlo - get seqlock position -- for the "counter" seqlock */
+extern seqlock_val_t seqlock_cur(struct seqlock *sqlo);
+/* sqlo++ - note: like x++, returns previous value, before bumping */
+extern seqlock_val_t seqlock_bump(struct seqlock *sqlo);
+
+
+/* sqlo = val - can be used on held seqlock. */
+extern void seqlock_acquire_val(struct seqlock *sqlo, seqlock_val_t val);
+/* sqlo = ref - standard pattern: acquire relative to other seqlock */
+static inline void seqlock_acquire(struct seqlock *sqlo, struct seqlock *ref)
+{
+	seqlock_acquire_val(sqlo, seqlock_cur(ref));
+}
+
+/* sqlo = 0 - set seqlock position to 0, marking as non-held */
+extern void seqlock_release(struct seqlock *sqlo);
+/* release should normally be followed by a bump on the "counter", if
+ * anything other than reading RCU items was done
+ */
+
+#endif /* _SEQLOCK_H */
diff --git a/lib/subdir.am b/lib/subdir.am
index 3b14be467..03629c14e 100644
--- a/lib/subdir.am
+++ b/lib/subdir.am
@@ -65,6 +65,7 @@ lib_libfrr_la_SOURCES = \
 	lib/ringbuf.c \
 	lib/routemap.c \
 	lib/sbuf.c \
+	lib/seqlock.c \
 	lib/sha256.c \
 	lib/sigevent.c \
 	lib/skiplist.c \
@@ -193,6 +194,7 @@ pkginclude_HEADERS += \
 	lib/ringbuf.h \
 	lib/routemap.h \
 	lib/sbuf.h \
+	lib/seqlock.h \
 	lib/sha256.h \
 	lib/sigevent.h \
 	lib/skiplist.h \
diff --git a/tests/.gitignore b/tests/.gitignore
index de648015f..c29a6c382 100644
--- a/tests/.gitignore
+++ b/tests/.gitignore
@@ -32,6 +32,7 @@
 /lib/test_privs
 /lib/test_ringbuf
 /lib/test_segv
+/lib/test_seqlock
 /lib/test_sig
 /lib/test_srcdest_table
 /lib/test_stream
diff --git a/tests/lib/test_seqlock.c b/tests/lib/test_seqlock.c
new file mode 100644
index 000000000..6b2b9ed8a
--- /dev/null
+++ b/tests/lib/test_seqlock.c
@@ -0,0 +1,122 @@
+/*
+ * basic test for seqlock
+ *
+ * Copyright (C) 2015  David Lamparter
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License as published by the Free
+ * Software Foundation; either version 2 of the License, or (at your option)
+ * any later version.
+ *
+ * This program 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 General Public License for
+ * more details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * this program; if not, write to the Free Software Foundation, Inc., 59 Temple
+ * Place, Suite 330, Boston, MA  02111-1307  USA
+ */
+
+#include <stdio.h>
+#include <stdint.h>
+#include <inttypes.h>
+#include <string.h>
+#include <unistd.h>
+#include <assert.h>
+#include <sys/uio.h>
+
+#include "monotime.h"
+#include "seqlock.h"
+
+static struct seqlock sqlo;
+static pthread_t thr1;
+static struct timeval start;
+
+static void writestr(const char *str)
+{
+	struct iovec iov[2];
+	char buf[32];
+	int64_t usec = monotime_since(&start, NULL);
+
+	snprintf(buf, sizeof(buf), "[%02"PRId64"] ", usec / 100000);
+
+	iov[0].iov_base = buf;
+	iov[0].iov_len = strlen(buf);
+	iov[1].iov_base = (char *)str;
+	iov[1].iov_len = strlen(str);
+	writev(1, iov, 2);
+}
+
+static void *thr1func(void *arg)
+{
+	assert(!seqlock_held(&sqlo));
+	assert(seqlock_check(&sqlo, 1));
+	seqlock_wait(&sqlo, 1);
+	writestr("thr1 (unheld)\n");
+
+	sleep(2);
+
+	assert(seqlock_held(&sqlo));
+	assert(seqlock_check(&sqlo, 1));
+	seqlock_wait(&sqlo, 1);
+	writestr("thr1 @1\n");
+
+	seqlock_wait(&sqlo, 3);
+	writestr("thr1 @3\n");
+
+	seqlock_wait(&sqlo, 5);
+	writestr("thr1 @5\n");
+
+	seqlock_wait(&sqlo, 7);
+	writestr("thr1 @7\n");
+
+	seqlock_wait(&sqlo, 9);
+	writestr("thr1 @9\n");
+
+	seqlock_wait(&sqlo, 11);
+	writestr("thr1 @11\n");
+	return NULL;
+}
+
+int main(int argc, char **argv)
+{
+	monotime(&start);
+
+	seqlock_init(&sqlo);
+
+	assert(!seqlock_held(&sqlo));
+	seqlock_acquire_val(&sqlo, 1);
+	assert(seqlock_held(&sqlo));
+
+	assert(seqlock_cur(&sqlo) == 1);
+	assert(seqlock_bump(&sqlo) == 1);
+	assert(seqlock_cur(&sqlo) == 3);
+	assert(seqlock_bump(&sqlo) == 3);
+	assert(seqlock_bump(&sqlo) == 5);
+	assert(seqlock_bump(&sqlo) == 7);
+	assert(seqlock_cur(&sqlo) == 9);
+
+	assert(seqlock_held(&sqlo));
+	seqlock_release(&sqlo);
+	assert(!seqlock_held(&sqlo));
+
+	pthread_create(&thr1, NULL, thr1func, NULL);
+	sleep(1);
+
+	writestr("main @3\n");
+	seqlock_acquire_val(&sqlo, 3);
+	sleep(2);
+
+	writestr("main @5\n");
+	seqlock_bump(&sqlo);
+	sleep(1);
+
+	writestr("main @9\n");
+	seqlock_acquire_val(&sqlo, 9);
+	sleep(1);
+
+	writestr("main @release\n");
+	seqlock_release(&sqlo);
+	sleep(1);
+}
diff --git a/tests/subdir.am b/tests/subdir.am
index 365fe00cc..167d8b43f 100644
--- a/tests/subdir.am
+++ b/tests/subdir.am
@@ -59,6 +59,7 @@ check_PROGRAMS = \
 	tests/lib/test_ringbuf \
 	tests/lib/test_srcdest_table \
 	tests/lib/test_segv \
+	tests/lib/test_seqlock \
 	tests/lib/test_sig \
 	tests/lib/test_stream \
 	tests/lib/test_table \
@@ -236,6 +237,10 @@ tests_lib_test_segv_CFLAGS = $(TESTS_CFLAGS)
 tests_lib_test_segv_CPPFLAGS = $(TESTS_CPPFLAGS)
 tests_lib_test_segv_LDADD = $(ALL_TESTS_LDADD)
 tests_lib_test_segv_SOURCES = tests/lib/test_segv.c
+tests_lib_test_seqlock_CFLAGS = $(TESTS_CFLAGS)
+tests_lib_test_seqlock_CPPFLAGS = $(TESTS_CPPFLAGS)
+tests_lib_test_seqlock_LDADD = $(ALL_TESTS_LDADD)
+tests_lib_test_seqlock_SOURCES = tests/lib/test_seqlock.c
 tests_lib_test_sig_CFLAGS = $(TESTS_CFLAGS)
 tests_lib_test_sig_CPPFLAGS = $(TESTS_CPPFLAGS)
 tests_lib_test_sig_LDADD = $(ALL_TESTS_LDADD)