From a6e0d253a2d0f38146c3551ea1fd93524a53de7e Mon Sep 17 00:00:00 2001 From: Daniel Walton Date: Wed, 28 Oct 2015 19:12:24 +0000 Subject: [PATCH] BGP: route-map scale - use a hash to store the route-maps - reduce the number of route_map_lookup_by_name() calls in BGP Signed-off-by: Daniel Walton Reviewed-by: Donald Sharp Ticket: CM-7407 --- bgpd/bgp_routemap.c | 101 ++++++++++++++++++++++---------------------- lib/routemap.c | 89 +++++++++++++++++++++++++++++++------- 2 files changed, 124 insertions(+), 66 deletions(-) diff --git a/bgpd/bgp_routemap.c b/bgpd/bgp_routemap.c index bf3f8c35f0..a3eb24b3e3 100644 --- a/bgpd/bgp_routemap.c +++ b/bgpd/bgp_routemap.c @@ -2666,8 +2666,9 @@ bgp_route_set_delete (struct vty *vty, struct route_map_index *index, * modifications. */ static void -bgp_route_map_process_peer (const char *rmap_name, struct peer *peer, - int afi, int safi, int route_update) +bgp_route_map_process_peer (const char *rmap_name, struct route_map *map, + struct peer *peer, int afi, int safi, + int route_update) { int update; @@ -2687,8 +2688,7 @@ bgp_route_map_process_peer (const char *rmap_name, struct peer *peer, if (filter->map[RMAP_IN].name && (strcmp(rmap_name, filter->map[RMAP_IN].name) == 0)) { - filter->map[RMAP_IN].map = - route_map_lookup_by_name (filter->map[RMAP_IN].name); + filter->map[RMAP_IN].map = map; if (route_update && peer->status == Established) { @@ -2723,17 +2723,14 @@ bgp_route_map_process_peer (const char *rmap_name, struct peer *peer, if (filter->map[RMAP_IMPORT].name && (strcmp(rmap_name, filter->map[RMAP_IMPORT].name) == 0)) { - filter->map[RMAP_IMPORT].map = - route_map_lookup_by_name (filter->map[RMAP_IMPORT].name); + filter->map[RMAP_IMPORT].map = map; update = 1; } if (filter->map[RMAP_EXPORT].name && (strcmp(rmap_name, filter->map[RMAP_EXPORT].name) == 0)) { - filter->map[RMAP_EXPORT].map = - route_map_lookup_by_name (filter->map[RMAP_EXPORT].name); - + filter->map[RMAP_EXPORT].map = map; update = 1; } @@ -2769,21 +2766,20 @@ bgp_route_map_process_peer (const char *rmap_name, struct peer *peer, */ if (filter->map[RMAP_OUT].name && (strcmp(rmap_name, filter->map[RMAP_OUT].name) == 0)) - filter->map[RMAP_OUT].map = - route_map_lookup_by_name (filter->map[RMAP_OUT].name); + filter->map[RMAP_OUT].map = map; if (filter->usmap.name && (strcmp(rmap_name, filter->usmap.name) == 0)) - filter->usmap.map = route_map_lookup_by_name (filter->usmap.name); + filter->usmap.map = map; if (peer->default_rmap[afi][safi].name && (strcmp (rmap_name, peer->default_rmap[afi][safi].name) == 0)) - peer->default_rmap[afi][safi].map = - route_map_lookup_by_name (peer->default_rmap[afi][safi].name); + peer->default_rmap[afi][safi].map = map; } static void -bgp_route_map_update_peer_group(const char *rmap_name, struct bgp *bgp) +bgp_route_map_update_peer_group(const char *rmap_name, struct route_map *map, + struct bgp *bgp) { struct peer_group *group; struct listnode *node, *nnode; @@ -2807,16 +2803,22 @@ bgp_route_map_update_peer_group(const char *rmap_name, struct bgp *bgp) { if ((filter->map[direct].name) && (strcmp(rmap_name, filter->map[direct].name) == 0)) - filter->map[direct].map = - route_map_lookup_by_name (filter->map[direct].name); + filter->map[direct].map = map; } if (filter->usmap.name && (strcmp(rmap_name, filter->usmap.name) == 0)) - filter->usmap.map = route_map_lookup_by_name (filter->usmap.name); + filter->usmap.map = map; } } +/* + * Note that if an extreme number (tens of thousands) of route-maps are in use + * and if bgp has an extreme number of peers, network statements, etc then this + * function can consume a lot of cycles. This is due to this function being + * called for each route-map and within this function we walk the list of peers, + * network statements, etc looking to see if they use this route-map. + */ static int bgp_route_map_process_update (void *arg, const char *rmap_name, int route_update) { @@ -2828,11 +2830,14 @@ bgp_route_map_process_update (void *arg, const char *rmap_name, int route_update struct bgp_static *bgp_static; struct bgp *bgp = (struct bgp *)arg; struct listnode *node, *nnode; + struct route_map *map; char buf[INET6_ADDRSTRLEN]; if (!bgp) return (-1); + map = route_map_lookup_by_name (rmap_name); + for (ALL_LIST_ELEMENTS (bgp->peer, node, nnode, peer)) { @@ -2848,7 +2853,7 @@ bgp_route_map_process_update (void *arg, const char *rmap_name, int route_update continue; /* process in/out/import/export/default-orig route-maps */ - bgp_route_map_process_peer(rmap_name, peer, afi, safi, route_update); + bgp_route_map_process_peer(rmap_name, map, peer, afi, safi, route_update); } } @@ -2857,49 +2862,46 @@ bgp_route_map_process_update (void *arg, const char *rmap_name, int route_update route_update, 0); /* update peer-group config (template) */ - bgp_route_map_update_peer_group(rmap_name, bgp); + bgp_route_map_update_peer_group(rmap_name, map, bgp); - /* For table route-map updates. */ for (afi = AFI_IP; afi < AFI_MAX; afi++) for (safi = SAFI_UNICAST; safi < SAFI_MAX; safi++) { + /* For table route-map updates. */ if (bgp->table_map[afi][safi].name && (strcmp(rmap_name, bgp->table_map[afi][safi].name) == 0)) { - bgp->table_map[afi][safi].map = - route_map_lookup_by_name (bgp->table_map[afi][safi].name); + bgp->table_map[afi][safi].map = map; + if (BGP_DEBUG (zebra, ZEBRA)) zlog_debug("Processing route_map %s update on " "table map", rmap_name); if (route_update) bgp_zebra_announce_table(bgp, afi, safi); } - } - /* For network route-map updates. */ - for (afi = AFI_IP; afi < AFI_MAX; afi++) - for (safi = SAFI_UNICAST; safi < SAFI_MAX; safi++) - for (bn = bgp_table_top (bgp->route[afi][safi]); bn; - bn = bgp_route_next (bn)) - if ((bgp_static = bn->info) != NULL) - { - if (bgp_static->rmap.name && - (strcmp(rmap_name, bgp_static->rmap.name) == 0)) - { - bgp_static->rmap.map = - route_map_lookup_by_name (bgp_static->rmap.name); - if (route_update) - if (!bgp_static->backdoor) - { - if (bgp_debug_zebra(&bn->p)) - zlog_debug("Processing route_map %s update on " - "static route %s", rmap_name, - inet_ntop (bn->p.family, &bn->p.u.prefix, - buf, INET6_ADDRSTRLEN)); - bgp_static_update (bgp, &bn->p, bgp_static, afi, safi); - } - } - } + /* For network route-map updates. */ + for (bn = bgp_table_top (bgp->route[afi][safi]); bn; bn = bgp_route_next (bn)) + if ((bgp_static = bn->info) != NULL) + { + if (bgp_static->rmap.name && + (strcmp(rmap_name, bgp_static->rmap.name) == 0)) + { + bgp_static->rmap.map = map; + + if (route_update) + if (!bgp_static->backdoor) + { + if (bgp_debug_zebra(&bn->p)) + zlog_debug("Processing route_map %s update on " + "static route %s", rmap_name, + inet_ntop (bn->p.family, &bn->p.u.prefix, + buf, INET6_ADDRSTRLEN)); + bgp_static_update (bgp, &bn->p, bgp_static, afi, safi); + } + } + } + } /* For redistribute route-map updates. */ for (afi = AFI_IP; afi < AFI_MAX; afi++) @@ -2918,8 +2920,7 @@ bgp_route_map_process_update (void *arg, const char *rmap_name, int route_update if (red->rmap.name && (strcmp(rmap_name, red->rmap.name) == 0)) { - red->rmap.map = - route_map_lookup_by_name (red->rmap.name); + red->rmap.map = map; if (route_update) { diff --git a/lib/routemap.c b/lib/routemap.c index 8e5064b00b..e760dacf7d 100644 --- a/lib/routemap.c +++ b/lib/routemap.c @@ -66,6 +66,38 @@ struct route_map_list /* Master list of route map. */ static struct route_map_list route_map_master = { NULL, NULL, NULL, NULL, NULL }; +struct hash *route_map_master_hash = NULL; + +static unsigned int +route_map_hash_key_make (void *p) +{ + const struct route_map *map = p; + return string_hash_make (map->name); +} + +static int +route_map_hash_cmp(const void *p1, const void *p2) +{ + const struct route_map *map1 = p1; + const struct route_map *map2 = p2; + + if (map1->deleted == map2->deleted) + { + if (map1->name && map2->name) + { + if (!strcmp (map1->name, map2->name)) + { + return 1; + } + } + else if (!map1->name && !map2->name) + { + return 1; + } + } + + return 0; +} enum route_map_upd8_type { @@ -127,7 +159,10 @@ route_map_add (const char *name) map = route_map_new (name); list = &route_map_master; - + + /* Add map to the hash */ + hash_get(route_map_master_hash, map, hash_alloc_intern); + map->next = NULL; map->prev = list->tail; if (list->tail) @@ -172,6 +207,7 @@ route_map_free_map (struct route_map *map) else list->head = map->next; + hash_release(route_map_master_hash, map); XFREE (MTYPE_ROUTE_MAP_NAME, map->name); XFREE (MTYPE_ROUTE_MAP, map); } @@ -211,14 +247,17 @@ struct route_map * route_map_lookup_by_name (const char *name) { struct route_map *map; + struct route_map tmp_map; if (!name) return NULL; - for (map = route_map_master.head; map; map = map->next) - if ((strcmp (map->name, name) == 0) && (!map->deleted)) - return map; - return NULL; + // map.deleted is 0 via memset + memset(&tmp_map, 0, sizeof(struct route_map)); + tmp_map.name = XSTRDUP(MTYPE_ROUTE_MAP_NAME, name); + map = hash_lookup(route_map_master_hash, &tmp_map); + XFREE(MTYPE_ROUTE_MAP_NAME, tmp_map.name); + return map; } int @@ -226,17 +265,30 @@ route_map_mark_updated (const char *name, int del_later) { struct route_map *map; int ret = -1; + struct route_map tmp_map; - /* We need to do this walk manually instead of calling lookup_by_name() - * because the lookup function doesn't return route maps marked as - * deleted. + if (!name) + return (ret); + + map = route_map_lookup_by_name(name); + + /* If we did not find the routemap with deleted=0 try again + * with deleted=1 */ - for (map = route_map_master.head; map; map = map->next) - if (strcmp (map->name, name) == 0) - { - map->to_be_processed = 1; - ret = 0; - } + if (!map) + { + memset(&tmp_map, 0, sizeof(struct route_map)); + tmp_map.name = XSTRDUP(MTYPE_ROUTE_MAP_NAME, name); + tmp_map.deleted = 1; + map = hash_lookup(route_map_master_hash, &tmp_map); + XFREE(MTYPE_ROUTE_MAP_NAME, tmp_map.name); + } + + if (map) + { + map->to_be_processed = 1; + ret = 0; + } return(ret); } @@ -386,8 +438,12 @@ vty_show_route_map (struct vty *vty, const char *name) } else { - vty_out (vty, "%%route-map %s not found%s", name, VTY_NEWLINE); - return CMD_WARNING; + if (zlog_default) + vty_out (vty, "%s", zlog_proto_names[zlog_default->protocol]); + if (zlog_default->instance) + vty_out (vty, " %d", zlog_default->instance); + vty_out (vty, ": 'route-map %s' not found%s", name, VTY_NEWLINE); + return CMD_SUCCESS; } } else @@ -1049,6 +1105,7 @@ route_map_init (void) /* Make vector for match and set. */ route_match_vec = vector_init (1); route_set_vec = vector_init (1); + route_map_master_hash = hash_create(route_map_hash_key_make, route_map_hash_cmp); } void -- 2.39.5