From 8e8f98c9d46788438bd176f7c2bfde0a5837cad9 Mon Sep 17 00:00:00 2001 From: Dave Barach Date: Fri, 3 Feb 2017 11:58:53 -0500 Subject: Wheel-timer infra Change-Id: I5499dd6b768425a56936afae50bd578620c83d30 Signed-off-by: Dave Barach --- src/vppinfra/test_tw_timer.c | 592 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 592 insertions(+) create mode 100644 src/vppinfra/test_tw_timer.c (limited to 'src/vppinfra/test_tw_timer.c') diff --git a/src/vppinfra/test_tw_timer.c b/src/vppinfra/test_tw_timer.c new file mode 100644 index 00000000..a0287b89 --- /dev/null +++ b/src/vppinfra/test_tw_timer.c @@ -0,0 +1,592 @@ +#include +#include +#include +#include +#include + +typedef struct +{ + /** Handle returned from tw_start_timer */ + u32 stop_timer_handle; + + /** Test item should expire at this clock tick */ + u32 expected_to_expire; +} tw_timer_test_elt_t; + +typedef struct +{ + /** Pool of test objects */ + tw_timer_test_elt_t *test_elts; + + /** The single-wheel */ + tw_timer_wheel_2t_1w_2048sl_t single_wheel; + + /** The double-wheel */ + tw_timer_wheel_16t_2w_512sl_t double_wheel; + + /** random number seed */ + u32 seed; + + /** number of timers */ + u32 ntimers; + + /** number of "churn" iterations */ + u32 niter; + + /** number of clock ticks per churn iteration */ + u32 ticks_per_iter; + + /** cpu timer */ + clib_time_t clib_time; +} tw_timer_test_main_t; + +tw_timer_test_main_t tw_timer_test_main; + +static void +run_single_wheel (tw_timer_wheel_2t_1w_2048sl_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_1w_2048sl (tw, now); + now += 1.01; + } +} + +static void +run_double_wheel (tw_timer_wheel_16t_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_16t_2w_512sl (tw, now); + now += 1.01; + } +} + +static void +expired_timer_single_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->single_wheel.current_tick) + { + fformat (stdout, "[%d] expired at %d not %d\n", + e - tm->test_elts, tm->single_wheel.current_tick, + e->expected_to_expire); + } + pool_put (tm->test_elts, e); + } +} + +static void +expired_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] & 0x0FFFFFFF; + timer_id = expired_timers[i] >> 28; + + ASSERT (timer_id == 14); + + e = pool_elt_at_index (tm->test_elts, pool_index); + + if (e->expected_to_expire != tm->double_wheel.current_tick) + { + fformat (stdout, "[%d] expired at %d not %d\n", + e - tm->test_elts, tm->double_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; + 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_2t_1w_2048sl (&tm->single_wheel, + expired_timer_single_callback, + 1.0 /* timer interval */ ); + + /* 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", + 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)); + + do + { + expiration_time = random_u32 (&tm->seed) & (2047); + } + 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_2t_1w_2048sl (&tm->single_wheel, e - tm->test_elts, + 1 /* timer id */ , + expiration_time); + } + + adds += i; + + for (i = 0; i < tm->niter; i++) + { + run_single_wheel (&tm->single_wheel, tm->ticks_per_iter); + + j = 0; + vec_reset_length (deleted_indices); + /* *INDENT-OFF* */ + pool_foreach (e, tm->test_elts, + ({ + tw_timer_stop_2t_1w_2048sl (&tm->single_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); + memset (e, 0, sizeof (*e)); + + do + { + expiration_time = random_u32 (&tm->seed) & (2047); + } + while (expiration_time == 0); + + if (expiration_time > max_expiration_time) + max_expiration_time = expiration_time; + + e->expected_to_expire = + expiration_time + tm->single_wheel.current_tick; + e->stop_timer_handle = tw_timer_start_2t_1w_2048sl + (&tm->single_wheel, e - tm->test_elts, 1 /* timer id */ , + expiration_time); + } + adds += j; + } + + vec_free (deleted_indices); + + run_single_wheel (&tm->single_wheel, max_expiration_time + 1); + + after = clib_time_now (&tm->clib_time); + + fformat (stdout, "%d adds, %d deletes, %d ticks\n", adds, deletes, + tm->single_wheel.current_tick); + fformat (stdout, "test ran %.2f seconds, %.2f ops/second\n", + (after - before), + ((f64) adds + (f64) deletes + + (f64) tm->single_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_2t_1w_2048sl (&tm->single_wheel); + return 0; +} + +static clib_error_t * +test2_double (tw_timer_test_main_t * tm) +{ + u32 i, j; + 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 */ ); + + /* Prime offset */ + initial_wheel_offset = 757; + + run_double_wheel (&tm->double_wheel, initial_wheel_offset); + + fformat (stdout, "test %d timers, %d iter, %d ticks per iter, 0x%x 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)); + + do + { + expiration_time = random_u32 (&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_16t_2w_512sl (&tm->double_wheel, e - tm->test_elts, + 14 /* timer id */ , + expiration_time); + } + + adds += i; + + for (i = 0; i < tm->niter; i++) + { + run_double_wheel (&tm->double_wheel, tm->ticks_per_iter); + + j = 0; + vec_reset_length (deleted_indices); + /* *INDENT-OFF* */ + pool_foreach (e, tm->test_elts, + ({ + tw_timer_stop_16t_2w_512sl (&tm->double_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); + memset (e, 0, sizeof (*e)); + + do + { + expiration_time = random_u32 (&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->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); + } + adds += j; + } + + 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 * +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 */ ); + + /* + * 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]); + + 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 + offset; + + 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); + } + 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 */ ); + + /* + * 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); + 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); + + 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 * +timer_test_command_fn (tw_timer_test_main_t * tm, unformat_input_t * input) +{ + + int is_test1 = 0; + int num_wheels = 1; + int is_test2 = 0; + + memset (tm, 0, sizeof (*tm)); + /* Default values */ + tm->ntimers = 100000; + tm->seed = 0xDEADDABE; + tm->niter = 1000; + tm->ticks_per_iter = 727; + + while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT) + { + if (unformat (input, "seed %d", &tm->seed)) + ; + else if (unformat (input, "test1")) + is_test1 = 1; + else if (unformat (input, "test2")) + is_test2 = 1; + else if (unformat (input, "wheels %d", &num_wheels)) + ; + else if (unformat (input, "ntimers %d", &tm->ntimers)) + ; + else if (unformat (input, "niter %d", &tm->niter)) + ; + else if (unformat (input, "ticks_per_iter %d", &tm->ticks_per_iter)) + ; + } + + if (is_test1 + is_test2 == 0) + return clib_error_return (0, "No test specified [test1..n]"); + + if (num_wheels < 1 || num_wheels > 2) + return clib_error_return (0, "unsupported... 1 or 2 wheels only"); + + if (is_test1) + { + if (num_wheels == 1) + return test1_single (tm); + else + return test1_double (tm); + } + if (is_test2) + { + if (num_wheels == 1) + return test2_single (tm); + else + return test2_double (tm); + } + /* NOTREACHED */ + return 0; +} + +#ifdef CLIB_UNIX +int +main (int argc, char *argv[]) +{ + unformat_input_t i; + clib_error_t *error; + tw_timer_test_main_t *tm = &tw_timer_test_main; + + clib_mem_init (0, 3ULL << 30); + + unformat_init_command_line (&i, argv); + error = timer_test_command_fn (tm, &i); + unformat_free (&i); + + if (error) + { + clib_error_report (error); + return 1; + } + return 0; +} +#endif /* CLIB_UNIX */ + +/* + * fd.io coding-style-patch-verification: ON + * + * Local Variables: + * eval: (c-set-style "gnu") + * End: + */ -- cgit 1.2.3-korg From 816f437d943688f67d61fb6b9708eff59432b2ee Mon Sep 17 00:00:00 2001 From: Filip Tehlar Date: Wed, 26 Apr 2017 16:09:06 +0200 Subject: Fix vnet unit tests Change-Id: Ibe55e4399c6b78d83268d7c49ed498cab7bfdb43 Signed-off-by: Filip Tehlar --- build-data/packages/vpp.mk | 4 +++ src/tests/vnet/lisp-cp/test_cp_serdes.c | 51 ++++++++++++++++++++++++++++++-- src/tests/vnet/lisp-cp/test_lisp_types.c | 45 +++++++++++++++++++++------- src/tests/vnet/lisp-gpe/test.c | 18 ----------- src/vlib/buffer.h | 12 ++++++++ src/vnet.am | 13 -------- src/vnet/lisp-cp/control.c | 14 ++++----- src/vnet/lisp-cp/control.h | 9 ++++++ src/vnet/lisp-cp/lisp_msg_serdes.c | 8 +++++ src/vnet/lisp-cp/lisp_types.c | 31 ++++++++++--------- src/vpp.am | 1 - src/vpp/api/test_client.c | 11 ------- src/vppinfra/test_tw_timer.c | 8 ++--- 13 files changed, 142 insertions(+), 83 deletions(-) delete mode 100644 src/tests/vnet/lisp-gpe/test.c (limited to 'src/vppinfra/test_tw_timer.c') diff --git a/build-data/packages/vpp.mk b/build-data/packages/vpp.mk index 64eb0d89..1acc59b2 100644 --- a/build-data/packages/vpp.mk +++ b/build-data/packages/vpp.mk @@ -30,3 +30,7 @@ ifeq ($($(PLATFORM)_uses_dpdk_mlx5_pmd),yes) vpp_configure_args += --with-dpdk-mlx5-pmd endif endif + +ifeq ($($(PLATFORM)_enable_tests),yes) +vpp_configure_args += --enable-tests +endif diff --git a/src/tests/vnet/lisp-cp/test_cp_serdes.c b/src/tests/vnet/lisp-cp/test_cp_serdes.c index 0766bee1..8e8c8455 100644 --- a/src/tests/vnet/lisp-cp/test_cp_serdes.c +++ b/src/tests/vnet/lisp-cp/test_cp_serdes.c @@ -21,9 +21,6 @@ #include #include -/* FIXME */ -#include - #define _assert(e) \ error = CLIB_ERROR_ASSERT (e); \ if (error) \ @@ -489,6 +486,53 @@ done: return error; } +static vlib_buffer_t * +create_buffer (u8 * data, u32 data_len) +{ + vlib_buffer_t *b; + + u8 *buf_data = clib_mem_alloc(500); + memset (buf_data, 0, 500); + b = (vlib_buffer_t *)buf_data; + + u8 * p = vlib_buffer_put_uninit (b, data_len); + clib_memcpy (p, data, data_len); + + return b; +} + +static clib_error_t * +test_lisp_parse_map_reply () +{ + clib_error_t * error = 0; + u8 map_reply_data[] = + { + 0x00, 0x00, 0x00, 0x01, /* type; rsvd; mapping count */ + 0x00, 0x00, 0x00, 0x00, + }; + vlib_buffer_t *b = create_buffer (map_reply_data, sizeof (map_reply_data)); + map_records_arg_t *mrecs = parse_map_reply (b); + _assert (0 == mrecs); + clib_mem_free (b); + + u8 map_reply_data2[] = + { + 0x00, 0x00, 0x00, 0x01, /* type; rsvd */ + 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, /* nonce */ + + /* 1. record - incomplete */ + 0x01, 0x02, 0x03, 0x04, /* record TTL */ + 0x01, /* locator count */ + }; + b = create_buffer (map_reply_data2, sizeof (map_reply_data2)); + mrecs = parse_map_reply (b); + _assert (0 == mrecs); +done: + clib_mem_free (b); + return error; +} + static clib_error_t * test_lisp_parse_lcaf () { @@ -610,6 +654,7 @@ done: _(lisp_msg_push_ecm) \ _(lisp_msg_parse) \ _(lisp_msg_parse_mapping_record) \ + _(lisp_parse_map_reply) \ _(lisp_parse_lcaf) \ _(lisp_map_register) diff --git a/src/tests/vnet/lisp-cp/test_lisp_types.c b/src/tests/vnet/lisp-cp/test_lisp_types.c index fa34a3c6..21575015 100644 --- a/src/tests/vnet/lisp-cp/test_lisp_types.c +++ b/src/tests/vnet/lisp-cp/test_lisp_types.c @@ -18,9 +18,6 @@ #include #include -/* FIXME */ -#include - #define _assert(e) \ error = CLIB_ERROR_ASSERT (e); \ if (error) \ @@ -265,7 +262,6 @@ done: } #endif -#if 0 /* uncomment this once VNI is supported */ static clib_error_t * test_write_mac_in_lcaf (void) { clib_error_t * error = 0; @@ -276,13 +272,12 @@ static clib_error_t * test_write_mac_in_lcaf (void) gid_address_t g = { .mac = {0x1, 0x2, 0x3, 0x4, 0x5, 0x6}, - .vni = 0x30, + .vni = 0x01020304, .vni_mask = 0x10, .type = GID_ADDR_MAC, }; u16 len = gid_address_put (b, &g); - _assert (8 == len); u8 expected[] = { @@ -290,20 +285,20 @@ static clib_error_t * test_write_mac_in_lcaf (void) 0x00, /* reserved1 */ 0x00, /* flags */ 0x02, /* LCAF type = Instance ID */ - 0x20, /* IID/VNI mask len */ - 0x00, 0x0a, /* length */ + 0x10, /* IID/IID mask len */ + 0x00, 0x0c, /* length */ 0x01, 0x02, 0x03, 0x04, /* Instance ID / VNI */ - 0x00, 0x06, /* AFI = MAC */ + 0x40, 0x05, /* AFI = MAC */ 0x01, 0x02, 0x03, 0x04, 0x05, 0x06 /* MAC */ - } + }; + _assert (sizeof (expected) == len); _assert (0 == memcmp (expected, b, len)); done: clib_mem_free (b); return error; } -#endif static clib_error_t * test_mac_address_write (void) { @@ -417,6 +412,32 @@ done: return error; } +static clib_error_t * +test_src_dst_deser_bad_afi (void) +{ + clib_error_t * error = 0; + + u8 expected_data[] = + { + 0x40, 0x03, 0x00, 0x00, /* AFI = LCAF, reserved1, flags */ + 0x0c, 0x00, 0x00, 0x14, /* LCAF type = source/dest key, rsvd, length */ + 0x00, 0x00, 0x00, 0x00, /* reserved; source-ML, Dest-ML */ + + 0xde, 0xad, /* AFI = bad value */ + 0x11, 0x22, 0x33, 0x44, + 0x55, 0x66, /* source */ + + 0x40, 0x05, /* AFI = MAC */ + 0x10, 0x21, 0x32, 0x43, + 0x54, 0x65, /* destination */ + }; + + gid_address_t p; + _assert (~0 == gid_address_parse (expected_data, &p)); +done: + return error; +} + static clib_error_t * test_src_dst_serdes (void) { @@ -537,6 +558,8 @@ done: _(mac_address_write) \ _(gid_address_write) \ _(src_dst_serdes) \ + _(write_mac_in_lcaf) \ + _(src_dst_deser_bad_afi) \ _(src_dst_with_vni_serdes) int run_tests (void) diff --git a/src/tests/vnet/lisp-gpe/test.c b/src/tests/vnet/lisp-gpe/test.c deleted file mode 100644 index dde633ae..00000000 --- a/src/tests/vnet/lisp-gpe/test.c +++ /dev/null @@ -1,18 +0,0 @@ -/* - * Copyright (c) 2016 Cisco and/or its affiliates. - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at: - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -int main(int argc, char **argv) { - return 0; -} diff --git a/src/vlib/buffer.h b/src/vlib/buffer.h index 69c8c7cc..18e2437d 100644 --- a/src/vlib/buffer.h +++ b/src/vlib/buffer.h @@ -205,6 +205,18 @@ vlib_buffer_advance (vlib_buffer_t * b, word l) b->current_length -= l; } +/** \brief Check if there is enough space in buffer to advance + + @param b - (vlib_buffer_t *) pointer to the buffer + @param l - (word) size to check + @return - 0 if there is less space than 'l' in buffer +*/ +always_inline u8 +vlib_buffer_has_space (vlib_buffer_t * b, word l) +{ + return b->current_length >= l; +} + /** \brief Reset current header & length to state they were in when packet was received. diff --git a/src/vnet.am b/src/vnet.am index 25b84616..9f3aedba 100644 --- a/src/vnet.am +++ b/src/vnet.am @@ -662,19 +662,6 @@ nobase_include_HEADERS += \ API_FILES += vnet/lisp-gpe/lisp_gpe.api -if ENABLE_TESTS -TESTS += test_test - -test_test_SOURCES = tests/vnet/lisp-gpe/test.c - -test_test_CPPFLAGS = $(AM_CPPFLAGS) -DCLIB_DEBUG - -test_test_LDADD = $(LIBOBJS) - -noinst_PROGRAMS += $(TESTS) -check_PROGRAMS += $(TESTS) -endif - ######################################## # DHCP client ######################################## diff --git a/src/vnet/lisp-cp/control.c b/src/vnet/lisp-cp/control.c index 6408b297..c0093301 100644 --- a/src/vnet/lisp-cp/control.c +++ b/src/vnet/lisp-cp/control.c @@ -44,13 +44,6 @@ typedef struct u8 smr_invoked; } map_request_args_t; -typedef struct -{ - u64 nonce; - u8 is_rloc_probe; - mapping_t *mappings; -} map_records_arg_t; - u8 vnet_lisp_get_map_request_mode (void) { @@ -3485,7 +3478,7 @@ done: vec_free (itr_rlocs); } -static map_records_arg_t * +map_records_arg_t * parse_map_reply (vlib_buffer_t * b) { locator_t probed; @@ -3501,6 +3494,11 @@ parse_map_reply (vlib_buffer_t * b) mrep_hdr = vlib_buffer_get_current (b); a->nonce = MREP_NONCE (mrep_hdr); a->is_rloc_probe = MREP_RLOC_PROBE (mrep_hdr); + if (!vlib_buffer_has_space (b, sizeof (*mrep_hdr))) + { + clib_mem_free (a); + return 0; + } vlib_buffer_pull (b, sizeof (*mrep_hdr)); for (i = 0; i < MREP_REC_COUNT (mrep_hdr); i++) diff --git a/src/vnet/lisp-cp/control.h b/src/vnet/lisp-cp/control.h index eae8a184..cb98eb09 100644 --- a/src/vnet/lisp-cp/control.h +++ b/src/vnet/lisp-cp/control.h @@ -273,6 +273,13 @@ typedef struct u8 key_id; } vnet_lisp_add_del_mapping_args_t; +typedef struct +{ + u64 nonce; + u8 is_rloc_probe; + mapping_t *mappings; +} map_records_arg_t; + int vnet_lisp_map_cache_add_del (vnet_lisp_add_del_mapping_args_t * a, u32 * map_index); @@ -332,6 +339,8 @@ int vnet_lisp_map_register_enable_disable (u8 is_enable); u8 vnet_lisp_map_register_state_get (void); u8 vnet_lisp_rloc_probe_state_get (void); +map_records_arg_t *parse_map_reply (vlib_buffer_t * b); + always_inline mapping_t * lisp_get_petr_mapping (lisp_cp_main_t * lcm) { diff --git a/src/vnet/lisp-cp/lisp_msg_serdes.c b/src/vnet/lisp-cp/lisp_msg_serdes.c index eee1885c..6c0a7219 100644 --- a/src/vnet/lisp-cp/lisp_msg_serdes.c +++ b/src/vnet/lisp-cp/lisp_msg_serdes.c @@ -312,6 +312,8 @@ lisp_msg_parse_loc (vlib_buffer_t * b, locator_t * loc) if (len == ~0) return ~0; + if (!vlib_buffer_has_space (b, sizeof (len))) + return ~0; vlib_buffer_pull (b, len); return len; @@ -326,6 +328,9 @@ lisp_msg_parse_mapping_record (vlib_buffer_t * b, gid_address_t * eid, int i = 0, len = 0, llen = 0; h = vlib_buffer_get_current (b); + if (!vlib_buffer_has_space (b, sizeof (mapping_record_hdr_t))) + return ~0; + vlib_buffer_pull (b, sizeof (mapping_record_hdr_t)); memset (eid, 0, sizeof (*eid)); @@ -333,6 +338,9 @@ lisp_msg_parse_mapping_record (vlib_buffer_t * b, gid_address_t * eid, if (len == ~0) return len; + if (!vlib_buffer_has_space (b, sizeof (len))) + return ~0; + vlib_buffer_pull (b, len); if (GID_ADDR_IP_PREFIX == gid_address_type (eid)) gid_address_ippref_len (eid) = MAP_REC_EID_PLEN (h); diff --git a/src/vnet/lisp-cp/lisp_types.c b/src/vnet/lisp-cp/lisp_types.c index ad3a4bdf..31a80081 100644 --- a/src/vnet/lisp-cp/lisp_types.c +++ b/src/vnet/lisp-cp/lisp_types.c @@ -657,12 +657,19 @@ fid_addr_parse (u8 * p, fid_address_t * a) return ip_address_parse (p, afi, ip_addr); case FID_ADDR_NSH: - ASSERT (0); break; } return ~0; } +#define INC(dst, exp) \ +do { \ + u16 _sum = (exp); \ + if ((u16)~0 == _sum) \ + return ~0; \ + dst += _sum; \ +} while (0); + u16 sd_parse (u8 * p, void *a) { @@ -677,8 +684,8 @@ sd_parse (u8 * p, void *a) sd_hdr = (lcaf_src_dst_hdr_t *) (p + size); size += sizeof (sd_hdr[0]); - size += fid_addr_parse (p + size, src); - size += fid_addr_parse (p + size, dst); + INC (size, fid_addr_parse (p + size, src)); + INC (size, fid_addr_parse (p + size, dst)); if (fid_addr_type (src) == FID_ADDR_IP_PREF) { @@ -704,7 +711,7 @@ try_parse_src_dst_lcaf (u8 * p, gid_address_t * a) if (LCAF_SOURCE_DEST != lcaf_type (&lcaf)) return ~0; - size += sd_parse (p + size, a); + INC (size, sd_parse (p + size, a)); return size; } @@ -724,13 +731,10 @@ vni_parse (u8 * p, void *a) u16 afi = clib_net_to_host_u16 (*((u16 *) (p + size))); if (LISP_AFI_LCAF == afi) { - u16 len = try_parse_src_dst_lcaf (p + size, g); - if ((u16) ~ 0 == len) - return ~0; - size += len; + INC (size, try_parse_src_dst_lcaf (p + size, g)); } else - size += gid_address_parse (p + size, g); + INC (size, gid_address_parse (p + size, g)); return size; } @@ -757,7 +761,7 @@ lcaf_parse (void *offset, gid_address_t * addr) clib_warning ("Unsupported LCAF type: %u", type); return ~0; } - size += (*lcaf_parse_fcts[type]) (offset + size, lcaf); + INC (size, (*lcaf_parse_fcts[type]) (offset + size, lcaf)); return sizeof (u16) + size; } @@ -1419,10 +1423,9 @@ u32 gid_address_parse (u8 * offset, gid_address_t * a) { lisp_afi_e afi; - int len = 0; + u16 len = 0; - if (!a) - return 0; + ASSERT (a); /* NOTE: since gid_address_parse may be called by vni_parse, we can't 0 * the gid address here */ @@ -1458,7 +1461,7 @@ gid_address_parse (u8 * offset, gid_address_t * a) clib_warning ("LISP AFI %d not supported!", afi); return ~0; } - return len; + return (len == (u16) ~ 0) ? ~0 : len; } void diff --git a/src/vpp.am b/src/vpp.am index 8cdc60d9..d8b3e4ec 100644 --- a/src/vpp.am +++ b/src/vpp.am @@ -100,7 +100,6 @@ bin_test_ha_SOURCES = \ bin_test_ha_LDADD = \ libvlibmemoryclient.la \ - libvlibapi.la \ libsvm.la \ libvppinfra.la \ -lpthread -lm -lrt diff --git a/src/vpp/api/test_client.c b/src/vpp/api/test_client.c index 551bdab9..231b3c18 100644 --- a/src/vpp/api/test_client.c +++ b/src/vpp/api/test_client.c @@ -541,13 +541,6 @@ static void vl_api_create_loopback_instance_reply_t_handler ntohl (mp->retval), ntohl (mp->sw_if_index)); } -static void -vl_api_sr_tunnel_add_del_reply_t_handler (vl_api_sr_tunnel_add_del_reply_t * - mp) -{ - fformat (stdout, "sr tunnel add/del reply %d\n", ntohl (mp->retval)); -} - static void vl_api_l2_patch_add_del_reply_t_handler (vl_api_l2_patch_add_del_reply_t * mp) { @@ -949,7 +942,6 @@ add_ip4_neighbor (test_main_t * tm, int add_del) mp->_vl_msg_id = ntohs (VL_API_IP_NEIGHBOR_ADD_DEL); mp->client_index = tm->my_client_index; mp->context = 0xdeadbeef; - mp->vrf_id = ntohl (11); mp->sw_if_index = ntohl (6); mp->is_add = add_del; @@ -972,7 +964,6 @@ add_ip6_neighbor (test_main_t * tm, int add_del) mp->_vl_msg_id = ntohs (VL_API_IP_NEIGHBOR_ADD_DEL); mp->client_index = tm->my_client_index; mp->context = 0xdeadbeef; - mp->vrf_id = ntohl (11); mp->sw_if_index = ntohl (6); mp->is_add = add_del; mp->is_ipv6 = 1; @@ -1055,9 +1046,7 @@ dhcp_set_proxy (test_main_t * tm, int ipv6) mp->_vl_msg_id = ntohs (VL_API_DHCP_PROXY_CONFIG); mp->client_index = tm->my_client_index; mp->context = 0xdeadbeef; - mp->vrf_id = ntohl (0); mp->is_ipv6 = ipv6; - mp->insert_circuit_id = 1; mp->is_add = 1; mp->dhcp_server[0] = 0x20; mp->dhcp_server[1] = 0x01; diff --git a/src/vppinfra/test_tw_timer.c b/src/vppinfra/test_tw_timer.c index a0287b89..26499509 100644 --- a/src/vppinfra/test_tw_timer.c +++ b/src/vppinfra/test_tw_timer.c @@ -138,7 +138,7 @@ 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; @@ -266,7 +266,7 @@ 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; @@ -387,7 +387,7 @@ test1_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, to make sure that the wheel starts in a @@ -454,7 +454,7 @@ test1_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, to make sure that the wheel starts in a -- cgit 1.2.3-korg From 4af9ba1dabe3dbd4a2dd3d8c71434477c5ea81b9 Mon Sep 17 00:00:00 2001 From: Dave Barach Date: Wed, 7 Jun 2017 15:18:23 -0400 Subject: three-level timer wheel implementation w/ overflow vector prep work for s/timing_wheel/tw_timer/ in the vlib process model Change-Id: I763f4968a8fce1764a3778b12def0afbd30086b1 Signed-off-by: Dave Barach --- src/vppinfra.am | 6 + src/vppinfra/test_tw_timer.c | 913 ++++++++++++++++++++++++++++---- src/vppinfra/tw_timer_16t_1w_2048sl.h | 1 + src/vppinfra/tw_timer_16t_2w_512sl.h | 1 + src/vppinfra/tw_timer_1t_3w_1024sl_ov.c | 26 + src/vppinfra/tw_timer_1t_3w_1024sl_ov.h | 48 ++ src/vppinfra/tw_timer_2t_1w_2048sl.h | 1 + src/vppinfra/tw_timer_4t_3w_256sl.c | 26 + src/vppinfra/tw_timer_4t_3w_256sl.h | 47 ++ src/vppinfra/tw_timer_4t_3w_4sl_ov.c | 32 ++ src/vppinfra/tw_timer_4t_3w_4sl_ov.h | 48 ++ src/vppinfra/tw_timer_template.c | 405 ++++++++++++-- src/vppinfra/tw_timer_template.h | 48 +- 13 files changed, 1428 insertions(+), 174 deletions(-) create mode 100644 src/vppinfra/tw_timer_1t_3w_1024sl_ov.c create mode 100644 src/vppinfra/tw_timer_1t_3w_1024sl_ov.h create mode 100644 src/vppinfra/tw_timer_4t_3w_256sl.c create mode 100644 src/vppinfra/tw_timer_4t_3w_256sl.h create mode 100644 src/vppinfra/tw_timer_4t_3w_4sl_ov.c create mode 100644 src/vppinfra/tw_timer_4t_3w_4sl_ov.h (limited to 'src/vppinfra/test_tw_timer.c') diff --git a/src/vppinfra.am b/src/vppinfra.am index 3939d3ce..ff2b8ea4 100644 --- a/src/vppinfra.am +++ b/src/vppinfra.am @@ -211,6 +211,8 @@ nobase_include_HEADERS = \ vppinfra/tw_timer_2t_1w_2048sl.h \ vppinfra/tw_timer_16t_2w_512sl.h \ vppinfra/tw_timer_16t_1w_2048sl.h \ + vppinfra/tw_timer_4t_3w_256sl.h \ + vppinfra/tw_timer_1t_3w_1024sl_ov.h \ vppinfra/tw_timer_template.h \ vppinfra/tw_timer_template.c \ vppinfra/types.h \ @@ -268,6 +270,10 @@ CLIB_CORE = \ vppinfra/tw_timer_16t_2w_512sl.c \ vppinfra/tw_timer_16t_1w_2048sl.h \ vppinfra/tw_timer_16t_1w_2048sl.c \ + vppinfra/tw_timer_4t_3w_256sl.h \ + vppinfra/tw_timer_4t_3w_256sl.c \ + vppinfra/tw_timer_1t_3w_1024sl_ov.h \ + vppinfra/tw_timer_1t_3w_1024sl_ov.c \ vppinfra/unformat.c \ vppinfra/vec.c \ vppinfra/vector.c \ diff --git a/src/vppinfra/test_tw_timer.c b/src/vppinfra/test_tw_timer.c index 26499509..ec0baa07 100644 --- a/src/vppinfra/test_tw_timer.c +++ b/src/vppinfra/test_tw_timer.c @@ -3,6 +3,8 @@ #include #include #include +#include +#include typedef struct { @@ -10,7 +12,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 +26,14 @@ 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; + /** random number seed */ - u32 seed; + u64 seed; /** number of timers */ u32 ntimers; @@ -68,6 +76,32 @@ run_double_wheel (tw_timer_wheel_16t_2w_512sl_t * tw, u32 n_ticks) } } +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 +121,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 +148,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 +156,64 @@ expired_timer_double_callback (u32 * expired_timers) } } +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; @@ -145,7 +230,14 @@ test2_single (tw_timer_test_main_t * tm) 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); @@ -158,7 +250,7 @@ test2_single (tw_timer_test_main_t * tm) do { - expiration_time = random_u32 (&tm->seed) & (2047); + expiration_time = random_u64 (&tm->seed) & (2047); } while (expiration_time == 0); @@ -192,7 +284,9 @@ 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; @@ -203,7 +297,7 @@ test2_single (tw_timer_test_main_t * tm) do { - expiration_time = random_u32 (&tm->seed) & (2047); + expiration_time = random_u64 (&tm->seed) & (2047); } while (expiration_time == 0); @@ -269,11 +363,19 @@ test2_double (tw_timer_test_main_t * tm) 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); @@ -286,7 +388,7 @@ test2_double (tw_timer_test_main_t * tm) 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 +396,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 */ , @@ -331,7 +434,7 @@ test2_double (tw_timer_test_main_t * tm) 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 +443,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); @@ -379,106 +483,126 @@ test2_double (tw_timer_test_main_t * tm) } static clib_error_t * -test1_single (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_2t_1w_2048sl (&tm->single_wheel, - expired_timer_single_callback, - 1.0 /* timer interval */ , ~0); + clib_time_init (&tm->clib_time); - /* - * Prime offset, to make sure that the wheel starts in a - * non-trivial position - */ - offset = 123; + tw_timer_wheel_init_4t_3w_256sl (&tm->triple_wheel, + expired_timer_triple_callback, + 1.0 /* timer interval */ , ~0); - 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]); + /* Prime offset */ + initial_wheel_offset = 75700; + run_triple_wheel (&tm->triple_wheel, initial_wheel_offset); - for (i = 0; i < tm->ntimers; i++) - { - u32 expected_to_expire; - u32 timer_arg; + 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]); - timer_arg = 1 + i; - timer_arg &= 2047; - if (timer_arg == 0) - timer_arg = 1; + initial_wheel_offset = tm->triple_wheel.current_tick; - expected_to_expire = timer_arg + offset; + 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 = 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)); + 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->single_wheel.current_tick, - tm->single_wheel.current_index[TW_TIMER_RING_FAST]); + e->expected_to_expire = expiration_time + initial_wheel_offset; - pool_free (tm->test_elts); - tw_timer_wheel_free_2t_1w_2048sl (&tm->single_wheel); - return 0; -} + e->stop_timer_handle = + tw_timer_start_4t_3w_256sl (&tm->triple_wheel, e - tm->test_elts, + 3 /* timer id */ , + expiration_time); + } -static clib_error_t * -test1_double (tw_timer_test_main_t * tm) -{ - u32 i; - tw_timer_test_elt_t *e; - u32 offset; + adds += i; - tw_timer_wheel_init_16t_2w_512sl (&tm->double_wheel, - expired_timer_double_callback, - 1.0 /* timer interval */ , ~0); + for (i = 0; i < tm->niter; i++) + { + run_triple_wheel (&tm->triple_wheel, tm->ticks_per_iter); - /* - * Prime offset, to make sure that the wheel starts in a - * non-trivial position - */ - offset = 227989; + 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* */ - run_double_wheel (&tm->double_wheel, offset); + del_and_re_add: + for (j = 0; j < vec_len (deleted_indices); j++) + pool_put_index (tm->test_elts, deleted_indices[j]); - fformat (stdout, "initial wheel time %d, fast index %d\n", - tm->double_wheel.current_tick, - tm->double_wheel.current_index[TW_TIMER_RING_FAST]); + deletes += j; - for (i = 0; i < tm->ntimers; i++) - { - pool_get (tm->test_elts, e); - memset (e, 0, sizeof (*e)); + for (j = 0; j < tm->ntimers / 4; j++) + { + 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); + 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; } - run_double_wheel (&tm->double_wheel, tm->ntimers + 3); + + 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", @@ -487,45 +611,567 @@ test1_double (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->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); + tw_timer_wheel_free_4t_3w_256sl (&tm->triple_wheel); return 0; } static clib_error_t * -timer_test_command_fn (tw_timer_test_main_t * tm, unformat_input_t * input) +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; - int is_test1 = 0; - int num_wheels = 1; - int is_test2 = 0; + clib_time_init (&tm->clib_time); - memset (tm, 0, sizeof (*tm)); - /* Default values */ - tm->ntimers = 100000; - tm->seed = 0xDEADDABE; - tm->niter = 1000; - tm->ticks_per_iter = 727; + tw_timer_wheel_init_1t_3w_1024sl_ov (&tm->triple_ov_wheel, + expired_timer_triple_ov_callback, + 1.0 /* timer interval */ , ~0); - while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT) - { - if (unformat (input, "seed %d", &tm->seed)) - ; + + /* 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); + 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); + 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 + offset; + + 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); + } + 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); + 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); + + 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 * +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); + 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); + 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); + 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); + return 0; +} + +static clib_error_t * +timer_test_command_fn (tw_timer_test_main_t * tm, unformat_input_t * input) +{ + + int is_test1 = 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)); + /* Default values */ + tm->ntimers = 100000; + tm->seed = 0xDEADDABEB00BFACE; + tm->niter = 1000; + tm->ticks_per_iter = 727; + + while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT) + { + 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, "wheels %d", &num_wheels)) ; else if (unformat (input, "ntimers %d", &tm->ntimers)) @@ -534,12 +1180,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) @@ -553,9 +1201,25 @@ timer_test_command_fn (tw_timer_test_main_t * tm, unformat_input_t * input) { if (num_wheels == 1) return test2_single (tm); - else + else if (num_wheels == 2) 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 +1247,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 * diff --git a/src/vppinfra/tw_timer_16t_1w_2048sl.h b/src/vppinfra/tw_timer_16t_1w_2048sl.h index 685ac31e..6edef17b 100644 --- a/src/vppinfra/tw_timer_16t_1w_2048sl.h +++ b/src/vppinfra/tw_timer_16t_1w_2048sl.h @@ -24,6 +24,7 @@ #undef TW_TIMERS_PER_OBJECT #undef LOG2_TW_TIMERS_PER_OBJECT #undef TW_SUFFIX +#undef TW_OVERFLOW_VECTOR #define TW_TIMER_WHEELS 1 #define TW_SLOTS_PER_RING 2048 diff --git a/src/vppinfra/tw_timer_16t_2w_512sl.h b/src/vppinfra/tw_timer_16t_2w_512sl.h index 93b26d29..2497b31c 100644 --- a/src/vppinfra/tw_timer_16t_2w_512sl.h +++ b/src/vppinfra/tw_timer_16t_2w_512sl.h @@ -24,6 +24,7 @@ #undef TW_TIMERS_PER_OBJECT #undef LOG2_TW_TIMERS_PER_OBJECT #undef TW_SUFFIX +#undef TW_OVERFLOW_VECTOR #define TW_TIMER_WHEELS 2 #define TW_SLOTS_PER_RING 512 diff --git a/src/vppinfra/tw_timer_1t_3w_1024sl_ov.c b/src/vppinfra/tw_timer_1t_3w_1024sl_ov.c new file mode 100644 index 00000000..8a65752c --- /dev/null +++ b/src/vppinfra/tw_timer_1t_3w_1024sl_ov.c @@ -0,0 +1,26 @@ +/* + * Copyright (c) 2017 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include +#include "tw_timer_1t_3w_1024sl_ov.h" +#include "tw_timer_template.c" + +/* + * fd.io coding-style-patch-verification: ON + * + * Local Variables: + * eval: (c-set-style "gnu") + * End: + */ diff --git a/src/vppinfra/tw_timer_1t_3w_1024sl_ov.h b/src/vppinfra/tw_timer_1t_3w_1024sl_ov.h new file mode 100644 index 00000000..7327f87b --- /dev/null +++ b/src/vppinfra/tw_timer_1t_3w_1024sl_ov.h @@ -0,0 +1,48 @@ +/* + * Copyright (c) 2017 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef __included_tw_timer_1t_3w_1024sl_ov_h__ +#define __included_tw_timer_1t_3w_1024sl_ov_h__ + +/* ... So that a client app can create multiple wheel geometries */ +#undef TW_TIMER_WHEELS +#undef TW_SLOTS_PER_RING +#undef TW_RING_SHIFT +#undef TW_RING_MASK +#undef TW_TIMERS_PER_OBJECT +#undef LOG2_TW_TIMERS_PER_OBJECT +#undef TW_SUFFIX +#undef TW_OVERFLOW_VECTOR + +#define TW_TIMER_WHEELS 3 +#define TW_SLOTS_PER_RING 1024 +#define TW_RING_SHIFT 10 +#define TW_RING_MASK (TW_SLOTS_PER_RING -1) +#define TW_TIMERS_PER_OBJECT 1 +#define LOG2_TW_TIMERS_PER_OBJECT 0 +#define TW_SUFFIX _1t_3w_1024sl_ov +#define TW_OVERFLOW_VECTOR 1 + +#include + +#endif /* __included_tw_timer_1t_3w_1024sl_ov_h__ */ + +/* + * fd.io coding-style-patch-verification: ON + * + * Local Variables: + * eval: (c-set-style "gnu") + * End: + */ diff --git a/src/vppinfra/tw_timer_2t_1w_2048sl.h b/src/vppinfra/tw_timer_2t_1w_2048sl.h index d1cf6d07..33b74405 100644 --- a/src/vppinfra/tw_timer_2t_1w_2048sl.h +++ b/src/vppinfra/tw_timer_2t_1w_2048sl.h @@ -24,6 +24,7 @@ #undef TW_TIMERS_PER_OBJECT #undef LOG2_TW_TIMERS_PER_OBJECT #undef TW_SUFFIX +#undef TW_OVERFLOW_VECTOR #define TW_TIMER_WHEELS 1 #define TW_SLOTS_PER_RING 2048 diff --git a/src/vppinfra/tw_timer_4t_3w_256sl.c b/src/vppinfra/tw_timer_4t_3w_256sl.c new file mode 100644 index 00000000..73bb34b2 --- /dev/null +++ b/src/vppinfra/tw_timer_4t_3w_256sl.c @@ -0,0 +1,26 @@ +/* + * Copyright (c) 2017 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include +#include "tw_timer_4t_3w_256sl.h" +#include "tw_timer_template.c" + +/* + * fd.io coding-style-patch-verification: ON + * + * Local Variables: + * eval: (c-set-style "gnu") + * End: + */ diff --git a/src/vppinfra/tw_timer_4t_3w_256sl.h b/src/vppinfra/tw_timer_4t_3w_256sl.h new file mode 100644 index 00000000..89adb7a2 --- /dev/null +++ b/src/vppinfra/tw_timer_4t_3w_256sl.h @@ -0,0 +1,47 @@ +/* + * Copyright (c) 2017 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef __included_tw_timer_4t_3w_256sl_h__ +#define __included_tw_timer_4t_3w_256sl_h__ + +/* ... So that a client app can create multiple wheel geometries */ +#undef TW_TIMER_WHEELS +#undef TW_SLOTS_PER_RING +#undef TW_RING_SHIFT +#undef TW_RING_MASK +#undef TW_TIMERS_PER_OBJECT +#undef LOG2_TW_TIMERS_PER_OBJECT +#undef TW_SUFFIX +#undef TW_OVERFLOW_VECTOR + +#define TW_TIMER_WHEELS 3 +#define TW_SLOTS_PER_RING 256 +#define TW_RING_SHIFT 8 +#define TW_RING_MASK (TW_SLOTS_PER_RING -1) +#define TW_TIMERS_PER_OBJECT 4 +#define LOG2_TW_TIMERS_PER_OBJECT 2 +#define TW_SUFFIX _4t_3w_256sl + +#include + +#endif /* __included_tw_timer_4t_3w_256sl_h__ */ + +/* + * fd.io coding-style-patch-verification: ON + * + * Local Variables: + * eval: (c-set-style "gnu") + * End: + */ diff --git a/src/vppinfra/tw_timer_4t_3w_4sl_ov.c b/src/vppinfra/tw_timer_4t_3w_4sl_ov.c new file mode 100644 index 00000000..e2af7b5d --- /dev/null +++ b/src/vppinfra/tw_timer_4t_3w_4sl_ov.c @@ -0,0 +1,32 @@ +/* + * Copyright (c) 2017 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +/* + * This wheel geometry is not prima facie useful, except for testing + */ + +#if TW_TIMER_TEST_GEOMETRY > 0 +#include +#include "tw_timer_4t_3w_4sl_ov.h" +#include "tw_timer_template.c" +#endif + +/* + * fd.io coding-style-patch-verification: ON + * + * Local Variables: + * eval: (c-set-style "gnu") + * End: + */ diff --git a/src/vppinfra/tw_timer_4t_3w_4sl_ov.h b/src/vppinfra/tw_timer_4t_3w_4sl_ov.h new file mode 100644 index 00000000..0f76164d --- /dev/null +++ b/src/vppinfra/tw_timer_4t_3w_4sl_ov.h @@ -0,0 +1,48 @@ +/* + * Copyright (c) 2017 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef __included_tw_timer_4t_3w_4sl_ov_h__ +#define __included_tw_timer_4t_3w_4sl_ov_h__ + +/* ... So that a client app can create multiple wheel geometries */ +#undef TW_TIMER_WHEELS +#undef TW_SLOTS_PER_RING +#undef TW_RING_SHIFT +#undef TW_RING_MASK +#undef TW_TIMERS_PER_OBJECT +#undef LOG2_TW_TIMERS_PER_OBJECT +#undef TW_SUFFIX +#undef TW_OVERFLOW_VECTOR + +#define TW_TIMER_WHEELS 3 +#define TW_SLOTS_PER_RING 4 +#define TW_RING_SHIFT 2 +#define TW_RING_MASK (TW_SLOTS_PER_RING -1) +#define TW_TIMERS_PER_OBJECT 4 +#define LOG2_TW_TIMERS_PER_OBJECT 2 +#define TW_SUFFIX _4t_3w_4sl_ov +#define TW_OVERFLOW_VECTOR 1 + +#include + +#endif /* __included_tw_timer_4t_3w_256sl_h__ */ + +/* + * fd.io coding-style-patch-verification: ON + * + * Local Variables: + * eval: (c-set-style "gnu") + * End: + */ diff --git a/src/vppinfra/tw_timer_template.c b/src/vppinfra/tw_timer_template.c index e3f44500..a0c407ae 100644 --- a/src/vppinfra/tw_timer_template.c +++ b/src/vppinfra/tw_timer_template.c @@ -18,16 +18,19 @@ * * */ - static inline u32 TW (make_internal_timer_handle) (u32 pool_index, u32 timer_id) { u32 handle; ASSERT (timer_id < TW_TIMERS_PER_OBJECT); +#if LOG2_TW_TIMERS_PER_OBJECT > 0 ASSERT (pool_index < (1 << (32 - LOG2_TW_TIMERS_PER_OBJECT))); handle = (timer_id << (32 - LOG2_TW_TIMERS_PER_OBJECT)) | (pool_index); +#else + handle = pool_index; +#endif return handle; } @@ -79,16 +82,22 @@ timer_remove (TWT (tw_timer) * pool, u32 index) * @param tw_timer_wheel_t * tw timer wheel object pointer * @param u32 pool_index user pool index, presumably for a tw session * @param u32 timer_id app-specific timer ID. 4 bits. - * @param u32 interval timer interval in ticks + * @param u64 interval timer interval in ticks * @returns handle needed to cancel the timer */ u32 TW (tw_timer_start) (TWT (tw_timer_wheel) * tw, u32 pool_index, u32 timer_id, - u32 interval) + u64 interval) { #if TW_TIMER_WHEELS > 1 u16 slow_ring_offset; u32 carry; +#endif +#if TW_TIMER_WHEELS > 2 + u16 glacier_ring_offset; +#endif +#if TW_OVERFLOW_VECTOR > 0 + u64 interval_plus_time_to_wrap, triple_wrap_mask; #endif u16 fast_ring_offset; tw_timer_wheel_slot_t *ts; @@ -97,31 +106,89 @@ TW (tw_timer_start) (TWT (tw_timer_wheel) * tw, u32 pool_index, u32 timer_id, ASSERT (interval); pool_get (tw->timers, t); - t->next = t->prev = ~0; -#if TW_TIMER_WHEELS > 1 - t->fast_ring_offset = ~0; -#endif + memset (t, 0xff, sizeof (*t)); + t->user_handle = TW (make_internal_timer_handle) (pool_index, timer_id); + /* Factor interval into 1..3 wheel offsets */ +#if TW_TIMER_WHEELS > 2 +#if TW_OVERFLOW_VECTOR > 0 + /* + * This is tricky. Put a timer onto the overflow + * vector if the interval PLUS the time + * until the next triple-wrap exceeds one full revolution + * of all three wheels. + */ + triple_wrap_mask = (1 << (3 * TW_RING_SHIFT)) - 1; + interval_plus_time_to_wrap = + interval + (tw->current_tick & triple_wrap_mask); + if ((interval_plus_time_to_wrap >= 1 << (3 * TW_RING_SHIFT))) + { + t->expiration_time = tw->current_tick + interval; + ts = &tw->overflow; + timer_addhead (tw->timers, ts->head_index, t - tw->timers); + return t - tw->timers; + } +#endif + + glacier_ring_offset = interval >> (2 * TW_RING_SHIFT); + ASSERT (glacier_ring_offset < TW_SLOTS_PER_RING); + interval -= (glacier_ring_offset << (2 * TW_RING_SHIFT)); +#endif +#if TW_TIMER_WHEELS > 1 + slow_ring_offset = interval >> TW_RING_SHIFT; + ASSERT (slow_ring_offset < TW_SLOTS_PER_RING); + interval -= (slow_ring_offset << TW_RING_SHIFT); +#endif fast_ring_offset = interval & TW_RING_MASK; - fast_ring_offset += tw->current_index[TW_TIMER_RING_FAST]; + + /* + * Account for the current wheel positions(s) + * This is made slightly complicated by the fact that the current + * index vector will contain (TW_SLOTS_PER_RING, ...) when + * the actual position is (0, ...) + */ + + fast_ring_offset += tw->current_index[TW_TIMER_RING_FAST] & TW_RING_MASK; + #if TW_TIMER_WHEELS > 1 carry = fast_ring_offset >= TW_SLOTS_PER_RING ? 1 : 0; fast_ring_offset %= TW_SLOTS_PER_RING; - slow_ring_offset = (interval >> TW_RING_SHIFT) + carry; + slow_ring_offset += (tw->current_index[TW_TIMER_RING_SLOW] & TW_RING_MASK) + + carry; + carry = slow_ring_offset >= TW_SLOTS_PER_RING ? 1 : 0; + slow_ring_offset %= TW_SLOTS_PER_RING; +#endif - /* Timer duration exceeds ~7 hrs? Oops */ - ASSERT (slow_ring_offset < TW_SLOTS_PER_RING); +#if TW_TIMER_WHEELS > 2 + glacier_ring_offset += + (tw->current_index[TW_TIMER_RING_GLACIER] & TW_RING_MASK) + carry; + glacier_ring_offset %= TW_SLOTS_PER_RING; +#endif - /* Timer expires more than 51.2 seconds from now? */ - if (slow_ring_offset) +#if TW_TIMER_WHEELS > 2 + if (glacier_ring_offset != + (tw->current_index[TW_TIMER_RING_GLACIER] & TW_RING_MASK)) { - slow_ring_offset += tw->current_index[TW_TIMER_RING_SLOW]; - slow_ring_offset %= TW_SLOTS_PER_RING; + /* We'll need slow and fast ring offsets later */ + t->slow_ring_offset = slow_ring_offset; + t->fast_ring_offset = fast_ring_offset; - /* We'll want the fast ring offset later... */ + ts = &tw->w[TW_TIMER_RING_GLACIER][glacier_ring_offset]; + + timer_addhead (tw->timers, ts->head_index, t - tw->timers); + + return t - tw->timers; + } +#endif + +#if TW_TIMER_WHEELS > 1 + /* Timer expires more than 51.2 seconds from now? */ + if (slow_ring_offset != + (tw->current_index[TW_TIMER_RING_SLOW] & TW_RING_MASK)) + { + /* We'll need the fast ring offset later... */ t->fast_ring_offset = fast_ring_offset; - ASSERT (t->fast_ring_offset < TW_SLOTS_PER_RING); ts = &tw->w[TW_TIMER_RING_SLOW][slow_ring_offset]; @@ -131,7 +198,6 @@ TW (tw_timer_start) (TWT (tw_timer_wheel) * tw, u32 pool_index, u32 timer_id, } #else fast_ring_offset %= TW_SLOTS_PER_RING; - ASSERT (interval < TW_SLOTS_PER_RING); #endif /* Timer expires less than one fast-ring revolution from now */ @@ -141,6 +207,41 @@ TW (tw_timer_start) (TWT (tw_timer_wheel) * tw, u32 pool_index, u32 timer_id, return t - tw->timers; } +#if TW_TIMER_SCAN_FOR_HANDLE > 0 +int TW (scan_for_handle) (TWT (tw_timer_wheel) * tw, u32 handle) +{ + int i, j; + tw_timer_wheel_slot_t *ts; + TWT (tw_timer) * t, *head; + u32 next_index; + int rv = 0; + + for (i = 0; i < TW_TIMER_WHEELS; i++) + { + for (j = 0; j < TW_SLOTS_PER_RING; j++) + { + ts = &tw->w[i][j]; + head = pool_elt_at_index (tw->timers, ts->head_index); + next_index = head->next; + + while (next_index != ts->head_index) + { + t = pool_elt_at_index (tw->timers, next_index); + if (next_index == handle) + { + clib_warning ("handle %d found in ring %d slot %d", + handle, i, j); + clib_warning ("user handle 0x%x", t->user_handle); + rv = 1; + } + next_index = t->next; + } + } + } + return rv; +} +#endif /* TW_TIMER_SCAN_FOR_HANDLE */ + /** * @brief Stop a tw timer * @param tw_timer_wheel_t * tw timer wheel object pointer @@ -164,7 +265,7 @@ void TW (tw_timer_stop) (TWT (tw_timer_wheel) * tw, u32 handle) * @brief Initialize a tw timer wheel template instance * @param tw_timer_wheel_t * tw timer wheel object pointer * @param void * expired_timer_callback. Passed a u32 * vector of - * expired timer handles. + * expired timer handles. The callback is optional. * @param f64 timer_interval_in_seconds */ void @@ -185,6 +286,9 @@ TW (tw_timer_wheel_init) (TWT (tw_timer_wheel) * tw, } tw->timer_interval = timer_interval_in_seconds; tw->ticks_per_second = 1.0 / timer_interval_in_seconds; + tw->first_expires_tick = ~0ULL; + vec_validate (tw->expired_timer_handles, 0); + _vec_len (tw->expired_timer_handles) = 0; for (ring = 0; ring < TW_TIMER_WHEELS; ring++) { @@ -197,6 +301,14 @@ TW (tw_timer_wheel_init) (TWT (tw_timer_wheel) * tw, ts->head_index = t - tw->timers; } } + +#if TW_OVERFLOW_VECTOR > 0 + ts = &tw->overflow; + pool_get (tw->timers, t); + memset (t, 0xff, sizeof (*t)); + t->next = t->prev = t - tw->timers; + ts->head_index = t - tw->timers; +#endif } /** @@ -227,6 +339,21 @@ void TW (tw_timer_wheel_free) (TWT (tw_timer_wheel) * tw) pool_put (tw->timers, head); } } + +#if TW_OVERFLOW_VECVOR > 0 + ts = &tw->overflow; + head = pool_elt_at_index (tw->timers, ts->head_index); + next_index = head->next; + + while (next_index != ts->head_index) + { + t = pool_elt_at_index (tw->timers, next_index); + next_index = t->next; + pool_put (tw->timers, t); + } + pool_put (tw->timers, head); +#endif + memset (tw, 0, sizeof (*tw)); } @@ -235,50 +362,185 @@ void TW (tw_timer_wheel_free) (TWT (tw_timer_wheel) * tw) * as needed. This routine should be called once every timer_interval seconds * @param tw_timer_wheel_t * tw timer wheel template instance pointer * @param f64 now the current time, e.g. from vlib_time_now(vm) + * @returns u32 * vector of expired user handles */ -u32 TW (tw_timer_expire_timers) (TWT (tw_timer_wheel) * tw, f64 now) +static inline + u32 * TW (tw_timer_expire_timers_internal) (TWT (tw_timer_wheel) * tw, + f64 now, + u32 * callback_vector_arg) { u32 nticks, i; tw_timer_wheel_slot_t *ts; TWT (tw_timer) * t, *head; + u32 *callback_vector; u32 fast_wheel_index; u32 next_index; - u32 nexpirations, total_nexpirations; -#if TW_TIMER_WHEELS > 1 - u32 slow_wheel_index; -#endif + u32 slow_wheel_index __attribute__ ((unused)); + u32 glacier_wheel_index __attribute__ ((unused)); /* Shouldn't happen */ if (PREDICT_FALSE (now < tw->next_run_time)) - return 0; + return callback_vector_arg; /* Number of ticks which have occurred */ nticks = tw->ticks_per_second * (now - tw->last_run_time); if (nticks == 0) - return 0; + return callback_vector_arg; /* Remember when we ran, compute next runtime */ tw->next_run_time = (now + tw->timer_interval); - total_nexpirations = 0; + if (callback_vector_arg == 0) + { + _vec_len (tw->expired_timer_handles) = 0; + callback_vector = tw->expired_timer_handles; + } + else + callback_vector = callback_vector_arg; + for (i = 0; i < nticks; i++) { fast_wheel_index = tw->current_index[TW_TIMER_RING_FAST]; + if (TW_TIMER_WHEELS > 1) + slow_wheel_index = tw->current_index[TW_TIMER_RING_SLOW]; + if (TW_TIMER_WHEELS > 2) + glacier_wheel_index = tw->current_index[TW_TIMER_RING_GLACIER]; + +#if TW_OVERFLOW_VECTOR > 0 + /* Triple odometer-click? Process the overflow vector... */ + if (PREDICT_FALSE (fast_wheel_index == TW_SLOTS_PER_RING + && slow_wheel_index == TW_SLOTS_PER_RING + && glacier_wheel_index == TW_SLOTS_PER_RING)) + { + u64 interval; + u32 new_glacier_ring_offset, new_slow_ring_offset; + u32 new_fast_ring_offset; + ts = &tw->overflow; + head = pool_elt_at_index (tw->timers, ts->head_index); + next_index = head->next; + + /* Make slot empty */ + head->next = head->prev = ts->head_index; + + /* traverse slot, place timers wherever they go */ + while (next_index != head - tw->timers) + { + t = pool_elt_at_index (tw->timers, next_index); + next_index = t->next; + + /* Remove from the overflow vector (hammer) */ + t->next = t->prev = ~0; + + ASSERT (t->expiration_time >= tw->current_tick); + + interval = t->expiration_time - tw->current_tick; + + /* Right back onto the overflow vector? */ + if (interval >= (1 << (3 * TW_RING_SHIFT))) + { + ts = &tw->overflow; + timer_addhead (tw->timers, ts->head_index, t - tw->timers); + continue; + } + /* Compute ring offsets */ + new_glacier_ring_offset = interval >> (2 * TW_RING_SHIFT); + + interval -= (new_glacier_ring_offset << (2 * TW_RING_SHIFT)); + + /* Note: the wheels are at (0,0,0), no add-with-carry needed */ + new_slow_ring_offset = interval >> TW_RING_SHIFT; + interval -= (new_slow_ring_offset << TW_RING_SHIFT); + new_fast_ring_offset = interval & TW_RING_MASK; + t->slow_ring_offset = new_slow_ring_offset; + t->fast_ring_offset = new_fast_ring_offset; + + /* Timer expires Right Now */ + if (PREDICT_FALSE (t->slow_ring_offset == 0 && + t->fast_ring_offset == 0 && + new_glacier_ring_offset == 0)) + { + vec_add1 (callback_vector, t->user_handle); + pool_put (tw->timers, t); + } + /* Timer moves to the glacier ring */ + else if (new_glacier_ring_offset) + { + ts = &tw->w[TW_TIMER_RING_GLACIER][new_glacier_ring_offset]; + timer_addhead (tw->timers, ts->head_index, t - tw->timers); + } + /* Timer moves to the slow ring */ + else if (t->slow_ring_offset) + { + /* Add to slow ring */ + ts = &tw->w[TW_TIMER_RING_SLOW][t->slow_ring_offset]; + timer_addhead (tw->timers, ts->head_index, t - tw->timers); + } + /* Timer timer moves to the fast ring */ + else + { + ts = &tw->w[TW_TIMER_RING_FAST][t->fast_ring_offset]; + timer_addhead (tw->timers, ts->head_index, t - tw->timers); + } + } + } +#endif + +#if TW_TIMER_WHEELS > 2 /* - * If we've been around the fast ring once, - * process one slot in the slow ring before we handle - * the fast ring. + * Double odometer-click? Process one slot in the glacier ring... */ - if (PREDICT_FALSE (fast_wheel_index == TW_SLOTS_PER_RING)) + if (PREDICT_FALSE (fast_wheel_index == TW_SLOTS_PER_RING + && slow_wheel_index == TW_SLOTS_PER_RING)) { - fast_wheel_index = tw->current_index[TW_TIMER_RING_FAST] = 0; + glacier_wheel_index %= TW_SLOTS_PER_RING; + ts = &tw->w[TW_TIMER_RING_GLACIER][glacier_wheel_index]; -#if TW_TIMER_WHEELS > 1 - tw->current_index[TW_TIMER_RING_SLOW]++; - tw->current_index[TW_TIMER_RING_SLOW] %= TW_SLOTS_PER_RING; - slow_wheel_index = tw->current_index[TW_TIMER_RING_SLOW]; + head = pool_elt_at_index (tw->timers, ts->head_index); + next_index = head->next; + + /* Make slot empty */ + head->next = head->prev = ts->head_index; + + /* traverse slot, deal timers into slow ring */ + while (next_index != head - tw->timers) + { + t = pool_elt_at_index (tw->timers, next_index); + next_index = t->next; + + /* Remove from glacier ring slot (hammer) */ + t->next = t->prev = ~0; + + /* Timer expires Right Now */ + if (PREDICT_FALSE (t->slow_ring_offset == 0 && + t->fast_ring_offset == 0)) + { + vec_add1 (callback_vector, t->user_handle); + pool_put (tw->timers, t); + } + /* Timer expires during slow-wheel tick 0 */ + else if (PREDICT_FALSE (t->slow_ring_offset == 0)) + { + ts = &tw->w[TW_TIMER_RING_FAST][t->fast_ring_offset]; + timer_addhead (tw->timers, ts->head_index, t - tw->timers); + } + else /* typical case */ + { + /* Add to slow ring */ + ts = &tw->w[TW_TIMER_RING_SLOW][t->slow_ring_offset]; + timer_addhead (tw->timers, ts->head_index, t - tw->timers); + } + } + } +#endif +#if TW_TIMER_WHEELS > 1 + /* + * Single odometer-click? Process a slot in the slow ring, + */ + if (PREDICT_FALSE (fast_wheel_index == TW_SLOTS_PER_RING)) + { + slow_wheel_index %= TW_SLOTS_PER_RING; ts = &tw->w[TW_TIMER_RING_SLOW][slow_wheel_index]; head = pool_elt_at_index (tw->timers, ts->head_index); @@ -293,19 +555,27 @@ u32 TW (tw_timer_expire_timers) (TWT (tw_timer_wheel) * tw, f64 now) t = pool_elt_at_index (tw->timers, next_index); next_index = t->next; - /* Remove from slow ring slot (hammer) */ + /* Remove from sloe ring slot (hammer) */ t->next = t->prev = ~0; - ASSERT (t->fast_ring_offset < TW_SLOTS_PER_RING); - /* Add to fast ring */ - ts = &tw->w[TW_TIMER_RING_FAST][t->fast_ring_offset]; - timer_addhead (tw->timers, ts->head_index, t - tw->timers); + + /* Timer expires Right Now */ + if (PREDICT_FALSE (t->fast_ring_offset == 0)) + { + vec_add1 (callback_vector, t->user_handle); + pool_put (tw->timers, t); + } + else /* typical case */ + { + /* Add to fast ring */ + ts = &tw->w[TW_TIMER_RING_FAST][t->fast_ring_offset]; + timer_addhead (tw->timers, ts->head_index, t - tw->timers); + } } -#endif } +#endif /* Handle the fast ring */ - vec_reset_length (tw->expired_timer_handles); - + fast_wheel_index %= TW_SLOTS_PER_RING; ts = &tw->w[TW_TIMER_RING_FAST][fast_wheel_index]; head = pool_elt_at_index (tw->timers, ts->head_index); @@ -319,26 +589,57 @@ u32 TW (tw_timer_expire_timers) (TWT (tw_timer_wheel) * tw, f64 now) { t = pool_elt_at_index (tw->timers, next_index); next_index = t->next; - vec_add1 (tw->expired_timer_handles, t->user_handle); + vec_add1 (callback_vector, t->user_handle); pool_put (tw->timers, t); } /* If any timers expired, tell the user */ - nexpirations = vec_len (tw->expired_timer_handles); - if (nexpirations) + if (callback_vector_arg == 0 && vec_len (callback_vector)) { - tw->expired_timer_callback (tw->expired_timer_handles); - total_nexpirations += nexpirations; + /* The callback is optional. We return the u32 * handle vector */ + if (tw->expired_timer_callback) + { + tw->expired_timer_callback (callback_vector); + _vec_len (callback_vector) = 0; + } + tw->expired_timer_handles = callback_vector; } - tw->current_index[TW_TIMER_RING_FAST]++; tw->current_tick++; + fast_wheel_index++; + tw->current_index[TW_TIMER_RING_FAST] = fast_wheel_index; + +#if TW_TIMER_WHEELS > 1 + if (PREDICT_FALSE (fast_wheel_index == TW_SLOTS_PER_RING)) + slow_wheel_index++; + tw->current_index[TW_TIMER_RING_SLOW] = slow_wheel_index; +#endif + +#if TW_TIMER_WHEELS > 2 + if (PREDICT_FALSE (slow_wheel_index == TW_SLOTS_PER_RING)) + glacier_wheel_index++; + tw->current_index[TW_TIMER_RING_GLACIER] = glacier_wheel_index; +#endif - if (total_nexpirations >= tw->max_expirations) + if (vec_len (callback_vector) >= tw->max_expirations) break; } + if (callback_vector_arg == 0) + tw->expired_timer_handles = callback_vector; + tw->last_run_time += i * tw->timer_interval; - return total_nexpirations; + return callback_vector; +} + +u32 *TW (tw_timer_expire_timers) (TWT (tw_timer_wheel) * tw, f64 now) +{ + return TW (tw_timer_expire_timers_internal) (tw, now, 0 /* no vector */ ); +} + +u32 *TW (tw_timer_expire_timers_vec) (TWT (tw_timer_wheel) * tw, f64 now, + u32 * vec) +{ + return TW (tw_timer_expire_timers_internal) (tw, now, vec); } /* diff --git a/src/vppinfra/tw_timer_template.h b/src/vppinfra/tw_timer_template.h index 6b61e424..76755609 100644 --- a/src/vppinfra/tw_timer_template.h +++ b/src/vppinfra/tw_timer_template.h @@ -110,16 +110,39 @@ Expired timer callback: } */ +#if (TW_TIMER_WHEELS != 1 && TW_TIMER_WHEELS != 2 && TW_TIMER_WHEELS != 3) +#error TW_TIMER_WHEELS must be 1, 2 or 3 +#endif + typedef struct { /** next, previous pool indices */ u32 next; u32 prev; -#if TW_TIMER_WHEELS > 0 - /** fast ring offset, only valid in the slow ring */ - u16 fast_ring_offset; - u16 pad; + + union + { + struct + { +#if (TW_TIMER_WHEELS == 3) + /** fast ring offset, only valid in the slow ring */ + u16 fast_ring_offset; + /** slow ring offset, only valid in the glacier ring */ + u16 slow_ring_offset; +#endif +#if (TW_TIMER_WHEELS == 2) + /** fast ring offset, only valid in the slow ring */ + u16 fast_ring_offset; + /** slow ring offset, only valid in the glacier ring */ + u16 pad; #endif + }; + +#if (TW_OVERFLOW_VECTOR > 0) + u64 expiration_time; +#endif + }; + /** user timer handle */ u32 user_handle; } TWT (tw_timer); @@ -141,6 +164,8 @@ typedef enum TW_TIMER_RING_FAST, /** Slow timer ring ID */ TW_TIMER_RING_SLOW, + /** Glacier ring ID */ + TW_TIMER_RING_GLACIER, } tw_ring_index_t; #endif /* __defined_tw_timer_wheel_slot__ */ @@ -162,7 +187,10 @@ typedef struct f64 timer_interval; /** current tick */ - u32 current_tick; + u64 current_tick; + + /** first expiration time */ + u64 first_expires_tick; /** current wheel indices */ u32 current_index[TW_TIMER_WHEELS]; @@ -170,6 +198,10 @@ typedef struct /** wheel arrays */ tw_timer_wheel_slot_t w[TW_TIMER_WHEELS][TW_SLOTS_PER_RING]; +#if TW_OVERFLOW_VECTOR > 0 + tw_timer_wheel_slot_t overflow; +#endif + /** expired timer callback, receives a vector of handles */ void (*expired_timer_callback) (u32 * expired_timer_handles); @@ -181,7 +213,7 @@ typedef struct } TWT (tw_timer_wheel); u32 TW (tw_timer_start) (TWT (tw_timer_wheel) * tw, - u32 pool_index, u32 timer_id, u32 interval); + u32 pool_index, u32 timer_id, u64 interval); void TW (tw_timer_stop) (TWT (tw_timer_wheel) * tw, u32 handle); @@ -191,7 +223,9 @@ void TW (tw_timer_wheel_init) (TWT (tw_timer_wheel) * tw, void TW (tw_timer_wheel_free) (TWT (tw_timer_wheel) * tw); -u32 TW (tw_timer_expire_timers) (TWT (tw_timer_wheel) * tw, f64 now); +u32 *TW (tw_timer_expire_timers) (TWT (tw_timer_wheel) * tw, f64 now); +u32 *TW (tw_timer_expire_timers_vec) (TWT (tw_timer_wheel) * tw, f64 now, + u32 * vec); /* * fd.io coding-style-patch-verification: ON -- cgit 1.2.3-korg