fib: Changes to interpose source

Type: improvement

1) stack the interpose on any path-extensions (e.g. labels) from the
next best source
2) allow more than 1 source to contribute a DPO for a given prefix

Signed-off-by: Neale Ranns <neale@graphiant.com>
Change-Id: Idc2fbb36cfbd2387081765d8af0f1fbe61612160

6 files changed, 227 insertions, 22 deletions

diff --git a/src/plugins/unittest/fib_test.c b/src/plugins/unittest/fib_test.c
index 1a2ba4a4b00..b9b77ba479f 100644
--- a/src/plugins/unittest/fib_test.c
+++ b/src/plugins/unittest/fib_test.c
@@ -43,6 +43,8 @@
 
 #include <vlib/unix/plugin.h>
 
+// clang-format off
+
 /*
  * Add debugs for passing tests
  */
@@ -446,6 +448,46 @@ fib_test_validate_lb_v (const load_balance_t *lb,
 			    exp->label_stack_o_adj.adj);
 	    }
 	    break;
+	case FT_LB_LABEL_CHAIN_O_ADJ:
+	    {
+		const mpls_label_dpo_t *mld = NULL;
+                mpls_label_dpo_flags_t mf;
+                mpls_label_t hdr;
+		u32 ii;
+
+                mf = ((exp->label_chain_o_adj.mode ==
+                       FIB_MPLS_LSP_MODE_UNIFORM) ?
+                      MPLS_LABEL_DPO_FLAG_UNIFORM_MODE :
+                      MPLS_LABEL_DPO_FLAG_NONE);
+
+                for (ii = 0; ii < exp->label_chain_o_adj.label_chain_size; ii++)
+                {
+                    FIB_TEST_LB((mpls_label_dpo_get_type(mf) == dpo->dpoi_type),
+                                "bucket %d stacks on %U",
+                                bucket,
+                                format_dpo_type, dpo->dpoi_type);
+                    mld = mpls_label_dpo_get(dpo->dpoi_index);
+
+		    hdr = clib_net_to_host_u32(mld->mld_hdr[0].label_exp_s_ttl);
+		    FIB_TEST_LB((vnet_mpls_uc_get_label(hdr) ==
+				 exp->label_chain_o_adj.label_chain[ii]),
+				"bucket %d stacks on label %d",
+				bucket,
+				exp->label_chain_o_adj.label_chain[ii]);
+                    dpo = &mld->mld_dpo;
+		}
+
+		FIB_TEST_LB((DPO_ADJACENCY_INCOMPLETE == mld->mld_dpo.dpoi_type),
+			    "bucket %d label stacks on %U",
+			    bucket,
+			    format_dpo_type, mld->mld_dpo.dpoi_type);
+
+		FIB_TEST_LB((exp->label_chain_o_adj.adj == mld->mld_dpo.dpoi_index),
+			    "bucket %d label stacks on adj %d",
+			    bucket,
+			    exp->label_chain_o_adj.adj);
+	    }
+	    break;
 	case FT_LB_LABEL_O_ADJ:
 	    {
 		const mpls_label_dpo_t *mld;
@@ -9667,6 +9709,82 @@ fib_test_inherit (void)
                                       &adj_o_10_10_10_3),
              "%U via 10.10.10.1",
              format_fib_prefix, &pfx_11_11_11_11_s_32);
