FD.io VPP  v17.01.1-3-gc6833f8
Vector Packet Processing
fib_path_list.c
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2016 Cisco and/or its affiliates.
3  * Licensed under the Apache License, Version 2.0 (the "License");
4  * you may not use this file except in compliance with the License.
5  * You may obtain a copy of the License at:
6  *
7  * http://www.apache.org/licenses/LICENSE-2.0
8  *
9  * Unless required by applicable law or agreed to in writing, software
10  * distributed under the License is distributed on an "AS IS" BASIS,
11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12  * See the License for the specific language governing permissions and
13  * limitations under the License.
14  */
15 
16 #include <vppinfra/mhash.h>
17 #include <vnet/ip/ip.h>
18 #include <vnet/adj/adj.h>
19 #include <vnet/dpo/load_balance.h>
21 
22 #include <vnet/fib/fib_path_list.h>
23 #include <vnet/fib/fib_internal.h>
24 #include <vnet/fib/fib_node_list.h>
25 #include <vnet/fib/fib_walk.h>
26 #include <vnet/fib/fib_urpf_list.h>
27 
28 /**
29  * FIB path-list
30  * A representation of the list/set of path trough which a prefix is reachable
31  */
32 typedef struct fib_path_list_t_ {
33  /**
34  * A path-list is a node in the FIB graph.
35  */
37 
38  /**
39  * Flags on the path-list
40  */
42 
43  /**
44  * The next-hop protocol for the paths in this path list.
45  * Note that fixing the proto here means we don't support a mix of
46  * v4 and v6 paths. ho hum.
47  */
49 
50  /**
51  * Vector of paths indicies for all configured paths.
52  * For shareable path-lists this list MUST not change.
53  */
55 
56  /**
57  * the RPF list calculated for this path list
58  */
61 
62 /*
63  * Array of strings/names for the FIB sources
64  */
66 
67 /*
68  * The memory pool from which we allocate all the path-lists
69  */
71 
72 /*
73  * The data-base of shared path-lists
74  */
76 
77 /*
78  * Debug macro
79  */
80 #ifdef FIB_DEBUG
81 #define FIB_PATH_LIST_DBG(_pl, _fmt, _args...) \
82 { \
83  u8 *_tmp = 0; \
84  _tmp = fib_path_list_format( \
85  fib_path_list_get_index(_pl), _tmp); \
86  clib_warning("pl:[%d:%p:%p:%s]:" _fmt, \
87  fib_path_list_get_index(_pl), \
88  _pl, _pl->fpl_paths, _tmp, \
89  ##_args); \
90  vec_free(_tmp); \
91 }
92 #else
93 #define FIB_PATH_LIST_DBG(_pl, _fmt, _args...)
94 #endif
95 
96 static fib_path_list_t *
98 {
99  return (pool_elt_at_index(fib_path_list_pool, index));
100 }
101 
102 static fib_node_t *
104 {
105  return ((fib_node_t*)fib_path_list_get(index));
106 }
107 
108 static fib_path_list_t*
110 {
111 #if CLIB_DEBUG > 0
113 #endif
114  return ((fib_path_list_t*)node);
115 }
116 
117 static fib_node_index_t
119 {
120  return (path_list - fib_path_list_pool);
121 }
122 
123 static u8 *
124 format_fib_path_list (u8 * s, va_list * args)
125 {
127  fib_node_index_t *path_index;
128  fib_path_list_t *path_list;
129 
130  path_list = va_arg (*args, fib_path_list_t *);
131 
132  s = format (s, " index:%u", fib_path_list_get_index(path_list));
133  s = format (s, " locks:%u", path_list->fpl_node.fn_locks);
134  s = format (s, " proto:%U", format_fib_protocol, path_list->fpl_nh_proto);
135 
136  if (FIB_PATH_LIST_FLAG_NONE != path_list->fpl_flags)
137  {
138  s = format (s, " flags:");
140  {
141  if ((1<<attr) & path_list->fpl_flags)
142  {
143  s = format (s, "%s,", fib_path_list_attr_names[attr]);
144  }
145  }
146  }
147  s = format (s, " %U\n", format_fib_urpf_list, path_list->fpl_urpf);
148 
149  vec_foreach (path_index, path_list->fpl_paths)
150  {
151  s = fib_path_format(*path_index, s);
152  s = format(s, "\n");
153  }
154 
155  return (s);
156 }
157 
158 u8 *
160  u32 indent,
161  u8 * s)
162 {
163  fib_path_list_t *path_list;
164  u32 i;
165 
166  path_list = fib_path_list_get(path_list_index);
167 
168  vec_foreach_index (i, path_list->fpl_paths)
169  {
170  s = fib_path_adj_format(path_list->fpl_paths[i],
171  indent, s);
172  }
173 
174  return (s);
175 }
176 
177 
178 u8 *
180  u8 * s)
181 {
182  fib_path_list_t *path_list;
183 
184  path_list = fib_path_list_get(path_list_index);
185 
186  return (format(s, "%U", format_fib_path_list, path_list));
187 }
188 
189 static uword
191 {
192  uword old_path_list_hash, new_path_list_hash, path_hash;
193  fib_node_index_t *path_index;
194 
195  ASSERT(path_list);
196 
197  new_path_list_hash = old_path_list_hash = vec_len(path_list->fpl_paths);
198 
199  vec_foreach (path_index, path_list->fpl_paths)
200  {
201  path_hash = fib_path_hash(*path_index);
202 #if uword_bits == 64
203  hash_mix64(path_hash, old_path_list_hash, new_path_list_hash);
204 #else
205  hash_mix32(path_hash, old_path_list_hash, new_path_list_hash);
206 #endif
207  }
208 
209  return (new_path_list_hash);
210 }
211 
214 {
215  return 1 + 2*index;
216 }
217 
220 {
221  return key & 1;
222 }
223 
226 {
228  return key / 2;
229 }
230 
231 static fib_path_list_t*
233 {
234  fib_path_list_t *path_list;
235 
237  {
238  fib_node_index_t path_list_index;
239 
240  path_list_index = fib_path_list_db_hash_key_2_index(key);
241  path_list = fib_path_list_get(path_list_index);
242  }
243  else
244  {
245  path_list = uword_to_pointer (key, fib_path_list_t *);
246  }
247 
248  return (path_list);
249 }
250 
251 static uword
253  uword key)
254 {
255  fib_path_list_t *path_list;
256 
257  path_list = fib_path_list_db_get_from_hash_key(key);
258 
259  return (fib_path_list_hash(path_list));
260 }
261 
262 static uword
264  uword key1,
265  uword key2)
266 {
267  fib_path_list_t *path_list1, *path_list2;
268 
269  path_list1 = fib_path_list_db_get_from_hash_key(key1);
270  path_list2 = fib_path_list_db_get_from_hash_key(key2);
271 
272  return (fib_path_list_hash(path_list1) ==
273  fib_path_list_hash(path_list2));
274 }
275 
276 static fib_node_index_t
278 {
279  uword *p;
280 
281  p = hash_get(fib_path_list_db, path_list);
282 
283  if (NULL != p)
284  {
285  return p[0];
286  }
287 
288  return (FIB_NODE_INDEX_INVALID);
289 }
290 
291 static void
293 {
294  fib_path_list_t *path_list;
295 
296  path_list = fib_path_list_get(path_list_index);
297 
299 
301  fib_path_list_db_hash_key_from_index(path_list_index),
302  path_list_index);
303 
304  FIB_PATH_LIST_DBG(path_list, "DB-inserted");
305 }
306 
307 static void
309 {
310  fib_path_list_t *path_list;
311 
312  path_list = fib_path_list_get(path_list_index);
313 
315 
317  fib_path_list_db_hash_key_from_index(path_list_index));
318 
319  FIB_PATH_LIST_DBG(path_list, "DB-removed");
320 }
321 
322 static void
324 {
325  fib_node_index_t *path_index;
326 
327  FIB_PATH_LIST_DBG(path_list, "destroy");
328 
329  vec_foreach (path_index, path_list->fpl_paths)
330  {
331  fib_path_destroy(*path_index);
332  }
333 
334  vec_free(path_list->fpl_paths);
335  fib_urpf_list_unlock(path_list->fpl_urpf);
336 
337  fib_node_deinit(&path_list->fpl_node);
338  pool_put(fib_path_list_pool, path_list);
339 }
340 
341 static void
343 {
344  fib_path_list_t *path_list;
345 
346  path_list = fib_path_list_from_fib_node(node);
347 
348  FIB_PATH_LIST_DBG(path_list, "last-lock");
349 
350  if (path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED)
351  {
353  }
354  fib_path_list_destroy(path_list);
355 }
356 
357 /*
358  * fib_path_mk_lb
359  *
360  * update the multipath adj this path-list will contribute to its
361  * children's forwarding.
362  */
363 static void
366  dpo_id_t *dpo)
367 {
368  load_balance_path_t *nhs;
369  fib_node_index_t *path_index;
370 
371  nhs = NULL;
372 
373  if (!dpo_id_is_valid(dpo))
374  {
375  /*
376  * first time create
377  */
378  dpo_set(dpo,
383  0 /* FIXME FLOW HASH */));
384  }
385 
386  /*
387  * We gather the DPOs from resolved paths.
388  */
389  vec_foreach (path_index, path_list->fpl_paths)
390  {
391  nhs = fib_path_append_nh_for_multipath_hash(*path_index,
392  fct,
393  nhs);
394  }
395 
396  /*
397  * Path-list load-balances, which if used, would be shared and hence
398  * never need a load-balance map.
399  */
401 
402  FIB_PATH_LIST_DBG(path_list, "mk lb: %d", dpo->dpoi_index);
403 
404  vec_free(nhs);
405 }
406 
407 /**
408  * @brief [re]build the path list's uRPF list
409  */
410 static void
412 {
413  fib_node_index_t *path_index;
414 
415  /*
416  * ditch the old one. by iterating through all paths we are going
417  * to re-find all the adjs that were in the old one anyway. If we
418  * keep the old one, then the |sort|uniq requires more work.
419  * All users of the RPF list have their own lock, so we can release
420  * immediately.
421  */
422  fib_urpf_list_unlock(path_list->fpl_urpf);
423  path_list->fpl_urpf = fib_urpf_list_alloc_and_lock();
424 
425  vec_foreach (path_index, path_list->fpl_paths)
426  {
427  fib_path_contribute_urpf(*path_index, path_list->fpl_urpf);
428  }
429 
430  fib_urpf_list_bake(path_list->fpl_urpf);
431 }
432 
433 /**
434  * @brief Contribute (add) this path list's uRPF list. This allows the child
435  * to construct an aggregate list.
436  */
437 void
439  index_t urpf)
440 {
441  fib_path_list_t *path_list;
442 
443  path_list = fib_path_list_get(path_list_index);
444 
445  fib_urpf_list_combine(urpf, path_list->fpl_urpf);
446 }
447 
448 /**
449  * @brief Return the the child the RPF list pre-built for this path list
450  */
451 index_t
453 {
454  fib_path_list_t *path_list;
455 
456  path_list = fib_path_list_get(path_list_index);
457 
458  return (path_list->fpl_urpf);
459 }
460 
461 /*
462  * fib_path_list_back_walk
463  *
464  * Called from one of this path-list's paths to progate
465  * a back walk
466  */
467 void
470 {
471  fib_path_list_t *path_list;
472 
473  path_list = fib_path_list_get(path_list_index);
474 
475  fib_path_list_mk_urpf(path_list);
476 
477  /*
478  * propagate the backwalk further
479  */
480  if (32 >= fib_node_list_get_size(path_list->fpl_node.fn_children))
481  {
482  /*
483  * only a few children. continue the walk synchronously
484  */
485  fib_walk_sync(FIB_NODE_TYPE_PATH_LIST, path_list_index, ctx);
486  }
487  else
488  {
489  /*
490  * many children. schedule a async walk
491  */
493  path_list_index,
495  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 thier 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",
525  pool_elts(fib_path_list_pool),
526  pool_len(fib_path_list_pool),
527  sizeof(fib_path_list_t));
529 }
530 
531 /*
532  * The FIB path-list's graph node virtual function table
533  */
534 static const fib_node_vft_t fib_path_list_vft = {
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 fib_path_list_t *
543 {
544  fib_path_list_t *path_list;
545 
546  pool_get(fib_path_list_pool, path_list);
547  memset(path_list, 0, sizeof(*path_list));
548 
549  fib_node_init(&path_list->fpl_node,
551  path_list->fpl_urpf = INDEX_INVALID;
552 
553  if (NULL != path_list_index)
554  {
555  *path_list_index = fib_path_list_get_index(path_list);
556  }
557 
558  FIB_PATH_LIST_DBG(path_list, "alloc");
559 
560  return (path_list);
561 }
562 
563 static fib_path_list_t *
565 {
566  fib_node_index_t *path_index, *paths, path_list_index;
567 
569 
570  /*
571  * resolving a path-list is a recursive action. this means more path
572  * lists can be created during this call, and hence this path-list
573  * can be realloc'd. so we work with copies.
574  * this function is called only once per-path list, so its no great overhead.
575  */
576  path_list_index = fib_path_list_get_index(path_list);
577  paths = vec_dup(path_list->fpl_paths);
578 
579  vec_foreach (path_index, paths)
580  {
581  fib_path_resolve(*path_index);
582  }
583 
584  vec_free(paths);
585  path_list = fib_path_list_get(path_list_index);
586 
587  FIB_PATH_LIST_DBG(path_list, "resovled");
588  fib_path_list_mk_urpf(path_list);
589 
590  return (path_list);
591 }
592 
593 u32
595 {
596  fib_path_list_t *path_list;
597 
598  path_list = fib_path_list_get(path_list_index);
599 
600  return (vec_len(path_list->fpl_paths));
601 }
602 
603 
604 u32
606 {
607  fib_node_index_t *path_index;
608  fib_path_list_t *path_list;
609  u32 sw_if_index;
610 
611  path_list = fib_path_list_get(path_list_index);
612 
613  sw_if_index = ~0;
614  vec_foreach (path_index, path_list->fpl_paths)
615  {
616  sw_if_index = fib_path_get_resolving_interface(*path_index);
617  if (~0 != sw_if_index)
618  {
619  return (sw_if_index);
620  }
621  }
622 
623  return (sw_if_index);
624 }
625 
628 {
629  fib_path_list_t *path_list;
630 
631  path_list = fib_path_list_get(path_list_index);
632 
633  /*
634  * we don't support a mix of path protocols, so we can return the proto
635  * of the first
636  */
637  return (fib_path_get_proto(path_list->fpl_paths[0]));
638 }
639 
640 int
642 {
643  fib_path_list_t *path_list;
644 
645  path_list = fib_path_list_get(path_list_index);
646 
647  return (path_list->fpl_flags & FIB_PATH_LIST_FLAG_LOOPED);
648 }
649 
650 static fib_path_cfg_flags_t
652 {
654 
655  if (plf & FIB_PATH_LIST_FLAG_LOCAL)
656  {
658  }
659  if (plf & FIB_PATH_LIST_FLAG_DROP)
660  {
662  }
664  {
666  }
667 
668  return (pf);
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  * we'll assume for now all paths are the same next-hop protocol
699  */
700  path_list->fpl_nh_proto = rpaths[0].frp_proto;
701 
702  vec_foreach_index(i, rpaths)
703  {
704  vec_add1(path_list->fpl_paths,
705  fib_path_create(path_list_index,
706  path_list->fpl_nh_proto,
708  &rpaths[i]));
709  }
710 
711  /*
712  * If a shared path list is requested, consult the DB for a match
713  */
714  if (flags & FIB_PATH_LIST_FLAG_SHARED)
715  {
716  /*
717  * check for a matching path-list in the DB.
718  * If we find one then we can return the existing one and destroy the
719  * new one just created.
720  */
721  old_path_list_index = fib_path_list_db_find(path_list);
722  if (FIB_NODE_INDEX_INVALID != old_path_list_index)
723  {
724  fib_path_list_destroy(path_list);
725 
726  path_list_index = old_path_list_index;
727  }
728  else
729  {
730  /*
731  * if there was not a matching path-list, then this
732  * new one will need inserting into the DB and resolving.
733  */
734  fib_path_list_db_insert(path_list_index);
735  path_list = fib_path_list_resolve(path_list);
736  }
737  }
738  else
739  {
740  /*
741  * no shared path list requested. resolve and use the one
742  * just created.
743  */
744  path_list = fib_path_list_resolve(path_list);
745  }
746 
747  return (path_list_index);
748 }
749 
753  const dpo_id_t *dpo)
754 {
755  fib_node_index_t path_index, path_list_index;
756  fib_path_list_t *path_list;
757 
758  path_list = fib_path_list_alloc(&path_list_index);
759  path_list->fpl_flags = flags;
760  path_list->fpl_nh_proto = nh_proto;
761 
762  path_index =
763  fib_path_create_special(path_list_index,
764  path_list->fpl_nh_proto,
766  dpo);
767  vec_add1(path_list->fpl_paths, path_index);
768 
769  /*
770  * we don't share path-lists. we can do PIC on them so why bother.
771  */
772  path_list = fib_path_list_resolve(path_list);
773 
774  return (path_list_index);
775 }
776 
777 /*
778  * fib_path_list_copy_and_path_add
779  *
780  * Create a copy of a path-list and append one more path to it.
781  * The path-list returned could either have been newly created, or
782  * can be a shared path-list from the data-base.
783  */
787  const fib_route_path_t *rpaths)
788 {
789  fib_node_index_t path_index, new_path_index, *orig_path_index;
790  fib_path_list_t *path_list, *orig_path_list;
791  fib_node_index_t path_list_index;
792  fib_node_index_t pi;
793 
794  ASSERT(1 == vec_len(rpaths));
795 
796  /*
797  * alloc the new list before we retrieve the old one, lest
798  * the alloc result in a realloc
799  */
800  path_list = fib_path_list_alloc(&path_list_index);
801 
802  orig_path_list = fib_path_list_get(orig_path_list_index);
803 
804  FIB_PATH_LIST_DBG(orig_path_list, "copy-add");
805 
806  flags = fib_path_list_flags_fixup(flags);
807  path_list->fpl_flags = flags;
808  path_list->fpl_nh_proto = orig_path_list->fpl_nh_proto;
809  vec_validate(path_list->fpl_paths, vec_len(orig_path_list->fpl_paths));
810  pi = 0;
811 
812  new_path_index = fib_path_create(path_list_index,
813  path_list->fpl_nh_proto,
815  rpaths);
816 
817  vec_foreach (orig_path_index, orig_path_list->fpl_paths)
818  {
819  /*
820  * don't add duplicate paths
821  * In the unlikely event the path is a duplicate, then we'll
822  * find a matching path-list later and this one will be toast.
823  */
824  if (0 != fib_path_cmp(new_path_index, *orig_path_index))
825  {
826  path_index = fib_path_copy(*orig_path_index, path_list_index);
827  path_list->fpl_paths[pi++] = path_index;
828  }
829  else
830  {
831  _vec_len(path_list->fpl_paths) = vec_len(orig_path_list->fpl_paths);
832  }
833  }
834 
835  path_list->fpl_paths[pi] = new_path_index;
836 
837  /*
838  * we sort the paths since the key for the path-list is
839  * the description of the paths it contains. The paths need to
840  * be sorted else this description will differ.
841  */
843 
844  FIB_PATH_LIST_DBG(path_list, "path-added");
845 
846  /*
847  * If a shared path list is requested, consult the DB for a match
848  */
849  if (path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED)
850  {
851  fib_node_index_t exist_path_list_index;
852  /*
853  * check for a matching path-list in the DB.
854  * If we find one then we can return the existing one and destroy the
855  * new one just created.
856  */
857  exist_path_list_index = fib_path_list_db_find(path_list);
858  if (FIB_NODE_INDEX_INVALID != exist_path_list_index)
859  {
860  fib_path_list_destroy(path_list);
861 
862  path_list_index = exist_path_list_index;
863  }
864  else
865  {
866  /*
867  * if there was not a matching path-list, then this
868  * new one will need inserting into the DB and resolving.
869  */
870  fib_path_list_db_insert(path_list_index);
871 
872  path_list = fib_path_list_resolve(path_list);
873  }
874  }
875  else
876  {
877  /*
878  * no shared path list requested. resolve and use the one
879  * just created.
880  */
881  path_list = fib_path_list_resolve(path_list);
882  }
883 
884  return (path_list_index);
885 }
886 
887 /*
888  * fib_path_list_copy_and_path_remove
889  *
890  * Copy the path-list excluding the path passed.
891  * If the path is the last one, then the index reurned will be invalid.
892  * i.e. the path-list is toast.
893  */
897  const fib_route_path_t *rpaths)
898 {
899  fib_node_index_t path_index, *orig_path_index, path_list_index, tmp_path_index;
900  fib_path_list_t *path_list, *orig_path_list;
901  fib_node_index_t pi;
902 
903  ASSERT(1 == vec_len(rpaths));
904 
905  path_list = fib_path_list_alloc(&path_list_index);
906 
907  flags = fib_path_list_flags_fixup(flags);
908  orig_path_list = fib_path_list_get(orig_path_list_index);
909 
910  FIB_PATH_LIST_DBG(orig_path_list, "copy-remove");
911 
912  path_list->fpl_flags = flags;
913  path_list->fpl_nh_proto = orig_path_list->fpl_nh_proto;
914  /*
915  * allocate as many paths as we might need in one go, rather than
916  * using vec_add to do a few at a time.
917  */
918  if (vec_len(orig_path_list->fpl_paths) > 1)
919  {
920  vec_validate(path_list->fpl_paths, vec_len(orig_path_list->fpl_paths) - 2);
921  }
922  pi = 0;
923 
924  /*
925  * create a representation of the path to be removed, so it
926  * can be used as a comparison object during the copy.
927  */
928  tmp_path_index = fib_path_create(path_list_index,
929  path_list->fpl_nh_proto,
931  rpaths);
932 
933  vec_foreach (orig_path_index, orig_path_list->fpl_paths)
934  {
935  if (0 != fib_path_cmp(tmp_path_index, *orig_path_index)) {
936  path_index = fib_path_copy(*orig_path_index, path_list_index);
937  if (pi < vec_len(path_list->fpl_paths))
938  {
939  path_list->fpl_paths[pi++] = path_index;
940  }
941  else
942  {
943  /*
944  * this is the unlikely case that the path being
945  * removed does not match one in the path-list, so
946  * we end up with as many paths as we started with.
947  * the paths vector was sized above with the expectation
948  * that we would have 1 less.
949  */
950  vec_add1(path_list->fpl_paths, path_index);
951  }
952  }
953  }
954 
955  /*
956  * done with the temporary now
957  */
958  fib_path_destroy(tmp_path_index);
959 
960  /*
961  * if there are no paths, then the new path-list is aborted
962  */
963  if (0 == vec_len(path_list->fpl_paths)) {
964  FIB_PATH_LIST_DBG(path_list, "last-path-removed");
965 
966  fib_path_list_destroy(path_list);
967 
968  path_list_index = FIB_NODE_INDEX_INVALID;
969  } else {
970  /*
971  * we sort the paths since the key for the path-list is
972  * the description of the paths it contains. The paths need to
973  * be sorted else this description will differ.
974  */
976 
977  /*
978  * If a shared path list is requested, consult the DB for a match
979  */
980  if (path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED)
981  {
982  fib_node_index_t exist_path_list_index;
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  exist_path_list_index = fib_path_list_db_find(path_list);
990  if (FIB_NODE_INDEX_INVALID != exist_path_list_index)
991  {
992  fib_path_list_destroy(path_list);
993 
994  path_list_index = exist_path_list_index;
995  }
996  else
997  {
998  /*
999  * if there was not a matching path-list, then this
1000  * new one will need inserting into the DB and resolving.
1001  */
1002  fib_path_list_db_insert(path_list_index);
1003 
1004  path_list = fib_path_list_resolve(path_list);
1005  }
1006  }
1007  else
1008  {
1009  /*
1010  * no shared path list requested. resolve and use the one
1011  * just created.
1012  */
1013  path_list = fib_path_list_resolve(path_list);
1014  }
1015  }
1016 
1017  return (path_list_index);
1018 }
1019 
1020 /*
1021  * fib_path_list_contribute_forwarding
1022  *
1023  * Return the index of a load-balance that user of this path-list should
1024  * use for forwarding
1025  */
1026 void
1029  dpo_id_t *dpo)
1030 {
1031  fib_path_list_t *path_list;
1032 
1033  path_list = fib_path_list_get(path_list_index);
1034 
1035  fib_path_list_mk_lb(path_list, type, dpo);
1036 }
1037 
1038 /*
1039  * fib_path_list_get_adj
1040  *
1041  * Return the index of a adjacency for the first path that user of this
1042  * path-list should use for forwarding
1043  */
1047 {
1048  fib_path_list_t *path_list;
1049 
1050  path_list = fib_path_list_get(path_list_index);
1051  return (fib_path_get_adj(path_list->fpl_paths[0]));
1052 }
1053 
1054 int
1056  fib_node_index_t **entry_indicies)
1057 {
1058  fib_node_index_t *path_index;
1059  int is_looped, list_looped;
1060  fib_path_list_t *path_list;
1061 
1062  list_looped = 0;
1063  path_list = fib_path_list_get(path_list_index);
1064 
1065  vec_foreach (path_index, path_list->fpl_paths)
1066  {
1067  fib_node_index_t *copy, **copy_ptr;
1068 
1069  /*
1070  * we need a copy of the nodes visited so that when we add entries
1071  * we explore on the nth path and a looped is detected, those entries
1072  * are not again searched for n+1 path and so finding a loop that does
1073  * not exist.
1074  */
1075  copy = vec_dup(*entry_indicies);
1076  copy_ptr = &copy;
1077 
1078  is_looped = fib_path_recursive_loop_detect(*path_index, copy_ptr);
1079  list_looped += is_looped;
1080  }
1081 
1082  FIB_PATH_LIST_DBG(path_list, "loop-detect: eval:%d", eval);
1083 
1084  if (list_looped)
1085  {
1086  path_list->fpl_flags |= FIB_PATH_LIST_FLAG_LOOPED;
1087  }
1088  else
1089  {
1090  path_list->fpl_flags &= ~FIB_PATH_LIST_FLAG_LOOPED;
1091  }
1092 
1093  return (list_looped);
1094 }
1095 
1096 u32
1098  fib_node_type_t child_type,
1099  fib_node_index_t child_index)
1100 {
1102  path_list_index,
1103  child_type,
1104  child_index));
1105 }
1106 
1107 void
1109  u32 si)
1110 {
1112  path_list_index,
1113  si);
1114 }
1115 
1116 void
1118 {
1119  fib_path_list_t *path_list;
1120 
1121  if (FIB_NODE_INDEX_INVALID != path_list_index)
1122  {
1123  path_list = fib_path_list_get(path_list_index);
1124 
1125  fib_node_lock(&path_list->fpl_node);
1126  FIB_PATH_LIST_DBG(path_list, "lock");
1127  }
1128 }
1129 
1130 void
1132 {
1133  fib_path_list_t *path_list;
1134 
1135  if (FIB_NODE_INDEX_INVALID != path_list_index)
1136  {
1137  path_list = fib_path_list_get(path_list_index);
1138  FIB_PATH_LIST_DBG(path_list, "unlock");
1139 
1140  fib_node_unlock(&path_list->fpl_node);
1141  }
1142 }
1143 
1144 u32
1146 {
1147  return (pool_elts(fib_path_list_pool));
1148 }
1149 
1150 u32
1152 {
1153  return (hash_elts(fib_path_list_db));
1154 }
1155 
1156 void
1159  void *ctx)
1160 {
1161  fib_node_index_t *path_index;
1162  fib_path_list_t *path_list;
1163 
1164  path_list = fib_path_list_get(path_list_index);
1165 
1166  vec_foreach(path_index, path_list->fpl_paths)
1167  {
1168  if (!func(path_list_index, *path_index, ctx))
1169  break;
1170  }
1171 }
1172 
1173 
1174 void
1176 {
1177  fib_node_register_type (FIB_NODE_TYPE_PATH_LIST, &fib_path_list_vft);
1178 
1179  fib_path_list_db = hash_create2 (/* elts */ 0,
1180  /* user */ 0,
1181  /* value_bytes */ sizeof (fib_node_index_t),
1184  /* format pair/arg */
1185  0, 0);
1186 }
1187 
1188 static clib_error_t *
1190  unformat_input_t * input,
1191  vlib_cli_command_t * cmd)
1192 {
1193  fib_path_list_t *path_list;
1194  fib_node_index_t pli;
1195 
1196  if (unformat (input, "%d", &pli))
1197  {
1198  /*
1199  * show one in detail
1200  */
1201  if (!pool_is_free_index(fib_path_list_pool, pli))
1202  {
1203  path_list = fib_path_list_get(pli);
1204  u8 *s = fib_path_list_format(pli, NULL);
1205  s = format(s, "children:");
1206  s = fib_node_children_format(path_list->fpl_node.fn_children, s);
1207  vlib_cli_output (vm, "%s", s);
1208  vec_free(s);
1209  }
1210  else
1211  {
1212  vlib_cli_output (vm, "path list %d invalid", pli);
1213  }
1214  }
1215  else
1216  {
1217  /*
1218  * show all
1219  */
1220  vlib_cli_output (vm, "FIB Path Lists");
1221  pool_foreach(path_list, fib_path_list_pool,
1222  ({
1223  vlib_cli_output (vm, "%U", format_fib_path_list, path_list);
1224  }));
1225  }
1226  return (NULL);
1227 }
1228 
1229 VLIB_CLI_COMMAND (show_fib_path_list, static) = {
1230  .path = "show fib path-lists",
1231  .function = show_fib_path_list_command,
1232  .short_help = "show fib path-lists",
1233 };
#define vec_validate(V, I)
Make sure vector is long enough for given index (no header, unspecified alignment) ...
Definition: vec.h:396
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)
fib_protocol_t frp_proto
The protocol of the address below.
Definition: fib_types.h:290
int fib_path_resolve(fib_node_index_t path_index)
Definition: fib_path.c:1457
void fib_path_list_module_init(void)
#define vec_foreach_index(var, v)
Iterate over vector indices.
#define hash_set(h, key, value)
Definition: hash.h:254
sll srl srl sll sra u16x4 i
Definition: vector_sse2.h:343
uword fib_path_hash(fib_node_index_t path_index)
Definition: fib_path.c:1169
uword unformat(unformat_input_t *i, char *fmt,...)
Definition: unformat.c:966
fib_protocol_t fib_path_get_proto(fib_node_index_t path_index)
Definition: fib_path.c:1943
void fib_path_list_child_remove(fib_node_index_t path_list_index, u32 si)
enum fib_node_type_t_ fib_node_type_t
The types of nodes in a FIB graph.
#define hash_unset(h, key)
Definition: hash.h:260
void fib_path_contribute_urpf(fib_node_index_t path_index, index_t urpf)
Contribute the path&#39;s adjacency to the list passed.
Definition: fib_path.c:1674
A representation of a path as described by a route producer.
Definition: fib_types.h:285
static uword fib_path_list_db_hash_key_equal(hash_t *h, uword key1, uword key2)
bad routing header type(not 4)") sr_error (NO_MORE_SEGMENTS
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:1277
void fib_node_init(fib_node_t *node, fib_node_type_t type)
Definition: fib_node.c:183
u32 fib_path_list_get_resolving_interface(fib_node_index_t path_list_index)
static int dpo_id_is_valid(const dpo_id_t *dpoi)
Return true if the DPO object is valid, i.e.
Definition: dpo.h:177
u8 * format_fib_urpf_list(u8 *s, va_list args)
Definition: fib_urpf_list.c:25
#define NULL
Definition: clib.h:55
enum fib_node_back_walk_rc_t_ fib_node_back_walk_rc_t
Return code from a back walk function.
fib_node_index_t * fpl_paths
Vector of paths indicies for all configured paths.
Definition: fib_path_list.c:54
void fib_urpf_list_show_mem(void)
dpo_proto_t fib_forw_chain_type_to_dpo_proto(fib_forward_chain_type_t fct)
Convert from a chain type to the DPO proto it will install.
Definition: fib_types.c:311
fib_protocol_t fib_path_list_get_proto(fib_node_index_t path_list_index)
u32 index_t
A Data-Path Object is an object that represents actions that are applied to packets are they are swit...
Definition: dpo.h:41
#define vec_add1(V, E)
Add 1 element to end of vector (unspecified alignment).
Definition: vec.h:482
static uword * fib_path_list_db
Definition: fib_path_list.c:75
void fib_path_list_walk(fib_node_index_t path_list_index, fib_path_list_walk_fn_t func, void *ctx)
void fib_node_deinit(fib_node_t *node)
Definition: fib_node.c:198
void fib_walk_async(fib_node_type_t parent_type, fib_node_index_t parent_index, fib_walk_priority_t prio, fib_node_back_walk_ctx_t *ctx)
Definition: fib_walk.c:620
static uword fib_path_list_db_hash_key_from_index(uword index)
u8 * fib_path_adj_format(fib_node_index_t pi, u32 indent, u8 *s)
Definition: fib_path.c:486
#define FOR_EACH_PATH_LIST_ATTRIBUTE(_item)
Definition: fib_path_list.h:88
#define pool_get(P, E)
Allocate an object E from a pool P (unspecified alignment).
Definition: pool.h:200
int fib_path_cmp_for_sort(void *v1, void *v2)
Definition: fib_path.c:1259
u32 fib_path_list_child_add(fib_node_index_t path_list_index, fib_node_type_t child_type, fib_node_index_t child_index)
static void fib_path_list_mk_urpf(fib_path_list_t *path_list)
[re]build the path list&#39;s uRPF list
#define pool_len(p)
Number of elements in pool vector.
Definition: pool.h:121
FIB path-list A representation of the list/set of path trough which a prefix is reachable.
Definition: fib_path_list.c:32
static fib_path_list_t * fib_path_list_pool
Definition: fib_path_list.c:70
enum fib_protocol_t_ fib_protocol_t
Protocol Type.
load_balance_path_t * fib_path_append_nh_for_multipath_hash(fib_node_index_t path_index, fib_forward_chain_type_t fct, load_balance_path_t *hash_key)
Definition: fib_path.c:1823
u32 fib_node_child_add(fib_node_type_t parent_type, fib_node_index_t parent_index, fib_node_type_t type, fib_node_index_t index)
Definition: fib_node.c:96
static const char * fib_path_list_attr_names[]
Definition: fib_path_list.c:65
void fib_node_register_type(fib_node_type_t type, const fib_node_vft_t *vft)
fib_node_register_type
Definition: fib_node.c:58
index_t load_balance_create(u32 n_buckets, dpo_proto_t lb_proto, flow_hash_config_t fhc)
Definition: load_balance.c:192
fib_node_t fpl_node
A path-list is a node in the FIB graph.
Definition: fib_path_list.c:36
fib_node_index_t fib_path_create(fib_node_index_t pl_index, fib_protocol_t nh_proto, fib_path_cfg_flags_t flags, const fib_route_path_t *rpath)
Definition: fib_path.c:974
static uword fib_path_list_db_hash_key_is_index(uword key)
#define pool_foreach(VAR, POOL, BODY)
Iterate through pool.
Definition: pool.h:348
#define always_inline
Definition: clib.h:84
void fib_walk_sync(fib_node_type_t parent_type, fib_node_index_t parent_index, fib_node_back_walk_ctx_t *ctx)
Back walk all the children of a FIB node.
Definition: fib_walk.c:674
index_t fib_urpf_list_alloc_and_lock(void)
Definition: fib_urpf_list.c:47
fib_node_index_t fib_path_create_special(fib_node_index_t pl_index, fib_protocol_t nh_proto, fib_path_cfg_flags_t flags, const dpo_id_t *dpo)
Definition: fib_path.c:1070
fib_node_index_t fib_path_copy(fib_node_index_t path_index, fib_node_index_t path_list_index)
Definition: fib_path.c:1115
static void fib_path_list_destroy(fib_path_list_t *path_list)
void fib_show_memory_usage(const char *name, u32 in_use_elts, u32 allocd_elts, size_t size_elt)
Show the memory usage for a type.
Definition: fib_node.c:221
static uword fib_path_list_hash(fib_path_list_t *path_list)
void load_balance_multipath_update(const dpo_id_t *dpo, const load_balance_path_t *raw_nhs, load_balance_flags_t flags)
Definition: load_balance.c:471
enum fib_path_list_attribute_t_ fib_path_list_attribute_t
Enumeration of path-list flags.
static fib_path_list_t * fib_path_list_alloc(fib_node_index_t *path_list_index)
u32 fib_path_list_db_size(void)
fib_node_index_t fib_path_list_copy_and_path_add(fib_node_index_t orig_path_list_index, fib_path_list_flags_t flags, const fib_route_path_t *rpaths)
The identity of a DPO is a combination of its type and its instance number/index of objects of that t...
Definition: dpo.h:138
static uword fib_path_list_db_hash_key_2_index(uword key)
#define hash_get(h, key)
Definition: hash.h:248
#define pool_elt_at_index(p, i)
Returns pointer to element at given index.
Definition: pool.h:369
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:79
static fib_node_back_walk_rc_t fib_path_list_back_walk_notify(fib_node_t *node, fib_node_back_walk_ctx_t *ctx)
void fib_node_lock(fib_node_t *node)
Definition: fib_node.c:204
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:1641
#define pool_put(P, E)
Free an object E in pool P.
Definition: pool.h:214
#define vec_dup(V)
Return copy of vector (no header, no alignment)
Definition: vec.h:334
void fib_path_list_lock(fib_node_index_t path_list_index)
fib_node_type_t fn_type
The node&#39;s type.
Definition: fib_node.h:278
An node in the FIB graph.
Definition: fib_node.h:273
void fib_node_unlock(fib_node_t *node)
Definition: fib_node.c:210
void vlib_cli_output(vlib_main_t *vm, char *fmt,...)
Definition: cli.c:576
fib_path_list_flags_t fpl_flags
Flags on the path-list.
Definition: fib_path_list.c:41
#define uword_to_pointer(u, type)
Definition: types.h:136
fib_node_index_t fib_path_list_copy_and_path_remove(fib_node_index_t orig_path_list_index, fib_path_list_flags_t flags, const fib_route_path_t *rpaths)
fib_node_list_t fn_children
Vector of nodes that depend upon/use/share this node.
Definition: fib_node.h:290
static void fib_path_list_last_lock_gone(fib_node_t *node)
#define hash_mix64(a0, b0, c0)
Definition: hash.h:507
u8 * fib_path_format(fib_node_index_t pi, u8 *s)
Definition: fib_path.c:475
#define vec_free(V)
Free vector&#39;s memory (no header).
Definition: vec.h:300
#define FIB_PATH_LIST_DBG(_pl, _fmt, _args...)
Definition: fib_path_list.c:93
void fib_urpf_list_bake(index_t ui)
Convert the uRPF list from the itf set obtained during the walk to a unique list. ...
static u8 * format_fib_path_list(u8 *s, va_list *args)
static fib_path_cfg_flags_t fib_path_list_flags_2_path_flags(fib_path_list_flags_t plf)
fib_node_get_t fnv_get
Definition: fib_node.h:261
#define hash_mix32(a0, b0, c0)
Definition: hash.h:515
u32 fib_path_list_get_n_paths(fib_node_index_t path_list_index)
u32 fib_node_index_t
A typedef of a node index.
Definition: fib_types.h:28
#define pool_is_free_index(P, I)
Use free bitmap to query whether given index is free.
Definition: pool.h:211
u32 adj_index_t
An index for adjacencies.
Definition: adj_types.h:30
int(* 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.
fib_node_index_t fpl_urpf
the RPF list calculated for this path list
Definition: fib_path_list.c:59
static fib_path_list_t * fib_path_list_get(fib_node_index_t index)
Definition: fib_path_list.c:97
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:154
void fib_path_list_unlock(fib_node_index_t path_list_index)
#define hash_create2(_elts, _user, _value_bytes,_key_sum, _key_equal,_format_pair, _format_pair_arg)
Definition: hash.h:470
Context passed between object during a back walk.
Definition: fib_node.h:186
#define VLIB_CLI_COMMAND(x,...)
Definition: cli.h:154
int fib_path_list_recursive_loop_detect(fib_node_index_t path_list_index, fib_node_index_t **entry_indicies)
static fib_path_list_t * fib_path_list_from_fib_node(fib_node_t *node)
int fib_path_list_is_looped(fib_node_index_t path_list_index)
u32 fib_node_list_get_size(fib_node_list_t list)
static uword hash_elts(void *v)
Definition: hash.h:117
#define ASSERT(truth)
unsigned int u32
Definition: types.h:88
static fib_path_list_t * fib_path_list_resolve(fib_path_list_t *path_list)
static void fib_path_list_db_insert(fib_node_index_t path_list_index)
void fib_urpf_list_combine(index_t ui1, index_t ui2)
Combine to interface lists.
enum fib_forward_chain_type_t_ fib_forward_chain_type_t
FIB output chain type.
void fib_node_child_remove(fib_node_type_t parent_type, fib_node_index_t parent_index, fib_node_index_t sibling_index)
Definition: fib_node.c:121
void fib_path_list_contribute_forwarding(fib_node_index_t path_list_index, fib_forward_chain_type_t type, dpo_id_t *dpo)
fib_protocol_t fpl_nh_proto
The next-hop protocol for the paths in this path list.
Definition: fib_path_list.c:48
static fib_path_list_flags_t fib_path_list_flags_fixup(fib_path_list_flags_t flags)
u8 * format_fib_protocol(u8 *s, va_list ap)
Definition: fib_types.c:30
static fib_node_index_t fib_path_list_get_index(fib_path_list_t *path_list)
u64 uword
Definition: types.h:112
void fib_path_list_back_walk(fib_node_index_t path_list_index, fib_node_back_walk_ctx_t *ctx)
u32 fib_path_get_resolving_interface(fib_node_index_t path_index)
Definition: fib_path.c:1616
index_t dpoi_index
the index of objects of that type
Definition: dpo.h:154
#define FIB_NODE_INDEX_INVALID
Definition: fib_types.h:29
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
unsigned char u8
Definition: types.h:56
u32 fn_locks
Number of dependents on this node.
Definition: fib_node.h:296
#define INDEX_INVALID
Invalid index - used when no index is known blazoned capitals INVALID speak volumes where ~0 does not...
Definition: dpo.h:47
static fib_path_list_t * fib_path_list_db_get_from_hash_key(uword key)
u8 * fib_path_list_format(fib_node_index_t path_list_index, u8 *s)
#define vec_sort_with_function(vec, f)
Sort a vector using the supplied element comparison function.
Definition: vec.h:920
void fib_urpf_list_unlock(index_t ui)
Definition: fib_urpf_list.c:60
One path from an [EU]CMP set that the client wants to add to a load-balance object.
Definition: load_balance.h:61
enum fib_path_cfg_flags_t_ fib_path_cfg_flags_t
Path config flags from the attributes.
static void fib_path_list_mk_lb(fib_path_list_t *path_list, fib_forward_chain_type_t fct, dpo_id_t *dpo)
int fib_path_recursive_loop_detect(fib_node_index_t path_index, fib_node_index_t **entry_indicies)
Definition: fib_path.c:1377
A FIB graph nodes virtual function table.
Definition: fib_node.h:260
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)
u8 * format(u8 *s, const char *fmt,...)
Definition: format.c:418
u8 * fib_path_list_adjs_format(fib_node_index_t path_list_index, u32 indent, u8 *s)
u32 fib_path_list_pool_size(void)
#define vec_foreach(var, vec)
Vector iterator.
enum fib_path_list_flags_t_ fib_path_list_flags_t
struct _unformat_input_t unformat_input_t
u32 flags
Definition: vhost-user.h:75
u8 * fib_node_children_format(fib_node_list_t list, u8 *s)
Definition: fib_node.c:174
static fib_node_t * fib_path_list_get_node(fib_node_index_t index)
struct fib_path_list_t_ fib_path_list_t
FIB path-list A representation of the list/set of path trough which a prefix is reachable.
void fib_path_destroy(fib_node_index_t path_index)
Definition: fib_path.c:1148
fib_node_index_t fib_path_list_create_special(fib_protocol_t nh_proto, fib_path_list_flags_t flags, const dpo_id_t *dpo)
static uword fib_path_list_db_hash_key_sum(hash_t *h, uword key)
static uword pool_elts(void *v)
Number of active elements in a pool.
Definition: pool.h:109