diff options
Diffstat (limited to 'tests/lib')
| -rw-r--r-- | tests/lib/cxxcompat.c | 3 | ||||
| -rw-r--r-- | tests/lib/test_atomlist.c | 404 | ||||
| -rw-r--r-- | tests/lib/test_atomlist.py | 6 | ||||
| -rw-r--r-- | tests/lib/test_seqlock.c | 122 | ||||
| -rw-r--r-- | tests/lib/test_srcdest_table.c | 4 | ||||
| -rw-r--r-- | tests/lib/test_typelist.c | 169 | ||||
| -rw-r--r-- | tests/lib/test_typelist.h | 562 | ||||
| -rw-r--r-- | tests/lib/test_typelist.py | 19 |
8 files changed, 1286 insertions, 3 deletions
diff --git a/tests/lib/cxxcompat.c b/tests/lib/cxxcompat.c index d10962993d..48fa0ec8a9 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" @@ -93,6 +92,8 @@ #include "lib/table.h" #include "lib/termtable.h" #include "lib/thread.h" +#include "lib/typesafe.h" +#include "lib/typerb.h" #include "lib/vector.h" #include "lib/vlan.h" #include "lib/vrf.h" diff --git a/tests/lib/test_atomlist.c b/tests/lib/test_atomlist.c new file mode 100644 index 0000000000..249fff8edb --- /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; + + frr_each(asort, &shead, item) { + assert(item->val1 >= prevval); + prevval = item->val1; + c++; + } + assert(c == asort_count(&shead)); + } else { + prev = &dummy; + frr_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); + frr_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_srcdest_table.c b/tests/lib/test_srcdest_table.c index 19a40b2184..0fca571d28 100644 --- a/tests/lib/test_srcdest_table.c +++ b/tests/lib/test_srcdest_table.c @@ -81,9 +81,9 @@ static char *format_srcdest(const struct prefix_ipv6 *dst_p, return rv; } -static unsigned int log_key(void *data) +static unsigned int log_key(const void *data) { - struct prefix *hash_entry = data; + const struct prefix *hash_entry = data; struct prefix_ipv6 *dst_p = (struct prefix_ipv6 *)&hash_entry[0]; struct prefix_ipv6 *src_p = (struct prefix_ipv6 *)&hash_entry[1]; unsigned int hash = 0; diff --git a/tests/lib/test_typelist.c b/tests/lib/test_typelist.c new file mode 100644 index 0000000000..2438fb5f08 --- /dev/null +++ b/tests/lib/test_typelist.c @@ -0,0 +1,169 @@ +/* + * 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> +#include <arpa/inet.h> + +#define WNO_ATOMLIST_UNSAFE_FIND + +#include "typesafe.h" +#include "atomlist.h" +#include "memory.h" +#include "monotime.h" +#include "jhash.h" +#include "sha256.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 T_SORTED (1 << 0) +#define T_UNIQ (1 << 1) +#define T_HASH (1 << 2) +#define T_HEAP (1 << 3) +#define T_ATOMIC (1 << 4) + +#define _T_LIST (0) +#define _T_DLIST (0) +#define _T_ATOMLIST (0 | T_ATOMIC) +#define _T_HEAP (T_SORTED | T_HEAP) +#define _T_SORTLIST_UNIQ (T_SORTED | T_UNIQ) +#define _T_SORTLIST_NONUNIQ (T_SORTED) +#define _T_HASH (T_SORTED | T_UNIQ | T_HASH) +#define _T_SKIPLIST_UNIQ (T_SORTED | T_UNIQ) +#define _T_SKIPLIST_NONUNIQ (T_SORTED) +#define _T_RBTREE_UNIQ (T_SORTED | T_UNIQ) +#define _T_RBTREE_NONUNIQ (T_SORTED) +#define _T_ATOMSORT_UNIQ (T_SORTED | T_UNIQ | T_ATOMIC) +#define _T_ATOMSORT_NONUNIQ (T_SORTED | T_ATOMIC) + +#define _T_TYPE(type) _T_##type +#define IS_SORTED(type) (_T_TYPE(type) & T_SORTED) +#define IS_UNIQ(type) (_T_TYPE(type) & T_UNIQ) +#define IS_HASH(type) (_T_TYPE(type) & T_HASH) +#define IS_HEAP(type) (_T_TYPE(type) & T_HEAP) +#define IS_ATOMIC(type) (_T_TYPE(type) & T_ATOMIC) + +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 LIST +#include "test_typelist.h" + +#define TYPE DLIST +#include "test_typelist.h" + +#define TYPE ATOMLIST +#include "test_typelist.h" + +#define TYPE HEAP +#include "test_typelist.h" + +#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 HASH_collisions +#define REALTYPE HASH +#define SHITTY_HASH +#include "test_typelist.h" +#undef SHITTY_HASH + +#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_LIST(); + test_DLIST(); + test_ATOMLIST(); + test_HEAP(); + test_SORTLIST_UNIQ(); + test_SORTLIST_NONUNIQ(); + test_HASH(); + test_HASH_collisions(); + 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..b288f0bd8e --- /dev/null +++ b/tests/lib/test_typelist.h @@ -0,0 +1,562 @@ +/* + * 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_add_head concat(TYPE, _add_head) +#define list_add_tail concat(TYPE, _add_tail) +#define list_add_after concat(TYPE, _add_after) +#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) + +#define ts_hash concat(ts_hash_, TYPE) + +#ifndef REALTYPE +#define REALTYPE TYPE +#endif + +PREDECL(REALTYPE, list) +struct item { + uint64_t val; + struct list_item itm; + int scratchpad; +}; + +#if IS_SORTED(REALTYPE) +static int list_cmp(const struct item *a, const struct item *b); + +#if IS_HASH(REALTYPE) +static uint32_t list_hash(const struct item *a); +DECLARE(REALTYPE, list, struct item, itm, list_cmp, list_hash) + +static uint32_t list_hash(const struct item *a) +{ +#ifdef SHITTY_HASH + /* crappy hash to get some hash collisions */ + return a->val ^ (a->val << 29) ^ 0x55AA0000U; +#else + return jhash_1word(a->val, 0xdeadbeef); +#endif +} + +#else +DECLARE(REALTYPE, 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; +} + +#else /* !IS_SORTED */ +DECLARE(REALTYPE, list, struct item, itm) +#endif + +#define NITEM 10000 +struct item itm[NITEM]; +static struct list_head head = concat(INIT_, REALTYPE)(head); + +static void ts_hash(const char *text, const char *expect) +{ + int64_t us = monotime_since(&ref, NULL); + SHA256_CTX ctx; + struct item *item; + unsigned i = 0; + uint8_t hash[32]; + char hashtext[65]; + uint32_t count; + + count = htonl(list_count(&head)); + + SHA256_Init(&ctx); + SHA256_Update(&ctx, &count, sizeof(count)); + + frr_each (list, &head, item) { + struct { + uint32_t val_upper, val_lower, index; + } hashitem = { + htonl(item->val >> 32), + htonl(item->val & 0xFFFFFFFFULL), + htonl(i), + }; + SHA256_Update(&ctx, &hashitem, sizeof(hashitem)); + i++; + assert(i < count); + } + SHA256_Final(hash, &ctx); + + for (i = 0; i < sizeof(hash); i++) + sprintf(hashtext + i * 2, "%02x", hash[i]); + + printf("%7"PRId64"us %-25s %s%s\n", us, text, + expect ? " " : "*", hashtext); + if (expect && strcmp(expect, hashtext)) { + printf("%-21s %s\n", "EXPECTED:", expect); + assert(0); + } + monotime(&ref); +} +/* hashes will have different item ordering */ +#if IS_HASH(REALTYPE) || IS_HEAP(REALTYPE) +#define ts_hashx(pos, csum) ts_hash(pos, NULL) +#else +#define ts_hashx(pos, csum) ts_hash(pos, csum) +#endif + +static void concat(test_, TYPE)(void) +{ + size_t i, j, k, l; + struct prng *prng; + struct item *item, *prev __attribute__((unused)); + struct item dummy __attribute__((unused)); + + 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); + assert(list_first(&head) == NULL); + + ts_hash("init", "df3f619804a92fdb4057192dc43dd748ea778adc52bc498ce80524c014b81119"); + +#if IS_SORTED(REALTYPE) + 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++; + } +#if !IS_HEAP(REALTYPE) + else + assert(list_add(&head, &itm[j]) == &itm[j]); +#endif + } + assert(list_count(&head) == k); + assert(list_first(&head) != NULL); + ts_hashx("fill", "a538546a6e6ab0484e925940aa8dd02fd934408bbaed8cb66a0721841584d838"); + + k = 0; + prev = NULL; + frr_each(list, &head, item) { +#if IS_HASH(REALTYPE) || IS_HEAP(REALTYPE) + /* 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(REALTYPE) + 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_hashx("add-dup", "a538546a6e6ab0484e925940aa8dd02fd934408bbaed8cb66a0721841584d838"); + +#elif IS_HEAP(REALTYPE) + /* heap - partially sorted. */ + prev = NULL; + l = k / 2; + for (i = 0; i < l; i++) { + item = list_pop(&head); + if (prev) + assert(prev->val < item->val); + item->scratchpad = 0; + k--; + prev = item; + } + ts_hash("pop", NULL); + +#else /* !IS_UNIQ(REALTYPE) && !IS_HEAP(REALTYPE) */ + 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_hash("add-dup+find_{lt,gteq}", "a538546a6e6ab0484e925940aa8dd02fd934408bbaed8cb66a0721841584d838"); +#endif +#if !IS_HASH(REALTYPE) && !IS_HEAP(REALTYPE) + 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_hashx("del", "cb2e5d80f08a803ef7b56c15e981b681adcea214bebc2f55e12e0bfb242b07ca"); + + frr_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_hashx("frr_each_safe+del", "e0beb71dd963a75af05b722b8e71b61b304587d860c8accdc4349067542b86bb"); + +#else /* !IS_SORTED */ + prng = prng_new(0); + k = 0; + for (i = 0; i < NITEM; i++) { + j = prng_rand(prng) % NITEM; + if (itm[j].scratchpad == 0) { + list_add_tail(&head, &itm[j]); + itm[j].scratchpad = 1; + k++; + } + } + assert(list_count(&head) == k); + assert(list_first(&head) != NULL); + ts_hash("fill / add_tail", "eabfcf1413936daaf20965abced95762f45110a6619b84aac7d38481bce4ea19"); + + for (i = 0; i < NITEM / 2; i++) { + j = prng_rand(prng) % NITEM; + if (itm[j].scratchpad == 1) { + list_del(&head, &itm[j]); + itm[j].scratchpad = 0; + k--; + } + } + ts_hash("del-prng", "86d568a95eb429dab3162976c5a5f3f75aabc835932cd682aa280b6923549564"); + + l = 0; + 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_hash("pop", "df3f619804a92fdb4057192dc43dd748ea778adc52bc498ce80524c014b81119"); + + prng_free(prng); + prng = prng_new(0x1e5a2d69); + + k = 0; + for (i = 0; i < NITEM; i++) { + j = prng_rand(prng) % NITEM; + if (itm[j].scratchpad == 0) { + list_add_head(&head, &itm[j]); + itm[j].scratchpad = 1; + k++; + } + } + assert(list_count(&head) == k); + assert(list_first(&head) != NULL); + ts_hash("fill / add_head", "3084d8f8a28b8c756ccc0a92d60d86f6d776273734ddc3f9e1d89526f5ca2795"); + + for (i = 0; i < NITEM / 2; i++) { + j = prng_rand(prng) % NITEM; + if (itm[j].scratchpad == 1) { + list_del(&head, &itm[j]); + itm[j].scratchpad = 0; + k--; + } + } + ts_hash("del-prng", "dc916fa7ea4418792c7c8232d74df2887f9975ead4222f4b977be6bc0b52285e"); + + l = 0; + 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_hash("pop", "df3f619804a92fdb4057192dc43dd748ea778adc52bc498ce80524c014b81119"); + + prng_free(prng); + prng = prng_new(0x692d1e5a); + + k = 0; + for (i = 0; i < NITEM; i++) { + j = prng_rand(prng) % NITEM; + if (itm[j].scratchpad == 0) { + if (prng_rand(prng) & 1) { + list_add_tail(&head, &itm[j]); + } else { + list_add_head(&head, &itm[j]); + } + itm[j].scratchpad = 1; + k++; + } + } + assert(list_count(&head) == k); + assert(list_first(&head) != NULL); + ts_hash("fill / add_{head,tail}", "93fa180a575c96e4b6c3775c2de7843ee3254dd6ed5af699bbe155f994114b06"); + + for (i = 0; i < NITEM * 3; i++) { + int op = prng_rand(prng); + j = prng_rand(prng) % NITEM; + + if (op & 1) { + /* delete or pop */ + if (op & 2) { + item = list_pop(&head); + if (!item) + continue; + } else { + item = &itm[j]; + if (item->scratchpad == 0) + continue; + list_del(&head, item); + } + item->scratchpad = 0; + k--; + } else { + item = &itm[j]; + if (item->scratchpad != 0) + continue; + + item->scratchpad = 1; + k++; + + switch ((op >> 1) & 1) { + case 0: + list_add_head(&head, item); + break; + case 1: + list_add_tail(&head, item); + break; + default: + assert(0); + } + } + } + assert(list_count(&head) == k); + assert(list_first(&head) != NULL); + ts_hash("prng add/del", "4909f31d06bb006efca4dfeebddb8de071733ddf502f89b6d532155208bbc6df"); + +#if !IS_ATOMIC(REALTYPE) + /* variant with add_after */ + + for (i = 0; i < NITEM * 3; i++) { + int op = prng_rand(prng); + j = prng_rand(prng) % NITEM; + + if (op & 1) { + /* delete or pop */ + if (op & 2) { + item = list_pop(&head); + if (!item) + continue; + } else { + item = &itm[j]; + if (item->scratchpad == 0) + continue; + list_del(&head, item); + } + item->scratchpad = 0; + k--; + } else { + item = &itm[j]; + if (item->scratchpad != 0) + continue; + + item->scratchpad = 1; + k++; + + switch ((op >> 1) & 3) { + case 0: + list_add_head(&head, item); + break; + case 1: + list_add_tail(&head, item); + break; + case 2: + case 3: + prev = NULL; + l = 0; + do { + j = prng_rand(prng) % NITEM; + prev = &itm[j]; + if (prev->scratchpad == 0 + || prev == item) + prev = NULL; + l++; + } while (!prev && l < 10); + list_add_after(&head, prev, item); + break; + default: + assert(0); + } + } + } + assert(list_count(&head) == k); + assert(list_first(&head) != NULL); + ts_hash("prng add/after/del", "84c5fc83294eabebb9808ccbba32a303c4fca084db87ed1277d2bae1f8c5bee4"); +#endif + + l = 0; +#endif + + 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_hash("pop", "df3f619804a92fdb4057192dc43dd748ea778adc52bc498ce80524c014b81119"); + + list_fini(&head); + ts_ref("fini"); + ts_end(); + printf("%s end\n", str(TYPE)); +} + +#undef ts_hashx + +#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_add_head +#undef list_add_tail +#undef list_add_after +#undef list_find +#undef list_find_lt +#undef list_find_gteq +#undef list_del +#undef list_pop + +#undef REALTYPE +#undef TYPE diff --git a/tests/lib/test_typelist.py b/tests/lib/test_typelist.py new file mode 100644 index 0000000000..0b3c743971 --- /dev/null +++ b/tests/lib/test_typelist.py @@ -0,0 +1,19 @@ +import frrtest + +class TestTypelist(frrtest.TestMultiOut): + program = './test_typelist' + +TestTypelist.onesimple('LIST end') +TestTypelist.onesimple('DLIST end') +TestTypelist.onesimple('ATOMLIST end') +TestTypelist.onesimple('HEAP end') +TestTypelist.onesimple('SORTLIST_UNIQ end') +TestTypelist.onesimple('SORTLIST_NONUNIQ end') +TestTypelist.onesimple('HASH end') +TestTypelist.onesimple('HASH_collisions 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') |