From 88711d8a91333869e77b1e9abe0a39c48d5787c4 Mon Sep 17 00:00:00 2001 From: David Lamparter Date: Sat, 6 Nov 2021 16:57:52 +0100 Subject: [PATCH] lib: use hash for route-map set/match commands Why would this be in a vector to loop over with strcmp()'ing each item... that just makes no sense. Use a hash instead. Signed-off-by: David Lamparter --- lib/routemap.c | 81 ++++++++++++++++++++++++++++++++------------------ lib/routemap.h | 34 +++++++++++++++++++-- 2 files changed, 84 insertions(+), 31 deletions(-) diff --git a/lib/routemap.c b/lib/routemap.c index 6227ebf158..0ca2235d9d 100644 --- a/lib/routemap.c +++ b/lib/routemap.c @@ -34,6 +34,7 @@ #include "lib_errors.h" #include "table.h" #include "json.h" +#include "jhash.h" DEFINE_MTYPE_STATIC(LIB, ROUTE_MAP, "Route map"); DEFINE_MTYPE(LIB, ROUTE_MAP_NAME, "Route map name"); @@ -47,6 +48,27 @@ DEFINE_MTYPE_STATIC(LIB, ROUTE_MAP_DEP_DATA, "Route map dependency data"); DEFINE_QOBJ_TYPE(route_map_index); DEFINE_QOBJ_TYPE(route_map); +static int rmap_cmd_name_cmp(const struct route_map_rule_cmd_proxy *a, + const struct route_map_rule_cmd_proxy *b) +{ + return strcmp(a->cmd->str, b->cmd->str); +} + +static uint32_t rmap_cmd_name_hash(const struct route_map_rule_cmd_proxy *item) +{ + return jhash(item->cmd->str, strlen(item->cmd->str), 0xbfd69320); +} + +DECLARE_HASH(rmap_cmd_name, struct route_map_rule_cmd_proxy, itm, + rmap_cmd_name_cmp, rmap_cmd_name_hash); + +static struct rmap_cmd_name_head rmap_match_cmds[1] = { + INIT_HASH(rmap_match_cmds[0]), +}; +static struct rmap_cmd_name_head rmap_set_cmds[1] = { + INIT_HASH(rmap_set_cmds[0]), +}; + #define IPv4_PREFIX_LIST "ip address prefix-list" #define IPv6_PREFIX_LIST "ipv6 address prefix-list" @@ -61,12 +83,6 @@ struct route_map_pentry_dep { route_map_event_t event; }; -/* Vector for route match rules. */ -static vector route_match_vec; - -/* Vector for route set rules. */ -static vector route_set_vec; - static void route_map_pfx_tbl_update(route_map_event_t event, struct route_map_index *index, afi_t afi, const char *plist_name); @@ -1231,40 +1247,40 @@ static struct route_map_rule *route_map_rule_new(void) } /* Install rule command to the match list. */ -void route_map_install_match(const struct route_map_rule_cmd *cmd) +void _route_map_install_match(struct route_map_rule_cmd_proxy *proxy) { - vector_set(route_match_vec, (void *)cmd); + rmap_cmd_name_add(rmap_match_cmds, proxy); } /* Install rule command to the set list. */ -void route_map_install_set(const struct route_map_rule_cmd *cmd) +void _route_map_install_set(struct route_map_rule_cmd_proxy *proxy) { - vector_set(route_set_vec, (void *)cmd); + rmap_cmd_name_add(rmap_set_cmds, proxy); } /* Lookup rule command from match list. */ static const struct route_map_rule_cmd *route_map_lookup_match(const char *name) { - unsigned int i; - const struct route_map_rule_cmd *rule; + struct route_map_rule_cmd refcmd = {.str = name}; + struct route_map_rule_cmd_proxy ref = {.cmd = &refcmd}; + struct route_map_rule_cmd_proxy *res; - for (i = 0; i < vector_active(route_match_vec); i++) - if ((rule = vector_slot(route_match_vec, i)) != NULL) - if (strcmp(rule->str, name) == 0) - return rule; + res = rmap_cmd_name_find(rmap_match_cmds, &ref); + if (res) + return res->cmd; return NULL; } /* Lookup rule command from set list. */ static const struct route_map_rule_cmd *route_map_lookup_set(const char *name) { - unsigned int i; - const struct route_map_rule_cmd *rule; + struct route_map_rule_cmd refcmd = {.str = name}; + struct route_map_rule_cmd_proxy ref = {.cmd = &refcmd}; + struct route_map_rule_cmd_proxy *res; - for (i = 0; i < vector_active(route_set_vec); i++) - if ((rule = vector_slot(route_set_vec, i)) != NULL) - if (strcmp(rule->str, name) == 0) - return rule; + res = rmap_cmd_name_find(rmap_set_cmds, &ref); + if (res) + return res->cmd; return NULL; } @@ -3161,11 +3177,21 @@ void route_map_rule_tag_free(void *rule) void route_map_finish(void) { int i; + struct route_map_rule_cmd_proxy *proxy; + + /* these 2 hash tables have INIT_HASH initializers, so the "default" + * state is "initialized & empty" => fini() followed by init() to + * return to that same state + */ + while ((proxy = rmap_cmd_name_pop(rmap_match_cmds))) + (void)proxy; + rmap_cmd_name_fini(rmap_match_cmds); + rmap_cmd_name_init(rmap_match_cmds); - vector_free(route_match_vec); - route_match_vec = NULL; - vector_free(route_set_vec); - route_set_vec = NULL; + while ((proxy = rmap_cmd_name_pop(rmap_set_cmds))) + (void)proxy; + rmap_cmd_name_fini(rmap_set_cmds); + rmap_cmd_name_init(rmap_set_cmds); /* * All protocols are setting these to NULL @@ -3309,9 +3335,6 @@ void route_map_init(void) { int i; - /* Make vector for match and set. */ - route_match_vec = vector_init(1); - route_set_vec = vector_init(1); route_map_master_hash = hash_create_size(8, route_map_hash_key_make, route_map_hash_cmp, "Route Map Master Hash"); diff --git a/lib/routemap.h b/lib/routemap.h index f8fdc67d57..7e17e14fa6 100644 --- a/lib/routemap.h +++ b/lib/routemap.h @@ -21,6 +21,7 @@ #ifndef _ZEBRA_ROUTEMAP_H #define _ZEBRA_ROUTEMAP_H +#include "typesafe.h" #include "prefix.h" #include "memory.h" #include "qobj.h" @@ -422,8 +423,37 @@ extern enum rmap_compile_rets route_map_delete_set(struct route_map_index *index, const char *set_name, const char *set_arg); +/* struct route_map_rule_cmd is kept const in order to not have writable + * function pointers (which is a security benefit.) Hence, below struct is + * used as proxy for hashing these for by-name lookup. + */ + +PREDECL_HASH(rmap_cmd_name); + +struct route_map_rule_cmd_proxy { + struct rmap_cmd_name_item itm; + const struct route_map_rule_cmd *cmd; +}; + +/* ... and just automatically create a proxy struct for each call location + * to route_map_install_{match,set} to avoid unnecessarily added boilerplate + * for each route-map user + */ + +#define route_map_install_match(c) \ + do { \ + static struct route_map_rule_cmd_proxy proxy = {.cmd = c}; \ + _route_map_install_match(&proxy); \ + } while (0) + +#define route_map_install_set(c) \ + do { \ + static struct route_map_rule_cmd_proxy proxy = {.cmd = c}; \ + _route_map_install_set(&proxy); \ + } while (0) + /* Install rule command to the match list. */ -extern void route_map_install_match(const struct route_map_rule_cmd *cmd); +extern void _route_map_install_match(struct route_map_rule_cmd_proxy *proxy); /* * Install rule command to the set list. @@ -434,7 +464,7 @@ extern void route_map_install_match(const struct route_map_rule_cmd *cmd); * in the apply command). See 'set metric' command * as it is handled in ripd/ripngd and ospfd. */ -extern void route_map_install_set(const struct route_map_rule_cmd *cmd); +extern void _route_map_install_set(struct route_map_rule_cmd_proxy *proxy); /* Lookup route map by name. */ extern struct route_map *route_map_lookup_by_name(const char *name); -- 2.39.5