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, 40 insertions, 4 deletions

diff --git a/src/vnet/fib/fib_entry.h b/src/vnet/fib/fib_entry.h
index cd2a685b765..cd954e3a15c 100644
--- a/src/vnet/fib/fib_entry.h
+++ b/src/vnet/fib/fib_entry.h
@@ -29,6 +29,10 @@
  */
 typedef enum fib_source_t_ {
     /**
+     * An invalid source of value 0
+     */
+    FIB_SOURCE_INVALID,
+    /**
      * Marker. Add new values after this one.
      */
     FIB_SOURCE_FIRST,
@@ -142,6 +146,7 @@ STATIC_ASSERT (sizeof(fib_source_t) == 1,
 #define FIB_SOURCE_MAX (FIB_SOURCE_LAST+1)
 
 #define FIB_SOURCES {					\
+    [FIB_SOURCE_INVALID] = "invalid",			\
     [FIB_SOURCE_SPECIAL] = "special",			\
     [FIB_SOURCE_INTERFACE] = "interface",		\
     [FIB_SOURCE_PROXY] = "proxy",                       \
@@ -377,6 +382,29 @@ typedef struct fib_entry_src_t_ {
 } fib_entry_src_t;
 
 /**
+ * FIB entry flags.
+ *  these are stored in the pad space within the fib_node_t
+ */
+typedef enum fib_entry_node_attribute_t_
+{
+    /**
+     * FIB entry has multiple sources, so the fe_srcs union
+     * uses the vector
+     */
+    FIB_ENTRY_NODE_ATTR_MULTIPLE_SRCS,
+} fib_entry_node_attribute_t;
+
+#define FIB_ENTRY_NODE_FLAG_NAMES {                            \
+    [FIB_ENTRY_NODE_ATTR_MULTIPLE_SRCS] = "multiple-srcs",     \
+}
+
+typedef enum fib_entry_node_flags_t_
+{
+    FIB_ENTRY_NODE_FLAG_MULTIPLE_SRCS = (1 << FIB_ENTRY_NODE_ATTR_MULTIPLE_SRCS),
+} fib_entry_node_flags_t;
+
+
+/**
  * An entry in a FIB table.
  *
  * This entry represents a route added to the FIB that is stored
@@ -409,12 +437,20 @@ typedef struct fib_entry_t_ {
      *     type to derive the EOS bit value.
      */
     dpo_id_t fe_lb;
+
     /**
-     * Vector of source infos.
-     * Most entries will only have 1 source. So we optimise for memory usage,
-     * which is preferable since we have many entries.
+     * Source info.
+     * in the majority of cases a FIB entry will have only one source.
+     * so to save the extra memory allocation of the source's vector, we
+     * store space for one source inline. When two sources are present, 
+     * we burn extra memory.
+     * The union is switched based on the FIB_ENTRY_NODE_FLAG_MULTIPLE_SRCS
      */
-    fib_entry_src_t *fe_srcs;
+    union {
+        fib_entry_src_t *fe_srcs;
+        fib_entry_src_t fe_src;
+    } fe_u_src;
+
     /**
      * the path-list for which this entry is a child. This is also the path-list
      * that is contributing forwarding for this entry.