8 files changed, 321 insertions, 25 deletions

diff --git a/src/vnet/mfib/ip4_mfib.c b/src/vnet/mfib/ip4_mfib.c
index 1d872f974fd..4da1be61113 100644
--- a/src/vnet/mfib/ip4_mfib.c
+++ b/src/vnet/mfib/ip4_mfib.c
@@ -506,9 +506,10 @@ ip4_show_mfib (vlib_main_t * vm,
             continue;
         }
 
-        vlib_cli_output (vm, "%U, fib_index %d",
+        vlib_cli_output (vm, "%U, fib_index:%d flags:%U",
                          format_mfib_table_name, mfib->index, FIB_PROTOCOL_IP4,
-                         mfib->index);
+                         mfib->index,
+                         format_mfib_table_flags, mfib_table->mft_flags);
 
         /* Show summary? */
         if (! verbose)
diff --git a/src/vnet/mfib/ip6_mfib.c b/src/vnet/mfib/ip6_mfib.c
index 5b15c8d1736..690f4ed9dfd 100644
--- a/src/vnet/mfib/ip6_mfib.c
+++ b/src/vnet/mfib/ip6_mfib.c
@@ -562,14 +562,14 @@ typedef struct ip6_mfib_show_ctx_t_ {
 } ip6_mfib_show_ctx_t;
 
 
-static int
+static walk_rc_t
 ip6_mfib_table_collect_entries (fib_node_index_t mfei, void *arg)
 {
     ip6_mfib_show_ctx_t *ctx = arg;
 
     vec_add1(ctx->entries, mfei);
 
-    return (0);
+    return (WALK_CONTINUE);
 }
 
 static void
@@ -609,7 +609,7 @@ typedef struct ip6_mfib_walk_ctx_t_
     void *i6w_ctx;
 } ip6_mfib_walk_ctx_t;
 
