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 prodcued 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 oppotunity 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 index_t
 333 bier_table_add_or_lock (const bier_table_id_t *btid,
 334                         mpls_label_t local_label)
 335 {
 336     bier_table_t *bt;
 337     index_t bti;
 338
 339     bt = bier_table_find(btid);
 340
 341     if (NULL != bt) {
 342         /*
 343          * modify an existing table.
 344          * change the lfib entry to the new local label
 345          */
 346         if (bier_table_is_main(bt))
 347         {
 348             /*
 349              * remove the mpls-fib or bift entry
 350              */
 351             if (MPLS_LABEL_INVALID != bt->bt_ll)
 352             {
 353                 bier_table_rm_lfib(bt);
 354             }
 355             else
 356             {
 357                 bier_table_rm_bift(bt);
 358             }
 359
 360             /*
 361              * reset
 362              */
 363             bt->bt_ll = MPLS_LABEL_INVALID;
 364
 365             /*
 366              * add whichever mpls-fib or bift we need
 367              */
 368             if (local_label != MPLS_LABEL_INVALID)
 369             {
 370                 bt->bt_ll = local_label;
 371                 bier_table_mk_lfib(bt);
 372             }
 373             else
 374             {
 375                 bier_table_mk_bift(bt);
 376             }
 377         }
 378         bti = bier_table_get_index(bt);
 379     }
 380     else
 381     {
 382         /*
 383          * add a new table
 384          */
 385         u32 key;
 386
 387         key = bier_table_mk_key(btid);
 388
 389         pool_get_aligned(bier_table_pool, bt, CLIB_CACHE_LINE_BYTES);
 390         bier_table_init(bt, btid, local_label);
 391
 392         hash_set(bier_tables_by_key, key, bier_table_get_index(bt));
 393         bti = bier_table_get_index(bt);
 394
 395         if (bier_table_is_main(bt))
 396         {
 397             bt = bier_table_mk_ecmp(bti);
 398
 399             /*
 400              * add whichever mpls-fib or bift we need
 401              */
 402             if (local_label != MPLS_LABEL_INVALID)
 403             {
 404                 bt->bt_ll = local_label;
 405                 bier_table_mk_lfib(bt);
 406             }
 407             else
 408             {
 409                 bier_table_mk_bift(bt);
 410             }
 411         }
 412     }
 413
 414     bier_table_lock_i(bt);
 415
 416     return (bti);
 417 }
 418
 419 index_t
 420 bier_table_ecmp_create_and_lock (const bier_table_id_t *btid)
 421 {
 422     return (bier_table_add_or_lock(btid, MPLS_LABEL_INVALID));
 423 }
 424
 425 void
 426 bier_table_ecmp_unlock (index_t bti)
 427 {
 428     bier_table_unlock_i(bier_table_get(bti));
 429 }
 430
 431 static void
 432 bier_table_dpo_lock (dpo_id_t *dpo)
 433 {
 434 }
 435
 436 static void
 437 bier_table_dpo_unlock (dpo_id_t *dpo)
 438 {
 439 }
 440
 441 static void
 442 bier_table_dpo_mem_show (void)
 443 {
 444     fib_show_memory_usage("BIER-table",
 445                           pool_elts(bier_table_pool),
 446                           pool_len(bier_table_pool),
 447                           sizeof(bier_table_t));
 448 }
 449 static u8 *
 450 format_bier_table_dpo (u8 *s, va_list *ap)
 451 {
 452     index_t bti = va_arg(*ap, index_t);
 453     bier_table_t *bt;
 454
 455     bt = bier_table_get(bti);
 456
 457     return (format(s, "[%U]", format_bier_table_id, &bt->bt_id));
 458 }
 459
 460 const static dpo_vft_t bier_table_dpo_vft = {
 461     .dv_lock = bier_table_dpo_lock,
 462     .dv_unlock = bier_table_dpo_unlock,
 463     .dv_format = format_bier_table_dpo,
 464     .dv_mem_show = bier_table_dpo_mem_show,
 465 };
 466
 467 const static char *const bier_table_mpls_nodes[] =
 468 {
 469     "bier-input",
 470     NULL
 471 };
 472 const static char * const * const bier_table_nodes[DPO_PROTO_NUM] =
 473 {
 474     [DPO_PROTO_BIER] = bier_table_mpls_nodes,
 475 };
 476
 477 static clib_error_t *
 478 bier_table_module_init (vlib_main_t *vm)
 479 {
 480     dpo_register(DPO_BIER_TABLE, &bier_table_dpo_vft, bier_table_nodes);
 481
 482     return (NULL);
 483 }
 484
 485 VLIB_INIT_FUNCTION (bier_table_module_init);
 486
 487 const bier_table_id_t *
 488 bier_table_get_id (index_t bti)
 489 {
 490     bier_table_t *bt;
 491
 492     bt = bier_table_get(bti);
 493
 494     return (&bt->bt_id);
 495 }
 496
 497 static void
 498 bier_table_insert (bier_table_t *bt,
 499                    bier_bp_t bp,
 500                    index_t bei)
 501 {
 502     bt->bt_entries[BIER_BP_TO_INDEX(bp)] = bei;
 503 }
 504
 505 static void
 506 bier_table_remove (bier_table_t *bt,
 507                    bier_bp_t bp)
 508 {
 509     bt->bt_entries[BIER_BP_TO_INDEX(bp)] = INDEX_INVALID;
 510 }
 511
 512 void
 513 bier_table_route_path_update_i (const bier_table_id_t *btid,
 514                                 bier_bp_t bp,
 515                                 fib_route_path_t *brps,
 516                                 u8 is_replace)
 517 {
 518     index_t bfmi, bti, bei, *bfmip, *bfmis = NULL;
 519     fib_route_path_t *brp;
 520     bier_table_t *bt;
 521
 522     bt = bier_table_find(btid);
 523
 524     if (NULL == bt) {
 525         return;
 526     }
 527
 528     bti = bier_table_get_index(bt);
 529     bei = bier_table_lookup(bt, bp);
 530
 531     /*
 532      * set the FIB index in the path to the BIER table index
 533      */
 534     vec_foreach(brp, brps)
 535     {
 536         /*
 537          * First use the path to find or construct an FMask object
 538          * via the next-hop
 539          */
 540         bfmi = bier_fmask_db_find_or_create_and_lock(bti, brp);
 541         vec_add1(bfmis, bfmi);
 542
 543         /*
 544          * then modify the path to resolve via this fmask object
 545          * and use it to resolve the BIER entry.
 546          */
 547         brp->frp_flags = FIB_ROUTE_PATH_BIER_FMASK;
 548         brp->frp_bier_fmask = bfmi;
 549     }
 550
 551     if (INDEX_INVALID == bei)
 552     {
 553         bei = bier_entry_create(bti, bp);
 554         bier_table_insert(bt, bp, bei);
 555     }
 556
 557     if (is_replace)
 558     {
 559         bier_entry_path_update(bei, brps);
 560     }
 561     else
 562     {
 563         fib_route_path_t *t_paths = NULL;
 564
 565         vec_foreach(brp, brps)
 566         {
 567             vec_add1(t_paths, *brp);
 568             bier_entry_path_add(bei, t_paths);
 569             vec_reset_length(t_paths);
 570         }
 571         vec_free(t_paths);
 572     }
 573
 574     vec_foreach(bfmip, bfmis)
 575     {
 576         bier_fmask_unlock(*bfmip);
 577     }
 578     vec_free(bfmis);
 579 }
 580
 581 void
 582 bier_table_route_path_update (const bier_table_id_t *btid,
 583                               bier_bp_t bp,
 584                               fib_route_path_t *brps)
 585 {
 586     bier_table_route_path_update_i(btid, bp, brps, 1);
 587 }
 588 void
 589 bier_table_route_path_add (const bier_table_id_t *btid,
 590                            bier_bp_t bp,
 591                            fib_route_path_t *brps)
 592 {
 593     bier_table_route_path_update_i(btid, bp, brps, 0);
 594 }
 595
 596 void
 597 bier_table_route_delete (const bier_table_id_t *btid,
 598                          bier_bp_t bp)
 599 {
 600     bier_table_t *bt;
 601     index_t bei;
 602
 603     bt = bier_table_find(btid);
 604
 605     if (NULL == bt) {
 606         return;
 607     }
 608
 609     bei = bier_table_lookup(bt, bp);
 610
 611     if (INDEX_INVALID == bei)
 612     {
 613         /* no such entry */
 614         return;
 615     }
 616
 617     bier_table_remove(bt, bp);
 618     bier_entry_delete(bei);
 619 }
 620
 621 void
 622 bier_table_route_path_remove (const bier_table_id_t *btid,
 623                               bier_bp_t bp,
 624                               fib_route_path_t *brps)
 625 {
 626     fib_route_path_t *brp = NULL, *t_paths = NULL;
 627     index_t bfmi, bti, bei;
 628     bier_table_t *bt;
 629     u32 ii;
 630
 631     bt = bier_table_find(btid);
 632
 633     if (NULL == bt) {
 634         return;
 635     }
 636
 637     bti = bier_table_get_index(bt);
 638     bei = bier_table_lookup(bt, bp);
 639
 640     if (INDEX_INVALID == bei)
 641     {
 642         /* no such entry */
 643         return;
 644     }
 645
 646     /*
 647      * set the FIB index in the path to the BIER table index
 648      */
 649     vec_foreach_index(ii, brps)
 650     {
 651         brp = &brps[ii];
 652         bfmi = bier_fmask_db_find(bti, brp);
 653
 654         if (INDEX_INVALID == bfmi)
 655         {
 656             /*
 657              * no matching fmask, not a path we can remove
 658              */
 659             vec_del1(brps, ii);
 660             continue;
 661         }
 662
 663         /*
 664          * then modify the path to resolve via this fmask object
 665          * and use it to resolve the BIER entry.
 666          */
 667         brp->frp_flags = FIB_ROUTE_PATH_BIER_FMASK;
 668         brp->frp_bier_fmask = bfmi;
 669     }
 670
 671     if (0 == vec_len(brps))
 672     {
 673         return;
 674     }
 675
 676     vec_foreach(brp, brps)
 677     {
 678         vec_add1(t_paths, *brp);
 679         if (0 == bier_entry_path_remove(bei, t_paths))
 680         {
 681             /* 0 remaining paths */
 682             bier_table_remove(bt, bp);
 683             bier_entry_delete(bei);
 684             break;
 685         }
 686         vec_reset_length(t_paths);
 687     }
 688     vec_free(t_paths);
 689 }
 690
 691 void
 692 bier_table_contribute_forwarding (index_t bti,
 693                                   dpo_id_t *dpo)
 694 {
 695     bier_table_t *bt;
 696
 697     bt = bier_table_get(bti);
 698
 699     if (BIER_ECMP_TABLE_ID_MAIN == bt->bt_id.bti_ecmp)
 700     {
 701         /*
 702          * return the load-balance for the ECMP tables
 703          */
 704         fib_path_list_contribute_forwarding(bt->bt_pl,
 705                                             FIB_FORW_CHAIN_TYPE_BIER,
 706                                             FIB_PATH_LIST_FWD_FLAG_COLLAPSE,
 707                                             dpo);
 708     }
 709     else
 710     {
 711         dpo_set(dpo, DPO_BIER_TABLE, DPO_PROTO_BIER, bti);
 712     }
 713 }
 714
 715 typedef struct bier_table_ecmp_walk_ctx_t_
 716 {
 717     bier_table_ecmp_walk_fn_t fn;
 718     void *ctx;
 719 } bier_table_ecmp_walk_ctx_t;
 720
 721 static fib_path_list_walk_rc_t
 722 bier_table_ecmp_walk_path_list (fib_node_index_t pl_index,
 723                                 fib_node_index_t path_index,
 724                                 void *arg)
 725 {
 726     bier_table_ecmp_walk_ctx_t *ctx = arg;
 727
 728     ctx->fn(fib_path_get_resolving_index(path_index), ctx->ctx);
 729     /* continue */
 730     return (FIB_PATH_LIST_WALK_CONTINUE);
 731 }
 732
 733 void
 734 bier_table_ecmp_walk (index_t bti,
 735                       bier_table_ecmp_walk_fn_t fn,
 736                       void *ctx)
 737 {
 738     bier_table_ecmp_walk_ctx_t ewc = {
 739         .fn = fn,
 740         .ctx = ctx,
 741     };
 742     bier_table_t *bt;
 743
 744     bt = bier_table_get(bti);
 745
 746     fib_path_list_walk(bt->bt_pl,
 747                        bier_table_ecmp_walk_path_list,
 748                        &ewc);
 749 }
 750
 751 void
 752 bier_table_ecmp_set_fmask (index_t bti,
 753                            bier_bp_t bp,
 754                            index_t bfmi)
 755 {
 756     bier_table_t *bt;
 757
 758     bt = bier_table_get(bti);
 759
 760     /*
 761      * we hold a lock for fmasks in the table
 762      */
 763     bier_fmask_lock(bfmi);
 764     bier_fmask_unlock(bt->bt_fmasks[BIER_BP_TO_INDEX(bp)]);
 765
 766     bt->bt_fmasks[BIER_BP_TO_INDEX(bp)] = bfmi;
 767 }
 768
 769 u8 *
 770 format_bier_table_entry (u8 *s, va_list *ap)
 771 {
 772     index_t bti = va_arg(*ap, index_t);
 773     bier_bp_t bp = va_arg(*ap, bier_bp_t);
 774     bier_table_t *bt;
 775     bt = bier_table_get(bti);
 776
 777     if (bier_table_is_main(bt))
 778     {
 779         index_t bei;
 780
 781         bei = bier_table_lookup(bier_table_get(bti), bp);
 782
 783         if (INDEX_INVALID != bei)
 784         {
 785             s = format(s, "%U", format_bier_entry, bei,
 786                        BIER_SHOW_DETAIL);
 787         }
 788     }
 789     else
 790     {
 791         index_t bfmi;
 792
 793         bfmi = bier_table_fwd_lookup(bier_table_get(bti), bp);
 794
 795         if (INDEX_INVALID != bfmi)
 796         {
 797             s = format(s, "%U", format_bier_fmask, bfmi,
 798                        BIER_SHOW_DETAIL);
 799         }
 800     }
 801     return (s);
 802 }
 803
 804 u8 *
 805 format_bier_table (u8 *s, va_list *ap)
 806 {
 807     index_t bti = va_arg(*ap, index_t);
 808     bier_show_flags_t flags = va_arg(*ap, bier_show_flags_t);
 809     bier_table_t *bt;
 810
 811     if (pool_is_free_index(bier_table_pool, bti))
 812     {
 813         return (format(s, "No BIER table %d", bti));
 814     }
 815
 816     bt = bier_table_get(bti);
 817
 818     s = format(s, "[@%d] bier-table:[%U local-label:%U",
 819                bti,
 820                format_bier_table_id, &bt->bt_id,
 821                format_mpls_unicast_label, bt->bt_ll);
 822
 823     if (flags & BIER_SHOW_DETAIL)
 824     {
 825         s = format(s, " locks:%d", bt->bt_locks);
 826     }
 827     s = format(s, "]");
 828
 829     if (flags & BIER_SHOW_DETAIL)
 830     {
 831         if (bier_table_is_main(bt))
 832         {
 833             index_t *bei;
 834
 835             vec_foreach (bei, bt->bt_entries)
 836             {
 837                 if (INDEX_INVALID != *bei)
 838                 {
 839                     s = format(s, "\n%U", format_bier_entry, *bei, 2);
 840                 }
 841             }
 842         }
 843         else
 844         {
 845             u32 ii;
 846
 847             vec_foreach_index (ii, bt->bt_fmasks)
 848             {
 849                 if (INDEX_INVALID != bt->bt_fmasks[ii])
 850                 {
 851                     s = format(s, "\n bp:%d\n %U", ii,
 852                                format_bier_fmask, bt->bt_fmasks[ii], 2);
 853                 }
 854             }
 855         }
 856     }
 857
 858     return (s);
 859 }
 860
 861 void
 862 bier_table_show_all (vlib_main_t * vm,
 863                      bier_show_flags_t flags)
 864 {
 865     if (!pool_elts(bier_table_pool))
 866     {
 867         vlib_cli_output (vm, "No BIER tables");
 868     }
 869     else
 870     {
 871         int ii;
 872
 873         pool_foreach_index(ii, bier_table_pool,
 874         ({
 875             vlib_cli_output (vm, "%U", format_bier_table, ii, flags);
 876         }));
 877     }
 878 }
 879
 880 void
 881 bier_tables_walk (bier_tables_walk_fn_t fn,
 882                   void *ctx)
 883 {
 884     ASSERT(0);
 885 }
 886
 887
 888 void
 889 bier_table_walk (const bier_table_id_t *bti,
 890                  bier_table_walk_fn_t fn,
 891                  void *ctx)
 892 {
 893     bier_table_t *bt;
 894     bier_entry_t *be;
 895     index_t *bei;
 896
 897     bt = bier_table_find(bti);
 898
 899     if (NULL == bt)
 900     {
 901         return;
 902     }
 903
 904     vec_foreach (bei, bt->bt_entries)
 905     {
 906         if (INDEX_INVALID != *bei)
 907         {
 908             be = bier_entry_get(*bei);
 909
 910             fn(bt, be, ctx);
 911         }
 912     }
 913 }