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