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);
409 f64 timer_interval_in_seconds,
u32 max_expirations)
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;
426 _vec_len (tw->expired_timer_handles) = 0;
432 ts = &tw->w[ring][
slot];
435 t->next = t->prev = t - tw->timers;
440 #if TW_OVERFLOW_VECTOR > 0 444 t->next = t->prev = t - tw->timers;
457 TWT (tw_timer) * head, *t;
466 next_index = head->next;
471 next_index = t->next;
478 #if TW_OVERFLOW_VECTOR > 0 481 next_index = head->next;
486 next_index = t->next;
505 u32 * callback_vector_arg)
509 TWT (tw_timer) * t, *head;
510 u32 *callback_vector;
511 u32 fast_wheel_index;
513 u32 slow_wheel_index __attribute__ ((unused));
514 u32 glacier_wheel_index __attribute__ ((unused));
518 return callback_vector_arg;
521 nticks = tw->ticks_per_second * (now - tw->last_run_time);
523 return callback_vector_arg;
526 tw->next_run_time = (now + tw->timer_interval);
530 ((tw->last_run_time == 0.0) || (now <= tw->last_run_time)))
532 tw->last_run_time = now;
533 return callback_vector_arg;
536 if (callback_vector_arg == 0)
538 _vec_len (tw->expired_timer_handles) = 0;
539 callback_vector = tw->expired_timer_handles;
542 callback_vector = callback_vector_arg;
544 for (i = 0; i < nticks; i++)
552 #if TW_OVERFLOW_VECTOR > 0 559 u32 new_glacier_ring_offset, new_slow_ring_offset;
560 u32 new_fast_ring_offset;
564 next_index = head->next;
570 while (next_index != head - tw->timers)
573 next_index = t->next;
576 t->next = t->prev = ~0;
578 ASSERT (t->expiration_time >= tw->current_tick);
580 interval = t->expiration_time - tw->current_tick;
592 interval -= (new_glacier_ring_offset << (2 *
TW_RING_SHIFT));
598 t->slow_ring_offset = new_slow_ring_offset;
599 t->fast_ring_offset = new_fast_ring_offset;
603 t->fast_ring_offset == 0 &&
604 new_glacier_ring_offset == 0))
606 vec_add1 (callback_vector, t->user_handle);
607 #if TW_START_STOP_TRACE_SIZE > 0 608 TW (tw_timer_trace) (tw, 0xfe, t->user_handle,
614 else if (new_glacier_ring_offset)
620 else if (t->slow_ring_offset)
631 #if TW_FAST_WHEEL_BITMAP 632 tw->fast_slot_bitmap =
634 t->fast_ring_offset, 1);
641 #if TW_TIMER_WHEELS > 2 652 next_index = head->next;
658 while (next_index != head - tw->timers)
661 next_index = t->next;
664 t->next = t->prev = ~0;
668 t->fast_ring_offset == 0))
670 vec_add1 (callback_vector, t->user_handle);
671 #if TW_START_STOP_TRACE_SIZE > 0 672 TW (tw_timer_trace) (tw, 0xfe, t->user_handle,
682 #if TW_FAST_WHEEL_BITMAP 683 tw->fast_slot_bitmap =
685 t->fast_ring_offset, 1);
698 #if TW_TIMER_WHEELS > 1 708 next_index = head->next;
714 while (next_index != head - tw->timers)
717 next_index = t->next;
720 t->next = t->prev = ~0;
725 vec_add1 (callback_vector, t->user_handle);
726 #if TW_START_STOP_TRACE_SIZE > 0 727 TW (tw_timer_trace) (tw, 0xfe, t->user_handle,
737 #if TW_FAST_WHEEL_BITMAP 738 tw->fast_slot_bitmap =
740 t->fast_ring_offset, 1);
752 next_index = head->next;
761 next_index = t->next;
762 vec_add1 (callback_vector, t->user_handle);
763 #if TW_START_STOP_TRACE_SIZE > 0 764 TW (tw_timer_trace) (tw, 0xfe, t->user_handle, t - tw->timers);
770 if (callback_vector_arg == 0 &&
vec_len (callback_vector))
773 if (tw->expired_timer_callback)
775 tw->expired_timer_callback (callback_vector);
778 tw->expired_timer_handles = callback_vector;
781 #if TW_FAST_WHEEL_BITMAP 783 fast_wheel_index, 0);
790 #if TW_TIMER_WHEELS > 1 796 #if TW_TIMER_WHEELS > 2 798 glacier_wheel_index++;
802 if (
vec_len (callback_vector) >= tw->max_expirations)
806 if (callback_vector_arg == 0)
807 tw->expired_timer_handles = callback_vector;
809 tw->last_run_time += i * tw->timer_interval;
810 return callback_vector;
824 #if TW_FAST_WHEEL_BITMAP 832 u32 TW (tw_timer_first_expires_in_ticks) (
TWT (tw_timer_wheel) * tw)
834 u32 first_expiring_index, fast_ring_index;
837 #if TW_TIMER_WHEELS > 1 842 first_expiring_index = clib_bitmap_next_set (tw->fast_slot_bitmap,
844 if (first_expiring_index == ~0)
856 first_expiring_index = clib_bitmap_next_set (tw->fast_slot_bitmap,
858 if (first_expiring_index == ~0 && fast_ring_index != 0)
862 ASSERT (first_expiring_index != ~0);
864 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)
sll srl srl sll sra u16x4 i
#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 void expired_timer_callback(u32 *expired_timers)
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.