fib: Table Replace

Type: feature

from the API doc, a table replace is:

"
    The use-case is that, for some unspecified reason, the control plane
    has a very different set of entries it wants in the table than VPP
    currently has. The CP would thus like to 'replace' VPP's current table
    only by specifying what the new set of entries shall be, i.e. it is not
    going to delete anything that already eixts.
    the CP delcartes the start of this procedure with this begin_replace
    API Call, and when it has populated all the entries it wants, it calls
    the below end_replace API. From this point on it is of coursce free
    to add and delete entries as usual.
    The underlying mechanism by which VPP implements this replace is
    purposefully left unspecified.
"

In the FIB, the algorithm is implemented using mark and sweep.

Algorithm goes:
1) replace_begin: this marks all the entries in that table as 'stale'
2) download all the entries that should be in this table
 - this clears the stale flag on those entries
3) signal the table converged: ip_table_replace_end
 - this removes all entries that are still stale

this procedure can be used when an agent first connects to VPP,
as an alternative to dump and diff state reconciliation.

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

7 files changed, 219 insertions, 17 deletions

diff --git a/src/vnet/fib/fib_entry.h b/src/vnet/fib/fib_entry.h
index 4ce28b1ae9d..f0e6e8d8aae 100644
--- a/src/vnet/fib/fib_entry.h
+++ b/src/vnet/fib/fib_entry.h
@@ -315,6 +315,10 @@ typedef enum fib_entry_src_attribute_t_ {
      */
     FIB_ENTRY_SRC_ATTRIBUTE_ACTIVE,
     /**
+     * the source is stale
+     */
+    FIB_ENTRY_SRC_ATTRIBUTE_STALE,
+    /**
      * the source is inherited from its cover
      */
     FIB_ENTRY_SRC_ATTRIBUTE_INHERITED,
@@ -329,6 +333,7 @@ typedef enum fib_entry_src_attribute_t_ {
     [FIB_ENTRY_SRC_ATTRIBUTE_ADDED]  = "added",	 \
     [FIB_ENTRY_SRC_ATTRIBUTE_CONTRIBUTING] = "contributing", \
     [FIB_ENTRY_SRC_ATTRIBUTE_ACTIVE] = "active", \
+    [FIB_ENTRY_SRC_ATTRIBUTE_STALE] = "stale",      \
     [FIB_ENTRY_SRC_ATTRIBUTE_INHERITED] = "inherited", \
 }
 
@@ -342,6 +347,7 @@ typedef enum fib_entry_src_flag_t_ {
     FIB_ENTRY_SRC_FLAG_ADDED  = (1 << FIB_ENTRY_SRC_ATTRIBUTE_ADDED),
     FIB_ENTRY_SRC_FLAG_CONTRIBUTING = (1 << FIB_ENTRY_SRC_ATTRIBUTE_CONTRIBUTING),
     FIB_ENTRY_SRC_FLAG_ACTIVE = (1 << FIB_ENTRY_SRC_ATTRIBUTE_ACTIVE),
+    FIB_ENTRY_SRC_FLAG_STALE = (1 << FIB_ENTRY_SRC_ATTRIBUTE_STALE),
     FIB_ENTRY_SRC_FLAG_INHERITED = (1 << FIB_ENTRY_SRC_ATTRIBUTE_INHERITED),
 } __attribute__ ((packed)) fib_entry_src_flag_t;
 
@@ -627,6 +633,8 @@ extern int fib_entry_is_sourced(fib_node_index_t fib_entry_index,
 extern fib_node_index_t fib_entry_get_path_list(fib_node_index_t fib_entry_index);
 extern int fib_entry_is_resolved(fib_node_index_t fib_entry_index);
 extern int fib_entry_is_host(fib_node_index_t fib_entry_index);
+extern int fib_entry_is_marked(fib_node_index_t fib_entry_index, fib_source_t source);
+extern void fib_entry_mark(fib_node_index_t fib_entry_index, fib_source_t source);
 extern void fib_entry_set_flow_hash_config(fib_node_index_t fib_entry_index,
                                            flow_hash_config_t hash_config);
 
diff --git a/src/vnet/fib/fib_entry_src.c b/src/vnet/fib/fib_entry_src.c
index 6ed13a328bd..176818abc0a 100644
--- a/src/vnet/fib/fib_entry_src.c
+++ b/src/vnet/fib/fib_entry_src.c
@@ -141,6 +141,44 @@ fib_entry_is_sourced (fib_node_index_t fib_entry_index,
     return (NULL != fib_entry_src_find(fib_entry, source));
 }
 
+int
+fib_entry_is_marked (fib_node_index_t fib_entry_index,
+                      fib_source_t source)
+{
+    fib_entry_t *fib_entry;
+    fib_entry_src_t *esrc;
+
+    fib_entry = fib_entry_get(fib_entry_index);
+
+    esrc = fib_entry_src_find(fib_entry, source);
+
+    if (NULL == esrc)
+    {
+        return (0);
+    }
+    else
+    {
+        return (!!(esrc->fes_flags & FIB_ENTRY_SRC_FLAG_STALE));
+    }
+}
+
+void
+fib_entry_mark (fib_node_index_t fib_entry_index,
+                fib_source_t source)
+{
+    fib_entry_t *fib_entry;
+    fib_entry_src_t *esrc;
+
+    fib_entry = fib_entry_get(fib_entry_index);
+
+    esrc = fib_entry_src_find(fib_entry, source);
+
+    if (NULL != esrc)
+    {
+        esrc->fes_flags |= FIB_ENTRY_SRC_FLAG_STALE;
+    }
+}
+
 static fib_entry_src_t *
 fib_entry_src_find_or_create (fib_entry_t *fib_entry,
 			      fib_source_t source,
diff --git a/src/vnet/fib/fib_entry_src.h b/src/vnet/fib/fib_entry_src.h
index a859b9c734a..8f13ae894bb 100644
--- a/src/vnet/fib/fib_entry_src.h
+++ b/src/vnet/fib/fib_entry_src.h
@@ -226,20 +226,24 @@ typedef struct fib_entry_src_vft_t_ {
     }								\
 }
 
-#define FIB_ENTRY_SRC_VFT_INVOKE(esrc, func, args)  \
-{                                                   \
-    const fib_entry_src_vft_t *_vft;                \
-    _vft = fib_entry_src_get_vft(esrc);             \
-    if (_vft->func)                                 \
-        _vft->func args;                            \
+#define FIB_ENTRY_SRC_VFT_INVOKE(esrc, func, args)             \
+{                                                              \
+    const fib_entry_src_vft_t *_vft;                           \
+    _vft = fib_entry_src_get_vft(esrc);                        \
+    if (_vft->func) {                                          \
+        (esrc)->fes_flags &= ~FIB_ENTRY_SRC_FLAG_STALE;        \
+        _vft->func args;                                       \
+    }                                                          \
 }
 
 #define FIB_ENTRY_SRC_VFT_INVOKE_AND_RETURN(esrc, func, args)  \
-{                                                   \
-    const fib_entry_src_vft_t *_vft;                \
-    _vft = fib_entry_src_get_vft(esrc);             \
-    if (_vft->func)                                 \
-        return (_vft->func args);                   \
+{                                                              \
+    const fib_entry_src_vft_t *_vft;                           \
+    _vft = fib_entry_src_get_vft(esrc);                        \
+    if (_vft->func) {                                          \
+        (esrc)->fes_flags &= ~FIB_ENTRY_SRC_FLAG_STALE;        \
+        return (_vft->func args);                              \
+    }                                                          \
 }
 
 #define FIB_ENTRY_SRC_VFT_EXISTS(esrc, func)        \
diff --git a/src/vnet/fib/fib_table.c b/src/vnet/fib/fib_table.c
index 3778fa9a944..d3cf5dc88b1 100644
--- a/src/vnet/fib/fib_table.c
+++ b/src/vnet/fib/fib_table.c
@@ -23,6 +23,8 @@
 #include <vnet/fib/ip6_fib.h>
 #include <vnet/fib/mpls_fib.h>
 
+const static char * fib_table_flags_strings[] = FIB_TABLE_ATTRIBUTES;
+
 fib_table_t *
 fib_table_get (fib_node_index_t index,
 	       fib_protocol_t proto)
@@ -1305,6 +1307,26 @@ format_fib_table_name (u8* s, va_list* ap)
     return (s);
 }
 
+u8*
+format_fib_table_flags (u8 *s, va_list *args)
+{
+    fib_table_flags_t flags = va_arg(*args, int);
+    fib_table_attribute_t attr;
+
+    if (!flags)
+    {
+        return format(s, "none");
+    }
+
+    FOR_EACH_FIB_TABLE_ATTRIBUTE(attr) {
+        if (1 << attr & flags) {
+            s = format(s, "%s", fib_table_flags_strings[attr]);
+        }
+    }
+
+    return (s);
+}
+
 /**
  * @brief Table flush context. Store the indicies of matching FIB entries
  * that need to be removed.
@@ -1335,7 +1357,6 @@ fib_table_flush_cb (fib_node_index_t fib_entry_index,
     return (FIB_TABLE_WALK_CONTINUE);
 }
 
-
 void
 fib_table_flush (u32 fib_index,
 		 fib_protocol_t proto,
@@ -1359,6 +1380,79 @@ fib_table_flush (u32 fib_index,
     vec_free(ctx.ftf_entries);
 }
 
+static fib_table_walk_rc_t
+fib_table_mark_cb (fib_node_index_t fib_entry_index,
+                   void *arg)
+{
+    fib_table_flush_ctx_t *ctx = arg;
+
+    if (fib_entry_is_sourced(fib_entry_index, ctx->ftf_source))
+    {
+        fib_entry_mark(fib_entry_index, ctx->ftf_source);
+    }
+    return (FIB_TABLE_WALK_CONTINUE);
+}
+
+void
+fib_table_mark (u32 fib_index,
+                fib_protocol_t proto,
+                fib_source_t source)
+{
+    fib_table_flush_ctx_t ctx = {
+        .ftf_source = source,
+    };
+    fib_table_t *fib_table;
+
+    fib_table = fib_table_get(fib_index, proto);
+
+    fib_table->ft_epoch++;
+    fib_table->ft_flags |= FIB_TABLE_FLAG_RESYNC;
+
+    fib_table_walk(fib_index, proto,
+                   fib_table_mark_cb,
+                   &ctx);
+}
+
+static fib_table_walk_rc_t
+fib_table_sweep_cb (fib_node_index_t fib_entry_index,
+                    void *arg)
+{
+    fib_table_flush_ctx_t *ctx = arg;
+
+    if (fib_entry_is_marked(fib_entry_index, ctx->ftf_source))
+    {
+        vec_add1(ctx->ftf_entries, fib_entry_index);
+    }
+    return (FIB_TABLE_WALK_CONTINUE);
+}
+
+void
+fib_table_sweep (u32 fib_index,
+                 fib_protocol_t proto,
+                 fib_source_t source)
+{
+    fib_table_flush_ctx_t ctx = {
+        .ftf_source = source,
+    };
+    fib_node_index_t *fib_entry_index;
+    fib_table_t *fib_table;
+
+    fib_table = fib_table_get(fib_index, proto);
+
+    fib_table->ft_flags &= ~FIB_TABLE_FLAG_RESYNC;
+
+    fib_table_walk(fib_index, proto,
+                   fib_table_sweep_cb,
+                   &ctx);
+
+    vec_foreach(fib_entry_index, ctx.ftf_entries)
+    {
+        fib_table_entry_delete_index(*fib_entry_index, source);
+    }
+
+    vec_free(ctx.ftf_entries);
+}
+
 u8 *
 format_fib_table_memory (u8 *s, va_list *args)
 {
diff --git a/src/vnet/fib/fib_table.h b/src/vnet/fib/fib_table.h
index f13dd77c8b4..74be63d326a 100644
--- a/src/vnet/fib/fib_table.h
+++ b/src/vnet/fib/fib_table.h
@@ -41,15 +41,20 @@ typedef enum fib_table_attribute_t_ {
      */
     FIB_TABLE_ATTRIBUTE_IP6_LL = FIB_TABLE_ATTRIBUTE_FIRST,
     /**
+     * the table is currently resync-ing
+     */
+    FIB_TABLE_ATTRIBUTE_RESYNC,
+    /**
      * Marker. add new entries before this one.
      */
-    FIB_TABLE_ATTRIBUTE_LAST = FIB_TABLE_ATTRIBUTE_IP6_LL,
+    FIB_TABLE_ATTRIBUTE_LAST = FIB_TABLE_ATTRIBUTE_RESYNC,
 } fib_table_attribute_t;
 
 #define FIB_TABLE_ATTRIBUTE_MAX (FIB_TABLE_ATTRIBUTE_LAST+1)
 
 #define FIB_TABLE_ATTRIBUTES {		         \
     [FIB_TABLE_ATTRIBUTE_IP6_LL]  = "ip6-ll",	 \
+    [FIB_TABLE_ATTRIBUTE_RESYNC]  = "resync",    \
 }
 
 #define FOR_EACH_FIB_TABLE_ATTRIBUTE(_item)      	\
@@ -60,8 +65,11 @@ typedef enum fib_table_attribute_t_ {
 typedef enum fib_table_flags_t_ {
     FIB_TABLE_FLAG_NONE   = 0,
     FIB_TABLE_FLAG_IP6_LL  = (1 << FIB_TABLE_ATTRIBUTE_IP6_LL),
+    FIB_TABLE_FLAG_RESYNC  = (1 << FIB_TABLE_ATTRIBUTE_RESYNC),
 } __attribute__ ((packed)) fib_table_flags_t;
 
+extern u8* format_fib_table_flags(u8 *s, va_list *args);
+
 /**
  * @brief 
  *   A protocol Independent FIB table
@@ -109,6 +117,11 @@ typedef struct fib_table_t_
     u32 ft_total_route_counts;
 
     /**
+     * Epoch - number of resyncs performed
+     */
+    u32 ft_epoch;
+
+    /**
      * Table description
      */
     u8* ft_desc;
@@ -624,6 +637,46 @@ extern void fib_table_flush(u32 fib_index,
 
 /**
  * @brief
+ *  Resync all entries from a table for the source
+ *  this is the mark part of the mark and sweep algorithm.
+ *  All entries in this FIB that are sourced by 'source' are marked
+ *  as stale.
+ *
+ * @param fib_index
+ *  The index of the FIB
+ *
+ * @paran proto
+ *  The protocol of the entries in the table
+ *
+ * @param source
+ *  the source to flush
+ */
+extern void fib_table_mark(u32 fib_index,
+                           fib_protocol_t proto,
+                           fib_source_t source);
+
+/**
+ * @brief
+ *  Signal that the table has converged, i.e. all updates are complete.
+ *  this is the sweep part of the mark and sweep algorithm.
+ *  All entries in this FIB that are sourced by 'source' and marked
+ *  as stale are flushed.
+ *
+ * @param fib_index
+ *  The index of the FIB
+ *
+ * @paran proto
+ *  The protocol of the entries in the table
+ *
+ * @param source
+ *  the source to flush
+ */
+extern void fib_table_sweep(u32 fib_index,
+                            fib_protocol_t proto,
+                            fib_source_t source);
+
+/**
+ * @brief
  *  Get the index of the FIB bound to the interface
  *
  * @paran proto
diff --git a/src/vnet/fib/ip4_fib.c b/src/vnet/fib/ip4_fib.c
index 0204b7a129a..02348af87d8 100644
--- a/src/vnet/fib/ip4_fib.c
+++ b/src/vnet/fib/ip4_fib.c
@@ -671,12 +671,14 @@ ip4_show_fib (vlib_main_t * vm,
             continue;
         }
 
-	s = format(s, "%U, fib_index:%d, flow hash:[%U] locks:[",
+	s = format(s, "%U, fib_index:%d, flow hash:[%U] epoch:%d flags:%U locks:[",
                    format_fib_table_name, fib->index,
                    FIB_PROTOCOL_IP4,
                    fib->index,
                    format_ip_flow_hash_config,
-                   fib_table->ft_flow_hash_config);
+                   fib_table->ft_flow_hash_config,
+                   fib_table->ft_epoch,
+                   format_fib_table_flags, fib_table->ft_flags);
 	FOR_EACH_FIB_SOURCE(source)
         {
             if (0 != fib_table->ft_locks[source])
diff --git a/src/vnet/fib/ip6_fib.c b/src/vnet/fib/ip6_fib.c
index cecfcbd1560..991fbc1151b 100644
--- a/src/vnet/fib/ip6_fib.c
+++ b/src/vnet/fib/ip6_fib.c
@@ -679,12 +679,15 @@ ip6_show_fib (vlib_main_t * vm,
         if (fib_table->ft_flags & FIB_TABLE_FLAG_IP6_LL)
             continue;
 
-	s = format(s, "%U, fib_index:%d, flow hash:[%U] locks:[",
+	s = format(s, "%U, fib_index:%d, flow hash:[%U] epoch:%d flags:%U locks:[",
                    format_fib_table_name, fib->index,
                    FIB_PROTOCOL_IP6,
                    fib->index,
                    format_ip_flow_hash_config,
-                   fib_table->ft_flow_hash_config);
+                   fib_table->ft_flow_hash_config,
+                   fib_table->ft_epoch,
+                   format_fib_table_flags, fib_table->ft_flags);
+
 	FOR_EACH_FIB_SOURCE(source)
         {
             if (0 != fib_table->ft_locks[source])