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