src/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      * Time the walk started
  82      */
  83     f64 fw_start_time;
  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      */
  90     fib_node_back_walk_ctx_t *fw_ctx;
  91 } fib_walk_t;
  92
  93 /**
  94  * @brief The pool of all walk objects
  95  */
  96 static fib_walk_t *fib_walk_pool;
  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  */
 106 typedef enum fib_walk_queue_stats_t_
 107 {
 108     FIB_WALK_SCHEDULED,
 109     FIB_WALK_COMPLETED,
 110 } fib_walk_queue_stats_t;
 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      */
 140     u64 fwq_stats[FIB_WALK_QUEUE_STATS_NUM];
 141
 142     /**
 143      * The node list which acts as the queue
 144      */
 145     fib_node_list_t fwq_queue;
 146 } fib_walk_queue_t;
 147
 148 /**
 149  * A set of priority queues for outstanding walks
 150  */
 151 typedef struct fib_walk_queues_t_
 152 {
 153     fib_walk_queue_t fwqs_queues[FIB_WALK_PRIORITY_NUM];
 154 } fib_walk_queues_t;
 155
 156 /**
 157  * The global queues of outstanding walks
 158  */
 159 static fib_walk_queues_t fib_walk_queues;
 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
 181 static u32 history_last_walk_pos;
 182 typedef struct fib_walk_history_t_ {
 183     u32 fwh_n_visits;
 184     f64 fwh_duration;
 185     f64 fwh_completed;
 186     fib_node_ptr_t fwh_parent;
 187     fib_walk_flags_t fwh_flags;
 188     fib_node_bw_reason_flag_t fwh_reason[MAX_HISTORY_REASONS];
 189 } 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
 197     ASSERT(prio < FIB_WALK_PRIORITY_NUM);
 198
 199     return (format(s, "%s", fib_walk_priority_names[prio]));
 200 }
 201 static u8*
 202 format_fib_walk_queue_stats (u8 *s, va_list ap)
 203 {
 204     fib_walk_queue_stats_t wqs = va_arg(ap, fib_walk_queue_stats_t);
 205
 206     ASSERT(wqs < FIB_WALK_QUEUE_STATS_NUM);
 207
 208     return (format(s, "%s", fib_walk_queue_stats_names[wqs]));
 209 }
 210
 211 static index_t
 212 fib_walk_get_index (fib_walk_t *fwalk)
 213 {
 214     return (fwalk - fib_walk_pool);
 215 }
 216
 217 static fib_walk_t *
 218 fib_walk_get (index_t fwi)
 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
 227 fib_walk_queue_get_size (fib_walk_priority_t prio)
 228 {
 229     return (fib_node_list_get_size(fib_walk_queues.fwqs_queues[prio].fwq_queue));
 230 }
 231
 232 static fib_node_index_t
 233 fib_walk_queue_get_front (fib_walk_priority_t prio)
 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
 243 fib_walk_destroy (fib_walk_t *fwalk)
 244 {
 245     u32 bucket, ii;
 246
 247     if (FIB_NODE_INDEX_INVALID != fwalk->fw_prio_sibling)
 248     {
 249         fib_node_list_elt_remove(fwalk->fw_prio_sibling);
 250     }
 251     fib_node_child_remove(fwalk->fw_parent.fnp_type,
 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 ?
 260               HISTOGRAM_VISITS_PER_WALK_N_BUCKETS - 1 :
 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 =
 271         vlib_time_now(vlib_get_main());
 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  */
 299 typedef enum fib_walk_advance_rc_t_
 300 {
 301     /**
 302      * The walk is complete
 303      */
 304     FIB_WALK_ADVANCE_DONE,
 305     /**
 306      * the walk has more work
 307      */
 308     FIB_WALK_ADVANCE_MORE,
 309     /**
 310      * The walk merged with the one in front
 311      */
 312     FIB_WALK_ADVANCE_MERGE,
 313 } fib_walk_advance_rc_t;
 314
 315 /**
 316  * @brief Advance the walk one element in its work list
 317  */
 318 static fib_walk_advance_rc_t
 319 fib_walk_advance (fib_node_index_t fwi)
 320 {
 321     fib_node_back_walk_ctx_t *ctx, *old;
 322     fib_node_back_walk_rc_t wrc;
 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  */
 381 typedef enum fib_walk_sleep_type_t_
 382 {
 383     FIB_WALK_SHORT_SLEEP,
 384     FIB_WALK_LONG_SLEEP,
 385 } fib_walk_sleep_type_t;
 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
 427 fib_walk_process_queues (vlib_main_t * vm,
 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
 443     FOR_EACH_FIB_WALK_PRIORITY(prio)
 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);
 453             fwalk->fw_flags |= FIB_WALK_FLAG_EXECUTING;
 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);
 479                 fwalk->fw_flags &= ~FIB_WALK_FLAG_EXECUTING;
 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      */
 497     bucket = ((n_elts/fib_walk_work_nodes_visisted_incr) > N_ELTS_BUCKETS ?
 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
 517 fib_walk_process (vlib_main_t * vm,
 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          */
 534         vlib_process_get_events(vm, NULL);
 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 *
 558 fib_walk_alloc (fib_node_type_t parent_type,
 559                 fib_node_index_t parent_index,
 560                 fib_walk_flags_t flags,
 561                 fib_node_back_walk_ctx_t *ctx)
 562 {
 563     fib_walk_t *fwalk;
 564
 565     pool_get(fib_walk_pool, fwalk);
 566
 567     fib_node_init(&fwalk->fw_node, FIB_NODE_TYPE_WALK);
 568
 569     fwalk->fw_flags = flags;
 570     fwalk->fw_dep_sibling  = FIB_NODE_INDEX_INVALID;
 571     fwalk->fw_prio_sibling = FIB_NODE_INDEX_INVALID;
 572     fwalk->fw_parent.fnp_index = parent_index;
 573     fwalk->fw_parent.fnp_type = parent_type;
 574     fwalk->fw_ctx = NULL;
 575     fwalk->fw_start_time = vlib_time_now(vlib_get_main());
 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
 595 fib_walk_prio_queue_enquue (fib_walk_priority_t prio,
 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,
 602                                        FIB_NODE_TYPE_WALK,
 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      */
 611     vlib_process_signal_event(vlib_get_main(),
 612                               fib_walk_process_node.index,
 613                               FIB_WALK_EVENT,
 614                               FIB_WALK_EVENT);
 615
 616     return (sibling);
 617 }
 618
 619 void
 620 fib_walk_async (fib_node_type_t parent_type,
 621                 fib_node_index_t parent_index,
 622                 fib_walk_priority_t prio,
 623                 fib_node_back_walk_ctx_t *ctx)
 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     }
 643     if (ctx->fnbw_flags & FIB_NODE_BW_FLAG_FORCE_SYNC)
 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,
 655                            FIB_WALK_FLAG_ASYNC,
 656                            ctx);
 657
 658     fwalk->fw_dep_sibling = fib_node_child_add(parent_type,
 659                                                parent_index,
 660                                                FIB_NODE_TYPE_WALK,
 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
 674 fib_walk_sync (fib_node_type_t parent_type,
 675                fib_node_index_t parent_index,
 676                fib_node_back_walk_ctx_t *ctx)
 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,
 701                            FIB_WALK_FLAG_SYNC,
 702                            ctx);
 703
 704     fwalk->fw_dep_sibling = fib_node_child_add(parent_type,
 705                                                parent_index,
 706                                                FIB_NODE_TYPE_WALK,
 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          */
 715         fwalk->fw_flags |= FIB_WALK_FLAG_EXECUTING;
 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 *
 782 fib_walk_get_node (fib_node_index_t index)
 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
 796 fib_walk_last_lock_gone (fib_node_t *node)
 797 {
 798     ASSERT(0);
 799 }
 800
 801 static fib_walk_t*
 802 fib_walk_get_from_node (fib_node_t *node)
 803 {
 804     return ((fib_walk_t*)(((char*)node) -
 805                           STRUCT_OFFSET_OF(fib_walk_t, fw_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  */
 813 static fib_node_back_walk_rc_t
 814 fib_walk_back_walk_notify (fib_node_t *node,
 815                            fib_node_back_walk_ctx_t *ctx)
 816 {
 817     fib_node_back_walk_ctx_t *last;
 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 = {
 858     .fnv_get = fib_walk_get_node,
 859     .fnv_last_lock = fib_walk_last_lock_gone,
 860     .fnv_back_walk = fib_walk_back_walk_notify,
 861 };
 862
 863 void
 864 fib_walk_module_init (void)
 865 {
 866     fib_walk_priority_t prio;
 867
 868     FOR_EACH_FIB_WALK_PRIORITY(prio)
 869     {
 870         fib_walk_queues.fwqs_queues[prio].fwq_queue = fib_node_list_create();
 871     }
 872
 873     fib_node_register_type(FIB_NODE_TYPE_WALK, &fib_walk_vft);
 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",
 885                    fib_node_type_get_name(fwalk->fw_parent.fnp_type),
 886                    fwalk->fw_parent.fnp_index,
 887                    fwalk->fw_n_visits,
 888                    fwalk->fw_flags));
 889 }
 890
 891 static clib_error_t *
 892 fib_walk_show (vlib_main_t * vm,
 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
 908     FOR_EACH_FIB_WALK_PRIORITY(prio)
 909     {
 910         vlib_cli_output(vm, " %U priority queue:",
 911                         format_fib_walk_priority, prio);
 912         vlib_cli_output(vm, "  Stats: ");
 913
 914         FOR_EACH_FIB_WALK_QUEUE_STATS(wqs)
 915         {
 916             vlib_cli_output(vm, "    %U:%d",
 917                             format_fib_walk_queue_stats, wqs,
 918                             fib_walk_queues.fwqs_queues[prio].fwq_stats[wqs]);
 919         }
 920         vlib_cli_output(vm, "  Occupancy:%d",
 921                         fib_node_list_get_size(
 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         {
 930             ASSERT(FIB_NODE_INDEX_INVALID != sibling.fnp_index);
 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 ",
 979                        ii*HISTOGRAM_VISITS_PER_WALK_INCR,
 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         {
 995             fib_node_back_walk_reason_t reason;
 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 *
1039 fib_walk_set_quota (vlib_main_t * vm,
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 *
1065 fib_walk_set_histogram_elements_size (vlib_main_t * vm,
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",
1087     .function = fib_walk_set_histogram_elements_size,
1088 };
1089
1090 static clib_error_t *
1091 fib_walk_clear (vlib_main_t * vm,
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 };