src/vnet/bier/bier_table.c

/*
 * 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 <vppinfra/vec.h>

#include <vnet/bier/bier_table.h>
#include <vnet/bier/bier_entry.h>
#include <vnet/bier/bier_update.h>
#include <vnet/bier/bier_fmask_db.h>
#include <vnet/bier/bier_fmask.h>
#include <vnet/bier/bier_bift_table.h>

#include <vnet/fib/mpls_fib.h>
#include <vnet/mpls/mpls.h>
#include <vnet/fib/fib_path_list.h>

/**
 * Memory pool of all the allocated tables
 */
bier_table_t *bier_table_pool;

/**
 * DB store of all BIER tables index by SD/set/hdr-len
 */
static uword *bier_tables_by_key;

/**
 * The magic number of BIER ECMP tables to create.
 * The load-balance distribution algorithm will use a power of 2
 * for the number of buckets, which constrains the choice.
 */
#define BIER_N_ECMP_TABLES 16

static inline index_t
bier_table_get_index (const bier_table_t *bt)
{
    return (bt - bier_table_pool);
}

int
bier_table_is_main (const bier_table_t *bt)
{
    return (BIER_ECMP_TABLE_ID_MAIN == bt->bt_id.bti_ecmp);
}

/*
 * Construct the key to use to find a BIER table
 * in the global hash map
 */
static u32
bier_table_mk_key (const bier_table_id_t *id)
{
    /*
     * the set and sub-domain Ids are 8 bit values.
     * we have space for ECMP table ID and talbe type (SPF/TE)
     * for later
     */
    u32 key = ((id->bti_sub_domain << 24)  |
               (id->bti_set << 16) |
               (id->bti_ecmp << 8) |
               (id->bti_hdr_len << 4) |
               (id->bti_type));

    return (key);
}

static void
bier_table_init (bier_table_t *bt,
                 const bier_table_id_t *id,
                 mpls_label_t ll)
{
    u32 num_entries;

    bt->bt_lfei = FIB_NODE_INDEX_INVALID;
    bt->bt_id = *id;
    bt->bt_ll = ll;
    num_entries = bier_hdr_len_id_to_num_bits(bt->bt_id.bti_hdr_len);

    /*
     * create the lookup table of entries.
     */
    if (bier_table_is_main(bt))
    {
        vec_validate_init_empty_aligned(bt->bt_entries,
                                        num_entries,
                                        INDEX_INVALID,
                                        CLIB_CACHE_LINE_BYTES);
    }
    else
    {
        vec_validate_init_empty_aligned(bt->bt_fmasks,
                                        num_entries,
                                        INDEX_INVALID,
                                        CLIB_CACHE_LINE_BYTES);
    }
}

static void
bier_table_rm_bift (bier_table_t *bt)
{
    ASSERT(MPLS_LABEL_INVALID == bt->bt_ll);

    bier_bift_table_entry_remove(bier_bift_id_encode(bt->bt_id.bti_set,
                                                     bt->bt_id.bti_sub_domain,
                                                     bt->bt_id.bti_hdr_len));
}

static void
bier_table_mk_bift (bier_table_t *bt)
{
    dpo_id_t dpo = DPO_INVALID;

    ASSERT(MPLS_LABEL_INVALID == bt->bt_ll);

    bier_table_contribute_forwarding(bier_table_get_index(bt), &dpo);

    bier_bift_table_entry_add(bier_bift_id_encode(bt->bt_id.bti_set,
                                                  bt->bt_id.bti_sub_domain,
                                                  bt->bt_id.bti_hdr_len),
                               &dpo);

    dpo_reset(&dpo);
}

static void
bier_table_rm_lfib (bier_table_t *bt)
{
    if (FIB_NODE_INDEX_INVALID != bt->bt_lfei)
    {
        fib_table_entry_delete_index(bt->bt_lfei,
                                     FIB_SOURCE_BIER);
        fib_table_unlock(MPLS_FIB_DEFAULT_TABLE_ID,
                         FIB_PROTOCOL_MPLS,
                         FIB_SOURCE_BIER);
    }
    bt->bt_lfei = FIB_NODE_INDEX_INVALID;
}

