FD.io VPP  v16.12-rc0-308-g931be3a
Vector Packet Processing
fib_walk.c
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2016 Cisco and/or its affiliates.
3  * Licensed under the Apache License, Version 2.0 (the "License");
4  * you may not use this file except in compliance with the License.
5  * You may obtain a copy of the License at:
6  *
7  * http://www.apache.org/licenses/LICENSE-2.0
8  *
9  * Unless required by applicable law or agreed to in writing, software
10  * distributed under the License is distributed on an "AS IS" BASIS,
11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12  * See the License for the specific language governing permissions and
13  * limitations under the License.
14  */
15 
16 #include <vnet/fib/fib_walk.h>
17 #include <vnet/fib/fib_node_list.h>
18 
19 /**
20  * The flags on a walk
21  */
22 typedef enum fib_walk_flags_t_
23 {
24  /**
25  * A synchronous walk.
26  * This walk will run to completion, i.e. visit ALL the children.
27  * It is a depth first traversal of the graph.
28  */
29  FIB_WALK_FLAG_SYNC = (1 << 0),
30  /**
31  * An asynchronous walk.
32  * This walk will be scheduled to run in the background. It will thus visits
33  * the children at a later point in time.
34  * It is a depth first traversal of the graph.
35  */
36  FIB_WALK_FLAG_ASYNC = (1 << 1),
37  /**
38  * An indication that the walk is currently executing.
39  */
42 
43 /**
44  * A representation of a graph walk from a parent object to its children
45  */
46 typedef struct fib_walk_t_
47 {
48  /**
49  * FIB node linkage. This object is not in the FIB object graph,
50  * but it is present in other node's dependency lists, so it needs to
51  * be pointerable to.
52  */
54 
55  /**
56  * the walk's flags
57  */
59 
60  /**
61  * Sibling index in the dependency list
62  */
64 
65  /**
66  * Sibling index in the list of all walks
67  */
69 
70  /**
71  * Pointer to the node whose dependants this walk is walking
72  */
74 
75  /**
76  * Number of nodes visited by this walk. saved for debugging purposes.
77  */
79 
80  /**
81  * Time the walk started
82  */
84 
85  /**
86  * The reasons this walk is occuring.
87  * This is a vector ordered in time. The reasons and the front were started
88  * first, and so should be acted first when a node is visisted.
89  */
91 } fib_walk_t;
92 
93 /**
94  * @brief The pool of all walk objects
95  */
97 
98 /**
99  * @brief There's only one event type sent to the walk process
100  */
101 #define FIB_WALK_EVENT 0
102 
103 /**
104  * Statistics maintained per-walk queue
105  */
107 {
111 #define FIB_WALK_QUEUE_STATS_NUM (FIB_WALK_COMPLETED+1)
112 
113 #define FIB_WALK_QUEUE_STATS { \
114  [FIB_WALK_SCHEDULED] = "scheduled", \
115  [FIB_WALK_COMPLETED] = "completed", \
116 }
117 
118 #define FOR_EACH_FIB_WALK_QUEUE_STATS(_wqs) \
119  for ((_wqs) = FIB_WALK_SCHEDULED; \
120  (_wqs) < FIB_WALK_QUEUE_STATS_NUM; \
121  (_wqs)++)
122 
123 /**
124  * The names of the walk stats
125  */
126 static const char * const fib_walk_queue_stats_names[] = FIB_WALK_QUEUE_STATS;
127 
128 /**
129  * A represenation of one queue of walk
130  */
131 typedef struct fib_walk_queue_t_
132 {
133  /**
134  * Qeuee stats
135  */
137 
138  /**
139  * The node list which acts as the queue
140  */
143 
144 /**
145  * A set of priority queues for outstanding walks
146  */
147 typedef struct fib_walk_queues_t_
148 {
151 
152 /**
153  * The global queues of outstanding walks
154  */
156 
157 /**
158  * The names of the walk priorities
159  */
160 static const char * const fib_walk_priority_names[] = FIB_WALK_PRIORITIES;
161 
162 /**
163  * @brief Histogram stats on the lenths of each walk in elemenets visisted.
164  * Store upto 1<<23 elements in increments of 1<<10
165  */
166 #define HISTOGRAM_VISITS_PER_WALK_MAX (1<<23)
167 #define HISTOGRAM_VISITS_PER_WALK_INCR (1<<10)
168 #define HISTOGRAM_VISITS_PER_WALK_N_BUCKETS \
169  (HISTOGRAM_VISITS_PER_WALK_MAX/HISTOGRAM_VISITS_PER_WALK_INCR)
170 static u64 fib_walk_hist_vists_per_walk[HISTOGRAM_VISITS_PER_WALK_N_BUCKETS];
171 
172 /**
173  * @brief History of state for the last 128 walks
174  */
175 #define HISTORY_N_WALKS 128
177 typedef struct fib_walk_history_t_ {
182 static fib_walk_history_t fib_walk_history[HISTORY_N_WALKS];
183 
184 u8*
185 format_fib_walk_priority (u8 *s, va_list ap)
186 {
187  fib_walk_priority_t prio = va_arg(ap, fib_walk_priority_t);
188 
190 
191  return (format(s, "%s", fib_walk_priority_names[prio]));
192 }
193 static u8*
195 {
196  fib_walk_queue_stats_t wqs = va_arg(ap, fib_walk_queue_stats_t);
197 
199 
200  return (format(s, "%s", fib_walk_queue_stats_names[wqs]));
201 }
202 
203 static index_t
205 {
206  return (fwalk - fib_walk_pool);
207 }
208 
209 static fib_walk_t *
211 {
212  return (pool_elt_at_index(fib_walk_pool, fwi));
213 }
214 
215 /*
216  * not static so it can be used in the unit tests
217  */
218 u32
220 {
221  return (fib_node_list_get_size(fib_walk_queues.fwqs_queues[prio].fwq_queue));
222 }
223 
224 static fib_node_index_t
226 {
227  fib_node_ptr_t wp;
228 
229  fib_node_list_get_front(fib_walk_queues.fwqs_queues[prio].fwq_queue, &wp);
230 
231  return (wp.fnp_index);
232 }
233 
234 static void
236 {
237  u32 bucket;
238 
240  {
242  }
244  fwalk->fw_parent.fnp_index,
245  fwalk->fw_dep_sibling);
246 
247  /*
248  * add the stats to the continuous histogram collection.
249  */
250  bucket = (fwalk->fw_n_visits / HISTOGRAM_VISITS_PER_WALK_INCR);
251  bucket = (bucket >= HISTOGRAM_VISITS_PER_WALK_N_BUCKETS ?
253  bucket);
254  fib_walk_hist_vists_per_walk[bucket]++;
255 
256  /*
257  * save stats to the recent history
258  */
259 
260  fib_walk_history[history_last_walk_pos].fwh_n_visits =
261  fwalk->fw_n_visits;
262  fib_walk_history[history_last_walk_pos].fwh_duration =
264  fib_walk_history[history_last_walk_pos].fwh_parent =
265  fwalk->fw_parent;
266 
267  history_last_walk_pos = (history_last_walk_pos + 1) % HISTORY_N_WALKS;
268 
269  fib_node_deinit(&fwalk->fw_node);
270  pool_put(fib_walk_pool, fwalk);
271 }
272 
273 /**
274  * return code when advancing a walk
275  */
277 {
278  /**
279  * The walk is complete
280  */
282  /**
283  * the walk has more work
284  */
286  /**
287  * The walk merged with the one in front
288  */
291 
292 /**
293  * @brief Advance the walk one element in its work list
294  */
295 static fib_walk_advance_rc_t
297 {
300  fib_node_ptr_t sibling;
301  fib_walk_t *fwalk;
302  int more_elts;
303 
304  /*
305  * this walk function is re-entrant - walks acan spawn walks.
306  * fib_walk_t objects come from a pool, so they can realloc. we need
307  * to retch from said pool at the appropriate times.
308  */
309  fwalk = fib_walk_get(fwi);
310 
311  more_elts = fib_node_list_elt_get_next(fwalk->fw_dep_sibling, &sibling);
312 
313  if (more_elts)
314  {
315  vec_foreach(ctx, fwalk->fw_ctx)
316  {
317  wrc = fib_node_back_walk_one(&sibling, ctx);
318 
319  fwalk = fib_walk_get(fwi);
320  fwalk->fw_n_visits++;
321 
322  if (FIB_NODE_BACK_WALK_MERGE == wrc)
323  {
324  /*
325  * this walk has merged with the one further along the node's
326  * dependecy list.
327  */
328  return (FIB_WALK_ADVANCE_MERGE);
329  }
330  }
331  /*
332  * move foward to the next node to visit
333  */
334  more_elts = fib_node_list_advance(fwalk->fw_dep_sibling);
335  }
336 
337  if (more_elts)
338  {
339  return (FIB_WALK_ADVANCE_MORE);
340  }
341 
342  return (FIB_WALK_ADVANCE_DONE);
343 }
344 
345 /**
346  * @breif Enurmerate the times of sleep between walks
347  */
349 {
353 
354 #define FIB_WALK_N_SLEEP (FIB_WALK_LONG_SLEEP+1)
355 
356 /**
357  * @brief Durations for the sleep types
358  */
359 static f64 fib_walk_sleep_duration[] = {
360  [FIB_WALK_LONG_SLEEP] = 1e-3,
361  [FIB_WALK_SHORT_SLEEP] = 1e-8,
362 };
363 
364 /**
365  * @brief The time quota for a walk. When more than this amount of time is
366  * spent, the walk process will yield.
367  */
368 static f64 quota = 1e-4;
369 
370 /**
371  * Histogram on the amount of work done (in msecs) in each walk
372  */
373 #define N_TIME_BUCKETS 128
374 #define TIME_INCREMENTS (N_TIME_BUCKETS/2)
375 static u64 fib_walk_work_time_taken[N_TIME_BUCKETS];
376 
377 /**
378  * Histogram on the number of nodes visted in each quota
379  */
380 #define N_ELTS_BUCKETS 128
381 static u32 fib_walk_work_nodes_visisted_incr = 2;
382 static u64 fib_walk_work_nodes_visited[N_ELTS_BUCKETS];
383 
384 /**
385  * Histogram of the sleep lengths
386  */
387 static u64 fib_walk_sleep_lengths[2];
388 
389 /**
390  * @brief Service the queues
391  * This is not declared static so that it can be unit tested - i know i know...
392  */
393 f64
395  const f64 quota)
396 {
397  f64 start_time, consumed_time;
398  fib_walk_sleep_type_t sleep;
399  fib_walk_priority_t prio;
400  fib_walk_advance_rc_t rc;
401  fib_node_index_t fwi;
402  fib_walk_t *fwalk;
403  u32 n_elts;
404  i32 bucket;
405 
406  consumed_time = 0;
407  start_time = vlib_time_now(vm);
408  n_elts = 0;
409 
411  {
412  while (0 != fib_walk_queue_get_size(prio))
413  {
414  fwi = fib_walk_queue_get_front(prio);
415 
416  /*
417  * set this walk as executing
418  */
419  fwalk = fib_walk_get(fwi);
421 
422  do
423  {
424  rc = fib_walk_advance(fwi);
425  n_elts++;
426  consumed_time = (vlib_time_now(vm) - start_time);
427  } while ((consumed_time < quota) &&
428  (FIB_WALK_ADVANCE_MORE == rc));
429 
430  /*
431  * if this walk has no more work then pop it from the queue
432  * and move on to the next.
433  */
434  if (FIB_WALK_ADVANCE_MORE != rc)
435  {
436  fwalk = fib_walk_get(fwi);
437  fib_walk_destroy(fwalk);
438  fib_walk_queues.fwqs_queues[prio].fwq_stats[FIB_WALK_COMPLETED]++;
439  }
440  else
441  {
442  /*
443  * passed our work quota. sleep time.
444  */
445  fwalk = fib_walk_get(fwi);
447  sleep = FIB_WALK_SHORT_SLEEP;
448  goto that_will_do_for_now;
449  }
450  }
451  }
452  /*
453  * got to the end of all the work
454  */
455  sleep = FIB_WALK_LONG_SLEEP;
456 
457 that_will_do_for_now:
458 
459  /*
460  * collect the stats:
461  * - for the number of nodes visisted we store 128 increments
462  * - for the time consumed we store quota/TIME_INCREMENTS increments.
463  */
465  N_ELTS_BUCKETS-1 :
466  n_elts/fib_walk_work_nodes_visisted_incr);
467  ++fib_walk_work_nodes_visited[bucket];
468 
469  bucket = (consumed_time - quota) / (quota / TIME_INCREMENTS);
470  bucket += N_TIME_BUCKETS/2;
471  bucket = (bucket < 0 ? 0 : bucket);
472  bucket = (bucket > N_TIME_BUCKETS-1 ? N_TIME_BUCKETS-1 : bucket);
473  ++fib_walk_work_time_taken[bucket];
474 
475  ++fib_walk_sleep_lengths[sleep];
476 
477  return (fib_walk_sleep_duration[sleep]);
478 }
479 
480 /**
481  * @brief The 'fib-walk' process's main loop.
482  */
483 static uword
485  vlib_node_runtime_t * node,
486  vlib_frame_t * f)
487 {
488  f64 sleep_time;
489 
490  sleep_time = fib_walk_sleep_duration[FIB_WALK_SHORT_SLEEP];
491 
492  while (1)
493  {
494  vlib_process_wait_for_event_or_clock(vm, sleep_time);
495 
496  /*
497  * there may be lots of event queued between the processes,
498  * but the walks we want to schedule are in the priority queues,
499  * so we ignore the process events.
500  */
502 
503  sleep_time = fib_walk_process_queues(vm, quota);
504  }
505 
506  /*
507  * Unreached
508  */
509  ASSERT(!"WTF");
510  return 0;
511 }
512 
513 /* *INDENT-OFF* */
514 VLIB_REGISTER_NODE (fib_walk_process_node,static) = {
515  .function = fib_walk_process,
516  .type = VLIB_NODE_TYPE_PROCESS,
517  .name = "fib-walk",
518 };
519 /* *INDENT-ON* */
520 
521 /**
522  * @brief Allocate a new walk object
523  */
524 static fib_walk_t *
526  fib_node_index_t parent_index,
529 {
530  fib_walk_t *fwalk;
531 
532  pool_get(fib_walk_pool, fwalk);
533 
535 
536  fwalk->fw_flags = flags;
539  fwalk->fw_parent.fnp_index = parent_index;
540  fwalk->fw_parent.fnp_type = parent_type;
541  fwalk->fw_ctx = NULL;
543  fwalk->fw_n_visits = 0;
544 
545  /*
546  * make a copy of the backwalk context so the depth count remains
547  * the same for each sibling visitsed. This is important in the case
548  * where a parents has a loop via one child, but all the others are not.
549  * if the looped child were visited first, the depth count would exceed, the
550  * max and the walk would terminate before it reached the other siblings.
551  */
552  vec_add1(fwalk->fw_ctx, *ctx);
553 
554  return (fwalk);
555 }
556 
557 /**
558  * @brief Enqueue a walk onto the appropriate priority queue. Then signal
559  * the background process there is work to do.
560  */
561 static index_t
563  fib_walk_t *fwalk)
564 {
565  index_t sibling;
566 
567  sibling = fib_node_list_push_front(fib_walk_queues.fwqs_queues[prio].fwq_queue,
568  0,
570  fib_walk_get_index(fwalk));
571  fib_walk_queues.fwqs_queues[prio].fwq_stats[FIB_WALK_SCHEDULED]++;
572 
573  /*
574  * poke the fib-walk process to perform the async walk.
575  * we are not passing it specific data, hence the last two args,
576  * the process will drain the queues
577  */
579  fib_walk_process_node.index,
582 
583  return (sibling);
584 }
585 
586 void
588  fib_node_index_t parent_index,
589  fib_walk_priority_t prio,
591 {
592  fib_walk_t *fwalk;
593 
594  if (FIB_NODE_GRAPH_MAX_DEPTH < ++ctx->fnbw_depth)
595  {
596  /*
597  * The walk has reached the maximum depth. there is a loop in the graph.
598  * bail.
599  */
600  return;
601  }
602 
603  fwalk = fib_walk_alloc(parent_type,
604  parent_index,
606  ctx);
607 
608  fwalk->fw_dep_sibling = fib_node_child_add(parent_type,
609  parent_index,
611  fib_walk_get_index(fwalk));
612 
613  fwalk->fw_prio_sibling = fib_walk_prio_queue_enquue(prio, fwalk);
614 }
615 
616 /**
617  * @brief Back walk all the children of a FIB node.
618  *
619  * note this is a synchronous depth first walk. Children visited may propagate
620  * the walk to thier children. Other children node types may not propagate,
621  * synchronously but instead queue the walk for later async completion.
622  */
623 void
625  fib_node_index_t parent_index,
627 {
628  fib_walk_advance_rc_t rc;
629  fib_node_index_t fwi;
630  fib_walk_t *fwalk;
631 
632  if (FIB_NODE_GRAPH_MAX_DEPTH < ++ctx->fnbw_depth)
633  {
634  /*
635  * The walk has reached the maximum depth. there is a loop in the graph.
636  * bail.
637  */
638  return;
639  }
640 
641  fwalk = fib_walk_alloc(parent_type,
642  parent_index,
644  ctx);
645 
646  fwalk->fw_dep_sibling = fib_node_child_add(parent_type,
647  parent_index,
649  fib_walk_get_index(fwalk));
650  fwi = fib_walk_get_index(fwalk);
651 
652  while (1)
653  {
654  /*
655  * set this walk as executing
656  */
658 
659  do
660  {
661  rc = fib_walk_advance(fwi);
662  } while (FIB_WALK_ADVANCE_MORE == rc);
663 
664 
665  /*
666  * this walk function is re-entrant - walks can spawn walks.
667  * fib_walk_t objects come from a pool, so they can realloc. we need
668  * to re-fetch from said pool at the appropriate times.
669  */
670  fwalk = fib_walk_get(fwi);
671 
672  if (FIB_WALK_ADVANCE_MERGE == rc)
673  {
674  /*
675  * this sync walk merged with an walk in front.
676  * by reqeusting a sync walk the client wanted all children walked,
677  * so we ditch the walk object in hand and continue with the one
678  * we merged into
679  */
680  fib_node_ptr_t merged_walk;
681 
682  fib_node_list_elt_get_next(fwalk->fw_dep_sibling, &merged_walk);
683 
684  ASSERT(FIB_NODE_INDEX_INVALID != merged_walk.fnp_index);
685  ASSERT(FIB_NODE_TYPE_WALK == merged_walk.fnp_type);
686 
687  fib_walk_destroy(fwalk);
688 
689  fwi = merged_walk.fnp_index;
690  fwalk = fib_walk_get(fwi);
691 
692  if (FIB_WALK_FLAG_EXECUTING & fwalk->fw_flags)
693  {
694  /*
695  * we are executing a sync walk, and we have met with another
696  * walk that is also executing. since only one walk executs at once
697  * (there is no multi-threading) this implies we have met ourselves
698  * and hence the is a loop in the graph.
699  * This function is re-entrant, so the walk object we met is being
700  * acted on in a stack frame below this one. We must therefore not
701  * continue with it now, but let the stack unwind and along the
702  * appropriate frame to read the depth count and bail.
703  */
704  fwalk = NULL;
705  break;
706  }
707  }
708  else
709  {
710  /*
711  * the walk reached the end of the depdency list.
712  */
713  break;
714  }
715  }
716 
717  if (NULL != fwalk)
718  {
719  fib_walk_destroy(fwalk);
720  }
721 }
722 
723 static fib_node_t *
725 {
726  fib_walk_t *fwalk;
727 
728  fwalk = fib_walk_get(index);
729 
730  return (&(fwalk->fw_node));
731 }
732 
733 /**
734  * Walk objects are not parents, nor are they locked.
735  * are no-ops
736  */
737 static void
739 {
740  ASSERT(0);
741 }
742 
743 static fib_walk_t*
745 {
746  return ((fib_walk_t*)(((char*)node) -
748 }
749 
750 /**
751  * @brief Another back walk has reach this walk.
752  * Megre them so there is only one left. It is this node being
753  * visited that will remain, so copy or merge the context onto it.
754  */
758 {
760  fib_walk_t *fwalk;
761 
762  fwalk = fib_walk_get_from_node(node);
763 
764  /*
765  * check whether the walk context can be merge with another,
766  * or whether it needs to be appended.
767  */
768  vec_foreach(old, fwalk->fw_ctx)
769  {
770  /*
771  * we can merge walks if the reason for the walk is the same.
772  */
773  if (old->fnbw_reason == ctx->fnbw_reason)
774  {
775  /*
776  * copy the largest of the depth values. in the presence of a loop,
777  * the same walk will merge with itself. if we take the smaller depth
778  * then it will never end.
779  */
780  old->fnbw_depth = ((old->fnbw_depth >= ctx->fnbw_depth) ?
781  old->fnbw_depth :
782  ctx->fnbw_depth);
783  goto out;
784  }
785  }
786 
787  /*
788  * walks could not be merged, this means that the walk infront needs to
789  * perform different action to this one that has caught up. the one in front
790  * was scheduled first so append the new walk context to the back of the list.
791  */
792  vec_add1(fwalk->fw_ctx, *ctx);
793 
794 out:
795  return (FIB_NODE_BACK_WALK_MERGE);
796 }
797 
798 /**
799  * The FIB walk's graph node virtual function table
800  */
801 static const fib_node_vft_t fib_walk_vft = {
803  .fnv_last_lock = fib_walk_last_lock_gone,
804  .fnv_back_walk = fib_walk_back_walk_notify,
805 };
806 
807 void
809 {
810  fib_walk_priority_t prio;
811 
813  {
814  fib_walk_queues.fwqs_queues[prio].fwq_queue = fib_node_list_create();
815  }
816 
818 }
819 
820 static u8*
821 format_fib_walk (u8* s, va_list ap)
822 {
823  fib_node_index_t fwi = va_arg(ap, fib_node_index_t);
824  fib_walk_t *fwalk;
825 
826  fwalk = fib_walk_get(fwi);
827 
828  return (format(s, " parent:{%s:%d} visits:%d flags:%d",
830  fwalk->fw_parent.fnp_index,
831  fwalk->fw_n_visits,
832  fwalk->fw_flags));
833 }
834 
835 static clib_error_t *
837  unformat_input_t * input,
838  vlib_cli_command_t * cmd)
839 {
840  fib_walk_queue_stats_t wqs;
841  fib_walk_priority_t prio;
842  fib_node_ptr_t sibling;
843  fib_node_index_t fwi;
844  fib_walk_t *fwalk;
845  int more_elts, ii;
846  u8 *s = NULL;
847 
848 #define USEC 1000000
849  vlib_cli_output(vm, "FIB Walk Quota = %.2fusec:", quota * USEC);
850  vlib_cli_output(vm, "FIB Walk queues:");
851 
853  {
854  vlib_cli_output(vm, " %U priority queue:",
856  vlib_cli_output(vm, " Stats: ");
857 
859  {
860  vlib_cli_output(vm, " %U:%d",
862  fib_walk_queues.fwqs_queues[prio].fwq_stats[wqs]);
863  }
864  vlib_cli_output(vm, " Occupancy:%d",
866  fib_walk_queues.fwqs_queues[prio].fwq_queue));
867 
868  more_elts = fib_node_list_get_front(
869  fib_walk_queues.fwqs_queues[prio].fwq_queue,
870  &sibling);
871 
872  while (more_elts)
873  {
875  ASSERT(FIB_NODE_TYPE_WALK == sibling.fnp_type);
876 
877  fwi = sibling.fnp_index;
878  fwalk = fib_walk_get(fwi);
879 
880  vlib_cli_output(vm, " %U", format_fib_walk, fwi);
881 
882  more_elts = fib_node_list_elt_get_next(fwalk->fw_prio_sibling,
883  &sibling);
884  }
885  }
886 
887  vlib_cli_output(vm, "Histogram Statistics:");
888  vlib_cli_output(vm, " Number of Elements visit per-quota:");
889  for (ii = 0; ii < N_ELTS_BUCKETS; ii++)
890  {
891  if (0 != fib_walk_work_nodes_visited[ii])
892  s = format(s, "%d:%d ",
893  (ii * fib_walk_work_nodes_visisted_incr),
894  fib_walk_work_nodes_visited[ii]);
895  }
896  vlib_cli_output(vm, " %v", s);
897  vec_free(s);
898 
899  vlib_cli_output(vm, " Time consumed per-quota (Quota=%f usec):", quota*USEC);
900  s = format(s, "0:%d ", fib_walk_work_time_taken[0]);
901  for (ii = 1; ii < N_TIME_BUCKETS; ii++)
902  {
903  if (0 != fib_walk_work_time_taken[ii])
904  s = format(s, "%d:%d ", (u32)((((ii - N_TIME_BUCKETS/2) *
905  (quota / TIME_INCREMENTS)) + quota) *
906  USEC),
907  fib_walk_work_time_taken[ii]);
908  }
909  vlib_cli_output(vm, " %v", s);
910  vec_free(s);
911 
912  vlib_cli_output(vm, " Sleep Types:");
913  vlib_cli_output(vm, " Short Long:");
914  vlib_cli_output(vm, " %d %d:",
915  fib_walk_sleep_lengths[FIB_WALK_SHORT_SLEEP],
916  fib_walk_sleep_lengths[FIB_WALK_LONG_SLEEP]);
917 
918  vlib_cli_output(vm, " Number of Elements visited per-walk:");
919  for (ii = 0; ii < HISTOGRAM_VISITS_PER_WALK_N_BUCKETS; ii++)
920  {
921  if (0 != fib_walk_hist_vists_per_walk[ii])
922  s = format(s, "%d:%d ",
924  fib_walk_hist_vists_per_walk[ii]);
925  }
926  vlib_cli_output(vm, " %v", s);
927  vec_free(s);
928 
929 
930  vlib_cli_output(vm, "Brief History (last %d walks):", HISTORY_N_WALKS);
932  do
933  {
934  if (0 != fib_walk_history[ii].fwh_n_visits)
935  {
937  vm, " %s:%d visits:%d duration:%.2f ",
938  fib_node_type_get_name(fib_walk_history[ii].fwh_parent.fnp_type),
939  fib_walk_history[ii].fwh_parent.fnp_index,
940  fib_walk_history[ii].fwh_n_visits,
941  fib_walk_history[ii].fwh_duration);
942  }
943 
944  ii = (ii + 1) % HISTORY_N_WALKS;
945  } while (ii != history_last_walk_pos);
946 
947 
948  return (NULL);
949 }
950 
951 VLIB_CLI_COMMAND (fib_walk_show_command, static) = {
952  .path = "show fib walk",
953  .short_help = "show fib walk",
954  .function = fib_walk_show,
955 };
956 
957 static clib_error_t *
959  unformat_input_t * input,
960  vlib_cli_command_t * cmd)
961 {
962  clib_error_t * error = NULL;
963  f64 new_quota;
964 
965  if (unformat (input, "%f", &new_quota))
966  {
967  quota = new_quota;
968  }
969  else
970  {
971  error = clib_error_return(0 , "Pass a float value");
972  }
973 
974  return (error);
975 }
976 
977 VLIB_CLI_COMMAND (fib_walk_set_quota_command, static) = {
978  .path = "set fib walk quota",
979  .short_help = "set fib walk quota",
980  .function = fib_walk_set_quota,
981 };
982 
983 static clib_error_t *
985  unformat_input_t * input,
986  vlib_cli_command_t * cmd)
987 {
988  clib_error_t * error = NULL;
989  u32 new;
990 
991  if (unformat (input, "%d", &new))
992  {
993  fib_walk_work_nodes_visisted_incr = new;
994  }
995  else
996  {
997  error = clib_error_return(0 , "Pass an int value");
998  }
999 
1000  return (error);
1001 }
1002 
1003 VLIB_CLI_COMMAND (fib_walk_set_histogram_elements_size_command, static) = {
1004  .path = "set fib walk histogram elements size",
1005  .short_help = "set fib walk histogram elements size",
1007 };
1008 
1009 static clib_error_t *
1011  unformat_input_t * input,
1012  vlib_cli_command_t * cmd)
1013 {
1014  memset(fib_walk_hist_vists_per_walk, 0, sizeof(fib_walk_hist_vists_per_walk));
1015  memset(fib_walk_history, 0, sizeof(fib_walk_history));
1016  memset(fib_walk_work_time_taken, 0, sizeof(fib_walk_work_time_taken));
1017  memset(fib_walk_work_nodes_visited, 0, sizeof(fib_walk_work_nodes_visited));
1018  memset(fib_walk_sleep_lengths, 0, sizeof(fib_walk_sleep_lengths));
1019 
1020  return (NULL);
1021 }
1022 
1023 VLIB_CLI_COMMAND (fib_walk_clear_command, static) = {
1024  .path = "clear fib walk",
1025  .short_help = "clear fib walk",
1026  .function = fib_walk_clear,
1027 };
#define HISTOGRAM_VISITS_PER_WALK_N_BUCKETS
Definition: fib_walk.c:168
struct fib_walk_history_t_ fib_walk_history_t
void fib_node_list_elt_remove(u32 sibling)
u8 * format_fib_walk_priority(u8 *s, va_list ap)
Definition: fib_walk.c:185
u32 fw_dep_sibling
Sibling index in the dependency list.
Definition: fib_walk.c:63
static fib_walk_t * fib_walk_pool
The pool of all walk objects.
Definition: fib_walk.c:96
uword unformat(unformat_input_t *i, char *fmt,...)
Definition: unformat.c:966
enum fib_node_type_t_ fib_node_type_t
The types of nodes in a FIB graph.
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...
Definition: node_funcs.h:684
static vlib_main_t * vlib_get_main(void)
Definition: global_funcs.h:23
fib_walk_advance_rc_t_
return code when advancing a walk
Definition: fib_walk.c:276
static clib_error_t * fib_walk_set_quota(vlib_main_t *vm, unformat_input_t *input, vlib_cli_command_t *cmd)
Definition: fib_walk.c:958
fib_walk_queue_t fwqs_queues[FIB_WALK_PRIORITY_NUM]
Definition: fib_walk.c:149
An asynchronous walk.
Definition: fib_walk.c:36
void fib_node_init(fib_node_t *node, fib_node_type_t type)
Definition: fib_node.c:172
#define NULL
Definition: clib.h:55
#define N_TIME_BUCKETS
Histogram on the amount of work done (in msecs) in each walk.
Definition: fib_walk.c:373
static f64 vlib_time_now(vlib_main_t *vm)
Definition: main.h:182
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.
Definition: fib_walk.c:136
u32 index_t
A Data-Path Object is an object that represents actions that are applied to packets are they are swit...
Definition: dpo.h:41
#define vec_add1(V, E)
Add 1 element to end of vector (unspecified alignment).
Definition: vec.h:482
static fib_node_index_t fib_walk_queue_get_front(fib_walk_priority_t prio)
Definition: fib_walk.c:225
#define STRUCT_OFFSET_OF(t, f)
Definition: clib.h:62
void fib_node_deinit(fib_node_t *node)
Definition: fib_node.c:187
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)
Definition: fib_walk.c:587
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)
Definition: fib_walk.c:210
#define pool_get(P, E)
Allocate an object E from a pool P (unspecified alignment).
Definition: pool.h:200
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)
Definition: fib_node.c:96
void fib_node_register_type(fib_node_type_t type, const fib_node_vft_t *vft)
fib_node_register_type
Definition: fib_node.c:58
static uword fib_walk_process(vlib_main_t *vm, vlib_node_runtime_t *node, vlib_frame_t *f)
The &#39;fib-walk&#39; process&#39;s main loop.
Definition: fib_walk.c:484
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...
Definition: fib_walk.c:394
static void fib_walk_destroy(fib_walk_t *fwalk)
Definition: fib_walk.c:235
fib_node_index_t fnp_index
node&#39;s index
Definition: fib_node.h:149
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...
Definition: node_funcs.h:527
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.
Definition: fib_walk.c:624
fib_node_back_walk_rc_t fib_node_back_walk_one(fib_node_ptr_t *ptr, fib_node_back_walk_ctx_t *ctx)
Definition: fib_node.c:141
#define FOR_EACH_FIB_WALK_PRIORITY(_prio)
Definition: fib_walk.h:39
fib_node_back_walk_ctx_t * fw_ctx
The reasons this walk is occuring.
Definition: fib_walk.c:90
int i32
Definition: types.h:81
static fib_walk_queues_t fib_walk_queues
The global queues of outstanding walks.
Definition: fib_walk.c:155
unsigned long u64
Definition: types.h:89
A representation of a graph walk from a parent object to its children.
Definition: fib_walk.c:46
fib_walk_queue_stats_t_
Statistics maintained per-walk queue.
Definition: fib_walk.c:106
A representation of one pointer to another node.
Definition: fib_node.h:141
enum fib_walk_advance_rc_t_ fib_walk_advance_rc_t
return code when advancing a walk
#define HISTOGRAM_VISITS_PER_WALK_INCR
Definition: fib_walk.c:167
#define FIB_WALK_PRIORITY_NUM
Definition: fib_walk.h:32
fib_node_bw_reason_flag_t fnbw_reason
The reason/trigger for the backwalk.
Definition: fib_node.h:164
#define pool_elt_at_index(p, i)
Returns pointer to element at given index.
Definition: pool.h:369
fib_node_type_t fnp_type
node type
Definition: fib_node.h:145
static void vlib_process_signal_event(vlib_main_t *vm, uword node_index, uword type_opaque, uword data)
Definition: node_funcs.h:931
u32 fnbw_depth
the number of levels the walk has already traversed.
Definition: fib_node.h:172
#define FIB_WALK_QUEUE_STATS_NUM
Definition: fib_walk.c:111
The walk merged with the one in front.
Definition: fib_walk.c:289
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.
Definition: fib_walk.c:78
#define pool_put(P, E)
Free an object E in pool P.
Definition: pool.h:214
#define N_ELTS_BUCKETS
Histogram on the number of nodes visted in each quota.
Definition: fib_walk.c:380
fib_walk_flags_t fw_flags
the walk&#39;s flags
Definition: fib_walk.c:58
A set of priority queues for outstanding walks.
Definition: fib_walk.c:147
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.
Definition: fib_node.h:242
int fib_node_list_advance(u32 sibling)
Advance the sibling one step (toward the tail) in the list.
void vlib_cli_output(vlib_main_t *vm, char *fmt,...)
Definition: cli.c:575
enum fib_walk_flags_t_ fib_walk_flags_t
The flags on a walk.
#define FIB_WALK_PRIORITIES
Definition: fib_walk.h:34
static index_t fib_walk_get_index(fib_walk_t *fwalk)
Definition: fib_walk.c:204
#define vec_free(V)
Free vector&#39;s memory (no header).
Definition: vec.h:300
static u8 * format_fib_walk(u8 *s, va_list ap)
Definition: fib_walk.c:821
static u8 * format_fib_walk_queue_stats(u8 *s, va_list ap)
Definition: fib_walk.c:194
fib_node_get_t fnv_get
Definition: fib_node.h:230
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.
Definition: fib_walk.c:756
u32 fib_node_index_t
A typedef of a node index.
Definition: fib_types.h:28
u32 fib_walk_queue_get_size(fib_walk_priority_t prio)
Definition: fib_walk.c:219
void fib_walk_module_init(void)
Definition: fib_walk.c:808
enum fib_walk_priority_t_ fib_walk_priority_t
Walk priorities.
static f64 quota
The time quota for a walk.
Definition: fib_walk.c:368
fib_node_ptr_t fw_parent
Pointer to the node whose dependants this walk is walking.
Definition: fib_walk.c:73
Context passed between object during a back walk.
Definition: fib_node.h:160
#define VLIB_CLI_COMMAND(x,...)
Definition: cli.h:154
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.
Definition: fib_walk.c:525
An indication that the walk is currently executing.
Definition: fib_walk.c:40
f64 fw_start_time
Time the walk started.
Definition: fib_walk.c:83
A synchronous walk.
Definition: fib_walk.c:29
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.
Definition: fib_walk.c:562
#define USEC
u32 fib_node_list_get_size(fib_node_list_t list)
#define ASSERT(truth)
fib_node_list_t fib_node_list_create(void)
Create a new node list.
#define FIB_WALK_QUEUE_STATS
Definition: fib_walk.c:113
fib_walk_flags_t_
The flags on a walk.
Definition: fib_walk.c:22
unsigned int u32
Definition: types.h:88
fib_node_ptr_t fwh_parent
Definition: fib_walk.c:180
static u32 fib_walk_work_nodes_visisted_incr
Definition: fib_walk.c:381
static clib_error_t * fib_walk_clear(vlib_main_t *vm, unformat_input_t *input, vlib_cli_command_t *cmd)
Definition: fib_walk.c:1010
fib_walk_sleep_type_t_
Enurmerate the times of sleep between walks
Definition: fib_walk.c:348
void fib_node_child_remove(fib_node_type_t parent_type, fib_node_index_t parent_index, fib_node_index_t sibling_index)
Definition: fib_node.c:121
u64 uword
Definition: types.h:112
The walk is complete.
Definition: fib_walk.c:281
int fib_node_list_get_front(fib_node_list_t list, fib_node_ptr_t *ptr)
fib_node_list_t fwq_queue
The node list which acts as the queue.
Definition: fib_walk.c:141
#define FIB_WALK_EVENT
There&#39;s only one event type sent to the walk process.
Definition: fib_walk.c:101
#define FIB_NODE_INDEX_INVALID
Definition: fib_types.h:29
double f64
Definition: types.h:142
unsigned char u8
Definition: types.h:56
static fib_walk_t * fib_walk_get_from_node(fib_node_t *node)
Definition: fib_walk.c:744
static fib_node_t * fib_walk_get_node(fib_node_index_t index)
Definition: fib_walk.c:724
static clib_error_t * fib_walk_set_histogram_elements_size(vlib_main_t *vm, unformat_input_t *input, vlib_cli_command_t *cmd)
Definition: fib_walk.c:984
See the respective fib_*.h files for descriptions of these objects.
Definition: fib_node.h:32
#define TIME_INCREMENTS
Definition: fib_walk.c:374
#define HISTORY_N_WALKS
History of state for the last 128 walks.
Definition: fib_walk.c:175
A FIB graph nodes virtual function table.
Definition: fib_node.h:229
static clib_error_t * fib_walk_show(vlib_main_t *vm, unformat_input_t *input, vlib_cli_command_t *cmd)
Definition: fib_walk.c:836
fib_node_t fw_node
FIB node linkage.
Definition: fib_walk.c:53
#define VLIB_REGISTER_NODE(x,...)
Definition: node.h:143
u8 * format(u8 *s, const char *fmt,...)
Definition: format.c:418
u32 fib_node_list_t
A list of FIB nodes.
Definition: fib_node.h:155
int fib_node_list_elt_get_next(u32 sibling, fib_node_ptr_t *ptr)
#define vec_foreach(var, vec)
Vector iterator.
the walk has more work
Definition: fib_walk.c:285
static u32 history_last_walk_pos
Definition: fib_walk.c:176
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.
#define clib_error_return(e, args...)
Definition: error.h:111
struct _unformat_input_t unformat_input_t
u32 flags
Definition: vhost-user.h:75
u32 fw_prio_sibling
Sibling index in the list of all walks.
Definition: fib_walk.c:68
static void fib_walk_last_lock_gone(fib_node_t *node)
Walk objects are not parents, nor are they locked.
Definition: fib_walk.c:738
static fib_walk_advance_rc_t fib_walk_advance(fib_node_index_t fwi)
Advance the walk one element in its work list.
Definition: fib_walk.c:296
const char * fib_node_type_get_name(fib_node_type_t type)
Definition: fib_node.c:35
A represenation of one queue of walk.
Definition: fib_walk.c:131
#define FOR_EACH_FIB_WALK_QUEUE_STATS(_wqs)
Definition: fib_walk.c:118
struct fib_walk_queues_t_ fib_walk_queues_t
A set of priority queues for outstanding walks.