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 };
 398 const static char * const * const bier_table_nodes[DPO_PROTO_NUM] =
 399 {
 400     [DPO_PROTO_BIER] = bier_table_mpls_nodes,
 401 };
 402
 403 static clib_error_t *
 404 bier_table_module_init (vlib_main_t *vm)
 405 {
 406     dpo_register(DPO_BIER_TABLE, &bier_table_dpo_vft, bier_table_nodes);
 407
 408     return (NULL);
 409 }
 410
 411 VLIB_INIT_FUNCTION (bier_table_module_init);
 412
 413 const bier_table_id_t *
 414 bier_table_get_id (index_t bti)
 415 {
 416     bier_table_t *bt;
 417
 418     bt = bier_table_get(bti);
 419
 420     return (&bt->bt_id);
 421 }
 422
 423 static void
 424 bier_table_insert (bier_table_t *bt,
 425                    bier_bp_t bp,
 426                    index_t bei)
 427 {
 428     bt->bt_entries[BIER_BP_TO_INDEX(bp)] = bei;
 429 }
 430
 431 static void
 432 bier_table_remove (bier_table_t *bt,
 433                    bier_bp_t bp)
 434 {
 435     bt->bt_entries[BIER_BP_TO_INDEX(bp)] = INDEX_INVALID;
 436 }
 437
 438 void
 439 bier_table_route_add (const bier_table_id_t *btid,
 440                       bier_bp_t bp,
 441                       fib_route_path_t *brps)
 442 {
 443     index_t bfmi, bti, bei, *bfmip, *bfmis = NULL;
 444     fib_route_path_t *brp;
 445     bier_table_t *bt;
 446
 447     bt = bier_table_find(btid);
 448
 449     if (NULL == bt) {
 450         return;
 451     }
 452
 453     bti = bier_table_get_index(bt);
 454     bei = bier_table_lookup(bt, bp);
 455
 456     /*
 457      * set the FIB index in the path to the BIER table index
 458      */
 459     vec_foreach(brp, brps)
 460     {
 461         bier_fmask_id_t fmid = {
 462             .bfmi_nh = brp->frp_addr,
 463             .bfmi_hdr_type = BIER_HDR_O_MPLS,
 464         };
 465         bfmi = bier_fmask_db_find_or_create_and_lock(bier_table_get_index(bt),
 466                                                      &fmid,
 467                                                      brp);
 468
 469         brp->frp_bier_fib_index = bti;
 470         vec_add1(bfmis, bfmi);
 471     }
 472
 473     if (INDEX_INVALID == bei)
 474     {
 475         bei = bier_entry_create(bti, bp);
 476         bier_table_insert(bt, bp, bei);
 477     }
 478     bier_entry_path_add(bei, brps);
 479
 480     vec_foreach(bfmip, bfmis)
 481     {
 482         bier_fmask_unlock(*bfmip);
 483     }
 484     vec_free(bfmis);
 485 }
 486
 487 void
 488 bier_table_route_remove (const bier_table_id_t *bti,
 489                          bier_bp_t bp,
 490                          fib_route_path_t *brps)
 491 {
 492     fib_route_path_t *brp = NULL;
 493     bier_table_t *bt;
 494     index_t bei;
 495
 496     bt = bier_table_find(bti);
 497
 498     if (NULL == bt) {
 499         return;
 500     }
 501
 502     bei = bier_table_lookup(bt, bp);
 503
 504     if (INDEX_INVALID == bei)
 505     {
 506         /* no such entry */
 507         return;
 508     }
 509
 510     vec_foreach(brp, brps)
 511     {
 512         brp->frp_bier_fib_index = bier_table_get_index(bt);
 513     }
 514
 515     if (0 == bier_entry_path_remove(bei, brps))
 516     {
 517         /* 0 remaining paths */
 518         bier_table_remove(bt, bp);
 519         bier_entry_delete(bei);
 520     }
 521 }
 522
 523 void
 524 bier_table_contribute_forwarding (index_t bti,
 525                                   dpo_id_t *dpo)
 526 {
 527     bier_table_t *bt;
 528
 529     bt = bier_table_get(bti);
 530
 531     if (BIER_ECMP_TABLE_ID_MAIN == bt->bt_id.bti_ecmp)
 532     {
 533         /*
 534          * return the load-balance for the ECMP tables
 535          */
 536         fib_path_list_contribute_forwarding(bt->bt_pl,
 537                                             FIB_FORW_CHAIN_TYPE_BIER,
 538                                             dpo);
 539     }
 540     else
 541     {
 542         dpo_set(dpo, DPO_BIER_TABLE, DPO_PROTO_BIER, bti);
 543     }
 544 }
 545
 546 typedef struct bier_table_ecmp_walk_ctx_t_
 547 {
 548     bier_table_ecmp_walk_fn_t fn;
 549     void *ctx;
 550 } bier_table_ecmp_walk_ctx_t;
 551
 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,
 555                                 void *arg)
 556 {
 557     bier_table_ecmp_walk_ctx_t *ctx = arg;
 558
 559     ctx->fn(fib_path_get_resolving_index(path_index), ctx->ctx);
 560     /* continue */
 561     return (FIB_PATH_LIST_WALK_CONTINUE);
 562 }
 563
 564 void
 565 bier_table_ecmp_walk (index_t bti,
 566                       bier_table_ecmp_walk_fn_t fn,
 567                       void *ctx)
 568 {
 569     bier_table_ecmp_walk_ctx_t ewc = {
 570         .fn = fn,
 571         .ctx = ctx,
 572     };
 573     bier_table_t *bt;
 574
 575     bt = bier_table_get(bti);
 576
 577     fib_path_list_walk(bt->bt_pl,
 578                        bier_table_ecmp_walk_path_list,
 579                        &ewc);
 580 }
 581
 582 void
 583 bier_table_ecmp_set_fmask (index_t bti,
 584                            bier_bp_t bp,
 585                            index_t bfmi)
 586 {
 587     bier_table_t *bt;
 588
 589     bt = bier_table_get(bti);
 590
 591     /*
 592      * we hold a lock for fmasks in the table
 593      */
 594     bier_fmask_lock(bfmi);
 595     bier_fmask_unlock(bt->bt_fmasks[BIER_BP_TO_INDEX(bp)]);
 596
 597     bt->bt_fmasks[BIER_BP_TO_INDEX(bp)] = bfmi;
 598 }
 599
 600 u8 *
 601 format_bier_table_entry (u8 *s, va_list *ap)
 602 {
 603     index_t bti = va_arg(*ap, index_t);
 604     bier_bp_t bp = va_arg(*ap, bier_bp_t);
 605     bier_table_t *bt;
 606     bt = bier_table_get(bti);
 607
 608     if (bier_table_is_main(bt))
 609     {
 610         index_t bei;
 611
 612         bei = bier_table_lookup(bier_table_get(bti), bp);
 613
 614         if (INDEX_INVALID != bei)
 615         {
 616             s = format(s, "%U", format_bier_entry, bei,
 617                        BIER_SHOW_DETAIL);
 618         }
 619     }
 620     else
 621     {
 622         index_t bfmi;
 623
 624         bfmi = bier_table_fwd_lookup(bier_table_get(bti), bp);
 625
 626         if (INDEX_INVALID != bfmi)
 627         {
 628             s = format(s, "%U", format_bier_fmask, bfmi,
 629                        BIER_SHOW_DETAIL);
 630         }
 631     }
 632     return (s);
 633 }
 634
 635 u8 *
 636 format_bier_table (u8 *s, va_list *ap)
 637 {
 638     index_t bti = va_arg(*ap, index_t);
 639     bier_show_flags_t flags = va_arg(*ap, bier_show_flags_t);
 640     bier_table_t *bt;
 641
 642     if (pool_is_free_index(bier_table_pool, bti))
 643     {
 644         return (format(s, "No BIER f-mask %d", bti));
 645     }
 646
 647     bt = bier_table_get(bti);
 648
 649     s = format(s, "[@%d] bier-table:[%U local-label:%U]",
 650                bti,
 651                format_bier_table_id, &bt->bt_id,
 652                format_mpls_unicast_label, bt->bt_ll);
 653
 654     if (flags & BIER_SHOW_DETAIL)
 655     {
 656         s = format(s, " locks:%d", bt->bt_locks);
 657     }
 658     s = format(s, "]");
 659
 660     if (flags & BIER_SHOW_DETAIL)
 661     {
 662         if (bier_table_is_main(bt))
 663         {
 664             index_t *bei;
 665
 666             vec_foreach (bei, bt->bt_entries)
 667             {
 668                 if (INDEX_INVALID != *bei)
 669                 {
 670                     s = format(s, "\n%U", format_bier_entry, *bei, 2);
 671                 }
 672             }
 673         }
 674         else
 675         {
 676             u32 ii;
 677
 678             vec_foreach_index (ii, bt->bt_fmasks)
 679             {
 680                 if (INDEX_INVALID != bt->bt_fmasks[ii])
 681                 {
 682                     s = format(s, "\n bp:%d\n %U", ii,
 683                                format_bier_fmask, bt->bt_fmasks[ii], 2);
 684                 }
 685             }
 686         }
 687     }
 688
 689     return (s);
 690 }
 691
 692 void
 693 bier_table_show_all (vlib_main_t * vm,
 694                      bier_show_flags_t flags)
 695 {
 696     if (!pool_elts(bier_table_pool))
 697     {
 698         vlib_cli_output (vm, "No BIER tables");
 699     }
 700     else
 701     {
 702         int ii;
 703
 704         pool_foreach_index(ii, bier_table_pool,
 705         ({
 706             vlib_cli_output (vm, "%U", format_bier_table, ii, flags);
 707         }));
 708     }
 709 }
 710
 711 void
 712 bier_tables_walk (bier_tables_walk_fn_t fn,
 713                   void *ctx)
 714 {
 715     ASSERT(0);
 716 }
 717
 718
 719 void
 720 bier_table_walk (const bier_table_id_t *bti,
 721                  bier_table_walk_fn_t fn,
 722                  void *ctx)
 723 {
 724     bier_table_t *bt;
 725     bier_entry_t *be;
 726     index_t *bei;
 727
 728     bt = bier_table_find(bti);
 729
 730     if (NULL == bt)
 731     {
 732         return;
 733     }
 734
 735     vec_foreach (bei, bt->bt_entries)
 736     {
 737         if (INDEX_INVALID != *bei)
 738         {
 739             be = bier_entry_get(*bei);
 740
 741             fn(bt, be, ctx);
 742         }
 743     }
 744 }