src/vnet/fib/fib_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 <vlib/vlib.h>
#include <vnet/dpo/drop_dpo.h>

#include <vnet/fib/fib_table.h>
#include <vnet/fib/fib_entry_cover.h>
#include <vnet/fib/fib_internal.h>
#include <vnet/fib/ip4_fib.h>
#include <vnet/fib/ip6_fib.h>
#include <vnet/fib/mpls_fib.h>

const static char * fib_table_flags_strings[] = FIB_TABLE_ATTRIBUTES;

fib_table_t *
fib_table_get (fib_node_index_t index,
	       fib_protocol_t proto)
{
    switch (proto)
    {
    case FIB_PROTOCOL_IP4:
	return (pool_elt_at_index(ip4_main.fibs, index));
    case FIB_PROTOCOL_IP6:
	return (pool_elt_at_index(ip6_main.fibs, index));
    case FIB_PROTOCOL_MPLS:
	return (pool_elt_at_index(mpls_main.fibs, index));
    }
    ASSERT(0);
    return (NULL);
}

static inline fib_node_index_t
fib_table_lookup_i (fib_table_t *fib_table,
		    const fib_prefix_t *prefix)
{
    switch (prefix->fp_proto)
    {
    case FIB_PROTOCOL_IP4:
	return (ip4_fib_table_lookup(ip4_fib_get(fib_table->ft_index),
				     &prefix->fp_addr.ip4,
				     prefix->fp_len));
    case FIB_PROTOCOL_IP6:
	return (ip6_fib_table_lookup(fib_table->ft_index,
				     &prefix->fp_addr.ip6,
				     prefix->fp_len));
    case FIB_PROTOCOL_MPLS:
	return (mpls_fib_table_lookup(mpls_fib_get(fib_table->ft_index),
				      prefix->fp_label,
				      prefix->fp_eos));
    }
    return (FIB_NODE_INDEX_INVALID);
}

fib_node_index_t
fib_table_lookup (u32 fib_index,
		  const fib_prefix_t *prefix)
{
    return (fib_table_lookup_i(fib_table_get(fib_index, prefix->fp_proto), prefix));
}

static inline fib_node_index_t
fib_table_lookup_exact_match_i (const fib_table_t *fib_table,
				const fib_prefix_t *prefix)
{
    switch (prefix->fp_proto)
    {
    case FIB_PROTOCOL_IP4:
	return (ip4_fib_table_lookup_exact_match(ip4_fib_get(fib_table->ft_index),
						 &prefix->fp_addr.ip4,
						 prefix->fp_len));
    case FIB_PROTOCOL_IP6:
	return (ip6_fib_table_lookup_exact_match(fib_table->ft_index,
						 &prefix->fp_addr.ip6,
						 prefix->fp_len));
    case FIB_PROTOCOL_MPLS:
	return (mpls_fib_table_lookup(mpls_fib_get(fib_table->ft_index),
				      prefix->fp_label,
				      prefix->fp_eos));
    }
    return (FIB_NODE_INDEX_INVALID);
}

fib_node_index_t
fib_table_lookup_exact_match (u32 fib_index,
			      const fib_prefix_t *prefix)
{
    return (fib_table_lookup_exact_match_i(fib_table_get(fib_index,
							 prefix->fp_proto),
					   prefix));
}

static fib_node_index_t
fib_table_get_less_specific_i (fib_table_t *fib_table,
			       const fib_prefix_t *prefix)
{
    fib_prefix_t pfx;

    pfx = *prefix;

    if (FIB_PROTOCOL_MPLS == pfx.fp_proto)
    {
	return (FIB_NODE_INDEX_INVALID);
    }

    /*
     * in the absence of a tree structure for the table that allows for an O(1)
     * parent get, a cheeky way to find the cover is to LPM for the prefix with
     * mask-1.
     * there should always be a cover, though it may be the default route. the
     * default route's cover is the default route.
     */
    if (pfx.fp_len != 0) {
	pfx.fp_len -= 1;
    }

    return (fib_table_lookup_i(fib_table, &pfx));    
}

fib_node_index_t
fib_table_get_less_specific (u32 fib_index,
			     const fib_prefix_t *prefix)
{
    return (fib_table_get_less_specific_i(fib_table_get(fib_index,
							prefix->fp_proto),
					  prefix));
}

static void
fib_table_entry_remove (fib_table_t *fib_table,
			const fib_prefix_t *prefix,
			fib_node_index_t fib_entry_index)
{
    vlib_smp_unsafe_warning();

    fib_table->ft_total_route_counts--;

    switch (prefix->fp_proto)
    {
    case FIB_PROTOCOL_IP4:
	ip4_fib_table_entry_remove(ip4_fib_get(fib_table->ft_index),
				   &prefix->fp_addr.ip4,
				   prefix->fp_len);
	break;
    case FIB_PROTOCOL_IP6:
	ip6_fib_table_entry_remove(fib_table->ft_index,
				   &prefix->fp_addr.ip6,
				   prefix->fp_len);
	break;
    case FIB_PROTOCOL_MPLS:
	mpls_fib_table_entry_remove(mpls_fib_get(fib_table->ft_index),
				    prefix->fp_label,
				    prefix->fp_eos);
	break;
    }

    fib_entry_unlock(fib_entry_index);
}

static void
fib_table_post_insert_actions (fib_table_t *fib_table,
			       const fib_prefix_t *prefix,
			       fib_node_index_t fib_entry_index)
{
    fib_node_index_t fib_entry_cover_index;

    /*
     * no cover relationships in the MPLS FIB
     */
    if (FIB_PROTOCOL_MPLS == prefix->fp_proto)
	return;

    /*
     * find  the covering entry
     */
    fib_entry_cover_index = fib_table_get_less_specific_i(fib_table, prefix);
    /*
     * the indicies are the same when the default route is first added
     */
    if (fib_entry_cover_index != fib_entry_index)
    {
        /*
         * push any inherting sources from the cover onto the covered
         */
        fib_entry_inherit(fib_entry_cover_index,
                          fib_entry_index);

        /*
         * inform the covering entry that a new more specific
         * has been inserted beneath it.
         * If the prefix that has been inserted is a host route
         * then it is not possible that it will be the cover for any
         * other entry, so we can elide the walk. This is particularly
         * beneficial since there are often many host entries sharing the
         * same cover (i.e. ADJ or RR sourced entries).
         */
        if (!fib_entry_is_host(fib_entry_index))
        {
            fib_entry_cover_change_notify(fib_entry_cover_index,
                                          fib_entry_index);
        }
    }
}

