From 5c20a0131a6a2516c14d5ccfc6db90fd13ec8a33 Mon Sep 17 00:00:00 2001 From: Dave Barach Date: Tue, 13 Jun 2017 08:48:31 -0400 Subject: switch vlib process model to tw_timer_template timer impl Change-Id: I36bb47faea55a6fea7af7ee58d87d8f6dd28f93d Signed-off-by: Dave Barach --- src/vlib/main.c | 62 +++++++++++++++++---------- src/vlib/node.h | 15 ++++--- src/vlib/node_funcs.h | 28 +++++++------ src/vlib/unix/input.c | 61 +++++++++++---------------- src/vnet/lisp-cp/control.h | 1 + src/vppinfra/tw_timer_16t_1w_2048sl.h | 4 ++ src/vppinfra/tw_timer_16t_2w_512sl.h | 4 ++ src/vppinfra/tw_timer_1t_3w_1024sl_ov.h | 4 ++ src/vppinfra/tw_timer_2t_1w_2048sl.h | 4 ++ src/vppinfra/tw_timer_4t_3w_256sl.h | 4 ++ src/vppinfra/tw_timer_4t_3w_4sl_ov.h | 4 ++ src/vppinfra/tw_timer_template.c | 74 +++++++++++++++++++++++++++++++++ src/vppinfra/tw_timer_template.h | 9 ++++ 13 files changed, 197 insertions(+), 77 deletions(-) diff --git a/src/vlib/main.c b/src/vlib/main.c index 14f680e61fc..19d70232e6e 100644 --- a/src/vlib/main.c +++ b/src/vlib/main.c @@ -41,6 +41,7 @@ #include #include #include +#include #include @@ -1341,9 +1342,16 @@ dispatch_process (vlib_main_t * vm, p->suspended_process_frame_index = pf - nm->suspended_process_frames; if (p->flags & VLIB_PROCESS_IS_SUSPENDED_WAITING_FOR_CLOCK) - timing_wheel_insert (&nm->timing_wheel, p->resume_cpu_time, - vlib_timing_wheel_data_set_suspended_process - (node->runtime_index)); + { + TWT (tw_timer_wheel) * tw = + (TWT (tw_timer_wheel) *) nm->timing_wheel; + p->stop_timer_handle = + TW (tw_timer_start) (tw, + vlib_timing_wheel_data_set_suspended_process + (node->runtime_index) /* [sic] pool idex */ , + 0 /* timer_id */ , + p->resume_clock_interval); + } } else p->flags &= ~VLIB_PROCESS_IS_RUNNING; @@ -1416,9 +1424,14 @@ dispatch_suspended_process (vlib_main_t * vm, n_vectors = 0; p->n_suspends += 1; if (p->flags & VLIB_PROCESS_IS_SUSPENDED_WAITING_FOR_CLOCK) - timing_wheel_insert (&nm->timing_wheel, p->resume_cpu_time, - vlib_timing_wheel_data_set_suspended_process - (node->runtime_index)); + { + p->stop_timer_handle = + TW (tw_timer_start) ((TWT (tw_timer_wheel) *) nm->timing_wheel, + vlib_timing_wheel_data_set_suspended_process + (node->runtime_index) /* [sic] pool idex */ , + 0 /* timer_id */ , + p->resume_clock_interval); + } } else { @@ -1465,17 +1478,6 @@ vlib_main_or_worker_loop (vlib_main_t * vm, int is_main) else cpu_time_now = clib_cpu_time_now (); - /* Arrange for first level of timing wheel to cover times we care - most about. */ - if (is_main) - { - nm->timing_wheel.min_sched_time = 10e-6; - nm->timing_wheel.max_sched_time = 10e-3; - timing_wheel_init (&nm->timing_wheel, - cpu_time_now, vm->clib_time.clocks_per_second); - vec_alloc (nm->data_from_advancing_timing_wheel, 32); - } - /* Pre-allocate interupt runtime indices and lock. */ vec_alloc (nm->pending_interrupt_node_runtime_indices, 32); vec_alloc (last_node_runtime_indices, 32); @@ -1561,12 +1563,15 @@ vlib_main_or_worker_loop (vlib_main_t * vm, int is_main) if (is_main) { /* Check if process nodes have expired from timing wheel. */ - nm->data_from_advancing_timing_wheel - = timing_wheel_advance (&nm->timing_wheel, cpu_time_now, - nm->data_from_advancing_timing_wheel, - &nm->cpu_time_next_process_ready); + ASSERT (nm->data_from_advancing_timing_wheel != 0); + + nm->data_from_advancing_timing_wheel = + TW (tw_timer_expire_timers_vec) + ((TWT (tw_timer_wheel) *) nm->timing_wheel, vlib_time_now (vm), + nm->data_from_advancing_timing_wheel); ASSERT (nm->data_from_advancing_timing_wheel != 0); + if (PREDICT_FALSE (_vec_len (nm->data_from_advancing_timing_wheel) > 0)) { @@ -1612,8 +1617,6 @@ vlib_main_or_worker_loop (vlib_main_t * vm, int is_main) dispatch_suspended_process (vm, di, cpu_time_now); } } - - /* Reset vector. */ _vec_len (nm->data_from_advancing_timing_wheel) = 0; } } @@ -1692,6 +1695,7 @@ int vlib_main (vlib_main_t * volatile vm, unformat_input_t * input) { clib_error_t *volatile error; + vlib_node_main_t *nm = &vm->node_main; vm->queue_signal_callback = dummy_queue_signal_callback; @@ -1746,6 +1750,18 @@ vlib_main (vlib_main_t * volatile vm, unformat_input_t * input) VLIB_BUFFER_DEFAULT_FREE_LIST_BYTES, "default"); + nm->timing_wheel = clib_mem_alloc_aligned (sizeof (TWT (tw_timer_wheel)), + CLIB_CACHE_LINE_BYTES); + + vec_validate (nm->data_from_advancing_timing_wheel, 10); + _vec_len (nm->data_from_advancing_timing_wheel) = 0; + + /* Create the process timing wheel */ + TW (tw_timer_wheel_init) ((TWT (tw_timer_wheel) *) nm->timing_wheel, + 0 /* no callback */ , + 10e-6 /* timer period 10us */ , + ~0 /* max expirations per call */ ); + switch (clib_setjmp (&vm->main_loop_exit, VLIB_MAIN_LOOP_EXIT_NONE)) { case VLIB_MAIN_LOOP_EXIT_NONE: diff --git a/src/vlib/node.h b/src/vlib/node.h index 906d795fe23..77914272bbc 100644 --- a/src/vlib/node.h +++ b/src/vlib/node.h @@ -43,7 +43,6 @@ #include #include #include -#include #include /* for vlib_trace_filter_t */ /* Forward declaration. */ @@ -542,8 +541,14 @@ typedef struct /* Pool of currently valid event types. */ vlib_process_event_type_t *event_type_pool; - /* When suspending saves cpu cycle counter when process is to be resumed. */ - u64 resume_cpu_time; + /* + * When suspending saves clock time (10us ticks) when process + * is to be resumed. + */ + u64 resume_clock_interval; + + /* Handle from timer code, to cancel an unexpired timer */ + u32 stop_timer_handle; /* Default output function and its argument for any CLI outputs within the process. */ @@ -664,7 +669,7 @@ typedef struct vlib_pending_frame_t *pending_frames; /* Timing wheel for scheduling time-based node dispatch. */ - timing_wheel_t timing_wheel; + void *timing_wheel; vlib_signal_timed_event_data_t *signal_timed_event_data_pool; @@ -672,7 +677,7 @@ typedef struct u32 *data_from_advancing_timing_wheel; /* CPU time of next process to be ready on timing wheel. */ - u64 cpu_time_next_process_ready; + f64 time_next_process_ready; /* Vector of process nodes. One for each node of type VLIB_NODE_TYPE_PROCESS. */ diff --git a/src/vlib/node_funcs.h b/src/vlib/node_funcs.h index 4d7cc1928f3..d6588a74ba1 100644 --- a/src/vlib/node_funcs.h +++ b/src/vlib/node_funcs.h @@ -46,6 +46,7 @@ #define included_vlib_node_funcs_h #include +#include /** \brief Get vlib node by index. @warning This function will ASSERT if @c i is out of range. @@ -428,14 +429,14 @@ vlib_current_process (vlib_main_t * vm) return vlib_get_current_process (vm)->node_runtime.node_index; } -/** Returns TRUE if a process suspend time is less than 1us +/** Returns TRUE if a process suspend time is less than 10us @param dt - remaining poll time in seconds - @returns 1 if dt < 1e-6, 0 otherwise + @returns 1 if dt < 10e-6, 0 otherwise */ always_inline uword vlib_process_suspend_time_is_zero (f64 dt) { - return dt < 1e-6; + return dt < 10e-6; } /** Suspend a vlib cooperative multi-tasking thread for a period of time @@ -450,7 +451,6 @@ vlib_process_suspend (vlib_main_t * vm, f64 dt) uword r; vlib_node_main_t *nm = &vm->node_main; vlib_process_t *p = vec_elt (nm->processes, nm->current_process_index); - u64 dt_cpu = dt * vm->clib_time.clocks_per_second; if (vlib_process_suspend_time_is_zero (dt)) return VLIB_PROCESS_RESUME_LONGJMP_RESUME; @@ -459,7 +459,8 @@ vlib_process_suspend (vlib_main_t * vm, f64 dt) r = clib_setjmp (&p->resume_longjmp, VLIB_PROCESS_RESUME_LONGJMP_SUSPEND); if (r == VLIB_PROCESS_RESUME_LONGJMP_SUSPEND) { - p->resume_cpu_time = clib_cpu_time_now () + dt_cpu; + /* expiration time in 10us ticks */ + p->resume_clock_interval = dt * 1e5; clib_longjmp (&p->return_longjmp, VLIB_PROCESS_RETURN_LONGJMP_SUSPEND); } @@ -718,8 +719,7 @@ vlib_process_wait_for_event_or_clock (vlib_main_t * vm, f64 dt) r = clib_setjmp (&p->resume_longjmp, VLIB_PROCESS_RESUME_LONGJMP_SUSPEND); if (r == VLIB_PROCESS_RESUME_LONGJMP_SUSPEND) { - p->resume_cpu_time = (clib_cpu_time_now () - + (dt * vm->clib_time.clocks_per_second)); + p->resume_clock_interval = dt * 1e5; clib_longjmp (&p->return_longjmp, VLIB_PROCESS_RETURN_LONGJMP_SUSPEND); } @@ -834,7 +834,8 @@ vlib_process_signal_event_helper (vlib_node_main_t * nm, p->flags = p_flags | VLIB_PROCESS_RESUME_PENDING; vec_add1 (nm->data_from_advancing_timing_wheel, x); if (delete_from_wheel) - timing_wheel_delete (&nm->timing_wheel, x); + TW (tw_timer_stop) ((TWT (tw_timer_wheel) *) nm->timing_wheel, + p->stop_timer_handle); } return data_to_be_written_by_caller; @@ -895,7 +896,6 @@ vlib_process_signal_event_at_time (vlib_main_t * vm, else { vlib_signal_timed_event_data_t *te; - u64 dt_cpu = dt * vm->clib_time.clocks_per_second; pool_get_aligned (nm->signal_timed_event_data_pool, te, sizeof (te[0])); @@ -911,10 +911,12 @@ vlib_process_signal_event_at_time (vlib_main_t * vm, te->process_node_index = n->runtime_index; te->event_type_index = t; - timing_wheel_insert (&nm->timing_wheel, clib_cpu_time_now () + dt_cpu, - vlib_timing_wheel_data_set_timed_event (te - - nm-> - signal_timed_event_data_pool)); + p->stop_timer_handle = + TW (tw_timer_start) ((TWT (tw_timer_wheel) *) nm->timing_wheel, + vlib_timing_wheel_data_set_timed_event + (te - nm->signal_timed_event_data_pool), + 0 /* timer_id */ , + (vlib_time_now (vm) + dt) * 1e5); /* Inline data big enough to hold event? */ if (te->n_data_bytes < sizeof (te->inline_event_data)) diff --git a/src/vlib/unix/input.c b/src/vlib/unix/input.c index 73783d13c89..515dae94811 100644 --- a/src/vlib/unix/input.c +++ b/src/vlib/unix/input.c @@ -40,6 +40,7 @@ #include #include #include +#include /* FIXME autoconf */ #define HAVE_LINUX_EPOLL @@ -113,56 +114,44 @@ linux_epoll_input (vlib_main_t * vm, { vlib_node_main_t *nm = &vm->node_main; - u64 t = nm->cpu_time_next_process_ready; + u32 ticks_until_expiration; f64 timeout; - int timeout_ms, max_timeout_ms = 10; + int timeout_ms = 0, max_timeout_ms = 10; f64 vector_rate = vlib_last_vectors_per_main_loop (vm); - if (t == ~0ULL) + /* If we're not working very hard, decide how long to sleep */ + if (vector_rate < 2 && vm->api_queue_nonempty == 0 + && nm->input_node_counts_by_state[VLIB_NODE_STATE_POLLING] == 0) { - timeout = 10e-3; - timeout_ms = max_timeout_ms; - } - else - { - timeout = - (((i64) t - (i64) clib_cpu_time_now ()) - * vm->clib_time.seconds_per_clock) - /* subtract off some slop time */ - 50e-6; + ticks_until_expiration = TW (tw_timer_first_expires_in_ticks) + ((TWT (tw_timer_wheel) *) nm->timing_wheel); - if (timeout < 1e-3) + /* Nothing on the fast wheel, sleep 10ms */ + if (ticks_until_expiration == TW_SLOTS_PER_RING) { - /* We have event happenning in less than 1 ms so - don't allow epoll to wait */ - timeout_ms = 0; + timeout = 10e-3; + timeout_ms = max_timeout_ms; } else { - timeout_ms = timeout * 1e3; - - /* Must be between 1 and 10 ms. */ - timeout_ms = clib_max (1, timeout_ms); - timeout_ms = clib_min (max_timeout_ms, timeout_ms); + timeout = (f64) ticks_until_expiration *1e-5; + if (timeout < 1e-3) + timeout_ms = 0; + else + { + timeout_ms = timeout * 1e3; + /* Must be between 1 and 10 ms. */ + timeout_ms = clib_max (1, timeout_ms); + timeout_ms = clib_min (max_timeout_ms, timeout_ms); + } } + node->input_main_loops_per_call = 0; } - - /* If we still have input nodes polling (e.g. vnet packet generator) - don't sleep. */ - if (nm->input_node_counts_by_state[VLIB_NODE_STATE_POLLING] > 0) - timeout_ms = 0; - - /* - * When busy: don't wait & only epoll for input - * every 1024 times through main loop. - */ - if (vector_rate > 1 || vm->api_queue_nonempty) + else /* busy */ { - timeout_ms = 0; + /* Don't come back for a respectable number of dispatch cycles */ node->input_main_loops_per_call = 1024; } - else - /* We're not busy; go to sleep for a while. */ - node->input_main_loops_per_call = 0; /* Allow any signal to wakeup our sleep. */ { diff --git a/src/vnet/lisp-cp/control.h b/src/vnet/lisp-cp/control.h index 577035c4f42..0e63b3c7454 100644 --- a/src/vnet/lisp-cp/control.h +++ b/src/vnet/lisp-cp/control.h @@ -19,6 +19,7 @@ #include #include #include +#include #define NUMBER_OF_RETRIES 1 #define PENDING_MREQ_EXPIRATION_TIME 3.0 /* seconds */ diff --git a/src/vppinfra/tw_timer_16t_1w_2048sl.h b/src/vppinfra/tw_timer_16t_1w_2048sl.h index 6edef17bf60..66cf7d37b68 100644 --- a/src/vppinfra/tw_timer_16t_1w_2048sl.h +++ b/src/vppinfra/tw_timer_16t_1w_2048sl.h @@ -25,6 +25,8 @@ #undef LOG2_TW_TIMERS_PER_OBJECT #undef TW_SUFFIX #undef TW_OVERFLOW_VECTOR +#undef TW_FAST_WHEEL_BITMAP +#undef TW_TIMER_ALLOW_DUPLICATE_STOP #define TW_TIMER_WHEELS 1 #define TW_SLOTS_PER_RING 2048 @@ -33,6 +35,8 @@ #define TW_TIMERS_PER_OBJECT 16 #define LOG2_TW_TIMERS_PER_OBJECT 4 #define TW_SUFFIX _16t_1w_2048sl +#define TW_FAST_WHEEL_BITMAP 0 +#define TW_TIMER_ALLOW_DUPLICATE_STOP 0 #include diff --git a/src/vppinfra/tw_timer_16t_2w_512sl.h b/src/vppinfra/tw_timer_16t_2w_512sl.h index 2497b31c1ad..00587b8eeda 100644 --- a/src/vppinfra/tw_timer_16t_2w_512sl.h +++ b/src/vppinfra/tw_timer_16t_2w_512sl.h @@ -25,6 +25,8 @@ #undef LOG2_TW_TIMERS_PER_OBJECT #undef TW_SUFFIX #undef TW_OVERFLOW_VECTOR +#undef TW_FAST_WHEEL_BITMAP +#undef TW_TIMER_ALLOW_DUPLICATE_STOP #define TW_TIMER_WHEELS 2 #define TW_SLOTS_PER_RING 512 @@ -33,6 +35,8 @@ #define TW_TIMERS_PER_OBJECT 16 #define LOG2_TW_TIMERS_PER_OBJECT 4 #define TW_SUFFIX _16t_2w_512sl +#define TW_FAST_WHEEL_BITMAP 0 +#define TW_TIMER_ALLOW_DUPLICATE_STOP 0 #include diff --git a/src/vppinfra/tw_timer_1t_3w_1024sl_ov.h b/src/vppinfra/tw_timer_1t_3w_1024sl_ov.h index 7327f87b900..e5e4cc19a90 100644 --- a/src/vppinfra/tw_timer_1t_3w_1024sl_ov.h +++ b/src/vppinfra/tw_timer_1t_3w_1024sl_ov.h @@ -25,6 +25,8 @@ #undef LOG2_TW_TIMERS_PER_OBJECT #undef TW_SUFFIX #undef TW_OVERFLOW_VECTOR +#undef TW_FAST_WHEEL_BITMAP +#undef TW_TIMER_ALLOW_DUPLICATE_STOP #define TW_TIMER_WHEELS 3 #define TW_SLOTS_PER_RING 1024 @@ -34,6 +36,8 @@ #define LOG2_TW_TIMERS_PER_OBJECT 0 #define TW_SUFFIX _1t_3w_1024sl_ov #define TW_OVERFLOW_VECTOR 1 +#define TW_FAST_WHEEL_BITMAP 1 +#define TW_TIMER_ALLOW_DUPLICATE_STOP 1 #include diff --git a/src/vppinfra/tw_timer_2t_1w_2048sl.h b/src/vppinfra/tw_timer_2t_1w_2048sl.h index 33b74405fcc..98b548b39d4 100644 --- a/src/vppinfra/tw_timer_2t_1w_2048sl.h +++ b/src/vppinfra/tw_timer_2t_1w_2048sl.h @@ -25,6 +25,8 @@ #undef LOG2_TW_TIMERS_PER_OBJECT #undef TW_SUFFIX #undef TW_OVERFLOW_VECTOR +#undef TW_FAST_WHEEL_BITMAP +#undef TW_TIMER_ALLOW_DUPLICATE_STOP #define TW_TIMER_WHEELS 1 #define TW_SLOTS_PER_RING 2048 @@ -33,6 +35,8 @@ #define TW_TIMERS_PER_OBJECT 2 #define LOG2_TW_TIMERS_PER_OBJECT 1 #define TW_SUFFIX _2t_1w_2048sl +#define TW_FAST_WHEEL_BITMAP 0 +#define TW_TIMER_ALLOW_DUPLICATE_STOP 0 #include diff --git a/src/vppinfra/tw_timer_4t_3w_256sl.h b/src/vppinfra/tw_timer_4t_3w_256sl.h index 89adb7a2464..07203de8742 100644 --- a/src/vppinfra/tw_timer_4t_3w_256sl.h +++ b/src/vppinfra/tw_timer_4t_3w_256sl.h @@ -25,6 +25,8 @@ #undef LOG2_TW_TIMERS_PER_OBJECT #undef TW_SUFFIX #undef TW_OVERFLOW_VECTOR +#undef TW_FAST_WHEEL_BITMAP +#undef TW_TIMER_ALLOW_DUPLICATE_STOP #define TW_TIMER_WHEELS 3 #define TW_SLOTS_PER_RING 256 @@ -33,6 +35,8 @@ #define TW_TIMERS_PER_OBJECT 4 #define LOG2_TW_TIMERS_PER_OBJECT 2 #define TW_SUFFIX _4t_3w_256sl +#define TW_FAST_WHEEL_BITMAP 0 +#define TW_TIMER_ALLOW_DUPLICATE_STOP 0 #include diff --git a/src/vppinfra/tw_timer_4t_3w_4sl_ov.h b/src/vppinfra/tw_timer_4t_3w_4sl_ov.h index 0f76164d069..20a01d05e7d 100644 --- a/src/vppinfra/tw_timer_4t_3w_4sl_ov.h +++ b/src/vppinfra/tw_timer_4t_3w_4sl_ov.h @@ -25,6 +25,8 @@ #undef LOG2_TW_TIMERS_PER_OBJECT #undef TW_SUFFIX #undef TW_OVERFLOW_VECTOR +#undef TW_FAST_WHEEL_BITMAP +#undef TW_TIMER_ALLOW_DUPLICATE_STOP #define TW_TIMER_WHEELS 3 #define TW_SLOTS_PER_RING 4 @@ -34,6 +36,8 @@ #define LOG2_TW_TIMERS_PER_OBJECT 2 #define TW_SUFFIX _4t_3w_4sl_ov #define TW_OVERFLOW_VECTOR 1 +#define TW_FAST_WHEEL_BITMAP 0 +#define TW_TIMER_ALLOW_DUPLICATE_STOP 0 #include diff --git a/src/vppinfra/tw_timer_template.c b/src/vppinfra/tw_timer_template.c index 9253488ceac..c0a9685aa82 100644 --- a/src/vppinfra/tw_timer_template.c +++ b/src/vppinfra/tw_timer_template.c @@ -204,6 +204,11 @@ TW (tw_timer_start) (TWT (tw_timer_wheel) * tw, u32 pool_index, u32 timer_id, ts = &tw->w[TW_TIMER_RING_FAST][fast_ring_offset]; timer_addhead (tw->timers, ts->head_index, t - tw->timers); + +#if TW_FAST_WHEEL_BITMAP + tw->fast_slot_bitmap = clib_bitmap_set (tw->fast_slot_bitmap, + fast_ring_offset, 1); +#endif return t - tw->timers; } @@ -251,6 +256,16 @@ void TW (tw_timer_stop) (TWT (tw_timer_wheel) * tw, u32 handle) { TWT (tw_timer) * t; +#if TW_TIMER_ALLOW_DUPLICATE_STOP + /* + * A vlib process may have its timer expire, and receive + * an event before the expiration is processed. + * That results in a duplicate tw_timer_stop. + */ + if (pool_is_free_index (tw->timers, handle)) + return; +#endif + t = pool_elt_at_index (tw->timers, handle); /* in case of idiotic handle (e.g. passing a listhead index) */ @@ -481,6 +496,11 @@ static inline { ts = &tw->w[TW_TIMER_RING_FAST][t->fast_ring_offset]; timer_addhead (tw->timers, ts->head_index, t - tw->timers); +#if TW_FAST_WHEEL_BITMAP + tw->fast_slot_bitmap = + clib_bitmap_set (tw->fast_slot_bitmap, + t->fast_ring_offset, 1); +#endif } } } @@ -523,6 +543,11 @@ static inline { ts = &tw->w[TW_TIMER_RING_FAST][t->fast_ring_offset]; timer_addhead (tw->timers, ts->head_index, t - tw->timers); +#if TW_FAST_WHEEL_BITMAP + tw->fast_slot_bitmap = + clib_bitmap_set (tw->fast_slot_bitmap, + t->fast_ring_offset, 1); +#endif } else /* typical case */ { @@ -569,6 +594,11 @@ static inline /* 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); +#if TW_FAST_WHEEL_BITMAP + tw->fast_slot_bitmap = + clib_bitmap_set (tw->fast_slot_bitmap, + t->fast_ring_offset, 1); +#endif } } } @@ -604,6 +634,12 @@ static inline } tw->expired_timer_handles = callback_vector; } + +#if TW_FAST_WHEEL_BITMAP + tw->fast_slot_bitmap = clib_bitmap_set (tw->fast_slot_bitmap, + fast_wheel_index, 0); +#endif + tw->current_tick++; fast_wheel_index++; tw->current_index[TW_TIMER_RING_FAST] = fast_wheel_index; @@ -642,6 +678,44 @@ u32 *TW (tw_timer_expire_timers_vec) (TWT (tw_timer_wheel) * tw, f64 now, return TW (tw_timer_expire_timers_internal) (tw, now, vec); } +#if TW_FAST_WHEEL_BITMAP +/** Returns an approximation to the first timer expiration in + * timer-ticks from "now". To avoid wasting an unjustifiable + * amount of time on the problem, we maintain an approximate fast-wheel slot + * occupancy bitmap. We don't worry about clearing fast wheel bits + * when timers are removed from fast wheel slots. + */ + +u32 TW (tw_timer_first_expires_in_ticks) (TWT (tw_timer_wheel) * tw) +{ + u32 first_expiring_index, fast_ring_index; + i32 delta; + + if (clib_bitmap_is_zero (tw->fast_slot_bitmap)) + return TW_SLOTS_PER_RING; + + fast_ring_index = tw->current_index[TW_TIMER_RING_FAST]; + if (fast_ring_index == TW_SLOTS_PER_RING) + fast_ring_index = 0; + + first_expiring_index = clib_bitmap_next_set (tw->fast_slot_bitmap, + fast_ring_index); + if (first_expiring_index == ~0 && fast_ring_index != 0) + first_expiring_index = clib_bitmap_first_set (tw->fast_slot_bitmap); + + ASSERT (first_expiring_index != ~0); + + delta = (i32) first_expiring_index - (i32) fast_ring_index; + if (delta < 0) + delta += TW_SLOTS_PER_RING; + + ASSERT (delta >= 0); + + return (u32) delta; +} + +#endif + /* * fd.io coding-style-patch-verification: ON * diff --git a/src/vppinfra/tw_timer_template.h b/src/vppinfra/tw_timer_template.h index 76755609451..0404e3f4715 100644 --- a/src/vppinfra/tw_timer_template.h +++ b/src/vppinfra/tw_timer_template.h @@ -19,6 +19,7 @@ #include #include +#include #ifndef _twt #define _twt(a,b) a##b##_t @@ -202,6 +203,11 @@ typedef struct tw_timer_wheel_slot_t overflow; #endif +#if TW_FAST_WHEEL_BITMAP > 0 + /** Fast wheel slot occupancy bitmap */ + uword *fast_slot_bitmap; +#endif + /** expired timer callback, receives a vector of handles */ void (*expired_timer_callback) (u32 * expired_timer_handles); @@ -226,6 +232,9 @@ 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_vec) (TWT (tw_timer_wheel) * tw, f64 now, u32 * vec); +#if TW_FAST_WHEEL_BITMAP +u32 TW (tw_timer_first_expires_in_ticks) (TWT (tw_timer_wheel) * tw); +#endif /* * fd.io coding-style-patch-verification: ON -- cgit 1.2.3-korg