BIER in non-MPLS netowrks

as decsribed in section 2.2
  ihttps://tools.ietf.org/html/draft-ietf-bier-mpls-encapsulation-10
with BIFT encoding from:
  https://tools.ietf.org/html/draft-wijnandsxu-bier-non-mpls-bift-encoding-00

changes:
1 - introduce the new BIFT lookup table. BIER tables that have an associated
    MPLS label are added to the MPLS-FIB. Those that don't are added to the
    BIER table
2 - BIER routes that have no associated output MPLS label will add a BIFT label.
3 - The BIER FMask has a path-list as a member to resolve via any possible path.

Change-Id: I1fd4d9dbd074f0e855c16e9329b81460ebe1efce
Signed-off-by: Neale Ranns <nranns@cisco.com>

6 files changed, 117 insertions, 146 deletions

diff --git a/src/vnet/fib/fib_entry_src.c b/src/vnet/fib/fib_entry_src.c
index 214dafe9b8d..1d73af3bf0d 100644
--- a/src/vnet/fib/fib_entry_src.c
+++ b/src/vnet/fib/fib_entry_src.c
@@ -1321,6 +1321,7 @@ fib_entry_get_dpo_for_source (fib_node_index_t fib_entry_index,
 	    fib_path_list_contribute_forwarding(
 		esrc->fes_pl,
 		fib_entry_get_default_chain_type(fib_entry),
+                FIB_PATH_LIST_FWD_FLAG_NONE,
 		dpo);
 
 	    return (dpo_id_is_valid(dpo));
diff --git a/src/vnet/fib/fib_path.c b/src/vnet/fib/fib_path.c
index c6677fb12f2..8d738c2b727 100644
--- a/src/vnet/fib/fib_path.c
+++ b/src/vnet/fib/fib_path.c
@@ -41,6 +41,7 @@
 #include <vnet/bier/bier_fmask.h>
 #include <vnet/bier/bier_table.h>
 #include <vnet/bier/bier_imp.h>
+#include <vnet/bier/bier_disp_table.h>
 
 /**
  * Enurmeration of path types
@@ -286,13 +287,9 @@ typedef struct fib_path_t_ {
 	} recursive;
 	struct {
             /**
-             * The next-hop
+             * BIER FMask ID
              */
-            ip46_address_t fp_nh;
-            /**
-             * The BIER FIB the fmask is in
-             */
-            index_t fp_bier_fib;
+            index_t fp_bier_fmask;
 	} bier_fmask;
 	struct {
             /**
@@ -369,13 +366,13 @@ typedef struct fib_path_t_ {
          */
         fib_node_index_t fp_via_fib;
         /**
-         * the resolving bier-fmask
-         */
-        index_t fp_via_bier_fmask;
-        /**
          * the resolving bier-table
          */
         index_t fp_via_bier_tbl;
+        /**
+         * the resolving bier-fmask
+         */
+        index_t fp_via_bier_fmask;
     };
 
     /**
@@ -409,8 +406,8 @@ static fib_path_t *fib_path_pool;
 {       		          				\
     u8 *_tmp = NULL;						\
     _tmp = fib_path_format(fib_path_get_index(_p), _tmp);	\
-    clib_warning("path:[%d:%s]:" _fmt,				\
-		 fib_path_get_index(_p), _tmp,			\
+    clib_warning("path:[%d:%U]:" _fmt,				\
+		 fib_path_get_index(_p), format_fib_path, _p, 0,\
 		 ##_args);					\
     vec_free(_tmp);						\
 }
@@ -446,12 +443,17 @@ fib_path_from_fib_node (fib_node_t *node)
 u8 *
 format_fib_path (u8 * s, va_list * args)
 {
-    fib_path_t *path = va_arg (*args, fib_path_t *);
+    fib_node_index_t path_index = va_arg (*args, fib_node_index_t);
+    u32 indent = va_arg (*args, u32);
     vnet_main_t * vnm = vnet_get_main();
     fib_path_oper_attribute_t oattr;
     fib_path_cfg_attribute_t cattr;
+    fib_path_t *path;
 
-    s = format (s, "      index:%d ", fib_path_get_index(path));
+    path = fib_path_get(path_index);
+
+    s = format (s, "%Upath:[%d] ", format_white_space, indent,
+                fib_path_get_index(path));
     s = format (s, "pl-index:%d ", path->fp_pl_index);
     s = format (s, "%U ", format_dpo_proto, path->fp_nh_proto);
     s = format (s, "weight=%d ", path->fp_weight);
@@ -473,7 +475,7 @@ format_fib_path (u8 * s, va_list * args)
 	    }
 	}
     }
-    s = format(s, "\n       ");
+    s = format(s, "\n%U", format_white_space, indent+2);
 
     switch (path->fp_type)
     {
@@ -501,19 +503,20 @@ format_fib_path (u8 * s, va_list * args)
 	}
 	if (!dpo_id_is_valid(&path->fp_dpo))
 	{
-	    s = format(s, "\n          unresolved");
+	    s = format(s, "\n%Uunresolved", format_white_space, indent+2);
 	}
 	else
 	{
-	    s = format(s, "\n          %U",
-		       format_dpo_id,
+	    s = format(s, "\n%U%U",
+		       format_white_space, indent,
+                       format_dpo_id,
 		       &path->fp_dpo, 13);
 	}
 	break;
     case FIB_PATH_TYPE_ATTACHED:
 	if (path->fp_oper_flags & FIB_PATH_OPER_FLAG_DROP)
 	{
-	    s = format (s, " if_index:%d", path->attached_next_hop.fp_interface);
+	    s = format (s, "if_index:%d", path->attached_next_hop.fp_interface);
 	}
 	else
 	{
@@ -551,7 +554,7 @@ format_fib_path (u8 * s, va_list * args)
 
 	break;
     case FIB_PATH_TYPE_UDP_ENCAP:
-        s = format (s, " UDP-encap ID:%d", path->udp_encap.fp_udp_encap_id);
+        s = format (s, "UDP-encap ID:%d", path->udp_encap.fp_udp_encap_id);
         break;
     case FIB_PATH_TYPE_BIER_TABLE:
         s = format (s, "via bier-table:[%U}",
@@ -562,14 +565,7 @@ format_fib_path (u8 * s, va_list * args)
                     path->fp_dpo.dpoi_index);
         break;
     case FIB_PATH_TYPE_BIER_FMASK:
-        s = format (s, "via %U",
-                    format_ip46_address,
-                    &path->bier_fmask.fp_nh,
-                    IP46_TYPE_ANY);
-	s = format (s, " in BIER-fib:%d",
-		    path->bier_fmask.fp_bier_fib,
-		    path->fp_via_fib); 
-	s = format (s, " via-fmask:%d", path->fp_via_bier_fmask); 
+	s = format (s, "via-fmask:%d", path->bier_fmask.fp_bier_fmask); 
 	s = format (s, " via-dpo:[%U:%d]",
 		    format_dpo_type, path->fp_dpo.dpoi_type, 
 		    path->fp_dpo.dpoi_index);
@@ -586,7 +582,7 @@ format_fib_path (u8 * s, va_list * args)
 	if (dpo_id_is_valid(&path->fp_dpo))
 	{
 	    s = format(s, "%U", format_dpo_id,
-		       &path->fp_dpo, 2);
+		       &path->fp_dpo, indent+2);
 	}
 	break;
     }
@@ -604,29 +600,6 @@ fib_path_format (fib_node_index_t pi, u8 *s)
     return (format (s, "%U", format_fib_path, path));
 }
 
-u8 *
-fib_path_adj_format (fib_node_index_t pi,
-		     u32 indent,
-		     u8 *s)
-{
-    fib_path_t *path;
-
-    path = fib_path_get(pi);
-    ASSERT(NULL != path);
-
-    if (!dpo_id_is_valid(&path->fp_dpo))
-    {
-	s = format(s, " unresolved");
-    }
-    else
-    {
-	s = format(s, "%U", format_dpo_id,
-		   &path->fp_dpo, 2);
-    }
-
-    return (s);
-}
-
 /*
  * fib_path_last_lock_gone
  *
@@ -832,7 +805,7 @@ static void
 fib_path_bier_fmask_update (fib_path_t *path,
                             dpo_id_t *dpo)
 {
-    bier_fmask_contribute_forwarding(path->fp_via_bier_fmask, dpo);
+    bier_fmask_contribute_forwarding(path->bier_fmask.fp_bier_fmask, dpo);
 
     /*
      * if we are stakcing on the drop, then the path is not resolved
@@ -893,12 +866,8 @@ fib_path_unresolve (fib_path_t *path)
 	}
 	break;
     case FIB_PATH_TYPE_BIER_FMASK:
-	if (FIB_NODE_INDEX_INVALID != path->fp_via_bier_fmask)
-	{
-	    bier_fmask_child_remove(path->fp_via_bier_fmask,
-                                    path->fp_sibling);
-	    path->fp_via_bier_fmask = FIB_NODE_INDEX_INVALID;
-	}
+        bier_fmask_child_remove(path->fp_via_bier_fmask,
+                                path->fp_sibling);
 	break;
     case FIB_PATH_TYPE_BIER_IMP:
         bier_imp_unlock(path->fp_dpo.dpoi_index);
@@ -1313,8 +1282,7 @@ fib_path_create (fib_node_index_t pl_index,
     else if (rpath->frp_flags & FIB_ROUTE_PATH_BIER_FMASK)
     {
         path->fp_type = FIB_PATH_TYPE_BIER_FMASK;
-        path->bier_fmask.fp_nh = rpath->frp_addr;
-        path->bier_fmask.fp_bier_fib = rpath->frp_bier_fib_index;
+        path->bier_fmask.fp_bier_fmask = rpath->frp_bier_fmask;
     }
     else if (rpath->frp_flags & FIB_ROUTE_PATH_BIER_IMP)
     {
@@ -1549,14 +1517,8 @@ fib_path_cmp_i (const fib_path_t *path1,
 	    }
 	    break;
 	case FIB_PATH_TYPE_BIER_FMASK:
-	    res = ip46_address_cmp(&path1->bier_fmask.fp_nh,
-				   &path2->bier_fmask.fp_nh);
- 
-	    if (0 == res)
-	    {
-		res = (path1->bier_fmask.fp_bier_fib -
-                       path2->bier_fmask.fp_bier_fib);
-	    }
+            res = (path1->bier_fmask.fp_bier_fmask -
+                   path2->bier_fmask.fp_bier_fmask);
 	    break;
 	case FIB_PATH_TYPE_BIER_IMP:
             res = (path1->bier_imp.fp_bier_imp -
@@ -1691,13 +1653,7 @@ fib_path_cmp_w_route_path (fib_node_index_t path_index,
             }
 	    break;
 	case FIB_PATH_TYPE_BIER_FMASK:
-            res = ip46_address_cmp(&path->bier_fmask.fp_nh,
-                                   &rpath->frp_addr);
-
-            if (0 == res)
-            {
-                res = (path->bier_fmask.fp_bier_fib - rpath->frp_bier_fib_index);
-            }
+            res = (path->bier_fmask.fp_bier_fmask - rpath->frp_bier_fmask);
 	    break;
 	case FIB_PATH_TYPE_BIER_IMP:
             res = (path->bier_imp.fp_bier_imp - rpath->frp_bier_imp);
@@ -1944,26 +1900,14 @@ fib_path_resolve (fib_node_index_t path_index)
     case FIB_PATH_TYPE_BIER_FMASK:
     {
         /*
-         * Find the BIER f-mask to link to
-         */
-        bier_fmask_id_t fmid = {
-            .bfmi_nh = path->bier_fmask.fp_nh,
-            .bfmi_hdr_type = BIER_HDR_O_MPLS,
-        };
-
-        ASSERT(FIB_NODE_INDEX_INVALID == path->fp_via_bier_fmask);
-
-        path->fp_via_bier_fmask = bier_fmask_db_find(path->bier_fmask.fp_bier_fib,
-                                                &fmid);
-
-        /*
          * become a dependent child of the entry so the path is
          * informed when the forwarding for the entry changes.
          */
