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