static void
fib_table_entry_insert (fib_table_t *fib_table,
			const fib_prefix_t *prefix,
			fib_node_index_t fib_entry_index)
{
    vlib_smp_unsafe_warning();

    fib_entry_lock(fib_entry_index);
    fib_table->ft_total_route_counts++;

    switch (prefix->fp_proto)
    {
    case FIB_PROTOCOL_IP4:
	ip4_fib_table_entry_insert(ip4_fib_get(fib_table->ft_index),
				   &prefix->fp_addr.ip4,
				   prefix->fp_len,
				   fib_entry_index);
	break;
    case FIB_PROTOCOL_IP6:
	ip6_fib_table_entry_insert(fib_table->ft_index,
				   &prefix->fp_addr.ip6,
				   prefix->fp_len,
				   fib_entry_index);
	break;
    case FIB_PROTOCOL_MPLS:
	mpls_fib_table_entry_insert(mpls_fib_get(fib_table->ft_index),
				    prefix->fp_label,
				    prefix->fp_eos,
				    fib_entry_index);
	break;
    }

    fib_table_post_insert_actions(fib_table, prefix, fib_entry_index);
}

void
fib_table_fwding_dpo_update (u32 fib_index,
			     const fib_prefix_t *prefix,
			     const dpo_id_t *dpo)
{
    vlib_smp_unsafe_warning();

    switch (prefix->fp_proto)
    {
    case FIB_PROTOCOL_IP4:
	return (ip4_fib_table_fwding_dpo_update(ip4_fib_get(fib_index),
						&prefix->fp_addr.ip4,
						prefix->fp_len,
						dpo));
    case FIB_PROTOCOL_IP6:
	return (ip6_fib_table_fwding_dpo_update(fib_index,
						&prefix->fp_addr.ip6,
						prefix->fp_len,
						dpo));
    case FIB_PROTOCOL_MPLS:
	return (mpls_fib_forwarding_table_update(mpls_fib_get(fib_index),
						 prefix->fp_label,
						 prefix->fp_eos,
						 dpo));
    }
}

void
fib_table_fwding_dpo_remove (u32 fib_index,
			     const fib_prefix_t *prefix,
			     const dpo_id_t *dpo)
{
    vlib_smp_unsafe_warning();

    switch (prefix->fp_proto)
    {
    case FIB_PROTOCOL_IP4:
	return (ip4_fib_table_fwding_dpo_remove(ip4_fib_get(fib_index),
						&prefix->fp_addr.ip4,
						prefix->fp_len,
						dpo,
                                                fib_table_get_less_specific(fib_index,
                                                                            prefix)));
    case FIB_PROTOCOL_IP6:
	return (ip6_fib_table_fwding_dpo_remove(fib_index,
						&prefix->fp_addr.ip6,
						prefix->fp_len,
						dpo));
    case FIB_PROTOCOL_MPLS:
	return (mpls_fib_forwarding_table_reset(mpls_fib_get(fib_index),
						prefix->fp_label,
						prefix->fp_eos));
    }
}

static void
fib_table_source_count_inc (fib_table_t *fib_table,
                            fib_source_t source)
{
    vec_validate (fib_table->ft_src_route_counts, source);
    fib_table->ft_src_route_counts[source]++;
}

static void
fib_table_source_count_dec (fib_table_t *fib_table,
                            fib_source_t source)
{
    vec_validate (fib_table->ft_src_route_counts, source);
    fib_table->ft_src_route_counts[source]--;
}

fib_node_index_t
fib_table_entry_special_dpo_add (u32 fib_index,
                                 const fib_prefix_t *prefix,
                                 fib_source_t source,
                                 fib_entry_flag_t flags,
                                 const dpo_id_t *dpo)
{
    fib_node_index_t fib_entry_index;
    fib_table_t *fib_table;

    fib_table = fib_table_get(fib_index, prefix->fp_proto);
    fib_entry_index = fib_table_lookup_exact_match_i(fib_table, prefix);

    if (FIB_NODE_INDEX_INVALID == fib_entry_index)
    {
	fib_entry_index = fib_entry_create_special(fib_index, prefix,
						   source, flags,
						   dpo);

	fib_table_entry_insert(fib_table, prefix, fib_entry_index);
        fib_table_source_count_inc(fib_table, source);
    }
    else
    {
        int was_sourced;

        was_sourced = fib_entry_is_sourced(fib_entry_index, source);
	fib_entry_special_add(fib_entry_index, source, flags, dpo);

        if (was_sourced != fib_entry_is_sourced(fib_entry_index, source))
        {
        fib_table_source_count_inc(fib_table, source);
        }
    }


    return (fib_entry_index);
}

