tests/lib/test_atomlist.c

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