static void
bier_table_destroy (bier_table_t *bt)
{
    if (bier_table_is_main(bt))
    {
        index_t *bei;

        if (MPLS_LABEL_INVALID != bt->bt_ll)
        {
            bier_table_rm_lfib(bt);
        }
        else
        {
            bier_table_rm_bift(bt);
        }

        fib_path_list_unlock(bt->bt_pl);
        bt->bt_pl = FIB_NODE_INDEX_INVALID;
        /*
         * unresolve/remove all entries from the table
         */
        vec_foreach (bei, bt->bt_entries)
        {
            if (INDEX_INVALID != *bei)
            {
                bier_entry_delete(*bei);
            }
        }
        vec_free (bt->bt_entries);
    }
    else
    {
        index_t *bfmi;

        /*
         * unlock any fmasks
         */
        vec_foreach (bfmi, bt->bt_fmasks)
        {
            bier_fmask_unlock(*bfmi);
        }
        vec_free(bt->bt_fmasks);
    }

    hash_unset(bier_tables_by_key,
               bier_table_mk_key(&bt->bt_id));
    pool_put(bier_table_pool, bt);
}

static void
bier_table_lock_i (bier_table_t *bt)
{
    bt->bt_locks++;
}

static void
bier_table_unlock_i (bier_table_t *bt)
{
    bt->bt_locks--;

    if (0 == bt->bt_locks)
    {
        bier_table_destroy(bt);
    }
}

void
bier_table_unlock (const bier_table_id_t *bti)
{
    uword *p;
    u32 key;

    key = bier_table_mk_key(bti);

    p = hash_get (bier_tables_by_key, key);

    if (NULL != p) {
        bier_table_unlock_i(bier_table_get(p[0]));
    }
}

static void
bier_table_mk_lfib (bier_table_t *bt)
{
    /*
     * Add a new MPLS lfib entry
     */
    if (MPLS_LABEL_INVALID != bt->bt_ll) {
        fib_prefix_t pfx = {
            .fp_proto = FIB_PROTOCOL_MPLS,
            .fp_len = 21,
            .fp_label = bt->bt_ll,
            .fp_eos = MPLS_EOS,
            .fp_payload_proto = DPO_PROTO_BIER,
        };
        u32 mpls_fib_index;
        dpo_id_t dpo = DPO_INVALID;

        fib_table_find_or_create_and_lock(FIB_PROTOCOL_MPLS,
                                          MPLS_FIB_DEFAULT_TABLE_ID,
                                          FIB_SOURCE_BIER);

        /*
         * stack the entry on the forwarding chain produced by the
         * path-list via the ECMP tables.
         */
        fib_path_list_contribute_forwarding(bt->bt_pl,
                                            FIB_FORW_CHAIN_TYPE_BIER,
                                            FIB_PATH_LIST_FWD_FLAG_COLLAPSE,
                                            &dpo);

        mpls_fib_index = fib_table_find(FIB_PROTOCOL_MPLS,
                                        MPLS_FIB_DEFAULT_TABLE_ID);
        bt->bt_lfei = fib_table_entry_special_dpo_add(mpls_fib_index,
                                                      &pfx,
                                                      FIB_SOURCE_BIER,
                                                      FIB_ENTRY_FLAG_EXCLUSIVE,
                                                      &dpo);
        dpo_reset(&dpo);
    }
}

static bier_table_t *
bier_table_find (const bier_table_id_t *bti)
{
    uword *p;
    u32 key;

    key = bier_table_mk_key(bti);

    p = hash_get(bier_tables_by_key, key);

    if (NULL != p)
    {
        return (bier_table_get(p[0]));
    }

    return (NULL);
}

