src/vnet/bier/bier_table.c

   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>
  21 #include <vnet/bier/bier_fmask_db.h>
  22 #include <vnet/bier/bier_fmask.h>
  23 #include <vnet/bier/bier_bift_table.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  */
  32 bier_table_t *bier_table_pool;
  33
  34 /**
  35  * DB store of all BIER tables index by SD/set/hdr-len
  36  */
  37 static uword *bier_tables_by_key;
  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
  47 bier_table_get_index (const bier_table_t *bt)
  48 {
  49     return (bt - bier_table_pool);
  50 }
  51
  52 int
  53 bier_table_is_main (const bier_table_t *bt)
  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
  63 bier_table_mk_key (const bier_table_id_t *id)
  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
  80 bier_table_init (bier_table_t *bt,
  81                  const bier_table_id_t *id,
  82                  mpls_label_t ll)
  83 {
  84     u32 num_entries;
  85
  86     bt->bt_lfei = FIB_NODE_INDEX_INVALID;
  87     bt->bt_id = *id;
  88     bt->bt_ll = ll;
  89     num_entries = bier_hdr_len_id_to_num_bits(bt->bt_id.bti_hdr_len);
  90
  91     /*
  92      * create the lookup table of entries.
  93      */
  94     if (bier_table_is_main(bt))
  95     {
  96         vec_validate_init_empty_aligned(bt->bt_entries,
  97                                         num_entries,
  98                                         INDEX_INVALID,
  99                                         CLIB_CACHE_LINE_BYTES);
 100     }
 101     else
 102     {
 103         vec_validate_init_empty_aligned(bt->bt_fmasks,
 104                                         num_entries,
 105                                         INDEX_INVALID,
 106                                         CLIB_CACHE_LINE_BYTES);
 107     }
 108 }
 109
 110 static void
 111 bier_table_rm_bift (bier_table_t *bt)
 112 {
 113     ASSERT(MPLS_LABEL_INVALID == bt->bt_ll);
 114
 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));
 118 }
 119
 120 static void
 121 bier_table_mk_bift (bier_table_t *bt)
 122 {
 123     dpo_id_t dpo = DPO_INVALID;
 124
 125     ASSERT(MPLS_LABEL_INVALID == bt->bt_ll);
 126
 127     bier_table_contribute_forwarding(bier_table_get_index(bt), &dpo);
 128
 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),
 132                                &dpo);
 133
 134     dpo_reset(&dpo);
 135 }
 136
 137 static void
 138 bier_table_rm_lfib (bier_table_t *bt)
 139 {
 140     if (FIB_NODE_INDEX_INVALID != bt->bt_lfei)
 141     {
 142         fib_table_entry_delete_index(bt->bt_lfei,
 143                                      FIB_SOURCE_BIER);
 144         fib_table_unlock(MPLS_FIB_DEFAULT_TABLE_ID,
 145                          FIB_PROTOCOL_MPLS,
 146                          FIB_SOURCE_BIER);
 147     }
 148     bt->bt_lfei = FIB_NODE_INDEX_INVALID;
 149 }
 150
 151 static void
 152 bier_table_destroy (bier_table_t *bt)
 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
 167         fib_path_list_unlock(bt->bt_pl);
 168         bt->bt_pl = FIB_NODE_INDEX_INVALID;
 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
 195     hash_unset(bier_tables_by_key,
 196                bier_table_mk_key(&bt->bt_id));
 197     pool_put(bier_table_pool, bt);
 198 }
 199
 200 static void
 201 bier_table_lock_i (bier_table_t *bt)
 202 {
 203     bt->bt_locks++;
 204 }
 205
 206 static void
 207 bier_table_unlock_i (bier_table_t *bt)
 208 {
 209     bt->bt_locks--;
 210
 211     if (0 == bt->bt_locks)
 212     {
 213         bier_table_destroy(bt);
 214     }
 215 }
 216
 217 void
 218 bier_table_unlock (const bier_table_id_t *bti)
 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) {
 228         bier_table_unlock_i(bier_table_get(p[0]));
 229     }
 230 }
 231
 232 static void
 233 bier_table_mk_lfib (bier_table_t *bt)
 234 {
 235     /*
 236      * Add a new MPLS lfib entry
 237      */
 238     if (MPLS_LABEL_INVALID != bt->bt_ll) {
 239         fib_prefix_t pfx = {
 240             .fp_proto = FIB_PROTOCOL_MPLS,
 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
 249         fib_table_find_or_create_and_lock(FIB_PROTOCOL_MPLS,
 250                                           MPLS_FIB_DEFAULT_TABLE_ID,
 251                                           FIB_SOURCE_BIER);
 252
 253         /*
 254          * stack the entry on the forwarding chain produced by the
 255          * path-list via the ECMP tables.
 256          */
 257         fib_path_list_contribute_forwarding(bt->bt_pl,
 258                                             FIB_FORW_CHAIN_TYPE_BIER,
 259                                             FIB_PATH_LIST_FWD_FLAG_COLLAPSE,
 260                                             &dpo);
 261
 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,
 265                                                       &pfx,
 266                                                       FIB_SOURCE_BIER,
 267                                                       FIB_ENTRY_FLAG_EXCLUSIVE,
 268                                                       &dpo);
 269         dpo_reset(&dpo);
 270     }
 271 }
 272
 273 static bier_table_t *
 274 bier_table_find (const bier_table_id_t *bti)
 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 *
 292 bier_table_mk_ecmp (index_t bti)
 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;
 308         rpaths[ii].frp_flags = FIB_ROUTE_PATH_BIER_TABLE;
 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      */
 317     pli = fib_path_list_create(FIB_PATH_LIST_FLAG_NO_URPF, rpaths);
 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
 334 bier_table_create (const bier_table_id_t *btid,
 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
 349     hash_set(bier_tables_by_key, key, bier_table_get_index(bt));
 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
 374 bier_table_lock (const bier_table_id_t *btid)
 375 {
 376     bier_table_t *bt;
 377     index_t bti;
 378
 379     bt = bier_table_find(btid);
 380
 381     if (NULL == bt)
 382     {
 383         bti = bier_table_create(btid, MPLS_LABEL_INVALID);
 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
 397 bier_table_add_or_lock (const bier_table_id_t *btid,
 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              */
 427             bt->bt_ll = MPLS_LABEL_INVALID;
 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
 456 bier_table_ecmp_create_and_lock (const bier_table_id_t *btid)
 457 {
 458     return (bier_table_add_or_lock(btid, MPLS_LABEL_INVALID));
 459 }
 460
 461 void
 462 bier_table_ecmp_unlock (index_t bti)
 463 {
 464     bier_table_unlock_i(bier_table_get(bti));
 465 }
 466
 467 static void
 468 bier_table_dpo_lock (dpo_id_t *dpo)
 469 {
 470 }
 471
 472 static void
 473 bier_table_dpo_unlock (dpo_id_t *dpo)
 474 {
 475 }
 476
 477 static void
 478 bier_table_dpo_mem_show (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 = {
 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,
 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 {
 510     [DPO_PROTO_BIER] = bier_table_mpls_nodes,
 511 };
 512
 513 static clib_error_t *
 514 bier_table_module_init (vlib_main_t *vm)
 515 {
 516     dpo_register(DPO_BIER_TABLE, &bier_table_dpo_vft, bier_table_nodes);
 517
 518     return (NULL);
 519 }
 520
 521 VLIB_INIT_FUNCTION (bier_table_module_init);
 522
 523 const bier_table_id_t *
 524 bier_table_get_id (index_t bti)
 525 {
 526     bier_table_t *bt;
 527
 528     bt = bier_table_get(bti);
 529
 530     return (&bt->bt_id);
 531 }
 532
 533 static void
 534 bier_table_insert (bier_table_t *bt,
 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
 542 bier_table_remove (bier_table_t *bt,
 543                    bier_bp_t bp)
 544 {
 545     bt->bt_entries[BIER_BP_TO_INDEX(bp)] = INDEX_INVALID;
 546 }
 547
 548 void
 549 bier_table_route_path_update_i (const bier_table_id_t *btid,
 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          */
 583         brp->frp_flags = FIB_ROUTE_PATH_BIER_FMASK;
 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
 618 bier_table_route_path_update (const bier_table_id_t *btid,
 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
 625 bier_table_route_path_add (const bier_table_id_t *btid,
 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
 633 bier_table_route_delete (const bier_table_id_t *btid,
 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
 658 bier_table_route_path_remove (const bier_table_id_t *btid,
 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          */
 703         brp->frp_flags = FIB_ROUTE_PATH_BIER_FMASK;
 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
 728 bier_table_contribute_forwarding (index_t bti,
 729                                   dpo_id_t *dpo)
 730 {
 731     bier_table_t *bt;
 732
 733     bt = bier_table_get(bti);
 734
 735     if (BIER_ECMP_TABLE_ID_MAIN == bt->bt_id.bti_ecmp)
 736     {
 737         /*
 738          * return the load-balance for the ECMP tables
 739          */
 740         fib_path_list_contribute_forwarding(bt->bt_pl,
 741                                             FIB_FORW_CHAIN_TYPE_BIER,
 742                                             FIB_PATH_LIST_FWD_FLAG_COLLAPSE,
 743                                             dpo);
 744     }
 745     else
 746     {
 747         dpo_set(dpo, DPO_BIER_TABLE, DPO_PROTO_BIER, bti);
 748     }
 749 }
 750
 751 typedef struct bier_table_ecmp_walk_ctx_t_
 752 {
 753     bier_table_ecmp_walk_fn_t fn;
 754     void *ctx;
 755 } bier_table_ecmp_walk_ctx_t;
 756
 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,
 760                                 void *arg)
 761 {
 762     bier_table_ecmp_walk_ctx_t *ctx = arg;
 763
 764     ctx->fn(fib_path_get_resolving_index(path_index), ctx->ctx);
 765     /* continue */
 766     return (FIB_PATH_LIST_WALK_CONTINUE);
 767 }
 768
 769 void
 770 bier_table_ecmp_walk (index_t bti,
 771                       bier_table_ecmp_walk_fn_t fn,
 772                       void *ctx)
 773 {
 774     bier_table_ecmp_walk_ctx_t ewc = {
 775         .fn = fn,
 776         .ctx = ctx,
 777     };
 778     bier_table_t *bt;
 779
 780     bt = bier_table_get(bti);
 781
 782     fib_path_list_walk(bt->bt_pl,
 783                        bier_table_ecmp_walk_path_list,
 784                        &ewc);
 785 }
 786
 787 void
 788 bier_table_ecmp_set_fmask (index_t bti,
 789                            bier_bp_t bp,
 790                            index_t bfmi)
 791 {
 792     bier_table_t *bt;
 793
 794     bt = bier_table_get(bti);
 795
 796     /*
 797      * we hold a lock for fmasks in the table
 798      */
 799     bier_fmask_lock(bfmi);
 800     bier_fmask_unlock(bt->bt_fmasks[BIER_BP_TO_INDEX(bp)]);
 801
 802     bt->bt_fmasks[BIER_BP_TO_INDEX(bp)] = bfmi;
 803 }
 804
 805 u8 *
 806 format_bier_table_entry (u8 *s, va_list *ap)
 807 {
 808     index_t bti = va_arg(*ap, index_t);
 809     bier_bp_t bp = va_arg(*ap, bier_bp_t);
 810     bier_table_t *bt;
 811     bt = bier_table_get(bti);
 812
 813     if (bier_table_is_main(bt))
 814     {
 815         index_t bei;
 816
 817         bei = bier_table_lookup(bier_table_get(bti), bp);
 818
 819         if (INDEX_INVALID != bei)
 820         {
 821             s = format(s, "%U", format_bier_entry, bei,
 822                        BIER_SHOW_DETAIL);
 823         }
 824     }
 825     else
 826     {
 827         index_t bfmi;
 828
 829         bfmi = bier_table_fwd_lookup(bier_table_get(bti), bp);
 830
 831         if (INDEX_INVALID != bfmi)
 832         {
 833             s = format(s, "%U", format_bier_fmask, bfmi,
 834                        BIER_SHOW_DETAIL);
 835         }
 836     }
 837     return (s);
 838 }
 839
 840 u8 *
 841 format_bier_table (u8 *s, va_list *ap)
 842 {
 843     index_t bti = va_arg(*ap, index_t);
 844     bier_show_flags_t flags = va_arg(*ap, bier_show_flags_t);
 845     bier_table_t *bt;
 846
 847     if (pool_is_free_index(bier_table_pool, bti))
 848     {
 849         return (format(s, "No BIER table %d", bti));
 850     }
 851
 852     bt = bier_table_get(bti);
 853
 854     s = format(s, "[@%d] bier-table:[%U local-label:%U",
 855                bti,
 856                format_bier_table_id, &bt->bt_id,
 857                format_mpls_unicast_label, bt->bt_ll);
 858
 859     if (flags & BIER_SHOW_DETAIL)
 860     {
 861         s = format(s, " locks:%d", bt->bt_locks);
 862     }
 863     s = format(s, "]");
 864
 865     if (flags & BIER_SHOW_DETAIL)
 866     {
 867         if (bier_table_is_main(bt))
 868         {
 869             index_t *bei;
 870
 871             vec_foreach (bei, bt->bt_entries)
 872             {
 873                 if (INDEX_INVALID != *bei)
 874                 {
 875                     s = format(s, "\n%U", format_bier_entry, *bei, 2);
 876                 }
 877             }
 878         }
 879         else
 880         {
 881             u32 ii;
 882
 883             vec_foreach_index (ii, bt->bt_fmasks)
 884             {
 885                 if (INDEX_INVALID != bt->bt_fmasks[ii])
 886                 {
 887                     s = format(s, "\n bp:%d\n %U", ii,
 888                                format_bier_fmask, bt->bt_fmasks[ii], 2);
 889                 }
 890             }
 891         }
 892     }
 893
 894     return (s);
 895 }
 896
 897 void
 898 bier_table_show_all (vlib_main_t * vm,
 899                      bier_show_flags_t flags)
 900 {
 901     if (!pool_elts(bier_table_pool))
 902     {
 903         vlib_cli_output (vm, "No BIER tables");
 904     }
 905     else
 906     {
 907         int ii;
 908
 909         pool_foreach_index(ii, bier_table_pool,
 910         ({
 911             vlib_cli_output (vm, "%U", format_bier_table, ii, flags);
 912         }));
 913     }
 914 }
 915
 916 void
 917 bier_tables_walk (bier_tables_walk_fn_t fn,
 918                   void *ctx)
 919 {
 920     ASSERT(0);
 921 }
 922
 923
 924 void
 925 bier_table_walk (const bier_table_id_t *bti,
 926                  bier_table_walk_fn_t fn,
 927                  void *ctx)
 928 {
 929     bier_table_t *bt;
 930     bier_entry_t *be;
 931     index_t *bei;
 932
 933     bt = bier_table_find(bti);
 934
 935     if (NULL == bt)
 936     {
 937         return;
 938     }
 939
 940     vec_foreach (bei, bt->bt_entries)
 941     {
 942         if (INDEX_INVALID != *bei)
 943         {
 944             be = bier_entry_get(*bei);
 945
 946             fn(bt, be, ctx);
 947         }
 948     }
 949 }