Merge pull request #3045 from opensourcerouting/atoms

READY: lists/skiplists/rb-trees new API & sequence lock & atomic lists

10 files changed, 990 insertions, 9 deletions

diff --git a/tests/.gitignore b/tests/.gitignore
index de648015f1..380172487d 100644
--- a/tests/.gitignore
+++ b/tests/.gitignore
@@ -20,6 +20,7 @@
 /lib/cli/test_commands_defun.c
 /lib/northbound/test_oper_data
 /lib/cxxcompat
+/lib/test_atomlist
 /lib/test_buffer
 /lib/test_checksum
 /lib/test_graph
@@ -32,6 +33,7 @@
 /lib/test_privs
 /lib/test_ringbuf
 /lib/test_segv
+/lib/test_seqlock
 /lib/test_sig
 /lib/test_srcdest_table
 /lib/test_stream
@@ -39,6 +41,7 @@
 /lib/test_timer_correctness
 /lib/test_timer_performance
 /lib/test_ttable
+/lib/test_typelist
 /lib/test_zlog
 /lib/test_zmq
 /ospf6d/test_lsdb
diff --git a/tests/isisd/test_isis_lspdb.c b/tests/isisd/test_isis_lspdb.c
index b9c6f2bbb2..f0baa482c7 100644
--- a/tests/isisd/test_isis_lspdb.c
+++ b/tests/isisd/test_isis_lspdb.c
@@ -28,21 +28,22 @@ static void test_lsp_build_list_nonzero_ht(void)
 
 	area->lsp_mtu = 1500;
 
-	dict_t *lspdb = lsp_db_init();
+	struct lspdb_head _lspdb, *lspdb = &_lspdb;
+	lsp_db_init(&_lspdb);
 
 	struct isis_lsp *lsp1 = lsp_new(area, lsp_id1, 6000, 0, 0, 0, NULL,
 					ISIS_LEVEL2);
 
-	lsp_insert(lsp1, lspdb);
+	lsp_insert(lspdb, lsp1);
 
 	struct isis_lsp *lsp2 = lsp_new(area, lsp_id2, 6000, 0, 0, 0, NULL,
 					ISIS_LEVEL2);
 
-	lsp_insert(lsp2, lspdb);
+	lsp_insert(lspdb, lsp2);
 
 	struct list *list = list_new();
 
-	lsp_build_list_nonzero_ht(lsp_id1, lsp_id_end, list, lspdb);
+	lsp_build_list_nonzero_ht(lspdb, lsp_id1, lsp_id_end, list);
 	assert(list->count == 1);
 	assert(listgetdata(listhead(list)) == lsp1);
 	list_delete_all_node(list);
@@ -50,7 +51,7 @@ static void test_lsp_build_list_nonzero_ht(void)
 	lsp_id_end[5] = 0x03;
 	lsp_id_end[6] = 0x00;
 
-	lsp_build_list_nonzero_ht(lsp_id1, lsp_id_end, list, lspdb);
+	lsp_build_list_nonzero_ht(lspdb, lsp_id1, lsp_id_end, list);
 	assert(list->count == 2);
 	assert(listgetdata(listhead(list)) == lsp1);
 	assert(listgetdata(listtail(list)) == lsp2);
@@ -58,7 +59,7 @@ static void test_lsp_build_list_nonzero_ht(void)
 
 	memcpy(lsp_id1, lsp_id2, sizeof(lsp_id1));
 
-	lsp_build_list_nonzero_ht(lsp_id1, lsp_id_end, list, lspdb);
+	lsp_build_list_nonzero_ht(lspdb, lsp_id1, lsp_id_end, list);
 	assert(list->count == 1);
 	assert(listgetdata(listhead(list)) == lsp2);
 	list_delete_all_node(list);
@@ -66,13 +67,13 @@ static void test_lsp_build_list_nonzero_ht(void)
 	lsp_id1[5] = 0x03;
 	lsp_id_end[5] = 0x04;
 
-	lsp_build_list_nonzero_ht(lsp_id1, lsp_id_end, list, lspdb);
+	lsp_build_list_nonzero_ht(lspdb, lsp_id1, lsp_id_end, list);
 	assert(list->count == 0);
 	list_delete_all_node(list);
 
 	lsp_id1[5] = 0x00;
 
-	lsp_build_list_nonzero_ht(lsp_id1, lsp_id_end, list, lspdb);
+	lsp_build_list_nonzero_ht(lspdb, lsp_id1, lsp_id_end, list);
 	assert(list->count == 2);
 	assert(listgetdata(listhead(list)) == lsp1);
 	assert(listgetdata(listtail(list)) == lsp2);