fib_node_index_t
fib_table_entry_special_dpo_update (u32 fib_index,
				    const fib_prefix_t *prefix,
				    fib_source_t source,
				    fib_entry_flag_t flags,
				    const dpo_id_t *dpo)
{
    fib_node_index_t fib_entry_index;
    fib_table_t *fib_table;

    fib_table = fib_table_get(fib_index, prefix->fp_proto);
    fib_entry_index = fib_table_lookup_exact_match_i(fib_table, prefix);

    if (FIB_NODE_INDEX_INVALID == fib_entry_index)
    {
	fib_entry_index = fib_entry_create_special(fib_index, prefix,
						   source, flags,
						   dpo);

	fib_table_entry_insert(fib_table, prefix, fib_entry_index);
        fib_table_source_count_inc(fib_table, source);
    }
    else
    {
        int was_sourced;

        was_sourced = fib_entry_is_sourced(fib_entry_index, source);

	if (was_sourced)
	    fib_entry_special_update(fib_entry_index, source, flags, dpo);
	else
	    fib_entry_special_add(fib_entry_index, source, flags, dpo);

        if (was_sourced != fib_entry_is_sourced(fib_entry_index, source))
        {
            fib_table_source_count_inc(fib_table, source);
        }
    }

    return (fib_entry_index);
}

fib_node_index_t
fib_table_entry_special_add (u32 fib_index,
			     const fib_prefix_t *prefix,
			     fib_source_t source,
			     fib_entry_flag_t flags)
{
    fib_node_index_t fib_entry_index;
    dpo_id_t tmp_dpo = DPO_INVALID;

    dpo_copy(&tmp_dpo, drop_dpo_get(fib_proto_to_dpo(prefix->fp_proto)));
 
    fib_entry_index = fib_table_entry_special_dpo_add(fib_index, prefix, source,
                                                      flags, &tmp_dpo);

    dpo_unlock(&tmp_dpo);

    return (fib_entry_index);
}

void
fib_table_entry_special_remove (u32 fib_index,
				const fib_prefix_t *prefix,
				fib_source_t source)
{
    /*
     * 1 is it present
     *   yes => remove source
     *    2 - is it still sourced?
     *      no => cover walk
     */
    fib_node_index_t fib_entry_index;
    fib_table_t *fib_table;

    fib_table = fib_table_get(fib_index, prefix->fp_proto);
    fib_entry_index = fib_table_lookup_exact_match_i(fib_table, prefix);

    if (FIB_NODE_INDEX_INVALID == fib_entry_index)
    {
	/*
	 * removing an etry that does not exist. i'll allow it.
	 */
    }
    else
    {
	fib_entry_src_flag_t src_flag;
        int was_sourced;

	/*
	 * don't nobody go nowhere
	 */
	fib_entry_lock(fib_entry_index);
        was_sourced = fib_entry_is_sourced(fib_entry_index, source);

	src_flag = fib_entry_special_remove(fib_entry_index, source);

	if (!(FIB_ENTRY_SRC_FLAG_ADDED & src_flag))
	{
	    /*
	     * last source gone. remove from the table
	     */
	    fib_table_entry_remove(fib_table, prefix, fib_entry_index);

	    /*
	     * now the entry is no longer in the table, we can
	     * inform the entries that it covers to re-calculate their cover
	     */
	    fib_entry_cover_change_notify(fib_entry_index,
					  FIB_NODE_INDEX_INVALID);
	}
	/*
	 * else
	 *   still has sources, leave it be.
	 */
        if (was_sourced != fib_entry_is_sourced(fib_entry_index, source))
        {
            fib_table_source_count_dec(fib_table, source);
        }

	fib_entry_unlock(fib_entry_index);
    }
}

/**
 * fib_table_route_path_fixup
 *
 * Convert attached hosts to attached next-hops.
 * 
 * This special case is required because an attached path will link to a
 * glean, and the FIB entry will have the interface or API/CLI source. When
 * the ARP/ND process is completes then that source (which will provide a
 * complete adjacency) will be lower priority and so the FIB entry will
 * remain linked to a glean and traffic will never reach the hosts. For
 * an ATTAHCED_HOST path we can link the path directly to the [incomplete]
 * adjacency.
 */
static void
fib_table_route_path_fixup (const fib_prefix_t *prefix,
                            fib_entry_flag_t *eflags,
			    fib_route_path_t *path)
{
    /*
     * not all zeros next hop &&
     * is recursive path &&
     * nexthop is same as the route's address
     */
    if ((!ip46_address_is_zero(&path->frp_addr)) &&
        (~0 == path->frp_sw_if_index) &&
        (0 == ip46_address_cmp(&path->frp_addr, &prefix->fp_addr)))
    {
        /* Prefix recurses via itself */
	path->frp_flags |= FIB_ROUTE_PATH_DROP;
    }
    if (!(path->frp_flags & FIB_ROUTE_PATH_LOCAL) &&
        fib_prefix_is_host(prefix) &&
	ip46_address_is_zero(&path->frp_addr) &&
	path->frp_sw_if_index != ~0 &&
        path->frp_proto != DPO_PROTO_ETHERNET)
    {
	path->frp_addr = prefix->fp_addr;
        path->frp_flags |= FIB_ROUTE_PATH_ATTACHED;
    }
    else if ((*eflags & FIB_ENTRY_FLAG_CONNECTED) &&
             !(*eflags & FIB_ENTRY_FLAG_LOCAL))
    {
        if (ip46_address_is_zero(&path->frp_addr))
        {
            path->frp_flags |= FIB_ROUTE_PATH_GLEAN;
            fib_prefix_normalize(prefix, &path->frp_connected);
        }
    }
    else if (fib_route_path_is_attached(path))
    {
        path->frp_flags |= FIB_ROUTE_PATH_GLEAN;
        /*
         * attached prefixes are not suitable as the source of ARP requests
         * so don't save the prefix in the glean adj
         */
        clib_memset(&path->frp_connected, 0, sizeof(path->frp_connected));
    }
    if (*eflags & FIB_ENTRY_FLAG_DROP)
    {
	path->frp_flags |= FIB_ROUTE_PATH_DROP;
    }
    if (*eflags & FIB_ENTRY_FLAG_LOCAL)
    {
	path->frp_flags |= FIB_ROUTE_PATH_LOCAL;
    }
    if (*eflags & FIB_ENTRY_FLAG_EXCLUSIVE)
    {
	path->frp_flags |= FIB_ROUTE_PATH_EXCLUSIVE;
    }
    if (path->frp_flags & FIB_ROUTE_PATH_LOCAL)
    {
        *eflags |= FIB_ENTRY_FLAG_LOCAL;

        if (path->frp_sw_if_index != ~0)
        {
            *eflags |= FIB_ENTRY_FLAG_CONNECTED;
        }
    }
}

