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>
9 /** Handle returned from tw_start_timer */
10 u32 stop_timer_handle;
12 /** Test item should expire at this clock tick */
13 u32 expected_to_expire;
14 } tw_timer_test_elt_t;
18 /** Pool of test objects */
19 tw_timer_test_elt_t *test_elts;
21 /** The single-wheel */
22 tw_timer_wheel_2t_1w_2048sl_t single_wheel;
24 /** The double-wheel */
25 tw_timer_wheel_16t_2w_512sl_t double_wheel;
27 /** random number seed */
30 /** number of timers */
33 /** number of "churn" iterations */
36 /** number of clock ticks per churn iteration */
40 clib_time_t clib_time;
41 } tw_timer_test_main_t;
43 tw_timer_test_main_t tw_timer_test_main;
46 run_single_wheel (tw_timer_wheel_2t_1w_2048sl_t * tw, u32 n_ticks)
49 f64 now = tw->last_run_time + 1.01;
51 for (i = 0; i < n_ticks; i++)
53 tw_timer_expire_timers_2t_1w_2048sl (tw, now);
59 run_double_wheel (tw_timer_wheel_16t_2w_512sl_t * tw, u32 n_ticks)
62 f64 now = tw->last_run_time + 1.01;
64 for (i = 0; i < n_ticks; i++)
66 tw_timer_expire_timers_16t_2w_512sl (tw, now);
72 expired_timer_single_callback (u32 * expired_timers)
75 u32 pool_index, timer_id;
76 tw_timer_test_elt_t *e;
77 tw_timer_test_main_t *tm = &tw_timer_test_main;
79 for (i = 0; i < vec_len (expired_timers); i++)
81 pool_index = expired_timers[i] & 0x7FFFFFFF;
82 timer_id = expired_timers[i] >> 31;
84 ASSERT (timer_id == 1);
86 e = pool_elt_at_index (tm->test_elts, pool_index);
88 if (e->expected_to_expire != tm->single_wheel.current_tick)
90 fformat (stdout, "[%d] expired at %d not %d\n",
91 e - tm->test_elts, tm->single_wheel.current_tick,
92 e->expected_to_expire);
94 pool_put (tm->test_elts, e);
99 expired_timer_double_callback (u32 * expired_timers)
102 u32 pool_index, timer_id;
103 tw_timer_test_elt_t *e;
104 tw_timer_test_main_t *tm = &tw_timer_test_main;
106 for (i = 0; i < vec_len (expired_timers); i++)
108 pool_index = expired_timers[i] & 0x0FFFFFFF;
109 timer_id = expired_timers[i] >> 28;
111 ASSERT (timer_id == 14);
113 e = pool_elt_at_index (tm->test_elts, pool_index);
115 if (e->expected_to_expire != tm->double_wheel.current_tick)
117 fformat (stdout, "[%d] expired at %d not %d\n",
118 e - tm->test_elts, tm->double_wheel.current_tick,
119 e->expected_to_expire);
121 pool_put (tm->test_elts, e);
125 static clib_error_t *
126 test2_single (tw_timer_test_main_t * tm)
129 tw_timer_test_elt_t *e;
130 u32 initial_wheel_offset;
132 u32 max_expiration_time = 0;
133 u32 *deleted_indices = 0;
134 u32 adds = 0, deletes = 0;
137 clib_time_init (&tm->clib_time);
139 tw_timer_wheel_init_2t_1w_2048sl (&tm->single_wheel,
140 expired_timer_single_callback,
141 1.0 /* timer interval */ );
144 initial_wheel_offset = 757;
146 run_single_wheel (&tm->single_wheel, initial_wheel_offset);
148 fformat (stdout, "test %d timers, %d iter, %d ticks per iter, 0x%x seed\n",
149 tm->ntimers, tm->niter, tm->ticks_per_iter, tm->seed);
151 before = clib_time_now (&tm->clib_time);
154 for (i = 0; i < tm->ntimers; i++)
156 pool_get (tm->test_elts, e);
157 memset (e, 0, sizeof (*e));
161 expiration_time = random_u32 (&tm->seed) & (2047);
163 while (expiration_time == 0);
165 if (expiration_time > max_expiration_time)
166 max_expiration_time = expiration_time;
168 e->expected_to_expire = expiration_time + initial_wheel_offset;
169 e->stop_timer_handle =
170 tw_timer_start_2t_1w_2048sl (&tm->single_wheel, e - tm->test_elts,
177 for (i = 0; i < tm->niter; i++)
179 run_single_wheel (&tm->single_wheel, tm->ticks_per_iter);
182 vec_reset_length (deleted_indices);
184 pool_foreach (e, tm->test_elts,
186 tw_timer_stop_2t_1w_2048sl (&tm->single_wheel, e->stop_timer_handle);
187 vec_add1 (deleted_indices, e - tm->test_elts);
188 if (++j >= tm->ntimers / 4)
194 for (j = 0; j < vec_len (deleted_indices); j++)
195 pool_put_index (tm->test_elts, deleted_indices[j]);
199 for (j = 0; j < tm->ntimers / 4; j++)
201 pool_get (tm->test_elts, e);
202 memset (e, 0, sizeof (*e));
206 expiration_time = random_u32 (&tm->seed) & (2047);
208 while (expiration_time == 0);
210 if (expiration_time > max_expiration_time)
211 max_expiration_time = expiration_time;
213 e->expected_to_expire =
214 expiration_time + tm->single_wheel.current_tick;
215 e->stop_timer_handle = tw_timer_start_2t_1w_2048sl
216 (&tm->single_wheel, e - tm->test_elts, 1 /* timer id */ ,
222 vec_free (deleted_indices);
224 run_single_wheel (&tm->single_wheel, max_expiration_time + 1);
226 after = clib_time_now (&tm->clib_time);
228 fformat (stdout, "%d adds, %d deletes, %d ticks\n", adds, deletes,
229 tm->single_wheel.current_tick);
230 fformat (stdout, "test ran %.2f seconds, %.2f ops/second\n",
232 ((f64) adds + (f64) deletes +
233 (f64) tm->single_wheel.current_tick) / (after - before));
235 if (pool_elts (tm->test_elts))
236 fformat (stdout, "Note: %d elements remain in pool\n",
237 pool_elts (tm->test_elts));
240 pool_foreach (e, tm->test_elts,
242 fformat (stdout, "[%d] expected to expire %d\n",
244 e->expected_to_expire);
248 pool_free (tm->test_elts);
249 tw_timer_wheel_free_2t_1w_2048sl (&tm->single_wheel);
253 static clib_error_t *
254 test2_double (tw_timer_test_main_t * tm)
257 tw_timer_test_elt_t *e;
258 u32 initial_wheel_offset;
260 u32 max_expiration_time = 0;
261 u32 *deleted_indices = 0;
262 u32 adds = 0, deletes = 0;
265 clib_time_init (&tm->clib_time);
267 tw_timer_wheel_init_16t_2w_512sl (&tm->double_wheel,
268 expired_timer_double_callback,
269 1.0 /* timer interval */ );
272 initial_wheel_offset = 757;
274 run_double_wheel (&tm->double_wheel, initial_wheel_offset);
276 fformat (stdout, "test %d timers, %d iter, %d ticks per iter, 0x%x seed\n",
277 tm->ntimers, tm->niter, tm->ticks_per_iter, tm->seed);
279 before = clib_time_now (&tm->clib_time);
282 for (i = 0; i < tm->ntimers; i++)
284 pool_get (tm->test_elts, e);
285 memset (e, 0, sizeof (*e));
289 expiration_time = random_u32 (&tm->seed) & ((1 << 17) - 1);
291 while (expiration_time == 0);
293 if (expiration_time > max_expiration_time)
294 max_expiration_time = expiration_time;
296 e->expected_to_expire = expiration_time + initial_wheel_offset;
297 e->stop_timer_handle =
298 tw_timer_start_16t_2w_512sl (&tm->double_wheel, e - tm->test_elts,
305 for (i = 0; i < tm->niter; i++)
307 run_double_wheel (&tm->double_wheel, tm->ticks_per_iter);
310 vec_reset_length (deleted_indices);
312 pool_foreach (e, tm->test_elts,
314 tw_timer_stop_16t_2w_512sl (&tm->double_wheel, e->stop_timer_handle);
315 vec_add1 (deleted_indices, e - tm->test_elts);
316 if (++j >= tm->ntimers / 4)
322 for (j = 0; j < vec_len (deleted_indices); j++)
323 pool_put_index (tm->test_elts, deleted_indices[j]);
327 for (j = 0; j < tm->ntimers / 4; j++)
329 pool_get (tm->test_elts, e);
330 memset (e, 0, sizeof (*e));
334 expiration_time = random_u32 (&tm->seed) & ((1 << 17) - 1);
336 while (expiration_time == 0);
338 if (expiration_time > max_expiration_time)
339 max_expiration_time = expiration_time;
341 e->expected_to_expire = expiration_time +
342 tm->double_wheel.current_tick;
343 e->stop_timer_handle = tw_timer_start_16t_2w_512sl
344 (&tm->double_wheel, e - tm->test_elts, 14 /* timer id */ ,
350 vec_free (deleted_indices);
352 run_double_wheel (&tm->double_wheel, max_expiration_time + 1);
354 after = clib_time_now (&tm->clib_time);
356 fformat (stdout, "%d adds, %d deletes, %d ticks\n", adds, deletes,
357 tm->double_wheel.current_tick);
358 fformat (stdout, "test ran %.2f seconds, %.2f ops/second\n",
360 ((f64) adds + (f64) deletes +
361 (f64) tm->double_wheel.current_tick) / (after - before));
363 if (pool_elts (tm->test_elts))
364 fformat (stdout, "Note: %d elements remain in pool\n",
365 pool_elts (tm->test_elts));
368 pool_foreach (e, tm->test_elts,
370 fformat (stdout, "[%d] expected to expire %d\n",
372 e->expected_to_expire);
376 pool_free (tm->test_elts);
377 tw_timer_wheel_free_16t_2w_512sl (&tm->double_wheel);
381 static clib_error_t *
382 test1_single (tw_timer_test_main_t * tm)
385 tw_timer_test_elt_t *e;
388 tw_timer_wheel_init_2t_1w_2048sl (&tm->single_wheel,
389 expired_timer_single_callback,
390 1.0 /* timer interval */ );
393 * Prime offset, to make sure that the wheel starts in a
394 * non-trivial position
398 run_single_wheel (&tm->single_wheel, offset);
400 fformat (stdout, "initial wheel time %d, fast index %d\n",
401 tm->single_wheel.current_tick,
402 tm->single_wheel.current_index[TW_TIMER_RING_FAST]);
404 for (i = 0; i < tm->ntimers; i++)
406 u32 expected_to_expire;
414 expected_to_expire = timer_arg + offset;
416 pool_get (tm->test_elts, e);
417 memset (e, 0, sizeof (*e));
418 e->expected_to_expire = expected_to_expire;
419 e->stop_timer_handle = tw_timer_start_2t_1w_2048sl
420 (&tm->single_wheel, e - tm->test_elts, 1 /* timer id */ ,
423 run_single_wheel (&tm->single_wheel, tm->ntimers + 3);
425 if (pool_elts (tm->test_elts))
426 fformat (stdout, "Note: %d elements remain in pool\n",
427 pool_elts (tm->test_elts));
430 pool_foreach (e, tm->test_elts,
432 fformat(stdout, "[%d] expected to expire %d\n",
434 e->expected_to_expire);
439 "final wheel time %d, fast index %d\n",
440 tm->single_wheel.current_tick,
441 tm->single_wheel.current_index[TW_TIMER_RING_FAST]);
443 pool_free (tm->test_elts);
444 tw_timer_wheel_free_2t_1w_2048sl (&tm->single_wheel);
448 static clib_error_t *
449 test1_double (tw_timer_test_main_t * tm)
452 tw_timer_test_elt_t *e;
455 tw_timer_wheel_init_16t_2w_512sl (&tm->double_wheel,
456 expired_timer_double_callback,
457 1.0 /* timer interval */ );
460 * Prime offset, to make sure that the wheel starts in a
461 * non-trivial position
465 run_double_wheel (&tm->double_wheel, offset);
467 fformat (stdout, "initial wheel time %d, fast index %d\n",
468 tm->double_wheel.current_tick,
469 tm->double_wheel.current_index[TW_TIMER_RING_FAST]);
471 for (i = 0; i < tm->ntimers; i++)
473 pool_get (tm->test_elts, e);
474 memset (e, 0, sizeof (*e));
476 e->expected_to_expire = i + offset + 1;
477 e->stop_timer_handle = tw_timer_start_16t_2w_512sl
478 (&tm->double_wheel, e - tm->test_elts, 14 /* timer id */ ,
481 run_double_wheel (&tm->double_wheel, tm->ntimers + 3);
483 if (pool_elts (tm->test_elts))
484 fformat (stdout, "Note: %d elements remain in pool\n",
485 pool_elts (tm->test_elts));
488 pool_foreach (e, tm->test_elts,
490 fformat(stdout, "[%d] expected to expire %d\n",
492 e->expected_to_expire);
497 "final wheel time %d, fast index %d\n",
498 tm->double_wheel.current_tick,
499 tm->double_wheel.current_index[TW_TIMER_RING_FAST]);
501 pool_free (tm->test_elts);
502 tw_timer_wheel_free_16t_2w_512sl (&tm->double_wheel);
506 static clib_error_t *
507 timer_test_command_fn (tw_timer_test_main_t * tm, unformat_input_t * input)
514 memset (tm, 0, sizeof (*tm));
516 tm->ntimers = 100000;
517 tm->seed = 0xDEADDABE;
519 tm->ticks_per_iter = 727;
521 while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
523 if (unformat (input, "seed %d", &tm->seed))
525 else if (unformat (input, "test1"))
527 else if (unformat (input, "test2"))
529 else if (unformat (input, "wheels %d", &num_wheels))
531 else if (unformat (input, "ntimers %d", &tm->ntimers))
533 else if (unformat (input, "niter %d", &tm->niter))
535 else if (unformat (input, "ticks_per_iter %d", &tm->ticks_per_iter))
539 if (is_test1 + is_test2 == 0)
540 return clib_error_return (0, "No test specified [test1..n]");
542 if (num_wheels < 1 || num_wheels > 2)
543 return clib_error_return (0, "unsupported... 1 or 2 wheels only");
548 return test1_single (tm);
550 return test1_double (tm);
555 return test2_single (tm);
557 return test2_double (tm);
565 main (int argc, char *argv[])
569 tw_timer_test_main_t *tm = &tw_timer_test_main;
571 clib_mem_init (0, 3ULL << 30);
573 unformat_init_command_line (&i, argv);
574 error = timer_test_command_fn (tm, &i);
579 clib_error_report (error);
584 #endif /* CLIB_UNIX */
587 * fd.io coding-style-patch-verification: ON
590 * eval: (c-set-style "gnu")