106 #define FIB_WALK_QUEUE_STATS_NUM ((fib_walk_queue_stats_t)(FIB_WALK_COMPLETED+1)) 108 #define FIB_WALK_QUEUE_STATS { \ 109 [FIB_WALK_SCHEDULED] = "scheduled", \ 110 [FIB_WALK_COMPLETED] = "completed", \ 113 #define FOR_EACH_FIB_WALK_QUEUE_STATS(_wqs) \ 114 for ((_wqs) = FIB_WALK_SCHEDULED; \ 115 (_wqs) < FIB_WALK_QUEUE_STATS_NUM; \ 165 #define HISTOGRAM_VISITS_PER_WALK_MAX (1<<23) 166 #define HISTOGRAM_VISITS_PER_WALK_INCR (1<<10) 167 #define HISTOGRAM_VISITS_PER_WALK_N_BUCKETS \ 168 (HISTOGRAM_VISITS_PER_WALK_MAX/HISTOGRAM_VISITS_PER_WALK_INCR) 174 #define HISTORY_N_WALKS 128 175 #define MAX_HISTORY_REASONS 16 194 return (
format(s,
"%s", fib_walk_priority_names[prio]));
199 fib_walk_queue_stats_t wqs = va_arg(*ap, fib_walk_queue_stats_t);
203 return (
format(s,
"%s", fib_walk_queue_stats_names[wqs]));
209 return (fwalk - fib_walk_pool);
266 fib_walk_hist_vists_per_walk[bucket]++;
322 static fib_walk_advance_rc_t
396 #define FIB_WALK_N_SLEEP (FIB_WALK_LONG_SLEEP+1) 401 static f64 fib_walk_sleep_duration[] = {
425 #define N_TIME_BUCKETS 128 426 #define TIME_INCREMENTS (N_TIME_BUCKETS/2) 432 #define N_ELTS_BUCKETS 128 433 static u32 fib_walk_work_nodes_visisted_incr = 2;
439 static u64 fib_walk_sleep_lengths[2];
449 f64 start_time, consumed_time;
450 fib_walk_sleep_type_t sleep;
452 fib_walk_advance_rc_t rc;
479 }
while ((consumed_time < quota) &&
499 goto that_will_do_for_now;
508 that_will_do_for_now:
517 n_elts/fib_walk_work_nodes_visisted_incr);
518 ++fib_walk_work_nodes_visited[bucket];
522 bucket = (bucket < 0 ? 0 : bucket);
524 ++fib_walk_work_time_taken[bucket];
526 ++fib_walk_sleep_lengths[sleep];
528 return (fib_walk_sleep_duration[sleep]);
549 uword event_type, *event_data = 0;
665 fib_walk_process_node.index,
680 if (FIB_NODE_GRAPH_MAX_DEPTH < ++ctx->fnbw_depth)
731 fib_walk_advance_rc_t rc;
735 if (FIB_NODE_GRAPH_MAX_DEPTH < ++ctx->fnbw_depth)
937 return (
format(s,
" parent:{%s:%d} visits:%d flags:%d",
949 fib_walk_queue_stats_t wqs;
1000 if (0 != fib_walk_work_nodes_visited[ii])
1002 (ii * fib_walk_work_nodes_visisted_incr),
1003 fib_walk_work_nodes_visited[ii]);
1008 vlib_cli_output(vm,
" Time consumed per-quota (Quota=%f usec):", quota*USEC);
1009 s =
format(s,
"0:%d ", fib_walk_work_time_taken[0]);
1012 if (0 != fib_walk_work_time_taken[ii])
1013 s =
format(s,
"%d:%d ", (
u32)((((ii - N_TIME_BUCKETS/2) *
1016 fib_walk_work_time_taken[ii]);
1030 if (0 != fib_walk_hist_vists_per_walk[ii])
1033 fib_walk_hist_vists_per_walk[ii]);
1040 ii = history_last_walk_pos - 1;
1044 while (ii != history_last_walk_pos)
1046 if (0 != fib_walk_history[ii].fwh_reason[0])
1052 s =
format(s,
"[@%d]: %s:%d visits:%d duration:%.2f completed:%.2f ",
1061 s =
format(s,
"async, ");
1063 s =
format(s,
"reason:");
1065 while (0 != fib_walk_history[ii].fwh_reason[jj])
1068 if ((1<<reason) & fib_walk_history[ii].fwh_reason[jj]) {
1069 s =
format (s,
"%s,", fib_node_bw_reason_names[reason]);
1086 .path =
"show fib walk",
1087 .short_help =
"show fib walk",
1099 if (
unformat (input,
"%f", &new_quota))
1112 .path =
"set fib walk quota",
1113 .short_help =
"set fib walk quota",
1127 fib_walk_work_nodes_visisted_incr =
new;
1138 .path =
"set fib walk histogram elements size",
1139 .short_help =
"set fib walk histogram elements size",
1148 memset(fib_walk_hist_vists_per_walk, 0,
sizeof(fib_walk_hist_vists_per_walk));
1149 memset(fib_walk_history, 0,
sizeof(fib_walk_history));
1150 memset(fib_walk_work_time_taken, 0,
sizeof(fib_walk_work_time_taken));
1151 memset(fib_walk_work_nodes_visited, 0,
sizeof(fib_walk_work_nodes_visited));
1152 memset(fib_walk_sleep_lengths, 0,
sizeof(fib_walk_sleep_lengths));
1158 .path =
"clear fib walk",
1159 .short_help =
"clear fib walk",
1167 fib_walk_process_node.index,
1176 fib_walk_process_node.index,
1190 else if (
unformat (input,
"disable"))
1202 .path =
"test fib-walk-process",
1203 .short_help =
"test fib-walk-process [enable|disable]",
#define HISTOGRAM_VISITS_PER_WALK_N_BUCKETS
#define FOR_EACH_FIB_NODE_BW_REASON(_item)
struct fib_walk_history_t_ fib_walk_history_t
void fib_node_list_elt_remove(u32 sibling)
#define vec_foreach_index(var, v)
Iterate over vector indices.
u32 fw_dep_sibling
Sibling index in the dependency list.
static fib_walk_t * fib_walk_pool
The pool of all walk objects.
static f64 vlib_process_wait_for_event_or_clock(vlib_main_t *vm, f64 dt)
Suspend a cooperative multi-tasking thread Waits for an event, or for the indicated number of seconds...
static uword * vlib_process_wait_for_event(vlib_main_t *vm)
fib_walk_advance_rc_t_
return code when advancing a walk
static clib_error_t * fib_walk_set_quota(vlib_main_t *vm, unformat_input_t *input, vlib_cli_command_t *cmd)
fib_walk_queue_t fwqs_queues[FIB_WALK_PRIORITY_NUM]
void fib_node_init(fib_node_t *node, fib_node_type_t type)
#define N_TIME_BUCKETS
Histogram on the amount of work done (in msecs) in each walk.
static f64 vlib_time_now(vlib_main_t *vm)
enum fib_node_back_walk_rc_t_ fib_node_back_walk_rc_t
Return code from a back walk function.
u64 fwq_stats[FIB_WALK_QUEUE_STATS_NUM]
Qeuee stats.
u32 index_t
A Data-Path Object is an object that represents actions that are applied to packets are they are swit...
#define vec_add1(V, E)
Add 1 element to end of vector (unspecified alignment).
static heap_elt_t * last(heap_header_t *h)
static fib_node_index_t fib_walk_queue_get_front(fib_walk_priority_t prio)
#define STRUCT_OFFSET_OF(t, f)
void fib_node_deinit(fib_node_t *node)
void fib_walk_async(fib_node_type_t parent_type, fib_node_index_t parent_index, fib_walk_priority_t prio, fib_node_back_walk_ctx_t *ctx)
struct fib_walk_queue_t_ fib_walk_queue_t
A represenation of one queue of walk.
static fib_walk_t * fib_walk_get(index_t fwi)
#define pool_get(P, E)
Allocate an object E from a pool P (unspecified alignment).
u32 fib_node_child_add(fib_node_type_t parent_type, fib_node_index_t parent_index, fib_node_type_t type, fib_node_index_t index)
#define vec_reset_length(v)
Reset vector length to zero NULL-pointer tolerant.
u8 * format_fib_walk_priority(u8 *s, va_list *ap)
void fib_node_register_type(fib_node_type_t type, const fib_node_vft_t *vft)
fib_node_register_type
static uword fib_walk_process(vlib_main_t *vm, vlib_node_runtime_t *node, vlib_frame_t *f)
The 'fib-walk' process's main loop.
f64 fib_walk_process_queues(vlib_main_t *vm, const f64 quota)
Service the queues This is not declared static so that it can be unit tested - i know i know...
static clib_error_t * fib_walk_process_enable_disable(vlib_main_t *vm, unformat_input_t *input, vlib_cli_command_t *cmd)
fib_node_index_t fnp_index
node's index
static uword vlib_process_get_events(vlib_main_t *vm, uword **data_vector)
Return the first event type which has occurred and a vector of per-event data of that type...
void fib_walk_sync(fib_node_type_t parent_type, fib_node_index_t parent_index, fib_node_back_walk_ctx_t *ctx)
Back walk all the children of a FIB node.
fib_walk_flags_t fwh_flags
fib_node_back_walk_rc_t fib_node_back_walk_one(fib_node_ptr_t *ptr, fib_node_back_walk_ctx_t *ctx)
#define FOR_EACH_FIB_WALK_PRIORITY(_prio)
fib_node_back_walk_ctx_t * fw_ctx
The reasons this walk is occuring.
#define MAX_HISTORY_REASONS
#define clib_error_return(e, args...)
static fib_walk_queues_t fib_walk_queues
The global queues of outstanding walks.
static u8 * format_fib_walk(u8 *s, va_list *ap)
A representation of a graph walk from a parent object to its children.
fib_walk_queue_stats_t_
Statistics maintained per-walk queue.
#define vec_end(v)
End (last data address) of vector.
A representation of one pointer to another node.
enum fib_walk_advance_rc_t_ fib_walk_advance_rc_t
return code when advancing a walk
#define HISTOGRAM_VISITS_PER_WALK_INCR
#define FIB_WALK_PRIORITY_NUM
fib_node_bw_reason_flag_t fnbw_reason
The reason/trigger for the backwalk.
#define pool_elt_at_index(p, i)
Returns pointer to element at given index.
fib_node_type_t fnp_type
node type
#define FIB_NODE_BW_REASONS
static void vlib_process_signal_event(vlib_main_t *vm, uword node_index, uword type_opaque, uword data)
u32 fnbw_depth
the number of levels the walk has already traversed.
#define FIB_WALK_QUEUE_STATS_NUM
static u8 * format_fib_walk_queue_stats(u8 *s, va_list *ap)
The walk merged with the one in front.
static void fib_walk_destroy(index_t fwi)
enum fib_walk_sleep_type_t_ fib_walk_sleep_type_t
Enurmerate the times of sleep between walks
u32 fw_n_visits
Number of nodes visited by this walk.
#define pool_put(P, E)
Free an object E in pool P.
#define N_ELTS_BUCKETS
Histogram on the number of nodes visted in each quota.
fib_walk_flags_t fw_flags
the walk's flags
fib_node_bw_flags_t fnbw_flags
additional flags for the walk
A set of priority queues for outstanding walks.
u32 fib_node_list_push_front(fib_node_list_t list, int owner_id, fib_node_type_t type, fib_node_index_t index)
Insert an element at the from of the list.
An node in the FIB graph.
int fib_node_list_advance(u32 sibling)
Advance the sibling one step (toward the tail) in the list.
enum fib_walk_flags_t_ fib_walk_flags_t
The flags on a walk.
#define FIB_WALK_PRIORITIES
enum fib_node_bw_reason_flag_t_ fib_node_bw_reason_flag_t
Flags enum constructed from the reaons.
static index_t fib_walk_get_index(fib_walk_t *fwalk)
void fib_walk_process_enable(void)
#define vec_free(V)
Free vector's memory (no header).
Force the walk to be synchronous.
static fib_node_back_walk_rc_t fib_walk_back_walk_notify(fib_node_t *node, fib_node_back_walk_ctx_t *ctx)
Another back walk has reach this walk.
u32 fib_node_index_t
A typedef of a node index.
u32 fib_node_get_n_children(fib_node_type_t parent_type, fib_node_index_t parent_index)
u32 fib_walk_queue_get_size(fib_walk_priority_t prio)
void fib_walk_module_init(void)
enum fib_walk_priority_t_ fib_walk_priority_t
Walk priorities.
static f64 quota
The time quota for a walk.
fib_node_ptr_t fw_parent
Pointer to the node whose dependants this walk is walking.
Context passed between object during a back walk.
#define VLIB_CLI_COMMAND(x,...)
static fib_walk_t * fib_walk_alloc(fib_node_type_t parent_type, fib_node_index_t parent_index, fib_walk_flags_t flags, fib_node_back_walk_ctx_t *ctx)
Allocate a new walk object.
An indication that the walk is currently executing.
f64 fw_start_time
Time the walk started.
static index_t fib_walk_prio_queue_enquue(fib_walk_priority_t prio, fib_walk_t *fwalk)
Enqueue a walk onto the appropriate priority queue.
u32 fib_node_list_get_size(fib_node_list_t list)
fib_node_list_t fib_node_list_create(void)
Create a new node list.
#define FIB_WALK_QUEUE_STATS
fib_walk_flags_t_
The flags on a walk.
fib_node_ptr_t fwh_parent
void fib_walk_process_disable(void)
static u32 fib_walk_work_nodes_visisted_incr
static clib_error_t * fib_walk_clear(vlib_main_t *vm, unformat_input_t *input, vlib_cli_command_t *cmd)
fib_walk_sleep_type_t_
Enurmerate the times of sleep between walks
enum fib_node_back_walk_reason_t_ fib_node_back_walk_reason_t
Reasons for backwalking the FIB object graph.
void fib_node_child_remove(fib_node_type_t parent_type, fib_node_index_t parent_index, fib_node_index_t sibling_index)
static vlib_main_t * vlib_get_main(void)
int fib_node_list_get_front(fib_node_list_t list, fib_node_ptr_t *ptr)
fib_walk_process_event_t_
Events sent to the FIB walk process.
fib_node_list_t fwq_queue
The node list which acts as the queue.
enum fib_walk_process_event_t_ fib_walk_process_event
Events sent to the FIB walk process.
#define FIB_NODE_INDEX_INVALID
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
static fib_walk_t * fib_walk_get_from_node(fib_node_t *node)
static fib_node_t * fib_walk_get_node(fib_node_index_t index)
static clib_error_t * fib_walk_set_histogram_elements_size(vlib_main_t *vm, unformat_input_t *input, vlib_cli_command_t *cmd)
See the respective fib_*.h files for descriptions of these objects.
#define HISTORY_N_WALKS
History of state for the last 128 walks.
A FIB graph nodes virtual function table.
static clib_error_t * fib_walk_show(vlib_main_t *vm, unformat_input_t *input, vlib_cli_command_t *cmd)
enum fib_node_type_t_ fib_node_type_t
The types of nodes in a FIB graph.
fib_node_t fw_node
FIB node linkage.
#define VLIB_REGISTER_NODE(x,...)
u32 fib_node_list_t
A list of FIB nodes.
int fib_node_list_elt_get_next(u32 sibling, fib_node_ptr_t *ptr)
static u32 history_last_walk_pos
struct fib_walk_t_ fib_walk_t
A representation of a graph walk from a parent object to its children.
enum fib_walk_queue_stats_t_ fib_walk_queue_stats_t
Statistics maintained per-walk queue.
u32 fw_prio_sibling
Sibling index in the list of all walks.
static void fib_walk_last_lock_gone(fib_node_t *node)
Walk objects are not parents, nor are they locked.
void vlib_cli_output(vlib_main_t *vm, char *fmt,...)
static fib_walk_advance_rc_t fib_walk_advance(fib_node_index_t fwi)
Advance the walk one element in its work list.
const char * fib_node_type_get_name(fib_node_type_t type)
A represenation of one queue of walk.
#define FOR_EACH_FIB_WALK_QUEUE_STATS(_wqs)
fib_node_bw_reason_flag_t fwh_reason[MAX_HISTORY_REASONS]
struct fib_walk_queues_t_ fib_walk_queues_t
A set of priority queues for outstanding walks.