fib_node_index_t
fib_table_entry_path_add (u32 fib_index,
			  const fib_prefix_t *prefix,
			  fib_source_t source,
			  fib_entry_flag_t flags,
			  dpo_proto_t next_hop_proto,
			  const ip46_address_t *next_hop,
			  u32 next_hop_sw_if_index,
			  u32 next_hop_fib_index,
			  u32 next_hop_weight,
			  fib_mpls_label_t *next_hop_labels,
			  fib_route_path_flags_t path_flags)
{
    fib_route_path_t path = {
	.frp_proto = next_hop_proto,
	.frp_addr = (NULL == next_hop? zero_addr : *next_hop),
	.frp_sw_if_index = next_hop_sw_if_index,
	.frp_fib_index = next_hop_fib_index,
	.frp_weight = next_hop_weight,
	.frp_flags = path_flags,
        .frp_rpf_id = INDEX_INVALID,
	.frp_label_stack = next_hop_labels,
    };
    fib_node_index_t fib_entry_index;
    fib_route_path_t *paths = NULL;

    vec_add1(paths, path);

    fib_entry_index = fib_table_entry_path_add2(fib_index, prefix,
						source, flags, paths);

    vec_free(paths);
    return (fib_entry_index);
}

static int
fib_route_path_cmp_for_sort (void * v1,
			     void * v2)
{
    return (fib_route_path_cmp(v1, v2));
}

fib_node_index_t
fib_table_entry_path_add2 (u32 fib_index,
			   const fib_prefix_t *prefix,
			   fib_source_t source,
			   fib_entry_flag_t flags,
			   fib_route_path_t *rpaths)
{
    fib_node_index_t fib_entry_index;
    fib_table_t *fib_table;
    u32 ii;

    fib_table = fib_table_get(fib_index, prefix->fp_proto);
    fib_entry_index = fib_table_lookup_exact_match_i(fib_table, prefix);

    for (ii = 0; ii < vec_len(rpaths); ii++)
    {
	fib_table_route_path_fixup(prefix, &flags, &rpaths[ii]);
    }
    /*
     * sort the paths provided by the control plane. this means
     * the paths and the extension on the entry will be sorted.
     */
    vec_sort_with_function(rpaths, fib_route_path_cmp_for_sort);

    if (FIB_NODE_INDEX_INVALID == fib_entry_index)
    {
	fib_entry_index = fib_entry_create(fib_index, prefix,
					   source, flags,
					   rpaths);

	fib_table_entry_insert(fib_table, prefix, fib_entry_index);
        fib_table_source_count_inc(fib_table, source);
    }
    else
    {
        int was_sourced;

        was_sourced = fib_entry_is_sourced(fib_entry_index, source);
	fib_entry_path_add(fib_entry_index, source, flags, rpaths);;

        if (was_sourced != fib_entry_is_sourced(fib_entry_index, source))
        {
            fib_table_source_count_inc(fib_table, source);
        }
    }

    return (fib_entry_index);
}

void
fib_table_entry_path_remove2 (u32 fib_index,
			      const fib_prefix_t *prefix,
			      fib_source_t source,
			      fib_route_path_t *rpaths)
{
    /*
     * 1 is it present
     *   yes => remove source
     *    2 - is it still sourced?
     *      no => cover walk
     */
    fib_node_index_t fib_entry_index;
    fib_route_path_t *rpath;
    fib_table_t *fib_table;

    fib_table = fib_table_get(fib_index, prefix->fp_proto);
    fib_entry_index = fib_table_lookup_exact_match_i(fib_table, prefix);

    if (FIB_NODE_INDEX_INVALID == fib_entry_index)
    {
	/*
	 * removing an etry that does not exist. i'll allow it.
	 */
    }
    else
    {
	fib_entry_src_flag_t src_flag;
        int was_sourced;

        /*
         * if it's not sourced, then there's nowt to remove
         */
        was_sourced = fib_entry_is_sourced(fib_entry_index, source);
        if (!was_sourced)
        {
            return;
        }

        /*
	 * don't nobody go nowhere
	 */
	fib_entry_lock(fib_entry_index);

        vec_foreach(rpath, rpaths)
        {
            fib_entry_flag_t eflags;

            eflags = fib_entry_get_flags_for_source(fib_entry_index,
                                                    source);
            fib_table_route_path_fixup(prefix, &eflags, rpath);
        }

	src_flag = fib_entry_path_remove(fib_entry_index, source, rpaths);

	if (!(FIB_ENTRY_SRC_FLAG_ADDED & src_flag))
	{
	    /*
	     * last source gone. remove from the table
	     */
	    fib_table_entry_remove(fib_table, prefix, fib_entry_index);

	    /*
	     * now the entry is no longer in the table, we can
	     * inform the entries that it covers to re-calculate their cover
	     */
	    fib_entry_cover_change_notify(fib_entry_index,
					  FIB_NODE_INDEX_INVALID);
	}
	/*
	 * else
	 *   still has sources, leave it be.
	 */
        if (was_sourced != fib_entry_is_sourced(fib_entry_index, source))
        {
            fib_table_source_count_dec(fib_table, source);
        }

	fib_entry_unlock(fib_entry_index);
    }
}

