X-Git-Url: https://gerrit.fd.io/r/gitweb?a=blobdiff_plain;f=src%2Fvnet%2Ffib%2Ffib_path_list.c;h=597a700a448d002bee5c9fa041597cecad1c915c;hb=630b9741659b9a4b68c64ebbeb675761c6f26842;hp=ea6565dd19b156ade4aefc6a7b0db0b3007e594b;hpb=0f26c5a0138ac86d7ebd197c31a09d8d624c35fe;p=vpp.git diff --git a/src/vnet/fib/fib_path_list.c b/src/vnet/fib/fib_path_list.c index ea6565dd19b..597a700a448 100644 --- a/src/vnet/fib/fib_path_list.c +++ b/src/vnet/fib/fib_path_list.c @@ -25,6 +25,16 @@ #include #include +/** + * The magic number of child entries that make a path-list popular. + * There's a trade-off here between convergnece and forwarding speed. + * Popular path-lists generate load-balance maps for the entires that + * use them. If the map is present there is a switch path cost to indirect + * through the map - this indirection provides the fast convergence - so + * without the map convergence is slower. + */ +#define FIB_PATH_LIST_POPULAR 64 + /** * FIB path-list * A representation of the list/set of path trough which a prefix is reachable @@ -106,9 +116,7 @@ fib_path_list_get_node (fib_node_index_t index) static fib_path_list_t* fib_path_list_from_fib_node (fib_node_t *node) { -#if CLIB_DEBUG > 0 ASSERT(FIB_NODE_TYPE_PATH_LIST == node->fn_type); -#endif return ((fib_path_list_t*)node); } @@ -454,14 +462,7 @@ fib_path_list_back_walk (fib_node_index_t path_list_index, /* * propagate the backwalk further */ - if (32 >= fib_node_list_get_size(path_list->fpl_node.fn_children)) - { - /* - * only a few children. continue the walk synchronously - */ - fib_walk_sync(FIB_NODE_TYPE_PATH_LIST, path_list_index, ctx); - } - else + if (path_list->fpl_flags & FIB_PATH_LIST_FLAG_POPULAR) { /* * many children. schedule a async walk @@ -471,6 +472,13 @@ fib_path_list_back_walk (fib_node_index_t path_list_index, FIB_WALK_PRIORITY_LOW, ctx); } + else + { + /* + * only a few children. continue the walk synchronously + */ + fib_walk_sync(FIB_NODE_TYPE_PATH_LIST, path_list_index, ctx); + } } /* @@ -573,6 +581,11 @@ fib_path_list_get_n_paths (fib_node_index_t path_list_index) { fib_path_list_t *path_list; + if (FIB_NODE_INDEX_INVALID == path_list_index) + { + return (0); + } + path_list = fib_path_list_get(path_list_index); return (vec_len(path_list->fpl_paths)); @@ -601,7 +614,7 @@ fib_path_list_get_resolving_interface (fib_node_index_t path_list_index) return (sw_if_index); } -fib_protocol_t +dpo_proto_t fib_path_list_get_proto (fib_node_index_t path_list_index) { fib_path_list_t *path_list; @@ -625,6 +638,16 @@ fib_path_list_is_looped (fib_node_index_t path_list_index) return (path_list->fpl_flags & FIB_PATH_LIST_FLAG_LOOPED); } +int +fib_path_list_is_popular (fib_node_index_t path_list_index) +{ + fib_path_list_t *path_list; + + path_list = fib_path_list_get(path_list_index); + + return (path_list->fpl_flags & FIB_PATH_LIST_FLAG_POPULAR); +} + static fib_path_list_flags_t fib_path_list_flags_fixup (fib_path_list_flags_t flags) { @@ -660,6 +683,16 @@ fib_path_list_create (fib_path_list_flags_t flags, fib_path_create(path_list_index, &rpaths[i])); } + /* + * we sort the paths since the key for the path-list is + * the description of the paths it contains. The paths need to + * be sorted else this description will differ. + */ + if (vec_len(path_list->fpl_paths) > 1) + { + vec_sort_with_function(path_list->fpl_paths, + fib_path_cmp_for_sort); + } } /* @@ -723,7 +756,7 @@ fib_path_list_flags_2_path_flags (fib_path_list_flags_t plf) } fib_node_index_t -fib_path_list_create_special (fib_protocol_t nh_proto, +fib_path_list_create_special (dpo_proto_t nh_proto, fib_path_list_flags_t flags, const dpo_id_t *dpo) { @@ -807,6 +840,7 @@ fib_path_list_path_add (fib_node_index_t path_list_index, */ if (0 == fib_path_cmp(new_path_index, *orig_path_index)) { + fib_path_destroy(new_path_index); return (*orig_path_index); } } @@ -893,21 +927,32 @@ fib_path_list_copy_and_path_add (fib_node_index_t orig_path_list_index, * If we find one then we can return the existing one and destroy the * new one just created. */ - exist_path_list_index = fib_path_list_db_find(path_list); - if (FIB_NODE_INDEX_INVALID != exist_path_list_index) + if (path_list->fpl_flags & FIB_PATH_LIST_FLAG_SHARED) { - fib_path_list_destroy(path_list); + exist_path_list_index = fib_path_list_db_find(path_list); + if (FIB_NODE_INDEX_INVALID != exist_path_list_index) + { + fib_path_list_destroy(path_list); - path_list_index = exist_path_list_index; + path_list_index = exist_path_list_index; + } + else + { + /* + * if there was not a matching path-list, then this + * new one will need inserting into the DB and resolving. + */ + fib_path_list_db_insert(path_list_index); + + path_list = fib_path_list_resolve(path_list); + } } else { /* - * if there was not a matching path-list, then this - * new one will need inserting into the DB and resolving. + * no shared path list requested. resolve and use the one + * just created. */ - fib_path_list_db_insert(path_list_index); - path_list = fib_path_list_resolve(path_list); } @@ -1173,10 +1218,38 @@ fib_path_list_child_add (fib_node_index_t path_list_index, fib_node_type_t child_type, fib_node_index_t child_index) { - return (fib_node_child_add(FIB_NODE_TYPE_PATH_LIST, - path_list_index, - child_type, - child_index)); + u32 sibling; + + sibling = fib_node_child_add(FIB_NODE_TYPE_PATH_LIST, + path_list_index, + child_type, + child_index); + + if (FIB_PATH_LIST_POPULAR == fib_node_get_n_children(FIB_NODE_TYPE_PATH_LIST, + path_list_index)) + { + /* + * Set the popular flag on the path-list once we pass the magic + * threshold. then walk children to update. + * We don't undo this action. The rational being that the number + * of entries using this prefix is large enough such that it is a + * non-trival amount of effort to converge them. If we get into the + * situation where we are adding and removing entries such that we + * flip-flop over the threshold, then this non-trivial work is added + * to each of those routes adds/deletes - not a situation we want. + */ + fib_node_back_walk_ctx_t ctx = { + .fnbw_reason = FIB_NODE_BW_REASON_FLAG_EVALUATE, + }; + fib_path_list_t *path_list; + + path_list = fib_path_list_get(path_list_index); + path_list->fpl_flags |= FIB_PATH_LIST_FLAG_POPULAR; + + fib_walk_sync(FIB_NODE_TYPE_PATH_LIST, path_list_index, &ctx); + } + + return (sibling); } void @@ -1240,7 +1313,9 @@ fib_path_list_walk (fib_node_index_t path_list_index, vec_foreach(path_index, path_list->fpl_paths) { - if (!func(path_list_index, *path_index, ctx)) + if (FIB_PATH_LIST_WALK_STOP == func(path_list_index, + *path_index, + ctx)) break; } }