-        path->fp_sibling = bier_fmask_child_add(path->fp_via_bier_fmask,
+        path->fp_sibling = bier_fmask_child_add(path->bier_fmask.fp_bier_fmask,
                                                 FIB_NODE_TYPE_PATH,
                                                 fib_path_get_index(path));
 
+        path->fp_via_bier_fmask = path->bier_fmask.fp_bier_fmask;
         fib_path_bier_fmask_update(path, &path->fp_dpo);
 
         break;
@@ -1996,27 +1940,35 @@ fib_path_resolve (fib_node_index_t path_index)
 	break;
     case FIB_PATH_TYPE_DEAG:
     {
-	/*
-	 * Resolve via a lookup DPO.
-         * FIXME. control plane should add routes with a table ID
-	 */
-        lookup_input_t input;
-        lookup_cast_t cast;
-
-        cast = (path->fp_cfg_flags & FIB_PATH_CFG_FLAG_RPF_ID ?
-                LOOKUP_MULTICAST :
-                LOOKUP_UNICAST);
-        input = (path->fp_cfg_flags & FIB_PATH_CFG_FLAG_DEAG_SRC ?
-                LOOKUP_INPUT_SRC_ADDR :
-                LOOKUP_INPUT_DST_ADDR);
-
-        lookup_dpo_add_or_lock_w_fib_index(path->deag.fp_tbl_id,
-                                           path->fp_nh_proto,
-                                           cast,
-                                           input,
-                                           LOOKUP_TABLE_FROM_CONFIG,
-                                           &path->fp_dpo);
-	break;
+        if (DPO_PROTO_BIER == path->fp_nh_proto)
+        {
+            bier_disp_table_contribute_forwarding(path->deag.fp_tbl_id,
+                                                  &path->fp_dpo);
+        }
+        else
+        {
+            /*
+             * Resolve via a lookup DPO.
+             * FIXME. control plane should add routes with a table ID
+             */
+            lookup_input_t input;
+            lookup_cast_t cast;
+
+            cast = (path->fp_cfg_flags & FIB_PATH_CFG_FLAG_RPF_ID ?
+                    LOOKUP_MULTICAST :
+                    LOOKUP_UNICAST);
+            input = (path->fp_cfg_flags & FIB_PATH_CFG_FLAG_DEAG_SRC ?
+                     LOOKUP_INPUT_SRC_ADDR :
+                     LOOKUP_INPUT_DST_ADDR);
+
+            lookup_dpo_add_or_lock_w_fib_index(path->deag.fp_tbl_id,
+                                               path->fp_nh_proto,
+                                               cast,
+                                               input,
+                                               LOOKUP_TABLE_FROM_CONFIG,
+                                               &path->fp_dpo);
+        }
+        break;
     }
     case FIB_PATH_TYPE_RECEIVE:
 	/*
@@ -2109,7 +2061,7 @@ fib_path_get_resolving_index (fib_node_index_t path_index)
     case FIB_PATH_TYPE_RECURSIVE:
 	return (path->fp_via_fib);
     case FIB_PATH_TYPE_BIER_FMASK:
- 	return (path->fp_via_bier_fmask);
+ 	return (path->bier_fmask.fp_bier_fmask);
    case FIB_PATH_TYPE_BIER_TABLE:
        return (path->fp_via_bier_tbl);
    case FIB_PATH_TYPE_BIER_IMP:
@@ -2623,8 +2575,7 @@ fib_path_encode (fib_node_index_t path_list_index,
         api_rpath->rpath.frp_addr = path->attached_next_hop.fp_nh;
         break;
       case FIB_PATH_TYPE_BIER_FMASK:
-        api_rpath->rpath.frp_fib_index = path->bier_fmask.fp_bier_fib;
-        api_rpath->rpath.frp_addr = path->bier_fmask.fp_nh;
+        api_rpath->rpath.frp_bier_fmask = path->bier_fmask.fp_bier_fmask;
         break;
       case FIB_PATH_TYPE_SPECIAL:
         break;
@@ -2673,7 +2624,7 @@ show_fib_path_command (vlib_main_t * vm,
 	if (!pool_is_free_index(fib_path_pool, pi))
 	{
 	    path = fib_path_get(pi);
-	    u8 *s = fib_path_format(pi, NULL);
+	    u8 *s = format(NULL, "%U", format_fib_path, pi, 1);
 	    s = format(s, "children:");
 	    s = fib_node_children_format(path->fp_node.fn_children, s);
 	    vlib_cli_output (vm, "%s", s);
diff --git a/src/vnet/fib/fib_path.h b/src/vnet/fib/fib_path.h
index 861bda95933..70b2f503aa8 100644
--- a/src/vnet/fib/fib_path.h
+++ b/src/vnet/fib/fib_path.h
@@ -128,12 +128,7 @@ typedef enum fib_path_cfg_flags_t_ {
 } __attribute__ ((packed)) fib_path_cfg_flags_t;
 
 
-extern u8 *fib_path_format(fib_node_index_t pi, u8 *s);
-extern u8 *fib_path_adj_format(fib_node_index_t pi,
-			       u32 indent,
-			       u8 *s);
-
-extern u8 * format_fib_path(u8 * s, va_list * args);
+extern u8 *format_fib_path(u8 *s, va_list *args);
 
 extern fib_node_index_t fib_path_create(fib_node_index_t pl_index,
 					const fib_route_path_t *path);
diff --git a/src/vnet/fib/fib_path_list.c b/src/vnet/fib/fib_path_list.c
index 597a700a448..5201b5a14e8 100644
--- a/src/vnet/fib/fib_path_list.c
+++ b/src/vnet/fib/fib_path_list.c
@@ -126,16 +126,21 @@ fib_path_list_get_index (fib_path_list_t *path_list)
     return (path_list - fib_path_list_pool);
 }
 
-static u8 *
+u8 *
 format_fib_path_list (u8 * s, va_list * args)
 {
+    fib_node_index_t *path_index, path_list_index;
     fib_path_list_attribute_t attr;
-    fib_node_index_t *path_index;
     fib_path_list_t *path_list;
+    u32 indent;
 
-    path_list = va_arg (*args, fib_path_list_t *);
-    
-    s = format (s, "    index:%u", fib_path_list_get_index(path_list));
+    path_list_index = va_arg (*args, fib_node_index_t);
+    indent = va_arg (*args, u32);
+    path_list = fib_path_list_get(path_list_index);
+
+    s = format (s, "%Upath-list:[%d]",
+                format_white_space, indent,
+                fib_path_list_get_index(path_list));
     s = format (s, " locks:%u", path_list->fpl_node.fn_locks);
 
     if (FIB_PATH_LIST_FLAG_NONE != path_list->fpl_flags)
@@ -153,7 +158,7 @@ format_fib_path_list (u8 * s, va_list * args)
 
     vec_foreach (path_index, path_list->fpl_paths)
     {
-	s = fib_path_format(*path_index, s);
+	s = format(s, "%U", format_fib_path, *path_index, indent+2);
 	s = format(s, "\n");
     }
 
@@ -164,11 +169,7 @@ u8 *
 fib_path_list_format (fib_node_index_t path_list_index,
 		      u8 * s)
 {
-    fib_path_list_t *path_list;
-
-    path_list = fib_path_list_get(path_list_index);
-
-    return (format(s, "%U", format_fib_path_list, path_list));
+    return (format(s, "%U", format_fib_path_list, path_list_index, 4));
 }
 
 static uword
@@ -353,20 +354,7 @@ fib_path_list_mk_lb (fib_path_list_t *path_list,
     load_balance_path_t *nhs;
     fib_node_index_t *path_index;
 
-    nhs  = NULL;
-
-    if (!dpo_id_is_valid(dpo))
-    {
-        /*
-         * first time create
-         */
-        dpo_set(dpo,
-                DPO_LOAD_BALANCE,
-                fib_forw_chain_type_to_dpo_proto(fct),
-                load_balance_create(0,
-				    fib_forw_chain_type_to_dpo_proto(fct),
-				    0 /* FIXME FLOW HASH */));
-    }
+    nhs = NULL;
 
     /*
      * We gather the DPOs from resolved paths.
@@ -382,6 +370,12 @@ fib_path_list_mk_lb (fib_path_list_t *path_list,
      * Path-list load-balances, which if used, would be shared and hence
      * never need a load-balance map.
      */
