FD.io VPP  v19.04.1-1-ge4a0f9f
Vector Packet Processing
fib_path_list.c
Go to the documentation of this file.
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>
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 
29 /**
30  * The magic number of child entries that make a path-list popular.
31  * There's a trade-off here between convergnece and forwarding speed.
32  * Popular path-lists generate load-balance maps for the entries that
33  * use them. If the map is present there is a switch path cost to indirect
34  * through the map - this indirection provides the fast convergence - so
35  * without the map convergence is slower.
36  */
37 #define FIB_PATH_LIST_POPULAR 64
38 
39 /**
40  * FIB path-list
41  * A representation of the list/set of path trough which a prefix is reachable
42  */
43 typedef struct fib_path_list_t_ {
44  /**
45  * A path-list is a node in the FIB graph.
46  */
48 
49  /**
50  * Flags on the path-list
51  */
53 
54  /**
55  * Vector of paths indicies for all configured paths.
56  * For shareable path-lists this list MUST not change.
57  */
59 
60  /**
61  * the RPF list calculated for this path list
62  */
64 
65  /**
66  * Hash table of paths. valid only with INDEXED flag
67  */
70 
71 /*
72  * Array of strings/names for the FIB sources
73  */
75 
76 /*
77  * The memory pool from which we allocate all the path-lists
78  */
80 
81 /*
82  * The data-base of shared path-lists
83  */
85 
86 /**
87  * the logger
88  */
90 
91 /*
92  * Debug macro
93  */
94 #define FIB_PATH_LIST_DBG(_pl, _fmt, _args...) \
95 { \
96  vlib_log_debug(fib_path_list_logger, \
97  "[%U]:" _fmt, \
98  format_fib_path_list, \
99  fib_path_list_get_index(_pl), 0, \
100  ##_args); \
101 }
102 
103 static fib_path_list_t *
105 {
106  return (pool_elt_at_index(fib_path_list_pool, index));
107 }
108 
109 static fib_node_t *
111 {
112  return ((fib_node_t*)fib_path_list_get(index));
113 }
114 
115 static fib_path_list_t*
117 {
119  return ((fib_path_list_t*)node);
120 }
121 
122 static fib_node_index_t
124 {
125  return (path_list - fib_path_list_pool);
126 }
127 
128 u8 *
129 format_fib_path_list (u8 * s, va_list * args)
130 {
131  fib_node_index_t *path_index, path_list_index;
133  fib_path_list_t *path_list;
134  u32 indent;
135 
136  path_list_index = va_arg (*args, fib_node_index_t);
137  indent = va_arg (*args, u32);
138  path_list = fib_path_list_get(path_list_index);
139 
140  s = format (s, "%Upath-list:[%d]",
141  format_white_space, indent,
142  fib_path_list_get_index(path_list));
143  s = format (s, " locks:%u", path_list->fpl_node.fn_locks);
144 
145  if (FIB_PATH_LIST_FLAG_NONE != path_list->fpl_flags)
146  {
147  s = format (s, " flags:");
149  {
150  if ((1<<attr) & path_list->fpl_flags)
151  {
152  s = format (s, "%s,", fib_path_list_attr_names[attr]);
153  }
154  }
155  }
156  s = format (s, " %U\n", format_fib_urpf_list, path_list->fpl_urpf);
157 
158  vec_foreach (path_index, path_list->fpl_paths)
159  {
160  s = format(s, "%U", format_fib_path, *path_index, indent+2,
162  s = format(s, "\n");
163  }
164 
165  return (s);
166 }
167 
168 u8 *
170  u8 * s)
171 {
172  return (format(s, "%U", format_fib_path_list, path_list_index, 4));
173 }
174 
175 static uword
177 {
178  uword old_path_list_hash, new_path_list_hash, path_hash;
179  fib_node_index_t *path_index;
180 
181  ASSERT(path_list);
182 
183  new_path_list_hash = old_path_list_hash = vec_len(path_list->fpl_paths);
184 
185  vec_foreach (path_index, path_list->fpl_paths)
186  {
187  path_hash = fib_path_hash(*path_index);
188 #if uword_bits == 64
189  hash_mix64(path_hash, old_path_list_hash, new_path_list_hash);
190 #else
191  hash_mix32(path_hash, old_path_list_hash, new_path_list_hash);
192 #endif
193  }
194 
195  return (new_path_list_hash);
196 }
197 
200 {
201  return 1 + 2*index;
202 }
203 
206 {
207  return key & 1;
208 }
209 
212 {
214  return key / 2;
215 }
216 
217 static fib_path_list_t*
219 {
220  fib_path_list_t *path_list;
221 
223  {
224  fib_node_index_t path_list_index;
225 
226  path_list_index = fib_path_list_db_hash_key_2_index(key);
227  path_list = fib_path_list_get(path_list_index);
228  }
229  else
230  {
231  path_list = uword_to_pointer (key, fib_path_list_t *);
232  }
233 
234  return (path_list);
235 }
236 
237 static uword
239  uword key)
240 {
241  fib_path_list_t *path_list;
242 
243  path_list = fib_path_list_db_get_from_hash_key(key);
244 
245  return (fib_path_list_hash(path_list));
246 }
247 
248 static uword
250  uword key1,
251  uword key2)
252 {
253  fib_path_list_t *path_list1, *path_list2;
254 
255  path_list1 = fib_path_list_db_get_from_hash_key(key1);
256  path_list2 = fib_path_list_db_get_from_hash_key(key2);
257 
258  return (fib_path_list_hash(path_list1) ==
259  fib_path_list_hash(path_list2));
260 }
261 
262 static fib_node_index_t
264 {
265  uword *p;
266 
267  p = hash_get(fib_path_list_db, path_list);
268 
269  if (NULL != p)
270  {
271  return p[0];
272  }
273 
274  return (FIB_NODE_INDEX_INVALID);
275 }
276 
277 static void
279 {
280  fib_path_list_t *path_list;
281 
282  path_list = fib_path_list_get(path_list_index);
283 
285 
287  fib_path_list_db_hash_key_from_index(path_list_index),
288  path_list_index);
289 
290  FIB_PATH_LIST_DBG(path_list, "DB-inserted");
291 }
292 
293 static void
295 {
296  fib_path_list_t *path_list;
297 
298  path_list = fib_path_list_get(path_list_index);
299 
301 
303  fib_path_list_db_hash_key_from_index(path_list_index));
304 
305  FIB_PATH_LIST_DBG(path_list, "DB-removed");
306 }
307 
308 static void
310 {
311  fib_node_index_t *path_index;
312 
313  FIB_PATH_LIST_DBG(path_list, "destroy");
314 
315  vec_foreach (path_index, path_list->fpl_paths)
316  {
317  fib_path_destroy(*path_index);
318  }
319 
320  vec_free(path_list->fpl_paths);
321  fib_urpf_list_unlock(path_list->fpl_urpf);
322 
323  fib_node_deinit(&path_list->fpl_node);
324  pool_put(fib_path_list_pool, path_list);
325 }
326 
327 static void
329 {
330  fib_path_list_t *path_list;
331 
332  path_list = fib_path_list_from_fib_node(node);
333 
334  FIB_PATH_LIST_DBG(path_list, "last-lock");
335 
336  if (path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED)
337  {
339  }
340  fib_path_list_destroy(path_list);
341 }
342 
345 {
347 
348  if (pl_flags & FIB_PATH_LIST_FWD_FLAG_STICKY)
349  {
350  lb_flags |= LOAD_BALANCE_ATTR_STICKY;
351  }
352  return (lb_flags);
353 }
354 
355 /*
356  * fib_path_mk_lb
357  *
358  * update the multipath adj this path-list will contribute to its
359  * children's forwarding.
360  */
361 static void
364  dpo_id_t *dpo,
366 {
368  fib_node_index_t *path_index;
369 
370  nhs = NULL;
371 
372  /*
373  * We gather the DPOs from resolved paths.
374  */
375  vec_foreach (path_index, path_list->fpl_paths)
376  {
377  if ((flags & FIB_PATH_LIST_FWD_FLAG_STICKY) ||
378  fib_path_is_resolved(*path_index))
379  {
380  nhs = fib_path_append_nh_for_multipath_hash(*path_index,
381  fct, nhs);
382  }
383  }
384 
385  /*
386  * Path-list load-balances, which if used, would be shared and hence
387  * never need a load-balance map.
388  */
389  dpo_set(dpo,
394  0 /* FIXME FLOW HASH */));
397 
398  FIB_PATH_LIST_DBG(path_list, "mk lb: %d", dpo->dpoi_index);
399 
400  vec_free(nhs);
401 }
402 
403 /**
404  * @brief [re]build the path list's uRPF list
405  */
406 static void
408 {
409  fib_node_index_t *path_index;
410 
411  /*
412  * ditch the old one. by iterating through all paths we are going
413  * to re-find all the adjs that were in the old one anyway. If we
414  * keep the old one, then the |sort|uniq requires more work.
415  * All users of the RPF list have their own lock, so we can release
416  * immediately.
417  */
418  fib_urpf_list_unlock(path_list->fpl_urpf);
419  path_list->fpl_urpf = fib_urpf_list_alloc_and_lock();
420 
421  vec_foreach (path_index, path_list->fpl_paths)
422  {
423  fib_path_contribute_urpf(*path_index, path_list->fpl_urpf);
424  }
425 
426  fib_urpf_list_bake(path_list->fpl_urpf);
427 }
428 
429 /**
430  * @brief Contribute (add) this path list's uRPF list. This allows the child
431  * to construct an aggregate list.
432  */
433 void
435  index_t urpf)
436 {
437  fib_path_list_t *path_list;
438 
439  path_list = fib_path_list_get(path_list_index);
440 
441  fib_urpf_list_combine(urpf, path_list->fpl_urpf);
442 }
443 
444 /**
445  * @brief Return the the child the RPF list pre-built for this path list
446  */
447 index_t
449 {
450  fib_path_list_t *path_list;
451 
452  path_list = fib_path_list_get(path_list_index);
453 
454  return (path_list->fpl_urpf);
455 }
456 
457 /*
458  * fib_path_list_back_walk
459  *
460  * Called from one of this path-list's paths to progate
461  * a back walk
462  */
463 void
466 {
467  fib_path_list_t *path_list;
468 
469  path_list = fib_path_list_get(path_list_index);
470 
471  fib_path_list_mk_urpf(path_list);
472 
473  FIB_PATH_LIST_DBG(path_list, "bw:%U",
475 
476  /*
477  * propagate the backwalk further
478  */
479  if (path_list->fpl_flags & FIB_PATH_LIST_FLAG_POPULAR)
480  {
481  /*
482  * many children. schedule a async walk
483  */
485  path_list_index,
487  ctx);
488  }
489  else
490  {
491  /*
492  * only a few children. continue the walk synchronously
493  */
494  fib_walk_sync(FIB_NODE_TYPE_PATH_LIST, path_list_index, ctx);
495  }
496 }
497 
498 /*
499  * fib_path_list_back_walk_notify
500  *
501  * A back walk has reach this path-list.
502  */
506 {
507  /*
508  * the path-list is not a direct child of any other node type
509  * paths, which do not change thier to-list-mapping, save the
510  * list they are a member of, and invoke the BW function directly.
511  */
512  ASSERT(0);
513 
515 }
516 
517 /*
518  * Display the path-list memory usage
519  */
520 static void
522 {
523  fib_show_memory_usage("Path-list",
524  pool_elts(fib_path_list_pool),
525  pool_len(fib_path_list_pool),
526  sizeof(fib_path_list_t));
528 }
529 
530 /*
531  * The FIB path-list's graph node virtual function table
532  */
533 static const fib_node_vft_t fib_path_list_vft = {
535  .fnv_last_lock = fib_path_list_last_lock_gone,
536  .fnv_back_walk = fib_path_list_back_walk_notify,
537  .fnv_mem_show = fib_path_list_memory_show,
538 };
539 
540 static inline fib_path_list_t *
542 {
543  fib_path_list_t *path_list;
544 
545  pool_get(fib_path_list_pool, path_list);
546  clib_memset(path_list, 0, sizeof(*path_list));
547 
548  fib_node_init(&path_list->fpl_node,
550  path_list->fpl_urpf = INDEX_INVALID;
551  path_list->fpl_paths = NULL;
552 
553  *path_list_index = fib_path_list_get_index(path_list);
554 
555  FIB_PATH_LIST_DBG(path_list, "alloc");
556 
557  return (path_list);
558 }
559 
560 static fib_path_list_t *
562 {
563  fib_node_index_t *path_index, *paths, path_list_index;
564 
566 
567  /*
568  * resolving a path-list is a recursive action. this means more path
569  * lists can be created during this call, and hence this path-list
570  * can be realloc'd. so we work with copies.
571  * this function is called only once per-path list, so its no great overhead.
572  */
573  path_list_index = fib_path_list_get_index(path_list);
574  paths = vec_dup(path_list->fpl_paths);
575 
576  vec_foreach (path_index, paths)
577  {
578  fib_path_resolve(*path_index);
579  }
580 
581  vec_free(paths);
582  path_list = fib_path_list_get(path_list_index);
583 
584  FIB_PATH_LIST_DBG(path_list, "resovled");
585 
586  if (!(path_list->fpl_flags & FIB_PATH_LIST_FLAG_NO_URPF))
587  {
588  fib_path_list_mk_urpf(path_list);
589  }
590  return (path_list);
591 }
592 
593 u32
595 {
596  fib_path_list_t *path_list;
597 
598  if (FIB_NODE_INDEX_INVALID == path_list_index)
599  {
600  return (0);
601  }
602 
603  path_list = fib_path_list_get(path_list_index);
604 
605  return (vec_len(path_list->fpl_paths));
606 }
607 
608 
609 u32
611 {
612  fib_node_index_t *path_index;
613  fib_path_list_t *path_list;
615 
616  path_list = fib_path_list_get(path_list_index);
617 
618  sw_if_index = ~0;
619  vec_foreach (path_index, path_list->fpl_paths)
620  {
621  sw_if_index = fib_path_get_resolving_interface(*path_index);
622  if (~0 != sw_if_index)
623  {
624  return (sw_if_index);
625  }
626  }
627 
628  return (sw_if_index);
629 }
630 
633 {
634  fib_path_list_t *path_list;
635 
636  path_list = fib_path_list_get(path_list_index);
637 
638  /*
639  * we don't support a mix of path protocols, so we can return the proto
640  * of the first
641  */
642  return (fib_path_get_proto(path_list->fpl_paths[0]));
643 }
644 
645 int
647 {
648  fib_path_list_t *path_list;
649 
650  path_list = fib_path_list_get(path_list_index);
651 
652  return (path_list->fpl_flags & FIB_PATH_LIST_FLAG_LOOPED);
653 }
654 
655 int
657 {
658  fib_path_list_t *path_list;
659 
660  path_list = fib_path_list_get(path_list_index);
661 
662  return (path_list->fpl_flags & FIB_PATH_LIST_FLAG_POPULAR);
663 }
664 
667 {
668  /*
669  * we do no share drop nor exclusive path-lists
670  */
671  if (flags & FIB_PATH_LIST_FLAG_DROP ||
673  {
674  flags &= ~FIB_PATH_LIST_FLAG_SHARED;
675  }
676 
677  return (flags);
678 }
679 
682  const fib_route_path_t *rpaths)
683 {
684  fib_node_index_t path_list_index, old_path_list_index;
685  fib_path_list_t *path_list;
686  int i;
687 
688  flags = fib_path_list_flags_fixup(flags);
689  path_list = fib_path_list_alloc(&path_list_index);
690  path_list->fpl_flags = flags;
691 
692  if (NULL != rpaths)
693  {
694  vec_foreach_index(i, rpaths)
695  {
696  vec_add1(path_list->fpl_paths,
697  fib_path_create(path_list_index,
698  &rpaths[i]));
699  }
700  /*
701  * we sort the paths since the key for the path-list is
702  * the description of the paths it contains. The paths need to
703  * be sorted else this description will differ.
704  */
705  if (vec_len(path_list->fpl_paths) > 1)
706  {
709  }
710  }
711 
712  /*
713  * If a shared path list is requested, consult the DB for a match
714  */
715  if (flags & FIB_PATH_LIST_FLAG_SHARED)
716  {
717  /*
718  * check for a matching path-list in the DB.
719  * If we find one then we can return the existing one and destroy the
720  * new one just created.
721  */
722  old_path_list_index = fib_path_list_db_find(path_list);
723  if (FIB_NODE_INDEX_INVALID != old_path_list_index)
724  {
725  fib_path_list_destroy(path_list);
726 
727  path_list_index = old_path_list_index;
728  }
729  else
730  {
731  /*
732  * if there was not a matching path-list, then this
733  * new one will need inserting into the DB and resolving.
734  */
735  fib_path_list_db_insert(path_list_index);
736  path_list = fib_path_list_resolve(path_list);
737  }
738  }
739  else
740  {
741  /*
742  * no shared path list requested. resolve and use the one
743  * just created.
744  */
745  path_list = fib_path_list_resolve(path_list);
746  }
747 
748  return (path_list_index);
749 }
750 
753 {
755 
756  if (plf & FIB_PATH_LIST_FLAG_DROP)
757  {
759  }
761  {
763  }
764  if (plf & FIB_PATH_LIST_FLAG_LOCAL)
765  {
767  }
768 
769  return (pf);
770 }
771 
775  const dpo_id_t *dpo)
776 {
777  fib_node_index_t path_index, path_list_index;
778  fib_path_list_t *path_list;
779 
780  path_list = fib_path_list_alloc(&path_list_index);
781  path_list->fpl_flags = flags;
782 
783  path_index =
784  fib_path_create_special(path_list_index,
785  nh_proto,
787  dpo);
788  vec_add1(path_list->fpl_paths, path_index);
789 
790  /*
791  * we don't share path-lists. we can do PIC on them so why bother.
792  */
793  path_list = fib_path_list_resolve(path_list);
794 
795  return (path_list_index);
796 }
797 
798 /*
799  * return the index info the path-lists's vector of paths, of the matching path.
800  * ~0 if not found
801  */
802 u32
804  const fib_route_path_t *rpath)
805 {
806  fib_path_list_t *path_list;
807  u32 ii;
808 
809  path_list = fib_path_list_get(path_list_index);
810 
811  vec_foreach_index (ii, path_list->fpl_paths)
812  {
813  if (!fib_path_cmp_w_route_path(path_list->fpl_paths[ii], rpath))
814  {
815  return (ii);
816  }
817  }
818  return (~0);
819 }
820 
821 
822 /*
823  * fib_path_list_copy_and_path_add
824  *
825  * Create a copy of a path-list and append one more path to it.
826  * The path-list returned could either have been newly created, or
827  * can be a shared path-list from the data-base.
828  */
831  const fib_route_path_t *rpaths)
832 {
833  fib_node_index_t new_path_index, *orig_path_index;
834  fib_path_list_t *path_list;
835 
836  /*
837  * alloc the new list before we retrieve the old one, lest
838  * the alloc result in a realloc
839  */
840  path_list = fib_path_list_get(path_list_index);
841 
842  ASSERT(1 == vec_len(rpaths));
843  ASSERT(!(path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED));
844 
845  FIB_PATH_LIST_DBG(path_list, "path-add");
846 
847  new_path_index = fib_path_create(path_list_index,
848  rpaths);
849 
850  vec_foreach (orig_path_index, path_list->fpl_paths)
851  {
852  /*
853  * don't add duplicate paths
854  */
855  if (0 == fib_path_cmp(new_path_index, *orig_path_index))
856  {
857  fib_path_destroy(new_path_index);
858  return (*orig_path_index);
859  }
860  }
861 
862  /*
863  * Add the new path - no sort, no sharing, no key..
864  */
865  vec_add1(path_list->fpl_paths, new_path_index);
866 
867  FIB_PATH_LIST_DBG(path_list, "path-added");
868 
869  /*
870  * no shared path list requested. resolve and use the one
871  * just created.
872  */
873  fib_path_resolve(new_path_index);
874 
875  return (new_path_index);
876 }
877 
881  const fib_route_path_t *rpaths)
882 {
883  fib_node_index_t path_index, new_path_index, *orig_path_index;
884  fib_path_list_t *path_list, *orig_path_list;
885  fib_node_index_t exist_path_list_index;
886  fib_node_index_t path_list_index;
887  fib_node_index_t pi;
888 
889  ASSERT(1 == vec_len(rpaths));
890 
891  /*
892  * alloc the new list before we retrieve the old one, lest
893  * the alloc result in a realloc
894  */
895  path_list = fib_path_list_alloc(&path_list_index);
896 
897  orig_path_list = fib_path_list_get(orig_path_list_index);
898 
899  FIB_PATH_LIST_DBG(orig_path_list, "copy-add");
900 
901  flags = fib_path_list_flags_fixup(flags);
902  path_list->fpl_flags = flags;
903 
904  vec_validate(path_list->fpl_paths, vec_len(orig_path_list->fpl_paths));
905  pi = 0;
906 
907  new_path_index = fib_path_create(path_list_index,
908  rpaths);
909 
910  vec_foreach (orig_path_index, orig_path_list->fpl_paths)
911  {
912  /*
913  * don't add duplicate paths
914  * In the unlikely event the path is a duplicate, then we'll
915  * find a matching path-list later and this one will be toast.
916  */
917  if (0 != fib_path_cmp(new_path_index, *orig_path_index))
918  {
919  path_index = fib_path_copy(*orig_path_index, path_list_index);
920  path_list->fpl_paths[pi++] = path_index;
921  }
922  else
923  {
924  _vec_len(path_list->fpl_paths) = vec_len(orig_path_list->fpl_paths);
925  }
926  }
927 
928  path_list->fpl_paths[pi] = new_path_index;
929 
930  /*
931  * we sort the paths since the key for the path-list is
932  * the description of the paths it contains. The paths need to
933  * be sorted else this description will differ.
934  */
936 
937  FIB_PATH_LIST_DBG(path_list, "path-added");
938 
939  /*
940  * check for a matching path-list in the DB.
941  * If we find one then we can return the existing one and destroy the
942  * new one just created.
943  */
944  if (path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED)
945  {
946  exist_path_list_index = fib_path_list_db_find(path_list);
947  if (FIB_NODE_INDEX_INVALID != exist_path_list_index)
948  {
949  fib_path_list_destroy(path_list);
950 
951  path_list_index = exist_path_list_index;
952  }
953  else
954  {
955  /*
956  * if there was not a matching path-list, then this
957  * new one will need inserting into the DB and resolving.
958  */
959  fib_path_list_db_insert(path_list_index);
960 
961  path_list = fib_path_list_resolve(path_list);
962  }
963  }
964  else
965  {
966  /*
967  * no shared path list requested. resolve and use the one
968  * just created.
969  */
970  path_list = fib_path_list_resolve(path_list);
971  }
972 
973  return (path_list_index);
974 }
975 
976 /*
977  * fib_path_list_path_remove
978  */
981  const fib_route_path_t *rpaths)
982 {
983  fib_node_index_t match_path_index, tmp_path_index;
984  fib_path_list_t *path_list;
985  fib_node_index_t pi;
986 
987  path_list = fib_path_list_get(path_list_index);
988 
989  ASSERT(1 == vec_len(rpaths));
990  ASSERT(!(path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED));
991 
992  FIB_PATH_LIST_DBG(path_list, "path-remove");
993 
994  /*
995  * create a representation of the path to be removed, so it
996  * can be used as a comparison object during the copy.
997  */
998  tmp_path_index = fib_path_create(path_list_index,
999  rpaths);
1000  match_path_index = FIB_NODE_INDEX_INVALID;
1001 
1002  vec_foreach_index (pi, path_list->fpl_paths)
1003  {
1004  if (0 == fib_path_cmp(tmp_path_index,
1005  path_list->fpl_paths[pi]))
1006  {
1007  /*
1008  * match - remove it
1009  */
1010  match_path_index = path_list->fpl_paths[pi];
1011  fib_path_destroy(match_path_index);
1012  vec_del1(path_list->fpl_paths, pi);
1013  }
1014  }
1015 
1016  /*
1017  * done with the temporary now
1018  */
1019  fib_path_destroy(tmp_path_index);
1020 
1021  return (match_path_index);
1022 }
1023 
1024 /*
1025  * fib_path_list_copy_and_path_remove
1026  *
1027  * Copy the path-list excluding the path passed.
1028  * If the path is the last one, then the index reurned will be invalid.
1029  * i.e. the path-list is toast.
1030  */
1034  const fib_route_path_t *rpath)
1035 {
1036  fib_node_index_t path_index, *orig_path_index, path_list_index, tmp_path_index;
1037  fib_path_list_t *path_list, *orig_path_list;
1038  fib_node_index_t pi;
1039 
1040  path_list = fib_path_list_alloc(&path_list_index);
1041 
1042  flags = fib_path_list_flags_fixup(flags);
1043  orig_path_list = fib_path_list_get(orig_path_list_index);
1044 
1045  FIB_PATH_LIST_DBG(orig_path_list, "copy-remove");
1046 
1047  path_list->fpl_flags = flags;
1048  /*
1049  * allocate as many paths as we might need in one go, rather than
1050  * using vec_add to do a few at a time.
1051  */
1052  if (vec_len(orig_path_list->fpl_paths) > 1)
1053  {
1054  vec_validate(path_list->fpl_paths, vec_len(orig_path_list->fpl_paths) - 2);
1055  }
1056  pi = 0;
1057 
1058  /*
1059  * create a representation of the path to be removed, so it
1060  * can be used as a comparison object during the copy.
1061  */
1062  tmp_path_index = fib_path_create(path_list_index, rpath);
1063 
1064  vec_foreach (orig_path_index, orig_path_list->fpl_paths)
1065  {
1066  if (0 != fib_path_cmp(tmp_path_index, *orig_path_index)) {
1067  path_index = fib_path_copy(*orig_path_index, path_list_index);
1068  if (pi < vec_len(path_list->fpl_paths))
1069  {
1070  path_list->fpl_paths[pi++] = path_index;
1071  }
1072  else
1073  {
1074  /*
1075  * this is the unlikely case that the path being
1076  * removed does not match one in the path-list, so
1077  * we end up with as many paths as we started with.
1078  * the paths vector was sized above with the expectation
1079  * that we would have 1 less.
1080  */
1081  vec_add1(path_list->fpl_paths, path_index);
1082  }
1083  }
1084  }
1085 
1086  /*
1087  * done with the temporary now
1088  */
1089  fib_path_destroy(tmp_path_index);
1090 
1091  /*
1092  * if there are no paths, then the new path-list is aborted
1093  */
1094  if (0 == vec_len(path_list->fpl_paths)) {
1095  FIB_PATH_LIST_DBG(path_list, "last-path-removed");
1096 
1097  fib_path_list_destroy(path_list);
1098 
1099  path_list_index = FIB_NODE_INDEX_INVALID;
1100  } else {
1101  /*
1102  * we sort the paths since the key for the path-list is
1103  * the description of the paths it contains. The paths need to
1104  * be sorted else this description will differ.
1105  */
1107 
1108  /*
1109  * If a shared path list is requested, consult the DB for a match
1110  */
1111  if (path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED)
1112  {
1113  fib_node_index_t exist_path_list_index;
1114 
1115  /*
1116  * check for a matching path-list in the DB.
1117  * If we find one then we can return the existing one and destroy the
1118  * new one just created.
1119  */
1120  exist_path_list_index = fib_path_list_db_find(path_list);
1121  if (FIB_NODE_INDEX_INVALID != exist_path_list_index)
1122  {
1123  fib_path_list_destroy(path_list);
1124 
1125  path_list_index = exist_path_list_index;
1126  }
1127  else
1128  {
1129  /*
1130  * if there was not a matching path-list, then this
1131  * new one will need inserting into the DB and resolving.
1132  */
1133  fib_path_list_db_insert(path_list_index);
1134 
1135  path_list = fib_path_list_resolve(path_list);
1136  }
1137  }
1138  else
1139  {
1140  /*
1141  * no shared path list requested. resolve and use the one
1142  * just created.
1143  */
1144  path_list = fib_path_list_resolve(path_list);
1145  }
1146  }
1147 
1148  return (path_list_index);
1149 }
1150 
1151 /*
1152  * fib_path_list_contribute_forwarding
1153  *
1154  * Return the index of a load-balance that user of this path-list should
1155  * use for forwarding
1156  */
1157 void
1161  dpo_id_t *dpo)
1162 {
1163  fib_path_list_t *path_list;
1164 
1165  path_list = fib_path_list_get(path_list_index);
1166 
1167  fib_path_list_mk_lb(path_list, fct, dpo, flags);
1168 
1170 
1171  /*
1172  * If there's only one bucket in the load-balance then we can
1173  * squash it out.
1174  */
1175  if ((1 == load_balance_n_buckets(dpo->dpoi_index)) &&
1177  {
1179  }
1180 }
1181 
1182 /*
1183  * fib_path_list_get_adj
1184  *
1185  * Return the index of a adjacency for the first path that user of this
1186  * path-list should use for forwarding
1187  */
1191 {
1192  fib_path_list_t *path_list;
1193 
1194  path_list = fib_path_list_get(path_list_index);
1195  return (fib_path_get_adj(path_list->fpl_paths[0]));
1196 }
1197 
1198 int
1200  fib_node_index_t **entry_indicies)
1201 {
1202  fib_node_index_t *path_index;
1203  int is_looped, list_looped;
1204  fib_path_list_t *path_list;
1205 
1206  list_looped = 0;
1207  path_list = fib_path_list_get(path_list_index);
1208 
1209  vec_foreach (path_index, path_list->fpl_paths)
1210  {
1211  fib_node_index_t *copy, **copy_ptr;
1212 
1213  /*
1214  * we need a copy of the nodes visited so that when we add entries
1215  * we explore on the nth path and a looped is detected, those entries
1216  * are not again searched for n+1 path and so finding a loop that does
1217  * not exist.
1218  */
1219  copy = vec_dup(*entry_indicies);
1220  copy_ptr = &copy;
1221 
1222  is_looped = fib_path_recursive_loop_detect(*path_index, copy_ptr);
1223  list_looped += is_looped;
1224 
1225  vec_free(copy);
1226  }
1227 
1228  FIB_PATH_LIST_DBG(path_list, "loop-detect: eval:%d", list_looped);
1229 
1230  if (list_looped)
1231  {
1232  path_list->fpl_flags |= FIB_PATH_LIST_FLAG_LOOPED;
1233  }
1234  else
1235  {
1236  path_list->fpl_flags &= ~FIB_PATH_LIST_FLAG_LOOPED;
1237  }
1238 
1239  return (list_looped);
1240 }
1241 
1242 u32
1244  fib_node_type_t child_type,
1245  fib_node_index_t child_index)
1246 {
1247  u32 sibling;
1248 
1250  path_list_index,
1251  child_type,
1252  child_index);
1253 
1255  path_list_index))
1256  {
1257  /*
1258  * Set the popular flag on the path-list once we pass the magic
1259  * threshold. then walk children to update.
1260  * We don't undo this action. The rational being that the number
1261  * of entries using this prefix is large enough such that it is a
1262  * non-trival amount of effort to converge them. If we get into the
1263  * situation where we are adding and removing entries such that we
1264  * flip-flop over the threshold, then this non-trivial work is added
1265  * to each of those routes adds/deletes - not a situation we want.
1266  */
1268  .fnbw_reason = FIB_NODE_BW_REASON_FLAG_EVALUATE,
1269  };
1270  fib_path_list_t *path_list;
1271 
1272  path_list = fib_path_list_get(path_list_index);
1273  path_list->fpl_flags |= FIB_PATH_LIST_FLAG_POPULAR;
1274 
1275  fib_walk_sync(FIB_NODE_TYPE_PATH_LIST, path_list_index, &ctx);
1276  }
1277 
1278  return (sibling);
1279 }
1280 
1281 void
1283  u32 si)
1284 {
1286  path_list_index,
1287  si);
1288 }
1289 
1290 void
1292 {
1293  fib_path_list_t *path_list;
1294 
1295  if (FIB_NODE_INDEX_INVALID != path_list_index)
1296  {
1297  path_list = fib_path_list_get(path_list_index);
1298 
1299  fib_node_lock(&path_list->fpl_node);
1300  }
1301 }
1302 
1303 void
1305 {
1306  fib_path_list_t *path_list;
1307 
1308  if (FIB_NODE_INDEX_INVALID != path_list_index)
1309  {
1310  path_list = fib_path_list_get(path_list_index);
1311 
1312  fib_node_unlock(&path_list->fpl_node);
1313  }
1314 }
1315 
1316 u32
1318 {
1319  return (pool_elts(fib_path_list_pool));
1320 }
1321 
1322 u32
1324 {
1325  return (hash_elts(fib_path_list_db));
1326 }
1327 
1328 void
1331  void *ctx)
1332 {
1333  fib_node_index_t *path_index;
1334  fib_path_list_t *path_list;
1335 
1336  path_list = fib_path_list_get(path_list_index);
1337 
1338  vec_foreach(path_index, path_list->fpl_paths)
1339  {
1340  if (FIB_PATH_LIST_WALK_STOP == func(path_list_index,
1341  *path_index,
1342  ctx))
1343  break;
1344  }
1345 }
1346 
1347 void
1349  const fib_path_ext_list_t *ext_list,
1351  void *ctx)
1352 {
1353  fib_node_index_t *path_index;
1354  fib_path_list_t *path_list;
1355  fib_path_ext_t *path_ext;
1356 
1357  path_list = fib_path_list_get(path_list_index);
1358 
1359  vec_foreach(path_index, path_list->fpl_paths)
1360  {
1361  path_ext = fib_path_ext_list_find_by_path_index(ext_list, *path_index);
1362 
1363  if (FIB_PATH_LIST_WALK_STOP == func(path_list_index,
1364  *path_index,
1365  path_ext,
1366  ctx))
1367  break;
1368  }
1369 }
1370 
1371 void
1373 {
1374  fib_node_register_type (FIB_NODE_TYPE_PATH_LIST, &fib_path_list_vft);
1375 
1376  fib_path_list_db = hash_create2 (/* elts */ 0,
1377  /* user */ 0,
1378  /* value_bytes */ sizeof (fib_node_index_t),
1381  /* format pair/arg */
1382  0, 0);
1383  fib_path_list_logger = vlib_log_register_class("fib", "path-list");
1384 }
1385 
1386 static clib_error_t *
1388  unformat_input_t * input,
1389  vlib_cli_command_t * cmd)
1390 {
1391  fib_path_list_t *path_list;
1392  fib_node_index_t pli;
1393 
1394  if (unformat (input, "%d", &pli))
1395  {
1396  /*
1397  * show one in detail
1398  */
1399  if (!pool_is_free_index(fib_path_list_pool, pli))
1400  {
1401  path_list = fib_path_list_get(pli);
1402  u8 *s = fib_path_list_format(pli, NULL);
1403  s = format(s, "children:");
1404  s = fib_node_children_format(path_list->fpl_node.fn_children, s);
1405  vlib_cli_output (vm, "%s", s);
1406  vec_free(s);
1407  }
1408  else
1409  {
1410  vlib_cli_output (vm, "path list %d invalid", pli);
1411  }
1412  }
1413  else
1414  {
1415  /*
1416  * show all
1417  */
1418  vlib_cli_output (vm, "FIB Path Lists");
1419  pool_foreach_index (pli, fib_path_list_pool,
1420  ({
1421  vlib_cli_output (vm, "%U", format_fib_path_list, pli, 0);
1422  }));
1423  }
1424  return (NULL);
1425 }
1426 
1427 VLIB_CLI_COMMAND (show_fib_path_list, static) = {
1428  .path = "show fib path-lists",
1429  .function = show_fib_path_list_command,
1430  .short_help = "show fib path-lists",
1431 };
vlib_log_class_t vlib_log_register_class(char *class, char *subclass)
Definition: log.c:227
#define vec_validate(V, I)
Make sure vector is long enough for given index (no header, unspecified alignment) ...
Definition: vec.h:439
u32 sw_if_index
Definition: ipsec_gre.api:37
int fib_path_is_resolved(fib_node_index_t path_index)
Definition: fib_path.c:2604
static fib_node_index_t fib_path_list_db_find(fib_path_list_t *path_list)
static void fib_path_list_db_remove(fib_node_index_t path_list_index)
static clib_error_t * show_fib_path_list_command(vlib_main_t *vm, unformat_input_t *input, vlib_cli_command_t *cmd)
int fib_path_resolve(fib_node_index_t path_index)
Definition: fib_path.c:1859
void fib_path_list_module_init(void)
#define vec_foreach_index(var, v)
Iterate over vector indices.
u32 fib_path_list_find_rpath(fib_node_index_t path_list_index, const fib_route_path_t *rpath)
#define hash_set(h, key, value)
Definition: hash.h:255
u32 flags
Definition: vhost_user.h:115
uword fib_path_hash(fib_node_index_t path_index)
Definition: fib_path.c:1497
fib_node_index_t fib_path_list_copy_and_path_remove(fib_node_index_t orig_path_list_index, fib_path_list_flags_t flags, const fib_route_path_t *rpath)
#define FIB_PATH_LIST_POPULAR
The magic number of child entries that make a path-list popular.
Definition: fib_path_list.c:37
void fib_path_list_child_remove(fib_node_index_t path_list_index, u32 si)
u16 load_balance_n_buckets(index_t lbi)
Definition: load_balance.c:267
#define hash_unset(h, key)
Definition: hash.h:261
void fib_path_contribute_urpf(fib_node_index_t path_index, index_t urpf)
Contribute the path&#39;s adjacency to the list passed.
Definition: fib_path.c:2217
A representation of a path as described by a route producer.
Definition: fib_types.h:470
static uword fib_path_list_db_hash_key_equal(hash_t *h, uword key1, uword key2)
adj_index_t fib_path_list_get_adj(fib_node_index_t path_list_index, fib_forward_chain_type_t type)
void fib_path_list_contribute_urpf(fib_node_index_t path_list_index, index_t urpf)
Contribute (add) this path list&#39;s uRPF list.
int fib_path_cmp(fib_node_index_t pi1, fib_node_index_t pi2)
Definition: fib_path.c:1637
void fib_node_init(fib_node_t *node, fib_node_type_t type)
Definition: fib_node.c:185
u32 fib_path_list_get_resolving_interface(fib_node_index_t path_list_index)
u8 * format_fib_path_list(u8 *s, va_list *args)
#define NULL
Definition: clib.h:58
enum fib_node_back_walk_rc_t_ fib_node_back_walk_rc_t
Return code from a back walk function.
fib_node_index_t fib_path_list_create_special(dpo_proto_t nh_proto, fib_path_list_flags_t flags, const dpo_id_t *dpo)
fib_node_index_t * fpl_paths
Vector of paths indicies for all configured paths.
Definition: fib_path_list.c:58
void fib_urpf_list_show_mem(void)
dpo_proto_t fib_forw_chain_type_to_dpo_proto(fib_forward_chain_type_t fct)
Convert from a chain type to the DPO proto it will install.
Definition: fib_types.c:410
void dpo_copy(dpo_id_t *dst, const dpo_id_t *src)
atomic copy a data-plane object.
Definition: dpo.c:261
u32 index_t
A Data-Path Object is an object that represents actions that are applied to packets are they are swit...
Definition: dpo.h:41
#define vec_add1(V, E)
Add 1 element to end of vector (unspecified alignment).
Definition: vec.h:522
static uword * fib_path_list_db
Definition: fib_path_list.c:84
int i
void fib_path_list_walk(fib_node_index_t path_list_index, fib_path_list_walk_fn_t func, void *ctx)
clib_memset(h->entries, 0, sizeof(h->entries[0])*entries)
void fib_node_deinit(fib_node_t *node)
Definition: fib_node.c:197
void fib_walk_async(fib_node_type_t parent_type, fib_node_index_t parent_index, fib_walk_priority_t prio, fib_node_back_walk_ctx_t *ctx)
Definition: fib_walk.c:688
u8 * format(u8 *s, const char *fmt,...)
Definition: format.c:424
static uword fib_path_list_db_hash_key_from_index(uword index)
#define FOR_EACH_PATH_LIST_ATTRIBUTE(_item)
#define pool_get(P, E)
Allocate an object E from a pool P (unspecified alignment).
Definition: pool.h:236
int fib_path_cmp_for_sort(void *v1, void *v2)
Definition: fib_path.c:1610
u32 fib_path_list_child_add(fib_node_index_t path_list_index, fib_node_type_t child_type, fib_node_index_t child_index)
static void fib_path_list_mk_urpf(fib_path_list_t *path_list)
[re]build the path list&#39;s uRPF list
unsigned char u8
Definition: types.h:56
#define pool_len(p)
Number of elements in pool vector.
Definition: pool.h:140
FIB path-list A representation of the list/set of path trough which a prefix is reachable.
Definition: fib_path_list.c:43
static fib_path_list_t * fib_path_list_pool
Definition: fib_path_list.c:79
load_balance_path_t * fib_path_append_nh_for_multipath_hash(fib_node_index_t path_index, fib_forward_chain_type_t fct, load_balance_path_t *hash_key)
Definition: fib_path.c:2543
u32 fib_node_child_add(fib_node_type_t parent_type, fib_node_index_t parent_index, fib_node_type_t type, fib_node_index_t index)
Definition: fib_node.c:98
static const char * fib_path_list_attr_names[]
Definition: fib_path_list.c:74
void fib_node_register_type(fib_node_type_t type, const fib_node_vft_t *vft)
fib_node_register_type
Definition: fib_node.c:60
index_t load_balance_create(u32 n_buckets, dpo_proto_t lb_proto, flow_hash_config_t fhc)
Definition: load_balance.c:217
fib_node_t fpl_node
A path-list is a node in the FIB graph.
Definition: fib_path_list.c:47
u32 vlib_log_class_t
Definition: vlib.h:50
static uword fib_path_list_db_hash_key_is_index(uword key)
#define always_inline
Definition: clib.h:98
void fib_walk_sync(fib_node_type_t parent_type, fib_node_index_t parent_index, fib_node_back_walk_ctx_t *ctx)
Back walk all the children of a FIB node.
Definition: fib_walk.c:745
index_t fib_urpf_list_alloc_and_lock(void)
Definition: fib_urpf_list.c:55
u8 * format_white_space(u8 *s, va_list *va)
Definition: std-formats.c:113
fib_node_index_t fib_path_copy(fib_node_index_t path_index, fib_node_index_t path_list_index)
Definition: fib_path.c:1443
static void fib_path_list_destroy(fib_path_list_t *path_list)
void fib_show_memory_usage(const char *name, u32 in_use_elts, u32 allocd_elts, size_t size_elt)
Show the memory usage for a type.
Definition: fib_node.c:220
static uword fib_path_list_hash(fib_path_list_t *path_list)
void load_balance_multipath_update(const dpo_id_t *dpo, const load_balance_path_t *raw_nhs, load_balance_flags_t flags)
Definition: load_balance.c:580
unsigned int u32
Definition: types.h:88
enum dpo_proto_t_ dpo_proto_t
Data path protocol.
fib_path_ext_t * fib_path_ext_list_find_by_path_index(const fib_path_ext_list_t *list, fib_node_index_t path_index)
Definition: fib_path_ext.c:326
enum fib_path_list_attribute_t_ fib_path_list_attribute_t
Enumeration of path-list flags.
fib_node_index_t fib_path_create_special(fib_node_index_t pl_index, dpo_proto_t nh_proto, fib_path_cfg_flags_t flags, const dpo_id_t *dpo)
Definition: fib_path.c:1397
static fib_path_list_t * fib_path_list_alloc(fib_node_index_t *path_list_index)
u32 fib_path_list_db_size(void)
u8 * format_fib_path(u8 *s, va_list *args)
Definition: fib_path.c:456
fib_node_index_t fib_path_list_copy_and_path_add(fib_node_index_t orig_path_list_index, fib_path_list_flags_t flags, const fib_route_path_t *rpaths)
The identity of a DPO is a combination of its type and its instance number/index of objects of that t...
Definition: dpo.h:168
fib_node_bw_reason_flag_t fnbw_reason
The reason/trigger for the backwalk.
Definition: fib_node.h:208
static uword fib_path_list_db_hash_key_2_index(uword key)
#define hash_get(h, key)
Definition: hash.h:249
#define pool_elt_at_index(p, i)
Returns pointer to element at given index.
Definition: pool.h:514
fib_node_index_t fib_path_list_create(fib_path_list_flags_t flags, const fib_route_path_t *rpaths)
#define FIB_PATH_LIST_ATTRIBUTES
Definition: fib_path_list.h:91
u8 * format_fib_node_bw_reason(u8 *s, va_list *args)
Definition: fib_walk.c:973
static fib_node_back_walk_rc_t fib_path_list_back_walk_notify(fib_node_t *node, fib_node_back_walk_ctx_t *ctx)
dpo_type_t dpoi_type
the type
Definition: dpo.h:172
void fib_node_lock(fib_node_t *node)
Definition: fib_node.c:203
long ctx[MAX_CONNS]
Definition: main.c:144
struct _unformat_input_t unformat_input_t
load-balancing over a choice of [un]equal cost paths
Definition: dpo.h:102
adj_index_t fib_path_get_adj(fib_node_index_t path_index)
Definition: fib_path.c:2155
#define pool_put(P, E)
Free an object E in pool P.
Definition: pool.h:286
#define vec_dup(V)
Return copy of vector (no header, no alignment)
Definition: vec.h:375
#define vec_del1(v, i)
Delete the element at index I.
Definition: vec.h:804
void fib_path_list_lock(fib_node_index_t path_list_index)
vl_api_gbp_next_hop_t nhs[8]
Definition: gbp.api:284
A list of path-extensions.
Definition: fib_types.h:605
fib_node_type_t fn_type
The node&#39;s type.
Definition: fib_node.h:295
An node in the FIB graph.
Definition: fib_node.h:291
void fib_node_unlock(fib_node_t *node)
Definition: fib_node.c:209
const dpo_id_t * load_balance_get_bucket(index_t lbi, u32 bucket)
Definition: load_balance.c:317
fib_path_list_walk_rc_t(* fib_path_list_walk_w_ext_fn_t)(fib_node_index_t pl_index, fib_node_index_t path_index, const struct fib_path_ext_t_ *ext_list, void *ctx)
fib_path_list_flags_t fpl_flags
Flags on the path-list.
Definition: fib_path_list.c:52
fib_node_list_t fn_children
Vector of nodes that depend upon/use/share this node.
Definition: fib_node.h:305
static void fib_path_list_last_lock_gone(fib_node_t *node)
#define hash_mix64(a0, b0, c0)
Definition: hash.h:531
int fib_path_list_is_popular(fib_node_index_t path_list_index)
vlib_main_t * vm
Definition: buffer.c:312
#define vec_free(V)
Free vector&#39;s memory (no header).
Definition: vec.h:341
#define FIB_PATH_LIST_DBG(_pl, _fmt, _args...)
Definition: fib_path_list.c:94
void fib_urpf_list_bake(index_t ui)
Convert the uRPF list from the itf set obtained during the walk to a unique list. ...
static fib_path_cfg_flags_t fib_path_list_flags_2_path_flags(fib_path_list_flags_t plf)
fib_node_get_t fnv_get
Definition: fib_node.h:279
#define hash_mix32(a0, b0, c0)
Definition: hash.h:539
u32 fib_path_list_get_n_paths(fib_node_index_t path_list_index)
u32 fib_node_index_t
A typedef of a node index.
Definition: fib_types.h:30
#define pool_is_free_index(P, I)
Use free bitmap to query whether given index is free.
Definition: pool.h:283
u32 fib_node_get_n_children(fib_node_type_t parent_type, fib_node_index_t parent_index)
Definition: fib_node.c:142
u32 adj_index_t
An index for adjacencies.
Definition: adj_types.h:30
fib_node_index_t fpl_urpf
the RPF list calculated for this path list
Definition: fib_path_list.c:63
static fib_path_list_t * fib_path_list_get(fib_node_index_t index)
void dpo_set(dpo_id_t *dpo, dpo_type_t type, dpo_proto_t proto, index_t index)
Set/create a DPO ID The DPO will be locked.
Definition: dpo.c:185
void fib_path_list_unlock(fib_node_index_t path_list_index)
enum fib_path_list_fwd_flags_t_ fib_path_list_fwd_flags_t
Flags to control how the path-list returns forwarding information.
#define hash_create2(_elts, _user, _value_bytes,_key_sum, _key_equal,_format_pair, _format_pair_arg)
Definition: hash.h:494
Context passed between object during a back walk.
Definition: fib_node.h:204
#define VLIB_CLI_COMMAND(x,...)
Definition: cli.h:155
int fib_path_list_recursive_loop_detect(fib_node_index_t path_list_index, fib_node_index_t **entry_indicies)
static fib_path_list_t * fib_path_list_from_fib_node(fib_node_t *node)
int fib_path_list_is_looped(fib_node_index_t path_list_index)
#define uword_to_pointer(u, type)
Definition: types.h:136
static uword hash_elts(void *v)
Definition: hash.h:118
#define ASSERT(truth)
static fib_path_list_t * fib_path_list_resolve(fib_path_list_t *path_list)
static void fib_path_list_db_insert(fib_node_index_t path_list_index)
vlib_log_class_t fib_path_list_logger
the logger
Definition: fib_path_list.c:89
uword * fpl_db
Hash table of paths.
Definition: fib_path_list.c:68
void fib_urpf_list_combine(index_t ui1, index_t ui2)
Combine to interface lists.
enum fib_forward_chain_type_t_ fib_forward_chain_type_t
FIB output chain type.
void fib_node_child_remove(fib_node_type_t parent_type, fib_node_index_t parent_index, fib_node_index_t sibling_index)
Definition: fib_node.c:123
static void fib_path_list_mk_lb(fib_path_list_t *path_list, fib_forward_chain_type_t fct, dpo_id_t *dpo, fib_path_list_fwd_flags_t flags)
static fib_path_list_flags_t fib_path_list_flags_fixup(fib_path_list_flags_t flags)
static fib_node_index_t fib_path_list_get_index(fib_path_list_t *path_list)
dpo_proto_t fib_path_get_proto(fib_node_index_t path_index)
Definition: fib_path.c:2701
enum load_balance_flags_t_ load_balance_flags_t
void fib_path_list_back_walk(fib_node_index_t path_list_index, fib_node_back_walk_ctx_t *ctx)
u32 fib_path_get_resolving_interface(fib_node_index_t path_index)
Definition: fib_path.c:2087
index_t dpoi_index
the index of objects of that type
Definition: dpo.h:184
#define FIB_NODE_INDEX_INVALID
Definition: fib_types.h:31
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
u32 fn_locks
Number of dependents on this node.
Definition: fib_node.h:311
static load_balance_flags_t fib_path_list_fwd_flags_2_load_balance(fib_path_list_fwd_flags_t pl_flags)
#define INDEX_INVALID
Invalid index - used when no index is known blazoned capitals INVALID speak volumes where ~0 does not...
Definition: dpo.h:47
static fib_path_list_t * fib_path_list_db_get_from_hash_key(uword key)
u8 * format_fib_urpf_list(u8 *s, va_list *args)
Definition: fib_urpf_list.c:25
u8 * fib_path_list_format(fib_node_index_t path_list_index, u8 *s)
u64 uword
Definition: types.h:112
#define vec_sort_with_function(vec, f)
Sort a vector using the supplied element comparison function.
Definition: vec.h:980
typedef key
Definition: ipsec.api:244
fib_node_index_t fib_path_create(fib_node_index_t pl_index, const fib_route_path_t *rpath)
Definition: fib_path.c:1258
void fib_urpf_list_unlock(index_t ui)
Definition: fib_urpf_list.c:68
One path from an [EU]CMP set that the client wants to add to a load-balance object.
Definition: load_balance.h:62
enum fib_path_cfg_flags_t_ fib_path_cfg_flags_t
Path config flags from the attributes.
void fib_path_list_contribute_forwarding(fib_node_index_t path_list_index, fib_forward_chain_type_t fct, fib_path_list_fwd_flags_t flags, dpo_id_t *dpo)
dpo_proto_t fib_path_list_get_proto(fib_node_index_t path_list_index)
int fib_path_recursive_loop_detect(fib_node_index_t path_index, fib_node_index_t **entry_indicies)
Definition: fib_path.c:1762
fib_node_index_t fib_path_list_path_add(fib_node_index_t path_list_index, const fib_route_path_t *rpaths)
A FIB graph nodes virtual function table.
Definition: fib_node.h:278
index_t fib_path_list_get_urpf(fib_node_index_t path_list_index)
Return the the child the RPF list pre-built for this path list.
static void fib_path_list_memory_show(void)
enum fib_node_type_t_ fib_node_type_t
The types of nodes in a FIB graph.
u32 fib_path_list_pool_size(void)
#define vec_foreach(var, vec)
Vector iterator.
A path extension is a per-entry addition to the forwarding information when packets are sent for that...
Definition: fib_path_ext.h:98
void fib_path_list_walk_w_ext(fib_node_index_t path_list_index, const fib_path_ext_list_t *ext_list, fib_path_list_walk_w_ext_fn_t func, void *ctx)
fib_path_list_walk_rc_t(* fib_path_list_walk_fn_t)(fib_node_index_t pl_index, fib_node_index_t path_index, void *ctx)
A callback function type for walking a path-list&#39;s paths.
enum fib_path_list_flags_t_ fib_path_list_flags_t
#define pool_foreach_index(i, v, body)
Iterate pool by index.
Definition: pool.h:538
u8 * fib_node_children_format(fib_node_list_t list, u8 *s)
Definition: fib_node.c:176
static fib_node_t * fib_path_list_get_node(fib_node_index_t index)
struct fib_path_list_t_ fib_path_list_t
FIB path-list A representation of the list/set of path trough which a prefix is reachable.
void vlib_cli_output(vlib_main_t *vm, char *fmt,...)
Definition: cli.c:725
void fib_path_destroy(fib_node_index_t path_index)
Definition: fib_path.c:1476
int fib_path_cmp_w_route_path(fib_node_index_t path_index, const fib_route_path_t *rpath)
Definition: fib_path.c:1649
uword unformat(unformat_input_t *i, const char *fmt,...)
Definition: unformat.c:972
fib_node_index_t fib_path_list_path_remove(fib_node_index_t path_list_index, const fib_route_path_t *rpaths)
static uword fib_path_list_db_hash_key_sum(hash_t *h, uword key)
static uword pool_elts(void *v)
Number of active elements in a pool.
Definition: pool.h:128