void
fib_table_entry_path_remove (u32 fib_index,
			     const fib_prefix_t *prefix,
			     fib_source_t source,
			     dpo_proto_t next_hop_proto,
			     const ip46_address_t *next_hop,
			     u32 next_hop_sw_if_index,
			     u32 next_hop_fib_index,
			     u32 next_hop_weight,
			     fib_route_path_flags_t path_flags)
{
    /*
     * 1 is it present
     *   yes => remove source
     *    2 - is it still sourced?
     *      no => cover walk
     */
    fib_route_path_t path = {
	.frp_proto = next_hop_proto,
	.frp_addr = (NULL == next_hop? zero_addr : *next_hop),
	.frp_sw_if_index = next_hop_sw_if_index,
	.frp_fib_index = next_hop_fib_index,
	.frp_weight = next_hop_weight,
	.frp_flags = path_flags,
    };
    fib_route_path_t *paths = NULL;

    vec_add1(paths, path);

    fib_table_entry_path_remove2(fib_index, prefix, source, paths);

    vec_free(paths);
}

fib_node_index_t
fib_table_entry_update (u32 fib_index,
			const fib_prefix_t *prefix,
			fib_source_t source,
			fib_entry_flag_t flags,
			fib_route_path_t *paths)
{
    fib_node_index_t fib_entry_index;
    fib_table_t *fib_table;
    u32 ii;

    fib_table = fib_table_get(fib_index, prefix->fp_proto);
    fib_entry_index = fib_table_lookup_exact_match_i(fib_table, prefix);

    for (ii = 0; ii < vec_len(paths); ii++)
    {
	fib_table_route_path_fixup(prefix, &flags, &paths[ii]);
    }
    /*
     * sort the paths provided by the control plane. this means
     * the paths and the extension on the entry will be sorted.
     */
    vec_sort_with_function(paths, fib_route_path_cmp_for_sort);

    if (FIB_NODE_INDEX_INVALID == fib_entry_index)
    {
    	fib_entry_index = fib_entry_create(fib_index, prefix,
    					   source, flags,
					   paths);

    	fib_table_entry_insert(fib_table, prefix, fib_entry_index);
        fib_table_source_count_inc(fib_table, source);
    }
    else
    {
        int was_sourced;

        was_sourced = fib_entry_is_sourced(fib_entry_index, source);
    	fib_entry_update(fib_entry_index, source, flags, paths);

        if (was_sourced != fib_entry_is_sourced(fib_entry_index, source))
        {
            fib_table_source_count_inc(fib_table, source);
        }
    }

    return (fib_entry_index);
}

fib_node_index_t
fib_table_entry_update_one_path (u32 fib_index,
				 const fib_prefix_t *prefix,
				 fib_source_t source,
				 fib_entry_flag_t flags,
				 dpo_proto_t next_hop_proto,
				 const ip46_address_t *next_hop,
				 u32 next_hop_sw_if_index,
				 u32 next_hop_fib_index,
				 u32 next_hop_weight,
				 fib_mpls_label_t *next_hop_labels,
				 fib_route_path_flags_t path_flags)
{
    fib_node_index_t fib_entry_index;
    fib_route_path_t path = {
	.frp_proto = next_hop_proto,
	.frp_addr = (NULL == next_hop? zero_addr : *next_hop),
	.frp_sw_if_index = next_hop_sw_if_index,
	.frp_fib_index = next_hop_fib_index,
	.frp_weight = next_hop_weight,
	.frp_flags = path_flags,
	.frp_label_stack = next_hop_labels,
    };
    fib_route_path_t *paths = NULL;

    vec_add1(paths, path);

    fib_entry_index = 
	fib_table_entry_update(fib_index, prefix, source, flags, paths);

    vec_free(paths);

    return (fib_entry_index);
}

static void
fib_table_entry_delete_i (u32 fib_index,
			  fib_node_index_t fib_entry_index,
			  const fib_prefix_t *prefix,
			  fib_source_t source)
{
    fib_entry_src_flag_t src_flag;
    fib_table_t *fib_table;
    int was_sourced;

    fib_table = fib_table_get(fib_index, prefix->fp_proto);
    was_sourced = fib_entry_is_sourced(fib_entry_index, source);

    /*
     * don't nobody go nowhere
     */
    fib_entry_lock(fib_entry_index);

    src_flag = fib_entry_delete(fib_entry_index, source);

    if (!(FIB_ENTRY_SRC_FLAG_ADDED & src_flag))
    {
	/*
	 * last source gone. remove from the table
	 */
	fib_table_entry_remove(fib_table, prefix, fib_entry_index);

	/*
	 * now the entry is no longer in the table, we can
	 * inform the entries that it covers to re-calculate their cover
	 */
	fib_entry_cover_change_notify(fib_entry_index,
				      FIB_NODE_INDEX_INVALID);
    }
    /*
     * else
     *   still has sources, leave it be.
     */
    if (was_sourced != fib_entry_is_sourced(fib_entry_index, source))
    {
        fib_table_source_count_dec(fib_table, source);
    }

    fib_entry_unlock(fib_entry_index);
}

void
fib_table_entry_delete (u32 fib_index,
			const fib_prefix_t *prefix,
			fib_source_t source)
{
    fib_node_index_t fib_entry_index;

    fib_entry_index = fib_table_lookup_exact_match(fib_index, prefix);

    if (FIB_NODE_INDEX_INVALID == fib_entry_index)
    {
	/*
	 * removing an etry that does not exist.
	 * i'll allow it, but i won't like it.
	 */
        if (0)
            clib_warning("%U not in FIB", format_fib_prefix, prefix);
    }
    else
    {
	fib_table_entry_delete_i(fib_index, fib_entry_index, prefix, source);
    }
}

void
fib_table_entry_delete_index (fib_node_index_t fib_entry_index,
			      fib_source_t source)
{
    const fib_prefix_t *prefix;

    prefix = fib_entry_get_prefix(fib_entry_index);

    fib_table_entry_delete_i(fib_entry_get_fib_index(fib_entry_index),
                             fib_entry_index, prefix, source);
}

u32
fib_table_entry_get_stats_index (u32 fib_index,
                                 const fib_prefix_t *prefix)
{
    return (fib_entry_get_stats_index(
                fib_table_lookup_exact_match(fib_index, prefix)));
}

