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;
148 TWT (tw_timer) * next_elt, *prev_elt;
150 ASSERT (elt->user_handle != ~0);
155 next_elt->prev = elt->prev;
156 prev_elt->next = elt->next;
158 elt->prev = elt->next = ~0;
173 #if TW_TIMER_WHEELS > 1 174 u16 slow_ring_offset;
177 #if TW_TIMER_WHEELS > 2 178 u16 glacier_ring_offset;
180 #if TW_OVERFLOW_VECTOR > 0 181 u64 interval_plus_time_to_wrap, triple_wrap_mask;
183 u16 fast_ring_offset;
190 memset (t, 0xff,
sizeof (*t));
195 #if TW_TIMER_WHEELS > 2 196 #if TW_OVERFLOW_VECTOR > 0 204 interval_plus_time_to_wrap =
205 interval + (tw->current_tick & triple_wrap_mask);
206 if ((interval_plus_time_to_wrap >= 1 << (3 *
TW_RING_SHIFT)))
208 t->expiration_time = tw->current_tick + interval;
211 #if TW_START_STOP_TRACE_SIZE > 0 212 TW (tw_timer_trace) (tw, timer_id, pool_index, t - tw->timers);
214 return t - tw->timers;
222 #if TW_TIMER_WHEELS > 1 238 #if TW_TIMER_WHEELS > 1 247 #if TW_TIMER_WHEELS > 2 248 glacier_ring_offset +=
253 #if TW_TIMER_WHEELS > 2 254 if (glacier_ring_offset !=
258 t->slow_ring_offset = 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, pool_index, t - tw->timers);
267 return t - tw->timers;
271 #if TW_TIMER_WHEELS > 1 273 if (slow_ring_offset !=
277 t->fast_ring_offset = fast_ring_offset;
282 #if TW_START_STOP_TRACE_SIZE > 0 283 TW (tw_timer_trace) (tw, timer_id, pool_index, t - tw->timers);
285 return t - tw->timers;
296 #if TW_FAST_WHEEL_BITMAP 298 fast_ring_offset, 1);
300 #if TW_START_STOP_TRACE_SIZE > 0 301 TW (tw_timer_trace) (tw, timer_id, pool_index, t - tw->timers);
303 return t - tw->timers;
306 #if TW_TIMER_SCAN_FOR_HANDLE > 0 307 int TW (scan_for_handle) (
TWT (tw_timer_wheel) * tw,
u32 handle)
311 TWT (tw_timer) * t, *head;
321 next_index = head->next;
326 if (next_index == handle)
333 next_index = t->next;
350 #if TW_TIMER_ALLOW_DUPLICATE_STOP 359 #if TW_START_STOP_TRACE_SIZE > 0 360 TW (tw_timer_trace) (tw, ~0, ~0, handle);
366 ASSERT (t->user_handle != ~0);
382 void *expired_timer_callback,
383 f64 timer_interval_in_seconds,
u32 max_expirations)
388 memset (tw, 0,
sizeof (*tw));
389 tw->expired_timer_callback = expired_timer_callback;
390 tw->max_expirations = max_expirations;
391 if (timer_interval_in_seconds == 0.0)
396 tw->timer_interval = timer_interval_in_seconds;
397 tw->ticks_per_second = 1.0 / timer_interval_in_seconds;
398 tw->first_expires_tick = ~0ULL;
401 _vec_len (tw->expired_timer_handles) = 0;
407 ts = &tw->w[ring][slot];
409 memset (t, 0xff,
sizeof (*t));
410 t->next = t->prev = t - tw->timers;
415 #if TW_OVERFLOW_VECTOR > 0 418 memset (t, 0xff,
sizeof (*t));
419 t->next = t->prev = t - tw->timers;
432 TWT (tw_timer) * head, *t;
441 next_index = head->next;
446 next_index = t->next;
453 #if TW_OVERFLOW_VECVOR > 0 456 next_index = head->next;
461 next_index = t->next;
467 memset (tw, 0,
sizeof (*tw));
480 u32 * callback_vector_arg)
484 TWT (tw_timer) * t, *head;
485 u32 *callback_vector;
486 u32 fast_wheel_index;
488 u32 slow_wheel_index __attribute__ ((unused));
489 u32 glacier_wheel_index __attribute__ ((unused));
493 return callback_vector_arg;
496 nticks = tw->ticks_per_second * (now - tw->last_run_time);
498 return callback_vector_arg;
501 tw->next_run_time = (now + tw->timer_interval);
503 if (callback_vector_arg == 0)
505 _vec_len (tw->expired_timer_handles) = 0;
506 callback_vector = tw->expired_timer_handles;
509 callback_vector = callback_vector_arg;
511 for (i = 0; i < nticks; i++)
519 #if TW_OVERFLOW_VECTOR > 0 526 u32 new_glacier_ring_offset, new_slow_ring_offset;
527 u32 new_fast_ring_offset;
531 next_index = head->next;
537 while (next_index != head - tw->timers)
540 next_index = t->next;
543 t->next = t->prev = ~0;
545 ASSERT (t->expiration_time >= tw->current_tick);
547 interval = t->expiration_time - tw->current_tick;
559 interval -= (new_glacier_ring_offset << (2 *
TW_RING_SHIFT));
565 t->slow_ring_offset = new_slow_ring_offset;
566 t->fast_ring_offset = new_fast_ring_offset;
570 t->fast_ring_offset == 0 &&
571 new_glacier_ring_offset == 0))
573 vec_add1 (callback_vector, t->user_handle);
574 #if TW_START_STOP_TRACE_SIZE > 0 575 TW (tw_timer_trace) (tw, 0xfe, t->user_handle,
581 else if (new_glacier_ring_offset)
587 else if (t->slow_ring_offset)
598 #if TW_FAST_WHEEL_BITMAP 599 tw->fast_slot_bitmap =
601 t->fast_ring_offset, 1);
608 #if TW_TIMER_WHEELS > 2 619 next_index = head->next;
625 while (next_index != head - tw->timers)
628 next_index = t->next;
631 t->next = t->prev = ~0;
635 t->fast_ring_offset == 0))
637 vec_add1 (callback_vector, t->user_handle);
638 #if TW_START_STOP_TRACE_SIZE > 0 639 TW (tw_timer_trace) (tw, 0xfe, t->user_handle,
649 #if TW_FAST_WHEEL_BITMAP 650 tw->fast_slot_bitmap =
652 t->fast_ring_offset, 1);
665 #if TW_TIMER_WHEELS > 1 675 next_index = head->next;
681 while (next_index != head - tw->timers)
684 next_index = t->next;
687 t->next = t->prev = ~0;
692 vec_add1 (callback_vector, t->user_handle);
693 #if TW_START_STOP_TRACE_SIZE > 0 694 TW (tw_timer_trace) (tw, 0xfe, t->user_handle,
704 #if TW_FAST_WHEEL_BITMAP 705 tw->fast_slot_bitmap =
707 t->fast_ring_offset, 1);
719 next_index = head->next;
728 next_index = t->next;
729 vec_add1 (callback_vector, t->user_handle);
730 #if TW_START_STOP_TRACE_SIZE > 0 731 TW (tw_timer_trace) (tw, 0xfe, t->user_handle, t - tw->timers);
737 if (callback_vector_arg == 0 &&
vec_len (callback_vector))
740 if (tw->expired_timer_callback)
742 tw->expired_timer_callback (callback_vector);
745 tw->expired_timer_handles = callback_vector;
748 #if TW_FAST_WHEEL_BITMAP 750 fast_wheel_index, 0);
757 #if TW_TIMER_WHEELS > 1 763 #if TW_TIMER_WHEELS > 2 765 glacier_wheel_index++;
769 if (
vec_len (callback_vector) >= tw->max_expirations)
773 if (callback_vector_arg == 0)
774 tw->expired_timer_handles = callback_vector;
776 tw->last_run_time += i * tw->timer_interval;
777 return callback_vector;
791 #if TW_FAST_WHEEL_BITMAP 799 u32 TW (tw_timer_first_expires_in_ticks) (
TWT (tw_timer_wheel) * tw)
801 u32 first_expiring_index, fast_ring_index;
813 if (first_expiring_index == ~0 && fast_ring_index != 0)
816 ASSERT (first_expiring_index != ~0);
818 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
u32 *TW() tw_timer_expire_timers_vec(TWT(tw_timer_wheel)*tw, f64 now, u32 *vec)
#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.
static uword clib_bitmap_is_zero(uword *ai)
predicate function; is an entire bitmap empty?
#define LOG2_TW_TIMERS_PER_OBJECT
u32 TW() tw_timer_start(TWT(tw_timer_wheel)*tw, u32 pool_index, u32 timer_id, u64 interval)
Start a Tw Timer.
static void timer_addhead(TWT(tw_timer)*pool, u32 head_index, u32 new_index)
#define pool_elt_at_index(p, i)
Returns pointer to element at given index.
static uword clib_bitmap_first_set(uword *ai)
Return the lowest numbered set bit in a bitmap.
#define TW_SLOTS_PER_RING
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 pool_put(P, E)
Free an object E in pool P.
#define clib_warning(format, args...)
void TW() tw_timer_stop(TWT(tw_timer_wheel)*tw, u32 handle)
Stop a tw timer.
static void timer_remove(TWT(tw_timer)*pool, u32 index)
#define pool_is_free_index(P, I)
Use free bitmap to query whether given index is free.
u32 *TW() tw_timer_expire_timers(TWT(tw_timer_wheel)*tw, f64 now)
#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)
static uword clib_bitmap_next_set(uword *ai, uword i)
Return the next set bit in a bitmap starting at bit i.
static u32 TW() make_internal_timer_handle(u32 pool_index, u32 timer_id)
void TW() tw_timer_wheel_free(TWT(tw_timer_wheel)*tw)
Free a tw timer wheel template instance.
u32 head_index
Listhead of timers which expire in this interval.