summaryrefslogtreecommitdiffstats
path: root/src/vnet/fib
diff options
context:
space:
mode:
authorNeale Ranns <nranns@cisco.com>2019-07-16 15:28:52 +0000
committerDave Barach <openvpp@barachs.net>2019-07-19 21:46:36 +0000
commit1f50bf8fc57ebf78f9056185a342493be460a847 (patch)
tree55bcf7508dc679b9a38552438d21b8b1fa05331e /src/vnet/fib
parentcca9618a5e1b126263ef262974b0b4d6ac6352a2 (diff)
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>
Diffstat (limited to 'src/vnet/fib')
-rw-r--r--src/vnet/fib/fib_attached_export.c24
-rw-r--r--src/vnet/fib/fib_bfd.c12
-rw-r--r--src/vnet/fib/fib_entry.c19
-rw-r--r--src/vnet/fib/fib_entry.h5
-rw-r--r--src/vnet/fib/fib_entry_cover.c7
-rw-r--r--src/vnet/fib/fib_entry_delegate.c122
-rw-r--r--src/vnet/fib/fib_entry_delegate.h44
-rw-r--r--src/vnet/fib/fib_entry_src.c1
-rw-r--r--src/vnet/fib/fib_entry_track.c178
-rw-r--r--src/vnet/fib/fib_entry_track.h57
-rw-r--r--src/vnet/fib/fib_node.h4
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" \
}
/**