From e237b0d211770d2e71c0a3ff73b4842f17df9019 Mon Sep 17 00:00:00 2001 From: Donald Sharp Date: Tue, 8 Jan 2019 20:23:11 -0500 Subject: [PATCH] bgpd: Further refine hash lookup to store hash value Further refine the previous commit to store the hash value in both the `struct community_list` as well as the `struct rmap_community` structures. This allows us to know a priori what our hash value is. This change cuts another couple of seconds of convergence off to ~55 seconds and further reduces cpu load of bgp: 16 40061.706 433732 92 330102 129 1242965 RWTEX TOTAL Down from ~43 seconds previously. Signed-off-by: Donald Sharp --- bgpd/bgp_clist.c | 23 +++++++++++++++++------ bgpd/bgp_clist.h | 14 +++++++++++++- bgpd/bgp_route.c | 4 ++-- bgpd/bgp_routemap.c | 13 +++++++++++++ bgpd/bgp_vty.c | 6 +++--- 5 files changed, 48 insertions(+), 12 deletions(-) diff --git a/bgpd/bgp_clist.c b/bgpd/bgp_clist.c index 25652b80fe..84a00488c1 100644 --- a/bgpd/bgp_clist.c +++ b/bgpd/bgp_clist.c @@ -40,7 +40,11 @@ static uint32_t bgp_clist_hash_key_community_list(void *data) { struct community_list *cl = data; - return jhash(cl->name, sizeof(cl->name), 0xdeadbeaf); + if (cl->name_hash) + return cl->name_hash; + + cl->name_hash = bgp_clist_hash_key(cl->name); + return cl->name_hash; } static bool bgp_clist_hash_cmp_community_list(const void *a1, const void *a2) @@ -48,6 +52,9 @@ static bool bgp_clist_hash_cmp_community_list(const void *a1, const void *a2) const struct community_list *cl1 = a1; const struct community_list *cl2 = a2; + if (cl1->name_hash != cl2->name_hash) + return false; + if (strcmp(cl1->name, cl2->name) == 0) return true; @@ -144,6 +151,7 @@ community_list_insert(struct community_list_handler *ch, const char *name, /* Allocate new community_list and copy given name. */ new = community_list_new(); new->name = XSTRDUP(MTYPE_COMMUNITY_LIST_NAME, name); + new->name_hash = bgp_clist_hash_key_community_list(new); /* Save for later */ hash_get(cm->hash, new, hash_alloc_intern); @@ -216,7 +224,9 @@ community_list_insert(struct community_list_handler *ch, const char *name, } struct community_list *community_list_lookup(struct community_list_handler *ch, - const char *name, int master) + const char *name, + uint32_t name_hash, + int master) { struct community_list lookup; struct community_list_master *cm; @@ -229,6 +239,7 @@ struct community_list *community_list_lookup(struct community_list_handler *ch, return NULL; lookup.name = (char *)name; + lookup.name_hash = name_hash; return hash_get(cm->hash, &lookup, NULL); } @@ -238,7 +249,7 @@ community_list_get(struct community_list_handler *ch, const char *name, { struct community_list *list; - list = community_list_lookup(ch, name, master); + list = community_list_lookup(ch, name, 0, master); if (!list) list = community_list_insert(ch, name, master); return list; @@ -907,7 +918,7 @@ int community_list_unset(struct community_list_handler *ch, const char *name, struct community *com = NULL; /* Lookup community list. */ - list = community_list_lookup(ch, name, COMMUNITY_LIST_MASTER); + list = community_list_lookup(ch, name, 0, COMMUNITY_LIST_MASTER); if (list == NULL) return COMMUNITY_LIST_ERR_CANT_FIND_LIST; @@ -1059,7 +1070,7 @@ int lcommunity_list_unset(struct community_list_handler *ch, const char *name, regex_t *regex = NULL; /* Lookup community list. */ - list = community_list_lookup(ch, name, LARGE_COMMUNITY_LIST_MASTER); + list = community_list_lookup(ch, name, 0, LARGE_COMMUNITY_LIST_MASTER); if (list == NULL) return COMMUNITY_LIST_ERR_CANT_FIND_LIST; @@ -1176,7 +1187,7 @@ int extcommunity_list_unset(struct community_list_handler *ch, const char *name, struct ecommunity *ecom = NULL; /* Lookup extcommunity list. */ - list = community_list_lookup(ch, name, EXTCOMMUNITY_LIST_MASTER); + list = community_list_lookup(ch, name, 0, EXTCOMMUNITY_LIST_MASTER); if (list == NULL) return COMMUNITY_LIST_ERR_CANT_FIND_LIST; diff --git a/bgpd/bgp_clist.h b/bgpd/bgp_clist.h index 6edf4389bb..9cf8a14a6a 100644 --- a/bgpd/bgp_clist.h +++ b/bgpd/bgp_clist.h @@ -21,6 +21,8 @@ #ifndef _QUAGGA_BGP_CLIST_H #define _QUAGGA_BGP_CLIST_H +#include "jhash.h" + /* Master Community-list. */ #define COMMUNITY_LIST_MASTER 0 #define EXTCOMMUNITY_LIST_MASTER 1 @@ -47,6 +49,9 @@ struct community_list { /* Name of the community-list. */ char *name; + /* Stored hash value of name, to further speed up hash operations */ + uint32_t name_hash; + /* String or number. */ int sort; @@ -152,7 +157,8 @@ extern struct community_list_master * community_list_master_lookup(struct community_list_handler *, int); extern struct community_list * -community_list_lookup(struct community_list_handler *, const char *, int); +community_list_lookup(struct community_list_handler *c, const char *name, + uint32_t name_hash, int master); extern int community_list_match(struct community *, struct community_list *); extern int ecommunity_list_match(struct ecommunity *, struct community_list *); @@ -164,4 +170,10 @@ extern struct community *community_list_match_delete(struct community *, extern struct lcommunity * lcommunity_list_match_delete(struct lcommunity *lcom, struct community_list *list); + +static inline uint32_t bgp_clist_hash_key(char *name) +{ + return jhash(name, sizeof(name), 0xdeadbeaf); +} + #endif /* _QUAGGA_BGP_CLIST_H */ diff --git a/bgpd/bgp_route.c b/bgpd/bgp_route.c index 31cd3d1f05..e3d55b4264 100644 --- a/bgpd/bgp_route.c +++ b/bgpd/bgp_route.c @@ -9266,7 +9266,7 @@ static int bgp_show_lcommunity_list(struct vty *vty, struct bgp *bgp, { struct community_list *list; - list = community_list_lookup(bgp_clist, lcom, + list = community_list_lookup(bgp_clist, lcom, 0, LARGE_COMMUNITY_LIST_MASTER); if (list == NULL) { vty_out(vty, "%% %s is not a valid large-community-list name\n", @@ -9787,7 +9787,7 @@ static int bgp_show_community_list(struct vty *vty, struct bgp *bgp, { struct community_list *list; - list = community_list_lookup(bgp_clist, com, COMMUNITY_LIST_MASTER); + list = community_list_lookup(bgp_clist, com, 0, COMMUNITY_LIST_MASTER); if (list == NULL) { vty_out(vty, "%% %s is not a valid community-list name\n", com); return CMD_WARNING; diff --git a/bgpd/bgp_routemap.c b/bgpd/bgp_routemap.c index b236fc7eed..d7ee2aa19f 100644 --- a/bgpd/bgp_routemap.c +++ b/bgpd/bgp_routemap.c @@ -1037,6 +1037,7 @@ struct route_map_rule_cmd route_match_aspath_cmd = { /* `match community COMMUNIY' */ struct rmap_community { char *name; + uint32_t name_hash; int exact; }; @@ -1055,6 +1056,7 @@ static route_map_result_t route_match_community(void *rule, rcom = rule; list = community_list_lookup(bgp_clist, rcom->name, + rcom->name_hash, COMMUNITY_LIST_MASTER); if (!list) return RMAP_NOMATCH; @@ -1090,6 +1092,8 @@ static void *route_match_community_compile(const char *arg) rcom->name = XSTRDUP(MTYPE_ROUTE_MAP_COMPILED, arg); rcom->exact = 0; } + + rcom->name_hash = bgp_clist_hash_key(rcom->name); return rcom; } @@ -1121,6 +1125,7 @@ static route_map_result_t route_match_lcommunity(void *rule, path = object; list = community_list_lookup(bgp_clist, rcom->name, + rcom->name_hash, LARGE_COMMUNITY_LIST_MASTER); if (!list) return RMAP_NOMATCH; @@ -1149,6 +1154,8 @@ static void *route_match_lcommunity_compile(const char *arg) rcom->name = XSTRDUP(MTYPE_ROUTE_MAP_COMPILED, arg); rcom->exact = 0; } + + rcom->name_hash = bgp_clist_hash_key(rcom->name); return rcom; } @@ -1181,6 +1188,7 @@ static route_map_result_t route_match_ecommunity(void *rule, path = object; list = community_list_lookup(bgp_clist, rcom->name, + rcom->name_hash, EXTCOMMUNITY_LIST_MASTER); if (!list) return RMAP_NOMATCH; @@ -1198,6 +1206,7 @@ static void *route_match_ecommunity_compile(const char *arg) rcom = XCALLOC(MTYPE_ROUTE_MAP_COMPILED, sizeof(struct rmap_community)); rcom->name = XSTRDUP(MTYPE_ROUTE_MAP_COMPILED, arg); + rcom->name_hash = bgp_clist_hash_key(rcom->name); return rcom; } @@ -1948,6 +1957,7 @@ static route_map_result_t route_set_lcommunity_delete(void *rule, path = object; list = community_list_lookup(bgp_clist, rcom->name, + rcom->name_hash, LARGE_COMMUNITY_LIST_MASTER); old = path->attr->lcommunity; @@ -2000,6 +2010,7 @@ static void *route_set_lcommunity_delete_compile(const char *arg) str = NULL; rcom->name = str; + rcom->name_hash = bgp_clist_hash_key(rcom->name); return rcom; } @@ -2041,6 +2052,7 @@ static route_map_result_t route_set_community_delete( path = object; list = community_list_lookup(bgp_clist, rcom->name, + rcom->name_hash, COMMUNITY_LIST_MASTER); old = path->attr->community; @@ -2093,6 +2105,7 @@ static void *route_set_community_delete_compile(const char *arg) str = NULL; rcom->name = str; + rcom->name_hash = bgp_clist_hash_key(rcom->name); return rcom; } diff --git a/bgpd/bgp_vty.c b/bgpd/bgp_vty.c index 2a4421aa54..7bf62f2843 100644 --- a/bgpd/bgp_vty.c +++ b/bgpd/bgp_vty.c @@ -14309,7 +14309,7 @@ DEFUN (show_community_list_arg, vty_out(vty, "'show bgp community-list <(1-500)|WORD>'\n"); zlog_warn("Deprecated option: 'ip show community-list <(1-500)|WORD>' being used"); } - list = community_list_lookup(bgp_clist, argv[idx_comm_list]->arg, + list = community_list_lookup(bgp_clist, argv[idx_comm_list]->arg, 0, COMMUNITY_LIST_MASTER); if (!list) { vty_out(vty, "%% Can't find community-list\n"); @@ -14834,7 +14834,7 @@ DEFUN (show_lcommunity_list_arg, zlog_warn("Deprecated option: 'ip show large-community-list <(1-500)|WORD>' being used"); } - list = community_list_lookup(bgp_clist, argv[3]->arg, + list = community_list_lookup(bgp_clist, argv[3]->arg, 0, LARGE_COMMUNITY_LIST_MASTER); if (!list) { vty_out(vty, "%% Can't find extcommunity-list\n"); @@ -15235,7 +15235,7 @@ DEFUN (show_extcommunity_list_arg, vty_out(vty, "'show bgp extcommunity-list <(1-500)|WORD>'\n"); zlog_warn("Deprecated option: 'ip show extcommunity-list <(1-500)|WORD>' being used"); } - list = community_list_lookup(bgp_clist, argv[idx_comm_list]->arg, + list = community_list_lookup(bgp_clist, argv[idx_comm_list]->arg, 0, EXTCOMMUNITY_LIST_MASTER); if (!list) { vty_out(vty, "%% Can't find extcommunity-list\n"); -- 2.39.5