From 3571a6a226768c3fa125219898dd2c07291599c8 Mon Sep 17 00:00:00 2001 From: Donald Sharp Date: Wed, 26 Dec 2018 13:21:10 -0500 Subject: [PATCH] bgpd: Add a hash for quick lookup in community_list_lookup The community_list_lookup function in a situation where you have a large number of communities and route-maps that reference them becomes a very expensive operation( effectively a linked list walk per route per route-map you apply per peer that has a routemap that refereces a community, ecommunity or lcommunity. This is a very expensive operation. In my testbed, I have a full bgp feed that feeds into 14 namespace view based bgp processes and finally those 14 feed into a final namespace FRR instance that has route-maps applied to each incoming peer for in and out: ! router bgp 65033 bgp bestpath as-path multipath-relax neighbor 192.168.41.1 remote-as external neighbor 192.168.42.2 remote-as external neighbor 192.168.43.3 remote-as external neighbor 192.168.44.4 remote-as external neighbor 192.168.45.5 remote-as external neighbor 192.168.46.6 remote-as external neighbor 192.168.47.7 remote-as external neighbor 192.168.48.8 remote-as external neighbor 192.168.49.9 remote-as external neighbor 192.168.50.10 remote-as external neighbor 192.168.51.11 remote-as external neighbor 192.168.52.12 remote-as external neighbor 192.168.53.13 remote-as external neighbor 192.168.54.14 remote-as external ! address-family ipv4 unicast neighbor 192.168.42.2 prefix-list two-in in neighbor 192.168.42.2 route-map two-in in neighbor 192.168.42.2 route-map two-out out neighbor 192.168.43.3 prefix-list three-in in neighbor 192.168.43.3 route-map three-in in neighbor 192.168.43.3 route-map three-out out neighbor 192.168.44.4 prefix-list four-in in neighbor 192.168.44.4 route-map four-in in neighbor 192.168.44.4 route-map four-out out neighbor 192.168.45.5 prefix-list five-in in neighbor 192.168.45.5 route-map five-in in neighbor 192.168.45.5 route-map five-out out neighbor 192.168.46.6 prefix-list six-in in neighbor 192.168.46.6 route-map six-in in neighbor 192.168.46.6 route-map six-out out neighbor 192.168.47.7 prefix-list seven-in in neighbor 192.168.47.7 route-map seven-in in neighbor 192.168.47.7 route-map seven-out out neighbor 192.168.48.8 prefix-list eight-in in neighbor 192.168.48.8 route-map eight-in in neighbor 192.168.48.8 route-map eight-out out neighbor 192.168.49.9 prefix-list nine-in in neighbor 192.168.49.9 route-map nine-in in neighbor 192.168.49.9 route-map nine-out out neighbor 192.168.50.10 prefix-list ten-in in neighbor 192.168.50.10 route-map ten-in in neighbor 192.168.50.10 route-map ten-out out neighbor 192.168.51.11 prefix-list eleven-in in neighbor 192.168.51.11 route-map eleven-in in neighbor 192.168.51.11 route-map eleven-out out neighbor 192.168.52.12 prefix-list twelve-in in neighbor 192.168.52.12 route-map twelve-in in neighbor 192.168.52.12 route-map twelve-out out neighbor 192.168.53.13 prefix-list thirteen-in in neighbor 192.168.53.13 route-map thirteen-in in neighbor 192.168.53.13 route-map thirteen-out out neighbor 192.168.54.14 prefix-list fourteen-in in neighbor 192.168.54.14 route-map fourteen-in in neighbor 192.168.54.14 route-map fourteen-out out exit-address-family ! This configuration on my machine before this change takes about 2:45 to converge and bgp takes: Total thread statistics 16 151715.050 493440 307 3464919 335 7376696 RWTEX TOTAL CPU time as reported by 'show thread cpu'. After this change BGP takes 58 seconds to converge and uses: Total thread statistics ------------------------- 16 42954.284 350319 122 295743 157 1194820 RWTEX TOTAL almost 43 seconds of CPU time. Signed-off-by: Donald Sharp --- bgpd/bgp_clist.c | 92 +++++++++++++++++++++++++++++++++++------------- bgpd/bgp_clist.h | 1 + 2 files changed, 69 insertions(+), 24 deletions(-) diff --git a/bgpd/bgp_clist.c b/bgpd/bgp_clist.c index c4a20ca233..25652b80fe 100644 --- a/bgpd/bgp_clist.c +++ b/bgpd/bgp_clist.c @@ -26,6 +26,7 @@ #include "queue.h" #include "filter.h" #include "stream.h" +#include "jhash.h" #include "bgpd/bgpd.h" #include "bgpd/bgp_community.h" @@ -35,6 +36,24 @@ #include "bgpd/bgp_regex.h" #include "bgpd/bgp_clist.h" +static uint32_t bgp_clist_hash_key_community_list(void *data) +{ + struct community_list *cl = data; + + return jhash(cl->name, sizeof(cl->name), 0xdeadbeaf); +} + +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 (strcmp(cl1->name, cl2->name) == 0) + return true; + + return false; +} + /* Lookup master structure for community-list or extcommunity-list. */ struct community_list_master * @@ -126,6 +145,9 @@ community_list_insert(struct community_list_handler *ch, const char *name, new = community_list_new(); new->name = XSTRDUP(MTYPE_COMMUNITY_LIST_NAME, name); + /* Save for later */ + hash_get(cm->hash, new, hash_alloc_intern); + /* If name is made by all digit character. We treat it as number. */ for (number = 0, i = 0; i < strlen(name); i++) { @@ -196,7 +218,7 @@ 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) { - struct community_list *list; + struct community_list lookup; struct community_list_master *cm; if (!name) @@ -206,14 +228,8 @@ struct community_list *community_list_lookup(struct community_list_handler *ch, if (!cm) return NULL; - for (list = cm->num.head; list; list = list->next) - if (strcmp(list->name, name) == 0) - return list; - for (list = cm->str.head; list; list = list->next) - if (strcmp(list->name, name) == 0) - return list; - - return NULL; + lookup.name = (char *)name; + return hash_get(cm->hash, &lookup, NULL); } static struct community_list * @@ -228,7 +244,8 @@ community_list_get(struct community_list_handler *ch, const char *name, return list; } -static void community_list_delete(struct community_list *list) +static void community_list_delete(struct community_list_master *cm, + struct community_list *list) { struct community_list_list *clist; struct community_entry *entry, *next; @@ -250,6 +267,7 @@ static void community_list_delete(struct community_list *list) else clist->head = list->next; + hash_release(cm->hash, list); community_list_free(list); } @@ -273,7 +291,8 @@ static void community_list_entry_add(struct community_list *list, } /* Delete community-list entry from the list. */ -static void community_list_entry_delete(struct community_list *list, +static void community_list_entry_delete(struct community_list_master *cm, + struct community_list *list, struct community_entry *entry) { if (entry->next) @@ -289,7 +308,7 @@ static void community_list_entry_delete(struct community_list *list, community_entry_free(entry); if (community_list_empty_p(list)) - community_list_delete(list); + community_list_delete(cm, list); } /* Lookup community-list entry from the list. */ @@ -882,6 +901,7 @@ int community_list_set(struct community_list_handler *ch, const char *name, int community_list_unset(struct community_list_handler *ch, const char *name, const char *str, int direct, int style) { + struct community_list_master *cm = NULL; struct community_entry *entry = NULL; struct community_list *list; struct community *com = NULL; @@ -891,9 +911,10 @@ int community_list_unset(struct community_list_handler *ch, const char *name, if (list == NULL) return COMMUNITY_LIST_ERR_CANT_FIND_LIST; + cm = community_list_master_lookup(ch, COMMUNITY_LIST_MASTER); /* Delete all of entry belongs to this community-list. */ if (!str) { - community_list_delete(list); + community_list_delete(cm, list); route_map_notify_dependencies(name, RMAP_EVENT_CLIST_DELETED); return 0; } @@ -910,7 +931,7 @@ int community_list_unset(struct community_list_handler *ch, const char *name, if (!entry) return COMMUNITY_LIST_ERR_CANT_FIND_LIST; - community_list_entry_delete(list, entry); + community_list_entry_delete(cm, list, entry); route_map_notify_dependencies(name, RMAP_EVENT_CLIST_DELETED); return 0; @@ -1031,6 +1052,7 @@ int lcommunity_list_set(struct community_list_handler *ch, const char *name, int lcommunity_list_unset(struct community_list_handler *ch, const char *name, const char *str, int direct, int style) { + struct community_list_master *cm = NULL; struct community_entry *entry = NULL; struct community_list *list; struct lcommunity *lcom = NULL; @@ -1041,9 +1063,10 @@ int lcommunity_list_unset(struct community_list_handler *ch, const char *name, if (list == NULL) return COMMUNITY_LIST_ERR_CANT_FIND_LIST; + cm = community_list_master_lookup(ch, LARGE_COMMUNITY_LIST_MASTER); /* Delete all of entry belongs to this community-list. */ if (!str) { - community_list_delete(list); + community_list_delete(cm, list); return 0; } @@ -1068,7 +1091,7 @@ int lcommunity_list_unset(struct community_list_handler *ch, const char *name, if (!entry) return COMMUNITY_LIST_ERR_CANT_FIND_LIST; - community_list_entry_delete(list, entry); + community_list_entry_delete(cm, list, entry); return 0; } @@ -1147,6 +1170,7 @@ int extcommunity_list_set(struct community_list_handler *ch, const char *name, int extcommunity_list_unset(struct community_list_handler *ch, const char *name, const char *str, int direct, int style) { + struct community_list_master *cm = NULL; struct community_entry *entry = NULL; struct community_list *list; struct ecommunity *ecom = NULL; @@ -1156,9 +1180,10 @@ int extcommunity_list_unset(struct community_list_handler *ch, const char *name, if (list == NULL) return COMMUNITY_LIST_ERR_CANT_FIND_LIST; + cm = community_list_master_lookup(ch, EXTCOMMUNITY_LIST_MASTER); /* Delete all of entry belongs to this extcommunity-list. */ if (!str) { - community_list_delete(list); + community_list_delete(cm, list); route_map_notify_dependencies(name, RMAP_EVENT_ECLIST_DELETED); return 0; } @@ -1175,7 +1200,7 @@ int extcommunity_list_unset(struct community_list_handler *ch, const char *name, if (!entry) return COMMUNITY_LIST_ERR_CANT_FIND_LIST; - community_list_entry_delete(list, entry); + community_list_entry_delete(cm, list, entry); route_map_notify_dependencies(name, RMAP_EVENT_ECLIST_DELETED); return 0; @@ -1187,6 +1212,22 @@ struct community_list_handler *community_list_init(void) struct community_list_handler *ch; ch = XCALLOC(MTYPE_COMMUNITY_LIST_HANDLER, sizeof(struct community_list_handler)); + + ch->community_list.hash = + hash_create_size(4, bgp_clist_hash_key_community_list, + bgp_clist_hash_cmp_community_list, + "Community List Number Quick Lookup"); + + ch->extcommunity_list.hash = + hash_create_size(4, bgp_clist_hash_key_community_list, + bgp_clist_hash_cmp_community_list, + "Extended Community List Quick Lookup"); + + ch->lcommunity_list.hash = + hash_create_size(4, bgp_clist_hash_key_community_list, + bgp_clist_hash_cmp_community_list, + "Large Community List Quick Lookup"); + return ch; } @@ -1198,21 +1239,24 @@ void community_list_terminate(struct community_list_handler *ch) cm = &ch->community_list; while ((list = cm->num.head) != NULL) - community_list_delete(list); + community_list_delete(cm, list); while ((list = cm->str.head) != NULL) - community_list_delete(list); + community_list_delete(cm, list); + hash_free(cm->hash); cm = &ch->lcommunity_list; while ((list = cm->num.head) != NULL) - community_list_delete(list); + community_list_delete(cm, list); while ((list = cm->str.head) != NULL) - community_list_delete(list); + community_list_delete(cm, list); + hash_free(cm->hash); cm = &ch->extcommunity_list; while ((list = cm->num.head) != NULL) - community_list_delete(list); + community_list_delete(cm, list); while ((list = cm->str.head) != NULL) - community_list_delete(list); + community_list_delete(cm, list); + hash_free(cm->hash); XFREE(MTYPE_COMMUNITY_LIST_HANDLER, ch); } diff --git a/bgpd/bgp_clist.h b/bgpd/bgp_clist.h index 9efb34d7b9..6edf4389bb 100644 --- a/bgpd/bgp_clist.h +++ b/bgpd/bgp_clist.h @@ -100,6 +100,7 @@ struct community_list_list { struct community_list_master { struct community_list_list num; struct community_list_list str; + struct hash *hash; }; /* Community-list handler. community_list_init() returns this -- 2.39.5