FD.io VPP  v19.04.4-rc0-5-ge88582fac
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 =
184  old_path_list_hash =
185  (vec_len(path_list->fpl_paths) << 16 |
186  (path_list->fpl_flags & FIB_PATH_LIST_KEY_FLAGS));
187 
188  vec_foreach (path_index, path_list->fpl_paths)
189  {
190  path_hash = fib_path_hash(*path_index);
191 #if uword_bits == 64
192  hash_mix64(path_hash, old_path_list_hash, new_path_list_hash);
193 #else
194  hash_mix32(path_hash, old_path_list_hash, new_path_list_hash);
195 #endif
196  }
197 
198  return (new_path_list_hash);
199 }
200 
203 {
204  return 1 + 2*index;
205 }
206 
209 {
210  return key & 1;
211 }
212 
215 {
217  return key / 2;
218 }
219 
220 static fib_path_list_t*
222 {
223  fib_path_list_t *path_list;
224 
226  {
227  fib_node_index_t path_list_index;
228 
229  path_list_index = fib_path_list_db_hash_key_2_index(key);
230  path_list = fib_path_list_get(path_list_index);
231  }
232  else
233  {
234  path_list = uword_to_pointer (key, fib_path_list_t *);
235  }
236 
237  return (path_list);
238 }
239 
240 static uword
242  uword key)
243 {
244  fib_path_list_t *path_list;
245 
246  path_list = fib_path_list_db_get_from_hash_key(key);
247 
248  return (fib_path_list_hash(path_list));
249 }
250 
251 static uword
253  uword key1,
254  uword key2)
255 {
256  fib_path_list_t *path_list1, *path_list2;
257 
258  path_list1 = fib_path_list_db_get_from_hash_key(key1);
259  path_list2 = fib_path_list_db_get_from_hash_key(key2);
260 
261  return (fib_path_list_hash(path_list1) ==
262  fib_path_list_hash(path_list2));
263 }
264 
265 static fib_node_index_t
267 {
268  uword *p;
269 
270  p = hash_get(fib_path_list_db, path_list);
271 
272  if (NULL != p)
273  {
274  return p[0];
275  }
276 
277  return (FIB_NODE_INDEX_INVALID);
278 }
279 
280 static void
282 {
283  fib_path_list_t *path_list;
284 
285  path_list = fib_path_list_get(path_list_index);
286 
288 
290  fib_path_list_db_hash_key_from_index(path_list_index),
291  path_list_index);
292 
293  FIB_PATH_LIST_DBG(path_list, "DB-inserted");
294 }
295 
296 static void
298 {
299  fib_path_list_t *path_list;
300 
301  path_list = fib_path_list_get(path_list_index);
302 
304 
306  fib_path_list_db_hash_key_from_index(path_list_index));
307 
308  FIB_PATH_LIST_DBG(path_list, "DB-removed");
309 }
310 
311 static void
313 {
314  fib_node_index_t *path_index;
315 
316  FIB_PATH_LIST_DBG(path_list, "destroy");
317 
318  vec_foreach (path_index, path_list->fpl_paths)
319  {
320  fib_path_destroy(*path_index);
321  }
322 
323  vec_free(path_list->fpl_paths);
324  fib_urpf_list_unlock(path_list->fpl_urpf);
325 
326  fib_node_deinit(&path_list->fpl_node);
327  pool_put(fib_path_list_pool, path_list);
328 }
329 
330 static void
332 {
333  fib_path_list_t *path_list;
334 
335  path_list = fib_path_list_from_fib_node(node);
336 
337  FIB_PATH_LIST_DBG(path_list, "last-lock");
338 
339  if (path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED)
340  {
342  }
343  fib_path_list_destroy(path_list);
344 }
345 
348 {
350 
351  if (pl_flags & FIB_PATH_LIST_FWD_FLAG_STICKY)
352  {
353  lb_flags |= LOAD_BALANCE_ATTR_STICKY;
354  }
355  return (lb_flags);
356 }
357 
358 /*
359  * fib_path_mk_lb
360  *
361  * update the multipath adj this path-list will contribute to its
362  * children's forwarding.
363  */
364 static void
367  dpo_id_t *dpo,
369 {
371  fib_node_index_t *path_index;
372 
373  nhs = NULL;
374 
375  /*
376  * We gather the DPOs from resolved paths.
377  */
378  vec_foreach (path_index, path_list->fpl_paths)
379  {
380  if ((flags & FIB_PATH_LIST_FWD_FLAG_STICKY) ||
381  fib_path_is_resolved(*path_index))
382  {
383  nhs = fib_path_append_nh_for_multipath_hash(*path_index,
384  fct, 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  dpo_set(dpo,
397  0 /* FIXME FLOW HASH */));
400 
401  FIB_PATH_LIST_DBG(path_list, "mk lb: %d", dpo->dpoi_index);
402 
403  vec_free(nhs);
404 }
405 
406 /**
407  * @brief [re]build the path list's uRPF list
408  */
409 static void
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  fib_urpf_list_unlock(path_list->fpl_urpf);
422  path_list->fpl_urpf = fib_urpf_list_alloc_and_lock();
423 
424  vec_foreach (path_index, path_list->fpl_paths)
425  {
426  fib_path_contribute_urpf(*path_index, path_list->fpl_urpf);
427  }
428 
429  fib_urpf_list_bake(path_list->fpl_urpf);
430 }
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
438  index_t urpf)
439 {
440  fib_path_list_t *path_list;
441 
442  path_list = fib_path_list_get(path_list_index);
443 
444  fib_urpf_list_combine(urpf, path_list->fpl_urpf);
445 }
446 
447 /**
448  * @brief Return the the child the RPF list pre-built for this path list
449  */
450 index_t
452 {
453  fib_path_list_t *path_list;
454 
455  path_list = fib_path_list_get(path_list_index);
456 
457  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
469 {
470  fib_path_list_t *path_list;
471 
472  path_list = fib_path_list_get(path_list_index);
473 
474  fib_path_list_mk_urpf(path_list);
475 
476  FIB_PATH_LIST_DBG(path_list, "bw:%U",
478 
479  /*
480  * propagate the backwalk further
481  */
482  if (path_list->fpl_flags & FIB_PATH_LIST_FLAG_POPULAR)
483  {
484  /*
485  * many children. schedule a async walk
486  */
488  path_list_index,
490  ctx);
491  }
492  else
493  {
494  /*
495  * only a few children. continue the walk synchronously
496  */
497  fib_walk_sync(FIB_NODE_TYPE_PATH_LIST, path_list_index, ctx);
498  }
499 }
500 
501 /*
502  * fib_path_list_back_walk_notify
503  *
504  * A back walk has reach this path-list.
505  */
509 {
510  /*
511  * the path-list is not a direct child of any other node type
512  * paths, which do not change thier to-list-mapping, save the
513  * list they are a member of, and invoke the BW function directly.
514  */
515  ASSERT(0);
516 
518 }
519 
520 /*
521  * Display the path-list memory usage
522  */
523 static void
525 {
526  fib_show_memory_usage("Path-list",
527  pool_elts(fib_path_list_pool),
528  pool_len(fib_path_list_pool),
529  sizeof(fib_path_list_t));
531 }
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 = {
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 *
545 {
546  fib_path_list_t *path_list;
547 
548  pool_get(fib_path_list_pool, path_list);
549  clib_memset(path_list, 0, sizeof(*path_list));
550 
551  fib_node_init(&path_list->fpl_node,
553  path_list->fpl_urpf = INDEX_INVALID;
554  path_list->fpl_paths = NULL;
555 
556  *path_list_index = fib_path_list_get_index(path_list);
557 
558  FIB_PATH_LIST_DBG(path_list, "alloc");
559 
560  return (path_list);
561 }
562 
563 static fib_path_list_t *
565 {
566  fib_node_index_t *path_index, *paths, path_list_index;
567 
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  path_list_index = fib_path_list_get_index(path_list);
577  paths = vec_dup(path_list->fpl_paths);
578 
579  vec_foreach (path_index, paths)
580  {
581  fib_path_resolve(*path_index);
582  }
583 
584  vec_free(paths);
585  path_list = fib_path_list_get(path_list_index);
586 
587  FIB_PATH_LIST_DBG(path_list, "resovled");
588 
589  if (!(path_list->fpl_flags & FIB_PATH_LIST_FLAG_NO_URPF))
590  {
591  fib_path_list_mk_urpf(path_list);
592  }
593  return (path_list);
594 }
595 
596 u32
598 {
599  fib_path_list_t *path_list;
600 
601  if (FIB_NODE_INDEX_INVALID == path_list_index)
602  {
603  return (0);
604  }
605 
606  path_list = fib_path_list_get(path_list_index);
607 
608  return (vec_len(path_list->fpl_paths));
609 }
610 
611 
612 u32
614 {
615  fib_node_index_t *path_index;
616  fib_path_list_t *path_list;
618 
619  path_list = fib_path_list_get(path_list_index);
620 
621  sw_if_index = ~0;
622  vec_foreach (path_index, path_list->fpl_paths)
623  {
624  sw_if_index = fib_path_get_resolving_interface(*path_index);
625  if (~0 != sw_if_index)
626  {
627  return (sw_if_index);
628  }
629  }
630 
631  return (sw_if_index);
632 }
633 
636 {
637  fib_path_list_t *path_list;
638 
639  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  return (fib_path_get_proto(path_list->fpl_paths[0]));
646 }
647 
648 int
650 {
651  fib_path_list_t *path_list;
652 
653  path_list = fib_path_list_get(path_list_index);
654 
655  return (path_list->fpl_flags & FIB_PATH_LIST_FLAG_LOOPED);
656 }
657 
658 int
660 {
661  fib_path_list_t *path_list;
662 
663  path_list = fib_path_list_get(path_list_index);
664 
665  return (path_list->fpl_flags & FIB_PATH_LIST_FLAG_POPULAR);
666 }
667 
670 {
671  /*
672  * we do no share drop nor exclusive path-lists
673  */
674  if (flags & FIB_PATH_LIST_FLAG_DROP ||
676  {
677  flags &= ~FIB_PATH_LIST_FLAG_SHARED;
678  }
679 
680  return (flags);
681 }
682 
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  flags = fib_path_list_flags_fixup(flags);
692  path_list = fib_path_list_alloc(&path_list_index);
693  path_list->fpl_flags = flags;
694 
695  if (NULL != rpaths)
696  {
697  vec_foreach_index(i, rpaths)
698  {
699  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  if (vec_len(path_list->fpl_paths) > 1)
709  {
712  }
713  }
714 
715  /*
716  * If a shared path list is requested, consult the DB for a match
717  */
718  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  old_path_list_index = fib_path_list_db_find(path_list);
726  if (FIB_NODE_INDEX_INVALID != old_path_list_index)
727  {
728  fib_path_list_destroy(path_list);
729 
730  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  fib_path_list_db_insert(path_list_index);
739  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  path_list = fib_path_list_resolve(path_list);
749  }
750 
751  return (path_list_index);
752 }
753 
756 {
758 
759  if (plf & FIB_PATH_LIST_FLAG_DROP)
760  {
762  }
764  {
766  }
767  if (plf & FIB_PATH_LIST_FLAG_LOCAL)
768  {
770  }
771 
772  return (pf);
773 }
774 
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  path_list = fib_path_list_alloc(&path_list_index);
784  path_list->fpl_flags = flags;
785 
786  path_index =
787  fib_path_create_special(path_list_index,
788  nh_proto,
790  dpo);
791  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  path_list = fib_path_list_resolve(path_list);
797 
798  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
807  const fib_route_path_t *rpath)
808 {
809  fib_path_list_t *path_list;
810  u32 ii;
811 
812  path_list = fib_path_list_get(path_list_index);
813 
814  vec_foreach_index (ii, path_list->fpl_paths)
815  {
816  if (!fib_path_cmp_w_route_path(path_list->fpl_paths[ii], rpath))
817  {
818  return (ii);
819  }
820  }
821  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  */
834  const fib_route_path_t *rpaths)
835 {
836  fib_node_index_t new_path_index, *orig_path_index;
837  fib_path_list_t *path_list;
838 
839  /*
840  * alloc the new list before we retrieve the old one, lest
841  * the alloc result in a realloc
842  */
843  path_list = fib_path_list_get(path_list_index);
844 
845  ASSERT(1 == vec_len(rpaths));
846  ASSERT(!(path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED));
847 
848  FIB_PATH_LIST_DBG(path_list, "path-add");
849 
850  new_path_index = fib_path_create(path_list_index,
851  rpaths);
852 
853  vec_foreach (orig_path_index, path_list->fpl_paths)
854  {
855  /*
856  * don't add duplicate paths
857  */
858  if (0 == fib_path_cmp(new_path_index, *orig_path_index))
859  {
860  fib_path_destroy(new_path_index);
861  return (*orig_path_index);
862  }
863  }
864 
865  /*
866  * Add the new path - no sort, no sharing, no key..
867  */
868  vec_add1(path_list->fpl_paths, new_path_index);
869 
870  FIB_PATH_LIST_DBG(path_list, "path-added");
871 
872  /*
873  * no shared path list requested. resolve and use the one
874  * just created.
875  */
876  fib_path_resolve(new_path_index);
877 
878  return (new_path_index);
879 }
880 
884  const fib_route_path_t *rpaths)
885 {
886  fib_node_index_t path_index, new_path_index, *orig_path_index;
887  fib_path_list_t *path_list, *orig_path_list;
888  fib_node_index_t exist_path_list_index;
889  fib_node_index_t path_list_index;
890  fib_node_index_t pi;
891 
892  ASSERT(1 == vec_len(rpaths));
893 
894  /*
895  * alloc the new list before we retrieve the old one, lest
896  * the alloc result in a realloc
897  */
898  path_list = fib_path_list_alloc(&path_list_index);
899 
900  orig_path_list = fib_path_list_get(orig_path_list_index);
901 
902  FIB_PATH_LIST_DBG(orig_path_list, "copy-add");
903 
904  flags = fib_path_list_flags_fixup(flags);
905  path_list->fpl_flags = flags;
906 
907  vec_validate(path_list->fpl_paths, vec_len(orig_path_list->fpl_paths));
908  pi = 0;
909 
910  new_path_index = fib_path_create(path_list_index,
911  rpaths);
912 
913  vec_foreach (orig_path_index, orig_path_list->fpl_paths)
914  {
915  /*
916  * don't add duplicate paths
917  * In the unlikely event the path is a duplicate, then we'll
918  * find a matching path-list later and this one will be toast.
919  */
920  if (0 != fib_path_cmp(new_path_index, *orig_path_index))
921  {
922  path_index = fib_path_copy(*orig_path_index, path_list_index);
923  path_list->fpl_paths[pi++] = path_index;
924  }
925  else
926  {
927  _vec_len(path_list->fpl_paths) = vec_len(orig_path_list->fpl_paths);
928  }
929  }
930 
931  path_list->fpl_paths[pi] = new_path_index;
932 
933  /*
934  * we sort the paths since the key for the path-list is
935  * the description of the paths it contains. The paths need to
936  * be sorted else this description will differ.
937  */
939 
940  FIB_PATH_LIST_DBG(path_list, "path-added");
941 
942  /*
943  * check for a matching path-list in the DB.
944  * If we find one then we can return the existing one and destroy the
945  * new one just created.
946  */
947  if (path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED)
948  {
949  exist_path_list_index = fib_path_list_db_find(path_list);
950  if (FIB_NODE_INDEX_INVALID != exist_path_list_index)
951  {
952  fib_path_list_destroy(path_list);
953 
954  path_list_index = exist_path_list_index;
955  }
956  else
957  {
958  /*
959  * if there was not a matching path-list, then this
960  * new one will need inserting into the DB and resolving.
961  */
962  fib_path_list_db_insert(path_list_index);
963 
964  path_list = fib_path_list_resolve(path_list);
965  }
966  }
967  else
968  {
969  /*
970  * no shared path list requested. resolve and use the one
971  * just created.
972  */
973  path_list = fib_path_list_resolve(path_list);
974  }
975 
976  return (path_list_index);
977 }
978 
979 /*
980  * fib_path_list_path_remove
981  */
984  const fib_route_path_t *rpaths)
985 {
986  fib_node_index_t match_path_index, tmp_path_index;
987  fib_path_list_t *path_list;
988  fib_node_index_t pi;
989 
990  path_list = fib_path_list_get(path_list_index);
991 
992  ASSERT(1 == vec_len(rpaths));
993  ASSERT(!(path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED));
994 
995  FIB_PATH_LIST_DBG(path_list, "path-remove");
996 
997  /*
998  * create a representation of the path to be removed, so it
999  * can be used as a comparison object during the copy.
1000  */
1001  tmp_path_index = fib_path_create(path_list_index,
1002  rpaths);
1003  match_path_index = FIB_NODE_INDEX_INVALID;
1004 
1005  vec_foreach_index (pi, path_list->fpl_paths)
1006  {
1007  if (0 == fib_path_cmp(tmp_path_index,
1008  path_list->fpl_paths[pi]))
1009  {
1010  /*
1011  * match - remove it
1012  */
1013  match_path_index = path_list->fpl_paths[pi];
1014  fib_path_destroy(match_path_index);
1015  vec_del1(path_list->fpl_paths, pi);
1016  }
1017  }
1018 
1019  /*
1020  * done with the temporary now
1021  */
1022  fib_path_destroy(tmp_path_index);
1023 
1024  return (match_path_index);
1025 }
1026 
1027 /*
1028  * fib_path_list_copy_and_path_remove
1029  *
1030  * Copy the path-list excluding the path passed.
1031  * If the path is the last one, then the index reurned will be invalid.
1032  * i.e. the path-list is toast.
1033  */
1037  const fib_route_path_t *rpath)
1038 {
1039  fib_node_index_t path_index, *orig_path_index, path_list_index, tmp_path_index;
1040  fib_path_list_t *path_list, *orig_path_list;
1041  fib_node_index_t pi;
1042 
1043  path_list = fib_path_list_alloc(&path_list_index);
1044 
1045  flags = fib_path_list_flags_fixup(flags);
1046  orig_path_list = fib_path_list_get(orig_path_list_index);
1047 
1048  FIB_PATH_LIST_DBG(orig_path_list, "copy-remove");
1049 
1050  path_list->fpl_flags = flags;
1051  /*
1052  * allocate as many paths as we might need in one go, rather than
1053  * using vec_add to do a few at a time.
1054  */
1055  if (vec_len(orig_path_list->fpl_paths) > 1)
1056  {
1057  vec_validate(path_list->fpl_paths, vec_len(orig_path_list->fpl_paths) - 2);
1058  }
1059  pi = 0;
1060 
1061  /*
1062  * create a representation of the path to be removed, so it
1063  * can be used as a comparison object during the copy.
1064  */
1065  tmp_path_index = fib_path_create(path_list_index, rpath);
1066 
1067  vec_foreach (orig_path_index, orig_path_list->fpl_paths)
1068  {
1069  if (0 != fib_path_cmp(tmp_path_index, *orig_path_index)) {
1070  path_index = fib_path_copy(*orig_path_index, path_list_index);
1071  if (pi < vec_len(path_list->fpl_paths))
1072  {
1073  path_list->fpl_paths[pi++] = path_index;
1074  }
1075  else
1076  {
1077  /*
1078  * this is the unlikely case that the path being
1079  * removed does not match one in the path-list, so
1080  * we end up with as many paths as we started with.
1081  * the paths vector was sized above with the expectation
1082  * that we would have 1 less.
1083  */
1084  vec_add1(path_list->fpl_paths, path_index);
1085  }
1086  }
1087  }
1088 
1089  /*
1090  * done with the temporary now
1091  */
1092  fib_path_destroy(tmp_path_index);
1093 
1094  /*
1095  * if there are no paths, then the new path-list is aborted
1096  */
1097  if (0 == vec_len(path_list->fpl_paths)) {
1098  FIB_PATH_LIST_DBG(path_list, "last-path-removed");
1099 
1100  fib_path_list_destroy(path_list);
1101 
1102  path_list_index = FIB_NODE_INDEX_INVALID;
1103  } else {
1104  /*
1105  * we sort the paths since the key for the path-list is
1106  * the description of the paths it contains. The paths need to
1107  * be sorted else this description will differ.
1108  */
1110 
1111  /*
1112  * If a shared path list is requested, consult the DB for a match
1113  */
1114  if (path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED)
1115  {
1116  fib_node_index_t exist_path_list_index;
1117 
1118  /*
1119  * check for a matching path-list in the DB.
1120  * If we find one then we can return the existing one and destroy the
1121  * new one just created.
1122  */
1123  exist_path_list_index = fib_path_list_db_find(path_list);
1124  if (FIB_NODE_INDEX_INVALID != exist_path_list_index)
1125  {
1126  fib_path_list_destroy(path_list);
1127 
1128  path_list_index = exist_path_list_index;
1129  }
1130  else
1131  {
1132  /*
1133  * if there was not a matching path-list, then this
1134  * new one will need inserting into the DB and resolving.
1135  */
1136  fib_path_list_db_insert(path_list_index);
1137 
1138  path_list = fib_path_list_resolve(path_list);
1139  }
1140  }
1141  else
1142  {
1143  /*
1144  * no shared path list requested. resolve and use the one
1145  * just created.
1146  */
1147  path_list = fib_path_list_resolve(path_list);
1148  }
1149  }
1150 
1151  return (path_list_index);
1152 }
1153 
1154 /*
1155  * fib_path_list_contribute_forwarding
1156  *
1157  * Return the index of a load-balance that user of this path-list should
1158  * use for forwarding
1159  */
1160 void
1164  dpo_id_t *dpo)
1165 {
1166  fib_path_list_t *path_list;
1167 
1168  path_list = fib_path_list_get(path_list_index);
1169 
1170  fib_path_list_mk_lb(path_list, fct, dpo, flags);
1171 
1173 
1174  /*
1175  * If there's only one bucket in the load-balance then we can
1176  * squash it out.
1177  */
1178  if ((1 == load_balance_n_buckets(dpo->dpoi_index)) &&
1180  {
1182  }
1183 }
1184 
1185 /*
1186  * fib_path_list_get_adj
1187  *
1188  * Return the index of a adjacency for the first path that user of this
1189  * path-list should use for forwarding
1190  */
1194 {
1195  fib_path_list_t *path_list;
1196 
1197  path_list = fib_path_list_get(path_list_index);
1198  return (fib_path_get_adj(path_list->fpl_paths[0]));
1199 }
1200 
1201 int
1203  fib_node_index_t **entry_indicies)
1204 {
1205  fib_node_index_t *path_index;
1206  int is_looped, list_looped;
1207  fib_path_list_t *path_list;
1208 
1209  list_looped = 0;
1210  path_list = fib_path_list_get(path_list_index);
1211 
1212  vec_foreach (path_index, path_list->fpl_paths)
1213  {
1214  fib_node_index_t *copy, **copy_ptr;
1215 
1216  /*
1217  * we need a copy of the nodes visited so that when we add entries
1218  * we explore on the nth path and a looped is detected, those entries
1219  * are not again searched for n+1 path and so finding a loop that does
1220  * not exist.
1221  */
1222  copy = vec_dup(*entry_indicies);
1223  copy_ptr = &copy;
1224 
1225  is_looped = fib_path_recursive_loop_detect(*path_index, copy_ptr);
1226  list_looped += is_looped;
1227 
1228  vec_free(copy);
1229  }
1230 
1231  FIB_PATH_LIST_DBG(path_list, "loop-detect: eval:%d", list_looped);
1232 
1233  if (list_looped)
1234  {
1235  path_list->fpl_flags |= FIB_PATH_LIST_FLAG_LOOPED;
1236  }
1237  else
1238  {
1239  path_list->fpl_flags &= ~FIB_PATH_LIST_FLAG_LOOPED;
1240  }
1241 
1242  return (list_looped);
1243 }
1244 
1245 u32
1247  fib_node_type_t child_type,
1248  fib_node_index_t child_index)
1249 {
1250  u32 sibling;
1251 
1253  path_list_index,
1254  child_type,
1255  child_index);
1256 
1258  path_list_index))
1259  {
1260  /*
1261  * Set the popular flag on the path-list once we pass the magic
1262  * threshold. then walk children to update.
1263  * We don't undo this action. The rational being that the number
1264  * of entries using this prefix is large enough such that it is a
1265  * non-trival amount of effort to converge them. If we get into the
1266  * situation where we are adding and removing entries such that we
1267  * flip-flop over the threshold, then this non-trivial work is added
1268  * to each of those routes adds/deletes - not a situation we want.
1269  */
1271  .fnbw_reason = FIB_NODE_BW_REASON_FLAG_EVALUATE,
1272  };
1273  fib_path_list_t *path_list;
1274 
1275  path_list = fib_path_list_get(path_list_index);
1276  path_list->fpl_flags |= FIB_PATH_LIST_FLAG_POPULAR;
1277 
1278  fib_walk_sync(FIB_NODE_TYPE_PATH_LIST, path_list_index, &ctx);
1279  }
1280 
1281  return (sibling);
1282 }
1283 
1284 void
1286  u32 si)
1287 {
1289  path_list_index,
1290  si);
1291 }
1292 
1293 void
1295 {
1296  fib_path_list_t *path_list;
1297 
1298  if (FIB_NODE_INDEX_INVALID != path_list_index)
1299  {
1300  path_list = fib_path_list_get(path_list_index);
1301 
1302  fib_node_lock(&path_list->fpl_node);
1303  }
1304 }
1305 
1306 void
1308 {
1309  fib_path_list_t *path_list;
1310 
1311  if (FIB_NODE_INDEX_INVALID != path_list_index)
1312  {
1313  path_list = fib_path_list_get(path_list_index);
1314 
1315  fib_node_unlock(&path_list->fpl_node);
1316  }
1317 }
1318 
1319 u32
1321 {
1322  return (pool_elts(fib_path_list_pool));
1323 }
1324 
1325 u32
1327 {
1328  return (hash_elts(fib_path_list_db));
1329 }
1330 
1331 void
1334  void *ctx)
1335 {
1336  fib_node_index_t *path_index;
1337  fib_path_list_t *path_list;
1338 
1339  path_list = fib_path_list_get(path_list_index);
1340 
1341  vec_foreach(path_index, path_list->fpl_paths)
1342  {
1343  if (FIB_PATH_LIST_WALK_STOP == func(path_list_index,
1344  *path_index,
1345  ctx))
1346  break;
1347  }
1348 }
1349 
1350 void
1352  const fib_path_ext_list_t *ext_list,
1354  void *ctx)
1355 {
1356  fib_node_index_t *path_index;
1357  fib_path_list_t *path_list;
1358  fib_path_ext_t *path_ext;
1359 
1360  path_list = fib_path_list_get(path_list_index);
1361 
1362  vec_foreach(path_index, path_list->fpl_paths)
1363  {
1364  path_ext = fib_path_ext_list_find_by_path_index(ext_list, *path_index);
1365 
1366  if (FIB_PATH_LIST_WALK_STOP == func(path_list_index,
1367  *path_index,
1368  path_ext,
1369  ctx))
1370  break;
1371  }
1372 }
1373 
1374 void
1376 {
1377  fib_node_register_type (FIB_NODE_TYPE_PATH_LIST, &fib_path_list_vft);
1378 
1379  fib_path_list_db = hash_create2 (/* elts */ 0,
1380  /* user */ 0,
1381  /* value_bytes */ sizeof (fib_node_index_t),
1384  /* format pair/arg */
1385  0, 0);
1386  fib_path_list_logger = vlib_log_register_class("fib", "path-list");
1387 }
1388 
1389 static clib_error_t *
1391  unformat_input_t * input,
1392  vlib_cli_command_t * cmd)
1393 {
1394  fib_path_list_t *path_list;
1395  fib_node_index_t pli;
1396 
1397  if (unformat (input, "%d", &pli))
1398  {
1399  /*
1400  * show one in detail
1401  */
1402  if (!pool_is_free_index(fib_path_list_pool, pli))
1403  {
1404  path_list = fib_path_list_get(pli);
1405  u8 *s = fib_path_list_format(pli, NULL);
1406  s = format(s, "children:");
1407  s = fib_node_children_format(path_list->fpl_node.fn_children, s);
1408  vlib_cli_output (vm, "%s", s);
1409  vec_free(s);
1410  }
1411  else
1412  {
1413  vlib_cli_output (vm, "path list %d invalid", pli);
1414  }
1415  }
1416  else
1417  {
1418  /*
1419  * show all
1420  */
1421  vlib_cli_output (vm, "FIB Path Lists");
1422  pool_foreach_index (pli, fib_path_list_pool,
1423  ({
1424  vlib_cli_output (vm, "%U", format_fib_path_list, pli, 0);
1425  }));
1426  }
1427  return (NULL);
1428 }
1429 
1430 VLIB_CLI_COMMAND (show_fib_path_list, static) = {
1431  .path = "show fib path-lists",
1432  .function = show_fib_path_list_command,
1433  .short_help = "show fib path-lists",
1434 };
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:476
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
clib_memset(h->entries, 0, sizeof(h->entries[0]) *entries)
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:417
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)
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 FIB_PATH_LIST_KEY_FLAGS
The flags on a path-list that contribute to its key in the DB.
#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:611
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.
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)
#define hash_create2(_elts, _user, _value_bytes, _key_sum, _key_equal, _format_pair, _format_pair_arg)
Definition: hash.h:494
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:762
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