static bier_table_t *
bier_table_mk_ecmp (index_t bti)
{
    fib_route_path_t *rpaths;
    fib_node_index_t pli;
    bier_table_t *bt;
    int ii;

    rpaths = NULL;
    bt = bier_table_get(bti);

    vec_validate(rpaths, BIER_N_ECMP_TABLES-1);

    vec_foreach_index(ii, rpaths)
    {
        rpaths[ii].frp_bier_tbl = bt->bt_id;
        rpaths[ii].frp_bier_tbl.bti_ecmp = ii;
        rpaths[ii].frp_flags = FIB_ROUTE_PATH_BIER_TABLE;
    }

    /*
     * no opportunity to share, this the resolving ECMP tables are unique
     * to this table.
     * no need to be a child of the path list, we can do nothing with any
     * notifications it would generate [not that it will].
     */
    pli = fib_path_list_create(FIB_PATH_LIST_FLAG_NO_URPF, rpaths);
    fib_path_list_lock(pli);

    /*
     * constructing the path-list will have created many more BIER tables,
     * so this main table will no doubt have re-alloc.
     */
    bt = bier_table_get(bti);
    bt->bt_pl = pli;

    vec_free(rpaths);

    return (bt);
}


static index_t
bier_table_create (const bier_table_id_t *btid,
                   mpls_label_t local_label)
{
    /*
     * add a new table
     */
    bier_table_t *bt;
    index_t bti;
    u32 key;

    key = bier_table_mk_key(btid);

    pool_get_aligned(bier_table_pool, bt, CLIB_CACHE_LINE_BYTES);
    bier_table_init(bt, btid, local_label);

    hash_set(bier_tables_by_key, key, bier_table_get_index(bt));
    bti = bier_table_get_index(bt);

    if (bier_table_is_main(bt))
    {
        bt = bier_table_mk_ecmp(bti);

        /*
         * add whichever mpls-fib or bift we need
         */
        if (local_label != MPLS_LABEL_INVALID)
        {
            bt->bt_ll = local_label;
            bier_table_mk_lfib(bt);
        }
        else
        {
            bier_table_mk_bift(bt);
        }
    }

    return (bti);
}

index_t
bier_table_lock (const bier_table_id_t *btid)
{
    bier_table_t *bt;
    index_t bti;

    bt = bier_table_find(btid);

    if (NULL == bt)
    {
        bti = bier_table_create(btid, MPLS_LABEL_INVALID);
        bt = bier_table_get(bti);
    }
    else
    {
        bti = bier_table_get_index(bt);
    }

    bier_table_lock_i(bt);

    return (bti);
}

index_t
bier_table_add_or_lock (const bier_table_id_t *btid,
                        mpls_label_t local_label)
{
    bier_table_t *bt;
    index_t bti;

    bt = bier_table_find(btid);

    if (NULL != bt) {
        /*
         * modify an existing table.
         * change the lfib entry to the new local label
         */
        if (bier_table_is_main(bt))
        {
            /*
             * remove the mpls-fib or bift entry
             */
            if (MPLS_LABEL_INVALID != bt->bt_ll)
            {
                bier_table_rm_lfib(bt);
            }
            else
            {
                bier_table_rm_bift(bt);
            }

            /*
             * reset
             */
            bt->bt_ll = MPLS_LABEL_INVALID;

            /*
             * add whichever mpls-fib or bift we need
             */
            if (local_label != MPLS_LABEL_INVALID)
            {
                bt->bt_ll = local_label;
                bier_table_mk_lfib(bt);
            }
            else
            {
                bier_table_mk_bift(bt);
            }
        }
        bti = bier_table_get_index(bt);
    }
    else
    {
        bti = bier_table_create(btid, local_label);
        bt = bier_table_get(bti);
    }

    bier_table_lock_i(bt);

    return (bti);
}

index_t
bier_table_ecmp_create_and_lock (const bier_table_id_t *btid)
{
    return (bier_table_add_or_lock(btid, MPLS_LABEL_INVALID));
}

void
bier_table_ecmp_unlock (index_t bti)
{
    bier_table_unlock_i(bier_table_get(bti));
}

static void
bier_table_dpo_lock (dpo_id_t *dpo)
{
}