+    dpo_set(dpo,
+            DPO_LOAD_BALANCE,
+            fib_forw_chain_type_to_dpo_proto(fct),
+            load_balance_create(vec_len(nhs),
+                                fib_forw_chain_type_to_dpo_proto(fct),
+                                0 /* FIXME FLOW HASH */));
     load_balance_multipath_update(dpo, nhs, LOAD_BALANCE_FLAG_NONE);
 
     FIB_PATH_LIST_DBG(path_list, "mk lb: %d", dpo->dpoi_index);
@@ -1146,6 +1140,7 @@ fib_path_list_copy_and_path_remove (fib_node_index_t orig_path_list_index,
 void
 fib_path_list_contribute_forwarding (fib_node_index_t path_list_index,
 				     fib_forward_chain_type_t fct,
+                                     fib_path_list_fwd_flags_t flags,
 				     dpo_id_t *dpo)
 {
     fib_path_list_t *path_list;
@@ -1153,6 +1148,18 @@ fib_path_list_contribute_forwarding (fib_node_index_t path_list_index,
     path_list = fib_path_list_get(path_list_index);
 
     fib_path_list_mk_lb(path_list, fct, dpo);
+
+    ASSERT(DPO_LOAD_BALANCE == dpo->dpoi_type);
+
+    /*
+     * If there's only one bucket in the load-balance then we can
+     * squash it out.
+     */
+    if ((1 == load_balance_n_buckets(dpo->dpoi_index)) &&
+        (FIB_PATH_LIST_FWD_FLAG_COLLAPSE & flags))
+    {
+        dpo_copy(dpo, load_balance_get_bucket(dpo->dpoi_index, 0));
+    }
 }
 
 /*
diff --git a/src/vnet/fib/fib_path_list.h b/src/vnet/fib/fib_path_list.h
index a54b79e2a6d..76870dc6c78 100644
--- a/src/vnet/fib/fib_path_list.h
+++ b/src/vnet/fib/fib_path_list.h
@@ -127,8 +127,18 @@ extern fib_node_index_t fib_path_list_path_remove (
 
 extern u32 fib_path_list_get_n_paths(fib_node_index_t pl_index);
 
+/**
+ * Flags to control how the path-list returns forwarding information
+ */
+typedef enum fib_path_list_fwd_flags_t_
+{
+    FIB_PATH_LIST_FWD_FLAG_NONE = 0,
+    FIB_PATH_LIST_FWD_FLAG_COLLAPSE = (1 << 0),
+} fib_path_list_fwd_flags_t;
+
 extern void fib_path_list_contribute_forwarding(fib_node_index_t path_list_index,
 						fib_forward_chain_type_t type,
+                                                fib_path_list_fwd_flags_t flags,
 						dpo_id_t *dpo);
 extern void fib_path_list_contribute_urpf(fib_node_index_t path_index,
 					  index_t urpf);
@@ -153,6 +163,8 @@ extern int fib_path_list_is_popular(fib_node_index_t path_list_index);
 extern dpo_proto_t fib_path_list_get_proto(fib_node_index_t path_list_index);
 extern u8 * fib_path_list_format(fib_node_index_t pl_index,
 				 u8 * s);
+extern u8 * format_fib_path_list(u8 * s, va_list *args);
+
 extern index_t fib_path_list_lb_map_add_or_lock(fib_node_index_t pl_index,
                                                 const fib_node_index_t *pis);
 extern u32 fib_path_list_find_rpath (fib_node_index_t path_list_index,
diff --git a/src/vnet/fib/fib_types.h b/src/vnet/fib/fib_types.h
index be6a24ee9cd..94c94228bb3 100644
--- a/src/vnet/fib/fib_types.h
+++ b/src/vnet/fib/fib_types.h
@@ -443,6 +443,11 @@ typedef struct fib_route_path_t_ {
          * UDP encap ID
          */
         u32 frp_udp_encap_id;
+
+        /**
+         * Resolving via a BIER Fmask
+         */
+        index_t frp_bier_fmask;
     };
     /**
      * [un]equal cost path weight