diff --git a/tests/lib/cxxcompat.c b/tests/lib/cxxcompat.c
index d10962993d..12c333c8b6 100644
--- a/tests/lib/cxxcompat.c
+++ b/tests/lib/cxxcompat.c
@@ -32,7 +32,6 @@
 #include "lib/debug.h"
 #include "lib/distribute.h"
 #include "lib/ferr.h"
-#include "lib/fifo.h"
 #include "lib/filter.h"
 #include "lib/frr_pthread.h"
 #include "lib/frratomic.h"
diff --git a/tests/lib/test_atomlist.c b/tests/lib/test_atomlist.c
new file mode 100644
index 0000000000..078e05e336
--- /dev/null
+++ b/tests/lib/test_atomlist.c
@@ -0,0 +1,404 @@
+/*
+ * Copyright (c) 2016-2018  David Lamparter, for NetDEF, Inc.
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#ifdef HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#include <stdio.h>
+#include <stdint.h>
+#include <inttypes.h>
+#include <string.h>
+#include <unistd.h>
+#include <assert.h>
+#include <pthread.h>
+
+#include "atomlist.h"
+#include "seqlock.h"
+#include "monotime.h"
+
+/*
+ * maybe test:
+ * - alist_del_hint
+ * - alist_next_safe
+ * - asort_del_hint
+ * - asort_next_safe
+ */
+
+static struct seqlock sqlo;
+
+PREDECL_ATOMLIST(alist)
+PREDECL_ATOMSORT_UNIQ(asort)
+struct item {
+	uint64_t val1;
+	struct alist_item chain;
+	struct asort_item sortc;
+	uint64_t val2;
+};
+DECLARE_ATOMLIST(alist, struct item, chain)
+
+static int icmp(const struct item *a, const struct item *b);
+DECLARE_ATOMSORT_UNIQ(asort, struct item, sortc, icmp)
+
+static int icmp(const struct item *a, const struct item *b)
+{
+	if (a->val1 > b->val1)
+		return 1;
+	if (a->val1 < b->val1)
+		return -1;
+	return 0;
+}
+
+#define NITEM 10000
+struct item itm[NITEM];
+
+static struct alist_head ahead;
+static struct asort_head shead;
+
+#define NTHREADS 4
+static struct testthread {
+	pthread_t pt;
+	struct seqlock sqlo;
+	size_t counter, nullops;
+} thr[NTHREADS];
+
+struct testrun {
+	struct testrun *next;
+	int lineno;
+	const char *desc;
+	ssize_t prefill;
+	bool sorted;
+	void (*func)(unsigned int offset);
+};
+struct testrun *runs = NULL;
+
+#define NOCLEAR -1
+
+#define deftestrun(name, _desc, _prefill, _sorted) \
+static void trfunc_##name(unsigned int offset); \
+struct testrun tr_##name = { \
+	.desc = _desc, \
+	.lineno = __LINE__, \
+	.prefill = _prefill, \
+	.func = &trfunc_##name, \
+	.sorted = _sorted }; \
+static void __attribute__((constructor)) trsetup_##name(void) \
+{ \
+	struct testrun **inspos = &runs; \
+	while (*inspos && (*inspos)->lineno < tr_##name.lineno) \
+		inspos = &(*inspos)->next; \
+	tr_##name.next = *inspos; \
+	*inspos = &tr_##name; \
+} \
+static void trfunc_##name(unsigned int offset) \
+{ \
+	size_t i = 0, n = 0;
+
+#define endtestrun \
+	thr[offset].counter = i; \
+	thr[offset].nullops = n; \
+}
+
+deftestrun(add, "add vs. add", 0, false)
+	for (; i < NITEM / NTHREADS; i++)
+		alist_add_head(&ahead, &itm[i * NTHREADS + offset]);
+endtestrun
+
+deftestrun(del, "del vs. del", NOCLEAR, false)
+	for (; i < NITEM / NTHREADS / 10; i++)
+		alist_del(&ahead, &itm[i * NTHREADS + offset]);
+endtestrun
+
+deftestrun(addtail, "add_tail vs. add_tail", 0, false)
+	for (; i < NITEM / NTHREADS; i++)
+		alist_add_tail(&ahead, &itm[i * NTHREADS + offset]);
+endtestrun
+
+deftestrun(pop, "pop vs. pop", NOCLEAR, false)
+	for (; i < NITEM / NTHREADS; )
+		if (alist_pop(&ahead))
+			i++;
+		else
+			n++;
+endtestrun
+
+deftestrun(headN_vs_pop1, "add_head(N) vs. pop(1)", 1, false);
+	if (offset == 0) {
+		struct item *dr = NULL;
+
+		for (i = n = 0; i < NITEM; ) {
+			dr = alist_pop(&ahead);
+			if (dr)
+				i++;
+			else
+				n++;
+		}
+	} else {
+		for (i = offset; i < NITEM; i += NTHREADS)
+			alist_add_head(&ahead, &itm[i]);
+		i = 0;
+	}
+endtestrun
+
+deftestrun(head1_vs_popN, "add_head(1) vs. pop(N)", 0, false);
+	if (offset < NTHREADS - 1) {
+		struct item *dr = NULL;
+
+		for (i = n = 0; i < NITEM / NTHREADS; ) {
+			dr = alist_pop(&ahead);
+			if (dr)
+				i++;
+			else
+				n++;
+		}
+	} else {
+		for (i = 0; i < NITEM; i++)
+			alist_add_head(&ahead, &itm[i]);
+		i = 0;
+	}
+endtestrun
+
+deftestrun(headN_vs_popN, "add_head(N) vs. pop(N)", NTHREADS / 2, false)
+	if (offset < NTHREADS / 2) {
+		struct item *dr = NULL;
+
+		for (i = n = 0; i < NITEM * 2 / NTHREADS; ) {
+			dr = alist_pop(&ahead);
+			if (dr)
+				i++;
+			else
+				n++;
+		}
+	} else {
+		for (i = offset; i < NITEM; i += NTHREADS)
+			alist_add_head(&ahead, &itm[i]);
+		i = 0;
+	}
+endtestrun
+
+deftestrun(tailN_vs_pop1, "add_tail(N) vs. pop(1)", 1, false)
+	if (offset == 0) {
+		struct item *dr = NULL;
+
+		for (i = n = 0; i < NITEM - (NITEM / NTHREADS); ) {
+			dr = alist_pop(&ahead);
+			if (dr)
+				i++;
+			else
+				n++;
+		}
+	} else {
+		for (i = offset; i < NITEM; i += NTHREADS)
+			alist_add_tail(&ahead, &itm[i]);
+		i = 0;
+	}
+endtestrun
+
+deftestrun(tail1_vs_popN, "add_tail(1) vs. pop(N)", 0, false)
+	if (offset < NTHREADS - 1) {
+		struct item *dr = NULL;
+
+		for (i = n = 0; i < NITEM / NTHREADS; ) {
+			dr = alist_pop(&ahead);
+			if (dr)
+				i++;
+			else
+				n++;
+		}
+	} else {
+		for (i = 0; i < NITEM; i++)
+			alist_add_tail(&ahead, &itm[i]);
+		i = 0;
+	}
+endtestrun
+
+deftestrun(sort_add, "add_sort vs. add_sort", 0, true)
+	for (; i < NITEM / NTHREADS / 10; i++)
+		asort_add(&shead, &itm[i * NTHREADS + offset]);
+endtestrun
+
+deftestrun(sort_del, "del_sort vs. del_sort", NOCLEAR, true)
+	for (; i < NITEM / NTHREADS / 10; i++)
+		asort_del(&shead, &itm[i * NTHREADS + offset]);
+endtestrun
+
+deftestrun(sort_add_del, "add_sort vs. del_sort", NTHREADS / 2, true)
+	if (offset < NTHREADS / 2) {
+		for (; i < NITEM / NTHREADS / 10; i++)
+			asort_del(&shead, &itm[i * NTHREADS + offset]);
+	} else {
+		for (; i < NITEM / NTHREADS / 10; i++)
+			asort_add(&shead, &itm[i * NTHREADS + offset]);
+	}
+endtestrun
+
+static void *thr1func(void *arg)
+{
+	struct testthread *p = arg;
+	unsigned int offset = (unsigned int)(p - &thr[0]);
+	seqlock_val_t sv;
+	struct testrun *tr;
+
+	for (tr = runs; tr; tr = tr->next) {
+		sv = seqlock_bump(&p->sqlo);
+		seqlock_wait(&sqlo, sv);
+
+		tr->func(offset);
+	}
+	seqlock_bump(&p->sqlo);
+
+	return NULL;
+}
+
+static void clear_list(size_t prefill)
+{
+	size_t i;
+
+	memset(&ahead, 0, sizeof(ahead));
+	memset(&shead, 0, sizeof(shead));
+	memset(itm, 0, sizeof(itm));
+	for (i = 0; i < NITEM; i++) {
+		itm[i].val1 = itm[i].val2 = i;
+		if ((i % NTHREADS) < prefill) {
+			alist_add_tail(&ahead, &itm[i]);
+			asort_add(&shead, &itm[i]);
+		}
+	}
+}
+
+static void run_tr(struct testrun *tr)
+{
+	const char *desc = tr->desc;
+	struct timeval tv;
+	int64_t delta;
+	seqlock_val_t sv;
+	size_t c = 0, s = 0, n = 0;
+	struct item *item, *prev, dummy;
+
+	printf("[%02u] %35s %s\n", seqlock_cur(&sqlo) >> 1, "", desc);
+	fflush(stdout);
+
+	if (tr->prefill != NOCLEAR)
+		clear_list(tr->prefill);
+
+	monotime(&tv);
+	sv = seqlock_bump(&sqlo);
+	for (size_t i = 0; i < NTHREADS; i++) {
+		seqlock_wait(&thr[i].sqlo, seqlock_cur(&sqlo));
+		s += thr[i].counter;
+		n += thr[i].nullops;
+		thr[i].counter = 0;
+		thr[i].nullops = 0;
+	}
+
+	delta = monotime_since(&tv, NULL);
+	if (tr->sorted) {
+		uint64_t prevval = 0;
+
+		for_each(asort, &shead, item) {
+			assert(item->val1 >= prevval);
+			prevval = item->val1;
+			c++;
+		}
+		assert(c == asort_count(&shead));
+	} else {
+		prev = &dummy;
+		for_each(alist, &ahead, item) {
+			assert(item != prev);
+			prev = item;
+			c++;
+			assert(c <= NITEM);
+		}
+		assert(c == alist_count(&ahead));
+	}
+	printf("\033[1A[%02u] %9"PRId64"us c=%5zu s=%5zu n=%5zu %s\n",
+		sv >> 1, delta, c, s, n, desc);
+}
+
+#ifdef BASIC_TESTS
+static void dump(const char *lbl)
+{
+	struct item *item, *safe;
+	size_t ctr = 0;
+
+	printf("dumping %s:\n", lbl);
+	for_each_safe(alist, &ahead, item) {
+		printf("%s %3zu %p %3"PRIu64" %3"PRIu64"\n", lbl, ctr++,
+				(void *)item, item->val1, item->val2);
+	}
+}
+
+static void basic_tests(void)
+{
+	size_t i;
+
+	memset(&ahead, 0, sizeof(ahead));
+	memset(itm, 0, sizeof(itm));
+	for (i = 0; i < NITEM; i++)
+		itm[i].val1 = itm[i].val2 = i;
+
+	assert(alist_first(&ahead) == NULL);
+	dump("");
+	alist_add_head(&ahead, &itm[0]);
+	dump("");
+	alist_add_head(&ahead, &itm[1]);
+	dump("");
+	alist_add_tail(&ahead, &itm[2]);
+	dump("");
+	alist_add_tail(&ahead, &itm[3]);
+	dump("");
+	alist_del(&ahead, &itm[1]);
+	dump("");
+	printf("POP: %p\n", alist_pop(&ahead));
+	dump("");
+	printf("POP: %p\n", alist_pop(&ahead));
+	printf("POP: %p\n", alist_pop(&ahead));
+	printf("POP: %p\n", alist_pop(&ahead));
+	printf("POP: %p\n", alist_pop(&ahead));
+	dump("");
+}
+#else
+#define basic_tests() do { } while (0)
+#endif
+
+int main(int argc, char **argv)
+{
+	size_t i;
+
+	basic_tests();
+
+	seqlock_init(&sqlo);
+	seqlock_acquire_val(&sqlo, 1);
+
+	for (i = 0; i < NTHREADS; i++) {
+		seqlock_init(&thr[i].sqlo);
+		seqlock_acquire(&thr[i].sqlo, &sqlo);
+		thr[i].counter = 0;
+		thr[i].nullops = 0;
+
+		pthread_create(&thr[i].pt, NULL, thr1func, &thr[i]);
+	}
+
+	struct testrun *tr;
+
+	for (tr = runs; tr; tr = tr->next)
+		run_tr(tr);
+
+	for (i = 0; i < NTHREADS; i++)
+		pthread_join(thr[i].pt, NULL);
+
+	return 0;
+}
diff --git a/tests/lib/test_atomlist.py b/tests/lib/test_atomlist.py
new file mode 100644
index 0000000000..293d47f316
--- /dev/null
+++ b/tests/lib/test_atomlist.py
@@ -0,0 +1,6 @@
+import frrtest
+
+class TestAtomlist(frrtest.TestMultiOut):
+    program = './test_atomlist'
+
+TestAtomlist.exit_cleanly()
diff --git a/tests/lib/test_seqlock.c b/tests/lib/test_seqlock.c
new file mode 100644
index 0000000000..6b2b9ed8a5
--- /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/lib/test_typelist.c b/tests/lib/test_typelist.c
new file mode 100644
index 0000000000..68ea82ea41
--- /dev/null
+++ b/tests/lib/test_typelist.c
@@ -0,0 +1,142 @@
+/*
+ * Copyright (c) 2016-2018  David Lamparter, for NetDEF, Inc.
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#ifdef HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#include <stdio.h>
+#include <stdint.h>
+#include <stdlib.h>
+#include <inttypes.h>
+#include <string.h>
+#include <unistd.h>
+#include <assert.h>
+
+#define WNO_ATOMLIST_UNSAFE_FIND
+
+#include "typesafe.h"
+#include "atomlist.h"
+#include "memory.h"
+#include "monotime.h"
+
+#include "tests/helpers/c/prng.h"
+
+/* note: these macros are layered 2-deep because that makes the C
+ * preprocessor expand the "type" argument.  Otherwise, you get
+ * "PREDECL_type" instead of "PREDECL_LIST"
+ */
+#define _concat(a, b)		a ## b
+#define concat(a, b)		_concat(a, b)
+#define _str(x)			#x
+#define str(x)			_str(x)
+
+#define _PREDECL(type, ...)	PREDECL_##type(__VA_ARGS__)
+#define PREDECL(type, ...)	_PREDECL(type, __VA_ARGS__)
+#define _DECLARE(type, ...)	DECLARE_##type(__VA_ARGS__)
+#define DECLARE(type, ...)	_DECLARE(type, __VA_ARGS__)
+
+#define _U_SORTLIST_UNIQ	1
+#define _U_SORTLIST_NONUNIQ	0
+#define _U_HASH			1
+#define _U_SKIPLIST_UNIQ	1
+#define _U_SKIPLIST_NONUNIQ	0
+#define _U_RBTREE_UNIQ		1
+#define _U_RBTREE_NONUNIQ	0
+#define _U_ATOMSORT_UNIQ	1
+#define _U_ATOMSORT_NONUNIQ	0
+
+#define _IS_UNIQ(type)		_U_##type
+#define IS_UNIQ(type)		_IS_UNIQ(type)
+
+#define _H_SORTLIST_UNIQ	0
+#define _H_SORTLIST_NONUNIQ	0
+#define _H_HASH			1
+#define _H_SKIPLIST_UNIQ	0
+#define _H_SKIPLIST_NONUNIQ	0
+#define _H_RBTREE_UNIQ		0
+#define _H_RBTREE_NONUNIQ	0
+#define _H_ATOMSORT_UNIQ	0
+#define _H_ATOMSORT_NONUNIQ	0
+
+#define _IS_HASH(type)		_H_##type
+#define IS_HASH(type)		_IS_HASH(type)
+
+static struct timeval ref, ref0;
+
+static void ts_start(void)
+{
+	monotime(&ref0);
+	monotime(&ref);
+}
+static void ts_ref(const char *text)
+{
+	int64_t us;
+	us = monotime_since(&ref, NULL);
+	printf("%7"PRId64"us  %s\n", us, text);
+	monotime(&ref);
+}
+static void ts_end(void)
+{
+	int64_t us;
+	us = monotime_since(&ref0, NULL);
+	printf("%7"PRId64"us  total\n", us);
+}
+
+#define TYPE SORTLIST_UNIQ
+#include "test_typelist.h"
+
+#define TYPE SORTLIST_NONUNIQ
+#include "test_typelist.h"
+
+#define TYPE HASH
+#include "test_typelist.h"
+
+#define TYPE SKIPLIST_UNIQ
+#include "test_typelist.h"
+
+#define TYPE SKIPLIST_NONUNIQ
+#include "test_typelist.h"
+
+#define TYPE RBTREE_UNIQ
+#include "test_typelist.h"
+
+#define TYPE RBTREE_NONUNIQ
+#include "test_typelist.h"
+
+#define TYPE ATOMSORT_UNIQ
+#include "test_typelist.h"
+
+#define TYPE ATOMSORT_NONUNIQ
+#include "test_typelist.h"
+
+int main(int argc, char **argv)
+{
+	srandom(1);
+
+	test_SORTLIST_UNIQ();
+	test_SORTLIST_NONUNIQ();
+	test_HASH();
+	test_SKIPLIST_UNIQ();
+	test_SKIPLIST_NONUNIQ();
+	test_RBTREE_UNIQ();
+	test_RBTREE_NONUNIQ();
+	test_ATOMSORT_UNIQ();
+	test_ATOMSORT_NONUNIQ();
+
+	log_memstats_stderr("test: ");
+	return 0;
+}
diff --git a/tests/lib/test_typelist.h b/tests/lib/test_typelist.h
new file mode 100644
index 0000000000..60a37e84ed
--- /dev/null
+++ b/tests/lib/test_typelist.h
@@ -0,0 +1,272 @@
+/*
+ * Copyright (c) 2019  David Lamparter, for NetDEF, Inc.
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+/* C++ called, they want their templates back */
+#define item		concat(item_, TYPE)
+#define itm		concat(itm_, TYPE)
+#define head		concat(head_, TYPE)
+#define list		concat(TYPE, )
+#define list_head	concat(TYPE, _head)
+#define list_item	concat(TYPE, _item)
+#define list_cmp	concat(TYPE, _cmp)
+#define list_hash	concat(TYPE, _hash)
+#define list_init	concat(TYPE, _init)
+#define list_fini	concat(TYPE, _fini)
+#define list_first	concat(TYPE, _first)
+#define list_next	concat(TYPE, _next)
+#define list_next_safe	concat(TYPE, _next_safe)
+#define list_count	concat(TYPE, _count)
+#define list_add	concat(TYPE, _add)
+#define list_find	concat(TYPE, _find)
+#define list_find_lt	concat(TYPE, _find_lt)
+#define list_find_gteq	concat(TYPE, _find_gteq)
+#define list_del	concat(TYPE, _del)
+#define list_pop	concat(TYPE, _pop)
+
+PREDECL(TYPE, list)
+struct item {
+	uint64_t val;
+	struct list_item itm;
+	int scratchpad;
+};
+
+static int list_cmp(const struct item *a, const struct item *b);
+
+#if IS_HASH(TYPE)
+static uint32_t list_hash(const struct item *a);
+DECLARE(TYPE, list, struct item, itm, list_cmp, list_hash)
+
+static uint32_t list_hash(const struct item *a)
+{
+	/* crappy hash to get some hash collisions */
+	return a->val ^ (a->val << 29) ^ 0x55AA0000U;
+}
+
+#else
+DECLARE(TYPE, list, struct item, itm, list_cmp)
+#endif
+
+static int list_cmp(const struct item *a, const struct item *b)
+{
+	if (a->val > b->val)
+		return 1;
+	if (a->val < b->val)
+		return -1;
+	return 0;
+}
+
+#define NITEM 10000
+struct item itm[NITEM];
+static struct list_head head = concat(INIT_, TYPE)(head);
+
+static void concat(test_, TYPE)(void)
+{
+	size_t i, j, k, l;
+	struct prng *prng;
+	struct item *item, *prev;
+	struct item dummy;
+
+	memset(itm, 0, sizeof(itm));
+	for (i = 0; i < NITEM; i++)
+		itm[i].val = i;
+
+	printf("%s start\n", str(TYPE));
+	ts_start();
+
+	list_init(&head);
+	ts_ref("init");
+
+	assert(list_first(&head) == NULL);
+
+	prng = prng_new(0);
+	k = 0;
+	for (i = 0; i < NITEM; i++) {
+		j = prng_rand(prng) % NITEM;
+		if (itm[j].scratchpad == 0) {
+			list_add(&head, &itm[j]);
+			itm[j].scratchpad = 1;
+			k++;
+		} else
+			assert(list_add(&head, &itm[j]) == &itm[j]);
+	}
+	assert(list_count(&head) == k);
+	assert(list_first(&head) != NULL);
+	ts_ref("fill");
+
+	k = 0;
+	prev = NULL;
+	for_each(list, &head, item) {
+#if IS_HASH(TYPE)
+		/* hash table doesn't give sorting */
+		(void)prev;
+#else
+		assert(!prev || prev->val < item->val);
+#endif
+		prev = item;
+		k++;
+	}
+	assert(list_count(&head) == k);
+	ts_ref("walk");
+
+#if IS_UNIQ(TYPE)
+	prng_free(prng);
+	prng = prng_new(0);
+
+	for (i = 0; i < NITEM; i++) {
+		j = prng_rand(prng) % NITEM;
+		dummy.val = j;
+		assert(list_find(&head, &dummy) == &itm[j]);
+	}
+	ts_ref("find");
+
+	for (i = 0; i < NITEM; i++) {
+		j = prng_rand(prng) % NITEM;
+		memset(&dummy, 0, sizeof(dummy));
+		dummy.val = j;
+		if (itm[j].scratchpad)
+			assert(list_add(&head, &dummy) == &itm[j]);
+		else {
+			assert(list_add(&head, &dummy) == NULL);
+			list_del(&head, &dummy);
+		}
+	}
+	ts_ref("add-dup");
+#else /* !IS_UNIQ(TYPE) */
+	for (i = 0; i < NITEM; i++) {
+		j = prng_rand(prng) % NITEM;
+		memset(&dummy, 0, sizeof(dummy));
+		dummy.val = j;
+
+		list_add(&head, &dummy);
+		if (itm[j].scratchpad) {
+			struct item *lt, *gteq, dummy2;
+
+			assert(list_next(&head, &itm[j]) == &dummy ||
+				list_next(&head, &dummy) == &itm[j]);
+
+			memset(&dummy2, 0, sizeof(dummy));
+			dummy2.val = j;
+			lt = list_find_lt(&head, &dummy2);
+			gteq = list_find_gteq(&head, &dummy2);
+
+			assert(gteq == &itm[j] || gteq == &dummy);
+			if (lt)
+				assert(list_next(&head, lt) == &itm[j] ||
+					list_next(&head, lt) == &dummy);
+			else
+				assert(list_first(&head) == &itm[j] ||
+					list_first(&head) == &dummy);
+		} else if (list_next(&head, &dummy))
+			assert(list_next(&head, &dummy)->val > j);
+		list_del(&head, &dummy);
+	}
+	ts_ref("add-dup+find_{lt,gteq}");
+#endif
+#if !IS_HASH(TYPE)
+	prng_free(prng);
+	prng = prng_new(123456);
+
+	l = 0;
+	for (i = 0; i < NITEM; i++) {
+		struct item *lt, *gteq, *tmp;
+
+		j = prng_rand(prng) % NITEM;
+		dummy.val = j;
+
+		lt = list_find_lt(&head, &dummy);
+		gteq = list_find_gteq(&head, &dummy);
+
+		if (lt) {
+			assert(lt->val < j);
+			tmp = list_next(&head, lt);
+			assert(tmp == gteq);
+			assert(!tmp || tmp->val >= j);
+		} else
+			assert(gteq == list_first(&head));
+		
+		if (gteq)
+			assert(gteq->val >= j);
+	}
+	ts_ref("find_{lt,gteq}");
+#endif /* !IS_HASH */
+
+	prng_free(prng);
+	prng = prng_new(0);
+
+	l = 0;
+	for (i = 0; i < NITEM; i++) {
+		(void)prng_rand(prng);
+		j = prng_rand(prng) % NITEM;
+		if (itm[j].scratchpad == 1) {
+			list_del(&head, &itm[j]);
+			itm[j].scratchpad = 0;
+			l++;
+		}
+	}
+	assert(l + list_count(&head) == k);
+	ts_ref("del");
+
+	for_each_safe(list, &head, item) {
+		assert(item->scratchpad != 0);
+
+		if (item->val & 1) {
+			list_del(&head, item);
+			item->scratchpad = 0;
+			l++;
+		}
+	}
+	assert(l + list_count(&head) == k);
+	ts_ref("for_each_safe+del");
+
+	while ((item = list_pop(&head))) {
+		assert(item->scratchpad != 0);
+
+		item->scratchpad = 0;
+		l++;
+	}
+	assert(l == k);
+	assert(list_count(&head) == 0);
+	assert(list_first(&head) == NULL);
+	ts_ref("pop");
+
+	list_fini(&head);
+	ts_ref("fini");
+	ts_end();
+	printf("%s end\n", str(TYPE));
+}
+
+#undef item
+#undef itm
+#undef head
+#undef list
+#undef list_head
+#undef list_item
+#undef list_cmp
+#undef list_hash
+#undef list_init
+#undef list_fini
+#undef list_first
+#undef list_next
+#undef list_next_safe
+#undef list_count
+#undef list_add
+#undef list_find
+#undef list_find_lt
+#undef list_find_gteq
+#undef list_del
+#undef list_pop
+
+#undef TYPE
diff --git a/tests/lib/test_typelist.py b/tests/lib/test_typelist.py
new file mode 100644
index 0000000000..3b7373ceb8
--- /dev/null
+++ b/tests/lib/test_typelist.py
@@ -0,0 +1,14 @@
+import frrtest
+
+class TestTypelist(frrtest.TestMultiOut):
+    program = './test_typelist'
+
+TestTypelist.onesimple('SORTLIST_UNIQ end')
+TestTypelist.onesimple('SORTLIST_NONUNIQ end')
+TestTypelist.onesimple('HASH end')
+TestTypelist.onesimple('SKIPLIST_UNIQ end')
+TestTypelist.onesimple('SKIPLIST_NONUNIQ end')
+TestTypelist.onesimple('RBTREE_UNIQ end')
+TestTypelist.onesimple('RBTREE_NONUNIQ end')
+TestTypelist.onesimple('ATOMSORT_UNIQ end')
+TestTypelist.onesimple('ATOMSORT_NONUNIQ end')
diff --git a/tests/subdir.am b/tests/subdir.am
index 365fe00cc6..ec5fea705e 100644
--- a/tests/subdir.am
+++ b/tests/subdir.am
@@ -47,6 +47,7 @@ tests/ospf6d/test_lsdb-test_lsdb.$(OBJEXT): tests/ospf6d/test_lsdb_clippy.c
 
 check_PROGRAMS = \
 	tests/lib/cxxcompat \
+	tests/lib/test_atomlist \
 	tests/lib/test_buffer \
 	tests/lib/test_checksum \
 	tests/lib/test_heavy_thread \
@@ -59,12 +60,14 @@ 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 \
 	tests/lib/test_timer_correctness \
 	tests/lib/test_timer_performance \
 	tests/lib/test_ttable \
+	tests/lib/test_typelist \
 	tests/lib/test_zlog \
 	tests/lib/test_graph \
 	tests/lib/cli/test_cli \
@@ -103,6 +106,7 @@ noinst_HEADERS += \
 	tests/helpers/c/prng.h \
 	tests/helpers/c/tests.h \
 	tests/lib/cli/common_cli.h \
+	tests/lib/test_typelist.h \
 	# end
 
 #
@@ -189,6 +193,10 @@ tests_lib_northbound_test_oper_data_CPPFLAGS = $(TESTS_CPPFLAGS)
 tests_lib_northbound_test_oper_data_LDADD = $(ALL_TESTS_LDADD)
 tests_lib_northbound_test_oper_data_SOURCES = tests/lib/northbound/test_oper_data.c
 nodist_tests_lib_northbound_test_oper_data_SOURCES = yang/frr-test-module.yang.c
+tests_lib_test_atomlist_CFLAGS = $(TESTS_CFLAGS)
+tests_lib_test_atomlist_CPPFLAGS = $(TESTS_CPPFLAGS)
+tests_lib_test_atomlist_LDADD = $(ALL_TESTS_LDADD)
+tests_lib_test_atomlist_SOURCES = tests/lib/test_atomlist.c
 tests_lib_test_buffer_CFLAGS = $(TESTS_CFLAGS)
 tests_lib_test_buffer_CPPFLAGS = $(TESTS_CPPFLAGS)
 tests_lib_test_buffer_LDADD = $(ALL_TESTS_LDADD)
@@ -236,6 +244,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)
@@ -264,6 +276,10 @@ tests_lib_test_ttable_CFLAGS = $(TESTS_CFLAGS)
 tests_lib_test_ttable_CPPFLAGS = $(TESTS_CPPFLAGS)
 tests_lib_test_ttable_LDADD = $(ALL_TESTS_LDADD)
 tests_lib_test_ttable_SOURCES = tests/lib/test_ttable.c