static void
bier_table_dpo_unlock (dpo_id_t *dpo)
{
}

static void
bier_table_dpo_mem_show (void)
{
    fib_show_memory_usage("BIER-table",
                          pool_elts(bier_table_pool),
                          pool_len(bier_table_pool),
                          sizeof(bier_table_t));
}
static u8 *
format_bier_table_dpo (u8 *s, va_list *ap)
{
    index_t bti = va_arg(*ap, index_t);
    bier_table_t *bt;

    bt = bier_table_get(bti);

    return (format(s, "[%U]", format_bier_table_id, &bt->bt_id));
}

const static dpo_vft_t bier_table_dpo_vft = {
    .dv_lock = bier_table_dpo_lock,
    .dv_unlock = bier_table_dpo_unlock,
    .dv_format = format_bier_table_dpo,
    .dv_mem_show = bier_table_dpo_mem_show,
};

const static char *const bier_table_mpls_nodes[] =
{
    "bier-input",
    NULL
};
const static char * const * const bier_table_nodes[DPO_PROTO_NUM] =
{
    [DPO_PROTO_BIER] = bier_table_mpls_nodes,
};

static clib_error_t *
bier_table_module_init (vlib_main_t *vm)
{
    dpo_register(DPO_BIER_TABLE, &bier_table_dpo_vft, bier_table_nodes);

    return (NULL);
}

VLIB_INIT_FUNCTION (bier_table_module_init);

const bier_table_id_t *
bier_table_get_id (index_t bti)
{
    bier_table_t *bt;

    bt = bier_table_get(bti);

    return (&bt->bt_id);
}

static void
bier_table_insert (bier_table_t *bt,
                   bier_bp_t bp,
                   index_t bei)
{
    bt->bt_entries[BIER_BP_TO_INDEX(bp)] = bei;
}

static void
bier_table_remove (bier_table_t *bt,
                   bier_bp_t bp)
{
    bt->bt_entries[BIER_BP_TO_INDEX(bp)] = INDEX_INVALID;
}

void
bier_table_route_path_update_i (const bier_table_id_t *btid,
                                bier_bp_t bp,
                                fib_route_path_t *brps,
                                u8 is_replace)
{
    index_t bfmi, bti, bei, *bfmip, *bfmis = NULL;
    fib_route_path_t *brp;
    bier_table_t *bt;

    bt = bier_table_find(btid);

    if (NULL == bt) {
        return;
    }

    bti = bier_table_get_index(bt);
    bei = bier_table_lookup(bt, bp);

    /*
     * set the FIB index in the path to the BIER table index
     */
    vec_foreach(brp, brps)
    {
        /*
         * First use the path to find or construct an FMask object
         * via the next-hop
         */
        bfmi = bier_fmask_db_find_or_create_and_lock(bti, brp);
        vec_add1(bfmis, bfmi);

        /*
         * then modify the path to resolve via this fmask object
         * and use it to resolve the BIER entry.
         */
        brp->frp_flags = FIB_ROUTE_PATH_BIER_FMASK;
        brp->frp_bier_fmask = bfmi;
    }

    if (INDEX_INVALID == bei)
    {
        bei = bier_entry_create(bti, bp);
        bier_table_insert(bt, bp, bei);
    }

    if (is_replace)
    {
        bier_entry_path_update(bei, brps);
    }
    else
    {
        fib_route_path_t *t_paths = NULL;

        vec_foreach(brp, brps)
        {
            vec_add1(t_paths, *brp);
            bier_entry_path_add(bei, t_paths);
            vec_reset_length(t_paths);
        }
        vec_free(t_paths);
    }

    vec_foreach(bfmip, bfmis)
    {
        bier_fmask_unlock(*bfmip);
    }
    vec_free(bfmis);
}

void
bier_table_route_path_update (const bier_table_id_t *btid,
                              bier_bp_t bp,
                              fib_route_path_t *brps)
{
    bier_table_route_path_update_i(btid, bp, brps, 1);
}
void
bier_table_route_path_add (const bier_table_id_t *btid,
                           bier_bp_t bp,
                           fib_route_path_t *brps)
{
    bier_table_route_path_update_i(btid, bp, brps, 0);
}

