fib: FIB Entry tracking

Instead of all clients directly RR sourcing the entry they are tracking,
use a deidcated 'tracker' object. This tracker object is a entry
delegate and a child of the entry. The clients are then children of the
tracker.
The benefit of this aproach is that each time a new client tracks the
entry it doesn't RR source it. When an entry is sourced all its children
are updated. Thus, new clients tracking an entry is O(n^2). With the
tracker as indirection, the entry is sourced only once.

Type: feature

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

11 files changed, 409 insertions, 64 deletions

diff --git a/src/vnet/fib/fib_attached_export.c b/src/vnet/fib/fib_attached_export.c
index da83a3d4184..a0f4e4e8bc2 100644
--- a/src/vnet/fib/fib_attached_export.c
+++ b/src/vnet/fib/fib_attached_export.c
@@ -99,8 +99,8 @@ fib_entry_ae_add_or_lock (fib_node_index_t connected)
     fib_entry_t *entry;
 
     entry = fib_entry_get(connected);
-    fed = fib_entry_delegate_get(entry,
-                                 FIB_ENTRY_DELEGATE_ATTACHED_EXPORT);
+    fed = fib_entry_delegate_find(entry,
+                                  FIB_ENTRY_DELEGATE_ATTACHED_EXPORT);
 
     if (NULL == fed)
     {
@@ -317,8 +317,8 @@ fib_attached_export_purge (fib_entry_t *fib_entry)
 {
     fib_entry_delegate_t *fed;
 
-    fed = fib_entry_delegate_get(fib_entry,
-                                 FIB_ENTRY_DELEGATE_ATTACHED_IMPORT);
+    fed = fib_entry_delegate_find(fib_entry,
+                                  FIB_ENTRY_DELEGATE_ATTACHED_IMPORT);
 
     if (NULL != fed)
     {
@@ -362,8 +362,8 @@ fib_attached_export_purge (fib_entry_t *fib_entry)
 
 	    export_entry = fib_entry_get(import->faei_export_entry);
 
-            fed = fib_entry_delegate_get(export_entry,
-                                         FIB_ENTRY_DELEGATE_ATTACHED_EXPORT);
+            fed = fib_entry_delegate_find(export_entry,
+                                          FIB_ENTRY_DELEGATE_ATTACHED_EXPORT);
             ASSERT(NULL != fed);
 
 	    export = pool_elt_at_index(fib_ae_export_pool, fed->fd_index);
@@ -400,8 +400,8 @@ fib_attached_export_covered_added (fib_entry_t *cover,
 {
     fib_entry_delegate_t *fed;
 
-    fed = fib_entry_delegate_get(cover,
-                                 FIB_ENTRY_DELEGATE_ATTACHED_EXPORT);
+    fed = fib_entry_delegate_find(cover,
+                                  FIB_ENTRY_DELEGATE_ATTACHED_EXPORT);
 
     if (NULL != fed)
     {
@@ -432,8 +432,8 @@ fib_attached_export_covered_removed (fib_entry_t *cover,
 {
     fib_entry_delegate_t *fed;
 
-    fed = fib_entry_delegate_get(cover,
-                                 FIB_ENTRY_DELEGATE_ATTACHED_EXPORT);
+    fed = fib_entry_delegate_find(cover,
+                                  FIB_ENTRY_DELEGATE_ATTACHED_EXPORT);
 
     if (NULL != fed)
     {
@@ -463,8 +463,8 @@ fib_attached_export_cover_modified_i (fib_entry_t *fib_entry)
 {
     fib_entry_delegate_t *fed;
 
-    fed = fib_entry_delegate_get(fib_entry,
-                                 FIB_ENTRY_DELEGATE_ATTACHED_IMPORT);
+    fed = fib_entry_delegate_find(fib_entry,
+                                  FIB_ENTRY_DELEGATE_ATTACHED_IMPORT);
 
     if (NULL != fed)
     {
diff --git a/src/vnet/fib/fib_bfd.c b/src/vnet/fib/fib_bfd.c
index f785ba2e68f..b02fbc67a63 100644
--- a/src/vnet/fib/fib_bfd.c
+++ b/src/vnet/fib/fib_bfd.c
@@ -94,8 +94,8 @@ fib_bfd_notify (bfd_listen_event_e event,
          * The creation of a new session
          */
         if ((FIB_NODE_INDEX_INVALID != fei) &&
-            (fed = fib_entry_delegate_get(fib_entry_get(fei),
-                                          FIB_ENTRY_DELEGATE_BFD)))
+            (fed = fib_entry_delegate_find(fib_entry_get(fei),
+                                           FIB_ENTRY_DELEGATE_BFD)))
         {
             /*
              * already got state for this entry
@@ -132,8 +132,8 @@ fib_bfd_notify (bfd_listen_event_e event,
          */
         ASSERT(FIB_NODE_INDEX_INVALID != fei);
 
-        fed = fib_entry_delegate_get(fib_entry_get(fei),
-                                     FIB_ENTRY_DELEGATE_BFD);
+        fed = fib_entry_delegate_find(fib_entry_get(fei),
+                                      FIB_ENTRY_DELEGATE_BFD);
 
         if (NULL != fed)
         {
@@ -156,8 +156,8 @@ fib_bfd_notify (bfd_listen_event_e event,
              * no FIB entry
              */
         }
-        else if (fib_entry_delegate_get(fib_entry_get(fei),
-                                        FIB_ENTRY_DELEGATE_BFD))
+        else if (fib_entry_delegate_find(fib_entry_get(fei),
+                                         FIB_ENTRY_DELEGATE_BFD))
         {
             /*
              * has an associated BFD tracking delegate
diff --git a/src/vnet/fib/fib_entry.c b/src/vnet/fib/fib_entry.c
index 6ff692dea98..9169dccff8a 100644
--- a/src/vnet/fib/fib_entry.c
+++ b/src/vnet/fib/fib_entry.c
@@ -28,6 +28,8 @@
 #include <vnet/fib/fib_internal.h>
 #include <vnet/fib/fib_attached_export.h>
 #include <vnet/fib/fib_path_ext.h>
+#include <vnet/fib/fib_entry_delegate.h>
+#include <vnet/fib/fib_entry_track.h>
 
 /*
  * Array of strings/names for the FIB sources
@@ -203,14 +205,13 @@ format_fib_entry (u8 * s, va_list * args)
 
         if (level >= FIB_ENTRY_FORMAT_DETAIL2)
         {
-            fib_entry_delegate_type_t fdt;
-            fib_entry_delegate_t *fed;
+            index_t *fedi;
 
             s = format (s, " Delegates:\n");
-            FOR_EACH_DELEGATE(fib_entry, fdt, fed,
+            vec_foreach(fedi, fib_entry->fe_delegates)
             {
-                s = format(s, "  %U\n", format_fib_entry_deletegate, fed);
-            });
+                s = format(s, "  %U\n", format_fib_entry_delegate, *fedi);
+            }
         }
     }
 
@@ -464,8 +465,8 @@ fib_entry_contribute_forwarding (fib_node_index_t fib_entry_index,
     }
     else
     {
-        fed = fib_entry_delegate_get(fib_entry,
-                                     fib_entry_chain_type_to_delegate_type(fct));
+        fed = fib_entry_delegate_find(fib_entry,
+                                      fib_entry_chain_type_to_delegate_type(fct));
 
         if (NULL == fed)
         {
@@ -1486,7 +1487,7 @@ fib_entry_is_resolved (fib_node_index_t fib_entry_index)
 
     fib_entry = fib_entry_get(fib_entry_index);
 
-    fed = fib_entry_delegate_get(fib_entry, FIB_ENTRY_DELEGATE_BFD);
+    fed = fib_entry_delegate_find(fib_entry, FIB_ENTRY_DELEGATE_BFD);
 
     if (NULL == fed)
     {
@@ -1642,6 +1643,8 @@ fib_entry_module_init (void)
 {
     fib_node_register_type(FIB_NODE_TYPE_ENTRY, &fib_entry_vft);
     fib_entry_logger = vlib_log_register_class("fib", "entry");
+
+    fib_entry_track_module_init();
 }
 
 fib_route_path_t *
diff --git a/src/vnet/fib/fib_entry.h b/src/vnet/fib/fib_entry.h
index 5d0fb24bcb2..70c66217156 100644
--- a/src/vnet/fib/fib_entry.h
+++ b/src/vnet/fib/fib_entry.h
@@ -17,7 +17,6 @@
 #define __FIB_ENTRY_H__
 
 #include <vnet/fib/fib_node.h>
-#include <vnet/fib/fib_entry_delegate.h>
 #include <vnet/adj/adj.h>
 #include <vnet/ip/ip.h>
 #include <vnet/dpo/dpo.h>
@@ -505,9 +504,9 @@ typedef struct fib_entry_t_ {
     u32 fe_sibling;
 
     /**
-     * A vector of delegates.
+     * A vector of delegate indices.
      */
-    fib_entry_delegate_t *fe_delegates;
+    index_t *fe_delegates;
 } fib_entry_t;
 
 #define FOR_EACH_FIB_ENTRY_FLAG(_item) \
diff --git a/src/vnet/fib/fib_entry_cover.c b/src/vnet/fib/fib_entry_cover.c
index c7308224f0a..153bd70a5bf 100644
--- a/src/vnet/fib/fib_entry_cover.c
+++ b/src/vnet/fib/fib_entry_cover.c
@@ -16,6 +16,7 @@
 #include <vnet/fib/fib_entry_cover.h>
 #include <vnet/fib/fib_entry_src.h>
 #include <vnet/fib/fib_node_list.h>
+#include <vnet/fib/fib_entry_delegate.h>
 
 u32
 fib_entry_cover_track (fib_entry_t* cover,
@@ -27,7 +28,7 @@ fib_entry_cover_track (fib_entry_t* cover,
 
     ASSERT(fib_entry_get_index(cover) != covered);
 
-    fed = fib_entry_delegate_get(cover, FIB_ENTRY_DELEGATE_COVERED);
+    fed = fib_entry_delegate_find(cover, FIB_ENTRY_DELEGATE_COVERED);
 
     if (NULL == fed)
     {
@@ -48,7 +49,7 @@ fib_entry_cover_untrack (fib_entry_t* cover,
 
     FIB_ENTRY_DBG(cover, "cover-untrack @ %d", tracked_index);
 
-    fed = fib_entry_delegate_get(cover, FIB_ENTRY_DELEGATE_COVERED);
+    fed = fib_entry_delegate_find(cover, FIB_ENTRY_DELEGATE_COVERED);
 
     if (NULL == fed)
         return;
@@ -90,7 +91,7 @@ fib_entry_cover_walk (fib_entry_t *cover,
 {
     fib_entry_delegate_t *fed;
 
-    fed = fib_entry_delegate_get(cover, FIB_ENTRY_DELEGATE_COVERED);
+    fed = fib_entry_delegate_find(cover, FIB_ENTRY_DELEGATE_COVERED);
 
     if (NULL == fed)
         return;
diff --git a/src/vnet/fib/fib_entry_delegate.c b/src/vnet/fib/fib_entry_delegate.c
index 4bf37df0a7e..d7503fbb1b9 100644
--- a/src/vnet/fib/fib_entry_delegate.c
+++ b/src/vnet/fib/fib_entry_delegate.c
@@ -17,17 +17,34 @@
 #include <vnet/fib/fib_entry.h>
 #include <vnet/fib/fib_attached_export.h>
 
+static fib_entry_delegate_t *fib_entry_delegate_pool;
+
+fib_entry_delegate_t *
+fib_entry_delegate_get (index_t fedi)
+{
+    return (pool_elt_at_index(fib_entry_delegate_pool, fedi));
+}
+
+fib_node_index_t
+fib_entry_delegate_get_index (const fib_entry_delegate_t *fed)
+{
+    return (fed - fib_entry_delegate_pool);
+}
+
 static fib_entry_delegate_t *
 fib_entry_delegate_find_i (const fib_entry_t *fib_entry,
                            fib_entry_delegate_type_t type,
                            u32 *index)
 {
     fib_entry_delegate_t *delegate;
+    index_t *fedi;
     int ii;
 
     ii = 0;
-    vec_foreach(delegate, fib_entry->fe_delegates)
+    vec_foreach(fedi, fib_entry->fe_delegates)
     {
+        delegate = fib_entry_delegate_get(*fedi);
+
 	if (delegate->fd_type == type)
 	{
             if (NULL != index)
@@ -45,7 +62,7 @@ fib_entry_delegate_find_i (const fib_entry_t *fib_entry,
 }
 
 fib_entry_delegate_t *
-fib_entry_delegate_get (const fib_entry_t *fib_entry,
+fib_entry_delegate_find (const fib_entry_t *fib_entry,
                         fib_entry_delegate_type_t type)
 {
     return (fib_entry_delegate_find_i(fib_entry, type, NULL));
@@ -63,13 +80,19 @@ fib_entry_delegate_remove (fib_entry_t *fib_entry,
     ASSERT(NULL != fed);
 
     vec_del1(fib_entry->fe_delegates, index);
+
+    pool_put(fib_entry_delegate_pool, fed);
 }
 
 static int
 fib_entry_delegate_cmp_for_sort (void * v1,
                                  void * v2)
 {
-    fib_entry_delegate_t *delegate1 = v1, *delegate2 = v2;
+    fib_entry_delegate_t *delegate1, *delegate2;
+    index_t *fedi1 = v1, *fedi2 = v2;
+
+    delegate1 = fib_entry_delegate_get(*fedi1);
+    delegate2 = fib_entry_delegate_get(*fedi2);
 
     return (delegate1->fd_type - delegate2->fd_type);
 }
@@ -79,12 +102,14 @@ fib_entry_delegate_init (fib_entry_t *fib_entry,
                          fib_entry_delegate_type_t type)
 
 {
-    fib_entry_delegate_t delegate = {
-	.fd_entry_index = fib_entry_get_index(fib_entry),
-	.fd_type = type,
-    };
+    fib_entry_delegate_t *delegate;
+
+    pool_get_zero(fib_entry_delegate_pool, delegate);
+
+    delegate->fd_entry_index = fib_entry_get_index(fib_entry);
+    delegate->fd_type = type;
 
-    vec_add1(fib_entry->fe_delegates, delegate);
+    vec_add1(fib_entry->fe_delegates, delegate - fib_entry_delegate_pool);
     vec_sort_with_function(fib_entry->fe_delegates,
 			   fib_entry_delegate_cmp_for_sort);
 }
@@ -95,14 +120,14 @@ fib_entry_delegate_find_or_add (fib_entry_t *fib_entry,
 {
     fib_entry_delegate_t *delegate;
 
-    delegate = fib_entry_delegate_get(fib_entry, fdt);
+    delegate = fib_entry_delegate_find(fib_entry, fdt);
 
     if (NULL == delegate)
     {
 	fib_entry_delegate_init(fib_entry, fdt);
     }
 
-    return (fib_entry_delegate_get(fib_entry, fdt));
+    return (fib_entry_delegate_find(fib_entry, fdt));
 }
 
 fib_entry_delegate_type_t
@@ -152,6 +177,7 @@ fib_entry_delegate_type_to_chain_type (fib_entry_delegate_type_t fdt)
     case FIB_ENTRY_DELEGATE_ATTACHED_IMPORT:
     case FIB_ENTRY_DELEGATE_ATTACHED_EXPORT:
     case FIB_ENTRY_DELEGATE_BFD:
+    case FIB_ENTRY_DELEGATE_TRACK:
         break;
     }
     ASSERT(0);
@@ -200,7 +226,8 @@ static u8 *
 fib_entry_delegate_fmt_import (const fib_entry_delegate_t *fed,
                                u8 *s)
 {
-    s = format(s, "import:%U", fib_ae_import_format, fed->fd_index);
+    s = format(s, "import:");
+    s = fib_ae_import_format(fed->fd_index, s);
 
     return (s);
 }
@@ -212,7 +239,8 @@ static u8 *
 fib_entry_delegate_fmt_export (const fib_entry_delegate_t *fed,
                                u8 *s)
 {
-    s = format(s, "export:%U", fib_ae_export_format, fed->fd_index);
+    s = format(s, "export:");
+    s = fib_ae_export_format(fed->fd_index, s);
 
     return (s);
 }
@@ -230,6 +258,23 @@ fib_entry_delegate_fmt_bfd (const fib_entry_delegate_t *fed,
 }
 
 /**
+ * Print a delegate that represents tracking
+ */
+static u8 *
+fib_entry_delegate_fmt_track (const fib_entry_delegate_t *fed,
+                              u8 *s)
+{
+    u32 indent = format_get_indent (s);
+
+    s = format(s, "track: sibling:%d", fed->fd_track.fedt_sibling);
+
+    s = format(s, "\n%UChildren:", format_white_space, indent);
+    s = fib_node_children_format(fed->fd_track.fedt_node.fn_children, s);
+
+    return (s);
+}
+
+/**
  * A delegate type to formatter map
  */
 static fib_entry_delegate_format_t fed_formatters[] =
@@ -244,14 +289,63 @@ static fib_entry_delegate_format_t fed_formatters[] =
     [FIB_ENTRY_DELEGATE_ATTACHED_IMPORT] = fib_entry_delegate_fmt_import,
     [FIB_ENTRY_DELEGATE_ATTACHED_EXPORT] = fib_entry_delegate_fmt_export,
     [FIB_ENTRY_DELEGATE_BFD] = fib_entry_delegate_fmt_bfd,
+    [FIB_ENTRY_DELEGATE_TRACK] = fib_entry_delegate_fmt_track,
 };
 
 u8 *
-format_fib_entry_deletegate (u8 * s, va_list * args)
+format_fib_entry_delegate (u8 * s, va_list * args)
 {
     fib_entry_delegate_t *fed;
+    index_t fedi;
 
-    fed = va_arg (*args, fib_entry_delegate_t *);
+    fedi = va_arg (*args, index_t);
+    fed = fib_entry_delegate_get(fedi);
 
     return (fed_formatters[fed->fd_type](fed, s));
 }
+
+static clib_error_t *
+show_fib_entry_delegate_command (vlib_main_t * vm,
+                                 unformat_input_t * input,
+                                 vlib_cli_command_t * cmd)
+{
+    fib_node_index_t fedi;
+
+    if (unformat (input, "%d", &fedi))
+    {
+	/*
+	 * show one in detail
+	 */
+	if (!pool_is_free_index(fib_entry_delegate_pool, fedi))
+	{
+	    vlib_cli_output (vm, "%d@%U",
+			     fedi,
+			     format_fib_entry_delegate, fedi);
+	}
+	else
+	{
+	    vlib_cli_output (vm, "entry %d invalid", fedi);
+	}
+    }
+    else
+    {
+	/*
+	 * show all
+	 */
+	vlib_cli_output (vm, "FIB Entry Delegates:");
+	pool_foreach_index(fedi, fib_entry_delegate_pool,
+        ({
+	    vlib_cli_output (vm, "%d@%U",
+			     fedi,
+			     format_fib_entry_delegate, fedi);
+	}));
+    }
+
+    return (NULL);
+}
+
+VLIB_CLI_COMMAND (show_fib_entry, static) = {
+  .path = "show fib entry-delegate",
+  .function = show_fib_entry_delegate_command,
+  .short_help = "show fib entry delegate",
+};
diff --git a/src/vnet/fib/fib_entry_delegate.h b/src/vnet/fib/fib_entry_delegate.h
index 333d357c120..8fb805a56a8 100644
--- a/src/vnet/fib/fib_entry_delegate.h
+++ b/src/vnet/fib/fib_entry_delegate.h
@@ -17,6 +17,7 @@
 #define __FIB_ENTRY_DELEGATE_T__
 
 #include <vnet/fib/fib_node.h>
+#include <vnet/fib/fib_entry.h>
 
 /**
  * Delegate types
@@ -47,6 +48,10 @@ typedef enum fib_entry_delegate_type_t_ {
      */
     FIB_ENTRY_DELEGATE_BFD,
     /**
+     * Tracker
+     */
+    FIB_ENTRY_DELEGATE_TRACK,
+    /**
      * Attached import/export functionality
      */
     FIB_ENTRY_DELEGATE_ATTACHED_IMPORT,
@@ -59,19 +64,7 @@ typedef enum fib_entry_delegate_type_t_ {
          _fdt <= FIB_ENTRY_DELEGATE_CHAIN_NSH;                \
          _fdt++)                                              \
     {                                                         \
-        _fed = fib_entry_delegate_get(_entry, _fdt);          \
-        if (NULL != _fed) {                                   \
-            _body;                                            \
-        }                                                     \
-    }                                                         \
-}
-#define FOR_EACH_DELEGATE(_entry, _fdt, _fed, _body)          \
-{                                                             \
-    for (_fdt = FIB_ENTRY_DELEGATE_CHAIN_UNICAST_IP4;         \
-         _fdt <= FIB_ENTRY_DELEGATE_ATTACHED_EXPORT;          \
-         _fdt++)                                              \
-    {                                                         \
-        _fed = fib_entry_delegate_get(_entry, _fdt);          \
+        _fed = fib_entry_delegate_find(_entry, _fdt);         \
         if (NULL != _fed) {                                   \
             _body;                                            \
         }                                                     \
@@ -89,6 +82,15 @@ typedef enum fib_bfd_state_t_
 } fib_bfd_state_t;
 
 /**
+ * State for FIB entry tracking
+ */
+typedef struct fib_entry_delegate_track_t_
+{
+    fib_node_t fedt_node;
+    u32 fedt_sibling;
+} fib_entry_delegate_track_t;
+
+/**
  * A Delagate is a means to implmenet the Delagation design pattern; the extension of an
  * objects functionality through the composition of, and delgation to, other objects.
  * These 'other' objects are delegates. Delagates are thus attached to other FIB objects
@@ -134,17 +136,22 @@ typedef struct fib_entry_delegate_t_
          * BFD state
          */
         fib_bfd_state_t fd_bfd_state;
+
+        /**
+         * tracker state
+         */
+        fib_entry_delegate_track_t fd_track;
     };
 } fib_entry_delegate_t;
 
 struct fib_entry_t_;
 
-extern void fib_entry_delegate_remove(struct fib_entry_t_ *fib_entry,
+extern void fib_entry_delegate_remove(fib_entry_t *fib_entry,
                                       fib_entry_delegate_type_t type);
 
-extern fib_entry_delegate_t *fib_entry_delegate_find_or_add(struct fib_entry_t_ *fib_entry,
+extern fib_entry_delegate_t *fib_entry_delegate_find_or_add(fib_entry_t *fib_entry,
                                                             fib_entry_delegate_type_t fdt);
-extern fib_entry_delegate_t *fib_entry_delegate_get(const struct fib_entry_t_ *fib_entry,
+extern fib_entry_delegate_t *fib_entry_delegate_find(const fib_entry_t *fib_entry,
                                                     fib_entry_delegate_type_t type);
 
 extern fib_forward_chain_type_t fib_entry_delegate_type_to_chain_type(
@@ -153,6 +160,9 @@ extern fib_forward_chain_type_t fib_entry_delegate_type_to_chain_type(
 extern fib_entry_delegate_type_t fib_entry_chain_type_to_delegate_type(
      fib_forward_chain_type_t type);
 
-extern u8 *format_fib_entry_deletegate(u8 * s, va_list * args);
+extern u8 *format_fib_entry_delegate(u8 * s, va_list * args);
+
+extern fib_node_index_t fib_entry_delegate_get_index (const fib_entry_delegate_t *fed);
+extern fib_entry_delegate_t * fib_entry_delegate_get (fib_node_index_t fedi);
 
 #endif
diff --git a/src/vnet/fib/fib_entry_src.c b/src/vnet/fib/fib_entry_src.c
index cd4e4703938..067733f0a8d 100644
--- a/src/vnet/fib/fib_entry_src.c
+++ b/src/vnet/fib/fib_entry_src.c
@@ -23,6 +23,7 @@
 #include <vnet/fib/fib_table.h>
 #include <vnet/fib/fib_path_ext.h>
 #include <vnet/fib/fib_urpf_list.h>
+#include <vnet/fib/fib_entry_delegate.h>
 
 /*
  * per-source type vft
diff --git a/src/vnet/fib/fib_entry_track.c b/src/vnet/fib/fib_entry_track.c
new file mode 100644
index 00000000000..35fe9c828a6
--- /dev/null
+++ b/src/vnet/fib/fib_entry_track.c
@@ -0,0 +1,178 @@
+/*
+ * Copyright (c) 2019 Cisco and/or its affiliates.
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at:
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <vnet/fib/fib_entry_track.h>
+#include <vnet/fib/fib_table.h>
+#include <vnet/fib/fib_entry_delegate.h>
+#include <vnet/fib/fib_walk.h>
+
+static fib_entry_delegate_t *
+fib_entry_track_delegate_add (u32 fib_index,
+                              const fib_prefix_t *prefix)
+{
+    fib_entry_delegate_t *fed;
+    fib_node_index_t fei;
+
+    fei = fib_table_entry_special_add(fib_index,
+                                      prefix,
+                                      FIB_SOURCE_RR,
+                                      FIB_ENTRY_FLAG_NONE);
+
+    fed = fib_entry_delegate_find_or_add(fib_entry_get(fei),
+                                         FIB_ENTRY_DELEGATE_TRACK);
+
+    fib_node_init(&fed->fd_track.fedt_node,
+                  FIB_NODE_TYPE_ENTRY_TRACK);
+
+    fed->fd_entry_index = fei;
+    fed->fd_track.fedt_sibling =
+        fib_entry_child_add(fei,
+                            FIB_NODE_TYPE_ENTRY_TRACK,
+                            fib_entry_delegate_get_index(fed));
+
+    return (fed);
+}
+
+fib_node_index_t
+fib_entry_track (u32 fib_index,
+                 const fib_prefix_t *prefix,
+                 fib_node_type_t child_type,
+                 index_t child_index,
+                 u32 *sibling)
+{
+    fib_entry_delegate_t *fed;
+    fib_node_index_t fei;
+
+    fei = fib_table_lookup_exact_match(fib_index, prefix);
+
+    if (INDEX_INVALID == fei ||
+        NULL == (fed = fib_entry_delegate_find(fib_entry_get(fei),
+                                               FIB_ENTRY_DELEGATE_TRACK)))
+    {
+        fed = fib_entry_track_delegate_add(fib_index, prefix);
+    }
+
+    /*
+     * add this child to the entry's delegate
+     */
+    *sibling = fib_node_child_add(FIB_NODE_TYPE_ENTRY_TRACK,
+                                  fib_entry_delegate_get_index(fed),
+                                  child_type,
+                                  child_index);
+
+    return (fed->fd_entry_index);
+}
+
+void
+fib_entry_untrack (fib_node_index_t fei,
+                   u32 sibling)
+{
+    fib_entry_delegate_t *fed;
+
+    fed = fib_entry_delegate_find(fib_entry_get(fei),
+                                  FIB_ENTRY_DELEGATE_TRACK);
+
+    if (NULL != fed)
+    {
+        fib_node_child_remove(FIB_NODE_TYPE_ENTRY_TRACK,
+                              fib_entry_delegate_get_index(fed),
+                              sibling);
+        /* if this is the last child the delegate will be removed. */
+    }
+    /* else untracked */
+}
+
+static fib_node_t *
+fib_entry_track_get_node (fib_node_index_t index)
+{
+    fib_entry_delegate_t *fed;
+
+    fed = fib_entry_delegate_get(index);
+    return (&fed->fd_track.fedt_node);
+}
+
+static fib_entry_delegate_t*
+fib_entry_delegate_from_fib_node (fib_node_t *node)
+{
+    ASSERT(FIB_NODE_TYPE_ENTRY_TRACK == node->fn_type);
+    return ((fib_entry_delegate_t *) (((char *) node) -
+                                      STRUCT_OFFSET_OF (fib_entry_delegate_t,
+                                                        fd_track.fedt_node)));
+}
+
+static void
+fib_entry_track_last_lock_gone (fib_node_t *node)
+{
+    fib_entry_delegate_t *fed;
+    fib_node_index_t fei;
+    u32 sibling;
+
+    fed = fib_entry_delegate_from_fib_node(node);
+    fei = fed->fd_entry_index;
+    sibling = fed->fd_track.fedt_sibling;
+
+    /*
+     * the tracker has no more children so it can be removed,
+     * and the FIB entry unsourced.
+     * remove the delegate first, then unlock the fib entry,
+     * since the delegate may be holding the last lock
+     */
+    fib_entry_delegate_remove(fib_entry_get(fei),
+                              FIB_ENTRY_DELEGATE_TRACK);
+    /* having removed the deletegate the fed object is now toast */
+    fib_entry_child_remove(fei, sibling);
+
+    fib_table_entry_delete_index(fei, FIB_SOURCE_RR);
+}
+
+static fib_node_back_walk_rc_t
+fib_entry_track_back_walk_notify (fib_node_t *node,
+                                  fib_node_back_walk_ctx_t *ctx)
+{
+    fib_entry_delegate_t *fed;
+
+    fed = fib_entry_delegate_from_fib_node(node);
+
+    /*
+     * propagate the walk to the delgate's children
+     */
+    
+    fib_walk_sync(FIB_NODE_TYPE_ENTRY_TRACK,
+                  fib_entry_delegate_get_index(fed),
+                  ctx);
+
+    return (FIB_NODE_BACK_WALK_CONTINUE);
+}
+
+static void
+fib_entry_track_show_memory (void)
+{
+}
+
+/*
+ * The FIB entry tracker's graph node virtual function table
+ */
+static const fib_node_vft_t fib_entry_track_vft = {
+    .fnv_get = fib_entry_track_get_node,
+    .fnv_last_lock = fib_entry_track_last_lock_gone,
+    .fnv_back_walk = fib_entry_track_back_walk_notify,
+    .fnv_mem_show = fib_entry_track_show_memory,
+};
+
+void
+fib_entry_track_module_init (void)
+{
+    fib_node_register_type(FIB_NODE_TYPE_ENTRY_TRACK, &fib_entry_track_vft);
+}
diff --git a/src/vnet/fib/fib_entry_track.h b/src/vnet/fib/fib_entry_track.h
new file mode 100644
index 00000000000..63d1be0ef9a
--- /dev/null
+++ b/src/vnet/fib/fib_entry_track.h
@@ -0,0 +1,57 @@
+/*
+ * Copyright (c) 2019 Cisco and/or its affiliates.
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at:
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef __FIB_TRACKER_H__
+#define __FIB_TRACKER_H__
+
+#include <vnet/fib/fib_entry.h>
+
+/**
+ * Trackers are used on FIB entries by objects that which to track the
+ * changing state of the entry. For example a tunnel would track its
+ * destination address to be informed of reachability changes.
+ *
+ * The benefit of this aproach is that each time a new client tracks the
+ * entry it doesn't RR source it. When an entry is sourced all its children
+ * are updated. Thus, new clients tracking an entry is O(n^2). With the
+ * tracker as indirection, the entry is sourced only once.
+ */
+
+/**
+ * Track a FIB entry
+ * @param fib_index The FIB the entry is in
+ * @param prefix The Prefix of the entry to track
+ * @param child_type The type of object that is tracking this entry
+ * @param child_index The pool index of the object tracking
+ * @param sigbling [RETURNED] The sibling index of the child on the tracker
+ * @return The index of the FIB entry
+ */
+extern fib_node_index_t fib_entry_track(u32 fib_index,
+                                        const fib_prefix_t *prefix,
+                                        fib_node_type_t child_type,
+                                        index_t child_index,
+                                        u32 *sibling);
+
+/**
+ * Stop tracking a FIB entry
+ * @param fei FIB entry index (as returned from the track API above)
+ * @param sibling Sibling index (as returned from the track API above)
+ */
+extern void fib_entry_untrack(fib_node_index_t fei,
+                              u32 sibling);
+
+extern void fib_entry_track_module_init(void);
+
+#endif
diff --git a/src/vnet/fib/fib_node.h b/src/vnet/fib/fib_node.h
index e5a72a16f87..bd8bee067e4 100644
--- a/src/vnet/fib/fib_node.h
+++ b/src/vnet/fib/fib_node.h
@@ -49,6 +49,7 @@ typedef enum fib_node_type_t_ {
     FIB_NODE_TYPE_VXLAN_GBP_TUNNEL,
     FIB_NODE_TYPE_IPSEC_SA,
     FIB_NODE_TYPE_IP_PUNT_REDIRECT,
+    FIB_NODE_TYPE_ENTRY_TRACK,
     /**
      * Marker. New types before this one. leave the test last.
      */
@@ -77,7 +78,8 @@ typedef enum fib_node_type_t_ {
     [FIB_NODE_TYPE_BIER_ENTRY] = "bier-entry",			\
     [FIB_NODE_TYPE_VXLAN_GBP_TUNNEL] = "vxlan-gbp-tunnel",	\
     [FIB_NODE_TYPE_IPSEC_SA] = "ipsec-sa",                      \
-    [FIB_NODE_TYPE_IP_PUNT_REDIRECT] = "ip-punt-redirect"       \
+    [FIB_NODE_TYPE_IP_PUNT_REDIRECT] = "ip-punt-redirect",      \
+    [FIB_NODE_TYPE_ENTRY_TRACK] = "fib-entry-track"             \
 }
 
 /**