src/vnet/fib/fib_path_ext.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/mpls/mpls.h>
 #include <vnet/dpo/mpls_label_dpo.h>
 #include <vnet/dpo/load_balance.h>
 #include <vnet/dpo/drop_dpo.h>

 #include <vnet/fib/fib_path_ext.h>
 #include <vnet/fib/fib_entry_src.h>
 #include <vnet/fib/fib_path.h>
 #include <vnet/fib/fib_path_list.h>
 #include <vnet/fib/fib_internal.h>

 const char *fib_path_ext_adj_flags_names[] = FIB_PATH_EXT_ADJ_ATTR_NAMES;
 const char *fib_path_ext_mpls_flags_names[] = FIB_PATH_EXT_MPLS_ATTR_NAMES;

 u8 *
 format_fib_path_ext (u8 * s, va_list * args)
 {
     fib_path_ext_t *path_ext;
     u32 ii;

     path_ext = va_arg (*args, fib_path_ext_t *);

     s = format(s, "path:%d ", path_ext->fpe_path_index);

     switch (path_ext->fpe_type)
     {
     case FIB_PATH_EXT_MPLS: {
         fib_path_ext_mpls_attr_t attr;

         if (path_ext->fpe_mpls_flags)
         {
             s = format(s, "mpls-flags:[");

             FOR_EACH_PATH_EXT_MPLS_ATTR(attr)
             {
                 if ((1<<attr) & path_ext->fpe_mpls_flags) {
                     s = format(s, "%s", fib_path_ext_mpls_flags_names[attr]);
                 }
             }
             s = format(s, "]");
         }
         s = format(s, " labels:[");
         for (ii = 0; ii < vec_len(path_ext->fpe_path.frp_label_stack); ii++)
         {
             s = format(s, "[%U]",
                        format_fib_mpls_label,
                        &path_ext->fpe_path.frp_label_stack[ii]);
         }
         s = format(s, "]");
         break;
     }
     case FIB_PATH_EXT_ADJ: {
         fib_path_ext_adj_attr_t attr;

         if (path_ext->fpe_adj_flags)
         {
             s = format(s, "adj-flags:[");
             FOR_EACH_PATH_EXT_ADJ_ATTR(attr)
             {
                 if ((1<<attr) & path_ext->fpe_adj_flags)
                 {
                     s = format(s, "%s", fib_path_ext_adj_flags_names[attr]);
                 }
             }
             s = format(s, "]");
         }
         break;
     }
     }
     return (s);
 }

 int
 fib_path_ext_cmp (fib_path_ext_t *path_ext,
 		  const fib_route_path_t *rpath)
 {
     return (fib_route_path_cmp(&path_ext->fpe_path, rpath));
 }

 static fib_path_list_walk_rc_t
 fib_path_ext_match (fib_node_index_t pl_index,
 		    fib_node_index_t path_index,
 		    void *ctx)
 {
     fib_path_ext_t *path_ext = ctx;

     if (!fib_path_cmp_w_route_path(path_index,
 				   &path_ext->fpe_path))
     {
 	path_ext->fpe_path_index = path_index;
 	return (FIB_PATH_LIST_WALK_STOP);
     }
     return (FIB_PATH_LIST_WALK_CONTINUE);
 }

 void
 fib_path_ext_resolve (fib_path_ext_t *path_ext,
 		      fib_node_index_t path_list_index)
 {
     /*
      * Find the path on the path list that this is an extension for
      */
     path_ext->fpe_path_index = FIB_NODE_INDEX_INVALID;
     fib_path_list_walk(path_list_index,
 		       fib_path_ext_match,
 		       path_ext);
 }

 static void
 fib_path_ext_init (fib_path_ext_t *path_ext,
 		   fib_node_index_t path_list_index,
                    fib_path_ext_type_t ext_type,
 		   const fib_route_path_t *rpath)
 {
     path_ext->fpe_path = *rpath;
     path_ext->fpe_path_index = FIB_NODE_INDEX_INVALID;
     path_ext->fpe_adj_flags = FIB_PATH_EXT_ADJ_FLAG_NONE;
     path_ext->fpe_type = ext_type;

     fib_path_ext_resolve(path_ext, path_list_index);
 }

 /**
  * @brief Return true if the label stack is implicit null
  * imp-null and pop equate to the same this as this level -
  * the label is coming off.
  */
 static int
 fib_path_ext_is_imp_null (fib_path_ext_t *path_ext)
 {
     return ((1 == vec_len(path_ext->fpe_label_stack)) &&
 	    ((MPLS_IETF_IMPLICIT_NULL_LABEL == path_ext->fpe_label_stack[0].fml_value) ||
              (MPLS_LABEL_POP == path_ext->fpe_label_stack[0].fml_value)));
 }

 mpls_label_dpo_flags_t
 fib_path_ext_mpls_flags_to_mpls_label (fib_path_ext_mpls_flags_t fpe_flags)
 {
     mpls_label_dpo_flags_t ml_flags = MPLS_LABEL_DPO_FLAG_NONE;

     if (fpe_flags &FIB_PATH_EXT_MPLS_FLAG_NO_IP_TTL_DECR)
     {
         ml_flags |= MPLS_LABEL_DPO_FLAG_NO_IP_TTL_DECR;
     }

     return (ml_flags);
 }

 load_balance_path_t *
 fib_path_ext_stack (fib_path_ext_t *path_ext,
                     dpo_proto_t payload_proto,
                     fib_forward_chain_type_t child_fct,
 		    load_balance_path_t *nhs)
 {
     fib_forward_chain_type_t parent_fct;
     load_balance_path_t *nh;

     if (!fib_path_is_resolved(path_ext->fpe_path_index))
 	return (nhs);

     /*
      * Since we are stacking this path-extension, it must have a valid out
      * label. From the chain type request by the child, determine what
      * chain type we will request from the parent.
      */
     switch (child_fct)
     {
     case FIB_FORW_CHAIN_TYPE_MPLS_EOS:
     {
 	/*
 	 * The EOS chain is a tricky since, when the path has an imp NULL one cannot know
          * the adjacency to link to without knowing what the packets payload protocol
 	 * will be once the label is popped.
 	 */
 	if (fib_path_ext_is_imp_null(path_ext))
 	{
             parent_fct = fib_forw_chain_type_from_dpo_proto(payload_proto);
         }
         else
         {
             /*
              * we have a label to stack. packets will thus be labelled when
              * they encounter the child, ergo, non-eos.
              */
 	    parent_fct = FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS;
         }
 	break;
     }
     case FIB_FORW_CHAIN_TYPE_UNICAST_IP4:
     case FIB_FORW_CHAIN_TYPE_UNICAST_IP6:
 	if (fib_path_ext_is_imp_null(path_ext))
 	{
             /*
              * implicit-null label for the eos or IP chain, need to pick up
              * the IP adj
              */
 	    parent_fct = child_fct;
 	}
         else
         {
             /*
              * we have a label to stack. packets will thus be labelled when
              * they encounter the child, ergo, non-eos.
              */
 	    parent_fct = FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS;
         }
 	break;
     case FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS:
         parent_fct = child_fct;
 	break;
     case FIB_FORW_CHAIN_TYPE_ETHERNET:
         parent_fct = FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS;
 	break;
     default:
         return (nhs);
 	break;
     }

     dpo_id_t via_dpo = DPO_INVALID;

     /*
      * The next object in the graph after the imposition of the label
      * will be the DPO contributed by the path through which the packets
      * are to be sent. We stack the MPLS Label DPO on this path DPO
      */
     fib_path_contribute_forwarding(path_ext->fpe_path_index,
 				   parent_fct,
                                    payload_proto,
 				   &via_dpo);

     if (dpo_is_drop(&via_dpo) ||
 	load_balance_is_drop(&via_dpo))
     {
 	/*
 	 * don't stack a path extension on a drop. doing so will create
 	 * a LB bucket entry on drop, and we will lose a percentage of traffic.
 	 */
     }
     else
     {
 	vec_add2(nhs, nh, 1);
 	nh->path_weight = fib_path_get_weight(path_ext->fpe_path_index);
 	nh->path_index = path_ext->fpe_path_index;
 	dpo_copy(&nh->path_dpo, &via_dpo);

 	/*
 	 * The label is stackable for this chain type
 	 * construct the mpls header that will be imposed in the data-path
 	 */
 	if (!fib_path_ext_is_imp_null(path_ext))
 	{
             /*
              * we use the parent protocol for the label so that
              * we pickup the correct MPLS imposition nodes to do
              * ip[46] processing.
              */
             dpo_id_t parent = DPO_INVALID;
             dpo_proto_t chain_proto;
             mpls_eos_bit_t eos;

             eos = (child_fct == FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS ?
                    MPLS_NON_EOS :
                    MPLS_EOS);
             chain_proto = fib_forw_chain_type_to_dpo_proto(child_fct);

             dpo_copy(&parent, &nh->path_dpo);
             mpls_label_dpo_create(path_ext->fpe_label_stack,
                                   eos,
                                   chain_proto,
                                   fib_path_ext_mpls_flags_to_mpls_label(
                                       path_ext->fpe_mpls_flags),
                                   &parent,
                                   &nh->path_dpo);

 	    dpo_reset(&parent);
 	}
         else if (child_fct == FIB_FORW_CHAIN_TYPE_MPLS_EOS)
         {
             /*
              * MPLS EOS packets using an imp-null. Insert the disposition.
              */
             fib_path_stack_mpls_disp(nh->path_index,
                                      fib_forw_chain_type_to_dpo_proto(parent_fct),
                                      path_ext->fpe_label_stack[0].fml_mode,
                                      &nh->path_dpo);
         }
     }
     dpo_reset(&via_dpo);

     return (nhs);
 }

 fib_path_ext_t *
 fib_path_ext_list_find (const fib_path_ext_list_t *list,
                         fib_path_ext_type_t ext_type,
                         const fib_route_path_t *rpath)
 {
     fib_path_ext_t *path_ext;

     vec_foreach(path_ext, list->fpel_exts)
     {
         if ((path_ext->fpe_type == ext_type) &&
             !fib_path_ext_cmp(path_ext, rpath) )
         {
             return (path_ext);
         }
     }
     return (NULL);
 }

 fib_path_ext_t *
 fib_path_ext_list_find_by_path_index (const fib_path_ext_list_t *list,
                                       fib_node_index_t path_index)
 {
     fib_path_ext_t *path_ext;

     if (NULL != list)
     {
         vec_foreach(path_ext, list->fpel_exts)
         {
             if (path_ext->fpe_path_index == path_index)
             {
                 return (path_ext);
             }
         }
     }
     return (NULL);
 }


 fib_path_ext_t *
 fib_path_ext_list_push_back (fib_path_ext_list_t *list,
                              fib_node_index_t path_list_index,
                              fib_path_ext_type_t ext_type,
                              const fib_route_path_t *rpath)
 {
     fib_path_ext_t *path_ext;

     path_ext = fib_path_ext_list_find(list, ext_type, rpath);

     if (NULL == path_ext)
     {
         vec_add2(list->fpel_exts, path_ext, 1);
         fib_path_ext_init(path_ext, path_list_index, ext_type, rpath);
     }

     return (path_ext);
 }

 /*
  * insert, sorted, a path extension to the entry's list.
  * It's not strictly necessary to sort the path extensions, since each
  * extension has the path index to which it resolves. However, by being
  * sorted the load-balance produced has a deterministic order, not an order
  * based on the sequence of extension additions. this is a considerable benefit.
  */
 fib_path_ext_t *
 fib_path_ext_list_insert (fib_path_ext_list_t *list,
                           fib_node_index_t path_list_index,
                           fib_path_ext_type_t ext_type,
                           const fib_route_path_t *rpath)
 {
     fib_path_ext_t new_path_ext, *path_ext;
     int i = 0;

     if (0 == fib_path_ext_list_length(list))
     {
         return (fib_path_ext_list_push_back(list, path_list_index,
                                             ext_type, rpath));
     }

     fib_path_ext_init(&new_path_ext, path_list_index, ext_type, rpath);

     vec_foreach(path_ext, list->fpel_exts)
     {
         int res = fib_path_ext_cmp(path_ext, rpath);

         if (0 == res)
         {
             /*
              * don't add duplicate extensions. modify instead
              */
             vec_free(path_ext->fpe_label_stack);
             *path_ext = new_path_ext;
             goto done;
         }
         else if (res < 0)
         {
             i++;
         }
         else
         {
             break;
         }
     }
     vec_insert_elts(list->fpel_exts, &new_path_ext, 1, i);
 done:
     return (&(list->fpel_exts[i]));
 }

 void
 fib_path_ext_list_resolve (fib_path_ext_list_t *list,
                            fib_node_index_t path_list_index)
 {
     fib_path_ext_t *path_ext;

     vec_foreach(path_ext, list->fpel_exts)
     {
         fib_path_ext_resolve(path_ext, path_list_index);
     };
 }

 void
 fib_path_ext_list_remove (fib_path_ext_list_t *list,
                           fib_path_ext_type_t ext_type,
                           const fib_route_path_t *rpath)
 {
     fib_path_ext_t *path_ext;

     path_ext = fib_path_ext_list_find(list, ext_type, rpath);

     if (NULL != path_ext)
     {
         /*
          * delete the element moving the remaining elements down 1 position.
          * this preserves the sorted order.
          */
         vec_free(path_ext->fpe_label_stack);
         vec_delete(list->fpel_exts, 1, (path_ext - list->fpel_exts));
     }
 }

 void
 fib_path_ext_list_flush (fib_path_ext_list_t *list)
 {
     fib_path_ext_t *path_ext;

     vec_foreach(path_ext, list->fpel_exts)
     {
         vec_free(path_ext->fpe_label_stack);
     };
     vec_free(list->fpel_exts);
     list->fpel_exts = NULL;
 }

 u8*
 format_fib_path_ext_list (u8 * s, va_list * args)
 {
     fib_path_ext_list_t *list;
     fib_path_ext_t *path_ext;

     list = va_arg (*args, fib_path_ext_list_t *);

     if (fib_path_ext_list_length(list))
     {
         s = format(s, "    Extensions:");
         vec_foreach(path_ext, list->fpel_exts)
         {
             s = format(s, "\n     %U", format_fib_path_ext, path_ext);
         };
     }

     return (s);
 }

 int
 fib_path_ext_list_length (const fib_path_ext_list_t *list)
 {
     return (vec_len(list->fpel_exts));
 }
	/*
	* 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/dpo/mpls_label_dpo.h>
	#include <vnet/dpo/load_balance.h>
	#include <vnet/dpo/drop_dpo.h>

	#include <vnet/fib/fib_path_ext.h>
	#include <vnet/fib/fib_entry_src.h>
	#include <vnet/fib/fib_path.h>
	#include <vnet/fib/fib_path_list.h>
	#include <vnet/fib/fib_internal.h>

	const char *fib_path_ext_adj_flags_names[] = FIB_PATH_EXT_ADJ_ATTR_NAMES;
	const char *fib_path_ext_mpls_flags_names[] = FIB_PATH_EXT_MPLS_ATTR_NAMES;

	u8 *
	format_fib_path_ext (u8 * s, va_list * args)
	{
	fib_path_ext_t *path_ext;
	u32 ii;

	path_ext = va_arg (args, fib_path_ext_t );

	s = format(s, "path:%d ", path_ext->fpe_path_index);

	switch (path_ext->fpe_type)
	{
	case FIB_PATH_EXT_MPLS: {
	fib_path_ext_mpls_attr_t attr;

	if (path_ext->fpe_mpls_flags)
	{
	s = format(s, "mpls-flags:[");

	FOR_EACH_PATH_EXT_MPLS_ATTR(attr)
	{
	if ((1<<attr) & path_ext->fpe_mpls_flags) {
	s = format(s, "%s", fib_path_ext_mpls_flags_names[attr]);
	}
	}
	s = format(s, "]");
	}
	s = format(s, " labels:[");
	for (ii = 0; ii < vec_len(path_ext->fpe_path.frp_label_stack); ii++)
	{
	s = format(s, "[%U]",
	format_fib_mpls_label,
	&path_ext->fpe_path.frp_label_stack[ii]);
	}
	s = format(s, "]");
	break;
	}
	case FIB_PATH_EXT_ADJ: {
	fib_path_ext_adj_attr_t attr;

	if (path_ext->fpe_adj_flags)
	{
	s = format(s, "adj-flags:[");
	FOR_EACH_PATH_EXT_ADJ_ATTR(attr)
	{
	if ((1<<attr) & path_ext->fpe_adj_flags)
	{
	s = format(s, "%s", fib_path_ext_adj_flags_names[attr]);
	}
	}
	s = format(s, "]");
	}
	break;
	}
	}
	return (s);
	}

	int
	fib_path_ext_cmp (fib_path_ext_t *path_ext,
	const fib_route_path_t *rpath)
	{
	return (fib_route_path_cmp(&path_ext->fpe_path, rpath));
	}

	static fib_path_list_walk_rc_t
	fib_path_ext_match (fib_node_index_t pl_index,
	fib_node_index_t path_index,
	void *ctx)
	{
	fib_path_ext_t *path_ext = ctx;

	if (!fib_path_cmp_w_route_path(path_index,
	&path_ext->fpe_path))
	{
	path_ext->fpe_path_index = path_index;
	return (FIB_PATH_LIST_WALK_STOP);
	}
	return (FIB_PATH_LIST_WALK_CONTINUE);
	}

	void
	fib_path_ext_resolve (fib_path_ext_t *path_ext,
	fib_node_index_t path_list_index)
	{
	/*
	* Find the path on the path list that this is an extension for
	*/
	path_ext->fpe_path_index = FIB_NODE_INDEX_INVALID;
	fib_path_list_walk(path_list_index,
	fib_path_ext_match,
	path_ext);
	}

	static void
	fib_path_ext_init (fib_path_ext_t *path_ext,
	fib_node_index_t path_list_index,
	fib_path_ext_type_t ext_type,
	const fib_route_path_t *rpath)
	{
	path_ext->fpe_path = *rpath;
	path_ext->fpe_path_index = FIB_NODE_INDEX_INVALID;
	path_ext->fpe_adj_flags = FIB_PATH_EXT_ADJ_FLAG_NONE;
	path_ext->fpe_type = ext_type;

	fib_path_ext_resolve(path_ext, path_list_index);
	}

	/**
	* @brief Return true if the label stack is implicit null
	* imp-null and pop equate to the same this as this level -
	* the label is coming off.
	*/
	static int
	fib_path_ext_is_imp_null (fib_path_ext_t *path_ext)
	{
	return ((1 == vec_len(path_ext->fpe_label_stack)) &&
	((MPLS_IETF_IMPLICIT_NULL_LABEL == path_ext->fpe_label_stack[0].fml_value) \|\|
	(MPLS_LABEL_POP == path_ext->fpe_label_stack[0].fml_value)));
	}

	mpls_label_dpo_flags_t
	fib_path_ext_mpls_flags_to_mpls_label (fib_path_ext_mpls_flags_t fpe_flags)
	{
	mpls_label_dpo_flags_t ml_flags = MPLS_LABEL_DPO_FLAG_NONE;

	if (fpe_flags &FIB_PATH_EXT_MPLS_FLAG_NO_IP_TTL_DECR)
	{
	ml_flags \|= MPLS_LABEL_DPO_FLAG_NO_IP_TTL_DECR;
	}

	return (ml_flags);
	}

	load_balance_path_t *
	fib_path_ext_stack (fib_path_ext_t *path_ext,
	dpo_proto_t payload_proto,
	fib_forward_chain_type_t child_fct,
	load_balance_path_t *nhs)
	{
	fib_forward_chain_type_t parent_fct;
	load_balance_path_t *nh;

	if (!fib_path_is_resolved(path_ext->fpe_path_index))
	return (nhs);

	/*
	* Since we are stacking this path-extension, it must have a valid out
	* label. From the chain type request by the child, determine what
	* chain type we will request from the parent.
	*/
	switch (child_fct)
	{
	case FIB_FORW_CHAIN_TYPE_MPLS_EOS:
	{
	/*
	* The EOS chain is a tricky since, when the path has an imp NULL one cannot know
	* the adjacency to link to without knowing what the packets payload protocol
	* will be once the label is popped.
	*/
	if (fib_path_ext_is_imp_null(path_ext))
	{
	parent_fct = fib_forw_chain_type_from_dpo_proto(payload_proto);
	}
	else
	{
	/*
	* we have a label to stack. packets will thus be labelled when
	* they encounter the child, ergo, non-eos.
	*/
	parent_fct = FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS;
	}
	break;
	}
	case FIB_FORW_CHAIN_TYPE_UNICAST_IP4:
	case FIB_FORW_CHAIN_TYPE_UNICAST_IP6:
	if (fib_path_ext_is_imp_null(path_ext))
	{
	/*
	* implicit-null label for the eos or IP chain, need to pick up
	* the IP adj
	*/
	parent_fct = child_fct;
	}
	else
	{
	/*
	* we have a label to stack. packets will thus be labelled when
	* they encounter the child, ergo, non-eos.
	*/
	parent_fct = FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS;
	}
	break;
	case FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS:
	parent_fct = child_fct;
	break;
	case FIB_FORW_CHAIN_TYPE_ETHERNET:
	parent_fct = FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS;
	break;
	default:
	return (nhs);
	break;
	}

	dpo_id_t via_dpo = DPO_INVALID;

	/*
	* The next object in the graph after the imposition of the label
	* will be the DPO contributed by the path through which the packets
	* are to be sent. We stack the MPLS Label DPO on this path DPO
	*/
	fib_path_contribute_forwarding(path_ext->fpe_path_index,
	parent_fct,
	payload_proto,
	&via_dpo);

	if (dpo_is_drop(&via_dpo) \|\|
	load_balance_is_drop(&via_dpo))
	{
	/*
	* don't stack a path extension on a drop. doing so will create
	* a LB bucket entry on drop, and we will lose a percentage of traffic.
	*/
	}
	else
	{
	vec_add2(nhs, nh, 1);
	nh->path_weight = fib_path_get_weight(path_ext->fpe_path_index);
	nh->path_index = path_ext->fpe_path_index;
	dpo_copy(&nh->path_dpo, &via_dpo);

	/*
	* The label is stackable for this chain type
	* construct the mpls header that will be imposed in the data-path
	*/
	if (!fib_path_ext_is_imp_null(path_ext))
	{
	/*
	* we use the parent protocol for the label so that
	* we pickup the correct MPLS imposition nodes to do
	* ip[46] processing.
	*/
	dpo_id_t parent = DPO_INVALID;
	dpo_proto_t chain_proto;
	mpls_eos_bit_t eos;

	eos = (child_fct == FIB_FORW_CHAIN_TYPE_MPLS_NON_EOS ?
	MPLS_NON_EOS :
	MPLS_EOS);
	chain_proto = fib_forw_chain_type_to_dpo_proto(child_fct);

	dpo_copy(&parent, &nh->path_dpo);
	mpls_label_dpo_create(path_ext->fpe_label_stack,
	eos,
	chain_proto,
	fib_path_ext_mpls_flags_to_mpls_label(
	path_ext->fpe_mpls_flags),
	&parent,
	&nh->path_dpo);

	dpo_reset(&parent);
	}
	else if (child_fct == FIB_FORW_CHAIN_TYPE_MPLS_EOS)
	{
	/*
	* MPLS EOS packets using an imp-null. Insert the disposition.
	*/
	fib_path_stack_mpls_disp(nh->path_index,
	fib_forw_chain_type_to_dpo_proto(parent_fct),
	path_ext->fpe_label_stack[0].fml_mode,
	&nh->path_dpo);
	}
	}
	dpo_reset(&via_dpo);

	return (nhs);
	}

	fib_path_ext_t *
	fib_path_ext_list_find (const fib_path_ext_list_t *list,
	fib_path_ext_type_t ext_type,
	const fib_route_path_t *rpath)
	{
	fib_path_ext_t *path_ext;

	vec_foreach(path_ext, list->fpel_exts)
	{
	if ((path_ext->fpe_type == ext_type) &&
	!fib_path_ext_cmp(path_ext, rpath) )
	{
	return (path_ext);
	}
	}
	return (NULL);
	}

	fib_path_ext_t *
	fib_path_ext_list_find_by_path_index (const fib_path_ext_list_t *list,
	fib_node_index_t path_index)
	{
	fib_path_ext_t *path_ext;

	if (NULL != list)
	{
	vec_foreach(path_ext, list->fpel_exts)
	{
	if (path_ext->fpe_path_index == path_index)
	{
	return (path_ext);
	}
	}
	}
	return (NULL);
	}


	fib_path_ext_t *
	fib_path_ext_list_push_back (fib_path_ext_list_t *list,
	fib_node_index_t path_list_index,
	fib_path_ext_type_t ext_type,
	const fib_route_path_t *rpath)
	{
	fib_path_ext_t *path_ext;

	path_ext = fib_path_ext_list_find(list, ext_type, rpath);

	if (NULL == path_ext)
	{
	vec_add2(list->fpel_exts, path_ext, 1);
	fib_path_ext_init(path_ext, path_list_index, ext_type, rpath);
	}

	return (path_ext);
	}

	/*
	* insert, sorted, a path extension to the entry's list.
	* It's not strictly necessary to sort the path extensions, since each
	* extension has the path index to which it resolves. However, by being
	* sorted the load-balance produced has a deterministic order, not an order
	* based on the sequence of extension additions. this is a considerable benefit.
	*/
	fib_path_ext_t *
	fib_path_ext_list_insert (fib_path_ext_list_t *list,
	fib_node_index_t path_list_index,
	fib_path_ext_type_t ext_type,
	const fib_route_path_t *rpath)
	{
	fib_path_ext_t new_path_ext, *path_ext;
	int i = 0;

	if (0 == fib_path_ext_list_length(list))
	{
	return (fib_path_ext_list_push_back(list, path_list_index,
	ext_type, rpath));
	}

	fib_path_ext_init(&new_path_ext, path_list_index, ext_type, rpath);

	vec_foreach(path_ext, list->fpel_exts)
	{
	int res = fib_path_ext_cmp(path_ext, rpath);

	if (0 == res)
	{
	/*
	* don't add duplicate extensions. modify instead
	*/
	vec_free(path_ext->fpe_label_stack);
	*path_ext = new_path_ext;
	goto done;
	}
	else if (res < 0)
	{
	i++;
	}
	else
	{
	break;
	}
	}
	vec_insert_elts(list->fpel_exts, &new_path_ext, 1, i);
	done:
	return (&(list->fpel_exts[i]));
	}

	void
	fib_path_ext_list_resolve (fib_path_ext_list_t *list,
	fib_node_index_t path_list_index)
	{
	fib_path_ext_t *path_ext;

	vec_foreach(path_ext, list->fpel_exts)
	{
	fib_path_ext_resolve(path_ext, path_list_index);
	};
	}

	void
	fib_path_ext_list_remove (fib_path_ext_list_t *list,
	fib_path_ext_type_t ext_type,
	const fib_route_path_t *rpath)
	{
	fib_path_ext_t *path_ext;

	path_ext = fib_path_ext_list_find(list, ext_type, rpath);

	if (NULL != path_ext)
	{
	/*
	* delete the element moving the remaining elements down 1 position.
	* this preserves the sorted order.
	*/
	vec_free(path_ext->fpe_label_stack);
	vec_delete(list->fpel_exts, 1, (path_ext - list->fpel_exts));
	}
	}

	void
	fib_path_ext_list_flush (fib_path_ext_list_t *list)
	{
	fib_path_ext_t *path_ext;

	vec_foreach(path_ext, list->fpel_exts)
	{
	vec_free(path_ext->fpe_label_stack);
	};
	vec_free(list->fpel_exts);
	list->fpel_exts = NULL;
	}

	u8*
	format_fib_path_ext_list (u8 * s, va_list * args)
	{
	fib_path_ext_list_t *list;
	fib_path_ext_t *path_ext;

	list = va_arg (args, fib_path_ext_list_t );

	if (fib_path_ext_list_length(list))
	{
	s = format(s, " Extensions:");
	vec_foreach(path_ext, list->fpel_exts)
	{
	s = format(s, "\n %U", format_fib_path_ext, path_ext);
	};
	}

	return (s);
	}

	int
	fib_path_ext_list_length (const fib_path_ext_list_t *list)
	{
	return (vec_len(list->fpel_exts));
	}