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