1 #include <vppinfra/time.h>
2 #include <vppinfra/cache.h>
3 #include <vppinfra/error.h>
4 #include <vppinfra/tw_timer_2t_1w_2048sl.h>
5 #include <vppinfra/tw_timer_16t_2w_512sl.h>
6 #include <vppinfra/tw_timer_4t_3w_256sl.h>
7 #include <vppinfra/tw_timer_1t_3w_1024sl_ov.h>
11 /** Handle returned from tw_start_timer */
12 u32 stop_timer_handle;
14 /** Test item should expire at this clock tick */
15 u64 expected_to_expire;
16 } tw_timer_test_elt_t;
20 /** Pool of test objects */
21 tw_timer_test_elt_t *test_elts;
23 /** The single-wheel */
24 tw_timer_wheel_2t_1w_2048sl_t single_wheel;
26 /** The double-wheel */
27 tw_timer_wheel_16t_2w_512sl_t double_wheel;
29 /* The triple wheel */
30 tw_timer_wheel_4t_3w_256sl_t triple_wheel;
32 /* The triple wheel with overflow vector */
33 tw_timer_wheel_1t_3w_1024sl_ov_t triple_ov_wheel;
35 /** random number seed */
38 /** number of timers */
41 /** number of "churn" iterations */
44 /** number of clock ticks per churn iteration */
48 clib_time_t clib_time;
49 } tw_timer_test_main_t;
51 tw_timer_test_main_t tw_timer_test_main;
54 run_single_wheel (tw_timer_wheel_2t_1w_2048sl_t * tw, u32 n_ticks)
57 f64 now = tw->last_run_time + 1.01;
59 for (i = 0; i < n_ticks; i++)
61 tw_timer_expire_timers_2t_1w_2048sl (tw, now);
67 run_double_wheel (tw_timer_wheel_16t_2w_512sl_t * tw, u32 n_ticks)
70 f64 now = tw->last_run_time + 1.01;
72 for (i = 0; i < n_ticks; i++)
74 tw_timer_expire_timers_16t_2w_512sl (tw, now);
80 run_triple_wheel (tw_timer_wheel_4t_3w_256sl_t * tw, u32 n_ticks)
83 f64 now = tw->last_run_time + 1.01;
85 for (i = 0; i < n_ticks; i++)
87 tw_timer_expire_timers_4t_3w_256sl (tw, now);
93 run_triple_ov_wheel (tw_timer_wheel_1t_3w_1024sl_ov_t * tw, u32 n_ticks)
96 f64 now = tw->last_run_time + 1.01;
98 for (i = 0; i < n_ticks; i++)
100 tw_timer_expire_timers_1t_3w_1024sl_ov (tw, now);
106 expired_timer_single_callback (u32 * expired_timers)
109 u32 pool_index, timer_id;
110 tw_timer_test_elt_t *e;
111 tw_timer_test_main_t *tm = &tw_timer_test_main;
113 for (i = 0; i < vec_len (expired_timers); i++)
115 pool_index = expired_timers[i] & 0x7FFFFFFF;
116 timer_id = expired_timers[i] >> 31;
118 ASSERT (timer_id == 1);
120 e = pool_elt_at_index (tm->test_elts, pool_index);
122 if (e->expected_to_expire != tm->single_wheel.current_tick)
124 fformat (stdout, "[%d] expired at %lld not %lld\n",
125 e - tm->test_elts, tm->single_wheel.current_tick,
126 e->expected_to_expire);
128 pool_put (tm->test_elts, e);
133 expired_timer_double_callback (u32 * expired_timers)
136 u32 pool_index, timer_id;
137 tw_timer_test_elt_t *e;
138 tw_timer_test_main_t *tm = &tw_timer_test_main;
140 for (i = 0; i < vec_len (expired_timers); i++)
142 pool_index = expired_timers[i] & 0x0FFFFFFF;
143 timer_id = expired_timers[i] >> 28;
145 ASSERT (timer_id == 14);
147 e = pool_elt_at_index (tm->test_elts, pool_index);
149 if (e->expected_to_expire != tm->double_wheel.current_tick)
151 fformat (stdout, "[%d] expired at %lld not %lld\n",
152 e - tm->test_elts, tm->double_wheel.current_tick,
153 e->expected_to_expire);
155 pool_put (tm->test_elts, e);
160 expired_timer_triple_callback (u32 * expired_timers)
163 u32 pool_index, timer_id;
164 tw_timer_test_elt_t *e;
165 tw_timer_test_main_t *tm = &tw_timer_test_main;
167 for (i = 0; i < vec_len (expired_timers); i++)
169 pool_index = expired_timers[i] & 0x3FFFFFFF;
170 timer_id = expired_timers[i] >> 30;
172 ASSERT (timer_id == 3);
174 e = pool_elt_at_index (tm->test_elts, pool_index);
176 if (e->expected_to_expire != tm->triple_wheel.current_tick)
178 fformat (stdout, "[%d] expired at %lld not %lld\n",
179 e - tm->test_elts, tm->triple_wheel.current_tick,
180 e->expected_to_expire);
182 pool_put (tm->test_elts, e);
187 expired_timer_triple_ov_callback (u32 * expired_timers)
191 tw_timer_test_elt_t *e;
192 tw_timer_test_main_t *tm = &tw_timer_test_main;
194 for (i = 0; i < vec_len (expired_timers); i++)
196 pool_index = expired_timers[i];
198 e = pool_elt_at_index (tm->test_elts, pool_index);
200 if (e->expected_to_expire != tm->triple_ov_wheel.current_tick)
202 fformat (stdout, "[%d] expired at %lld not %lld\n",
203 e - tm->test_elts, tm->triple_ov_wheel.current_tick,
204 e->expected_to_expire);
206 pool_put (tm->test_elts, e);
210 static clib_error_t *
211 test2_single (tw_timer_test_main_t * tm)
214 tw_timer_test_elt_t *e;
215 u32 initial_wheel_offset;
217 u32 max_expiration_time = 0;
218 u32 *deleted_indices = 0;
219 u32 adds = 0, deletes = 0;
222 clib_time_init (&tm->clib_time);
224 tw_timer_wheel_init_2t_1w_2048sl (&tm->single_wheel,
225 expired_timer_single_callback,
226 1.0 /* timer interval */ , ~0);
229 initial_wheel_offset = 757;
231 run_single_wheel (&tm->single_wheel, initial_wheel_offset);
233 fformat (stdout, "initial wheel time %d, fast index %d\n",
234 tm->single_wheel.current_tick,
235 tm->single_wheel.current_index[TW_TIMER_RING_FAST]);
237 initial_wheel_offset = tm->single_wheel.current_tick;
240 "test %d timers, %d iter, %d ticks per iter, 0x%llx seed\n",
241 tm->ntimers, tm->niter, tm->ticks_per_iter, tm->seed);
243 before = clib_time_now (&tm->clib_time);
246 for (i = 0; i < tm->ntimers; i++)
248 pool_get (tm->test_elts, e);
249 memset (e, 0, sizeof (*e));
253 expiration_time = random_u64 (&tm->seed) & (2047);
255 while (expiration_time == 0);
257 if (expiration_time > max_expiration_time)
258 max_expiration_time = expiration_time;
260 e->expected_to_expire = expiration_time + initial_wheel_offset;
261 e->stop_timer_handle =
262 tw_timer_start_2t_1w_2048sl (&tm->single_wheel, e - tm->test_elts,
269 for (i = 0; i < tm->niter; i++)
271 run_single_wheel (&tm->single_wheel, tm->ticks_per_iter);
274 vec_reset_length (deleted_indices);
276 pool_foreach (e, tm->test_elts,
278 tw_timer_stop_2t_1w_2048sl (&tm->single_wheel, e->stop_timer_handle);
279 vec_add1 (deleted_indices, e - tm->test_elts);
280 if (++j >= tm->ntimers / 4)
286 for (j = 0; j < vec_len (deleted_indices); j++)
288 pool_put_index (tm->test_elts, deleted_indices[j]);
293 for (j = 0; j < tm->ntimers / 4; j++)
295 pool_get (tm->test_elts, e);
296 memset (e, 0, sizeof (*e));
300 expiration_time = random_u64 (&tm->seed) & (2047);
302 while (expiration_time == 0);
304 if (expiration_time > max_expiration_time)
305 max_expiration_time = expiration_time;
307 e->expected_to_expire =
308 expiration_time + tm->single_wheel.current_tick;
309 e->stop_timer_handle = tw_timer_start_2t_1w_2048sl
310 (&tm->single_wheel, e - tm->test_elts, 1 /* timer id */ ,
316 vec_free (deleted_indices);
318 run_single_wheel (&tm->single_wheel, max_expiration_time + 1);
320 after = clib_time_now (&tm->clib_time);
322 fformat (stdout, "%d adds, %d deletes, %d ticks\n", adds, deletes,
323 tm->single_wheel.current_tick);
324 fformat (stdout, "test ran %.2f seconds, %.2f ops/second\n",
326 ((f64) adds + (f64) deletes +
327 (f64) tm->single_wheel.current_tick) / (after - before));
329 if (pool_elts (tm->test_elts))
330 fformat (stdout, "Note: %d elements remain in pool\n",
331 pool_elts (tm->test_elts));
334 pool_foreach (e, tm->test_elts,
336 fformat (stdout, "[%d] expected to expire %d\n",
338 e->expected_to_expire);
342 pool_free (tm->test_elts);
343 tw_timer_wheel_free_2t_1w_2048sl (&tm->single_wheel);
347 static clib_error_t *
348 test2_double (tw_timer_test_main_t * tm)
351 tw_timer_test_elt_t *e;
352 u32 initial_wheel_offset;
354 u32 max_expiration_time = 0;
355 u32 *deleted_indices = 0;
356 u32 adds = 0, deletes = 0;
359 clib_time_init (&tm->clib_time);
361 tw_timer_wheel_init_16t_2w_512sl (&tm->double_wheel,
362 expired_timer_double_callback,
363 1.0 /* timer interval */ , ~0);
366 initial_wheel_offset = 7577;
368 run_double_wheel (&tm->double_wheel, initial_wheel_offset);
370 fformat (stdout, "initial wheel time %d, fast index %d slow index %d\n",
371 tm->double_wheel.current_tick,
372 tm->double_wheel.current_index[TW_TIMER_RING_FAST],
373 tm->double_wheel.current_index[TW_TIMER_RING_SLOW]);
375 initial_wheel_offset = tm->double_wheel.current_tick;
378 "test %d timers, %d iter, %d ticks per iter, 0x%llx seed\n",
379 tm->ntimers, tm->niter, tm->ticks_per_iter, tm->seed);
381 before = clib_time_now (&tm->clib_time);
384 for (i = 0; i < tm->ntimers; i++)
386 pool_get (tm->test_elts, e);
387 memset (e, 0, sizeof (*e));
391 expiration_time = random_u64 (&tm->seed) & ((1 << 17) - 1);
393 while (expiration_time == 0);
395 if (expiration_time > max_expiration_time)
396 max_expiration_time = expiration_time;
398 e->expected_to_expire = expiration_time + initial_wheel_offset;
400 e->stop_timer_handle =
401 tw_timer_start_16t_2w_512sl (&tm->double_wheel, e - tm->test_elts,
408 for (i = 0; i < tm->niter; i++)
410 run_double_wheel (&tm->double_wheel, tm->ticks_per_iter);
413 vec_reset_length (deleted_indices);
415 pool_foreach (e, tm->test_elts,
417 tw_timer_stop_16t_2w_512sl (&tm->double_wheel, e->stop_timer_handle);
418 vec_add1 (deleted_indices, e - tm->test_elts);
419 if (++j >= tm->ntimers / 4)
425 for (j = 0; j < vec_len (deleted_indices); j++)
426 pool_put_index (tm->test_elts, deleted_indices[j]);
430 for (j = 0; j < tm->ntimers / 4; j++)
432 pool_get (tm->test_elts, e);
433 memset (e, 0, sizeof (*e));
437 expiration_time = random_u64 (&tm->seed) & ((1 << 17) - 1);
439 while (expiration_time == 0);
441 if (expiration_time > max_expiration_time)
442 max_expiration_time = expiration_time;
444 e->expected_to_expire = expiration_time +
445 tm->double_wheel.current_tick;
447 e->stop_timer_handle = tw_timer_start_16t_2w_512sl
448 (&tm->double_wheel, e - tm->test_elts, 14 /* timer id */ ,
454 vec_free (deleted_indices);
456 run_double_wheel (&tm->double_wheel, max_expiration_time + 1);
458 after = clib_time_now (&tm->clib_time);
460 fformat (stdout, "%d adds, %d deletes, %d ticks\n", adds, deletes,
461 tm->double_wheel.current_tick);
462 fformat (stdout, "test ran %.2f seconds, %.2f ops/second\n",
464 ((f64) adds + (f64) deletes +
465 (f64) tm->double_wheel.current_tick) / (after - before));
467 if (pool_elts (tm->test_elts))
468 fformat (stdout, "Note: %d elements remain in pool\n",
469 pool_elts (tm->test_elts));
472 pool_foreach (e, tm->test_elts,
474 fformat (stdout, "[%d] expected to expire %d\n",
476 e->expected_to_expire);
480 pool_free (tm->test_elts);
481 tw_timer_wheel_free_16t_2w_512sl (&tm->double_wheel);
485 static clib_error_t *
486 test2_triple (tw_timer_test_main_t * tm)
489 tw_timer_test_elt_t *e;
490 u32 initial_wheel_offset = 0;
492 u32 max_expiration_time = 0;
493 u32 *deleted_indices = 0;
494 u32 adds = 0, deletes = 0;
497 clib_time_init (&tm->clib_time);
499 tw_timer_wheel_init_4t_3w_256sl (&tm->triple_wheel,
500 expired_timer_triple_callback,
501 1.0 /* timer interval */ , ~0);
505 initial_wheel_offset = 75700;
506 run_triple_wheel (&tm->triple_wheel, initial_wheel_offset);
509 "initial wheel time %d, fi %d si %d gi %d\n",
510 tm->triple_wheel.current_tick,
511 tm->triple_wheel.current_index[TW_TIMER_RING_FAST],
512 tm->triple_wheel.current_index[TW_TIMER_RING_SLOW],
513 tm->triple_wheel.current_index[TW_TIMER_RING_GLACIER]);
515 initial_wheel_offset = tm->triple_wheel.current_tick;
518 "test %d timers, %d iter, %d ticks per iter, 0x%llx seed\n",
519 tm->ntimers, tm->niter, tm->ticks_per_iter, tm->seed);
521 before = clib_time_now (&tm->clib_time);
524 for (i = 0; i < tm->ntimers; i++)
526 pool_get (tm->test_elts, e);
527 memset (e, 0, sizeof (*e));
531 expiration_time = random_u64 (&tm->seed) & ((1 << 17) - 1);
533 while (expiration_time == 0);
535 if (expiration_time > max_expiration_time)
536 max_expiration_time = expiration_time;
538 e->expected_to_expire = expiration_time + initial_wheel_offset;
540 e->stop_timer_handle =
541 tw_timer_start_4t_3w_256sl (&tm->triple_wheel, e - tm->test_elts,
548 for (i = 0; i < tm->niter; i++)
550 run_triple_wheel (&tm->triple_wheel, tm->ticks_per_iter);
553 vec_reset_length (deleted_indices);
555 pool_foreach (e, tm->test_elts,
557 tw_timer_stop_4t_3w_256sl (&tm->triple_wheel, e->stop_timer_handle);
558 vec_add1 (deleted_indices, e - tm->test_elts);
559 if (++j >= tm->ntimers / 4)
565 for (j = 0; j < vec_len (deleted_indices); j++)
566 pool_put_index (tm->test_elts, deleted_indices[j]);
570 for (j = 0; j < tm->ntimers / 4; j++)
572 pool_get (tm->test_elts, e);
573 memset (e, 0, sizeof (*e));
577 expiration_time = random_u64 (&tm->seed) & ((1 << 17) - 1);
579 while (expiration_time == 0);
581 if (expiration_time > max_expiration_time)
582 max_expiration_time = expiration_time;
584 e->expected_to_expire = expiration_time +
585 tm->triple_wheel.current_tick;
587 e->stop_timer_handle = tw_timer_start_4t_3w_256sl
588 (&tm->triple_wheel, e - tm->test_elts, 3 /* timer id */ ,
594 vec_free (deleted_indices);
596 run_triple_wheel (&tm->triple_wheel, max_expiration_time + 1);
598 after = clib_time_now (&tm->clib_time);
600 fformat (stdout, "%d adds, %d deletes, %d ticks\n", adds, deletes,
601 tm->triple_wheel.current_tick);
602 fformat (stdout, "test ran %.2f seconds, %.2f ops/second\n",
604 ((f64) adds + (f64) deletes +
605 (f64) tm->triple_wheel.current_tick) / (after - before));
607 if (pool_elts (tm->test_elts))
608 fformat (stdout, "Note: %d elements remain in pool\n",
609 pool_elts (tm->test_elts));
612 pool_foreach (e, tm->test_elts,
614 fformat (stdout, "[%d] expected to expire %d\n",
616 e->expected_to_expire);
620 pool_free (tm->test_elts);
621 tw_timer_wheel_free_4t_3w_256sl (&tm->triple_wheel);
625 static clib_error_t *
626 test2_triple_ov (tw_timer_test_main_t * tm)
629 tw_timer_test_elt_t *e;
630 u32 initial_wheel_offset = 0;
632 u32 max_expiration_time = 0;
633 u32 *deleted_indices = 0;
634 u32 adds = 0, deletes = 0;
637 clib_time_init (&tm->clib_time);
639 tw_timer_wheel_init_1t_3w_1024sl_ov (&tm->triple_ov_wheel,
640 expired_timer_triple_ov_callback,
641 1.0 /* timer interval */ , ~0);
645 initial_wheel_offset = 75700;
646 run_triple_ov_wheel (&tm->triple_ov_wheel, initial_wheel_offset);
649 "initial wheel time %d, fi %d si %d gi %d\n",
650 tm->triple_ov_wheel.current_tick,
651 tm->triple_ov_wheel.current_index[TW_TIMER_RING_FAST],
652 tm->triple_ov_wheel.current_index[TW_TIMER_RING_SLOW],
653 tm->triple_ov_wheel.current_index[TW_TIMER_RING_GLACIER]);
655 initial_wheel_offset = tm->triple_ov_wheel.current_tick;
658 "test %d timers, %d iter, %d ticks per iter, 0x%llx seed\n",
659 tm->ntimers, tm->niter, tm->ticks_per_iter, tm->seed);
661 before = clib_time_now (&tm->clib_time);
664 for (i = 0; i < tm->ntimers; i++)
666 pool_get (tm->test_elts, e);
667 memset (e, 0, sizeof (*e));
671 expiration_time = random_u64 (&tm->seed) & ((1 << 17) - 1);
673 while (expiration_time == 0);
675 if (expiration_time > max_expiration_time)
676 max_expiration_time = expiration_time;
678 e->expected_to_expire = expiration_time + initial_wheel_offset;
680 e->stop_timer_handle =
681 tw_timer_start_1t_3w_1024sl_ov (&tm->triple_ov_wheel,
682 e - tm->test_elts, 0 /* timer id */ ,
688 for (i = 0; i < tm->niter; i++)
690 run_triple_ov_wheel (&tm->triple_ov_wheel, tm->ticks_per_iter);
693 vec_reset_length (deleted_indices);
695 pool_foreach (e, tm->test_elts,
697 tw_timer_stop_1t_3w_1024sl_ov (&tm->triple_ov_wheel,
698 e->stop_timer_handle);
699 vec_add1 (deleted_indices, e - tm->test_elts);
700 if (++j >= tm->ntimers / 4)
706 for (j = 0; j < vec_len (deleted_indices); j++)
707 pool_put_index (tm->test_elts, deleted_indices[j]);
711 for (j = 0; j < tm->ntimers / 4; j++)
713 pool_get (tm->test_elts, e);
714 memset (e, 0, sizeof (*e));
718 expiration_time = random_u64 (&tm->seed) & ((1 << 17) - 1);
720 while (expiration_time == 0);
722 if (expiration_time > max_expiration_time)
723 max_expiration_time = expiration_time;
725 e->expected_to_expire = expiration_time +
726 tm->triple_ov_wheel.current_tick;
728 e->stop_timer_handle = tw_timer_start_1t_3w_1024sl_ov
729 (&tm->triple_ov_wheel, e - tm->test_elts, 0 /* timer id */ ,
735 vec_free (deleted_indices);
737 run_triple_ov_wheel (&tm->triple_ov_wheel, max_expiration_time + 1);
739 after = clib_time_now (&tm->clib_time);
741 fformat (stdout, "%d adds, %d deletes, %d ticks\n", adds, deletes,
742 tm->triple_ov_wheel.current_tick);
743 fformat (stdout, "test ran %.2f seconds, %.2f ops/second\n",
745 ((f64) adds + (f64) deletes +
746 (f64) tm->triple_ov_wheel.current_tick) / (after - before));
748 if (pool_elts (tm->test_elts))
749 fformat (stdout, "Note: %d elements remain in pool\n",
750 pool_elts (tm->test_elts));
753 pool_foreach (e, tm->test_elts,
757 fformat (stdout, "[%d] expected to expire %d\n",
759 e->expected_to_expire);
760 t = pool_elt_at_index (tm->triple_ov_wheel.timers, e->stop_timer_handle);
761 fformat (stdout, " expiration_time %lld\n", t->expiration_time);
765 pool_free (tm->test_elts);
766 tw_timer_wheel_free_1t_3w_1024sl_ov (&tm->triple_ov_wheel);
770 static clib_error_t *
771 test1_single (tw_timer_test_main_t * tm)
774 tw_timer_test_elt_t *e;
777 tw_timer_wheel_init_2t_1w_2048sl (&tm->single_wheel,
778 expired_timer_single_callback,
779 1.0 /* timer interval */ , ~0);
782 * Prime offset, to make sure that the wheel starts in a
783 * non-trivial position
787 run_single_wheel (&tm->single_wheel, offset);
789 fformat (stdout, "initial wheel time %d, fast index %d\n",
790 tm->single_wheel.current_tick,
791 tm->single_wheel.current_index[TW_TIMER_RING_FAST]);
793 offset = tm->single_wheel.current_tick;
795 for (i = 0; i < tm->ntimers; i++)
797 u32 expected_to_expire;
805 expected_to_expire = timer_arg + offset;
807 pool_get (tm->test_elts, e);
808 memset (e, 0, sizeof (*e));
809 e->expected_to_expire = expected_to_expire;
810 e->stop_timer_handle = tw_timer_start_2t_1w_2048sl
811 (&tm->single_wheel, e - tm->test_elts, 1 /* timer id */ ,
814 run_single_wheel (&tm->single_wheel, tm->ntimers + 3);
816 if (pool_elts (tm->test_elts))
817 fformat (stdout, "Note: %d elements remain in pool\n",
818 pool_elts (tm->test_elts));
821 pool_foreach (e, tm->test_elts,
823 fformat(stdout, "[%d] expected to expire %d\n",
825 e->expected_to_expire);
830 "final wheel time %d, fast index %d\n",
831 tm->single_wheel.current_tick,
832 tm->single_wheel.current_index[TW_TIMER_RING_FAST]);
834 pool_free (tm->test_elts);
835 tw_timer_wheel_free_2t_1w_2048sl (&tm->single_wheel);
839 static clib_error_t *
840 test1_double (tw_timer_test_main_t * tm)
843 tw_timer_test_elt_t *e;
846 tw_timer_wheel_init_16t_2w_512sl (&tm->double_wheel,
847 expired_timer_double_callback,
848 1.0 /* timer interval */ , ~0);
851 * Prime offset, to make sure that the wheel starts in a
852 * non-trivial position
856 run_double_wheel (&tm->double_wheel, offset);
858 fformat (stdout, "initial wheel time %d, fast index %d\n",
859 tm->double_wheel.current_tick,
860 tm->double_wheel.current_index[TW_TIMER_RING_FAST]);
862 for (i = 0; i < tm->ntimers; i++)
864 pool_get (tm->test_elts, e);
865 memset (e, 0, sizeof (*e));
867 e->expected_to_expire = i + offset + 1;
868 e->stop_timer_handle = tw_timer_start_16t_2w_512sl
869 (&tm->double_wheel, e - tm->test_elts, 14 /* timer id */ ,
872 run_double_wheel (&tm->double_wheel, tm->ntimers + 3);
874 if (pool_elts (tm->test_elts))
875 fformat (stdout, "Note: %d elements remain in pool\n",
876 pool_elts (tm->test_elts));
879 pool_foreach (e, tm->test_elts,
881 fformat(stdout, "[%d] expected to expire %d\n",
883 e->expected_to_expire);
888 "final wheel time %d, fast index %d\n",
889 tm->double_wheel.current_tick,
890 tm->double_wheel.current_index[TW_TIMER_RING_FAST]);
892 pool_free (tm->test_elts);
893 tw_timer_wheel_free_16t_2w_512sl (&tm->double_wheel);
897 static clib_error_t *
898 test3_triple_double (tw_timer_test_main_t * tm)
900 tw_timer_test_elt_t *e;
901 u32 initial_wheel_offset = 0;
903 u32 max_expiration_time = 0;
904 u32 adds = 0, deletes = 0;
907 clib_time_init (&tm->clib_time);
909 tw_timer_wheel_init_4t_3w_256sl (&tm->triple_wheel,
910 expired_timer_triple_callback,
911 1.0 /* timer interval */ , ~0);
913 initial_wheel_offset = 0;
914 run_triple_wheel (&tm->triple_wheel, initial_wheel_offset);
917 "initial wheel time %d, fi %d si %d gi %d\n",
918 tm->triple_wheel.current_tick,
919 tm->triple_wheel.current_index[TW_TIMER_RING_FAST],
920 tm->triple_wheel.current_index[TW_TIMER_RING_SLOW],
921 tm->triple_wheel.current_index[TW_TIMER_RING_GLACIER]);
923 initial_wheel_offset = tm->triple_wheel.current_tick;
925 fformat (stdout, "Create a timer which expires at wheel-time (1, 0, 0)\n");
927 before = clib_time_now (&tm->clib_time);
930 pool_get (tm->test_elts, e);
931 memset (e, 0, sizeof (*e));
933 /* 1 glacier ring tick from now */
934 expiration_time = TW_SLOTS_PER_RING * TW_SLOTS_PER_RING;
935 e->expected_to_expire = expiration_time + initial_wheel_offset;
936 max_expiration_time = expiration_time;
938 e->stop_timer_handle =
939 tw_timer_start_4t_3w_256sl (&tm->triple_wheel, e - tm->test_elts,
943 run_triple_wheel (&tm->triple_wheel, max_expiration_time + 1);
945 after = clib_time_now (&tm->clib_time);
947 fformat (stdout, "%d adds, %d deletes, %d ticks\n", adds, deletes,
948 tm->triple_wheel.current_tick);
949 fformat (stdout, "test ran %.2f seconds, %.2f ops/second\n",
951 ((f64) adds + (f64) deletes +
952 (f64) tm->triple_wheel.current_tick) / (after - before));
954 if (pool_elts (tm->test_elts))
955 fformat (stdout, "Note: %d elements remain in pool\n",
956 pool_elts (tm->test_elts));
959 pool_foreach (e, tm->test_elts,
961 fformat (stdout, "[%d] expected to expire %d\n",
963 e->expected_to_expire);
967 pool_free (tm->test_elts);
968 tw_timer_wheel_free_4t_3w_256sl (&tm->triple_wheel);
972 static clib_error_t *
973 test4_double_double (tw_timer_test_main_t * tm)
976 tw_timer_test_elt_t *e;
977 u32 initial_wheel_offset;
979 u32 max_expiration_time = 0;
980 u32 *deleted_indices = 0;
981 u32 adds = 0, deletes = 0;
984 clib_time_init (&tm->clib_time);
986 tw_timer_wheel_init_16t_2w_512sl (&tm->double_wheel,
987 expired_timer_double_callback,
988 1.0 /* timer interval */ , ~0);
990 initial_wheel_offset = 0;
992 run_double_wheel (&tm->double_wheel, initial_wheel_offset);
994 fformat (stdout, "initial wheel time %d, fast index %d slow index %d\n",
995 tm->double_wheel.current_tick,
996 tm->double_wheel.current_index[TW_TIMER_RING_FAST],
997 tm->double_wheel.current_index[TW_TIMER_RING_SLOW]);
999 initial_wheel_offset = tm->double_wheel.current_tick;
1001 fformat (stdout, "test timer which expires at 512 ticks\n");
1003 before = clib_time_now (&tm->clib_time);
1005 /* Prime the pump */
1006 for (i = 0; i < tm->ntimers; i++)
1008 pool_get (tm->test_elts, e);
1009 memset (e, 0, sizeof (*e));
1011 expiration_time = 512;
1013 if (expiration_time > max_expiration_time)
1014 max_expiration_time = expiration_time;
1016 e->expected_to_expire = expiration_time + initial_wheel_offset;
1017 e->stop_timer_handle =
1018 tw_timer_start_16t_2w_512sl (&tm->double_wheel, e - tm->test_elts,
1025 vec_free (deleted_indices);
1027 run_double_wheel (&tm->double_wheel, max_expiration_time + 1);
1029 after = clib_time_now (&tm->clib_time);
1031 fformat (stdout, "%d adds, %d deletes, %d ticks\n", adds, deletes,
1032 tm->double_wheel.current_tick);
1033 fformat (stdout, "test ran %.2f seconds, %.2f ops/second\n",
1035 ((f64) adds + (f64) deletes +
1036 (f64) tm->double_wheel.current_tick) / (after - before));
1038 if (pool_elts (tm->test_elts))
1039 fformat (stdout, "Note: %d elements remain in pool\n",
1040 pool_elts (tm->test_elts));
1043 pool_foreach (e, tm->test_elts,
1045 fformat (stdout, "[%d] expected to expire %d\n",
1047 e->expected_to_expire);
1051 pool_free (tm->test_elts);
1052 tw_timer_wheel_free_16t_2w_512sl (&tm->double_wheel);
1056 static clib_error_t *
1057 test5_double (tw_timer_test_main_t * tm)
1060 tw_timer_test_elt_t *e;
1061 u32 initial_wheel_offset;
1062 u32 expiration_time;
1063 u32 max_expiration_time = 0;
1064 u32 adds = 0, deletes = 0;
1067 clib_time_init (&tm->clib_time);
1069 tw_timer_wheel_init_16t_2w_512sl (&tm->double_wheel,
1070 expired_timer_double_callback,
1071 1.0 /* timer interval */ , ~0);
1074 initial_wheel_offset = 7567;
1076 run_double_wheel (&tm->double_wheel, initial_wheel_offset);
1078 fformat (stdout, "initial wheel time %d, fast index %d slow index %d\n",
1079 tm->double_wheel.current_tick,
1080 tm->double_wheel.current_index[TW_TIMER_RING_FAST],
1081 tm->double_wheel.current_index[TW_TIMER_RING_SLOW]);
1083 initial_wheel_offset = tm->double_wheel.current_tick;
1086 "test %d timers, %d iter, %d ticks per iter, 0x%llx seed\n",
1087 tm->ntimers, tm->niter, tm->ticks_per_iter, tm->seed);
1089 before = clib_time_now (&tm->clib_time);
1091 /* Prime the pump */
1092 for (i = 0; i < tm->ntimers; i++)
1094 pool_get (tm->test_elts, e);
1095 memset (e, 0, sizeof (*e));
1097 expiration_time = i + 1;
1099 if (expiration_time > max_expiration_time)
1100 max_expiration_time = expiration_time;
1102 e->expected_to_expire = expiration_time + initial_wheel_offset;
1103 e->stop_timer_handle =
1104 tw_timer_start_16t_2w_512sl (&tm->double_wheel, e - tm->test_elts,
1111 run_double_wheel (&tm->double_wheel, max_expiration_time + 1);
1113 after = clib_time_now (&tm->clib_time);
1115 fformat (stdout, "%d adds, %d deletes, %d ticks\n", adds, deletes,
1116 tm->double_wheel.current_tick);
1117 fformat (stdout, "test ran %.2f seconds, %.2f ops/second\n",
1119 ((f64) adds + (f64) deletes +
1120 (f64) tm->double_wheel.current_tick) / (after - before));
1122 if (pool_elts (tm->test_elts))
1123 fformat (stdout, "Note: %d elements remain in pool\n",
1124 pool_elts (tm->test_elts));
1127 pool_foreach (e, tm->test_elts,
1129 fformat (stdout, "[%d] expected to expire %d\n",
1131 e->expected_to_expire);
1135 pool_free (tm->test_elts);
1136 tw_timer_wheel_free_16t_2w_512sl (&tm->double_wheel);
1140 static clib_error_t *
1141 timer_test_command_fn (tw_timer_test_main_t * tm, unformat_input_t * input)
1152 memset (tm, 0, sizeof (*tm));
1153 /* Default values */
1154 tm->ntimers = 100000;
1155 tm->seed = 0xDEADDABEB00BFACE;
1157 tm->ticks_per_iter = 727;
1159 while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
1161 if (unformat (input, "seed %lld", &tm->seed))
1163 else if (unformat (input, "test1"))
1165 else if (unformat (input, "test2"))
1167 else if (unformat (input, "overflow"))
1169 else if (unformat (input, "lebron"))
1171 else if (unformat (input, "wilt"))
1173 else if (unformat (input, "linear"))
1175 else if (unformat (input, "wheels %d", &num_wheels))
1177 else if (unformat (input, "ntimers %d", &tm->ntimers))
1179 else if (unformat (input, "niter %d", &tm->niter))
1181 else if (unformat (input, "ticks_per_iter %d", &tm->ticks_per_iter))
1187 if (is_test1 + is_test2 + is_test3 + is_test4 + is_test5 == 0)
1188 return clib_error_return (0, "No test specified [test1..n]");
1190 if (num_wheels < 1 || num_wheels > 3)
1191 return clib_error_return (0, "unsupported... 1 or 2 wheels only");
1195 if (num_wheels == 1)
1196 return test1_single (tm);
1198 return test1_double (tm);
1202 if (num_wheels == 1)
1203 return test2_single (tm);
1204 else if (num_wheels == 2)
1205 return test2_double (tm);
1206 else if (num_wheels == 3)
1209 return test2_triple (tm);
1211 return test2_triple_ov (tm);
1215 return test3_triple_double (tm);
1218 return test4_double_double (tm);
1221 return test5_double (tm);
1229 main (int argc, char *argv[])
1232 clib_error_t *error;
1233 tw_timer_test_main_t *tm = &tw_timer_test_main;
1235 clib_mem_init (0, 3ULL << 30);
1237 unformat_init_command_line (&i, argv);
1238 error = timer_test_command_fn (tm, &i);
1243 clib_error_report (error);
1248 #endif /* CLIB_UNIX */
1250 /* For debugging... */
1252 pifi (void *p, u32 index)
1254 return pool_is_free_index (p, index);
1266 return (pool_elts (v));
1270 * fd.io coding-style-patch-verification: ON
1273 * eval: (c-set-style "gnu")