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