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])