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:
7 * http://www.apache.org/licenses/LICENSE-2.0
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.
16 #include <vppinfra/vec.h>
18 #include <vnet/bier/bier_table.h>
19 #include <vnet/bier/bier_entry.h>
20 #include <vnet/bier/bier_update.h>
21 #include <vnet/bier/bier_fmask_db.h>
22 #include <vnet/bier/bier_fmask.h>
23 #include <vnet/bier/bier_bift_table.h>
25 #include <vnet/fib/mpls_fib.h>
26 #include <vnet/mpls/mpls.h>
27 #include <vnet/fib/fib_path_list.h>
30 * Memory pool of all the allocated tables
32 bier_table_t *bier_table_pool;
35 * DB store of all BIER tables index by SD/set/hdr-len
37 static uword *bier_tables_by_key;
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.
44 #define BIER_N_ECMP_TABLES 16
47 bier_table_get_index (const bier_table_t *bt)
49 return (bt - bier_table_pool);
53 bier_table_is_main (const bier_table_t *bt)
55 return (BIER_ECMP_TABLE_ID_MAIN == bt->bt_id.bti_ecmp);
59 * Construct the key to use to find a BIER table
60 * in the global hash map
63 bier_table_mk_key (const bier_table_id_t *id)
66 * the set and sub-domain Ids are 8 bit values.
67 * we have space for ECMP table ID and talbe type (SPF/TE)
70 u32 key = ((id->bti_sub_domain << 24) |
73 (id->bti_hdr_len << 4) |
80 bier_table_init (bier_table_t *bt,
81 const bier_table_id_t *id,
86 bt->bt_lfei = FIB_NODE_INDEX_INVALID;
89 num_entries = bier_hdr_len_id_to_num_bits(bt->bt_id.bti_hdr_len);
92 * create the lookup table of entries.
94 if (bier_table_is_main(bt))
96 vec_validate_init_empty_aligned(bt->bt_entries,
99 CLIB_CACHE_LINE_BYTES);
103 vec_validate_init_empty_aligned(bt->bt_fmasks,
106 CLIB_CACHE_LINE_BYTES);
111 bier_table_rm_bift (bier_table_t *bt)
113 ASSERT(MPLS_LABEL_INVALID == bt->bt_ll);
115 bier_bift_table_entry_remove(bier_bift_id_encode(bt->bt_id.bti_set,
116 bt->bt_id.bti_sub_domain,
117 bt->bt_id.bti_hdr_len));
121 bier_table_mk_bift (bier_table_t *bt)
123 dpo_id_t dpo = DPO_INVALID;
125 ASSERT(MPLS_LABEL_INVALID == bt->bt_ll);
127 bier_table_contribute_forwarding(bier_table_get_index(bt), &dpo);
129 bier_bift_table_entry_add(bier_bift_id_encode(bt->bt_id.bti_set,
130 bt->bt_id.bti_sub_domain,
131 bt->bt_id.bti_hdr_len),
138 bier_table_rm_lfib (bier_table_t *bt)
140 if (FIB_NODE_INDEX_INVALID != bt->bt_lfei)
142 fib_table_entry_delete_index(bt->bt_lfei,
144 fib_table_unlock(MPLS_FIB_DEFAULT_TABLE_ID,
148 bt->bt_lfei = FIB_NODE_INDEX_INVALID;
152 bier_table_destroy (bier_table_t *bt)
154 if (bier_table_is_main(bt))
158 if (MPLS_LABEL_INVALID != bt->bt_ll)
160 bier_table_rm_lfib(bt);
164 bier_table_rm_bift(bt);
167 fib_path_list_unlock(bt->bt_pl);
168 bt->bt_pl = FIB_NODE_INDEX_INVALID;
170 * unresolve/remove all entries from the table
172 vec_foreach (bei, bt->bt_entries)
174 if (INDEX_INVALID != *bei)
176 bier_entry_delete(*bei);
179 vec_free (bt->bt_entries);
188 vec_foreach (bfmi, bt->bt_fmasks)
190 bier_fmask_unlock(*bfmi);
192 vec_free(bt->bt_fmasks);
195 hash_unset(bier_tables_by_key,
196 bier_table_mk_key(&bt->bt_id));
197 pool_put(bier_table_pool, bt);
201 bier_table_lock_i (bier_table_t *bt)
207 bier_table_unlock_i (bier_table_t *bt)
211 if (0 == bt->bt_locks)
213 bier_table_destroy(bt);
218 bier_table_unlock (const bier_table_id_t *bti)
223 key = bier_table_mk_key(bti);
225 p = hash_get (bier_tables_by_key, key);
228 bier_table_unlock_i(bier_table_get(p[0]));
233 bier_table_mk_lfib (bier_table_t *bt)
236 * Add a new MPLS lfib entry
238 if (MPLS_LABEL_INVALID != bt->bt_ll) {
240 .fp_proto = FIB_PROTOCOL_MPLS,
242 .fp_label = bt->bt_ll,
244 .fp_payload_proto = DPO_PROTO_BIER,
247 dpo_id_t dpo = DPO_INVALID;
249 fib_table_find_or_create_and_lock(FIB_PROTOCOL_MPLS,
250 MPLS_FIB_DEFAULT_TABLE_ID,
254 * stack the entry on the forwarding chain produced by the
255 * path-list via the ECMP tables.
257 fib_path_list_contribute_forwarding(bt->bt_pl,
258 FIB_FORW_CHAIN_TYPE_BIER,
259 FIB_PATH_LIST_FWD_FLAG_COLLAPSE,
262 mpls_fib_index = fib_table_find(FIB_PROTOCOL_MPLS,
263 MPLS_FIB_DEFAULT_TABLE_ID);
264 bt->bt_lfei = fib_table_entry_special_dpo_add(mpls_fib_index,
267 FIB_ENTRY_FLAG_EXCLUSIVE,
273 static bier_table_t *
274 bier_table_find (const bier_table_id_t *bti)
279 key = bier_table_mk_key(bti);
281 p = hash_get(bier_tables_by_key, key);
285 return (bier_table_get(p[0]));
291 static bier_table_t *
292 bier_table_mk_ecmp (index_t bti)
294 fib_route_path_t *rpaths;
295 fib_node_index_t pli;
300 bt = bier_table_get(bti);
302 vec_validate(rpaths, BIER_N_ECMP_TABLES-1);
304 vec_foreach_index(ii, rpaths)
306 rpaths[ii].frp_bier_tbl = bt->bt_id;
307 rpaths[ii].frp_bier_tbl.bti_ecmp = ii;
308 rpaths[ii].frp_flags = FIB_ROUTE_PATH_BIER_TABLE;
312 * no opportunity to share, this the resolving ECMP tables are unique
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].
317 pli = fib_path_list_create(FIB_PATH_LIST_FLAG_NO_URPF, rpaths);
318 fib_path_list_lock(pli);
321 * constructing the path-list will have created many more BIER tables,
322 * so this main table will no doubt have re-alloc.
324 bt = bier_table_get(bti);
334 bier_table_create (const bier_table_id_t *btid,
335 mpls_label_t local_label)
344 key = bier_table_mk_key(btid);
346 pool_get_aligned(bier_table_pool, bt, CLIB_CACHE_LINE_BYTES);
347 bier_table_init(bt, btid, local_label);
349 hash_set(bier_tables_by_key, key, bier_table_get_index(bt));
350 bti = bier_table_get_index(bt);
352 if (bier_table_is_main(bt))
354 bt = bier_table_mk_ecmp(bti);
357 * add whichever mpls-fib or bift we need
359 if (local_label != MPLS_LABEL_INVALID)
361 bt->bt_ll = local_label;
362 bier_table_mk_lfib(bt);
366 bier_table_mk_bift(bt);
374 bier_table_lock (const bier_table_id_t *btid)
379 bt = bier_table_find(btid);
383 bti = bier_table_create(btid, MPLS_LABEL_INVALID);
384 bt = bier_table_get(bti);
388 bti = bier_table_get_index(bt);
391 bier_table_lock_i(bt);
397 bier_table_add_or_lock (const bier_table_id_t *btid,
398 mpls_label_t local_label)
403 bt = bier_table_find(btid);
407 * modify an existing table.
408 * change the lfib entry to the new local label
410 if (bier_table_is_main(bt))
413 * remove the mpls-fib or bift entry
415 if (MPLS_LABEL_INVALID != bt->bt_ll)
417 bier_table_rm_lfib(bt);
421 bier_table_rm_bift(bt);
427 bt->bt_ll = MPLS_LABEL_INVALID;
430 * add whichever mpls-fib or bift we need
432 if (local_label != MPLS_LABEL_INVALID)
434 bt->bt_ll = local_label;
435 bier_table_mk_lfib(bt);
439 bier_table_mk_bift(bt);
442 bti = bier_table_get_index(bt);
446 bti = bier_table_create(btid, local_label);
447 bt = bier_table_get(bti);
450 bier_table_lock_i(bt);
456 bier_table_ecmp_create_and_lock (const bier_table_id_t *btid)
458 return (bier_table_add_or_lock(btid, MPLS_LABEL_INVALID));
462 bier_table_ecmp_unlock (index_t bti)
464 bier_table_unlock_i(bier_table_get(bti));
468 bier_table_dpo_lock (dpo_id_t *dpo)
473 bier_table_dpo_unlock (dpo_id_t *dpo)
478 bier_table_dpo_mem_show (void)
480 fib_show_memory_usage("BIER-table",
481 pool_elts(bier_table_pool),
482 pool_len(bier_table_pool),
483 sizeof(bier_table_t));
486 format_bier_table_dpo (u8 *s, va_list *ap)
488 index_t bti = va_arg(*ap, index_t);
491 bt = bier_table_get(bti);
493 return (format(s, "[%U]", format_bier_table_id, &bt->bt_id));
496 const static dpo_vft_t bier_table_dpo_vft = {
497 .dv_lock = bier_table_dpo_lock,
498 .dv_unlock = bier_table_dpo_unlock,
499 .dv_format = format_bier_table_dpo,
500 .dv_mem_show = bier_table_dpo_mem_show,
503 const static char *const bier_table_mpls_nodes[] =
508 const static char * const * const bier_table_nodes[DPO_PROTO_NUM] =
510 [DPO_PROTO_BIER] = bier_table_mpls_nodes,
513 static clib_error_t *
514 bier_table_module_init (vlib_main_t *vm)
516 dpo_register(DPO_BIER_TABLE, &bier_table_dpo_vft, bier_table_nodes);
521 VLIB_INIT_FUNCTION (bier_table_module_init);
523 const bier_table_id_t *
524 bier_table_get_id (index_t bti)
528 bt = bier_table_get(bti);
534 bier_table_insert (bier_table_t *bt,
538 bt->bt_entries[BIER_BP_TO_INDEX(bp)] = bei;
542 bier_table_remove (bier_table_t *bt,
545 bt->bt_entries[BIER_BP_TO_INDEX(bp)] = INDEX_INVALID;
549 bier_table_route_path_update_i (const bier_table_id_t *btid,
551 fib_route_path_t *brps,
554 index_t bfmi, bti, bei, *bfmip, *bfmis = NULL;
555 fib_route_path_t *brp;
558 bt = bier_table_find(btid);
564 bti = bier_table_get_index(bt);
565 bei = bier_table_lookup(bt, bp);
568 * set the FIB index in the path to the BIER table index
570 vec_foreach(brp, brps)
573 * First use the path to find or construct an FMask object
576 bfmi = bier_fmask_db_find_or_create_and_lock(bti, brp);
577 vec_add1(bfmis, bfmi);
580 * then modify the path to resolve via this fmask object
581 * and use it to resolve the BIER entry.
583 brp->frp_flags = FIB_ROUTE_PATH_BIER_FMASK;
584 brp->frp_bier_fmask = bfmi;
587 if (INDEX_INVALID == bei)
589 bei = bier_entry_create(bti, bp);
590 bier_table_insert(bt, bp, bei);
595 bier_entry_path_update(bei, brps);
599 fib_route_path_t *t_paths = NULL;
601 vec_foreach(brp, brps)
603 vec_add1(t_paths, *brp);
604 bier_entry_path_add(bei, t_paths);
605 vec_reset_length(t_paths);
610 vec_foreach(bfmip, bfmis)
612 bier_fmask_unlock(*bfmip);
618 bier_table_route_path_update (const bier_table_id_t *btid,
620 fib_route_path_t *brps)
622 bier_table_route_path_update_i(btid, bp, brps, 1);
625 bier_table_route_path_add (const bier_table_id_t *btid,
627 fib_route_path_t *brps)
629 bier_table_route_path_update_i(btid, bp, brps, 0);
633 bier_table_route_delete (const bier_table_id_t *btid,
639 bt = bier_table_find(btid);
645 bei = bier_table_lookup(bt, bp);
647 if (INDEX_INVALID == bei)
653 bier_table_remove(bt, bp);
654 bier_entry_delete(bei);
658 bier_table_route_path_remove (const bier_table_id_t *btid,
660 fib_route_path_t *brps)
662 fib_route_path_t *brp = NULL, *t_paths = NULL;
663 index_t bfmi, bti, bei;
667 bt = bier_table_find(btid);
673 bti = bier_table_get_index(bt);
674 bei = bier_table_lookup(bt, bp);
676 if (INDEX_INVALID == bei)
683 * set the FIB index in the path to the BIER table index
685 vec_foreach_index(ii, brps)
688 bfmi = bier_fmask_db_find(bti, brp);
690 if (INDEX_INVALID == bfmi)
693 * no matching fmask, not a path we can remove
700 * then modify the path to resolve via this fmask object
701 * and use it to resolve the BIER entry.
703 brp->frp_flags = FIB_ROUTE_PATH_BIER_FMASK;
704 brp->frp_bier_fmask = bfmi;
707 if (0 == vec_len(brps))
712 vec_foreach(brp, brps)
714 vec_add1(t_paths, *brp);
715 if (0 == bier_entry_path_remove(bei, t_paths))
717 /* 0 remaining paths */
718 bier_table_remove(bt, bp);
719 bier_entry_delete(bei);
722 vec_reset_length(t_paths);
728 bier_table_contribute_forwarding (index_t bti,
733 bt = bier_table_get(bti);
735 if (BIER_ECMP_TABLE_ID_MAIN == bt->bt_id.bti_ecmp)
738 * return the load-balance for the ECMP tables
740 fib_path_list_contribute_forwarding(bt->bt_pl,
741 FIB_FORW_CHAIN_TYPE_BIER,
742 FIB_PATH_LIST_FWD_FLAG_COLLAPSE,
747 dpo_set(dpo, DPO_BIER_TABLE, DPO_PROTO_BIER, bti);
751 typedef struct bier_table_ecmp_walk_ctx_t_
753 bier_table_ecmp_walk_fn_t fn;
755 } bier_table_ecmp_walk_ctx_t;
757 static fib_path_list_walk_rc_t
758 bier_table_ecmp_walk_path_list (fib_node_index_t pl_index,
759 fib_node_index_t path_index,
762 bier_table_ecmp_walk_ctx_t *ctx = arg;
764 ctx->fn(fib_path_get_resolving_index(path_index), ctx->ctx);
766 return (FIB_PATH_LIST_WALK_CONTINUE);
770 bier_table_ecmp_walk (index_t bti,
771 bier_table_ecmp_walk_fn_t fn,
774 bier_table_ecmp_walk_ctx_t ewc = {
780 bt = bier_table_get(bti);
782 if (FIB_NODE_INDEX_INVALID != bt->bt_pl)
784 fib_path_list_walk(bt->bt_pl,
785 bier_table_ecmp_walk_path_list,
791 bier_table_ecmp_set_fmask (index_t bti,
797 bt = bier_table_get(bti);
800 * we hold a lock for fmasks in the table
802 bier_fmask_lock(bfmi);
803 bier_fmask_unlock(bt->bt_fmasks[BIER_BP_TO_INDEX(bp)]);
805 bt->bt_fmasks[BIER_BP_TO_INDEX(bp)] = bfmi;
809 format_bier_table_entry (u8 *s, va_list *ap)
811 index_t bti = va_arg(*ap, index_t);
812 bier_bp_t bp = va_arg(*ap, bier_bp_t);
814 bt = bier_table_get(bti);
816 if (bier_table_is_main(bt))
820 bei = bier_table_lookup(bier_table_get(bti), bp);
822 if (INDEX_INVALID != bei)
824 s = format(s, "%U", format_bier_entry, bei,
832 bfmi = bier_table_fwd_lookup(bier_table_get(bti), bp);
834 if (INDEX_INVALID != bfmi)
836 s = format(s, "%U", format_bier_fmask, bfmi,
844 format_bier_table (u8 *s, va_list *ap)
846 index_t bti = va_arg(*ap, index_t);
847 bier_show_flags_t flags = va_arg(*ap, bier_show_flags_t);
850 if (pool_is_free_index(bier_table_pool, bti))
852 return (format(s, "No BIER table %d", bti));
855 bt = bier_table_get(bti);
857 s = format(s, "[@%d] bier-table:[%U local-label:%U",
859 format_bier_table_id, &bt->bt_id,
860 format_mpls_unicast_label, bt->bt_ll);
862 if (flags & BIER_SHOW_DETAIL)
864 s = format(s, " locks:%d", bt->bt_locks);
868 if (flags & BIER_SHOW_DETAIL)
870 if (bier_table_is_main(bt))
874 vec_foreach (bei, bt->bt_entries)
876 if (INDEX_INVALID != *bei)
878 s = format(s, "\n%U", format_bier_entry, *bei, 2);
886 vec_foreach_index (ii, bt->bt_fmasks)
888 if (INDEX_INVALID != bt->bt_fmasks[ii])
890 s = format(s, "\n bp:%d\n %U", ii,
891 format_bier_fmask, bt->bt_fmasks[ii], 2);
901 bier_table_show_all (vlib_main_t * vm,
902 bier_show_flags_t flags)
904 if (!pool_elts(bier_table_pool))
906 vlib_cli_output (vm, "No BIER tables");
912 pool_foreach_index (ii, bier_table_pool)
914 vlib_cli_output (vm, "%U", format_bier_table, ii, flags);
920 bier_tables_walk (bier_tables_walk_fn_t fn,
928 bier_table_walk (const bier_table_id_t *bti,
929 bier_table_walk_fn_t fn,
936 bt = bier_table_find(bti);
943 vec_foreach (bei, bt->bt_entries)
945 if (INDEX_INVALID != *bei)
947 be = bier_entry_get(*bei);