FD.io VPP  v18.07-34-g55fbdb9
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  wrc = fib_node_back_walk_one(&sibling, &fwalk->fw_ctx[ii]);
354 
355  ii++;
356  fwalk = fib_walk_get(fwi);
357  fwalk->fw_n_visits++;
358 
359  if (FIB_NODE_BACK_WALK_MERGE == wrc)
360  {
361  /*
362  * this walk has merged with the one further along the node's
363  * dependecy list.
364  */
365  return (FIB_WALK_ADVANCE_MERGE);
366  }
367 
368  /*
369  * re-evaluate the number of backwalk contexts we need to process.
370  */
371  n_ctxs = vec_len(fwalk->fw_ctx);
372  }
373  /*
374  * move foward to the next node to visit
375  */
376  more_elts = fib_node_list_advance(fwalk->fw_dep_sibling);
377  }
378 
379  if (more_elts)
380  {
381  return (FIB_WALK_ADVANCE_MORE);
382  }
383 
384  return (FIB_WALK_ADVANCE_DONE);
385 }
386 
387 /**
388  * @breif Enurmerate the times of sleep between walks
389  */
391 {
395 
396 #define FIB_WALK_N_SLEEP (FIB_WALK_LONG_SLEEP+1)
397 
398 /**
399  * @brief Durations for the sleep types
400  */
401 static f64 fib_walk_sleep_duration[] = {
402  /**
403  * Long sleep when there is no more work, i.e. the queues are empty.
404  * This is a sleep (as opposed to a wait for event) just to be sure we
405  * are not missing events by sleeping forever.
406  */
407  [FIB_WALK_LONG_SLEEP] = 2,
408 
409  /**
410  * Short sleep. There is work left in the queues. We are yielding the CPU
411  * momentarily.
412  */
413  [FIB_WALK_SHORT_SLEEP] = 1e-8,
414 };
415 
416 /**
417  * @brief The time quota for a walk. When more than this amount of time is
418  * spent, the walk process will yield.
419  */
420 static f64 quota = 1e-4;
421 
422 /**
423  * Histogram on the amount of work done (in msecs) in each walk
424  */
425 #define N_TIME_BUCKETS 128
426 #define TIME_INCREMENTS (N_TIME_BUCKETS/2)
427 static u64 fib_walk_work_time_taken[N_TIME_BUCKETS];
428 
429 /**
430  * Histogram on the number of nodes visted in each quota
431  */
432 #define N_ELTS_BUCKETS 128
433 static u32 fib_walk_work_nodes_visisted_incr = 2;
434 static u64 fib_walk_work_nodes_visited[N_ELTS_BUCKETS];
435 
436 /**
437  * Histogram of the sleep lengths
438  */
439 static u64 fib_walk_sleep_lengths[2];
440 
441 /**
442  * @brief Service the queues
443  * This is not declared static so that it can be unit tested - i know i know...
444  */
445 f64
447  const f64 quota)
448 {
449  f64 start_time, consumed_time;
450  fib_walk_sleep_type_t sleep;
451  fib_walk_priority_t prio;
452  fib_walk_advance_rc_t rc;
453  fib_node_index_t fwi;
454  fib_walk_t *fwalk;
455  u32 n_elts;
456  i32 bucket;
457 
458  consumed_time = 0;
459  start_time = vlib_time_now(vm);
460  n_elts = 0;
461 
463  {
464  while (0 != fib_walk_queue_get_size(prio))
465  {
466  fwi = fib_walk_queue_get_front(prio);
467 
468  /*
469  * set this walk as executing
470  */
471  fwalk = fib_walk_get(fwi);
473 
474  do
475  {
476  rc = fib_walk_advance(fwi);
477  n_elts++;
478  consumed_time = (vlib_time_now(vm) - start_time);
479  } while ((consumed_time < quota) &&
480  (FIB_WALK_ADVANCE_MORE == rc));
481 
482  /*
483  * if this walk has no more work then pop it from the queue
484  * and move on to the next.
485  */
486  if (FIB_WALK_ADVANCE_MORE != rc)
487  {
488  fib_walk_destroy(fwi);
489  fib_walk_queues.fwqs_queues[prio].fwq_stats[FIB_WALK_COMPLETED]++;
490  }
491  else
492  {
493  /*
494  * passed our work quota. sleep time.
495  */
496  fwalk = fib_walk_get(fwi);
498  sleep = FIB_WALK_SHORT_SLEEP;
499  goto that_will_do_for_now;
500  }
501  }
502  }
503  /*
504  * got to the end of all the work
505  */
506  sleep = FIB_WALK_LONG_SLEEP;
507 
508 that_will_do_for_now:
509 
510  /*
511  * collect the stats:
512  * - for the number of nodes visisted we store 128 increments
513  * - for the time consumed we store quota/TIME_INCREMENTS increments.
514  */
516  N_ELTS_BUCKETS-1 :
517  n_elts/fib_walk_work_nodes_visisted_incr);
518  ++fib_walk_work_nodes_visited[bucket];
519 
520  bucket = (consumed_time - quota) / (quota / TIME_INCREMENTS);
521  bucket += N_TIME_BUCKETS/2;
522  bucket = (bucket < 0 ? 0 : bucket);
523  bucket = (bucket > N_TIME_BUCKETS-1 ? N_TIME_BUCKETS-1 : bucket);
524  ++fib_walk_work_time_taken[bucket];
525 
526  ++fib_walk_sleep_lengths[sleep];
527 
528  return (fib_walk_sleep_duration[sleep]);
529 }
530 
531 /**
532  * Events sent to the FIB walk process
533  */
535 {
540 
541 /**
542  * @brief The 'fib-walk' process's main loop.
543  */
544 static uword
546  vlib_node_runtime_t * node,
547  vlib_frame_t * f)
548 {
549  uword event_type, *event_data = 0;
550  f64 sleep_time;
551  int enabled;
552 
553  enabled = 1;
554  sleep_time = fib_walk_sleep_duration[FIB_WALK_SHORT_SLEEP];
555 
556  while (1)
557  {
558  /*
559  * the feature to disable/enable this walk process is only
560  * for testing purposes
561  */
562  if (enabled)
563  {
564  vlib_process_wait_for_event_or_clock(vm, sleep_time);
565  }
566  else
567  {
569  }
570 
571  event_type = vlib_process_get_events(vm, &event_data);
572  vec_reset_length(event_data);
573 
574  switch (event_type)
575  {
577  enabled = 1;
578  break;
580  enabled = 0;
581  break;
582  default:
583  break;
584  }
585 
586  if (enabled)
587  {
588  sleep_time = fib_walk_process_queues(vm, quota);
589  }
590  }
591 
592  /*
593  * Unreached
594  */
595  ASSERT(!"WTF");
596  return 0;
597 }
598 
599 /* *INDENT-OFF* */
600 VLIB_REGISTER_NODE (fib_walk_process_node,static) = {
601  .function = fib_walk_process,
602  .type = VLIB_NODE_TYPE_PROCESS,
603  .name = "fib-walk",
604 };
605 /* *INDENT-ON* */
606 
607 /**
608  * @brief Allocate a new walk object
609  */
610 static fib_walk_t *
612  fib_node_index_t parent_index,
615 {
616  fib_walk_t *fwalk;
617 
618  pool_get(fib_walk_pool, fwalk);
619 
621 
622  fwalk->fw_flags = flags;
625  fwalk->fw_parent.fnp_index = parent_index;
626  fwalk->fw_parent.fnp_type = parent_type;
627  fwalk->fw_ctx = NULL;
629  fwalk->fw_n_visits = 0;
630 
631  /*
632  * make a copy of the backwalk context so the depth count remains
633  * the same for each sibling visitsed. This is important in the case
634  * where a parent has a loop via one child, but all the others are not.
635  * if the looped child were visited first, the depth count would exceed, the
636  * max and the walk would terminate before it reached the other siblings.
637  */
638  vec_add1(fwalk->fw_ctx, *ctx);
639 
640  return (fwalk);
641 }
642 
643 /**
644  * @brief Enqueue a walk onto the appropriate priority queue. Then signal
645  * the background process there is work to do.
646  */
647 static index_t
649  fib_walk_t *fwalk)
650 {
651  index_t sibling;
652 
653  sibling = fib_node_list_push_front(fib_walk_queues.fwqs_queues[prio].fwq_queue,
654  0,
656  fib_walk_get_index(fwalk));
657  fib_walk_queues.fwqs_queues[prio].fwq_stats[FIB_WALK_SCHEDULED]++;
658 
659  /*
660  * poke the fib-walk process to perform the async walk.
661  * we are not passing it specific data, hence the last two args,
662  * the process will drain the queues
663  */
665  fib_walk_process_node.index,
667  0);
668 
669  return (sibling);
670 }
671 
672 void
674  fib_node_index_t parent_index,
675  fib_walk_priority_t prio,
677 {
678  fib_walk_t *fwalk;
679 
680  if (FIB_NODE_GRAPH_MAX_DEPTH < ++ctx->fnbw_depth)
681  {
682  /*
683  * The walk has reached the maximum depth. there is a loop in the graph.
684  * bail.
685  */
686  return;
687  }
688  if (0 == fib_node_get_n_children(parent_type,
689  parent_index))
690  {
691  /*
692  * no children to walk - quit now
693  */
694  return;
695  }
697  {
698  /*
699  * the originator of the walk wanted it to be synchronous, but the
700  * parent object chose async - denied.
701  */
702  return (fib_walk_sync(parent_type, parent_index, ctx));
703  }
704 
705 
706  fwalk = fib_walk_alloc(parent_type,
707  parent_index,
709  ctx);
710 
711  fwalk->fw_dep_sibling = fib_node_child_add(parent_type,
712  parent_index,
714  fib_walk_get_index(fwalk));
715 
716  fwalk->fw_prio_sibling = fib_walk_prio_queue_enquue(prio, fwalk);
717 }
718 
719 /**
720  * @brief Back walk all the children of a FIB node.
721  *
722  * note this is a synchronous depth first walk. Children visited may propagate
723  * the walk to thier children. Other children node types may not propagate,
724  * synchronously but instead queue the walk for later async completion.
725  */
726 void
728  fib_node_index_t parent_index,
730 {
731  fib_walk_advance_rc_t rc;
732  fib_node_index_t fwi;
733  fib_walk_t *fwalk;
734 
735  if (FIB_NODE_GRAPH_MAX_DEPTH < ++ctx->fnbw_depth)
736  {
737  /*
738  * The walk has reached the maximum depth. there is a loop in the graph.
739  * bail.
740  */
741  return;
742  }
743  if (0 == fib_node_get_n_children(parent_type,
744  parent_index))
745  {
746  /*
747  * no children to walk - quit now
748  */
749  return;
750  }
751 
752  fwalk = fib_walk_alloc(parent_type,
753  parent_index,
755  ctx);
756 
757  fwalk->fw_dep_sibling = fib_node_child_add(parent_type,
758  parent_index,
760  fib_walk_get_index(fwalk));
761  fwi = fib_walk_get_index(fwalk);
762 
763  while (1)
764  {
765  /*
766  * set this walk as executing
767  */
769 
770  do
771  {
772  rc = fib_walk_advance(fwi);
773  } while (FIB_WALK_ADVANCE_MORE == rc);
774 
775 
776  /*
777  * this walk function is re-entrant - walks can spawn walks.
778  * fib_walk_t objects come from a pool, so they can realloc. we need
779  * to re-fetch from said pool at the appropriate times.
780  */
781  fwalk = fib_walk_get(fwi);
782 
783  if (FIB_WALK_ADVANCE_MERGE == rc)
784  {
785  /*
786  * this sync walk merged with an walk in front.
787  * by reqeusting a sync walk the client wanted all children walked,
788  * so we ditch the walk object in hand and continue with the one
789  * we merged into
790  */
791  fib_node_ptr_t merged_walk;
792 
793  fib_node_list_elt_get_next(fwalk->fw_dep_sibling, &merged_walk);
794 
795  ASSERT(FIB_NODE_INDEX_INVALID != merged_walk.fnp_index);
796  ASSERT(FIB_NODE_TYPE_WALK == merged_walk.fnp_type);
797 
798  fib_walk_destroy(fwi);
799 
800  fwi = merged_walk.fnp_index;
801  fwalk = fib_walk_get(fwi);
802 
803  if (FIB_WALK_FLAG_EXECUTING & fwalk->fw_flags)
804  {
805  /*
806  * we are executing a sync walk, and we have met with another
807  * walk that is also executing. since only one walk executs at once
808  * (there is no multi-threading) this implies we have met ourselves
809  * and hence the is a loop in the graph.
810  * This function is re-entrant, so the walk object we met is being
811  * acted on in a stack frame below this one. We must therefore not
812  * continue with it now, but let the stack unwind and along the
813  * appropriate frame to read the depth count and bail.
814  */
815  fwalk = NULL;
816  break;
817  }
818  }
819  else
820  {
821  /*
822  * the walk reached the end of the depdency list.
823  */
824  break;
825  }
826  }
827 
828  if (NULL != fwalk)
829  {
830  fib_walk_destroy(fwi);
831  }
832 }
833 
834 static fib_node_t *
836 {
837  fib_walk_t *fwalk;
838 
839  fwalk = fib_walk_get(index);
840 
841  return (&(fwalk->fw_node));
842 }
843 
844 /**
845  * Walk objects are not parents, nor are they locked.
846  * are no-ops
847  */
848 static void
850 {
851  ASSERT(0);
852 }
853 
854 static fib_walk_t*
856 {
857  return ((fib_walk_t*)(((char*)node) -
859 }
860 
861 /**
862  * @brief Another back walk has reach this walk.
863  * Megre them so there is only one left. It is this node being
864  * visited that will remain, so copy or merge the context onto it.
865  */
869 {
871  fib_walk_t *fwalk;
872 
873  fwalk = fib_walk_get_from_node(node);
874 
875  /*
876  * check whether the walk context can be merged with the most recent.
877  * the most recent was the one last added and is thus at the back of the vector.
878  * we can merge walks if the reason for the walk is the same.
879  */
880  last = vec_end(fwalk->fw_ctx) - 1;
881 
882  if (last->fnbw_reason == ctx->fnbw_reason)
883  {
884  /*
885  * copy the largest of the depth values. in the presence of a loop,
886  * the same walk will merge with itself. if we take the smaller depth
887  * then it will never end.
888  */
889  last->fnbw_depth = ((last->fnbw_depth >= ctx->fnbw_depth) ?
890  last->fnbw_depth :
891  ctx->fnbw_depth);
892  }
893  else
894  {
895  /*
896  * walks could not be merged, this means that the walk infront needs to
897  * perform different action to this one that has caught up. the one in
898  * front was scheduled first so append the new walk context to the back
899  * of the list.
900  */
901  vec_add1(fwalk->fw_ctx, *ctx);
902  }
903 
904  return (FIB_NODE_BACK_WALK_MERGE);
905 }
906 
907 /**
908  * The FIB walk's graph node virtual function table
909  */
910 static const fib_node_vft_t fib_walk_vft = {
912  .fnv_last_lock = fib_walk_last_lock_gone,
913  .fnv_back_walk = fib_walk_back_walk_notify,
914 };
915 
916 void
918 {
919  fib_walk_priority_t prio;
920 
922  {
923  fib_walk_queues.fwqs_queues[prio].fwq_queue = fib_node_list_create();
924  }
925 
927 }
928 
929 static u8*
930 format_fib_walk (u8* s, va_list *ap)
931 {
932  fib_node_index_t fwi = va_arg(*ap, fib_node_index_t);
933  fib_walk_t *fwalk;
934 
935  fwalk = fib_walk_get(fwi);
936 
937  return (format(s, " parent:{%s:%d} visits:%d flags:%d",
939  fwalk->fw_parent.fnp_index,
940  fwalk->fw_n_visits,
941  fwalk->fw_flags));
942 }
943 
944 static clib_error_t *
946  unformat_input_t * input,
947  vlib_cli_command_t * cmd)
948 {
949  fib_walk_queue_stats_t wqs;
950  fib_walk_priority_t prio;
951  fib_node_ptr_t sibling;
952  fib_node_index_t fwi;
953  fib_walk_t *fwalk;
954  int more_elts, ii;
955  u8 *s = NULL;
956 
957 #define USEC 1000000
958  vlib_cli_output(vm, "FIB Walk Quota = %.2fusec:", quota * USEC);
959  vlib_cli_output(vm, "FIB Walk queues:");
960 
962  {
963  vlib_cli_output(vm, " %U priority queue:",
965  vlib_cli_output(vm, " Stats: ");
966 
968  {
969  vlib_cli_output(vm, " %U:%d",
971  fib_walk_queues.fwqs_queues[prio].fwq_stats[wqs]);
972  }
973  vlib_cli_output(vm, " Occupancy:%d",
975  fib_walk_queues.fwqs_queues[prio].fwq_queue));
976 
977  more_elts = fib_node_list_get_front(
978  fib_walk_queues.fwqs_queues[prio].fwq_queue,
979  &sibling);
980 
981  while (more_elts)
982  {
984  ASSERT(FIB_NODE_TYPE_WALK == sibling.fnp_type);
985 
986  fwi = sibling.fnp_index;
987  fwalk = fib_walk_get(fwi);
988 
989  vlib_cli_output(vm, " %U", format_fib_walk, fwi);
990 
991  more_elts = fib_node_list_elt_get_next(fwalk->fw_prio_sibling,
992  &sibling);
993  }
994  }
995 
996  vlib_cli_output(vm, "Histogram Statistics:");
997  vlib_cli_output(vm, " Number of Elements visit per-quota:");
998  for (ii = 0; ii < N_ELTS_BUCKETS; ii++)
999  {
1000  if (0 != fib_walk_work_nodes_visited[ii])
1001  s = format(s, "%d:%d ",
1002  (ii * fib_walk_work_nodes_visisted_incr),
1003  fib_walk_work_nodes_visited[ii]);
1004  }
1005  vlib_cli_output(vm, " %v", s);
1006  vec_free(s);
1007 
1008  vlib_cli_output(vm, " Time consumed per-quota (Quota=%f usec):", quota*USEC);
1009  s = format(s, "0:%d ", fib_walk_work_time_taken[0]);
1010  for (ii = 1; ii < N_TIME_BUCKETS; ii++)
1011  {
1012  if (0 != fib_walk_work_time_taken[ii])
1013  s = format(s, "%d:%d ", (u32)((((ii - N_TIME_BUCKETS/2) *
1014  (quota / TIME_INCREMENTS)) + quota) *
1015  USEC),
1016  fib_walk_work_time_taken[ii]);
1017  }
1018  vlib_cli_output(vm, " %v", s);
1019  vec_free(s);
1020 
1021  vlib_cli_output(vm, " Sleep Types:");
1022  vlib_cli_output(vm, " Short Long:");
1023  vlib_cli_output(vm, " %d %d:",
1024  fib_walk_sleep_lengths[FIB_WALK_SHORT_SLEEP],
1025  fib_walk_sleep_lengths[FIB_WALK_LONG_SLEEP]);
1026 
1027  vlib_cli_output(vm, " Number of Elements visited per-walk:");
1028  for (ii = 0; ii < HISTOGRAM_VISITS_PER_WALK_N_BUCKETS; ii++)
1029  {
1030  if (0 != fib_walk_hist_vists_per_walk[ii])
1031  s = format(s, "%d:%d ",
1033  fib_walk_hist_vists_per_walk[ii]);
1034  }
1035  vlib_cli_output(vm, " %v", s);
1036  vec_free(s);
1037 
1038 
1039  vlib_cli_output(vm, "Brief History (last %d walks):", HISTORY_N_WALKS);
1040  ii = history_last_walk_pos - 1;
1041  if (ii < 0)
1042  ii = HISTORY_N_WALKS - 1;
1043 
1044  while (ii != history_last_walk_pos)
1045  {
1046  if (0 != fib_walk_history[ii].fwh_reason[0])
1047  {
1049  u8 *s = NULL;
1050  u32 jj;
1051 
1052  s = format(s, "[@%d]: %s:%d visits:%d duration:%.2f completed:%.2f ",
1053  ii, fib_node_type_get_name(fib_walk_history[ii].fwh_parent.fnp_type),
1054  fib_walk_history[ii].fwh_parent.fnp_index,
1055  fib_walk_history[ii].fwh_n_visits,
1056  fib_walk_history[ii].fwh_duration,
1057  fib_walk_history[ii].fwh_completed);
1058  if (FIB_WALK_FLAG_SYNC & fib_walk_history[ii].fwh_flags)
1059  s = format(s, "sync, ");
1060  if (FIB_WALK_FLAG_ASYNC & fib_walk_history[ii].fwh_flags)
1061  s = format(s, "async, ");
1062 
1063  s = format(s, "reason:");
1064  jj = 0;
1065  while (0 != fib_walk_history[ii].fwh_reason[jj])
1066  {
1067  FOR_EACH_FIB_NODE_BW_REASON(reason) {
1068  if ((1<<reason) & fib_walk_history[ii].fwh_reason[jj]) {
1069  s = format (s, "%s,", fib_node_bw_reason_names[reason]);
1070  }
1071  }
1072  jj++;
1073  }
1074  vlib_cli_output(vm, "%v", s);
1075  }
1076 
1077  ii--;
1078  if (ii < 0)
1079  ii = HISTORY_N_WALKS - 1;
1080  }
1081 
1082  return (NULL);
1083 }
1084 
1085 VLIB_CLI_COMMAND (fib_walk_show_command, static) = {
1086  .path = "show fib walk",
1087  .short_help = "show fib walk",
1088  .function = fib_walk_show,
1089 };
1090 
1091 static clib_error_t *
1093  unformat_input_t * input,
1094  vlib_cli_command_t * cmd)
1095 {
1096  clib_error_t * error = NULL;
1097  f64 new_quota;
1098 
1099  if (unformat (input, "%f", &new_quota))
1100  {
1101  quota = new_quota;
1102  }
1103  else
1104  {
1105  error = clib_error_return(0 , "Pass a float value");
1106  }
1107 
1108  return (error);
1109 }
1110 
1111 VLIB_CLI_COMMAND (fib_walk_set_quota_command, static) = {
1112  .path = "set fib walk quota",
1113  .short_help = "set fib walk quota",
1114  .function = fib_walk_set_quota,
1115 };
1116 
1117 static clib_error_t *
1119  unformat_input_t * input,
1120  vlib_cli_command_t * cmd)
1121 {
1122  clib_error_t * error = NULL;
1123  u32 new;
1124 
1125  if (unformat (input, "%d", &new))
1126  {
1127  fib_walk_work_nodes_visisted_incr = new;
1128  }
1129  else
1130  {
1131  error = clib_error_return(0 , "Pass an int value");
1132  }
1133 
1134  return (error);
1135 }
1136 
1137 VLIB_CLI_COMMAND (fib_walk_set_histogram_elements_size_command, static) = {
1138  .path = "set fib walk histogram elements size",
1139  .short_help = "set fib walk histogram elements size",
1141 };
1142 
1143 static clib_error_t *
1145  unformat_input_t * input,
1146  vlib_cli_command_t * cmd)
1147 {
1148  memset(fib_walk_hist_vists_per_walk, 0, sizeof(fib_walk_hist_vists_per_walk));
1149  memset(fib_walk_history, 0, sizeof(fib_walk_history));
1150  memset(fib_walk_work_time_taken, 0, sizeof(fib_walk_work_time_taken));
1151  memset(fib_walk_work_nodes_visited, 0, sizeof(fib_walk_work_nodes_visited));
1152  memset(fib_walk_sleep_lengths, 0, sizeof(fib_walk_sleep_lengths));
1153 
1154  return (NULL);
1155 }
1156 
1157 VLIB_CLI_COMMAND (fib_walk_clear_command, static) = {
1158  .path = "clear fib walk",
1159  .short_help = "clear fib walk",
1160  .function = fib_walk_clear,
1161 };
1162 
1163 void
1165 {
1167  fib_walk_process_node.index,
1169  0);
1170 }
1171 
1172 void
1174 {
1176  fib_walk_process_node.index,
1178  0);
1179 }
1180 
1181 static clib_error_t *
1183  unformat_input_t * input,
1184  vlib_cli_command_t * cmd)
1185 {
1186  if (unformat (input, "enable"))
1187  {
1189  }
1190  else if (unformat (input, "disable"))
1191  {
1193  }
1194  else
1195  {
1196  return clib_error_return(0, "choose enable or disable");
1197  }
1198  return (NULL);
1199 }
1200 
1201 VLIB_CLI_COMMAND (fib_walk_process_command, static) = {
1202  .path = "test fib-walk-process",
1203  .short_help = "test fib-walk-process [enable|disable]",
1204  .function = fib_walk_process_enable_disable,
1205 };
#define HISTOGRAM_VISITS_PER_WALK_N_BUCKETS
Definition: fib_walk.c:167
#define FOR_EACH_FIB_NODE_BW_REASON(_item)
Definition: fib_node.h:135
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:1092
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:55
#define N_TIME_BUCKETS
Histogram on the amount of work done (in msecs) in each walk.
Definition: fib_walk.c:425
static f64 vlib_time_now(vlib_main_t *vm)
Definition: main.h:225
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:62
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:673
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:545
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:446
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:1182
fib_node_index_t fnp_index
node&#39;s index
Definition: fib_node.h:189
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:727
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:930
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:181
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:204
#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:185
#define FIB_NODE_BW_REASONS
Definition: fib_node.h:125
static void vlib_process_signal_event(vlib_main_t *vm, uword node_index, uword type_opaque, uword data)
Definition: node_funcs.h:952
u32 fnbw_depth
the number of levels the walk has already traversed.
Definition: fib_node.h:217
#define FIB_WALK_QUEUE_STATS_NUM
Definition: fib_walk.c:106
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:432
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:209
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:287
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:110
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:1164
#define VLIB_REGISTER_NODE(x,...)
Definition: node.h:153
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:166
fib_node_get_t fnv_get
Definition: fib_node.h:275
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:867
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:917
enum fib_walk_priority_t_ fib_walk_priority_t
Walk priorities.
static f64 quota
The time quota for a walk.
Definition: fib_walk.c:420
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:200
#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:611
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:648
signed int i32
Definition: types.h:81
#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:1173
long ctx[MAX_CONNS]
Definition: main.c:126
static u32 fib_walk_work_nodes_visisted_incr
Definition: fib_walk.c:433
static clib_error_t * fib_walk_clear(vlib_main_t *vm, unformat_input_t *input, vlib_cli_command_t *cmd)
Definition: fib_walk.c:1144
fib_walk_sleep_type_t_
Enurmerate the times of sleep between walks
Definition: fib_walk.c:390
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:534
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:855
static fib_node_t * fib_walk_get_node(fib_node_index_t index)
Definition: fib_walk.c:835
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:1118
See the respective fib_*.h files for descriptions of these objects.
Definition: fib_node.h:32
#define TIME_INCREMENTS
Definition: fib_walk.c:426
#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:274
static clib_error_t * fib_walk_show(vlib_main_t *vm, unformat_input_t *input, vlib_cli_command_t *cmd)
Definition: fib_walk.c:945
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:195
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:849
void vlib_cli_output(vlib_main_t *vm, char *fmt,...)
Definition: cli.c:681
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.