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>
diff --git a/src/vnet/CMakeLists.txt b/src/vnet/CMakeLists.txt
index 7af1703..68e806e 100644
--- a/src/vnet/CMakeLists.txt
+++ b/src/vnet/CMakeLists.txt
@@ -1288,6 +1288,7 @@
fib/fib_entry_src_lisp.c
fib/fib_entry_cover.c
fib/fib_entry_delegate.c
+ fib/fib_entry_track.c
fib/fib_path_list.c
fib/fib_path.c
fib/fib_path_ext.c
diff --git a/src/vnet/adj/adj_midchain_delegate.c b/src/vnet/adj/adj_midchain_delegate.c
index 922283e..9e78843 100644
--- a/src/vnet/adj/adj_midchain_delegate.c
+++ b/src/vnet/adj/adj_midchain_delegate.c
@@ -16,6 +16,7 @@
#include <vnet/adj/adj_delegate.h>
#include <vnet/adj/adj_midchain.h>
#include <vnet/fib/fib_table.h>
+#include <vnet/fib/fib_entry_track.h>
/**
* Midchain stacker delegate
@@ -121,13 +122,11 @@
amd->amd_fei = FIB_NODE_INDEX_INVALID;
adj_delegate_add(adj, ADJ_DELEGATE_MIDCHAIN, amd - amd_pool);
- amd->amd_fei = fib_table_entry_special_add(fib_index,
- pfx,
- FIB_SOURCE_RR,
- FIB_ENTRY_FLAG_NONE);
- amd->amd_sibling = fib_entry_child_add(amd->amd_fei,
- FIB_NODE_TYPE_ADJ,
- ai);
+ amd->amd_fei = fib_entry_track(fib_index,
+ pfx,
+ FIB_NODE_TYPE_ADJ,
+ ai,
+ &amd->amd_sibling);
}
adj_midchain_delegate_restack_i(ai, amd);
}
@@ -145,8 +144,7 @@
amd = pool_elt_at_index(amd_pool, ad->ad_index);
- fib_entry_child_remove (amd->amd_fei, amd->amd_sibling);
- fib_table_entry_delete_index (amd->amd_fei, FIB_SOURCE_RR);
+ fib_entry_untrack(amd->amd_fei, amd->amd_sibling);
pool_put(amd_pool, amd);
}
diff --git a/src/vnet/fib/fib_attached_export.c b/src/vnet/fib/fib_attached_export.c
index da83a3d..a0f4e4e 100644
--- a/src/vnet/fib/fib_attached_export.c
+++ b/src/vnet/fib/fib_attached_export.c
@@ -99,8 +99,8 @@
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_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 @@
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_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_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_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 f785ba2..b02fbc6 100644
--- a/src/vnet/fib/fib_bfd.c
+++ b/src/vnet/fib/fib_bfd.c
@@ -94,8 +94,8 @@
* 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 @@
*/
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 @@
* 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 6ff692d..9169dcc 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 @@
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 @@
}
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 = 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_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 5d0fb24..70c6621 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 @@
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 c730822..153bd70 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 @@
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_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_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 4bf37df..d7503fb 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_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 @@
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_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;
- vec_add1(fib_entry->fe_delegates, 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 - 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_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 @@
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 @@
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 @@
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 @@
}
/**
+ * 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 @@
[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 333d357..8fb805a 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 @@
*/
FIB_ENTRY_DELEGATE_BFD,
/**
+ * Tracker
+ */
+ FIB_ENTRY_DELEGATE_TRACK,
+ /**
* Attached import/export functionality
*/
FIB_ENTRY_DELEGATE_ATTACHED_IMPORT,
@@ -59,19 +64,7 @@
_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 @@
} 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 @@
* 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_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 cd4e470..067733f 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 0000000..35fe9c8
--- /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 0000000..63d1be0
--- /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 e5a72a1..bd8bee0 100644
--- a/src/vnet/fib/fib_node.h
+++ b/src/vnet/fib/fib_node.h
@@ -49,6 +49,7 @@
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 @@
[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" \
}
/**
diff --git a/src/vnet/geneve/geneve.c b/src/vnet/geneve/geneve.c
index b0c17e2..dcbdb2f 100644
--- a/src/vnet/geneve/geneve.c
+++ b/src/vnet/geneve/geneve.c
@@ -16,6 +16,7 @@
#include <vnet/ip/format.h>
#include <vnet/fib/fib_entry.h>
#include <vnet/fib/fib_table.h>
+#include <vnet/fib/fib_entry_track.h>
#include <vnet/mfib/mfib_table.h>
#include <vnet/adj/adj_mcast.h>
#include <vnet/interface.h>
@@ -498,12 +499,11 @@
* re-stack accordingly
*/
vtep_addr_ref (&t->local);
- t->fib_entry_index = fib_table_entry_special_add
- (t->encap_fib_index, &tun_remote_pfx, FIB_SOURCE_RR,
- FIB_ENTRY_FLAG_NONE);
- t->sibling_index = fib_entry_child_add
- (t->fib_entry_index, FIB_NODE_TYPE_GENEVE_TUNNEL,
- t - vxm->tunnels);
+ t->fib_entry_index = fib_entry_track (t->encap_fib_index,
+ &tun_remote_pfx,
+ FIB_NODE_TYPE_GENEVE_TUNNEL,
+ t - vxm->tunnels,
+ &t->sibling_index);
geneve_tunnel_restack_dpo (t);
}
else
@@ -605,8 +605,7 @@
if (!ip46_address_is_multicast (&t->remote))
{
vtep_addr_unref (&t->local);
- fib_entry_child_remove (t->fib_entry_index, t->sibling_index);
- fib_table_entry_delete_index (t->fib_entry_index, FIB_SOURCE_RR);
+ fib_entry_untrack (t->fib_entry_index, t->sibling_index);
}
else if (vtep_addr_unref (&t->remote) == 0)
{
diff --git a/src/vnet/ipip/sixrd.c b/src/vnet/ipip/sixrd.c
index 30c37c8..d4adf9d 100644
--- a/src/vnet/ipip/sixrd.c
+++ b/src/vnet/ipip/sixrd.c
@@ -34,6 +34,7 @@
#include <vnet/adj/adj_midchain.h>
#include <vnet/dpo/lookup_dpo.h>
#include <vnet/fib/fib_table.h>
+#include <vnet/fib/fib_entry_track.h>
#include <vnet/fib/ip6_fib.h>
#include <vnet/plugin/plugin.h>
@@ -227,12 +228,10 @@
fib_node_init (&sixrd_ad->sixrd_node, sixrd_fib_node_type);
sixrd_ad->adj_index = ai;
sixrd_ad->sixrd_fib_entry_index =
- fib_table_entry_special_add (t->fib_index, &pfx, FIB_SOURCE_RR,
- FIB_ENTRY_FLAG_NONE);
- sixrd_ad->sixrd_sibling =
- fib_entry_child_add (sixrd_ad->sixrd_fib_entry_index,
- sixrd_fib_node_type,
- sixrd_ad - sixrd_adj_delegate_pool);
+ fib_entry_track (t->fib_index, &pfx,
+ sixrd_fib_node_type,
+ sixrd_ad - sixrd_adj_delegate_pool,
+ &sixrd_ad->sixrd_sibling);
adj_delegate_add (adj, sixrd_adj_delegate_type,
sixrd_ad - sixrd_adj_delegate_pool);
@@ -421,10 +420,8 @@
sixrd_adj_delegate_t *sixrd_ad;
sixrd_ad = sixrd_adj_from_base (aed);
- fib_entry_child_remove (sixrd_ad->sixrd_fib_entry_index,
- sixrd_ad->sixrd_sibling);
- fib_table_entry_delete_index (sixrd_ad->sixrd_fib_entry_index,
- FIB_SOURCE_RR);
+ fib_entry_untrack (sixrd_ad->sixrd_fib_entry_index,
+ sixrd_ad->sixrd_sibling);
pool_put (sixrd_adj_delegate_pool, sixrd_ad);
}
diff --git a/src/vnet/ipsec/ipsec_sa.c b/src/vnet/ipsec/ipsec_sa.c
index e3eff58..11d6b10 100644
--- a/src/vnet/ipsec/ipsec_sa.c
+++ b/src/vnet/ipsec/ipsec_sa.c
@@ -17,6 +17,7 @@
#include <vnet/ipsec/esp.h>
#include <vnet/udp/udp.h>
#include <vnet/fib/fib_table.h>
+#include <vnet/fib/fib_entry_track.h>
#include <vnet/ipsec/ipsec_tun.h>
/**
@@ -218,12 +219,10 @@
return VNET_API_ERROR_NO_SUCH_FIB;
}
- sa->fib_entry_index = fib_table_entry_special_add (sa->tx_fib_index,
- &pfx,
- FIB_SOURCE_RR,
- FIB_ENTRY_FLAG_NONE);
- sa->sibling = fib_entry_child_add (sa->fib_entry_index,
- FIB_NODE_TYPE_IPSEC_SA, sa_index);
+ sa->fib_entry_index = fib_entry_track (sa->tx_fib_index,
+ &pfx,
+ FIB_NODE_TYPE_IPSEC_SA,
+ sa_index, &sa->sibling);
ipsec_sa_stack (sa);
/* generate header templates */
@@ -288,10 +287,7 @@
if (ipsec_sa_is_set_IS_TUNNEL (sa) && !ipsec_sa_is_set_IS_INBOUND (sa))
{
- fib_entry_child_remove (sa->fib_entry_index, sa->sibling);
- fib_table_entry_special_remove
- (sa->tx_fib_index,
- fib_entry_get_prefix (sa->fib_entry_index), FIB_SOURCE_RR);
+ fib_entry_untrack (sa->fib_entry_index, sa->sibling);
dpo_reset (&sa->dpo);
}
vnet_crypto_key_del (vm, sa->crypto_key_index);
diff --git a/src/vnet/udp/udp_encap.c b/src/vnet/udp/udp_encap.c
index df4a811..0b1d3d7 100644
--- a/src/vnet/udp/udp_encap.c
+++ b/src/vnet/udp/udp_encap.c
@@ -15,6 +15,7 @@
#include <vnet/udp/udp_encap.h>
#include <vnet/fib/fib_entry.h>
+#include <vnet/fib/fib_entry_track.h>
#include <vnet/fib/fib_table.h>
#include <vnet/dpo/drop_dpo.h>
@@ -117,14 +118,10 @@
.fp_addr = *dst_ip,
};
- ue->ue_fib_entry_index =
- fib_table_entry_special_add (fib_index,
- &dst_pfx,
- FIB_SOURCE_RR, FIB_ENTRY_FLAG_NONE);
- ue->ue_fib_sibling =
- fib_entry_child_add (ue->ue_fib_entry_index,
- FIB_NODE_TYPE_UDP_ENCAP, uei);
-
+ ue->ue_fib_entry_index = fib_entry_track (fib_index,
+ &dst_pfx,
+ FIB_NODE_TYPE_UDP_ENCAP,
+ uei, &ue->ue_fib_sibling);
udp_encap_restack (ue);
return (uei);
@@ -322,9 +319,7 @@
*/
dpo_reset (&ue->ue_dpo);
- fib_entry_child_remove (ue->ue_fib_entry_index, ue->ue_fib_sibling);
- fib_table_entry_delete_index (ue->ue_fib_entry_index, FIB_SOURCE_RR);
-
+ fib_entry_untrack (ue->ue_fib_entry_index, ue->ue_fib_sibling);
pool_put (udp_encap_pool, ue);
}
diff --git a/src/vnet/vxlan-gbp/vxlan_gbp.c b/src/vnet/vxlan-gbp/vxlan_gbp.c
index 7b09b57..3b6f166 100644
--- a/src/vnet/vxlan-gbp/vxlan_gbp.c
+++ b/src/vnet/vxlan-gbp/vxlan_gbp.c
@@ -16,6 +16,7 @@
#include <vnet/ip/format.h>
#include <vnet/fib/fib_entry.h>
#include <vnet/fib/fib_table.h>
+#include <vnet/fib/fib_entry_track.h>
#include <vnet/mfib/mfib_table.h>
#include <vnet/adj/adj_mcast.h>
#include <vnet/adj/rewrite.h>
@@ -529,12 +530,11 @@
* re-stack accordingly
*/
vtep_addr_ref (&t->src);
- t->fib_entry_index = fib_table_entry_special_add
- (t->encap_fib_index, &tun_dst_pfx, FIB_SOURCE_RR,
- FIB_ENTRY_FLAG_NONE);
- t->sibling_index = fib_entry_child_add
- (t->fib_entry_index, FIB_NODE_TYPE_VXLAN_GBP_TUNNEL,
- dev_instance);
+ t->fib_entry_index = fib_entry_track (t->encap_fib_index,
+ &tun_dst_pfx,
+ FIB_NODE_TYPE_VXLAN_GBP_TUNNEL,
+ dev_instance,
+ &t->sibling_index);
vxlan_gbp_tunnel_restack_dpo (t);
}
else
@@ -640,8 +640,7 @@
if (!ip46_address_is_multicast (&t->dst))
{
vtep_addr_unref (&t->src);
- fib_entry_child_remove (t->fib_entry_index, t->sibling_index);
- fib_table_entry_delete_index (t->fib_entry_index, FIB_SOURCE_RR);
+ fib_entry_untrack (t->fib_entry_index, t->sibling_index);
}
else if (vtep_addr_unref (&t->dst) == 0)
{
diff --git a/src/vnet/vxlan-gpe/vxlan_gpe.c b/src/vnet/vxlan-gpe/vxlan_gpe.c
index dd0e544..fda9853 100644
--- a/src/vnet/vxlan-gpe/vxlan_gpe.c
+++ b/src/vnet/vxlan-gpe/vxlan_gpe.c
@@ -22,6 +22,7 @@
#include <vnet/ip/format.h>
#include <vnet/fib/fib_entry.h>
#include <vnet/fib/fib_table.h>
+#include <vnet/fib/fib_entry_track.h>
#include <vnet/mfib/mfib_table.h>
#include <vnet/adj/adj_mcast.h>
#include <vnet/interface.h>
@@ -620,12 +621,11 @@
* re-stack accordingly
*/
vtep_addr_ref (&t->local);
- t->fib_entry_index = fib_table_entry_special_add
- (t->encap_fib_index, &tun_remote_pfx, FIB_SOURCE_RR,
- FIB_ENTRY_FLAG_NONE);
- t->sibling_index = fib_entry_child_add
- (t->fib_entry_index, FIB_NODE_TYPE_VXLAN_GPE_TUNNEL,
- t - ngm->tunnels);
+ t->fib_entry_index = fib_entry_track (t->encap_fib_index,
+ &tun_remote_pfx,
+ FIB_NODE_TYPE_VXLAN_GPE_TUNNEL,
+ t - ngm->tunnels,
+ &t->sibling_index);
vxlan_gpe_tunnel_restack_dpo (t);
}
else
@@ -727,8 +727,7 @@
if (!ip46_address_is_multicast (&t->remote))
{
vtep_addr_unref (&t->local);
- fib_entry_child_remove (t->fib_entry_index, t->sibling_index);
- fib_table_entry_delete_index (t->fib_entry_index, FIB_SOURCE_RR);
+ fib_entry_untrack (t->fib_entry_index, t->sibling_index);
}
else if (vtep_addr_unref (&t->remote) == 0)
{
diff --git a/src/vnet/vxlan/vxlan.c b/src/vnet/vxlan/vxlan.c
index def306a..c274cdb 100644
--- a/src/vnet/vxlan/vxlan.c
+++ b/src/vnet/vxlan/vxlan.c
@@ -16,6 +16,7 @@
#include <vnet/ip/format.h>
#include <vnet/fib/fib_entry.h>
#include <vnet/fib/fib_table.h>
+#include <vnet/fib/fib_entry_track.h>
#include <vnet/mfib/mfib_table.h>
#include <vnet/adj/adj_mcast.h>
#include <vnet/adj/rewrite.h>
@@ -513,11 +514,11 @@
* re-stack accordingly
*/
vtep_addr_ref (&t->src);
- t->fib_entry_index = fib_table_entry_special_add
- (t->encap_fib_index, &tun_dst_pfx, FIB_SOURCE_RR,
- FIB_ENTRY_FLAG_NONE);
- t->sibling_index = fib_entry_child_add
- (t->fib_entry_index, FIB_NODE_TYPE_VXLAN_TUNNEL, dev_instance);
+ t->fib_entry_index = fib_entry_track (t->encap_fib_index,
+ &tun_dst_pfx,
+ FIB_NODE_TYPE_VXLAN_TUNNEL,
+ dev_instance,
+ &t->sibling_index);
vxlan_tunnel_restack_dpo (t);
}
else
@@ -619,8 +620,7 @@
vnet_flow_del (vnm, t->flow_index);
vtep_addr_unref (&t->src);
- fib_entry_child_remove (t->fib_entry_index, t->sibling_index);
- fib_table_entry_delete_index (t->fib_entry_index, FIB_SOURCE_RR);
+ fib_entry_untrack (t->fib_entry_index, t->sibling_index);
}
else if (vtep_addr_unref (&t->dst) == 0)
{