fib_node_index_t
fib_table_entry_local_label_add (u32 fib_index,
				 const fib_prefix_t *prefix,
				 mpls_label_t label)
{
    fib_node_index_t fib_entry_index;
 
    fib_entry_index = fib_table_lookup_exact_match(fib_index, prefix);

    if (FIB_NODE_INDEX_INVALID == fib_entry_index ||
	!fib_entry_is_sourced(fib_entry_index, FIB_SOURCE_MPLS))
    {
	/*
	 * only source the prefix once. this allows the label change
	 * operation to work
	 */
	fib_entry_index = fib_table_entry_special_dpo_add(fib_index, prefix,
							  FIB_SOURCE_MPLS,
							  FIB_ENTRY_FLAG_NONE,
							  NULL);
    }

    fib_entry_set_source_data(fib_entry_index, FIB_SOURCE_MPLS, &label);

    return (fib_entry_index);
}

void
fib_table_entry_local_label_remove (u32 fib_index,
				    const fib_prefix_t *prefix,
				    mpls_label_t label)
{
    fib_node_index_t fib_entry_index;
    const void *data;
    mpls_label_t pl;

    fib_entry_index = fib_table_lookup_exact_match(fib_index, prefix);

    if (FIB_NODE_INDEX_INVALID == fib_entry_index)
        return;

    data = fib_entry_get_source_data(fib_entry_index, FIB_SOURCE_MPLS);

    if (NULL == data)
        return;

    pl = *(mpls_label_t*)data;

    if (pl != label)
        return;

    pl = MPLS_LABEL_INVALID;

    fib_entry_set_source_data(fib_entry_index, FIB_SOURCE_MPLS, &pl);
    fib_table_entry_special_remove(fib_index,
				   prefix,
				   FIB_SOURCE_MPLS);
}

u32
fib_table_get_index_for_sw_if_index (fib_protocol_t proto,
				     u32 sw_if_index)
{
    switch (proto)
    {
    case FIB_PROTOCOL_IP4:
	return (ip4_fib_table_get_index_for_sw_if_index(sw_if_index));
    case FIB_PROTOCOL_IP6:
	return (ip6_fib_table_get_index_for_sw_if_index(sw_if_index));
    case FIB_PROTOCOL_MPLS:
	return (mpls_fib_table_get_index_for_sw_if_index(sw_if_index));
    }
    return (~0);
}

flow_hash_config_t
fib_table_get_flow_hash_config (u32 fib_index,
				fib_protocol_t proto)
{
    fib_table_t *fib;

    fib = fib_table_get(fib_index, proto);

    return (fib->ft_flow_hash_config);
}

flow_hash_config_t
fib_table_get_default_flow_hash_config (fib_protocol_t proto)
{
    switch (proto)
    {
    case FIB_PROTOCOL_IP4:
    case FIB_PROTOCOL_IP6:
	return (IP_FLOW_HASH_DEFAULT);

    case FIB_PROTOCOL_MPLS:
	return (MPLS_FLOW_HASH_DEFAULT);
    }

    ASSERT(0);
    return (IP_FLOW_HASH_DEFAULT);
}

/**
 * @brief Table set flow hash config context.
 */
typedef struct fib_table_set_flow_hash_config_ctx_t_
{
    /**
     * the flow hash config to set
     */
    flow_hash_config_t hash_config;
} fib_table_set_flow_hash_config_ctx_t;

static fib_table_walk_rc_t
fib_table_set_flow_hash_config_cb (fib_node_index_t fib_entry_index,
                                   void *arg)
{
    fib_table_set_flow_hash_config_ctx_t *ctx = arg;

    fib_entry_set_flow_hash_config(fib_entry_index, ctx->hash_config);

    return (FIB_TABLE_WALK_CONTINUE);
}

void
fib_table_set_flow_hash_config (u32 fib_index,
                                fib_protocol_t proto,
                                flow_hash_config_t hash_config)
{
    fib_table_set_flow_hash_config_ctx_t ctx = {
        .hash_config = hash_config,
    };
    fib_table_t *fib;

    fib = fib_table_get(fib_index, proto);
    fib->ft_flow_hash_config = hash_config;

    fib_table_walk(fib_index, proto,
                   fib_table_set_flow_hash_config_cb,
                   &ctx);
}

u32
fib_table_get_table_id_for_sw_if_index (fib_protocol_t proto,
					u32 sw_if_index)
{
    fib_table_t *fib_table;

    fib_table = fib_table_get(fib_table_get_index_for_sw_if_index(
				  proto, sw_if_index),
			      proto);

    return ((NULL != fib_table ? fib_table->ft_table_id : ~0));
}

u32
fib_table_get_table_id (u32 fib_index,
                        fib_protocol_t proto)
{
    fib_table_t *fib_table;

    fib_table = fib_table_get(fib_index, proto);

    return ((NULL != fib_table ? fib_table->ft_table_id : ~0));
}

u32
fib_table_find (fib_protocol_t proto,
		u32 table_id)
{
    switch (proto)
    {
    case FIB_PROTOCOL_IP4:
	return (ip4_fib_index_from_table_id(table_id));
    case FIB_PROTOCOL_IP6:
	return (ip6_fib_index_from_table_id(table_id));
    case FIB_PROTOCOL_MPLS:
	return (mpls_fib_index_from_table_id(table_id));
    }
    return (~0);
}

static u32
fib_table_find_or_create_and_lock_i (fib_protocol_t proto,
                                     u32 table_id,
                                     fib_source_t src,
                                     const u8 *name)
{
    fib_table_t *fib_table;
    fib_node_index_t fi;

    switch (proto)
    {
    case FIB_PROTOCOL_IP4:
	fi = ip4_fib_table_find_or_create_and_lock(table_id, src);
        break;
    case FIB_PROTOCOL_IP6:
	fi = ip6_fib_table_find_or_create_and_lock(table_id, src);
        break;
    case FIB_PROTOCOL_MPLS:
	fi = mpls_fib_table_find_or_create_and_lock(table_id, src);
        break;
    default:
        return (~0);        
    }

    fib_table = fib_table_get(fi, proto);

    if (NULL == fib_table->ft_desc)
    {
        if (name && name[0])
        {
            fib_table->ft_desc = format(NULL, "%s", name);
        }
        else
        {
            fib_table->ft_desc = format(NULL, "%U-VRF:%d",
                                        format_fib_protocol, proto,
                                        table_id);
        }
    }

    return (fi);
}