-static int
+static void
 ip6_mfib_walk_cb (clib_bihash_kv_40_8_t * kvp,
                  void *arg)
 {
@@ -617,9 +617,8 @@ ip6_mfib_walk_cb (clib_bihash_kv_40_8_t * kvp,
 
     if ((kvp->key[4] >> 32) == ctx->i6w_mfib_index)
     {
-        return (ctx->i6w_fn(kvp->value, ctx->i6w_ctx));
+        ctx->i6w_fn(kvp->value, ctx->i6w_ctx);
     }
-    return (FIB_TABLE_WALK_CONTINUE);
 }
 
 void
diff --git a/src/vnet/mfib/mfib_entry.c b/src/vnet/mfib/mfib_entry.c
index f169dc0886e..448e6c5e0a8 100644
--- a/src/vnet/mfib/mfib_entry.c
+++ b/src/vnet/mfib/mfib_entry.c
@@ -38,6 +38,7 @@ static mfib_path_ext_t *mfib_path_ext_pool;
  * String names for each source
  */
 static const char *mfib_source_names[] = MFIB_SOURCE_NAMES;
+static const char *mfib_src_attribute_names[] = MFIB_ENTRY_SRC_ATTRIBUTES;
 
 /*
  * Pool for all fib_entries
@@ -102,6 +103,26 @@ format_mfib_entry_path_ext (u8 * s, va_list * args)
 }
 
 u8 *
+format_mfib_entry_src_flags (u8 *s, va_list *args)
+{
+    mfib_entry_src_attribute_t sattr;
+    mfib_entry_src_flags_t flag = va_arg(*args, int);
+
+    if (!flag)
+    {
+        return format(s, "none");
+    }
+
+    FOR_EACH_MFIB_SRC_ATTRIBUTE(sattr) {
+        if ((1 << sattr) & flag) {
+            s = format (s, "%s,", mfib_src_attribute_names[sattr]);
+        }
+    }
+
+    return (s);
+}
+
+u8 *
 format_mfib_entry (u8 * s, va_list * args)
 {
     fib_node_index_t fei, mfi;
@@ -127,14 +148,15 @@ format_mfib_entry (u8 * s, va_list * args)
         s = format (s, " locks:%d\n", mfib_entry->mfe_node.fn_locks);
         vec_foreach(msrc, mfib_entry->mfe_srcs)
         {
-            s = format (s, "  src:%s locks:%d:",
+            s = format (s, "  src:%s flags:%U locks:%d:",
                         mfib_source_names[msrc->mfes_src],
+                        format_mfib_entry_src_flags, msrc->mfes_flags,
                         msrc->mfes_ref_count);
             if (msrc->mfes_cover != FIB_NODE_INDEX_INVALID)
             {
                 s = format (s, " cover:%d", msrc->mfes_cover);
             }
-            s = format (s, " %U\n", format_mfib_entry_flags, msrc->mfes_flags);
+            s = format (s, " %U\n", format_mfib_entry_flags, msrc->mfes_route_flags);
             if (FIB_NODE_INDEX_INVALID != msrc->mfes_pl)
             {
                 s = fib_path_list_format(msrc->mfes_pl, s);
@@ -201,7 +223,7 @@ mfib_entry_src_init (mfib_entry_t *mfib_entry,
 {
     mfib_entry_src_t esrc = {
         .mfes_pl = FIB_NODE_INDEX_INVALID,
-        .mfes_flags = MFIB_ENTRY_FLAG_NONE,
+        .mfes_route_flags = MFIB_ENTRY_FLAG_NONE,
         .mfes_src = source,
         .mfes_cover = FIB_NODE_INDEX_INVALID,
         .mfes_sibling = FIB_NODE_INDEX_INVALID,
@@ -215,8 +237,8 @@ mfib_entry_src_init (mfib_entry_t *mfib_entry,
 
 static mfib_entry_src_t *
 mfib_entry_src_find (const mfib_entry_t *mfib_entry,
-                    mfib_source_t source,
-                    u32 *index)
+                     mfib_source_t source,
+                     u32 *index)
 
 {
     mfib_entry_src_t *esrc;
@@ -269,8 +291,9 @@ mfib_entry_src_update (mfib_entry_t *mfib_entry,
 
     msrc = mfib_entry_src_find_or_create(mfib_entry, source);
 
-    msrc->mfes_flags = entry_flags;
+    msrc->mfes_route_flags = entry_flags;
     msrc->mfes_rpf_id = rpf_id;
+    msrc->mfes_flags &= ~MFIB_ENTRY_SRC_FLAG_STALE;
 
     return (msrc);
 }
@@ -286,6 +309,7 @@ mfib_entry_src_update_and_lock (mfib_entry_t *mfib_entry,
     msrc = mfib_entry_src_update(mfib_entry, source, rpf_id, entry_flags);
 
     msrc->mfes_ref_count++;
+    msrc->mfes_flags &= ~MFIB_ENTRY_SRC_FLAG_STALE;
 
     return (msrc);
 }
@@ -332,6 +356,44 @@ mfib_entry_is_sourced (fib_node_index_t mfib_entry_index,
 }
 
 int
+mfib_entry_is_marked (fib_node_index_t mfib_entry_index,
+                      mfib_source_t source)
+{
+    mfib_entry_t *mfib_entry;
+    mfib_entry_src_t *esrc;
+
+    mfib_entry = mfib_entry_get(mfib_entry_index);
+
+    esrc = mfib_entry_src_find(mfib_entry, source, NULL);
+
+    if (NULL == esrc)
+    {
+        return (0);
+    }
+    else
+    {
+        return (!!(esrc->mfes_flags & MFIB_ENTRY_SRC_FLAG_STALE));
+    }
+}
+
+void
+mfib_entry_mark (fib_node_index_t fib_entry_index,
+                 mfib_source_t source)
+{
+    mfib_entry_t *mfib_entry;
+    mfib_entry_src_t *esrc;
+
+    mfib_entry = mfib_entry_get(fib_entry_index);
+
+    esrc = mfib_entry_src_find(mfib_entry, source, NULL);
+
+    if (NULL != esrc)
+    {
+        esrc->mfes_flags |= MFIB_ENTRY_SRC_FLAG_STALE;
+    }
+}
+
+int
 mfib_entry_is_host (fib_node_index_t mfib_entry_index)
 {
     return (mfib_prefix_is_host(mfib_entry_get_prefix(mfib_entry_index)));
@@ -578,7 +640,7 @@ mfib_entry_stack (mfib_entry_t *mfib_entry,
          * updates to recalculate forwarding.
          */
         mfib_entry->mfe_pl = msrc->mfes_pl;
-        mfib_entry->mfe_flags = msrc->mfes_flags;
+        mfib_entry->mfe_flags = msrc->mfes_route_flags;
         mfib_entry->mfe_itfs = msrc->mfes_itfs;
         mfib_entry->mfe_rpf_id = msrc->mfes_rpf_id;
 
@@ -677,7 +739,9 @@ static fib_node_index_t*
 mfib_entry_src_paths_add (mfib_entry_src_t *msrc,
                           const fib_route_path_t *rpaths)
 {
-    ASSERT(!(MFIB_ENTRY_FLAG_EXCLUSIVE & msrc->mfes_flags));
+    ASSERT(!(MFIB_ENTRY_FLAG_EXCLUSIVE & msrc->mfes_route_flags));
+
+    msrc->mfes_flags &= ~MFIB_ENTRY_SRC_FLAG_STALE;
 
     if (FIB_NODE_INDEX_INVALID == msrc->mfes_pl)
     {
@@ -694,7 +758,9 @@ static fib_node_index_t*
 mfib_entry_src_paths_remove (mfib_entry_src_t *msrc,
                              const fib_route_path_t *rpaths)
 {
-    ASSERT(!(MFIB_ENTRY_FLAG_EXCLUSIVE & msrc->mfes_flags));
+    ASSERT(!(MFIB_ENTRY_FLAG_EXCLUSIVE & msrc->mfes_route_flags));
+
+    msrc->mfes_flags &= ~MFIB_ENTRY_SRC_FLAG_STALE;
 
     return (fib_path_list_paths_remove(msrc->mfes_pl, rpaths));
 }
@@ -792,11 +858,11 @@ static int
 mfib_entry_src_ok_for_delete (const mfib_entry_src_t *msrc)
 {
     return ((INDEX_INVALID == msrc->mfes_cover &&
-             MFIB_ENTRY_FLAG_NONE == msrc->mfes_flags &&
+             MFIB_ENTRY_FLAG_NONE == msrc->mfes_route_flags &&
              0 == fib_path_list_get_n_paths(msrc->mfes_pl)) &&
             (0 == hash_elts(msrc->mfes_itfs)));
 
-    /* return ((MFIB_ENTRY_FLAG_NONE == msrc->mfes_flags) && */
+    /* return ((MFIB_ENTRY_FLAG_NONE == msrc->mfes_route_flags) && */
     /*         (0 == fib_path_list_get_n_paths(msrc->mfes_pl)) && */
     /*         (0 == hash_elts(msrc->mfes_itfs))); */
 }
diff --git a/src/vnet/mfib/mfib_entry.h b/src/vnet/mfib/mfib_entry.h
index 4a1121bc9d5..7087fe87a4d 100644
--- a/src/vnet/mfib/mfib_entry.h
+++ b/src/vnet/mfib/mfib_entry.h
@@ -161,6 +161,8 @@ extern u32 mfib_entry_get_fib_index(fib_node_index_t fib_entry_index);
 extern int mfib_entry_is_sourced(fib_node_index_t fib_entry_index,
                                  mfib_source_t source);
 extern int mfib_entry_is_host(fib_node_index_t fib_entry_index);
+extern int mfib_entry_is_marked(fib_node_index_t fib_entry_index, mfib_source_t source);
+extern void mfib_entry_mark(fib_node_index_t fib_entry_index, mfib_source_t source);
 extern u32 mfib_entry_get_stats_index(fib_node_index_t fib_entry_index);
 extern void mfib_entry_cover_changed(fib_node_index_t fib_entry_index);
 extern void mfib_entry_cover_updated(fib_node_index_t fib_entry_index);
diff --git a/src/vnet/mfib/mfib_entry_src.h b/src/vnet/mfib/mfib_entry_src.h
index 86752e071ec..b85c010779c 100644
--- a/src/vnet/mfib/mfib_entry_src.h
+++ b/src/vnet/mfib/mfib_entry_src.h
@@ -28,6 +28,48 @@ typedef struct mfib_path_ext_t_
 } mfib_path_ext_t;
 
 /**
+ * Flags for the source data
+ */
+typedef enum mfib_entry_src_attribute_t_ {
+    /**
+     * Marker. Add new values after this one.
+     */
+    MFIB_ENTRY_SRC_ATTRIBUTE_FIRST,
+    /**
+     * the source has been added to the entry
+     */
+    MFIB_ENTRY_SRC_ATTRIBUTE_STALE = MFIB_ENTRY_SRC_ATTRIBUTE_FIRST,
+    /**
+     * Marker. add new entries before this one.
+     */
+    MFIB_ENTRY_SRC_ATTRIBUTE_LAST = MFIB_ENTRY_SRC_ATTRIBUTE_STALE,
+} mfib_entry_src_attribute_t;
+
+
+#define MFIB_ENTRY_SRC_ATTRIBUTES {                  \
+    [MFIB_ENTRY_SRC_ATTRIBUTE_STALE] = "stale",      \
+}
+
+#define FOR_EACH_MFIB_SRC_ATTRIBUTE(_item)                      \
+    for (_item = MFIB_ENTRY_SRC_ATTRIBUTE_FIRST;		\
+	 _item <= MFIB_ENTRY_SRC_ATTRIBUTE_LAST;		\
+	 _item++)
+
+typedef enum mfib_entry_src_flag_t_ {
+    MFIB_ENTRY_SRC_FLAG_NONE   = 0,
+    MFIB_ENTRY_SRC_FLAG_STALE = (1 << MFIB_ENTRY_SRC_ATTRIBUTE_STALE),
+} __attribute__ ((packed)) mfib_entry_src_flags_t;
+
+extern u8 * format_mfib_entry_src_flags(u8 *s, va_list *args);
+
+/*
+ * Keep the size of the flags field to 2 bytes, so it
+ * can be placed next to the 2 bytes reference count
+ */
+STATIC_ASSERT (sizeof(mfib_entry_src_flags_t) <= 2,
+	       "FIB entry flags field size too big");
+
+/**
  * The source of an MFIB entry
  */
 typedef struct mfib_entry_src_t_
@@ -40,7 +82,12 @@ typedef struct mfib_entry_src_t_
     /**
      * Route flags
      */
-    mfib_entry_flags_t mfes_flags;
+    mfib_entry_flags_t mfes_route_flags;
+
+    /**
+     * Source flags
+     */
+    mfib_entry_src_flags_t mfes_flags;
 
     /**
      * The reference count on the entry. this is a u32
diff --git a/src/vnet/mfib/mfib_entry_src_rr.c b/src/vnet/mfib/mfib_entry_src_rr.c
index 4512f74a9f5..a6a1e0d8aa5 100644
--- a/src/vnet/mfib/mfib_entry_src_rr.c
+++ b/src/vnet/mfib/mfib_entry_src_rr.c
@@ -62,7 +62,7 @@ mfib_entry_src_rr_activiate (mfib_entry_t *mfib_entry,
 
     msrc->mfes_pl = csrc->mfes_pl;
     fib_path_list_lock(msrc->mfes_pl);
-    msrc->mfes_flags = csrc->mfes_flags;
+    msrc->mfes_route_flags = csrc->mfes_route_flags;
     msrc->mfes_itfs = csrc->mfes_itfs;
     msrc->mfes_exts = csrc->mfes_exts;
     msrc->mfes_rpf_id = csrc->mfes_rpf_id;
@@ -91,7 +91,7 @@ mfib_entry_src_rr_cover_update (mfib_entry_t *mfib_entry,
 
     cover = mfib_entry_get(msrc->mfes_cover);
 
-    msrc->mfes_flags = cover->mfe_flags;
+    msrc->mfes_route_flags = cover->mfe_flags;
     msrc->mfes_itfs = cover->mfe_itfs;
     msrc->mfes_rpf_id = cover->mfe_rpf_id;
 
diff --git a/src/vnet/mfib/mfib_table.c b/src/vnet/mfib/mfib_table.c
index 504333a2474..a6a82774794 100644
--- a/src/vnet/mfib/mfib_table.c
+++ b/src/vnet/mfib/mfib_table.c
@@ -24,6 +24,8 @@
 #include <vnet/mfib/mfib_entry_cover.h>
 #include <vnet/mfib/mfib_signal.h>
 
+const static char * mfib_table_flags_strings[] = MFIB_TABLE_ATTRIBUTES;
+
 mfib_table_t *
 mfib_table_get (fib_node_index_t index,
                 fib_protocol_t proto)
@@ -643,7 +645,7 @@ typedef struct mfib_table_flush_ctx_t_
     mfib_source_t mftf_source;
 } mfib_table_flush_ctx_t;
 
-static int
+static walk_rc_t
 mfib_table_flush_cb (fib_node_index_t mfib_entry_index,
                      void *arg)
 {
@@ -653,7 +655,7 @@ mfib_table_flush_cb (fib_node_index_t mfib_entry_index,
     {
         vec_add1(ctx->mftf_entries, mfib_entry_index);
     }
-    return (1);
+    return (WALK_CONTINUE);
 }
 
 void
@@ -679,6 +681,79 @@ mfib_table_flush (u32 mfib_index,
     vec_free(ctx.mftf_entries);
 }
 
+static walk_rc_t
+mfib_table_mark_cb (fib_node_index_t fib_entry_index,
+                   void *arg)
+{
+    mfib_table_flush_ctx_t *ctx = arg;
+
+    if (mfib_entry_is_sourced(fib_entry_index, ctx->mftf_source))
+    {
+        mfib_entry_mark(fib_entry_index, ctx->mftf_source);
+    }
+    return (WALK_CONTINUE);
+}
+
+void
+mfib_table_mark (u32 fib_index,
+                 fib_protocol_t proto,
+                 mfib_source_t source)
+{
+    mfib_table_flush_ctx_t ctx = {
+        .mftf_source = source,
+    };
+    mfib_table_t *mfib_table;
+
+    mfib_table = mfib_table_get(fib_index, proto);
+
+    mfib_table->mft_epoch++;
+    mfib_table->mft_flags |= MFIB_TABLE_FLAG_RESYNC;
+
+    mfib_table_walk(fib_index, proto,
+                   mfib_table_mark_cb,
+                   &ctx);
+}
+
+static walk_rc_t
+mfib_table_sweep_cb (fib_node_index_t fib_entry_index,
+                    void *arg)
+{
+    mfib_table_flush_ctx_t *ctx = arg;
+
+    if (mfib_entry_is_marked(fib_entry_index, ctx->mftf_source))
+    {
+        vec_add1(ctx->mftf_entries, fib_entry_index);
+    }
+    return (WALK_CONTINUE);
+}
+
+void
+mfib_table_sweep (u32 fib_index,
+                  fib_protocol_t proto,
+                  mfib_source_t source)
+{
+    mfib_table_flush_ctx_t ctx = {
+        .mftf_source = source,
+    };
+    fib_node_index_t *fib_entry_index;
+    mfib_table_t *mfib_table;
+
+    mfib_table = mfib_table_get(fib_index, proto);
+
+    mfib_table->mft_flags &= ~MFIB_TABLE_FLAG_RESYNC;
+
+    mfib_table_walk(fib_index, proto,
+                    mfib_table_sweep_cb,
+                    &ctx);
+
+    vec_foreach(fib_entry_index, ctx.mftf_entries)
+    {
+        mfib_table_entry_delete_index(*fib_entry_index, source);
+    }
+
+    vec_free(ctx.mftf_entries);
+}
+
 static void
 mfib_table_destroy (mfib_table_t *mfib_table)
 {
@@ -770,6 +845,26 @@ mfib_table_walk (u32 fib_index,
 }
 
 u8*
+format_mfib_table_flags (u8 *s, va_list *args)
+{
+    mfib_table_flags_t flags = va_arg(*args, int);
+    mfib_table_attribute_t attr;
+
+    if (!flags)
+    {
+        return format(s, "none");
+    }
+
+    FOR_EACH_MFIB_TABLE_ATTRIBUTE(attr) {
+        if (1 << attr & flags) {
+            s = format(s, "%s", mfib_table_flags_strings[attr]);
+        }
+    }
+
+    return (s);
+}
+
+u8*
 format_mfib_table_name (u8* s, va_list *ap)
 {
     fib_node_index_t fib_index = va_arg(*ap, fib_node_index_t);
diff --git a/src/vnet/mfib/mfib_table.h b/src/vnet/mfib/mfib_table.h
index 47461375a10..d6b6dc3845d 100644
--- a/src/vnet/mfib/mfib_table.h
+++ b/src/vnet/mfib/mfib_table.h
@@ -29,6 +29,42 @@
 #define MFIB_TABLE_TOTAL_LOCKS MFIB_N_SOURCES
 
 /**
+ * Flags for the source data
+ */
+typedef enum mfib_table_attribute_t_ {
+    /**
+     * Marker. Add new values after this one.
+     */
+    MFIB_TABLE_ATTRIBUTE_FIRST,
+    /**
+     * the table is currently resync-ing
+     */
+    MFIB_TABLE_ATTRIBUTE_RESYNC = MFIB_TABLE_ATTRIBUTE_FIRST,
+    /**
+     * Marker. add new entries before this one.
+     */
+    MFIB_TABLE_ATTRIBUTE_LAST = MFIB_TABLE_ATTRIBUTE_RESYNC,
+} mfib_table_attribute_t;
+
+#define MFIB_TABLE_ATTRIBUTE_MAX (MFIB_TABLE_ATTRIBUTE_LAST+1)
+
+#define MFIB_TABLE_ATTRIBUTES {		         \
+    [MFIB_TABLE_ATTRIBUTE_RESYNC]  = "resync",    \
+}
+
+#define FOR_EACH_MFIB_TABLE_ATTRIBUTE(_item)      	\
+    for (_item = MFIB_TABLE_ATTRIBUTE_FIRST;		\
+	 _item < MFIB_TABLE_ATTRIBUTE_MAX;		\
+	 _item++)
+
+typedef enum mfib_table_flags_t_ {
+    MFIB_TABLE_FLAG_NONE   = 0,
+    MFIB_TABLE_FLAG_RESYNC  = (1 << MFIB_TABLE_ATTRIBUTE_RESYNC),
+} __attribute__ ((packed)) mfib_table_flags_t;
+
+extern u8* format_mfib_table_flags(u8 *s, va_list *args);
+
+/**
  * @brief
  *   A protocol Independent IP multicast FIB table
  */
