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);
319 pool_foreach (e, tm->test_elts)
321 tw_timer_stop_2t_1w_2048sl (&tm->single_wheel, e->stop_timer_handle);
322 vec_add1 (deleted_indices, e - tm->test_elts);
323 if (++j >= tm->ntimers / 4)
328 for (j = 0; j < vec_len (deleted_indices); j++)
330 pool_put_index (tm->test_elts, deleted_indices[j]);
335 for (j = 0; j < tm->ntimers / 4; j++)
337 pool_get (tm->test_elts, e);
338 clib_memset (e, 0, sizeof (*e));
342 expiration_time = random_u64 (&tm->seed) & (2047);
344 while (expiration_time == 0);
346 if (expiration_time > max_expiration_time)
347 max_expiration_time = expiration_time;
349 e->expected_to_expire =
350 expiration_time + tm->single_wheel.current_tick;
351 e->stop_timer_handle = tw_timer_start_2t_1w_2048sl
352 (&tm->single_wheel, e - tm->test_elts, 1 /* timer id */ ,
358 vec_free (deleted_indices);
360 run_single_wheel (&tm->single_wheel, max_expiration_time + 1);
362 after = clib_time_now (&tm->clib_time);
364 fformat (stdout, "%d adds, %d deletes, %d ticks\n", adds, deletes,
365 tm->single_wheel.current_tick);
366 fformat (stdout, "test ran %.2f seconds, %.2f ops/second\n",
368 ((f64) adds + (f64) deletes +
369 (f64) tm->single_wheel.current_tick) / (after - before));
371 if (pool_elts (tm->test_elts))
372 fformat (stdout, "Note: %d elements remain in pool\n",
373 pool_elts (tm->test_elts));
375 pool_foreach (e, tm->test_elts)
377 fformat (stdout, "[%d] expected to expire %d\n",
379 e->expected_to_expire);
382 pool_free (tm->test_elts);
383 tw_timer_wheel_free_2t_1w_2048sl (&tm->single_wheel);
387 static clib_error_t *
388 test2_double (tw_timer_test_main_t * tm)
391 tw_timer_test_elt_t *e;
392 u32 initial_wheel_offset;
394 u32 max_expiration_time = 0;
395 u32 *deleted_indices = 0;
396 u32 adds = 0, deletes = 0;
399 clib_time_init (&tm->clib_time);
401 tw_timer_wheel_init_16t_2w_512sl (&tm->double_wheel,
402 expired_timer_double_callback,
403 1.0 /* timer interval */ , ~0);
406 initial_wheel_offset = 7577;
408 run_double_wheel (&tm->double_wheel, initial_wheel_offset);
410 fformat (stdout, "initial wheel time %d, fast index %d slow index %d\n",
411 tm->double_wheel.current_tick,
412 tm->double_wheel.current_index[TW_TIMER_RING_FAST],
413 tm->double_wheel.current_index[TW_TIMER_RING_SLOW]);
415 initial_wheel_offset = tm->double_wheel.current_tick;
418 "test %d timers, %d iter, %d ticks per iter, 0x%llx seed\n",
419 tm->ntimers, tm->niter, tm->ticks_per_iter, tm->seed);
421 before = clib_time_now (&tm->clib_time);
424 for (i = 0; i < tm->ntimers; i++)
426 pool_get (tm->test_elts, e);
427 clib_memset (e, 0, sizeof (*e));
431 expiration_time = random_u64 (&tm->seed) & ((1 << 17) - 1);
433 while (expiration_time == 0);
435 if (expiration_time > max_expiration_time)
436 max_expiration_time = expiration_time;
438 e->expected_to_expire = expiration_time + initial_wheel_offset;
440 e->stop_timer_handle =
441 tw_timer_start_16t_2w_512sl (&tm->double_wheel, e - tm->test_elts,
448 for (i = 0; i < tm->niter; i++)
450 run_double_wheel (&tm->double_wheel, tm->ticks_per_iter);
453 vec_reset_length (deleted_indices);
454 pool_foreach (e, tm->test_elts)
456 tw_timer_stop_16t_2w_512sl (&tm->double_wheel, e->stop_timer_handle);
457 vec_add1 (deleted_indices, e - tm->test_elts);
458 if (++j >= tm->ntimers / 4)
463 for (j = 0; j < vec_len (deleted_indices); j++)
464 pool_put_index (tm->test_elts, deleted_indices[j]);
468 for (j = 0; j < tm->ntimers / 4; j++)
470 pool_get (tm->test_elts, e);
471 clib_memset (e, 0, sizeof (*e));
475 expiration_time = random_u64 (&tm->seed) & ((1 << 17) - 1);
477 while (expiration_time == 0);
479 if (expiration_time > max_expiration_time)
480 max_expiration_time = expiration_time;
482 e->expected_to_expire = expiration_time +
483 tm->double_wheel.current_tick;
485 e->stop_timer_handle = tw_timer_start_16t_2w_512sl
486 (&tm->double_wheel, e - tm->test_elts, 14 /* timer id */ ,
492 vec_free (deleted_indices);
494 run_double_wheel (&tm->double_wheel, max_expiration_time + 1);
496 after = clib_time_now (&tm->clib_time);
498 fformat (stdout, "%d adds, %d deletes, %d ticks\n", adds, deletes,
499 tm->double_wheel.current_tick);
500 fformat (stdout, "test ran %.2f seconds, %.2f ops/second\n",
502 ((f64) adds + (f64) deletes +
503 (f64) tm->double_wheel.current_tick) / (after - before));
505 if (pool_elts (tm->test_elts))
506 fformat (stdout, "Note: %d elements remain in pool\n",
507 pool_elts (tm->test_elts));
509 pool_foreach (e, tm->test_elts)
511 fformat (stdout, "[%d] expected to expire %d\n",
513 e->expected_to_expire);
516 pool_free (tm->test_elts);
517 tw_timer_wheel_free_16t_2w_512sl (&tm->double_wheel);
522 get_expiration_time (tw_timer_test_main_t * tm)
527 expiration_time = random_u64 (&tm->seed) & ((1 << 17) - 1);
529 while (expiration_time == 0);
530 return expiration_time;
533 static clib_error_t *
534 test2_double_updates (tw_timer_test_main_t * tm)
537 tw_timer_test_elt_t *e;
538 u32 initial_wheel_offset;
540 u32 max_expiration_time = 0, updates = 0;
543 clib_time_init (&tm->clib_time);
544 tw_timer_wheel_init_16t_2w_512sl (&tm->double_wheel,
545 expired_timer_double_callback,
546 1.0 /* timer interval */ , ~0);
549 initial_wheel_offset = 7577;
550 run_double_wheel (&tm->double_wheel, initial_wheel_offset);
551 fformat (stdout, "initial wheel time %d, fast index %d slow index %d\n",
552 tm->double_wheel.current_tick,
553 tm->double_wheel.current_index[TW_TIMER_RING_FAST],
554 tm->double_wheel.current_index[TW_TIMER_RING_SLOW]);
556 initial_wheel_offset = tm->double_wheel.current_tick;
558 "test %d timers, %d iter, %d ticks per iter, 0x%llx seed\n",
559 tm->ntimers, tm->niter, tm->ticks_per_iter, tm->seed);
561 before = clib_time_now (&tm->clib_time);
564 for (i = 0; i < tm->ntimers; i++)
566 pool_get (tm->test_elts, e);
567 clib_memset (e, 0, sizeof (*e));
569 expiration_time = get_expiration_time (tm);
570 max_expiration_time = clib_max (expiration_time, max_expiration_time);
572 e->expected_to_expire = expiration_time + initial_wheel_offset;
573 e->stop_timer_handle = tw_timer_start_16t_2w_512sl (&tm->double_wheel,
579 for (i = 0; i < tm->niter; i++)
581 run_double_wheel (&tm->double_wheel, tm->ticks_per_iter);
585 pool_foreach (e, tm->test_elts)
587 expiration_time = get_expiration_time (tm);
588 max_expiration_time = clib_max (expiration_time, max_expiration_time);
589 e->expected_to_expire = expiration_time
590 + tm->double_wheel.current_tick;
591 tw_timer_update_16t_2w_512sl (&tm->double_wheel, e->stop_timer_handle,
593 if (++j >= tm->ntimers / 4)
601 run_double_wheel (&tm->double_wheel, max_expiration_time + 1);
603 after = clib_time_now (&tm->clib_time);
605 fformat (stdout, "%d updates, %d ticks\n", updates,
606 tm->double_wheel.current_tick);
607 fformat (stdout, "test ran %.2f seconds, %.2f ops/second\n",
609 ((f64) updates + (f64) tm->double_wheel.current_tick) / (after -
612 if (pool_elts (tm->test_elts))
613 fformat (stdout, "Note: %d elements remain in pool\n",
614 pool_elts (tm->test_elts));
616 pool_foreach (e, tm->test_elts)
618 fformat (stdout, "[%d] expected to expire %d\n",
620 e->expected_to_expire);
623 pool_free (tm->test_elts);
624 tw_timer_wheel_free_16t_2w_512sl (&tm->double_wheel);
628 static clib_error_t *
629 test2_triple (tw_timer_test_main_t * tm)
632 tw_timer_test_elt_t *e;
633 u32 initial_wheel_offset = 0;
635 u32 max_expiration_time = 0;
636 u32 *deleted_indices = 0;
637 u32 adds = 0, deletes = 0;
640 clib_time_init (&tm->clib_time);
642 tw_timer_wheel_init_4t_3w_256sl (&tm->triple_wheel,
643 expired_timer_triple_callback,
644 1.0 /* timer interval */ , ~0);
648 initial_wheel_offset = 75700;
649 run_triple_wheel (&tm->triple_wheel, initial_wheel_offset);
652 "initial wheel time %d, fi %d si %d gi %d\n",
653 tm->triple_wheel.current_tick,
654 tm->triple_wheel.current_index[TW_TIMER_RING_FAST],
655 tm->triple_wheel.current_index[TW_TIMER_RING_SLOW],
656 tm->triple_wheel.current_index[TW_TIMER_RING_GLACIER]);
658 initial_wheel_offset = tm->triple_wheel.current_tick;
661 "test %d timers, %d iter, %d ticks per iter, 0x%llx seed\n",
662 tm->ntimers, tm->niter, tm->ticks_per_iter, tm->seed);
664 before = clib_time_now (&tm->clib_time);
667 for (i = 0; i < tm->ntimers; i++)
669 pool_get (tm->test_elts, e);
670 clib_memset (e, 0, sizeof (*e));
674 expiration_time = random_u64 (&tm->seed) & ((1 << 17) - 1);
676 while (expiration_time == 0);
678 if (expiration_time > max_expiration_time)
679 max_expiration_time = expiration_time;
681 e->expected_to_expire = expiration_time + initial_wheel_offset;
683 e->stop_timer_handle =
684 tw_timer_start_4t_3w_256sl (&tm->triple_wheel, e - tm->test_elts,
691 for (i = 0; i < tm->niter; i++)
693 run_triple_wheel (&tm->triple_wheel, tm->ticks_per_iter);
696 vec_reset_length (deleted_indices);
697 pool_foreach (e, tm->test_elts)
699 tw_timer_stop_4t_3w_256sl (&tm->triple_wheel, e->stop_timer_handle);
700 vec_add1 (deleted_indices, e - tm->test_elts);
701 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 clib_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_wheel.current_tick;
728 e->stop_timer_handle = tw_timer_start_4t_3w_256sl
729 (&tm->triple_wheel, e - tm->test_elts, 3 /* timer id */ ,
735 vec_free (deleted_indices);
737 run_triple_wheel (&tm->triple_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_wheel.current_tick);
743 fformat (stdout, "test ran %.2f seconds, %.2f ops/second\n",
745 ((f64) adds + (f64) deletes +
746 (f64) tm->triple_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));
752 pool_foreach (e, tm->test_elts)
754 fformat (stdout, "[%d] expected to expire %d\n",
756 e->expected_to_expire);
759 pool_free (tm->test_elts);
760 tw_timer_wheel_free_4t_3w_256sl (&tm->triple_wheel);
764 static clib_error_t *
765 test2_triple_ov (tw_timer_test_main_t * tm)
768 tw_timer_test_elt_t *e;
769 u32 initial_wheel_offset = 0;
771 u32 max_expiration_time = 0;
772 u32 *deleted_indices = 0;
773 u32 adds = 0, deletes = 0;
776 clib_time_init (&tm->clib_time);
778 tw_timer_wheel_init_1t_3w_1024sl_ov (&tm->triple_ov_wheel,
779 expired_timer_triple_ov_callback,
780 1.0 /* timer interval */ , ~0);
784 initial_wheel_offset = 75700;
785 run_triple_ov_wheel (&tm->triple_ov_wheel, initial_wheel_offset);
788 "initial wheel time %d, fi %d si %d gi %d\n",
789 tm->triple_ov_wheel.current_tick,
790 tm->triple_ov_wheel.current_index[TW_TIMER_RING_FAST],
791 tm->triple_ov_wheel.current_index[TW_TIMER_RING_SLOW],
792 tm->triple_ov_wheel.current_index[TW_TIMER_RING_GLACIER]);
794 initial_wheel_offset = tm->triple_ov_wheel.current_tick;
797 "test %d timers, %d iter, %d ticks per iter, 0x%llx seed\n",
798 tm->ntimers, tm->niter, tm->ticks_per_iter, tm->seed);
800 before = clib_time_now (&tm->clib_time);
803 for (i = 0; i < tm->ntimers; i++)
805 pool_get (tm->test_elts, e);
806 clib_memset (e, 0, sizeof (*e));
810 expiration_time = random_u64 (&tm->seed) & ((1 << 17) - 1);
812 while (expiration_time == 0);
814 if (expiration_time > max_expiration_time)
815 max_expiration_time = expiration_time;
817 e->expected_to_expire = expiration_time + initial_wheel_offset;
819 e->stop_timer_handle =
820 tw_timer_start_1t_3w_1024sl_ov (&tm->triple_ov_wheel,
821 e - tm->test_elts, 0 /* timer id */ ,
827 for (i = 0; i < tm->niter; i++)
829 run_triple_ov_wheel (&tm->triple_ov_wheel, tm->ticks_per_iter);
832 vec_reset_length (deleted_indices);
833 pool_foreach (e, tm->test_elts)
835 tw_timer_stop_1t_3w_1024sl_ov (&tm->triple_ov_wheel,
836 e->stop_timer_handle);
837 vec_add1 (deleted_indices, e - tm->test_elts);
838 if (++j >= tm->ntimers / 4)
843 for (j = 0; j < vec_len (deleted_indices); j++)
844 pool_put_index (tm->test_elts, deleted_indices[j]);
848 for (j = 0; j < tm->ntimers / 4; j++)
850 pool_get (tm->test_elts, e);
851 clib_memset (e, 0, sizeof (*e));
855 expiration_time = random_u64 (&tm->seed) & ((1 << 17) - 1);
857 while (expiration_time == 0);
859 if (expiration_time > max_expiration_time)
860 max_expiration_time = expiration_time;
862 e->expected_to_expire = expiration_time +
863 tm->triple_ov_wheel.current_tick;
865 e->stop_timer_handle = tw_timer_start_1t_3w_1024sl_ov
866 (&tm->triple_ov_wheel, e - tm->test_elts, 0 /* timer id */ ,
872 vec_free (deleted_indices);
874 run_triple_ov_wheel (&tm->triple_ov_wheel, max_expiration_time + 1);
876 after = clib_time_now (&tm->clib_time);
878 fformat (stdout, "%d adds, %d deletes, %d ticks\n", adds, deletes,
879 tm->triple_ov_wheel.current_tick);
880 fformat (stdout, "test ran %.2f seconds, %.2f ops/second\n",
882 ((f64) adds + (f64) deletes +
883 (f64) tm->triple_ov_wheel.current_tick) / (after - before));
885 if (pool_elts (tm->test_elts))
886 fformat (stdout, "Note: %d elements remain in pool\n",
887 pool_elts (tm->test_elts));
889 pool_foreach (e, tm->test_elts)
893 fformat (stdout, "[%d] expected to expire %d\n",
895 e->expected_to_expire);
896 t = pool_elt_at_index (tm->triple_ov_wheel.timers, e->stop_timer_handle);
897 fformat (stdout, " expiration_time %lld\n", t->expiration_time);
900 pool_free (tm->test_elts);
901 tw_timer_wheel_free_1t_3w_1024sl_ov (&tm->triple_ov_wheel);
905 static clib_error_t *
906 test1_single (tw_timer_test_main_t * tm)
909 tw_timer_test_elt_t *e;
912 tw_timer_wheel_init_2t_1w_2048sl (&tm->single_wheel,
913 expired_timer_single_callback,
914 1.0 /* timer interval */ , ~0);
917 * Prime offset, to make sure that the wheel starts in a
918 * non-trivial position
922 run_single_wheel (&tm->single_wheel, offset);
924 fformat (stdout, "initial wheel time %d, fast index %d\n",
925 tm->single_wheel.current_tick,
926 tm->single_wheel.current_index[TW_TIMER_RING_FAST]);
928 offset = tm->single_wheel.current_tick;
930 for (i = 0; i < tm->ntimers; i++)
932 u32 expected_to_expire;
940 expected_to_expire = timer_arg + tm->single_wheel.current_tick;
942 pool_get (tm->test_elts, e);
943 clib_memset (e, 0, sizeof (*e));
944 e->expected_to_expire = expected_to_expire;
945 e->stop_timer_handle = tw_timer_start_2t_1w_2048sl
946 (&tm->single_wheel, e - tm->test_elts, 1 /* timer id */ ,
949 run_single_wheel (&tm->single_wheel, tm->ntimers + 3);
951 if (pool_elts (tm->test_elts))
952 fformat (stdout, "Note: %d elements remain in pool\n",
953 pool_elts (tm->test_elts));
955 pool_foreach (e, tm->test_elts)
957 fformat(stdout, "[%d] expected to expire %d\n",
959 e->expected_to_expire);
963 "final wheel time %d, fast index %d\n",
964 tm->single_wheel.current_tick,
965 tm->single_wheel.current_index[TW_TIMER_RING_FAST]);
967 pool_free (tm->test_elts);
968 tw_timer_wheel_free_2t_1w_2048sl (&tm->single_wheel);
972 static clib_error_t *
973 test1_double (tw_timer_test_main_t * tm)
976 tw_timer_test_elt_t *e;
979 tw_timer_wheel_init_16t_2w_512sl (&tm->double_wheel,
980 expired_timer_double_callback,
981 1.0 /* timer interval */ , ~0);
984 * Prime offset, to make sure that the wheel starts in a
985 * non-trivial position
989 run_double_wheel (&tm->double_wheel, offset);
991 fformat (stdout, "initial wheel time %d, fast index %d\n",
992 tm->double_wheel.current_tick,
993 tm->double_wheel.current_index[TW_TIMER_RING_FAST]);
995 for (i = 0; i < tm->ntimers; i++)
997 pool_get (tm->test_elts, e);
998 clib_memset (e, 0, sizeof (*e));
1000 e->expected_to_expire = i + tm->double_wheel.current_tick + 1;
1001 e->stop_timer_handle = tw_timer_start_16t_2w_512sl
1002 (&tm->double_wheel, e - tm->test_elts, 14 /* timer id */ ,
1005 run_double_wheel (&tm->double_wheel, tm->ntimers + 3);
1007 if (pool_elts (tm->test_elts))
1008 fformat (stdout, "Note: %d elements remain in pool\n",
1009 pool_elts (tm->test_elts));
1011 pool_foreach (e, tm->test_elts)
1013 fformat(stdout, "[%d] expected to expire %d\n",
1015 e->expected_to_expire);
1019 "final wheel time %d, fast index %d\n",
1020 tm->double_wheel.current_tick,
1021 tm->double_wheel.current_index[TW_TIMER_RING_FAST]);
1023 pool_free (tm->test_elts);
1024 tw_timer_wheel_free_16t_2w_512sl (&tm->double_wheel);
1028 static clib_error_t *
1029 test1_two_timer_double (tw_timer_test_main_t * tm)
1032 tw_timer_test_elt_t *e;
1035 tw_timer_wheel_init_2t_2w_512sl (&tm->two_timer_double_wheel,
1036 expired_timer_two_timer_double_callback,
1037 1.0 /* timer interval */ , ~0);
1040 * Prime offset, to make sure that the wheel starts in a
1041 * non-trivial position
1045 run_two_timer_double_wheel (&tm->two_timer_double_wheel, offset);
1047 fformat (stdout, "initial wheel time %d, fast index %d\n",
1048 tm->two_timer_double_wheel.current_tick,
1049 tm->two_timer_double_wheel.current_index[TW_TIMER_RING_FAST]);
1051 for (i = 0; i < tm->ntimers; i++)
1053 pool_get (tm->test_elts, e);
1054 clib_memset (e, 0, sizeof (*e));
1056 e->expected_to_expire = i + tm->two_timer_double_wheel.current_tick + 1;
1057 e->stop_timer_handle = tw_timer_start_2t_2w_512sl
1058 (&tm->two_timer_double_wheel, e - tm->test_elts, 1 /* timer id */ ,
1061 run_two_timer_double_wheel (&tm->two_timer_double_wheel, tm->ntimers + 3);
1063 if (pool_elts (tm->test_elts))
1064 fformat (stdout, "Note: %d elements remain in pool\n",
1065 pool_elts (tm->test_elts));
1067 pool_foreach (e, tm->test_elts)
1069 fformat(stdout, "[%d] expected to expire %d\n",
1071 e->expected_to_expire);
1075 "final wheel time %d, fast index %d\n",
1076 tm->two_timer_double_wheel.current_tick,
1077 tm->two_timer_double_wheel.current_index[TW_TIMER_RING_FAST]);
1079 pool_free (tm->test_elts);
1080 tw_timer_wheel_free_2t_2w_512sl (&tm->two_timer_double_wheel);
1084 static clib_error_t *
1085 test3_triple_double (tw_timer_test_main_t * tm)
1087 tw_timer_test_elt_t *e;
1088 u32 initial_wheel_offset = 0;
1089 u32 expiration_time;
1090 u32 max_expiration_time = 0;
1091 u32 adds = 0, deletes = 0;
1094 clib_time_init (&tm->clib_time);
1096 tw_timer_wheel_init_4t_3w_256sl (&tm->triple_wheel,
1097 expired_timer_triple_callback,
1098 1.0 /* timer interval */ , ~0);
1100 initial_wheel_offset = 0;
1101 run_triple_wheel (&tm->triple_wheel, initial_wheel_offset);
1104 "initial wheel time %d, fi %d si %d gi %d\n",
1105 tm->triple_wheel.current_tick,
1106 tm->triple_wheel.current_index[TW_TIMER_RING_FAST],
1107 tm->triple_wheel.current_index[TW_TIMER_RING_SLOW],
1108 tm->triple_wheel.current_index[TW_TIMER_RING_GLACIER]);
1110 initial_wheel_offset = tm->triple_wheel.current_tick;
1112 fformat (stdout, "Create a timer which expires at wheel-time (1, 0, 0)\n");
1114 before = clib_time_now (&tm->clib_time);
1116 /* Prime the pump */
1117 pool_get (tm->test_elts, e);
1118 clib_memset (e, 0, sizeof (*e));
1120 /* 1 glacier ring tick from now */
1121 expiration_time = TW_SLOTS_PER_RING * TW_SLOTS_PER_RING;
1122 e->expected_to_expire = expiration_time + initial_wheel_offset;
1123 max_expiration_time = expiration_time;
1125 e->stop_timer_handle =
1126 tw_timer_start_4t_3w_256sl (&tm->triple_wheel, e - tm->test_elts,
1130 run_triple_wheel (&tm->triple_wheel, max_expiration_time + 1);
1132 after = clib_time_now (&tm->clib_time);
1134 fformat (stdout, "%d adds, %d deletes, %d ticks\n", adds, deletes,
1135 tm->triple_wheel.current_tick);
1136 fformat (stdout, "test ran %.2f seconds, %.2f ops/second\n",
1138 ((f64) adds + (f64) deletes +
1139 (f64) tm->triple_wheel.current_tick) / (after - before));
1141 if (pool_elts (tm->test_elts))
1142 fformat (stdout, "Note: %d elements remain in pool\n",
1143 pool_elts (tm->test_elts));
1145 pool_foreach (e, tm->test_elts)
1147 fformat (stdout, "[%d] expected to expire %d\n",
1149 e->expected_to_expire);
1152 pool_free (tm->test_elts);
1153 tw_timer_wheel_free_4t_3w_256sl (&tm->triple_wheel);
1157 static clib_error_t *
1158 test4_double_double (tw_timer_test_main_t * tm)
1161 tw_timer_test_elt_t *e;
1162 u32 initial_wheel_offset;
1163 u32 expiration_time;
1164 u32 max_expiration_time = 0;
1165 u32 *deleted_indices = 0;
1166 u32 adds = 0, deletes = 0;
1169 clib_time_init (&tm->clib_time);
1171 tw_timer_wheel_init_16t_2w_512sl (&tm->double_wheel,
1172 expired_timer_double_callback,
1173 1.0 /* timer interval */ , ~0);
1175 initial_wheel_offset = 0;
1177 run_double_wheel (&tm->double_wheel, initial_wheel_offset);
1179 fformat (stdout, "initial wheel time %d, fast index %d slow index %d\n",
1180 tm->double_wheel.current_tick,
1181 tm->double_wheel.current_index[TW_TIMER_RING_FAST],
1182 tm->double_wheel.current_index[TW_TIMER_RING_SLOW]);
1184 initial_wheel_offset = tm->double_wheel.current_tick;
1186 fformat (stdout, "test timer which expires at 512 ticks\n");
1188 before = clib_time_now (&tm->clib_time);
1190 /* Prime the pump */
1191 for (i = 0; i < tm->ntimers; i++)
1193 pool_get (tm->test_elts, e);
1194 clib_memset (e, 0, sizeof (*e));
1196 expiration_time = 512;
1198 if (expiration_time > max_expiration_time)
1199 max_expiration_time = expiration_time;
1201 e->expected_to_expire = expiration_time + initial_wheel_offset;
1202 e->stop_timer_handle =
1203 tw_timer_start_16t_2w_512sl (&tm->double_wheel, e - tm->test_elts,
1210 vec_free (deleted_indices);
1212 run_double_wheel (&tm->double_wheel, max_expiration_time + 1);
1214 after = clib_time_now (&tm->clib_time);
1216 fformat (stdout, "%d adds, %d deletes, %d ticks\n", adds, deletes,
1217 tm->double_wheel.current_tick);
1218 fformat (stdout, "test ran %.2f seconds, %.2f ops/second\n",
1220 ((f64) adds + (f64) deletes +
1221 (f64) tm->double_wheel.current_tick) / (after - before));
1223 if (pool_elts (tm->test_elts))
1224 fformat (stdout, "Note: %d elements remain in pool\n",
1225 pool_elts (tm->test_elts));
1227 pool_foreach (e, tm->test_elts)
1229 fformat (stdout, "[%d] expected to expire %d\n",
1231 e->expected_to_expire);
1234 pool_free (tm->test_elts);
1235 tw_timer_wheel_free_16t_2w_512sl (&tm->double_wheel);
1239 static clib_error_t *
1240 test5_double (tw_timer_test_main_t * tm)
1243 tw_timer_test_elt_t *e;
1244 u32 initial_wheel_offset;
1245 u32 expiration_time;
1246 u32 max_expiration_time = 0;
1247 u32 adds = 0, deletes = 0;
1250 clib_time_init (&tm->clib_time);
1252 tw_timer_wheel_init_16t_2w_512sl (&tm->double_wheel,
1253 expired_timer_double_callback,
1254 1.0 /* timer interval */ , ~0);
1257 initial_wheel_offset = 7567;
1259 run_double_wheel (&tm->double_wheel, initial_wheel_offset);
1261 fformat (stdout, "initial wheel time %d, fast index %d slow index %d\n",
1262 tm->double_wheel.current_tick,
1263 tm->double_wheel.current_index[TW_TIMER_RING_FAST],
1264 tm->double_wheel.current_index[TW_TIMER_RING_SLOW]);
1266 initial_wheel_offset = tm->double_wheel.current_tick;
1269 "test %d timers, %d iter, %d ticks per iter, 0x%llx seed\n",
1270 tm->ntimers, tm->niter, tm->ticks_per_iter, tm->seed);
1272 before = clib_time_now (&tm->clib_time);
1274 /* Prime the pump */
1275 for (i = 0; i < tm->ntimers; i++)
1277 pool_get (tm->test_elts, e);
1278 clib_memset (e, 0, sizeof (*e));
1280 expiration_time = i + 1;
1282 if (expiration_time > max_expiration_time)
1283 max_expiration_time = expiration_time;
1285 e->expected_to_expire = expiration_time + initial_wheel_offset;
1286 e->stop_timer_handle =
1287 tw_timer_start_16t_2w_512sl (&tm->double_wheel, e - tm->test_elts,
1294 run_double_wheel (&tm->double_wheel, max_expiration_time + 1);
1296 after = clib_time_now (&tm->clib_time);
1298 fformat (stdout, "%d adds, %d deletes, %d ticks\n", adds, deletes,
1299 tm->double_wheel.current_tick);
1300 fformat (stdout, "test ran %.2f seconds, %.2f ops/second\n",
1302 ((f64) adds + (f64) deletes +
1303 (f64) tm->double_wheel.current_tick) / (after - before));
1305 if (pool_elts (tm->test_elts))
1306 fformat (stdout, "Note: %d elements remain in pool\n",
1307 pool_elts (tm->test_elts));
1309 pool_foreach (e, tm->test_elts)
1311 fformat (stdout, "[%d] expected to expire %d\n",
1313 e->expected_to_expire);
1316 pool_free (tm->test_elts);
1317 tw_timer_wheel_free_16t_2w_512sl (&tm->double_wheel);
1321 static clib_error_t *
1322 timer_test_command_fn (tw_timer_test_main_t * tm, unformat_input_t * input)
1325 int is_test1 = 0, is_updates = 0;
1333 clib_memset (tm, 0, sizeof (*tm));
1334 /* Default values */
1335 tm->ntimers = 100000;
1336 tm->seed = 0xDEADDABEB00BFACE;
1338 tm->ticks_per_iter = 727;
1340 while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
1342 if (unformat (input, "seed %lld", &tm->seed))
1344 else if (unformat (input, "test1"))
1346 else if (unformat (input, "test2"))
1348 else if (unformat (input, "overflow"))
1350 else if (unformat (input, "lebron"))
1352 else if (unformat (input, "wilt"))
1354 else if (unformat (input, "linear"))
1356 else if (unformat (input, "updates"))
1358 else if (unformat (input, "wheels %d", &num_wheels))
1360 else if (unformat (input, "ntimers %d", &tm->ntimers))
1362 else if (unformat (input, "niter %d", &tm->niter))
1364 else if (unformat (input, "ticks_per_iter %d", &tm->ticks_per_iter))
1370 if (is_test1 + is_test2 + is_test3 + is_test4 + is_test5 == 0)
1371 return clib_error_return (0, "No test specified [test1..n]");
1373 if (num_wheels < 1 || num_wheels > 3)
1374 return clib_error_return (0, "unsupported... 1 or 2 wheels only");
1378 if (num_wheels == 1)
1379 return test1_single (tm);
1382 (void) test1_double (tm);
1383 return test1_two_timer_double (tm);
1388 if (num_wheels == 1)
1389 return test2_single (tm);
1390 else if (num_wheels == 2)
1392 return test2_double_updates (tm);
1394 return test2_double (tm);
1395 else if (num_wheels == 3)
1398 return test2_triple (tm);
1400 return test2_triple_ov (tm);
1404 return test3_triple_double (tm);
1407 return test4_double_double (tm);
1410 return test5_double (tm);
1418 main (int argc, char *argv[])
1421 clib_error_t *error;
1422 tw_timer_test_main_t *tm = &tw_timer_test_main;
1424 clib_mem_init (0, 3ULL << 30);
1426 unformat_init_command_line (&i, argv);
1427 error = timer_test_command_fn (tm, &i);
1432 clib_error_report (error);
1437 #endif /* CLIB_UNIX */
1439 /* For debugging... */
1441 pifi (void *p, u32 index)
1443 return pool_is_free_index (p, index);
1455 return (pool_elts (v));
1459 * fd.io coding-style-patch-verification: ON
1462 * eval: (c-set-style "gnu")