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