+    dpo_reset(&interposer);
+    fib_table_entry_delete(0, &pfx_11_11_11_11_s_32, FIB_SOURCE_API);
+
+    /*
+     * add an interposer to a source with path-extensions
+     */
+    fib_mpls_label_t *l3300 = NULL, fml_3300 = {
+        .fml_value = 3300,
+    };
+    vec_add1(l3300, fml_3300);
+    fib_table_entry_update_one_path(0,
+                                    &pfx_11_11_11_11_s_32,
+                                    FIB_SOURCE_API,
+                                    FIB_ENTRY_FLAG_NONE,
+                                    DPO_PROTO_IP4,
+                                    &nh_10_10_10_3,
+                                    tm->hw[0]->sw_if_index,
+                                    ~0,
+                                    1,
+                                    l3300,
+                                    FIB_ROUTE_PATH_FLAG_NONE);
+
+    mpls_label_dpo_create(l99,
+                          MPLS_EOS,
+                          DPO_PROTO_IP4,
+                          MPLS_LABEL_DPO_FLAG_NONE,
+                          punt_dpo_get(DPO_PROTO_MPLS),
+                          &interposer);
+
+    adj_index_t ai_mpls_10_10_10_3 = adj_nbr_add_or_lock(FIB_PROTOCOL_IP4,
+                                                         VNET_LINK_MPLS,
+                                                         &nh_10_10_10_3,
+                                                         tm->hw[0]->sw_if_index);
+    fib_test_lb_bucket_t l3300_o_10_10_10_3 = {
+        .type = FT_LB_LABEL_O_ADJ,
+        .label_o_adj = {
+            .adj = ai_mpls_10_10_10_3,
+            .label = 3300,
+            .eos = MPLS_EOS,
+        },
+    };
+    fib_test_lb_bucket_t lchain_o_10_10_10_3 = {
+        .type = FT_LB_LABEL_CHAIN_O_ADJ,
+        .label_chain_o_adj = {
+            .adj = ai_mpls_10_10_10_3,
+            .label_chain_size = 2,
+            .label_chain = {
+                99, 3300
+            },
+            .eos = MPLS_EOS,
+        },
+    };
+
+    fei = fib_table_entry_special_dpo_add(0,
+                                          &pfx_11_11_11_11_s_32,
+                                          FIB_SOURCE_SPECIAL,
+                                          FIB_ENTRY_FLAG_INTERPOSE,
+                                          &interposer);
+
+    FIB_TEST(!fib_test_validate_entry(fei,
+                                      FIB_FORW_CHAIN_TYPE_UNICAST_IP4,
+                                      1,
+                                      &lchain_o_10_10_10_3),
+             "%U via interposer & mpls on adj",
+             format_fib_prefix, &pfx_11_11_11_11_s_32);
+
+    fib_table_entry_special_remove(0,
+                                   &pfx_11_11_11_11_s_32,
+                                   FIB_SOURCE_SPECIAL);
+    FIB_TEST(!fib_test_validate_entry(fei,
+                                      FIB_FORW_CHAIN_TYPE_UNICAST_IP4,
+                                      1,
+                                      &l3300_o_10_10_10_3),
+             "%U via 10.10.10.1",
+             format_fib_prefix, &pfx_11_11_11_11_s_32);
+    adj_unlock(ai_mpls_10_10_10_3);
 
     /*
      * remove and re-add the second best API source while the interpose
@@ -9680,11 +9798,11 @@ fib_test_inherit (void)
     FIB_TEST(!fib_test_validate_entry(fei,
                                       FIB_FORW_CHAIN_TYPE_UNICAST_IP4,
                                       1,
-                                      &l99_o_10_10_10_3),
+                                      &lchain_o_10_10_10_3),
              "%U via interposer adj",
              format_fib_prefix,&pfx_11_11_11_11_s_32);
 
-    FIB_TEST(2 == pool_elts(mpls_label_dpo_pool),
+    FIB_TEST(3 == pool_elts(mpls_label_dpo_pool),
              "MPLS label pool: %d",
              pool_elts(mpls_label_dpo_pool));
 
@@ -9756,6 +9874,18 @@ fib_test_inherit (void)
      * multiple interpose sources on the same entry. Only the high
      * priority source gets to add the interpose.
      */
+    fib_table_entry_update_one_path(0,
+                                    &pfx_11_11_11_11_s_32,
+                                    FIB_SOURCE_API,
+                                    FIB_ENTRY_FLAG_NONE,
+                                    DPO_PROTO_IP4,
+                                    &nh_10_10_10_3,
+                                    tm->hw[0]->sw_if_index,
+                                    ~0,
+                                    1,
+                                    NULL,
+                                    FIB_ROUTE_PATH_FLAG_NONE);
+
     dpo_id_t interposer2 = DPO_INVALID;
     fib_mpls_label_t *l100 = NULL, fml_100 = {
         .fml_value = 100,
@@ -9774,10 +9904,23 @@ fib_test_inherit (void)
                                           FIB_SOURCE_CLASSIFY,
                                           FIB_ENTRY_FLAG_INTERPOSE,
                                           &interposer2);
