FD.io VPP  v19.08-24-ge6a5712
Vector Packet Processing
fib_path_list.c
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2016 Cisco and/or its affiliates.
3  * Licensed under the Apache License, Version 2.0 (the "License");
4  * you may not use this file except in compliance with the License.
5  * You may obtain a copy of the License at:
6  *
7  * http://www.apache.org/licenses/LICENSE-2.0
8  *
9  * Unless required by applicable law or agreed to in writing, software
10  * distributed under the License is distributed on an "AS IS" BASIS,
11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12  * See the License for the specific language governing permissions and
13  * limitations under the License.
14  */
15 
16 #include <vppinfra/mhash.h>
17 #include <vnet/ip/ip.h>
18 #include <vnet/adj/adj.h>
19 #include <vnet/dpo/load_balance.h>
21 
22 #include <vnet/fib/fib_path_list.h>
23 #include <vnet/fib/fib_internal.h>
24 #include <vnet/fib/fib_node_list.h>
25 #include <vnet/fib/fib_walk.h>
26 #include <vnet/fib/fib_urpf_list.h>
27 #include <vnet/fib/fib_path_ext.h>
28 #include <vnet/fib/fib_table.h>
29 
30 /**
31  * The magic number of child entries that make a path-list popular.
32  * There's a trade-off here between convergnece and forwarding speed.
33  * Popular path-lists generate load-balance maps for the entries that
34  * use them. If the map is present there is a switch path cost to indirect
35  * through the map - this indirection provides the fast convergence - so
36  * without the map convergence is slower.
37  */
38 #define FIB_PATH_LIST_POPULAR 64
39 
40 /**
41  * FIB path-list
42  * A representation of the list/set of path trough which a prefix is reachable
43  */
44 typedef struct fib_path_list_t_ {
45  /**
46  * A path-list is a node in the FIB graph.
47  */
49 
50  /**
51  * Flags on the path-list
52  */
54 
55  /**
56  * Vector of paths indicies for all configured paths.
57  * For shareable path-lists this list MUST not change.
58  */
60 
61  /**
62  * the RPF list calculated for this path list
63  */
65 
66  /**
67  * Hash table of paths. valid only with INDEXED flag
68  */
71 
72 /*
73  * Array of strings/names for the FIB sources
74  */
76 
77 /*
78  * The memory pool from which we allocate all the path-lists
79  */
81 
82 /*
83  * The data-base of shared path-lists
84  */
86 
87 /**
88  * the logger
89  */
91 
92 /*
93  * Debug macro
94  */
95 #define FIB_PATH_LIST_DBG(_pl, _fmt, _args...) \
96 { \
97  vlib_log_debug(fib_path_list_logger, \
98  "[%U]:" _fmt, \
99  format_fib_path_list, \
100  fib_path_list_get_index(_pl), 0, \
101  ##_args); \
102 }
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,
163  s = format(s, "\n");
164  }
165 
166  return (s);
167 }
168 
169 u8 *
171  u8 * s)
172 {
173  return (format(s, "%U", format_fib_path_list, path_list_index, 4));
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 =
185  old_path_list_hash =
186  (vec_len(path_list->fpl_paths) << 16 |
187  (path_list->fpl_flags & FIB_PATH_LIST_KEY_FLAGS));
188 
189  vec_foreach (path_index, path_list->fpl_paths)
190  {
191  path_hash = fib_path_hash(*path_index);
192 #if uword_bits == 64
193  hash_mix64(path_hash, old_path_list_hash, new_path_list_hash);
194 #else
195  hash_mix32(path_hash, old_path_list_hash, new_path_list_hash);
196 #endif
197  }
198 
199  return (new_path_list_hash);
200 }
201 
204 {
205  return 1 + 2*index;
206 }
207 
210 {
211  return key & 1;
212 }
213 
216 {
218  return key / 2;
219 }
220 
221 static fib_path_list_t*
223 {
224  fib_path_list_t *path_list;
225 
227  {
228  fib_node_index_t path_list_index;
229 
230  path_list_index = fib_path_list_db_hash_key_2_index(key);
231  path_list = fib_path_list_get(path_list_index);
232  }
233  else
234  {
235  path_list = uword_to_pointer (key, fib_path_list_t *);
236  }
237 
238  return (path_list);
239 }
240 
241 static uword
243  uword key)
244 {
245  fib_path_list_t *path_list;
246 
247  path_list = fib_path_list_db_get_from_hash_key(key);
248 
249  return (fib_path_list_hash(path_list));
250 }
251 
252 static uword
254  uword key1,
255  uword key2)
256 {
257  fib_path_list_t *path_list1, *path_list2;
258 
259  path_list1 = fib_path_list_db_get_from_hash_key(key1);
260  path_list2 = fib_path_list_db_get_from_hash_key(key2);
261 
262  return (fib_path_list_hash(path_list1) ==
263  fib_path_list_hash(path_list2));
264 }
265 
266 static fib_node_index_t
268 {
269  uword *p;
270 
271  p = hash_get(fib_path_list_db, path_list);
272 
273  if (NULL != p)
274  {
275  return p[0];
276  }
277 
278  return (FIB_NODE_INDEX_INVALID);
279 }
280 
281 static void
283 {
284  fib_path_list_t *path_list;
285 
286  path_list = fib_path_list_get(path_list_index);
287 
289 
291  fib_path_list_db_hash_key_from_index(path_list_index),
292  path_list_index);
293 
294  FIB_PATH_LIST_DBG(path_list, "DB-inserted");
295 }
296 
297 static void
299 {
300  fib_path_list_t *path_list;
301 
302  path_list = fib_path_list_get(path_list_index);
303 
305 
307  fib_path_list_db_hash_key_from_index(path_list_index));
308 
309  FIB_PATH_LIST_DBG(path_list, "DB-removed");
310 }
311 
312 static void
314 {
315  fib_node_index_t *path_index;
316 
317  FIB_PATH_LIST_DBG(path_list, "destroy");
318 
319  vec_foreach (path_index, path_list->fpl_paths)
320  {
321  fib_path_destroy(*path_index);
322  }
323 
324  vec_free(path_list->fpl_paths);
325  fib_urpf_list_unlock(path_list->fpl_urpf);
326 
327  fib_node_deinit(&path_list->fpl_node);
328  pool_put(fib_path_list_pool, path_list);
329 }
330 
331 static void
333 {
334  fib_path_list_t *path_list;
335 
336  path_list = fib_path_list_from_fib_node(node);
337 
338  FIB_PATH_LIST_DBG(path_list, "last-lock");
339 
340  if (path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED)
341  {
343  }
344  fib_path_list_destroy(path_list);
345 }
346 
349 {
351 
352  if (pl_flags & FIB_PATH_LIST_FWD_FLAG_STICKY)
353  {
354  lb_flags |= LOAD_BALANCE_ATTR_STICKY;
355  }
356  return (lb_flags);
357 }
358 
359 /*
360  * fib_path_mk_lb
361  *
362  * update the multipath adj this path-list will contribute to its
363  * children's forwarding.
364  */
365 static void
368  dpo_id_t *dpo,
370 {
371  fib_node_index_t *path_index;
373  dpo_proto_t dproto;
374 
375  nhs = NULL;
376  dproto = fib_forw_chain_type_to_dpo_proto(fct);
377 
378  /*
379  * We gather the DPOs from resolved paths.
380  */
381  vec_foreach (path_index, path_list->fpl_paths)
382  {
383  if ((flags & FIB_PATH_LIST_FWD_FLAG_STICKY) ||
384  fib_path_is_resolved(*path_index))
385  {
386  nhs = fib_path_append_nh_for_multipath_hash(*path_index,
387  fct, nhs);
388  }
389  }
390 
391  /*
392  * Path-list load-balances, which if used, would be shared and hence
393  * never need a load-balance map.
394  */
395  dpo_set(dpo,
397  dproto,
399  dproto,
403 
404  FIB_PATH_LIST_DBG(path_list, "mk lb: %d", dpo->dpoi_index);
405 
406  vec_free(nhs);
407 }
408 
409 /**
410  * @brief [re]build the path list's uRPF list
411  */
412 static void
414 {
415  fib_node_index_t *path_index;
416 
417  /*
418  * ditch the old one. by iterating through all paths we are going
419  * to re-find all the adjs that were in the old one anyway. If we
420  * keep the old one, then the |sort|uniq requires more work.
421  * All users of the RPF list have their own lock, so we can release
422  * immediately.
423  */
424  fib_urpf_list_unlock(path_list->fpl_urpf);
425  path_list->fpl_urpf = fib_urpf_list_alloc_and_lock();
426 
427  vec_foreach (path_index, path_list->fpl_paths)
428  {
429  fib_path_contribute_urpf(*path_index, path_list->fpl_urpf);
430  }
431 
432  fib_urpf_list_bake(path_list->fpl_urpf);
433 }
434 
435 /**
436  * @brief Contribute (add) this path list's uRPF list. This allows the child
437  * to construct an aggregate list.
438  */
439 void
441  index_t urpf)
442 {
443  fib_path_list_t *path_list;
444 
445  path_list = fib_path_list_get(path_list_index);
446 
447  fib_urpf_list_combine(urpf, path_list->fpl_urpf);
448 }
449 
450 /**
451  * @brief Return the the child the RPF list pre-built for this path list
452  */
453 index_t
455 {
456  fib_path_list_t *path_list;
457 
458  path_list = fib_path_list_get(path_list_index);
459 
460  return (path_list->fpl_urpf);
461 }
462 
463 /*
464  * fib_path_list_back_walk
465  *
466  * Called from one of this path-list's paths to progate
467  * a back walk
468  */
469 void
472 {
473  fib_path_list_t *path_list;
474 
475  path_list = fib_path_list_get(path_list_index);
476 
477  fib_path_list_mk_urpf(path_list);
478 
479  FIB_PATH_LIST_DBG(path_list, "bw:%U",
481 
482  /*
483  * propagate the backwalk further
484  */
485  if (path_list->fpl_flags & FIB_PATH_LIST_FLAG_POPULAR)
486  {
487  /*
488  * many children. schedule a async walk
489  */
491  path_list_index,
493  ctx);
494  }
495  else
496  {
497  /*
498  * only a few children. continue the walk synchronously
499  */
500  fib_walk_sync(FIB_NODE_TYPE_PATH_LIST, path_list_index, ctx);
501  }
502 }
503 
504 /*
505  * fib_path_list_back_walk_notify
506  *
507  * A back walk has reach this path-list.
508  */
512 {
513  /*
514  * the path-list is not a direct child of any other node type
515  * paths, which do not change thier to-list-mapping, save the
516  * list they are a member of, and invoke the BW function directly.
517  */
518  ASSERT(0);
519 
521 }
522 
523 /*
524  * Display the path-list memory usage
525  */
526 static void
528 {
529  fib_show_memory_usage("Path-list",
530  pool_elts(fib_path_list_pool),
531  pool_len(fib_path_list_pool),
532  sizeof(fib_path_list_t));
534 }
535 
536 /*
537  * The FIB path-list's graph node virtual function table
538  */
539 static const fib_node_vft_t fib_path_list_vft = {
541  .fnv_last_lock = fib_path_list_last_lock_gone,
542  .fnv_back_walk = fib_path_list_back_walk_notify,
543  .fnv_mem_show = fib_path_list_memory_show,
544 };
545 
546 static inline fib_path_list_t *
548 {
549  fib_path_list_t *path_list;
550 
551  pool_get(fib_path_list_pool, path_list);
552  clib_memset(path_list, 0, sizeof(*path_list));
553 
554  fib_node_init(&path_list->fpl_node,
556  path_list->fpl_urpf = INDEX_INVALID;
557  path_list->fpl_paths = NULL;
558 
559  *path_list_index = fib_path_list_get_index(path_list);
560 
561  FIB_PATH_LIST_DBG(path_list, "alloc");
562 
563  return (path_list);
564 }
565 
566 static fib_path_list_t *
568 {
569  fib_node_index_t *path_index, *paths, path_list_index;
570 
572 
573  /*
574  * resolving a path-list is a recursive action. this means more path
575  * lists can be created during this call, and hence this path-list
576  * can be realloc'd. so we work with copies.
577  * this function is called only once per-path list, so its no great overhead.
578  */
579  path_list_index = fib_path_list_get_index(path_list);
580  paths = vec_dup(path_list->fpl_paths);
581 
582  vec_foreach (path_index, paths)
583  {
584  fib_path_resolve(*path_index);
585  }
586 
587  vec_free(paths);
588  path_list = fib_path_list_get(path_list_index);
589 
590  FIB_PATH_LIST_DBG(path_list, "resovled");
591 
592  if (!(path_list->fpl_flags & FIB_PATH_LIST_FLAG_NO_URPF))
593  {
594  fib_path_list_mk_urpf(path_list);
595  }
596  return (path_list);
597 }
598 
599 u32
601 {
602  fib_path_list_t *path_list;
603 
604  if (FIB_NODE_INDEX_INVALID == path_list_index)
605  {
606  return (0);
607  }
608 
609  path_list = fib_path_list_get(path_list_index);
610 
611  return (vec_len(path_list->fpl_paths));
612 }
613 
614 
615 u32
617 {
618  fib_node_index_t *path_index;
619  fib_path_list_t *path_list;
621 
622  path_list = fib_path_list_get(path_list_index);
623 
624  sw_if_index = ~0;
625  vec_foreach (path_index, path_list->fpl_paths)
626  {
627  sw_if_index = fib_path_get_resolving_interface(*path_index);
628  if (~0 != sw_if_index)
629  {
630  return (sw_if_index);
631  }
632  }
633 
634  return (sw_if_index);
635 }
636 
639 {
640  fib_path_list_t *path_list;
641 
642  path_list = fib_path_list_get(path_list_index);
643 
644  /*
645  * we don't support a mix of path protocols, so we can return the proto
646  * of the first
647  */
648  return (fib_path_get_proto(path_list->fpl_paths[0]));
649 }
650 
651 int
653 {
654  fib_path_list_t *path_list;
655 
656  path_list = fib_path_list_get(path_list_index);
657 
658  return (path_list->fpl_flags & FIB_PATH_LIST_FLAG_LOOPED);
659 }
660 
661 int
663 {
664  fib_path_list_t *path_list;
665 
666  path_list = fib_path_list_get(path_list_index);
667 
668  return (path_list->fpl_flags & FIB_PATH_LIST_FLAG_POPULAR);
669 }
670 
673 {
674  /*
675  * we do no share drop nor exclusive path-lists
676  */
677  if (flags & FIB_PATH_LIST_FLAG_DROP ||
679  {
680  flags &= ~FIB_PATH_LIST_FLAG_SHARED;
681  }
682 
683  return (flags);
684 }
685 
688  const fib_route_path_t *rpaths)
689 {
690  fib_node_index_t path_list_index, old_path_list_index;
691  fib_path_list_t *path_list;
692  int i;
693 
694  flags = fib_path_list_flags_fixup(flags);
695  path_list = fib_path_list_alloc(&path_list_index);
696  path_list->fpl_flags = flags;
697 
698  if (NULL != rpaths)
699  {
700  vec_foreach_index(i, rpaths)
701  {
702  vec_add1(path_list->fpl_paths,
703  fib_path_create(path_list_index,
704  &rpaths[i]));
705  }
706  /*
707  * we sort the paths since the key for the path-list is
708  * the description of the paths it contains. The paths need to
709  * be sorted else this description will differ.
710  */
711  if (vec_len(path_list->fpl_paths) > 1)
712  {
715  }
716  }
717 
718  /*
719  * If a shared path list is requested, consult the DB for a match
720  */
721  if (flags & FIB_PATH_LIST_FLAG_SHARED)
722  {
723  /*
724  * check for a matching path-list in the DB.
725  * If we find one then we can return the existing one and destroy the
726  * new one just created.
727  */
728  old_path_list_index = fib_path_list_db_find(path_list);
729  if (FIB_NODE_INDEX_INVALID != old_path_list_index)
730  {
731  fib_path_list_destroy(path_list);
732 
733  path_list_index = old_path_list_index;
734  }
735  else
736  {
737  /*
738  * if there was not a matching path-list, then this
739  * new one will need inserting into the DB and resolving.
740  */
741  fib_path_list_db_insert(path_list_index);
742  path_list = fib_path_list_resolve(path_list);
743  }
744  }
745  else
746  {
747  /*
748  * no shared path list requested. resolve and use the one
749  * just created.
750  */
751  path_list = fib_path_list_resolve(path_list);
752  }
753 
754  return (path_list_index);
755 }
756 
759 {
761 
762  if (plf & FIB_PATH_LIST_FLAG_DROP)
763  {
765  }
767  {
769  }
770  if (plf & FIB_PATH_LIST_FLAG_LOCAL)
771  {
773  }
774 
775  return (pf);
776 }
777 
781  const dpo_id_t *dpo)
782 {
783  fib_node_index_t path_index, path_list_index;
784  fib_path_list_t *path_list;
785 
786  path_list = fib_path_list_alloc(&path_list_index);
787  path_list->fpl_flags = flags;
788 
789  path_index =
790  fib_path_create_special(path_list_index,
791  nh_proto,
793  dpo);
794  vec_add1(path_list->fpl_paths, path_index);
795 
796  /*
797  * we don't share path-lists. we can do PIC on them so why bother.
798  */
799  path_list = fib_path_list_resolve(path_list);
800 
801  return (path_list_index);
802 }
803 
804 /*
805  * return the index info the path-lists's vector of paths, of the matching path.
806  * ~0 if not found
807  */
808 u32
810  const fib_route_path_t *rpath)
811 {
812  fib_path_list_t *path_list;
813  u32 ii;
814 
815  path_list = fib_path_list_get(path_list_index);
816 
817  vec_foreach_index (ii, path_list->fpl_paths)
818  {
819  if (!fib_path_cmp_w_route_path(path_list->fpl_paths[ii], rpath))
820  {
821  return (ii);
822  }
823  }
824  return (~0);
825 }
826 
827 
828 /*
829  * fib_path_list_copy_and_path_add
830  *
831  * Create a copy of a path-list and append one more path to it.
832  * The path-list returned could either have been newly created, or
833  * can be a shared path-list from the data-base.
834  */
837  const fib_route_path_t *rpaths)
838 {
839  fib_node_index_t *new_path_indices, *path_index;
840  const fib_route_path_t *rpath;
841  fib_path_list_t *path_list;
842  u32 ii;
843 
844  /*
845  * alloc the new list before we retrieve the old one, lest
846  * the alloc result in a realloc
847  */
848  path_list = fib_path_list_get(path_list_index);
849 
850  ASSERT(!(path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED));
851 
852  FIB_PATH_LIST_DBG(path_list, "paths-add");
853 
854  new_path_indices = NULL;
855  vec_validate_init_empty(new_path_indices,
856  vec_len(rpaths) - 1,
858 
859  vec_foreach (path_index, path_list->fpl_paths)
860  {
861  /*
862  * don't add duplicate paths
863  */
864  int found = 0;
865 
866  vec_foreach_index(ii, rpaths)
867  {
868  rpath = &rpaths[ii];
869  if (0 == fib_path_cmp_w_route_path(*path_index, rpath))
870  {
871  found = 1;
872  break;
873  }
874  }
875  if (found)
876  {
877  new_path_indices[ii] = *path_index;
878  }
879  }
880 
881  /*
882  * new_path_indices array contains INVALID for each path not found
883  * and something valid for matches
884  */
885  vec_foreach_index (ii, new_path_indices)
886  {
887  path_index = &new_path_indices[ii];
888  rpath = &rpaths[ii];
889 
890  if (FIB_NODE_INDEX_INVALID == *path_index)
891  {
892  *path_index = fib_path_create(path_list_index, rpath);
893  /*
894  * Add the new path - no sort, no sharing, no key..
895  */
896  vec_add1(path_list->fpl_paths, *path_index);
897 
898  /*
899  * no shared path list requested. resolve and use the one
900  * just created.
901  */
902  fib_path_resolve(*path_index);
903  }
904  }
905 
906  FIB_PATH_LIST_DBG(path_list, "paths-added");
907 
908  return (new_path_indices);
909 }
910 
914  const fib_route_path_t *rpaths)
915 {
916  fib_node_index_t new_path_index, *orig_path_index;
917  fib_path_list_t *path_list, *orig_path_list;
918  fib_node_index_t exist_path_list_index;
919  fib_node_index_t path_list_index;
920  const fib_route_path_t *rpath;
921  fib_node_index_t pi;
922 
923  /*
924  * alloc the new list before we retrieve the old one, lest
925  * the alloc result in a realloc
926  */
927  path_list = fib_path_list_alloc(&path_list_index);
928 
929  orig_path_list = fib_path_list_get(orig_path_list_index);
930 
931  FIB_PATH_LIST_DBG(orig_path_list, "copy-add");
932 
933  flags = fib_path_list_flags_fixup(flags);
934  path_list->fpl_flags = flags;
935 
936  vec_validate(path_list->fpl_paths,
937  (vec_len(orig_path_list->fpl_paths) +
938  vec_len(rpaths) - 1));
939  pi = 0;
940 
941  vec_foreach(orig_path_index, orig_path_list->fpl_paths)
942  {
943  /*
944  * copy the original paths over to the new list
945  */
946  path_list->fpl_paths[pi++] = fib_path_copy(*orig_path_index,
947  path_list_index);
948  }
949  vec_foreach(rpath, rpaths)
950  {
951  int duplicate = 0;
952 
953  new_path_index = fib_path_create(path_list_index, rpath);
954 
955  vec_foreach(orig_path_index, orig_path_list->fpl_paths)
956  {
957  /*
958  * don't add duplicate paths
959  * In the unlikely event the path is a duplicate, then we'll
960  * find a matching path-list later and this one will be toast.
961  */
962  if (0 == fib_path_cmp(new_path_index, *orig_path_index))
963  {
964  duplicate = 1;
965  break;
966  }
967  }
968  if (duplicate)
969  {
970  _vec_len(path_list->fpl_paths) =
971  vec_len(path_list->fpl_paths) - 1;
972  fib_path_destroy(new_path_index);
973  }
974  else
975  {
976  path_list->fpl_paths[pi++] = new_path_index;
977  }
978  }
979 
980  /*
981  * we sort the paths since the key for the path-list is
982  * the description of the paths it contains. The paths need to
983  * be sorted else this description will differ.
984  */
986 
987  FIB_PATH_LIST_DBG(path_list, "path-added");
988 
989  /*
990  * check for a matching path-list in the DB.
991  * If we find one then we can return the existing one and destroy the
992  * new one just created.
993  */
994  if (path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED)
995  {
996  exist_path_list_index = fib_path_list_db_find(path_list);
997  if (FIB_NODE_INDEX_INVALID != exist_path_list_index)
998  {
999  fib_path_list_destroy(path_list);
1000 
1001  path_list_index = exist_path_list_index;
1002  }
1003  else
1004  {
1005  /*
1006  * if there was not a matching path-list, then this
1007  * new one will need inserting into the DB and resolving.
1008  */
1009  fib_path_list_db_insert(path_list_index);
1010 
1011  path_list = fib_path_list_resolve(path_list);
1012  }
1013  }
1014  else
1015  {
1016  /*
1017  * no shared path list requested. resolve and use the one
1018  * just created.
1019  */
1020  path_list = fib_path_list_resolve(path_list);
1021  }
1022 
1023  return (path_list_index);
1024 }
1025 
1026 /*
1027  * fib_path_list_paths_remove
1028  */
1031  const fib_route_path_t *rpaths)
1032 {
1033  fib_node_index_t *match_path_indices;
1034  fib_path_list_t *path_list;
1035  i32 ii, jj;
1036 
1037  path_list = fib_path_list_get(path_list_index);
1038  match_path_indices = NULL;
1039  vec_validate_init_empty(match_path_indices,
1040  vec_len(rpaths) - 1,
1042 
1043  ASSERT(!(path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED));
1044 
1045  FIB_PATH_LIST_DBG(path_list, "path-remove");
1046 
1047  /*
1048  * the number of existing paths is likely to be larger than the
1049  * number of paths being added.
1050  * walk in reverse so the vec_del is ok
1051  */
1052  vec_foreach_index_backwards(ii, path_list->fpl_paths)
1053  {
1054  int found = ~0;
1055 
1056  vec_foreach_index(jj, rpaths)
1057  {
1058  if (0 == fib_path_cmp_w_route_path(path_list->fpl_paths[ii],
1059  &rpaths[jj]))
1060  {
1061  found = jj;
1062  break;
1063  }
1064  }
1065  if (~0 != found)
1066  {
1067  fib_node_index_t match_path_index;
1068  /*
1069  * match - remove it
1070  */
1071  match_path_index = path_list->fpl_paths[ii];
1072  vec_del1(path_list->fpl_paths, ii);
1073  fib_path_destroy(match_path_index);
1074  match_path_indices[jj] = match_path_index;
1075  }
1076  }
1077 
1078  FIB_PATH_LIST_DBG(path_list, "paths-removed");
1079 
1080  return (match_path_indices);
1081 }
1082 
1083 /*
1084  * fib_path_list_copy_and_path_remove
1085  *
1086  * Copy the path-list excluding the path passed.
1087  * If the path is the last one, then the index reurned will be invalid.
1088  * i.e. the path-list is toast.
1089  */
1093  const fib_route_path_t *rpaths)
1094 {
1095  fib_node_index_t *orig_path_index, path_list_index, tmp_path_index;
1096  fib_path_list_t *path_list, *orig_path_list;
1097  const fib_route_path_t *rpath;
1098  fib_node_index_t pi;
1099 
1100  path_list = fib_path_list_alloc(&path_list_index);
1101 
1102  flags = fib_path_list_flags_fixup(flags);
1103  orig_path_list = fib_path_list_get(orig_path_list_index);
1104 
1105  FIB_PATH_LIST_DBG(orig_path_list, "copy-remove");
1106 
1107  path_list->fpl_flags = flags;
1108  /*
1109  * allocate as many paths as we might need in one go, rather than
1110  * using vec_add to do a few at a time.
1111  */
1112  vec_validate(path_list->fpl_paths,
1113  vec_len(orig_path_list->fpl_paths) - 1);
1114  pi = 0;
1115 
1116  /*
1117  * create a representation of the path to be removed, so it
1118  * can be used as a comparison object during the copy.
1119  */
1120  vec_foreach(orig_path_index, orig_path_list->fpl_paths)
1121  {
1122  /*
1123  * copy the original paths over to the new list
1124  */
1125  path_list->fpl_paths[pi++] = fib_path_copy(*orig_path_index,
1126  path_list_index);
1127  }
1128  vec_foreach(rpath, rpaths)
1129  {
1130  int found = 0;
1131  tmp_path_index = fib_path_create(path_list_index, rpath);
1132 
1133  vec_foreach_index(pi, path_list->fpl_paths)
1134  {
1135  if (0 == fib_path_cmp(tmp_path_index, path_list->fpl_paths[pi]))
1136  {
1137  found = 1;
1138  break;
1139  }
1140  }
1141  if (found)
1142  {
1143  fib_path_destroy(path_list->fpl_paths[pi]);
1144  vec_del1(path_list->fpl_paths, pi);
1145  }
1146  fib_path_destroy(tmp_path_index);
1147  }
1148 
1149  /*
1150  * if there are no paths, then the new path-list is aborted
1151  */
1152  if (0 == vec_len(path_list->fpl_paths)) {
1153  FIB_PATH_LIST_DBG(path_list, "last-path-removed");
1154 
1155  fib_path_list_destroy(path_list);
1156 
1157  path_list_index = FIB_NODE_INDEX_INVALID;
1158  } else {
1159  /*
1160  * we sort the paths since the key for the path-list is
1161  * the description of the paths it contains. The paths need to
1162  * be sorted else this description will differ.
1163  */
1165 
1166  /*
1167  * If a shared path list is requested, consult the DB for a match
1168  */
1169  if (path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED)
1170  {
1171  fib_node_index_t exist_path_list_index;
1172 
1173  /*
1174  * check for a matching path-list in the DB.
1175  * If we find one then we can return the existing one and destroy the
1176  * new one just created.
1177  */
1178  exist_path_list_index = fib_path_list_db_find(path_list);
1179  if (FIB_NODE_INDEX_INVALID != exist_path_list_index)
1180  {
1181  fib_path_list_destroy(path_list);
1182 
1183  path_list_index = exist_path_list_index;
1184  }
1185  else
1186  {
1187  /*
1188  * if there was not a matching path-list, then this
1189  * new one will need inserting into the DB and resolving.
1190  */
1191  fib_path_list_db_insert(path_list_index);
1192 
1193  path_list = fib_path_list_resolve(path_list);
1194  }
1195  }
1196  else
1197  {
1198  /*
1199  * no shared path list requested. resolve and use the one
1200  * just created.
1201  */
1202  path_list = fib_path_list_resolve(path_list);
1203  }
1204  }
1205 
1206  return (path_list_index);
1207 }
1208 
1209 /*
1210  * fib_path_list_contribute_forwarding
1211  *
1212  * Return the index of a load-balance that user of this path-list should
1213  * use for forwarding
1214  */
1215 void
1219  dpo_id_t *dpo)
1220 {
1221  fib_path_list_t *path_list;
1222 
1223  path_list = fib_path_list_get(path_list_index);
1224 
1225  fib_path_list_mk_lb(path_list, fct, dpo, flags);
1226 
1228 
1229  /*
1230  * If there's only one bucket in the load-balance then we can
1231  * squash it out.
1232  */
1233  if ((1 == load_balance_n_buckets(dpo->dpoi_index)) &&
1235  {
1237  }
1238 }
1239 
1240 /*
1241  * fib_path_list_get_adj
1242  *
1243  * Return the index of a adjacency for the first path that user of this
1244  * path-list should use for forwarding
1245  */
1249 {
1250  fib_path_list_t *path_list;
1251 
1252  path_list = fib_path_list_get(path_list_index);
1253  return (fib_path_get_adj(path_list->fpl_paths[0]));
1254 }
1255 
1256 int
1258  fib_node_index_t **entry_indicies)
1259 {
1260  fib_node_index_t *path_index;
1261  int is_looped, list_looped;
1262  fib_path_list_t *path_list;
1263 
1264  list_looped = 0;
1265  path_list = fib_path_list_get(path_list_index);
1266 
1267  vec_foreach (path_index, path_list->fpl_paths)
1268  {
1269  fib_node_index_t *copy, **copy_ptr;
1270 
1271  /*
1272  * we need a copy of the nodes visited so that when we add entries
1273  * we explore on the nth path and a looped is detected, those entries
1274  * are not again searched for n+1 path and so finding a loop that does
1275  * not exist.
1276  */
1277  copy = vec_dup(*entry_indicies);
1278  copy_ptr = &copy;
1279 
1280  is_looped = fib_path_recursive_loop_detect(*path_index, copy_ptr);
1281  list_looped += is_looped;
1282 
1283  vec_free(copy);
1284  }
1285 
1286  FIB_PATH_LIST_DBG(path_list, "loop-detect: eval:%d", list_looped);
1287 
1288  if (list_looped)
1289  {
1290  path_list->fpl_flags |= FIB_PATH_LIST_FLAG_LOOPED;
1291  }
1292  else
1293  {
1294  path_list->fpl_flags &= ~FIB_PATH_LIST_FLAG_LOOPED;
1295  }
1296 
1297  return (list_looped);
1298 }
1299 
1300 u32
1302  fib_node_type_t child_type,
1303  fib_node_index_t child_index)
1304 {
1305  u32 sibling;
1306 
1308  path_list_index,
1309  child_type,
1310  child_index);
1311 
1313  path_list_index))
1314  {
1315  /*
1316  * Set the popular flag on the path-list once we pass the magic
1317  * threshold. then walk children to update.
1318  * We don't undo this action. The rational being that the number
1319  * of entries using this prefix is large enough such that it is a
1320  * non-trival amount of effort to converge them. If we get into the
1321  * situation where we are adding and removing entries such that we
1322  * flip-flop over the threshold, then this non-trivial work is added
1323  * to each of those routes adds/deletes - not a situation we want.
1324  */
1326  .fnbw_reason = FIB_NODE_BW_REASON_FLAG_EVALUATE,
1327  };
1328  fib_path_list_t *path_list;
1329 
1330  path_list = fib_path_list_get(path_list_index);
1331  path_list->fpl_flags |= FIB_PATH_LIST_FLAG_POPULAR;
1332 
1333  fib_walk_sync(FIB_NODE_TYPE_PATH_LIST, path_list_index, &ctx);
1334  }
1335 
1336  return (sibling);
1337 }
1338 
1339 void
1341  u32 si)
1342 {
1344  path_list_index,
1345  si);
1346 }
1347 
1348 void
1350 {
1351  fib_path_list_t *path_list;
1352 
1353  if (FIB_NODE_INDEX_INVALID != path_list_index)
1354  {
1355  path_list = fib_path_list_get(path_list_index);
1356 
1357  fib_node_lock(&path_list->fpl_node);
1358  }
1359 }
1360 
1361 void
1363 {
1364  fib_path_list_t *path_list;
1365 
1366  if (FIB_NODE_INDEX_INVALID != path_list_index)
1367  {
1368  path_list = fib_path_list_get(path_list_index);
1369 
1370  fib_node_unlock(&path_list->fpl_node);
1371  }
1372 }
1373 
1374 u32
1376 {
1377  return (pool_elts(fib_path_list_pool));
1378 }
1379 
1380 u32
1382 {
1383  return (hash_elts(fib_path_list_db));
1384 }
1385 
1386 void
1389  void *ctx)
1390 {
1391  fib_node_index_t *path_index;
1392  fib_path_list_t *path_list;
1393 
1394  path_list = fib_path_list_get(path_list_index);
1395 
1396  vec_foreach(path_index, path_list->fpl_paths)
1397  {
1398  if (FIB_PATH_LIST_WALK_STOP == func(path_list_index,
1399  *path_index,
1400  ctx))
1401  break;
1402  }
1403 }
1404 
1405 void
1407  const fib_path_ext_list_t *ext_list,
1409  void *ctx)
1410 {
1411  fib_node_index_t *path_index;
1412  fib_path_list_t *path_list;
1413  fib_path_ext_t *path_ext;
1414 
1415  path_list = fib_path_list_get(path_list_index);
1416 
1417  vec_foreach(path_index, path_list->fpl_paths)
1418  {
1419  path_ext = fib_path_ext_list_find_by_path_index(ext_list, *path_index);
1420 
1421  if (FIB_PATH_LIST_WALK_STOP == func(path_list_index,
1422  *path_index,
1423  path_ext,
1424  ctx))
1425  break;
1426  }
1427 }
1428 
1429 void
1431 {
1432  fib_node_register_type (FIB_NODE_TYPE_PATH_LIST, &fib_path_list_vft);
1433 
1434  fib_path_list_db = hash_create2 (/* elts */ 0,
1435  /* user */ 0,
1436  /* value_bytes */ sizeof (fib_node_index_t),
1439  /* format pair/arg */
1440  0, 0);
1441  fib_path_list_logger = vlib_log_register_class("fib", "path-list");
1442 }
1443 
1444 static clib_error_t *
1446  unformat_input_t * input,
1447  vlib_cli_command_t * cmd)
1448 {
1449  fib_path_list_t *path_list;
1450  fib_node_index_t pli;
1451 
1452  if (unformat (input, "%d", &pli))
1453  {
1454  /*
1455  * show one in detail
1456  */
1457  if (!pool_is_free_index(fib_path_list_pool, pli))
1458  {
1459  path_list = fib_path_list_get(pli);
1460  u8 *s = fib_path_list_format(pli, NULL);
1461  s = format(s, "children:");
1462  s = fib_node_children_format(path_list->fpl_node.fn_children, s);
1463  vlib_cli_output (vm, "%s", s);
1464  vec_free(s);
1465  }
1466  else
1467  {
1468  vlib_cli_output (vm, "path list %d invalid", pli);
1469  }
1470  }
1471  else
1472  {
1473  /*
1474  * show all
1475  */
1476  vlib_cli_output (vm, "FIB Path Lists");
1477  pool_foreach_index (pli, fib_path_list_pool,
1478  ({
1479  vlib_cli_output (vm, "%U", format_fib_path_list, pli, 0);
1480  }));
1481  }
1482  return (NULL);
1483 }
1484 
1485 VLIB_CLI_COMMAND (show_fib_path_list, static) = {
1486  .path = "show fib path-lists",
1487  .function = show_fib_path_list_command,
1488  .short_help = "show fib path-lists",
1489 };
vlib_log_class_t vlib_log_register_class(char *class, char *subclass)
Definition: log.c:176
#define vec_validate(V, I)
Make sure vector is long enough for given index (no header, unspecified alignment) ...
Definition: vec.h:439
int fib_path_is_resolved(fib_node_index_t path_index)
Definition: fib_path.c:2669
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:1892
void fib_path_list_module_init(void)
#define vec_foreach_index(var, v)
Iterate over vector indices.
u32 fib_path_list_find_rpath(fib_node_index_t path_list_index, const fib_route_path_t *rpath)
#define hash_set(h, key, value)
Definition: hash.h:255
u32 flags
Definition: vhost_user.h:141
uword fib_path_hash(fib_node_index_t path_index)
Definition: fib_path.c:1521
#define FIB_PATH_LIST_POPULAR
The magic number of child entries that make a path-list popular.
Definition: fib_path_list.c:38
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:289
#define hash_unset(h, key)
Definition: hash.h:261
void fib_path_contribute_urpf(fib_node_index_t path_index, index_t urpf)
Contribute the path&#39;s adjacency to the list passed.
Definition: fib_path.c:2272
A representation of a path as described by a route producer.
Definition: fib_types.h:479
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:1661
void fib_node_init(fib_node_t *node, fib_node_type_t type)
Definition: fib_node.c:185
u32 fib_path_list_get_resolving_interface(fib_node_index_t path_list_index)
u8 * format_fib_path_list(u8 *s, va_list *args)
#define NULL
Definition: clib.h:58
enum fib_node_back_walk_rc_t_ fib_node_back_walk_rc_t
Return code from a back walk function.
fib_node_index_t fib_path_list_create_special(dpo_proto_t nh_proto, fib_path_list_flags_t flags, const dpo_id_t *dpo)
fib_node_index_t * fpl_paths
Vector of paths indicies for all configured paths.
Definition: fib_path_list.c:59
void fib_urpf_list_show_mem(void)
dpo_proto_t fib_forw_chain_type_to_dpo_proto(fib_forward_chain_type_t fct)
Convert from a chain type to the DPO proto it will install.
Definition: fib_types.c:410
void dpo_copy(dpo_id_t *dst, const dpo_id_t *src)
atomic copy a data-plane object.
Definition: dpo.c:262
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:85
int i
void fib_path_list_walk(fib_node_index_t path_list_index, fib_path_list_walk_fn_t func, void *ctx)
clib_memset(h->entries, 0, sizeof(h->entries[0])*entries)
void fib_node_deinit(fib_node_t *node)
Definition: fib_node.c:197
void fib_walk_async(fib_node_type_t parent_type, fib_node_index_t parent_index, fib_walk_priority_t prio, fib_node_back_walk_ctx_t *ctx)
Definition: fib_walk.c:688
u8 * format(u8 *s, const char *fmt,...)
Definition: format.c:424
static uword fib_path_list_db_hash_key_from_index(uword index)
#define FIB_PATH_LIST_KEY_FLAGS
The flags on a path-list that contribute to its key in the DB.
#define FOR_EACH_PATH_LIST_ATTRIBUTE(_item)
#define vec_foreach_index_backwards(var, v)
Iterate over vector indices (reverse).
fib_node_index_t * fib_path_list_paths_add(fib_node_index_t path_list_index, const fib_route_path_t *rpaths)
#define pool_get(P, E)
Allocate an object E from a pool P (unspecified alignment).
Definition: pool.h:236
int fib_path_cmp_for_sort(void *v1, void *v2)
Definition: fib_path.c:1634
u32 fib_path_list_child_add(fib_node_index_t path_list_index, fib_node_type_t child_type, fib_node_index_t child_index)
static void fib_path_list_mk_urpf(fib_path_list_t *path_list)
[re]build the path list&#39;s uRPF list
unsigned char u8
Definition: types.h:56
#define pool_len(p)
Number of elements in pool vector.
Definition: pool.h:140
FIB path-list A representation of the list/set of path trough which a prefix is reachable.
Definition: fib_path_list.c:44
static fib_path_list_t * fib_path_list_pool
Definition: fib_path_list.c:80
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:2608
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:75
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:239
fib_node_t fpl_node
A path-list is a node in the FIB graph.
Definition: fib_path_list.c:48
u32 vlib_log_class_t
Definition: vlib.h:51
static uword fib_path_list_db_hash_key_is_index(uword key)
vl_api_interface_index_t sw_if_index
Definition: gre.api:50
#define always_inline
Definition: clib.h:98
void fib_walk_sync(fib_node_type_t parent_type, fib_node_index_t parent_index, fib_node_back_walk_ctx_t *ctx)
Back walk all the children of a FIB node.
Definition: fib_walk.c:745
index_t fib_urpf_list_alloc_and_lock(void)
Definition: fib_urpf_list.c:55
u8 * format_white_space(u8 *s, va_list *va)
Definition: std-formats.c:129
fib_node_index_t fib_path_copy(fib_node_index_t path_index, fib_node_index_t path_list_index)
Definition: fib_path.c:1467
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:602
unsigned int u32
Definition: types.h:88
enum dpo_proto_t_ dpo_proto_t
Data path protocol.
fib_path_ext_t * fib_path_ext_list_find_by_path_index(const fib_path_ext_list_t *list, fib_node_index_t path_index)
Definition: fib_path_ext.c:326
enum fib_path_list_attribute_t_ fib_path_list_attribute_t
Enumeration of path-list flags.
fib_node_index_t fib_path_create_special(fib_node_index_t pl_index, dpo_proto_t nh_proto, fib_path_cfg_flags_t flags, const dpo_id_t *dpo)
Definition: fib_path.c:1421
vl_api_fib_path_type_t type
Definition: fib_types.api:123
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:464
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:170
fib_node_bw_reason_flag_t fnbw_reason
The reason/trigger for the backwalk.
Definition: fib_node.h:212
static uword fib_path_list_db_hash_key_2_index(uword key)
#define hash_get(h, key)
Definition: hash.h:249
#define pool_elt_at_index(p, i)
Returns pointer to element at given index.
Definition: pool.h:514
fib_node_index_t fib_path_list_create(fib_path_list_flags_t flags, const fib_route_path_t *rpaths)
#define FIB_PATH_LIST_ATTRIBUTES
Definition: fib_path_list.h:91
u8 * format_fib_node_bw_reason(u8 *s, va_list *args)
Definition: fib_walk.c:973
static fib_node_back_walk_rc_t fib_path_list_back_walk_notify(fib_node_t *node, fib_node_back_walk_ctx_t *ctx)
dpo_type_t dpoi_type
the type
Definition: dpo.h:174
void fib_node_lock(fib_node_t *node)
Definition: fib_node.c:203
long ctx[MAX_CONNS]
Definition: main.c:144
struct _unformat_input_t unformat_input_t
flow_hash_config_t load_balance_get_default_flow_hash(dpo_proto_t lb_proto)
Definition: load_balance.c:193
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:2210
#define pool_put(P, E)
Free an object E in pool P.
Definition: pool.h:286
#define vec_dup(V)
Return copy of vector (no header, no alignment)
Definition: vec.h:375
#define vec_del1(v, i)
Delete the element at index I.
Definition: vec.h:804
void fib_path_list_lock(fib_node_index_t path_list_index)
vl_api_gbp_next_hop_t nhs[8]
Definition: gbp.api:289
A list of path-extensions.
Definition: fib_types.h:614
fib_node_type_t fn_type
The node&#39;s type.
Definition: fib_node.h:299
An node in the FIB graph.
Definition: fib_node.h:295
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:339
fib_path_list_walk_rc_t(* fib_path_list_walk_w_ext_fn_t)(fib_node_index_t pl_index, fib_node_index_t path_index, const struct fib_path_ext_t_ *ext_list, void *ctx)
fib_path_list_flags_t fpl_flags
Flags on the path-list.
Definition: fib_path_list.c:53
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:309
static void fib_path_list_last_lock_gone(fib_node_t *node)
#define hash_mix64(a0, b0, c0)
Definition: hash.h:531
int fib_path_list_is_popular(fib_node_index_t path_list_index)
vlib_main_t * vm
Definition: buffer.c:312
#define vec_free(V)
Free vector&#39;s memory (no header).
Definition: vec.h:341
#define FIB_PATH_LIST_DBG(_pl, _fmt, _args...)
Definition: fib_path_list.c:95
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:283
#define hash_mix32(a0, b0, c0)
Definition: hash.h:539
u32 fib_path_list_get_n_paths(fib_node_index_t path_list_index)
u32 fib_node_index_t
A typedef of a node index.
Definition: fib_types.h:30
#define pool_is_free_index(P, I)
Use free bitmap to query whether given index is free.
Definition: pool.h:283
u32 fib_node_get_n_children(fib_node_type_t parent_type, fib_node_index_t parent_index)
Definition: fib_node.c:142
u32 adj_index_t
An index for adjacencies.
Definition: adj_types.h:30
fib_node_index_t fpl_urpf
the RPF list calculated for this path list
Definition: fib_path_list.c:64
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:186
void fib_path_list_unlock(fib_node_index_t path_list_index)
enum fib_path_list_fwd_flags_t_ fib_path_list_fwd_flags_t
Flags to control how the path-list returns forwarding information.
#define hash_create2(_elts, _user, _value_bytes,_key_sum, _key_equal,_format_pair, _format_pair_arg)
Definition: hash.h:494
Context passed between object during a back walk.
Definition: fib_node.h:208
#define VLIB_CLI_COMMAND(x,...)
Definition: cli.h:155
int fib_path_list_recursive_loop_detect(fib_node_index_t path_list_index, fib_node_index_t **entry_indicies)
static fib_path_list_t * fib_path_list_from_fib_node(fib_node_t *node)
int fib_path_list_is_looped(fib_node_index_t path_list_index)
signed int i32
Definition: types.h:77
#define uword_to_pointer(u, type)
Definition: types.h:136
static uword hash_elts(void *v)
Definition: hash.h:118
#define ASSERT(truth)
static fib_path_list_t * fib_path_list_resolve(fib_path_list_t *path_list)
static void fib_path_list_db_insert(fib_node_index_t path_list_index)
vlib_log_class_t fib_path_list_logger
the logger
Definition: fib_path_list.c:90
uword * fpl_db
Hash table of paths.
Definition: fib_path_list.c:69
void fib_urpf_list_combine(index_t ui1, index_t ui2)
Combine to interface lists.
enum fib_forward_chain_type_t_ fib_forward_chain_type_t
FIB output chain type.
void fib_node_child_remove(fib_node_type_t parent_type, fib_node_index_t parent_index, fib_node_index_t sibling_index)
Definition: fib_node.c:123
static void fib_path_list_mk_lb(fib_path_list_t *path_list, fib_forward_chain_type_t fct, dpo_id_t *dpo, fib_path_list_fwd_flags_t flags)
static fib_path_list_flags_t fib_path_list_flags_fixup(fib_path_list_flags_t flags)
vl_api_mfib_path_t paths[n_paths]
Definition: ip.api:458
static fib_node_index_t fib_path_list_get_index(fib_path_list_t *path_list)
dpo_proto_t fib_path_get_proto(fib_node_index_t path_index)
Definition: fib_path.c:2776
enum load_balance_flags_t_ load_balance_flags_t
void fib_path_list_back_walk(fib_node_index_t path_list_index, fib_node_back_walk_ctx_t *ctx)
u32 fib_path_get_resolving_interface(fib_node_index_t path_index)
Definition: fib_path.c:2142
index_t dpoi_index
the index of objects of that type
Definition: dpo.h:186
#define FIB_NODE_INDEX_INVALID
Definition: fib_types.h:31
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
u32 fn_locks
Number of dependents on this node.
Definition: fib_node.h:315
static load_balance_flags_t fib_path_list_fwd_flags_2_load_balance(fib_path_list_fwd_flags_t pl_flags)
#define INDEX_INVALID
Invalid index - used when no index is known blazoned capitals INVALID speak volumes where ~0 does not...
Definition: dpo.h:47
static fib_path_list_t * fib_path_list_db_get_from_hash_key(uword key)
u8 * format_fib_urpf_list(u8 *s, va_list *args)
Definition: fib_urpf_list.c:25
u8 * fib_path_list_format(fib_node_index_t path_list_index, u8 *s)
u64 uword
Definition: types.h:112
#define vec_sort_with_function(vec, f)
Sort a vector using the supplied element comparison function.
Definition: vec.h:980
typedef key
Definition: ipsec.api:245
fib_node_index_t fib_path_create(fib_node_index_t pl_index, const fib_route_path_t *rpath)
Definition: fib_path.c:1272
void fib_urpf_list_unlock(index_t ui)
Definition: fib_urpf_list.c:68
One path from an [EU]CMP set that the client wants to add to a load-balance object.
Definition: load_balance.h:62
enum fib_path_cfg_flags_t_ fib_path_cfg_flags_t
Path config flags from the attributes.
void fib_path_list_contribute_forwarding(fib_node_index_t path_list_index, fib_forward_chain_type_t fct, fib_path_list_fwd_flags_t flags, dpo_id_t *dpo)
dpo_proto_t fib_path_list_get_proto(fib_node_index_t path_list_index)
int fib_path_recursive_loop_detect(fib_node_index_t path_index, fib_node_index_t **entry_indicies)
Definition: fib_path.c:1795
A FIB graph nodes virtual function table.
Definition: fib_node.h:282
index_t fib_path_list_get_urpf(fib_node_index_t path_list_index)
Return the the child the RPF list pre-built for this path list.
static void fib_path_list_memory_show(void)
enum fib_node_type_t_ fib_node_type_t
The types of nodes in a FIB graph.
u32 fib_path_list_pool_size(void)
#define vec_foreach(var, vec)
Vector iterator.
A path extension is a per-entry addition to the forwarding information when packets are sent for that...
Definition: fib_path_ext.h:98
void fib_path_list_walk_w_ext(fib_node_index_t path_list_index, const fib_path_ext_list_t *ext_list, fib_path_list_walk_w_ext_fn_t func, void *ctx)
fib_path_list_walk_rc_t(* fib_path_list_walk_fn_t)(fib_node_index_t pl_index, fib_node_index_t path_index, void *ctx)
A callback function type for walking a path-list&#39;s paths.
enum fib_path_list_flags_t_ fib_path_list_flags_t
#define pool_foreach_index(i, v, body)
Iterate pool by index.
Definition: pool.h:538
#define vec_validate_init_empty(V, I, INIT)
Make sure vector is long enough for given index and initialize empty space (no header, unspecified alignment)
Definition: vec.h:486
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:768
void fib_path_destroy(fib_node_index_t path_index)
Definition: fib_path.c:1500
fib_node_index_t * fib_path_list_paths_remove(fib_node_index_t path_list_index, const fib_route_path_t *rpaths)
int fib_path_cmp_w_route_path(fib_node_index_t path_index, const fib_route_path_t *rpath)
Definition: fib_path.c:1673
uword unformat(unformat_input_t *i, const char *fmt,...)
Definition: unformat.c:978
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