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 <vppinfra/mhash.h>
17 : #include <vnet/ip/ip.h>
18 : #include <vnet/adj/adj.h>
19 : #include <vnet/dpo/load_balance.h>
20 : #include <vnet/dpo/load_balance_map.h>
21 :
22 : #include <vnet/fib/fib_path_list.h>
23 : #include <vnet/fib/fib_internal.h>
24 : #include <vnet/fib/fib_node_list.h>
25 : #include <vnet/fib/fib_walk.h>
26 : #include <vnet/fib/fib_urpf_list.h>
27 : #include <vnet/fib/fib_path_ext.h>
28 : #include <vnet/fib/fib_table.h>
29 :
30 : /**
31 : * The magic number of child entries that make a path-list popular.
32 : * There's a trade-off here between convergence and forwarding speed.
33 : * Popular path-lists generate load-balance maps for the entries that
34 : * use them. If the map is present there is a switch path cost to indirect
35 : * through the map - this indirection provides the fast convergence - so
36 : * without the map convergence is slower.
37 : */
38 : #define FIB_PATH_LIST_POPULAR 64
39 :
40 : /**
41 : * FIB path-list
42 : * A representation of the list/set of path trough which a prefix is reachable
43 : */
44 : typedef struct fib_path_list_t_ {
45 : /**
46 : * A path-list is a node in the FIB graph.
47 : */
48 : fib_node_t fpl_node;
49 :
50 : /**
51 : * Flags on the path-list
52 : */
53 : fib_path_list_flags_t fpl_flags;
54 :
55 : /**
56 : * Vector of paths indicies for all configured paths.
57 : * For shareable path-lists this list MUST not change.
58 : */
59 : fib_node_index_t *fpl_paths;
60 :
61 : /**
62 : * the RPF list calculated for this path list
63 : */
64 : fib_node_index_t fpl_urpf;
65 : } fib_path_list_t;
66 :
67 : /*
68 : * Array of strings/names for the FIB sources
69 : */
70 : static const char *fib_path_list_attr_names[] = FIB_PATH_LIST_ATTRIBUTES;
71 :
72 : /*
73 : * The memory pool from which we allocate all the path-lists
74 : */
75 : static fib_path_list_t * fib_path_list_pool;
76 :
77 : /*
78 : * The data-base of shared path-lists
79 : */
80 : static uword *fib_path_list_db;
81 :
82 : /**
83 : * the logger
84 : */
85 : vlib_log_class_t fib_path_list_logger;
86 :
87 : /*
88 : * Debug macro
89 : */
90 : #define FIB_PATH_LIST_DBG(_pl, _fmt, _args...) \
91 : { \
92 : vlib_log_debug(fib_path_list_logger, \
93 : "[%U]:" _fmt, \
94 : format_fib_path_list, \
95 : fib_path_list_get_index(_pl), 0, \
96 : ##_args); \
97 : }
98 :
99 : static fib_path_list_t *
100 1644230 : fib_path_list_get (fib_node_index_t index)
101 : {
102 1644230 : return (pool_elt_at_index(fib_path_list_pool, index));
103 : }
104 :
105 : static fib_node_t *
106 451305 : fib_path_list_get_node (fib_node_index_t index)
107 : {
108 451305 : return ((fib_node_t*)fib_path_list_get(index));
109 : }
110 :
111 : static fib_path_list_t*
112 48140 : fib_path_list_from_fib_node (fib_node_t *node)
113 : {
114 48140 : ASSERT(FIB_NODE_TYPE_PATH_LIST == node->fn_type);
115 48140 : return ((fib_path_list_t*)node);
116 : }
117 :
118 : static fib_node_index_t
119 649296 : fib_path_list_get_index (fib_path_list_t *path_list)
120 : {
121 649296 : return (path_list - fib_path_list_pool);
122 : }
123 :
124 : u8 *
125 237 : format_fib_path_list (u8 * s, va_list * args)
126 : {
127 : fib_node_index_t *path_index, path_list_index;
128 : fib_path_list_attribute_t attr;
129 : fib_path_list_t *path_list;
130 : u32 indent;
131 :
132 237 : path_list_index = va_arg (*args, fib_node_index_t);
133 237 : indent = va_arg (*args, u32);
134 237 : path_list = fib_path_list_get(path_list_index);
135 :
136 237 : s = format (s, "%Upath-list:[%d]",
137 : format_white_space, indent,
138 : fib_path_list_get_index(path_list));
139 237 : s = format (s, " locks:%u", path_list->fpl_node.fn_locks);
140 :
141 237 : if (FIB_PATH_LIST_FLAG_NONE != path_list->fpl_flags)
142 : {
143 234 : s = format (s, " flags:");
144 2106 : FOR_EACH_PATH_LIST_ATTRIBUTE(attr)
145 : {
146 1872 : if ((1<<attr) & path_list->fpl_flags)
147 : {
148 240 : s = format (s, "%s,", fib_path_list_attr_names[attr]);
149 : }
150 : }
151 : }
152 237 : s = format (s, " %U\n", format_fib_urpf_list, path_list->fpl_urpf);
153 :
154 543 : vec_foreach (path_index, path_list->fpl_paths)
155 : {
156 306 : s = format(s, "%U", format_fib_path, *path_index, indent+2,
157 : FIB_PATH_FORMAT_FLAGS_NONE);
158 306 : s = format(s, "\n");
159 : }
160 :
161 237 : return (s);
162 : }
163 :
164 : u8 *
165 221 : fib_path_list_format (fib_node_index_t path_list_index,
166 : u8 * s)
167 : {
168 221 : return (format(s, "%U", format_fib_path_list, path_list_index, 4));
169 : }
170 :
171 : static uword
172 71824 : fib_path_list_hash (fib_path_list_t *path_list)
173 : {
174 : uword old_path_list_hash, new_path_list_hash, path_hash;
175 : fib_node_index_t *path_index;
176 :
177 71824 : ASSERT(path_list);
178 :
179 71824 : new_path_list_hash =
180 71824 : old_path_list_hash =
181 71824 : (vec_len(path_list->fpl_paths) << 16 |
182 71824 : (path_list->fpl_flags & FIB_PATH_LIST_KEY_FLAGS));
183 :
184 262187 : vec_foreach (path_index, path_list->fpl_paths)
185 : {
186 190363 : path_hash = fib_path_hash(*path_index);
187 : #if uword_bits == 64
188 190363 : hash_mix64(path_hash, old_path_list_hash, new_path_list_hash);
189 : #else
190 : hash_mix32(path_hash, old_path_list_hash, new_path_list_hash);
191 : #endif
192 : }
193 :
194 71824 : return (new_path_list_hash);
195 : }
196 :
197 : always_inline uword
198 13755 : fib_path_list_db_hash_key_from_index (uword index)
199 : {
200 13755 : return 1 + 2*index;
201 : }
202 :
203 : always_inline uword
204 111112 : fib_path_list_db_hash_key_is_index (uword key)
205 : {
206 111112 : return key & 1;
207 : }
208 :
209 : always_inline uword
210 39288 : fib_path_list_db_hash_key_2_index (uword key)
211 : {
212 39288 : ASSERT (fib_path_list_db_hash_key_is_index (key));
213 39288 : return key / 2;
214 : }
215 :
216 : static fib_path_list_t*
217 71824 : fib_path_list_db_get_from_hash_key (uword key)
218 : {
219 : fib_path_list_t *path_list;
220 :
221 71824 : if (fib_path_list_db_hash_key_is_index (key))
222 : {
223 : fib_node_index_t path_list_index;
224 :
225 39288 : path_list_index = fib_path_list_db_hash_key_2_index(key);
226 39288 : path_list = fib_path_list_get(path_list_index);
227 : }
228 : else
229 : {
230 32536 : path_list = uword_to_pointer (key, fib_path_list_t *);
231 : }
232 :
233 71824 : return (path_list);
234 : }
235 :
236 : static uword
237 35968 : fib_path_list_db_hash_key_sum (hash_t * h,
238 : uword key)
239 : {
240 : fib_path_list_t *path_list;
241 :
242 35968 : path_list = fib_path_list_db_get_from_hash_key(key);
243 :
244 35968 : return (fib_path_list_hash(path_list));
245 : }
246 :
247 : static uword
248 17928 : fib_path_list_db_hash_key_equal (hash_t * h,
249 : uword key1,
250 : uword key2)
251 : {
252 : fib_path_list_t *path_list1, *path_list2;
253 :
254 17928 : path_list1 = fib_path_list_db_get_from_hash_key(key1);
255 17928 : path_list2 = fib_path_list_db_get_from_hash_key(key2);
256 :
257 35856 : return (fib_path_list_hash(path_list1) ==
258 17928 : fib_path_list_hash(path_list2));
259 : }
260 :
261 : static fib_node_index_t
262 23557 : fib_path_list_db_find (fib_path_list_t *path_list)
263 : {
264 : uword *p;
265 :
266 23557 : p = hash_get(fib_path_list_db, path_list);
267 :
268 23557 : if (NULL != p)
269 : {
270 9431 : return p[0];
271 : }
272 :
273 14126 : return (FIB_NODE_INDEX_INVALID);
274 : }
275 :
276 : static void
277 7063 : fib_path_list_db_insert (fib_node_index_t path_list_index)
278 : {
279 : fib_path_list_t *path_list;
280 :
281 7063 : path_list = fib_path_list_get(path_list_index);
282 :
283 7063 : ASSERT(FIB_NODE_INDEX_INVALID == fib_path_list_db_find(path_list));
284 :
285 7063 : hash_set (fib_path_list_db,
286 : fib_path_list_db_hash_key_from_index(path_list_index),
287 : path_list_index);
288 :
289 7063 : FIB_PATH_LIST_DBG(path_list, "DB-inserted");
290 7063 : }
291 :
292 : static void
293 6692 : fib_path_list_db_remove (fib_node_index_t path_list_index)
294 : {
295 : fib_path_list_t *path_list;
296 :
297 6692 : path_list = fib_path_list_get(path_list_index);
298 :
299 6692 : ASSERT(FIB_NODE_INDEX_INVALID != fib_path_list_db_find(path_list));
300 :
301 6692 : hash_unset(fib_path_list_db,
302 : fib_path_list_db_hash_key_from_index(path_list_index));
303 :
304 6692 : FIB_PATH_LIST_DBG(path_list, "DB-removed");
305 6692 : }
306 :
307 : static void
308 56756 : fib_path_list_destroy (fib_path_list_t *path_list)
309 : {
310 : fib_node_index_t *path_index;
311 :
312 56756 : FIB_PATH_LIST_DBG(path_list, "destroy");
313 :
314 124856 : vec_foreach (path_index, path_list->fpl_paths)
315 : {
316 68100 : fib_path_destroy(*path_index);
317 : }
318 :
319 56756 : vec_free(path_list->fpl_paths);
320 56756 : fib_urpf_list_unlock(path_list->fpl_urpf);
321 :
322 56756 : fib_node_deinit(&path_list->fpl_node);
323 56756 : pool_put(fib_path_list_pool, path_list);
324 56756 : }
325 :
326 : static void
327 48140 : fib_path_list_last_lock_gone (fib_node_t *node)
328 : {
329 : fib_path_list_t *path_list;
330 :
331 48140 : path_list = fib_path_list_from_fib_node(node);
332 :
333 48140 : FIB_PATH_LIST_DBG(path_list, "last-lock");
334 :
335 48140 : if (path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED)
336 : {
337 6692 : fib_path_list_db_remove(fib_path_list_get_index(path_list));
338 : }
339 48140 : fib_path_list_destroy(path_list);
340 48140 : }
341 :
342 : static load_balance_flags_t
343 2878 : fib_path_list_fwd_flags_2_load_balance (fib_path_list_fwd_flags_t pl_flags)
344 : {
345 2878 : load_balance_flags_t lb_flags = LOAD_BALANCE_FLAG_NONE;
346 :
347 2878 : if (pl_flags & FIB_PATH_LIST_FWD_FLAG_STICKY)
348 : {
349 0 : lb_flags |= LOAD_BALANCE_ATTR_STICKY;
350 : }
351 2878 : return (lb_flags);
352 : }
353 :
354 : /*
355 : * fib_path_mk_lb
356 : *
357 : * update the multipath adj this path-list will contribute to its
358 : * children's forwarding.
359 : */
360 : static void
361 2878 : fib_path_list_mk_lb (fib_path_list_t *path_list,
362 : fib_forward_chain_type_t fct,
363 : dpo_id_t *dpo,
364 : fib_path_list_fwd_flags_t flags)
365 : {
366 : fib_node_index_t *path_index;
367 : load_balance_path_t *nhs;
368 : dpo_proto_t dproto;
369 :
370 2878 : nhs = NULL;
371 2878 : dproto = fib_forw_chain_type_to_dpo_proto(fct);
372 :
373 : /*
374 : * We gather the DPOs from resolved paths.
375 : */
376 6295 : vec_foreach (path_index, path_list->fpl_paths)
377 : {
378 6834 : if ((flags & FIB_PATH_LIST_FWD_FLAG_STICKY) ||
379 3417 : fib_path_is_resolved(*path_index))
380 : {
381 3221 : nhs = fib_path_append_nh_for_multipath_hash(
382 : *path_index, fct,
383 3221 : fib_forw_chain_type_to_dpo_proto(fct),
384 : nhs);
385 : }
386 : }
387 :
388 : /*
389 : * Path-list load-balances, which if used, would be shared and hence
390 : * never need a load-balance map.
391 : */
392 5756 : dpo_set(dpo,
393 : DPO_LOAD_BALANCE,
394 : dproto,
395 2878 : load_balance_create(vec_len(nhs),
396 : dproto,
397 : load_balance_get_default_flow_hash(dproto)));
398 2878 : load_balance_multipath_update(dpo, nhs,
399 2878 : fib_path_list_fwd_flags_2_load_balance(flags));
400 :
401 2878 : FIB_PATH_LIST_DBG(path_list, "mk lb: %d", dpo->dpoi_index);
402 :
403 2878 : vec_free(nhs);
404 2878 : }
405 :
406 : /**
407 : * @brief [re]build the path list's uRPF list
408 : */
409 : static void
410 86388 : fib_path_list_mk_urpf (fib_path_list_t *path_list)
411 : {
412 : fib_node_index_t *path_index;
413 :
414 : /*
415 : * ditch the old one. by iterating through all paths we are going
416 : * to re-find all the adjs that were in the old one anyway. If we
417 : * keep the old one, then the |sort|uniq requires more work.
418 : * All users of the RPF list have their own lock, so we can release
419 : * immediately.
420 : */
421 86388 : fib_urpf_list_unlock(path_list->fpl_urpf);
422 86388 : path_list->fpl_urpf = fib_urpf_list_alloc_and_lock();
423 :
424 225882 : vec_foreach (path_index, path_list->fpl_paths)
425 : {
426 139494 : fib_path_contribute_urpf(*path_index, path_list->fpl_urpf);
427 : }
428 :
429 86388 : fib_urpf_list_bake(path_list->fpl_urpf);
430 86388 : }
431 :
432 : /**
433 : * @brief Contribute (add) this path list's uRPF list. This allows the child
434 : * to construct an aggregate list.
435 : */
436 : void
437 3306 : fib_path_list_contribute_urpf (fib_node_index_t path_list_index,
438 : index_t urpf)
439 : {
440 : fib_path_list_t *path_list;
441 :
442 3306 : path_list = fib_path_list_get(path_list_index);
443 :
444 3306 : fib_urpf_list_combine(urpf, path_list->fpl_urpf);
445 3306 : }
446 :
447 : /**
448 : * @brief Return the the child the RPF list pre-built for this path list
449 : */
450 : index_t
451 79876 : fib_path_list_get_urpf (fib_node_index_t path_list_index)
452 : {
453 : fib_path_list_t *path_list;
454 :
455 79876 : path_list = fib_path_list_get(path_list_index);
456 :
457 79876 : return (path_list->fpl_urpf);
458 : }
459 :
460 : /*
461 : * fib_path_list_back_walk
462 : *
463 : * Called from one of this path-list's paths to progate
464 : * a back walk
465 : */
466 : void
467 32165 : fib_path_list_back_walk (fib_node_index_t path_list_index,
468 : fib_node_back_walk_ctx_t *ctx)
469 : {
470 : fib_path_list_t *path_list;
471 :
472 32165 : path_list = fib_path_list_get(path_list_index);
473 :
474 32165 : fib_path_list_mk_urpf(path_list);
475 :
476 32165 : FIB_PATH_LIST_DBG(path_list, "bw:%U",
477 : format_fib_node_bw_reason, ctx->fnbw_reason);
478 :
479 : /*
480 : * propagate the backwalk further
481 : */
482 32165 : if (path_list->fpl_flags & FIB_PATH_LIST_FLAG_POPULAR)
483 : {
484 : /*
485 : * many children. schedule a async walk
486 : */
487 56 : fib_walk_async(FIB_NODE_TYPE_PATH_LIST,
488 : path_list_index,
489 : FIB_WALK_PRIORITY_LOW,
490 : ctx);
491 : }
492 : else
493 : {
494 : /*
495 : * only a few children. continue the walk synchronously
496 : */
497 32109 : fib_walk_sync(FIB_NODE_TYPE_PATH_LIST, path_list_index, ctx);
498 : }
499 32165 : }
500 :
501 : /*
502 : * fib_path_list_back_walk_notify
503 : *
504 : * A back walk has reach this path-list.
505 : */
506 : static fib_node_back_walk_rc_t
507 0 : fib_path_list_back_walk_notify (fib_node_t *node,
508 : fib_node_back_walk_ctx_t *ctx)
509 : {
510 : /*
511 : * the path-list is not a direct child of any other node type
512 : * paths, which do not change their to-list-mapping, save the
513 : * list they are a member of, and invoke the BW function directly.
514 : */
515 0 : ASSERT(0);
516 :
517 0 : return (FIB_NODE_BACK_WALK_CONTINUE);
518 : }
519 :
520 : /*
521 : * Display the path-list memory usage
522 : */
523 : static void
524 1 : fib_path_list_memory_show (void)
525 : {
526 1 : fib_show_memory_usage("Path-list",
527 1 : pool_elts(fib_path_list_pool),
528 1 : pool_len(fib_path_list_pool),
529 : sizeof(fib_path_list_t));
530 1 : fib_urpf_list_show_mem();
531 1 : }
532 :
533 : /*
534 : * The FIB path-list's graph node virtual function table
535 : */
536 : static const fib_node_vft_t fib_path_list_vft = {
537 : .fnv_get = fib_path_list_get_node,
538 : .fnv_last_lock = fib_path_list_last_lock_gone,
539 : .fnv_back_walk = fib_path_list_back_walk_notify,
540 : .fnv_mem_show = fib_path_list_memory_show,
541 : };
542 :
543 : static inline fib_path_list_t *
544 70262 : fib_path_list_alloc (fib_node_index_t *path_list_index)
545 : {
546 : fib_path_list_t *path_list;
547 :
548 70262 : pool_get(fib_path_list_pool, path_list);
549 70262 : clib_memset(path_list, 0, sizeof(*path_list));
550 :
551 70262 : fib_node_init(&path_list->fpl_node,
552 : FIB_NODE_TYPE_PATH_LIST);
553 70262 : path_list->fpl_urpf = INDEX_INVALID;
554 70262 : path_list->fpl_paths = NULL;
555 :
556 70262 : *path_list_index = fib_path_list_get_index(path_list);
557 :
558 70262 : FIB_PATH_LIST_DBG(path_list, "alloc");
559 :
560 70262 : return (path_list);
561 : }
562 :
563 : static fib_path_list_t *
564 61646 : fib_path_list_resolve (fib_path_list_t *path_list)
565 : {
566 : fib_node_index_t *path_index, *paths, path_list_index;
567 :
568 61646 : ASSERT(!(path_list->fpl_flags & FIB_PATH_LIST_FLAG_RESOLVED));
569 :
570 : /*
571 : * resolving a path-list is a recursive action. this means more path
572 : * lists can be created during this call, and hence this path-list
573 : * can be realloc'd. so we work with copies.
574 : * this function is called only once per-path list, so its no great overhead.
575 : */
576 61646 : path_list_index = fib_path_list_get_index(path_list);
577 61646 : paths = vec_dup(path_list->fpl_paths);
578 :
579 128673 : vec_foreach (path_index, paths)
580 : {
581 67027 : fib_path_resolve(*path_index);
582 : }
583 :
584 61646 : vec_free(paths);
585 61646 : path_list = fib_path_list_get(path_list_index);
586 :
587 61646 : FIB_PATH_LIST_DBG(path_list, "resovled");
588 :
589 61646 : if (!(path_list->fpl_flags & FIB_PATH_LIST_FLAG_NO_URPF))
590 : {
591 54223 : fib_path_list_mk_urpf(path_list);
592 : }
593 61646 : return (path_list);
594 : }
595 :
596 : u32
597 159913 : fib_path_list_get_n_paths (fib_node_index_t path_list_index)
598 : {
599 : fib_path_list_t *path_list;
600 :
601 159913 : if (FIB_NODE_INDEX_INVALID == path_list_index)
602 : {
603 178 : return (0);
604 : }
605 :
606 159735 : path_list = fib_path_list_get(path_list_index);
607 :
608 159735 : return (vec_len(path_list->fpl_paths));
609 : }
610 :
611 :
612 : u32
613 95410 : fib_path_list_get_resolving_interface (fib_node_index_t path_list_index)
614 : {
615 : fib_node_index_t *path_index;
616 : fib_path_list_t *path_list;
617 : u32 sw_if_index;
618 :
619 95410 : path_list = fib_path_list_get(path_list_index);
620 :
621 95408 : sw_if_index = ~0;
622 99994 : vec_foreach (path_index, path_list->fpl_paths)
623 : {
624 95408 : sw_if_index = fib_path_get_resolving_interface(*path_index);
625 95410 : if (~0 != sw_if_index)
626 : {
627 90824 : return (sw_if_index);
628 : }
629 : }
630 :
631 4586 : return (sw_if_index);
632 : }
633 :
634 : dpo_proto_t
635 0 : fib_path_list_get_proto (fib_node_index_t path_list_index)
636 : {
637 : fib_path_list_t *path_list;
638 :
639 0 : path_list = fib_path_list_get(path_list_index);
640 :
641 : /*
642 : * we don't support a mix of path protocols, so we can return the proto
643 : * of the first
644 : */
645 0 : return (fib_path_get_proto(path_list->fpl_paths[0]));
646 : }
647 :
648 : int
649 8448 : fib_path_list_is_looped (fib_node_index_t path_list_index)
650 : {
651 : fib_path_list_t *path_list;
652 :
653 8448 : path_list = fib_path_list_get(path_list_index);
654 :
655 8448 : return (path_list->fpl_flags & FIB_PATH_LIST_FLAG_LOOPED);
656 : }
657 :
658 : int
659 2637 : fib_path_list_is_popular (fib_node_index_t path_list_index)
660 : {
661 : fib_path_list_t *path_list;
662 :
663 2637 : path_list = fib_path_list_get(path_list_index);
664 :
665 2637 : return (path_list->fpl_flags & FIB_PATH_LIST_FLAG_POPULAR);
666 : }
667 :
668 : static fib_path_list_flags_t
669 42545 : fib_path_list_flags_fixup (fib_path_list_flags_t flags)
670 : {
671 : /*
672 : * we do no share drop nor exclusive path-lists
673 : */
674 42545 : if (flags & FIB_PATH_LIST_FLAG_DROP ||
675 42545 : flags & FIB_PATH_LIST_FLAG_EXCLUSIVE)
676 : {
677 406 : flags &= ~FIB_PATH_LIST_FLAG_SHARED;
678 : }
679 :
680 42545 : return (flags);
681 : }
682 :
683 : fib_node_index_t
684 36358 : fib_path_list_create (fib_path_list_flags_t flags,
685 : const fib_route_path_t *rpaths)
686 : {
687 : fib_node_index_t path_list_index, old_path_list_index;
688 : fib_path_list_t *path_list;
689 : int i;
690 :
691 36358 : flags = fib_path_list_flags_fixup(flags);
692 36358 : path_list = fib_path_list_alloc(&path_list_index);
693 36358 : path_list->fpl_flags = flags;
694 :
695 36358 : if (NULL != rpaths)
696 : {
697 72691 : vec_foreach_index(i, rpaths)
698 : {
699 43530 : vec_add1(path_list->fpl_paths,
700 : fib_path_create(path_list_index,
701 : &rpaths[i]));
702 : }
703 : /*
704 : * we sort the paths since the key for the path-list is
705 : * the description of the paths it contains. The paths need to
706 : * be sorted else this description will differ.
707 : */
708 29161 : if (vec_len(path_list->fpl_paths) > 1)
709 : {
710 1289 : vec_sort_with_function(path_list->fpl_paths,
711 : fib_path_cmp_for_sort);
712 : }
713 : }
714 :
715 : /*
716 : * If a shared path list is requested, consult the DB for a match
717 : */
718 36358 : if (flags & FIB_PATH_LIST_FLAG_SHARED)
719 : {
720 : /*
721 : * check for a matching path-list in the DB.
722 : * If we find one then we can return the existing one and destroy the
723 : * new one just created.
724 : */
725 9504 : old_path_list_index = fib_path_list_db_find(path_list);
726 9504 : if (FIB_NODE_INDEX_INVALID != old_path_list_index)
727 : {
728 2475 : fib_path_list_destroy(path_list);
729 :
730 2475 : path_list_index = old_path_list_index;
731 : }
732 : else
733 : {
734 : /*
735 : * if there was not a matching path-list, then this
736 : * new one will need inserting into the DB and resolving.
737 : */
738 7029 : fib_path_list_db_insert(path_list_index);
739 7029 : path_list = fib_path_list_resolve(path_list);
740 : }
741 : }
742 : else
743 : {
744 : /*
745 : * no shared path list requested. resolve and use the one
746 : * just created.
747 : */
748 26854 : path_list = fib_path_list_resolve(path_list);
749 : }
750 :
751 36358 : return (path_list_index);
752 : }
753 :
754 : static fib_path_cfg_flags_t
755 27717 : fib_path_list_flags_2_path_flags (fib_path_list_flags_t plf)
756 : {
757 27717 : fib_path_cfg_flags_t pf = FIB_PATH_CFG_FLAG_NONE;
758 :
759 27717 : if (plf & FIB_PATH_LIST_FLAG_DROP)
760 : {
761 12274 : pf |= FIB_PATH_CFG_FLAG_DROP;
762 : }
763 27717 : if (plf & FIB_PATH_LIST_FLAG_EXCLUSIVE)
764 : {
765 1083 : pf |= FIB_PATH_CFG_FLAG_EXCLUSIVE;
766 : }
767 27717 : if (plf & FIB_PATH_LIST_FLAG_LOCAL)
768 : {
769 7183 : pf |= FIB_PATH_CFG_FLAG_LOCAL;
770 : }
771 :
772 27717 : return (pf);
773 : }
774 :
775 : fib_node_index_t
776 27717 : fib_path_list_create_special (dpo_proto_t nh_proto,
777 : fib_path_list_flags_t flags,
778 : const dpo_id_t *dpo)
779 : {
780 : fib_node_index_t path_index, path_list_index;
781 : fib_path_list_t *path_list;
782 :
783 27717 : path_list = fib_path_list_alloc(&path_list_index);
784 27717 : path_list->fpl_flags = flags;
785 :
786 : path_index =
787 27717 : fib_path_create_special(path_list_index,
788 : nh_proto,
789 27717 : fib_path_list_flags_2_path_flags(flags),
790 : dpo);
791 27717 : vec_add1(path_list->fpl_paths, path_index);
792 :
793 : /*
794 : * we don't share path-lists. we can do PIC on them so why bother.
795 : */
796 27717 : path_list = fib_path_list_resolve(path_list);
797 :
798 27717 : return (path_list_index);
799 : }
800 :
801 : /*
802 : * return the index info the path-lists's vector of paths, of the matching path.
803 : * ~0 if not found
804 : */
805 : u32
806 0 : fib_path_list_find_rpath (fib_node_index_t path_list_index,
807 : const fib_route_path_t *rpath)
808 : {
809 : fib_path_list_t *path_list;
810 : u32 ii;
811 :
812 0 : path_list = fib_path_list_get(path_list_index);
813 :
814 0 : vec_foreach_index (ii, path_list->fpl_paths)
815 : {
816 0 : if (!fib_path_cmp_w_route_path(path_list->fpl_paths[ii], rpath))
817 : {
818 0 : return (ii);
819 : }
820 : }
821 0 : return (~0);
822 : }
823 :
824 :
825 : /*
826 : * fib_path_list_copy_and_path_add
827 : *
828 : * Create a copy of a path-list and append one more path to it.
829 : * The path-list returned could either have been newly created, or
830 : * can be a shared path-list from the data-base.
831 : */
832 : fib_node_index_t*
833 23514 : fib_path_list_paths_add (fib_node_index_t path_list_index,
834 : const fib_route_path_t *rpaths)
835 : {
836 : fib_node_index_t *new_path_indices, *path_index;
837 : const fib_route_path_t *rpath;
838 : fib_path_list_t *path_list;
839 : u32 ii;
840 :
841 : /*
842 : * alloc the new list before we retrieve the old one, lest
843 : * the alloc result in a realloc
844 : */
845 23514 : path_list = fib_path_list_get(path_list_index);
846 :
847 23514 : ASSERT(!(path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED));
848 :
849 23514 : FIB_PATH_LIST_DBG(path_list, "paths-add");
850 :
851 23514 : new_path_indices = NULL;
852 49663 : vec_validate_init_empty(new_path_indices,
853 : vec_len(rpaths) - 1,
854 : FIB_NODE_INDEX_INVALID);
855 :
856 58833 : vec_foreach (path_index, path_list->fpl_paths)
857 : {
858 : /*
859 : * don't add duplicate paths
860 : */
861 35319 : int found = 0;
862 :
863 71512 : vec_foreach_index(ii, rpaths)
864 : {
865 38203 : rpath = &rpaths[ii];
866 38203 : if (0 == fib_path_cmp_w_route_path(*path_index, rpath))
867 : {
868 2010 : found = 1;
869 2010 : break;
870 : }
871 : }
872 35319 : if (found)
873 : {
874 2010 : new_path_indices[ii] = *path_index;
875 : }
876 : }
877 :
878 : /*
879 : * new_path_indices array contains INVALID for each path not found
880 : * and something valid for matches
881 : */
882 49663 : vec_foreach_index (ii, new_path_indices)
883 : {
884 26149 : path_index = &new_path_indices[ii];
885 26149 : rpath = &rpaths[ii];
886 :
887 26149 : if (FIB_NODE_INDEX_INVALID == *path_index)
888 : {
889 24139 : *path_index = fib_path_create(path_list_index, rpath);
890 : /*
891 : * Add the new path - no sort, no sharing, no key..
892 : */
893 24139 : vec_add1(path_list->fpl_paths, *path_index);
894 :
895 : /*
896 : * no shared path list requested. resolve and use the one
897 : * just created.
898 : */
899 24139 : fib_path_resolve(*path_index);
900 : }
901 : }
902 :
903 23514 : FIB_PATH_LIST_DBG(path_list, "paths-added");
904 :
905 23514 : return (new_path_indices);
906 : }
907 :
908 : fib_node_index_t
909 291 : fib_path_list_copy_and_path_add (fib_node_index_t orig_path_list_index,
910 : fib_path_list_flags_t flags,
911 : const fib_route_path_t *rpaths)
912 : {
913 : fib_node_index_t new_path_index, *orig_path_index;
914 : fib_path_list_t *path_list, *orig_path_list;
915 : fib_node_index_t exist_path_list_index;
916 : fib_node_index_t path_list_index;
917 : const fib_route_path_t *rpath;
918 : fib_node_index_t pi;
919 :
920 : /*
921 : * alloc the new list before we retrieve the old one, lest
922 : * the alloc result in a realloc
923 : */
924 291 : path_list = fib_path_list_alloc(&path_list_index);
925 :
926 291 : orig_path_list = fib_path_list_get(orig_path_list_index);
927 :
928 291 : FIB_PATH_LIST_DBG(orig_path_list, "copy-add");
929 :
930 291 : flags = fib_path_list_flags_fixup(flags);
931 291 : path_list->fpl_flags = flags;
932 :
933 291 : vec_validate(path_list->fpl_paths,
934 : (vec_len(orig_path_list->fpl_paths) +
935 : vec_len(rpaths) - 1));
936 291 : pi = 0;
937 :
938 715 : vec_foreach(orig_path_index, orig_path_list->fpl_paths)
939 : {
940 : /*
941 : * copy the original paths over to the new list
942 : */
943 424 : path_list->fpl_paths[pi++] = fib_path_copy(*orig_path_index,
944 : path_list_index);
945 : }
946 582 : vec_foreach(rpath, rpaths)
947 : {
948 291 : int duplicate = 0;
949 :
950 291 : new_path_index = fib_path_create(path_list_index, rpath);
951 :
952 710 : vec_foreach(orig_path_index, orig_path_list->fpl_paths)
953 : {
954 : /*
955 : * don't add duplicate paths
956 : * In the unlikely event the path is a duplicate, then we'll
957 : * find a matching path-list later and this one will be toast.
958 : */
959 424 : if (0 == fib_path_cmp(new_path_index, *orig_path_index))
960 : {
961 5 : duplicate = 1;
962 5 : break;
963 : }
964 : }
965 291 : if (duplicate)
966 : {
967 5 : vec_set_len(path_list->fpl_paths, vec_len(path_list->fpl_paths) - 1);
968 5 : fib_path_destroy(new_path_index);
969 : }
970 : else
971 : {
972 286 : path_list->fpl_paths[pi++] = new_path_index;
973 : }
974 : }
975 :
976 : /*
977 : * we sort the paths since the key for the path-list is
978 : * the description of the paths it contains. The paths need to
979 : * be sorted else this description will differ.
980 : */
981 291 : vec_sort_with_function(path_list->fpl_paths, fib_path_cmp_for_sort);
982 :
983 291 : FIB_PATH_LIST_DBG(path_list, "path-added");
984 :
985 : /*
986 : * check for a matching path-list in the DB.
987 : * If we find one then we can return the existing one and destroy the
988 : * new one just created.
989 : */
990 291 : if (path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED)
991 : {
992 285 : exist_path_list_index = fib_path_list_db_find(path_list);
993 285 : if (FIB_NODE_INDEX_INVALID != exist_path_list_index)
994 : {
995 261 : fib_path_list_destroy(path_list);
996 :
997 261 : path_list_index = exist_path_list_index;
998 : }
999 : else
1000 : {
1001 : /*
1002 : * if there was not a matching path-list, then this
1003 : * new one will need inserting into the DB and resolving.
1004 : */
1005 24 : fib_path_list_db_insert(path_list_index);
1006 :
1007 24 : path_list = fib_path_list_resolve(path_list);
1008 : }
1009 : }
1010 : else
1011 : {
1012 : /*
1013 : * no shared path list requested. resolve and use the one
1014 : * just created.
1015 : */
1016 6 : path_list = fib_path_list_resolve(path_list);
1017 : }
1018 :
1019 291 : return (path_list_index);
1020 : }
1021 :
1022 : /*
1023 : * fib_path_list_paths_remove
1024 : */
1025 : fib_node_index_t*
1026 38894 : fib_path_list_paths_remove (fib_node_index_t path_list_index,
1027 : const fib_route_path_t *rpaths)
1028 : {
1029 : fib_node_index_t *match_path_indices;
1030 : fib_path_list_t *path_list;
1031 : i32 ii, jj;
1032 :
1033 38894 : path_list = fib_path_list_get(path_list_index);
1034 38894 : match_path_indices = NULL;
1035 77825 : vec_validate_init_empty(match_path_indices,
1036 : vec_len(rpaths) - 1,
1037 : FIB_NODE_INDEX_INVALID);
1038 :
1039 38894 : ASSERT(!(path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED));
1040 :
1041 38894 : FIB_PATH_LIST_DBG(path_list, "path-remove");
1042 :
1043 : /*
1044 : * the number of existing paths is likely to be larger than the
1045 : * number of paths being added.
1046 : * walk in reverse so the vec_del is ok
1047 : */
1048 119021 : vec_foreach_index_backwards(ii, path_list->fpl_paths)
1049 : {
1050 80127 : int found = ~0;
1051 :
1052 146976 : vec_foreach_index(jj, rpaths)
1053 : {
1054 80193 : if (0 == fib_path_cmp_w_route_path(path_list->fpl_paths[ii],
1055 80193 : &rpaths[jj]))
1056 : {
1057 13344 : found = jj;
1058 13344 : break;
1059 : }
1060 : }
1061 80127 : if (~0 != found)
1062 : {
1063 : fib_node_index_t match_path_index;
1064 : /*
1065 : * match - remove it
1066 : */
1067 13344 : match_path_index = path_list->fpl_paths[ii];
1068 13344 : vec_del1(path_list->fpl_paths, ii);
1069 13344 : fib_path_destroy(match_path_index);
1070 13344 : match_path_indices[jj] = match_path_index;
1071 : }
1072 : }
1073 :
1074 38894 : FIB_PATH_LIST_DBG(path_list, "paths-removed");
1075 :
1076 38894 : return (match_path_indices);
1077 : }
1078 :
1079 : /*
1080 : * fib_path_list_copy_and_path_remove
1081 : *
1082 : * Copy the path-list excluding the path passed.
1083 : * If the path is the last one, then the index reurned will be invalid.
1084 : * i.e. the path-list is toast.
1085 : */
1086 : fib_node_index_t
1087 5896 : fib_path_list_copy_and_path_remove (fib_node_index_t orig_path_list_index,
1088 : fib_path_list_flags_t flags,
1089 : const fib_route_path_t *rpaths)
1090 : {
1091 : fib_node_index_t *orig_path_index, path_list_index, tmp_path_index;
1092 : fib_path_list_t *path_list, *orig_path_list;
1093 : const fib_route_path_t *rpath;
1094 : fib_node_index_t pi;
1095 :
1096 5896 : path_list = fib_path_list_alloc(&path_list_index);
1097 :
1098 5896 : flags = fib_path_list_flags_fixup(flags);
1099 5896 : orig_path_list = fib_path_list_get(orig_path_list_index);
1100 :
1101 5896 : FIB_PATH_LIST_DBG(orig_path_list, "copy-remove");
1102 :
1103 5896 : path_list->fpl_flags = flags;
1104 : /*
1105 : * allocate as many paths as we might need in one go, rather than
1106 : * using vec_add to do a few at a time.
1107 : */
1108 5896 : vec_validate(path_list->fpl_paths,
1109 : vec_len(orig_path_list->fpl_paths) - 1);
1110 5896 : pi = 0;
1111 :
1112 : /*
1113 : * create a representation of the path to be removed, so it
1114 : * can be used as a comparison object during the copy.
1115 : */
1116 11818 : vec_foreach(orig_path_index, orig_path_list->fpl_paths)
1117 : {
1118 : /*
1119 : * copy the original paths over to the new list
1120 : */
1121 5922 : path_list->fpl_paths[pi++] = fib_path_copy(*orig_path_index,
1122 : path_list_index);
1123 : }
1124 11793 : vec_foreach(rpath, rpaths)
1125 : {
1126 5897 : int found = 0;
1127 5897 : tmp_path_index = fib_path_create(path_list_index, rpath);
1128 :
1129 5905 : vec_foreach_index(pi, path_list->fpl_paths)
1130 : {
1131 5905 : if (0 == fib_path_cmp(tmp_path_index, path_list->fpl_paths[pi]))
1132 : {
1133 5897 : found = 1;
1134 5897 : break;
1135 : }
1136 : }
1137 5897 : if (found)
1138 : {
1139 5897 : fib_path_destroy(path_list->fpl_paths[pi]);
1140 5897 : vec_del1(path_list->fpl_paths, pi);
1141 : }
1142 5897 : fib_path_destroy(tmp_path_index);
1143 : }
1144 :
1145 : /*
1146 : * if there are no paths, then the new path-list is aborted
1147 : */
1148 5896 : if (0 == vec_len(path_list->fpl_paths)) {
1149 5877 : FIB_PATH_LIST_DBG(path_list, "last-path-removed");
1150 :
1151 5877 : fib_path_list_destroy(path_list);
1152 :
1153 5877 : path_list_index = FIB_NODE_INDEX_INVALID;
1154 : } else {
1155 : /*
1156 : * we sort the paths since the key for the path-list is
1157 : * the description of the paths it contains. The paths need to
1158 : * be sorted else this description will differ.
1159 : */
1160 19 : vec_sort_with_function(path_list->fpl_paths, fib_path_cmp_for_sort);
1161 :
1162 : /*
1163 : * If a shared path list is requested, consult the DB for a match
1164 : */
1165 19 : if (path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED)
1166 : {
1167 : fib_node_index_t exist_path_list_index;
1168 :
1169 : /*
1170 : * check for a matching path-list in the DB.
1171 : * If we find one then we can return the existing one and destroy the
1172 : * new one just created.
1173 : */
1174 13 : exist_path_list_index = fib_path_list_db_find(path_list);
1175 13 : if (FIB_NODE_INDEX_INVALID != exist_path_list_index)
1176 : {
1177 3 : fib_path_list_destroy(path_list);
1178 :
1179 3 : path_list_index = exist_path_list_index;
1180 : }
1181 : else
1182 : {
1183 : /*
1184 : * if there was not a matching path-list, then this
1185 : * new one will need inserting into the DB and resolving.
1186 : */
1187 10 : fib_path_list_db_insert(path_list_index);
1188 :
1189 10 : path_list = fib_path_list_resolve(path_list);
1190 : }
1191 : }
1192 : else
1193 : {
1194 : /*
1195 : * no shared path list requested. resolve and use the one
1196 : * just created.
1197 : */
1198 6 : path_list = fib_path_list_resolve(path_list);
1199 : }
1200 : }
1201 :
1202 5896 : return (path_list_index);
1203 : }
1204 :
1205 : /*
1206 : * fib_path_list_contribute_forwarding
1207 : *
1208 : * Return the index of a load-balance that user of this path-list should
1209 : * use for forwarding
1210 : */
1211 : void
1212 2878 : fib_path_list_contribute_forwarding (fib_node_index_t path_list_index,
1213 : fib_forward_chain_type_t fct,
1214 : fib_path_list_fwd_flags_t flags,
1215 : dpo_id_t *dpo)
1216 : {
1217 : fib_path_list_t *path_list;
1218 :
1219 2878 : path_list = fib_path_list_get(path_list_index);
1220 :
1221 2878 : fib_path_list_mk_lb(path_list, fct, dpo, flags);
1222 :
1223 2878 : ASSERT(DPO_LOAD_BALANCE == dpo->dpoi_type);
1224 :
1225 : /*
1226 : * If there's only one bucket in the load-balance then we can
1227 : * squash it out.
1228 : */
1229 2878 : if ((1 == load_balance_n_buckets(dpo->dpoi_index)) &&
1230 2754 : (FIB_PATH_LIST_FWD_FLAG_COLLAPSE & flags))
1231 : {
1232 2754 : dpo_copy(dpo, load_balance_get_bucket(dpo->dpoi_index, 0));
1233 : }
1234 2878 : }
1235 :
1236 : /*
1237 : * fib_path_list_get_adj
1238 : *
1239 : * Return the index of a adjacency for the first path that user of this
1240 : * path-list should use for forwarding
1241 : */
1242 : adj_index_t
1243 5621 : fib_path_list_get_adj (fib_node_index_t path_list_index,
1244 : fib_forward_chain_type_t type)
1245 : {
1246 : fib_path_list_t *path_list;
1247 :
1248 5621 : path_list = fib_path_list_get(path_list_index);
1249 5621 : return (fib_path_get_adj(path_list->fpl_paths[0]));
1250 : }
1251 :
1252 : int
1253 87686 : fib_path_list_recursive_loop_detect (fib_node_index_t path_list_index,
1254 : fib_node_index_t **entry_indicies)
1255 : {
1256 : fib_node_index_t *path_index;
1257 : int is_looped, list_looped;
1258 : fib_path_list_t *path_list;
1259 :
1260 87686 : list_looped = 0;
1261 87686 : path_list = fib_path_list_get(path_list_index);
1262 :
1263 205300 : vec_foreach (path_index, path_list->fpl_paths)
1264 : {
1265 : fib_node_index_t *copy, **copy_ptr;
1266 :
1267 : /*
1268 : * we need a copy of the nodes visited so that when we add entries
1269 : * we explore on the nth path and a looped is detected, those entries
1270 : * are not again searched for n+1 path and so finding a loop that does
1271 : * not exist.
1272 : */
1273 117614 : copy = vec_dup(*entry_indicies);
1274 117614 : copy_ptr = ©
1275 :
1276 117614 : is_looped = fib_path_recursive_loop_detect(*path_index, copy_ptr);
1277 117614 : list_looped += is_looped;
1278 :
1279 117614 : vec_free(copy);
1280 : }
1281 :
1282 87686 : FIB_PATH_LIST_DBG(path_list, "loop-detect: eval:%d", list_looped);
1283 :
1284 87686 : if (list_looped)
1285 : {
1286 21 : path_list->fpl_flags |= FIB_PATH_LIST_FLAG_LOOPED;
1287 : }
1288 : else
1289 : {
1290 87665 : path_list->fpl_flags &= ~FIB_PATH_LIST_FLAG_LOOPED;
1291 : }
1292 :
1293 87686 : return (list_looped);
1294 : }
1295 :
1296 : u32
1297 122811 : fib_path_list_child_add (fib_node_index_t path_list_index,
1298 : fib_node_type_t child_type,
1299 : fib_node_index_t child_index)
1300 : {
1301 122811 : if (FIB_PATH_LIST_POPULAR - 1 == fib_node_get_n_children(FIB_NODE_TYPE_PATH_LIST,
1302 : path_list_index))
1303 : {
1304 : /*
1305 : * Set the popular flag on the path-list once we pass the magic
1306 : * threshold. then walk children to update.
1307 : * We don't undo this action. The rational being that the number
1308 : * of entries using this prefix is large enough such that it is a
1309 : * non-trival amount of effort to converge them. If we get into the
1310 : * situation where we are adding and removing entries such that we
1311 : * flip-flop over the threshold, then this non-trivial work is added
1312 : * to each of those routes adds/deletes - not a situation we want.
1313 : */
1314 11 : fib_node_back_walk_ctx_t ctx = {
1315 : .fnbw_reason = FIB_NODE_BW_REASON_FLAG_EVALUATE,
1316 : };
1317 : fib_path_list_t *path_list;
1318 :
1319 11 : path_list = fib_path_list_get(path_list_index);
1320 11 : path_list->fpl_flags |= FIB_PATH_LIST_FLAG_POPULAR;
1321 :
1322 11 : fib_walk_sync(FIB_NODE_TYPE_PATH_LIST, path_list_index, &ctx);
1323 : }
1324 :
1325 122811 : return (fib_node_child_add(FIB_NODE_TYPE_PATH_LIST,
1326 : path_list_index,
1327 : child_type,
1328 : child_index));
1329 : }
1330 :
1331 : void
1332 109258 : fib_path_list_child_remove (fib_node_index_t path_list_index,
1333 : u32 si)
1334 : {
1335 109258 : fib_node_child_remove(FIB_NODE_TYPE_PATH_LIST,
1336 : path_list_index,
1337 : si);
1338 109258 : }
1339 :
1340 : void
1341 85180 : fib_path_list_lock(fib_node_index_t path_list_index)
1342 : {
1343 : fib_path_list_t *path_list;
1344 :
1345 85180 : if (FIB_NODE_INDEX_INVALID != path_list_index)
1346 : {
1347 67454 : path_list = fib_path_list_get(path_list_index);
1348 :
1349 67454 : fib_node_lock(&path_list->fpl_node);
1350 : }
1351 85180 : }
1352 :
1353 : void
1354 77640 : fib_path_list_unlock (fib_node_index_t path_list_index)
1355 : {
1356 : fib_path_list_t *path_list;
1357 :
1358 77640 : if (FIB_NODE_INDEX_INVALID != path_list_index)
1359 : {
1360 53890 : path_list = fib_path_list_get(path_list_index);
1361 :
1362 53890 : fib_node_unlock(&path_list->fpl_node);
1363 : }
1364 77640 : }
1365 :
1366 : u32
1367 63 : fib_path_list_pool_size (void)
1368 : {
1369 63 : return (pool_elts(fib_path_list_pool));
1370 : }
1371 :
1372 : u32
1373 53 : fib_path_list_db_size (void)
1374 : {
1375 53 : return (hash_elts(fib_path_list_db));
1376 : }
1377 :
1378 : void
1379 193008 : fib_path_list_walk (fib_node_index_t path_list_index,
1380 : fib_path_list_walk_fn_t func,
1381 : void *ctx)
1382 : {
1383 : fib_node_index_t *path_index;
1384 : fib_path_list_t *path_list;
1385 :
1386 193008 : path_list = fib_path_list_get(path_list_index);
1387 :
1388 511502 : vec_foreach(path_index, path_list->fpl_paths)
1389 : {
1390 335017 : if (FIB_PATH_LIST_WALK_STOP == func(path_list_index,
1391 : *path_index,
1392 : ctx))
1393 16523 : break;
1394 : }
1395 193008 : }
1396 :
1397 : void
1398 217282 : fib_path_list_walk_w_ext (fib_node_index_t path_list_index,
1399 : const fib_path_ext_list_t *ext_list,
1400 : fib_path_list_walk_w_ext_fn_t func,
1401 : void *ctx)
1402 : {
1403 : fib_node_index_t *path_index;
1404 : fib_path_list_t *path_list;
1405 : fib_path_ext_t *path_ext;
1406 :
1407 217282 : path_list = fib_path_list_get(path_list_index);
1408 :
1409 453074 : vec_foreach(path_index, path_list->fpl_paths)
1410 : {
1411 235792 : path_ext = fib_path_ext_list_find_by_path_index(ext_list, *path_index);
1412 :
1413 235792 : if (FIB_PATH_LIST_WALK_STOP == func(path_list_index,
1414 : *path_index,
1415 : path_ext,
1416 : ctx))
1417 0 : break;
1418 : }
1419 217282 : }
1420 :
1421 : void
1422 575 : fib_path_list_module_init (void)
1423 : {
1424 575 : fib_node_register_type (FIB_NODE_TYPE_PATH_LIST, &fib_path_list_vft);
1425 :
1426 575 : fib_path_list_db = hash_create2 (/* elts */ 0,
1427 : /* user */ 0,
1428 : /* value_bytes */ sizeof (fib_node_index_t),
1429 : fib_path_list_db_hash_key_sum,
1430 : fib_path_list_db_hash_key_equal,
1431 : /* format pair/arg */
1432 : 0, 0);
1433 575 : fib_path_list_logger = vlib_log_register_class("fib", "path-list");
1434 575 : }
1435 :
1436 : static clib_error_t *
1437 3 : show_fib_path_list_command (vlib_main_t * vm,
1438 : unformat_input_t * input,
1439 : vlib_cli_command_t * cmd)
1440 : {
1441 : fib_path_list_t *path_list;
1442 : fib_node_index_t pli;
1443 :
1444 3 : if (unformat (input, "%d", &pli))
1445 : {
1446 : /*
1447 : * show one in detail
1448 : */
1449 2 : if (!pool_is_free_index(fib_path_list_pool, pli))
1450 : {
1451 1 : path_list = fib_path_list_get(pli);
1452 1 : u8 *s = fib_path_list_format(pli, NULL);
1453 1 : s = format(s, "children:");
1454 1 : s = fib_node_children_format(path_list->fpl_node.fn_children, s);
1455 1 : vlib_cli_output (vm, "%v", s);
1456 1 : vec_free(s);
1457 : }
1458 : else
1459 : {
1460 1 : vlib_cli_output (vm, "path list %d invalid", pli);
1461 : }
1462 : }
1463 : else
1464 : {
1465 : /*
1466 : * show all
1467 : */
1468 1 : vlib_cli_output (vm, "FIB Path Lists");
1469 14 : pool_foreach_index (pli, fib_path_list_pool)
1470 : {
1471 13 : vlib_cli_output (vm, "%U", format_fib_path_list, pli, 0);
1472 : }
1473 : }
1474 3 : return (NULL);
1475 : }
1476 :
1477 285289 : VLIB_CLI_COMMAND (show_fib_path_list, static) = {
1478 : .path = "show fib path-lists",
1479 : .function = show_fib_path_list_command,
1480 : .short_help = "show fib path-lists",
1481 : };
|
