From f12a83f54ff2239d70494d577af3e1bb253692e1 Mon Sep 17 00:00:00 2001 From: Neale Ranns Date: Tue, 18 Apr 2017 09:09:40 -0700 Subject: Improve Load-Balance MAPs - only build them for popular path-lists (where popular means more than 64 children) the reason to have a map is to improve convergence speed for recursive prefixes - if there are only a few this technique is not needed - only build them when there is at least one path that has recursive constraints, i.e. a path that can 'fail' in a PIC scenario. - Use the MAPS in the switch path. - PIC test cases for functionality (not convergence performance) Change-Id: I70705444c8469d22b07ae34be82cfb6a01358e10 Signed-off-by: Neale Ranns --- src/vnet/fib/fib_path_list.h | 24 +++++++++++++----------- 1 file changed, 13 insertions(+), 11 deletions(-) (limited to 'src/vnet/fib/fib_path_list.h') diff --git a/src/vnet/fib/fib_path_list.h b/src/vnet/fib/fib_path_list.h index 9d2462119fb..376cb726dd6 100644 --- a/src/vnet/fib/fib_path_list.h +++ b/src/vnet/fib/fib_path_list.h @@ -38,11 +38,6 @@ typedef enum fib_path_list_attribute_t_ { * be searched for each route update. */ FIB_PATH_LIST_ATTRIBUTE_SHARED = FIB_PATH_LIST_ATTRIBUTE_FIRST, - /** - * Indexed means the path-list keeps a hash table of all paths for - * fast lookup. The lookup result is the fib_node_index of the path. - */ - FIB_PATH_LIST_ATTRIBUTE_INDEXED, /** * explicit drop path-list. Used when the entry source needs to * force a drop, despite the fact the path info is present. @@ -65,6 +60,12 @@ typedef enum fib_path_list_attribute_t_ { * looped path-list. one path looped implies the whole list is */ FIB_PATH_LIST_ATTRIBUTE_LOOPED, + /** + * a popular path-ist is one that is shared amongst many entries. + * Path list become popular as they gain more children, but they + * don't become unpopular as they lose them. + */ + FIB_PATH_LIST_ATTRIBUTE_POPULAR, /** * no uRPF - do not generate unicast RPF list for this path-list */ @@ -72,30 +73,30 @@ typedef enum fib_path_list_attribute_t_ { /** * Marher. Add new flags before this one, and then update it. */ - FIB_PATH_LIST_ATTRIBUTE_LAST = FIB_PATH_LIST_ATTRIBUTE_LOOPED, + FIB_PATH_LIST_ATTRIBUTE_LAST = FIB_PATH_LIST_ATTRIBUTE_NO_URPF, } fib_path_list_attribute_t; typedef enum fib_path_list_flags_t_ { FIB_PATH_LIST_FLAG_NONE = 0, FIB_PATH_LIST_FLAG_SHARED = (1 << FIB_PATH_LIST_ATTRIBUTE_SHARED), - FIB_PATH_LIST_FLAG_INDEXED = (1 << FIB_PATH_LIST_ATTRIBUTE_INDEXED), FIB_PATH_LIST_FLAG_DROP = (1 << FIB_PATH_LIST_ATTRIBUTE_DROP), FIB_PATH_LIST_FLAG_LOCAL = (1 << FIB_PATH_LIST_ATTRIBUTE_LOCAL), FIB_PATH_LIST_FLAG_EXCLUSIVE = (1 << FIB_PATH_LIST_ATTRIBUTE_EXCLUSIVE), FIB_PATH_LIST_FLAG_RESOLVED = (1 << FIB_PATH_LIST_ATTRIBUTE_RESOLVED), FIB_PATH_LIST_FLAG_LOOPED = (1 << FIB_PATH_LIST_ATTRIBUTE_LOOPED), + FIB_PATH_LIST_FLAG_POPULAR = (1 << FIB_PATH_LIST_ATTRIBUTE_POPULAR), FIB_PATH_LIST_FLAG_NO_URPF = (1 << FIB_PATH_LIST_ATTRIBUTE_NO_URPF), } fib_path_list_flags_t; #define FIB_PATH_LIST_ATTRIBUTES { \ [FIB_PATH_LIST_ATTRIBUTE_SHARED] = "shared", \ - [FIB_PATH_LIST_ATTRIBUTE_INDEXED] = "indexed", \ [FIB_PATH_LIST_ATTRIBUTE_RESOLVED] = "resolved", \ [FIB_PATH_LIST_ATTRIBUTE_DROP] = "drop", \ [FIB_PATH_LIST_ATTRIBUTE_EXCLUSIVE] = "exclusive", \ - [FIB_PATH_LIST_ATTRIBUTE_LOCAL] = "local", \ - [FIB_PATH_LIST_ATTRIBUTE_LOOPED] = "looped", \ - [FIB_PATH_LIST_ATTRIBUTE_NO_URPF] = "no-uRPF", \ + [FIB_PATH_LIST_ATTRIBUTE_LOCAL] = "local", \ + [FIB_PATH_LIST_ATTRIBUTE_LOOPED] = "looped", \ + [FIB_PATH_LIST_ATTRIBUTE_POPULAR] = "popular", \ + [FIB_PATH_LIST_ATTRIBUTE_NO_URPF] = "no-uRPF", \ } #define FOR_EACH_PATH_LIST_ATTRIBUTE(_item) \ @@ -148,6 +149,7 @@ extern int fib_path_list_recursive_loop_detect(fib_node_index_t path_list_index, fib_node_index_t **entry_indicies); extern u32 fib_path_list_get_resolving_interface(fib_node_index_t path_list_index); extern int fib_path_list_is_looped(fib_node_index_t path_list_index); +extern int fib_path_list_is_popular(fib_node_index_t path_list_index); extern fib_protocol_t fib_path_list_get_proto(fib_node_index_t path_list_index); extern u8 * fib_path_list_format(fib_node_index_t pl_index, u8 * s); -- cgit 1.2.3-korg