From a4e776642fe2d4572b6e604478182fa9b7e1fa2d Mon Sep 17 00:00:00 2001 From: Neale Ranns Date: Mon, 4 Dec 2017 20:00:30 +0000 Subject: [PATCH] Revert "FIB: optimise for src memory allocations" This reverts commit 84517cfd1508f6da24937f310f7fffe752f22584. Change-Id: Ic7eeffa2ed4607d3d653f34b93c20c833c789ee1 Signed-off-by: Neale Ranns --- src/vnet/fib/fib_entry.c | 67 +++++-------- src/vnet/fib/fib_entry.h | 44 +-------- src/vnet/fib/fib_entry_src.c | 197 +++++++++++++------------------------- src/vnet/fib/fib_entry_src.h | 70 +++++--------- src/vnet/fib/fib_entry_src_mpls.c | 7 ++ 5 files changed, 121 insertions(+), 264 deletions(-) diff --git a/src/vnet/fib/fib_entry.c b/src/vnet/fib/fib_entry.c index a9ca0f20f6d..35716cacc29 100644 --- a/src/vnet/fib/fib_entry.c +++ b/src/vnet/fib/fib_entry.c @@ -213,33 +213,29 @@ fib_entry_last_lock_gone (fib_node_t *node) FIB_ENTRY_DBG(fib_entry, "last-lock"); fib_node_deinit(&fib_entry->fe_node); + // FIXME -RR Backwalk ASSERT(0 == vec_len(fib_entry->fe_delegates)); vec_free(fib_entry->fe_delegates); - if (fib_entry_has_multiple_srcs(fib_entry)) - { - vec_free(fib_entry->fe_u_src.fe_srcs); - } + vec_free(fib_entry->fe_srcs); pool_put(fib_entry_pool, fib_entry); } -static const fib_entry_src_t* +static fib_entry_src_t* fib_entry_get_best_src_i (const fib_entry_t *fib_entry) { - const fib_entry_src_t *bsrc; + fib_entry_src_t *bsrc; /* * the enum of sources is deliberately arranged in priority order */ - if (fib_entry_has_multiple_srcs(fib_entry)) + if (0 == vec_len(fib_entry->fe_srcs)) { - ASSERT(vec_len(fib_entry->fe_u_src.fe_srcs)); - - bsrc = vec_elt_at_index(fib_entry->fe_u_src.fe_srcs, 0); + bsrc = NULL; } else { - bsrc = &fib_entry->fe_u_src.fe_src; + bsrc = vec_elt_at_index(fib_entry->fe_srcs, 0); } return (bsrc); @@ -252,7 +248,7 @@ fib_entry_src_get_source (const fib_entry_src_t *esrc) { return (esrc->fes_src); } - return (FIB_SOURCE_INVALID); + return (FIB_SOURCE_MAX); } static fib_entry_flag_t @@ -265,18 +261,6 @@ fib_entry_src_get_flags (const fib_entry_src_t *esrc) return (FIB_ENTRY_FLAG_NONE); } -fib_entry_flag_t -fib_entry_get_flags_i (const fib_entry_t *fib_entry) -{ - const fib_entry_src_t *esrc; - - esrc = fib_entry_get_best_src_i(fib_entry); - - ASSERT(esrc); - - return (esrc->fes_entry_flags); -} - fib_entry_flag_t fib_entry_get_flags (fib_node_index_t fib_entry_index) { @@ -346,18 +330,11 @@ fib_entry_show_memory (void) pool_foreach(entry, fib_entry_pool, ({ - if (fib_entry_has_multiple_srcs(entry)) - { - n_srcs += vec_len(entry->fe_u_src.fe_srcs); - vec_foreach(esrc, entry->fe_u_src.fe_srcs) - { - n_exts += fib_path_ext_list_length(&esrc->fes_path_exts); - } - } - else - { - n_exts += fib_path_ext_list_length(&entry->fe_u_src.fe_src.fes_path_exts); - } + n_srcs += vec_len(entry->fe_srcs); + vec_foreach(esrc, entry->fe_srcs) + { + n_exts += fib_path_ext_list_length(&esrc->fes_path_exts); + } })); fib_show_memory_usage("Entry Source", @@ -818,10 +795,10 @@ fib_entry_special_add (fib_node_index_t fib_entry_index, fib_entry_flag_t flags, const dpo_id_t *dpo) { - const fib_entry_src_t *bsrc; fib_source_t best_source; fib_entry_flag_t bflags; fib_entry_t *fib_entry; + fib_entry_src_t *bsrc; fib_entry = fib_entry_get(fib_entry_index); @@ -839,10 +816,10 @@ fib_entry_special_update (fib_node_index_t fib_entry_index, fib_entry_flag_t flags, const dpo_id_t *dpo) { - const fib_entry_src_t *bsrc; fib_source_t best_source; fib_entry_flag_t bflags; fib_entry_t *fib_entry; + fib_entry_src_t *bsrc; fib_entry = fib_entry_get(fib_entry_index); @@ -861,10 +838,10 @@ fib_entry_path_add (fib_node_index_t fib_entry_index, fib_entry_flag_t flags, const fib_route_path_t *rpath) { - const fib_entry_src_t *bsrc; fib_source_t best_source; fib_entry_flag_t bflags; fib_entry_t *fib_entry; + fib_entry_src_t *bsrc; ASSERT(1 == vec_len(rpath)); @@ -923,11 +900,11 @@ fib_entry_path_remove (fib_node_index_t fib_entry_index, fib_source_t source, const fib_route_path_t *rpath) { - const fib_entry_src_t *bsrc; fib_entry_src_flag_t sflag; fib_source_t best_source; fib_entry_flag_t bflags; fib_entry_t *fib_entry; + fib_entry_src_t *bsrc; ASSERT(1 == vec_len(rpath)); @@ -974,7 +951,7 @@ fib_entry_path_remove (fib_node_index_t fib_entry_index, bsrc = fib_entry_get_best_src_i(fib_entry); best_source = fib_entry_src_get_source(bsrc); - if (FIB_SOURCE_INVALID == best_source) { + if (FIB_SOURCE_MAX == best_source) { /* * no more sources left. this entry is toast. */ @@ -1019,11 +996,11 @@ fib_entry_src_flag_t fib_entry_special_remove (fib_node_index_t fib_entry_index, fib_source_t source) { - const fib_entry_src_t *bsrc; fib_entry_src_flag_t sflag; fib_source_t best_source; fib_entry_flag_t bflags; fib_entry_t *fib_entry; + fib_entry_src_t *bsrc; fib_entry = fib_entry_get(fib_entry_index); ASSERT(NULL != fib_entry); @@ -1064,7 +1041,7 @@ fib_entry_special_remove (fib_node_index_t fib_entry_index, bsrc = fib_entry_get_best_src_i(fib_entry); best_source = fib_entry_src_get_source(bsrc); - if (FIB_SOURCE_INVALID == best_source) { + if (FIB_SOURCE_MAX == best_source) { /* * no more sources left. this entry is toast. */ @@ -1121,10 +1098,10 @@ fib_entry_update (fib_node_index_t fib_entry_index, fib_entry_flag_t flags, const fib_route_path_t *paths) { - const fib_entry_src_t *bsrc; fib_source_t best_source; fib_entry_flag_t bflags; fib_entry_t *fib_entry; + fib_entry_src_t *bsrc; fib_entry = fib_entry_get(fib_entry_index); ASSERT(NULL != fib_entry); @@ -1384,8 +1361,8 @@ fib_entry_get_resolving_interface (fib_node_index_t entry_index) fib_source_t fib_entry_get_best_source (fib_node_index_t entry_index) { - const fib_entry_src_t *bsrc; fib_entry_t *fib_entry; + fib_entry_src_t *bsrc; fib_entry = fib_entry_get(entry_index); diff --git a/src/vnet/fib/fib_entry.h b/src/vnet/fib/fib_entry.h index cd954e3a15c..cd2a685b765 100644 --- a/src/vnet/fib/fib_entry.h +++ b/src/vnet/fib/fib_entry.h @@ -28,10 +28,6 @@ * The lower the value the higher the priority */ typedef enum fib_source_t_ { - /** - * An invalid source of value 0 - */ - FIB_SOURCE_INVALID, /** * Marker. Add new values after this one. */ @@ -146,7 +142,6 @@ STATIC_ASSERT (sizeof(fib_source_t) == 1, #define FIB_SOURCE_MAX (FIB_SOURCE_LAST+1) #define FIB_SOURCES { \ - [FIB_SOURCE_INVALID] = "invalid", \ [FIB_SOURCE_SPECIAL] = "special", \ [FIB_SOURCE_INTERFACE] = "interface", \ [FIB_SOURCE_PROXY] = "proxy", \ @@ -381,29 +376,6 @@ typedef struct fib_entry_src_t_ { }; } fib_entry_src_t; -/** - * FIB entry flags. - * these are stored in the pad space within the fib_node_t - */ -typedef enum fib_entry_node_attribute_t_ -{ - /** - * FIB entry has multiple sources, so the fe_srcs union - * uses the vector - */ - FIB_ENTRY_NODE_ATTR_MULTIPLE_SRCS, -} fib_entry_node_attribute_t; - -#define FIB_ENTRY_NODE_FLAG_NAMES { \ - [FIB_ENTRY_NODE_ATTR_MULTIPLE_SRCS] = "multiple-srcs", \ -} - -typedef enum fib_entry_node_flags_t_ -{ - FIB_ENTRY_NODE_FLAG_MULTIPLE_SRCS = (1 << FIB_ENTRY_NODE_ATTR_MULTIPLE_SRCS), -} fib_entry_node_flags_t; - - /** * An entry in a FIB table. * @@ -437,20 +409,12 @@ typedef struct fib_entry_t_ { * type to derive the EOS bit value. */ dpo_id_t fe_lb; - /** - * Source info. - * in the majority of cases a FIB entry will have only one source. - * so to save the extra memory allocation of the source's vector, we - * store space for one source inline. When two sources are present, - * we burn extra memory. - * The union is switched based on the FIB_ENTRY_NODE_FLAG_MULTIPLE_SRCS + * Vector of source infos. + * Most entries will only have 1 source. So we optimise for memory usage, + * which is preferable since we have many entries. */ - union { - fib_entry_src_t *fe_srcs; - fib_entry_src_t fe_src; - } fe_u_src; - + fib_entry_src_t *fe_srcs; /** * the path-list for which this entry is a child. This is also the path-list * that is contributing forwarding for this entry. diff --git a/src/vnet/fib/fib_entry_src.c b/src/vnet/fib/fib_entry_src.c index acb8579e85e..214dafe9b8d 100644 --- a/src/vnet/fib/fib_entry_src.c +++ b/src/vnet/fib/fib_entry_src.c @@ -61,62 +61,13 @@ fib_entry_src_action_init (fib_entry_t *fib_entry, fib_entry_src_vft[source].fesv_init(&esrc); } - if (fib_entry_has_multiple_srcs(fib_entry)) - { - vec_add1(fib_entry->fe_u_src.fe_srcs, esrc); - - vec_sort_with_function(fib_entry->fe_u_src.fe_srcs, - fib_entry_src_cmp_for_sort); - } - else - { - /* - * is this the very first source - */ - if (FIB_SOURCE_INVALID == fib_entry->fe_u_src.fe_src.fes_src) - { - clib_memcpy(&fib_entry->fe_u_src.fe_src, &esrc, sizeof(esrc)); - } - else - { - /* - * transitioning to multiple sources. - * allocate the vecotr of sources. - */ - fib_entry_src_t *srcs = NULL; - - vec_validate(srcs, 1); - - /* - * sorted insert - */ - if (fib_entry->fe_u_src.fe_src.fes_src < esrc.fes_src) - { - srcs[0] = fib_entry->fe_u_src.fe_src; - srcs[1] = esrc; - } - else - { - srcs[0] = esrc; - srcs[1] = fib_entry->fe_u_src.fe_src; - } - memset(&fib_entry->fe_u_src.fe_src, 0, - sizeof(fib_entry->fe_u_src.fe_src)); - fib_entry->fe_u_src.fe_srcs = srcs; - - fib_entry->fe_node.fn_pad |= FIB_ENTRY_NODE_FLAG_MULTIPLE_SRCS; - } - } -} - -u32 -fib_entry_has_multiple_srcs(const fib_entry_t * fib_entry) -{ - return (fib_entry->fe_node.fn_pad & FIB_ENTRY_NODE_FLAG_MULTIPLE_SRCS); + vec_add1(fib_entry->fe_srcs, esrc); + vec_sort_with_function(fib_entry->fe_srcs, + fib_entry_src_cmp_for_sort); } static fib_entry_src_t * -fib_entry_src_find (fib_entry_t *fib_entry, +fib_entry_src_find (const fib_entry_t *fib_entry, fib_source_t source, u32 *index) @@ -125,80 +76,20 @@ fib_entry_src_find (fib_entry_t *fib_entry, int ii; ii = 0; - if (fib_entry_has_multiple_srcs(fib_entry)) - { - vec_foreach(esrc, fib_entry->fe_u_src.fe_srcs) - { - if (esrc->fes_src == source) - { - if (NULL != index) - { - *index = ii; - } - return (esrc); - } - else - { - ii++; - } - } - } - else - { - esrc = &fib_entry->fe_u_src.fe_src; - if (esrc->fes_src == source) - { - if (NULL != index) - { - *index = -1; - } - return (esrc); - } - } - - return (NULL); -} - -static fib_entry_src_t * -fib_entry_src_delete (fib_entry_t *fib_entry, - u32 index) - -{ - if (-1 == index) - { - ASSERT(!fib_entry_has_multiple_srcs(fib_entry)); - memset(&fib_entry->fe_u_src.fe_src, 0, - sizeof(fib_entry->fe_u_src.fe_src)); - } - else + vec_foreach(esrc, fib_entry->fe_srcs) { - vec_del1(fib_entry->fe_u_src.fe_srcs, index); - - ASSERT(vec_len(fib_entry->fe_u_src.fe_srcs)); - if (1 == vec_len(fib_entry->fe_u_src.fe_srcs)) - { - /* - * Is there much point in transitioning back? - * We've paid the cost of the malloc for the vector, - * why not keep it. - * Favour memory use. If the expectation that multiple sources - * is rare is correct, then we should expect this entry is - * unlikely to need the vector again - */ - fib_entry_src_t *srcs; - - srcs = fib_entry->fe_u_src.fe_srcs; - fib_entry->fe_node.fn_pad &= ~FIB_ENTRY_NODE_FLAG_MULTIPLE_SRCS; - clib_memcpy(&fib_entry->fe_u_src.fe_src, - &srcs[0], - sizeof(fib_entry->fe_u_src.fe_src)); - vec_free(srcs); - } - else - { - vec_sort_with_function(fib_entry->fe_u_src.fe_srcs, - fib_entry_src_cmp_for_sort); - } + if (esrc->fes_src == source) + { + if (NULL != index) + { + *index = ii; + } + return (esrc); + } + else + { + ii++; + } } return (NULL); @@ -217,7 +108,8 @@ fib_entry_is_sourced (fib_node_index_t fib_entry_index, static fib_entry_src_t * fib_entry_src_find_or_create (fib_entry_t *fib_entry, - fib_source_t source) + fib_source_t source, + u32 *index) { fib_entry_src_t *esrc; @@ -249,7 +141,7 @@ fib_entry_src_action_deinit (fib_entry_t *fib_entry, } fib_path_ext_list_flush(&esrc->fes_path_exts); - fib_entry_src_delete(fib_entry, index); + vec_del1(fib_entry->fe_srcs, index); } fib_entry_src_cover_res_t @@ -852,6 +744,23 @@ fib_entry_src_action_deactivate (fib_entry_t *fib_entry, fib_entry->fe_sibling = FIB_NODE_INDEX_INVALID; } +static void +fib_entry_src_action_fwd_update (const fib_entry_t *fib_entry, + fib_source_t source) +{ + fib_entry_src_t *esrc; + + vec_foreach(esrc, fib_entry->fe_srcs) + { + if (NULL != fib_entry_src_vft[esrc->fes_src].fesv_fwd_update) + { + fib_entry_src_vft[esrc->fes_src].fesv_fwd_update(esrc, + fib_entry, + source); + } + } +} + void fib_entry_src_action_reactivate (fib_entry_t *fib_entry, fib_source_t source) @@ -904,10 +813,11 @@ fib_entry_src_action_reactivate (fib_entry_t *fib_entry, fib_path_list_unlock(path_list_index); } fib_entry_src_action_install(fib_entry, source); + fib_entry_src_action_fwd_update(fib_entry, source); } void -fib_entry_src_action_installed (fib_entry_t *fib_entry, +fib_entry_src_action_installed (const fib_entry_t *fib_entry, fib_source_t source) { fib_entry_src_t *esrc; @@ -919,6 +829,8 @@ fib_entry_src_action_installed (fib_entry_t *fib_entry, fib_entry_src_vft[source].fesv_installed(esrc, fib_entry); } + + fib_entry_src_action_fwd_update(fib_entry, source); } /* @@ -938,7 +850,7 @@ fib_entry_src_action_add (fib_entry_t *fib_entry, fib_node_index_t fib_entry_index; fib_entry_src_t *esrc; - esrc = fib_entry_src_find_or_create(fib_entry, source); + esrc = fib_entry_src_find_or_create(fib_entry, source, NULL); esrc->fes_ref_count++; @@ -997,7 +909,7 @@ fib_entry_src_action_update (fib_entry_t *fib_entry, fib_node_index_t fib_entry_index, old_path_list_index; fib_entry_src_t *esrc; - esrc = fib_entry_src_find_or_create(fib_entry, source); + esrc = fib_entry_src_find_or_create(fib_entry, source, NULL); if (NULL == esrc) return (fib_entry_src_action_add(fib_entry, source, flags, dpo)); @@ -1457,6 +1369,29 @@ fib_entry_get_flags_for_source (fib_node_index_t entry_index, return (FIB_ENTRY_FLAG_NONE); } +fib_entry_flag_t +fib_entry_get_flags_i (const fib_entry_t *fib_entry) +{ + fib_entry_flag_t flags; + + /* + * the vector of sources is deliberately arranged in priority order + */ + if (0 == vec_len(fib_entry->fe_srcs)) + { + flags = FIB_ENTRY_FLAG_NONE; + } + else + { + fib_entry_src_t *esrc; + + esrc = vec_elt_at_index(fib_entry->fe_srcs, 0); + flags = esrc->fes_entry_flags; + } + + return (flags); +} + void fib_entry_set_source_data (fib_node_index_t fib_entry_index, fib_source_t source, diff --git a/src/vnet/fib/fib_entry_src.h b/src/vnet/fib/fib_entry_src.h index a19fae10a1c..35c43936a1f 100644 --- a/src/vnet/fib/fib_entry_src.h +++ b/src/vnet/fib/fib_entry_src.h @@ -104,6 +104,15 @@ typedef fib_entry_src_cover_res_t (*fib_entry_src_cover_update_t)( fib_entry_src_t *src, const fib_entry_t *fib_entry); +/** + * Forwarding updated. Notification that the forwarding information for the + * entry has been updated. This notification is sent to all sources, not just + * the active best. + */ +typedef void (*fib_entry_src_fwd_update_t)(fib_entry_src_t *src, + const fib_entry_t *fib_entry, + fib_source_t best_source); + /** * Installed. Notification that the source is now installed as * the entry's forwarding source. @@ -173,56 +182,22 @@ typedef struct fib_entry_src_vft_t_ { fib_entry_src_cover_update_t fesv_cover_update; fib_entry_src_format_t fesv_format; fib_entry_src_installed_t fesv_installed; + fib_entry_src_fwd_update_t fesv_fwd_update; fib_entry_src_get_data_t fesv_get_data; fib_entry_src_set_data_t fesv_set_data; } fib_entry_src_vft_t; -#define FOR_EACH_SRC_ADDED(_entry, _src, _source, action) \ -{ \ - if (fib_entry_has_multiple_srcs(_entry)) \ - { \ - vec_foreach(_src, _entry->fe_u_src.fe_srcs) \ - { \ - if (_src->fes_flags & FIB_ENTRY_SRC_FLAG_ADDED) { \ - _source = _src->fes_src; \ - do { \ - action; \ - } while(0); \ - } \ - } \ - } \ - else \ - { \ - _src = &_entry->fe_u_src.fe_src; \ - if (_src->fes_flags & FIB_ENTRY_SRC_FLAG_ADDED) { \ - _source = _src->fes_src; \ - do { \ - action; \ - } while(0); \ - } \ - } \ -} - -#define FOR_EACH_SRC(_entry, _src, _source, action) \ -{ \ - if (fib_entry_has_multiple_srcs(_entry)) \ - { \ - vec_foreach(_src, _entry->fe_u_src.fe_srcs) \ - { \ - _source = _src->fes_src; \ - do { \ - action; \ - } while(0); \ - } \ - } \ - else \ - { \ - _src = &_entry->fe_u_src.fe_src; \ - _source = _src->fes_src; \ - do { \ - action; \ - } while(0); \ - } \ +#define FOR_EACH_SRC_ADDED(_entry, _src, _source, action) \ +{ \ + vec_foreach(_src, _entry->fe_srcs) \ + { \ + if (_src->fes_flags & FIB_ENTRY_SRC_FLAG_ADDED) { \ + _source = _src->fes_src; \ + do { \ + action; \ + } while(0); \ + } \ + } \ } extern u8* fib_entry_src_format(fib_entry_t *entry, @@ -285,7 +260,7 @@ extern fib_entry_src_flag_t fib_entry_src_action_path_remove(fib_entry_t *fib_en fib_source_t source, const fib_route_path_t *path); -extern void fib_entry_src_action_installed(fib_entry_t *fib_entry, +extern void fib_entry_src_action_installed(const fib_entry_t *fib_entry, fib_source_t source); extern fib_forward_chain_type_t fib_entry_get_default_chain_type( @@ -304,7 +279,6 @@ extern void fib_entry_src_mk_lb (fib_entry_t *fib_entry, extern fib_protocol_t fib_entry_get_proto(const fib_entry_t * fib_entry); extern dpo_proto_t fib_entry_get_dpo_proto(const fib_entry_t * fib_entry); -extern u32 fib_entry_has_multiple_srcs(const fib_entry_t * fib_entry); /* * Per-source registration. declared here so we save a separate .h file for each diff --git a/src/vnet/fib/fib_entry_src_mpls.c b/src/vnet/fib/fib_entry_src_mpls.c index f95ca657705..f80d42afbb0 100644 --- a/src/vnet/fib/fib_entry_src_mpls.c +++ b/src/vnet/fib/fib_entry_src_mpls.c @@ -181,6 +181,13 @@ const static fib_entry_src_vft_t mpls_src_vft = { .fesv_format = fib_entry_src_mpls_format, .fesv_set_data = fib_entry_src_mpls_set_data, .fesv_get_data = fib_entry_src_mpls_get_data, + /* + * .fesv_fwd_update = fib_entry_src_mpls_fwd_update, + * When the forwarding for the IP entry is updated, any MPLS chains + * it has created are also updated. Since the MPLS entry will have already + * installed that chain/load-balance there is no need to update the netry + * FIXME: later: propagate any walk to the children of the MPLS entry. for SR + */ }; void -- 2.16.6