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>
24 #include <vnet/fib/mpls_fib.h>
25 #include <vnet/mpls/mpls.h>
26 #include <vnet/fib/fib_path_list.h>
29 * Memory pool of all the allocated tables
31 bier_table_t *bier_table_pool;
34 * DB store of all BIER tables index by SD/set/hdr-len
36 static uword *bier_tables_by_key;
39 * The magic number of BIER ECMP tables to create.
40 * The load-balance distribution algorithm will use a power of 2
41 * for the number of buckets, which constrains the choice.
43 #define BIER_N_ECMP_TABLES 16
46 bier_table_get_index (const bier_table_t *bt)
48 return (bt - bier_table_pool);
52 bier_table_is_main (const bier_table_t *bt)
54 return (BIER_ECMP_TABLE_ID_MAIN == bt->bt_id.bti_ecmp);
58 * Construct the key to use to find a BIER table
59 * in the global hash map
62 bier_table_mk_key (const bier_table_id_t *id)
65 * the set and sub-domain Ids are 8 bit values.
66 * we have space for ECMP table ID and talbe type (SPF/TE)
69 u32 key = ((id->bti_sub_domain << 24) |
72 (id->bti_hdr_len << 4) |
79 bier_table_init (bier_table_t *bt,
80 const bier_table_id_t *id,
85 bt->bt_lfei = FIB_NODE_INDEX_INVALID;
88 num_entries = bier_hdr_len_id_to_num_bits(bt->bt_id.bti_hdr_len);
91 * create the lookup table of entries.
93 if (bier_table_is_main(bt))
95 vec_validate_init_empty_aligned(bt->bt_entries,
98 CLIB_CACHE_LINE_BYTES);
99 fib_table_find_or_create_and_lock(FIB_PROTOCOL_MPLS,
100 MPLS_FIB_DEFAULT_TABLE_ID,
105 vec_validate_init_empty_aligned(bt->bt_fmasks,
108 CLIB_CACHE_LINE_BYTES);
113 bier_table_rm_lfib (bier_table_t *bt)
115 if (FIB_NODE_INDEX_INVALID != bt->bt_lfei)
117 fib_table_entry_delete_index(bt->bt_lfei,
120 bt->bt_lfei = FIB_NODE_INDEX_INVALID;
124 bier_table_destroy (bier_table_t *bt)
126 if (bier_table_is_main(bt))
130 fib_path_list_unlock(bt->bt_pl);
131 bt->bt_pl = FIB_NODE_INDEX_INVALID;
133 * unresolve/remove all entries from the table
135 vec_foreach (bei, bt->bt_entries)
137 if (INDEX_INVALID != *bei)
139 bier_entry_delete(*bei);
142 vec_free (bt->bt_entries);
143 fib_table_unlock(fib_table_find(FIB_PROTOCOL_MPLS,
144 MPLS_FIB_DEFAULT_TABLE_ID),
155 vec_foreach (bfmi, bt->bt_fmasks)
157 bier_fmask_unlock(*bfmi);
159 vec_free(bt->bt_fmasks);
162 hash_unset(bier_tables_by_key,
163 bier_table_mk_key(&bt->bt_id));
164 pool_put(bier_table_pool, bt);
168 bier_table_lock_i (bier_table_t *bt)
174 bier_table_unlock_i (bier_table_t *bt)
178 if (0 == bt->bt_locks)
180 bier_table_rm_lfib(bt);
181 bier_table_destroy(bt);
186 bier_table_unlock (const bier_table_id_t *bti)
191 key = bier_table_mk_key(bti);
193 p = hash_get (bier_tables_by_key, key);
196 bier_table_unlock_i(bier_table_get(p[0]));
201 bier_table_mk_lfib (bier_table_t *bt)
204 * Add a new MPLS lfib entry
206 if (MPLS_LABEL_INVALID != bt->bt_ll) {
208 .fp_proto = FIB_PROTOCOL_MPLS,
210 .fp_label = bt->bt_ll,
212 .fp_payload_proto = DPO_PROTO_BIER,
215 dpo_id_t dpo = DPO_INVALID;
218 * stack the entry on the forwarding chain prodcued by the
219 * path-list via the ECMP tables.
221 fib_path_list_contribute_forwarding(bt->bt_pl,
222 FIB_FORW_CHAIN_TYPE_BIER,
225 mpls_fib_index = fib_table_find(FIB_PROTOCOL_MPLS,
226 MPLS_FIB_DEFAULT_TABLE_ID);
227 bt->bt_lfei = fib_table_entry_special_dpo_add(mpls_fib_index,
230 FIB_ENTRY_FLAG_EXCLUSIVE,
236 static bier_table_t *
237 bier_table_find (const bier_table_id_t *bti)
242 key = bier_table_mk_key(bti);
244 p = hash_get(bier_tables_by_key, key);
248 return (bier_table_get(p[0]));
254 static bier_table_t *
255 bier_table_mk_ecmp (index_t bti)
257 fib_route_path_t *rpaths;
258 fib_node_index_t pli;
263 bt = bier_table_get(bti);
265 vec_validate(rpaths, BIER_N_ECMP_TABLES-1);
267 vec_foreach_index(ii, rpaths)
269 rpaths[ii].frp_bier_tbl = bt->bt_id;
270 rpaths[ii].frp_bier_tbl.bti_ecmp = ii;
271 rpaths[ii].frp_flags = FIB_ROUTE_PATH_BIER_TABLE;
275 * no oppotunity to share, this the resolving ECMP tables are unique
277 * no need to be a child of the path list, we can do nothing with any
278 * notifications it would generate [not that it will].
280 pli = fib_path_list_create(FIB_PATH_LIST_FLAG_NO_URPF, rpaths);
281 fib_path_list_lock(pli);
284 * constructing the path-list will have created many more BIER tables,
285 * so this main table will no doubt have re-alloc.
287 bt = bier_table_get(bti);
296 bier_table_add_or_lock (const bier_table_id_t *btid,
297 mpls_label_t local_label)
302 bt = bier_table_find(btid);
306 * modify an existing table.
307 * change the lfib entry to the new local label
309 if (bier_table_is_main(bt) &&
310 (local_label != MPLS_LABEL_INVALID))
312 bier_table_rm_lfib(bt);
314 bt->bt_ll = local_label;
315 bier_table_mk_lfib(bt);
317 bti = bier_table_get_index(bt);
326 key = bier_table_mk_key(btid);
328 pool_get_aligned(bier_table_pool, bt, CLIB_CACHE_LINE_BYTES);
329 bier_table_init(bt, btid, local_label);
331 hash_set(bier_tables_by_key, key, bier_table_get_index(bt));
332 bti = bier_table_get_index(bt);
334 if (bier_table_is_main(bt))
336 bt = bier_table_mk_ecmp(bti);
337 bier_table_mk_lfib(bt);
341 bier_table_lock_i(bt);
347 bier_table_ecmp_create_and_lock (const bier_table_id_t *btid)
349 return (bier_table_add_or_lock(btid, MPLS_LABEL_INVALID));
353 bier_table_ecmp_unlock (index_t bti)
355 bier_table_unlock_i(bier_table_get(bti));
359 bier_table_dpo_lock (dpo_id_t *dpo)
364 bier_table_dpo_unlock (dpo_id_t *dpo)
369 bier_table_dpo_mem_show (void)
371 fib_show_memory_usage("BIER-table",
372 pool_elts(bier_table_pool),
373 pool_len(bier_table_pool),
374 sizeof(bier_table_t));
377 format_bier_table_dpo (u8 *s, va_list *ap)
379 index_t bti = va_arg(*ap, index_t);
382 bt = bier_table_get(bti);
384 return (format(s, "[%U]", format_bier_table_id, &bt->bt_id));
387 const static dpo_vft_t bier_table_dpo_vft = {
388 .dv_lock = bier_table_dpo_lock,
389 .dv_unlock = bier_table_dpo_unlock,
390 .dv_format = format_bier_table_dpo,
391 .dv_mem_show = bier_table_dpo_mem_show,
394 const static char *const bier_table_mpls_nodes[] =
398 const static char * const * const bier_table_nodes[DPO_PROTO_NUM] =
400 [DPO_PROTO_BIER] = bier_table_mpls_nodes,
403 static clib_error_t *
404 bier_table_module_init (vlib_main_t *vm)
406 dpo_register(DPO_BIER_TABLE, &bier_table_dpo_vft, bier_table_nodes);
411 VLIB_INIT_FUNCTION (bier_table_module_init);
413 const bier_table_id_t *
414 bier_table_get_id (index_t bti)
418 bt = bier_table_get(bti);
424 bier_table_insert (bier_table_t *bt,
428 bt->bt_entries[BIER_BP_TO_INDEX(bp)] = bei;
432 bier_table_remove (bier_table_t *bt,
435 bt->bt_entries[BIER_BP_TO_INDEX(bp)] = INDEX_INVALID;
439 bier_table_route_add (const bier_table_id_t *btid,
441 fib_route_path_t *brps)
443 index_t bfmi, bti, bei, *bfmip, *bfmis = NULL;
444 fib_route_path_t *brp;
447 bt = bier_table_find(btid);
453 bti = bier_table_get_index(bt);
454 bei = bier_table_lookup(bt, bp);
457 * set the FIB index in the path to the BIER table index
459 vec_foreach(brp, brps)
461 bier_fmask_id_t fmid = {
462 .bfmi_nh = brp->frp_addr,
463 .bfmi_hdr_type = BIER_HDR_O_MPLS,
465 bfmi = bier_fmask_db_find_or_create_and_lock(bier_table_get_index(bt),
469 brp->frp_bier_fib_index = bti;
470 vec_add1(bfmis, bfmi);
473 if (INDEX_INVALID == bei)
475 bei = bier_entry_create(bti, bp);
476 bier_table_insert(bt, bp, bei);
478 bier_entry_path_add(bei, brps);
480 vec_foreach(bfmip, bfmis)
482 bier_fmask_unlock(*bfmip);
488 bier_table_route_remove (const bier_table_id_t *bti,
490 fib_route_path_t *brps)
492 fib_route_path_t *brp = NULL;
496 bt = bier_table_find(bti);
502 bei = bier_table_lookup(bt, bp);
504 if (INDEX_INVALID == bei)
510 vec_foreach(brp, brps)
512 brp->frp_bier_fib_index = bier_table_get_index(bt);
515 if (0 == bier_entry_path_remove(bei, brps))
517 /* 0 remaining paths */
518 bier_table_remove(bt, bp);
519 bier_entry_delete(bei);
524 bier_table_contribute_forwarding (index_t bti,
529 bt = bier_table_get(bti);
531 if (BIER_ECMP_TABLE_ID_MAIN == bt->bt_id.bti_ecmp)
534 * return the load-balance for the ECMP tables
536 fib_path_list_contribute_forwarding(bt->bt_pl,
537 FIB_FORW_CHAIN_TYPE_BIER,
542 dpo_set(dpo, DPO_BIER_TABLE, DPO_PROTO_BIER, bti);
546 typedef struct bier_table_ecmp_walk_ctx_t_
548 bier_table_ecmp_walk_fn_t fn;
550 } bier_table_ecmp_walk_ctx_t;
552 static fib_path_list_walk_rc_t
553 bier_table_ecmp_walk_path_list (fib_node_index_t pl_index,
554 fib_node_index_t path_index,
557 bier_table_ecmp_walk_ctx_t *ctx = arg;
559 ctx->fn(fib_path_get_resolving_index(path_index), ctx->ctx);
561 return (FIB_PATH_LIST_WALK_CONTINUE);
565 bier_table_ecmp_walk (index_t bti,
566 bier_table_ecmp_walk_fn_t fn,
569 bier_table_ecmp_walk_ctx_t ewc = {
575 bt = bier_table_get(bti);
577 fib_path_list_walk(bt->bt_pl,
578 bier_table_ecmp_walk_path_list,
583 bier_table_ecmp_set_fmask (index_t bti,
589 bt = bier_table_get(bti);
592 * we hold a lock for fmasks in the table
594 bier_fmask_lock(bfmi);
595 bier_fmask_unlock(bt->bt_fmasks[BIER_BP_TO_INDEX(bp)]);
597 bt->bt_fmasks[BIER_BP_TO_INDEX(bp)] = bfmi;
601 format_bier_table_entry (u8 *s, va_list *ap)
603 index_t bti = va_arg(*ap, index_t);
604 bier_bp_t bp = va_arg(*ap, bier_bp_t);
606 bt = bier_table_get(bti);
608 if (bier_table_is_main(bt))
612 bei = bier_table_lookup(bier_table_get(bti), bp);
614 if (INDEX_INVALID != bei)
616 s = format(s, "%U", format_bier_entry, bei,
624 bfmi = bier_table_fwd_lookup(bier_table_get(bti), bp);
626 if (INDEX_INVALID != bfmi)
628 s = format(s, "%U", format_bier_fmask, bfmi,
636 format_bier_table (u8 *s, va_list *ap)
638 index_t bti = va_arg(*ap, index_t);
639 bier_show_flags_t flags = va_arg(*ap, bier_show_flags_t);
642 if (pool_is_free_index(bier_table_pool, bti))
644 return (format(s, "No BIER f-mask %d", bti));
647 bt = bier_table_get(bti);
649 s = format(s, "[@%d] bier-table:[%U local-label:%U]",
651 format_bier_table_id, &bt->bt_id,
652 format_mpls_unicast_label, bt->bt_ll);
654 if (flags & BIER_SHOW_DETAIL)
656 s = format(s, " locks:%d", bt->bt_locks);
660 if (flags & BIER_SHOW_DETAIL)
662 if (bier_table_is_main(bt))
666 vec_foreach (bei, bt->bt_entries)
668 if (INDEX_INVALID != *bei)
670 s = format(s, "\n%U", format_bier_entry, *bei, 2);
678 vec_foreach_index (ii, bt->bt_fmasks)
680 if (INDEX_INVALID != bt->bt_fmasks[ii])
682 s = format(s, "\n bp:%d\n %U", ii,
683 format_bier_fmask, bt->bt_fmasks[ii], 2);
693 bier_table_show_all (vlib_main_t * vm,
694 bier_show_flags_t flags)
696 if (!pool_elts(bier_table_pool))
698 vlib_cli_output (vm, "No BIER tables");
704 pool_foreach_index(ii, bier_table_pool,
706 vlib_cli_output (vm, "%U", format_bier_table, ii, flags);
712 bier_tables_walk (bier_tables_walk_fn_t fn,
720 bier_table_walk (const bier_table_id_t *bti,
721 bier_table_walk_fn_t fn,
728 bt = bier_table_find(bti);
735 vec_foreach (bei, bt->bt_entries)
737 if (INDEX_INVALID != *bei)
739 be = bier_entry_get(*bei);