From df48e56e987f84bb32ea53dfe98569dfe3fb7e37 Mon Sep 17 00:00:00 2001 From: Pablo Neira Ayuso Date: Fri, 2 Apr 2021 20:26:15 +0200 Subject: cache: add hashtable cache for sets This patch adds a hashtable for set lookups. This patch also splits table->sets in two: - Sets that reside in the cache are stored in the new tables->cache_set and tables->cache_set_ht. - Set that defined via command line / ruleset file reside in tables->set. Sets in the cache (already in the kernel) are not placed in the table->sets list. By keeping separated lists, sets defined via command line / ruleset file can be added to cache. Adding 10000 sets, before: # time nft -f x real 0m6,415s user 0m3,126s sys 0m3,284s After: # time nft -f x real 0m3,949s user 0m0,743s sys 0m3,205s Signed-off-by: Pablo Neira Ayuso --- include/cache.h | 2 + include/netlink.h | 1 - include/rule.h | 6 ++- src/cache.c | 93 +++++++++++++++++++++++++++++++++++++++++++++-- src/evaluate.c | 20 +++++----- src/json.c | 6 +-- src/monitor.c | 2 +- src/netlink.c | 31 ---------------- src/netlink_delinearize.c | 6 +-- src/rule.c | 36 ++++++++---------- 10 files changed, 128 insertions(+), 75 deletions(-) diff --git a/include/cache.h b/include/cache.h index 087f9ba9..f500e1b1 100644 --- a/include/cache.h +++ b/include/cache.h @@ -59,5 +59,7 @@ void cache_release(struct nft_cache *cache); void chain_cache_add(struct chain *chain, struct table *table); struct chain *chain_cache_find(const struct table *table, const struct handle *handle); +void set_cache_add(struct set *set, struct table *table); +struct set *set_cache_find(const struct table *table, const char *name); #endif /* _NFT_CACHE_H_ */ diff --git a/include/netlink.h b/include/netlink.h index cf8aae46..f93c5322 100644 --- a/include/netlink.h +++ b/include/netlink.h @@ -139,7 +139,6 @@ extern int netlink_list_tables(struct netlink_ctx *ctx, const struct handle *h); extern struct table *netlink_delinearize_table(struct netlink_ctx *ctx, const struct nftnl_table *nlt); -extern int netlink_list_sets(struct netlink_ctx *ctx, const struct handle *h); extern struct set *netlink_delinearize_set(struct netlink_ctx *ctx, const struct nftnl_set *nls); diff --git a/include/rule.h b/include/rule.h index ad9cca90..90c01e90 100644 --- a/include/rule.h +++ b/include/rule.h @@ -158,6 +158,8 @@ struct table { struct list_head *cache_chain_ht; struct list_head cache_chain; struct list_head chains; + struct list_head *cache_set_ht; + struct list_head cache_set; struct list_head sets; struct list_head objs; struct list_head flowtables; @@ -331,6 +333,8 @@ void rule_stmt_insert_at(struct rule *rule, struct stmt *nstmt, */ struct set { struct list_head list; + struct list_head cache_hlist; + struct list_head cache_list; struct handle handle; struct location location; unsigned int refcnt; @@ -359,8 +363,6 @@ extern struct set *set_alloc(const struct location *loc); extern struct set *set_get(struct set *set); extern void set_free(struct set *set); extern struct set *set_clone(const struct set *set); -extern void set_add_hash(struct set *set, struct table *table); -extern struct set *set_lookup(const struct table *table, const char *name); extern struct set *set_lookup_global(uint32_t family, const char *table, const char *name, struct nft_cache *cache); extern struct set *set_lookup_fuzzy(const char *set_name, diff --git a/src/cache.c b/src/cache.c index 4e573676..80632c86 100644 --- a/src/cache.c +++ b/src/cache.c @@ -259,6 +259,85 @@ struct chain *chain_cache_find(const struct table *table, return NULL; } +struct set_cache_dump_ctx { + struct netlink_ctx *nlctx; + struct table *table; +}; + +static int set_cache_cb(struct nftnl_set *nls, void *arg) +{ + struct set_cache_dump_ctx *ctx = arg; + const char *set_name; + struct set *set; + uint32_t hash; + + set = netlink_delinearize_set(ctx->nlctx, nls); + if (!set) + return -1; + + set_name = nftnl_set_get_str(nls, NFTNL_SET_NAME); + hash = djb_hash(set_name) % NFT_CACHE_HSIZE; + list_add_tail(&set->cache_hlist, &ctx->table->cache_set_ht[hash]); + list_add_tail(&set->cache_list, &ctx->table->cache_set); + + return 0; +} + +static int set_cache_init(struct netlink_ctx *ctx, struct table *table, + struct nftnl_set_list *set_list) +{ + struct set_cache_dump_ctx dump_ctx = { + .nlctx = ctx, + .table = table, + }; + nftnl_set_list_foreach(set_list, set_cache_cb, &dump_ctx); + + return 0; +} + +static struct nftnl_set_list *set_cache_dump(struct netlink_ctx *ctx, + const struct table *table, + int *err) +{ + struct nftnl_set_list *set_list; + + set_list = mnl_nft_set_dump(ctx, table->handle.family, + table->handle.table.name); + if (!set_list) { + if (errno == EINTR) { + *err = -1; + return NULL; + } + *err = 0; + return NULL; + } + + return set_list; +} + +void set_cache_add(struct set *set, struct table *table) +{ + uint32_t hash; + + hash = djb_hash(set->handle.set.name) % NFT_CACHE_HSIZE; + list_add_tail(&set->cache_hlist, &table->cache_set_ht[hash]); + list_add_tail(&set->cache_list, &table->cache_set); +} + +struct set *set_cache_find(const struct table *table, const char *name) +{ + struct set *set; + uint32_t hash; + + hash = djb_hash(name) % NFT_CACHE_HSIZE; + list_for_each_entry(set, &table->cache_set_ht[hash], cache_hlist) { + if (!strcmp(set->handle.set.name, name)) + return set; + } + + return NULL; +} + static int cache_init_tables(struct netlink_ctx *ctx, struct handle *h, struct nft_cache *cache) { @@ -276,6 +355,7 @@ static int cache_init_tables(struct netlink_ctx *ctx, struct handle *h, static int cache_init_objects(struct netlink_ctx *ctx, unsigned int flags) { struct nftnl_chain_list *chain_list = NULL; + struct nftnl_set_list *set_list = NULL; struct rule *rule, *nrule; struct table *table; struct chain *chain; @@ -290,15 +370,22 @@ static int cache_init_objects(struct netlink_ctx *ctx, unsigned int flags) list_for_each_entry(table, &ctx->nft->cache.list, list) { if (flags & NFT_CACHE_SET_BIT) { - ret = netlink_list_sets(ctx, &table->handle); - list_splice_tail_init(&ctx->list, &table->sets); + set_list = set_cache_dump(ctx, table, &ret); + if (!set_list) { + ret = -1; + goto cache_fails; + } + ret = set_cache_init(ctx, table, set_list); + + nftnl_set_list_free(set_list); + if (ret < 0) { ret = -1; goto cache_fails; } } if (flags & NFT_CACHE_SETELEM_BIT) { - list_for_each_entry(set, &table->sets, list) { + list_for_each_entry(set, &table->cache_set, cache_list) { ret = netlink_list_setelems(ctx, &set->handle, set); if (ret < 0) { diff --git a/src/evaluate.c b/src/evaluate.c index 50f100db..85cf9e05 100644 --- a/src/evaluate.c +++ b/src/evaluate.c @@ -273,7 +273,7 @@ static int expr_evaluate_symbol(struct eval_ctx *ctx, struct expr **expr) if (table == NULL) return table_not_found(ctx); - set = set_lookup(table, (*expr)->identifier); + set = set_cache_find(table, (*expr)->identifier); if (set == NULL) return set_not_found(ctx, &(*expr)->location, (*expr)->identifier); @@ -3677,7 +3677,7 @@ static int setelem_evaluate(struct eval_ctx *ctx, struct cmd *cmd) if (table == NULL) return table_not_found(ctx); - set = set_lookup(table, ctx->cmd->handle.set.name); + set = set_cache_find(table, ctx->cmd->handle.set.name); if (set == NULL) return set_not_found(ctx, &ctx->cmd->handle.set.location, ctx->cmd->handle.set.name); @@ -3793,8 +3793,8 @@ static int set_evaluate(struct eval_ctx *ctx, struct set *set) } ctx->set = NULL; - if (set_lookup(table, set->handle.set.name) == NULL) - set_add_hash(set_get(set), table); + if (set_cache_find(table, set->handle.set.name) == NULL) + set_cache_add(set_get(set), table); return 0; } @@ -4401,7 +4401,7 @@ static int cmd_evaluate_list(struct eval_ctx *ctx, struct cmd *cmd) if (table == NULL) return table_not_found(ctx); - set = set_lookup(table, cmd->handle.set.name); + set = set_cache_find(table, cmd->handle.set.name); if (set == NULL) return set_not_found(ctx, &ctx->cmd->handle.set.location, ctx->cmd->handle.set.name); @@ -4415,7 +4415,7 @@ static int cmd_evaluate_list(struct eval_ctx *ctx, struct cmd *cmd) if (table == NULL) return table_not_found(ctx); - set = set_lookup(table, cmd->handle.set.name); + set = set_cache_find(table, cmd->handle.set.name); if (set == NULL) return set_not_found(ctx, &ctx->cmd->handle.set.location, ctx->cmd->handle.set.name); @@ -4429,7 +4429,7 @@ static int cmd_evaluate_list(struct eval_ctx *ctx, struct cmd *cmd) if (table == NULL) return table_not_found(ctx); - set = set_lookup(table, cmd->handle.set.name); + set = set_cache_find(table, cmd->handle.set.name); if (set == NULL) return set_not_found(ctx, &ctx->cmd->handle.set.location, ctx->cmd->handle.set.name); @@ -4544,7 +4544,7 @@ static int cmd_evaluate_flush(struct eval_ctx *ctx, struct cmd *cmd) if (table == NULL) return table_not_found(ctx); - set = set_lookup(table, cmd->handle.set.name); + set = set_cache_find(table, cmd->handle.set.name); if (set == NULL) return set_not_found(ctx, &ctx->cmd->handle.set.location, ctx->cmd->handle.set.name); @@ -4560,7 +4560,7 @@ static int cmd_evaluate_flush(struct eval_ctx *ctx, struct cmd *cmd) if (table == NULL) return table_not_found(ctx); - set = set_lookup(table, cmd->handle.set.name); + set = set_cache_find(table, cmd->handle.set.name); if (set == NULL) return set_not_found(ctx, &ctx->cmd->handle.set.location, ctx->cmd->handle.set.name); @@ -4576,7 +4576,7 @@ static int cmd_evaluate_flush(struct eval_ctx *ctx, struct cmd *cmd) if (table == NULL) return table_not_found(ctx); - set = set_lookup(table, cmd->handle.set.name); + set = set_cache_find(table, cmd->handle.set.name); if (set == NULL) return set_not_found(ctx, &ctx->cmd->handle.set.location, ctx->cmd->handle.set.name); diff --git a/src/json.c b/src/json.c index 14e403fe..52603a57 100644 --- a/src/json.c +++ b/src/json.c @@ -1574,7 +1574,7 @@ static json_t *table_print_json_full(struct netlink_ctx *ctx, tmp = obj_print_json(obj); json_array_append_new(root, tmp); } - list_for_each_entry(set, &table->sets, list) { + list_for_each_entry(set, &table->cache_set, cache_list) { if (set_is_anonymous(set->flags)) continue; tmp = set_print_json(&ctx->nft->output, set); @@ -1687,7 +1687,7 @@ static json_t *do_list_chains_json(struct netlink_ctx *ctx, struct cmd *cmd) static json_t *do_list_set_json(struct netlink_ctx *ctx, struct cmd *cmd, struct table *table) { - struct set *set = set_lookup(table, cmd->handle.set.name); + struct set *set = set_cache_find(table, cmd->handle.set.name); if (set == NULL) return json_null(); @@ -1707,7 +1707,7 @@ static json_t *do_list_sets_json(struct netlink_ctx *ctx, struct cmd *cmd) cmd->handle.family != table->handle.family) continue; - list_for_each_entry(set, &table->sets, list) { + list_for_each_entry(set, &table->cache_set, cache_list) { if (cmd->obj == CMD_OBJ_SETS && !set_is_literal(set->flags)) continue; diff --git a/src/monitor.c b/src/monitor.c index 047d89db..dc3f0848 100644 --- a/src/monitor.c +++ b/src/monitor.c @@ -632,7 +632,7 @@ static void netlink_events_cache_addset(struct netlink_mon_handler *monh, goto out; } - set_add_hash(s, t); + set_cache_add(s, t); out: nftnl_set_free(nls); } diff --git a/src/netlink.c b/src/netlink.c index 89d224ed..e8b01609 100644 --- a/src/netlink.c +++ b/src/netlink.c @@ -974,37 +974,6 @@ struct set *netlink_delinearize_set(struct netlink_ctx *ctx, return set; } -static int list_set_cb(struct nftnl_set *nls, void *arg) -{ - struct netlink_ctx *ctx = arg; - struct set *set; - - set = netlink_delinearize_set(ctx, nls); - if (set == NULL) - return -1; - list_add_tail(&set->list, &ctx->list); - return 0; -} - -int netlink_list_sets(struct netlink_ctx *ctx, const struct handle *h) -{ - struct nftnl_set_list *set_cache; - int err; - - set_cache = mnl_nft_set_dump(ctx, h->family, h->table.name); - if (set_cache == NULL) { - if (errno == EINTR) - return -1; - - return 0; - } - - ctx->data = h; - err = nftnl_set_list_foreach(set_cache, list_set_cb, ctx); - nftnl_set_list_free(set_cache); - return err; -} - void alloc_setelem_cache(const struct expr *set, struct nftnl_set *nls) { struct nftnl_set_elem *nlse; diff --git a/src/netlink_delinearize.c b/src/netlink_delinearize.c index 7cd7d403..710c668a 100644 --- a/src/netlink_delinearize.c +++ b/src/netlink_delinearize.c @@ -356,7 +356,7 @@ static void netlink_parse_lookup(struct netlink_parse_ctx *ctx, uint32_t flag; name = nftnl_expr_get_str(nle, NFTNL_EXPR_LOOKUP_SET); - set = set_lookup(ctx->table, name); + set = set_cache_find(ctx->table, name); if (set == NULL) return netlink_error(ctx, loc, "Unknown set '%s' in lookup expression", @@ -1531,7 +1531,7 @@ static void netlink_parse_dynset(struct netlink_parse_ctx *ctx, init_list_head(&dynset_parse_ctx.stmt_list); name = nftnl_expr_get_str(nle, NFTNL_EXPR_DYNSET_SET_NAME); - set = set_lookup(ctx->table, name); + set = set_cache_find(ctx->table, name); if (set == NULL) return netlink_error(ctx, loc, "Unknown set '%s' in dynset statement", @@ -1640,7 +1640,7 @@ static void netlink_parse_objref(struct netlink_parse_ctx *ctx, struct set *set; name = nftnl_expr_get_str(nle, NFTNL_EXPR_OBJREF_SET_NAME); - set = set_lookup(ctx->table, name); + set = set_cache_find(ctx->table, name); if (set == NULL) return netlink_error(ctx, loc, "Unknown set '%s' in objref expression", diff --git a/src/rule.c b/src/rule.c index 9c9fd7fd..2c6292c4 100644 --- a/src/rule.c +++ b/src/rule.c @@ -201,22 +201,6 @@ void set_free(struct set *set) xfree(set); } -void set_add_hash(struct set *set, struct table *table) -{ - list_add_tail(&set->list, &table->sets); -} - -struct set *set_lookup(const struct table *table, const char *name) -{ - struct set *set; - - list_for_each_entry(set, &table->sets, list) { - if (!strcmp(set->handle.set.name, name)) - return set; - } - return NULL; -} - struct set *set_lookup_fuzzy(const char *set_name, const struct nft_cache *cache, const struct table **t) @@ -228,7 +212,7 @@ struct set *set_lookup_fuzzy(const char *set_name, string_misspell_init(&st); list_for_each_entry(table, &cache->list, list) { - list_for_each_entry(set, &table->sets, list) { + list_for_each_entry(set, &table->cache_set, cache_list) { if (set_is_anonymous(set->flags)) continue; if (!strcmp(set->handle.set.name, set_name)) { @@ -256,7 +240,7 @@ struct set *set_lookup_global(uint32_t family, const char *table, if (t == NULL) return NULL; - return set_lookup(t, name); + return set_cache_find(t, name); } struct print_fmt_options { @@ -1124,6 +1108,7 @@ struct table *table_alloc(void) init_list_head(&table->chains); init_list_head(&table->cache_chain); init_list_head(&table->sets); + init_list_head(&table->cache_set); init_list_head(&table->objs); init_list_head(&table->flowtables); init_list_head(&table->chain_bindings); @@ -1135,6 +1120,11 @@ struct table *table_alloc(void) for (i = 0; i < NFT_CACHE_HSIZE; i++) init_list_head(&table->cache_chain_ht[i]); + table->cache_set_ht = + xmalloc(sizeof(struct list_head) * NFT_CACHE_HSIZE); + for (i = 0; i < NFT_CACHE_HSIZE; i++) + init_list_head(&table->cache_set_ht[i]); + return table; } @@ -1158,6 +1148,9 @@ void table_free(struct table *table) chain_free(chain); list_for_each_entry_safe(set, nset, &table->sets, list) set_free(set); + /* this is implicitly releasing sets in the hashtable cache */ + list_for_each_entry_safe(set, nset, &table->cache_set, cache_list) + set_free(set); list_for_each_entry_safe(ft, nft, &table->flowtables, list) flowtable_free(ft); list_for_each_entry_safe(obj, nobj, &table->objs, list) @@ -1165,6 +1158,7 @@ void table_free(struct table *table) handle_free(&table->handle); scope_release(&table->scope); xfree(table->cache_chain_ht); + xfree(table->cache_set_ht); xfree(table); } @@ -1275,7 +1269,7 @@ static void table_print(const struct table *table, struct output_ctx *octx) obj_print(obj, octx); delim = "\n"; } - list_for_each_entry(set, &table->sets, list) { + list_for_each_entry(set, &table->cache_set, cache_list) { if (set_is_anonymous(set->flags)) continue; nft_print(octx, "%s", delim); @@ -1697,7 +1691,7 @@ static int do_list_sets(struct netlink_ctx *ctx, struct cmd *cmd) family2str(table->handle.family), table->handle.table.name); - list_for_each_entry(set, &table->sets, list) { + list_for_each_entry(set, &table->cache_set, cache_list) { if (cmd->obj == CMD_OBJ_SETS && !set_is_literal(set->flags)) continue; @@ -2435,7 +2429,7 @@ static int do_list_set(struct netlink_ctx *ctx, struct cmd *cmd, { struct set *set; - set = set_lookup(table, cmd->handle.set.name); + set = set_cache_find(table, cmd->handle.set.name); if (set == NULL) return -1; -- cgit v1.2.3