aboutsummaryrefslogtreecommitdiffstats
path: root/resources/tools/presentation/fdio.svg
blob: 32dd070d3660c4e4d644cae5107eb90863ae63d5 (plain) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">
<svg xmlns="http://www.w3.org/2000/svg" xml:space="preserve" width="630px" height="394px" version="1.1" style="shape-rendering:geometricPrecision; text-rendering:geometricPrecision; image-rendering:optimizeQuality; fill-rule:evenodd; clip-rule:evenodd"
viewBox="0 0 94500000 59062500"
 xmlns:xlink="http://www.w3.org/1999/xlink">
 <defs>
  <style type="text/css">
   <![CDATA[
    .fil2 {fill:#3C4641}
    .fil1 {fill:#3E4742}
    .fil0 {fill:#ED3341}
   ]]>
  </style>
 </defs>
 <g id="Layer_x0020_1">
  <path class="fil0" d="M42892251 15970973c234833,2555989 1402971,3784607 3633525,3195163 64614,-17483 464586,-605509 524121,-613778 100406,-13939 -325789,592397 -234951,589562 663981,-21026 1166839,235659 2703054,-1575788 -125567,2507794 385088,1931698 753047,3733577 -1039736,2409632 -1745415,307125 -1486485,4471622 -4668654,-2126 -6967721,-648979 -9839813,2159679 -1571417,1536924 -3134683,5759184 -3805515,8365022 -725760,124740 -1467939,37800 -1887401,510536 -484194,545619 -431747,1408050 35674,1833418 379890,345516 987289,308424 1519678,355793 800769,71348 1142151,473327 1136244,1236651 -6615,848964 -451001,1192826 -1631306,1191054 -3702746,-5316 -8320961,16538 -11713866,45596 -1026624,8741 -1698992,464822 -1746714,1344971 -50676,931416 521640,1260039 1499833,1295831 4286993,156988 8304069,-117653 12887201,141041 783996,103714 1189755,583183 1168256,1106004 -35201,855461 -707923,1099626 -1411594,1145104 -5730598,370440 -13969581,-91665 -19611231,141278 -797344,32839 -1694621,179786 -1702890,1222476 -6615,840459 589798,1177943 1399899,1281538 2377738,7088 5327556,1418 7519956,1890 2596151,591 5192775,4134 7788926,-118l-1007843 3222096 9601909 24334 3086606 -8484328c2943911,-111628 4325029,-862076 6023666,-2197361 944528,-742534 2909773,-3271590 3377903,-4985466l-6699578 -78081 1196016 -3619114c2873627,-19727 7980761,562984 10127447,-748913 1534089,-937440 4106970,-3980458 4422954,-6498411 -1731358,-38863 -8963443,287753 -9479649,-290469 -811991,-1588073 1028633,-2402426 1978121,-3132911 1388678,-1068441 1793846,-1560904 1785578,-3760746 230108,313386 87413,679809 294368,826048 502740,355320 1446913,224319 3038411,773010 1055447,363943 2115855,607399 3274661,404696 606218,-105958 570662,-121196 999692,-407413 -87767,-924683 -247472,-1025089 -709813,-1469003 1446086,654176 966617,1888937 966499,3676168 0,1623983 504512,3115429 -2599,4527259 -1397891,3892219 -3372351,4768234 -4125752,6086745l4834856 25043 -4320540 12061626c-2523504,20318 -10295893,-341499 -12094937,331459 -2551264,954568 -5105126,4809341 -5427844,6962878 3747398,-8151 17429226,243219 20078179,-244755 5769579,-1062534 6837902,-6323231 8783066,-11759344 1441716,-4029244 5291646,-11853371 -1699464,-14191183 -1193535,-382253 -1853145,-295667 -2077228,-395955 -216523,-96863 4489,-368078 -1209600,-1404861 -1196488,-1140379 -417690,-2367934 118716,-3662820 1265001,-3005691 3370461,-2733058 3370343,-6944096 -236,-4388934 2680611,-3141771 3022583,-4763627 307479,-1458135 -1345326,-645317 -2307336,-1215388 -794273,-470610 -170809,-694693 -1801524,-842940l-178251 -1084151c-406114,246999 -713003,925509 -824631,912870 -159705,-18191 -35083,-801478 -213216,-759780 -33075,7796 -73828,19845 -123323,42643 -162068,75009 -368668,285036 -609053,585900 -1161759,1454355 -3112358,5035433 -4642076,5789779 -3004746,1481878 -5309719,91074 -10962709,3162206 -2587056,1405451 -4703383,1914216 -7362259,348233z"/>
  <path class="fil1" d="M81444116 48006591c-917831,-4596598 5486670,-5710989 6489669,-1741753 1221649,4834502 -5678387,5805017 -6489669,1741753zm1873463 -5811986c-6608858,1801052 -4202297,11851718 2867130,10021253 6433324,-1665681 4111577,-11922947 -2867130,-10021253z"/>
  <polygon class="fil2" points="76840667,42255321 75263698,42301508 75172978,52072571 76944144,52066547 "/>
  <path class="fil1" d="M70635206 52314137c1084388,307834 2141370,-714302 1520859,-1977413 -474863,-966853 -2784797,-983627 -2488776,930589 89421,578931 388041,882158 967916,1046824z"/>
  <path class="fil1" d="M76175978 40542272c695402,-45006 1114037,-372448 1062889,-1137426 -18309,-275349 -120251,-539595 -294013,-710876 -609761,-601611 -1840151,-411548 -1952016,509001 -111628,919485 435173,1387733 1183140,1339301z"/>
  <path class="fil0" d="M14086524 36346354l15995897 0c719972,0 1308943,589089 1308943,1308943l0 0c0,719854 -589089,1308943 -1308943,1308943l-15995897 0c-719736,0 -1308943,-588971 -1308943,-1308943l0 0c0,-719972 589089,-1308943 1308943,-1308943z"/>
  <path class="fil0" d="M20652975 31242173l13718919 0c719972,0 1308943,589326 1308943,1308943l0 118c0,719618 -589208,1308943 -1308943,1308943l-13718919 0c-719736,0 -1308943,-588971 -1308943,-1308943l0 -118c0,-719972 588971,-1308943 1308943,-1308943z"/>
  <path class="fil0" d="M6885624 46609763l3154410 0c719972,0 1308943,589208 1308943,1308943l0 0c0,719736 -589326,1308943 -1308943,1308943l-3154410 0c-719736,0 -1308943,-588971 -1308943,-1308943l0 0c0,-719972 588971,-1308943 1308943,-1308943z"/>
 </g>
</svg>
id='n686' href='#n686'>686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 
/*
 * Copyright (c) 2016 Cisco and/or its affiliates.
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at:
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */


#include <vnet/mpls/mpls.h>
#include <vnet/bier/bier_table.h>
#include <vnet/bier/bier_entry.h>
#include <vnet/bier/bier_fmask.h>
#include <vnet/bier/bier_bit_string.h>
#include <vnet/bier/bier_imp.h>
#include <vnet/bier/bier_disp_table.h>
#include <vnet/bier/bier_disp_entry.h>
#include <vnet/fib/fib_entry.h>
#include <vnet/fib/fib_table.h>
#include <vnet/fib/mpls_fib.h>
#include <vnet/dpo/load_balance.h>
#include <vnet/dpo/drop_dpo.h>
#include <vnet/dpo/lookup_dpo.h>
#include <vnet/mfib/mfib_table.h>

#include <vnet/fib/fib_test.h>

/*
 * Add debugs for passing tests
 */
static int bier_test_do_debug;

#define BIER_TEST_I(_cond, _comment, _args...)			\
({								\
    int _evald = (_cond);					\
    if (!(_evald)) {						\
        fformat(stderr, "FAIL:%d: " _comment "\n",		\
                __LINE__, ##_args);				\
        res = 1;                                                \
    } else {							\
        if (bier_test_do_debug)                                 \
            fformat(stderr, "PASS:%d: " _comment "\n",          \
                    __LINE__, ##_args);				\
    }								\
    res;							\
})
#define BIER_TEST(_cond, _comment, _args...)			\
{								\
    if (BIER_TEST_I(_cond, _comment, ##_args)) {		\
        return 1;                                               \
        ASSERT(!("FAIL: " _comment));				\
    }								\
}

/**
 * A 'i'm not fussed is this is not efficient' store of test data
 */
typedef struct test_main_t_ {
    /**
     * HW if indicies
     */
    u32 hw_if_indicies[4];
    /**
     * HW interfaces
     */
    vnet_hw_interface_t * hw[4];

} test_main_t;
static test_main_t test_main;

/* fake ethernet device class, distinct from "fake-ethX" */
static u8 * format_test_interface_name (u8 * s, va_list * args)
{
  u32 dev_instance = va_arg (*args, u32);
  return format (s, "test-eth%d", dev_instance);
}

static uword dummy_interface_tx (vlib_main_t * vm,
                                 vlib_node_runtime_t * node,
                                 vlib_frame_t * frame)
{
  clib_warning ("you shouldn't be here, leaking buffers...");
  return frame->n_vectors;
}

VNET_DEVICE_CLASS (test_interface_device_class,static) = {
  .name = "Test interface",
  .format_device_name = format_test_interface_name,
  .tx_function = dummy_interface_tx,
};

static u8 *hw_address;

static int
bier_test_mk_intf (u32 ninterfaces)
{
    clib_error_t * error = NULL;
    test_main_t *tm = &test_main;
    u8 byte;
    int res;
    u32 i;

    res = 0;
    ASSERT(ninterfaces <= ARRAY_LEN(tm->hw_if_indicies));

    for (i=0; i<6; i++)
    {
        byte = 0xd0+i;
        vec_add1(hw_address, byte);
    }

    for (i = 0; i < ninterfaces; i++)
    {
        hw_address[5] = i;

        error = ethernet_register_interface(vnet_get_main(),
                                            test_interface_device_class.index,
                                            i /* instance */,
                                            hw_address,
                                            &tm->hw_if_indicies[i],
                                            /* flag change */ 0);

        error = vnet_hw_interface_set_flags(vnet_get_main(),
                                            tm->hw_if_indicies[i],
                                            VNET_HW_INTERFACE_FLAG_LINK_UP);
        BIER_TEST((NULL == error), "ADD interface %d", i);

        tm->hw[i] = vnet_get_hw_interface(vnet_get_main(),
                                          tm->hw_if_indicies[i]);
        vec_validate (ip4_main.fib_index_by_sw_if_index, tm->hw[i]->sw_if_index);
        vec_validate (ip6_main.fib_index_by_sw_if_index, tm->hw[i]->sw_if_index);
        ip4_main.fib_index_by_sw_if_index[tm->hw[i]->sw_if_index] = 0;
        ip6_main.fib_index_by_sw_if_index[tm->hw[i]->sw_if_index] = 0;
        error = vnet_sw_interface_set_flags(vnet_get_main(),
                                            tm->hw[i]->sw_if_index,
                                            VNET_SW_INTERFACE_FLAG_ADMIN_UP);
        BIER_TEST((NULL == error), "UP interface %d", i);
    }
    /*
     * re-eval after the inevitable realloc
     */
    for (i = 0; i < ninterfaces; i++)
    {
        tm->hw[i] = vnet_get_hw_interface(vnet_get_main(),
                                          tm->hw_if_indicies[i]);
    }

    return (res);
}

#define BIER_TEST_LB(_cond, _comment, _args...)			\
{								\
    if (BIER_TEST_I(_cond, _comment, ##_args)) {		\
        return (1);						\
    }								\
}

static int
bier_test_validate_entry (index_t bei,
                          int n_buckets,
                          ...)
{
    dpo_id_t dpo = DPO_INVALID;
    const load_balance_t *lb;
    va_list ap;
    int res;

    va_start(ap, n_buckets);

    res = 0;
    bier_entry_contribute_forwarding(bei, &dpo);

    res = BIER_TEST_I((DPO_LOAD_BALANCE == dpo.dpoi_type),
                      "Entry links to %U",
                      format_dpo_type, dpo.dpoi_type);

    if (!res)
    {
        lb = load_balance_get(dpo.dpoi_index);
        res = fib_test_validate_lb_v(lb, n_buckets, &ap);
    }

    dpo_reset(&dpo);
    va_end(ap);

    return (res);
}

static int
bier_test_mpls_spf (void)
{
    fib_node_index_t lfei, fei, bti;
    u32 mpls_fib_index;
    test_main_t *tm;
    int lb_count;
    int res;

    res = 0;
    lb_count = pool_elts(load_balance_pool);
    tm = &test_main;
#define N_BIER_ECMP_TABLES 16
    int ii;

    /*
     * Add the BIER Main table
     */
    const bier_table_id_t bt_0_0_0_256 = {
        .bti_set = 0,
        .bti_sub_domain = 0,
        .bti_hdr_len = BIER_HDR_LEN_256,
        .bti_type = BIER_TABLE_MPLS_SPF,
        .bti_ecmp = BIER_ECMP_TABLE_ID_MAIN,
    };

    bti = bier_table_add_or_lock(&bt_0_0_0_256, 1600);

    fib_test_lb_bucket_t l_o_bt[N_BIER_ECMP_TABLES];
    bier_table_id_t bt_ecmp_0_0_0_256 = bt_0_0_0_256;

    for (ii = 0; ii < N_BIER_ECMP_TABLES; ii++)
    {
        bt_ecmp_0_0_0_256.bti_ecmp = ii;

        l_o_bt[ii].type = FT_LB_BIER_TABLE;
        l_o_bt[ii].bier.table =
            bier_table_ecmp_create_and_lock(&bt_ecmp_0_0_0_256);
    };
    const fib_prefix_t pfx_1600_neos = {
        .fp_len = 21,
        .fp_proto = FIB_PROTOCOL_MPLS,
        .fp_label = 1600,
        .fp_eos = MPLS_NON_EOS,
        .fp_payload_proto = DPO_PROTO_BIER,
    };
    const fib_prefix_t pfx_1600_eos = {
        .fp_len = 21,
        .fp_proto = FIB_PROTOCOL_MPLS,
        .fp_label = 1600,
        .fp_eos = MPLS_EOS,
        .fp_payload_proto = DPO_PROTO_BIER,
    };

    mpls_fib_index = fib_table_find(FIB_PROTOCOL_MPLS,
                                    MPLS_FIB_DEFAULT_TABLE_ID);

    lfei = fib_table_lookup(mpls_fib_index, &pfx_1600_neos);
    BIER_TEST(FIB_NODE_INDEX_INVALID == lfei, "1600/0 is not present");

    lfei = fib_table_lookup(mpls_fib_index, &pfx_1600_eos);
    BIER_TEST(!fib_test_validate_entry(lfei, FIB_FORW_CHAIN_TYPE_MPLS_EOS,
                                       16,
                                       &l_o_bt[0],
                                       &l_o_bt[1],
                                       &l_o_bt[2],
                                       &l_o_bt[3],
                                       &l_o_bt[4],
                                       &l_o_bt[5],
                                       &l_o_bt[6],
                                       &l_o_bt[7],
                                       &l_o_bt[8],
                                       &l_o_bt[9],
                                       &l_o_bt[10],
                                       &l_o_bt[11],
                                       &l_o_bt[12],
                                       &l_o_bt[13],
                                       &l_o_bt[14],
                                       &l_o_bt[15]),
              "1600/1 LB stacks on BIER table %d", bti);

    /*
     * modify the table's local label - keep the lock count accurate
     */
    const fib_prefix_t pfx_1601_eos = {
        .fp_len = 21,
        .fp_proto = FIB_PROTOCOL_MPLS,
        .fp_label = 1601,
        .fp_eos = MPLS_EOS,
        .fp_payload_proto = DPO_PROTO_BIER,
    };
    bti = bier_table_add_or_lock(&bt_0_0_0_256, 1601);
    bier_table_unlock(&bt_0_0_0_256);

    lfei = fib_table_lookup(mpls_fib_index, &pfx_1600_eos);
    BIER_TEST(FIB_NODE_INDEX_INVALID == lfei, "1600/1 is deleted");

    lfei = fib_table_lookup(mpls_fib_index, &pfx_1601_eos);
    BIER_TEST(!fib_test_validate_entry(lfei, FIB_FORW_CHAIN_TYPE_MPLS_EOS,
                                       16,
                                       &l_o_bt[0],
                                       &l_o_bt[1],
                                       &l_o_bt[2],
                                       &l_o_bt[3],
                                       &l_o_bt[4],
                                       &l_o_bt[5],
                                       &l_o_bt[6],
                                       &l_o_bt[7],
                                       &l_o_bt[8],
                                       &l_o_bt[9],
                                       &l_o_bt[10],
                                       &l_o_bt[11],
                                       &l_o_bt[12],
                                       &l_o_bt[13],
                                       &l_o_bt[14],
                                       &l_o_bt[15]),
              "1601/1 LB stacks on BIER table %d", bti);

    /*
     * add a route to the table. the via IP route does not exist.
     */
    const ip46_address_t nh_1_1_1_1 = {
        .ip4 = {
            .as_u32 = clib_host_to_net_u32(0x01010101),
        },
    };
    fib_route_path_t *paths_1_1_1_1 = NULL, *input_paths_1_1_1_1;
    fib_route_path_t path_1_1_1_1 = {
        .frp_addr = nh_1_1_1_1,
        .frp_bier_fib_index = bti,
        .frp_sw_if_index = ~0,
    };
    fib_mpls_label_t fml_500 = {
        .fml_value = 500,
    };
    vec_add1(path_1_1_1_1.frp_label_stack, fml_500);
    vec_add1(paths_1_1_1_1, path_1_1_1_1);
    const fib_prefix_t pfx_1_1_1_1_s_32 = {
        .fp_addr = nh_1_1_1_1,
        .fp_len = 32,
        .fp_proto = FIB_PROTOCOL_IP4,
    };
    index_t bei_1;

    input_paths_1_1_1_1 = vec_dup(paths_1_1_1_1);
    bier_table_route_path_add(&bt_0_0_0_256, 1, input_paths_1_1_1_1);
    bei_1 = bier_table_lookup(bier_table_get(bti), 1);

    BIER_TEST((INDEX_INVALID != bei_1), "BP:1 present");

    /*
     * the newly created fmask should stack on the non-eos chain
     * of the via-fib-entry
     */
    dpo_id_t neos_dpo_1_1_1_1 = DPO_INVALID;
    bier_fmask_t *bfm_1_1_1_1;
    index_t bfmi_1_1_1_1;

    fei = fib_table_lookup_exact_match(0, &pfx_1_1_1_1_s_32);
    fib_entry_contribute_forwarding(fei,
                                    FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS,
                                    &neos_dpo_1_1_1_1);

    bfmi_1_1_1_1 = bier_fmask_db_find(bti, &path_1_1_1_1);
    bfm_1_1_1_1 = bier_fmask_get(bfmi_1_1_1_1);

    BIER_TEST(!dpo_cmp(drop_dpo_get(DPO_PROTO_MPLS),
                       &bfm_1_1_1_1->bfm_dpo),
              "Fmask via 1.1.1.1 stacks on MPLS drop");

    /*
     * The BIER entry should stack on the forwarding chain of the fmask
     */
    const fib_test_lb_bucket_t dpo_o_bfm_1_1_1_1 = {
        .type = FT_LB_BIER_FMASK,
        .bier = {
            .fmask = bfmi_1_1_1_1,
        },
    };
    dpo_id_t dpo_bei = DPO_INVALID;
    bier_entry_contribute_forwarding(bei_1, &dpo_bei);

    BIER_TEST(!dpo_cmp(&dpo_bei, drop_dpo_get(DPO_PROTO_BIER)),
              "BP:1 stacks on bier drop");

    /*
     * give 1.1.1.1/32 a path and hence a interesting n-eos chain
     */
    ip46_address_t nh_10_10_10_1 = {
        .ip4 = {
            .as_u32 = clib_host_to_net_u32(0x0a0a0a01),
        },
    };
    adj_index_t ai_mpls_10_10_10_1;
    ai_mpls_10_10_10_1 = adj_nbr_add_or_lock(FIB_PROTOCOL_IP4,
                                             VNET_LINK_MPLS,
                                             &nh_10_10_10_1,
                                             tm->hw[0]->sw_if_index);

    fib_test_lb_bucket_t bucket_neos_99_via_10_10_10_1 = {
        .type = FT_LB_LABEL_O_ADJ,
        .label_o_adj = {
            .label = 99,
            .eos = MPLS_NON_EOS,
            .adj = ai_mpls_10_10_10_1,
            .ttl = 255,
        },
    };
    fib_mpls_label_t *out_lbl_99 = NULL, fml_99 = {
        .fml_value = 99,
    };
    vec_add1(out_lbl_99, fml_99);

    fei = fib_table_entry_update_one_path(0,
                                          &pfx_1_1_1_1_s_32,
                                          FIB_SOURCE_API,
                                          FIB_ENTRY_FLAG_NONE,
                                          DPO_PROTO_IP4,
                                          &nh_10_10_10_1,
                                          tm->hw[0]->sw_if_index,
                                          ~0, // invalid fib index
                                          1,
                                          out_lbl_99,
                                          FIB_ROUTE_PATH_FLAG_NONE);
    fib_entry_contribute_forwarding(fei,
                                    FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS,
                                    &neos_dpo_1_1_1_1);
    BIER_TEST(!fib_test_validate_lb(&neos_dpo_1_1_1_1, 1,
                                    &bucket_neos_99_via_10_10_10_1),
              "1.1.1.1/32 n-eos LB 1 buckets via: 99 + 10.10.10.1");
    BIER_TEST(!dpo_cmp(&neos_dpo_1_1_1_1,
                       &bfm_1_1_1_1->bfm_dpo),
              "Fmask via 1.1.1.1 stacks on updated non-eos of 1.1.1.1/32");
    bier_entry_contribute_forwarding(bei_1, &dpo_bei);
    BIER_TEST((dpo_bei.dpoi_index == bfmi_1_1_1_1),
              "BP:1  stacks on fmask 1.1.1.1");

    /*
     * add another path to the via entry.
     * this makes the via-entry instantiate a new load-balance with
     * 2 buckets. and the back-walk to the BIER entry will need to
     * re-stack on it.
     */
    ip46_address_t nh_10_10_10_2 = {
        .ip4 = {
            .as_u32 = clib_host_to_net_u32(0x0a0a0a02),
        },
    };
    adj_index_t ai_mpls_10_10_10_2;

    ai_mpls_10_10_10_2 = adj_nbr_add_or_lock(FIB_PROTOCOL_IP4,
                                             VNET_LINK_MPLS,
                                             &nh_10_10_10_2,
                                             tm->hw[0]->sw_if_index);

    fib_test_lb_bucket_t bucket_neos_100_via_10_10_10_2 = {
        .type = FT_LB_LABEL_O_ADJ,
        .label_o_adj = {
            .label = 100,
            .eos = MPLS_NON_EOS,
            .adj = ai_mpls_10_10_10_2,
            .ttl = 255,
        },
    };
    fib_mpls_label_t *out_lbl_100 = NULL, fml_100 = {
        .fml_value = 100,
    };
    vec_add1(out_lbl_100, fml_100);

    fei = fib_table_entry_path_add(0,
                                   &pfx_1_1_1_1_s_32,
                                   FIB_SOURCE_API,
                                   FIB_ENTRY_FLAG_NONE,
                                   DPO_PROTO_IP4,
                                   &nh_10_10_10_2,
                                   tm->hw[0]->sw_if_index,
                                   ~0, // invalid fib index
                                   1,
                                   out_lbl_100,
                                   FIB_ROUTE_PATH_FLAG_NONE);

    fib_entry_contribute_forwarding(fei,
                                    FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS,
                                    &neos_dpo_1_1_1_1);
    BIER_TEST(!fib_test_validate_lb(&neos_dpo_1_1_1_1, 2,
                                    &bucket_neos_99_via_10_10_10_1,
                                    &bucket_neos_100_via_10_10_10_2),
              "1.1.1.1/32 n-eos LB 2 buckets "
              "via: 99 + 10.10.10.1, "
              "via: 100 + 10.10.10.2");
    BIER_TEST(!dpo_cmp(&neos_dpo_1_1_1_1,
                       &bfm_1_1_1_1->bfm_dpo),
              "Fmask via 1.1.1.1 stacks on updated non-eos of 1.1.1.1/32");

    /*
     * add another bier bit-position via the same next-hop
     * since its the same next hop, the two bit-positions should link
     * to the same fmask
     */
    index_t bei_2;

    input_paths_1_1_1_1 = vec_dup(paths_1_1_1_1);
    bier_table_route_path_add(&bt_0_0_0_256, 2, input_paths_1_1_1_1);
    bei_2 = bier_table_lookup(bier_table_get(bti), 2);

    bier_entry_contribute_forwarding(bei_2, &dpo_bei);
    BIER_TEST((dpo_bei.dpoi_index == bfmi_1_1_1_1),
              "BP:2  stacks on fmask 1.1.1.1");

    /*
     * now add a bit-position via a different next hop and expect to
     * link via a different fmask
     */
    const ip46_address_t nh_1_1_1_2 = {
        .ip4 = {
            .as_u32 = clib_host_to_net_u32(0x01010102),
        },
    };
    const fib_prefix_t pfx_1_1_1_2_s_32 = {
        .fp_addr = nh_1_1_1_2,
        .fp_len = 32,
        .fp_proto = FIB_PROTOCOL_IP4,
    };
    fib_route_path_t *paths_1_1_1_2 = NULL, *input_paths_1_1_1_2, path_1_1_1_2 = {
        .frp_addr = nh_1_1_1_2,
        .frp_bier_fib_index = bti,
        .frp_sw_if_index = ~0,
    };
    fib_mpls_label_t fml_501 = {
        .fml_value = 501,
    };
    vec_add1(path_1_1_1_2.frp_label_stack, fml_501);
    vec_add1(paths_1_1_1_2, path_1_1_1_2);
    input_paths_1_1_1_2 = vec_dup(paths_1_1_1_2);
    index_t bei_3;

    fib_mpls_label_t *out_lbl_101 = NULL, fml_101 = {
        .fml_value = 101,
    };
    vec_add1(out_lbl_101, fml_101);
    fei = fib_table_entry_path_add(0,
                                   &pfx_1_1_1_2_s_32,
                                   FIB_SOURCE_API,
                                   FIB_ENTRY_FLAG_NONE,
                                   DPO_PROTO_IP4,
                                   &nh_10_10_10_2,
                                   tm->hw[0]->sw_if_index,
                                   ~0, // invalid fib index
                                   1,
                                   out_lbl_101,
                                   FIB_ROUTE_PATH_FLAG_NONE);
    bier_table_route_path_update(&bt_0_0_0_256, 3, input_paths_1_1_1_2);
    bei_3 = bier_table_lookup(bier_table_get(bti), 3);

    BIER_TEST((INDEX_INVALID != bei_3), "BP:3 present");

    /*
     * the newly created fmask should stack on the non-eos chain
     * of the via-fib-entry
     */
    dpo_id_t neos_dpo_1_1_1_2 = DPO_INVALID;
    bier_fmask_t *bfm_1_1_1_2;
    index_t bfmi_1_1_1_2;

    fei = fib_table_lookup_exact_match(0, &pfx_1_1_1_2_s_32);
    fib_entry_contribute_forwarding(fei,
                                    FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS,
                                    &neos_dpo_1_1_1_2);

    bfmi_1_1_1_2 = bier_fmask_db_find(bti, &path_1_1_1_2);
    bfm_1_1_1_2 = bier_fmask_get(bfmi_1_1_1_2);

    BIER_TEST(!dpo_cmp(&neos_dpo_1_1_1_2,
                       &bfm_1_1_1_2->bfm_dpo),
              "Fmask via 1.1.1.2 stacks on non-eos of 1.1.1.2/32");

    /*
     * The BIER entry should stack on the forwarding chain of the fmask
     */
    const fib_test_lb_bucket_t dpo_o_bfm_1_1_1_2 = {
        .type = FT_LB_BIER_FMASK,
        .bier = {
            .fmask = bfmi_1_1_1_2,
        },
    };
    bier_entry_contribute_forwarding(bei_3, &dpo_bei);
    BIER_TEST((dpo_bei.dpoi_index == bfmi_1_1_1_2),
              "BP:2 stacks on fmask 1.1.1.2");

    /*
     * Load-balance BP:3 over both next-hops
     */
    paths_1_1_1_1[0] = path_1_1_1_1;
    input_paths_1_1_1_1 = vec_dup(paths_1_1_1_1);
    bier_table_route_path_add(&bt_0_0_0_256, 3, input_paths_1_1_1_1);

    BIER_TEST(!bier_test_validate_entry(bei_3, 2,
                                        &dpo_o_bfm_1_1_1_1,
                                        &dpo_o_bfm_1_1_1_2),
              "BP:3 stacks on fmask 1.1.1.2 & 1.1.1.1");

    /*
     * test that the ECMP choices for BP:3 have been spread over the
     * ECMP tables
     */
    BIER_TEST((bier_table_fwd_lookup(bier_table_get(l_o_bt[0].bier.table), 3) ==
               bfmi_1_1_1_1),
              "fwd lookup for BP:3 ECMP:0 is 1.1.1.1");
    BIER_TEST((bier_table_fwd_lookup(bier_table_get(l_o_bt[1].bier.table), 3) ==
               bfmi_1_1_1_2),
              "fwd lookup for BP:3 ECMP:1 is 1.1.1.2");

    /*
     * Withdraw one of the via FIB and thus bring down the fmask
     * expect the bier-entry forwarding to remove this from the set
     */
    fib_table_entry_delete(0, &pfx_1_1_1_2_s_32, FIB_SOURCE_API);

    bier_entry_contribute_forwarding(bei_3, &dpo_bei);
    BIER_TEST((dpo_bei.dpoi_index == bfmi_1_1_1_1),
              "BP:3 stacks on fmask 1.1.1.1");

    BIER_TEST((bier_table_fwd_lookup(bier_table_get(l_o_bt[0].bier.table), 3) ==
               bfmi_1_1_1_1),
              "fwd lookup for BP:3 ECMP:0 is 1.1.1.1");
    BIER_TEST((bier_table_fwd_lookup(bier_table_get(l_o_bt[1].bier.table), 3) ==
               bfmi_1_1_1_1),
              "fwd lookup for BP:3 ECMP:1 is 1.1.1.1");

    /*
     * add the via back
     */
    out_lbl_101 = NULL;
    vec_add1(out_lbl_101, fml_101);
    fei = fib_table_entry_path_add(0,
                                   &pfx_1_1_1_2_s_32,
                                   FIB_SOURCE_API,
                                   FIB_ENTRY_FLAG_NONE,
                                   DPO_PROTO_IP4,
                                   &nh_10_10_10_2,
                                   tm->hw[0]->sw_if_index,
                                   ~0, // invalid fib index
                                   1,
                                   out_lbl_101,
                                   FIB_ROUTE_PATH_FLAG_NONE);
    /* suspend so the update walk kicks int */
    vlib_process_suspend(vlib_get_main(), 1e-5);

    BIER_TEST(!bier_test_validate_entry(bei_3, 2,
                                        &dpo_o_bfm_1_1_1_1,
                                        &dpo_o_bfm_1_1_1_2),
              "BP:3 stacks on fmask 1.1.1.2 & 1.1.1.1");
    BIER_TEST((bier_table_fwd_lookup(bier_table_get(l_o_bt[0].bier.table), 3) ==
               bfmi_1_1_1_1),
              "fwd lookup for BP:3 ECMP:0 is 1.1.1.1");
    BIER_TEST((bier_table_fwd_lookup(bier_table_get(l_o_bt[1].bier.table), 3) ==
               bfmi_1_1_1_2),
              "fwd lookup for BP:3 ECMP:1 is 1.1.1.2");

    /*
     * remove the original 1.1.1.2 fmask from BP:3
     */
    input_paths_1_1_1_2 = vec_dup(paths_1_1_1_2);
    bier_table_route_path_remove(&bt_0_0_0_256, 3, input_paths_1_1_1_2);
    bier_entry_contribute_forwarding(bei_3, &dpo_bei);
    BIER_TEST((dpo_bei.dpoi_index == bfmi_1_1_1_1),
              "BP:3 stacks on fmask 1.1.1.1");

    /*
     * test that the ECMP choices for BP:3 have been updated
     */
    BIER_TEST((bier_table_fwd_lookup(bier_table_get(l_o_bt[0].bier.table), 3) ==
               bfmi_1_1_1_1),
              "fwd lookup for BP:3 ECMP:0 is 1.1.1.1");
    BIER_TEST((bier_table_fwd_lookup(bier_table_get(l_o_bt[1].bier.table), 3) ==
               bfmi_1_1_1_1),
              "fwd lookup for BP:3 ECMP:1 is 1.1.1.1");

    /*
     * remove the routes added
     */
    input_paths_1_1_1_1 = vec_dup(paths_1_1_1_1);
    bier_table_route_path_remove(&bt_0_0_0_256, 2, input_paths_1_1_1_1);
    input_paths_1_1_1_2 = vec_dup(paths_1_1_1_2);
    bier_table_route_path_remove(&bt_0_0_0_256, 3, input_paths_1_1_1_2);
    input_paths_1_1_1_1 = vec_dup(paths_1_1_1_1);
    bier_table_route_path_remove(&bt_0_0_0_256, 3, input_paths_1_1_1_1);

    bier_table_route_delete(&bt_0_0_0_256, 1);

    /*
     * delete the table
     */
    bier_table_unlock(&bt_0_0_0_256);

    /*
     * test resources are freed
     */
    dpo_reset(&dpo_bei);
    for (ii = 0; ii < N_BIER_ECMP_TABLES; ii++)
    {
        bier_table_ecmp_unlock(l_o_bt[ii].bier.table);
    };
    BIER_TEST(0 == pool_elts(bier_table_pool), "BIER table pool empty");
    BIER_TEST(0 == pool_elts(bier_fmask_pool), "BIER fmask pool empty");
    BIER_TEST(0 == pool_elts(bier_entry_pool), "BIER entry pool empty");

    adj_unlock(ai_mpls_10_10_10_1);
    adj_unlock(ai_mpls_10_10_10_2);
    dpo_reset(&neos_dpo_1_1_1_1);
    dpo_reset(&neos_dpo_1_1_1_2);
    fib_table_entry_delete(0, &pfx_1_1_1_1_s_32, FIB_SOURCE_API);
    fib_table_entry_delete(0, &pfx_1_1_1_2_s_32, FIB_SOURCE_API);

    /* +1 to account for the one time alloc'd drop LB in the MPLS fibs */
    BIER_TEST(lb_count+1 == pool_elts(load_balance_pool),
              "Load-balance resources freed ");
    BIER_TEST((0 == adj_nbr_db_size()), "ADJ DB size is %d",
             adj_nbr_db_size());

    vec_free(paths_1_1_1_1);
    vec_free(paths_1_1_1_2);
    vec_free(input_paths_1_1_1_1);
    vec_free(input_paths_1_1_1_2);

    return (0);
}

static int
bier_test_mpls_imp (void)
{
    fib_node_index_t bii;
    int res;

    /*
     * Add the BIER Main table
     */
    const bier_table_id_t bt_0_0_0_256 = {
        .bti_set = 0,
        .bti_sub_domain = 0,
        .bti_hdr_len = BIER_HDR_LEN_256,
        .bti_type = BIER_TABLE_MPLS_SPF,
        .bti_ecmp = BIER_ECMP_TABLE_ID_MAIN,
    };

    bier_table_add_or_lock(&bt_0_0_0_256, 1600);

    /*
     * A bit-string for imp 1.
     */
    bier_bit_string_t bbs_256;
    u8 buckets[BIER_HDR_BUCKETS_256];
    clib_memset(buckets, 0x5, BIER_HDR_BUCKETS_256);

    res = 0;
    bier_bit_string_init(&bbs_256, BIER_HDR_LEN_256, buckets);

    bii = bier_imp_add_or_lock(&bt_0_0_0_256, 1, &bbs_256);

    /*
     * An mfib entry that resolves via the BIER imposition
     */
    const mfib_prefix_t pfx_1_1_1_1_c_239_1_1_1 = {
        .fp_len = 64,
        .fp_proto = FIB_PROTOCOL_IP4,
        .fp_grp_addr = {
            .ip4.as_u32 = clib_host_to_net_u32(0xef010101),
        },
        .fp_src_addr = {
            .ip4.as_u32 = clib_host_to_net_u32(0x01010101),
        },
    };
    fib_route_path_t path_via_bier_imp_1 = {
        .frp_proto = DPO_PROTO_BIER,
        .frp_bier_imp = bii,
        .frp_weight = 0,
        .frp_flags = FIB_ROUTE_PATH_BIER_IMP,
        .frp_mitf_flags = MFIB_ITF_FLAG_FORWARD,
    };
    mfib_table_entry_path_update(0, // default table
                                 &pfx_1_1_1_1_c_239_1_1_1 ,
                                 MFIB_SOURCE_API,
                                 &path_via_bier_imp_1);
    mfib_table_entry_delete(0,
                            &pfx_1_1_1_1_c_239_1_1_1 ,
                            MFIB_SOURCE_API);

    bier_imp_unlock(bii);
    bier_table_unlock(&bt_0_0_0_256);

    BIER_TEST(0 == pool_elts(bier_imp_pool),
              "BIER imposition resources freed ");
    BIER_TEST(0 == pool_elts(bier_table_pool),
              "BIER table resources freed ");

    return (0);
}

static int
bier_test_mpls_disp (void)
{
    /*
     * Add the BIER Main table
     */
    const bier_table_id_t bt_0_0_0_256 = {
        .bti_set = 0,
        .bti_sub_domain = 0,
        .bti_hdr_len = BIER_HDR_LEN_256,
        .bti_type = BIER_TABLE_MPLS_SPF,
        .bti_ecmp = BIER_ECMP_TABLE_ID_MAIN,
    };
    index_t bti;
    int res;

    res = 0;
    bti = bier_table_add_or_lock(&bt_0_0_0_256, 1600);

    /*
     * Add a BIER disposition table
     */
    const u32 bier_disp_tbl_id = 1;
    index_t bdti1;

    bdti1 = bier_disp_table_add_or_lock(bier_disp_tbl_id);

    /*
     * add a bit-position in the table that resolves via
     * DISP table, i.e. a for-us bit-position
     */
    fib_route_path_t *paths_via_disp = NULL, path_via_disp = {
        // .frp_addr = all-zeros
        .frp_proto = DPO_PROTO_BIER,
        .frp_bier_fib_index = bdti1,
        .frp_sw_if_index = ~0,
    };
    vec_add1(paths_via_disp, path_via_disp);

    bier_table_route_path_add(&bt_0_0_0_256, 3, paths_via_disp);

    /*
     * the fmask should stack on the BIER disp table
     */
    bier_fmask_t *bfm_0_0_0_0;
    index_t bfmi_0_0_0_0;
    dpo_id_t dpo_disp_tbl_1 = DPO_INVALID;

    bier_disp_table_contribute_forwarding(bdti1, &dpo_disp_tbl_1);

    bfmi_0_0_0_0 = bier_fmask_db_find(bti, &path_via_disp);
    bfm_0_0_0_0 = bier_fmask_get(bfmi_0_0_0_0);

    BIER_TEST(!dpo_cmp(&dpo_disp_tbl_1, &bfm_0_0_0_0->bfm_dpo),
              "Fmask via 0.0.0.0 stacks on BIER disp table 1");

    /*
     * and a deag entry into the disposition table
     */
    fib_route_path_t *rpaths = NULL, path_via_mfib = {
        .frp_proto = DPO_PROTO_IP4,
        .frp_addr = zero_addr,
        .frp_fib_index = 0, // default MFIB table
        .frp_rpf_id = 9, // some non-zero value
        .frp_flags = FIB_ROUTE_PATH_RPF_ID,
    };
    bier_hdr_src_id_t src = 99;
    vec_add1(rpaths, path_via_mfib);
    bier_disp_table_entry_path_add(bier_disp_tbl_id, src,
                                   BIER_HDR_PROTO_IPV4, rpaths);

    /* which should stack on a lookup in the mfib table */
    const dpo_id_t *dpo_disp_entry_v4;
    bier_disp_entry_t *bde_99;
    index_t bdei;

    bdei = bier_disp_table_lookup(bdti1, clib_host_to_net_u16(src));
    bde_99 = bier_disp_entry_get(bdei);
    dpo_disp_entry_v4 = &bde_99->bde_fwd[BIER_HDR_PROTO_IPV4].bde_dpo;

    lookup_dpo_t *lkd = lookup_dpo_get(dpo_disp_entry_v4->dpoi_index);

    BIER_TEST((bdti1 == lkd->lkd_fib_index),
              "disp is deag in %d %U",
              lkd->lkd_fib_index,
              format_dpo_id, dpo_disp_entry_v4, 0);
    BIER_TEST((LOOKUP_INPUT_DST_ADDR == lkd->lkd_input),
              "disp is destination deag in %d %U",
              lkd->lkd_input,
              format_dpo_id, dpo_disp_entry_v4, 0);
    BIER_TEST((LOOKUP_MULTICAST == lkd->lkd_cast),
              "disp is multicast deag in %d %U",
              lkd->lkd_input,
              format_dpo_id, dpo_disp_entry_v4, 0);

    /*
     * cleanup
     */
    dpo_reset(&dpo_disp_tbl_1);

    bier_disp_table_entry_path_remove(bier_disp_tbl_id, src,
                                      BIER_HDR_PROTO_IPV4, rpaths);
    bier_table_route_path_remove(&bt_0_0_0_256, 3, paths_via_disp);

    bier_disp_table_unlock_w_table_id(bier_disp_tbl_id);

    bier_table_unlock(&bt_0_0_0_256);

    BIER_TEST(0 == pool_elts(bier_fmask_pool),
              "BIER fmask resources freed ");
    BIER_TEST(0 == pool_elts(bier_table_pool),
              "BIER table resources freed ");
    BIER_TEST(0 == pool_elts(bier_disp_table_pool),
              "BIER Disposition table resources freed ");
    BIER_TEST(0 == pool_elts(bier_disp_entry_pool),
              "BIER Disposition entry resources freed ");

    vec_free(paths_via_disp);
    return (0);
}

static clib_error_t *
bier_test (vlib_main_t * vm,
           unformat_input_t * input,
           vlib_cli_command_t * cmd_arg)
{
    int res = 0;

    res += bier_test_mk_intf(4);

    if (unformat (input, "debug"))
    {
        bier_test_do_debug = 1;
    }

    if (unformat (input, "mid"))
        res += bier_test_mpls_spf();
    else if (unformat (input, "head"))
        res += bier_test_mpls_imp();
    else if (unformat (input, "tail"))
        res += bier_test_mpls_disp();
    else
    {
        res += bier_test_mpls_spf();
        res += bier_test_mpls_imp();
        res += bier_test_mpls_disp();
    }

    if (res)
    {
        return clib_error_return(0, "BIER Unit Test Failed");
    }
    else
    {
        return (NULL);
    }
}

VLIB_CLI_COMMAND (test_route_command, static) = {
    .path = "test bier",
    .short_help = "bier unit tests",
    .function = bier_test,
};

clib_error_t *
bier_test_init (vlib_main_t *vm)
{
    return 0;
}

VLIB_INIT_FUNCTION (bier_test_init);