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);
486 get_expiration_time (tw_timer_test_main_t * tm)
491 expiration_time = random_u64 (&tm->seed) & ((1 << 17) - 1);
493 while (expiration_time == 0);
494 return expiration_time;
497 static clib_error_t *
498 test2_double_updates (tw_timer_test_main_t * tm)
501 tw_timer_test_elt_t *e;
502 u32 initial_wheel_offset;
504 u32 max_expiration_time = 0, updates = 0;
507 clib_time_init (&tm->clib_time);
508 tw_timer_wheel_init_16t_2w_512sl (&tm->double_wheel,
509 expired_timer_double_callback,
510 1.0 /* timer interval */ , ~0);
513 initial_wheel_offset = 7577;
514 run_double_wheel (&tm->double_wheel, initial_wheel_offset);
515 fformat (stdout, "initial wheel time %d, fast index %d slow index %d\n",
516 tm->double_wheel.current_tick,
517 tm->double_wheel.current_index[TW_TIMER_RING_FAST],
518 tm->double_wheel.current_index[TW_TIMER_RING_SLOW]);
520 initial_wheel_offset = tm->double_wheel.current_tick;
522 "test %d timers, %d iter, %d ticks per iter, 0x%llx seed\n",
523 tm->ntimers, tm->niter, tm->ticks_per_iter, tm->seed);
525 before = clib_time_now (&tm->clib_time);
528 for (i = 0; i < tm->ntimers; i++)
530 pool_get (tm->test_elts, e);
531 memset (e, 0, sizeof (*e));
533 expiration_time = get_expiration_time (tm);
534 max_expiration_time = clib_max (expiration_time, max_expiration_time);
536 e->expected_to_expire = expiration_time + initial_wheel_offset;
537 e->stop_timer_handle = tw_timer_start_16t_2w_512sl (&tm->double_wheel,
543 for (i = 0; i < tm->niter; i++)
545 run_double_wheel (&tm->double_wheel, tm->ticks_per_iter);
550 pool_foreach (e, tm->test_elts,
552 expiration_time = get_expiration_time (tm);
553 max_expiration_time = clib_max (expiration_time, max_expiration_time);
554 e->expected_to_expire = expiration_time
555 + tm->double_wheel.current_tick;
556 tw_timer_update_16t_2w_512sl (&tm->double_wheel, e->stop_timer_handle,
558 if (++j >= tm->ntimers / 4)
567 run_double_wheel (&tm->double_wheel, max_expiration_time + 1);
569 after = clib_time_now (&tm->clib_time);
571 fformat (stdout, "%d updates, %d ticks\n", updates,
572 tm->double_wheel.current_tick);
573 fformat (stdout, "test ran %.2f seconds, %.2f ops/second\n",
575 ((f64) updates + (f64) tm->double_wheel.current_tick) / (after -
578 if (pool_elts (tm->test_elts))
579 fformat (stdout, "Note: %d elements remain in pool\n",
580 pool_elts (tm->test_elts));
583 pool_foreach (e, tm->test_elts,
585 fformat (stdout, "[%d] expected to expire %d\n",
587 e->expected_to_expire);
591 pool_free (tm->test_elts);
592 tw_timer_wheel_free_16t_2w_512sl (&tm->double_wheel);
596 static clib_error_t *
597 test2_triple (tw_timer_test_main_t * tm)
600 tw_timer_test_elt_t *e;
601 u32 initial_wheel_offset = 0;
603 u32 max_expiration_time = 0;
604 u32 *deleted_indices = 0;
605 u32 adds = 0, deletes = 0;
608 clib_time_init (&tm->clib_time);
610 tw_timer_wheel_init_4t_3w_256sl (&tm->triple_wheel,
611 expired_timer_triple_callback,
612 1.0 /* timer interval */ , ~0);
616 initial_wheel_offset = 75700;
617 run_triple_wheel (&tm->triple_wheel, initial_wheel_offset);
620 "initial wheel time %d, fi %d si %d gi %d\n",
621 tm->triple_wheel.current_tick,
622 tm->triple_wheel.current_index[TW_TIMER_RING_FAST],
623 tm->triple_wheel.current_index[TW_TIMER_RING_SLOW],
624 tm->triple_wheel.current_index[TW_TIMER_RING_GLACIER]);
626 initial_wheel_offset = tm->triple_wheel.current_tick;
629 "test %d timers, %d iter, %d ticks per iter, 0x%llx seed\n",
630 tm->ntimers, tm->niter, tm->ticks_per_iter, tm->seed);
632 before = clib_time_now (&tm->clib_time);
635 for (i = 0; i < tm->ntimers; i++)
637 pool_get (tm->test_elts, e);
638 memset (e, 0, sizeof (*e));
642 expiration_time = random_u64 (&tm->seed) & ((1 << 17) - 1);
644 while (expiration_time == 0);
646 if (expiration_time > max_expiration_time)
647 max_expiration_time = expiration_time;
649 e->expected_to_expire = expiration_time + initial_wheel_offset;
651 e->stop_timer_handle =
652 tw_timer_start_4t_3w_256sl (&tm->triple_wheel, e - tm->test_elts,
659 for (i = 0; i < tm->niter; i++)
661 run_triple_wheel (&tm->triple_wheel, tm->ticks_per_iter);
664 vec_reset_length (deleted_indices);
666 pool_foreach (e, tm->test_elts,
668 tw_timer_stop_4t_3w_256sl (&tm->triple_wheel, e->stop_timer_handle);
669 vec_add1 (deleted_indices, e - tm->test_elts);
670 if (++j >= tm->ntimers / 4)
676 for (j = 0; j < vec_len (deleted_indices); j++)
677 pool_put_index (tm->test_elts, deleted_indices[j]);
681 for (j = 0; j < tm->ntimers / 4; j++)
683 pool_get (tm->test_elts, e);
684 memset (e, 0, sizeof (*e));
688 expiration_time = random_u64 (&tm->seed) & ((1 << 17) - 1);
690 while (expiration_time == 0);
692 if (expiration_time > max_expiration_time)
693 max_expiration_time = expiration_time;
695 e->expected_to_expire = expiration_time +
696 tm->triple_wheel.current_tick;
698 e->stop_timer_handle = tw_timer_start_4t_3w_256sl
699 (&tm->triple_wheel, e - tm->test_elts, 3 /* timer id */ ,
705 vec_free (deleted_indices);
707 run_triple_wheel (&tm->triple_wheel, max_expiration_time + 1);
709 after = clib_time_now (&tm->clib_time);
711 fformat (stdout, "%d adds, %d deletes, %d ticks\n", adds, deletes,
712 tm->triple_wheel.current_tick);
713 fformat (stdout, "test ran %.2f seconds, %.2f ops/second\n",
715 ((f64) adds + (f64) deletes +
716 (f64) tm->triple_wheel.current_tick) / (after - before));
718 if (pool_elts (tm->test_elts))
719 fformat (stdout, "Note: %d elements remain in pool\n",
720 pool_elts (tm->test_elts));
723 pool_foreach (e, tm->test_elts,
725 fformat (stdout, "[%d] expected to expire %d\n",
727 e->expected_to_expire);
731 pool_free (tm->test_elts);
732 tw_timer_wheel_free_4t_3w_256sl (&tm->triple_wheel);
736 static clib_error_t *
737 test2_triple_ov (tw_timer_test_main_t * tm)
740 tw_timer_test_elt_t *e;
741 u32 initial_wheel_offset = 0;
743 u32 max_expiration_time = 0;
744 u32 *deleted_indices = 0;
745 u32 adds = 0, deletes = 0;
748 clib_time_init (&tm->clib_time);
750 tw_timer_wheel_init_1t_3w_1024sl_ov (&tm->triple_ov_wheel,
751 expired_timer_triple_ov_callback,
752 1.0 /* timer interval */ , ~0);
756 initial_wheel_offset = 75700;
757 run_triple_ov_wheel (&tm->triple_ov_wheel, initial_wheel_offset);
760 "initial wheel time %d, fi %d si %d gi %d\n",
761 tm->triple_ov_wheel.current_tick,
762 tm->triple_ov_wheel.current_index[TW_TIMER_RING_FAST],
763 tm->triple_ov_wheel.current_index[TW_TIMER_RING_SLOW],
764 tm->triple_ov_wheel.current_index[TW_TIMER_RING_GLACIER]);
766 initial_wheel_offset = tm->triple_ov_wheel.current_tick;
769 "test %d timers, %d iter, %d ticks per iter, 0x%llx seed\n",
770 tm->ntimers, tm->niter, tm->ticks_per_iter, tm->seed);
772 before = clib_time_now (&tm->clib_time);
775 for (i = 0; i < tm->ntimers; i++)
777 pool_get (tm->test_elts, e);
778 memset (e, 0, sizeof (*e));
782 expiration_time = random_u64 (&tm->seed) & ((1 << 17) - 1);
784 while (expiration_time == 0);
786 if (expiration_time > max_expiration_time)
787 max_expiration_time = expiration_time;
789 e->expected_to_expire = expiration_time + initial_wheel_offset;
791 e->stop_timer_handle =
792 tw_timer_start_1t_3w_1024sl_ov (&tm->triple_ov_wheel,
793 e - tm->test_elts, 0 /* timer id */ ,
799 for (i = 0; i < tm->niter; i++)
801 run_triple_ov_wheel (&tm->triple_ov_wheel, tm->ticks_per_iter);
804 vec_reset_length (deleted_indices);
806 pool_foreach (e, tm->test_elts,
808 tw_timer_stop_1t_3w_1024sl_ov (&tm->triple_ov_wheel,
809 e->stop_timer_handle);
810 vec_add1 (deleted_indices, e - tm->test_elts);
811 if (++j >= tm->ntimers / 4)
817 for (j = 0; j < vec_len (deleted_indices); j++)
818 pool_put_index (tm->test_elts, deleted_indices[j]);
822 for (j = 0; j < tm->ntimers / 4; j++)
824 pool_get (tm->test_elts, e);
825 memset (e, 0, sizeof (*e));
829 expiration_time = random_u64 (&tm->seed) & ((1 << 17) - 1);
831 while (expiration_time == 0);
833 if (expiration_time > max_expiration_time)
834 max_expiration_time = expiration_time;
836 e->expected_to_expire = expiration_time +
837 tm->triple_ov_wheel.current_tick;
839 e->stop_timer_handle = tw_timer_start_1t_3w_1024sl_ov
840 (&tm->triple_ov_wheel, e - tm->test_elts, 0 /* timer id */ ,
846 vec_free (deleted_indices);
848 run_triple_ov_wheel (&tm->triple_ov_wheel, max_expiration_time + 1);
850 after = clib_time_now (&tm->clib_time);
852 fformat (stdout, "%d adds, %d deletes, %d ticks\n", adds, deletes,
853 tm->triple_ov_wheel.current_tick);
854 fformat (stdout, "test ran %.2f seconds, %.2f ops/second\n",
856 ((f64) adds + (f64) deletes +
857 (f64) tm->triple_ov_wheel.current_tick) / (after - before));
859 if (pool_elts (tm->test_elts))
860 fformat (stdout, "Note: %d elements remain in pool\n",
861 pool_elts (tm->test_elts));
864 pool_foreach (e, tm->test_elts,
868 fformat (stdout, "[%d] expected to expire %d\n",
870 e->expected_to_expire);
871 t = pool_elt_at_index (tm->triple_ov_wheel.timers, e->stop_timer_handle);
872 fformat (stdout, " expiration_time %lld\n", t->expiration_time);
876 pool_free (tm->test_elts);
877 tw_timer_wheel_free_1t_3w_1024sl_ov (&tm->triple_ov_wheel);
881 static clib_error_t *
882 test1_single (tw_timer_test_main_t * tm)
885 tw_timer_test_elt_t *e;
888 tw_timer_wheel_init_2t_1w_2048sl (&tm->single_wheel,
889 expired_timer_single_callback,
890 1.0 /* timer interval */ , ~0);
893 * Prime offset, to make sure that the wheel starts in a
894 * non-trivial position
898 run_single_wheel (&tm->single_wheel, offset);
900 fformat (stdout, "initial wheel time %d, fast index %d\n",
901 tm->single_wheel.current_tick,
902 tm->single_wheel.current_index[TW_TIMER_RING_FAST]);
904 offset = tm->single_wheel.current_tick;
906 for (i = 0; i < tm->ntimers; i++)
908 u32 expected_to_expire;
916 expected_to_expire = timer_arg + offset;
918 pool_get (tm->test_elts, e);
919 memset (e, 0, sizeof (*e));
920 e->expected_to_expire = expected_to_expire;
921 e->stop_timer_handle = tw_timer_start_2t_1w_2048sl
922 (&tm->single_wheel, e - tm->test_elts, 1 /* timer id */ ,
925 run_single_wheel (&tm->single_wheel, tm->ntimers + 3);
927 if (pool_elts (tm->test_elts))
928 fformat (stdout, "Note: %d elements remain in pool\n",
929 pool_elts (tm->test_elts));
932 pool_foreach (e, tm->test_elts,
934 fformat(stdout, "[%d] expected to expire %d\n",
936 e->expected_to_expire);
941 "final wheel time %d, fast index %d\n",
942 tm->single_wheel.current_tick,
943 tm->single_wheel.current_index[TW_TIMER_RING_FAST]);
945 pool_free (tm->test_elts);
946 tw_timer_wheel_free_2t_1w_2048sl (&tm->single_wheel);
950 static clib_error_t *
951 test1_double (tw_timer_test_main_t * tm)
954 tw_timer_test_elt_t *e;
957 tw_timer_wheel_init_16t_2w_512sl (&tm->double_wheel,
958 expired_timer_double_callback,
959 1.0 /* timer interval */ , ~0);
962 * Prime offset, to make sure that the wheel starts in a
963 * non-trivial position
967 run_double_wheel (&tm->double_wheel, offset);
969 fformat (stdout, "initial wheel time %d, fast index %d\n",
970 tm->double_wheel.current_tick,
971 tm->double_wheel.current_index[TW_TIMER_RING_FAST]);
973 for (i = 0; i < tm->ntimers; i++)
975 pool_get (tm->test_elts, e);
976 memset (e, 0, sizeof (*e));
978 e->expected_to_expire = i + offset + 1;
979 e->stop_timer_handle = tw_timer_start_16t_2w_512sl
980 (&tm->double_wheel, e - tm->test_elts, 14 /* timer id */ ,
983 run_double_wheel (&tm->double_wheel, tm->ntimers + 3);
985 if (pool_elts (tm->test_elts))
986 fformat (stdout, "Note: %d elements remain in pool\n",
987 pool_elts (tm->test_elts));
990 pool_foreach (e, tm->test_elts,
992 fformat(stdout, "[%d] expected to expire %d\n",
994 e->expected_to_expire);
999 "final wheel time %d, fast index %d\n",
1000 tm->double_wheel.current_tick,
1001 tm->double_wheel.current_index[TW_TIMER_RING_FAST]);
1003 pool_free (tm->test_elts);
1004 tw_timer_wheel_free_16t_2w_512sl (&tm->double_wheel);
1008 static clib_error_t *
1009 test3_triple_double (tw_timer_test_main_t * tm)
1011 tw_timer_test_elt_t *e;
1012 u32 initial_wheel_offset = 0;
1013 u32 expiration_time;
1014 u32 max_expiration_time = 0;
1015 u32 adds = 0, deletes = 0;
1018 clib_time_init (&tm->clib_time);
1020 tw_timer_wheel_init_4t_3w_256sl (&tm->triple_wheel,
1021 expired_timer_triple_callback,
1022 1.0 /* timer interval */ , ~0);
1024 initial_wheel_offset = 0;
1025 run_triple_wheel (&tm->triple_wheel, initial_wheel_offset);
1028 "initial wheel time %d, fi %d si %d gi %d\n",
1029 tm->triple_wheel.current_tick,
1030 tm->triple_wheel.current_index[TW_TIMER_RING_FAST],
1031 tm->triple_wheel.current_index[TW_TIMER_RING_SLOW],
1032 tm->triple_wheel.current_index[TW_TIMER_RING_GLACIER]);
1034 initial_wheel_offset = tm->triple_wheel.current_tick;
1036 fformat (stdout, "Create a timer which expires at wheel-time (1, 0, 0)\n");
1038 before = clib_time_now (&tm->clib_time);
1040 /* Prime the pump */
1041 pool_get (tm->test_elts, e);
1042 memset (e, 0, sizeof (*e));
1044 /* 1 glacier ring tick from now */
1045 expiration_time = TW_SLOTS_PER_RING * TW_SLOTS_PER_RING;
1046 e->expected_to_expire = expiration_time + initial_wheel_offset;
1047 max_expiration_time = expiration_time;
1049 e->stop_timer_handle =
1050 tw_timer_start_4t_3w_256sl (&tm->triple_wheel, e - tm->test_elts,
1054 run_triple_wheel (&tm->triple_wheel, max_expiration_time + 1);
1056 after = clib_time_now (&tm->clib_time);
1058 fformat (stdout, "%d adds, %d deletes, %d ticks\n", adds, deletes,
1059 tm->triple_wheel.current_tick);
1060 fformat (stdout, "test ran %.2f seconds, %.2f ops/second\n",
1062 ((f64) adds + (f64) deletes +
1063 (f64) tm->triple_wheel.current_tick) / (after - before));
1065 if (pool_elts (tm->test_elts))
1066 fformat (stdout, "Note: %d elements remain in pool\n",
1067 pool_elts (tm->test_elts));
1070 pool_foreach (e, tm->test_elts,
1072 fformat (stdout, "[%d] expected to expire %d\n",
1074 e->expected_to_expire);
1078 pool_free (tm->test_elts);
1079 tw_timer_wheel_free_4t_3w_256sl (&tm->triple_wheel);
1083 static clib_error_t *
1084 test4_double_double (tw_timer_test_main_t * tm)
1087 tw_timer_test_elt_t *e;
1088 u32 initial_wheel_offset;
1089 u32 expiration_time;
1090 u32 max_expiration_time = 0;
1091 u32 *deleted_indices = 0;
1092 u32 adds = 0, deletes = 0;
1095 clib_time_init (&tm->clib_time);
1097 tw_timer_wheel_init_16t_2w_512sl (&tm->double_wheel,
1098 expired_timer_double_callback,
1099 1.0 /* timer interval */ , ~0);
1101 initial_wheel_offset = 0;
1103 run_double_wheel (&tm->double_wheel, initial_wheel_offset);
1105 fformat (stdout, "initial wheel time %d, fast index %d slow index %d\n",
1106 tm->double_wheel.current_tick,
1107 tm->double_wheel.current_index[TW_TIMER_RING_FAST],
1108 tm->double_wheel.current_index[TW_TIMER_RING_SLOW]);
1110 initial_wheel_offset = tm->double_wheel.current_tick;
1112 fformat (stdout, "test timer which expires at 512 ticks\n");
1114 before = clib_time_now (&tm->clib_time);
1116 /* Prime the pump */
1117 for (i = 0; i < tm->ntimers; i++)
1119 pool_get (tm->test_elts, e);
1120 memset (e, 0, sizeof (*e));
1122 expiration_time = 512;
1124 if (expiration_time > max_expiration_time)
1125 max_expiration_time = expiration_time;
1127 e->expected_to_expire = expiration_time + initial_wheel_offset;
1128 e->stop_timer_handle =
1129 tw_timer_start_16t_2w_512sl (&tm->double_wheel, e - tm->test_elts,
1136 vec_free (deleted_indices);
1138 run_double_wheel (&tm->double_wheel, max_expiration_time + 1);
1140 after = clib_time_now (&tm->clib_time);
1142 fformat (stdout, "%d adds, %d deletes, %d ticks\n", adds, deletes,
1143 tm->double_wheel.current_tick);
1144 fformat (stdout, "test ran %.2f seconds, %.2f ops/second\n",
1146 ((f64) adds + (f64) deletes +
1147 (f64) tm->double_wheel.current_tick) / (after - before));
1149 if (pool_elts (tm->test_elts))
1150 fformat (stdout, "Note: %d elements remain in pool\n",
1151 pool_elts (tm->test_elts));
1154 pool_foreach (e, tm->test_elts,
1156 fformat (stdout, "[%d] expected to expire %d\n",
1158 e->expected_to_expire);
1162 pool_free (tm->test_elts);
1163 tw_timer_wheel_free_16t_2w_512sl (&tm->double_wheel);
1167 static clib_error_t *
1168 test5_double (tw_timer_test_main_t * tm)
1171 tw_timer_test_elt_t *e;
1172 u32 initial_wheel_offset;
1173 u32 expiration_time;
1174 u32 max_expiration_time = 0;
1175 u32 adds = 0, deletes = 0;
1178 clib_time_init (&tm->clib_time);
1180 tw_timer_wheel_init_16t_2w_512sl (&tm->double_wheel,
1181 expired_timer_double_callback,
1182 1.0 /* timer interval */ , ~0);
1185 initial_wheel_offset = 7567;
1187 run_double_wheel (&tm->double_wheel, initial_wheel_offset);
1189 fformat (stdout, "initial wheel time %d, fast index %d slow index %d\n",
1190 tm->double_wheel.current_tick,
1191 tm->double_wheel.current_index[TW_TIMER_RING_FAST],
1192 tm->double_wheel.current_index[TW_TIMER_RING_SLOW]);
1194 initial_wheel_offset = tm->double_wheel.current_tick;
1197 "test %d timers, %d iter, %d ticks per iter, 0x%llx seed\n",
1198 tm->ntimers, tm->niter, tm->ticks_per_iter, tm->seed);
1200 before = clib_time_now (&tm->clib_time);
1202 /* Prime the pump */
1203 for (i = 0; i < tm->ntimers; i++)
1205 pool_get (tm->test_elts, e);
1206 memset (e, 0, sizeof (*e));
1208 expiration_time = i + 1;
1210 if (expiration_time > max_expiration_time)
1211 max_expiration_time = expiration_time;
1213 e->expected_to_expire = expiration_time + initial_wheel_offset;
1214 e->stop_timer_handle =
1215 tw_timer_start_16t_2w_512sl (&tm->double_wheel, e - tm->test_elts,
1222 run_double_wheel (&tm->double_wheel, max_expiration_time + 1);
1224 after = clib_time_now (&tm->clib_time);
1226 fformat (stdout, "%d adds, %d deletes, %d ticks\n", adds, deletes,
1227 tm->double_wheel.current_tick);
1228 fformat (stdout, "test ran %.2f seconds, %.2f ops/second\n",
1230 ((f64) adds + (f64) deletes +
1231 (f64) tm->double_wheel.current_tick) / (after - before));
1233 if (pool_elts (tm->test_elts))
1234 fformat (stdout, "Note: %d elements remain in pool\n",
1235 pool_elts (tm->test_elts));
1238 pool_foreach (e, tm->test_elts,
1240 fformat (stdout, "[%d] expected to expire %d\n",
1242 e->expected_to_expire);
1246 pool_free (tm->test_elts);
1247 tw_timer_wheel_free_16t_2w_512sl (&tm->double_wheel);
1251 static clib_error_t *
1252 timer_test_command_fn (tw_timer_test_main_t * tm, unformat_input_t * input)
1255 int is_test1 = 0, is_updates = 0;
1263 memset (tm, 0, sizeof (*tm));
1264 /* Default values */
1265 tm->ntimers = 100000;
1266 tm->seed = 0xDEADDABEB00BFACE;
1268 tm->ticks_per_iter = 727;
1270 while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
1272 if (unformat (input, "seed %lld", &tm->seed))
1274 else if (unformat (input, "test1"))
1276 else if (unformat (input, "test2"))
1278 else if (unformat (input, "overflow"))
1280 else if (unformat (input, "lebron"))
1282 else if (unformat (input, "wilt"))
1284 else if (unformat (input, "linear"))
1286 else if (unformat (input, "updates"))
1288 else if (unformat (input, "wheels %d", &num_wheels))
1290 else if (unformat (input, "ntimers %d", &tm->ntimers))
1292 else if (unformat (input, "niter %d", &tm->niter))
1294 else if (unformat (input, "ticks_per_iter %d", &tm->ticks_per_iter))
1300 if (is_test1 + is_test2 + is_test3 + is_test4 + is_test5 == 0)
1301 return clib_error_return (0, "No test specified [test1..n]");
1303 if (num_wheels < 1 || num_wheels > 3)
1304 return clib_error_return (0, "unsupported... 1 or 2 wheels only");
1308 if (num_wheels == 1)
1309 return test1_single (tm);
1311 return test1_double (tm);
1315 if (num_wheels == 1)
1316 return test2_single (tm);
1317 else if (num_wheels == 2)
1319 return test2_double_updates (tm);
1321 return test2_double (tm);
1322 else if (num_wheels == 3)
1325 return test2_triple (tm);
1327 return test2_triple_ov (tm);
1331 return test3_triple_double (tm);
1334 return test4_double_double (tm);
1337 return test5_double (tm);
1345 main (int argc, char *argv[])
1348 clib_error_t *error;
1349 tw_timer_test_main_t *tm = &tw_timer_test_main;
1351 clib_mem_init (0, 3ULL << 30);
1353 unformat_init_command_line (&i, argv);
1354 error = timer_test_command_fn (tm, &i);
1359 clib_error_report (error);
1364 #endif /* CLIB_UNIX */
1366 /* For debugging... */
1368 pifi (void *p, u32 index)
1370 return pool_is_free_index (p, index);
1382 return (pool_elts (v));
1386 * fd.io coding-style-patch-verification: ON
1389 * eval: (c-set-style "gnu")