u32
fib_table_find_or_create_and_lock (fib_protocol_t proto,
				   u32 table_id,
                                   fib_source_t src)
{
    return (fib_table_find_or_create_and_lock_i(proto, table_id,
                                                src, NULL));
}

u32
fib_table_find_or_create_and_lock_w_name (fib_protocol_t proto,
                                          u32 table_id,
                                          fib_source_t src,
                                          const u8 *name)
{
    return (fib_table_find_or_create_and_lock_i(proto, table_id,
                                                src, name));
}

u32
fib_table_create_and_lock (fib_protocol_t proto,
                           fib_source_t src,
                           const char *const fmt,
                           ...)
{
    fib_table_t *fib_table;
    fib_node_index_t fi;
    va_list ap;


    switch (proto)
    {
    case FIB_PROTOCOL_IP4:
	fi = ip4_fib_table_create_and_lock(src);
        break;
    case FIB_PROTOCOL_IP6:
	fi = ip6_fib_table_create_and_lock(src, FIB_TABLE_FLAG_NONE, NULL);
        break;
     case FIB_PROTOCOL_MPLS:
	fi = mpls_fib_table_create_and_lock(src);
        break;
   default:
        return (~0);        
    }

    fib_table = fib_table_get(fi, proto);

    va_start(ap, fmt);

    fib_table->ft_desc = va_format(fib_table->ft_desc, fmt, &ap);

    va_end(ap);
    return (fi);
}

static void
fib_table_destroy (fib_table_t *fib_table)
{
    vec_free(fib_table->ft_desc);

    switch (fib_table->ft_proto)
    {
    case FIB_PROTOCOL_IP4:
	ip4_fib_table_destroy(fib_table->ft_index);
	break;
    case FIB_PROTOCOL_IP6:
	ip6_fib_table_destroy(fib_table->ft_index);
	break;
    case FIB_PROTOCOL_MPLS:
	mpls_fib_table_destroy(fib_table->ft_index);
	break;
    }
}

void
fib_table_walk (u32 fib_index,
                fib_protocol_t proto,
                fib_table_walk_fn_t fn,
                void *ctx)
{
    switch (proto)
    {
    case FIB_PROTOCOL_IP4:
	ip4_fib_table_walk(ip4_fib_get(fib_index), fn, ctx);
	break;
    case FIB_PROTOCOL_IP6:
	ip6_fib_table_walk(fib_index, fn, ctx);
	break;
    case FIB_PROTOCOL_MPLS:
	mpls_fib_table_walk(mpls_fib_get(fib_index), fn, ctx);
	break;
    }
}

typedef struct fib_table_walk_w_src_ctx_t_
{
    fib_table_walk_fn_t fn;
    void *data;
    fib_source_t src;
} fib_table_walk_w_src_cxt_t;

static fib_table_walk_rc_t
fib_table_walk_w_src_cb (fib_node_index_t fei,
                         void *arg)
{
    fib_table_walk_w_src_cxt_t *ctx = arg;

    if (ctx->src == fib_entry_get_best_source(fei))
    {
        return (ctx->fn(fei, ctx->data));
    }
    return (FIB_TABLE_WALK_CONTINUE);
}

void
fib_table_walk_w_src (u32 fib_index,
                      fib_protocol_t proto,
                      fib_source_t src,
                      fib_table_walk_fn_t fn,
                      void *data)
{
    fib_table_walk_w_src_cxt_t ctx = {
        .fn = fn,
        .src = src,
        .data = data,
    };

    fib_table_walk(fib_index, proto, fib_table_walk_w_src_cb, &ctx);
}

void
fib_table_sub_tree_walk (u32 fib_index,
                         fib_protocol_t proto,
                         const fib_prefix_t *root,
                         fib_table_walk_fn_t fn,
                         void *ctx)
{
    switch (proto)
    {
    case FIB_PROTOCOL_IP4:
	ip4_fib_table_sub_tree_walk(ip4_fib_get(fib_index), root, fn, ctx);
	break;
    case FIB_PROTOCOL_IP6:
	ip6_fib_table_sub_tree_walk(fib_index, root, fn, ctx);
	break;
    case FIB_PROTOCOL_MPLS:
	break;
    }
}

static void
fib_table_lock_dec (fib_table_t *fib_table,
                    fib_source_t source)
{
    vec_validate(fib_table->ft_locks, source);

    ASSERT(fib_table->ft_locks[source] > 0);
    fib_table->ft_locks[source]--;
    fib_table->ft_total_locks--;
}

static void
fib_table_lock_inc (fib_table_t *fib_table,
                    fib_source_t source)
{
    vec_validate(fib_table->ft_locks, source);

    ASSERT(fib_table->ft_total_locks < (0xffffffff - 1));
    fib_table->ft_locks[source]++;
    fib_table->ft_total_locks++;
}


static void
fib_table_lock_clear (fib_table_t *fib_table,
                      fib_source_t source)
{
    vec_validate(fib_table->ft_locks, source);

    ASSERT(fib_table->ft_locks[source] <= 1);
    if (fib_table->ft_locks[source])
    {
        fib_table->ft_locks[source]--;
        fib_table->ft_total_locks--;
    }
}

static void
fib_table_lock_set (fib_table_t *fib_table,
                    fib_source_t source)
{
    vec_validate(fib_table->ft_locks, source);

    ASSERT(fib_table->ft_locks[source] <= 1);
    ASSERT(fib_table->ft_total_locks < (0xffffffff - 1));
    if (!fib_table->ft_locks[source])
    {
        fib_table->ft_locks[source]++;
        fib_table->ft_total_locks++;
    }
}