+tests_lib_test_typelist_CFLAGS = $(TESTS_CFLAGS)
+tests_lib_test_typelist_CPPFLAGS = $(TESTS_CPPFLAGS)
+tests_lib_test_typelist_LDADD = $(ALL_TESTS_LDADD)
+tests_lib_test_typelist_SOURCES = tests/lib/test_typelist.c tests/helpers/c/prng.c
 tests_lib_test_zlog_CFLAGS = $(TESTS_CFLAGS)
 tests_lib_test_zlog_CPPFLAGS = $(TESTS_CPPFLAGS)
 tests_lib_test_zlog_LDADD = $(ALL_TESTS_LDADD)
@@ -301,6 +317,7 @@ EXTRA_DIST += \
 	tests/lib/northbound/test_oper_data.in \
 	tests/lib/northbound/test_oper_data.py \
 	tests/lib/northbound/test_oper_data.refout \
+	tests/lib/test_atomlist.py \
 	tests/lib/test_nexthop_iter.py \
 	tests/lib/test_ringbuf.py \
 	tests/lib/test_srcdest_table.py \
@@ -310,6 +327,7 @@ EXTRA_DIST += \
 	tests/lib/test_timer_correctness.py \
 	tests/lib/test_ttable.py \
 	tests/lib/test_ttable.refout \
+	tests/lib/test_typelist.py \
 	tests/lib/test_zlog.py \
 	tests/lib/test_graph.py \
 	tests/lib/test_graph.refout \