src/vppinfra/test_tw_timer.c

   1 #include <vppinfra/time.h>
   2 #include <vppinfra/cache.h>
   3 #include <vppinfra/error.h>
   4 #include <vppinfra/tw_timer_2t_1w_2048sl.h>
   5 #include <vppinfra/tw_timer_16t_2w_512sl.h>
   6 #include <vppinfra/tw_timer_4t_3w_256sl.h>
   7 #include <vppinfra/tw_timer_1t_3w_1024sl_ov.h>
   8
   9 typedef struct
  10 {
  11   /** Handle returned from tw_start_timer */
  12   u32 stop_timer_handle;
  13
  14   /** Test item should expire at this clock tick */
  15   u64 expected_to_expire;
  16 } tw_timer_test_elt_t;
  17
  18 typedef struct
  19 {
  20   /** Pool of test objects */
  21   tw_timer_test_elt_t *test_elts;
  22
  23   /** The single-wheel */
  24   tw_timer_wheel_2t_1w_2048sl_t single_wheel;
  25
  26   /** The double-wheel */
  27   tw_timer_wheel_16t_2w_512sl_t double_wheel;
  28
  29   /* The triple wheel */
  30   tw_timer_wheel_4t_3w_256sl_t triple_wheel;
  31
  32   /* The triple wheel with overflow vector */
  33   tw_timer_wheel_1t_3w_1024sl_ov_t triple_ov_wheel;
  34
  35   /** random number seed */
  36   u64 seed;
  37
  38   /** number of timers */
  39   u32 ntimers;
  40
  41   /** number of "churn" iterations */
  42   u32 niter;
  43
  44   /** number of clock ticks per churn iteration */
  45   u32 ticks_per_iter;
  46
  47   /** cpu timer */
  48   clib_time_t clib_time;
  49 } tw_timer_test_main_t;
  50
  51 tw_timer_test_main_t tw_timer_test_main;
  52
  53 static void
  54 run_single_wheel (tw_timer_wheel_2t_1w_2048sl_t * tw, u32 n_ticks)
  55 {
  56   u32 i;
  57   f64 now = tw->last_run_time + 1.01;
  58
  59   for (i = 0; i < n_ticks; i++)
  60     {
  61       tw_timer_expire_timers_2t_1w_2048sl (tw, now);
  62       now += 1.01;
  63     }
  64 }
  65
  66 static void
  67 run_double_wheel (tw_timer_wheel_16t_2w_512sl_t * tw, u32 n_ticks)
  68 {
  69   u32 i;
  70   f64 now = tw->last_run_time + 1.01;
  71
  72   for (i = 0; i < n_ticks; i++)
  73     {
  74       tw_timer_expire_timers_16t_2w_512sl (tw, now);
  75       now += 1.01;
  76     }
  77 }
  78
  79 static void
  80 run_triple_wheel (tw_timer_wheel_4t_3w_256sl_t * tw, u32 n_ticks)
  81 {
  82   u32 i;
  83   f64 now = tw->last_run_time + 1.01;
  84
  85   for (i = 0; i < n_ticks; i++)
  86     {
  87       tw_timer_expire_timers_4t_3w_256sl (tw, now);
  88       now += 1.01;
  89     }
  90 }
  91
  92 static void
  93 run_triple_ov_wheel (tw_timer_wheel_1t_3w_1024sl_ov_t * tw, u32 n_ticks)
  94 {
  95   u32 i;
  96   f64 now = tw->last_run_time + 1.01;
  97
  98   for (i = 0; i < n_ticks; i++)
  99     {
 100       tw_timer_expire_timers_1t_3w_1024sl_ov (tw, now);
 101       now += 1.01;
 102     }
 103 }
 104
 105 static void
 106 expired_timer_single_callback (u32 * expired_timers)
 107 {
 108   int i;
 109   u32 pool_index, timer_id;
 110   tw_timer_test_elt_t *e;
 111   tw_timer_test_main_t *tm = &tw_timer_test_main;
 112
 113   for (i = 0; i < vec_len (expired_timers); i++)
 114     {
 115       pool_index = expired_timers[i] & 0x7FFFFFFF;
 116       timer_id = expired_timers[i] >> 31;
 117
 118       ASSERT (timer_id == 1);
 119
 120       e = pool_elt_at_index (tm->test_elts, pool_index);
 121
 122       if (e->expected_to_expire != tm->single_wheel.current_tick)
 123         {
 124           fformat (stdout, "[%d] expired at %lld not %lld\n",
 125                    e - tm->test_elts, tm->single_wheel.current_tick,
 126                    e->expected_to_expire);
 127         }
 128       pool_put (tm->test_elts, e);
 129     }
 130 }
 131
 132 static void
 133 expired_timer_double_callback (u32 * expired_timers)
 134 {
 135   int i;
 136   u32 pool_index, timer_id;
 137   tw_timer_test_elt_t *e;
 138   tw_timer_test_main_t *tm = &tw_timer_test_main;
 139
 140   for (i = 0; i < vec_len (expired_timers); i++)
 141     {
 142       pool_index = expired_timers[i] & 0x0FFFFFFF;
 143       timer_id = expired_timers[i] >> 28;
 144
 145       ASSERT (timer_id == 14);
 146
 147       e = pool_elt_at_index (tm->test_elts, pool_index);
 148
 149       if (e->expected_to_expire != tm->double_wheel.current_tick)
 150         {
 151           fformat (stdout, "[%d] expired at %lld not %lld\n",
 152                    e - tm->test_elts, tm->double_wheel.current_tick,
 153                    e->expected_to_expire);
 154         }
 155       pool_put (tm->test_elts, e);
 156     }
 157 }
 158
 159 static void
 160 expired_timer_triple_callback (u32 * expired_timers)
 161 {
 162   int i;
 163   u32 pool_index, timer_id;
 164   tw_timer_test_elt_t *e;
 165   tw_timer_test_main_t *tm = &tw_timer_test_main;
 166
 167   for (i = 0; i < vec_len (expired_timers); i++)
 168     {
 169       pool_index = expired_timers[i] & 0x3FFFFFFF;
 170       timer_id = expired_timers[i] >> 30;
 171
 172       ASSERT (timer_id == 3);
 173
 174       e = pool_elt_at_index (tm->test_elts, pool_index);
 175
 176       if (e->expected_to_expire != tm->triple_wheel.current_tick)
 177         {
 178           fformat (stdout, "[%d] expired at %lld not %lld\n",
 179                    e - tm->test_elts, tm->triple_wheel.current_tick,
 180                    e->expected_to_expire);
 181         }
 182       pool_put (tm->test_elts, e);
 183     }
 184 }
 185
 186 static void
 187 expired_timer_triple_ov_callback (u32 * expired_timers)
 188 {
 189   int i;
 190   u32 pool_index;
 191   tw_timer_test_elt_t *e;
 192   tw_timer_test_main_t *tm = &tw_timer_test_main;
 193
 194   for (i = 0; i < vec_len (expired_timers); i++)
 195     {
 196       pool_index = expired_timers[i];
 197
 198       e = pool_elt_at_index (tm->test_elts, pool_index);
 199
 200       if (e->expected_to_expire != tm->triple_ov_wheel.current_tick)
 201         {
 202           fformat (stdout, "[%d] expired at %lld not %lld\n",
 203                    e - tm->test_elts, tm->triple_ov_wheel.current_tick,
 204                    e->expected_to_expire);
 205         }
 206       pool_put (tm->test_elts, e);
 207     }
 208 }
 209
 210 static clib_error_t *
 211 test2_single (tw_timer_test_main_t * tm)
 212 {
 213   u32 i, j;
 214   tw_timer_test_elt_t *e;
 215   u32 initial_wheel_offset;
 216   u64 expiration_time;
 217   u32 max_expiration_time = 0;
 218   u32 *deleted_indices = 0;
 219   u32 adds = 0, deletes = 0;
 220   f64 before, after;
 221
 222   clib_time_init (&tm->clib_time);
 223
 224   tw_timer_wheel_init_2t_1w_2048sl (&tm->single_wheel,
 225                                     expired_timer_single_callback,
 226                                     1.0 /* timer interval */ , ~0);
 227
 228   /* Prime offset */
 229   initial_wheel_offset = 757;
 230
 231   run_single_wheel (&tm->single_wheel, initial_wheel_offset);
 232
 233   fformat (stdout, "initial wheel time %d, fast index %d\n",
 234            tm->single_wheel.current_tick,
 235            tm->single_wheel.current_index[TW_TIMER_RING_FAST]);
 236
 237   initial_wheel_offset = tm->single_wheel.current_tick;
 238
 239   fformat (stdout,
 240            "test %d timers, %d iter, %d ticks per iter, 0x%llx seed\n",
 241            tm->ntimers, tm->niter, tm->ticks_per_iter, tm->seed);
 242
 243   before = clib_time_now (&tm->clib_time);
 244
 245   /* Prime the pump */
 246   for (i = 0; i < tm->ntimers; i++)
 247     {
 248       pool_get (tm->test_elts, e);
 249       memset (e, 0, sizeof (*e));
 250
 251       do
 252         {
 253           expiration_time = random_u64 (&tm->seed) & (2047);
 254         }
 255       while (expiration_time == 0);
 256
 257       if (expiration_time > max_expiration_time)
 258         max_expiration_time = expiration_time;
 259
 260       e->expected_to_expire = expiration_time + initial_wheel_offset;
 261       e->stop_timer_handle =
 262         tw_timer_start_2t_1w_2048sl (&tm->single_wheel, e - tm->test_elts,
 263                                      1 /* timer id */ ,
 264                                      expiration_time);
 265     }
 266
 267   adds += i;
 268
 269   for (i = 0; i < tm->niter; i++)
 270     {
 271       run_single_wheel (&tm->single_wheel, tm->ticks_per_iter);
 272
 273       j = 0;
 274       vec_reset_length (deleted_indices);
 275       /* *INDENT-OFF* */
 276       pool_foreach (e, tm->test_elts,
 277       ({
 278         tw_timer_stop_2t_1w_2048sl (&tm->single_wheel, e->stop_timer_handle);
 279         vec_add1 (deleted_indices, e - tm->test_elts);
 280         if (++j >= tm->ntimers / 4)
 281           goto del_and_re_add;
 282       }));
 283       /* *INDENT-ON* */
 284
 285     del_and_re_add:
 286       for (j = 0; j < vec_len (deleted_indices); j++)
 287         {
 288           pool_put_index (tm->test_elts, deleted_indices[j]);
 289         }
 290
 291       deletes += j;
 292
 293       for (j = 0; j < tm->ntimers / 4; j++)
 294         {
 295           pool_get (tm->test_elts, e);
 296           memset (e, 0, sizeof (*e));
 297
 298           do
 299             {
 300               expiration_time = random_u64 (&tm->seed) & (2047);
 301             }
 302           while (expiration_time == 0);
 303
 304           if (expiration_time > max_expiration_time)
 305             max_expiration_time = expiration_time;
 306
 307           e->expected_to_expire =
 308             expiration_time + tm->single_wheel.current_tick;
 309           e->stop_timer_handle = tw_timer_start_2t_1w_2048sl
 310             (&tm->single_wheel, e - tm->test_elts, 1 /* timer id */ ,
 311              expiration_time);
 312         }
 313       adds += j;
 314     }
 315
 316   vec_free (deleted_indices);
 317
 318   run_single_wheel (&tm->single_wheel, max_expiration_time + 1);
 319
 320   after = clib_time_now (&tm->clib_time);
 321
 322   fformat (stdout, "%d adds, %d deletes, %d ticks\n", adds, deletes,
 323            tm->single_wheel.current_tick);
 324   fformat (stdout, "test ran %.2f seconds, %.2f ops/second\n",
 325            (after - before),
 326            ((f64) adds + (f64) deletes +
 327             (f64) tm->single_wheel.current_tick) / (after - before));
 328
 329   if (pool_elts (tm->test_elts))
 330     fformat (stdout, "Note: %d elements remain in pool\n",
 331              pool_elts (tm->test_elts));
 332
 333   /* *INDENT-OFF* */
 334   pool_foreach (e, tm->test_elts,
 335   ({
 336     fformat (stdout, "[%d] expected to expire %d\n",
 337              e - tm->test_elts,
 338              e->expected_to_expire);
 339   }));
 340   /* *INDENT-ON* */
 341
 342   pool_free (tm->test_elts);
 343   tw_timer_wheel_free_2t_1w_2048sl (&tm->single_wheel);
 344   return 0;
 345 }
 346
 347 static clib_error_t *
 348 test2_double (tw_timer_test_main_t * tm)
 349 {
 350   u32 i, j;
 351   tw_timer_test_elt_t *e;
 352   u32 initial_wheel_offset;
 353   u32 expiration_time;
 354   u32 max_expiration_time = 0;
 355   u32 *deleted_indices = 0;
 356   u32 adds = 0, deletes = 0;
 357   f64 before, after;
 358
 359   clib_time_init (&tm->clib_time);
 360
 361   tw_timer_wheel_init_16t_2w_512sl (&tm->double_wheel,
 362                                     expired_timer_double_callback,
 363                                     1.0 /* timer interval */ , ~0);
 364
 365   /* Prime offset */
 366   initial_wheel_offset = 7577;
 367
 368   run_double_wheel (&tm->double_wheel, initial_wheel_offset);
 369
 370   fformat (stdout, "initial wheel time %d, fast index %d slow index %d\n",
 371            tm->double_wheel.current_tick,
 372            tm->double_wheel.current_index[TW_TIMER_RING_FAST],
 373            tm->double_wheel.current_index[TW_TIMER_RING_SLOW]);
 374
 375   initial_wheel_offset = tm->double_wheel.current_tick;
 376
 377   fformat (stdout,
 378            "test %d timers, %d iter, %d ticks per iter, 0x%llx seed\n",
 379            tm->ntimers, tm->niter, tm->ticks_per_iter, tm->seed);
 380
 381   before = clib_time_now (&tm->clib_time);
 382
 383   /* Prime the pump */
 384   for (i = 0; i < tm->ntimers; i++)
 385     {
 386       pool_get (tm->test_elts, e);
 387       memset (e, 0, sizeof (*e));
 388
 389       do
 390         {
 391           expiration_time = random_u64 (&tm->seed) & ((1 << 17) - 1);
 392         }
 393       while (expiration_time == 0);
 394
 395       if (expiration_time > max_expiration_time)
 396         max_expiration_time = expiration_time;
 397
 398       e->expected_to_expire = expiration_time + initial_wheel_offset;
 399
 400       e->stop_timer_handle =
 401         tw_timer_start_16t_2w_512sl (&tm->double_wheel, e - tm->test_elts,
 402                                      14 /* timer id */ ,
 403                                      expiration_time);
 404     }
 405
 406   adds += i;
 407
 408   for (i = 0; i < tm->niter; i++)
 409     {
 410       run_double_wheel (&tm->double_wheel, tm->ticks_per_iter);
 411
 412       j = 0;
 413       vec_reset_length (deleted_indices);
 414       /* *INDENT-OFF* */
 415       pool_foreach (e, tm->test_elts,
 416       ({
 417         tw_timer_stop_16t_2w_512sl (&tm->double_wheel, e->stop_timer_handle);
 418         vec_add1 (deleted_indices, e - tm->test_elts);
 419         if (++j >= tm->ntimers / 4)
 420           goto del_and_re_add;
 421       }));
 422       /* *INDENT-ON* */
 423
 424     del_and_re_add:
 425       for (j = 0; j < vec_len (deleted_indices); j++)
 426         pool_put_index (tm->test_elts, deleted_indices[j]);
 427
 428       deletes += j;
 429
 430       for (j = 0; j < tm->ntimers / 4; j++)
 431         {
 432           pool_get (tm->test_elts, e);
 433           memset (e, 0, sizeof (*e));
 434
 435           do
 436             {
 437               expiration_time = random_u64 (&tm->seed) & ((1 << 17) - 1);
 438             }
 439           while (expiration_time == 0);
 440
 441           if (expiration_time > max_expiration_time)
 442             max_expiration_time = expiration_time;
 443
 444           e->expected_to_expire = expiration_time +
 445             tm->double_wheel.current_tick;
 446
 447           e->stop_timer_handle = tw_timer_start_16t_2w_512sl
 448             (&tm->double_wheel, e - tm->test_elts, 14 /* timer id */ ,
 449              expiration_time);
 450         }
 451       adds += j;
 452     }
 453
 454   vec_free (deleted_indices);
 455
 456   run_double_wheel (&tm->double_wheel, max_expiration_time + 1);
 457
 458   after = clib_time_now (&tm->clib_time);
 459
 460   fformat (stdout, "%d adds, %d deletes, %d ticks\n", adds, deletes,
 461            tm->double_wheel.current_tick);
 462   fformat (stdout, "test ran %.2f seconds, %.2f ops/second\n",
 463            (after - before),
 464            ((f64) adds + (f64) deletes +
 465             (f64) tm->double_wheel.current_tick) / (after - before));
 466
 467   if (pool_elts (tm->test_elts))
 468     fformat (stdout, "Note: %d elements remain in pool\n",
 469              pool_elts (tm->test_elts));
 470
 471   /* *INDENT-OFF* */
 472   pool_foreach (e, tm->test_elts,
 473   ({
 474     fformat (stdout, "[%d] expected to expire %d\n",
 475              e - tm->test_elts,
 476              e->expected_to_expire);
 477   }));
 478   /* *INDENT-ON* */
 479
 480   pool_free (tm->test_elts);
 481   tw_timer_wheel_free_16t_2w_512sl (&tm->double_wheel);
 482   return 0;
 483 }
 484
 485 static clib_error_t *
 486 test2_triple (tw_timer_test_main_t * tm)
 487 {
 488   u32 i, j;
 489   tw_timer_test_elt_t *e;
 490   u32 initial_wheel_offset = 0;
 491   u32 expiration_time;
 492   u32 max_expiration_time = 0;
 493   u32 *deleted_indices = 0;
 494   u32 adds = 0, deletes = 0;
 495   f64 before, after;
 496
 497   clib_time_init (&tm->clib_time);
 498
 499   tw_timer_wheel_init_4t_3w_256sl (&tm->triple_wheel,
 500                                    expired_timer_triple_callback,
 501                                    1.0 /* timer interval */ , ~0);
 502
 503
 504   /* Prime offset */
 505   initial_wheel_offset = 75700;
 506   run_triple_wheel (&tm->triple_wheel, initial_wheel_offset);
 507
 508   fformat (stdout,
 509            "initial wheel time %d, fi %d si %d gi %d\n",
 510            tm->triple_wheel.current_tick,
 511            tm->triple_wheel.current_index[TW_TIMER_RING_FAST],
 512            tm->triple_wheel.current_index[TW_TIMER_RING_SLOW],
 513            tm->triple_wheel.current_index[TW_TIMER_RING_GLACIER]);
 514
 515   initial_wheel_offset = tm->triple_wheel.current_tick;
 516
 517   fformat (stdout,
 518            "test %d timers, %d iter, %d ticks per iter, 0x%llx seed\n",
 519            tm->ntimers, tm->niter, tm->ticks_per_iter, tm->seed);
 520
 521   before = clib_time_now (&tm->clib_time);
 522
 523   /* Prime the pump */
 524   for (i = 0; i < tm->ntimers; i++)
 525     {
 526       pool_get (tm->test_elts, e);
 527       memset (e, 0, sizeof (*e));
 528
 529       do
 530         {
 531           expiration_time = random_u64 (&tm->seed) & ((1 << 17) - 1);
 532         }
 533       while (expiration_time == 0);
 534
 535       if (expiration_time > max_expiration_time)
 536         max_expiration_time = expiration_time;
 537
 538       e->expected_to_expire = expiration_time + initial_wheel_offset;
 539
 540       e->stop_timer_handle =
 541         tw_timer_start_4t_3w_256sl (&tm->triple_wheel, e - tm->test_elts,
 542                                     3 /* timer id */ ,
 543                                     expiration_time);
 544     }
 545
 546   adds += i;
 547
 548   for (i = 0; i < tm->niter; i++)
 549     {
 550       run_triple_wheel (&tm->triple_wheel, tm->ticks_per_iter);
 551
 552       j = 0;
 553       vec_reset_length (deleted_indices);
 554       /* *INDENT-OFF* */
 555       pool_foreach (e, tm->test_elts,
 556       ({
 557         tw_timer_stop_4t_3w_256sl (&tm->triple_wheel, e->stop_timer_handle);
 558         vec_add1 (deleted_indices, e - tm->test_elts);
 559         if (++j >= tm->ntimers / 4)
 560           goto del_and_re_add;
 561       }));
 562       /* *INDENT-ON* */
 563
 564     del_and_re_add:
 565       for (j = 0; j < vec_len (deleted_indices); j++)
 566         pool_put_index (tm->test_elts, deleted_indices[j]);
 567
 568       deletes += j;
 569
 570       for (j = 0; j < tm->ntimers / 4; j++)
 571         {
 572           pool_get (tm->test_elts, e);
 573           memset (e, 0, sizeof (*e));
 574
 575           do
 576             {
 577               expiration_time = random_u64 (&tm->seed) & ((1 << 17) - 1);
 578             }
 579           while (expiration_time == 0);
 580
 581           if (expiration_time > max_expiration_time)
 582             max_expiration_time = expiration_time;
 583
 584           e->expected_to_expire = expiration_time +
 585             tm->triple_wheel.current_tick;
 586
 587           e->stop_timer_handle = tw_timer_start_4t_3w_256sl
 588             (&tm->triple_wheel, e - tm->test_elts, 3 /* timer id */ ,
 589              expiration_time);
 590         }
 591       adds += j;
 592     }
 593
 594   vec_free (deleted_indices);
 595
 596   run_triple_wheel (&tm->triple_wheel, max_expiration_time + 1);
 597
 598   after = clib_time_now (&tm->clib_time);
 599
 600   fformat (stdout, "%d adds, %d deletes, %d ticks\n", adds, deletes,
 601            tm->triple_wheel.current_tick);
 602   fformat (stdout, "test ran %.2f seconds, %.2f ops/second\n",
 603            (after - before),
 604            ((f64) adds + (f64) deletes +
 605             (f64) tm->triple_wheel.current_tick) / (after - before));
 606
 607   if (pool_elts (tm->test_elts))
 608     fformat (stdout, "Note: %d elements remain in pool\n",
 609              pool_elts (tm->test_elts));
 610
 611   /* *INDENT-OFF* */
 612   pool_foreach (e, tm->test_elts,
 613   ({
 614     fformat (stdout, "[%d] expected to expire %d\n",
 615              e - tm->test_elts,
 616              e->expected_to_expire);
 617   }));
 618   /* *INDENT-ON* */
 619
 620   pool_free (tm->test_elts);
 621   tw_timer_wheel_free_4t_3w_256sl (&tm->triple_wheel);
 622   return 0;
 623 }
 624
 625 static clib_error_t *
 626 test2_triple_ov (tw_timer_test_main_t * tm)
 627 {
 628   u32 i, j;
 629   tw_timer_test_elt_t *e;
 630   u32 initial_wheel_offset = 0;
 631   u32 expiration_time;
 632   u32 max_expiration_time = 0;
 633   u32 *deleted_indices = 0;
 634   u32 adds = 0, deletes = 0;
 635   f64 before, after;
 636
 637   clib_time_init (&tm->clib_time);
 638
 639   tw_timer_wheel_init_1t_3w_1024sl_ov (&tm->triple_ov_wheel,
 640                                        expired_timer_triple_ov_callback,
 641                                        1.0 /* timer interval */ , ~0);
 642
 643
 644   /* Prime offset */
 645   initial_wheel_offset = 75700;
 646   run_triple_ov_wheel (&tm->triple_ov_wheel, initial_wheel_offset);
 647
 648   fformat (stdout,
 649            "initial wheel time %d, fi %d si %d gi %d\n",
 650            tm->triple_ov_wheel.current_tick,
 651            tm->triple_ov_wheel.current_index[TW_TIMER_RING_FAST],
 652            tm->triple_ov_wheel.current_index[TW_TIMER_RING_SLOW],
 653            tm->triple_ov_wheel.current_index[TW_TIMER_RING_GLACIER]);
 654
 655   initial_wheel_offset = tm->triple_ov_wheel.current_tick;
 656
 657   fformat (stdout,
 658            "test %d timers, %d iter, %d ticks per iter, 0x%llx seed\n",
 659            tm->ntimers, tm->niter, tm->ticks_per_iter, tm->seed);
 660
 661   before = clib_time_now (&tm->clib_time);
 662
 663   /* Prime the pump */
 664   for (i = 0; i < tm->ntimers; i++)
 665     {
 666       pool_get (tm->test_elts, e);
 667       memset (e, 0, sizeof (*e));
 668
 669       do
 670         {
 671           expiration_time = random_u64 (&tm->seed) & ((1 << 17) - 1);
 672         }
 673       while (expiration_time == 0);
 674
 675       if (expiration_time > max_expiration_time)
 676         max_expiration_time = expiration_time;
 677
 678       e->expected_to_expire = expiration_time + initial_wheel_offset;
 679
 680       e->stop_timer_handle =
 681         tw_timer_start_1t_3w_1024sl_ov (&tm->triple_ov_wheel,
 682                                         e - tm->test_elts, 0 /* timer id */ ,
 683                                         expiration_time);
 684     }
 685
 686   adds += i;
 687
 688   for (i = 0; i < tm->niter; i++)
 689     {
 690       run_triple_ov_wheel (&tm->triple_ov_wheel, tm->ticks_per_iter);
 691
 692       j = 0;
 693       vec_reset_length (deleted_indices);
 694       /* *INDENT-OFF* */
 695       pool_foreach (e, tm->test_elts,
 696       ({
 697         tw_timer_stop_1t_3w_1024sl_ov (&tm->triple_ov_wheel,
 698                                        e->stop_timer_handle);
 699         vec_add1 (deleted_indices, e - tm->test_elts);
 700         if (++j >= tm->ntimers / 4)
 701           goto del_and_re_add;
 702       }));
 703       /* *INDENT-ON* */
 704
 705     del_and_re_add:
 706       for (j = 0; j < vec_len (deleted_indices); j++)
 707         pool_put_index (tm->test_elts, deleted_indices[j]);
 708
 709       deletes += j;
 710
 711       for (j = 0; j < tm->ntimers / 4; j++)
 712         {
 713           pool_get (tm->test_elts, e);
 714           memset (e, 0, sizeof (*e));
 715
 716           do
 717             {
 718               expiration_time = random_u64 (&tm->seed) & ((1 << 17) - 1);
 719             }
 720           while (expiration_time == 0);
 721
 722           if (expiration_time > max_expiration_time)
 723             max_expiration_time = expiration_time;
 724
 725           e->expected_to_expire = expiration_time +
 726             tm->triple_ov_wheel.current_tick;
 727
 728           e->stop_timer_handle = tw_timer_start_1t_3w_1024sl_ov
 729             (&tm->triple_ov_wheel, e - tm->test_elts, 0 /* timer id */ ,
 730              expiration_time);
 731         }
 732       adds += j;
 733     }
 734
 735   vec_free (deleted_indices);
 736
 737   run_triple_ov_wheel (&tm->triple_ov_wheel, max_expiration_time + 1);
 738
 739   after = clib_time_now (&tm->clib_time);
 740
 741   fformat (stdout, "%d adds, %d deletes, %d ticks\n", adds, deletes,
 742            tm->triple_ov_wheel.current_tick);
 743   fformat (stdout, "test ran %.2f seconds, %.2f ops/second\n",
 744            (after - before),
 745            ((f64) adds + (f64) deletes +
 746             (f64) tm->triple_ov_wheel.current_tick) / (after - before));
 747
 748   if (pool_elts (tm->test_elts))
 749     fformat (stdout, "Note: %d elements remain in pool\n",
 750              pool_elts (tm->test_elts));
 751
 752   /* *INDENT-OFF* */
 753   pool_foreach (e, tm->test_elts,
 754   ({
 755     TWT (tw_timer) * t;
 756
 757     fformat (stdout, "[%d] expected to expire %d\n",
 758              e - tm->test_elts,
 759              e->expected_to_expire);
 760     t = pool_elt_at_index (tm->triple_ov_wheel.timers, e->stop_timer_handle);
 761     fformat (stdout, "  expiration_time %lld\n", t->expiration_time);
 762   }));
 763   /* *INDENT-ON* */
 764
 765   pool_free (tm->test_elts);
 766   tw_timer_wheel_free_1t_3w_1024sl_ov (&tm->triple_ov_wheel);
 767   return 0;
 768 }
 769
 770 static clib_error_t *
 771 test1_single (tw_timer_test_main_t * tm)
 772 {
 773   u32 i;
 774   tw_timer_test_elt_t *e;
 775   u32 offset;
 776
 777   tw_timer_wheel_init_2t_1w_2048sl (&tm->single_wheel,
 778                                     expired_timer_single_callback,
 779                                     1.0 /* timer interval */ , ~0);
 780
 781   /*
 782    * Prime offset, to make sure that the wheel starts in a
 783    * non-trivial position
 784    */
 785   offset = 123;
 786
 787   run_single_wheel (&tm->single_wheel, offset);
 788
 789   fformat (stdout, "initial wheel time %d, fast index %d\n",
 790            tm->single_wheel.current_tick,
 791            tm->single_wheel.current_index[TW_TIMER_RING_FAST]);
 792
 793   offset = tm->single_wheel.current_tick;
 794
 795   for (i = 0; i < tm->ntimers; i++)
 796     {
 797       u32 expected_to_expire;
 798       u32 timer_arg;
 799
 800       timer_arg = 1 + i;
 801       timer_arg &= 2047;
 802       if (timer_arg == 0)
 803         timer_arg = 1;
 804
 805       expected_to_expire = timer_arg + offset;
 806
 807       pool_get (tm->test_elts, e);
 808       memset (e, 0, sizeof (*e));
 809       e->expected_to_expire = expected_to_expire;
 810       e->stop_timer_handle = tw_timer_start_2t_1w_2048sl
 811         (&tm->single_wheel, e - tm->test_elts, 1 /* timer id */ ,
 812          timer_arg);
 813     }
 814   run_single_wheel (&tm->single_wheel, tm->ntimers + 3);
 815
 816   if (pool_elts (tm->test_elts))
 817     fformat (stdout, "Note: %d elements remain in pool\n",
 818              pool_elts (tm->test_elts));
 819
 820   /* *INDENT-OFF* */
 821   pool_foreach (e, tm->test_elts,
 822   ({
 823     fformat(stdout, "[%d] expected to expire %d\n",
 824                      e - tm->test_elts,
 825                      e->expected_to_expire);
 826   }));
 827   /* *INDENT-ON* */
 828
 829   fformat (stdout,
 830            "final wheel time %d, fast index %d\n",
 831            tm->single_wheel.current_tick,
 832            tm->single_wheel.current_index[TW_TIMER_RING_FAST]);
 833
 834   pool_free (tm->test_elts);
 835   tw_timer_wheel_free_2t_1w_2048sl (&tm->single_wheel);
 836   return 0;
 837 }
 838
 839 static clib_error_t *
 840 test1_double (tw_timer_test_main_t * tm)
 841 {
 842   u32 i;
 843   tw_timer_test_elt_t *e;
 844   u32 offset;
 845
 846   tw_timer_wheel_init_16t_2w_512sl (&tm->double_wheel,
 847                                     expired_timer_double_callback,
 848                                     1.0 /* timer interval */ , ~0);
 849
 850   /*
 851    * Prime offset, to make sure that the wheel starts in a
 852    * non-trivial position
 853    */
 854   offset = 227989;
 855
 856   run_double_wheel (&tm->double_wheel, offset);
 857
 858   fformat (stdout, "initial wheel time %d, fast index %d\n",
 859            tm->double_wheel.current_tick,
 860            tm->double_wheel.current_index[TW_TIMER_RING_FAST]);
 861
 862   for (i = 0; i < tm->ntimers; i++)
 863     {
 864       pool_get (tm->test_elts, e);
 865       memset (e, 0, sizeof (*e));
 866
 867       e->expected_to_expire = i + offset + 1;
 868       e->stop_timer_handle = tw_timer_start_16t_2w_512sl
 869         (&tm->double_wheel, e - tm->test_elts, 14 /* timer id */ ,
 870          i + 1);
 871     }
 872   run_double_wheel (&tm->double_wheel, tm->ntimers + 3);
 873
 874   if (pool_elts (tm->test_elts))
 875     fformat (stdout, "Note: %d elements remain in pool\n",
 876              pool_elts (tm->test_elts));
 877
 878   /* *INDENT-OFF* */
 879   pool_foreach (e, tm->test_elts,
 880   ({
 881     fformat(stdout, "[%d] expected to expire %d\n",
 882                      e - tm->test_elts,
 883                      e->expected_to_expire);
 884   }));
 885   /* *INDENT-ON* */
 886
 887   fformat (stdout,
 888            "final wheel time %d, fast index %d\n",
 889            tm->double_wheel.current_tick,
 890            tm->double_wheel.current_index[TW_TIMER_RING_FAST]);
 891
 892   pool_free (tm->test_elts);
 893   tw_timer_wheel_free_16t_2w_512sl (&tm->double_wheel);
 894   return 0;
 895 }
 896
 897 static clib_error_t *
 898 test3_triple_double (tw_timer_test_main_t * tm)
 899 {
 900   tw_timer_test_elt_t *e;
 901   u32 initial_wheel_offset = 0;
 902   u32 expiration_time;
 903   u32 max_expiration_time = 0;
 904   u32 adds = 0, deletes = 0;
 905   f64 before, after;
 906
 907   clib_time_init (&tm->clib_time);
 908
 909   tw_timer_wheel_init_4t_3w_256sl (&tm->triple_wheel,
 910                                    expired_timer_triple_callback,
 911                                    1.0 /* timer interval */ , ~0);
 912
 913   initial_wheel_offset = 0;
 914   run_triple_wheel (&tm->triple_wheel, initial_wheel_offset);
 915
 916   fformat (stdout,
 917            "initial wheel time %d, fi %d si %d gi %d\n",
 918            tm->triple_wheel.current_tick,
 919            tm->triple_wheel.current_index[TW_TIMER_RING_FAST],
 920            tm->triple_wheel.current_index[TW_TIMER_RING_SLOW],
 921            tm->triple_wheel.current_index[TW_TIMER_RING_GLACIER]);
 922
 923   initial_wheel_offset = tm->triple_wheel.current_tick;
 924
 925   fformat (stdout, "Create a timer which expires at wheel-time (1, 0, 0)\n");
 926
 927   before = clib_time_now (&tm->clib_time);
 928
 929   /* Prime the pump */
 930   pool_get (tm->test_elts, e);
 931   memset (e, 0, sizeof (*e));
 932
 933   /* 1 glacier ring tick from now */
 934   expiration_time = TW_SLOTS_PER_RING * TW_SLOTS_PER_RING;
 935   e->expected_to_expire = expiration_time + initial_wheel_offset;
 936   max_expiration_time = expiration_time;
 937
 938   e->stop_timer_handle =
 939     tw_timer_start_4t_3w_256sl (&tm->triple_wheel, e - tm->test_elts,
 940                                 3 /* timer id */ ,
 941                                 expiration_time);
 942
 943   run_triple_wheel (&tm->triple_wheel, max_expiration_time + 1);
 944
 945   after = clib_time_now (&tm->clib_time);
 946
 947   fformat (stdout, "%d adds, %d deletes, %d ticks\n", adds, deletes,
 948            tm->triple_wheel.current_tick);
 949   fformat (stdout, "test ran %.2f seconds, %.2f ops/second\n",
 950            (after - before),
 951            ((f64) adds + (f64) deletes +
 952             (f64) tm->triple_wheel.current_tick) / (after - before));
 953
 954   if (pool_elts (tm->test_elts))
 955     fformat (stdout, "Note: %d elements remain in pool\n",
 956              pool_elts (tm->test_elts));
 957
 958   /* *INDENT-OFF* */
 959   pool_foreach (e, tm->test_elts,
 960   ({
 961     fformat (stdout, "[%d] expected to expire %d\n",
 962              e - tm->test_elts,
 963              e->expected_to_expire);
 964   }));
 965   /* *INDENT-ON* */
 966
 967   pool_free (tm->test_elts);
 968   tw_timer_wheel_free_4t_3w_256sl (&tm->triple_wheel);
 969   return 0;
 970 }
 971
 972 static clib_error_t *
 973 test4_double_double (tw_timer_test_main_t * tm)
 974 {
 975   u32 i;
 976   tw_timer_test_elt_t *e;
 977   u32 initial_wheel_offset;
 978   u32 expiration_time;
 979   u32 max_expiration_time = 0;
 980   u32 *deleted_indices = 0;
 981   u32 adds = 0, deletes = 0;
 982   f64 before, after;
 983
 984   clib_time_init (&tm->clib_time);
 985
 986   tw_timer_wheel_init_16t_2w_512sl (&tm->double_wheel,
 987                                     expired_timer_double_callback,
 988                                     1.0 /* timer interval */ , ~0);
 989   /* Prime offset */
 990   initial_wheel_offset = 0;
 991
 992   run_double_wheel (&tm->double_wheel, initial_wheel_offset);
 993
 994   fformat (stdout, "initial wheel time %d, fast index %d slow index %d\n",
 995            tm->double_wheel.current_tick,
 996            tm->double_wheel.current_index[TW_TIMER_RING_FAST],
 997            tm->double_wheel.current_index[TW_TIMER_RING_SLOW]);
 998
 999   initial_wheel_offset = tm->double_wheel.current_tick;
1000
1001   fformat (stdout, "test timer which expires at 512 ticks\n");
1002
1003   before = clib_time_now (&tm->clib_time);
1004
1005   /* Prime the pump */
1006   for (i = 0; i < tm->ntimers; i++)
1007     {
1008       pool_get (tm->test_elts, e);
1009       memset (e, 0, sizeof (*e));
1010
1011       expiration_time = 512;
1012
1013       if (expiration_time > max_expiration_time)
1014         max_expiration_time = expiration_time;
1015
1016       e->expected_to_expire = expiration_time + initial_wheel_offset;
1017       e->stop_timer_handle =
1018         tw_timer_start_16t_2w_512sl (&tm->double_wheel, e - tm->test_elts,
1019                                      14 /* timer id */ ,
1020                                      expiration_time);
1021     }
1022
1023   adds = 1;
1024
1025   vec_free (deleted_indices);
1026
1027   run_double_wheel (&tm->double_wheel, max_expiration_time + 1);
1028
1029   after = clib_time_now (&tm->clib_time);
1030
1031   fformat (stdout, "%d adds, %d deletes, %d ticks\n", adds, deletes,
1032            tm->double_wheel.current_tick);
1033   fformat (stdout, "test ran %.2f seconds, %.2f ops/second\n",
1034            (after - before),
1035            ((f64) adds + (f64) deletes +
1036             (f64) tm->double_wheel.current_tick) / (after - before));
1037
1038   if (pool_elts (tm->test_elts))
1039     fformat (stdout, "Note: %d elements remain in pool\n",
1040              pool_elts (tm->test_elts));
1041
1042   /* *INDENT-OFF* */
1043   pool_foreach (e, tm->test_elts,
1044   ({
1045     fformat (stdout, "[%d] expected to expire %d\n",
1046              e - tm->test_elts,
1047              e->expected_to_expire);
1048   }));
1049   /* *INDENT-ON* */
1050
1051   pool_free (tm->test_elts);
1052   tw_timer_wheel_free_16t_2w_512sl (&tm->double_wheel);
1053   return 0;
1054 }
1055
1056 static clib_error_t *
1057 test5_double (tw_timer_test_main_t * tm)
1058 {
1059   u32 i;
1060   tw_timer_test_elt_t *e;
1061   u32 initial_wheel_offset;
1062   u32 expiration_time;
1063   u32 max_expiration_time = 0;
1064   u32 adds = 0, deletes = 0;
1065   f64 before, after;
1066
1067   clib_time_init (&tm->clib_time);
1068
1069   tw_timer_wheel_init_16t_2w_512sl (&tm->double_wheel,
1070                                     expired_timer_double_callback,
1071                                     1.0 /* timer interval */ , ~0);
1072
1073   /* Prime offset */
1074   initial_wheel_offset = 7567;
1075
1076   run_double_wheel (&tm->double_wheel, initial_wheel_offset);
1077
1078   fformat (stdout, "initial wheel time %d, fast index %d slow index %d\n",
1079            tm->double_wheel.current_tick,
1080            tm->double_wheel.current_index[TW_TIMER_RING_FAST],
1081            tm->double_wheel.current_index[TW_TIMER_RING_SLOW]);
1082
1083   initial_wheel_offset = tm->double_wheel.current_tick;
1084
1085   fformat (stdout,
1086            "test %d timers, %d iter, %d ticks per iter, 0x%llx seed\n",
1087            tm->ntimers, tm->niter, tm->ticks_per_iter, tm->seed);
1088
1089   before = clib_time_now (&tm->clib_time);
1090
1091   /* Prime the pump */
1092   for (i = 0; i < tm->ntimers; i++)
1093     {
1094       pool_get (tm->test_elts, e);
1095       memset (e, 0, sizeof (*e));
1096
1097       expiration_time = i + 1;
1098
1099       if (expiration_time > max_expiration_time)
1100         max_expiration_time = expiration_time;
1101
1102       e->expected_to_expire = expiration_time + initial_wheel_offset;
1103       e->stop_timer_handle =
1104         tw_timer_start_16t_2w_512sl (&tm->double_wheel, e - tm->test_elts,
1105                                      14 /* timer id */ ,
1106                                      expiration_time);
1107     }
1108
1109   adds += i;
1110
1111   run_double_wheel (&tm->double_wheel, max_expiration_time + 1);
1112
1113   after = clib_time_now (&tm->clib_time);
1114
1115   fformat (stdout, "%d adds, %d deletes, %d ticks\n", adds, deletes,
1116            tm->double_wheel.current_tick);
1117   fformat (stdout, "test ran %.2f seconds, %.2f ops/second\n",
1118            (after - before),
1119            ((f64) adds + (f64) deletes +
1120             (f64) tm->double_wheel.current_tick) / (after - before));
1121
1122   if (pool_elts (tm->test_elts))
1123     fformat (stdout, "Note: %d elements remain in pool\n",
1124              pool_elts (tm->test_elts));
1125
1126   /* *INDENT-OFF* */
1127   pool_foreach (e, tm->test_elts,
1128   ({
1129     fformat (stdout, "[%d] expected to expire %d\n",
1130              e - tm->test_elts,
1131              e->expected_to_expire);
1132   }));
1133   /* *INDENT-ON* */
1134
1135   pool_free (tm->test_elts);
1136   tw_timer_wheel_free_16t_2w_512sl (&tm->double_wheel);
1137   return 0;
1138 }
1139
1140 static clib_error_t *
1141 timer_test_command_fn (tw_timer_test_main_t * tm, unformat_input_t * input)
1142 {
1143
1144   int is_test1 = 0;
1145   int num_wheels = 1;
1146   int is_test2 = 0;
1147   int is_test3 = 0;
1148   int is_test4 = 0;
1149   int is_test5 = 0;
1150   int overflow = 0;
1151
1152   memset (tm, 0, sizeof (*tm));
1153   /* Default values */
1154   tm->ntimers = 100000;
1155   tm->seed = 0xDEADDABEB00BFACE;
1156   tm->niter = 1000;
1157   tm->ticks_per_iter = 727;
1158
1159   while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
1160     {
1161       if (unformat (input, "seed %lld", &tm->seed))
1162         ;
1163       else if (unformat (input, "test1"))
1164         is_test1 = 1;
1165       else if (unformat (input, "test2"))
1166         is_test2 = 1;
1167       else if (unformat (input, "overflow"))
1168         overflow = 1;
1169       else if (unformat (input, "lebron"))
1170         is_test3 = 1;
1171       else if (unformat (input, "wilt"))
1172         is_test4 = 1;
1173       else if (unformat (input, "linear"))
1174         is_test5 = 1;
1175       else if (unformat (input, "wheels %d", &num_wheels))
1176         ;
1177       else if (unformat (input, "ntimers %d", &tm->ntimers))
1178         ;
1179       else if (unformat (input, "niter %d", &tm->niter))
1180         ;
1181       else if (unformat (input, "ticks_per_iter %d", &tm->ticks_per_iter))
1182         ;
1183       else
1184         break;
1185     }
1186
1187   if (is_test1 + is_test2 + is_test3 + is_test4 + is_test5 == 0)
1188     return clib_error_return (0, "No test specified [test1..n]");
1189
1190   if (num_wheels < 1 || num_wheels > 3)
1191     return clib_error_return (0, "unsupported... 1 or 2 wheels only");
1192
1193   if (is_test1)
1194     {
1195       if (num_wheels == 1)
1196         return test1_single (tm);
1197       else
1198         return test1_double (tm);
1199     }
1200   if (is_test2)
1201     {
1202       if (num_wheels == 1)
1203         return test2_single (tm);
1204       else if (num_wheels == 2)
1205         return test2_double (tm);
1206       else if (num_wheels == 3)
1207         {
1208           if (overflow == 0)
1209             return test2_triple (tm);
1210           else
1211             return test2_triple_ov (tm);
1212         }
1213     }
1214   if (is_test3)
1215     return test3_triple_double (tm);
1216
1217   if (is_test4)
1218     return test4_double_double (tm);
1219
1220   if (is_test5)
1221     return test5_double (tm);
1222
1223   /* NOTREACHED */
1224   return 0;
1225 }
1226
1227 #ifdef CLIB_UNIX
1228 int
1229 main (int argc, char *argv[])
1230 {
1231   unformat_input_t i;
1232   clib_error_t *error;
1233   tw_timer_test_main_t *tm = &tw_timer_test_main;
1234
1235   clib_mem_init (0, 3ULL << 30);
1236
1237   unformat_init_command_line (&i, argv);
1238   error = timer_test_command_fn (tm, &i);
1239   unformat_free (&i);
1240
1241   if (error)
1242     {
1243       clib_error_report (error);
1244       return 1;
1245     }
1246   return 0;
1247 }
1248 #endif /* CLIB_UNIX */
1249
1250 /* For debugging... */
1251 int
1252 pifi (void *p, u32 index)
1253 {
1254   return pool_is_free_index (p, index);
1255 }
1256
1257 u32
1258 vl (void *p)
1259 {
1260   return vec_len (p);
1261 }
1262
1263 uword
1264 pe (void *v)
1265 {
1266   return (pool_elts (v));
1267 }
1268
1269 /*
1270  * fd.io coding-style-patch-verification: ON
1271  *
1272  * Local Variables:
1273  * eval: (c-set-style "gnu")
1274  * End:
1275  */