diff options
Diffstat (limited to 'src/vnet/fib')
| -rw-r--r-- | src/vnet/fib/fib_entry.c | 67 | ||||
| -rw-r--r-- | src/vnet/fib/fib_entry.h | 44 | ||||
| -rw-r--r-- | src/vnet/fib/fib_entry_src.c | 197 | ||||
| -rw-r--r-- | src/vnet/fib/fib_entry_src.h | 70 | ||||
| -rw-r--r-- | src/vnet/fib/fib_entry_src_mpls.c | 7 |
5 files changed, 264 insertions, 121 deletions
diff --git a/src/vnet/fib/fib_entry.c b/src/vnet/fib/fib_entry.c index 35716cacc29..a9ca0f20f6d 100644 --- a/src/vnet/fib/fib_entry.c +++ b/src/vnet/fib/fib_entry.c @@ -213,29 +213,33 @@ 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); - vec_free(fib_entry->fe_srcs); + if (fib_entry_has_multiple_srcs(fib_entry)) + { + vec_free(fib_entry->fe_u_src.fe_srcs); + } pool_put(fib_entry_pool, fib_entry); } -static fib_entry_src_t* +static const fib_entry_src_t* fib_entry_get_best_src_i (const fib_entry_t *fib_entry) { - fib_entry_src_t *bsrc; + const fib_entry_src_t *bsrc; /* * the enum of sources is deliberately arranged in priority order */ - if (0 == vec_len(fib_entry->fe_srcs)) + if (fib_entry_has_multiple_srcs(fib_entry)) { - bsrc = NULL; + ASSERT(vec_len(fib_entry->fe_u_src.fe_srcs)); + + bsrc = vec_elt_at_index(fib_entry->fe_u_src.fe_srcs, 0); } else { - bsrc = vec_elt_at_index(fib_entry->fe_srcs, 0); + bsrc = &fib_entry->fe_u_src.fe_src; } return (bsrc); @@ -248,7 +252,7 @@ fib_entry_src_get_source (const fib_entry_src_t *esrc) { return (esrc->fes_src); } - return (FIB_SOURCE_MAX); + return (FIB_SOURCE_INVALID); } static fib_entry_flag_t @@ -262,6 +266,18 @@ fib_entry_src_get_flags (const fib_entry_src_t *esrc) } 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) { return (fib_entry_get_flags_i(fib_entry_get(fib_entry_index))); @@ -330,11 +346,18 @@ fib_entry_show_memory (void) pool_foreach(entry, fib_entry_pool, ({ - n_srcs += vec_len(entry->fe_srcs); - vec_foreach(esrc, entry->fe_srcs) - { - n_exts += fib_path_ext_list_length(&esrc->fes_path_exts); - } + 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); + } })); fib_show_memory_usage("Entry Source", @@ -795,10 +818,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); @@ -816,10 +839,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); @@ -838,10 +861,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)); @@ -900,11 +923,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)); @@ -951,7 +974,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_MAX == best_source) { + if (FIB_SOURCE_INVALID == best_source) { /* * no more sources left. this entry is toast. */ @@ -996,11 +1019,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); @@ -1041,7 +1064,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_MAX == best_source) { + if (FIB_SOURCE_INVALID == best_source) { /* * no more sources left. this entry is toast. */ @@ -1098,10 +1121,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); @@ -1361,8 +1384,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 cd2a685b765..cd954e3a15c 100644 --- a/src/vnet/fib/fib_entry.h +++ b/src/vnet/fib/fib_entry.h @@ -29,6 +29,10 @@ */ typedef enum fib_source_t_ { /** + * An invalid source of value 0 + */ + FIB_SOURCE_INVALID, + /** * Marker. Add new values after this one. */ FIB_SOURCE_FIRST, @@ -142,6 +146,7 @@ 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", \ @@ -377,6 +382,29 @@ 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. * * This entry represents a route added to the FIB that is stored @@ -409,12 +437,20 @@ typedef struct fib_entry_t_ { * type to derive the EOS bit value. */ dpo_id_t fe_lb; + /** - * 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. + * 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 */ - fib_entry_src_t *fe_srcs; + union { + fib_entry_src_t *fe_srcs; + fib_entry_src_t fe_src; + } fe_u_src; + /** * 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 214dafe9b8d..acb8579e85e 100644 --- a/src/vnet/fib/fib_entry_src.c +++ b/src/vnet/fib/fib_entry_src.c @@ -61,13 +61,62 @@ fib_entry_src_action_init (fib_entry_t *fib_entry, fib_entry_src_vft[source].fesv_init(&esrc); } - vec_add1(fib_entry->fe_srcs, esrc); - vec_sort_with_function(fib_entry->fe_srcs, - fib_entry_src_cmp_for_sort); + 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); } static fib_entry_src_t * -fib_entry_src_find (const fib_entry_t *fib_entry, +fib_entry_src_find (fib_entry_t *fib_entry, fib_source_t source, u32 *index) @@ -76,20 +125,80 @@ fib_entry_src_find (const fib_entry_t *fib_entry, int ii; ii = 0; - vec_foreach(esrc, fib_entry->fe_srcs) + if (fib_entry_has_multiple_srcs(fib_entry)) { - if (esrc->fes_src == source) - { - if (NULL != index) - { - *index = ii; - } - return (esrc); - } - else - { - ii++; - } + 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_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); + } } return (NULL); @@ -108,8 +217,7 @@ 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, - u32 *index) + fib_source_t source) { fib_entry_src_t *esrc; @@ -141,7 +249,7 @@ fib_entry_src_action_deinit (fib_entry_t *fib_entry, } fib_path_ext_list_flush(&esrc->fes_path_exts); - vec_del1(fib_entry->fe_srcs, index); + fib_entry_src_delete(fib_entry, index); } fib_entry_src_cover_res_t @@ -744,23 +852,6 @@ 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) @@ -813,11 +904,10 @@ 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 (const fib_entry_t *fib_entry, +fib_entry_src_action_installed (fib_entry_t *fib_entry, fib_source_t source) { fib_entry_src_t *esrc; @@ -829,8 +919,6 @@ fib_entry_src_action_installed (const fib_entry_t *fib_entry, fib_entry_src_vft[source].fesv_installed(esrc, fib_entry); } - - fib_entry_src_action_fwd_update(fib_entry, source); } /* @@ -850,7 +938,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, NULL); + esrc = fib_entry_src_find_or_create(fib_entry, source); esrc->fes_ref_count++; @@ -909,7 +997,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, NULL); + esrc = fib_entry_src_find_or_create(fib_entry, source); if (NULL == esrc) return (fib_entry_src_action_add(fib_entry, source, flags, dpo)); @@ -1369,29 +1457,6 @@ 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 35c43936a1f..a19fae10a1c 100644 --- a/src/vnet/fib/fib_entry_src.h +++ b/src/vnet/fib/fib_entry_src.h @@ -105,15 +105,6 @@ typedef fib_entry_src_cover_res_t (*fib_entry_src_cover_update_t)( 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. */ @@ -182,22 +173,56 @@ 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) \ -{ \ - vec_foreach(_src, _entry->fe_srcs) \ - { \ - if (_src->fes_flags & FIB_ENTRY_SRC_FLAG_ADDED) { \ - _source = _src->fes_src; \ - do { \ - action; \ - } while(0); \ - } \ - } \ +#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); \ + } \ } extern u8* fib_entry_src_format(fib_entry_t *entry, @@ -260,7 +285,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(const fib_entry_t *fib_entry, +extern void fib_entry_src_action_installed(fib_entry_t *fib_entry, fib_source_t source); extern fib_forward_chain_type_t fib_entry_get_default_chain_type( @@ -279,6 +304,7 @@ 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 f80d42afbb0..f95ca657705 100644 --- a/src/vnet/fib/fib_entry_src_mpls.c +++ b/src/vnet/fib/fib_entry_src_mpls.c @@ -181,13 +181,6 @@ 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 |