FD.io VPP  v19.04.4-rc0-5-ge88582fac
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 
20 
21 /**
22  * The flags on a walk
23  */
24 typedef enum fib_walk_flags_t_
25 {
26  /**
27  * A synchronous walk.
28  * This walk will run to completion, i.e. visit ALL the children.
29  * It is a depth first traversal of the graph.
30  */
31  FIB_WALK_FLAG_SYNC = (1 << 0),
32  /**
33  * An asynchronous walk.
34  * This walk will be scheduled to run in the background. It will thus visits
35  * the children at a later point in time.
36  * It is a depth first traversal of the graph.
37  */
38  FIB_WALK_FLAG_ASYNC = (1 << 1),
39  /**
40  * An indication that the walk is currently executing.
41  */
44 
45 /**
46  * A representation of a graph walk from a parent object to its children
47  */
48 typedef struct fib_walk_t_
49 {
50  /**
51  * FIB node linkage. This object is not in the FIB object graph,
52  * but it is present in other node's dependency lists, so it needs to
53  * be pointerable to.
54  */
56 
57  /**
58  * the walk's flags
59  */
61 
62  /**
63  * Sibling index in the dependency list
64  */
66 
67  /**
68  * Sibling index in the list of all walks
69  */
71 
72  /**
73  * Pointer to the node whose dependants this walk is walking
74  */
76 
77  /**
78  * Number of nodes visited by this walk. saved for debugging purposes.
79  */
81 
82  /**
83  * Time the walk started
84  */
86 
87  /**
88  * The reasons this walk is occuring.
89  * This is a vector ordered in time. The reasons and the front were started
90  * first, and so should be acted first when a node is visited.
91  */
93 } fib_walk_t;
94 
95 /**
96  * @brief The pool of all walk objects
97  */
99 
100 /**
101  * Statistics maintained per-walk queue
102  */
104 {
108 #define FIB_WALK_QUEUE_STATS_NUM ((fib_walk_queue_stats_t)(FIB_WALK_COMPLETED+1))
109 
110 #define FIB_WALK_QUEUE_STATS { \
111  [FIB_WALK_SCHEDULED] = "scheduled", \
112  [FIB_WALK_COMPLETED] = "completed", \
113 }
114 
115 #define FOR_EACH_FIB_WALK_QUEUE_STATS(_wqs) \
116  for ((_wqs) = FIB_WALK_SCHEDULED; \
117  (_wqs) < FIB_WALK_QUEUE_STATS_NUM; \
118  (_wqs)++)
119 
120 /**
121  * The names of the walk stats
122  */
123 static const char * const fib_walk_queue_stats_names[] = FIB_WALK_QUEUE_STATS;
124 /**
125  * The names of the walk reasons
126  */
127 static const char * const fib_node_bw_reason_names[] = FIB_NODE_BW_REASONS;
128 
129 /**
130  * A represenation of one queue of walk
131  */
132 typedef struct fib_walk_queue_t_
133 {
134  /**
135  * Qeuee stats
136  */
138 
139  /**
140  * The node list which acts as the queue
141  */
144 
145 /**
146  * A set of priority queues for outstanding walks
147  */
148 typedef struct fib_walk_queues_t_
149 {
152 
153 /**
154  * The global queues of outstanding walks
155  */
157 
158 /**
159  * The names of the walk priorities
160  */
161 static const char * const fib_walk_priority_names[] = FIB_WALK_PRIORITIES;
162 
163 /**
164  * @brief Histogram stats on the lenths of each walk in elemenets visited.
165  * Store upto 1<<23 elements in increments of 1<<10
166  */
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)
171 static u64 fib_walk_hist_vists_per_walk[HISTOGRAM_VISITS_PER_WALK_N_BUCKETS];
172 
173 /**
174  * @brief History of state for the last 128 walks
175  */
176 #define HISTORY_N_WALKS 128
177 #define MAX_HISTORY_REASONS 16
179 typedef struct fib_walk_history_t_ {
187 static fib_walk_history_t fib_walk_history[HISTORY_N_WALKS];
188 
189 static u8* format_fib_walk (u8* s, va_list *ap);
190 
191 #define FIB_WALK_DBG(_walk, _fmt, _args...) \
192 { \
193  vlib_log_debug(fib_walk_logger, \
194  "[%U]:" _fmt, \
195  format_fib_walk, \
196  fib_walk_get_index(_walk), \
197  ##_args); \
198 }
199 
200 u8*
201 format_fib_walk_priority (u8 *s, va_list *ap)
202 {
203  fib_walk_priority_t prio = va_arg(*ap, fib_walk_priority_t);
204 
206 
207  return (format(s, "%s", fib_walk_priority_names[prio]));
208 }
209 static u8*
211 {
212  fib_walk_queue_stats_t wqs = va_arg(*ap, fib_walk_queue_stats_t);
213 
215 
216  return (format(s, "%s", fib_walk_queue_stats_names[wqs]));
217 }
218 
219 static index_t
221 {
222  return (fwalk - fib_walk_pool);
223 }
224 
225 static fib_walk_t *
227 {
228  return (pool_elt_at_index(fib_walk_pool, fwi));
229 }
230 
231 /*
232  * not static so it can be used in the unit tests
233  */
234 u32
236 {
237  return (fib_node_list_get_size(fib_walk_queues.fwqs_queues[prio].fwq_queue));
238 }
239 
240 static fib_node_index_t
242 {
243  fib_node_ptr_t wp;
244 
245  fib_node_list_get_front(fib_walk_queues.fwqs_queues[prio].fwq_queue, &wp);
246 
247  return (wp.fnp_index);
248 }
249 
250 static void
252 {
253  fib_walk_t *fwalk;
254  u32 bucket, ii;
255 
256  fwalk = fib_walk_get(fwi);
257 
259  {
261  }
263  fwalk->fw_parent.fnp_index,
264  fwalk->fw_dep_sibling);
265 
266  /*
267  * refetch the walk object. More walks could have been spawned as a result
268  * of releasing the lock on the parent.
269  */
270  fwalk = fib_walk_get(fwi);
271 
272  /*
273  * add the stats to the continuous histogram collection.
274  */
275  bucket = (fwalk->fw_n_visits / HISTOGRAM_VISITS_PER_WALK_INCR);
276  bucket = (bucket >= HISTOGRAM_VISITS_PER_WALK_N_BUCKETS ?
278  bucket);
279  fib_walk_hist_vists_per_walk[bucket]++;
280 
281  /*
282  * save stats to the recent history
283  */
284 
285  fib_walk_history[history_last_walk_pos].fwh_n_visits =
286  fwalk->fw_n_visits;
287  fib_walk_history[history_last_walk_pos].fwh_completed =
289  fib_walk_history[history_last_walk_pos].fwh_duration =
290  fib_walk_history[history_last_walk_pos].fwh_completed -
291  fwalk->fw_start_time;
292  fib_walk_history[history_last_walk_pos].fwh_parent =
293  fwalk->fw_parent;
294  fib_walk_history[history_last_walk_pos].fwh_flags =
295  fwalk->fw_flags;
296 
297  vec_foreach_index(ii, fwalk->fw_ctx)
298  {
299  if (ii < MAX_HISTORY_REASONS)
300  {
301  fib_walk_history[history_last_walk_pos].fwh_reason[ii] =
302  fwalk->fw_ctx[ii].fnbw_reason;
303  }
304  }
305 
306  history_last_walk_pos = (history_last_walk_pos + 1) % HISTORY_N_WALKS;
307 
308  fib_node_deinit(&fwalk->fw_node);
309  vec_free(fwalk->fw_ctx);
310  pool_put(fib_walk_pool, fwalk);
311 }
312 
313 /**
314  * return code when advancing a walk
315  */
317 {
318  /**
319  * The walk is complete
320  */
322  /**
323  * the walk has more work
324  */
326  /**
327  * The walk merged with the one in front
328  */
331 
332 /**
333  * @brief Advance the walk one element in its work list
334  */
335 static fib_walk_advance_rc_t
337 {
339  fib_node_ptr_t sibling;
340  fib_walk_t *fwalk;
341  uint n_ctxs, ii;
342  int more_elts;
343 
344  /*
345  * this walk function is re-entrant - walks acan spawn walks.
346  * fib_walk_t objects come from a pool, so they can realloc. we need
347  * to retch from said pool at the appropriate times.
348  */
349  fwalk = fib_walk_get(fwi);
350 
351  more_elts = fib_node_list_elt_get_next(fwalk->fw_dep_sibling, &sibling);
352 
353  if (more_elts)
354  {
355 
356  /*
357  * loop through the backwalk contexts. This can grow in length
358  * as walks on the same object meet each other. Order is preserved so the
359  * most recently started walk as at the back of the vector.
360  */
361  ii = 0;
362  n_ctxs = vec_len(fwalk->fw_ctx);
363 
364  while (ii < n_ctxs)
365  {
366  fib_node_back_walk_ctx_t ctx = fwalk->fw_ctx[ii];
367 
368  wrc = fib_node_back_walk_one(&sibling, &ctx);
369 
370  ii++;
371  fwalk = fib_walk_get(fwi);
372  fwalk->fw_n_visits++;
373 
374  if (FIB_NODE_BACK_WALK_MERGE == wrc)
375  {
376  /*
377  * this walk has merged with the one further along the node's
378  * dependecy list.
379  */
380  return (FIB_WALK_ADVANCE_MERGE);
381  }
382 
383  /*
384  * re-evaluate the number of backwalk contexts we need to process.
385  */
386  n_ctxs = vec_len(fwalk->fw_ctx);
387  }
388  /*
389  * move foward to the next node to visit
390  */
391  more_elts = fib_node_list_advance(fwalk->fw_dep_sibling);
392  }
393 
394  if (more_elts)
395  {
396  return (FIB_WALK_ADVANCE_MORE);
397  }
398 
399  return (FIB_WALK_ADVANCE_DONE);
400 }
401 
402 /**
403  * @breif Enurmerate the times of sleep between walks
404  */
406 {
410 
411 #define FIB_WALK_N_SLEEP (FIB_WALK_LONG_SLEEP+1)
412 
413 /**
414  * @brief Durations for the sleep types
415  */
416 static f64 fib_walk_sleep_duration[] = {
417  /**
418  * Long sleep when there is no more work, i.e. the queues are empty.
419  * This is a sleep (as opposed to a wait for event) just to be sure we
420  * are not missing events by sleeping forever.
421  */
422  [FIB_WALK_LONG_SLEEP] = 2,
423 
424  /**
425  * Short sleep. There is work left in the queues. We are yielding the CPU
426  * momentarily.
427  */
428  [FIB_WALK_SHORT_SLEEP] = 1e-8,
429 };
430 
431 /**
432  * @brief The time quota for a walk. When more than this amount of time is
433  * spent, the walk process will yield.
434  */
435 static f64 quota = 1e-4;
436 
437 /**
438  * Histogram on the amount of work done (in msecs) in each walk
439  */
440 #define N_TIME_BUCKETS 128
441 #define TIME_INCREMENTS (N_TIME_BUCKETS/2)
442 static u64 fib_walk_work_time_taken[N_TIME_BUCKETS];
443 
444 /**
445  * Histogram on the number of nodes visted in each quota
446  */
447 #define N_ELTS_BUCKETS 128
448 static u32 fib_walk_work_nodes_visited_incr = 2;
449 static u64 fib_walk_work_nodes_visited[N_ELTS_BUCKETS];
450 
451 /**
452  * Histogram of the sleep lengths
453  */
454 static u64 fib_walk_sleep_lengths[2];
455 
456 /**
457  * @brief Service the queues
458  * This is not declared static so that it can be unit tested - i know i know...
459  */
460 f64
462  const f64 quota)
463 {
464  f64 start_time, consumed_time;
465  fib_walk_sleep_type_t sleep;
466  fib_walk_priority_t prio;
467  fib_walk_advance_rc_t rc;
468  fib_node_index_t fwi;
469  fib_walk_t *fwalk;
470  u32 n_elts;
471  i32 bucket;
472 
473  consumed_time = 0;
474  start_time = vlib_time_now(vm);
475  n_elts = 0;
476 
478  {
479  while (0 != fib_walk_queue_get_size(prio))
480  {
481  fwi = fib_walk_queue_get_front(prio);
482 
483  /*
484  * set this walk as executing
485  */
486  fwalk = fib_walk_get(fwi);
488 
489  do
490  {
491  rc = fib_walk_advance(fwi);
492  n_elts++;
493  consumed_time = (vlib_time_now(vm) - start_time);
494  } while ((consumed_time < quota) &&
495  (FIB_WALK_ADVANCE_MORE == rc));
496 
497  /*
498  * if this walk has no more work then pop it from the queue
499  * and move on to the next.
500  */
501  if (FIB_WALK_ADVANCE_MORE != rc)
502  {
503  fib_walk_destroy(fwi);
504  fib_walk_queues.fwqs_queues[prio].fwq_stats[FIB_WALK_COMPLETED]++;
505  }
506  else
507  {
508  /*
509  * passed our work quota. sleep time.
510  */
511  fwalk = fib_walk_get(fwi);
513  sleep = FIB_WALK_SHORT_SLEEP;
514  goto that_will_do_for_now;
515  }
516  }
517  }
518  /*
519  * got to the end of all the work
520  */
521  sleep = FIB_WALK_LONG_SLEEP;
522 
523 that_will_do_for_now:
524 
525  /*
526  * collect the stats:
527  * - for the number of nodes visited we store 128 increments
528  * - for the time consumed we store quota/TIME_INCREMENTS increments.
529  */
530  bucket = ((n_elts/fib_walk_work_nodes_visited_incr) > N_ELTS_BUCKETS ?
531  N_ELTS_BUCKETS-1 :
532  n_elts/fib_walk_work_nodes_visited_incr);
533  ++fib_walk_work_nodes_visited[bucket];
534 
535  bucket = (consumed_time - quota) / (quota / TIME_INCREMENTS);
536  bucket += N_TIME_BUCKETS/2;
537  bucket = (bucket < 0 ? 0 : bucket);
538  bucket = (bucket > N_TIME_BUCKETS-1 ? N_TIME_BUCKETS-1 : bucket);
539  ++fib_walk_work_time_taken[bucket];
540 
541  ++fib_walk_sleep_lengths[sleep];
542 
543  return (fib_walk_sleep_duration[sleep]);
544 }
545 
546 /**
547  * Events sent to the FIB walk process
548  */
550 {
555 
556 /**
557  * @brief The 'fib-walk' process's main loop.
558  */
559 static uword
561  vlib_node_runtime_t * node,
562  vlib_frame_t * f)
563 {
564  uword event_type, *event_data = 0;
565  f64 sleep_time;
566  int enabled;
567 
568  enabled = 1;
569  sleep_time = fib_walk_sleep_duration[FIB_WALK_SHORT_SLEEP];
570 
571  while (1)
572  {
573  /*
574  * the feature to disable/enable this walk process is only
575  * for testing purposes
576  */
577  if (enabled)
578  {
579  vlib_process_wait_for_event_or_clock(vm, sleep_time);
580  }
581  else
582  {
584  }
585 
586  event_type = vlib_process_get_events(vm, &event_data);
587  vec_reset_length(event_data);
588 
589  switch (event_type)
590  {
592  enabled = 1;
593  break;
595  enabled = 0;
596  break;
597  default:
598  break;
599  }
600 
601  if (enabled)
602  {
603  sleep_time = fib_walk_process_queues(vm, quota);
604  }
605  }
606 
607  /*
608  * Unreached
609  */
610  ASSERT(!"WTF");
611  return 0;
612 }
613 
614 /* *INDENT-OFF* */
615 VLIB_REGISTER_NODE (fib_walk_process_node,static) = {
616  .function = fib_walk_process,
617  .type = VLIB_NODE_TYPE_PROCESS,
618  .name = "fib-walk",
619 };
620 /* *INDENT-ON* */
621 
622 /**
623  * @brief Allocate a new walk object
624  */
625 static fib_walk_t *
627  fib_node_index_t parent_index,
630 {
631  fib_walk_t *fwalk;
632 
633  pool_get(fib_walk_pool, fwalk);
634 
636 
637  fwalk->fw_flags = flags;
640  fwalk->fw_parent.fnp_index = parent_index;
641  fwalk->fw_parent.fnp_type = parent_type;
642  fwalk->fw_ctx = NULL;
644  fwalk->fw_n_visits = 0;
645 
646  /*
647  * make a copy of the backwalk context so the depth count remains
648  * the same for each sibling visitsed. This is important in the case
649  * where a parent has a loop via one child, but all the others are not.
650  * if the looped child were visited first, the depth count would exceed, the
651  * max and the walk would terminate before it reached the other siblings.
652  */
653  vec_add1(fwalk->fw_ctx, *ctx);
654 
655  return (fwalk);
656 }
657 
658 /**
659  * @brief Enqueue a walk onto the appropriate priority queue. Then signal
660  * the background process there is work to do.
661  */
662 static index_t
664  fib_walk_t *fwalk)
665 {
666  index_t sibling;
667 
668  sibling = fib_node_list_push_front(fib_walk_queues.fwqs_queues[prio].fwq_queue,
669  0,
671  fib_walk_get_index(fwalk));
672  fib_walk_queues.fwqs_queues[prio].fwq_stats[FIB_WALK_SCHEDULED]++;
673 
674  /*
675  * poke the fib-walk process to perform the async walk.
676  * we are not passing it specific data, hence the last two args,
677  * the process will drain the queues
678  */
680  fib_walk_process_node.index,
682  0);
683 
684  return (sibling);
685 }
686 
687 void
689  fib_node_index_t parent_index,
690  fib_walk_priority_t prio,
692 {
693  fib_walk_t *fwalk;
694 
695  if (FIB_NODE_GRAPH_MAX_DEPTH < ++ctx->fnbw_depth)
696  {
697  /*
698  * The walk has reached the maximum depth. there is a loop in the graph.
699  * bail.
700  */
701  return;
702  }
703  if (0 == fib_node_get_n_children(parent_type,
704  parent_index))
705  {
706  /*
707  * no children to walk - quit now
708  */
709  return;
710  }
712  {
713  /*
714  * the originator of the walk wanted it to be synchronous, but the
715  * parent object chose async - denied.
716  */
717  return (fib_walk_sync(parent_type, parent_index, ctx));
718  }
719 
720 
721  fwalk = fib_walk_alloc(parent_type,
722  parent_index,
724  ctx);
725 
726  fwalk->fw_dep_sibling = fib_node_child_add(parent_type,
727  parent_index,
729  fib_walk_get_index(fwalk));
730 
731  fwalk->fw_prio_sibling = fib_walk_prio_queue_enquue(prio, fwalk);
732 
733  FIB_WALK_DBG(fwalk, "async-start: %U",
735 }
736 
737 /**
738  * @brief Back walk all the children of a FIB node.
739  *
740  * note this is a synchronous depth first walk. Children visited may propagate
741  * the walk to thier children. Other children node types may not propagate,
742  * synchronously but instead queue the walk for later async completion.
743  */
744 void
746  fib_node_index_t parent_index,
748 {
749  fib_walk_advance_rc_t rc;
750  fib_node_index_t fwi;
751  fib_walk_t *fwalk;
752 
753  if (FIB_NODE_GRAPH_MAX_DEPTH < ++ctx->fnbw_depth)
754  {
755  /*
756  * The walk has reached the maximum depth. there is a loop in the graph.
757  * bail.
758  */
759  return;
760  }
761  if (0 == fib_node_get_n_children(parent_type,
762  parent_index))
763  {
764  /*
765  * no children to walk - quit now
766  */
767  return;
768  }
769 
770  fwalk = fib_walk_alloc(parent_type,
771  parent_index,
773  ctx);
774 
775  fwalk->fw_dep_sibling = fib_node_child_add(parent_type,
776  parent_index,
778  fib_walk_get_index(fwalk));
779  fwi = fib_walk_get_index(fwalk);
780  FIB_WALK_DBG(fwalk, "sync-start: %U",
782 
783  while (1)
784  {
785  /*
786  * set this walk as executing
787  */
789 
790  do
791  {
792  rc = fib_walk_advance(fwi);
793  } while (FIB_WALK_ADVANCE_MORE == rc);
794 
795 
796  /*
797  * this walk function is re-entrant - walks can spawn walks.
798  * fib_walk_t objects come from a pool, so they can realloc. we need
799  * to re-fetch from said pool at the appropriate times.
800  */
801  fwalk = fib_walk_get(fwi);
802 
803  if (FIB_WALK_ADVANCE_MERGE == rc)
804  {
805  /*
806  * this sync walk merged with an walk in front.
807  * by reqeusting a sync walk the client wanted all children walked,
808  * so we ditch the walk object in hand and continue with the one
809  * we merged into
810  */
811  fib_node_ptr_t merged_walk;
812 
813  fib_node_list_elt_get_next(fwalk->fw_dep_sibling, &merged_walk);
814 
815  ASSERT(FIB_NODE_INDEX_INVALID != merged_walk.fnp_index);
816  ASSERT(FIB_NODE_TYPE_WALK == merged_walk.fnp_type);
817 
818  fib_walk_destroy(fwi);
819 
820  fwi = merged_walk.fnp_index;
821  fwalk = fib_walk_get(fwi);
822 
823  if (FIB_WALK_FLAG_EXECUTING & fwalk->fw_flags)
824  {
825  /*
826  * we are executing a sync walk, and we have met with another
827  * walk that is also executing. since only one walk executs at once
828  * (there is no multi-threading) this implies we have met ourselves
829  * and hence the is a loop in the graph.
830  * This function is re-entrant, so the walk object we met is being
831  * acted on in a stack frame below this one. We must therefore not
832  * continue with it now, but let the stack unwind and along the
833  * appropriate frame to read the depth count and bail.
834  */
835  FIB_WALK_DBG(fwalk, "sync-stop: %U",
837  ctx->fnbw_reason);
838 
839  fwalk = NULL;
840  break;
841  }
842  }
843  else
844  {
845  /*
846  * the walk reached the end of the depdency list.
847  */
848  break;
849  }
850  }
851 
852  if (NULL != fwalk)
853  {
854  FIB_WALK_DBG(fwalk, "sync-stop: %U",
856  ctx->fnbw_reason);
857  fib_walk_destroy(fwi);
858  }
859 }
860 
861 static fib_node_t *
863 {
864  fib_walk_t *fwalk;
865 
866  fwalk = fib_walk_get(index);
867 
868  return (&(fwalk->fw_node));
869 }
870 
871 /**
872  * Walk objects are not parents, nor are they locked.
873  * are no-ops
874  */
875 static void
877 {
878  ASSERT(0);
879 }
880 
881 static fib_walk_t*
883 {
884  return ((fib_walk_t*)(((char*)node) -
886 }
887 
888 /**
889  * @brief Another back walk has reach this walk.
890  * Megre them so there is only one left. It is this node being
891  * visited that will remain, so copy or merge the context onto it.
892  */
896 {
898  fib_walk_t *fwalk;
899 
900  fwalk = fib_walk_get_from_node(node);
901 
902  /*
903  * check whether the walk context can be merged with the most recent.
904  * the most recent was the one last added and is thus at the back of the vector.
905  * we can merge walks if the reason for the walk is the same.
906  */
907  last = vec_end(fwalk->fw_ctx) - 1;
908 
909  if (last->fnbw_reason == ctx->fnbw_reason)
910  {
911  /*
912  * copy the largest of the depth values. in the presence of a loop,
913  * the same walk will merge with itself. if we take the smaller depth
914  * then it will never end.
915  */
916  last->fnbw_depth = ((last->fnbw_depth >= ctx->fnbw_depth) ?
917  last->fnbw_depth :
918  ctx->fnbw_depth);
919  }
920  else
921  {
922  /*
923  * walks could not be merged, this means that the walk infront needs to
924  * perform different action to this one that has caught up. the one in
925  * front was scheduled first so append the new walk context to the back
926  * of the list.
927  */
928  vec_add1(fwalk->fw_ctx, *ctx);
929  }
930 
931  return (FIB_NODE_BACK_WALK_MERGE);
932 }
933 
934 /**
935  * The FIB walk's graph node virtual function table
936  */
937 static const fib_node_vft_t fib_walk_vft = {
939  .fnv_last_lock = fib_walk_last_lock_gone,
940  .fnv_back_walk = fib_walk_back_walk_notify,
941 };
942 
943 void
945 {
946  fib_walk_priority_t prio;
947 
949  {
950  fib_walk_queues.fwqs_queues[prio].fwq_queue = fib_node_list_create();
951  }
952 
954  fib_walk_logger = vlib_log_register_class("fib", "walk");
955 }
956 
957 static u8*
958 format_fib_walk (u8* s, va_list *ap)
959 {
960  fib_node_index_t fwi = va_arg(*ap, fib_node_index_t);
961  fib_walk_t *fwalk;
962 
963  fwalk = fib_walk_get(fwi);
964 
965  return (format(s, "[@%d] parent:{%s:%d} visits:%d flags:%d", fwi,
967  fwalk->fw_parent.fnp_index,
968  fwalk->fw_n_visits,
969  fwalk->fw_flags));
970 }
971 
972 u8 *
973 format_fib_node_bw_reason (u8 *s, va_list *args)
974 {
975  fib_node_bw_reason_flag_t flag = va_arg (*args, int);
977 
979  if ((1<<reason) & flag)
980  s = format(s, "%s", fib_node_bw_reason_names[reason]);
981  }
982 
983  return (s);
984 }
985 
986 static clib_error_t *
988  unformat_input_t * input,
989  vlib_cli_command_t * cmd)
990 {
991  fib_walk_queue_stats_t wqs;
992  fib_walk_priority_t prio;
993  fib_node_ptr_t sibling;
994  fib_node_index_t fwi;
995  fib_walk_t *fwalk;
996  int more_elts, ii;
997  u8 *s = NULL;
998 
999 #define USEC 1000000
1000  vlib_cli_output(vm, "FIB Walk Quota = %.2fusec:", quota * USEC);
1001  vlib_cli_output(vm, "FIB Walk queues:");
1002 
1004  {
1005  vlib_cli_output(vm, " %U priority queue:",
1006  format_fib_walk_priority, prio);
1007  vlib_cli_output(vm, " Stats: ");
1008 
1010  {
1011  vlib_cli_output(vm, " %U:%d",
1013  fib_walk_queues.fwqs_queues[prio].fwq_stats[wqs]);
1014  }
1015  vlib_cli_output(vm, " Occupancy:%d",
1017  fib_walk_queues.fwqs_queues[prio].fwq_queue));
1018 
1019  more_elts = fib_node_list_get_front(
1020  fib_walk_queues.fwqs_queues[prio].fwq_queue,
1021  &sibling);
1022 
1023  while (more_elts)
1024  {
1026  ASSERT(FIB_NODE_TYPE_WALK == sibling.fnp_type);
1027 
1028  fwi = sibling.fnp_index;
1029  fwalk = fib_walk_get(fwi);
1030 
1031  vlib_cli_output(vm, " %U", format_fib_walk, fwi);
1032 
1033  more_elts = fib_node_list_elt_get_next(fwalk->fw_prio_sibling,
1034  &sibling);
1035  }
1036  }
1037 
1038  vlib_cli_output(vm, "Histogram Statistics:");
1039  vlib_cli_output(vm, " Number of Elements visit per-quota:");
1040  for (ii = 0; ii < N_ELTS_BUCKETS; ii++)
1041  {
1042  if (0 != fib_walk_work_nodes_visited[ii])
1043  s = format(s, "%d:%d ",
1044  (ii * fib_walk_work_nodes_visited_incr),
1045  fib_walk_work_nodes_visited[ii]);
1046  }
1047  vlib_cli_output(vm, " %v", s);
1048  vec_free(s);
1049 
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]);
1052  for (ii = 1; ii < N_TIME_BUCKETS; ii++)
1053  {
1054  if (0 != fib_walk_work_time_taken[ii])
1055  s = format(s, "%d:%d ", (u32)((((ii - N_TIME_BUCKETS/2) *
1056  (quota / TIME_INCREMENTS)) + quota) *
1057  USEC),
1058  fib_walk_work_time_taken[ii]);
1059  }
1060  vlib_cli_output(vm, " %v", s);
1061  vec_free(s);
1062 
1063  vlib_cli_output(vm, " Sleep Types:");
1064  vlib_cli_output(vm, " Short Long:");
1065  vlib_cli_output(vm, " %d %d:",
1066  fib_walk_sleep_lengths[FIB_WALK_SHORT_SLEEP],
1067  fib_walk_sleep_lengths[FIB_WALK_LONG_SLEEP]);
1068 
1069  vlib_cli_output(vm, " Number of Elements visited per-walk:");
1070  for (ii = 0; ii < HISTOGRAM_VISITS_PER_WALK_N_BUCKETS; ii++)
1071  {
1072  if (0 != fib_walk_hist_vists_per_walk[ii])
1073  s = format(s, "%d:%d ",
1075  fib_walk_hist_vists_per_walk[ii]);
1076  }
1077  vlib_cli_output(vm, " %v", s);
1078  vec_free(s);
1079 
1080 
1081  vlib_cli_output(vm, "Brief History (last %d walks):", HISTORY_N_WALKS);
1082  ii = history_last_walk_pos - 1;
1083  if (ii < 0)
1084  ii = HISTORY_N_WALKS - 1;
1085 
1086  while (ii != history_last_walk_pos)
1087  {
1088  if (0 != fib_walk_history[ii].fwh_reason[0])
1089  {
1090  u8 *s = NULL;
1091  u32 jj;
1092 
1093  s = format(s, "[@%d]: %s:%d visits:%d duration:%.2f completed:%.2f ",
1094  ii, fib_node_type_get_name(fib_walk_history[ii].fwh_parent.fnp_type),
1095  fib_walk_history[ii].fwh_parent.fnp_index,
1096  fib_walk_history[ii].fwh_n_visits,
1097  fib_walk_history[ii].fwh_duration,
1098  fib_walk_history[ii].fwh_completed);
1099  if (FIB_WALK_FLAG_SYNC & fib_walk_history[ii].fwh_flags)
1100  s = format(s, "sync, ");
1101  if (FIB_WALK_FLAG_ASYNC & fib_walk_history[ii].fwh_flags)
1102  s = format(s, "async, ");
1103 
1104  s = format(s, "reason:");
1105  jj = 0;
1106  while (0 != fib_walk_history[ii].fwh_reason[jj])
1107  {
1108  s = format (s, "%U,", format_fib_node_bw_reason,
1109  fib_walk_history[ii].fwh_reason[jj]);
1110  jj++;
1111  }
1112  vlib_cli_output(vm, "%v", s);
1113  }
1114 
1115  ii--;
1116  if (ii < 0)
1117  ii = HISTORY_N_WALKS - 1;
1118  }
1119 
1120  return (NULL);
1121 }
1122 
1123 VLIB_CLI_COMMAND (fib_walk_show_command, static) = {
1124  .path = "show fib walk",
1125  .short_help = "show fib walk",
1126  .function = fib_walk_show,
1127 };
1128 
1129 static clib_error_t *
1131  unformat_input_t * input,
1132  vlib_cli_command_t * cmd)
1133 {
1134  clib_error_t * error = NULL;
1135  f64 new_quota;
1136 
1137  if (unformat (input, "%f", &new_quota))
1138  {
1139  quota = new_quota;
1140  }
1141  else
1142  {
1143  error = clib_error_return(0 , "Pass a float value");
1144  }
1145 
1146  return (error);
1147 }
1148 
1149 VLIB_CLI_COMMAND (fib_walk_set_quota_command, static) = {
1150  .path = "set fib walk quota",
1151  .short_help = "set fib walk quota",
1152  .function = fib_walk_set_quota,
1153 };
1154 
1155 static clib_error_t *
1157  unformat_input_t * input,
1158  vlib_cli_command_t * cmd)
1159 {
1160  clib_error_t * error = NULL;
1161  u32 new;
1162 
1163  if (unformat (input, "%d", &new))
1164  {
1165  fib_walk_work_nodes_visited_incr = new;
1166  }
1167  else
1168  {
1169  error = clib_error_return(0 , "Pass an int value");
1170  }
1171 
1172  return (error);
1173 }
1174 
1175 VLIB_CLI_COMMAND (fib_walk_set_histogram_elements_size_command, static) = {
1176  .path = "set fib walk histogram elements size",
1177  .short_help = "set fib walk histogram elements size",
1179 };
1180 
1181 static clib_error_t *
1183  unformat_input_t * input,
1184  vlib_cli_command_t * cmd)
1185 {
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));
1191 
1192  return (NULL);
1193 }
1194 
1195 VLIB_CLI_COMMAND (fib_walk_clear_command, static) = {
1196  .path = "clear fib walk",
1197  .short_help = "clear fib walk",
1198  .function = fib_walk_clear,
1199 };
1200 
1201 void
1203 {
1205  fib_walk_process_node.index,
1207  0);
1208 }
1209 
1210 void
1212 {
1214  fib_walk_process_node.index,
1216  0);
1217 }
1218 
1219 static clib_error_t *
1221  unformat_input_t * input,
1222  vlib_cli_command_t * cmd)
1223 {
1224  if (unformat (input, "enable"))
1225  {
1227  }
1228  else if (unformat (input, "disable"))
1229  {
1231  }
1232  else
1233  {
1234  return clib_error_return(0, "choose enable or disable");
1235  }
1236  return (NULL);
1237 }
1238 
1239 VLIB_CLI_COMMAND (fib_walk_process_command, static) = {
1240  .path = "test fib-walk-process",
1241  .short_help = "test fib-walk-process [enable|disable]",
1242  .function = fib_walk_process_enable_disable,
1243 };
#define HISTOGRAM_VISITS_PER_WALK_N_BUCKETS
Definition: fib_walk.c:169
vlib_log_class_t vlib_log_register_class(char *class, char *subclass)
Definition: log.c:227
#define FOR_EACH_FIB_NODE_BW_REASON(_item)
Definition: fib_node.h:137
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.
Definition: fib_walk.c:65
u32 flags
Definition: vhost_user.h:115
static fib_walk_t * fib_walk_pool
The pool of all walk objects.
Definition: fib_walk.c:98
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:673
static uword * vlib_process_wait_for_event(vlib_main_t *vm)
Definition: node_funcs.h:593
fib_walk_advance_rc_t_
return code when advancing a walk
Definition: fib_walk.c:316
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:1130
fib_walk_queue_t fwqs_queues[FIB_WALK_PRIORITY_NUM]
Definition: fib_walk.c:150
An asynchronous walk.
Definition: fib_walk.c:38
void fib_node_init(fib_node_t *node, fib_node_type_t type)
Definition: fib_node.c:185
unsigned long u64
Definition: types.h:89
#define NULL
Definition: clib.h:58
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.
Definition: fib_walk.c:440
static f64 vlib_time_now(vlib_main_t *vm)
Definition: main.h:255
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:137
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:522
static heap_elt_t * last(heap_header_t *h)
Definition: heap.c:53
static fib_node_index_t fib_walk_queue_get_front(fib_walk_priority_t prio)
Definition: fib_walk.c:241
#define STRUCT_OFFSET_OF(t, f)
Definition: clib.h:65
void fib_node_deinit(fib_node_t *node)
Definition: fib_node.c:197
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:688
struct fib_walk_queue_t_ fib_walk_queue_t
A represenation of one queue of walk.
u8 * format(u8 *s, const char *fmt,...)
Definition: format.c:424
static fib_walk_t * fib_walk_get(index_t fwi)
Definition: fib_walk.c:226
#define pool_get(P, E)
Allocate an object E from a pool P (unspecified alignment).
Definition: pool.h:236
unsigned char u8
Definition: types.h:56
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:98
#define vec_reset_length(v)
Reset vector length to zero NULL-pointer tolerant.
double f64
Definition: types.h:142
u8 * format_fib_walk_priority(u8 *s, va_list *ap)
Definition: fib_walk.c:201
void fib_node_register_type(fib_node_type_t type, const fib_node_vft_t *vft)
fib_node_register_type
Definition: fib_node.c:60
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:560
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:461
static clib_error_t * fib_walk_process_enable_disable(vlib_main_t *vm, unformat_input_t *input, vlib_cli_command_t *cmd)
Definition: fib_walk.c:1220
u32 vlib_log_class_t
Definition: vlib.h:50
fib_node_index_t fnp_index
node&#39;s index
Definition: fib_node.h:193
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:516
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:745
fib_walk_flags_t fwh_flags
Definition: fib_walk.c:184
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:154
#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:92
#define MAX_HISTORY_REASONS
Definition: fib_walk.c:177
#define clib_error_return(e, args...)
Definition: error.h:99
u8 * format_fib_node_bw_reason(u8 *s, va_list *args)
Definition: fib_walk.c:973
static fib_walk_queues_t fib_walk_queues
The global queues of outstanding walks.
Definition: fib_walk.c:156
A representation of a graph walk from a parent object to its children.
Definition: fib_walk.c:48
unsigned int u32
Definition: types.h:88
fib_walk_queue_stats_t_
Statistics maintained per-walk queue.
Definition: fib_walk.c:103
#define vec_end(v)
End (last data address) of vector.
A representation of one pointer to another node.
Definition: fib_node.h:185
static u32 fib_walk_work_nodes_visited_incr
Definition: fib_walk.c:448
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:168
#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:208
#define pool_elt_at_index(p, i)
Returns pointer to element at given index.
Definition: pool.h:514
fib_node_type_t fnp_type
node type
Definition: fib_node.h:189
#define FIB_NODE_BW_REASONS
Definition: fib_node.h:127
static void vlib_process_signal_event(vlib_main_t *vm, uword node_index, uword type_opaque, uword data)
Definition: node_funcs.h:934
u32 fnbw_depth
the number of levels the walk has already traversed.
Definition: fib_node.h:221
#define FIB_WALK_QUEUE_STATS_NUM
Definition: fib_walk.c:108
long ctx[MAX_CONNS]
Definition: main.c:144
struct _unformat_input_t unformat_input_t
static u8 * format_fib_walk_queue_stats(u8 *s, va_list *ap)
Definition: fib_walk.c:210
The walk merged with the one in front.
Definition: fib_walk.c:329
static void fib_walk_destroy(index_t fwi)
Definition: fib_walk.c:251
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:80
#define pool_put(P, E)
Free an object E in pool P.
Definition: pool.h:286
#define N_ELTS_BUCKETS
Histogram on the number of nodes visted in each quota.
Definition: fib_walk.c:447
fib_walk_flags_t fw_flags
the walk&#39;s flags
Definition: fib_walk.c:60
fib_node_bw_flags_t fnbw_flags
additional flags for the walk
Definition: fib_node.h:213
A set of priority queues for outstanding walks.
Definition: fib_walk.c:148
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:291
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
Definition: fib_walk.h:34
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)
Definition: fib_walk.c:220
void fib_walk_process_enable(void)
Definition: fib_walk.c:1202
#define VLIB_REGISTER_NODE(x,...)
Definition: node.h:169
vlib_main_t * vm
Definition: buffer.c:312
#define vec_free(V)
Free vector&#39;s memory (no header).
Definition: vec.h:341
Force the walk to be synchronous.
Definition: fib_node.h:170
fib_node_get_t fnv_get
Definition: fib_node.h:279
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:894
u32 fib_node_index_t
A typedef of a node index.
Definition: fib_types.h:30
u32 fib_node_get_n_children(fib_node_type_t parent_type, fib_node_index_t parent_index)
Definition: fib_node.c:142
u32 fib_walk_queue_get_size(fib_walk_priority_t prio)
Definition: fib_walk.c:235
void fib_walk_module_init(void)
Definition: fib_walk.c:944
enum fib_walk_priority_t_ fib_walk_priority_t
Walk priorities.
static f64 quota
The time quota for a walk.
Definition: fib_walk.c:435
fib_node_ptr_t fw_parent
Pointer to the node whose dependants this walk is walking.
Definition: fib_walk.c:75
Context passed between object during a back walk.
Definition: fib_node.h:204
#define VLIB_CLI_COMMAND(x,...)
Definition: cli.h:155
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:626
An indication that the walk is currently executing.
Definition: fib_walk.c:42
f64 fw_start_time
Time the walk started.
Definition: fib_walk.c:85
A synchronous walk.
Definition: fib_walk.c:31
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:663
signed int i32
Definition: types.h:77
#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:110
fib_walk_flags_t_
The flags on a walk.
Definition: fib_walk.c:24
fib_node_ptr_t fwh_parent
Definition: fib_walk.c:183
void fib_walk_process_disable(void)
Definition: fib_walk.c:1211
static clib_error_t * fib_walk_clear(vlib_main_t *vm, unformat_input_t *input, vlib_cli_command_t *cmd)
Definition: fib_walk.c:1182
#define FIB_WALK_DBG(_walk, _fmt, _args...)
Definition: fib_walk.c:191
fib_walk_sleep_type_t_
Enurmerate the times of sleep between walks
Definition: fib_walk.c:405
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)
Definition: fib_node.c:123
static vlib_main_t * vlib_get_main(void)
Definition: global_funcs.h:23
The walk is complete.
Definition: fib_walk.c:321
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.
Definition: fib_walk.c:549
fib_node_list_t fwq_queue
The node list which acts as the queue.
Definition: fib_walk.c:142
enum fib_walk_process_event_t_ fib_walk_process_event
Events sent to the FIB walk process.
#define FIB_NODE_INDEX_INVALID
Definition: fib_types.h:31
vlib_log_class_t fib_walk_logger
Definition: fib_walk.c:19
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
u64 uword
Definition: types.h:112
static fib_walk_t * fib_walk_get_from_node(fib_node_t *node)
Definition: fib_walk.c:882
static fib_node_t * fib_walk_get_node(fib_node_index_t index)
Definition: fib_walk.c:862
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:1156
See the respective fib_*.h files for descriptions of these objects.
Definition: fib_node.h:32
#define TIME_INCREMENTS
Definition: fib_walk.c:441
#define HISTORY_N_WALKS
History of state for the last 128 walks.
Definition: fib_walk.c:176
A FIB graph nodes virtual function table.
Definition: fib_node.h:278
static u8 * format_fib_walk(u8 *s, va_list *ap)
Definition: fib_walk.c:958
static clib_error_t * fib_walk_show(vlib_main_t *vm, unformat_input_t *input, vlib_cli_command_t *cmd)
Definition: fib_walk.c:987
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.
Definition: fib_walk.c:55
u32 fib_node_list_t
A list of FIB nodes.
Definition: fib_node.h:199
int fib_node_list_elt_get_next(u32 sibling, fib_node_ptr_t *ptr)
the walk has more work
Definition: fib_walk.c:325
static u32 history_last_walk_pos
Definition: fib_walk.c:178
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.
Definition: fib_walk.c:70
static void fib_walk_last_lock_gone(fib_node_t *node)
Walk objects are not parents, nor are they locked.
Definition: fib_walk.c:876
void vlib_cli_output(vlib_main_t *vm, char *fmt,...)
Definition: cli.c:762
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:336
const char * fib_node_type_get_name(fib_node_type_t type)
Definition: fib_node.c:37
A represenation of one queue of walk.
Definition: fib_walk.c:132
uword unformat(unformat_input_t *i, const char *fmt,...)
Definition: unformat.c:972
#define FOR_EACH_FIB_WALK_QUEUE_STATS(_wqs)
Definition: fib_walk.c:115
fib_node_bw_reason_flag_t fwh_reason[MAX_HISTORY_REASONS]
Definition: fib_walk.c:185
struct fib_walk_queues_t_ fib_walk_queues_t
A set of priority queues for outstanding walks.