21 #if TW_START_STOP_TRACE_SIZE > 0 23 void TW (tw_timer_trace) (
TWT (tw_timer_wheel) * tw,
u32 timer_id,
24 u32 pool_index,
u32 handle)
26 TWT (
trace) * t = &tw->traces[tw->trace_index];
28 t->timer_id = timer_id;
29 t->pool_index = pool_index;
33 if (tw->trace_index == TW_START_STOP_TRACE_SIZE)
40 void TW (tw_search_trace) (
TWT (tw_timer_wheel) * tw,
u32 handle)
48 start_pos = tw->trace_index;
50 start_pos = TW_START_STOP_TRACE_SIZE - 1;
54 for (i = start_pos; i > 0; i--)
57 if (t->handle == handle)
71 fformat (stderr,
"handle 0x%x (%d) %s at trace %d\n",
72 handle, handle, s, i);
75 if (tw->trace_wrapped > 0)
77 for (i = TW_START_STOP_TRACE_SIZE; i >= tw->trace_index; i--)
80 if (t->handle == handle)
94 fformat (stderr,
"handle 0x%x (%d) %s at trace %d\n",
95 handle, handle, s, i);
108 #if LOG2_TW_TIMERS_PER_OBJECT > 0 122 TWT (tw_timer) * old_first;
124 TWT (tw_timer) *
new;
130 head->next = head->prev = new_index;
131 new->next =
new->prev = head_index;
135 old_first_index = head->next;
138 new->next = old_first_index;
139 new->prev = old_first->prev;
140 old_first->prev = new_index;
141 head->next = new_index;
147 TWT (tw_timer) * next_elt, *prev_elt;
149 ASSERT (elt->user_handle != ~0);
154 next_elt->prev = elt->prev;
155 prev_elt->next = elt->next;
157 elt->prev = elt->next = ~0;
163 #if TW_TIMER_WHEELS > 1 164 u16 slow_ring_offset;
167 #if TW_TIMER_WHEELS > 2 168 u16 glacier_ring_offset;
170 #if TW_OVERFLOW_VECTOR > 0 171 u64 interval_plus_time_to_wrap, triple_wrap_mask;
173 u16 fast_ring_offset;
177 #if TW_TIMER_WHEELS > 2 178 #if TW_OVERFLOW_VECTOR > 0 186 interval_plus_time_to_wrap =
187 interval + (tw->current_tick & triple_wrap_mask);
188 if ((interval_plus_time_to_wrap >= 1 << (3 *
TW_RING_SHIFT)))
190 t->expiration_time = tw->current_tick + interval;
193 #if TW_START_STOP_TRACE_SIZE > 0 194 TW (tw_timer_trace) (tw, timer_id, user_id, t - tw->timers);
204 #if TW_TIMER_WHEELS > 1 220 #if TW_TIMER_WHEELS > 1 229 #if TW_TIMER_WHEELS > 2 230 glacier_ring_offset +=
235 #if TW_TIMER_WHEELS > 2 236 if (glacier_ring_offset !=
240 t->slow_ring_offset = slow_ring_offset;
241 t->fast_ring_offset = fast_ring_offset;
246 #if TW_START_STOP_TRACE_SIZE > 0 247 TW (tw_timer_trace) (tw, timer_id, user_id, t - tw->timers);
253 #if TW_TIMER_WHEELS > 1 255 if (slow_ring_offset !=
259 t->fast_ring_offset = fast_ring_offset;
264 #if TW_START_STOP_TRACE_SIZE > 0 265 TW (tw_timer_trace) (tw, timer_id, user_id, t - tw->timers);
278 #if TW_FAST_WHEEL_BITMAP 280 fast_ring_offset, 1);
282 #if TW_START_STOP_TRACE_SIZE > 0 283 TW (tw_timer_trace) (tw, timer_id, user_id, t - tw->timers);
309 return t - tw->timers;
312 #if TW_TIMER_SCAN_FOR_HANDLE > 0 313 int TW (scan_for_handle) (
TWT (tw_timer_wheel) * tw,
u32 handle)
317 TWT (tw_timer) * t, *head;
327 next_index = head->next;
332 if (next_index == handle)
339 next_index = t->next;
356 #if TW_TIMER_ALLOW_DUPLICATE_STOP 365 #if TW_START_STOP_TRACE_SIZE > 0 366 TW (tw_timer_trace) (tw, ~0, ~0, handle);
372 ASSERT (t->user_handle != ~0);
408 void *expired_timer_callback,
409 f64 timer_interval_in_seconds,
u32 max_expirations)
415 tw->expired_timer_callback = expired_timer_callback;
416 tw->max_expirations = max_expirations;
417 if (timer_interval_in_seconds == 0.0)
422 tw->timer_interval = timer_interval_in_seconds;
423 tw->ticks_per_second = 1.0 / timer_interval_in_seconds;
424 tw->first_expires_tick = ~0ULL;
427 _vec_len (tw->expired_timer_handles) = 0;
433 ts = &tw->w[ring][
slot];
436 t->next = t->prev = t - tw->timers;
441 #if TW_OVERFLOW_VECTOR > 0 445 t->next = t->prev = t - tw->timers;
458 TWT (tw_timer) * head, *t;
467 next_index = head->next;
472 next_index = t->next;
479 #if TW_OVERFLOW_VECTOR > 0 482 next_index = head->next;
487 next_index = t->next;
506 u32 * callback_vector_arg)
510 TWT (tw_timer) * t, *head;
511 u32 *callback_vector;
512 u32 fast_wheel_index;
514 u32 slow_wheel_index __attribute__ ((unused));
515 u32 glacier_wheel_index __attribute__ ((unused));
519 return callback_vector_arg;
522 nticks = tw->ticks_per_second * (now - tw->last_run_time);
524 return callback_vector_arg;
527 tw->next_run_time = (now + tw->timer_interval);
529 if (callback_vector_arg == 0)
531 _vec_len (tw->expired_timer_handles) = 0;
532 callback_vector = tw->expired_timer_handles;
535 callback_vector = callback_vector_arg;
537 for (i = 0; i < nticks; i++)
545 #if TW_OVERFLOW_VECTOR > 0 552 u32 new_glacier_ring_offset, new_slow_ring_offset;
553 u32 new_fast_ring_offset;
557 next_index = head->next;
563 while (next_index != head - tw->timers)
566 next_index = t->next;
569 t->next = t->prev = ~0;
571 ASSERT (t->expiration_time >= tw->current_tick);
573 interval = t->expiration_time - tw->current_tick;
585 interval -= (new_glacier_ring_offset << (2 *
TW_RING_SHIFT));
591 t->slow_ring_offset = new_slow_ring_offset;
592 t->fast_ring_offset = new_fast_ring_offset;
596 t->fast_ring_offset == 0 &&
597 new_glacier_ring_offset == 0))
599 vec_add1 (callback_vector, t->user_handle);
600 #if TW_START_STOP_TRACE_SIZE > 0 601 TW (tw_timer_trace) (tw, 0xfe, t->user_handle,
607 else if (new_glacier_ring_offset)
613 else if (t->slow_ring_offset)
624 #if TW_FAST_WHEEL_BITMAP 625 tw->fast_slot_bitmap =
627 t->fast_ring_offset, 1);
634 #if TW_TIMER_WHEELS > 2 645 next_index = head->next;
651 while (next_index != head - tw->timers)
654 next_index = t->next;
657 t->next = t->prev = ~0;
661 t->fast_ring_offset == 0))
663 vec_add1 (callback_vector, t->user_handle);
664 #if TW_START_STOP_TRACE_SIZE > 0 665 TW (tw_timer_trace) (tw, 0xfe, t->user_handle,
675 #if TW_FAST_WHEEL_BITMAP 676 tw->fast_slot_bitmap =
678 t->fast_ring_offset, 1);
691 #if TW_TIMER_WHEELS > 1 701 next_index = head->next;
707 while (next_index != head - tw->timers)
710 next_index = t->next;
713 t->next = t->prev = ~0;
718 vec_add1 (callback_vector, t->user_handle);
719 #if TW_START_STOP_TRACE_SIZE > 0 720 TW (tw_timer_trace) (tw, 0xfe, t->user_handle,
730 #if TW_FAST_WHEEL_BITMAP 731 tw->fast_slot_bitmap =
733 t->fast_ring_offset, 1);
745 next_index = head->next;
754 next_index = t->next;
755 vec_add1 (callback_vector, t->user_handle);
756 #if TW_START_STOP_TRACE_SIZE > 0 757 TW (tw_timer_trace) (tw, 0xfe, t->user_handle, t - tw->timers);
763 if (callback_vector_arg == 0 &&
vec_len (callback_vector))
766 if (tw->expired_timer_callback)
768 tw->expired_timer_callback (callback_vector);
771 tw->expired_timer_handles = callback_vector;
774 #if TW_FAST_WHEEL_BITMAP 776 fast_wheel_index, 0);
783 #if TW_TIMER_WHEELS > 1 789 #if TW_TIMER_WHEELS > 2 791 glacier_wheel_index++;
795 if (
vec_len (callback_vector) >= tw->max_expirations)
799 if (callback_vector_arg == 0)
800 tw->expired_timer_handles = callback_vector;
802 tw->last_run_time += i * tw->timer_interval;
803 return callback_vector;
817 #if TW_FAST_WHEEL_BITMAP 825 u32 TW (tw_timer_first_expires_in_ticks) (
TWT (tw_timer_wheel) * tw)
827 u32 first_expiring_index, fast_ring_index;
830 #if TW_TIMER_WHEELS > 1 835 first_expiring_index = clib_bitmap_next_set (tw->fast_slot_bitmap,
837 if (first_expiring_index == ~0)
849 first_expiring_index = clib_bitmap_next_set (tw->fast_slot_bitmap,
851 if (first_expiring_index == ~0 && fast_ring_index != 0)
855 ASSERT (first_expiring_index != ~0);
857 delta = (
i32) first_expiring_index - (
i32) fast_ring_index;
#define vec_validate(V, I)
Make sure vector is long enough for given index (no header, unspecified alignment) ...
void TW() tw_timer_wheel_init(TWT(tw_timer_wheel) *tw, void *expired_timer_callback, f64 timer_interval_in_seconds, u32 max_expirations)
Initialize a tw timer wheel template instance.
static vlib_cli_command_t trace
(constructor) VLIB_CLI_COMMAND (trace)
#define TW_TIMERS_PER_OBJECT
clib_memset(h->entries, 0, sizeof(h->entries[0]) *entries)
#define vec_add1(V, E)
Add 1 element to end of vector (unspecified alignment).
static uword * clib_bitmap_set(uword *ai, uword i, uword value)
Sets the ith bit of a bitmap to new_value Removes trailing zeros from the bitmap. ...
#define pool_get(P, E)
Allocate an object E from a pool P (unspecified alignment).
#define vec_reset_length(v)
Reset vector length to zero NULL-pointer tolerant.
void TW() tw_timer_wheel_free(TWT(tw_timer_wheel) *tw)
Free a tw timer wheel template instance.
static void timer_addhead(TWT(tw_timer) *pool, u32 head_index, u32 new_index)
static uword clib_bitmap_is_zero(uword *ai)
predicate function; is an entire bitmap empty?
#define LOG2_TW_TIMERS_PER_OBJECT
int TW() tw_timer_handle_is_free(TWT(tw_timer_wheel) *tw, u32 handle)
#define pool_elt_at_index(p, i)
Returns pointer to element at given index.
static void timer_add(TWT(tw_timer_wheel) *tw, TWT(tw_timer) *t, u64 interval)
u32 *TW() tw_timer_expire_timers(TWT(tw_timer_wheel) *tw, f64 now)
static uword clib_bitmap_first_set(uword *ai)
Return the lowest numbered set bit in a bitmap.
static u32 *TW() tw_timer_expire_timers_internal(TWT(tw_timer_wheel) *tw, f64 now, u32 *callback_vector_arg)
Advance a tw timer wheel.
#define TW_SLOTS_PER_RING
u32 *TW() tw_timer_expire_timers_vec(TWT(tw_timer_wheel) *tw, f64 now, u32 *vec)
#define pool_put(P, E)
Free an object E in pool P.
void TW() tw_timer_update(TWT(tw_timer_wheel) *tw, u32 handle, u64 interval)
Update a tw timer.
static void timer_remove(TWT(tw_timer) *pool, TWT(tw_timer) *elt)
#define clib_warning(format, args...)
#define pool_is_free_index(P, I)
Use free bitmap to query whether given index is free.
#define pool_put_index(p, i)
Free pool element with given index.
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
u32 TW() tw_timer_start(TWT(tw_timer_wheel) *tw, u32 user_id, u32 timer_id, u64 interval)
Start a Tw Timer.
static u32 TW() make_internal_timer_handle(u32 pool_index, u32 timer_id)
void TW() tw_timer_stop(TWT(tw_timer_wheel) *tw, u32 handle)
Stop a tw timer.
u32 head_index
Listhead of timers which expire in this interval.