108 #define FIB_WALK_QUEUE_STATS_NUM ((fib_walk_queue_stats_t)(FIB_WALK_COMPLETED+1)) 110 #define FIB_WALK_QUEUE_STATS { \ 111 [FIB_WALK_SCHEDULED] = "scheduled", \ 112 [FIB_WALK_COMPLETED] = "completed", \ 115 #define FOR_EACH_FIB_WALK_QUEUE_STATS(_wqs) \ 116 for ((_wqs) = FIB_WALK_SCHEDULED; \ 117 (_wqs) < FIB_WALK_QUEUE_STATS_NUM; \ 167 #define HISTOGRAM_VISITS_PER_WALK_MAX (1<<23) 168 #define HISTOGRAM_VISITS_PER_WALK_INCR (1<<10) 169 #define HISTOGRAM_VISITS_PER_WALK_N_BUCKETS \ 170 (HISTOGRAM_VISITS_PER_WALK_MAX/HISTOGRAM_VISITS_PER_WALK_INCR) 176 #define HISTORY_N_WALKS 128 177 #define MAX_HISTORY_REASONS 16 191 #define FIB_WALK_DBG(_walk, _fmt, _args...) \ 193 vlib_log_debug(fib_walk_logger, \ 196 fib_walk_get_index(_walk), \ 207 return (
format(s,
"%s", fib_walk_priority_names[prio]));
212 fib_walk_queue_stats_t wqs = va_arg(*ap, fib_walk_queue_stats_t);
216 return (
format(s,
"%s", fib_walk_queue_stats_names[wqs]));
222 return (fwalk - fib_walk_pool);
279 fib_walk_hist_vists_per_walk[bucket]++;
335 static fib_walk_advance_rc_t
411 #define FIB_WALK_N_SLEEP (FIB_WALK_LONG_SLEEP+1) 416 static f64 fib_walk_sleep_duration[] = {
440 #define N_TIME_BUCKETS 128 441 #define TIME_INCREMENTS (N_TIME_BUCKETS/2) 447 #define N_ELTS_BUCKETS 128 448 static u32 fib_walk_work_nodes_visisted_incr = 2;
454 static u64 fib_walk_sleep_lengths[2];
464 f64 start_time, consumed_time;
465 fib_walk_sleep_type_t sleep;
467 fib_walk_advance_rc_t rc;
494 }
while ((consumed_time < quota) &&
514 goto that_will_do_for_now;
523 that_will_do_for_now:
532 n_elts/fib_walk_work_nodes_visisted_incr);
533 ++fib_walk_work_nodes_visited[bucket];
537 bucket = (bucket < 0 ? 0 : bucket);
539 ++fib_walk_work_time_taken[bucket];
541 ++fib_walk_sleep_lengths[sleep];
543 return (fib_walk_sleep_duration[sleep]);
564 uword event_type, *event_data = 0;
680 fib_walk_process_node.index,
695 if (FIB_NODE_GRAPH_MAX_DEPTH < ++ctx->fnbw_depth)
749 fib_walk_advance_rc_t rc;
753 if (FIB_NODE_GRAPH_MAX_DEPTH < ++ctx->fnbw_depth)
965 return (
format(s,
"[@%d] parent:{%s:%d} visits:%d flags:%d", fwi,
979 if ((1<<reason) & flag)
980 s =
format(s,
"%s", fib_node_bw_reason_names[reason]);
991 fib_walk_queue_stats_t wqs;
1042 if (0 != fib_walk_work_nodes_visited[ii])
1044 (ii * fib_walk_work_nodes_visisted_incr),
1045 fib_walk_work_nodes_visited[ii]);
1050 vlib_cli_output(vm,
" Time consumed per-quota (Quota=%f usec):", quota*USEC);
1051 s =
format(s,
"0:%d ", fib_walk_work_time_taken[0]);
1054 if (0 != fib_walk_work_time_taken[ii])
1055 s =
format(s,
"%d:%d ", (
u32)((((ii - N_TIME_BUCKETS/2) *
1058 fib_walk_work_time_taken[ii]);
1072 if (0 != fib_walk_hist_vists_per_walk[ii])
1075 fib_walk_hist_vists_per_walk[ii]);
1082 ii = history_last_walk_pos - 1;
1086 while (ii != history_last_walk_pos)
1088 if (0 != fib_walk_history[ii].fwh_reason[0])
1093 s =
format(s,
"[@%d]: %s:%d visits:%d duration:%.2f completed:%.2f ",
1102 s =
format(s,
"async, ");
1104 s =
format(s,
"reason:");
1106 while (0 != fib_walk_history[ii].fwh_reason[jj])
1109 fib_walk_history[ii].fwh_reason[jj]);
1124 .path =
"show fib walk",
1125 .short_help =
"show fib walk",
1137 if (
unformat (input,
"%f", &new_quota))
1150 .path =
"set fib walk quota",
1151 .short_help =
"set fib walk quota",
1165 fib_walk_work_nodes_visisted_incr =
new;
1176 .path =
"set fib walk histogram elements size",
1177 .short_help =
"set fib walk histogram elements size",
1186 clib_memset(fib_walk_hist_vists_per_walk, 0,
sizeof(fib_walk_hist_vists_per_walk));
1187 clib_memset(fib_walk_history, 0,
sizeof(fib_walk_history));
1188 clib_memset(fib_walk_work_time_taken, 0,
sizeof(fib_walk_work_time_taken));
1189 clib_memset(fib_walk_work_nodes_visited, 0,
sizeof(fib_walk_work_nodes_visited));
1190 clib_memset(fib_walk_sleep_lengths, 0,
sizeof(fib_walk_sleep_lengths));
1196 .path =
"clear fib walk",
1197 .short_help =
"clear fib walk",
1205 fib_walk_process_node.index,
1214 fib_walk_process_node.index,
1228 else if (
unformat (input,
"disable"))
1240 .path =
"test fib-walk-process",
1241 .short_help =
"test fib-walk-process [enable|disable]",
#define HISTOGRAM_VISITS_PER_WALK_N_BUCKETS
vlib_log_class_t vlib_log_register_class(char *class, char *subclass)
#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)
clib_memset(h->entries, 0, sizeof(h->entries[0]) *entries)
#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...)
u8 * format_fib_node_bw_reason(u8 *s, va_list *args)
static fib_walk_queues_t fib_walk_queues
The global queues of outstanding walks.
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 VLIB_REGISTER_NODE(x,...)
#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)
#define FIB_WALK_DBG(_walk, _fmt, _args...)
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
vlib_log_class_t fib_walk_logger
#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 u8 * format_fib_walk(u8 *s, va_list *ap)
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.
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.