+
+    fib_test_lb_bucket_t lc100_o_10_10_10_3 = {
+        .type = FT_LB_LABEL_CHAIN_O_ADJ,
+        .label_chain_o_adj = {
+            .adj = ai_10_10_10_3,
+            .label_chain_size = 2,
+            .label_chain = {
+                99, 100
+            },
+            .eos = MPLS_EOS,
+        },
+    };
+
     FIB_TEST(!fib_test_validate_entry(fei,
                                       FIB_FORW_CHAIN_TYPE_UNICAST_IP4,
                                       1,
-                                      &l99_o_10_10_10_3),
+                                      &lc100_o_10_10_10_3),
              "%U via interposer label 99",
              format_fib_prefix,&pfx_11_11_11_11_s_32);
 
@@ -9800,6 +9943,7 @@ fib_test_inherit (void)
              format_fib_prefix,&pfx_11_11_11_11_s_32);
 
     fib_table_entry_delete(0, &pfx_11_11_11_0_s_24, FIB_SOURCE_API);
+    fib_table_entry_delete(0, &pfx_11_11_11_11_s_32, FIB_SOURCE_API);
     FIB_TEST(!fib_test_validate_entry(fei,
                                       FIB_FORW_CHAIN_TYPE_UNICAST_IP4,
                                       1,
@@ -10626,3 +10770,5 @@ fib_test_init (vlib_main_t *vm)
 }
 
 VLIB_INIT_FUNCTION (fib_test_init);
+
+// clang-format on
diff --git a/src/vnet/fib/.clang-format b/src/vnet/fib/.clang-format
new file mode 100644
index 00000000000..9d159247d51
--- /dev/null
+++ b/src/vnet/fib/.clang-format
@@ -0,0 +1,2 @@
+DisableFormat: true
+SortIncludes: false
diff --git a/src/vnet/fib/fib_entry.c b/src/vnet/fib/fib_entry.c
index a5fab8551ce..6edf31b47f3 100644
--- a/src/vnet/fib/fib_entry.c
+++ b/src/vnet/fib/fib_entry.c
@@ -473,7 +473,7 @@ fib_entry_contribute_forwarding (fib_node_index_t fib_entry_index,
              *      then up on the right trigger is more code. i favour the latter.
              */
             fib_entry_src_mk_lb(fib_entry,
-                                fib_entry_get_best_src_i(fib_entry),
+                                fib_entry_get_best_source(fib_entry_index),
                                 fct,
                                 &tmp);
 
@@ -1435,7 +1435,7 @@ fib_entry_recursive_loop_detect (fib_node_index_t entry_index,
             FOR_EACH_DELEGATE_CHAIN(fib_entry, fdt, fed,
             {
                 fib_entry_src_mk_lb(fib_entry,
-                                    fib_entry_get_best_src_i(fib_entry),
+                                    fib_entry_get_best_source(entry_index),
                                     fib_entry_delegate_type_to_chain_type(fdt),
                                     &fed->fd_dpo);
 	    });
diff --git a/src/vnet/fib/fib_entry_src.c b/src/vnet/fib/fib_entry_src.c
index 7f4db6a071b..503473a6099 100644
--- a/src/vnet/fib/fib_entry_src.c
+++ b/src/vnet/fib/fib_entry_src.c
@@ -253,7 +253,7 @@ typedef struct fib_entry_src_collect_forwarding_ctx_t_
 {
     load_balance_path_t *next_hops;
     const fib_entry_t *fib_entry;
-    const fib_entry_src_t *esrc;
+    i32 start_source_index, end_source_index;
     fib_forward_chain_type_t fct;
     int n_recursive_constrained;
     u16 preference;
@@ -263,15 +263,16 @@ typedef struct fib_entry_src_collect_forwarding_ctx_t_
  * @brief Determine whether this FIB entry should use a load-balance MAP
  * to support PIC edge fast convergence
  */
-load_balance_flags_t
-fib_entry_calc_lb_flags (fib_entry_src_collect_forwarding_ctx_t *ctx)
+static load_balance_flags_t
+fib_entry_calc_lb_flags (fib_entry_src_collect_forwarding_ctx_t *ctx,
+                         const fib_entry_src_t *esrc)
 {
     /**
      * We'll use a LB map if the path-list has multiple recursive paths.
      * recursive paths implies BGP, and hence scale.
      */
     if (ctx->n_recursive_constrained > 1 &&
-        fib_path_list_is_popular(ctx->esrc->fes_pl))
+        fib_path_list_is_popular(esrc->fes_pl))
     {
         return (LOAD_BALANCE_FLAG_USES_MAP);
     }
@@ -419,6 +420,7 @@ fib_entry_src_collect_forwarding (fib_node_index_t pl_index,
                                   void *arg)
 {
     fib_entry_src_collect_forwarding_ctx_t *ctx;
+    const fib_entry_src_t *esrc;
     fib_path_ext_t *path_ext;
     u32 n_nhs;
 
@@ -426,6 +428,11 @@ fib_entry_src_collect_forwarding (fib_node_index_t pl_index,
     n_nhs = vec_len(ctx->next_hops);
 
     /*
+     * walk the paths and extension of the best non-interpose source
+     */
+    esrc = &ctx->fib_entry->fe_srcs[ctx->end_source_index];
+
+    /*
      * if the path is not resolved, don't include it.
      */
     if (!fib_path_is_resolved(path_index))
@@ -457,7 +464,7 @@ fib_entry_src_collect_forwarding (fib_node_index_t pl_index,
     /*
      * get the matching path-extension for the path being visited.
      */
-    path_ext = fib_path_ext_list_find_by_path_index(&ctx->esrc->fes_path_exts,
+    path_ext = fib_path_ext_list_find_by_path_index(&esrc->fes_path_exts,
                                                     path_index);
 
     if (NULL != path_ext)
@@ -514,14 +521,26 @@ fib_entry_src_collect_forwarding (fib_node_index_t pl_index,
          */
         const fib_entry_src_vft_t *vft;
 
-        vft = fib_entry_src_get_vft(ctx->esrc);
+        /*
+         * roll up the sources that are interposes
+         */
+        i32 index;
 
-        if (NULL != vft->fesv_contribute_interpose)
+        for (index = ctx->end_source_index;
+             index >= ctx->start_source_index;
+             index--)
         {
             const dpo_id_t *interposer;
 
-            interposer = vft->fesv_contribute_interpose(ctx->esrc,
-                                                        ctx->fib_entry);
+            esrc = &ctx->fib_entry->fe_srcs[index];
+            vft = fib_entry_src_get_vft(esrc);
+
+            if (!(esrc->fes_flags & FIB_ENTRY_SRC_FLAG_CONTRIBUTING) ||
+                !(esrc->fes_entry_flags & FIB_ENTRY_FLAG_INTERPOSE))
+                continue;
+
+            ASSERT(vft->fesv_contribute_interpose);
+            interposer = vft->fesv_contribute_interpose(esrc, ctx->fib_entry);
 
             if (NULL != interposer)
             {
@@ -542,11 +561,40 @@ fib_entry_src_collect_forwarding (fib_node_index_t pl_index,
 
 void
 fib_entry_src_mk_lb (fib_entry_t *fib_entry,
-		     const fib_entry_src_t *esrc,
+                     fib_source_t source,
 		     fib_forward_chain_type_t fct,
 		     dpo_id_t *dpo_lb)
 {
+    const fib_entry_src_t *esrc;
     dpo_proto_t lb_proto;
+    u32 start, end;
+
+    /*
+     * The source passed here is the 'best', i.e. the one the client
+     * wants. however, if it's an interpose then it does not contribute
+     * the forwarding, the next best source that is not an interpose does.
+     * So roll down the sources, to find the best non-interpose
+     */
+    vec_foreach_index (start, fib_entry->fe_srcs)
+    {
+        if (source == fib_entry->fe_srcs[start].fes_src)
+            break;
+    }
+    for (end = start; end < vec_len (fib_entry->fe_srcs); end++)
+    {
+        if (!(fib_entry->fe_srcs[end].fes_entry_flags &
+              FIB_ENTRY_FLAG_INTERPOSE) &&
+            (fib_entry->fe_srcs[end].fes_flags &
+             FIB_ENTRY_SRC_FLAG_CONTRIBUTING))
+            break;
+    }
+    if (end == vec_len(fib_entry->fe_srcs))
+    {
+        /* didn't find any contributing non-interpose sources */
+        end = start;
+    }
+
+    esrc = &fib_entry->fe_srcs[end];
 
     /*
      * If the entry has path extensions then we construct a load-balance
@@ -554,12 +602,13 @@ fib_entry_src_mk_lb (fib_entry_t *fib_entry,
      * Otherwise we use the load-balance of the path-list
      */
     fib_entry_src_collect_forwarding_ctx_t ctx = {
-        .esrc = esrc,
         .fib_entry = fib_entry,
         .next_hops = NULL,
         .n_recursive_constrained = 0,
         .fct = fct,
         .preference = 0xffff,
+        .start_source_index = start,
+        .end_source_index = end,
     };
 
     /*
@@ -644,7 +693,7 @@ fib_entry_src_mk_lb (fib_entry_t *fib_entry,
     {
         load_balance_multipath_update(dpo_lb,
                                       ctx.next_hops,
-                                      fib_entry_calc_lb_flags(&ctx));
+                                      fib_entry_calc_lb_flags(&ctx, esrc));
         vec_free(ctx.next_hops);
 
         /*
@@ -688,11 +737,9 @@ fib_entry_src_action_install (fib_entry_t *fib_entry,
      * tables
      */
     fib_forward_chain_type_t fct;
-    fib_entry_src_t *esrc;
     int insert;
 
     fct = fib_entry_get_default_chain_type(fib_entry);
-    esrc = fib_entry_src_find(fib_entry, source);
 
     /*
      * Every entry has its own load-balance object. All changes to the entry's
@@ -702,7 +749,7 @@ fib_entry_src_action_install (fib_entry_t *fib_entry,
      */
     insert = !dpo_id_is_valid(&fib_entry->fe_lb);
 
-    fib_entry_src_mk_lb(fib_entry, esrc, fct, &fib_entry->fe_lb);
+    fib_entry_src_mk_lb(fib_entry, source, fct, &fib_entry->fe_lb);
 
     ASSERT(dpo_id_is_valid(&fib_entry->fe_lb));
     FIB_ENTRY_DBG(fib_entry, "install: %d", fib_entry->fe_lb);
@@ -726,7 +773,7 @@ fib_entry_src_action_install (fib_entry_t *fib_entry,
 
     FOR_EACH_DELEGATE_CHAIN(fib_entry, fdt, fed,
     {
-        fib_entry_src_mk_lb(fib_entry, esrc,
+        fib_entry_src_mk_lb(fib_entry, source,
                             fib_entry_delegate_type_to_chain_type(fdt),
                             &fed->fd_dpo);
     });
diff --git a/src/vnet/fib/fib_entry_src.h b/src/vnet/fib/fib_entry_src.h
index 210507932c4..248cf6c4079 100644
--- a/src/vnet/fib/fib_entry_src.h
+++ b/src/vnet/fib/fib_entry_src.h
@@ -334,7 +334,7 @@ extern fib_forward_chain_type_t fib_entry_chain_type_fixup(const fib_entry_t *en
                                                            fib_forward_chain_type_t fct);
 
 extern void fib_entry_src_mk_lb (fib_entry_t *fib_entry,
-				 const fib_entry_src_t *esrc,
+				 fib_source_t source,
 				 fib_forward_chain_type_t fct,
 				 dpo_id_t *dpo_lb);
 
diff --git a/src/vnet/fib/fib_test.h b/src/vnet/fib/fib_test.h
index b2abcf537fa..6bedd9ecaa5 100644
--- a/src/vnet/fib/fib_test.h
+++ b/src/vnet/fib/fib_test.h
@@ -27,6 +27,7 @@
 typedef enum fib_test_lb_bucket_type_t_ {
     FT_LB_LABEL_O_ADJ,
     FT_LB_LABEL_STACK_O_ADJ,
+    FT_LB_LABEL_CHAIN_O_ADJ,
     FT_LB_LABEL_O_LB,
     FT_LB_O_LB,
     FT_LB_MPLS_DISP_PIPE_O_ADJ,
@@ -55,6 +56,15 @@ typedef struct fib_test_lb_bucket_t_ {
 	struct
 	{
 	    mpls_eos_bit_t eos;
+	    mpls_label_t label_chain[8];
+            fib_mpls_lsp_mode_t mode;
+	    u8 label_chain_size;
+	    u8 ttl;
+	    adj_index_t adj;
+	} label_chain_o_adj;
+	struct
+	{
+	    mpls_eos_bit_t eos;
 	    mpls_label_t label_stack[8];
             fib_mpls_lsp_mode_t mode;
 	    u8 label_stack_size;