22 f64 cpu_clocks_per_second)
44 cpu_time_relative_to_base))
75 ASSERT (rtime < w->bins_per_wheel);
76 *rtime_result = rtime;
118 error = CLIB_ERROR_ASSERT (x); \ 120 if (error) return error; \ 128 (vec_len (level->
elts[wi]) > 0));
136 uword e_ti, e_li, e_wi;
142 if (e_li == level_index - 1)
149 _(e_li == level_index);
153 _(e_wi == wi || e_wi + 1 == wi || e_wi - 1 == wi);
187 memset (ev, ~0,
vec_len (ev) *
sizeof (ev[0]));
232 uword rtime, level_index;
242 if (insert_cpu_time < w->cached_min_cpu_time_on_wheel)
307 l->elts[wi] = delete_user_data (l->elts[wi], user_data);
308 if (vec_len (l->elts[wi]) == 0)
309 l->occupancy_bitmap = clib_bitmap_andnoti (l->occupancy_bitmap, wi);
318 if (oe->user_data == user_data)
319 pool_put (w->overflow_pool, oe);
371 if (l[1].occupancy_bitmap
390 wrapped = wi != wi + 1;
402 ({ min_t = clib_min (min_t, oe->cpu_time); }));
425 u64 current_cpu_time)
440 uword wheel_index,
u64 advance_cpu_time,
u32 * expired_user_data)
450 vec_add2 (expired_user_data, x, e_len);
451 for (i = j = 0; i < e_len; i++)
462 _vec_len (expired_user_data) -= e_len - j;
466 level->
elts[wheel_index] = 0;
469 return expired_user_data;
490 vec_foreach (e, l->elts[wi])
495 ASSERT (e->cpu_time_relative_to_base >= delta);
496 e->cpu_time_relative_to_base -= delta;
508 if (0 == ((oe->cpu_time - w->cpu_time_base) >> BITS (e->cpu_time_relative_to_base)))
510 u64 ti = oe->cpu_time >> w->log2_clocks_per_bin;
511 if (ti <= w->current_time_index)
516 if (! elt_is_deleted (w, oe->user_data))
517 vec_add1 (expired_user_data, oe->user_data);
520 timing_wheel_insert_helper (w, oe->cpu_time, oe->user_data);
521 pool_put (w->overflow_pool, oe);
526 return expired_user_data;
532 u64 advance_cpu_time,
533 uword from_wheel_index,
534 uword to_wheel_index,
u32 * expired_user_data)
557 es = level->
elts[from_wheel_index];
558 level->
elts[from_wheel_index] = 0;
566 if (ti <= advance_time_index)
578 if (from_wheel_index == to_wheel_index)
581 from_wheel_index =
wheel_add (w, from_wheel_index + 1);
587 return expired_user_data;
593 u32 * expired_user_data,
594 u64 * next_expiring_element_cpu_time)
597 uword level_index, advance_rtime, advance_level_index, advance_wheel_index;
598 uword n_expired_user_data_before;
599 u64 current_time_index, advance_time_index;
601 n_expired_user_data_before =
vec_len (expired_user_data);
608 u64 current_ti, advance_ti;
619 while (current_ti != advance_ti)
628 c, a, expired_user_data);
636 advance_level_index =
638 advance_wheel_index =
642 for (level_index = 0; level_index < advance_level_index; level_index++)
652 expired_user_data = expire_bin (w, level_index, wi, advance_cpu_time,
668 expire_bin (w, advance_level_index, wi, advance_cpu_time,
673 if (wi == advance_wheel_index)
698 if (next_expiring_element_cpu_time)
703 if (
vec_len (expired_user_data) == n_expired_user_data_before
712 *next_expiring_element_cpu_time = min_t;
715 return expired_user_data;
722 int verbose = va_arg (*va,
int);
725 s =
format (s,
"level 0: %.4e - %.4e secs, 2^%d - 2^%d clocks",
735 s =
format (s,
"\n%Utime base advances %Ld, every %.4e secs",
742 s =
format (s,
"\n%Ulevel %d: refills %Ld",
747 refills[l] : (
u64) 0);
#define vec_validate(V, I)
Make sure vector is long enough for given index (no header, unspecified alignment) ...
timing_wheel_overflow_elt_t * overflow_pool
void timing_wheel_validate(timing_wheel_t *w)
sll srl srl sll sra u16x4 i
#define hash_unset(h, key)
#define STRUCT_BITS_OF(t, f)
void timing_wheel_init(timing_wheel_t *w, u64 current_cpu_time, f64 cpu_clocks_per_second)
Fixed length block allocator.
u64 timing_wheel_next_expiring_elt_time(timing_wheel_t *w)
u64 cached_min_cpu_time_on_wheel
#define vec_add1(V, E)
Add 1 element to end of vector (unspecified alignment).
#define vec_add2(V, P, N)
Add N elements to end of vector V, return pointer to new elements in P.
void timing_wheel_insert(timing_wheel_t *w, u64 insert_cpu_time, u32 user_data)
#define pool_get(P, E)
Allocate an object E from a pool P (unspecified alignment).
static uword clib_bitmap_get_no_check(uword *ai, uword i)
Gets the ith bit value from a bitmap Does not sanity-check the bit position.
#define vec_pop(V)
Returns last element of a vector and decrements its length.
static uword wheel_add(timing_wheel_t *w, word x)
static timing_wheel_elt_t * delete_user_data(timing_wheel_elt_t *elts, u32 user_data)
static uword clib_bitmap_set_no_check(uword *a, uword i, uword new_value)
Sets the ith bit of a bitmap to new_value.
static void free_elt_vector(timing_wheel_t *w, timing_wheel_elt_t *ev)
#define clib_bitmap_validate(v, n_bits)
static timing_wheel_elt_t * insert_helper(timing_wheel_t *w, uword level_index, uword rtime)
#define pool_foreach(VAR, POOL, BODY)
Iterate through pool.
timing_wheel_stats_t stats
#define vec_elt_at_index(v, i)
Get vector value at index i checking that i is in bounds.
f64 cpu_clocks_per_second
static u32 * advance_cpu_time_base(timing_wheel_t *w, u32 *expired_user_data)
static void validate_expired_elt(timing_wheel_t *w, timing_wheel_elt_t *e, u64 current_cpu_time)
static u32 * expire_bin(timing_wheel_t *w, uword level_index, uword wheel_index, u64 advance_cpu_time, u32 *expired_user_data)
#define clib_bitmap_foreach(i, ai, body)
Macro to iterate across set bits in a bitmap.
timing_wheel_elt_t ** free_elt_vectors
u8 * format_timing_wheel(u8 *s, va_list *va)
static uword current_time_wheel_index(timing_wheel_t *w, uword level_index)
static u64 elt_cpu_time(timing_wheel_t *w, timing_wheel_elt_t *e)
static void timing_wheel_insert_helper(timing_wheel_t *w, u64 insert_cpu_time, u32 user_data)
static uword rtime_to_wheel_index(timing_wheel_t *w, uword level_index, uword rtime)
#define vec_free(V)
Free vector's memory (no header).
u32 * timing_wheel_advance(timing_wheel_t *w, u64 advance_cpu_time, u32 *expired_user_data, u64 *next_expiring_element_cpu_time)
void timing_wheel_delete(timing_wheel_t *w, u32 user_data)
timing_wheel_elt_t ** elts
#define hash_set1(h, key)
timing_wheel_elt_t * unexpired_elts_pending_insert
#define hash_create(elts, value_bytes)
uword * deleted_user_data_hash
static uword hash_elts(void *v)
u64 time_index_next_cpu_time_base_update
Bitmaps built as vectors of machine words.
#define clib_error_report(e)
static uword get_level_and_relative_time(timing_wheel_t *w, u64 cpu_time, uword *rtime_result)
timing_wheel_level_t * levels
#define vec_elt(v, i)
Get vector value at index i.
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
static uword max_log2(uword x)
static u32 * refill_level(timing_wheel_t *w, uword level_index, u64 advance_cpu_time, uword from_wheel_index, uword to_wheel_index, u32 *expired_user_data)
#define vec_foreach(var, vec)
Vector iterator.
static uword time_index_to_wheel_index(timing_wheel_t *w, uword level_index, u64 ti)
static void insert_elt(timing_wheel_t *w, timing_wheel_elt_t *e)
u64 cpu_time_base_advances
static uword elt_is_deleted(timing_wheel_t *w, u32 user_data)
static clib_error_t * validate_level(timing_wheel_t *w, uword level_index, uword *n_elts)
u32 cpu_time_relative_to_base
static uword pool_elts(void *v)
Number of active elements in a pool.