vnet/vnet/fib/fib_walk.c

   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      */
  40     FIB_WALK_FLAG_EXECUTING = (1 << 2),
  41 } fib_walk_flags_t;
  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      */
  53     fib_node_t fw_node;
  54
  55     /**
  56      * the walk's flags
  57      */
  58     fib_walk_flags_t fw_flags;
  59
  60     /**
  61      * Sibling index in the dependency list
  62      */
  63     u32 fw_dep_sibling;
  64
  65     /**
  66      * Sibling index in the list of all walks
  67      */
  68     u32 fw_prio_sibling;
  69
  70     /**
  71      * Pointer to the node whose dependants this walk is walking
  72      */
  73     fib_node_ptr_t fw_parent;
  74
  75     /**
  76      * Number of nodes visited by this walk. saved for debugging purposes.
  77      */
  78     u32 fw_n_visits;
  79
  80     /**
  81      * The reasons this walk is occuring.
  82      * This is a vector ordered in time. The reasons and the front were started
  83      * first, and so should be acted first when a node is visisted.
  84      */
  85     fib_node_back_walk_ctx_t *fw_ctx;
  86 } fib_walk_t;
  87
  88 /**
  89  * @brief The pool of all walk objects
  90  */
  91 static fib_walk_t *fib_walk_pool;
  92
  93 /**
  94  * @brief There's only one event type sent to the walk process
  95  */
  96 #define FIB_WALK_EVENT 0
  97
  98 /**
  99  * Statistics maintained per-walk queue
 100  */
 101 typedef enum fib_walk_queue_stats_t_
 102 {
 103     FIB_WALK_SCHEDULED,
 104     FIB_WALK_COMPLETED,
 105 } fib_walk_queue_stats_t;
 106 #define FIB_WALK_QUEUE_STATS_NUM (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 /**
 124  * A represenation of one queue of walk
 125  */
 126 typedef struct fib_walk_queue_t_
 127 {
 128     /**
 129      * Qeuee stats
 130      */
 131     u64 fwq_stats[FIB_WALK_QUEUE_STATS_NUM];
 132
 133     /**
 134      * The node list which acts as the queue
 135      */
 136     fib_node_list_t fwq_queue;
 137 } fib_walk_queue_t;
 138
 139 /**
 140  * A set of priority queues for outstanding walks
 141  */
 142 typedef struct fib_walk_queues_t_
 143 {
 144     fib_walk_queue_t fwqs_queues[FIB_WALK_PRIORITY_NUM];
 145 } fib_walk_queues_t;
 146
 147 /**
 148  * The global queues of outstanding walks
 149  */
 150 static fib_walk_queues_t fib_walk_queues;
 151
 152 /**
 153  * The names of the walk priorities
 154  */
 155 static const char * const fib_walk_priority_names[] = FIB_WALK_PRIORITIES;
 156
 157 u8*
 158 format_fib_walk_priority (u8 *s, va_list ap)
 159 {
 160     fib_walk_priority_t prio = va_arg(ap, fib_walk_priority_t);
 161
 162     ASSERT(prio < FIB_WALK_PRIORITY_NUM);
 163
 164     return (format(s, "%s", fib_walk_priority_names[prio]));
 165 }
 166 static u8*
 167 format_fib_walk_queue_stats (u8 *s, va_list ap)
 168 {
 169     fib_walk_queue_stats_t wqs = va_arg(ap, fib_walk_queue_stats_t);
 170
 171     ASSERT(wqs < FIB_WALK_QUEUE_STATS_NUM);
 172
 173     return (format(s, "%s", fib_walk_queue_stats_names[wqs]));
 174 }
 175
 176 static index_t
 177 fib_walk_get_index (fib_walk_t *fwalk)
 178 {
 179     return (fwalk - fib_walk_pool);
 180 }
 181
 182 static fib_walk_t *
 183 fib_walk_get (index_t fwi)
 184 {
 185     return (pool_elt_at_index(fib_walk_pool, fwi));
 186 }
 187
 188 /*
 189  * not static so it can be used in the unit tests
 190  */
 191 u32
 192 fib_walk_queue_get_size (fib_walk_priority_t prio)
 193 {
 194     return (fib_node_list_get_size(fib_walk_queues.fwqs_queues[prio].fwq_queue));
 195 }
 196
 197 static fib_node_index_t
 198 fib_walk_queue_get_front (fib_walk_priority_t prio)
 199 {
 200     fib_node_ptr_t wp;
 201
 202     fib_node_list_get_front(fib_walk_queues.fwqs_queues[prio].fwq_queue, &wp);
 203
 204     return (wp.fnp_index);
 205 }
 206
 207 static void
 208 fib_walk_destroy (fib_walk_t *fwalk)
 209 {
 210     if (FIB_NODE_INDEX_INVALID != fwalk->fw_prio_sibling)
 211     {
 212         fib_node_list_elt_remove(fwalk->fw_prio_sibling);
 213     }
 214     fib_node_child_remove(fwalk->fw_parent.fnp_type,
 215                           fwalk->fw_parent.fnp_index,
 216                           fwalk->fw_dep_sibling);
 217
 218     fib_node_deinit(&fwalk->fw_node);
 219     pool_put(fib_walk_pool, fwalk);
 220 }
 221
 222 /**
 223  * return code when advancing a walk
 224  */
 225 typedef enum fib_walk_advance_rc_t_
 226 {
 227     /**
 228      * The walk is complete
 229      */
 230     FIB_WALK_ADVANCE_DONE,
 231     /**
 232      * the walk has more work
 233      */
 234     FIB_WALK_ADVANCE_MORE,
 235     /**
 236      * The walk merged with the one in front
 237      */
 238     FIB_WALK_ADVANCE_MERGE,
 239 } fib_walk_advance_rc_t;
 240
 241 /**
 242  * @brief Advance the walk one element in its work list
 243  */
 244 static fib_walk_advance_rc_t
 245 fib_walk_advance (fib_node_index_t fwi)
 246 {
 247     fib_node_back_walk_ctx_t *ctx;
 248     fib_node_back_walk_rc_t wrc;
 249     fib_node_ptr_t sibling;
 250     fib_walk_t *fwalk;
 251     int more_elts;
 252
 253     /*
 254      * this walk function is re-entrant - walks acan spawn walks.
 255      * fib_walk_t objects come from a pool, so they can realloc. we need
 256      * to retch from said pool at the appropriate times.
 257      */
 258     fwalk = fib_walk_get(fwi);
 259
 260     more_elts = fib_node_list_elt_get_next(fwalk->fw_dep_sibling, &sibling);
 261
 262     if (more_elts)
 263     {
 264         vec_foreach(ctx, fwalk->fw_ctx)
 265         {
 266             wrc = fib_node_back_walk_one(&sibling, ctx);
 267
 268             fwalk = fib_walk_get(fwi);
 269             fwalk->fw_n_visits++;
 270
 271             if (FIB_NODE_BACK_WALK_MERGE == wrc)
 272             {
 273                 /*
 274                  * this walk has merged with the one further along the node's
 275                  * dependecy list.
 276                  */
 277                 return (FIB_WALK_ADVANCE_MERGE);
 278             }
 279         }
 280         /*
 281          * move foward to the next node to visit
 282          */
 283         more_elts = fib_node_list_advance(fwalk->fw_dep_sibling);
 284     }
 285
 286     if (more_elts)
 287     {
 288         return (FIB_WALK_ADVANCE_MORE);
 289     }
 290
 291     return (FIB_WALK_ADVANCE_DONE);
 292 }
 293
 294 /**
 295  * First guesses as to good values
 296  */
 297 #define SHORT_SLEEP 1e-8
 298 #define LONG_SLEEP  1e-3
 299 #define QUOTA       1e-4
 300
 301 /**
 302  * @brief Service the queues
 303  * This is not declared static so that it can be unit tested - i know i know...
 304  */
 305 f64
 306 fib_walk_process_queues (vlib_main_t * vm,
 307                          const f64 quota)
 308 {
 309     fib_walk_priority_t prio;
 310     fib_walk_advance_rc_t rc;
 311     fib_node_index_t fwi;
 312     fib_walk_t *fwalk;
 313
 314     f64 sleep_time, start_time; // , vector_rate;
 315
 316     start_time = vlib_time_now(vm);
 317
 318     FOR_EACH_FIB_WALK_PRIORITY(prio)
 319     {
 320         while (0 != fib_walk_queue_get_size(prio))
 321         {
 322             fwi = fib_walk_queue_get_front(prio);
 323
 324             /*
 325              * set this walk as executing
 326              */
 327             fwalk = fib_walk_get(fwi);
 328             fwalk->fw_flags |= FIB_WALK_FLAG_EXECUTING;
 329
 330             do
 331             {
 332                 rc = fib_walk_advance(fwi);
 333             } while (((vlib_time_now(vm) - start_time) < quota) &&
 334                      (FIB_WALK_ADVANCE_MORE == rc));
 335
 336             /*
 337              * if this walk has no more work then pop it from the queue
 338              * and move on to the next.
 339              */
 340             if (FIB_WALK_ADVANCE_MORE != rc)
 341             {
 342                 fwalk = fib_walk_get(fwi);
 343                 fib_walk_destroy(fwalk);
 344                 fib_walk_queues.fwqs_queues[prio].fwq_stats[FIB_WALK_COMPLETED]++;
 345             }
 346             else
 347             {
 348                 /*
 349                  * passed our work quota. sleep time.
 350                  */
 351                 fwalk = fib_walk_get(fwi);
 352                 fwalk->fw_flags &= ~FIB_WALK_FLAG_EXECUTING;
 353                 sleep_time = SHORT_SLEEP;
 354                 goto that_will_do_for_now;
 355             }
 356         }
 357     }
 358     /*
 359      * got to the end of all the work
 360      */
 361     sleep_time = LONG_SLEEP;
 362
 363 that_will_do_for_now:
 364     return (sleep_time);
 365 }
 366
 367 /**
 368  * @brief The 'fib-walk' process's main loop.
 369  */
 370 static uword
 371 fib_walk_process (vlib_main_t * vm,
 372                   vlib_node_runtime_t * node,
 373                   vlib_frame_t * f)
 374 {
 375     f64 sleep_time;
 376
 377     sleep_time = SHORT_SLEEP;
 378
 379     while (1)
 380     {
 381         vlib_process_wait_for_event_or_clock(vm, sleep_time);
 382
 383         /*
 384          * there may be lots of event queued between the processes,
 385          * but the walks we want to schedule are in the priority queues,
 386          * so we ignore the process events.
 387          */
 388         vlib_process_get_events(vm, NULL);
 389
 390         sleep_time = fib_walk_process_queues(vm, QUOTA);
 391     }
 392
 393     /*
 394      * Unreached
 395      */
 396     ASSERT(!"WTF");
 397     return 0;
 398 }
 399
 400 /* *INDENT-OFF* */
 401 VLIB_REGISTER_NODE (fib_walk_process_node,static) = {
 402     .function = fib_walk_process,
 403     .type = VLIB_NODE_TYPE_PROCESS,
 404     .name = "fib-walk",
 405 };
 406 /* *INDENT-ON* */
 407
 408 /**
 409  * @brief Allocate a new walk object
 410  */
 411 static fib_walk_t *
 412 fib_walk_alloc (fib_node_type_t parent_type,
 413                 fib_node_index_t parent_index,
 414                 fib_walk_flags_t flags,
 415                 fib_node_back_walk_ctx_t *ctx)
 416 {
 417     fib_walk_t *fwalk;
 418
 419     pool_get(fib_walk_pool, fwalk);
 420
 421     fib_node_init(&fwalk->fw_node, FIB_NODE_TYPE_WALK);
 422
 423     fwalk->fw_flags = flags;
 424     fwalk->fw_dep_sibling  = FIB_NODE_INDEX_INVALID;
 425     fwalk->fw_prio_sibling = FIB_NODE_INDEX_INVALID;
 426     fwalk->fw_parent.fnp_index = parent_index;
 427     fwalk->fw_parent.fnp_type = parent_type;
 428     fwalk->fw_ctx = NULL;
 429
 430     /*
 431      * make a copy of the backwalk context so the depth count remains
 432      * the same for each sibling visitsed. This is important in the case
 433      * where a parents has a loop via one child, but all the others are not.
 434      * if the looped child were visited first, the depth count would exceed, the
 435      * max and the walk would terminate before it reached the other siblings.
 436      */
 437     vec_add1(fwalk->fw_ctx, *ctx);
 438
 439     return (fwalk);
 440 }
 441
 442 /**
 443  * @brief Enqueue a walk onto the appropriate priority queue. Then signal
 444  * the background process there is work to do.
 445  */
 446 static index_t
 447 fib_walk_prio_queue_enquue (fib_walk_priority_t prio,
 448                             fib_walk_t *fwalk)
 449 {
 450     index_t sibling;
 451
 452     sibling = fib_node_list_push_front(fib_walk_queues.fwqs_queues[prio].fwq_queue,
 453                                        0,
 454                                        FIB_NODE_TYPE_WALK,
 455                                        fib_walk_get_index(fwalk));
 456     fib_walk_queues.fwqs_queues[prio].fwq_stats[FIB_WALK_SCHEDULED]++;
 457
 458     /*
 459      * poke the fib-walk process to perform the async walk.
 460      * we are not passing it specific data, hence the last two args,
 461      * the process will drain the queues
 462      */
 463     vlib_process_signal_event(vlib_get_main(),
 464                               fib_walk_process_node.index,
 465                               FIB_WALK_EVENT,
 466                               FIB_WALK_EVENT);
 467
 468     return (sibling);
 469 }
 470
 471 void
 472 fib_walk_async (fib_node_type_t parent_type,
 473                 fib_node_index_t parent_index,
 474                 fib_walk_priority_t prio,
 475                 fib_node_back_walk_ctx_t *ctx)
 476 {
 477     fib_walk_t *fwalk;
 478
 479     if (FIB_NODE_GRAPH_MAX_DEPTH < ++ctx->fnbw_depth)
 480     {
 481         /*
 482          * The walk has reached the maximum depth. there is a loop in the graph.
 483          * bail.
 484          */
 485         return;
 486     }
 487
 488     fwalk = fib_walk_alloc(parent_type,
 489                            parent_index,
 490                            FIB_WALK_FLAG_ASYNC,
 491                            ctx);
 492
 493     fwalk->fw_dep_sibling = fib_node_child_add(parent_type,
 494                                                parent_index,
 495                                                FIB_NODE_TYPE_WALK,
 496                                                fib_walk_get_index(fwalk));
 497
 498     fwalk->fw_prio_sibling = fib_walk_prio_queue_enquue(prio, fwalk);
 499 }
 500
 501 /**
 502  * @brief Back walk all the children of a FIB node.
 503  *
 504  * note this is a synchronous depth first walk. Children visited may propagate
 505  * the walk to thier children. Other children node types may not propagate,
 506  * synchronously but instead queue the walk for later async completion.
 507  */
 508 void
 509 fib_walk_sync (fib_node_type_t parent_type,
 510                fib_node_index_t parent_index,
 511                fib_node_back_walk_ctx_t *ctx)
 512 {
 513     fib_walk_advance_rc_t rc;
 514     fib_node_index_t fwi;
 515     fib_walk_t *fwalk;
 516
 517     if (FIB_NODE_GRAPH_MAX_DEPTH < ++ctx->fnbw_depth)
 518     {
 519         /*
 520          * The walk has reached the maximum depth. there is a loop in the graph.
 521          * bail.
 522          */
 523         return;
 524     }
 525
 526     fwalk = fib_walk_alloc(parent_type,
 527                            parent_index,
 528                            FIB_WALK_FLAG_SYNC,
 529                            ctx);
 530
 531     fwalk->fw_dep_sibling = fib_node_child_add(parent_type,
 532                                                parent_index,
 533                                                FIB_NODE_TYPE_WALK,
 534                                                fib_walk_get_index(fwalk));
 535     fwi = fib_walk_get_index(fwalk);
 536
 537     while (1)
 538     {
 539         /*
 540          * set this walk as executing
 541          */
 542         fwalk->fw_flags |= FIB_WALK_FLAG_EXECUTING;
 543
 544         do
 545         {
 546             rc = fib_walk_advance(fwi);
 547         } while (FIB_WALK_ADVANCE_MORE == rc);
 548
 549
 550         /*
 551          * this walk function is re-entrant - walks can spawn walks.
 552          * fib_walk_t objects come from a pool, so they can realloc. we need
 553          * to re-fetch from said pool at the appropriate times.
 554          */
 555         fwalk = fib_walk_get(fwi);
 556
 557         if (FIB_WALK_ADVANCE_MERGE == rc)
 558         {
 559             /*
 560              * this sync walk merged with an walk in front.
 561              * by reqeusting a sync walk the client wanted all children walked,
 562              * so we ditch the walk object in hand and continue with the one
 563              * we merged into
 564              */
 565             fib_node_ptr_t merged_walk;
 566
 567             fib_node_list_elt_get_next(fwalk->fw_dep_sibling, &merged_walk);
 568
 569             ASSERT(FIB_NODE_INDEX_INVALID != merged_walk.fnp_index);
 570             ASSERT(FIB_NODE_TYPE_WALK == merged_walk.fnp_type);
 571
 572             fib_walk_destroy(fwalk);
 573
 574             fwi = merged_walk.fnp_index;
 575             fwalk = fib_walk_get(fwi);
 576
 577             if (FIB_WALK_FLAG_EXECUTING & fwalk->fw_flags)
 578             {
 579                 /*
 580                  * we are executing a sync walk, and we have met with another
 581                  * walk that is also executing. since only one walk executs at once
 582                  * (there is no multi-threading) this implies we have met ourselves
 583                  * and hence the is a loop in the graph.
 584                  * This function is re-entrant, so the walk object we met is being
 585                  * acted on in a stack frame below this one. We must therefore not
 586                  * continue with it now, but let the stack unwind and along the
 587                  * appropriate frame to read the depth count and bail.
 588                  */
 589                 fwalk = NULL;
 590                 break;
 591             }
 592         }
 593         else
 594         {
 595             /*
 596              * the walk reached the end of the depdency list.
 597              */
 598             break;
 599         }
 600     }
 601
 602     if (NULL != fwalk)
 603     {
 604         fib_walk_destroy(fwalk);
 605     }
 606 }
 607
 608 static fib_node_t *
 609 fib_walk_get_node (fib_node_index_t index)
 610 {
 611     fib_walk_t *fwalk;
 612
 613     fwalk = fib_walk_get(index);
 614
 615     return (&(fwalk->fw_node));
 616 }
 617
 618 /**
 619  * Walk objects are not parents, nor are they locked.
 620  * are no-ops
 621  */
 622 static void
 623 fib_walk_last_lock_gone (fib_node_t *node)
 624 {
 625     ASSERT(0);
 626 }
 627
 628 static fib_walk_t*
 629 fib_walk_get_from_node (fib_node_t *node)
 630 {
 631     return ((fib_walk_t*)(((char*)node) -
 632                           STRUCT_OFFSET_OF(fib_walk_t, fw_node)));
 633 }
 634
 635 /**
 636  * @brief Another back walk has reach this walk.
 637  * Megre them so there is only one left. It is this node being
 638  * visited that will remain, so copy or merge the context onto it.
 639  */
 640 static fib_node_back_walk_rc_t
 641 fib_walk_back_walk_notify (fib_node_t *node,
 642                            fib_node_back_walk_ctx_t *ctx)
 643 {
 644     fib_node_back_walk_ctx_t *old;
 645     fib_walk_t *fwalk;
 646
 647     fwalk = fib_walk_get_from_node(node);
 648
 649     /*
 650      * check whether the walk context can be merge with another,
 651      * or whether it needs to be appended.
 652      */
 653     vec_foreach(old, fwalk->fw_ctx)
 654     {
 655         /*
 656          * we can merge walks if the reason for the walk is the same.
 657          */
 658         if (old->fnbw_reason == ctx->fnbw_reason)
 659         {
 660             /*
 661              * copy the largest of the depth values. in the presence of a loop,
 662              * the same walk will merge with itself. if we take the smaller depth
 663              * then it will never end.
 664              */
 665             old->fnbw_depth = ((old->fnbw_depth >= ctx->fnbw_depth) ?
 666                                 old->fnbw_depth :
 667                                 ctx->fnbw_depth);
 668             goto out;
 669         }
 670     }
 671
 672     /*
 673      * walks could not be merged, this means that the walk infront needs to
 674      * perform different action to this one that has caught up. the one in front
 675      * was scheduled first so append the new walk context to the back of the list.
 676      */
 677     vec_add1(fwalk->fw_ctx, *ctx);
 678
 679 out:
 680     return (FIB_NODE_BACK_WALK_MERGE);
 681 }
 682
 683 /**
 684  * The FIB walk's graph node virtual function table
 685  */
 686 static const fib_node_vft_t fib_walk_vft = {
 687     .fnv_get = fib_walk_get_node,
 688     .fnv_last_lock = fib_walk_last_lock_gone,
 689     .fnv_back_walk = fib_walk_back_walk_notify,
 690 };
 691
 692 void
 693 fib_walk_module_init (void)
 694 {
 695     fib_walk_priority_t prio;
 696
 697     FOR_EACH_FIB_WALK_PRIORITY(prio)
 698     {
 699         fib_walk_queues.fwqs_queues[prio].fwq_queue = fib_node_list_create();
 700     }
 701
 702     fib_node_register_type(FIB_NODE_TYPE_WALK, &fib_walk_vft);
 703 }
 704
 705 static u8*
 706 format_fib_walk (u8* s, va_list ap)
 707 {
 708     fib_node_index_t fwi = va_arg(ap, fib_node_index_t);
 709     fib_walk_t *fwalk;
 710
 711     fwalk = fib_walk_get(fwi);
 712
 713     return (format(s, "  parent:{%s:%d} visits:%d flags:%d",
 714                    fib_node_type_get_name(fwalk->fw_parent.fnp_type),
 715                    fwalk->fw_parent.fnp_index,
 716                    fwalk->fw_n_visits,
 717                    fwalk->fw_flags));
 718 }
 719
 720 static clib_error_t *
 721 fib_walk_show (vlib_main_t * vm,
 722                unformat_input_t * input,
 723                vlib_cli_command_t * cmd)
 724 {
 725     fib_walk_queue_stats_t wqs;
 726     fib_walk_priority_t prio;
 727     fib_node_ptr_t sibling;
 728     fib_node_index_t fwi;
 729     fib_walk_t *fwalk;
 730     int more_elts;
 731
 732     vlib_cli_output(vm, "FIB Walk queues:");
 733
 734     FOR_EACH_FIB_WALK_PRIORITY(prio)
 735     {
 736         vlib_cli_output(vm, " %U priority queue:",
 737                         format_fib_walk_priority, prio);
 738         vlib_cli_output(vm, "  Stats: ");
 739
 740         FOR_EACH_FIB_WALK_QUEUE_STATS(wqs)
 741         {
 742             vlib_cli_output(vm, "    %U:%d",
 743                             format_fib_walk_queue_stats, wqs,
 744                             fib_walk_queues.fwqs_queues[prio].fwq_stats[wqs]);
 745         }
 746         vlib_cli_output(vm, "  Occupancy:%d",
 747                         fib_node_list_get_size(
 748                             fib_walk_queues.fwqs_queues[prio].fwq_queue));
 749
 750         more_elts = fib_node_list_get_front(
 751                         fib_walk_queues.fwqs_queues[prio].fwq_queue,
 752                         &sibling);
 753
 754         while (more_elts)
 755         {
 756             ASSERT(FIB_NODE_INDEX_INVALID != sibling.fnp_index);
 757             ASSERT(FIB_NODE_TYPE_WALK == sibling.fnp_type);
 758
 759             fwi = sibling.fnp_index;
 760             fwalk = fib_walk_get(fwi);
 761
 762             vlib_cli_output(vm, "  %U", format_fib_walk, fwi);
 763
 764             more_elts = fib_node_list_elt_get_next(fwalk->fw_prio_sibling,
 765                                                    &sibling);
 766         }
 767     }
 768     return (NULL);
 769 }
 770
 771 VLIB_CLI_COMMAND (fib_walk_show_command, static) = {
 772     .path = "show fib walk",
 773     .short_help = "show fib walk",
 774     .function = fib_walk_show,
 775 };