@@ -56,6 +92,11 @@ typedef struct mfib_table_t_
     fib_protocol_t mft_proto;
 
     /**
+     * table falgs
+     */
+    mfib_table_flags_t mft_flags;
+
+    /**
      * number of locks on the table
      */
     u16 mft_locks[MFIB_TABLE_N_LOCKS];
@@ -66,6 +107,11 @@ typedef struct mfib_table_t_
     u32 mft_table_id;
 
     /**
+     * resync epoch
+     */
+    u32 mft_epoch;
+
+    /**
      * Index into FIB vector.
      */
     fib_node_index_t mft_index;
@@ -282,6 +328,46 @@ extern void mfib_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 mfib_table_mark(u32 fib_index,
+                            fib_protocol_t proto,
+                            mfib_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 mfib_table_sweep(u32 fib_index,
+                             fib_protocol_t proto,
+                             mfib_source_t source);
+
+/**
+ * @brief
  *  Get the index of the FIB bound to the interface
  *
  * @paran proto
@@ -465,8 +551,8 @@ extern mfib_table_t *mfib_table_get(fib_node_index_t index,
 /**
  * @brief Call back function when walking entries in a FIB table
  */
-typedef int (*mfib_table_walk_fn_t)(fib_node_index_t fei,
-                                    void *ctx);
+typedef walk_rc_t (*mfib_table_walk_fn_t)(fib_node_index_t fei,
+                                          void *ctx);
 
 /**
  * @brief Walk all entries in a FIB table