src/vnet/bier/bier_fmask.c - fdio/vpp - Gitiles

 /*
  * 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/fib/fib_entry.h>
 #include <vnet/fib/fib_table.h>
 #include <vnet/fib/fib_walk.h>
 #include <vnet/fib/fib_path_list.h>

 #include <vnet/bier/bier_table.h>
 #include <vnet/bier/bier_fmask.h>
 #include <vnet/bier/bier_bit_string.h>
 #include <vnet/bier/bier_disp_table.h>

 #include <vnet/mpls/mpls.h>
 #include <vnet/dpo/drop_dpo.h>
 #include <vnet/dpo/load_balance.h>

 /*
  * attributes names for formatting
  */
 static const char *const bier_fmask_attr_names[] = BIER_FMASK_ATTR_NAMES;

 /*
  * pool of BIER fmask objects
  */
 bier_fmask_t *bier_fmask_pool;

 /**
  * Stats for each BIER fmask object
  */
 vlib_combined_counter_main_t bier_fmask_counters;

 static inline index_t
 bier_fmask_get_index (const bier_fmask_t *bfm)
 {
     return (bfm - bier_fmask_pool);
 }

 static void
 bier_fmask_bits_init (bier_fmask_bits_t *bits,
                       bier_hdr_len_id_t hlid)
 {
     bits->bfmb_refs = clib_mem_alloc(sizeof(bits->bfmb_refs[0]) *
                                      bier_hdr_len_id_to_num_bits(hlid));
     clib_memset(bits->bfmb_refs,
            0,
            (sizeof(bits->bfmb_refs[0]) *
             bier_hdr_len_id_to_num_bits(hlid)));

     bits->bfmb_input_reset_string.bbs_len =
         bier_hdr_len_id_to_num_buckets(hlid);

     /*
      * The buckets are accessed in the switch path
      */
     bits->bfmb_input_reset_string.bbs_buckets =
         clib_mem_alloc_aligned(
             sizeof(bits->bfmb_input_reset_string.bbs_buckets[0]) *
             bier_hdr_len_id_to_num_buckets(hlid),
             CLIB_CACHE_LINE_BYTES);
     clib_memset(bits->bfmb_input_reset_string.bbs_buckets,
            0,
            sizeof(bits->bfmb_input_reset_string.bbs_buckets[0]) *
            bier_hdr_len_id_to_num_buckets(hlid));
 }

 static void
 bier_fmask_stack (bier_fmask_t *bfm)
 {
     dpo_id_t via_dpo = DPO_INVALID;
     fib_forward_chain_type_t fct;

     if (bfm->bfm_flags & BIER_FMASK_FLAG_MPLS)
     {
         fct = FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS;
     }
     else
     {
         fct = FIB_FORW_CHAIN_TYPE_BIER;
     }

     fib_path_list_contribute_forwarding(bfm->bfm_pl, fct,
                                         FIB_PATH_LIST_FWD_FLAG_COLLAPSE,
                                         &via_dpo);

     /*
      * If the via PL entry provides no forwarding (i.e. a drop)
      * then neither does this fmask. That way children consider this fmask
      * unresolved and other ECMP options are used instead.
      */
     if (dpo_is_drop(&via_dpo))
     {
         bfm->bfm_flags &= ~BIER_FMASK_FLAG_FORWARDING;
     }
     else
     {
         bfm->bfm_flags |= BIER_FMASK_FLAG_FORWARDING;
     }

     dpo_stack(DPO_BIER_FMASK,
               DPO_PROTO_BIER,
               &bfm->bfm_dpo,
               &via_dpo);
     dpo_reset(&via_dpo);
 }

 void
 bier_fmask_contribute_forwarding (index_t bfmi,
                                   dpo_id_t *dpo)
 {
     bier_fmask_t *bfm;

     bfm = bier_fmask_get(bfmi);

     if (bfm->bfm_flags & BIER_FMASK_FLAG_FORWARDING)
     {
         dpo_set(dpo,
                 DPO_BIER_FMASK,
                 DPO_PROTO_BIER,
                 bfmi);
     }
     else
     {
         dpo_copy(dpo, drop_dpo_get(DPO_PROTO_BIER));
     }
 }

 u32
 bier_fmask_child_add (fib_node_index_t bfmi,
                      fib_node_type_t child_type,
                      fib_node_index_t child_index)
 {
     return (fib_node_child_add(FIB_NODE_TYPE_BIER_FMASK,
                                bfmi,
                                child_type,
                                child_index));
 };

 void
 bier_fmask_child_remove (fib_node_index_t bfmi,
                          u32 sibling_index)
 {
     if (INDEX_INVALID == bfmi)
     {
         return;
     }

     fib_node_child_remove(FIB_NODE_TYPE_BIER_FMASK,
                           bfmi,
                           sibling_index);
 }

 static void
 bier_fmask_init (bier_fmask_t *bfm,
                  const bier_fmask_id_t *fmid,
                  const fib_route_path_t *rpath)
 {
     const bier_table_id_t *btid;
     fib_route_path_t *rpaths;
     mpls_label_t olabel;

     clib_memset(bfm, 0, sizeof(*bfm));

     bfm->bfm_id = clib_mem_alloc(sizeof(*bfm->bfm_id));

     fib_node_init(&bfm->bfm_node, FIB_NODE_TYPE_BIER_FMASK);
     *bfm->bfm_id = *fmid;
     dpo_reset(&bfm->bfm_dpo);
     btid = bier_table_get_id(bfm->bfm_id->bfmi_bti);
     bier_fmask_bits_init(&bfm->bfm_bits, btid->bti_hdr_len);

     if (rpath->frp_flags & FIB_ROUTE_PATH_UDP_ENCAP)
     {
         bfm->bfm_id->bfmi_nh_type = BIER_NH_UDP;
     }
     else if (ip46_address_is_zero(&(bfm->bfm_id->bfmi_nh)))
     {
         bfm->bfm_flags |= BIER_FMASK_FLAG_DISP;
     }

     if (!(bfm->bfm_flags & BIER_FMASK_FLAG_DISP))
     {
         if (NULL != rpath->frp_label_stack)
         {
             olabel = rpath->frp_label_stack[0].fml_value;
             vnet_mpls_uc_set_label(&bfm->bfm_label, olabel);
             vnet_mpls_uc_set_exp(&bfm->bfm_label, 0);
             vnet_mpls_uc_set_s(&bfm->bfm_label, 1);
             vnet_mpls_uc_set_ttl(&bfm->bfm_label, 64);
             bfm->bfm_flags |= BIER_FMASK_FLAG_MPLS;
         }
         else
         {
             bier_bift_id_t id;

             /*
              * not an MPLS label
              */
             bfm->bfm_flags &= ~BIER_FMASK_FLAG_MPLS;

             /*
              * use a label as encoded for BIFT value
              */
             id = bier_bift_id_encode(btid->bti_set,
                                      btid->bti_sub_domain,
                                      btid->bti_hdr_len);
             vnet_mpls_uc_set_label(&bfm->bfm_label, id);
             vnet_mpls_uc_set_s(&bfm->bfm_label, 1);
             vnet_mpls_uc_set_exp(&bfm->bfm_label, 0);
             vnet_mpls_uc_set_ttl(&bfm->bfm_label, 64);
         }
         bfm->bfm_label = clib_host_to_net_u32(bfm->bfm_label);
     }

     rpaths = NULL;
     vec_add1(rpaths, *rpath);
     bfm->bfm_pl = fib_path_list_create((FIB_PATH_LIST_FLAG_SHARED |
                                         FIB_PATH_LIST_FLAG_NO_URPF),
                                        rpaths);
     bfm->bfm_sibling = fib_path_list_child_add(bfm->bfm_pl,
                                                FIB_NODE_TYPE_BIER_FMASK,
                                                bier_fmask_get_index(bfm));
     vec_free(rpaths);
     bier_fmask_stack(bfm);
 }

 static void
 bier_fmask_destroy (bier_fmask_t *bfm)
 {
     clib_mem_free(bfm->bfm_bits.bfmb_refs);
     clib_mem_free(bfm->bfm_bits.bfmb_input_reset_string.bbs_buckets);

     bier_fmask_db_remove(bfm->bfm_id);
     fib_path_list_child_remove(bfm->bfm_pl,
                                bfm->bfm_sibling);
     dpo_reset(&bfm->bfm_dpo);
     clib_mem_free(bfm->bfm_id);
     pool_put(bier_fmask_pool, bfm);
 }

 void
 bier_fmask_unlock (index_t bfmi)
 {
     bier_fmask_t *bfm;

     if (INDEX_INVALID == bfmi)
     {
         return;
     }

     bfm = bier_fmask_get(bfmi);

     fib_node_unlock(&bfm->bfm_node);
 }

 void
 bier_fmask_lock (index_t bfmi)
 {
     bier_fmask_t *bfm;

     if (INDEX_INVALID == bfmi)
     {
         return;
     }

     bfm = bier_fmask_get(bfmi);

     fib_node_lock(&bfm->bfm_node);
 }

 index_t
 bier_fmask_create_and_lock (const bier_fmask_id_t *fmid,
                             const fib_route_path_t *rpath)
 {
     bier_fmask_t *bfm;
     index_t bfmi;

     pool_get_aligned(bier_fmask_pool, bfm, CLIB_CACHE_LINE_BYTES);
     bfmi = bier_fmask_get_index(bfm);

     vlib_validate_combined_counter (&(bier_fmask_counters), bfmi);
     vlib_zero_combined_counter (&(bier_fmask_counters), bfmi);

     bier_fmask_init(bfm, fmid, rpath);

     bier_fmask_lock(bfmi);

     return (bfmi);
 }

 void
 bier_fmask_link (index_t bfmi,
                  bier_bp_t bp)
 {
     bier_fmask_t *bfm;

     bfm = bier_fmask_get(bfmi);

     if (0 == bfm->bfm_bits.bfmb_refs[BIER_BP_TO_INDEX(bp)])
     {
         /*
          * 0 -> 1 transition - set the bit in the string
          */
         bier_bit_string_set_bit(&bfm->bfm_bits.bfmb_input_reset_string, bp);
     }

     ++bfm->bfm_bits.bfmb_refs[BIER_BP_TO_INDEX(bp)];
     ++bfm->bfm_bits.bfmb_count;
 }

 void
 bier_fmask_unlink (index_t bfmi,
                    bier_bp_t bp)
 {
     bier_fmask_t *bfm;

     bfm = bier_fmask_get(bfmi);

     --bfm->bfm_bits.bfmb_refs[BIER_BP_TO_INDEX(bp)];
     --bfm->bfm_bits.bfmb_count;

     if (0 == bfm->bfm_bits.bfmb_refs[BIER_BP_TO_INDEX(bp)])
     {
         /*
          * 1 -> 0 transition - clear the bit in the string
          */
         bier_bit_string_clear_bit(&bfm->bfm_bits.bfmb_input_reset_string, bp);
     }
 }

 u8*
 format_bier_fmask (u8 *s, va_list *ap)
 {
     index_t bfmi = va_arg(*ap, index_t);
     u32 indent = va_arg(*ap, u32);
     bier_fmask_attributes_t attr;
     bier_fmask_t *bfm;
     vlib_counter_t to;

     if (pool_is_free_index(bier_fmask_pool, bfmi))
     {
         return (format(s, "No BIER f-mask %d", bfmi));
     }

     bfm = bier_fmask_get(bfmi);

     s = format(s, "fmask: nh:%U bs:%U locks:%d ",
                format_ip46_address, &bfm->bfm_id->bfmi_nh, IP46_TYPE_ANY,
                format_bier_bit_string, &bfm->bfm_bits.bfmb_input_reset_string,
                bfm->bfm_node.fn_locks);
     s = format(s, "flags:");
     FOR_EACH_BIER_FMASK_ATTR(attr) {
         if ((1<<attr) & bfm->bfm_flags) {
             s = format (s, "%s,", bier_fmask_attr_names[attr]);
         }
     }
     vlib_get_combined_counter (&(bier_fmask_counters), bfmi, &to);
     s = format (s, " to:[%Ld:%Ld]]", to.packets, to.bytes);
     s = format(s, "\n");
     s = fib_path_list_format(bfm->bfm_pl, s);

     if (bfm->bfm_flags & BIER_FMASK_FLAG_MPLS)
     {
         s = format(s, "  output-label:%U",
                    format_mpls_unicast_label,
                    vnet_mpls_uc_get_label(clib_net_to_host_u32(bfm->bfm_label)));
     }
     else
     {
         s = format(s, "  output-bfit:[%U]",
                    format_bier_bift_id,
                    vnet_mpls_uc_get_label(clib_net_to_host_u32(bfm->bfm_label)));
     }
     s = format(s, "\n %U%U",
                format_white_space, indent,
                format_dpo_id, &bfm->bfm_dpo, indent+2);

     return (s);
 }

 void
 bier_fmask_get_stats (index_t bfmi, u64 * packets, u64 * bytes)
 {
   vlib_counter_t to;

   vlib_get_combined_counter (&(bier_fmask_counters), bfmi, &to);

   *packets = to.packets;
   *bytes = to.bytes;
 }

 void
 bier_fmask_encode (index_t bfmi,
                    bier_table_id_t *btid,
                    fib_route_path_t *rpath)
 {
     bier_fmask_t *bfm;

     bfm = bier_fmask_get(bfmi);
     *btid = *bier_table_get_id(bfm->bfm_id->bfmi_bti);

     clib_memset(rpath, 0, sizeof(*rpath));

     rpath->frp_sw_if_index = ~0;

     switch (bfm->bfm_id->bfmi_nh_type)
     {
     case BIER_NH_UDP:
         rpath->frp_flags = FIB_ROUTE_PATH_UDP_ENCAP;
         rpath->frp_udp_encap_id = bfm->bfm_id->bfmi_id;
         break;
     case BIER_NH_IP:
         memcpy(&rpath->frp_addr, &bfm->bfm_id->bfmi_nh,
                sizeof(rpath->frp_addr));
         break;
     }
 }

 static fib_node_t *
 bier_fmask_get_node (fib_node_index_t index)
 {
     bier_fmask_t *bfm = bier_fmask_get(index);
     return (&(bfm->bfm_node));
 }

 static bier_fmask_t*
 bier_fmask_get_from_node (fib_node_t *node)
 {
     return ((bier_fmask_t*)(((char*)node) -
                             STRUCT_OFFSET_OF(bier_fmask_t,
                                              bfm_node)));
 }

 /*
  * bier_fmask_last_lock_gone
  */
 static void
 bier_fmask_last_lock_gone (fib_node_t *node)
 {
     bier_fmask_destroy(bier_fmask_get_from_node(node));
 }

 /*
  * bier_fmask_back_walk_notify
  *
  * A back walk has reached this BIER fmask
  */
 static fib_node_back_walk_rc_t
 bier_fmask_back_walk_notify (fib_node_t *node,
                              fib_node_back_walk_ctx_t *ctx)
 {
     /*
      * re-stack the fmask on the n-eos of the via
      */
     bier_fmask_t *bfm = bier_fmask_get_from_node(node);

     bier_fmask_stack(bfm);

     /*
      * propagate further up the graph.
      * we can do this synchronously since the fan out is small.
      */
     fib_walk_sync(FIB_NODE_TYPE_BIER_FMASK, bier_fmask_get_index(bfm), ctx);

     return (FIB_NODE_BACK_WALK_CONTINUE);
 }

 /*
  * The BIER fmask's graph node virtual function table
  */
 static const fib_node_vft_t bier_fmask_vft = {
     .fnv_get = bier_fmask_get_node,
     .fnv_last_lock = bier_fmask_last_lock_gone,
     .fnv_back_walk = bier_fmask_back_walk_notify,
 };

 static void
 bier_fmask_dpo_lock (dpo_id_t *dpo)
 {
 }

 static void
 bier_fmask_dpo_unlock (dpo_id_t *dpo)
 {
 }

 static void
 bier_fmask_dpo_mem_show (void)
 {
     fib_show_memory_usage("BIER-fmask",
                           pool_elts(bier_fmask_pool),
                           pool_len(bier_fmask_pool),
                           sizeof(bier_fmask_t));
 }

 const static dpo_vft_t bier_fmask_dpo_vft = {
     .dv_lock = bier_fmask_dpo_lock,
     .dv_unlock = bier_fmask_dpo_unlock,
     .dv_mem_show = bier_fmask_dpo_mem_show,
     .dv_format = format_bier_fmask,
 };

 const static char *const bier_fmask_mpls_nodes[] =
 {
     "bier-output",
     NULL
 };
 const static char * const * const bier_fmask_nodes[DPO_PROTO_NUM] =
 {
     [DPO_PROTO_BIER] = bier_fmask_mpls_nodes,
     [DPO_PROTO_MPLS] = bier_fmask_mpls_nodes,
 };

 clib_error_t *
 bier_fmask_module_init (vlib_main_t * vm)
 {
     fib_node_register_type (FIB_NODE_TYPE_BIER_FMASK, &bier_fmask_vft);
     dpo_register(DPO_BIER_FMASK, &bier_fmask_dpo_vft, bier_fmask_nodes);

     return (NULL);
 }

 VLIB_INIT_FUNCTION (bier_fmask_module_init);

 static clib_error_t *
 bier_fmask_show (vlib_main_t * vm,
                  unformat_input_t * input,
                  vlib_cli_command_t * cmd)
 {
     bier_fmask_t *bfm;
     index_t bfmi;

     bfmi = INDEX_INVALID;

     while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT) {
         if (unformat (input, "%d", &bfmi))
         {
             ;
         } else
         {
             break;
         }
     }

     if (INDEX_INVALID == bfmi)
     {
         pool_foreach(bfm, bier_fmask_pool,
         ({
             vlib_cli_output (vm, "[@%d] %U",
                              bier_fmask_get_index(bfm),
                              format_bier_fmask, bier_fmask_get_index(bfm), 0);
         }));
     }
     else
     {
         vlib_cli_output (vm, "%U", format_bier_fmask, bfmi, 0);
     }

     return (NULL);
 }

 VLIB_CLI_COMMAND (show_bier_fmask, static) = {
     .path = "show bier fmask",
     .short_help = "show bier fmask",
     .function = bier_fmask_show,
 };
	/*
	* 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/fib/fib_entry.h>
	#include <vnet/fib/fib_table.h>
	#include <vnet/fib/fib_walk.h>
	#include <vnet/fib/fib_path_list.h>

	#include <vnet/bier/bier_table.h>
	#include <vnet/bier/bier_fmask.h>
	#include <vnet/bier/bier_bit_string.h>
	#include <vnet/bier/bier_disp_table.h>

	#include <vnet/mpls/mpls.h>
	#include <vnet/dpo/drop_dpo.h>
	#include <vnet/dpo/load_balance.h>

	/*
	* attributes names for formatting
	*/
	static const char *const bier_fmask_attr_names[] = BIER_FMASK_ATTR_NAMES;

	/*
	* pool of BIER fmask objects
	*/
	bier_fmask_t *bier_fmask_pool;

	/**
	* Stats for each BIER fmask object
	*/
	vlib_combined_counter_main_t bier_fmask_counters;

	static inline index_t
	bier_fmask_get_index (const bier_fmask_t *bfm)
	{
	return (bfm - bier_fmask_pool);
	}

	static void
	bier_fmask_bits_init (bier_fmask_bits_t *bits,
	bier_hdr_len_id_t hlid)
	{
	bits->bfmb_refs = clib_mem_alloc(sizeof(bits->bfmb_refs[0]) *
	bier_hdr_len_id_to_num_bits(hlid));
	clib_memset(bits->bfmb_refs,
	0,
	(sizeof(bits->bfmb_refs[0]) *
	bier_hdr_len_id_to_num_bits(hlid)));

	bits->bfmb_input_reset_string.bbs_len =
	bier_hdr_len_id_to_num_buckets(hlid);

	/*
	* The buckets are accessed in the switch path
	*/
	bits->bfmb_input_reset_string.bbs_buckets =
	clib_mem_alloc_aligned(
	sizeof(bits->bfmb_input_reset_string.bbs_buckets[0]) *
	bier_hdr_len_id_to_num_buckets(hlid),
	CLIB_CACHE_LINE_BYTES);
	clib_memset(bits->bfmb_input_reset_string.bbs_buckets,
	0,
	sizeof(bits->bfmb_input_reset_string.bbs_buckets[0]) *
	bier_hdr_len_id_to_num_buckets(hlid));
	}

	static void
	bier_fmask_stack (bier_fmask_t *bfm)
	{
	dpo_id_t via_dpo = DPO_INVALID;
	fib_forward_chain_type_t fct;

	if (bfm->bfm_flags & BIER_FMASK_FLAG_MPLS)
	{
	fct = FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS;
	}
	else
	{
	fct = FIB_FORW_CHAIN_TYPE_BIER;
	}

	fib_path_list_contribute_forwarding(bfm->bfm_pl, fct,
	FIB_PATH_LIST_FWD_FLAG_COLLAPSE,
	&via_dpo);

	/*
	* If the via PL entry provides no forwarding (i.e. a drop)
	* then neither does this fmask. That way children consider this fmask
	* unresolved and other ECMP options are used instead.
	*/
	if (dpo_is_drop(&via_dpo))
	{
	bfm->bfm_flags &= ~BIER_FMASK_FLAG_FORWARDING;
	}
	else
	{
	bfm->bfm_flags \|= BIER_FMASK_FLAG_FORWARDING;
	}

	dpo_stack(DPO_BIER_FMASK,
	DPO_PROTO_BIER,
	&bfm->bfm_dpo,
	&via_dpo);
	dpo_reset(&via_dpo);
	}

	void
	bier_fmask_contribute_forwarding (index_t bfmi,
	dpo_id_t *dpo)
	{
	bier_fmask_t *bfm;

	bfm = bier_fmask_get(bfmi);

	if (bfm->bfm_flags & BIER_FMASK_FLAG_FORWARDING)
	{
	dpo_set(dpo,
	DPO_BIER_FMASK,
	DPO_PROTO_BIER,
	bfmi);
	}
	else
	{
	dpo_copy(dpo, drop_dpo_get(DPO_PROTO_BIER));
	}
	}

	u32
	bier_fmask_child_add (fib_node_index_t bfmi,
	fib_node_type_t child_type,
	fib_node_index_t child_index)
	{
	return (fib_node_child_add(FIB_NODE_TYPE_BIER_FMASK,
	bfmi,
	child_type,
	child_index));
	};

	void
	bier_fmask_child_remove (fib_node_index_t bfmi,
	u32 sibling_index)
	{
	if (INDEX_INVALID == bfmi)
	{
	return;
	}

	fib_node_child_remove(FIB_NODE_TYPE_BIER_FMASK,
	bfmi,
	sibling_index);
	}

	static void
	bier_fmask_init (bier_fmask_t *bfm,
	const bier_fmask_id_t *fmid,
	const fib_route_path_t *rpath)
	{
	const bier_table_id_t *btid;
	fib_route_path_t *rpaths;
	mpls_label_t olabel;

	clib_memset(bfm, 0, sizeof(*bfm));

	bfm->bfm_id = clib_mem_alloc(sizeof(*bfm->bfm_id));

	fib_node_init(&bfm->bfm_node, FIB_NODE_TYPE_BIER_FMASK);
	bfm->bfm_id = fmid;
	dpo_reset(&bfm->bfm_dpo);
	btid = bier_table_get_id(bfm->bfm_id->bfmi_bti);
	bier_fmask_bits_init(&bfm->bfm_bits, btid->bti_hdr_len);

	if (rpath->frp_flags & FIB_ROUTE_PATH_UDP_ENCAP)
	{
	bfm->bfm_id->bfmi_nh_type = BIER_NH_UDP;
	}
	else if (ip46_address_is_zero(&(bfm->bfm_id->bfmi_nh)))
	{
	bfm->bfm_flags \|= BIER_FMASK_FLAG_DISP;
	}

	if (!(bfm->bfm_flags & BIER_FMASK_FLAG_DISP))
	{
	if (NULL != rpath->frp_label_stack)
	{
	olabel = rpath->frp_label_stack[0].fml_value;
	vnet_mpls_uc_set_label(&bfm->bfm_label, olabel);
	vnet_mpls_uc_set_exp(&bfm->bfm_label, 0);
	vnet_mpls_uc_set_s(&bfm->bfm_label, 1);
	vnet_mpls_uc_set_ttl(&bfm->bfm_label, 64);
	bfm->bfm_flags \|= BIER_FMASK_FLAG_MPLS;
	}
	else
	{
	bier_bift_id_t id;

	/*
	* not an MPLS label
	*/
	bfm->bfm_flags &= ~BIER_FMASK_FLAG_MPLS;

	/*
	* use a label as encoded for BIFT value
	*/
	id = bier_bift_id_encode(btid->bti_set,
	btid->bti_sub_domain,
	btid->bti_hdr_len);
	vnet_mpls_uc_set_label(&bfm->bfm_label, id);
	vnet_mpls_uc_set_s(&bfm->bfm_label, 1);
	vnet_mpls_uc_set_exp(&bfm->bfm_label, 0);
	vnet_mpls_uc_set_ttl(&bfm->bfm_label, 64);
	}
	bfm->bfm_label = clib_host_to_net_u32(bfm->bfm_label);
	}

	rpaths = NULL;
	vec_add1(rpaths, *rpath);
	bfm->bfm_pl = fib_path_list_create((FIB_PATH_LIST_FLAG_SHARED \|
	FIB_PATH_LIST_FLAG_NO_URPF),
	rpaths);
	bfm->bfm_sibling = fib_path_list_child_add(bfm->bfm_pl,
	FIB_NODE_TYPE_BIER_FMASK,
	bier_fmask_get_index(bfm));
	vec_free(rpaths);
	bier_fmask_stack(bfm);
	}

	static void
	bier_fmask_destroy (bier_fmask_t *bfm)
	{
	clib_mem_free(bfm->bfm_bits.bfmb_refs);
	clib_mem_free(bfm->bfm_bits.bfmb_input_reset_string.bbs_buckets);

	bier_fmask_db_remove(bfm->bfm_id);
	fib_path_list_child_remove(bfm->bfm_pl,
	bfm->bfm_sibling);
	dpo_reset(&bfm->bfm_dpo);
	clib_mem_free(bfm->bfm_id);
	pool_put(bier_fmask_pool, bfm);
	}

	void
	bier_fmask_unlock (index_t bfmi)
	{
	bier_fmask_t *bfm;

	if (INDEX_INVALID == bfmi)
	{
	return;
	}

	bfm = bier_fmask_get(bfmi);

	fib_node_unlock(&bfm->bfm_node);
	}

	void
	bier_fmask_lock (index_t bfmi)
	{
	bier_fmask_t *bfm;

	if (INDEX_INVALID == bfmi)
	{
	return;
	}

	bfm = bier_fmask_get(bfmi);

	fib_node_lock(&bfm->bfm_node);
	}

	index_t
	bier_fmask_create_and_lock (const bier_fmask_id_t *fmid,
	const fib_route_path_t *rpath)
	{
	bier_fmask_t *bfm;
	index_t bfmi;

	pool_get_aligned(bier_fmask_pool, bfm, CLIB_CACHE_LINE_BYTES);
	bfmi = bier_fmask_get_index(bfm);

	vlib_validate_combined_counter (&(bier_fmask_counters), bfmi);
	vlib_zero_combined_counter (&(bier_fmask_counters), bfmi);

	bier_fmask_init(bfm, fmid, rpath);

	bier_fmask_lock(bfmi);

	return (bfmi);
	}

	void
	bier_fmask_link (index_t bfmi,
	bier_bp_t bp)
	{
	bier_fmask_t *bfm;

	bfm = bier_fmask_get(bfmi);

	if (0 == bfm->bfm_bits.bfmb_refs[BIER_BP_TO_INDEX(bp)])
	{
	/*
	* 0 -> 1 transition - set the bit in the string
	*/
	bier_bit_string_set_bit(&bfm->bfm_bits.bfmb_input_reset_string, bp);
	}

	++bfm->bfm_bits.bfmb_refs[BIER_BP_TO_INDEX(bp)];
	++bfm->bfm_bits.bfmb_count;
	}

	void
	bier_fmask_unlink (index_t bfmi,
	bier_bp_t bp)
	{
	bier_fmask_t *bfm;

	bfm = bier_fmask_get(bfmi);

	--bfm->bfm_bits.bfmb_refs[BIER_BP_TO_INDEX(bp)];
	--bfm->bfm_bits.bfmb_count;

	if (0 == bfm->bfm_bits.bfmb_refs[BIER_BP_TO_INDEX(bp)])
	{
	/*
	* 1 -> 0 transition - clear the bit in the string
	*/
	bier_bit_string_clear_bit(&bfm->bfm_bits.bfmb_input_reset_string, bp);
	}
	}

	u8*
	format_bier_fmask (u8 s, va_list ap)
	{
	index_t bfmi = va_arg(*ap, index_t);
	u32 indent = va_arg(*ap, u32);
	bier_fmask_attributes_t attr;
	bier_fmask_t *bfm;
	vlib_counter_t to;

	if (pool_is_free_index(bier_fmask_pool, bfmi))
	{
	return (format(s, "No BIER f-mask %d", bfmi));
	}

	bfm = bier_fmask_get(bfmi);

	s = format(s, "fmask: nh:%U bs:%U locks:%d ",
	format_ip46_address, &bfm->bfm_id->bfmi_nh, IP46_TYPE_ANY,
	format_bier_bit_string, &bfm->bfm_bits.bfmb_input_reset_string,
	bfm->bfm_node.fn_locks);
	s = format(s, "flags:");
	FOR_EACH_BIER_FMASK_ATTR(attr) {
	if ((1<<attr) & bfm->bfm_flags) {
	s = format (s, "%s,", bier_fmask_attr_names[attr]);
	}
	}
	vlib_get_combined_counter (&(bier_fmask_counters), bfmi, &to);
	s = format (s, " to:[%Ld:%Ld]]", to.packets, to.bytes);
	s = format(s, "\n");
	s = fib_path_list_format(bfm->bfm_pl, s);

	if (bfm->bfm_flags & BIER_FMASK_FLAG_MPLS)
	{
	s = format(s, " output-label:%U",
	format_mpls_unicast_label,
	vnet_mpls_uc_get_label(clib_net_to_host_u32(bfm->bfm_label)));
	}
	else
	{
	s = format(s, " output-bfit:[%U]",
	format_bier_bift_id,
	vnet_mpls_uc_get_label(clib_net_to_host_u32(bfm->bfm_label)));
	}
	s = format(s, "\n %U%U",
	format_white_space, indent,
	format_dpo_id, &bfm->bfm_dpo, indent+2);

	return (s);
	}

	void
	bier_fmask_get_stats (index_t bfmi, u64 * packets, u64 * bytes)
	{
	vlib_counter_t to;

	vlib_get_combined_counter (&(bier_fmask_counters), bfmi, &to);

	*packets = to.packets;
	*bytes = to.bytes;
	}

	void
	bier_fmask_encode (index_t bfmi,
	bier_table_id_t *btid,
	fib_route_path_t *rpath)
	{
	bier_fmask_t *bfm;

	bfm = bier_fmask_get(bfmi);
	btid = bier_table_get_id(bfm->bfm_id->bfmi_bti);

	clib_memset(rpath, 0, sizeof(*rpath));

	rpath->frp_sw_if_index = ~0;

	switch (bfm->bfm_id->bfmi_nh_type)
	{
	case BIER_NH_UDP:
	rpath->frp_flags = FIB_ROUTE_PATH_UDP_ENCAP;
	rpath->frp_udp_encap_id = bfm->bfm_id->bfmi_id;
	break;
	case BIER_NH_IP:
	memcpy(&rpath->frp_addr, &bfm->bfm_id->bfmi_nh,
	sizeof(rpath->frp_addr));
	break;
	}
	}

	static fib_node_t *
	bier_fmask_get_node (fib_node_index_t index)
	{
	bier_fmask_t *bfm = bier_fmask_get(index);
	return (&(bfm->bfm_node));
	}

	static bier_fmask_t*
	bier_fmask_get_from_node (fib_node_t *node)
	{
	return ((bier_fmask_t)(((char)node) -
	STRUCT_OFFSET_OF(bier_fmask_t,
	bfm_node)));
	}

	/*
	* bier_fmask_last_lock_gone
	*/
	static void
	bier_fmask_last_lock_gone (fib_node_t *node)
	{
	bier_fmask_destroy(bier_fmask_get_from_node(node));
	}

	/*
	* bier_fmask_back_walk_notify
	*
	* A back walk has reached this BIER fmask
	*/
	static fib_node_back_walk_rc_t
	bier_fmask_back_walk_notify (fib_node_t *node,
	fib_node_back_walk_ctx_t *ctx)
	{
	/*
	* re-stack the fmask on the n-eos of the via
	*/
	bier_fmask_t *bfm = bier_fmask_get_from_node(node);

	bier_fmask_stack(bfm);

	/*
	* propagate further up the graph.
	* we can do this synchronously since the fan out is small.
	*/
	fib_walk_sync(FIB_NODE_TYPE_BIER_FMASK, bier_fmask_get_index(bfm), ctx);

	return (FIB_NODE_BACK_WALK_CONTINUE);
	}

	/*
	* The BIER fmask's graph node virtual function table
	*/
	static const fib_node_vft_t bier_fmask_vft = {
	.fnv_get = bier_fmask_get_node,
	.fnv_last_lock = bier_fmask_last_lock_gone,
	.fnv_back_walk = bier_fmask_back_walk_notify,
	};

	static void
	bier_fmask_dpo_lock (dpo_id_t *dpo)
	{
	}

	static void
	bier_fmask_dpo_unlock (dpo_id_t *dpo)
	{
	}

	static void
	bier_fmask_dpo_mem_show (void)
	{
	fib_show_memory_usage("BIER-fmask",
	pool_elts(bier_fmask_pool),
	pool_len(bier_fmask_pool),
	sizeof(bier_fmask_t));
	}

	const static dpo_vft_t bier_fmask_dpo_vft = {
	.dv_lock = bier_fmask_dpo_lock,
	.dv_unlock = bier_fmask_dpo_unlock,
	.dv_mem_show = bier_fmask_dpo_mem_show,
	.dv_format = format_bier_fmask,
	};

	const static char *const bier_fmask_mpls_nodes[] =
	{
	"bier-output",
	NULL
	};
	const static char * const * const bier_fmask_nodes[DPO_PROTO_NUM] =
	{
	[DPO_PROTO_BIER] = bier_fmask_mpls_nodes,
	[DPO_PROTO_MPLS] = bier_fmask_mpls_nodes,
	};

	clib_error_t *
	bier_fmask_module_init (vlib_main_t * vm)
	{
	fib_node_register_type (FIB_NODE_TYPE_BIER_FMASK, &bier_fmask_vft);
	dpo_register(DPO_BIER_FMASK, &bier_fmask_dpo_vft, bier_fmask_nodes);

	return (NULL);
	}

	VLIB_INIT_FUNCTION (bier_fmask_module_init);

	static clib_error_t *
	bier_fmask_show (vlib_main_t * vm,
	unformat_input_t * input,
	vlib_cli_command_t * cmd)
	{
	bier_fmask_t *bfm;
	index_t bfmi;

	bfmi = INDEX_INVALID;

	while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT) {
	if (unformat (input, "%d", &bfmi))
	{
	;
	} else
	{
	break;
	}
	}

	if (INDEX_INVALID == bfmi)
	{
	pool_foreach(bfm, bier_fmask_pool,
	({
	vlib_cli_output (vm, "[@%d] %U",
	bier_fmask_get_index(bfm),
	format_bier_fmask, bier_fmask_get_index(bfm), 0);
	}));
	}
	else
	{
	vlib_cli_output (vm, "%U", format_bier_fmask, bfmi, 0);
	}

	return (NULL);
	}

	VLIB_CLI_COMMAND (show_bier_fmask, static) = {
	.path = "show bier fmask",
	.short_help = "show bier fmask",
	.function = bier_fmask_show,
	};