#include <vppinfra/timing_wheel.h>
void
-timing_wheel_init (timing_wheel_t * w, u64 current_cpu_time, f64 cpu_clocks_per_second)
+timing_wheel_init (timing_wheel_t * w, u64 current_cpu_time,
+ f64 cpu_clocks_per_second)
{
if (w->max_sched_time <= w->min_sched_time)
{
}
w->cpu_clocks_per_second = cpu_clocks_per_second;
- w->log2_clocks_per_bin = max_log2 (w->cpu_clocks_per_second * w->min_sched_time);
- w->log2_bins_per_wheel = max_log2 (w->cpu_clocks_per_second * w->max_sched_time);
+ w->log2_clocks_per_bin =
+ max_log2 (w->cpu_clocks_per_second * w->min_sched_time);
+ w->log2_bins_per_wheel =
+ max_log2 (w->cpu_clocks_per_second * w->max_sched_time);
w->log2_bins_per_wheel -= w->log2_clocks_per_bin;
w->log2_clocks_per_wheel = w->log2_bins_per_wheel + w->log2_clocks_per_bin;
w->bins_per_wheel = 1 << w->log2_bins_per_wheel;
w->current_time_index = current_cpu_time >> w->log2_clocks_per_bin;
if (w->n_wheel_elt_time_bits <= 0 ||
- w->n_wheel_elt_time_bits >= STRUCT_BITS_OF (timing_wheel_elt_t, cpu_time_relative_to_base))
- w->n_wheel_elt_time_bits = STRUCT_BITS_OF (timing_wheel_elt_t, cpu_time_relative_to_base) - 1;
+ w->n_wheel_elt_time_bits >= STRUCT_BITS_OF (timing_wheel_elt_t,
+ cpu_time_relative_to_base))
+ w->n_wheel_elt_time_bits =
+ STRUCT_BITS_OF (timing_wheel_elt_t, cpu_time_relative_to_base) - 1;
w->cpu_time_base = current_cpu_time;
w->time_index_next_cpu_time_base_update
- = w->current_time_index + ((u64) 1 << (w->n_wheel_elt_time_bits - w->log2_clocks_per_bin));
+ =
+ w->current_time_index +
+ ((u64) 1 << (w->n_wheel_elt_time_bits - w->log2_clocks_per_bin));
}
always_inline uword
-get_level_and_relative_time (timing_wheel_t * w, u64 cpu_time, uword * rtime_result)
+get_level_and_relative_time (timing_wheel_t * w, u64 cpu_time,
+ uword * rtime_result)
{
u64 dt, rtime;
uword level_index;
always_inline uword
time_index_to_wheel_index (timing_wheel_t * w, uword level_index, u64 ti)
-{ return (ti >> (level_index * w->log2_bins_per_wheel)) & w->bins_per_wheel_mask; }
+{
+ return (ti >> (level_index * w->log2_bins_per_wheel)) &
+ w->bins_per_wheel_mask;
+}
/* Find current time on this level. */
always_inline uword
current_time_wheel_index (timing_wheel_t * w, uword level_index)
-{ return time_index_to_wheel_index (w, level_index, w->current_time_index); }
+{
+ return time_index_to_wheel_index (w, level_index, w->current_time_index);
+}
/* Circular wheel indexing. */
always_inline uword
wheel_add (timing_wheel_t * w, word x)
-{ return x & w->bins_per_wheel_mask; }
+{
+ return x & w->bins_per_wheel_mask;
+}
always_inline uword
rtime_to_wheel_index (timing_wheel_t * w, uword level_index, uword rtime)
static clib_error_t *
validate_level (timing_wheel_t * w, uword level_index, uword * n_elts)
{
- timing_wheel_level_t * level;
- timing_wheel_elt_t * e;
+ timing_wheel_level_t *level;
+ timing_wheel_elt_t *e;
uword wi;
- clib_error_t * error = 0;
-
+ clib_error_t *error = 0;
+
#define _(x) \
do { \
error = CLIB_ERROR_ASSERT (x); \
for (wi = 0; wi < vec_len (level->elts); wi++)
{
/* Validate occupancy bitmap. */
- _ (clib_bitmap_get_no_check (level->occupancy_bitmap, wi) == (vec_len (level->elts[wi]) > 0));
+ _(clib_bitmap_get_no_check (level->occupancy_bitmap, wi) ==
+ (vec_len (level->elts[wi]) > 0));
*n_elts += vec_len (level->elts[wi]);
vec_foreach (e, level->elts[wi])
- {
- /* Validate time bin and level. */
- u64 e_time;
- uword e_ti, e_li, e_wi;
-
- e_time = e->cpu_time_relative_to_base + w->cpu_time_base;
- e_li = get_level_and_relative_time (w, e_time, &e_ti);
- e_wi = rtime_to_wheel_index (w, level_index, e_ti);
-
- if (e_li == level_index - 1)
- /* If this element was scheduled on the previous level
- it must be wrapped. */
- _ (e_ti + current_time_wheel_index (w, level_index - 1)
- >= w->bins_per_wheel);
- else
- {
- _ (e_li == level_index);
- if (e_li == 0)
- _ (e_wi == wi);
- else
- _ (e_wi == wi || e_wi + 1 == wi || e_wi - 1 == wi);
- }
- }
+ {
+ /* Validate time bin and level. */
+ u64 e_time;
+ uword e_ti, e_li, e_wi;
+
+ e_time = e->cpu_time_relative_to_base + w->cpu_time_base;
+ e_li = get_level_and_relative_time (w, e_time, &e_ti);
+ e_wi = rtime_to_wheel_index (w, level_index, e_ti);
+
+ if (e_li == level_index - 1)
+ /* If this element was scheduled on the previous level
+ it must be wrapped. */
+ _(e_ti + current_time_wheel_index (w, level_index - 1)
+ >= w->bins_per_wheel);
+ else
+ {
+ _(e_li == level_index);
+ if (e_li == 0)
+ _(e_wi == wi);
+ else
+ _(e_wi == wi || e_wi + 1 == wi || e_wi - 1 == wi);
+ }
+ }
}
#undef _
return error;
}
-void timing_wheel_validate (timing_wheel_t * w)
+void
+timing_wheel_validate (timing_wheel_t * w)
{
uword l;
- clib_error_t * error = 0;
+ clib_error_t *error = 0;
uword n_elts;
- if (! w->validate)
+ if (!w->validate)
return;
n_elts = pool_elts (w->overflow_pool);
}
static timing_wheel_elt_t *
-insert_helper (timing_wheel_t * w,
- uword level_index,
- uword rtime)
+insert_helper (timing_wheel_t * w, uword level_index, uword rtime)
{
- timing_wheel_level_t * level;
- timing_wheel_elt_t * e;
+ timing_wheel_level_t *level;
+ timing_wheel_elt_t *e;
uword wheel_index;
/* Circular buffer. */
vec_validate (w->levels, level_index);
level = vec_elt_at_index (w->levels, level_index);
- if (PREDICT_FALSE (! level->elts))
+ if (PREDICT_FALSE (!level->elts))
{
uword max = w->bins_per_wheel - 1;
clib_bitmap_validate (level->occupancy_bitmap, max);
wheel_index = rtime_to_wheel_index (w, level_index, rtime);
- level->occupancy_bitmap = clib_bitmap_ori (level->occupancy_bitmap, wheel_index);
+ level->occupancy_bitmap =
+ clib_bitmap_ori (level->occupancy_bitmap, wheel_index);
/* Allocate an elt vector from free list if there is one. */
- if (! level->elts[wheel_index] && vec_len (w->free_elt_vectors))
+ if (!level->elts[wheel_index] && vec_len (w->free_elt_vectors))
level->elts[wheel_index] = vec_pop (w->free_elt_vectors);
/* Add element to vector for this time bin. */
}
/* Insert user data on wheel at given CPU time stamp. */
-static void timing_wheel_insert_helper (timing_wheel_t * w, u64 insert_cpu_time, u32 user_data)
+static void
+timing_wheel_insert_helper (timing_wheel_t * w, u64 insert_cpu_time,
+ u32 user_data)
{
- timing_wheel_elt_t * e;
+ timing_wheel_elt_t *e;
u64 dt;
uword rtime, level_index;
else
{
/* Time too far in the future: add to overflow vector. */
- timing_wheel_overflow_elt_t * oe;
+ timing_wheel_overflow_elt_t *oe;
pool_get (w->overflow_pool, oe);
oe->user_data = user_data;
oe->cpu_time = insert_cpu_time;
delete_user_data (timing_wheel_elt_t * elts, u32 user_data)
{
uword found_match;
- timing_wheel_elt_t * e, * new_elts;
+ timing_wheel_elt_t *e, *new_elts;
/* Quickly scan to see if there are any elements to delete
in this bucket. */
found_match = 0;
vec_foreach (e, elts)
- {
- found_match = e->user_data == user_data;
- if (found_match)
- break;
- }
- if (! found_match)
+ {
+ found_match = e->user_data == user_data;
+ if (found_match)
+ break;
+ }
+ if (!found_match)
return elts;
/* Re-scan to build vector of new elts with matching user_data deleted. */
new_elts = 0;
vec_foreach (e, elts)
- {
- if (e->user_data != user_data)
- vec_add1 (new_elts, e[0]);
- }
+ {
+ if (e->user_data != user_data)
+ vec_add1 (new_elts, e[0]);
+ }
vec_free (elts);
return new_elts;
}
/* Insert user data on wheel at given CPU time stamp. */
-void timing_wheel_insert (timing_wheel_t * w, u64 insert_cpu_time, u32 user_data)
+void
+timing_wheel_insert (timing_wheel_t * w, u64 insert_cpu_time, u32 user_data)
{
/* Remove previously deleted elements. */
if (elt_is_deleted (w, user_data))
{
- timing_wheel_level_t * l;
+ timing_wheel_level_t *l;
uword wi;
/* Delete elts with given user data so that stale events don't expire. */
vec_foreach (l, w->levels)
- {
+ {
+ /* *INDENT-OFF* */
clib_bitmap_foreach (wi, l->occupancy_bitmap, ({
l->elts[wi] = delete_user_data (l->elts[wi], user_data);
if (vec_len (l->elts[wi]) == 0)
l->occupancy_bitmap = clib_bitmap_andnoti (l->occupancy_bitmap, wi);
}));
- }
+ /* *INDENT-ON* */
+ }
{
- timing_wheel_overflow_elt_t * oe;
+ timing_wheel_overflow_elt_t *oe;
+ /* *INDENT-OFF* */
pool_foreach (oe, w->overflow_pool, ({
if (oe->user_data == user_data)
pool_put (w->overflow_pool, oe);
}));
+ /* *INDENT-ON* */
}
hash_unset (w->deleted_user_data_hash, user_data);
timing_wheel_insert_helper (w, insert_cpu_time, user_data);
}
-void timing_wheel_delete (timing_wheel_t * w, u32 user_data)
+void
+timing_wheel_delete (timing_wheel_t * w, u32 user_data)
{
- if (! w->deleted_user_data_hash)
- w->deleted_user_data_hash = hash_create (/* capacity */ 0, /* value bytes */ 0);
+ if (!w->deleted_user_data_hash)
+ w->deleted_user_data_hash =
+ hash_create ( /* capacity */ 0, /* value bytes */ 0);
hash_set1 (w->deleted_user_data_hash, user_data);
}
/* Returns time of next expiring element. */
-u64 timing_wheel_next_expiring_elt_time (timing_wheel_t * w)
+u64
+timing_wheel_next_expiring_elt_time (timing_wheel_t * w)
{
- timing_wheel_level_t * l;
- timing_wheel_elt_t * e;
+ timing_wheel_level_t *l;
+ timing_wheel_elt_t *e;
uword li, wi, wi0;
u32 min_dt;
u64 min_t;
min_dt = ~0;
min_t = ~0ULL;
vec_foreach (l, w->levels)
- {
- if (! l->occupancy_bitmap)
- continue;
-
- li = l - w->levels;
- wi0 = wi = current_time_wheel_index (w, li);
- wrapped = 0;
- while (1)
- {
- if (clib_bitmap_get_no_check (l->occupancy_bitmap, wi))
- {
- vec_foreach (e, l->elts[wi])
- min_dt = clib_min (min_dt, e->cpu_time_relative_to_base);
+ {
+ if (!l->occupancy_bitmap)
+ continue;
- if (wrapped && li + 1 < vec_len (w->levels))
- {
- uword wi1 = current_time_wheel_index (w, li + 1);
- if (l[1].occupancy_bitmap && clib_bitmap_get_no_check (l[1].occupancy_bitmap, wi1))
+ li = l - w->levels;
+ wi0 = wi = current_time_wheel_index (w, li);
+ wrapped = 0;
+ while (1)
+ {
+ if (clib_bitmap_get_no_check (l->occupancy_bitmap, wi))
+ {
+ vec_foreach (e, l->elts[wi])
+ min_dt = clib_min (min_dt, e->cpu_time_relative_to_base);
+
+ if (wrapped && li + 1 < vec_len (w->levels))
+ {
+ uword wi1 = current_time_wheel_index (w, li + 1);
+ if (l[1].occupancy_bitmap
+ && clib_bitmap_get_no_check (l[1].occupancy_bitmap, wi1))
+ {
+ vec_foreach (e, l[1].elts[wi1])
{
- vec_foreach (e, l[1].elts[wi1]) {
- min_dt = clib_min (min_dt, e->cpu_time_relative_to_base);
- }
+ min_dt =
+ clib_min (min_dt, e->cpu_time_relative_to_base);
}
- }
+ }
+ }
- min_t = w->cpu_time_base + min_dt;
- goto done;
- }
+ min_t = w->cpu_time_base + min_dt;
+ goto done;
+ }
- wi = wheel_add (w, wi + 1);
- if (wi == wi0)
- break;
+ wi = wheel_add (w, wi + 1);
+ if (wi == wi0)
+ break;
- wrapped = wi != wi + 1;
- }
- }
+ wrapped = wi != wi + 1;
+ }
+ }
{
- timing_wheel_overflow_elt_t * oe;
+ timing_wheel_overflow_elt_t *oe;
if (min_dt != ~0)
min_t = w->cpu_time_base + min_dt;
+ /* *INDENT-OFF* */
pool_foreach (oe, w->overflow_pool,
({ min_t = clib_min (min_t, oe->cpu_time); }));
+ /* *INDENT-ON* */
done:
return min_t;
always_inline u64
elt_cpu_time (timing_wheel_t * w, timing_wheel_elt_t * e)
-{ return w->cpu_time_base + e->cpu_time_relative_to_base; }
+{
+ return w->cpu_time_base + e->cpu_time_relative_to_base;
+}
always_inline void
validate_expired_elt (timing_wheel_t * w, timing_wheel_elt_t * e,
static u32 *
expire_bin (timing_wheel_t * w,
uword level_index,
- uword wheel_index,
- u64 advance_cpu_time,
- u32 * expired_user_data)
+ uword wheel_index, u64 advance_cpu_time, u32 * expired_user_data)
{
- timing_wheel_level_t * level = vec_elt_at_index (w->levels, level_index);
- timing_wheel_elt_t * e;
- u32 * x;
+ timing_wheel_level_t *level = vec_elt_at_index (w->levels, level_index);
+ timing_wheel_elt_t *e;
+ u32 *x;
uword i, j, e_len;
e = vec_elt (level->elts, wheel_index);
x[j] = e[i].user_data;
/* Only advance if elt is not to be deleted. */
- j += ! elt_is_deleted (w, e[i].user_data);
+ j += !elt_is_deleted (w, e[i].user_data);
}
/* Adjust for deleted elts. */
static void
advance_cpu_time_base (timing_wheel_t * w, u32 * expired_user_data)
{
- timing_wheel_level_t * l;
- timing_wheel_elt_t * e;
+ timing_wheel_level_t *l;
+ timing_wheel_elt_t *e;
u64 delta;
w->stats.cpu_time_base_advances++;
w->time_index_next_cpu_time_base_update += delta >> w->log2_clocks_per_bin;
vec_foreach (l, w->levels)
- {
- uword wi;
+ {
+ uword wi;
+ /* *INDENT-OFF* */
clib_bitmap_foreach (wi, l->occupancy_bitmap, ({
vec_foreach (e, l->elts[wi])
{
e->cpu_time_relative_to_base -= delta;
}
}));
- }
+ /* *INDENT-ON* */
+ }
/* See which overflow elements fit now. */
{
- timing_wheel_overflow_elt_t * oe;
+ timing_wheel_overflow_elt_t *oe;
+ /* *INDENT-OFF* */
pool_foreach (oe, w->overflow_pool, ({
/* It fits now into 32 bits. */
if (0 == ((oe->cpu_time - w->cpu_time_base) >> BITS (e->cpu_time_relative_to_base)))
pool_put (w->overflow_pool, oe);
}
}));
+ /* *INDENT-ON* */
}
}
uword level_index,
u64 advance_cpu_time,
uword from_wheel_index,
- uword to_wheel_index,
- u32 * expired_user_data)
+ uword to_wheel_index, u32 * expired_user_data)
{
- timing_wheel_level_t * level;
- timing_wheel_elt_t * to_insert = w->unexpired_elts_pending_insert;
+ timing_wheel_level_t *level;
+ timing_wheel_elt_t *to_insert = w->unexpired_elts_pending_insert;
u64 advance_time_index = advance_cpu_time >> w->log2_clocks_per_bin;
vec_validate (w->stats.refills, level_index);
goto done;
level = vec_elt_at_index (w->levels, level_index + 1);
- if (! level->occupancy_bitmap)
+ if (!level->occupancy_bitmap)
goto done;
while (1)
{
- timing_wheel_elt_t * e, * es;
+ timing_wheel_elt_t *e, *es;
- if (clib_bitmap_get_no_check (level->occupancy_bitmap, from_wheel_index))
+ if (clib_bitmap_get_no_check
+ (level->occupancy_bitmap, from_wheel_index))
{
es = level->elts[from_wheel_index];
level->elts[from_wheel_index] = 0;
- clib_bitmap_set_no_check (level->occupancy_bitmap, from_wheel_index, 0);
+ clib_bitmap_set_no_check (level->occupancy_bitmap, from_wheel_index,
+ 0);
vec_foreach (e, es)
- {
- u64 e_time = elt_cpu_time (w, e);
- u64 ti = e_time >> w->log2_clocks_per_bin;
- if (ti <= advance_time_index)
- {
- validate_expired_elt (w, e, advance_cpu_time);
- if (! elt_is_deleted (w, e->user_data))
- vec_add1 (expired_user_data, e->user_data);
- }
- else
- vec_add1 (to_insert, e[0]);
- }
+ {
+ u64 e_time = elt_cpu_time (w, e);
+ u64 ti = e_time >> w->log2_clocks_per_bin;
+ if (ti <= advance_time_index)
+ {
+ validate_expired_elt (w, e, advance_cpu_time);
+ if (!elt_is_deleted (w, e->user_data))
+ vec_add1 (expired_user_data, e->user_data);
+ }
+ else
+ vec_add1 (to_insert, e[0]);
+ }
free_elt_vector (w, es);
}
}
timing_wheel_validate (w);
- done:
+done:
w->unexpired_elts_pending_insert = to_insert;
return expired_user_data;
}
/* Advance wheel and return any expired user data in vector. */
u32 *
-timing_wheel_advance (timing_wheel_t * w, u64 advance_cpu_time, u32 * expired_user_data,
+timing_wheel_advance (timing_wheel_t * w, u64 advance_cpu_time,
+ u32 * expired_user_data,
u64 * next_expiring_element_cpu_time)
{
- timing_wheel_level_t * level;
+ timing_wheel_level_t *level;
uword level_index, advance_rtime, advance_level_index, advance_wheel_index;
uword n_expired_user_data_before;
u64 current_time_index, advance_time_index;
expired_user_data = refill_level (w,
level_index,
advance_cpu_time,
- c, a,
- expired_user_data);
+ c, a, expired_user_data);
current_ti >>= w->log2_bins_per_wheel;
advance_ti >>= w->log2_bins_per_wheel;
level_index++;
}
}
- advance_level_index = get_level_and_relative_time (w, advance_cpu_time, &advance_rtime);
- advance_wheel_index = rtime_to_wheel_index (w, advance_level_index, advance_rtime);
+ advance_level_index =
+ get_level_and_relative_time (w, advance_cpu_time, &advance_rtime);
+ advance_wheel_index =
+ rtime_to_wheel_index (w, advance_level_index, advance_rtime);
/* Empty all occupied bins for entire levels that we advance past. */
for (level_index = 0; level_index < advance_level_index; level_index++)
break;
level = vec_elt_at_index (w->levels, level_index);
+ /* *INDENT-OFF* */
clib_bitmap_foreach (wi, level->occupancy_bitmap, ({
expired_user_data = expire_bin (w, level_index, wi, advance_cpu_time,
expired_user_data);
}));
+ /* *INDENT-ON* */
}
if (PREDICT_TRUE (level_index < vec_len (w->levels)))
{
uword wi;
level = vec_elt_at_index (w->levels, level_index);
- wi = current_time_wheel_index (w, level_index);
+ wi = current_time_wheel_index (w, level_index);
if (level->occupancy_bitmap)
while (1)
{
if (clib_bitmap_get_no_check (level->occupancy_bitmap, wi))
- expired_user_data = expire_bin (w, advance_level_index, wi, advance_cpu_time,
- expired_user_data);
+ expired_user_data =
+ expire_bin (w, advance_level_index, wi, advance_cpu_time,
+ expired_user_data);
if (wi == advance_wheel_index)
break;
if (vec_len (w->unexpired_elts_pending_insert) > 0)
{
- timing_wheel_elt_t * e;
- vec_foreach (e, w->unexpired_elts_pending_insert)
- insert_elt (w, e);
+ timing_wheel_elt_t *e;
+ vec_foreach (e, w->unexpired_elts_pending_insert) insert_elt (w, e);
_vec_len (w->unexpired_elts_pending_insert) = 0;
}
/* Don't advance until necessary. */
- while (PREDICT_FALSE (advance_time_index >= w->time_index_next_cpu_time_base_update))
+ while (PREDICT_FALSE
+ (advance_time_index >= w->time_index_next_cpu_time_base_update))
advance_cpu_time_base (w, expired_user_data);
if (next_expiring_element_cpu_time)
return expired_user_data;
}
-u8 * format_timing_wheel (u8 * s, va_list * va)
+u8 *
+format_timing_wheel (u8 * s, va_list * va)
{
- timing_wheel_t * w = va_arg (*va, timing_wheel_t *);
+ timing_wheel_t *w = va_arg (*va, timing_wheel_t *);
int verbose = va_arg (*va, int);
uword indent = format_get_indent (s);
s = format (s, "level 0: %.4e - %.4e secs, 2^%d - 2^%d clocks",
(f64) (1 << w->log2_clocks_per_bin) / w->cpu_clocks_per_second,
- (f64) (1 << w->log2_clocks_per_wheel) / w->cpu_clocks_per_second,
- w->log2_clocks_per_bin, w->log2_clocks_per_wheel);
+ (f64) (1 << w->log2_clocks_per_wheel) /
+ w->cpu_clocks_per_second, w->log2_clocks_per_bin,
+ w->log2_clocks_per_wheel);
if (verbose)
{
s = format (s, "\n%Utime base advances %Ld, every %.4e secs",
format_white_space, indent + 2,
w->stats.cpu_time_base_advances,
- (f64) ((u64) 1 << w->n_wheel_elt_time_bits) / w->cpu_clocks_per_second);
+ (f64) ((u64) 1 << w->n_wheel_elt_time_bits) /
+ w->cpu_clocks_per_second);
for (l = 0; l < vec_len (w->levels); l++)
s = format (s, "\n%Ulevel %d: refills %Ld",
format_white_space, indent + 2,
- l, l < vec_len (w->stats.refills) ? w->stats.refills[l] : (u64) 0);
+ l,
+ l <
+ vec_len (w->stats.refills) ? w->stats.
+ refills[l] : (u64) 0);
}
return s;
}
+
+/*
+ * fd.io coding-style-patch-verification: ON
+ *
+ * Local Variables:
+ * eval: (c-set-style "gnu")
+ * End:
+ */
Code Review / vpp.git / blobdiff