src/plugins/unittest/bier_test.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
  17 #include <vnet/mpls/mpls.h>
  18 #include <vnet/bier/bier_table.h>
  19 #include <vnet/bier/bier_entry.h>
  20 #include <vnet/bier/bier_fmask.h>
  21 #include <vnet/bier/bier_bit_string.h>
  22 #include <vnet/bier/bier_imp.h>
  23 #include <vnet/bier/bier_disp_table.h>
  24 #include <vnet/bier/bier_disp_entry.h>
  25 #include <vnet/fib/fib_entry.h>
  26 #include <vnet/fib/fib_table.h>
  27 #include <vnet/fib/mpls_fib.h>
  28 #include <vnet/dpo/load_balance.h>
  29 #include <vnet/dpo/drop_dpo.h>
  30 #include <vnet/dpo/lookup_dpo.h>
  31 #include <vnet/mfib/mfib_table.h>
  32
  33 #include <vnet/fib/fib_test.h>
  34
  35 /*
  36  * Add debugs for passing tests
  37  */
  38 static int bier_test_do_debug;
  39
  40 #define BIER_TEST_I(_cond, _comment, _args...)                  \
  41 ({                                                              \
  42     int _evald = (_cond);                                       \
  43     if (!(_evald)) {                                            \
  44         fformat(stderr, "FAIL:%d: " _comment "\n",              \
  45                 __LINE__, ##_args);                             \
  46         res = 1;                                                \
  47     } else {                                                    \
  48         if (bier_test_do_debug)                                 \
  49             fformat(stderr, "PASS:%d: " _comment "\n",          \
  50                     __LINE__, ##_args);                         \
  51     }                                                           \
  52     res;                                                        \
  53 })
  54 #define BIER_TEST(_cond, _comment, _args...)                    \
  55 {                                                               \
  56     if (BIER_TEST_I(_cond, _comment, ##_args)) {                \
  57         return 1;                                               \
  58         ASSERT(!("FAIL: " _comment));                           \
  59     }                                                           \
  60 }
  61
  62 /**
  63  * A 'i'm not fussed is this is not efficient' store of test data
  64  */
  65 typedef struct test_main_t_ {
  66     /**
  67      * HW if indicies
  68      */
  69     u32 hw_if_indicies[4];
  70     /**
  71      * HW interfaces
  72      */
  73     vnet_hw_interface_t * hw[4];
  74
  75 } test_main_t;
  76 static test_main_t test_main;
  77
  78 /* fake ethernet device class, distinct from "fake-ethX" */
  79 static u8 * format_test_interface_name (u8 * s, va_list * args)
  80 {
  81   u32 dev_instance = va_arg (*args, u32);
  82   return format (s, "test-eth%d", dev_instance);
  83 }
  84
  85 static uword dummy_interface_tx (vlib_main_t * vm,
  86                                  vlib_node_runtime_t * node,
  87                                  vlib_frame_t * frame)
  88 {
  89   clib_warning ("you shouldn't be here, leaking buffers...");
  90   return frame->n_vectors;
  91 }
  92
  93 VNET_DEVICE_CLASS (test_interface_device_class,static) = {
  94   .name = "Test interface",
  95   .format_device_name = format_test_interface_name,
  96   .tx_function = dummy_interface_tx,
  97 };
  98
  99 static u8 *hw_address;
 100
 101 static int
 102 bier_test_mk_intf (u32 ninterfaces)
 103 {
 104     clib_error_t * error = NULL;
 105     test_main_t *tm = &test_main;
 106     u8 byte;
 107     int res;
 108     u32 i;
 109
 110     res = 0;
 111     ASSERT(ninterfaces <= ARRAY_LEN(tm->hw_if_indicies));
 112
 113     for (i=0; i<6; i++)
 114     {
 115         byte = 0xd0+i;
 116         vec_add1(hw_address, byte);
 117     }
 118
 119     for (i = 0; i < ninterfaces; i++)
 120     {
 121         hw_address[5] = i;
 122
 123         error = ethernet_register_interface(vnet_get_main(),
 124                                             test_interface_device_class.index,
 125                                             i /* instance */,
 126                                             hw_address,
 127                                             &tm->hw_if_indicies[i],
 128                                             /* flag change */ 0);
 129
 130         error = vnet_hw_interface_set_flags(vnet_get_main(),
 131                                             tm->hw_if_indicies[i],
 132                                             VNET_HW_INTERFACE_FLAG_LINK_UP);
 133         BIER_TEST((NULL == error), "ADD interface %d", i);
 134
 135         tm->hw[i] = vnet_get_hw_interface(vnet_get_main(),
 136                                           tm->hw_if_indicies[i]);
 137         vec_validate (ip4_main.fib_index_by_sw_if_index, tm->hw[i]->sw_if_index);
 138         vec_validate (ip6_main.fib_index_by_sw_if_index, tm->hw[i]->sw_if_index);
 139         ip4_main.fib_index_by_sw_if_index[tm->hw[i]->sw_if_index] = 0;
 140         ip6_main.fib_index_by_sw_if_index[tm->hw[i]->sw_if_index] = 0;
 141         error = vnet_sw_interface_set_flags(vnet_get_main(),
 142                                             tm->hw[i]->sw_if_index,
 143                                             VNET_SW_INTERFACE_FLAG_ADMIN_UP);
 144         BIER_TEST((NULL == error), "UP interface %d", i);
 145     }
 146     /*
 147      * re-eval after the inevitable realloc
 148      */
 149     for (i = 0; i < ninterfaces; i++)
 150     {
 151         tm->hw[i] = vnet_get_hw_interface(vnet_get_main(),
 152                                           tm->hw_if_indicies[i]);
 153     }
 154
 155     return (res);
 156 }
 157
 158 #define BIER_TEST_LB(_cond, _comment, _args...)                 \
 159 {                                                               \
 160     if (BIER_TEST_I(_cond, _comment, ##_args)) {                \
 161         return (1);                                             \
 162     }                                                           \
 163 }
 164
 165 static int
 166 bier_test_validate_entry (index_t bei,
 167                           int n_buckets,
 168                           ...)
 169 {
 170     dpo_id_t dpo = DPO_INVALID;
 171     const load_balance_t *lb;
 172     va_list ap;
 173     int res;
 174
 175     va_start(ap, n_buckets);
 176
 177     res = 0;
 178     bier_entry_contribute_forwarding(bei, &dpo);
 179
 180     res = BIER_TEST_I((DPO_LOAD_BALANCE == dpo.dpoi_type),
 181                       "Entry links to %U",
 182                       format_dpo_type, dpo.dpoi_type);
 183
 184     if (!res)
 185     {
 186         lb = load_balance_get(dpo.dpoi_index);
 187         res = fib_test_validate_lb_v(lb, n_buckets, &ap);
 188     }
 189
 190     dpo_reset(&dpo);
 191     va_end(ap);
 192
 193     return (res);
 194 }
 195
 196 static int
 197 bier_test_mpls_spf (void)
 198 {
 199     fib_node_index_t lfei, fei, bti;
 200     u32 mpls_fib_index;
 201     test_main_t *tm;
 202     int lb_count;
 203     int res;
 204
 205     res = 0;
 206     lb_count = pool_elts(load_balance_pool);
 207     tm = &test_main;
 208 #define N_BIER_ECMP_TABLES 16
 209     int ii;
 210
 211     /*
 212      * Add the BIER Main table
 213      */
 214     const bier_table_id_t bt_0_0_0_256 = {
 215         .bti_set = 0,
 216         .bti_sub_domain = 0,
 217         .bti_hdr_len = BIER_HDR_LEN_256,
 218         .bti_type = BIER_TABLE_MPLS_SPF,
 219         .bti_ecmp = BIER_ECMP_TABLE_ID_MAIN,
 220     };
 221
 222     bti = bier_table_add_or_lock(&bt_0_0_0_256, 1600);
 223
 224     fib_test_lb_bucket_t l_o_bt[N_BIER_ECMP_TABLES];
 225     bier_table_id_t bt_ecmp_0_0_0_256 = bt_0_0_0_256;
 226
 227     for (ii = 0; ii < N_BIER_ECMP_TABLES; ii++)
 228     {
 229         bt_ecmp_0_0_0_256.bti_ecmp = ii;
 230
 231         l_o_bt[ii].type = FT_LB_BIER_TABLE;
 232         l_o_bt[ii].bier.table =
 233             bier_table_ecmp_create_and_lock(&bt_ecmp_0_0_0_256);
 234     };
 235     const fib_prefix_t pfx_1600_neos = {
 236         .fp_len = 21,
 237         .fp_proto = FIB_PROTOCOL_MPLS,
 238         .fp_label = 1600,
 239         .fp_eos = MPLS_NON_EOS,
 240         .fp_payload_proto = DPO_PROTO_BIER,
 241     };
 242     const fib_prefix_t pfx_1600_eos = {
 243         .fp_len = 21,
 244         .fp_proto = FIB_PROTOCOL_MPLS,
 245         .fp_label = 1600,
 246         .fp_eos = MPLS_EOS,
 247         .fp_payload_proto = DPO_PROTO_BIER,
 248     };
 249
 250     mpls_fib_index = fib_table_find(FIB_PROTOCOL_MPLS,
 251                                     MPLS_FIB_DEFAULT_TABLE_ID);
 252
 253     lfei = fib_table_lookup(mpls_fib_index, &pfx_1600_neos);
 254     BIER_TEST(FIB_NODE_INDEX_INVALID == lfei, "1600/0 is not present");
 255
 256     lfei = fib_table_lookup(mpls_fib_index, &pfx_1600_eos);
 257     BIER_TEST(!fib_test_validate_entry(lfei, FIB_FORW_CHAIN_TYPE_MPLS_EOS,
 258                                        16,
 259                                        &l_o_bt[0],
 260                                        &l_o_bt[1],
 261                                        &l_o_bt[2],
 262                                        &l_o_bt[3],
 263                                        &l_o_bt[4],
 264                                        &l_o_bt[5],
 265                                        &l_o_bt[6],
 266                                        &l_o_bt[7],
 267                                        &l_o_bt[8],
 268                                        &l_o_bt[9],
 269                                        &l_o_bt[10],
 270                                        &l_o_bt[11],
 271                                        &l_o_bt[12],
 272                                        &l_o_bt[13],
 273                                        &l_o_bt[14],
 274                                        &l_o_bt[15]),
 275               "1600/1 LB stacks on BIER table %d", bti);
 276
 277     /*
 278      * modify the table's local label - keep the lock count accurate
 279      */
 280     const fib_prefix_t pfx_1601_eos = {
 281         .fp_len = 21,
 282         .fp_proto = FIB_PROTOCOL_MPLS,
 283         .fp_label = 1601,
 284         .fp_eos = MPLS_EOS,
 285         .fp_payload_proto = DPO_PROTO_BIER,
 286     };
 287     bti = bier_table_add_or_lock(&bt_0_0_0_256, 1601);
 288     bier_table_unlock(&bt_0_0_0_256);
 289
 290     lfei = fib_table_lookup(mpls_fib_index, &pfx_1600_eos);
 291     BIER_TEST(FIB_NODE_INDEX_INVALID == lfei, "1600/1 is deleted");
 292
 293     lfei = fib_table_lookup(mpls_fib_index, &pfx_1601_eos);
 294     BIER_TEST(!fib_test_validate_entry(lfei, FIB_FORW_CHAIN_TYPE_MPLS_EOS,
 295                                        16,
 296                                        &l_o_bt[0],
 297                                        &l_o_bt[1],
 298                                        &l_o_bt[2],
 299                                        &l_o_bt[3],
 300                                        &l_o_bt[4],
 301                                        &l_o_bt[5],
 302                                        &l_o_bt[6],
 303                                        &l_o_bt[7],
 304                                        &l_o_bt[8],
 305                                        &l_o_bt[9],
 306                                        &l_o_bt[10],
 307                                        &l_o_bt[11],
 308                                        &l_o_bt[12],
 309                                        &l_o_bt[13],
 310                                        &l_o_bt[14],
 311                                        &l_o_bt[15]),
 312               "1601/1 LB stacks on BIER table %d", bti);
 313
 314     /*
 315      * add a route to the table. the via IP route does not exist.
 316      */
 317     const ip46_address_t nh_1_1_1_1 = {
 318         .ip4 = {
 319             .as_u32 = clib_host_to_net_u32(0x01010101),
 320         },
 321     };
 322     fib_route_path_t *paths_1_1_1_1 = NULL, *input_paths_1_1_1_1;
 323     fib_route_path_t path_1_1_1_1 = {
 324         .frp_addr = nh_1_1_1_1,
 325         .frp_bier_fib_index = bti,
 326         .frp_sw_if_index = ~0,
 327     };
 328     fib_mpls_label_t fml_500 = {
 329         .fml_value = 500,
 330     };
 331     vec_add1(path_1_1_1_1.frp_label_stack, fml_500);
 332     vec_add1(paths_1_1_1_1, path_1_1_1_1);
 333     const fib_prefix_t pfx_1_1_1_1_s_32 = {
 334         .fp_addr = nh_1_1_1_1,
 335         .fp_len = 32,
 336         .fp_proto = FIB_PROTOCOL_IP4,
 337     };
 338     index_t bei_1;
 339
 340     input_paths_1_1_1_1 = vec_dup(paths_1_1_1_1);
 341     bier_table_route_path_add(&bt_0_0_0_256, 1, input_paths_1_1_1_1);
 342     bei_1 = bier_table_lookup(bier_table_get(bti), 1);
 343
 344     BIER_TEST((INDEX_INVALID != bei_1), "BP:1 present");
 345
 346     /*
 347      * the newly created fmask should stack on the non-eos chain
 348      * of the via-fib-entry
 349      */
 350     dpo_id_t neos_dpo_1_1_1_1 = DPO_INVALID;
 351     bier_fmask_t *bfm_1_1_1_1;
 352     index_t bfmi_1_1_1_1;
 353
 354     fei = fib_table_lookup_exact_match(0, &pfx_1_1_1_1_s_32);
 355     fib_entry_contribute_forwarding(fei,
 356                                     FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS,
 357                                     &neos_dpo_1_1_1_1);
 358
 359     bfmi_1_1_1_1 = bier_fmask_db_find(bti, &path_1_1_1_1);
 360     bfm_1_1_1_1 = bier_fmask_get(bfmi_1_1_1_1);
 361
 362     BIER_TEST(!dpo_cmp(drop_dpo_get(DPO_PROTO_MPLS),
 363                        &bfm_1_1_1_1->bfm_dpo),
 364               "Fmask via 1.1.1.1 stacks on MPLS drop");
 365
 366     /*
 367      * The BIER entry should stack on the forwarding chain of the fmask
 368      */
 369     const fib_test_lb_bucket_t dpo_o_bfm_1_1_1_1 = {
 370         .type = FT_LB_BIER_FMASK,
 371         .bier = {
 372             .fmask = bfmi_1_1_1_1,
 373         },
 374     };
 375     dpo_id_t dpo_bei = DPO_INVALID;
 376     bier_entry_contribute_forwarding(bei_1, &dpo_bei);
 377
 378     BIER_TEST(!dpo_cmp(&dpo_bei, drop_dpo_get(DPO_PROTO_BIER)),
 379               "BP:1 stacks on bier drop");
 380
 381     /*
 382      * give 1.1.1.1/32 a path and hence a interesting n-eos chain
 383      */
 384     ip46_address_t nh_10_10_10_1 = {
 385         .ip4 = {
 386             .as_u32 = clib_host_to_net_u32(0x0a0a0a01),
 387         },
 388     };
 389     adj_index_t ai_mpls_10_10_10_1;
 390     ai_mpls_10_10_10_1 = adj_nbr_add_or_lock(FIB_PROTOCOL_IP4,
 391                                              VNET_LINK_MPLS,
 392                                              &nh_10_10_10_1,
 393                                              tm->hw[0]->sw_if_index);
 394
 395     fib_test_lb_bucket_t bucket_neos_99_via_10_10_10_1 = {
 396         .type = FT_LB_LABEL_O_ADJ,
 397         .label_o_adj = {
 398             .label = 99,
 399             .eos = MPLS_NON_EOS,
 400             .adj = ai_mpls_10_10_10_1,
 401             .ttl = 255,
 402         },
 403     };
 404     fib_mpls_label_t *out_lbl_99 = NULL, fml_99 = {
 405         .fml_value = 99,
 406     };
 407     vec_add1(out_lbl_99, fml_99);
 408
 409     fei = fib_table_entry_update_one_path(0,
 410                                           &pfx_1_1_1_1_s_32,
 411                                           FIB_SOURCE_API,
 412                                           FIB_ENTRY_FLAG_NONE,
 413                                           DPO_PROTO_IP4,
 414                                           &nh_10_10_10_1,
 415                                           tm->hw[0]->sw_if_index,
 416                                           ~0, // invalid fib index
 417                                           1,
 418                                           out_lbl_99,
 419                                           FIB_ROUTE_PATH_FLAG_NONE);
 420     fib_entry_contribute_forwarding(fei,
 421                                     FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS,
 422                                     &neos_dpo_1_1_1_1);
 423     BIER_TEST(!fib_test_validate_lb(&neos_dpo_1_1_1_1, 1,
 424                                     &bucket_neos_99_via_10_10_10_1),
 425               "1.1.1.1/32 n-eos LB 1 buckets via: 99 + 10.10.10.1");
 426     BIER_TEST(!dpo_cmp(&neos_dpo_1_1_1_1,
 427                        &bfm_1_1_1_1->bfm_dpo),
 428               "Fmask via 1.1.1.1 stacks on updated non-eos of 1.1.1.1/32");
 429     bier_entry_contribute_forwarding(bei_1, &dpo_bei);
 430     BIER_TEST((dpo_bei.dpoi_index == bfmi_1_1_1_1),
 431               "BP:1  stacks on fmask 1.1.1.1");
 432
 433     /*
 434      * add another path to the via entry.
 435      * this makes the via-entry instantiate a new load-balance with
 436      * 2 buckets. and the back-walk to the BIER entry will need to
 437      * re-stack on it.
 438      */
 439     ip46_address_t nh_10_10_10_2 = {
 440         .ip4 = {
 441             .as_u32 = clib_host_to_net_u32(0x0a0a0a02),
 442         },
 443     };
 444     adj_index_t ai_mpls_10_10_10_2;
 445
 446     ai_mpls_10_10_10_2 = adj_nbr_add_or_lock(FIB_PROTOCOL_IP4,
 447                                              VNET_LINK_MPLS,
 448                                              &nh_10_10_10_2,
 449                                              tm->hw[0]->sw_if_index);
 450
 451     fib_test_lb_bucket_t bucket_neos_100_via_10_10_10_2 = {
 452         .type = FT_LB_LABEL_O_ADJ,
 453         .label_o_adj = {
 454             .label = 100,
 455             .eos = MPLS_NON_EOS,
 456             .adj = ai_mpls_10_10_10_2,
 457             .ttl = 255,
 458         },
 459     };
 460     fib_mpls_label_t *out_lbl_100 = NULL, fml_100 = {
 461         .fml_value = 100,
 462     };
 463     vec_add1(out_lbl_100, fml_100);
 464
 465     fei = fib_table_entry_path_add(0,
 466                                    &pfx_1_1_1_1_s_32,
 467                                    FIB_SOURCE_API,
 468                                    FIB_ENTRY_FLAG_NONE,
 469                                    DPO_PROTO_IP4,
 470                                    &nh_10_10_10_2,
 471                                    tm->hw[0]->sw_if_index,
 472                                    ~0, // invalid fib index
 473                                    1,
 474                                    out_lbl_100,
 475                                    FIB_ROUTE_PATH_FLAG_NONE);
 476
 477     fib_entry_contribute_forwarding(fei,
 478                                     FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS,
 479                                     &neos_dpo_1_1_1_1);
 480     BIER_TEST(!fib_test_validate_lb(&neos_dpo_1_1_1_1, 2,
 481                                     &bucket_neos_99_via_10_10_10_1,
 482                                     &bucket_neos_100_via_10_10_10_2),
 483               "1.1.1.1/32 n-eos LB 2 buckets "
 484               "via: 99 + 10.10.10.1, "
 485               "via: 100 + 10.10.10.2");
 486     BIER_TEST(!dpo_cmp(&neos_dpo_1_1_1_1,
 487                        &bfm_1_1_1_1->bfm_dpo),
 488               "Fmask via 1.1.1.1 stacks on updated non-eos of 1.1.1.1/32");
 489
 490     /*
 491      * add another bier bit-position via the same next-hop
 492      * since its the same next hop, the two bit-positions should link
 493      * to the same fmask
 494      */
 495     index_t bei_2;
 496
 497     input_paths_1_1_1_1 = vec_dup(paths_1_1_1_1);
 498     bier_table_route_path_add(&bt_0_0_0_256, 2, input_paths_1_1_1_1);
 499     bei_2 = bier_table_lookup(bier_table_get(bti), 2);
 500
 501     bier_entry_contribute_forwarding(bei_2, &dpo_bei);
 502     BIER_TEST((dpo_bei.dpoi_index == bfmi_1_1_1_1),
 503               "BP:2  stacks on fmask 1.1.1.1");
 504
 505     /*
 506      * now add a bit-position via a different next hop and expect to
 507      * link via a different fmask
 508      */
 509     const ip46_address_t nh_1_1_1_2 = {
 510         .ip4 = {
 511             .as_u32 = clib_host_to_net_u32(0x01010102),
 512         },
 513     };
 514     const fib_prefix_t pfx_1_1_1_2_s_32 = {
 515         .fp_addr = nh_1_1_1_2,
 516         .fp_len = 32,
 517         .fp_proto = FIB_PROTOCOL_IP4,
 518     };
 519     fib_route_path_t *paths_1_1_1_2 = NULL, *input_paths_1_1_1_2, path_1_1_1_2 = {
 520         .frp_addr = nh_1_1_1_2,
 521         .frp_bier_fib_index = bti,
 522         .frp_sw_if_index = ~0,
 523     };
 524     fib_mpls_label_t fml_501 = {
 525         .fml_value = 501,
 526     };
 527     vec_add1(path_1_1_1_2.frp_label_stack, fml_501);
 528     vec_add1(paths_1_1_1_2, path_1_1_1_2);
 529     input_paths_1_1_1_2 = vec_dup(paths_1_1_1_2);
 530     index_t bei_3;
 531
 532     fib_mpls_label_t *out_lbl_101 = NULL, fml_101 = {
 533         .fml_value = 101,
 534     };
 535     vec_add1(out_lbl_101, fml_101);
 536     fei = fib_table_entry_path_add(0,
 537                                    &pfx_1_1_1_2_s_32,
 538                                    FIB_SOURCE_API,
 539                                    FIB_ENTRY_FLAG_NONE,
 540                                    DPO_PROTO_IP4,
 541                                    &nh_10_10_10_2,
 542                                    tm->hw[0]->sw_if_index,
 543                                    ~0, // invalid fib index
 544                                    1,
 545                                    out_lbl_101,
 546                                    FIB_ROUTE_PATH_FLAG_NONE);
 547     bier_table_route_path_update(&bt_0_0_0_256, 3, input_paths_1_1_1_2);
 548     bei_3 = bier_table_lookup(bier_table_get(bti), 3);
 549
 550     BIER_TEST((INDEX_INVALID != bei_3), "BP:3 present");
 551
 552     /*
 553      * the newly created fmask should stack on the non-eos chain
 554      * of the via-fib-entry
 555      */
 556     dpo_id_t neos_dpo_1_1_1_2 = DPO_INVALID;
 557     bier_fmask_t *bfm_1_1_1_2;
 558     index_t bfmi_1_1_1_2;
 559
 560     fei = fib_table_lookup_exact_match(0, &pfx_1_1_1_2_s_32);
 561     fib_entry_contribute_forwarding(fei,
 562                                     FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS,
 563                                     &neos_dpo_1_1_1_2);
 564
 565     bfmi_1_1_1_2 = bier_fmask_db_find(bti, &path_1_1_1_2);
 566     bfm_1_1_1_2 = bier_fmask_get(bfmi_1_1_1_2);
 567
 568     BIER_TEST(!dpo_cmp(&neos_dpo_1_1_1_2,
 569                        &bfm_1_1_1_2->bfm_dpo),
 570               "Fmask via 1.1.1.2 stacks on non-eos of 1.1.1.2/32");
 571
 572     /*
 573      * The BIER entry should stack on the forwarding chain of the fmask
 574      */
 575     const fib_test_lb_bucket_t dpo_o_bfm_1_1_1_2 = {
 576         .type = FT_LB_BIER_FMASK,
 577         .bier = {
 578             .fmask = bfmi_1_1_1_2,
 579         },
 580     };
 581     bier_entry_contribute_forwarding(bei_3, &dpo_bei);
 582     BIER_TEST((dpo_bei.dpoi_index == bfmi_1_1_1_2),
 583               "BP:2 stacks on fmask 1.1.1.2");
 584
 585     /*
 586      * Load-balance BP:3 over both next-hops
 587      */
 588     paths_1_1_1_1[0] = path_1_1_1_1;
 589     input_paths_1_1_1_1 = vec_dup(paths_1_1_1_1);
 590     bier_table_route_path_add(&bt_0_0_0_256, 3, input_paths_1_1_1_1);
 591
 592     BIER_TEST(!bier_test_validate_entry(bei_3, 2,
 593                                         &dpo_o_bfm_1_1_1_1,
 594                                         &dpo_o_bfm_1_1_1_2),
 595               "BP:3 stacks on fmask 1.1.1.2 & 1.1.1.1");
 596
 597     /*
 598      * test that the ECMP choices for BP:3 have been spread over the
 599      * ECMP tables
 600      */
 601     BIER_TEST((bier_table_fwd_lookup(bier_table_get(l_o_bt[0].bier.table), 3) ==
 602                bfmi_1_1_1_1),
 603               "fwd lookup for BP:3 ECMP:0 is 1.1.1.1");
 604     BIER_TEST((bier_table_fwd_lookup(bier_table_get(l_o_bt[1].bier.table), 3) ==
 605                bfmi_1_1_1_2),
 606               "fwd lookup for BP:3 ECMP:1 is 1.1.1.2");
 607
 608     /*
 609      * Withdraw one of the via FIB and thus bring down the fmask
 610      * expect the bier-entry forwarding to remove this from the set
 611      */
 612     fib_table_entry_delete(0, &pfx_1_1_1_2_s_32, FIB_SOURCE_API);
 613
 614     bier_entry_contribute_forwarding(bei_3, &dpo_bei);
 615     BIER_TEST((dpo_bei.dpoi_index == bfmi_1_1_1_1),
 616               "BP:3 stacks on fmask 1.1.1.1");
 617
 618     BIER_TEST((bier_table_fwd_lookup(bier_table_get(l_o_bt[0].bier.table), 3) ==
 619                bfmi_1_1_1_1),
 620               "fwd lookup for BP:3 ECMP:0 is 1.1.1.1");
 621     BIER_TEST((bier_table_fwd_lookup(bier_table_get(l_o_bt[1].bier.table), 3) ==
 622                bfmi_1_1_1_1),
 623               "fwd lookup for BP:3 ECMP:1 is 1.1.1.1");
 624
 625     /*
 626      * add the via back
 627      */
 628     out_lbl_101 = NULL;
 629     vec_add1(out_lbl_101, fml_101);
 630     fei = fib_table_entry_path_add(0,
 631                                    &pfx_1_1_1_2_s_32,
 632                                    FIB_SOURCE_API,
 633                                    FIB_ENTRY_FLAG_NONE,
 634                                    DPO_PROTO_IP4,
 635                                    &nh_10_10_10_2,
 636                                    tm->hw[0]->sw_if_index,
 637                                    ~0, // invalid fib index
 638                                    1,
 639                                    out_lbl_101,
 640                                    FIB_ROUTE_PATH_FLAG_NONE);
 641     /* suspend so the update walk kicks int */
 642     vlib_process_suspend(vlib_get_main(), 1e-5);
 643
 644     BIER_TEST(!bier_test_validate_entry(bei_3, 2,
 645                                         &dpo_o_bfm_1_1_1_1,
 646                                         &dpo_o_bfm_1_1_1_2),
 647               "BP:3 stacks on fmask 1.1.1.2 & 1.1.1.1");
 648     BIER_TEST((bier_table_fwd_lookup(bier_table_get(l_o_bt[0].bier.table), 3) ==
 649                bfmi_1_1_1_1),
 650               "fwd lookup for BP:3 ECMP:0 is 1.1.1.1");
 651     BIER_TEST((bier_table_fwd_lookup(bier_table_get(l_o_bt[1].bier.table), 3) ==
 652                bfmi_1_1_1_2),
 653               "fwd lookup for BP:3 ECMP:1 is 1.1.1.2");
 654
 655     /*
 656      * remove the original 1.1.1.2 fmask from BP:3
 657      */
 658     input_paths_1_1_1_2 = vec_dup(paths_1_1_1_2);
 659     bier_table_route_path_remove(&bt_0_0_0_256, 3, input_paths_1_1_1_2);
 660     bier_entry_contribute_forwarding(bei_3, &dpo_bei);
 661     BIER_TEST((dpo_bei.dpoi_index == bfmi_1_1_1_1),
 662               "BP:3 stacks on fmask 1.1.1.1");
 663
 664     /*
 665      * test that the ECMP choices for BP:3 have been updated
 666      */
 667     BIER_TEST((bier_table_fwd_lookup(bier_table_get(l_o_bt[0].bier.table), 3) ==
 668                bfmi_1_1_1_1),
 669               "fwd lookup for BP:3 ECMP:0 is 1.1.1.1");
 670     BIER_TEST((bier_table_fwd_lookup(bier_table_get(l_o_bt[1].bier.table), 3) ==
 671                bfmi_1_1_1_1),
 672               "fwd lookup for BP:3 ECMP:1 is 1.1.1.1");
 673
 674     /*
 675      * remove the routes added
 676      */
 677     input_paths_1_1_1_1 = vec_dup(paths_1_1_1_1);
 678     bier_table_route_path_remove(&bt_0_0_0_256, 2, input_paths_1_1_1_1);
 679     input_paths_1_1_1_2 = vec_dup(paths_1_1_1_2);
 680     bier_table_route_path_remove(&bt_0_0_0_256, 3, input_paths_1_1_1_2);
 681     input_paths_1_1_1_1 = vec_dup(paths_1_1_1_1);
 682     bier_table_route_path_remove(&bt_0_0_0_256, 3, input_paths_1_1_1_1);
 683
 684     bier_table_route_delete(&bt_0_0_0_256, 1);
 685
 686     /*
 687      * delete the table
 688      */
 689     bier_table_unlock(&bt_0_0_0_256);
 690
 691     /*
 692      * test resources are freed
 693      */
 694     dpo_reset(&dpo_bei);
 695     for (ii = 0; ii < N_BIER_ECMP_TABLES; ii++)
 696     {
 697         bier_table_ecmp_unlock(l_o_bt[ii].bier.table);
 698     };
 699     BIER_TEST(0 == pool_elts(bier_table_pool), "BIER table pool empty");
 700     BIER_TEST(0 == pool_elts(bier_fmask_pool), "BIER fmask pool empty");
 701     BIER_TEST(0 == pool_elts(bier_entry_pool), "BIER entry pool empty");
 702
 703     adj_unlock(ai_mpls_10_10_10_1);
 704     adj_unlock(ai_mpls_10_10_10_2);
 705     dpo_reset(&neos_dpo_1_1_1_1);
 706     dpo_reset(&neos_dpo_1_1_1_2);
 707     fib_table_entry_delete(0, &pfx_1_1_1_1_s_32, FIB_SOURCE_API);
 708     fib_table_entry_delete(0, &pfx_1_1_1_2_s_32, FIB_SOURCE_API);
 709
 710     /* +1 to account for the one time alloc'd drop LB in the MPLS fibs */
 711     BIER_TEST(lb_count+1 == pool_elts(load_balance_pool),
 712               "Load-balance resources freed ");
 713     BIER_TEST((0 == adj_nbr_db_size()), "ADJ DB size is %d",
 714              adj_nbr_db_size());
 715
 716     vec_free(paths_1_1_1_1);
 717     vec_free(paths_1_1_1_2);
 718     vec_free(input_paths_1_1_1_1);
 719     vec_free(input_paths_1_1_1_2);
 720
 721     return (0);
 722 }
 723
 724 static int
 725 bier_test_mpls_imp (void)
 726 {
 727     fib_node_index_t bii;
 728     int res;
 729
 730     /*
 731      * Add the BIER Main table
 732      */
 733     const bier_table_id_t bt_0_0_0_256 = {
 734         .bti_set = 0,
 735         .bti_sub_domain = 0,
 736         .bti_hdr_len = BIER_HDR_LEN_256,
 737         .bti_type = BIER_TABLE_MPLS_SPF,
 738         .bti_ecmp = BIER_ECMP_TABLE_ID_MAIN,
 739     };
 740
 741     bier_table_add_or_lock(&bt_0_0_0_256, 1600);
 742
 743     /*
 744      * A bit-string for imp 1.
 745      */
 746     bier_bit_string_t bbs_256;
 747     u8 buckets[BIER_HDR_BUCKETS_256];
 748     clib_memset(buckets, 0x5, BIER_HDR_BUCKETS_256);
 749
 750     res = 0;
 751     bier_bit_string_init(&bbs_256, BIER_HDR_LEN_256, buckets);
 752
 753     bii = bier_imp_add_or_lock(&bt_0_0_0_256, 1, &bbs_256);
 754
 755     /*
 756      * An mfib entry that resolves via the BIER imposition
 757      */
 758     const mfib_prefix_t pfx_1_1_1_1_c_239_1_1_1 = {
 759         .fp_len = 64,
 760         .fp_proto = FIB_PROTOCOL_IP4,
 761         .fp_grp_addr = {
 762             .ip4.as_u32 = clib_host_to_net_u32(0xef010101),
 763         },
 764         .fp_src_addr = {
 765             .ip4.as_u32 = clib_host_to_net_u32(0x01010101),
 766         },
 767     };
 768     fib_route_path_t path_via_bier_imp_1 = {
 769         .frp_proto = DPO_PROTO_BIER,
 770         .frp_bier_imp = bii,
 771         .frp_weight = 0,
 772         .frp_flags = FIB_ROUTE_PATH_BIER_IMP,
 773     };
 774     mfib_table_entry_path_update(0, // default table
 775                                  &pfx_1_1_1_1_c_239_1_1_1 ,
 776                                  MFIB_SOURCE_API,
 777                                  &path_via_bier_imp_1,
 778                                  MFIB_ITF_FLAG_FORWARD);
 779     mfib_table_entry_delete(0,
 780                             &pfx_1_1_1_1_c_239_1_1_1 ,
 781                             MFIB_SOURCE_API);
 782
 783     bier_imp_unlock(bii);
 784     bier_table_unlock(&bt_0_0_0_256);
 785
 786     BIER_TEST(0 == pool_elts(bier_imp_pool),
 787               "BIER imposition resources freed ");
 788     BIER_TEST(0 == pool_elts(bier_table_pool),
 789               "BIER table resources freed ");
 790
 791     return (0);
 792 }
 793
 794 static int
 795 bier_test_mpls_disp (void)
 796 {
 797     /*
 798      * Add the BIER Main table
 799      */
 800     const bier_table_id_t bt_0_0_0_256 = {
 801         .bti_set = 0,
 802         .bti_sub_domain = 0,
 803         .bti_hdr_len = BIER_HDR_LEN_256,
 804         .bti_type = BIER_TABLE_MPLS_SPF,
 805         .bti_ecmp = BIER_ECMP_TABLE_ID_MAIN,
 806     };
 807     index_t bti;
 808     int res;
 809
 810     res = 0;
 811     bti = bier_table_add_or_lock(&bt_0_0_0_256, 1600);
 812
 813     /*
 814      * Add a BIER disposition table
 815      */
 816     const u32 bier_disp_tbl_id = 1;
 817     index_t bdti1;
 818
 819     bdti1 = bier_disp_table_add_or_lock(bier_disp_tbl_id);
 820
 821     /*
 822      * add a bit-position in the table that resolves via
 823      * DISP table, i.e. a for-us bit-position
 824      */
 825     fib_route_path_t *paths_via_disp = NULL, path_via_disp = {
 826         // .frp_addr = all-zeros
 827         .frp_proto = DPO_PROTO_BIER,
 828         .frp_bier_fib_index = bdti1,
 829         .frp_sw_if_index = ~0,
 830     };
 831     vec_add1(paths_via_disp, path_via_disp);
 832
 833     bier_table_route_path_add(&bt_0_0_0_256, 3, paths_via_disp);
 834
 835     /*
 836      * the fmask should stack on the BIER disp table
 837      */
 838     bier_fmask_t *bfm_0_0_0_0;
 839     index_t bfmi_0_0_0_0;
 840     dpo_id_t dpo_disp_tbl_1 = DPO_INVALID;
 841
 842     bier_disp_table_contribute_forwarding(bdti1, &dpo_disp_tbl_1);
 843
 844     bfmi_0_0_0_0 = bier_fmask_db_find(bti, &path_via_disp);
 845     bfm_0_0_0_0 = bier_fmask_get(bfmi_0_0_0_0);
 846
 847     BIER_TEST(!dpo_cmp(&dpo_disp_tbl_1, &bfm_0_0_0_0->bfm_dpo),
 848               "Fmask via 0.0.0.0 stacks on BIER disp table 1");
 849
 850     /*
 851      * and a deag entry into the disposition table
 852      */
 853     fib_route_path_t *rpaths = NULL, path_via_mfib = {
 854         .frp_proto = DPO_PROTO_IP4,
 855         .frp_addr = zero_addr,
 856         .frp_fib_index = 0, // default MFIB table
 857         .frp_rpf_id = 9, // some non-zero value
 858         .frp_flags = FIB_ROUTE_PATH_RPF_ID,
 859     };
 860     bier_hdr_src_id_t src = 99;
 861     vec_add1(rpaths, path_via_mfib);
 862     bier_disp_table_entry_path_add(bier_disp_tbl_id, src,
 863                                    BIER_HDR_PROTO_IPV4, rpaths);
 864
 865     /* which should stack on a lookup in the mfib table */
 866     const dpo_id_t *dpo_disp_entry_v4;
 867     bier_disp_entry_t *bde_99;
 868     index_t bdei;
 869
 870     bdei = bier_disp_table_lookup(bdti1, clib_host_to_net_u16(src));
 871     bde_99 = bier_disp_entry_get(bdei);
 872     dpo_disp_entry_v4 = &bde_99->bde_fwd[BIER_HDR_PROTO_IPV4].bde_dpo;
 873
 874     lookup_dpo_t *lkd = lookup_dpo_get(dpo_disp_entry_v4->dpoi_index);
 875
 876     BIER_TEST((bdti1 == lkd->lkd_fib_index),
 877               "disp is deag in %d %U",
 878               lkd->lkd_fib_index,
 879               format_dpo_id, dpo_disp_entry_v4, 0);
 880     BIER_TEST((LOOKUP_INPUT_DST_ADDR == lkd->lkd_input),
 881               "disp is destination deag in %d %U",
 882               lkd->lkd_input,
 883               format_dpo_id, dpo_disp_entry_v4, 0);
 884     BIER_TEST((LOOKUP_MULTICAST == lkd->lkd_cast),
 885               "disp is multicast deag in %d %U",
 886               lkd->lkd_input,
 887               format_dpo_id, dpo_disp_entry_v4, 0);
 888
 889     /*
 890      * cleanup
 891      */
 892     dpo_reset(&dpo_disp_tbl_1);
 893
 894     bier_disp_table_entry_path_remove(bier_disp_tbl_id, src,
 895                                       BIER_HDR_PROTO_IPV4, rpaths);
 896     bier_table_route_path_remove(&bt_0_0_0_256, 3, paths_via_disp);
 897
 898     bier_disp_table_unlock_w_table_id(bier_disp_tbl_id);
 899
 900     bier_table_unlock(&bt_0_0_0_256);
 901
 902     BIER_TEST(0 == pool_elts(bier_fmask_pool),
 903               "BIER fmask resources freed ");
 904     BIER_TEST(0 == pool_elts(bier_table_pool),
 905               "BIER table resources freed ");
 906     BIER_TEST(0 == pool_elts(bier_disp_table_pool),
 907               "BIER Disposition table resources freed ");
 908     BIER_TEST(0 == pool_elts(bier_disp_entry_pool),
 909               "BIER Disposition entry resources freed ");
 910
 911     vec_free(paths_via_disp);
 912     return (0);
 913 }
 914
 915 static clib_error_t *
 916 bier_test (vlib_main_t * vm,
 917            unformat_input_t * input,
 918            vlib_cli_command_t * cmd_arg)
 919 {
 920     int res = 0;
 921
 922     res += bier_test_mk_intf(4);
 923
 924     if (unformat (input, "debug"))
 925     {
 926         bier_test_do_debug = 1;
 927     }
 928
 929     if (unformat (input, "mid"))
 930         res += bier_test_mpls_spf();
 931     else if (unformat (input, "head"))
 932         res += bier_test_mpls_imp();
 933     else if (unformat (input, "tail"))
 934         res += bier_test_mpls_disp();
 935     else
 936     {
 937         res += bier_test_mpls_spf();
 938         res += bier_test_mpls_imp();
 939         res += bier_test_mpls_disp();
 940     }
 941
 942     if (res)
 943     {
 944         return clib_error_return(0, "BIER Unit Test Failed");
 945     }
 946     else
 947     {
 948         return (NULL);
 949     }
 950 }
 951
 952 VLIB_CLI_COMMAND (test_route_command, static) = {
 953     .path = "test bier",
 954     .short_help = "bier unit tests",
 955     .function = bier_test,
 956 };
 957
 958 clib_error_t *
 959 bier_test_init (vlib_main_t *vm)
 960 {
 961     return 0;
 962 }
 963
 964 VLIB_INIT_FUNCTION (bier_test_init);