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