X-Git-Url: https://gerrit.fd.io/r/gitweb?a=blobdiff_plain;f=src%2Fvppinfra%2Ftest_tw_timer.c;h=499cc017ba1fae3fa8304f49e29432ab2e31ef41;hb=9076789779c5a038ec17936130a556703c234fa8;hp=a0287b8986298266bb314b9150caba0010840f23;hpb=8e8f98c9d46788438bd176f7c2bfde0a5837cad9;p=vpp.git diff --git a/src/vppinfra/test_tw_timer.c b/src/vppinfra/test_tw_timer.c index a0287b89862..499cc017ba1 100644 --- a/src/vppinfra/test_tw_timer.c +++ b/src/vppinfra/test_tw_timer.c @@ -2,7 +2,10 @@ #include #include #include +#include #include +#include +#include typedef struct { @@ -10,7 +13,7 @@ typedef struct u32 stop_timer_handle; /** Test item should expire at this clock tick */ - u32 expected_to_expire; + u64 expected_to_expire; } tw_timer_test_elt_t; typedef struct @@ -24,8 +27,17 @@ typedef struct /** The double-wheel */ tw_timer_wheel_16t_2w_512sl_t double_wheel; + /* The triple wheel */ + tw_timer_wheel_4t_3w_256sl_t triple_wheel; + + /* The triple wheel with overflow vector */ + tw_timer_wheel_1t_3w_1024sl_ov_t triple_ov_wheel; + + /* Another two timer wheel geometry */ + tw_timer_wheel_2t_2w_512sl_t two_timer_double_wheel; + /** random number seed */ - u32 seed; + u64 seed; /** number of timers */ u32 ntimers; @@ -68,6 +80,45 @@ run_double_wheel (tw_timer_wheel_16t_2w_512sl_t * tw, u32 n_ticks) } } +static void +run_two_timer_double_wheel (tw_timer_wheel_2t_2w_512sl_t * tw, u32 n_ticks) +{ + u32 i; + f64 now = tw->last_run_time + 1.01; + + for (i = 0; i < n_ticks; i++) + { + tw_timer_expire_timers_2t_2w_512sl (tw, now); + now += 1.01; + } +} + +static void +run_triple_wheel (tw_timer_wheel_4t_3w_256sl_t * tw, u32 n_ticks) +{ + u32 i; + f64 now = tw->last_run_time + 1.01; + + for (i = 0; i < n_ticks; i++) + { + tw_timer_expire_timers_4t_3w_256sl (tw, now); + now += 1.01; + } +} + +static void +run_triple_ov_wheel (tw_timer_wheel_1t_3w_1024sl_ov_t * tw, u32 n_ticks) +{ + u32 i; + f64 now = tw->last_run_time + 1.01; + + for (i = 0; i < n_ticks; i++) + { + tw_timer_expire_timers_1t_3w_1024sl_ov (tw, now); + now += 1.01; + } +} + static void expired_timer_single_callback (u32 * expired_timers) { @@ -87,7 +138,7 @@ expired_timer_single_callback (u32 * expired_timers) if (e->expected_to_expire != tm->single_wheel.current_tick) { - fformat (stdout, "[%d] expired at %d not %d\n", + fformat (stdout, "[%d] expired at %lld not %lld\n", e - tm->test_elts, tm->single_wheel.current_tick, e->expected_to_expire); } @@ -114,7 +165,7 @@ expired_timer_double_callback (u32 * expired_timers) if (e->expected_to_expire != tm->double_wheel.current_tick) { - fformat (stdout, "[%d] expired at %d not %d\n", + fformat (stdout, "[%d] expired at %lld not %lld\n", e - tm->test_elts, tm->double_wheel.current_tick, e->expected_to_expire); } @@ -122,13 +173,91 @@ expired_timer_double_callback (u32 * expired_timers) } } +static void +expired_timer_two_timer_double_callback (u32 * expired_timers) +{ + int i; + u32 pool_index, timer_id; + tw_timer_test_elt_t *e; + tw_timer_test_main_t *tm = &tw_timer_test_main; + + for (i = 0; i < vec_len (expired_timers); i++) + { + pool_index = expired_timers[i] & 0x7FFFFFFF; + timer_id = expired_timers[i] >> 31; + + ASSERT (timer_id == 1); + + e = pool_elt_at_index (tm->test_elts, pool_index); + + if (e->expected_to_expire != tm->two_timer_double_wheel.current_tick) + { + fformat (stdout, "[%d] expired at %lld not %lld\n", + e - tm->test_elts, tm->two_timer_double_wheel.current_tick, + e->expected_to_expire); + } + pool_put (tm->test_elts, e); + } +} + +static void +expired_timer_triple_callback (u32 * expired_timers) +{ + int i; + u32 pool_index, timer_id; + tw_timer_test_elt_t *e; + tw_timer_test_main_t *tm = &tw_timer_test_main; + + for (i = 0; i < vec_len (expired_timers); i++) + { + pool_index = expired_timers[i] & 0x3FFFFFFF; + timer_id = expired_timers[i] >> 30; + + ASSERT (timer_id == 3); + + e = pool_elt_at_index (tm->test_elts, pool_index); + + if (e->expected_to_expire != tm->triple_wheel.current_tick) + { + fformat (stdout, "[%d] expired at %lld not %lld\n", + e - tm->test_elts, tm->triple_wheel.current_tick, + e->expected_to_expire); + } + pool_put (tm->test_elts, e); + } +} + +static void +expired_timer_triple_ov_callback (u32 * expired_timers) +{ + int i; + u32 pool_index; + tw_timer_test_elt_t *e; + tw_timer_test_main_t *tm = &tw_timer_test_main; + + for (i = 0; i < vec_len (expired_timers); i++) + { + pool_index = expired_timers[i]; + + e = pool_elt_at_index (tm->test_elts, pool_index); + + if (e->expected_to_expire != tm->triple_ov_wheel.current_tick) + { + fformat (stdout, "[%d] expired at %lld not %lld\n", + e - tm->test_elts, tm->triple_ov_wheel.current_tick, + e->expected_to_expire); + } + pool_put (tm->test_elts, e); + } +} + static clib_error_t * test2_single (tw_timer_test_main_t * tm) { u32 i, j; tw_timer_test_elt_t *e; u32 initial_wheel_offset; - u32 expiration_time; + u64 expiration_time; u32 max_expiration_time = 0; u32 *deleted_indices = 0; u32 adds = 0, deletes = 0; @@ -138,14 +267,21 @@ test2_single (tw_timer_test_main_t * tm) tw_timer_wheel_init_2t_1w_2048sl (&tm->single_wheel, expired_timer_single_callback, - 1.0 /* timer interval */ ); + 1.0 /* timer interval */ , ~0); /* Prime offset */ initial_wheel_offset = 757; run_single_wheel (&tm->single_wheel, initial_wheel_offset); - fformat (stdout, "test %d timers, %d iter, %d ticks per iter, 0x%x seed\n", + fformat (stdout, "initial wheel time %d, fast index %d\n", + tm->single_wheel.current_tick, + tm->single_wheel.current_index[TW_TIMER_RING_FAST]); + + initial_wheel_offset = tm->single_wheel.current_tick; + + fformat (stdout, + "test %d timers, %d iter, %d ticks per iter, 0x%llx seed\n", tm->ntimers, tm->niter, tm->ticks_per_iter, tm->seed); before = clib_time_now (&tm->clib_time); @@ -154,11 +290,11 @@ test2_single (tw_timer_test_main_t * tm) for (i = 0; i < tm->ntimers; i++) { pool_get (tm->test_elts, e); - memset (e, 0, sizeof (*e)); + clib_memset (e, 0, sizeof (*e)); do { - expiration_time = random_u32 (&tm->seed) & (2047); + expiration_time = random_u64 (&tm->seed) & (2047); } while (expiration_time == 0); @@ -192,18 +328,20 @@ test2_single (tw_timer_test_main_t * tm) del_and_re_add: for (j = 0; j < vec_len (deleted_indices); j++) - pool_put_index (tm->test_elts, deleted_indices[j]); + { + pool_put_index (tm->test_elts, deleted_indices[j]); + } deletes += j; for (j = 0; j < tm->ntimers / 4; j++) { pool_get (tm->test_elts, e); - memset (e, 0, sizeof (*e)); + clib_memset (e, 0, sizeof (*e)); do { - expiration_time = random_u32 (&tm->seed) & (2047); + expiration_time = random_u64 (&tm->seed) & (2047); } while (expiration_time == 0); @@ -266,14 +404,22 @@ test2_double (tw_timer_test_main_t * tm) tw_timer_wheel_init_16t_2w_512sl (&tm->double_wheel, expired_timer_double_callback, - 1.0 /* timer interval */ ); + 1.0 /* timer interval */ , ~0); /* Prime offset */ - initial_wheel_offset = 757; + initial_wheel_offset = 7577; run_double_wheel (&tm->double_wheel, initial_wheel_offset); - fformat (stdout, "test %d timers, %d iter, %d ticks per iter, 0x%x seed\n", + fformat (stdout, "initial wheel time %d, fast index %d slow index %d\n", + tm->double_wheel.current_tick, + tm->double_wheel.current_index[TW_TIMER_RING_FAST], + tm->double_wheel.current_index[TW_TIMER_RING_SLOW]); + + initial_wheel_offset = tm->double_wheel.current_tick; + + fformat (stdout, + "test %d timers, %d iter, %d ticks per iter, 0x%llx seed\n", tm->ntimers, tm->niter, tm->ticks_per_iter, tm->seed); before = clib_time_now (&tm->clib_time); @@ -282,11 +428,11 @@ test2_double (tw_timer_test_main_t * tm) for (i = 0; i < tm->ntimers; i++) { pool_get (tm->test_elts, e); - memset (e, 0, sizeof (*e)); + clib_memset (e, 0, sizeof (*e)); do { - expiration_time = random_u32 (&tm->seed) & ((1 << 17) - 1); + expiration_time = random_u64 (&tm->seed) & ((1 << 17) - 1); } while (expiration_time == 0); @@ -294,6 +440,7 @@ test2_double (tw_timer_test_main_t * tm) max_expiration_time = expiration_time; e->expected_to_expire = expiration_time + initial_wheel_offset; + e->stop_timer_handle = tw_timer_start_16t_2w_512sl (&tm->double_wheel, e - tm->test_elts, 14 /* timer id */ , @@ -327,11 +474,11 @@ test2_double (tw_timer_test_main_t * tm) for (j = 0; j < tm->ntimers / 4; j++) { pool_get (tm->test_elts, e); - memset (e, 0, sizeof (*e)); + clib_memset (e, 0, sizeof (*e)); do { - expiration_time = random_u32 (&tm->seed) & ((1 << 17) - 1); + expiration_time = random_u64 (&tm->seed) & ((1 << 17) - 1); } while (expiration_time == 0); @@ -340,6 +487,7 @@ test2_double (tw_timer_test_main_t * tm) e->expected_to_expire = expiration_time + tm->double_wheel.current_tick; + e->stop_timer_handle = tw_timer_start_16t_2w_512sl (&tm->double_wheel, e - tm->test_elts, 14 /* timer id */ , expiration_time); @@ -378,49 +526,98 @@ test2_double (tw_timer_test_main_t * tm) return 0; } +static u32 +get_expiration_time (tw_timer_test_main_t * tm) +{ + u32 expiration_time; + do + { + expiration_time = random_u64 (&tm->seed) & ((1 << 17) - 1); + } + while (expiration_time == 0); + return expiration_time; +} + static clib_error_t * -test1_single (tw_timer_test_main_t * tm) +test2_double_updates (tw_timer_test_main_t * tm) { - u32 i; + u32 i, j; tw_timer_test_elt_t *e; - u32 offset; + u32 initial_wheel_offset; + u32 expiration_time; + u32 max_expiration_time = 0, updates = 0; + f64 before, after; - tw_timer_wheel_init_2t_1w_2048sl (&tm->single_wheel, - expired_timer_single_callback, - 1.0 /* timer interval */ ); + clib_time_init (&tm->clib_time); + tw_timer_wheel_init_16t_2w_512sl (&tm->double_wheel, + expired_timer_double_callback, + 1.0 /* timer interval */ , ~0); - /* - * Prime offset, to make sure that the wheel starts in a - * non-trivial position - */ - offset = 123; + /* Prime offset */ + initial_wheel_offset = 7577; + run_double_wheel (&tm->double_wheel, initial_wheel_offset); + fformat (stdout, "initial wheel time %d, fast index %d slow index %d\n", + tm->double_wheel.current_tick, + tm->double_wheel.current_index[TW_TIMER_RING_FAST], + tm->double_wheel.current_index[TW_TIMER_RING_SLOW]); - run_single_wheel (&tm->single_wheel, offset); + initial_wheel_offset = tm->double_wheel.current_tick; + fformat (stdout, + "test %d timers, %d iter, %d ticks per iter, 0x%llx seed\n", + tm->ntimers, tm->niter, tm->ticks_per_iter, tm->seed); - fformat (stdout, "initial wheel time %d, fast index %d\n", - tm->single_wheel.current_tick, - tm->single_wheel.current_index[TW_TIMER_RING_FAST]); + before = clib_time_now (&tm->clib_time); + /* Prime the pump */ for (i = 0; i < tm->ntimers; i++) { - u32 expected_to_expire; - u32 timer_arg; + pool_get (tm->test_elts, e); + clib_memset (e, 0, sizeof (*e)); - timer_arg = 1 + i; - timer_arg &= 2047; - if (timer_arg == 0) - timer_arg = 1; + expiration_time = get_expiration_time (tm); + max_expiration_time = clib_max (expiration_time, max_expiration_time); - expected_to_expire = timer_arg + offset; + e->expected_to_expire = expiration_time + initial_wheel_offset; + e->stop_timer_handle = tw_timer_start_16t_2w_512sl (&tm->double_wheel, + e - tm->test_elts, + 14 /* timer id */ , + expiration_time); + } - pool_get (tm->test_elts, e); - memset (e, 0, sizeof (*e)); - e->expected_to_expire = expected_to_expire; - e->stop_timer_handle = tw_timer_start_2t_1w_2048sl - (&tm->single_wheel, e - tm->test_elts, 1 /* timer id */ , - timer_arg); + for (i = 0; i < tm->niter; i++) + { + run_double_wheel (&tm->double_wheel, tm->ticks_per_iter); + + j = 0; + + /* *INDENT-OFF* */ + pool_foreach (e, tm->test_elts, + ({ + expiration_time = get_expiration_time (tm); + max_expiration_time = clib_max (expiration_time, max_expiration_time); + e->expected_to_expire = expiration_time + + tm->double_wheel.current_tick; + tw_timer_update_16t_2w_512sl (&tm->double_wheel, e->stop_timer_handle, + expiration_time); + if (++j >= tm->ntimers / 4) + goto done; + })); + /* *INDENT-ON* */ + + done: + updates += j; } - run_single_wheel (&tm->single_wheel, tm->ntimers + 3); + + run_double_wheel (&tm->double_wheel, max_expiration_time + 1); + + after = clib_time_now (&tm->clib_time); + + fformat (stdout, "%d updates, %d ticks\n", updates, + tm->double_wheel.current_tick); + fformat (stdout, "test ran %.2f seconds, %.2f ops/second\n", + (after - before), + ((f64) updates + (f64) tm->double_wheel.current_tick) / (after - + before)); if (pool_elts (tm->test_elts)) fformat (stdout, "Note: %d elements remain in pool\n", @@ -429,74 +626,724 @@ test1_single (tw_timer_test_main_t * tm) /* *INDENT-OFF* */ pool_foreach (e, tm->test_elts, ({ - fformat(stdout, "[%d] expected to expire %d\n", - e - tm->test_elts, - e->expected_to_expire); + fformat (stdout, "[%d] expected to expire %d\n", + e - tm->test_elts, + e->expected_to_expire); })); /* *INDENT-ON* */ - fformat (stdout, - "final wheel time %d, fast index %d\n", - tm->single_wheel.current_tick, - tm->single_wheel.current_index[TW_TIMER_RING_FAST]); - pool_free (tm->test_elts); - tw_timer_wheel_free_2t_1w_2048sl (&tm->single_wheel); + tw_timer_wheel_free_16t_2w_512sl (&tm->double_wheel); return 0; } static clib_error_t * -test1_double (tw_timer_test_main_t * tm) +test2_triple (tw_timer_test_main_t * tm) { - u32 i; + u32 i, j; tw_timer_test_elt_t *e; - u32 offset; + u32 initial_wheel_offset = 0; + u32 expiration_time; + u32 max_expiration_time = 0; + u32 *deleted_indices = 0; + u32 adds = 0, deletes = 0; + f64 before, after; - tw_timer_wheel_init_16t_2w_512sl (&tm->double_wheel, - expired_timer_double_callback, - 1.0 /* timer interval */ ); + clib_time_init (&tm->clib_time); - /* - * Prime offset, to make sure that the wheel starts in a - * non-trivial position - */ - offset = 227989; + tw_timer_wheel_init_4t_3w_256sl (&tm->triple_wheel, + expired_timer_triple_callback, + 1.0 /* timer interval */ , ~0); - run_double_wheel (&tm->double_wheel, offset); - fformat (stdout, "initial wheel time %d, fast index %d\n", - tm->double_wheel.current_tick, - tm->double_wheel.current_index[TW_TIMER_RING_FAST]); + /* Prime offset */ + initial_wheel_offset = 75700; + run_triple_wheel (&tm->triple_wheel, initial_wheel_offset); + + fformat (stdout, + "initial wheel time %d, fi %d si %d gi %d\n", + tm->triple_wheel.current_tick, + tm->triple_wheel.current_index[TW_TIMER_RING_FAST], + tm->triple_wheel.current_index[TW_TIMER_RING_SLOW], + tm->triple_wheel.current_index[TW_TIMER_RING_GLACIER]); + + initial_wheel_offset = tm->triple_wheel.current_tick; + + fformat (stdout, + "test %d timers, %d iter, %d ticks per iter, 0x%llx seed\n", + tm->ntimers, tm->niter, tm->ticks_per_iter, tm->seed); + + before = clib_time_now (&tm->clib_time); + /* Prime the pump */ for (i = 0; i < tm->ntimers; i++) { pool_get (tm->test_elts, e); - memset (e, 0, sizeof (*e)); - - e->expected_to_expire = i + offset + 1; - e->stop_timer_handle = tw_timer_start_16t_2w_512sl - (&tm->double_wheel, e - tm->test_elts, 14 /* timer id */ , - i + 1); - } - run_double_wheel (&tm->double_wheel, tm->ntimers + 3); + clib_memset (e, 0, sizeof (*e)); - if (pool_elts (tm->test_elts)) - fformat (stdout, "Note: %d elements remain in pool\n", - pool_elts (tm->test_elts)); + do + { + expiration_time = random_u64 (&tm->seed) & ((1 << 17) - 1); + } + while (expiration_time == 0); - /* *INDENT-OFF* */ - pool_foreach (e, tm->test_elts, - ({ - fformat(stdout, "[%d] expected to expire %d\n", - e - tm->test_elts, - e->expected_to_expire); - })); - /* *INDENT-ON* */ + if (expiration_time > max_expiration_time) + max_expiration_time = expiration_time; - fformat (stdout, - "final wheel time %d, fast index %d\n", - tm->double_wheel.current_tick, - tm->double_wheel.current_index[TW_TIMER_RING_FAST]); + e->expected_to_expire = expiration_time + initial_wheel_offset; + + e->stop_timer_handle = + tw_timer_start_4t_3w_256sl (&tm->triple_wheel, e - tm->test_elts, + 3 /* timer id */ , + expiration_time); + } + + adds += i; + + for (i = 0; i < tm->niter; i++) + { + run_triple_wheel (&tm->triple_wheel, tm->ticks_per_iter); + + j = 0; + vec_reset_length (deleted_indices); + /* *INDENT-OFF* */ + pool_foreach (e, tm->test_elts, + ({ + tw_timer_stop_4t_3w_256sl (&tm->triple_wheel, e->stop_timer_handle); + vec_add1 (deleted_indices, e - tm->test_elts); + if (++j >= tm->ntimers / 4) + goto del_and_re_add; + })); + /* *INDENT-ON* */ + + del_and_re_add: + for (j = 0; j < vec_len (deleted_indices); j++) + pool_put_index (tm->test_elts, deleted_indices[j]); + + deletes += j; + + for (j = 0; j < tm->ntimers / 4; j++) + { + pool_get (tm->test_elts, e); + clib_memset (e, 0, sizeof (*e)); + + do + { + expiration_time = random_u64 (&tm->seed) & ((1 << 17) - 1); + } + while (expiration_time == 0); + + if (expiration_time > max_expiration_time) + max_expiration_time = expiration_time; + + e->expected_to_expire = expiration_time + + tm->triple_wheel.current_tick; + + e->stop_timer_handle = tw_timer_start_4t_3w_256sl + (&tm->triple_wheel, e - tm->test_elts, 3 /* timer id */ , + expiration_time); + } + adds += j; + } + + vec_free (deleted_indices); + + run_triple_wheel (&tm->triple_wheel, max_expiration_time + 1); + + after = clib_time_now (&tm->clib_time); + + fformat (stdout, "%d adds, %d deletes, %d ticks\n", adds, deletes, + tm->triple_wheel.current_tick); + fformat (stdout, "test ran %.2f seconds, %.2f ops/second\n", + (after - before), + ((f64) adds + (f64) deletes + + (f64) tm->triple_wheel.current_tick) / (after - before)); + + if (pool_elts (tm->test_elts)) + fformat (stdout, "Note: %d elements remain in pool\n", + pool_elts (tm->test_elts)); + + /* *INDENT-OFF* */ + pool_foreach (e, tm->test_elts, + ({ + fformat (stdout, "[%d] expected to expire %d\n", + e - tm->test_elts, + e->expected_to_expire); + })); + /* *INDENT-ON* */ + + pool_free (tm->test_elts); + tw_timer_wheel_free_4t_3w_256sl (&tm->triple_wheel); + return 0; +} + +static clib_error_t * +test2_triple_ov (tw_timer_test_main_t * tm) +{ + u32 i, j; + tw_timer_test_elt_t *e; + u32 initial_wheel_offset = 0; + u32 expiration_time; + u32 max_expiration_time = 0; + u32 *deleted_indices = 0; + u32 adds = 0, deletes = 0; + f64 before, after; + + clib_time_init (&tm->clib_time); + + tw_timer_wheel_init_1t_3w_1024sl_ov (&tm->triple_ov_wheel, + expired_timer_triple_ov_callback, + 1.0 /* timer interval */ , ~0); + + + /* Prime offset */ + initial_wheel_offset = 75700; + run_triple_ov_wheel (&tm->triple_ov_wheel, initial_wheel_offset); + + fformat (stdout, + "initial wheel time %d, fi %d si %d gi %d\n", + tm->triple_ov_wheel.current_tick, + tm->triple_ov_wheel.current_index[TW_TIMER_RING_FAST], + tm->triple_ov_wheel.current_index[TW_TIMER_RING_SLOW], + tm->triple_ov_wheel.current_index[TW_TIMER_RING_GLACIER]); + + initial_wheel_offset = tm->triple_ov_wheel.current_tick; + + fformat (stdout, + "test %d timers, %d iter, %d ticks per iter, 0x%llx seed\n", + tm->ntimers, tm->niter, tm->ticks_per_iter, tm->seed); + + before = clib_time_now (&tm->clib_time); + + /* Prime the pump */ + for (i = 0; i < tm->ntimers; i++) + { + pool_get (tm->test_elts, e); + clib_memset (e, 0, sizeof (*e)); + + do + { + expiration_time = random_u64 (&tm->seed) & ((1 << 17) - 1); + } + while (expiration_time == 0); + + if (expiration_time > max_expiration_time) + max_expiration_time = expiration_time; + + e->expected_to_expire = expiration_time + initial_wheel_offset; + + e->stop_timer_handle = + tw_timer_start_1t_3w_1024sl_ov (&tm->triple_ov_wheel, + e - tm->test_elts, 0 /* timer id */ , + expiration_time); + } + + adds += i; + + for (i = 0; i < tm->niter; i++) + { + run_triple_ov_wheel (&tm->triple_ov_wheel, tm->ticks_per_iter); + + j = 0; + vec_reset_length (deleted_indices); + /* *INDENT-OFF* */ + pool_foreach (e, tm->test_elts, + ({ + tw_timer_stop_1t_3w_1024sl_ov (&tm->triple_ov_wheel, + e->stop_timer_handle); + vec_add1 (deleted_indices, e - tm->test_elts); + if (++j >= tm->ntimers / 4) + goto del_and_re_add; + })); + /* *INDENT-ON* */ + + del_and_re_add: + for (j = 0; j < vec_len (deleted_indices); j++) + pool_put_index (tm->test_elts, deleted_indices[j]); + + deletes += j; + + for (j = 0; j < tm->ntimers / 4; j++) + { + pool_get (tm->test_elts, e); + clib_memset (e, 0, sizeof (*e)); + + do + { + expiration_time = random_u64 (&tm->seed) & ((1 << 17) - 1); + } + while (expiration_time == 0); + + if (expiration_time > max_expiration_time) + max_expiration_time = expiration_time; + + e->expected_to_expire = expiration_time + + tm->triple_ov_wheel.current_tick; + + e->stop_timer_handle = tw_timer_start_1t_3w_1024sl_ov + (&tm->triple_ov_wheel, e - tm->test_elts, 0 /* timer id */ , + expiration_time); + } + adds += j; + } + + vec_free (deleted_indices); + + run_triple_ov_wheel (&tm->triple_ov_wheel, max_expiration_time + 1); + + after = clib_time_now (&tm->clib_time); + + fformat (stdout, "%d adds, %d deletes, %d ticks\n", adds, deletes, + tm->triple_ov_wheel.current_tick); + fformat (stdout, "test ran %.2f seconds, %.2f ops/second\n", + (after - before), + ((f64) adds + (f64) deletes + + (f64) tm->triple_ov_wheel.current_tick) / (after - before)); + + if (pool_elts (tm->test_elts)) + fformat (stdout, "Note: %d elements remain in pool\n", + pool_elts (tm->test_elts)); + + /* *INDENT-OFF* */ + pool_foreach (e, tm->test_elts, + ({ + TWT (tw_timer) * t; + + fformat (stdout, "[%d] expected to expire %d\n", + e - tm->test_elts, + e->expected_to_expire); + t = pool_elt_at_index (tm->triple_ov_wheel.timers, e->stop_timer_handle); + fformat (stdout, " expiration_time %lld\n", t->expiration_time); + })); + /* *INDENT-ON* */ + + pool_free (tm->test_elts); + tw_timer_wheel_free_1t_3w_1024sl_ov (&tm->triple_ov_wheel); + return 0; +} + +static clib_error_t * +test1_single (tw_timer_test_main_t * tm) +{ + u32 i; + tw_timer_test_elt_t *e; + u32 offset; + + tw_timer_wheel_init_2t_1w_2048sl (&tm->single_wheel, + expired_timer_single_callback, + 1.0 /* timer interval */ , ~0); + + /* + * Prime offset, to make sure that the wheel starts in a + * non-trivial position + */ + offset = 123; + + run_single_wheel (&tm->single_wheel, offset); + + fformat (stdout, "initial wheel time %d, fast index %d\n", + tm->single_wheel.current_tick, + tm->single_wheel.current_index[TW_TIMER_RING_FAST]); + + offset = tm->single_wheel.current_tick; + + for (i = 0; i < tm->ntimers; i++) + { + u32 expected_to_expire; + u32 timer_arg; + + timer_arg = 1 + i; + timer_arg &= 2047; + if (timer_arg == 0) + timer_arg = 1; + + expected_to_expire = timer_arg + tm->single_wheel.current_tick; + + pool_get (tm->test_elts, e); + clib_memset (e, 0, sizeof (*e)); + e->expected_to_expire = expected_to_expire; + e->stop_timer_handle = tw_timer_start_2t_1w_2048sl + (&tm->single_wheel, e - tm->test_elts, 1 /* timer id */ , + timer_arg); + } + run_single_wheel (&tm->single_wheel, tm->ntimers + 3); + + if (pool_elts (tm->test_elts)) + fformat (stdout, "Note: %d elements remain in pool\n", + pool_elts (tm->test_elts)); + + /* *INDENT-OFF* */ + pool_foreach (e, tm->test_elts, + ({ + fformat(stdout, "[%d] expected to expire %d\n", + e - tm->test_elts, + e->expected_to_expire); + })); + /* *INDENT-ON* */ + + fformat (stdout, + "final wheel time %d, fast index %d\n", + tm->single_wheel.current_tick, + tm->single_wheel.current_index[TW_TIMER_RING_FAST]); + + pool_free (tm->test_elts); + tw_timer_wheel_free_2t_1w_2048sl (&tm->single_wheel); + return 0; +} + +static clib_error_t * +test1_double (tw_timer_test_main_t * tm) +{ + u32 i; + tw_timer_test_elt_t *e; + u32 offset; + + tw_timer_wheel_init_16t_2w_512sl (&tm->double_wheel, + expired_timer_double_callback, + 1.0 /* timer interval */ , ~0); + + /* + * Prime offset, to make sure that the wheel starts in a + * non-trivial position + */ + offset = 227989; + + run_double_wheel (&tm->double_wheel, offset); + + fformat (stdout, "initial wheel time %d, fast index %d\n", + tm->double_wheel.current_tick, + tm->double_wheel.current_index[TW_TIMER_RING_FAST]); + + for (i = 0; i < tm->ntimers; i++) + { + pool_get (tm->test_elts, e); + clib_memset (e, 0, sizeof (*e)); + + e->expected_to_expire = i + tm->double_wheel.current_tick + 1; + e->stop_timer_handle = tw_timer_start_16t_2w_512sl + (&tm->double_wheel, e - tm->test_elts, 14 /* timer id */ , + i + 1); + } + run_double_wheel (&tm->double_wheel, tm->ntimers + 3); + + if (pool_elts (tm->test_elts)) + fformat (stdout, "Note: %d elements remain in pool\n", + pool_elts (tm->test_elts)); + + /* *INDENT-OFF* */ + pool_foreach (e, tm->test_elts, + ({ + fformat(stdout, "[%d] expected to expire %d\n", + e - tm->test_elts, + e->expected_to_expire); + })); + /* *INDENT-ON* */ + + fformat (stdout, + "final wheel time %d, fast index %d\n", + tm->double_wheel.current_tick, + tm->double_wheel.current_index[TW_TIMER_RING_FAST]); + + pool_free (tm->test_elts); + tw_timer_wheel_free_16t_2w_512sl (&tm->double_wheel); + return 0; +} + +static clib_error_t * +test1_two_timer_double (tw_timer_test_main_t * tm) +{ + u32 i; + tw_timer_test_elt_t *e; + u32 offset; + + tw_timer_wheel_init_2t_2w_512sl (&tm->two_timer_double_wheel, + expired_timer_two_timer_double_callback, + 1.0 /* timer interval */ , ~0); + + /* + * Prime offset, to make sure that the wheel starts in a + * non-trivial position + */ + offset = 2745; + + run_two_timer_double_wheel (&tm->two_timer_double_wheel, offset); + + fformat (stdout, "initial wheel time %d, fast index %d\n", + tm->two_timer_double_wheel.current_tick, + tm->two_timer_double_wheel.current_index[TW_TIMER_RING_FAST]); + + for (i = 0; i < tm->ntimers; i++) + { + pool_get (tm->test_elts, e); + clib_memset (e, 0, sizeof (*e)); + + e->expected_to_expire = i + tm->two_timer_double_wheel.current_tick + 1; + e->stop_timer_handle = tw_timer_start_2t_2w_512sl + (&tm->two_timer_double_wheel, e - tm->test_elts, 1 /* timer id */ , + i + 1); + } + run_two_timer_double_wheel (&tm->two_timer_double_wheel, tm->ntimers + 3); + + if (pool_elts (tm->test_elts)) + fformat (stdout, "Note: %d elements remain in pool\n", + pool_elts (tm->test_elts)); + + /* *INDENT-OFF* */ + pool_foreach (e, tm->test_elts, + ({ + fformat(stdout, "[%d] expected to expire %d\n", + e - tm->test_elts, + e->expected_to_expire); + })); + /* *INDENT-ON* */ + + fformat (stdout, + "final wheel time %d, fast index %d\n", + tm->two_timer_double_wheel.current_tick, + tm->two_timer_double_wheel.current_index[TW_TIMER_RING_FAST]); + + pool_free (tm->test_elts); + tw_timer_wheel_free_2t_2w_512sl (&tm->two_timer_double_wheel); + return 0; +} + +static clib_error_t * +test3_triple_double (tw_timer_test_main_t * tm) +{ + tw_timer_test_elt_t *e; + u32 initial_wheel_offset = 0; + u32 expiration_time; + u32 max_expiration_time = 0; + u32 adds = 0, deletes = 0; + f64 before, after; + + clib_time_init (&tm->clib_time); + + tw_timer_wheel_init_4t_3w_256sl (&tm->triple_wheel, + expired_timer_triple_callback, + 1.0 /* timer interval */ , ~0); + + initial_wheel_offset = 0; + run_triple_wheel (&tm->triple_wheel, initial_wheel_offset); + + fformat (stdout, + "initial wheel time %d, fi %d si %d gi %d\n", + tm->triple_wheel.current_tick, + tm->triple_wheel.current_index[TW_TIMER_RING_FAST], + tm->triple_wheel.current_index[TW_TIMER_RING_SLOW], + tm->triple_wheel.current_index[TW_TIMER_RING_GLACIER]); + + initial_wheel_offset = tm->triple_wheel.current_tick; + + fformat (stdout, "Create a timer which expires at wheel-time (1, 0, 0)\n"); + + before = clib_time_now (&tm->clib_time); + + /* Prime the pump */ + pool_get (tm->test_elts, e); + clib_memset (e, 0, sizeof (*e)); + + /* 1 glacier ring tick from now */ + expiration_time = TW_SLOTS_PER_RING * TW_SLOTS_PER_RING; + e->expected_to_expire = expiration_time + initial_wheel_offset; + max_expiration_time = expiration_time; + + e->stop_timer_handle = + tw_timer_start_4t_3w_256sl (&tm->triple_wheel, e - tm->test_elts, + 3 /* timer id */ , + expiration_time); + + run_triple_wheel (&tm->triple_wheel, max_expiration_time + 1); + + after = clib_time_now (&tm->clib_time); + + fformat (stdout, "%d adds, %d deletes, %d ticks\n", adds, deletes, + tm->triple_wheel.current_tick); + fformat (stdout, "test ran %.2f seconds, %.2f ops/second\n", + (after - before), + ((f64) adds + (f64) deletes + + (f64) tm->triple_wheel.current_tick) / (after - before)); + + if (pool_elts (tm->test_elts)) + fformat (stdout, "Note: %d elements remain in pool\n", + pool_elts (tm->test_elts)); + + /* *INDENT-OFF* */ + pool_foreach (e, tm->test_elts, + ({ + fformat (stdout, "[%d] expected to expire %d\n", + e - tm->test_elts, + e->expected_to_expire); + })); + /* *INDENT-ON* */ + + pool_free (tm->test_elts); + tw_timer_wheel_free_4t_3w_256sl (&tm->triple_wheel); + return 0; +} + +static clib_error_t * +test4_double_double (tw_timer_test_main_t * tm) +{ + u32 i; + tw_timer_test_elt_t *e; + u32 initial_wheel_offset; + u32 expiration_time; + u32 max_expiration_time = 0; + u32 *deleted_indices = 0; + u32 adds = 0, deletes = 0; + f64 before, after; + + clib_time_init (&tm->clib_time); + + tw_timer_wheel_init_16t_2w_512sl (&tm->double_wheel, + expired_timer_double_callback, + 1.0 /* timer interval */ , ~0); + /* Prime offset */ + initial_wheel_offset = 0; + + run_double_wheel (&tm->double_wheel, initial_wheel_offset); + + fformat (stdout, "initial wheel time %d, fast index %d slow index %d\n", + tm->double_wheel.current_tick, + tm->double_wheel.current_index[TW_TIMER_RING_FAST], + tm->double_wheel.current_index[TW_TIMER_RING_SLOW]); + + initial_wheel_offset = tm->double_wheel.current_tick; + + fformat (stdout, "test timer which expires at 512 ticks\n"); + + before = clib_time_now (&tm->clib_time); + + /* Prime the pump */ + for (i = 0; i < tm->ntimers; i++) + { + pool_get (tm->test_elts, e); + clib_memset (e, 0, sizeof (*e)); + + expiration_time = 512; + + if (expiration_time > max_expiration_time) + max_expiration_time = expiration_time; + + e->expected_to_expire = expiration_time + initial_wheel_offset; + e->stop_timer_handle = + tw_timer_start_16t_2w_512sl (&tm->double_wheel, e - tm->test_elts, + 14 /* timer id */ , + expiration_time); + } + + adds = 1; + + vec_free (deleted_indices); + + run_double_wheel (&tm->double_wheel, max_expiration_time + 1); + + after = clib_time_now (&tm->clib_time); + + fformat (stdout, "%d adds, %d deletes, %d ticks\n", adds, deletes, + tm->double_wheel.current_tick); + fformat (stdout, "test ran %.2f seconds, %.2f ops/second\n", + (after - before), + ((f64) adds + (f64) deletes + + (f64) tm->double_wheel.current_tick) / (after - before)); + + if (pool_elts (tm->test_elts)) + fformat (stdout, "Note: %d elements remain in pool\n", + pool_elts (tm->test_elts)); + + /* *INDENT-OFF* */ + pool_foreach (e, tm->test_elts, + ({ + fformat (stdout, "[%d] expected to expire %d\n", + e - tm->test_elts, + e->expected_to_expire); + })); + /* *INDENT-ON* */ + + pool_free (tm->test_elts); + tw_timer_wheel_free_16t_2w_512sl (&tm->double_wheel); + return 0; +} + +static clib_error_t * +test5_double (tw_timer_test_main_t * tm) +{ + u32 i; + tw_timer_test_elt_t *e; + u32 initial_wheel_offset; + u32 expiration_time; + u32 max_expiration_time = 0; + u32 adds = 0, deletes = 0; + f64 before, after; + + clib_time_init (&tm->clib_time); + + tw_timer_wheel_init_16t_2w_512sl (&tm->double_wheel, + expired_timer_double_callback, + 1.0 /* timer interval */ , ~0); + + /* Prime offset */ + initial_wheel_offset = 7567; + + run_double_wheel (&tm->double_wheel, initial_wheel_offset); + + fformat (stdout, "initial wheel time %d, fast index %d slow index %d\n", + tm->double_wheel.current_tick, + tm->double_wheel.current_index[TW_TIMER_RING_FAST], + tm->double_wheel.current_index[TW_TIMER_RING_SLOW]); + + initial_wheel_offset = tm->double_wheel.current_tick; + + fformat (stdout, + "test %d timers, %d iter, %d ticks per iter, 0x%llx seed\n", + tm->ntimers, tm->niter, tm->ticks_per_iter, tm->seed); + + before = clib_time_now (&tm->clib_time); + + /* Prime the pump */ + for (i = 0; i < tm->ntimers; i++) + { + pool_get (tm->test_elts, e); + clib_memset (e, 0, sizeof (*e)); + + expiration_time = i + 1; + + if (expiration_time > max_expiration_time) + max_expiration_time = expiration_time; + + e->expected_to_expire = expiration_time + initial_wheel_offset; + e->stop_timer_handle = + tw_timer_start_16t_2w_512sl (&tm->double_wheel, e - tm->test_elts, + 14 /* timer id */ , + expiration_time); + } + + adds += i; + + run_double_wheel (&tm->double_wheel, max_expiration_time + 1); + + after = clib_time_now (&tm->clib_time); + + fformat (stdout, "%d adds, %d deletes, %d ticks\n", adds, deletes, + tm->double_wheel.current_tick); + fformat (stdout, "test ran %.2f seconds, %.2f ops/second\n", + (after - before), + ((f64) adds + (f64) deletes + + (f64) tm->double_wheel.current_tick) / (after - before)); + + if (pool_elts (tm->test_elts)) + fformat (stdout, "Note: %d elements remain in pool\n", + pool_elts (tm->test_elts)); + + /* *INDENT-OFF* */ + pool_foreach (e, tm->test_elts, + ({ + fformat (stdout, "[%d] expected to expire %d\n", + e - tm->test_elts, + e->expected_to_expire); + })); + /* *INDENT-ON* */ pool_free (tm->test_elts); tw_timer_wheel_free_16t_2w_512sl (&tm->double_wheel); @@ -507,25 +1354,39 @@ static clib_error_t * timer_test_command_fn (tw_timer_test_main_t * tm, unformat_input_t * input) { - int is_test1 = 0; + int is_test1 = 0, is_updates = 0; int num_wheels = 1; int is_test2 = 0; + int is_test3 = 0; + int is_test4 = 0; + int is_test5 = 0; + int overflow = 0; - memset (tm, 0, sizeof (*tm)); + clib_memset (tm, 0, sizeof (*tm)); /* Default values */ tm->ntimers = 100000; - tm->seed = 0xDEADDABE; + tm->seed = 0xDEADDABEB00BFACE; tm->niter = 1000; tm->ticks_per_iter = 727; while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT) { - if (unformat (input, "seed %d", &tm->seed)) + if (unformat (input, "seed %lld", &tm->seed)) ; else if (unformat (input, "test1")) is_test1 = 1; else if (unformat (input, "test2")) is_test2 = 1; + else if (unformat (input, "overflow")) + overflow = 1; + else if (unformat (input, "lebron")) + is_test3 = 1; + else if (unformat (input, "wilt")) + is_test4 = 1; + else if (unformat (input, "linear")) + is_test5 = 1; + else if (unformat (input, "updates")) + is_updates = 1; else if (unformat (input, "wheels %d", &num_wheels)) ; else if (unformat (input, "ntimers %d", &tm->ntimers)) @@ -534,12 +1395,14 @@ timer_test_command_fn (tw_timer_test_main_t * tm, unformat_input_t * input) ; else if (unformat (input, "ticks_per_iter %d", &tm->ticks_per_iter)) ; + else + break; } - if (is_test1 + is_test2 == 0) + if (is_test1 + is_test2 + is_test3 + is_test4 + is_test5 == 0) return clib_error_return (0, "No test specified [test1..n]"); - if (num_wheels < 1 || num_wheels > 2) + if (num_wheels < 1 || num_wheels > 3) return clib_error_return (0, "unsupported... 1 or 2 wheels only"); if (is_test1) @@ -547,15 +1410,37 @@ timer_test_command_fn (tw_timer_test_main_t * tm, unformat_input_t * input) if (num_wheels == 1) return test1_single (tm); else - return test1_double (tm); + { + (void) test1_double (tm); + return test1_two_timer_double (tm); + } } if (is_test2) { if (num_wheels == 1) return test2_single (tm); - else - return test2_double (tm); + else if (num_wheels == 2) + if (is_updates) + return test2_double_updates (tm); + else + return test2_double (tm); + else if (num_wheels == 3) + { + if (overflow == 0) + return test2_triple (tm); + else + return test2_triple_ov (tm); + } } + if (is_test3) + return test3_triple_double (tm); + + if (is_test4) + return test4_double_double (tm); + + if (is_test5) + return test5_double (tm); + /* NOTREACHED */ return 0; } @@ -583,6 +1468,25 @@ main (int argc, char *argv[]) } #endif /* CLIB_UNIX */ +/* For debugging... */ +int +pifi (void *p, u32 index) +{ + return pool_is_free_index (p, index); +} + +u32 +vl (void *p) +{ + return vec_len (p); +} + +uword +pe (void *v) +{ + return (pool_elts (v)); +} + /* * fd.io coding-style-patch-verification: ON *