void
fib_table_unlock (u32 fib_index,
		  fib_protocol_t proto,
                  fib_source_t source)
{
    fib_table_t *fib_table;

    fib_table = fib_table_get(fib_index, proto);

    if (source == FIB_SOURCE_API || source == FIB_SOURCE_CLI)
        fib_table_lock_clear(fib_table, source);
    else
        fib_table_lock_dec(fib_table, source);

    if (0 == fib_table->ft_total_locks)
    {
        /*
         * no more lock from any source - kill it
         */
	fib_table_destroy(fib_table);
    }
}

void
fib_table_lock (u32 fib_index,
		fib_protocol_t proto,
                fib_source_t source)
{
    fib_table_t *fib_table;

    fib_table = fib_table_get(fib_index, proto);

    if (source == FIB_SOURCE_API || source == FIB_SOURCE_CLI)
        fib_table_lock_set(fib_table, source);
    else
        fib_table_lock_inc(fib_table, source);
}

u32
fib_table_get_num_entries (u32 fib_index,
			   fib_protocol_t proto,
			   fib_source_t source)
{
    fib_table_t *fib_table;

    fib_table = fib_table_get(fib_index, proto);

    return (fib_table->ft_src_route_counts[source]);
}

u8*
format_fib_table_name (u8* s, va_list* ap)
{
    fib_node_index_t fib_index = va_arg(*ap, fib_node_index_t);
    fib_protocol_t proto = va_arg(*ap, int); // int promotion
    fib_table_t *fib_table;

    fib_table = fib_table_get(fib_index, proto);

    s = format(s, "%v", fib_table->ft_desc);

    return (s);
}

u8*
format_fib_table_flags (u8 *s, va_list *args)
{
    fib_table_flags_t flags = va_arg(*args, int);
    fib_table_attribute_t attr;

    if (!flags)
    {
        return format(s, "none");
    }

    FOR_EACH_FIB_TABLE_ATTRIBUTE(attr) {
        if (1 << attr & flags) {
            s = format(s, "%s", fib_table_flags_strings[attr]);
        }
    }

    return (s);
}

/**
 * @brief Table flush context. Store the indicies of matching FIB entries
 * that need to be removed.
 */
typedef struct fib_table_flush_ctx_t_
{
    /**
     * The list of entries to flush
     */
    fib_node_index_t *ftf_entries;

    /**
     * The source we are flushing
     */
    fib_source_t ftf_source;
} fib_table_flush_ctx_t;

static fib_table_walk_rc_t
fib_table_flush_cb (fib_node_index_t fib_entry_index,
                    void *arg)
{
    fib_table_flush_ctx_t *ctx = arg;

    if (fib_entry_is_sourced(fib_entry_index, ctx->ftf_source))
    {
        vec_add1(ctx->ftf_entries, fib_entry_index);
    }
    return (FIB_TABLE_WALK_CONTINUE);
}

void
fib_table_flush (u32 fib_index,
		 fib_protocol_t proto,
		 fib_source_t source)
{
    fib_node_index_t *fib_entry_index;
    fib_table_flush_ctx_t ctx = {
        .ftf_entries = NULL,
        .ftf_source = source,
    };

    fib_table_walk(fib_index, proto,
                   fib_table_flush_cb,
                   &ctx);

    vec_foreach(fib_entry_index, ctx.ftf_entries)
    {
        fib_table_entry_delete_index(*fib_entry_index, source);
    }

    vec_free(ctx.ftf_entries);
}

static fib_table_walk_rc_t
fib_table_mark_cb (fib_node_index_t fib_entry_index,
                   void *arg)
{
    fib_table_flush_ctx_t *ctx = arg;

    if (fib_entry_is_sourced(fib_entry_index, ctx->ftf_source))
    {
        fib_entry_mark(fib_entry_index, ctx->ftf_source);
    }
    return (FIB_TABLE_WALK_CONTINUE);
}

void
fib_table_mark (u32 fib_index,
                fib_protocol_t proto,
                fib_source_t source)
{
    fib_table_flush_ctx_t ctx = {
        .ftf_source = source,
    };
    fib_table_t *fib_table;

    fib_table = fib_table_get(fib_index, proto);

    fib_table->ft_epoch++;
    fib_table->ft_flags |= FIB_TABLE_FLAG_RESYNC;

    fib_table_walk(fib_index, proto,
                   fib_table_mark_cb,
                   &ctx);
}

static fib_table_walk_rc_t
fib_table_sweep_cb (fib_node_index_t fib_entry_index,
                    void *arg)
{
    fib_table_flush_ctx_t *ctx = arg;

    if (fib_entry_is_marked(fib_entry_index, ctx->ftf_source))
    {
        vec_add1(ctx->ftf_entries, fib_entry_index);
    }
    return (FIB_TABLE_WALK_CONTINUE);
}

void
fib_table_sweep (u32 fib_index,
                 fib_protocol_t proto,
                 fib_source_t source)
{
    fib_table_flush_ctx_t ctx = {
        .ftf_source = source,
    };
    fib_node_index_t *fib_entry_index;
    fib_table_t *fib_table;

    fib_table = fib_table_get(fib_index, proto);

    fib_table->ft_flags &= ~FIB_TABLE_FLAG_RESYNC;

    fib_table_walk(fib_index, proto,
                   fib_table_sweep_cb,
                   &ctx);

    vec_foreach(fib_entry_index, ctx.ftf_entries)
    {
        fib_table_entry_delete_index(*fib_entry_index, source);
    }

    vec_free(ctx.ftf_entries);
}

u8 *
format_fib_table_memory (u8 *s, va_list *args)
{
    s = format(s, "%U", format_ip4_fib_table_memory);
    s = format(s, "%U", format_ip6_fib_table_memory);
    s = format(s, "%U", format_mpls_fib_table_memory);

    return (s);
}