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
   7 typedef struct
   8 {
   9   /** Handle returned from tw_start_timer */
  10   u32 stop_timer_handle;
  11
  12   /** Test item should expire at this clock tick */
  13   u32 expected_to_expire;
  14 } tw_timer_test_elt_t;
  15
  16 typedef struct
  17 {
  18   /** Pool of test objects */
  19   tw_timer_test_elt_t *test_elts;
  20
  21   /** The single-wheel */
  22   tw_timer_wheel_2t_1w_2048sl_t single_wheel;
  23
  24   /** The double-wheel */
  25   tw_timer_wheel_16t_2w_512sl_t double_wheel;
  26
  27   /** random number seed */
  28   u32 seed;
  29
  30   /** number of timers */
  31   u32 ntimers;
  32
  33   /** number of "churn" iterations */
  34   u32 niter;
  35
  36   /** number of clock ticks per churn iteration */
  37   u32 ticks_per_iter;
  38
  39   /** cpu timer */
  40   clib_time_t clib_time;
  41 } tw_timer_test_main_t;
  42
  43 tw_timer_test_main_t tw_timer_test_main;
  44
  45 static void
  46 run_single_wheel (tw_timer_wheel_2t_1w_2048sl_t * tw, u32 n_ticks)
  47 {
  48   u32 i;
  49   f64 now = tw->last_run_time + 1.01;
  50
  51   for (i = 0; i < n_ticks; i++)
  52     {
  53       tw_timer_expire_timers_2t_1w_2048sl (tw, now);
  54       now += 1.01;
  55     }
  56 }
  57
  58 static void
  59 run_double_wheel (tw_timer_wheel_16t_2w_512sl_t * tw, u32 n_ticks)
  60 {
  61   u32 i;
  62   f64 now = tw->last_run_time + 1.01;
  63
  64   for (i = 0; i < n_ticks; i++)
  65     {
  66       tw_timer_expire_timers_16t_2w_512sl (tw, now);
  67       now += 1.01;
  68     }
  69 }
  70
  71 static void
  72 expired_timer_single_callback (u32 * expired_timers)
  73 {
  74   int i;
  75   u32 pool_index, timer_id;
  76   tw_timer_test_elt_t *e;
  77   tw_timer_test_main_t *tm = &tw_timer_test_main;
  78
  79   for (i = 0; i < vec_len (expired_timers); i++)
  80     {
  81       pool_index = expired_timers[i] & 0x7FFFFFFF;
  82       timer_id = expired_timers[i] >> 31;
  83
  84       ASSERT (timer_id == 1);
  85
  86       e = pool_elt_at_index (tm->test_elts, pool_index);
  87
  88       if (e->expected_to_expire != tm->single_wheel.current_tick)
  89         {
  90           fformat (stdout, "[%d] expired at %d not %d\n",
  91                    e - tm->test_elts, tm->single_wheel.current_tick,
  92                    e->expected_to_expire);
  93         }
  94       pool_put (tm->test_elts, e);
  95     }
  96 }
  97
  98 static void
  99 expired_timer_double_callback (u32 * expired_timers)
 100 {
 101   int i;
 102   u32 pool_index, timer_id;
 103   tw_timer_test_elt_t *e;
 104   tw_timer_test_main_t *tm = &tw_timer_test_main;
 105
 106   for (i = 0; i < vec_len (expired_timers); i++)
 107     {
 108       pool_index = expired_timers[i] & 0x0FFFFFFF;
 109       timer_id = expired_timers[i] >> 28;
 110
 111       ASSERT (timer_id == 14);
 112
 113       e = pool_elt_at_index (tm->test_elts, pool_index);
 114
 115       if (e->expected_to_expire != tm->double_wheel.current_tick)
 116         {
 117           fformat (stdout, "[%d] expired at %d not %d\n",
 118                    e - tm->test_elts, tm->double_wheel.current_tick,
 119                    e->expected_to_expire);
 120         }
 121       pool_put (tm->test_elts, e);
 122     }
 123 }
 124
 125 static clib_error_t *
 126 test2_single (tw_timer_test_main_t * tm)
 127 {
 128   u32 i, j;
 129   tw_timer_test_elt_t *e;
 130   u32 initial_wheel_offset;
 131   u32 expiration_time;
 132   u32 max_expiration_time = 0;
 133   u32 *deleted_indices = 0;
 134   u32 adds = 0, deletes = 0;
 135   f64 before, after;
 136
 137   clib_time_init (&tm->clib_time);
 138
 139   tw_timer_wheel_init_2t_1w_2048sl (&tm->single_wheel,
 140                                     expired_timer_single_callback,
 141                                     1.0 /* timer interval */ );
 142
 143   /* Prime offset */
 144   initial_wheel_offset = 757;
 145
 146   run_single_wheel (&tm->single_wheel, initial_wheel_offset);
 147
 148   fformat (stdout, "test %d timers, %d iter, %d ticks per iter, 0x%x seed\n",
 149            tm->ntimers, tm->niter, tm->ticks_per_iter, tm->seed);
 150
 151   before = clib_time_now (&tm->clib_time);
 152
 153   /* Prime the pump */
 154   for (i = 0; i < tm->ntimers; i++)
 155     {
 156       pool_get (tm->test_elts, e);
 157       memset (e, 0, sizeof (*e));
 158
 159       do
 160         {
 161           expiration_time = random_u32 (&tm->seed) & (2047);
 162         }
 163       while (expiration_time == 0);
 164
 165       if (expiration_time > max_expiration_time)
 166         max_expiration_time = expiration_time;
 167
 168       e->expected_to_expire = expiration_time + initial_wheel_offset;
 169       e->stop_timer_handle =
 170         tw_timer_start_2t_1w_2048sl (&tm->single_wheel, e - tm->test_elts,
 171                                      1 /* timer id */ ,
 172                                      expiration_time);
 173     }
 174
 175   adds += i;
 176
 177   for (i = 0; i < tm->niter; i++)
 178     {
 179       run_single_wheel (&tm->single_wheel, tm->ticks_per_iter);
 180
 181       j = 0;
 182       vec_reset_length (deleted_indices);
 183       /* *INDENT-OFF* */
 184       pool_foreach (e, tm->test_elts,
 185       ({
 186         tw_timer_stop_2t_1w_2048sl (&tm->single_wheel, e->stop_timer_handle);
 187         vec_add1 (deleted_indices, e - tm->test_elts);
 188         if (++j >= tm->ntimers / 4)
 189           goto del_and_re_add;
 190       }));
 191       /* *INDENT-ON* */
 192
 193     del_and_re_add:
 194       for (j = 0; j < vec_len (deleted_indices); j++)
 195         pool_put_index (tm->test_elts, deleted_indices[j]);
 196
 197       deletes += j;
 198
 199       for (j = 0; j < tm->ntimers / 4; j++)
 200         {
 201           pool_get (tm->test_elts, e);
 202           memset (e, 0, sizeof (*e));
 203
 204           do
 205             {
 206               expiration_time = random_u32 (&tm->seed) & (2047);
 207             }
 208           while (expiration_time == 0);
 209
 210           if (expiration_time > max_expiration_time)
 211             max_expiration_time = expiration_time;
 212
 213           e->expected_to_expire =
 214             expiration_time + tm->single_wheel.current_tick;
 215           e->stop_timer_handle = tw_timer_start_2t_1w_2048sl
 216             (&tm->single_wheel, e - tm->test_elts, 1 /* timer id */ ,
 217              expiration_time);
 218         }
 219       adds += j;
 220     }
 221
 222   vec_free (deleted_indices);
 223
 224   run_single_wheel (&tm->single_wheel, max_expiration_time + 1);
 225
 226   after = clib_time_now (&tm->clib_time);
 227
 228   fformat (stdout, "%d adds, %d deletes, %d ticks\n", adds, deletes,
 229            tm->single_wheel.current_tick);
 230   fformat (stdout, "test ran %.2f seconds, %.2f ops/second\n",
 231            (after - before),
 232            ((f64) adds + (f64) deletes +
 233             (f64) tm->single_wheel.current_tick) / (after - before));
 234
 235   if (pool_elts (tm->test_elts))
 236     fformat (stdout, "Note: %d elements remain in pool\n",
 237              pool_elts (tm->test_elts));
 238
 239   /* *INDENT-OFF* */
 240   pool_foreach (e, tm->test_elts,
 241   ({
 242     fformat (stdout, "[%d] expected to expire %d\n",
 243              e - tm->test_elts,
 244              e->expected_to_expire);
 245   }));
 246   /* *INDENT-ON* */
 247
 248   pool_free (tm->test_elts);
 249   tw_timer_wheel_free_2t_1w_2048sl (&tm->single_wheel);
 250   return 0;
 251 }
 252
 253 static clib_error_t *
 254 test2_double (tw_timer_test_main_t * tm)
 255 {
 256   u32 i, j;
 257   tw_timer_test_elt_t *e;
 258   u32 initial_wheel_offset;
 259   u32 expiration_time;
 260   u32 max_expiration_time = 0;
 261   u32 *deleted_indices = 0;
 262   u32 adds = 0, deletes = 0;
 263   f64 before, after;
 264
 265   clib_time_init (&tm->clib_time);
 266
 267   tw_timer_wheel_init_16t_2w_512sl (&tm->double_wheel,
 268                                     expired_timer_double_callback,
 269                                     1.0 /* timer interval */ );
 270
 271   /* Prime offset */
 272   initial_wheel_offset = 757;
 273
 274   run_double_wheel (&tm->double_wheel, initial_wheel_offset);
 275
 276   fformat (stdout, "test %d timers, %d iter, %d ticks per iter, 0x%x seed\n",
 277            tm->ntimers, tm->niter, tm->ticks_per_iter, tm->seed);
 278
 279   before = clib_time_now (&tm->clib_time);
 280
 281   /* Prime the pump */
 282   for (i = 0; i < tm->ntimers; i++)
 283     {
 284       pool_get (tm->test_elts, e);
 285       memset (e, 0, sizeof (*e));
 286
 287       do
 288         {
 289           expiration_time = random_u32 (&tm->seed) & ((1 << 17) - 1);
 290         }
 291       while (expiration_time == 0);
 292
 293       if (expiration_time > max_expiration_time)
 294         max_expiration_time = expiration_time;
 295
 296       e->expected_to_expire = expiration_time + initial_wheel_offset;
 297       e->stop_timer_handle =
 298         tw_timer_start_16t_2w_512sl (&tm->double_wheel, e - tm->test_elts,
 299                                      14 /* timer id */ ,
 300                                      expiration_time);
 301     }
 302
 303   adds += i;
 304
 305   for (i = 0; i < tm->niter; i++)
 306     {
 307       run_double_wheel (&tm->double_wheel, tm->ticks_per_iter);
 308
 309       j = 0;
 310       vec_reset_length (deleted_indices);
 311       /* *INDENT-OFF* */
 312       pool_foreach (e, tm->test_elts,
 313       ({
 314         tw_timer_stop_16t_2w_512sl (&tm->double_wheel, e->stop_timer_handle);
 315         vec_add1 (deleted_indices, e - tm->test_elts);
 316         if (++j >= tm->ntimers / 4)
 317           goto del_and_re_add;
 318       }));
 319       /* *INDENT-ON* */
 320
 321     del_and_re_add:
 322       for (j = 0; j < vec_len (deleted_indices); j++)
 323         pool_put_index (tm->test_elts, deleted_indices[j]);
 324
 325       deletes += j;
 326
 327       for (j = 0; j < tm->ntimers / 4; j++)
 328         {
 329           pool_get (tm->test_elts, e);
 330           memset (e, 0, sizeof (*e));
 331
 332           do
 333             {
 334               expiration_time = random_u32 (&tm->seed) & ((1 << 17) - 1);
 335             }
 336           while (expiration_time == 0);
 337
 338           if (expiration_time > max_expiration_time)
 339             max_expiration_time = expiration_time;
 340
 341           e->expected_to_expire = expiration_time +
 342             tm->double_wheel.current_tick;
 343           e->stop_timer_handle = tw_timer_start_16t_2w_512sl
 344             (&tm->double_wheel, e - tm->test_elts, 14 /* timer id */ ,
 345              expiration_time);
 346         }
 347       adds += j;
 348     }
 349
 350   vec_free (deleted_indices);
 351
 352   run_double_wheel (&tm->double_wheel, max_expiration_time + 1);
 353
 354   after = clib_time_now (&tm->clib_time);
 355
 356   fformat (stdout, "%d adds, %d deletes, %d ticks\n", adds, deletes,
 357            tm->double_wheel.current_tick);
 358   fformat (stdout, "test ran %.2f seconds, %.2f ops/second\n",
 359            (after - before),
 360            ((f64) adds + (f64) deletes +
 361             (f64) tm->double_wheel.current_tick) / (after - before));
 362
 363   if (pool_elts (tm->test_elts))
 364     fformat (stdout, "Note: %d elements remain in pool\n",
 365              pool_elts (tm->test_elts));
 366
 367   /* *INDENT-OFF* */
 368   pool_foreach (e, tm->test_elts,
 369   ({
 370     fformat (stdout, "[%d] expected to expire %d\n",
 371              e - tm->test_elts,
 372              e->expected_to_expire);
 373   }));
 374   /* *INDENT-ON* */
 375
 376   pool_free (tm->test_elts);
 377   tw_timer_wheel_free_16t_2w_512sl (&tm->double_wheel);
 378   return 0;
 379 }
 380
 381 static clib_error_t *
 382 test1_single (tw_timer_test_main_t * tm)
 383 {
 384   u32 i;
 385   tw_timer_test_elt_t *e;
 386   u32 offset;
 387
 388   tw_timer_wheel_init_2t_1w_2048sl (&tm->single_wheel,
 389                                     expired_timer_single_callback,
 390                                     1.0 /* timer interval */ );
 391
 392   /*
 393    * Prime offset, to make sure that the wheel starts in a
 394    * non-trivial position
 395    */
 396   offset = 123;
 397
 398   run_single_wheel (&tm->single_wheel, offset);
 399
 400   fformat (stdout, "initial wheel time %d, fast index %d\n",
 401            tm->single_wheel.current_tick,
 402            tm->single_wheel.current_index[TW_TIMER_RING_FAST]);
 403
 404   for (i = 0; i < tm->ntimers; i++)
 405     {
 406       u32 expected_to_expire;
 407       u32 timer_arg;
 408
 409       timer_arg = 1 + i;
 410       timer_arg &= 2047;
 411       if (timer_arg == 0)
 412         timer_arg = 1;
 413
 414       expected_to_expire = timer_arg + offset;
 415
 416       pool_get (tm->test_elts, e);
 417       memset (e, 0, sizeof (*e));
 418       e->expected_to_expire = expected_to_expire;
 419       e->stop_timer_handle = tw_timer_start_2t_1w_2048sl
 420         (&tm->single_wheel, e - tm->test_elts, 1 /* timer id */ ,
 421          timer_arg);
 422     }
 423   run_single_wheel (&tm->single_wheel, tm->ntimers + 3);
 424
 425   if (pool_elts (tm->test_elts))
 426     fformat (stdout, "Note: %d elements remain in pool\n",
 427              pool_elts (tm->test_elts));
 428
 429   /* *INDENT-OFF* */
 430   pool_foreach (e, tm->test_elts,
 431   ({
 432     fformat(stdout, "[%d] expected to expire %d\n",
 433                      e - tm->test_elts,
 434                      e->expected_to_expire);
 435   }));
 436   /* *INDENT-ON* */
 437
 438   fformat (stdout,
 439            "final wheel time %d, fast index %d\n",
 440            tm->single_wheel.current_tick,
 441            tm->single_wheel.current_index[TW_TIMER_RING_FAST]);
 442
 443   pool_free (tm->test_elts);
 444   tw_timer_wheel_free_2t_1w_2048sl (&tm->single_wheel);
 445   return 0;
 446 }
 447
 448 static clib_error_t *
 449 test1_double (tw_timer_test_main_t * tm)
 450 {
 451   u32 i;
 452   tw_timer_test_elt_t *e;
 453   u32 offset;
 454
 455   tw_timer_wheel_init_16t_2w_512sl (&tm->double_wheel,
 456                                     expired_timer_double_callback,
 457                                     1.0 /* timer interval */ );
 458
 459   /*
 460    * Prime offset, to make sure that the wheel starts in a
 461    * non-trivial position
 462    */
 463   offset = 227989;
 464
 465   run_double_wheel (&tm->double_wheel, offset);
 466
 467   fformat (stdout, "initial wheel time %d, fast index %d\n",
 468            tm->double_wheel.current_tick,
 469            tm->double_wheel.current_index[TW_TIMER_RING_FAST]);
 470
 471   for (i = 0; i < tm->ntimers; i++)
 472     {
 473       pool_get (tm->test_elts, e);
 474       memset (e, 0, sizeof (*e));
 475
 476       e->expected_to_expire = i + offset + 1;
 477       e->stop_timer_handle = tw_timer_start_16t_2w_512sl
 478         (&tm->double_wheel, e - tm->test_elts, 14 /* timer id */ ,
 479          i + 1);
 480     }
 481   run_double_wheel (&tm->double_wheel, tm->ntimers + 3);
 482
 483   if (pool_elts (tm->test_elts))
 484     fformat (stdout, "Note: %d elements remain in pool\n",
 485              pool_elts (tm->test_elts));
 486
 487   /* *INDENT-OFF* */
 488   pool_foreach (e, tm->test_elts,
 489   ({
 490     fformat(stdout, "[%d] expected to expire %d\n",
 491                      e - tm->test_elts,
 492                      e->expected_to_expire);
 493   }));
 494   /* *INDENT-ON* */
 495
 496   fformat (stdout,
 497            "final wheel time %d, fast index %d\n",
 498            tm->double_wheel.current_tick,
 499            tm->double_wheel.current_index[TW_TIMER_RING_FAST]);
 500
 501   pool_free (tm->test_elts);
 502   tw_timer_wheel_free_16t_2w_512sl (&tm->double_wheel);
 503   return 0;
 504 }
 505
 506 static clib_error_t *
 507 timer_test_command_fn (tw_timer_test_main_t * tm, unformat_input_t * input)
 508 {
 509
 510   int is_test1 = 0;
 511   int num_wheels = 1;
 512   int is_test2 = 0;
 513
 514   memset (tm, 0, sizeof (*tm));
 515   /* Default values */
 516   tm->ntimers = 100000;
 517   tm->seed = 0xDEADDABE;
 518   tm->niter = 1000;
 519   tm->ticks_per_iter = 727;
 520
 521   while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
 522     {
 523       if (unformat (input, "seed %d", &tm->seed))
 524         ;
 525       else if (unformat (input, "test1"))
 526         is_test1 = 1;
 527       else if (unformat (input, "test2"))
 528         is_test2 = 1;
 529       else if (unformat (input, "wheels %d", &num_wheels))
 530         ;
 531       else if (unformat (input, "ntimers %d", &tm->ntimers))
 532         ;
 533       else if (unformat (input, "niter %d", &tm->niter))
 534         ;
 535       else if (unformat (input, "ticks_per_iter %d", &tm->ticks_per_iter))
 536         ;
 537     }
 538
 539   if (is_test1 + is_test2 == 0)
 540     return clib_error_return (0, "No test specified [test1..n]");
 541
 542   if (num_wheels < 1 || num_wheels > 2)
 543     return clib_error_return (0, "unsupported... 1 or 2 wheels only");
 544
 545   if (is_test1)
 546     {
 547       if (num_wheels == 1)
 548         return test1_single (tm);
 549       else
 550         return test1_double (tm);
 551     }
 552   if (is_test2)
 553     {
 554       if (num_wheels == 1)
 555         return test2_single (tm);
 556       else
 557         return test2_double (tm);
 558     }
 559   /* NOTREACHED */
 560   return 0;
 561 }
 562
 563 #ifdef CLIB_UNIX
 564 int
 565 main (int argc, char *argv[])
 566 {
 567   unformat_input_t i;
 568   clib_error_t *error;
 569   tw_timer_test_main_t *tm = &tw_timer_test_main;
 570
 571   clib_mem_init (0, 3ULL << 30);
 572
 573   unformat_init_command_line (&i, argv);
 574   error = timer_test_command_fn (tm, &i);
 575   unformat_free (&i);
 576
 577   if (error)
 578     {
 579       clib_error_report (error);
 580       return 1;
 581     }
 582   return 0;
 583 }
 584 #endif /* CLIB_UNIX */
 585
 586 /*
 587  * fd.io coding-style-patch-verification: ON
 588  *
 589  * Local Variables:
 590  * eval: (c-set-style "gnu")
 591  * End:
 592  */