FIB: optimise for src memory allocations

Most FIB entries will only ever have one source providing forwarding
information. Currently the source infom is stored in a vector of sources
on the FIB entry. Change this to a union of one source inline and a vector.
This saves the need to alloc a vector of sources for each FIB entry.

before:
vpp# ip route add count 1500000 1.0.0.1/32 via 10.10.10.2 loop0
4.392857e5 routes/sec
vpp# ip route del count 1500000 1.0.0.1/32 via 10.10.10.2 loop0
9.175464e5 routes/sec
vpp# ip route add count 1500000 1.0.0.1/32 via 10.10.10.2 loop0
5.193375e5 routes/sec
vpp# sh fib mem
FIB memory
             Name               Size  in-use /allocated   totals
             Entry               72   1500011/ 1500011    108000792/108000792
         Entry Source            32   1500011/ 1500011    48000352/48000352

after:
vpp# ip route add count 1500000 1.0.0.1/32 via 10.10.10.2 loop0
4.726560e5 routes/sec
vpp# ip route del count 1500000 1.0.0.1/32 via 10.10.10.2 loop0
1.041629e6 routes/sec
vpp# ip route add count 1500000 1.0.0.1/32 via 10.10.10.2 loop0
5.702895e5 routes/sec
vpp# sh fib mem
FIB memory
             Name               Size  in-use /allocated   totals
             Entry               96   1500011/ 1500011    144001056/144001056
         Entry Source            32      0   /    0       0/0

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

1 files changed, 45 insertions, 22 deletions

diff --git a/src/vnet/fib/fib_entry.c b/src/vnet/fib/fib_entry.c
index 35716cacc29..a9ca0f20f6d 100644
--- a/src/vnet/fib/fib_entry.c
+++ b/src/vnet/fib/fib_entry.c
@@ -213,29 +213,33 @@ fib_entry_last_lock_gone (fib_node_t *node)
     FIB_ENTRY_DBG(fib_entry, "last-lock");
 
     fib_node_deinit(&fib_entry->fe_node);
-    // FIXME -RR Backwalk
 
     ASSERT(0 == vec_len(fib_entry->fe_delegates));
     vec_free(fib_entry->fe_delegates);
-    vec_free(fib_entry->fe_srcs);
+    if (fib_entry_has_multiple_srcs(fib_entry))
+    {
+        vec_free(fib_entry->fe_u_src.fe_srcs);
+    }
     pool_put(fib_entry_pool, fib_entry);
 }
 
-static fib_entry_src_t*
+static const fib_entry_src_t*
 fib_entry_get_best_src_i (const fib_entry_t *fib_entry)
 {
-    fib_entry_src_t *bsrc;
+    const fib_entry_src_t *bsrc;
 
     /*
      * the enum of sources is deliberately arranged in priority order
      */
-    if (0 == vec_len(fib_entry->fe_srcs))
+    if (fib_entry_has_multiple_srcs(fib_entry))
     {
-	bsrc = NULL;
+        ASSERT(vec_len(fib_entry->fe_u_src.fe_srcs));
+
+        bsrc = vec_elt_at_index(fib_entry->fe_u_src.fe_srcs, 0);
     }
     else
     {
-	bsrc = vec_elt_at_index(fib_entry->fe_srcs, 0);
+        bsrc = &fib_entry->fe_u_src.fe_src;
     }
 
     return (bsrc);
@@ -248,7 +252,7 @@ fib_entry_src_get_source (const fib_entry_src_t *esrc)
     {
 	return (esrc->fes_src);
     }
-    return (FIB_SOURCE_MAX);
+    return (FIB_SOURCE_INVALID);
 }
 
 static fib_entry_flag_t
@@ -262,6 +266,18 @@ fib_entry_src_get_flags (const fib_entry_src_t *esrc)
 }
 
 fib_entry_flag_t
