diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/vppinfra.am | 13 | ||||
| -rw-r--r-- | src/vppinfra/test_tw_timer.c | 592 | ||||
| -rw-r--r-- | src/vppinfra/tw_timer_16t_2w_512sl.c | 26 | ||||
| -rw-r--r-- | src/vppinfra/tw_timer_16t_2w_512sl.h | 46 | ||||
| -rw-r--r-- | src/vppinfra/tw_timer_2t_1w_2048sl.c | 26 | ||||
| -rw-r--r-- | src/vppinfra/tw_timer_2t_1w_2048sl.h | 46 | ||||
| -rw-r--r-- | src/vppinfra/tw_timer_template.c | 341 | ||||
| -rw-r--r-- | src/vppinfra/tw_timer_template.h | 199 |
8 files changed, 1289 insertions, 0 deletions
diff --git a/src/vppinfra.am b/src/vppinfra.am index 724f21c9705..eb8a92b89b8 100644 --- a/src/vppinfra.am +++ b/src/vppinfra.am @@ -37,6 +37,7 @@ TESTS += test_bihash_template \ test_socket \ test_time \ test_timing_wheel \ + test_tw_timer \ test_vec \ test_zvec endif @@ -65,6 +66,7 @@ test_slist_SOURCES = vppinfra/test_slist.c test_socket_SOURCES = vppinfra/test_socket.c test_time_SOURCES = vppinfra/test_time.c test_timing_wheel_SOURCES = vppinfra/test_timing_wheel.c +test_tw_timer_SOURCES = vppinfra/test_tw_timer.c test_vec_SOURCES = vppinfra/test_vec.c test_zvec_SOURCES = vppinfra/test_zvec.c @@ -91,6 +93,7 @@ test_serialize_CPPFLAGS = $(AM_CPPFLAGS) -DCLIB_DEBUG test_slist_CPPFLAGS = $(AM_CPPFLAGS) -DCLIB_DEBUG test_time_CPPFLAGS = $(AM_CPPFLAGS) -DCLIB_DEBUG test_timing_wheel_CPPFLAGS = $(AM_CPPFLAGS) -DCLIB_DEBUG +test_tw_timer_CPPFLAGS = $(AM_CPPFLAGS) -DCLIB_DEBUG test_vec_CPPFLAGS = $(AM_CPPFLAGS) -DCLIB_DEBUG test_zvec_CPPFLAGS = $(AM_CPPFLAGS) -DCLIB_DEBUG @@ -115,6 +118,7 @@ test_slist_LDADD = libvppinfra.la test_socket_LDADD = libvppinfra.la test_time_LDADD = libvppinfra.la -lm test_timing_wheel_LDADD = libvppinfra.la -lm +test_tw_timer_LDADD = libvppinfra.la test_vec_LDADD = libvppinfra.la test_zvec_LDADD = libvppinfra.la @@ -139,6 +143,7 @@ test_slist_LDFLAGS = -static test_socket_LDFLAGS = -static test_time_LDFLAGS = -static test_timing_wheel_LDFLAGS = -static +test_tw_timer_LDFLAGS = -static test_vec_LDFLAGS = -static test_zvec_LDFLAGS = -static @@ -199,6 +204,9 @@ nobase_include_HEADERS = \ vppinfra/time.h \ vppinfra/timing_wheel.h \ vppinfra/timer.h \ + vppinfra/tw_timer_2t_1w_2048sl.h \ + vppinfra/tw_timer_16t_2w_512sl.h \ + vppinfra/tw_timer_template.h \ vppinfra/types.h \ vppinfra/unix.h \ vppinfra/vec.h \ @@ -247,6 +255,11 @@ CLIB_CORE = \ vppinfra/string.c \ vppinfra/time.c \ vppinfra/timing_wheel.c \ + vppinfra/tw_timer_template.h \ + vppinfra/tw_timer_2t_1w_2048sl.h \ + vppinfra/tw_timer_2t_1w_2048sl.c \ + vppinfra/tw_timer_16t_2w_512sl.h \ + vppinfra/tw_timer_16t_2w_512sl.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 new file mode 100644 index 00000000000..a0287b89862 --- /dev/null +++ b/src/vppinfra/test_tw_timer.c @@ -0,0 +1,592 @@ +#include <vppinfra/time.h> +#include <vppinfra/cache.h> +#include <vppinfra/error.h> +#include <vppinfra/tw_timer_2t_1w_2048sl.h> +#include <vppinfra/tw_timer_16t_2w_512sl.h> + +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: + */ diff --git a/src/vppinfra/tw_timer_16t_2w_512sl.c b/src/vppinfra/tw_timer_16t_2w_512sl.c new file mode 100644 index 00000000000..ad1b9a4a4f5 --- /dev/null +++ b/src/vppinfra/tw_timer_16t_2w_512sl.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 <vppinfra/error.h> +#include "tw_timer_16t_2w_512sl.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_16t_2w_512sl.h b/src/vppinfra/tw_timer_16t_2w_512sl.h new file mode 100644 index 00000000000..93b26d29e20 --- /dev/null +++ b/src/vppinfra/tw_timer_16t_2w_512sl.h @@ -0,0 +1,46 @@ +/* + * 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_16t_2w_512sl_h__ +#define __included_tw_timer_16t_2w_512sl_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 + +#define TW_TIMER_WHEELS 2 +#define TW_SLOTS_PER_RING 512 +#define TW_RING_SHIFT 9 +#define TW_RING_MASK (TW_SLOTS_PER_RING -1) +#define TW_TIMERS_PER_OBJECT 16 +#define LOG2_TW_TIMERS_PER_OBJECT 4 +#define TW_SUFFIX _16t_2w_512sl + +#include <vppinfra/tw_timer_template.h> + +#endif /* __included_tw_timer_16t_2w_512sl_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.c b/src/vppinfra/tw_timer_2t_1w_2048sl.c new file mode 100644 index 00000000000..79d293e1dec --- /dev/null +++ b/src/vppinfra/tw_timer_2t_1w_2048sl.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 <vppinfra/error.h> +#include "tw_timer_2t_1w_2048sl.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_2t_1w_2048sl.h b/src/vppinfra/tw_timer_2t_1w_2048sl.h new file mode 100644 index 00000000000..d1cf6d07a95 --- /dev/null +++ b/src/vppinfra/tw_timer_2t_1w_2048sl.h @@ -0,0 +1,46 @@ +/* + * 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_2t_1w_2048sl_h__ +#define __included_tw_timer_2t_1w_2048sl_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 + +#define TW_TIMER_WHEELS 1 +#define TW_SLOTS_PER_RING 2048 +#define TW_RING_SHIFT 11 +#define TW_RING_MASK (TW_SLOTS_PER_RING -1) +#define TW_TIMERS_PER_OBJECT 2 +#define LOG2_TW_TIMERS_PER_OBJECT 1 +#define TW_SUFFIX _2t_1w_2048sl + +#include <vppinfra/tw_timer_template.h> + +#endif /* __included_tw_timer_2t_1w_2048sl_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 new file mode 100644 index 00000000000..9aa5624f91f --- /dev/null +++ b/src/vppinfra/tw_timer_template.c @@ -0,0 +1,341 @@ +/* + * 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. + */ + +/** @file + * @brief TW timer implementation TEMPLATE ONLY, do not compile directly + * + * + */ + +static inline u32 +TW (make_internal_timer_handle) (u32 pool_index, u32 timer_id) +{ + u32 handle; + + ASSERT (timer_id < TW_TIMERS_PER_OBJECT); + ASSERT (pool_index < (1 << (32 - LOG2_TW_TIMERS_PER_OBJECT))); + + handle = (timer_id << (32 - LOG2_TW_TIMERS_PER_OBJECT)) | (pool_index); + return handle; +} + +static inline void +timer_addhead (TWT (tw_timer) * pool, u32 head_index, u32 new_index) +{ + TWT (tw_timer) * head = pool_elt_at_index (pool, head_index); + TWT (tw_timer) * old_first; + u32 old_first_index; + TWT (tw_timer) * new; + + new = pool_elt_at_index (pool, new_index); + + if (PREDICT_FALSE (head->next == head_index)) + { + head->next = head->prev = new_index; + new->next = new->prev = head_index; + return; + } + + old_first_index = head->next; + old_first = pool_elt_at_index (pool, old_first_index); + + new->next = old_first_index; + new->prev = old_first->prev; + old_first->prev = new_index; + head->next = new_index; +} + +static inline void +timer_remove (TWT (tw_timer) * pool, u32 index) +{ + TWT (tw_timer) * elt = pool_elt_at_index (pool, index); + TWT (tw_timer) * next_elt, *prev_elt; + + ASSERT (elt->user_handle != ~0); + + next_elt = pool_elt_at_index (pool, elt->next); + prev_elt = pool_elt_at_index (pool, elt->prev); + + next_elt->prev = elt->prev; + prev_elt->next = elt->next; + + elt->prev = elt->next = ~0; +} + +/** + * @brief Start a Tw Timer + * @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 + * @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) +{ +#if TW_TIMER_WHEELS > 1 + u16 slow_ring_offset; + u32 carry; +#endif + u16 fast_ring_offset; + tw_timer_wheel_slot_t *ts; + TWT (tw_timer) * t; + + ASSERT (interval); + + pool_get (tw->timers, t); + t->next = t->prev = ~0; +#if TW_TIMER_WHEELS > 1 + t->fast_ring_offset = ~0; +#endif + t->user_handle = TW (make_internal_timer_handle) (pool_index, timer_id); + + fast_ring_offset = interval & TW_RING_MASK; + fast_ring_offset += tw->current_index[TW_TIMER_RING_FAST]; +#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; + + /* Timer duration exceeds ~7 hrs? Oops */ + ASSERT (slow_ring_offset < TW_SLOTS_PER_RING); + + /* Timer expires more than 51.2 seconds from now? */ + if (slow_ring_offset) + { + slow_ring_offset += tw->current_index[TW_TIMER_RING_SLOW]; + slow_ring_offset %= TW_SLOTS_PER_RING; + + /* We'll want 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]; + + timer_addhead (tw->timers, ts->head_index, t - tw->timers); + + return t - tw->timers; + } +#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 */ + ts = &tw->w[TW_TIMER_RING_FAST][fast_ring_offset]; + + timer_addhead (tw->timers, ts->head_index, t - tw->timers); + return t - tw->timers; +} + +/** + * @brief Stop a tw timer + * @param tw_timer_wheel_t * tw timer wheel object pointer + * @param u32 pool_index user pool index, passed for consistency checking only + * @param u32 timer_id 4 bit timer ID, passed for consistency checking only + * @param u32 handle timer cancellation returned by tw_timer_start + */ + +void TW (tw_timer_stop) (TWT (tw_timer_wheel) * tw, u32 handle) +{ + TWT (tw_timer) * t; + + t = pool_elt_at_index (tw->timers, handle); + + /* in case of idiotic handle (e.g. passing a listhead index) */ + ASSERT (t->user_handle != ~0); + + timer_remove (tw->timers, handle); + + pool_put_index (tw->timers, 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. + * @param f64 timer_interval_in_seconds + */ +void +TW (tw_timer_wheel_init) (TWT (tw_timer_wheel) * tw, + void *expired_timer_callback, + f64 timer_interval_in_seconds) +{ + int ring, slot; + tw_timer_wheel_slot_t *ts; + TWT (tw_timer) * t; + memset (tw, 0, sizeof (*tw)); + tw->expired_timer_callback = expired_timer_callback; + if (timer_interval_in_seconds == 0.0) + { + clib_warning ("timer interval is zero"); + abort (); + } + tw->timer_interval = timer_interval_in_seconds; + tw->ticks_per_second = 1.0 / timer_interval_in_seconds; + + for (ring = 0; ring < TW_TIMER_WHEELS; ring++) + { + for (slot = 0; slot < TW_SLOTS_PER_RING; slot++) + { + ts = &tw->w[ring][slot]; + pool_get (tw->timers, t); + memset (t, 0xff, sizeof (*t)); + t->next = t->prev = t - tw->timers; + ts->head_index = t - tw->timers; + } + } +} + +/** + * @brief Free a tw timer wheel template instance + * @param tw_timer_wheel_t * tw timer wheel object pointer + */ +void TW (tw_timer_wheel_free) (TWT (tw_timer_wheel) * tw) +{ + int i, j; + tw_timer_wheel_slot_t *ts; + TWT (tw_timer) * head, *t; + u32 next_index; + + 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); + next_index = t->next; + pool_put (tw->timers, t); + } + pool_put (tw->timers, head); + } + } + memset (tw, 0, sizeof (*tw)); +} + +/** + * @brief Advance a tw timer wheel. Calls the expired timer callback + * 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) + */ +void TW (tw_timer_expire_timers) (TWT (tw_timer_wheel) * tw, f64 now) +{ + u32 nticks, i; + tw_timer_wheel_slot_t *ts; + TWT (tw_timer) * t, *head; + u32 fast_wheel_index; + u32 next_index; +#if TW_TIMER_WHEELS > 1 + u32 slow_wheel_index; +#endif + + /* Shouldn't happen */ + if (PREDICT_FALSE (now < tw->next_run_time)) + return; + + /* Number of ticks which have occurred */ + nticks = tw->ticks_per_second * (now - tw->last_run_time); + if (nticks == 0) + return; + + /* Remember when we ran, compute next runtime */ + tw->next_run_time = (now + tw->timer_interval); + tw->last_run_time = now; + + for (i = 0; i < nticks; i++) + { + fast_wheel_index = tw->current_index[TW_TIMER_RING_FAST]; + + /* + * If we've been around the fast ring once, + * process one slot in the slow ring before we handle + * the fast ring. + */ + if (PREDICT_FALSE (fast_wheel_index == TW_SLOTS_PER_RING)) + { + fast_wheel_index = tw->current_index[TW_TIMER_RING_FAST] = 0; + +#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]; + + ts = &tw->w[TW_TIMER_RING_SLOW][slow_wheel_index]; + + 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 fast ring */ + while (next_index != head - tw->timers) + { + t = pool_elt_at_index (tw->timers, next_index); + next_index = t->next; + + /* Remove from slow 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); + } +#endif + } + + /* Handle the fast ring */ + vec_reset_length (tw->expired_timer_handles); + + ts = &tw->w[TW_TIMER_RING_FAST][fast_wheel_index]; + + head = pool_elt_at_index (tw->timers, ts->head_index); + next_index = head->next; + + /* Make slot empty */ + head->next = head->prev = ts->head_index; + + /* Construct vector of expired timer handles to give the user */ + while (next_index != ts->head_index) + { + t = pool_elt_at_index (tw->timers, next_index); + next_index = t->next; + vec_add1 (tw->expired_timer_handles, t->user_handle); + pool_put (tw->timers, t); + } + + /* If any timers expired, tell the user */ + if (vec_len (tw->expired_timer_handles)) + tw->expired_timer_callback (tw->expired_timer_handles); + tw->current_index[TW_TIMER_RING_FAST]++; + tw->current_tick++; + } +} + +/* + * fd.io coding-style-patch-verification: ON + * + * Local Variables: + * eval: (c-set-style "gnu") + * End: + */ diff --git a/src/vppinfra/tw_timer_template.h b/src/vppinfra/tw_timer_template.h new file mode 100644 index 00000000000..cf15ab8a667 --- /dev/null +++ b/src/vppinfra/tw_timer_template.h @@ -0,0 +1,199 @@ +/* + * 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. + */ + +#ifndef TW_SUFFIX +#error do not include tw_timer_template.h directly +#endif + +#include <vppinfra/clib.h> +#include <vppinfra/pool.h> + +#ifndef _twt +#define _twt(a,b) a##b##_t +#define __twt(a,b) _twt(a,b) +#define TWT(a) __twt(a,TW_SUFFIX) + +#define _tw(a,b) a##b +#define __tw(a,b) _tw(a,b) +#define TW(a) __tw(a,TW_SUFFIX) +#endif + +/** @file + @brief TW timer template header file, do not compile directly + +Instantiation of tw_timer_template.h generates named structures to +implement specific timer wheel geometries. Choices include: number of +timer wheels (currently, 1 or 2), number of slots per ring (a power of +two), and the number of timers per "object handle". + +Internally, user object/timer handles are 32-bit integers, so if one +selects 16 timers/object (4 bits), the resulting timer wheel handle is +limited to 2**28 objects. + +Here are the specific settings required to generate a single 2048 slot +wheel which supports 2 timers per object: + + #define TW_TIMER_WHEELS 1 + #define TW_SLOTS_PER_RING 2048 + #define TW_RING_SHIFT 11 + #define TW_RING_MASK (TW_SLOTS_PER_RING -1) + #define TW_TIMERS_PER_OBJECT 2 + #define LOG2_TW_TIMERS_PER_OBJECT 1 + #define TW_SUFFIX _2t_1w_2048sl + +See tw_timer_2t_1w_2048sl.h for a complete +example. + +tw_timer_template.h is not intended to be #included directly. Client +codes can include multiple timer geometry header files, although +extreme caution would required to use the TW and TWT macros in such a +case. + +API usage example: + +Initialize a two-timer, single 2048-slot wheel w/ a 1-second +timer granularity: + + tw_timer_wheel_init_2t_1w_2048sl (&tm->single_wheel, + expired_timer_single_callback, + 1.0 / * timer interval * / ); + +Start a timer: + + handle = tw_timer_start_2t_1w_2048sl (&tm->single_wheel, elt_index, + [0 | 1] / * timer id * / , + expiration_time_in_u32_ticks); + +Stop a timer: + + tw_timer_stop_2t_1w_2048sl (&tm->single_wheel, handle); + +Expired timer callback: + + 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); + { + 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); + } + } + */ + +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; +#endif + /** user timer handle */ + u32 user_handle; +} TWT (tw_timer); + +/* + * These structures ar used by all geometries, + * so they need a private #include block... + */ +#ifndef __defined_tw_timer_wheel_slot__ +#define __defined_tw_timer_wheel_slot__ +typedef struct +{ + /** Listhead of timers which expire in this interval */ + u32 head_index; +} tw_timer_wheel_slot_t; +typedef enum +{ + /** Fast timer ring ID */ + TW_TIMER_RING_FAST, + /** Slow timer ring ID */ + TW_TIMER_RING_SLOW, +} tw_ring_index_t; +#endif /* __defined_tw_timer_wheel_slot__ */ + +typedef struct +{ + /** Timer pool */ + TWT (tw_timer) * timers; + + /** Next time the wheel should run */ + f64 next_run_time; + + /** Last time the wheel ran */ + f64 last_run_time; + + /** Timer ticks per second */ + f64 ticks_per_second; + + /** Timer interval, also needed to avoid fp divide in speed path */ + f64 timer_interval; + + /** current tick */ + u32 current_tick; + + /** current wheel indices */ + u32 current_index[TW_TIMER_WHEELS]; + + /** wheel arrays */ + tw_timer_wheel_slot_t w[TW_TIMER_WHEELS][TW_SLOTS_PER_RING]; + + /** expired timer callback, receives a vector of handles */ + void (*expired_timer_callback) (u32 * expired_timer_handles); + + /** vector of expired timers */ + u32 *expired_timer_handles; +} TWT (tw_timer_wheel); + +u32 TW (tw_timer_start) (TWT (tw_timer_wheel) * tw, + u32 pool_index, u32 timer_id, u32 interval); + +void TW (tw_timer_stop) (TWT (tw_timer_wheel) * tw, u32 handle); + +void TW (tw_timer_wheel_init) (TWT (tw_timer_wheel) * tw, + void *expired_timer_callback, + f64 timer_interval); + +void TW (tw_timer_wheel_free) (TWT (tw_timer_wheel) * tw); + +void TW (tw_timer_expire_timers) (TWT (tw_timer_wheel) * tw, f64 now); + +/* + * fd.io coding-style-patch-verification: ON + * + * Local Variables: + * eval: (c-set-style "gnu") + * End: + */ |