From 1f50bf8fc57ebf78f9056185a342493be460a847 Mon Sep 17 00:00:00 2001 From: Neale Ranns Date: Tue, 16 Jul 2019 15:28:52 +0000 Subject: 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 --- src/vnet/fib/fib_attached_export.c | 24 ++--- src/vnet/fib/fib_bfd.c | 12 +-- src/vnet/fib/fib_entry.c | 19 ++-- src/vnet/fib/fib_entry.h | 5 +- src/vnet/fib/fib_entry_cover.c | 7 +- src/vnet/fib/fib_entry_delegate.c | 122 ++++++++++++++++++++++--- src/vnet/fib/fib_entry_delegate.h | 44 +++++---- src/vnet/fib/fib_entry_src.c | 1 + src/vnet/fib/fib_entry_track.c | 178 +++++++++++++++++++++++++++++++++++++ src/vnet/fib/fib_entry_track.h | 57 ++++++++++++ src/vnet/fib/fib_node.h | 4 +- 11 files changed, 409 insertions(+), 64 deletions(-) create mode 100644 src/vnet/fib/fib_entry_track.c create mode 100644 src/vnet/fib/fib_entry_track.h (limited to 'src/vnet/fib') 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 #include #include +#include +#include /* * 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 -#include #include #include #include @@ -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 #include #include +#include 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 #include +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); } @@ -229,6 +257,23 @@ fib_entry_delegate_fmt_bfd (const fib_entry_delegate_t *fed, return (s); } +/** + * 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 */ @@ -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 +#include /** * Delegate types @@ -46,6 +47,10 @@ typedef enum fib_entry_delegate_type_t_ { * BFD session state */ FIB_ENTRY_DELEGATE_BFD, + /** + * Tracker + */ + FIB_ENTRY_DELEGATE_TRACK, /** * Attached import/export functionality */ @@ -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; \ } \ @@ -88,6 +81,15 @@ typedef enum fib_bfd_state_t_ FIB_BFD_STATE_DOWN, } 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. @@ -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 #include #include +#include /* * 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 +#include +#include +#include + +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 + +/** + * 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" \ } /** -- cgit 1.2.3-korg