FD.io VPP  v17.07.01-10-g3be13f0
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 {
119 #if CLIB_DEBUG > 0
121 #endif
122  return ((fib_path_list_t*)node);
123 }
124 
125 static fib_node_index_t
127 {
128  return (path_list - fib_path_list_pool);
129 }
130 
131 static u8 *
132 format_fib_path_list (u8 * s, va_list * args)
133 {
135  fib_node_index_t *path_index;
136  fib_path_list_t *path_list;
137 
138  path_list = va_arg (*args, fib_path_list_t *);
139 
140  s = format (s, " index:%u", fib_path_list_get_index(path_list));
141  s = format (s, " locks:%u", path_list->fpl_node.fn_locks);
142 
143  if (FIB_PATH_LIST_FLAG_NONE != path_list->fpl_flags)
144  {
145  s = format (s, " flags:");
147  {
148  if ((1<<attr) & path_list->fpl_flags)
149  {
150  s = format (s, "%s,", fib_path_list_attr_names[attr]);
151  }
152  }
153  }
154  s = format (s, " %U\n", format_fib_urpf_list, path_list->fpl_urpf);
155 
156  vec_foreach (path_index, path_list->fpl_paths)
157  {
158  s = fib_path_format(*path_index, s);
159  s = format(s, "\n");
160  }
161 
162  return (s);
163 }
164 
165 u8 *
167  u8 * s)
168 {
169  fib_path_list_t *path_list;
170 
171  path_list = fib_path_list_get(path_list_index);
172 
173  return (format(s, "%U", format_fib_path_list, path_list));
174 }
175 
176 static uword
178 {
179  uword old_path_list_hash, new_path_list_hash, path_hash;
180  fib_node_index_t *path_index;
181 
182  ASSERT(path_list);
183 
184  new_path_list_hash = old_path_list_hash = vec_len(path_list->fpl_paths);
185 
186  vec_foreach (path_index, path_list->fpl_paths)
187  {
188  path_hash = fib_path_hash(*path_index);
189 #if uword_bits == 64
190  hash_mix64(path_hash, old_path_list_hash, new_path_list_hash);
191 #else
192  hash_mix32(path_hash, old_path_list_hash, new_path_list_hash);
193 #endif
194  }
195 
196  return (new_path_list_hash);
197 }
198 
201 {
202  return 1 + 2*index;
203 }
204 
207 {
208  return key & 1;
209 }
210 
213 {
215  return key / 2;
216 }
217 
218 static fib_path_list_t*
220 {
221  fib_path_list_t *path_list;
222 
224  {
225  fib_node_index_t path_list_index;
226 
227  path_list_index = fib_path_list_db_hash_key_2_index(key);
228  path_list = fib_path_list_get(path_list_index);
229  }
230  else
231  {
232  path_list = uword_to_pointer (key, fib_path_list_t *);
233  }
234 
235  return (path_list);
236 }
237 
238 static uword
240  uword key)
241 {
242  fib_path_list_t *path_list;
243 
244  path_list = fib_path_list_db_get_from_hash_key(key);
245 
246  return (fib_path_list_hash(path_list));
247 }
248 
249 static uword
251  uword key1,
252  uword key2)
253 {
254  fib_path_list_t *path_list1, *path_list2;
255 
256  path_list1 = fib_path_list_db_get_from_hash_key(key1);
257  path_list2 = fib_path_list_db_get_from_hash_key(key2);
258 
259  return (fib_path_list_hash(path_list1) ==
260  fib_path_list_hash(path_list2));
261 }
262 
263 static fib_node_index_t
265 {
266  uword *p;
267 
268  p = hash_get(fib_path_list_db, path_list);
269 
270  if (NULL != p)
271  {
272  return p[0];
273  }
274 
275  return (FIB_NODE_INDEX_INVALID);
276 }
277 
278 static void
280 {
281  fib_path_list_t *path_list;
282 
283  path_list = fib_path_list_get(path_list_index);
284 
286 
288  fib_path_list_db_hash_key_from_index(path_list_index),
289  path_list_index);
290 
291  FIB_PATH_LIST_DBG(path_list, "DB-inserted");
292 }
293 
294 static void
296 {
297  fib_path_list_t *path_list;
298 
299  path_list = fib_path_list_get(path_list_index);
300 
302 
304  fib_path_list_db_hash_key_from_index(path_list_index));
305 
306  FIB_PATH_LIST_DBG(path_list, "DB-removed");
307 }
308 
309 static void
311 {
312  fib_node_index_t *path_index;
313 
314  FIB_PATH_LIST_DBG(path_list, "destroy");
315 
316  vec_foreach (path_index, path_list->fpl_paths)
317  {
318  fib_path_destroy(*path_index);
319  }
320 
321  vec_free(path_list->fpl_paths);
322  fib_urpf_list_unlock(path_list->fpl_urpf);
323 
324  fib_node_deinit(&path_list->fpl_node);
325  pool_put(fib_path_list_pool, path_list);
326 }
327 
328 static void
330 {
331  fib_path_list_t *path_list;
332 
333  path_list = fib_path_list_from_fib_node(node);
334 
335  FIB_PATH_LIST_DBG(path_list, "last-lock");
336 
337  if (path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED)
338  {
340  }
341  fib_path_list_destroy(path_list);
342 }
343 
344 /*
345  * fib_path_mk_lb
346  *
347  * update the multipath adj this path-list will contribute to its
348  * children's forwarding.
349  */
350 static void
353  dpo_id_t *dpo)
354 {
355  load_balance_path_t *nhs;
356  fib_node_index_t *path_index;
357 
358  nhs = NULL;
359 
360  if (!dpo_id_is_valid(dpo))
361  {
362  /*
363  * first time create
364  */
365  dpo_set(dpo,
370  0 /* FIXME FLOW HASH */));
371  }
372 
373  /*
374  * We gather the DPOs from resolved paths.
375  */
376  vec_foreach (path_index, path_list->fpl_paths)
377  {
378  nhs = fib_path_append_nh_for_multipath_hash(*path_index,
379  fct,
380  nhs);
381  }
382 
383  /*
384  * Path-list load-balances, which if used, would be shared and hence
385  * never need a load-balance map.
386  */
388 
389  FIB_PATH_LIST_DBG(path_list, "mk lb: %d", dpo->dpoi_index);
390 
391  vec_free(nhs);
392 }
393 
394 /**
395  * @brief [re]build the path list's uRPF list
396  */
397 static void
399 {
400  fib_node_index_t *path_index;
401 
402  /*
403  * ditch the old one. by iterating through all paths we are going
404  * to re-find all the adjs that were in the old one anyway. If we
405  * keep the old one, then the |sort|uniq requires more work.
406  * All users of the RPF list have their own lock, so we can release
407  * immediately.
408  */
409  fib_urpf_list_unlock(path_list->fpl_urpf);
410  path_list->fpl_urpf = fib_urpf_list_alloc_and_lock();
411 
412  vec_foreach (path_index, path_list->fpl_paths)
413  {
414  fib_path_contribute_urpf(*path_index, path_list->fpl_urpf);
415  }
416 
417  fib_urpf_list_bake(path_list->fpl_urpf);
418 }
419 
420 /**
421  * @brief Contribute (add) this path list's uRPF list. This allows the child
422  * to construct an aggregate list.
423  */
424 void
426  index_t urpf)
427 {
428  fib_path_list_t *path_list;
429 
430  path_list = fib_path_list_get(path_list_index);
431 
432  fib_urpf_list_combine(urpf, path_list->fpl_urpf);
433 }
434 
435 /**
436  * @brief Return the the child the RPF list pre-built for this path list
437  */
438 index_t
440 {
441  fib_path_list_t *path_list;
442 
443  path_list = fib_path_list_get(path_list_index);
444 
445  return (path_list->fpl_urpf);
446 }
447 
448 /*
449  * fib_path_list_back_walk
450  *
451  * Called from one of this path-list's paths to progate
452  * a back walk
453  */
454 void
457 {
458  fib_path_list_t *path_list;
459 
460  path_list = fib_path_list_get(path_list_index);
461 
462  fib_path_list_mk_urpf(path_list);
463 
464  /*
465  * propagate the backwalk further
466  */
467  if (path_list->fpl_flags & FIB_PATH_LIST_FLAG_POPULAR)
468  {
469  /*
470  * many children. schedule a async walk
471  */
473  path_list_index,
475  ctx);
476  }
477  else
478  {
479  /*
480  * only a few children. continue the walk synchronously
481  */
482  fib_walk_sync(FIB_NODE_TYPE_PATH_LIST, path_list_index, ctx);
483  }
484 }
485 
486 /*
487  * fib_path_list_back_walk_notify
488  *
489  * A back walk has reach this path-list.
490  */
494 {
495  /*
496  * the path-list is not a direct child of any other node type
497  * paths, which do not change thier to-list-mapping, save the
498  * list they are a member of, and invoke the BW function directly.
499  */
500  ASSERT(0);
501 
503 }
504 
505 /*
506  * Display the path-list memory usage
507  */
508 static void
510 {
511  fib_show_memory_usage("Path-list",
512  pool_elts(fib_path_list_pool),
513  pool_len(fib_path_list_pool),
514  sizeof(fib_path_list_t));
516 }
517 
518 /*
519  * The FIB path-list's graph node virtual function table
520  */
521 static const fib_node_vft_t fib_path_list_vft = {
523  .fnv_last_lock = fib_path_list_last_lock_gone,
524  .fnv_back_walk = fib_path_list_back_walk_notify,
525  .fnv_mem_show = fib_path_list_memory_show,
526 };
527 
528 static inline fib_path_list_t *
530 {
531  fib_path_list_t *path_list;
532 
533  pool_get(fib_path_list_pool, path_list);
534  memset(path_list, 0, sizeof(*path_list));
535 
536  fib_node_init(&path_list->fpl_node,
538  path_list->fpl_urpf = INDEX_INVALID;
539  path_list->fpl_paths = NULL;
540 
541  *path_list_index = fib_path_list_get_index(path_list);
542 
543  FIB_PATH_LIST_DBG(path_list, "alloc");
544 
545  return (path_list);
546 }
547 
548 static fib_path_list_t *
550 {
551  fib_node_index_t *path_index, *paths, path_list_index;
552 
554 
555  /*
556  * resolving a path-list is a recursive action. this means more path
557  * lists can be created during this call, and hence this path-list
558  * can be realloc'd. so we work with copies.
559  * this function is called only once per-path list, so its no great overhead.
560  */
561  path_list_index = fib_path_list_get_index(path_list);
562  paths = vec_dup(path_list->fpl_paths);
563 
564  vec_foreach (path_index, paths)
565  {
566  fib_path_resolve(*path_index);
567  }
568 
569  vec_free(paths);
570  path_list = fib_path_list_get(path_list_index);
571 
572  FIB_PATH_LIST_DBG(path_list, "resovled");
573 
574  if (!(path_list->fpl_flags & FIB_PATH_LIST_FLAG_NO_URPF))
575  {
576  fib_path_list_mk_urpf(path_list);
577  }
578  return (path_list);
579 }
580 
581 u32
583 {
584  fib_path_list_t *path_list;
585 
586  path_list = fib_path_list_get(path_list_index);
587 
588  return (vec_len(path_list->fpl_paths));
589 }
590 
591 
592 u32
594 {
595  fib_node_index_t *path_index;
596  fib_path_list_t *path_list;
597  u32 sw_if_index;
598 
599  path_list = fib_path_list_get(path_list_index);
600 
601  sw_if_index = ~0;
602  vec_foreach (path_index, path_list->fpl_paths)
603  {
604  sw_if_index = fib_path_get_resolving_interface(*path_index);
605  if (~0 != sw_if_index)
606  {
607  return (sw_if_index);
608  }
609  }
610 
611  return (sw_if_index);
612 }
613 
616 {
617  fib_path_list_t *path_list;
618 
619  path_list = fib_path_list_get(path_list_index);
620 
621  /*
622  * we don't support a mix of path protocols, so we can return the proto
623  * of the first
624  */
625  return (fib_path_get_proto(path_list->fpl_paths[0]));
626 }
627 
628 int
630 {
631  fib_path_list_t *path_list;
632 
633  path_list = fib_path_list_get(path_list_index);
634 
635  return (path_list->fpl_flags & FIB_PATH_LIST_FLAG_LOOPED);
636 }
637 
638 int
640 {
641  fib_path_list_t *path_list;
642 
643  path_list = fib_path_list_get(path_list_index);
644 
645  return (path_list->fpl_flags & FIB_PATH_LIST_FLAG_POPULAR);
646 }
647 
650 {
651  /*
652  * we do no share drop nor exclusive path-lists
653  */
654  if (flags & FIB_PATH_LIST_FLAG_DROP ||
656  {
657  flags &= ~FIB_PATH_LIST_FLAG_SHARED;
658  }
659 
660  return (flags);
661 }
662 
665  const fib_route_path_t *rpaths)
666 {
667  fib_node_index_t path_list_index, old_path_list_index;
668  fib_path_list_t *path_list;
669  int i;
670 
671  flags = fib_path_list_flags_fixup(flags);
672  path_list = fib_path_list_alloc(&path_list_index);
673  path_list->fpl_flags = flags;
674 
675  if (NULL != rpaths)
676  {
677  vec_foreach_index(i, rpaths)
678  {
679  vec_add1(path_list->fpl_paths,
680  fib_path_create(path_list_index,
681  &rpaths[i]));
682  }
683  }
684 
685  /*
686  * If a shared path list is requested, consult the DB for a match
687  */
688  if (flags & FIB_PATH_LIST_FLAG_SHARED)
689  {
690  /*
691  * check for a matching path-list in the DB.
692  * If we find one then we can return the existing one and destroy the
693  * new one just created.
694  */
695  old_path_list_index = fib_path_list_db_find(path_list);
696  if (FIB_NODE_INDEX_INVALID != old_path_list_index)
697  {
698  fib_path_list_destroy(path_list);
699 
700  path_list_index = old_path_list_index;
701  }
702  else
703  {
704  /*
705  * if there was not a matching path-list, then this
706  * new one will need inserting into the DB and resolving.
707  */
708  fib_path_list_db_insert(path_list_index);
709  path_list = fib_path_list_resolve(path_list);
710  }
711  }
712  else
713  {
714  /*
715  * no shared path list requested. resolve and use the one
716  * just created.
717  */
718  path_list = fib_path_list_resolve(path_list);
719  }
720 
721  return (path_list_index);
722 }
723 
724 static fib_path_cfg_flags_t
726 {
728 
729  if (plf & FIB_PATH_LIST_FLAG_DROP)
730  {
732  }
734  {
736  }
737  if (plf & FIB_PATH_LIST_FLAG_LOCAL)
738  {
740  }
741 
742  return (pf);
743 }
744 
748  const dpo_id_t *dpo)
749 {
750  fib_node_index_t path_index, path_list_index;
751  fib_path_list_t *path_list;
752 
753  path_list = fib_path_list_alloc(&path_list_index);
754  path_list->fpl_flags = flags;
755 
756  path_index =
757  fib_path_create_special(path_list_index,
758  nh_proto,
760  dpo);
761  vec_add1(path_list->fpl_paths, path_index);
762 
763  /*
764  * we don't share path-lists. we can do PIC on them so why bother.
765  */
766  path_list = fib_path_list_resolve(path_list);
767 
768  return (path_list_index);
769 }
770 
771 /*
772  * return the index info the path-lists's vector of paths, of the matching path.
773  * ~0 if not found
774  */
775 u32
777  const fib_route_path_t *rpath)
778 {
779  fib_path_list_t *path_list;
780  u32 ii;
781 
782  path_list = fib_path_list_get(path_list_index);
783 
784  vec_foreach_index (ii, path_list->fpl_paths)
785  {
786  if (!fib_path_cmp_w_route_path(path_list->fpl_paths[ii], rpath))
787  {
788  return (ii);
789  }
790  }
791  return (~0);
792 }
793 
794 
795 /*
796  * fib_path_list_copy_and_path_add
797  *
798  * Create a copy of a path-list and append one more path to it.
799  * The path-list returned could either have been newly created, or
800  * can be a shared path-list from the data-base.
801  */
804  const fib_route_path_t *rpaths)
805 {
806  fib_node_index_t new_path_index, *orig_path_index;
807  fib_path_list_t *path_list;
808 
809  /*
810  * alloc the new list before we retrieve the old one, lest
811  * the alloc result in a realloc
812  */
813  path_list = fib_path_list_get(path_list_index);
814 
815  ASSERT(1 == vec_len(rpaths));
816  ASSERT(!(path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED));
817 
818  FIB_PATH_LIST_DBG(orig_path_list, "path-add");
819 
820  new_path_index = fib_path_create(path_list_index,
821  rpaths);
822 
823  vec_foreach (orig_path_index, path_list->fpl_paths)
824  {
825  /*
826  * don't add duplicate paths
827  */
828  if (0 == fib_path_cmp(new_path_index, *orig_path_index))
829  {
830  fib_path_destroy(new_path_index);
831  return (*orig_path_index);
832  }
833  }
834 
835  /*
836  * Add the new path - no sort, no sharing, no key..
837  */
838  vec_add1(path_list->fpl_paths, new_path_index);
839 
840  FIB_PATH_LIST_DBG(path_list, "path-added");
841 
842  /*
843  * no shared path list requested. resolve and use the one
844  * just created.
845  */
846  fib_path_resolve(new_path_index);
847 
848  return (new_path_index);
849 }
850 
854  const fib_route_path_t *rpaths)
855 {
856  fib_node_index_t path_index, new_path_index, *orig_path_index;
857  fib_path_list_t *path_list, *orig_path_list;
858  fib_node_index_t exist_path_list_index;
859  fib_node_index_t path_list_index;
860  fib_node_index_t pi;
861 
862  ASSERT(1 == vec_len(rpaths));
863 
864  /*
865  * alloc the new list before we retrieve the old one, lest
866  * the alloc result in a realloc
867  */
868  path_list = fib_path_list_alloc(&path_list_index);
869 
870  orig_path_list = fib_path_list_get(orig_path_list_index);
871 
872  FIB_PATH_LIST_DBG(orig_path_list, "copy-add");
873 
874  flags = fib_path_list_flags_fixup(flags);
875  path_list->fpl_flags = flags;
876 
877  vec_validate(path_list->fpl_paths, vec_len(orig_path_list->fpl_paths));
878  pi = 0;
879 
880  new_path_index = fib_path_create(path_list_index,
881  rpaths);
882 
883  vec_foreach (orig_path_index, orig_path_list->fpl_paths)
884  {
885  /*
886  * don't add duplicate paths
887  * In the unlikely event the path is a duplicate, then we'll
888  * find a matching path-list later and this one will be toast.
889  */
890  if (0 != fib_path_cmp(new_path_index, *orig_path_index))
891  {
892  path_index = fib_path_copy(*orig_path_index, path_list_index);
893  path_list->fpl_paths[pi++] = path_index;
894  }
895  else
896  {
897  _vec_len(path_list->fpl_paths) = vec_len(orig_path_list->fpl_paths);
898  }
899  }
900 
901  path_list->fpl_paths[pi] = new_path_index;
902 
903  /*
904  * we sort the paths since the key for the path-list is
905  * the description of the paths it contains. The paths need to
906  * be sorted else this description will differ.
907  */
909 
910  FIB_PATH_LIST_DBG(path_list, "path-added");
911 
912  /*
913  * check for a matching path-list in the DB.
914  * If we find one then we can return the existing one and destroy the
915  * new one just created.
916  */
917  if (path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED)
918  {
919  exist_path_list_index = fib_path_list_db_find(path_list);
920  if (FIB_NODE_INDEX_INVALID != exist_path_list_index)
921  {
922  fib_path_list_destroy(path_list);
923 
924  path_list_index = exist_path_list_index;
925  }
926  else
927  {
928  /*
929  * if there was not a matching path-list, then this
930  * new one will need inserting into the DB and resolving.
931  */
932  fib_path_list_db_insert(path_list_index);
933 
934  path_list = fib_path_list_resolve(path_list);
935  }
936  }
937  else
938  {
939  /*
940  * no shared path list requested. resolve and use the one
941  * just created.
942  */
943  path_list = fib_path_list_resolve(path_list);
944  }
945 
946  return (path_list_index);
947 }
948 
949 /*
950  * fib_path_list_path_remove
951  */
954  const fib_route_path_t *rpaths)
955 {
956  fib_node_index_t match_path_index, tmp_path_index;
957  fib_path_list_t *path_list;
958  fib_node_index_t pi;
959 
960  path_list = fib_path_list_get(path_list_index);
961 
962  ASSERT(1 == vec_len(rpaths));
963  ASSERT(!(path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED));
964 
965  FIB_PATH_LIST_DBG(orig_path_list, "path-remove");
966 
967  /*
968  * create a representation of the path to be removed, so it
969  * can be used as a comparison object during the copy.
970  */
971  tmp_path_index = fib_path_create(path_list_index,
972  rpaths);
973  match_path_index = FIB_NODE_INDEX_INVALID;
974 
975  vec_foreach_index (pi, path_list->fpl_paths)
976  {
977  if (0 == fib_path_cmp(tmp_path_index,
978  path_list->fpl_paths[pi]))
979  {
980  /*
981  * match - remove it
982  */
983  match_path_index = path_list->fpl_paths[pi];
984  fib_path_destroy(match_path_index);
985  vec_del1(path_list->fpl_paths, pi);
986  }
987  }
988 
989  /*
990  * done with the temporary now
991  */
992  fib_path_destroy(tmp_path_index);
993 
994  return (match_path_index);
995 }
996 
997 /*
998  * fib_path_list_copy_and_path_remove
999  *
1000  * Copy the path-list excluding the path passed.
1001  * If the path is the last one, then the index reurned will be invalid.
1002  * i.e. the path-list is toast.
1003  */
1007  const fib_route_path_t *rpaths)
1008 {
1009  fib_node_index_t path_index, *orig_path_index, path_list_index, tmp_path_index;
1010  fib_path_list_t *path_list, *orig_path_list;
1011  fib_node_index_t pi;
1012 
1013  ASSERT(1 == vec_len(rpaths));
1014 
1015  path_list = fib_path_list_alloc(&path_list_index);
1016 
1017  flags = fib_path_list_flags_fixup(flags);
1018  orig_path_list = fib_path_list_get(orig_path_list_index);
1019 
1020  FIB_PATH_LIST_DBG(orig_path_list, "copy-remove");
1021 
1022  path_list->fpl_flags = flags;
1023  /*
1024  * allocate as many paths as we might need in one go, rather than
1025  * using vec_add to do a few at a time.
1026  */
1027  if (vec_len(orig_path_list->fpl_paths) > 1)
1028  {
1029  vec_validate(path_list->fpl_paths, vec_len(orig_path_list->fpl_paths) - 2);
1030  }
1031  pi = 0;
1032 
1033  /*
1034  * create a representation of the path to be removed, so it
1035  * can be used as a comparison object during the copy.
1036  */
1037  tmp_path_index = fib_path_create(path_list_index,
1038  rpaths);
1039 
1040  vec_foreach (orig_path_index, orig_path_list->fpl_paths)
1041  {
1042  if (0 != fib_path_cmp(tmp_path_index, *orig_path_index)) {
1043  path_index = fib_path_copy(*orig_path_index, path_list_index);
1044  if (pi < vec_len(path_list->fpl_paths))
1045  {
1046  path_list->fpl_paths[pi++] = path_index;
1047  }
1048  else
1049  {
1050  /*
1051  * this is the unlikely case that the path being
1052  * removed does not match one in the path-list, so
1053  * we end up with as many paths as we started with.
1054  * the paths vector was sized above with the expectation
1055  * that we would have 1 less.
1056  */
1057  vec_add1(path_list->fpl_paths, path_index);
1058  }
1059  }
1060  }
1061 
1062  /*
1063  * done with the temporary now
1064  */
1065  fib_path_destroy(tmp_path_index);
1066 
1067  /*
1068  * if there are no paths, then the new path-list is aborted
1069  */
1070  if (0 == vec_len(path_list->fpl_paths)) {
1071  FIB_PATH_LIST_DBG(path_list, "last-path-removed");
1072 
1073  fib_path_list_destroy(path_list);
1074 
1075  path_list_index = FIB_NODE_INDEX_INVALID;
1076  } else {
1077  /*
1078  * we sort the paths since the key for the path-list is
1079  * the description of the paths it contains. The paths need to
1080  * be sorted else this description will differ.
1081  */
1083 
1084  /*
1085  * If a shared path list is requested, consult the DB for a match
1086  */
1087  if (path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED)
1088  {
1089  fib_node_index_t exist_path_list_index;
1090 
1091  /*
1092  * check for a matching path-list in the DB.
1093  * If we find one then we can return the existing one and destroy the
1094  * new one just created.
1095  */
1096  exist_path_list_index = fib_path_list_db_find(path_list);
1097  if (FIB_NODE_INDEX_INVALID != exist_path_list_index)
1098  {
1099  fib_path_list_destroy(path_list);
1100 
1101  path_list_index = exist_path_list_index;
1102  }
1103  else
1104  {
1105  /*
1106  * if there was not a matching path-list, then this
1107  * new one will need inserting into the DB and resolving.
1108  */
1109  fib_path_list_db_insert(path_list_index);
1110 
1111  path_list = fib_path_list_resolve(path_list);
1112  }
1113  }
1114  else
1115  {
1116  /*
1117  * no shared path list requested. resolve and use the one
1118  * just created.
1119  */
1120  path_list = fib_path_list_resolve(path_list);
1121  }
1122  }
1123 
1124  return (path_list_index);
1125 }
1126 
1127 /*
1128  * fib_path_list_contribute_forwarding
1129  *
1130  * Return the index of a load-balance that user of this path-list should
1131  * use for forwarding
1132  */
1133 void
1136  dpo_id_t *dpo)
1137 {
1138  fib_path_list_t *path_list;
1139 
1140  path_list = fib_path_list_get(path_list_index);
1141 
1142  fib_path_list_mk_lb(path_list, fct, dpo);
1143 }
1144 
1145 /*
1146  * fib_path_list_get_adj
1147  *
1148  * Return the index of a adjacency for the first path that user of this
1149  * path-list should use for forwarding
1150  */
1154 {
1155  fib_path_list_t *path_list;
1156 
1157  path_list = fib_path_list_get(path_list_index);
1158  return (fib_path_get_adj(path_list->fpl_paths[0]));
1159 }
1160 
1161 int
1163  fib_node_index_t **entry_indicies)
1164 {
1165  fib_node_index_t *path_index;
1166  int is_looped, list_looped;
1167  fib_path_list_t *path_list;
1168 
1169  list_looped = 0;
1170  path_list = fib_path_list_get(path_list_index);
1171 
1172  vec_foreach (path_index, path_list->fpl_paths)
1173  {
1174  fib_node_index_t *copy, **copy_ptr;
1175 
1176  /*
1177  * we need a copy of the nodes visited so that when we add entries
1178  * we explore on the nth path and a looped is detected, those entries
1179  * are not again searched for n+1 path and so finding a loop that does
1180  * not exist.
1181  */
1182  copy = vec_dup(*entry_indicies);
1183  copy_ptr = &copy;
1184 
1185  is_looped = fib_path_recursive_loop_detect(*path_index, copy_ptr);
1186  list_looped += is_looped;
1187  }
1188 
1189  FIB_PATH_LIST_DBG(path_list, "loop-detect: eval:%d", eval);
1190 
1191  if (list_looped)
1192  {
1193  path_list->fpl_flags |= FIB_PATH_LIST_FLAG_LOOPED;
1194  }
1195  else
1196  {
1197  path_list->fpl_flags &= ~FIB_PATH_LIST_FLAG_LOOPED;
1198  }
1199 
1200  return (list_looped);
1201 }
1202 
1203 u32
1205  fib_node_type_t child_type,
1206  fib_node_index_t child_index)
1207 {
1208  u32 sibling;
1209 
1211  path_list_index,
1212  child_type,
1213  child_index);
1214 
1216  path_list_index))
1217  {
1218  /*
1219  * Set the popular flag on the path-list once we pass the magic
1220  * threshold. then walk children to update.
1221  * We don't undo this action. The rational being that the number
1222  * of entries using this prefix is large enough such that it is a
1223  * non-trival amount of effort to converge them. If we get into the
1224  * situation where we are adding and removing entries such that we
1225  * flip-flop over the threshold, then this non-trivial work is added
1226  * to each of those routes adds/deletes - not a situation we want.
1227  */
1228  fib_node_back_walk_ctx_t ctx = {
1230  };
1231  fib_path_list_t *path_list;
1232 
1233  path_list = fib_path_list_get(path_list_index);
1234  path_list->fpl_flags |= FIB_PATH_LIST_FLAG_POPULAR;
1235 
1236  fib_walk_sync(FIB_NODE_TYPE_PATH_LIST, path_list_index, &ctx);
1237  }
1238 
1239  return (sibling);
1240 }
1241 
1242 void
1244  u32 si)
1245 {
1247  path_list_index,
1248  si);
1249 }
1250 
1251 void
1253 {
1254  fib_path_list_t *path_list;
1255 
1256  if (FIB_NODE_INDEX_INVALID != path_list_index)
1257  {
1258  path_list = fib_path_list_get(path_list_index);
1259 
1260  fib_node_lock(&path_list->fpl_node);
1261  FIB_PATH_LIST_DBG(path_list, "lock");
1262  }
1263 }
1264 
1265 void
1267 {
1268  fib_path_list_t *path_list;
1269 
1270  if (FIB_NODE_INDEX_INVALID != path_list_index)
1271  {
1272  path_list = fib_path_list_get(path_list_index);
1273  FIB_PATH_LIST_DBG(path_list, "unlock");
1274 
1275  fib_node_unlock(&path_list->fpl_node);
1276  }
1277 }
1278 
1279 u32
1281 {
1282  return (pool_elts(fib_path_list_pool));
1283 }
1284 
1285 u32
1287 {
1288  return (hash_elts(fib_path_list_db));
1289 }
1290 
1291 void
1294  void *ctx)
1295 {
1296  fib_node_index_t *path_index;
1297  fib_path_list_t *path_list;
1298 
1299  path_list = fib_path_list_get(path_list_index);
1300 
1301  vec_foreach(path_index, path_list->fpl_paths)
1302  {
1303  if (FIB_PATH_LIST_WALK_STOP == func(path_list_index,
1304  *path_index,
1305  ctx))
1306  break;
1307  }
1308 }
1309 
1310 
1311 void
1313 {
1314  fib_node_register_type (FIB_NODE_TYPE_PATH_LIST, &fib_path_list_vft);
1315 
1316  fib_path_list_db = hash_create2 (/* elts */ 0,
1317  /* user */ 0,
1318  /* value_bytes */ sizeof (fib_node_index_t),
1321  /* format pair/arg */
1322  0, 0);
1323 }
1324 
1325 static clib_error_t *
1327  unformat_input_t * input,
1328  vlib_cli_command_t * cmd)
1329 {
1330  fib_path_list_t *path_list;
1331  fib_node_index_t pli;
1332 
1333  if (unformat (input, "%d", &pli))
1334  {
1335  /*
1336  * show one in detail
1337  */
1338  if (!pool_is_free_index(fib_path_list_pool, pli))
1339  {
1340  path_list = fib_path_list_get(pli);
1341  u8 *s = fib_path_list_format(pli, NULL);
1342  s = format(s, "children:");
1343  s = fib_node_children_format(path_list->fpl_node.fn_children, s);
1344  vlib_cli_output (vm, "%s", s);
1345  vec_free(s);
1346  }
1347  else
1348  {
1349  vlib_cli_output (vm, "path list %d invalid", pli);
1350  }
1351  }
1352  else
1353  {
1354  /*
1355  * show all
1356  */
1357  vlib_cli_output (vm, "FIB Path Lists");
1358  pool_foreach(path_list, fib_path_list_pool,
1359  ({
1360  vlib_cli_output (vm, "%U", format_fib_path_list, path_list);
1361  }));
1362  }
1363  return (NULL);
1364 }
1365 
1366 VLIB_CLI_COMMAND (show_fib_path_list, static) = {
1367  .path = "show fib path-lists",
1368  .function = show_fib_path_list_command,
1369  .short_help = "show fib path-lists",
1370 };
#define vec_validate(V, I)
Make sure vector is long enough for given index (no header, unspecified alignment) ...
Definition: vec.h:436
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:1550
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:1251
fib_protocol_t fib_path_get_proto(fib_node_index_t path_index)
Definition: fib_path.c:2149
#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)
enum fib_node_type_t_ fib_node_type_t
The types of nodes in a FIB graph.
#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:1772
A representation of a path as described by a route producer.
Definition: fib_types.h:336
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:1362
void fib_node_init(fib_node_t *node, fib_node_type_t type)
Definition: fib_node.c:183
u32 fib_path_list_get_resolving_interface(fib_node_index_t path_list_index)
static int dpo_id_is_valid(const dpo_id_t *dpoi)
Return true if the DPO object is valid, i.e.
Definition: dpo.h:191
u8 * format_fib_urpf_list(u8 *s, va_list args)
Definition: fib_urpf_list.c:25
#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 * 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:308
fib_protocol_t fib_path_list_get_proto(fib_node_index_t path_list_index)
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: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:198
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:200
int fib_path_cmp_for_sort(void *v1, void *v2)
Definition: fib_path.c:1344
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:121
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
enum fib_protocol_t_ fib_protocol_t
Protocol Type.
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:2027
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:96
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:58
index_t load_balance_create(u32 n_buckets, dpo_proto_t lb_proto, flow_hash_config_t fhc)
Definition: load_balance.c:193
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 pool_foreach(VAR, POOL, BODY)
Iterate through pool.
Definition: pool.h:376
#define always_inline
Definition: clib.h:84
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
fib_node_index_t fib_path_create_special(fib_node_index_t pl_index, fib_protocol_t nh_proto, fib_path_cfg_flags_t flags, const dpo_id_t *dpo)
Definition: fib_path.c:1152
void fib_path_list_contribute_forwarding(fib_node_index_t path_list_index, fib_forward_chain_type_t fct, dpo_id_t *dpo)
fib_node_index_t fib_path_copy(fib_node_index_t path_index, fib_node_index_t path_list_index)
Definition: fib_path.c:1197
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:221
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:483
enum fib_path_list_attribute_t_ fib_path_list_attribute_t
Enumeration of path-list flags.
static fib_path_list_t * fib_path_list_alloc(fib_node_index_t *path_list_index)
u32 fib_path_list_db_size(void)
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:152
fib_node_bw_reason_flag_t fnbw_reason
The reason/trigger for the backwalk.
Definition: fib_node.h:196
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:397
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)
void fib_node_lock(fib_node_t *node)
Definition: fib_node.c:204
struct _unformat_input_t unformat_input_t
load-balancing over a choice of [un]equal cost paths
Definition: dpo.h:104
adj_index_t fib_path_get_adj(fib_node_index_t path_index)
Definition: fib_path.c:1739
#define pool_put(P, E)
Free an object E in pool P.
Definition: pool.h:241
#define vec_dup(V)
Return copy of vector (no header, no alignment)
Definition: vec.h:374
#define vec_del1(v, i)
Delete the element at index I.
Definition: vec.h:805
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:284
An node in the FIB graph.
Definition: fib_node.h:279
void fib_node_unlock(fib_node_t *node)
Definition: fib_node.c:210
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
Vector of nodes that depend upon/use/share this node.
Definition: fib_node.h:296
static void fib_path_list_last_lock_gone(fib_node_t *node)
#define hash_mix64(a0, b0, c0)
Definition: hash.h:507
int fib_path_list_is_popular(fib_node_index_t path_list_index)
u8 * fib_path_format(fib_node_index_t pi, u8 *s)
Definition: fib_path.c:489
#define vec_free(V)
Free vector&#39;s memory (no header).
Definition: vec.h:340
#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 u8 * format_fib_path_list(u8 *s, va_list *args)
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:267
#define hash_mix32(a0, b0, c0)
Definition: hash.h:515
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:28
#define pool_is_free_index(P, I)
Use free bitmap to query whether given index is free.
Definition: pool.h:238
u32 fib_node_get_n_children(fib_node_type_t parent_type, fib_node_index_t parent_index)
Definition: fib_node.c:140
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:159
void fib_path_list_unlock(fib_node_index_t path_list_index)
#define hash_create2(_elts, _user, _value_bytes,_key_sum, _key_equal,_format_pair, _format_pair_arg)
Definition: hash.h:470
Context passed between object during a back walk.
Definition: fib_node.h:192
#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)
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:121
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
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:1709
index_t dpoi_index
the index of objects of that type
Definition: dpo.h:168
#define FIB_NODE_INDEX_INVALID
Definition: fib_types.h:29
#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:302
#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 * 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:960
fib_node_index_t fib_path_create(fib_node_index_t pl_index, const fib_route_path_t *rpath)
Definition: fib_path.c:1050
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.
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:1469
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:266
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)
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
u32 flags
Definition: vhost-user.h:76
u8 * fib_node_children_format(fib_node_list_t list, u8 *s)
Definition: fib_node.c:174
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:1230
fib_node_index_t fib_path_list_create_special(fib_protocol_t nh_proto, fib_path_list_flags_t flags, const dpo_id_t *dpo)
int fib_path_cmp_w_route_path(fib_node_index_t path_index, const fib_route_path_t *rpath)
Definition: fib_path.c:1374
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:109