void
bier_table_route_delete (const bier_table_id_t *btid,
                         bier_bp_t bp)
{
    bier_table_t *bt;
    index_t bei;

    bt = bier_table_find(btid);

    if (NULL == bt) {
        return;
    }

    bei = bier_table_lookup(bt, bp);

    if (INDEX_INVALID == bei)
    {
        /* no such entry */
        return;
    }

    bier_table_remove(bt, bp);
    bier_entry_delete(bei);
}

void
bier_table_route_path_remove (const bier_table_id_t *btid,
                              bier_bp_t bp,
                              fib_route_path_t *brps)
{
    fib_route_path_t *brp = NULL, *t_paths = NULL;
    index_t bfmi, bti, bei;
    bier_table_t *bt;
    u32 ii;

    bt = bier_table_find(btid);

    if (NULL == bt) {
        return;
    }

    bti = bier_table_get_index(bt);
    bei = bier_table_lookup(bt, bp);

    if (INDEX_INVALID == bei)
    {
        /* no such entry */
        return;
    }

    /*
     * set the FIB index in the path to the BIER table index
     */
    vec_foreach_index(ii, brps)
    {
        brp = &brps[ii];
        bfmi = bier_fmask_db_find(bti, brp);

        if (INDEX_INVALID == bfmi)
        {
            /*
             * no matching fmask, not a path we can remove
             */
            vec_del1(brps, ii);
            continue;
        }

        /*
         * then modify the path to resolve via this fmask object
         * and use it to resolve the BIER entry.
         */
        brp->frp_flags = FIB_ROUTE_PATH_BIER_FMASK;
        brp->frp_bier_fmask = bfmi;
    }

    if (0 == vec_len(brps))
    {
        return;
    }

    vec_foreach(brp, brps)
    {
        vec_add1(t_paths, *brp);
        if (0 == bier_entry_path_remove(bei, t_paths))
        {
            /* 0 remaining paths */
            bier_table_remove(bt, bp);
            bier_entry_delete(bei);
            break;
        }
        vec_reset_length(t_paths);
    }
    vec_free(t_paths);
}

void
bier_table_contribute_forwarding (index_t bti,
                                  dpo_id_t *dpo)
{
    bier_table_t *bt;

    bt = bier_table_get(bti);

    if (BIER_ECMP_TABLE_ID_MAIN == bt->bt_id.bti_ecmp)
    {
        /*
         * return the load-balance for the ECMP tables
         */
        fib_path_list_contribute_forwarding(bt->bt_pl,
                                            FIB_FORW_CHAIN_TYPE_BIER,
                                            FIB_PATH_LIST_FWD_FLAG_COLLAPSE,
                                            dpo);
    }
    else
    {
        dpo_set(dpo, DPO_BIER_TABLE, DPO_PROTO_BIER, bti);
    }
}

typedef struct bier_table_ecmp_walk_ctx_t_
{
    bier_table_ecmp_walk_fn_t fn;
    void *ctx;
} bier_table_ecmp_walk_ctx_t;

static fib_path_list_walk_rc_t
bier_table_ecmp_walk_path_list (fib_node_index_t pl_index,
                                fib_node_index_t path_index,
                                void *arg)
{
    bier_table_ecmp_walk_ctx_t *ctx = arg;

    ctx->fn(fib_path_get_resolving_index(path_index), ctx->ctx);
    /* continue */
    return (FIB_PATH_LIST_WALK_CONTINUE);
}

void
bier_table_ecmp_walk (index_t bti,
                      bier_table_ecmp_walk_fn_t fn,
                      void *ctx)
{
    bier_table_ecmp_walk_ctx_t ewc = {
        .fn = fn,
        .ctx = ctx,
    };
    bier_table_t *bt;

    bt = bier_table_get(bti);

    if (FIB_NODE_INDEX_INVALID != bt->bt_pl)
    {
        fib_path_list_walk(bt->bt_pl,
                           bier_table_ecmp_walk_path_list,
                           &ewc);
    }
}

