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