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>
12 /** Handle returned from tw_start_timer */
13 u32 stop_timer_handle;
15 /** Test item should expire at this clock tick */
16 u64 expected_to_expire;
17 } tw_timer_test_elt_t;
21 /** Pool of test objects */
22 tw_timer_test_elt_t *test_elts;
24 /** The single-wheel */
25 tw_timer_wheel_2t_1w_2048sl_t single_wheel;
27 /** The double-wheel */
28 tw_timer_wheel_16t_2w_512sl_t double_wheel;
30 /* The triple wheel */
31 tw_timer_wheel_4t_3w_256sl_t triple_wheel;
33 /* The triple wheel with overflow vector */
34 tw_timer_wheel_1t_3w_1024sl_ov_t triple_ov_wheel;
36 /* Another two timer wheel geometry */
37 tw_timer_wheel_2t_2w_512sl_t two_timer_double_wheel;
39 /** random number seed */
42 /** number of timers */
45 /** number of "churn" iterations */
48 /** number of clock ticks per churn iteration */
52 clib_time_t clib_time;
53 } tw_timer_test_main_t;
55 tw_timer_test_main_t tw_timer_test_main;
58 run_single_wheel (tw_timer_wheel_2t_1w_2048sl_t * tw, u32 n_ticks)
61 f64 now = tw->last_run_time + 1.01;
63 for (i = 0; i < n_ticks; i++)
65 tw_timer_expire_timers_2t_1w_2048sl (tw, now);
71 run_double_wheel (tw_timer_wheel_16t_2w_512sl_t * tw, u32 n_ticks)
74 f64 now = tw->last_run_time + 1.01;
76 for (i = 0; i < n_ticks; i++)
78 tw_timer_expire_timers_16t_2w_512sl (tw, now);
84 run_two_timer_double_wheel (tw_timer_wheel_2t_2w_512sl_t * tw, u32 n_ticks)
87 f64 now = tw->last_run_time + 1.01;
89 for (i = 0; i < n_ticks; i++)
91 tw_timer_expire_timers_2t_2w_512sl (tw, now);
97 run_triple_wheel (tw_timer_wheel_4t_3w_256sl_t * tw, u32 n_ticks)
100 f64 now = tw->last_run_time + 1.01;
102 for (i = 0; i < n_ticks; i++)
104 tw_timer_expire_timers_4t_3w_256sl (tw, now);
110 run_triple_ov_wheel (tw_timer_wheel_1t_3w_1024sl_ov_t * tw, u32 n_ticks)
113 f64 now = tw->last_run_time + 1.01;
115 for (i = 0; i < n_ticks; i++)
117 tw_timer_expire_timers_1t_3w_1024sl_ov (tw, now);
123 expired_timer_single_callback (u32 * expired_timers)
126 u32 pool_index, timer_id;
127 tw_timer_test_elt_t *e;
128 tw_timer_test_main_t *tm = &tw_timer_test_main;
130 for (i = 0; i < vec_len (expired_timers); i++)
132 pool_index = expired_timers[i] & 0x7FFFFFFF;
133 timer_id = expired_timers[i] >> 31;
135 ASSERT (timer_id == 1);
137 e = pool_elt_at_index (tm->test_elts, pool_index);
139 if (e->expected_to_expire != tm->single_wheel.current_tick)
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);
145 pool_put (tm->test_elts, e);
150 expired_timer_double_callback (u32 * expired_timers)
153 u32 pool_index, timer_id;
154 tw_timer_test_elt_t *e;
155 tw_timer_test_main_t *tm = &tw_timer_test_main;
157 for (i = 0; i < vec_len (expired_timers); i++)
159 pool_index = expired_timers[i] & 0x0FFFFFFF;
160 timer_id = expired_timers[i] >> 28;
162 ASSERT (timer_id == 14);
164 e = pool_elt_at_index (tm->test_elts, pool_index);
166 if (e->expected_to_expire != tm->double_wheel.current_tick)
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);
172 pool_put (tm->test_elts, e);
177 expired_timer_two_timer_double_callback (u32 * expired_timers)
180 u32 pool_index, timer_id;
181 tw_timer_test_elt_t *e;
182 tw_timer_test_main_t *tm = &tw_timer_test_main;
184 for (i = 0; i < vec_len (expired_timers); i++)
186 pool_index = expired_timers[i] & 0x7FFFFFFF;
187 timer_id = expired_timers[i] >> 31;
189 ASSERT (timer_id == 1);
191 e = pool_elt_at_index (tm->test_elts, pool_index);
193 if (e->expected_to_expire != tm->two_timer_double_wheel.current_tick)
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);
199 pool_put (tm->test_elts, e);
204 expired_timer_triple_callback (u32 * expired_timers)
207 u32 pool_index, timer_id;
208 tw_timer_test_elt_t *e;
209 tw_timer_test_main_t *tm = &tw_timer_test_main;
211 for (i = 0; i < vec_len (expired_timers); i++)
213 pool_index = expired_timers[i] & 0x3FFFFFFF;
214 timer_id = expired_timers[i] >> 30;
216 ASSERT (timer_id == 3);
218 e = pool_elt_at_index (tm->test_elts, pool_index);
220 if (e->expected_to_expire != tm->triple_wheel.current_tick)
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);
226 pool_put (tm->test_elts, e);
231 expired_timer_triple_ov_callback (u32 * expired_timers)
235 tw_timer_test_elt_t *e;
236 tw_timer_test_main_t *tm = &tw_timer_test_main;
238 for (i = 0; i < vec_len (expired_timers); i++)
240 pool_index = expired_timers[i];
242 e = pool_elt_at_index (tm->test_elts, pool_index);
244 if (e->expected_to_expire != tm->triple_ov_wheel.current_tick)
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);
250 pool_put (tm->test_elts, e);
254 static clib_error_t *
255 test2_single (tw_timer_test_main_t * tm)
258 tw_timer_test_elt_t *e;
259 u32 initial_wheel_offset;
261 u32 max_expiration_time = 0;
262 u32 *deleted_indices = 0;
263 u32 adds = 0, deletes = 0;
266 clib_time_init (&tm->clib_time);
268 tw_timer_wheel_init_2t_1w_2048sl (&tm->single_wheel,
269 expired_timer_single_callback,
270 1.0 /* timer interval */ , ~0);
273 initial_wheel_offset = 757;
275 run_single_wheel (&tm->single_wheel, initial_wheel_offset);
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]);
281 initial_wheel_offset = tm->single_wheel.current_tick;
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);
287 before = clib_time_now (&tm->clib_time);
290 for (i = 0; i < tm->ntimers; i++)
292 pool_get (tm->test_elts, e);
293 clib_memset (e, 0, sizeof (*e));
297 expiration_time = random_u64 (&tm->seed) & (2047);
299 while (expiration_time == 0);
301 if (expiration_time > max_expiration_time)
302 max_expiration_time = expiration_time;
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,
313 for (i = 0; i < tm->niter; i++)
315 run_single_wheel (&tm->single_wheel, tm->ticks_per_iter);
318 vec_reset_length (deleted_indices);
320 pool_foreach (e, tm->test_elts,
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)
330 for (j = 0; j < vec_len (deleted_indices); j++)
332 pool_put_index (tm->test_elts, deleted_indices[j]);
337 for (j = 0; j < tm->ntimers / 4; j++)
339 pool_get (tm->test_elts, e);
340 clib_memset (e, 0, sizeof (*e));
344 expiration_time = random_u64 (&tm->seed) & (2047);
346 while (expiration_time == 0);
348 if (expiration_time > max_expiration_time)
349 max_expiration_time = expiration_time;
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 */ ,
360 vec_free (deleted_indices);
362 run_single_wheel (&tm->single_wheel, max_expiration_time + 1);
364 after = clib_time_now (&tm->clib_time);
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",
370 ((f64) adds + (f64) deletes +
371 (f64) tm->single_wheel.current_tick) / (after - before));
373 if (pool_elts (tm->test_elts))
374 fformat (stdout, "Note: %d elements remain in pool\n",
375 pool_elts (tm->test_elts));
378 pool_foreach (e, tm->test_elts,
380 fformat (stdout, "[%d] expected to expire %d\n",
382 e->expected_to_expire);
386 pool_free (tm->test_elts);
387 tw_timer_wheel_free_2t_1w_2048sl (&tm->single_wheel);
391 static clib_error_t *
392 test2_double (tw_timer_test_main_t * tm)
395 tw_timer_test_elt_t *e;
396 u32 initial_wheel_offset;
398 u32 max_expiration_time = 0;
399 u32 *deleted_indices = 0;
400 u32 adds = 0, deletes = 0;
403 clib_time_init (&tm->clib_time);
405 tw_timer_wheel_init_16t_2w_512sl (&tm->double_wheel,
406 expired_timer_double_callback,
407 1.0 /* timer interval */ , ~0);
410 initial_wheel_offset = 7577;
412 run_double_wheel (&tm->double_wheel, initial_wheel_offset);
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]);
419 initial_wheel_offset = tm->double_wheel.current_tick;
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);
425 before = clib_time_now (&tm->clib_time);
428 for (i = 0; i < tm->ntimers; i++)
430 pool_get (tm->test_elts, e);
431 clib_memset (e, 0, sizeof (*e));
435 expiration_time = random_u64 (&tm->seed) & ((1 << 17) - 1);
437 while (expiration_time == 0);
439 if (expiration_time > max_expiration_time)
440 max_expiration_time = expiration_time;
442 e->expected_to_expire = expiration_time + initial_wheel_offset;
444 e->stop_timer_handle =
445 tw_timer_start_16t_2w_512sl (&tm->double_wheel, e - tm->test_elts,
452 for (i = 0; i < tm->niter; i++)
454 run_double_wheel (&tm->double_wheel, tm->ticks_per_iter);
457 vec_reset_length (deleted_indices);
459 pool_foreach (e, tm->test_elts,
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)
469 for (j = 0; j < vec_len (deleted_indices); j++)
470 pool_put_index (tm->test_elts, deleted_indices[j]);
474 for (j = 0; j < tm->ntimers / 4; j++)
476 pool_get (tm->test_elts, e);
477 clib_memset (e, 0, sizeof (*e));
481 expiration_time = random_u64 (&tm->seed) & ((1 << 17) - 1);
483 while (expiration_time == 0);
485 if (expiration_time > max_expiration_time)
486 max_expiration_time = expiration_time;
488 e->expected_to_expire = expiration_time +
489 tm->double_wheel.current_tick;
491 e->stop_timer_handle = tw_timer_start_16t_2w_512sl
492 (&tm->double_wheel, e - tm->test_elts, 14 /* timer id */ ,
498 vec_free (deleted_indices);
500 run_double_wheel (&tm->double_wheel, max_expiration_time + 1);
502 after = clib_time_now (&tm->clib_time);
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",
508 ((f64) adds + (f64) deletes +
509 (f64) tm->double_wheel.current_tick) / (after - before));
511 if (pool_elts (tm->test_elts))
512 fformat (stdout, "Note: %d elements remain in pool\n",
513 pool_elts (tm->test_elts));
516 pool_foreach (e, tm->test_elts,
518 fformat (stdout, "[%d] expected to expire %d\n",
520 e->expected_to_expire);
524 pool_free (tm->test_elts);
525 tw_timer_wheel_free_16t_2w_512sl (&tm->double_wheel);
530 get_expiration_time (tw_timer_test_main_t * tm)
535 expiration_time = random_u64 (&tm->seed) & ((1 << 17) - 1);
537 while (expiration_time == 0);
538 return expiration_time;
541 static clib_error_t *
542 test2_double_updates (tw_timer_test_main_t * tm)
545 tw_timer_test_elt_t *e;
546 u32 initial_wheel_offset;
548 u32 max_expiration_time = 0, updates = 0;
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);
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]);
564 initial_wheel_offset = tm->double_wheel.current_tick;
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);
569 before = clib_time_now (&tm->clib_time);
572 for (i = 0; i < tm->ntimers; i++)
574 pool_get (tm->test_elts, e);
575 clib_memset (e, 0, sizeof (*e));
577 expiration_time = get_expiration_time (tm);
578 max_expiration_time = clib_max (expiration_time, max_expiration_time);
580 e->expected_to_expire = expiration_time + initial_wheel_offset;
581 e->stop_timer_handle = tw_timer_start_16t_2w_512sl (&tm->double_wheel,
587 for (i = 0; i < tm->niter; i++)
589 run_double_wheel (&tm->double_wheel, tm->ticks_per_iter);
594 pool_foreach (e, tm->test_elts,
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,
602 if (++j >= tm->ntimers / 4)
611 run_double_wheel (&tm->double_wheel, max_expiration_time + 1);
613 after = clib_time_now (&tm->clib_time);
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",
619 ((f64) updates + (f64) tm->double_wheel.current_tick) / (after -
622 if (pool_elts (tm->test_elts))
623 fformat (stdout, "Note: %d elements remain in pool\n",
624 pool_elts (tm->test_elts));
627 pool_foreach (e, tm->test_elts,
629 fformat (stdout, "[%d] expected to expire %d\n",
631 e->expected_to_expire);
635 pool_free (tm->test_elts);
636 tw_timer_wheel_free_16t_2w_512sl (&tm->double_wheel);
640 static clib_error_t *
641 test2_triple (tw_timer_test_main_t * tm)
644 tw_timer_test_elt_t *e;
645 u32 initial_wheel_offset = 0;
647 u32 max_expiration_time = 0;
648 u32 *deleted_indices = 0;
649 u32 adds = 0, deletes = 0;
652 clib_time_init (&tm->clib_time);
654 tw_timer_wheel_init_4t_3w_256sl (&tm->triple_wheel,
655 expired_timer_triple_callback,
656 1.0 /* timer interval */ , ~0);
660 initial_wheel_offset = 75700;
661 run_triple_wheel (&tm->triple_wheel, initial_wheel_offset);
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]);
670 initial_wheel_offset = tm->triple_wheel.current_tick;
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);
676 before = clib_time_now (&tm->clib_time);
679 for (i = 0; i < tm->ntimers; i++)
681 pool_get (tm->test_elts, e);
682 clib_memset (e, 0, sizeof (*e));
686 expiration_time = random_u64 (&tm->seed) & ((1 << 17) - 1);
688 while (expiration_time == 0);
690 if (expiration_time > max_expiration_time)
691 max_expiration_time = expiration_time;
693 e->expected_to_expire = expiration_time + initial_wheel_offset;
695 e->stop_timer_handle =
696 tw_timer_start_4t_3w_256sl (&tm->triple_wheel, e - tm->test_elts,
703 for (i = 0; i < tm->niter; i++)
705 run_triple_wheel (&tm->triple_wheel, tm->ticks_per_iter);
708 vec_reset_length (deleted_indices);
710 pool_foreach (e, tm->test_elts,
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)
720 for (j = 0; j < vec_len (deleted_indices); j++)
721 pool_put_index (tm->test_elts, deleted_indices[j]);
725 for (j = 0; j < tm->ntimers / 4; j++)
727 pool_get (tm->test_elts, e);
728 clib_memset (e, 0, sizeof (*e));
732 expiration_time = random_u64 (&tm->seed) & ((1 << 17) - 1);
734 while (expiration_time == 0);
736 if (expiration_time > max_expiration_time)
737 max_expiration_time = expiration_time;
739 e->expected_to_expire = expiration_time +
740 tm->triple_wheel.current_tick;
742 e->stop_timer_handle = tw_timer_start_4t_3w_256sl
743 (&tm->triple_wheel, e - tm->test_elts, 3 /* timer id */ ,
749 vec_free (deleted_indices);
751 run_triple_wheel (&tm->triple_wheel, max_expiration_time + 1);
753 after = clib_time_now (&tm->clib_time);
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",
759 ((f64) adds + (f64) deletes +
760 (f64) tm->triple_wheel.current_tick) / (after - before));
762 if (pool_elts (tm->test_elts))
763 fformat (stdout, "Note: %d elements remain in pool\n",
764 pool_elts (tm->test_elts));
767 pool_foreach (e, tm->test_elts,
769 fformat (stdout, "[%d] expected to expire %d\n",
771 e->expected_to_expire);
775 pool_free (tm->test_elts);
776 tw_timer_wheel_free_4t_3w_256sl (&tm->triple_wheel);
780 static clib_error_t *
781 test2_triple_ov (tw_timer_test_main_t * tm)
784 tw_timer_test_elt_t *e;
785 u32 initial_wheel_offset = 0;
787 u32 max_expiration_time = 0;
788 u32 *deleted_indices = 0;
789 u32 adds = 0, deletes = 0;
792 clib_time_init (&tm->clib_time);
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);
800 initial_wheel_offset = 75700;
801 run_triple_ov_wheel (&tm->triple_ov_wheel, initial_wheel_offset);
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]);
810 initial_wheel_offset = tm->triple_ov_wheel.current_tick;
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);
816 before = clib_time_now (&tm->clib_time);
819 for (i = 0; i < tm->ntimers; i++)
821 pool_get (tm->test_elts, e);
822 clib_memset (e, 0, sizeof (*e));
826 expiration_time = random_u64 (&tm->seed) & ((1 << 17) - 1);
828 while (expiration_time == 0);
830 if (expiration_time > max_expiration_time)
831 max_expiration_time = expiration_time;
833 e->expected_to_expire = expiration_time + initial_wheel_offset;
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 */ ,
843 for (i = 0; i < tm->niter; i++)
845 run_triple_ov_wheel (&tm->triple_ov_wheel, tm->ticks_per_iter);
848 vec_reset_length (deleted_indices);
850 pool_foreach (e, tm->test_elts,
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)
861 for (j = 0; j < vec_len (deleted_indices); j++)
862 pool_put_index (tm->test_elts, deleted_indices[j]);
866 for (j = 0; j < tm->ntimers / 4; j++)
868 pool_get (tm->test_elts, e);
869 clib_memset (e, 0, sizeof (*e));
873 expiration_time = random_u64 (&tm->seed) & ((1 << 17) - 1);
875 while (expiration_time == 0);
877 if (expiration_time > max_expiration_time)
878 max_expiration_time = expiration_time;
880 e->expected_to_expire = expiration_time +
881 tm->triple_ov_wheel.current_tick;
883 e->stop_timer_handle = tw_timer_start_1t_3w_1024sl_ov
884 (&tm->triple_ov_wheel, e - tm->test_elts, 0 /* timer id */ ,
890 vec_free (deleted_indices);
892 run_triple_ov_wheel (&tm->triple_ov_wheel, max_expiration_time + 1);
894 after = clib_time_now (&tm->clib_time);
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",
900 ((f64) adds + (f64) deletes +
901 (f64) tm->triple_ov_wheel.current_tick) / (after - before));
903 if (pool_elts (tm->test_elts))
904 fformat (stdout, "Note: %d elements remain in pool\n",
905 pool_elts (tm->test_elts));
908 pool_foreach (e, tm->test_elts,
912 fformat (stdout, "[%d] expected to expire %d\n",
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);
920 pool_free (tm->test_elts);
921 tw_timer_wheel_free_1t_3w_1024sl_ov (&tm->triple_ov_wheel);
925 static clib_error_t *
926 test1_single (tw_timer_test_main_t * tm)
929 tw_timer_test_elt_t *e;
932 tw_timer_wheel_init_2t_1w_2048sl (&tm->single_wheel,
933 expired_timer_single_callback,
934 1.0 /* timer interval */ , ~0);
937 * Prime offset, to make sure that the wheel starts in a
938 * non-trivial position
942 run_single_wheel (&tm->single_wheel, offset);
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]);
948 offset = tm->single_wheel.current_tick;
950 for (i = 0; i < tm->ntimers; i++)
952 u32 expected_to_expire;
960 expected_to_expire = timer_arg + tm->single_wheel.current_tick;
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 */ ,
969 run_single_wheel (&tm->single_wheel, tm->ntimers + 3);
971 if (pool_elts (tm->test_elts))
972 fformat (stdout, "Note: %d elements remain in pool\n",
973 pool_elts (tm->test_elts));
976 pool_foreach (e, tm->test_elts,
978 fformat(stdout, "[%d] expected to expire %d\n",
980 e->expected_to_expire);
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]);
989 pool_free (tm->test_elts);
990 tw_timer_wheel_free_2t_1w_2048sl (&tm->single_wheel);
994 static clib_error_t *
995 test1_double (tw_timer_test_main_t * tm)
998 tw_timer_test_elt_t *e;
1001 tw_timer_wheel_init_16t_2w_512sl (&tm->double_wheel,
1002 expired_timer_double_callback,
1003 1.0 /* timer interval */ , ~0);
1006 * Prime offset, to make sure that the wheel starts in a
1007 * non-trivial position
1011 run_double_wheel (&tm->double_wheel, offset);
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]);
1017 for (i = 0; i < tm->ntimers; i++)
1019 pool_get (tm->test_elts, e);
1020 clib_memset (e, 0, sizeof (*e));
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 */ ,
1027 run_double_wheel (&tm->double_wheel, tm->ntimers + 3);
1029 if (pool_elts (tm->test_elts))
1030 fformat (stdout, "Note: %d elements remain in pool\n",
1031 pool_elts (tm->test_elts));
1034 pool_foreach (e, tm->test_elts,
1036 fformat(stdout, "[%d] expected to expire %d\n",
1038 e->expected_to_expire);
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]);
1047 pool_free (tm->test_elts);
1048 tw_timer_wheel_free_16t_2w_512sl (&tm->double_wheel);
1052 static clib_error_t *
1053 test1_two_timer_double (tw_timer_test_main_t * tm)
1056 tw_timer_test_elt_t *e;
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);
1064 * Prime offset, to make sure that the wheel starts in a
1065 * non-trivial position
1069 run_two_timer_double_wheel (&tm->two_timer_double_wheel, offset);
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]);
1075 for (i = 0; i < tm->ntimers; i++)
1077 pool_get (tm->test_elts, e);
1078 clib_memset (e, 0, sizeof (*e));
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 */ ,
1085 run_two_timer_double_wheel (&tm->two_timer_double_wheel, tm->ntimers + 3);
1087 if (pool_elts (tm->test_elts))
1088 fformat (stdout, "Note: %d elements remain in pool\n",
1089 pool_elts (tm->test_elts));
1092 pool_foreach (e, tm->test_elts,
1094 fformat(stdout, "[%d] expected to expire %d\n",
1096 e->expected_to_expire);
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]);
1105 pool_free (tm->test_elts);
1106 tw_timer_wheel_free_2t_2w_512sl (&tm->two_timer_double_wheel);
1110 static clib_error_t *
1111 test3_triple_double (tw_timer_test_main_t * tm)
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;
1120 clib_time_init (&tm->clib_time);
1122 tw_timer_wheel_init_4t_3w_256sl (&tm->triple_wheel,
1123 expired_timer_triple_callback,
1124 1.0 /* timer interval */ , ~0);
1126 initial_wheel_offset = 0;
1127 run_triple_wheel (&tm->triple_wheel, initial_wheel_offset);
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]);
1136 initial_wheel_offset = tm->triple_wheel.current_tick;
1138 fformat (stdout, "Create a timer which expires at wheel-time (1, 0, 0)\n");
1140 before = clib_time_now (&tm->clib_time);
1142 /* Prime the pump */
1143 pool_get (tm->test_elts, e);
1144 clib_memset (e, 0, sizeof (*e));
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;
1151 e->stop_timer_handle =
1152 tw_timer_start_4t_3w_256sl (&tm->triple_wheel, e - tm->test_elts,
1156 run_triple_wheel (&tm->triple_wheel, max_expiration_time + 1);
1158 after = clib_time_now (&tm->clib_time);
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",
1164 ((f64) adds + (f64) deletes +
1165 (f64) tm->triple_wheel.current_tick) / (after - before));
1167 if (pool_elts (tm->test_elts))
1168 fformat (stdout, "Note: %d elements remain in pool\n",
1169 pool_elts (tm->test_elts));
1172 pool_foreach (e, tm->test_elts,
1174 fformat (stdout, "[%d] expected to expire %d\n",
1176 e->expected_to_expire);
1180 pool_free (tm->test_elts);
1181 tw_timer_wheel_free_4t_3w_256sl (&tm->triple_wheel);
1185 static clib_error_t *
1186 test4_double_double (tw_timer_test_main_t * tm)
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;
1197 clib_time_init (&tm->clib_time);
1199 tw_timer_wheel_init_16t_2w_512sl (&tm->double_wheel,
1200 expired_timer_double_callback,
1201 1.0 /* timer interval */ , ~0);
1203 initial_wheel_offset = 0;
1205 run_double_wheel (&tm->double_wheel, initial_wheel_offset);
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]);
1212 initial_wheel_offset = tm->double_wheel.current_tick;
1214 fformat (stdout, "test timer which expires at 512 ticks\n");
1216 before = clib_time_now (&tm->clib_time);
1218 /* Prime the pump */
1219 for (i = 0; i < tm->ntimers; i++)
1221 pool_get (tm->test_elts, e);
1222 clib_memset (e, 0, sizeof (*e));
1224 expiration_time = 512;
1226 if (expiration_time > max_expiration_time)
1227 max_expiration_time = expiration_time;
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,
1238 vec_free (deleted_indices);
1240 run_double_wheel (&tm->double_wheel, max_expiration_time + 1);
1242 after = clib_time_now (&tm->clib_time);
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",
1248 ((f64) adds + (f64) deletes +
1249 (f64) tm->double_wheel.current_tick) / (after - before));
1251 if (pool_elts (tm->test_elts))
1252 fformat (stdout, "Note: %d elements remain in pool\n",
1253 pool_elts (tm->test_elts));
1256 pool_foreach (e, tm->test_elts,
1258 fformat (stdout, "[%d] expected to expire %d\n",
1260 e->expected_to_expire);
1264 pool_free (tm->test_elts);
1265 tw_timer_wheel_free_16t_2w_512sl (&tm->double_wheel);
1269 static clib_error_t *
1270 test5_double (tw_timer_test_main_t * tm)
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;
1280 clib_time_init (&tm->clib_time);
1282 tw_timer_wheel_init_16t_2w_512sl (&tm->double_wheel,
1283 expired_timer_double_callback,
1284 1.0 /* timer interval */ , ~0);
1287 initial_wheel_offset = 7567;
1289 run_double_wheel (&tm->double_wheel, initial_wheel_offset);
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]);
1296 initial_wheel_offset = tm->double_wheel.current_tick;
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);
1302 before = clib_time_now (&tm->clib_time);
1304 /* Prime the pump */
1305 for (i = 0; i < tm->ntimers; i++)
1307 pool_get (tm->test_elts, e);
1308 clib_memset (e, 0, sizeof (*e));
1310 expiration_time = i + 1;
1312 if (expiration_time > max_expiration_time)
1313 max_expiration_time = expiration_time;
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,
1324 run_double_wheel (&tm->double_wheel, max_expiration_time + 1);
1326 after = clib_time_now (&tm->clib_time);
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",
1332 ((f64) adds + (f64) deletes +
1333 (f64) tm->double_wheel.current_tick) / (after - before));
1335 if (pool_elts (tm->test_elts))
1336 fformat (stdout, "Note: %d elements remain in pool\n",
1337 pool_elts (tm->test_elts));
1340 pool_foreach (e, tm->test_elts,
1342 fformat (stdout, "[%d] expected to expire %d\n",
1344 e->expected_to_expire);
1348 pool_free (tm->test_elts);
1349 tw_timer_wheel_free_16t_2w_512sl (&tm->double_wheel);
1353 static clib_error_t *
1354 timer_test_command_fn (tw_timer_test_main_t * tm, unformat_input_t * input)
1357 int is_test1 = 0, is_updates = 0;
1365 clib_memset (tm, 0, sizeof (*tm));
1366 /* Default values */
1367 tm->ntimers = 100000;
1368 tm->seed = 0xDEADDABEB00BFACE;
1370 tm->ticks_per_iter = 727;
1372 while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
1374 if (unformat (input, "seed %lld", &tm->seed))
1376 else if (unformat (input, "test1"))
1378 else if (unformat (input, "test2"))
1380 else if (unformat (input, "overflow"))
1382 else if (unformat (input, "lebron"))
1384 else if (unformat (input, "wilt"))
1386 else if (unformat (input, "linear"))
1388 else if (unformat (input, "updates"))
1390 else if (unformat (input, "wheels %d", &num_wheels))
1392 else if (unformat (input, "ntimers %d", &tm->ntimers))
1394 else if (unformat (input, "niter %d", &tm->niter))
1396 else if (unformat (input, "ticks_per_iter %d", &tm->ticks_per_iter))
1402 if (is_test1 + is_test2 + is_test3 + is_test4 + is_test5 == 0)
1403 return clib_error_return (0, "No test specified [test1..n]");
1405 if (num_wheels < 1 || num_wheels > 3)
1406 return clib_error_return (0, "unsupported... 1 or 2 wheels only");
1410 if (num_wheels == 1)
1411 return test1_single (tm);
1414 (void) test1_double (tm);
1415 return test1_two_timer_double (tm);
1420 if (num_wheels == 1)
1421 return test2_single (tm);
1422 else if (num_wheels == 2)
1424 return test2_double_updates (tm);
1426 return test2_double (tm);
1427 else if (num_wheels == 3)
1430 return test2_triple (tm);
1432 return test2_triple_ov (tm);
1436 return test3_triple_double (tm);
1439 return test4_double_double (tm);
1442 return test5_double (tm);
1450 main (int argc, char *argv[])
1453 clib_error_t *error;
1454 tw_timer_test_main_t *tm = &tw_timer_test_main;
1456 clib_mem_init (0, 3ULL << 30);
1458 unformat_init_command_line (&i, argv);
1459 error = timer_test_command_fn (tm, &i);
1464 clib_error_report (error);
1469 #endif /* CLIB_UNIX */
1471 /* For debugging... */
1473 pifi (void *p, u32 index)
1475 return pool_is_free_index (p, index);
1487 return (pool_elts (v));
1491 * fd.io coding-style-patch-verification: ON
1494 * eval: (c-set-style "gnu")