FD.io VPP  v20.01-48-g3e0dafb74
Vector Packet Processing
bier_table.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/vec.h>
17 
18 #include <vnet/bier/bier_table.h>
19 #include <vnet/bier/bier_entry.h>
20 #include <vnet/bier/bier_update.h>
22 #include <vnet/bier/bier_fmask.h>
24 
25 #include <vnet/fib/mpls_fib.h>
26 #include <vnet/mpls/mpls.h>
27 #include <vnet/fib/fib_path_list.h>
28 
29 /**
30  * Memory pool of all the allocated tables
31  */
33 
34 /**
35  * DB store of all BIER tables index by SD/set/hdr-len
36  */
38 
39 /**
40  * The magic number of BIER ECMP tables to create.
41  * The load-balance distribution algorithm will use a power of 2
42  * for the number of buckets, which constrains the choice.
43  */
44 #define BIER_N_ECMP_TABLES 16
45 
46 static inline index_t
48 {
49  return (bt - bier_table_pool);
50 }
51 
52 int
54 {
55  return (BIER_ECMP_TABLE_ID_MAIN == bt->bt_id.bti_ecmp);
56 }
57 
58 /*
59  * Construct the key to use to find a BIER table
60  * in the global hash map
61  */
62 static u32
64 {
65  /*
66  * the set and sub-domain Ids are 8 bit values.
67  * we have space for ECMP table ID and talbe type (SPF/TE)
68  * for later
69  */
70  u32 key = ((id->bti_sub_domain << 24) |
71  (id->bti_set << 16) |
72  (id->bti_ecmp << 8) |
73  (id->bti_hdr_len << 4) |
74  (id->bti_type));
75 
76  return (key);
77 }
78 
79 static void
81  const bier_table_id_t *id,
82  mpls_label_t ll)
83 {
84  u32 num_entries;
85 
87  bt->bt_id = *id;
88  bt->bt_ll = ll;
90 
91  /*
92  * create the lookup table of entries.
93  */
94  if (bier_table_is_main(bt))
95  {
97  num_entries,
100  }
101  else
102  {
104  num_entries,
107  }
108 }
109 
110 static void
112 {
114 
116  bt->bt_id.bti_sub_domain,
117  bt->bt_id.bti_hdr_len));
118 }
119 
120 static void
122 {
123  dpo_id_t dpo = DPO_INVALID;
124 
126 
128 
130  bt->bt_id.bti_sub_domain,
131  bt->bt_id.bti_hdr_len),
132  &dpo);
133 
134  dpo_reset(&dpo);
135 }
136 
137 static void
139 {
140  if (FIB_NODE_INDEX_INVALID != bt->bt_lfei)
141  {
147  }
149 }
150 
151 static void
153 {
154  if (bier_table_is_main(bt))
155  {
156  index_t *bei;
157 
158  if (MPLS_LABEL_INVALID != bt->bt_ll)
159  {
160  bier_table_rm_lfib(bt);
161  }
162  else
163  {
164  bier_table_rm_bift(bt);
165  }
166 
169  /*
170  * unresolve/remove all entries from the table
171  */
172  vec_foreach (bei, bt->bt_entries)
173  {
174  if (INDEX_INVALID != *bei)
175  {
176  bier_entry_delete(*bei);
177  }
178  }
179  vec_free (bt->bt_entries);
180  }
181  else
182  {
183  index_t *bfmi;
184 
185  /*
186  * unlock any fmasks
187  */
188  vec_foreach (bfmi, bt->bt_fmasks)
189  {
190  bier_fmask_unlock(*bfmi);
191  }
192  vec_free(bt->bt_fmasks);
193  }
194 
196  bier_table_mk_key(&bt->bt_id));
197  pool_put(bier_table_pool, bt);
198 }
199 
200 static void
202 {
203  bt->bt_locks++;
204 }
205 
206 static void
208 {
209  bt->bt_locks--;
210 
211  if (0 == bt->bt_locks)
212  {
213  bier_table_destroy(bt);
214  }
215 }
216 
217 void
219 {
220  uword *p;
221  u32 key;
222 
223  key = bier_table_mk_key(bti);
224 
225  p = hash_get (bier_tables_by_key, key);
226 
227  if (NULL != p) {
229  }
230 }
231 
232 static void
234 {
235  /*
236  * Add a new MPLS lfib entry
237  */
238  if (MPLS_LABEL_INVALID != bt->bt_ll) {
239  fib_prefix_t pfx = {
241  .fp_len = 21,
242  .fp_label = bt->bt_ll,
243  .fp_eos = MPLS_EOS,
244  .fp_payload_proto = DPO_PROTO_BIER,
245  };
246  u32 mpls_fib_index;
247  dpo_id_t dpo = DPO_INVALID;
248 
252 
253  /*
254  * stack the entry on the forwarding chain produced by the
255  * path-list via the ECMP tables.
256  */
260  &dpo);
261 
262  mpls_fib_index = fib_table_find(FIB_PROTOCOL_MPLS,
264  bt->bt_lfei = fib_table_entry_special_dpo_add(mpls_fib_index,
265  &pfx,
268  &dpo);
269  dpo_reset(&dpo);
270  }
271 }
272 
273 static bier_table_t *
275 {
276  uword *p;
277  u32 key;
278 
279  key = bier_table_mk_key(bti);
280 
281  p = hash_get(bier_tables_by_key, key);
282 
283  if (NULL != p)
284  {
285  return (bier_table_get(p[0]));
286  }
287 
288  return (NULL);
289 }
290 
291 static bier_table_t *
293 {
294  fib_route_path_t *rpaths;
295  fib_node_index_t pli;
296  bier_table_t *bt;
297  int ii;
298 
299  rpaths = NULL;
300  bt = bier_table_get(bti);
301 
302  vec_validate(rpaths, BIER_N_ECMP_TABLES-1);
303 
304  vec_foreach_index(ii, rpaths)
305  {
306  rpaths[ii].frp_bier_tbl = bt->bt_id;
307  rpaths[ii].frp_bier_tbl.bti_ecmp = ii;
309  }
310 
311  /*
312  * no opportunity to share, this the resolving ECMP tables are unique
313  * to this table.
314  * no need to be a child of the path list, we can do nothing with any
315  * notifications it would generate [not that it will].
316  */
318  fib_path_list_lock(pli);
319 
320  /*
321  * constructing the path-list will have created many more BIER tables,
322  * so this main table will no doubt have re-alloc.
323  */
324  bt = bier_table_get(bti);
325  bt->bt_pl = pli;
326 
327  vec_free(rpaths);
328 
329  return (bt);
330 }
331 
332 
333 static index_t
335  mpls_label_t local_label)
336 {
337  /*
338  * add a new table
339  */
340  bier_table_t *bt;
341  index_t bti;
342  u32 key;
343 
344  key = bier_table_mk_key(btid);
345 
346  pool_get_aligned(bier_table_pool, bt, CLIB_CACHE_LINE_BYTES);
347  bier_table_init(bt, btid, local_label);
348 
350  bti = bier_table_get_index(bt);
351 
352  if (bier_table_is_main(bt))
353  {
354  bt = bier_table_mk_ecmp(bti);
355 
356  /*
357  * add whichever mpls-fib or bift we need
358  */
359  if (local_label != MPLS_LABEL_INVALID)
360  {
361  bt->bt_ll = local_label;
362  bier_table_mk_lfib(bt);
363  }
364  else
365  {
366  bier_table_mk_bift(bt);
367  }
368  }
369 
370  return (bti);
371 }
372 
373 index_t
375 {
376  bier_table_t *bt;
377  index_t bti;
378 
379  bt = bier_table_find(btid);
380 
381  if (NULL == bt)
382  {
384  bt = bier_table_get(bti);
385  }
386  else
387  {
388  bti = bier_table_get_index(bt);
389  }
390 
391  bier_table_lock_i(bt);
392 
393  return (bti);
394 }
395 
396 index_t
398  mpls_label_t local_label)
399 {
400  bier_table_t *bt;
401  index_t bti;
402 
403  bt = bier_table_find(btid);
404 
405  if (NULL != bt) {
406  /*
407  * modify an existing table.
408  * change the lfib entry to the new local label
409  */
410  if (bier_table_is_main(bt))
411  {
412  /*
413  * remove the mpls-fib or bift entry
414  */
415  if (MPLS_LABEL_INVALID != bt->bt_ll)
416  {
417  bier_table_rm_lfib(bt);
418  }
419  else
420  {
421  bier_table_rm_bift(bt);
422  }
423 
424  /*
425  * reset
426  */
428 
429  /*
430  * add whichever mpls-fib or bift we need
431  */
432  if (local_label != MPLS_LABEL_INVALID)
433  {
434  bt->bt_ll = local_label;
435  bier_table_mk_lfib(bt);
436  }
437  else
438  {
439  bier_table_mk_bift(bt);
440  }
441  }
442  bti = bier_table_get_index(bt);
443  }
444  else
445  {
446  bti = bier_table_create(btid, local_label);
447  bt = bier_table_get(bti);
448  }
449 
450  bier_table_lock_i(bt);
451 
452  return (bti);
453 }
454 
455 index_t
457 {
459 }
460 
461 void
463 {
465 }
466 
467 static void
469 {
470 }
471 
472 static void
474 {
475 }
476 
477 static void
479 {
480  fib_show_memory_usage("BIER-table",
481  pool_elts(bier_table_pool),
482  pool_len(bier_table_pool),
483  sizeof(bier_table_t));
484 }
485 static u8 *
486 format_bier_table_dpo (u8 *s, va_list *ap)
487 {
488  index_t bti = va_arg(*ap, index_t);
489  bier_table_t *bt;
490 
491  bt = bier_table_get(bti);
492 
493  return (format(s, "[%U]", format_bier_table_id, &bt->bt_id));
494 }
495 
496 const static dpo_vft_t bier_table_dpo_vft = {
498  .dv_unlock = bier_table_dpo_unlock,
499  .dv_format = format_bier_table_dpo,
500  .dv_mem_show = bier_table_dpo_mem_show,
501 };
502 
503 const static char *const bier_table_mpls_nodes[] =
504 {
505  "bier-input",
506  NULL
507 };
508 const static char * const * const bier_table_nodes[DPO_PROTO_NUM] =
509 {
511 };
512 
513 static clib_error_t *
515 {
516  dpo_register(DPO_BIER_TABLE, &bier_table_dpo_vft, bier_table_nodes);
517 
518  return (NULL);
519 }
520 
522 
523 const bier_table_id_t *
525 {
526  bier_table_t *bt;
527 
528  bt = bier_table_get(bti);
529 
530  return (&bt->bt_id);
531 }
532 
533 static void
535  bier_bp_t bp,
536  index_t bei)
537 {
538  bt->bt_entries[BIER_BP_TO_INDEX(bp)] = bei;
539 }
540 
541 static void
543  bier_bp_t bp)
544 {
546 }
547 
548 void
550  bier_bp_t bp,
551  fib_route_path_t *brps,
552  u8 is_replace)
553 {
554  index_t bfmi, bti, bei, *bfmip, *bfmis = NULL;
555  fib_route_path_t *brp;
556  bier_table_t *bt;
557 
558  bt = bier_table_find(btid);
559 
560  if (NULL == bt) {
561  return;
562  }
563 
564  bti = bier_table_get_index(bt);
565  bei = bier_table_lookup(bt, bp);
566 
567  /*
568  * set the FIB index in the path to the BIER table index
569  */
570  vec_foreach(brp, brps)
571  {
572  /*
573  * First use the path to find or construct an FMask object
574  * via the next-hop
575  */
576  bfmi = bier_fmask_db_find_or_create_and_lock(bti, brp);
577  vec_add1(bfmis, bfmi);
578 
579  /*
580  * then modify the path to resolve via this fmask object
581  * and use it to resolve the BIER entry.
582  */
584  brp->frp_bier_fmask = bfmi;
585  }
586 
587  if (INDEX_INVALID == bei)
588  {
589  bei = bier_entry_create(bti, bp);
590  bier_table_insert(bt, bp, bei);
591  }
592 
593  if (is_replace)
594  {
595  bier_entry_path_update(bei, brps);
596  }
597  else
598  {
599  fib_route_path_t *t_paths = NULL;
600 
601  vec_foreach(brp, brps)
602  {
603  vec_add1(t_paths, *brp);
604  bier_entry_path_add(bei, t_paths);
605  vec_reset_length(t_paths);
606  }
607  vec_free(t_paths);
608  }
609 
610  vec_foreach(bfmip, bfmis)
611  {
612  bier_fmask_unlock(*bfmip);
613  }
614  vec_free(bfmis);
615 }
616 
617 void
619  bier_bp_t bp,
620  fib_route_path_t *brps)
621 {
622  bier_table_route_path_update_i(btid, bp, brps, 1);
623 }
624 void
626  bier_bp_t bp,
627  fib_route_path_t *brps)
628 {
629  bier_table_route_path_update_i(btid, bp, brps, 0);
630 }
631 
632 void
634  bier_bp_t bp)
635 {
636  bier_table_t *bt;
637  index_t bei;
638 
639  bt = bier_table_find(btid);
640 
641  if (NULL == bt) {
642  return;
643  }
644 
645  bei = bier_table_lookup(bt, bp);
646 
647  if (INDEX_INVALID == bei)
648  {
649  /* no such entry */
650  return;
651  }
652 
653  bier_table_remove(bt, bp);
654  bier_entry_delete(bei);
655 }
656 
657 void
659  bier_bp_t bp,
660  fib_route_path_t *brps)
661 {
662  fib_route_path_t *brp = NULL, *t_paths = NULL;
663  index_t bfmi, bti, bei;
664  bier_table_t *bt;
665  u32 ii;
666 
667  bt = bier_table_find(btid);
668 
669  if (NULL == bt) {
670  return;
671  }
672 
673  bti = bier_table_get_index(bt);
674  bei = bier_table_lookup(bt, bp);
675 
676  if (INDEX_INVALID == bei)
677  {
678  /* no such entry */
679  return;
680  }
681 
682  /*
683  * set the FIB index in the path to the BIER table index
684  */
685  vec_foreach_index(ii, brps)
686  {
687  brp = &brps[ii];
688  bfmi = bier_fmask_db_find(bti, brp);
689 
690  if (INDEX_INVALID == bfmi)
691  {
692  /*
693  * no matching fmask, not a path we can remove
694  */
695  vec_del1(brps, ii);
696  continue;
697  }
698 
699  /*
700  * then modify the path to resolve via this fmask object
701  * and use it to resolve the BIER entry.
702  */
704  brp->frp_bier_fmask = bfmi;
705  }
706 
707  if (0 == vec_len(brps))
708  {
709  return;
710  }
711 
712  vec_foreach(brp, brps)
713  {
714  vec_add1(t_paths, *brp);
715  if (0 == bier_entry_path_remove(bei, t_paths))
716  {
717  /* 0 remaining paths */
718  bier_table_remove(bt, bp);
719  bier_entry_delete(bei);
720  break;
721  }
722  vec_reset_length(t_paths);
723  }
724  vec_free(t_paths);
725 }
726 
727 void
729  dpo_id_t *dpo)
730 {
731  bier_table_t *bt;
732 
733  bt = bier_table_get(bti);
734 
736  {
737  /*
738  * return the load-balance for the ECMP tables
739  */
743  dpo);
744  }
745  else
746  {
748  }
749 }
750 
752 {
754  void *ctx;
756 
759  fib_node_index_t path_index,
760  void *arg)
761 {
763 
764  ctx->fn(fib_path_get_resolving_index(path_index), ctx->ctx);
765  /* continue */
767 }
768 
769 void
772  void *ctx)
773 {
775  .fn = fn,
776  .ctx = ctx,
777  };
778  bier_table_t *bt;
779 
780  bt = bier_table_get(bti);
781 
782  if (FIB_NODE_INDEX_INVALID != bt->bt_pl)
783  {
786  &ewc);
787  }
788 }
789 
790 void
792  bier_bp_t bp,
793  index_t bfmi)
794 {
795  bier_table_t *bt;
796 
797  bt = bier_table_get(bti);
798 
799  /*
800  * we hold a lock for fmasks in the table
801  */
802  bier_fmask_lock(bfmi);
804 
805  bt->bt_fmasks[BIER_BP_TO_INDEX(bp)] = bfmi;
806 }
807 
808 u8 *
809 format_bier_table_entry (u8 *s, va_list *ap)
810 {
811  index_t bti = va_arg(*ap, index_t);
812  bier_bp_t bp = va_arg(*ap, bier_bp_t);
813  bier_table_t *bt;
814  bt = bier_table_get(bti);
815 
816  if (bier_table_is_main(bt))
817  {
818  index_t bei;
819 
820  bei = bier_table_lookup(bier_table_get(bti), bp);
821 
822  if (INDEX_INVALID != bei)
823  {
824  s = format(s, "%U", format_bier_entry, bei,
826  }
827  }
828  else
829  {
830  index_t bfmi;
831 
832  bfmi = bier_table_fwd_lookup(bier_table_get(bti), bp);
833 
834  if (INDEX_INVALID != bfmi)
835  {
836  s = format(s, "%U", format_bier_fmask, bfmi,
838  }
839  }
840  return (s);
841 }
842 
843 u8 *
844 format_bier_table (u8 *s, va_list *ap)
845 {
846  index_t bti = va_arg(*ap, index_t);
848  bier_table_t *bt;
849 
850  if (pool_is_free_index(bier_table_pool, bti))
851  {
852  return (format(s, "No BIER table %d", bti));
853  }
854 
855  bt = bier_table_get(bti);
856 
857  s = format(s, "[@%d] bier-table:[%U local-label:%U",
858  bti,
861 
862  if (flags & BIER_SHOW_DETAIL)
863  {
864  s = format(s, " locks:%d", bt->bt_locks);
865  }
866  s = format(s, "]");
867 
868  if (flags & BIER_SHOW_DETAIL)
869  {
870  if (bier_table_is_main(bt))
871  {
872  index_t *bei;
873 
874  vec_foreach (bei, bt->bt_entries)
875  {
876  if (INDEX_INVALID != *bei)
877  {
878  s = format(s, "\n%U", format_bier_entry, *bei, 2);
879  }
880  }
881  }
882  else
883  {
884  u32 ii;
885 
886  vec_foreach_index (ii, bt->bt_fmasks)
887  {
888  if (INDEX_INVALID != bt->bt_fmasks[ii])
889  {
890  s = format(s, "\n bp:%d\n %U", ii,
891  format_bier_fmask, bt->bt_fmasks[ii], 2);
892  }
893  }
894  }
895  }
896 
897  return (s);
898 }
899 
900 void
903 {
904  if (!pool_elts(bier_table_pool))
905  {
906  vlib_cli_output (vm, "No BIER tables");
907  }
908  else
909  {
910  int ii;
911 
912  pool_foreach_index(ii, bier_table_pool,
913  ({
914  vlib_cli_output (vm, "%U", format_bier_table, ii, flags);
915  }));
916  }
917 }
918 
919 void
921  void *ctx)
922 {
923  ASSERT(0);
924 }
925 
926 
927 void
930  void *ctx)
931 {
932  bier_table_t *bt;
933  bier_entry_t *be;
934  index_t *bei;
935 
936  bt = bier_table_find(bti);
937 
938  if (NULL == bt)
939  {
940  return;
941  }
942 
943  vec_foreach (bei, bt->bt_entries)
944  {
945  if (INDEX_INVALID != *bei)
946  {
947  be = bier_entry_get(*bei);
948 
949  fn(bt, be, ctx);
950  }
951  }
952 }
static bier_table_t * bier_table_mk_ecmp(index_t bti)
Definition: bier_table.c:292
void bier_entry_path_update(index_t bei, const fib_route_path_t *rpaths)
Definition: bier_entry.c:240
#define vec_validate(V, I)
Make sure vector is long enough for given index (no header, unspecified alignment) ...
Definition: vec.h:440
fib_protocol_t fp_proto
protocol type
Definition: fib_types.h:212
dpo_lock_fn_t dv_lock
A reference counting lock function.
Definition: dpo.h:406
Contribute an object that is to be used to forward BIER packets.
Definition: fib_types.h:122
#define vec_foreach_index(var, v)
Iterate over vector indices.
#define hash_set(h, key, value)
Definition: hash.h:255
u8 * format_bier_fmask(u8 *s, va_list *ap)
Definition: bier_fmask.c:344
static void bier_table_mk_bift(bier_table_t *bt)
Definition: bier_table.c:121
A virtual function table regisitered for a DPO type.
Definition: dpo.h:401
#define hash_unset(h, key)
Definition: hash.h:261
void bier_fmask_lock(index_t bfmi)
Definition: bier_fmask.c:269
u32 bier_fmask_db_find_or_create_and_lock(index_t bti, const fib_route_path_t *rpath)
index_t fib_path_get_resolving_index(fib_node_index_t path_index)
Definition: fib_path.c:2197
A representation of a path as described by a route producer.
Definition: fib_types.h:485
#define BIER_N_ECMP_TABLES
The magic number of BIER ECMP tables to create.
Definition: bier_table.c:44
u8 * format_bier_table(u8 *s, va_list *ap)
Definition: bier_table.c:844
u16 bt_locks
Number of locks on the table.
Definition: bier_table.h:64
u8 * format_bier_table_id(u8 *s, va_list *ap)
Format a BIER table ID.
Definition: bier_types.c:193
index_t * bt_fmasks
f-masks in the ECMP table This is a vector sized to the appropriate number of entries given the table...
Definition: bier_table.h:86
enum bier_show_flags_t_ bier_show_flags_t
Flags to control show output.
static const char *const *const bier_table_nodes[DPO_PROTO_NUM]
Definition: bier_table.c:508
static index_t bier_table_get_index(const bier_table_t *bt)
Definition: bier_table.c:47
void bier_entry_delete(index_t bei)
Definition: bier_entry.c:143
#define NULL
Definition: clib.h:58
void bier_table_ecmp_unlock(index_t bti)
Definition: bier_table.c:462
u32 mpls_label_t
A label value only, i.e.
Definition: packet.h:26
From the BIER subsystem.
Definition: fib_source.h:64
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:523
static index_t bier_table_create(const bier_table_id_t *btid, mpls_label_t local_label)
Definition: bier_table.c:334
index_t bier_entry_create(index_t bti, bier_bp_t bp)
Definition: bier_entry.c:62
void(* bier_table_ecmp_walk_fn_t)(index_t btei, void *ctx)
Types and functions to walk the ECMP tables of a main table.
Definition: bier_table.h:129
A path that resolves via a BIER [ECMP] Table.
Definition: fib_types.h:375
void fib_path_list_walk(fib_node_index_t path_list_index, fib_path_list_walk_fn_t func, void *ctx)
static const char *const bier_table_mpls_nodes[]
Definition: bier_table.c:503
u8 * format(u8 *s, const char *fmt,...)
Definition: format.c:424
static void bier_table_insert(bier_table_t *bt, bier_bp_t bp, index_t bei)
Definition: bier_table.c:534
static bier_entry_t * bier_entry_get(index_t bei)
Definition: bier_entry.h:93
static bier_table_t * bier_table_get(index_t bti)
Definition: bier_table.h:160
bier_table_id_t frp_bier_tbl
A path that resolves via a BIER Table.
Definition: fib_types.h:560
The ID of a table.
Definition: bier_types.h:394
unsigned char u8
Definition: types.h:56
#define pool_len(p)
Number of elements in pool vector.
Definition: pool.h:140
void bier_bift_table_entry_add(bier_bift_id_t id, const dpo_id_t *dpo)
static void bier_table_unlock_i(bier_table_t *bt)
Definition: bier_table.c:207
u8 id[64]
Definition: dhcp.api:160
#define vec_reset_length(v)
Reset vector length to zero NULL-pointer tolerant.
static uword * bier_tables_by_key
DB store of all BIER tables index by SD/set/hdr-len.
Definition: bier_table.c:37
static bier_table_t * bier_table_find(const bier_table_id_t *bti)
Definition: bier_table.c:274
void(* bier_tables_walk_fn_t)(const bier_table_t *bt, void *ctx)
Types and functions to walk all the BIER Tables.
Definition: bier_table.h:139
void dpo_register(dpo_type_t type, const dpo_vft_t *vft, const char *const *const *nodes)
For a given DPO type Register:
Definition: dpo.c:322
#define VLIB_INIT_FUNCTION(x)
Definition: init.h:173
bier_table_ecmp_id_t bti_ecmp
The SUB/ECMP-ID Constructed by FIB to achieve ECMP between BFR-NBRs.
Definition: bier_types.h:414
void bier_table_contribute_forwarding(index_t bti, dpo_id_t *dpo)
Definition: bier_table.c:728
int bier_table_is_main(const bier_table_t *bt)
Definition: bier_table.c:53
bier_table_set_id_t bti_set
The SET-ID The control plane divdies the bit-position space into sets in the case the max bit-positio...
Definition: bier_types.h:401
Aggregate type for a prefix.
Definition: fib_types.h:203
bier_bift_id_t bier_bift_id_encode(bier_table_set_id_t set, bier_table_sub_domain_id_t sd, bier_hdr_len_id_t bsl)
Encode a BIFT-ID as per draft-wijnandsxu-bier-non-mpls-bift-encoding-00.txt.
Definition: bier_types.c:164
void fib_show_memory_usage(const char *name, u32 in_use_elts, u32 allocd_elts, size_t size_elt)
Show the memory usage for a type.
Definition: fib_node.c:220
static void bier_table_dpo_unlock(dpo_id_t *dpo)
Definition: bier_table.c:473
void bier_table_route_path_remove(const bier_table_id_t *btid, bier_bp_t bp, fib_route_path_t *brps)
Definition: bier_table.c:658
static void bier_table_destroy(bier_table_t *bt)
Definition: bier_table.c:152
unsigned int u32
Definition: types.h:88
u32 fib_table_find(fib_protocol_t proto, u32 table_id)
Get the index of the FIB for a Table-ID.
Definition: fib_table.c:1097
mpls_label_t bt_ll
Save the MPLS local label associated with the table.
Definition: bier_table.h:48
u32 bier_bp_t
A bit positon as assigned to egress PEs.
Definition: bier_types.h:294
index_t frp_bier_fmask
Resolving via a BIER Fmask.
Definition: fib_types.h:575
u32 bier_hdr_len_id_to_num_bits(bier_hdr_len_id_t id)
Definition: bier_types.c:78
The identity of a DPO is a combination of its type and its instance number/index of objects of that t...
Definition: dpo.h:170
#define hash_get(h, key)
Definition: hash.h:249
static fib_path_list_walk_rc_t bier_table_ecmp_walk_path_list(fib_node_index_t pl_index, fib_node_index_t path_index, void *arg)
Definition: bier_table.c:758
Definition: fib_entry.h:116
fib_node_index_t fib_path_list_create(fib_path_list_flags_t flags, const fib_route_path_t *rpaths)
bier_hdr_len_id_t bti_hdr_len
The size of the bit string processed by this table.
Definition: bier_types.h:419
index_t bier_table_add_or_lock(const bier_table_id_t *btid, mpls_label_t local_label)
Definition: bier_table.c:397
static void bier_table_remove(bier_table_t *bt, bier_bp_t bp)
Definition: bier_table.c:542
#define pool_put(P, E)
Free an object E in pool P.
Definition: pool.h:287
static const index_t bier_table_fwd_lookup(const bier_table_t *bt, bier_bp_t bp)
Definition: bier_table.h:173
#define vec_del1(v, i)
Delete the element at index I.
Definition: vec.h:806
void fib_path_list_lock(fib_node_index_t path_list_index)
bier_table_ecmp_walk_fn_t fn
Definition: bier_table.c:753
void fib_table_unlock(u32 fib_index, fib_protocol_t proto, fib_source_t source)
Take a reference counting lock on the table.
Definition: fib_table.c:1291
vlib_main_t * vm
Definition: in2out_ed.c:1810
u8 * format_bier_table_entry(u8 *s, va_list *ap)
Definition: bier_table.c:809
#define pool_get_aligned(P, E, A)
Allocate an object E from a pool P with alignment A.
Definition: pool.h:231
int bier_entry_path_remove(index_t bei, const fib_route_path_t *rpaths)
Definition: bier_entry.c:296
#define MPLS_FIB_DEFAULT_TABLE_ID
Definition: mpls_fib.h:28
u32 flags
Definition: vhost_user.h:141
static u32 bier_table_mk_key(const bier_table_id_t *id)
Definition: bier_table.c:63
void fib_table_entry_delete_index(fib_node_index_t fib_entry_index, fib_source_t source)
Delete a FIB entry.
Definition: fib_table.c:910
#define MPLS_LABEL_INVALID
Definition: mpls_types.h:48
#define vec_free(V)
Free vector&#39;s memory (no header).
Definition: vec.h:342
static const index_t bier_table_lookup(const bier_table_t *bt, bier_bp_t bp)
Definition: bier_table.h:166
u32 fib_node_index_t
A typedef of a node index.
Definition: fib_types.h:30
#define pool_is_free_index(P, I)
Use free bitmap to query whether given index is free.
Definition: pool.h:284
void dpo_set(dpo_id_t *dpo, dpo_type_t type, dpo_proto_t proto, index_t index)
Set/create a DPO ID The DPO will be locked.
Definition: dpo.c:186
void fib_path_list_unlock(fib_node_index_t path_list_index)
void bier_table_walk(const bier_table_id_t *bti, bier_table_walk_fn_t fn, void *ctx)
Definition: bier_table.c:928
bier_table_t * bier_table_pool
Memory pool of all the allocated tables.
Definition: bier_table.c:32
fib_node_index_t fib_table_entry_special_dpo_add(u32 fib_index, const fib_prefix_t *prefix, fib_source_t source, fib_entry_flag_t flags, const dpo_id_t *dpo)
Add a &#39;special&#39; entry to the FIB that links to the DPO passed A special entry is an entry that the FI...
Definition: fib_table.c:324
fib_node_index_t bt_lfei
The index of the lfib entry created for this table.
Definition: bier_table.h:59
The BIER entry.
Definition: bier_entry.h:46
#define ASSERT(truth)
void bier_table_unlock(const bier_table_id_t *bti)
Definition: bier_table.c:218
static void bier_table_init(bier_table_t *bt, const bier_table_id_t *id, mpls_label_t ll)
Definition: bier_table.c:80
index_t * bt_entries
Entries in the table This is a vector sized to the appropriate number of entries given the table&#39;s su...
Definition: bier_table.h:71
static void bier_table_mk_lfib(bier_table_t *bt)
Definition: bier_table.c:233
const bier_table_id_t * bier_table_get_id(index_t bti)
Definition: bier_table.c:524
void bier_table_route_delete(const bier_table_id_t *btid, bier_bp_t bp)
Definition: bier_table.c:633
static void bier_table_lock_i(bier_table_t *bt)
Definition: bier_table.c:201
index_t bier_table_ecmp_create_and_lock(const bier_table_id_t *btid)
Definition: bier_table.c:456
static void bier_table_dpo_lock(dpo_id_t *dpo)
Definition: bier_table.c:468
u32 fib_table_find_or_create_and_lock(fib_protocol_t proto, u32 table_id, fib_source_t src)
Get the index of the FIB for a Table-ID.
Definition: fib_table.c:1156
fib_route_path_flags_t frp_flags
flags on the path
Definition: fib_types.h:595
u8 * format_bier_entry(u8 *s, va_list *ap)
Definition: bier_entry.c:367
void bier_table_route_path_update_i(const bier_table_id_t *btid, bier_bp_t bp, fib_route_path_t *brps, u8 is_replace)
Definition: bier_table.c:549
fib_node_index_t bt_pl
The path-list used for the ECMP-tables.
Definition: bier_table.h:53
A path that resolves via a BIER F-Mask.
Definition: fib_types.h:371
format_function_t format_mpls_unicast_label
Definition: mpls.h:71
index_t bier_table_lock(const bier_table_id_t *btid)
Definition: bier_table.c:374
void(* bier_table_walk_fn_t)(const bier_table_t *bt, const bier_entry_t *be, void *ctx)
Types and functions to walk all the entries in one BIER Table.
Definition: bier_table.h:147
typedef key
Definition: ipsec_types.api:83
bier_table_id_t bt_id
The identity/key or the table.
Definition: bier_table.h:76
#define DPO_PROTO_NUM
Definition: dpo.h:70
enum fib_path_list_walk_rc_t_ fib_path_list_walk_rc_t
return code to control pat-hlist walk
#define FIB_NODE_INDEX_INVALID
Definition: fib_types.h:31
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
void bier_table_route_path_add(const bier_table_id_t *btid, bier_bp_t bp, fib_route_path_t *brps)
Definition: bier_table.c:625
#define INDEX_INVALID
Invalid index - used when no index is known blazoned capitals INVALID speak volumes where ~0 does not...
Definition: dpo.h:47
A BIER Table is the bit-indexed forwarding table.
Definition: bier_table.h:38
bier_table_sub_domain_id_t bti_sub_domain
The Sub-Domain-ID The control plane has the configuration option to specify multiple domains or topol...
Definition: bier_types.h:408
u64 uword
Definition: types.h:112
void bier_table_show_all(vlib_main_t *vm, bier_show_flags_t flags)
Definition: bier_table.c:901
#define DPO_INVALID
An initialiser for DPOs declared on the stack.
Definition: dpo.h:197
static clib_error_t * bier_table_module_init(vlib_main_t *vm)
Definition: bier_table.c:514
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)
#define BIER_ECMP_TABLE_ID_MAIN
Definition of the ID of the BIER main table.
Definition: bier_types.h:389
static void bier_table_rm_bift(bier_table_t *bt)
Definition: bier_table.c:111
#define BIER_BP_TO_INDEX(bp)
Definition: bier_types.h:296
void bier_fmask_unlock(index_t bfmi)
Definition: bier_fmask.c:254
void bier_entry_path_add(index_t bei, const fib_route_path_t *rpaths)
Definition: bier_entry.c:170
void bier_bift_table_entry_remove(bier_bift_id_t id)
#define vec_validate_init_empty_aligned(V, I, INIT, A)
Make sure vector is long enough for given index and initialize empty space (no header, alignment alignment)
Definition: vec.h:499
void dpo_reset(dpo_id_t *dpo)
reset a DPO ID The DPO will be unlocked.
Definition: dpo.c:232
#define vec_foreach(var, vec)
Vector iterator.
struct bier_table_ecmp_walk_ctx_t_ bier_table_ecmp_walk_ctx_t
void bier_table_ecmp_walk(index_t bti, bier_table_ecmp_walk_fn_t fn, void *ctx)
Definition: bier_table.c:770
void bier_table_ecmp_set_fmask(index_t bti, bier_bp_t bp, index_t bfmi)
Definition: bier_table.c:791
static u8 * format_bier_table_dpo(u8 *s, va_list *ap)
Definition: bier_table.c:486
#define pool_foreach_index(i, v, body)
Iterate pool by index.
Definition: pool.h:543
void bier_tables_walk(bier_tables_walk_fn_t fn, void *ctx)
Definition: bier_table.c:920
#define CLIB_CACHE_LINE_BYTES
Definition: cache.h:59
u32 bier_fmask_db_find(index_t bti, const fib_route_path_t *rpath)
Definition: bier_fmask_db.c:90
void vlib_cli_output(vlib_main_t *vm, char *fmt,...)
Definition: cli.c:689
void bier_table_route_path_update(const bier_table_id_t *btid, bier_bp_t bp, fib_route_path_t *brps)
Definition: bier_table.c:618
static void bier_table_rm_lfib(bier_table_t *bt)
Definition: bier_table.c:138
CLIB vectors are ubiquitous dynamically resized arrays with by user defined "headers".
static void bier_table_dpo_mem_show(void)
Definition: bier_table.c:478
static uword pool_elts(void *v)
Number of active elements in a pool.
Definition: pool.h:128