MTRIE Optimisations 2

1) 16-8-8 stride. Reduce trie depth walk traded with increased memory in the top PLY.
2) separate the vector of protocol-independent (PI) fib_table_t with the vector of protocol dependent (PD) FIBs. PD FIBs are large structures, we don't want to burn the memory for ech PD type
3) Go straight to the PD FIB in the data-path thus avoiding an indirection through, e.g., a PLY pool.

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

3 files changed, 32 insertions, 33 deletions

diff --git a/src/vnet/mpls/interface.c b/src/vnet/mpls/interface.c
index f631dc7652c..a085aaa2f19 100644
--- a/src/vnet/mpls/interface.c
+++ b/src/vnet/mpls/interface.c
@@ -18,6 +18,7 @@
 #include <vnet/vnet.h>
 #include <vnet/pg/pg.h>
 #include <vnet/mpls/mpls.h>
+#include <vnet/fib/mpls_fib.h>
 #include <vnet/fib/ip4_fib.h>
 #include <vnet/adj/adj_midchain.h>
 #include <vnet/dpo/classify_dpo.h>
diff --git a/src/vnet/mpls/mpls.h b/src/vnet/mpls/mpls.h
index 300f2cfd6be..b0125e60c63 100644
--- a/src/vnet/mpls/mpls.h
+++ b/src/vnet/mpls/mpls.h
@@ -30,29 +30,6 @@ typedef enum {
   MPLS_N_ERROR,
 } mpls_error_t;
 
-#define MPLS_FIB_DEFAULT_TABLE_ID 0
-
-/**
- * Type exposure is to allow the DP fast/inlined access
- */
-#define MPLS_FIB_KEY_SIZE 21
-#define MPLS_FIB_DB_SIZE (1 << (MPLS_FIB_KEY_SIZE-1))
-
-typedef struct mpls_fib_t_
-{
-  /**
-   * A hash table of entries. 21 bit key
-   * Hash table for reduced memory footprint
-   */
-  uword * mf_entries;
-
-  /**
-   * The load-balance indeices keyed by 21 bit label+eos bit.
-   * A flat array for maximum lookup performace.
-   */
-  index_t mf_lbs[MPLS_FIB_DB_SIZE];
-} mpls_fib_t;
-
 /**
  * @brief Definition of a callback for receiving MPLS interface state change
  * notifications
@@ -67,6 +44,9 @@ typedef struct {
   /**  A pool of all the MPLS FIBs */
   struct fib_table_t_ *fibs;
 
+  /**  A pool of all the MPLS FIBs */
+  struct mpls_fib_t_ *mpls_fibs;
+
   /** A hash table to lookup the mpls_fib by table ID */
   uword *fib_index_by_table_id;
 
diff --git a/src/vnet/mpls/mpls_api.c b/src/vnet/mpls/mpls_api.c
index a36a504608f..f1aef6c92c6 100644
--- a/src/vnet/mpls/mpls_api.c
+++ b/src/vnet/mpls/mpls_api.c
@@ -26,6 +26,7 @@
 #include <vnet/mpls/mpls_tunnel.h>
 #include <vnet/fib/fib_table.h>
 #include <vnet/fib/fib_api.h>
+#include <vnet/fib/mpls_fib.h>
 
 #include <vnet/vnet_msg_enum.h>
 
@@ -369,6 +370,21 @@ send_mpls_fib_details (vpe_api_main_t * am,
   vl_msg_api_send_shmem (q, (u8 *) & mp);
 }
 
+typedef struct vl_api_mpls_fib_dump_table_walk_ctx_t_
+{
+  fib_node_index_t *lfeis;
+} vl_api_mpls_fib_dump_table_walk_ctx_t;
+
+static int
+vl_api_mpls_fib_dump_table_walk (fib_node_index_t fei, void *arg)
+{
+  vl_api_mpls_fib_dump_table_walk_ctx_t *ctx = arg;
+
+  vec_add1 (ctx->lfeis, fei);
+
+  return (1);
+}
+
 static void
 vl_api_mpls_fib_dump_t_handler (vl_api_mpls_fib_dump_t * mp)
 {
@@ -376,28 +392,30 @@ vl_api_mpls_fib_dump_t_handler (vl_api_mpls_fib_dump_t * mp)
   unix_shared_memory_queue_t *q;
   mpls_main_t *mm = &mpls_main;
   fib_table_t *fib_table;
-  fib_node_index_t lfei, *lfeip, *lfeis = NULL;
-  mpls_label_t key;
+  mpls_fib_t *mpls_fib;
+  fib_node_index_t *lfeip = NULL;
   fib_prefix_t pfx;
   u32 fib_index;
   fib_route_path_encode_t *api_rpaths;
+  vl_api_mpls_fib_dump_table_walk_ctx_t ctx = {
+    .lfeis = NULL,
+  };
 
   q = vl_api_client_index_to_input_queue (mp->client_index);
   if (q == 0)
     return;
 
   /* *INDENT-OFF* */
-  pool_foreach (fib_table, mm->fibs,
+  pool_foreach (mpls_fib, mm->mpls_fibs,
   ({
-    hash_foreach(key, lfei, fib_table->mpls.mf_entries,
-    ({
-  vec_add1(lfeis, lfei);
-    }));
+    mpls_fib_table_walk (mpls_fib,
+                         vl_api_mpls_fib_dump_table_walk,
+                         &ctx);
   }));
   /* *INDENT-ON* */
-  vec_sort_with_function (lfeis, fib_entry_cmp_for_sort);
+  vec_sort_with_function (ctx.lfeis, fib_entry_cmp_for_sort);
 
-  vec_foreach (lfeip, lfeis)
+  vec_foreach (lfeip, ctx.lfeis)
   {
     fib_entry_get_prefix (*lfeip, &pfx);
     fib_index = fib_entry_get_fib_index (*lfeip);
@@ -410,7 +428,7 @@ vl_api_mpls_fib_dump_t_handler (vl_api_mpls_fib_dump_t * mp)
     vec_free (api_rpaths);
   }
 
-  vec_free (lfeis);
+  vec_free (ctx.lfeis);
 }
 
 /*