void
bier_table_ecmp_set_fmask (index_t bti,
                           bier_bp_t bp,
                           index_t bfmi)
{
    bier_table_t *bt;

    bt = bier_table_get(bti);

    /*
     * we hold a lock for fmasks in the table
     */
    bier_fmask_lock(bfmi);
    bier_fmask_unlock(bt->bt_fmasks[BIER_BP_TO_INDEX(bp)]);

    bt->bt_fmasks[BIER_BP_TO_INDEX(bp)] = bfmi;
}

u8 *
format_bier_table_entry (u8 *s, va_list *ap)
{
    index_t bti = va_arg(*ap, index_t);
    bier_bp_t bp = va_arg(*ap, bier_bp_t);
    bier_table_t *bt;
    bt = bier_table_get(bti);

    if (bier_table_is_main(bt))
    {
        index_t bei;

        bei = bier_table_lookup(bier_table_get(bti), bp);

        if (INDEX_INVALID != bei)
        {
            s = format(s, "%U", format_bier_entry, bei,
                       BIER_SHOW_DETAIL);
        }
    }
    else
    {
        index_t bfmi;

        bfmi = bier_table_fwd_lookup(bier_table_get(bti), bp);

        if (INDEX_INVALID != bfmi)
        {
            s = format(s, "%U", format_bier_fmask, bfmi,
                       BIER_SHOW_DETAIL);
        }
    }
    return (s);
}

u8 *
format_bier_table (u8 *s, va_list *ap)
{
    index_t bti = va_arg(*ap, index_t);
    bier_show_flags_t flags = va_arg(*ap, bier_show_flags_t);
    bier_table_t *bt;

    if (pool_is_free_index(bier_table_pool, bti))
    {
        return (format(s, "No BIER table %d", bti));
    }

    bt = bier_table_get(bti);

    s = format(s, "[@%d] bier-table:[%U local-label:%U",
               bti,
               format_bier_table_id, &bt->bt_id,
               format_mpls_unicast_label, bt->bt_ll);

    if (flags & BIER_SHOW_DETAIL)
    {
        s = format(s, " locks:%d", bt->bt_locks);
    }
    s = format(s, "]");

    if (flags & BIER_SHOW_DETAIL)
    {
        if (bier_table_is_main(bt))
        {
            index_t *bei;

            vec_foreach (bei, bt->bt_entries)
            {
                if (INDEX_INVALID != *bei)
                {
                    s = format(s, "\n%U", format_bier_entry, *bei, 2);
                }
            }
        }
        else
        {
            u32 ii;

            vec_foreach_index (ii, bt->bt_fmasks)
            {
                if (INDEX_INVALID != bt->bt_fmasks[ii])
                {
                    s = format(s, "\n bp:%d\n %U", ii,
                               format_bier_fmask, bt->bt_fmasks[ii], 2);
                }
            }
        }
    }

    return (s);
}

void
bier_table_show_all (vlib_main_t * vm,
                     bier_show_flags_t flags)
{
    if (!pool_elts(bier_table_pool))
    {
        vlib_cli_output (vm, "No BIER tables");
    }
    else
    {
        int ii;

        pool_foreach_index (ii, bier_table_pool)
         {
            vlib_cli_output (vm, "%U", format_bier_table, ii, flags);
        }
    }
}

void
bier_tables_walk (bier_tables_walk_fn_t fn,
                  void *ctx)
{
    ASSERT(0);
}


void
bier_table_walk (const bier_table_id_t *bti,
                 bier_table_walk_fn_t fn,
                 void *ctx)
{
    bier_table_t *bt;
    bier_entry_t *be;
    index_t *bei;

    bt = bier_table_find(bti);

    if (NULL == bt)
    {
        return;
    }

    vec_foreach (bei, bt->bt_entries)
    {
        if (INDEX_INVALID != *bei)
        {
            be = bier_entry_get(*bei);

            fn(bt, be, ctx);
        }
    }
}