FD.io VPP  v18.01.2-1-g9b554f3
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 
28 /**
29  * The magic number of child entries that make a path-list popular.
30  * There's a trade-off here between convergnece and forwarding speed.
31  * Popular path-lists generate load-balance maps for the entires that
32  * use them. If the map is present there is a switch path cost to indirect
33  * through the map - this indirection provides the fast convergence - so
34  * without the map convergence is slower.
35  */
36 #define FIB_PATH_LIST_POPULAR 64
37 
38 /**
39  * FIB path-list
40  * A representation of the list/set of path trough which a prefix is reachable
41  */
42 typedef struct fib_path_list_t_ {
43  /**
44  * A path-list is a node in the FIB graph.
45  */
47 
48  /**
49  * Flags on the path-list
50  */
52 
53  /**
54  * Vector of paths indicies for all configured paths.
55  * For shareable path-lists this list MUST not change.
56  */
58 
59  /**
60  * the RPF list calculated for this path list
61  */
63 
64  /**
65  * Hash table of paths. valid only with INDEXED flag
66  */
69 
70 /*
71  * Array of strings/names for the FIB sources
72  */
74 
75 /*
76  * The memory pool from which we allocate all the path-lists
77  */
79 
80 /*
81  * The data-base of shared path-lists
82  */
84 
85 /*
86  * Debug macro
87  */
88 #ifdef FIB_DEBUG
89 #define FIB_PATH_LIST_DBG(_pl, _fmt, _args...) \
90 { \
91  u8 *_tmp = 0; \
92  _tmp = fib_path_list_format( \
93  fib_path_list_get_index(_pl), _tmp); \
94  clib_warning("pl:[%d:%p:%p:%s]:" _fmt, \
95  fib_path_list_get_index(_pl), \
96  _pl, _pl->fpl_paths, _tmp, \
97  ##_args); \
98  vec_free(_tmp); \
99 }
100 #else
101 #define FIB_PATH_LIST_DBG(_pl, _fmt, _args...)
102 #endif
103 
104 static fib_path_list_t *
106 {
107  return (pool_elt_at_index(fib_path_list_pool, index));
108 }
109 
110 static fib_node_t *
112 {
113  return ((fib_node_t*)fib_path_list_get(index));
114 }
115 
116 static fib_path_list_t*
118 {
120  return ((fib_path_list_t*)node);
121 }
122 
123 static fib_node_index_t
125 {
126  return (path_list - fib_path_list_pool);
127 }
128 
129 u8 *
130 format_fib_path_list (u8 * s, va_list * args)
131 {
132  fib_node_index_t *path_index, path_list_index;
134  fib_path_list_t *path_list;
135  u32 indent;
136 
137  path_list_index = va_arg (*args, fib_node_index_t);
138  indent = va_arg (*args, u32);
139  path_list = fib_path_list_get(path_list_index);
140 
141  s = format (s, "%Upath-list:[%d]",
142  format_white_space, indent,
143  fib_path_list_get_index(path_list));
144  s = format (s, " locks:%u", path_list->fpl_node.fn_locks);
145 
146  if (FIB_PATH_LIST_FLAG_NONE != path_list->fpl_flags)
147  {
148  s = format (s, " flags:");
150  {
151  if ((1<<attr) & path_list->fpl_flags)
152  {
153  s = format (s, "%s,", fib_path_list_attr_names[attr]);
154  }
155  }
156  }
157  s = format (s, " %U\n", format_fib_urpf_list, path_list->fpl_urpf);
158 
159  vec_foreach (path_index, path_list->fpl_paths)
160  {
161  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 
343 /*
344  * fib_path_mk_lb
345  *
346  * update the multipath adj this path-list will contribute to its
347  * children's forwarding.
348  */
349 static void
352  dpo_id_t *dpo)
353 {
354  load_balance_path_t *nhs;
355  fib_node_index_t *path_index;
356 
357  nhs = NULL;
358 
359  /*
360  * We gather the DPOs from resolved paths.
361  */
362  vec_foreach (path_index, path_list->fpl_paths)
363  {
364  nhs = fib_path_append_nh_for_multipath_hash(*path_index,
365  fct,
366  nhs);
367  }
368 
369  /*
370  * Path-list load-balances, which if used, would be shared and hence
371  * never need a load-balance map.
372  */
373  dpo_set(dpo,
378  0 /* FIXME FLOW HASH */));
380 
381  FIB_PATH_LIST_DBG(path_list, "mk lb: %d", dpo->dpoi_index);
382 
383  vec_free(nhs);
384 }
385 
386 /**
387  * @brief [re]build the path list's uRPF list
388  */
389 static void
391 {
392  fib_node_index_t *path_index;
393 
394  /*
395  * ditch the old one. by iterating through all paths we are going
396  * to re-find all the adjs that were in the old one anyway. If we
397  * keep the old one, then the |sort|uniq requires more work.
398  * All users of the RPF list have their own lock, so we can release
399  * immediately.
400  */
401  fib_urpf_list_unlock(path_list->fpl_urpf);
402  path_list->fpl_urpf = fib_urpf_list_alloc_and_lock();
403 
404  vec_foreach (path_index, path_list->fpl_paths)
405  {
406  fib_path_contribute_urpf(*path_index, path_list->fpl_urpf);
407  }
408 
409  fib_urpf_list_bake(path_list->fpl_urpf);
410 }
411 
412 /**
413  * @brief Contribute (add) this path list's uRPF list. This allows the child
414  * to construct an aggregate list.
415  */
416 void
418  index_t urpf)
419 {
420  fib_path_list_t *path_list;
421 
422  path_list = fib_path_list_get(path_list_index);
423 
424  fib_urpf_list_combine(urpf, path_list->fpl_urpf);
425 }
426 
427 /**
428  * @brief Return the the child the RPF list pre-built for this path list
429  */
430 index_t
432 {
433  fib_path_list_t *path_list;
434 
435  path_list = fib_path_list_get(path_list_index);
436 
437  return (path_list->fpl_urpf);
438 }
439 
440 /*
441  * fib_path_list_back_walk
442  *
443  * Called from one of this path-list's paths to progate
444  * a back walk
445  */
446 void
449 {
450  fib_path_list_t *path_list;
451 
452  path_list = fib_path_list_get(path_list_index);
453 
454  fib_path_list_mk_urpf(path_list);
455 
456  /*
457  * propagate the backwalk further
458  */
459  if (path_list->fpl_flags & FIB_PATH_LIST_FLAG_POPULAR)
460  {
461  /*
462  * many children. schedule a async walk
463  */
465  path_list_index,
467  ctx);
468  }
469  else
470  {
471  /*
472  * only a few children. continue the walk synchronously
473  */
474  fib_walk_sync(FIB_NODE_TYPE_PATH_LIST, path_list_index, ctx);
475  }
476 }
477 
478 /*
479  * fib_path_list_back_walk_notify
480  *
481  * A back walk has reach this path-list.
482  */
486 {
487  /*
488  * the path-list is not a direct child of any other node type
489  * paths, which do not change thier to-list-mapping, save the
490  * list they are a member of, and invoke the BW function directly.
491  */
492  ASSERT(0);
493 
495 }
496 
497 /*
498  * Display the path-list memory usage
499  */
500 static void
502 {
503  fib_show_memory_usage("Path-list",
504  pool_elts(fib_path_list_pool),
505  pool_len(fib_path_list_pool),
506  sizeof(fib_path_list_t));
508 }
509 
510 /*
511  * The FIB path-list's graph node virtual function table
512  */
513 static const fib_node_vft_t fib_path_list_vft = {
515  .fnv_last_lock = fib_path_list_last_lock_gone,
516  .fnv_back_walk = fib_path_list_back_walk_notify,
517  .fnv_mem_show = fib_path_list_memory_show,
518 };
519 
520 static inline fib_path_list_t *
522 {
523  fib_path_list_t *path_list;
524 
525  pool_get(fib_path_list_pool, path_list);
526  memset(path_list, 0, sizeof(*path_list));
527 
528  fib_node_init(&path_list->fpl_node,
530  path_list->fpl_urpf = INDEX_INVALID;
531  path_list->fpl_paths = NULL;
532 
533  *path_list_index = fib_path_list_get_index(path_list);
534 
535  FIB_PATH_LIST_DBG(path_list, "alloc");
536 
537  return (path_list);
538 }
539 
540 static fib_path_list_t *
542 {
543  fib_node_index_t *path_index, *paths, path_list_index;
544 
546 
547  /*
548  * resolving a path-list is a recursive action. this means more path
549  * lists can be created during this call, and hence this path-list
550  * can be realloc'd. so we work with copies.
551  * this function is called only once per-path list, so its no great overhead.
552  */
553  path_list_index = fib_path_list_get_index(path_list);
554  paths = vec_dup(path_list->fpl_paths);
555 
556  vec_foreach (path_index, paths)
557  {
558  fib_path_resolve(*path_index);
559  }
560 
561  vec_free(paths);
562  path_list = fib_path_list_get(path_list_index);
563 
564  FIB_PATH_LIST_DBG(path_list, "resovled");
565 
566  if (!(path_list->fpl_flags & FIB_PATH_LIST_FLAG_NO_URPF))
567  {
568  fib_path_list_mk_urpf(path_list);
569  }
570  return (path_list);
571 }
572 
573 u32
575 {
576  fib_path_list_t *path_list;
577 
578  if (FIB_NODE_INDEX_INVALID == path_list_index)
579  {
580  return (0);
581  }
582 
583  path_list = fib_path_list_get(path_list_index);
584 
585  return (vec_len(path_list->fpl_paths));
586 }
587 
588 
589 u32
591 {
592  fib_node_index_t *path_index;
593  fib_path_list_t *path_list;
594  u32 sw_if_index;
595 
596  path_list = fib_path_list_get(path_list_index);
597 
598  sw_if_index = ~0;
599  vec_foreach (path_index, path_list->fpl_paths)
600  {
601  sw_if_index = fib_path_get_resolving_interface(*path_index);
602  if (~0 != sw_if_index)
603  {
604  return (sw_if_index);
605  }
606  }
607 
608  return (sw_if_index);
609 }
610 
613 {
614  fib_path_list_t *path_list;
615 
616  path_list = fib_path_list_get(path_list_index);
617 
618  /*
619  * we don't support a mix of path protocols, so we can return the proto
620  * of the first
621  */
622  return (fib_path_get_proto(path_list->fpl_paths[0]));
623 }
624 
625 int
627 {
628  fib_path_list_t *path_list;
629 
630  path_list = fib_path_list_get(path_list_index);
631 
632  return (path_list->fpl_flags & FIB_PATH_LIST_FLAG_LOOPED);
633 }
634 
635 int
637 {
638  fib_path_list_t *path_list;
639 
640  path_list = fib_path_list_get(path_list_index);
641 
642  return (path_list->fpl_flags & FIB_PATH_LIST_FLAG_POPULAR);
643 }
644 
647 {
648  /*
649  * we do no share drop nor exclusive path-lists
650  */
651  if (flags & FIB_PATH_LIST_FLAG_DROP ||
653  {
654  flags &= ~FIB_PATH_LIST_FLAG_SHARED;
655  }
656 
657  return (flags);
658 }
659 
662  const fib_route_path_t *rpaths)
663 {
664  fib_node_index_t path_list_index, old_path_list_index;
665  fib_path_list_t *path_list;
666  int i;
667 
668  flags = fib_path_list_flags_fixup(flags);
669  path_list = fib_path_list_alloc(&path_list_index);
670  path_list->fpl_flags = flags;
671 
672  if (NULL != rpaths)
673  {
674  vec_foreach_index(i, rpaths)
675  {
676  vec_add1(path_list->fpl_paths,
677  fib_path_create(path_list_index,
678  &rpaths[i]));
679  }
680  /*
681  * we sort the paths since the key for the path-list is
682  * the description of the paths it contains. The paths need to
683  * be sorted else this description will differ.
684  */
685  if (vec_len(path_list->fpl_paths) > 1)
686  {
689  }
690  }
691 
692  /*
693  * If a shared path list is requested, consult the DB for a match
694  */
695  if (flags & FIB_PATH_LIST_FLAG_SHARED)
696  {
697  /*
698  * check for a matching path-list in the DB.
699  * If we find one then we can return the existing one and destroy the
700  * new one just created.
701  */
702  old_path_list_index = fib_path_list_db_find(path_list);
703  if (FIB_NODE_INDEX_INVALID != old_path_list_index)
704  {
705  fib_path_list_destroy(path_list);
706 
707  path_list_index = old_path_list_index;
708  }
709  else
710  {
711  /*
712  * if there was not a matching path-list, then this
713  * new one will need inserting into the DB and resolving.
714  */
715  fib_path_list_db_insert(path_list_index);
716  path_list = fib_path_list_resolve(path_list);
717  }
718  }
719  else
720  {
721  /*
722  * no shared path list requested. resolve and use the one
723  * just created.
724  */
725  path_list = fib_path_list_resolve(path_list);
726  }
727 
728  return (path_list_index);
729 }
730 
731 static fib_path_cfg_flags_t
733 {
735 
736  if (plf & FIB_PATH_LIST_FLAG_DROP)
737  {
739  }
741  {
743  }
744  if (plf & FIB_PATH_LIST_FLAG_LOCAL)
745  {
747  }
748 
749  return (pf);
750 }
751 
755  const dpo_id_t *dpo)
756 {
757  fib_node_index_t path_index, path_list_index;
758  fib_path_list_t *path_list;
759 
760  path_list = fib_path_list_alloc(&path_list_index);
761  path_list->fpl_flags = flags;
762 
763  path_index =
764  fib_path_create_special(path_list_index,
765  nh_proto,
767  dpo);
768  vec_add1(path_list->fpl_paths, path_index);
769 
770  /*
771  * we don't share path-lists. we can do PIC on them so why bother.
772  */
773  path_list = fib_path_list_resolve(path_list);
774 
775  return (path_list_index);
776 }
777 
778 /*
779  * return the index info the path-lists's vector of paths, of the matching path.
780  * ~0 if not found
781  */
782 u32
784  const fib_route_path_t *rpath)
785 {
786  fib_path_list_t *path_list;
787  u32 ii;
788 
789  path_list = fib_path_list_get(path_list_index);
790 
791  vec_foreach_index (ii, path_list->fpl_paths)
792  {
793  if (!fib_path_cmp_w_route_path(path_list->fpl_paths[ii], rpath))
794  {
795  return (ii);
796  }
797  }
798  return (~0);
799 }
800 
801 
802 /*
803  * fib_path_list_copy_and_path_add
804  *
805  * Create a copy of a path-list and append one more path to it.
806  * The path-list returned could either have been newly created, or
807  * can be a shared path-list from the data-base.
808  */
811  const fib_route_path_t *rpaths)
812 {
813  fib_node_index_t new_path_index, *orig_path_index;
814  fib_path_list_t *path_list;
815 
816  /*
817  * alloc the new list before we retrieve the old one, lest
818  * the alloc result in a realloc
819  */
820  path_list = fib_path_list_get(path_list_index);
821 
822  ASSERT(1 == vec_len(rpaths));
823  ASSERT(!(path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED));
824 
825  FIB_PATH_LIST_DBG(orig_path_list, "path-add");
826 
827  new_path_index = fib_path_create(path_list_index,
828  rpaths);
829 
830  vec_foreach (orig_path_index, path_list->fpl_paths)
831  {
832  /*
833  * don't add duplicate paths
834  */
835  if (0 == fib_path_cmp(new_path_index, *orig_path_index))
836  {
837  fib_path_destroy(new_path_index);
838  return (*orig_path_index);
839  }
840  }
841 
842  /*
843  * Add the new path - no sort, no sharing, no key..
844  */
845  vec_add1(path_list->fpl_paths, new_path_index);
846 
847  FIB_PATH_LIST_DBG(path_list, "path-added");
848 
849  /*
850  * no shared path list requested. resolve and use the one
851  * just created.
852  */
853  fib_path_resolve(new_path_index);
854 
855  return (new_path_index);
856 }
857 
861  const fib_route_path_t *rpaths)
862 {
863  fib_node_index_t path_index, new_path_index, *orig_path_index;
864  fib_path_list_t *path_list, *orig_path_list;
865  fib_node_index_t exist_path_list_index;
866  fib_node_index_t path_list_index;
867  fib_node_index_t pi;
868 
869  ASSERT(1 == vec_len(rpaths));
870 
871  /*
872  * alloc the new list before we retrieve the old one, lest
873  * the alloc result in a realloc
874  */
875  path_list = fib_path_list_alloc(&path_list_index);
876 
877  orig_path_list = fib_path_list_get(orig_path_list_index);
878 
879  FIB_PATH_LIST_DBG(orig_path_list, "copy-add");
880 
881  flags = fib_path_list_flags_fixup(flags);
882  path_list->fpl_flags = flags;
883 
884  vec_validate(path_list->fpl_paths, vec_len(orig_path_list->fpl_paths));
885  pi = 0;
886 
887  new_path_index = fib_path_create(path_list_index,
888  rpaths);
889 
890  vec_foreach (orig_path_index, orig_path_list->fpl_paths)
891  {
892  /*
893  * don't add duplicate paths
894  * In the unlikely event the path is a duplicate, then we'll
895  * find a matching path-list later and this one will be toast.
896  */
897  if (0 != fib_path_cmp(new_path_index, *orig_path_index))
898  {
899  path_index = fib_path_copy(*orig_path_index, path_list_index);
900  path_list->fpl_paths[pi++] = path_index;
901  }
902  else
903  {
904  _vec_len(path_list->fpl_paths) = vec_len(orig_path_list->fpl_paths);
905  }
906  }
907 
908  path_list->fpl_paths[pi] = new_path_index;
909 
910  /*
911  * we sort the paths since the key for the path-list is
912  * the description of the paths it contains. The paths need to
913  * be sorted else this description will differ.
914  */
916 
917  FIB_PATH_LIST_DBG(path_list, "path-added");
918 
919  /*
920  * check for a matching path-list in the DB.
921  * If we find one then we can return the existing one and destroy the
922  * new one just created.
923  */
924  if (path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED)
925  {
926  exist_path_list_index = fib_path_list_db_find(path_list);
927  if (FIB_NODE_INDEX_INVALID != exist_path_list_index)
928  {
929  fib_path_list_destroy(path_list);
930 
931  path_list_index = exist_path_list_index;
932  }
933  else
934  {
935  /*
936  * if there was not a matching path-list, then this
937  * new one will need inserting into the DB and resolving.
938  */
939  fib_path_list_db_insert(path_list_index);
940 
941  path_list = fib_path_list_resolve(path_list);
942  }
943  }
944  else
945  {
946  /*
947  * no shared path list requested. resolve and use the one
948  * just created.
949  */
950  path_list = fib_path_list_resolve(path_list);
951  }
952 
953  return (path_list_index);
954 }
955 
956 /*
957  * fib_path_list_path_remove
958  */
961  const fib_route_path_t *rpaths)
962 {
963  fib_node_index_t match_path_index, tmp_path_index;
964  fib_path_list_t *path_list;
965  fib_node_index_t pi;
966 
967  path_list = fib_path_list_get(path_list_index);
968 
969  ASSERT(1 == vec_len(rpaths));
970  ASSERT(!(path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED));
971 
972  FIB_PATH_LIST_DBG(orig_path_list, "path-remove");
973 
974  /*
975  * create a representation of the path to be removed, so it
976  * can be used as a comparison object during the copy.
977  */
978  tmp_path_index = fib_path_create(path_list_index,
979  rpaths);
980  match_path_index = FIB_NODE_INDEX_INVALID;
981 
982  vec_foreach_index (pi, path_list->fpl_paths)
983  {
984  if (0 == fib_path_cmp(tmp_path_index,
985  path_list->fpl_paths[pi]))
986  {
987  /*
988  * match - remove it
989  */
990  match_path_index = path_list->fpl_paths[pi];
991  fib_path_destroy(match_path_index);
992  vec_del1(path_list->fpl_paths, pi);
993  }
994  }
995 
996  /*
997  * done with the temporary now
998  */
999  fib_path_destroy(tmp_path_index);
1000 
1001  return (match_path_index);
1002 }
1003 
1004 /*
1005  * fib_path_list_copy_and_path_remove
1006  *
1007  * Copy the path-list excluding the path passed.
1008  * If the path is the last one, then the index reurned will be invalid.
1009  * i.e. the path-list is toast.
1010  */
1014  const fib_route_path_t *rpaths)
1015 {
1016  fib_node_index_t path_index, *orig_path_index, path_list_index, tmp_path_index;
1017  fib_path_list_t *path_list, *orig_path_list;
1018  fib_node_index_t pi;
1019 
1020  ASSERT(1 == vec_len(rpaths));
1021 
1022  path_list = fib_path_list_alloc(&path_list_index);
1023 
1024  flags = fib_path_list_flags_fixup(flags);
1025  orig_path_list = fib_path_list_get(orig_path_list_index);
1026 
1027  FIB_PATH_LIST_DBG(orig_path_list, "copy-remove");
1028 
1029  path_list->fpl_flags = flags;
1030  /*
1031  * allocate as many paths as we might need in one go, rather than
1032  * using vec_add to do a few at a time.
1033  */
1034  if (vec_len(orig_path_list->fpl_paths) > 1)
1035  {
1036  vec_validate(path_list->fpl_paths, vec_len(orig_path_list->fpl_paths) - 2);
1037  }
1038  pi = 0;
1039 
1040  /*
1041  * create a representation of the path to be removed, so it
1042  * can be used as a comparison object during the copy.
1043  */
1044  tmp_path_index = fib_path_create(path_list_index,
1045  rpaths);
1046 
1047  vec_foreach (orig_path_index, orig_path_list->fpl_paths)
1048  {
1049  if (0 != fib_path_cmp(tmp_path_index, *orig_path_index)) {
1050  path_index = fib_path_copy(*orig_path_index, path_list_index);
1051  if (pi < vec_len(path_list->fpl_paths))
1052  {
1053  path_list->fpl_paths[pi++] = path_index;
1054  }
1055  else
1056  {
1057  /*
1058  * this is the unlikely case that the path being
1059  * removed does not match one in the path-list, so
1060  * we end up with as many paths as we started with.
1061  * the paths vector was sized above with the expectation
1062  * that we would have 1 less.
1063  */
1064  vec_add1(path_list->fpl_paths, path_index);
1065  }
1066  }
1067  }
1068 
1069  /*
1070  * done with the temporary now
1071  */
1072  fib_path_destroy(tmp_path_index);
1073 
1074  /*
1075  * if there are no paths, then the new path-list is aborted
1076  */
1077  if (0 == vec_len(path_list->fpl_paths)) {
1078  FIB_PATH_LIST_DBG(path_list, "last-path-removed");
1079 
1080  fib_path_list_destroy(path_list);
1081 
1082  path_list_index = FIB_NODE_INDEX_INVALID;
1083  } else {
1084  /*
1085  * we sort the paths since the key for the path-list is
1086  * the description of the paths it contains. The paths need to
1087  * be sorted else this description will differ.
1088  */
1090 
1091  /*
1092  * If a shared path list is requested, consult the DB for a match
1093  */
1094  if (path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED)
1095  {
1096  fib_node_index_t exist_path_list_index;
1097 
1098  /*
1099  * check for a matching path-list in the DB.
1100  * If we find one then we can return the existing one and destroy the
1101  * new one just created.
1102  */
1103  exist_path_list_index = fib_path_list_db_find(path_list);
1104  if (FIB_NODE_INDEX_INVALID != exist_path_list_index)
1105  {
1106  fib_path_list_destroy(path_list);
1107 
1108  path_list_index = exist_path_list_index;
1109  }
1110  else
1111  {
1112  /*
1113  * if there was not a matching path-list, then this
1114  * new one will need inserting into the DB and resolving.
1115  */
1116  fib_path_list_db_insert(path_list_index);
1117 
1118  path_list = fib_path_list_resolve(path_list);
1119  }
1120  }
1121  else
1122  {
1123  /*
1124  * no shared path list requested. resolve and use the one
1125  * just created.
1126  */
1127  path_list = fib_path_list_resolve(path_list);
1128  }
1129  }
1130 
1131  return (path_list_index);
1132 }
1133 
1134 /*
1135  * fib_path_list_contribute_forwarding
1136  *
1137  * Return the index of a load-balance that user of this path-list should
1138  * use for forwarding
1139  */
1140 void
1144  dpo_id_t *dpo)
1145 {
1146  fib_path_list_t *path_list;
1147 
1148  path_list = fib_path_list_get(path_list_index);
1149 
1150  fib_path_list_mk_lb(path_list, fct, dpo);
1151 
1153 
1154  /*
1155  * If there's only one bucket in the load-balance then we can
1156  * squash it out.
1157  */
1158  if ((1 == load_balance_n_buckets(dpo->dpoi_index)) &&
1160  {
1162  }
1163 }
1164 
1165 /*
1166  * fib_path_list_get_adj
1167  *
1168  * Return the index of a adjacency for the first path that user of this
1169  * path-list should use for forwarding
1170  */
1174 {
1175  fib_path_list_t *path_list;
1176 
1177  path_list = fib_path_list_get(path_list_index);
1178  return (fib_path_get_adj(path_list->fpl_paths[0]));
1179 }
1180 
1181 int
1183  fib_node_index_t **entry_indicies)
1184 {
1185  fib_node_index_t *path_index;
1186  int is_looped, list_looped;
1187  fib_path_list_t *path_list;
1188 
1189  list_looped = 0;
1190  path_list = fib_path_list_get(path_list_index);
1191 
1192  vec_foreach (path_index, path_list->fpl_paths)
1193  {
1194  fib_node_index_t *copy, **copy_ptr;
1195 
1196  /*
1197  * we need a copy of the nodes visited so that when we add entries
1198  * we explore on the nth path and a looped is detected, those entries
1199  * are not again searched for n+1 path and so finding a loop that does
1200  * not exist.
1201  */
1202  copy = vec_dup(*entry_indicies);
1203  copy_ptr = &copy;
1204 
1205  is_looped = fib_path_recursive_loop_detect(*path_index, copy_ptr);
1206  list_looped += is_looped;
1207 
1208  vec_free(copy);
1209  }
1210 
1211  FIB_PATH_LIST_DBG(path_list, "loop-detect: eval:%d", eval);
1212 
1213  if (list_looped)
1214  {
1215  path_list->fpl_flags |= FIB_PATH_LIST_FLAG_LOOPED;
1216  }
1217  else
1218  {
1219  path_list->fpl_flags &= ~FIB_PATH_LIST_FLAG_LOOPED;
1220  }
1221 
1222  return (list_looped);
1223 }
1224 
1225 u32
1227  fib_node_type_t child_type,
1228  fib_node_index_t child_index)
1229 {
1230  u32 sibling;
1231 
1233  path_list_index,
1234  child_type,
1235  child_index);
1236 
1238  path_list_index))
1239  {
1240  /*
1241  * Set the popular flag on the path-list once we pass the magic
1242  * threshold. then walk children to update.
1243  * We don't undo this action. The rational being that the number
1244  * of entries using this prefix is large enough such that it is a
1245  * non-trival amount of effort to converge them. If we get into the
1246  * situation where we are adding and removing entries such that we
1247  * flip-flop over the threshold, then this non-trivial work is added
1248  * to each of those routes adds/deletes - not a situation we want.
1249  */
1251  .fnbw_reason = FIB_NODE_BW_REASON_FLAG_EVALUATE,
1252  };
1253  fib_path_list_t *path_list;
1254 
1255  path_list = fib_path_list_get(path_list_index);
1256  path_list->fpl_flags |= FIB_PATH_LIST_FLAG_POPULAR;
1257 
1258  fib_walk_sync(FIB_NODE_TYPE_PATH_LIST, path_list_index, &ctx);
1259  }
1260 
1261  return (sibling);
1262 }
1263 
1264 void
1266  u32 si)
1267 {
1269  path_list_index,
1270  si);
1271 }
1272 
1273 void
1275 {
1276  fib_path_list_t *path_list;
1277 
1278  if (FIB_NODE_INDEX_INVALID != path_list_index)
1279  {
1280  path_list = fib_path_list_get(path_list_index);
1281 
1282  fib_node_lock(&path_list->fpl_node);
1283  FIB_PATH_LIST_DBG(path_list, "lock");
1284  }
1285 }
1286 
1287 void
1289 {
1290  fib_path_list_t *path_list;
1291 
1292  if (FIB_NODE_INDEX_INVALID != path_list_index)
1293  {
1294  path_list = fib_path_list_get(path_list_index);
1295  FIB_PATH_LIST_DBG(path_list, "unlock");
1296 
1297  fib_node_unlock(&path_list->fpl_node);
1298  }
1299 }
1300 
1301 u32
1303 {
1304  return (pool_elts(fib_path_list_pool));
1305 }
1306 
1307 u32
1309 {
1310  return (hash_elts(fib_path_list_db));
1311 }
1312 
1313 void
1316  void *ctx)
1317 {
1318  fib_node_index_t *path_index;
1319  fib_path_list_t *path_list;
1320 
1321  path_list = fib_path_list_get(path_list_index);
1322 
1323  vec_foreach(path_index, path_list->fpl_paths)
1324  {
1325  if (FIB_PATH_LIST_WALK_STOP == func(path_list_index,
1326  *path_index,
1327  ctx))
1328  break;
1329  }
1330 }
1331 
1332 
1333 void
1335 {
1336  fib_node_register_type (FIB_NODE_TYPE_PATH_LIST, &fib_path_list_vft);
1337 
1338  fib_path_list_db = hash_create2 (/* elts */ 0,
1339  /* user */ 0,
1340  /* value_bytes */ sizeof (fib_node_index_t),
1343  /* format pair/arg */
1344  0, 0);
1345 }
1346 
1347 static clib_error_t *
1349  unformat_input_t * input,
1350  vlib_cli_command_t * cmd)
1351 {
1352  fib_path_list_t *path_list;
1353  fib_node_index_t pli;
1354 
1355  if (unformat (input, "%d", &pli))
1356  {
1357  /*
1358  * show one in detail
1359  */
1360  if (!pool_is_free_index(fib_path_list_pool, pli))
1361  {
1362  path_list = fib_path_list_get(pli);
1363  u8 *s = fib_path_list_format(pli, NULL);
1364  s = format(s, "children:");
1365  s = fib_node_children_format(path_list->fpl_node.fn_children, s);
1366  vlib_cli_output (vm, "%s", s);
1367  vec_free(s);
1368  }
1369  else
1370  {
1371  vlib_cli_output (vm, "path list %d invalid", pli);
1372  }
1373  }
1374  else
1375  {
1376  /*
1377  * show all
1378  */
1379  vlib_cli_output (vm, "FIB Path Lists");
1380  pool_foreach_index (pli, fib_path_list_pool,
1381  ({
1382  vlib_cli_output (vm, "%U", format_fib_path_list, pli, 0);
1383  }));
1384  }
1385  return (NULL);
1386 }
1387 
1388 VLIB_CLI_COMMAND (show_fib_path_list, static) = {
1389  .path = "show fib path-lists",
1390  .function = show_fib_path_list_command,
1391  .short_help = "show fib path-lists",
1392 };
#define vec_validate(V, I)
Make sure vector is long enough for given index (no header, unspecified alignment) ...
Definition: vec.h:432
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:1797
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:254
sll srl srl sll sra u16x4 i
Definition: vector_sse2.h:337
uword fib_path_hash(fib_node_index_t path_index)
Definition: fib_path.c:1458
#define FIB_PATH_LIST_POPULAR
The magic number of child entries that make a path-list popular.
Definition: fib_path_list.c:36
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:202
#define hash_unset(h, key)
Definition: hash.h:260
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:2141
A representation of a path as described by a route producer.
Definition: fib_types.h:377
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:1593
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:55
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:57
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:311
void dpo_copy(dpo_id_t *dst, const dpo_id_t *src)
atomic copy a data-plane object.
Definition: dpo.c:258
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:518
static uword * fib_path_list_db
Definition: fib_path_list.c:83
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:673
u8 * format(u8 *s, const char *fmt,...)
Definition: format.c:419
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:225
int fib_path_cmp_for_sort(void *v1, void *v2)
Definition: fib_path.c:1566
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
#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:42
static fib_path_list_t * fib_path_list_pool
Definition: fib_path_list.c:78
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:2472
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:73
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:194
fib_node_t fpl_node
A path-list is a node in the FIB graph.
Definition: fib_path_list.c:46
static uword fib_path_list_db_hash_key_is_index(uword key)
#define always_inline
Definition: clib.h:92
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:727
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:1404
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:494
enum dpo_proto_t_ dpo_proto_t
Data path protocol.
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:1358
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:444
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:166
static uword fib_path_list_db_hash_key_2_index(uword key)
#define hash_get(h, key)
Definition: hash.h:248
#define pool_elt_at_index(p, i)
Returns pointer to element at given index.
Definition: pool.h:459
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
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:170
void fib_node_lock(fib_node_t *node)
Definition: fib_node.c:203
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:2079
#define pool_put(P, E)
Free an object E in pool P.
Definition: pool.h:271
#define vec_dup(V)
Return copy of vector (no header, no alignment)
Definition: vec.h:370
#define vec_del1(v, i)
Delete the element at index I.
Definition: vec.h:801
void fib_path_list_lock(fib_node_index_t path_list_index)
fib_node_type_t fn_type
The node&#39;s type.
Definition: fib_node.h:290
An node in the FIB graph.
Definition: fib_node.h:286
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:294
fib_path_list_flags_t fpl_flags
Flags on the path-list.
Definition: fib_path_list.c:51
#define uword_to_pointer(u, type)
Definition: types.h:136
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 *rpaths)
fib_node_list_t fn_children
The node&#39;s VFT.
Definition: fib_node.h:306
static void fib_path_list_last_lock_gone(fib_node_t *node)
#define hash_mix64(a0, b0, c0)
Definition: hash.h:530
int fib_path_list_is_popular(fib_node_index_t path_list_index)
vlib_main_t * vm
Definition: buffer.c:283
vec_header_t h
Definition: buffer.c:282
#define vec_free(V)
Free vector&#39;s memory (no header).
Definition: vec.h:336
#define FIB_PATH_LIST_DBG(_pl, _fmt, _args...)
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:274
#define hash_mix32(a0, b0, c0)
Definition: hash.h:538
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:29
#define pool_is_free_index(P, I)
Use free bitmap to query whether given index is free.
Definition: pool.h:268
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:62
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:182
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:493
Context passed between object during a back walk.
Definition: fib_node.h:199
#define VLIB_CLI_COMMAND(x,...)
Definition: cli.h:154
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)
static uword hash_elts(void *v)
Definition: hash.h:117
#define ASSERT(truth)
unsigned int u32
Definition: types.h:88
static fib_path_list_t * fib_path_list_resolve(fib_path_list_t *path_list)
long ctx[MAX_CONNS]
Definition: main.c:122
static void fib_path_list_db_insert(fib_node_index_t path_list_index)
uword * fpl_db
Hash table of paths.
Definition: fib_path_list.c:67
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 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)
u64 uword
Definition: types.h:112
dpo_proto_t fib_path_get_proto(fib_node_index_t path_index)
Definition: fib_path.c:2601
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:2014
index_t dpoi_index
the index of objects of that type
Definition: dpo.h:182
#define FIB_NODE_INDEX_INVALID
Definition: fib_types.h:30
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
unsigned char u8
Definition: types.h:56
u32 fn_locks
Number of dependents on this node.
Definition: fib_node.h:312
#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)
#define vec_sort_with_function(vec, f)
Sort a vector using the supplied element comparison function.
Definition: vec.h:956
fib_node_index_t fib_path_create(fib_node_index_t pl_index, const fib_route_path_t *rpath)
Definition: fib_path.c:1230
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)
static void fib_path_list_mk_lb(fib_path_list_t *path_list, fib_forward_chain_type_t fct, dpo_id_t *dpo)
int fib_path_recursive_loop_detect(fib_node_index_t path_index, fib_node_index_t **entry_indicies)
Definition: fib_path.c:1713
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:273
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.
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:480
u32 flags
Definition: vhost-user.h:77
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:680
void fib_path_destroy(fib_node_index_t path_index)
Definition: fib_path.c:1437
int fib_path_cmp_w_route_path(fib_node_index_t path_index, const fib_route_path_t *rpath)
Definition: fib_path.c:1605
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