+fib_entry_get_flags_i (const fib_entry_t *fib_entry)
+{
+    const fib_entry_src_t *esrc;
+
+    esrc = fib_entry_get_best_src_i(fib_entry);
+
+    ASSERT(esrc);
+
+    return (esrc->fes_entry_flags);
+}
+
+fib_entry_flag_t
 fib_entry_get_flags (fib_node_index_t fib_entry_index)
 {
     return (fib_entry_get_flags_i(fib_entry_get(fib_entry_index)));
@@ -330,11 +346,18 @@ fib_entry_show_memory (void)
 
     pool_foreach(entry, fib_entry_pool,
     ({
-	n_srcs += vec_len(entry->fe_srcs);
-	vec_foreach(esrc, entry->fe_srcs)
-	{
-	    n_exts += fib_path_ext_list_length(&esrc->fes_path_exts);
-	}
+        if (fib_entry_has_multiple_srcs(entry))
+        {
+            n_srcs += vec_len(entry->fe_u_src.fe_srcs);
+            vec_foreach(esrc, entry->fe_u_src.fe_srcs)
+            {
+                n_exts += fib_path_ext_list_length(&esrc->fes_path_exts);
+            }
+        }
+        else
+        {
+            n_exts += fib_path_ext_list_length(&entry->fe_u_src.fe_src.fes_path_exts);
+        }
     }));
 
     fib_show_memory_usage("Entry Source",
@@ -795,10 +818,10 @@ fib_entry_special_add (fib_node_index_t fib_entry_index,
 		       fib_entry_flag_t flags,
 		       const dpo_id_t *dpo)
 {
+    const fib_entry_src_t *bsrc;
     fib_source_t best_source;
     fib_entry_flag_t bflags;
     fib_entry_t *fib_entry;
-    fib_entry_src_t *bsrc;
 
     fib_entry = fib_entry_get(fib_entry_index);
 
@@ -816,10 +839,10 @@ fib_entry_special_update (fib_node_index_t fib_entry_index,
 			  fib_entry_flag_t flags,
 			  const dpo_id_t *dpo)
 {
+    const fib_entry_src_t *bsrc;
     fib_source_t best_source;
     fib_entry_flag_t bflags;
     fib_entry_t *fib_entry;
-    fib_entry_src_t *bsrc;
 
     fib_entry = fib_entry_get(fib_entry_index);
 
@@ -838,10 +861,10 @@ fib_entry_path_add (fib_node_index_t fib_entry_index,
 		    fib_entry_flag_t flags,
 		    const fib_route_path_t *rpath)
 {
+    const fib_entry_src_t *bsrc;
     fib_source_t best_source;
     fib_entry_flag_t bflags;
     fib_entry_t *fib_entry;
-    fib_entry_src_t *bsrc;
 
     ASSERT(1 == vec_len(rpath));
 
@@ -900,11 +923,11 @@ fib_entry_path_remove (fib_node_index_t fib_entry_index,
 		       fib_source_t source,
 		       const fib_route_path_t *rpath)
 {
+    const fib_entry_src_t *bsrc;
     fib_entry_src_flag_t sflag;
     fib_source_t best_source;
     fib_entry_flag_t bflags;
     fib_entry_t *fib_entry;
-    fib_entry_src_t *bsrc;
 
     ASSERT(1 == vec_len(rpath));
 
@@ -951,7 +974,7 @@ fib_entry_path_remove (fib_node_index_t fib_entry_index,
 	    bsrc = fib_entry_get_best_src_i(fib_entry);
 	    best_source = fib_entry_src_get_source(bsrc);
 
-	    if (FIB_SOURCE_MAX == best_source) {
+	    if (FIB_SOURCE_INVALID == best_source) {
 		/*
 		 * no more sources left. this entry is toast.
 		 */
@@ -996,11 +1019,11 @@ fib_entry_src_flag_t
 fib_entry_special_remove (fib_node_index_t fib_entry_index,
 			  fib_source_t source)
 {
+    const fib_entry_src_t *bsrc;
     fib_entry_src_flag_t sflag;
     fib_source_t best_source;
     fib_entry_flag_t bflags;
     fib_entry_t *fib_entry;
-    fib_entry_src_t *bsrc;
 
     fib_entry = fib_entry_get(fib_entry_index);
     ASSERT(NULL != fib_entry);
@@ -1041,7 +1064,7 @@ fib_entry_special_remove (fib_node_index_t fib_entry_index,
 	    bsrc = fib_entry_get_best_src_i(fib_entry);
 	    best_source = fib_entry_src_get_source(bsrc);
 
-	    if (FIB_SOURCE_MAX == best_source) {
+	    if (FIB_SOURCE_INVALID == best_source) {
 		/*
 		 * no more sources left. this entry is toast.
 		 */
@@ -1098,10 +1121,10 @@ fib_entry_update (fib_node_index_t fib_entry_index,
 		  fib_entry_flag_t flags,
 		  const fib_route_path_t *paths)
 {
+    const fib_entry_src_t *bsrc;
     fib_source_t best_source;
     fib_entry_flag_t bflags;
     fib_entry_t *fib_entry;
-    fib_entry_src_t *bsrc;
 
     fib_entry = fib_entry_get(fib_entry_index);
     ASSERT(NULL != fib_entry);
@@ -1361,8 +1384,8 @@ fib_entry_get_resolving_interface (fib_node_index_t entry_index)
 fib_source_t
 fib_entry_get_best_source (fib_node_index_t entry_index)
 {
+    const fib_entry_src_t *bsrc;
     fib_entry_t *fib_entry;
-    fib_entry_src_t *bsrc;
 
     fib_entry = fib_entry_get(entry_index);