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
  24 #include <vnet/fib/mpls_fib.h>
  25 #include <vnet/mpls/mpls.h>
  26 #include <vnet/fib/fib_path_list.h>
  27
  28 /**
  29  * Memory pool of all the allocated tables
  30  */
  31 bier_table_t *bier_table_pool;
  32
  33 /**
  34  * DB store of all BIER tables index by SD/set/hdr-len
  35  */
  36 static uword *bier_tables_by_key;
  37
  38 /**
  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.
  42  */
  43 #define BIER_N_ECMP_TABLES 16
  44
  45 static inline index_t
  46 bier_table_get_index (const bier_table_t *bt)
  47 {
  48     return (bt - bier_table_pool);
  49 }
  50
  51 int
  52 bier_table_is_main (const bier_table_t *bt)
  53 {
  54     return (BIER_ECMP_TABLE_ID_MAIN == bt->bt_id.bti_ecmp);
  55 }
  56
  57 /*
  58  * Construct the key to use to find a BIER table
  59  * in the global hash map
  60  */
  61 static u32
  62 bier_table_mk_key (const bier_table_id_t *id)
  63 {
  64     /*
  65      * the set and sub-domain Ids are 8 bit values.
  66      * we have space for ECMP table ID and talbe type (SPF/TE)
  67      * for later
  68      */
  69     u32 key = ((id->bti_sub_domain << 24)  |
  70                (id->bti_set << 16) |
  71                (id->bti_ecmp << 8) |
  72                (id->bti_hdr_len << 4) |
  73                (id->bti_type));
  74
  75     return (key);
  76 }
  77
  78 static void
  79 bier_table_init (bier_table_t *bt,
  80                  const bier_table_id_t *id,
  81                  mpls_label_t ll)
  82 {
  83     u32 num_entries;
  84
  85     bt->bt_lfei = FIB_NODE_INDEX_INVALID;
  86     bt->bt_id = *id;
  87     bt->bt_ll = ll;
  88     num_entries = bier_hdr_len_id_to_num_bits(bt->bt_id.bti_hdr_len);
  89
  90     /*
  91      * create the lookup table of entries.
  92      */
  93     if (bier_table_is_main(bt))
  94     {
  95         vec_validate_init_empty_aligned(bt->bt_entries,
  96                                         num_entries,
  97                                         INDEX_INVALID,
  98                                         CLIB_CACHE_LINE_BYTES);
  99         fib_table_find_or_create_and_lock(FIB_PROTOCOL_MPLS,
 100                                           MPLS_FIB_DEFAULT_TABLE_ID,
 101                                           FIB_SOURCE_BIER);
 102     }
 103     else
 104     {
 105         vec_validate_init_empty_aligned(bt->bt_fmasks,
 106                                         num_entries,
 107                                         INDEX_INVALID,
 108                                         CLIB_CACHE_LINE_BYTES);
 109     }
 110 }
 111
 112 static void
 113 bier_table_rm_lfib (bier_table_t *bt)
 114 {
 115     if (FIB_NODE_INDEX_INVALID != bt->bt_lfei)
 116     {
 117         fib_table_entry_delete_index(bt->bt_lfei,
 118                                      FIB_SOURCE_BIER);
 119     }
 120     bt->bt_lfei = FIB_NODE_INDEX_INVALID;
 121 }
 122
 123 static void
 124 bier_table_destroy (bier_table_t *bt)
 125 {
 126     if (bier_table_is_main(bt))
 127     {
 128         index_t *bei;
 129
 130         fib_path_list_unlock(bt->bt_pl);
 131         bt->bt_pl = FIB_NODE_INDEX_INVALID;
 132         /*
 133          * unresolve/remove all entries from the table
 134          */
 135         vec_foreach (bei, bt->bt_entries)
 136         {
 137             if (INDEX_INVALID != *bei)
 138             {
 139                 bier_entry_delete(*bei);
 140             }
 141         }
 142         vec_free (bt->bt_entries);
 143         fib_table_unlock(fib_table_find(FIB_PROTOCOL_MPLS,
 144                                         MPLS_FIB_DEFAULT_TABLE_ID),
 145                          FIB_PROTOCOL_MPLS,
 146                          FIB_SOURCE_BIER);
 147     }
 148     else
 149     {
 150         index_t *bfmi;
 151
 152         /*
 153          * unlock any fmasks
 154          */
 155         vec_foreach (bfmi, bt->bt_fmasks)
 156         {
 157             bier_fmask_unlock(*bfmi);
 158         }
 159         vec_free(bt->bt_fmasks);
 160     }
 161
 162     hash_unset(bier_tables_by_key,
 163                bier_table_mk_key(&bt->bt_id));
 164     pool_put(bier_table_pool, bt);
 165 }
 166
 167 static void
 168 bier_table_lock_i (bier_table_t *bt)
 169 {
 170     bt->bt_locks++;
 171 }
 172
 173 static void
 174 bier_table_unlock_i (bier_table_t *bt)
 175 {
 176     bt->bt_locks--;
 177
 178     if (0 == bt->bt_locks)
 179     {
 180         bier_table_rm_lfib(bt);
 181         bier_table_destroy(bt);
 182     }
 183 }
 184
 185 void
 186 bier_table_unlock (const bier_table_id_t *bti)
 187 {
 188     uword *p;
 189     u32 key;
 190
 191     key = bier_table_mk_key(bti);
 192
 193     p = hash_get (bier_tables_by_key, key);
 194
 195     if (NULL != p) {
 196         bier_table_unlock_i(bier_table_get(p[0]));
 197     }
 198 }
 199
 200 static void
 201 bier_table_mk_lfib (bier_table_t *bt)
 202 {
 203     /*
 204      * Add a new MPLS lfib entry
 205      */
 206     if (MPLS_LABEL_INVALID != bt->bt_ll) {
 207         fib_prefix_t pfx = {
 208             .fp_proto = FIB_PROTOCOL_MPLS,
 209             .fp_len = 21,
 210             .fp_label = bt->bt_ll,
 211             .fp_eos = MPLS_EOS,
 212             .fp_payload_proto = DPO_PROTO_BIER,
 213         };
 214         u32 mpls_fib_index;
 215         dpo_id_t dpo = DPO_INVALID;
 216
 217         /*
 218          * stack the entry on the forwarding chain prodcued by the
 219          * path-list via the ECMP tables.
 220          */
 221         fib_path_list_contribute_forwarding(bt->bt_pl,
 222                                             FIB_FORW_CHAIN_TYPE_BIER,
 223                                             &dpo);
 224
 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,
 228                                                       &pfx,
 229                                                       FIB_SOURCE_BIER,
 230                                                       FIB_ENTRY_FLAG_EXCLUSIVE,
 231                                                       &dpo);
 232         dpo_reset(&dpo);
 233     }
 234 }
 235
 236 static bier_table_t *
 237 bier_table_find (const bier_table_id_t *bti)
 238 {
 239     uword *p;
 240     u32 key;
 241
 242     key = bier_table_mk_key(bti);
 243
 244     p = hash_get(bier_tables_by_key, key);
 245
 246     if (NULL != p)
 247     {
 248         return (bier_table_get(p[0]));
 249     }
 250
 251     return (NULL);
 252 }
 253
 254 static bier_table_t *
 255 bier_table_mk_ecmp (index_t bti)
 256 {
 257     fib_route_path_t *rpaths;
 258     fib_node_index_t pli;
 259     bier_table_t *bt;
 260     int ii;
 261
 262     rpaths = NULL;
 263     bt = bier_table_get(bti);
 264
 265     vec_validate(rpaths, BIER_N_ECMP_TABLES-1);
 266
 267     vec_foreach_index(ii, rpaths)
 268     {
 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;
 272     }
 273
 274     /*
 275      * no oppotunity to share, this the resolving ECMP tables are unique
 276      * to this table.
 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].
 279      */
 280     pli = fib_path_list_create(FIB_PATH_LIST_FLAG_NO_URPF, rpaths);
 281     fib_path_list_lock(pli);
 282
 283     /*
 284      * constructing the path-list will have created many more BIER tables,
 285      * so this main table will no doubt have re-alloc.
 286      */
 287     bt = bier_table_get(bti);
 288     bt->bt_pl = pli;
 289
 290     vec_free(rpaths);
 291
 292     return (bt);
 293 }
 294
 295 index_t
 296 bier_table_add_or_lock (const bier_table_id_t *btid,
 297                         mpls_label_t local_label)
 298 {
 299     bier_table_t *bt;
 300     index_t bti;
 301
 302     bt = bier_table_find(btid);
 303
 304     if (NULL != bt) {
 305         /*
 306          * modify an existing table.
 307          * change the lfib entry to the new local label
 308          */
 309         if (bier_table_is_main(bt) &&
 310             (local_label != MPLS_LABEL_INVALID))
 311         {
 312             bier_table_rm_lfib(bt);
 313
 314             bt->bt_ll = local_label;
 315             bier_table_mk_lfib(bt);
 316         }
 317         bti = bier_table_get_index(bt);
 318     }
 319     else
 320     {
 321         /*
 322          * add a new table
 323          */
 324         u32 key;
 325
 326         key = bier_table_mk_key(btid);
 327
 328         pool_get_aligned(bier_table_pool, bt, CLIB_CACHE_LINE_BYTES);
 329         bier_table_init(bt, btid, local_label);
 330
 331         hash_set(bier_tables_by_key, key, bier_table_get_index(bt));
 332         bti = bier_table_get_index(bt);
 333
 334         if (bier_table_is_main(bt))
 335         {
 336             bt = bier_table_mk_ecmp(bti);
 337             bier_table_mk_lfib(bt);
 338         }
 339     }
 340
 341     bier_table_lock_i(bt);
 342
 343     return (bti);
 344 }
 345
 346 index_t
 347 bier_table_ecmp_create_and_lock (const bier_table_id_t *btid)
 348 {
 349     return (bier_table_add_or_lock(btid, MPLS_LABEL_INVALID));
 350 }
 351
 352 void
 353 bier_table_ecmp_unlock (index_t bti)
 354 {
 355     bier_table_unlock_i(bier_table_get(bti));
 356 }
 357
 358 static void
 359 bier_table_dpo_lock (dpo_id_t *dpo)
 360 {
 361 }
 362
 363 static void
 364 bier_table_dpo_unlock (dpo_id_t *dpo)
 365 {
 366 }
 367
 368 static void
 369 bier_table_dpo_mem_show (void)
 370 {
 371     fib_show_memory_usage("BIER-table",
 372                           pool_elts(bier_table_pool),
 373                           pool_len(bier_table_pool),
 374                           sizeof(bier_table_t));
 375 }
 376 static u8 *
 377 format_bier_table_dpo (u8 *s, va_list *ap)
 378 {
 379     index_t bti = va_arg(*ap, index_t);
 380     bier_table_t *bt;
 381
 382     bt = bier_table_get(bti);
 383
 384     return (format(s, "[%U]", format_bier_table_id, &bt->bt_id));
 385 }
 386
 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,
 392 };
 393
 394 const static char *const bier_table_mpls_nodes[] =
 395 {
 396     "bier-input",
 397     NULL
 398 };
 399 const static char * const * const bier_table_nodes[DPO_PROTO_NUM] =
 400 {
 401     [DPO_PROTO_BIER] = bier_table_mpls_nodes,
 402 };
 403
 404 static clib_error_t *
 405 bier_table_module_init (vlib_main_t *vm)
 406 {
 407     dpo_register(DPO_BIER_TABLE, &bier_table_dpo_vft, bier_table_nodes);
 408
 409     return (NULL);
 410 }
 411
 412 VLIB_INIT_FUNCTION (bier_table_module_init);
 413
 414 const bier_table_id_t *
 415 bier_table_get_id (index_t bti)
 416 {
 417     bier_table_t *bt;
 418
 419     bt = bier_table_get(bti);
 420
 421     return (&bt->bt_id);
 422 }
 423
 424 static void
 425 bier_table_insert (bier_table_t *bt,
 426                    bier_bp_t bp,
 427                    index_t bei)
 428 {
 429     bt->bt_entries[BIER_BP_TO_INDEX(bp)] = bei;
 430 }
 431
 432 static void
 433 bier_table_remove (bier_table_t *bt,
 434                    bier_bp_t bp)
 435 {
 436     bt->bt_entries[BIER_BP_TO_INDEX(bp)] = INDEX_INVALID;
 437 }
 438
 439 void
 440 bier_table_route_add (const bier_table_id_t *btid,
 441                       bier_bp_t bp,
 442                       fib_route_path_t *brps)
 443 {
 444     index_t bfmi, bti, bei, *bfmip, *bfmis = NULL;
 445     fib_route_path_t *brp;
 446     bier_table_t *bt;
 447
 448     bt = bier_table_find(btid);
 449
 450     if (NULL == bt) {
 451         return;
 452     }
 453
 454     bti = bier_table_get_index(bt);
 455     bei = bier_table_lookup(bt, bp);
 456
 457     /*
 458      * set the FIB index in the path to the BIER table index
 459      */
 460     vec_foreach(brp, brps)
 461     {
 462         bier_fmask_id_t fmid = {
 463             .bfmi_nh = brp->frp_addr,
 464             .bfmi_hdr_type = BIER_HDR_O_MPLS,
 465         };
 466         bfmi = bier_fmask_db_find_or_create_and_lock(bier_table_get_index(bt),
 467                                                      &fmid,
 468                                                      brp);
 469
 470         brp->frp_bier_fib_index = bti;
 471         vec_add1(bfmis, bfmi);
 472     }
 473
 474     if (INDEX_INVALID == bei)
 475     {
 476         bei = bier_entry_create(bti, bp);
 477         bier_table_insert(bt, bp, bei);
 478     }
 479     bier_entry_path_add(bei, brps);
 480
 481     vec_foreach(bfmip, bfmis)
 482     {
 483         bier_fmask_unlock(*bfmip);
 484     }
 485     vec_free(bfmis);
 486 }
 487
 488 void
 489 bier_table_route_remove (const bier_table_id_t *bti,
 490                          bier_bp_t bp,
 491                          fib_route_path_t *brps)
 492 {
 493     fib_route_path_t *brp = NULL;
 494     bier_table_t *bt;
 495     index_t bei;
 496
 497     bt = bier_table_find(bti);
 498
 499     if (NULL == bt) {
 500         return;
 501     }
 502
 503     bei = bier_table_lookup(bt, bp);
 504
 505     if (INDEX_INVALID == bei)
 506     {
 507         /* no such entry */
 508         return;
 509     }
 510
 511     vec_foreach(brp, brps)
 512     {
 513         brp->frp_bier_fib_index = bier_table_get_index(bt);
 514     }
 515
 516     if (0 == bier_entry_path_remove(bei, brps))
 517     {
 518         /* 0 remaining paths */
 519         bier_table_remove(bt, bp);
 520         bier_entry_delete(bei);
 521     }
 522 }
 523
 524 void
 525 bier_table_contribute_forwarding (index_t bti,
 526                                   dpo_id_t *dpo)
 527 {
 528     bier_table_t *bt;
 529
 530     bt = bier_table_get(bti);
 531
 532     if (BIER_ECMP_TABLE_ID_MAIN == bt->bt_id.bti_ecmp)
 533     {
 534         /*
 535          * return the load-balance for the ECMP tables
 536          */
 537         fib_path_list_contribute_forwarding(bt->bt_pl,
 538                                             FIB_FORW_CHAIN_TYPE_BIER,
 539                                             dpo);
 540     }
 541     else
 542     {
 543         dpo_set(dpo, DPO_BIER_TABLE, DPO_PROTO_BIER, bti);
 544     }
 545 }
 546
 547 typedef struct bier_table_ecmp_walk_ctx_t_
 548 {
 549     bier_table_ecmp_walk_fn_t fn;
 550     void *ctx;
 551 } bier_table_ecmp_walk_ctx_t;
 552
 553 static fib_path_list_walk_rc_t
 554 bier_table_ecmp_walk_path_list (fib_node_index_t pl_index,
 555                                 fib_node_index_t path_index,
 556                                 void *arg)
 557 {
 558     bier_table_ecmp_walk_ctx_t *ctx = arg;
 559
 560     ctx->fn(fib_path_get_resolving_index(path_index), ctx->ctx);
 561     /* continue */
 562     return (FIB_PATH_LIST_WALK_CONTINUE);
 563 }
 564
 565 void
 566 bier_table_ecmp_walk (index_t bti,
 567                       bier_table_ecmp_walk_fn_t fn,
 568                       void *ctx)
 569 {
 570     bier_table_ecmp_walk_ctx_t ewc = {
 571         .fn = fn,
 572         .ctx = ctx,
 573     };
 574     bier_table_t *bt;
 575
 576     bt = bier_table_get(bti);
 577
 578     fib_path_list_walk(bt->bt_pl,
 579                        bier_table_ecmp_walk_path_list,
 580                        &ewc);
 581 }
 582
 583 void
 584 bier_table_ecmp_set_fmask (index_t bti,
 585                            bier_bp_t bp,
 586                            index_t bfmi)
 587 {
 588     bier_table_t *bt;
 589
 590     bt = bier_table_get(bti);
 591
 592     /*
 593      * we hold a lock for fmasks in the table
 594      */
 595     bier_fmask_lock(bfmi);
 596     bier_fmask_unlock(bt->bt_fmasks[BIER_BP_TO_INDEX(bp)]);
 597
 598     bt->bt_fmasks[BIER_BP_TO_INDEX(bp)] = bfmi;
 599 }
 600
 601 u8 *
 602 format_bier_table_entry (u8 *s, va_list *ap)
 603 {
 604     index_t bti = va_arg(*ap, index_t);
 605     bier_bp_t bp = va_arg(*ap, bier_bp_t);
 606     bier_table_t *bt;
 607     bt = bier_table_get(bti);
 608
 609     if (bier_table_is_main(bt))
 610     {
 611         index_t bei;
 612
 613         bei = bier_table_lookup(bier_table_get(bti), bp);
 614
 615         if (INDEX_INVALID != bei)
 616         {
 617             s = format(s, "%U", format_bier_entry, bei,
 618                        BIER_SHOW_DETAIL);
 619         }
 620     }
 621     else
 622     {
 623         index_t bfmi;
 624
 625         bfmi = bier_table_fwd_lookup(bier_table_get(bti), bp);
 626
 627         if (INDEX_INVALID != bfmi)
 628         {
 629             s = format(s, "%U", format_bier_fmask, bfmi,
 630                        BIER_SHOW_DETAIL);
 631         }
 632     }
 633     return (s);
 634 }
 635
 636 u8 *
 637 format_bier_table (u8 *s, va_list *ap)
 638 {
 639     index_t bti = va_arg(*ap, index_t);
 640     bier_show_flags_t flags = va_arg(*ap, bier_show_flags_t);
 641     bier_table_t *bt;
 642
 643     if (pool_is_free_index(bier_table_pool, bti))
 644     {
 645         return (format(s, "No BIER f-mask %d", bti));
 646     }
 647
 648     bt = bier_table_get(bti);
 649
 650     s = format(s, "[@%d] bier-table:[%U local-label:%U]",
 651                bti,
 652                format_bier_table_id, &bt->bt_id,
 653                format_mpls_unicast_label, bt->bt_ll);
 654
 655     if (flags & BIER_SHOW_DETAIL)
 656     {
 657         s = format(s, " locks:%d", bt->bt_locks);
 658     }
 659     s = format(s, "]");
 660
 661     if (flags & BIER_SHOW_DETAIL)
 662     {
 663         if (bier_table_is_main(bt))
 664         {
 665             index_t *bei;
 666
 667             vec_foreach (bei, bt->bt_entries)
 668             {
 669                 if (INDEX_INVALID != *bei)
 670                 {
 671                     s = format(s, "\n%U", format_bier_entry, *bei, 2);
 672                 }
 673             }
 674         }
 675         else
 676         {
 677             u32 ii;
 678
 679             vec_foreach_index (ii, bt->bt_fmasks)
 680             {
 681                 if (INDEX_INVALID != bt->bt_fmasks[ii])
 682                 {
 683                     s = format(s, "\n bp:%d\n %U", ii,
 684                                format_bier_fmask, bt->bt_fmasks[ii], 2);
 685                 }
 686             }
 687         }
 688     }
 689
 690     return (s);
 691 }
 692
 693 void
 694 bier_table_show_all (vlib_main_t * vm,
 695                      bier_show_flags_t flags)
 696 {
 697     if (!pool_elts(bier_table_pool))
 698     {
 699         vlib_cli_output (vm, "No BIER tables");
 700     }
 701     else
 702     {
 703         int ii;
 704
 705         pool_foreach_index(ii, bier_table_pool,
 706         ({
 707             vlib_cli_output (vm, "%U", format_bier_table, ii, flags);
 708         }));
 709     }
 710 }
 711
 712 void
 713 bier_tables_walk (bier_tables_walk_fn_t fn,
 714                   void *ctx)
 715 {
 716     ASSERT(0);
 717 }
 718
 719
 720 void
 721 bier_table_walk (const bier_table_id_t *bti,
 722                  bier_table_walk_fn_t fn,
 723                  void *ctx)
 724 {
 725     bier_table_t *bt;
 726     bier_entry_t *be;
 727     index_t *bei;
 728
 729     bt = bier_table_find(bti);
 730
 731     if (NULL == bt)
 732     {
 733         return;
 734     }
 735
 736     vec_foreach (bei, bt->bt_entries)
 737     {
 738         if (INDEX_INVALID != *bei)
 739         {
 740             be = bier_entry_get(*bei);
 741
 742             fn(bt, be, ctx);
 743         }
 744     }
 745 }