tests/lib/test_atomlist.c

   1 // SPDX-License-Identifier: ISC
   2 /*
   3  * Copyright (c) 2016-2018  David Lamparter, for NetDEF, Inc.
   4  */
   5
   6 #ifdef HAVE_CONFIG_H
   7 #include "config.h"
   8 #endif
   9
  10 #include <stdio.h>
  11 #include <stdint.h>
  12 #include <inttypes.h>
  13 #include <string.h>
  14 #include <unistd.h>
  15 #include <assert.h>
  16 #include <pthread.h>
  17
  18 #include "atomlist.h"
  19 #include "seqlock.h"
  20 #include "monotime.h"
  21 #include "printfrr.h"
  22
  23 /*
  24  * maybe test:
  25  * - alist_del_hint
  26  * - alist_next_safe
  27  * - asort_del_hint
  28  * - asort_next_safe
  29  */
  30
  31 static struct seqlock sqlo;
  32
  33 PREDECL_ATOMLIST(alist);
  34 PREDECL_ATOMSORT_UNIQ(asort);
  35 struct item {
  36         uint64_t val1;
  37         struct alist_item chain;
  38         struct asort_item sortc;
  39         uint64_t val2;
  40 };
  41 DECLARE_ATOMLIST(alist, struct item, chain);
  42
  43 static int icmp(const struct item *a, const struct item *b);
  44 DECLARE_ATOMSORT_UNIQ(asort, struct item, sortc, icmp);
  45
  46 static int icmp(const struct item *a, const struct item *b)
  47 {
  48         if (a->val1 > b->val1)
  49                 return 1;
  50         if (a->val1 < b->val1)
  51                 return -1;
  52         return 0;
  53 }
  54
  55 #define NITEM 10000
  56 struct item itm[NITEM];
  57
  58 static struct alist_head ahead;
  59 static struct asort_head shead;
  60
  61 #define NTHREADS 4
  62 static struct testthread {
  63         pthread_t pt;
  64         struct seqlock sqlo;
  65         size_t counter, nullops;
  66 } thr[NTHREADS];
  67
  68 struct testrun {
  69         struct testrun *next;
  70         int lineno;
  71         const char *desc;
  72         ssize_t prefill;
  73         bool sorted;
  74         void (*func)(unsigned int offset);
  75 };
  76 struct testrun *runs = NULL;
  77
  78 #define NOCLEAR -1
  79
  80 #define deftestrun(name, _desc, _prefill, _sorted) \
  81 static void trfunc_##name(unsigned int offset); \
  82 struct testrun tr_##name = { \
  83         .desc = _desc, \
  84         .lineno = __LINE__, \
  85         .prefill = _prefill, \
  86         .func = &trfunc_##name, \
  87         .sorted = _sorted }; \
  88 static void __attribute__((constructor)) trsetup_##name(void) \
  89 { \
  90         struct testrun **inspos = &runs; \
  91         while (*inspos && (*inspos)->lineno < tr_##name.lineno) \
  92                 inspos = &(*inspos)->next; \
  93         tr_##name.next = *inspos; \
  94         *inspos = &tr_##name; \
  95 } \
  96 static void trfunc_##name(unsigned int offset) \
  97 { \
  98         size_t i = 0, n = 0;
  99
 100 #define endtestrun \
 101         thr[offset].counter = i; \
 102         thr[offset].nullops = n; \
 103 }
 104
 105 deftestrun(add, "add vs. add", 0, false)
 106         for (; i < NITEM / NTHREADS; i++)
 107                 alist_add_head(&ahead, &itm[i * NTHREADS + offset]);
 108 endtestrun
 109
 110 deftestrun(del, "del vs. del", NOCLEAR, false)
 111         for (; i < NITEM / NTHREADS / 10; i++)
 112                 alist_del(&ahead, &itm[i * NTHREADS + offset]);
 113 endtestrun
 114
 115 deftestrun(addtail, "add_tail vs. add_tail", 0, false)
 116         for (; i < NITEM / NTHREADS; i++)
 117                 alist_add_tail(&ahead, &itm[i * NTHREADS + offset]);
 118 endtestrun
 119
 120 deftestrun(pop, "pop vs. pop", NOCLEAR, false)
 121         for (; i < NITEM / NTHREADS; )
 122                 if (alist_pop(&ahead))
 123                         i++;
 124                 else
 125                         n++;
 126 endtestrun
 127
 128 deftestrun(headN_vs_pop1, "add_head(N) vs. pop(1)", 1, false);
 129         if (offset == 0) {
 130                 struct item *dr = NULL;
 131
 132                 for (i = n = 0; i < NITEM; ) {
 133                         dr = alist_pop(&ahead);
 134                         if (dr)
 135                                 i++;
 136                         else
 137                                 n++;
 138                 }
 139         } else {
 140                 for (i = offset; i < NITEM; i += NTHREADS)
 141                         alist_add_head(&ahead, &itm[i]);
 142                 i = 0;
 143         }
 144 endtestrun
 145
 146 deftestrun(head1_vs_popN, "add_head(1) vs. pop(N)", 0, false);
 147         if (offset < NTHREADS - 1) {
 148                 struct item *dr = NULL;
 149
 150                 for (i = n = 0; i < NITEM / NTHREADS; ) {
 151                         dr = alist_pop(&ahead);
 152                         if (dr)
 153                                 i++;
 154                         else
 155                                 n++;
 156                 }
 157         } else {
 158                 for (i = 0; i < NITEM; i++)
 159                         alist_add_head(&ahead, &itm[i]);
 160                 i = 0;
 161         }
 162 endtestrun
 163
 164 deftestrun(headN_vs_popN, "add_head(N) vs. pop(N)", NTHREADS / 2, false)
 165         if (offset < NTHREADS / 2) {
 166                 struct item *dr = NULL;
 167
 168                 for (i = n = 0; i < NITEM * 2 / NTHREADS; ) {
 169                         dr = alist_pop(&ahead);
 170                         if (dr)
 171                                 i++;
 172                         else
 173                                 n++;
 174                 }
 175         } else {
 176                 for (i = offset; i < NITEM; i += NTHREADS)
 177                         alist_add_head(&ahead, &itm[i]);
 178                 i = 0;
 179         }
 180 endtestrun
 181
 182 deftestrun(tailN_vs_pop1, "add_tail(N) vs. pop(1)", 1, false)
 183         if (offset == 0) {
 184                 struct item *dr = NULL;
 185
 186                 for (i = n = 0; i < NITEM - (NITEM / NTHREADS); ) {
 187                         dr = alist_pop(&ahead);
 188                         if (dr)
 189                                 i++;
 190                         else
 191                                 n++;
 192                 }
 193         } else {
 194                 for (i = offset; i < NITEM; i += NTHREADS)
 195                         alist_add_tail(&ahead, &itm[i]);
 196                 i = 0;
 197         }
 198 endtestrun
 199
 200 deftestrun(tail1_vs_popN, "add_tail(1) vs. pop(N)", 0, false)
 201         if (offset < NTHREADS - 1) {
 202                 struct item *dr = NULL;
 203
 204                 for (i = n = 0; i < NITEM / NTHREADS; ) {
 205                         dr = alist_pop(&ahead);
 206                         if (dr)
 207                                 i++;
 208                         else
 209                                 n++;
 210                 }
 211         } else {
 212                 for (i = 0; i < NITEM; i++)
 213                         alist_add_tail(&ahead, &itm[i]);
 214                 i = 0;
 215         }
 216 endtestrun
 217
 218 deftestrun(sort_add, "add_sort vs. add_sort", 0, true)
 219         for (; i < NITEM / NTHREADS / 10; i++)
 220                 asort_add(&shead, &itm[i * NTHREADS + offset]);
 221 endtestrun
 222
 223 deftestrun(sort_del, "del_sort vs. del_sort", NOCLEAR, true)
 224         for (; i < NITEM / NTHREADS / 10; i++)
 225                 asort_del(&shead, &itm[i * NTHREADS + offset]);
 226 endtestrun
 227
 228 deftestrun(sort_add_del, "add_sort vs. del_sort", NTHREADS / 2, true)
 229         if (offset < NTHREADS / 2) {
 230                 for (; i < NITEM / NTHREADS / 10; i++)
 231                         asort_del(&shead, &itm[i * NTHREADS + offset]);
 232         } else {
 233                 for (; i < NITEM / NTHREADS / 10; i++)
 234                         asort_add(&shead, &itm[i * NTHREADS + offset]);
 235         }
 236 endtestrun
 237
 238 static void *thr1func(void *arg)
 239 {
 240         struct testthread *p = arg;
 241         unsigned int offset = (unsigned int)(p - &thr[0]);
 242         seqlock_val_t sv;
 243         struct testrun *tr;
 244
 245         for (tr = runs; tr; tr = tr->next) {
 246                 sv = seqlock_bump(&p->sqlo) - SEQLOCK_INCR;
 247                 seqlock_wait(&sqlo, sv);
 248
 249                 tr->func(offset);
 250         }
 251         seqlock_bump(&p->sqlo);
 252
 253         return NULL;
 254 }
 255
 256 static void clear_list(size_t prefill)
 257 {
 258         size_t i;
 259
 260         memset(&ahead, 0, sizeof(ahead));
 261         memset(&shead, 0, sizeof(shead));
 262         memset(itm, 0, sizeof(itm));
 263         for (i = 0; i < NITEM; i++) {
 264                 itm[i].val1 = itm[i].val2 = i;
 265                 if ((i % NTHREADS) < prefill) {
 266                         alist_add_tail(&ahead, &itm[i]);
 267                         asort_add(&shead, &itm[i]);
 268                 }
 269         }
 270 }
 271
 272 static void run_tr(struct testrun *tr)
 273 {
 274         const char *desc = tr->desc;
 275         struct timeval tv;
 276         int64_t delta;
 277         seqlock_val_t sv;
 278         size_t c = 0, s = 0, n = 0;
 279         struct item *item, *prev, dummy;
 280
 281         printfrr("[%02u] %35s %s\n", seqlock_cur(&sqlo) >> 2, "", desc);
 282         fflush(stdout);
 283
 284         if (tr->prefill != NOCLEAR)
 285                 clear_list(tr->prefill);
 286
 287         monotime(&tv);
 288         sv = seqlock_bump(&sqlo) - SEQLOCK_INCR;
 289         for (size_t i = 0; i < NTHREADS; i++) {
 290                 seqlock_wait(&thr[i].sqlo, seqlock_cur(&sqlo));
 291                 s += thr[i].counter;
 292                 n += thr[i].nullops;
 293                 thr[i].counter = 0;
 294                 thr[i].nullops = 0;
 295         }
 296
 297         delta = monotime_since(&tv, NULL);
 298         if (tr->sorted) {
 299                 uint64_t prevval = 0;
 300
 301                 frr_each(asort, &shead, item) {
 302                         assert(item->val1 >= prevval);
 303                         prevval = item->val1;
 304                         c++;
 305                 }
 306                 assert(c == asort_count(&shead));
 307         } else {
 308                 prev = &dummy;
 309                 frr_each(alist, &ahead, item) {
 310                         assert(item != prev);
 311                         prev = item;
 312                         c++;
 313                         assert(c <= NITEM);
 314                 }
 315                 assert(c == alist_count(&ahead));
 316         }
 317         printfrr("\033[1A[%02u] %9"PRId64"us c=%5zu s=%5zu n=%5zu %s\n",
 318                 sv >> 2, delta, c, s, n, desc);
 319 }
 320
 321 #ifdef BASIC_TESTS
 322 static void dump(const char *lbl)
 323 {
 324         struct item *item, *safe;
 325         size_t ctr = 0;
 326
 327         printfrr("dumping %s:\n", lbl);
 328         frr_each_safe(alist, &ahead, item) {
 329                 printfrr("%s %3zu %p %3"PRIu64" %3"PRIu64"\n", lbl, ctr++,
 330                                 (void *)item, item->val1, item->val2);
 331         }
 332 }
 333
 334 static void basic_tests(void)
 335 {
 336         size_t i;
 337
 338         memset(&ahead, 0, sizeof(ahead));
 339         memset(itm, 0, sizeof(itm));
 340         for (i = 0; i < NITEM; i++)
 341                 itm[i].val1 = itm[i].val2 = i;
 342
 343         assert(alist_first(&ahead) == NULL);
 344         dump("");
 345         alist_add_head(&ahead, &itm[0]);
 346         dump("");
 347         alist_add_head(&ahead, &itm[1]);
 348         dump("");
 349         alist_add_tail(&ahead, &itm[2]);
 350         dump("");
 351         alist_add_tail(&ahead, &itm[3]);
 352         dump("");
 353         alist_del(&ahead, &itm[1]);
 354         dump("");
 355         printfrr("POP: %p\n", alist_pop(&ahead));
 356         dump("");
 357         printfrr("POP: %p\n", alist_pop(&ahead));
 358         printfrr("POP: %p\n", alist_pop(&ahead));
 359         printfrr("POP: %p\n", alist_pop(&ahead));
 360         printfrr("POP: %p\n", alist_pop(&ahead));
 361         dump("");
 362 }
 363 #else
 364 #define basic_tests() do { } while (0)
 365 #endif
 366
 367 int main(int argc, char **argv)
 368 {
 369         size_t i;
 370
 371         basic_tests();
 372
 373         seqlock_init(&sqlo);
 374         seqlock_acquire_val(&sqlo, SEQLOCK_STARTVAL);
 375
 376         for (i = 0; i < NTHREADS; i++) {
 377                 seqlock_init(&thr[i].sqlo);
 378                 seqlock_acquire(&thr[i].sqlo, &sqlo);
 379                 thr[i].counter = 0;
 380                 thr[i].nullops = 0;
 381
 382                 pthread_create(&thr[i].pt, NULL, thr1func, &thr[i]);
 383         }
 384
 385         struct testrun *tr;
 386
 387         for (tr = runs; tr; tr = tr->next)
 388                 run_tr(tr);
 389
 390         for (i = 0; i < NTHREADS; i++)
 391                 pthread_join(thr[i].pt, NULL);
 392
 393         return 0;
 394 }