From fbd8fb09c50bcee3f046dce2281f25baa4e14927 Mon Sep 17 00:00:00 2001 From: Pablo Neira Ayuso Date: Fri, 21 Aug 2020 12:04:12 +0200 Subject: src: add chain hashtable cache This significantly improves ruleset listing time with large rulesets (~50k rules) with _lots_ of non-base chains. # time nft list ruleset &> /dev/null Before this patch: real 0m11,172s user 0m6,810s sys 0m4,220s After this patch: real 0m4,747s user 0m0,802s sys 0m3,912s This patch also removes list_bindings from netlink_ctx since there is no need to keep a temporary list of chains anymore. Signed-off-by: Pablo Neira Ayuso --- include/cache.h | 14 +++++++++ include/netlink.h | 1 - include/rule.h | 4 ++- src/cache.c | 92 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/evaluate.c | 6 ++-- src/netlink.c | 46 ---------------------------- src/rule.c | 34 ++++++++++++-------- 7 files changed, 133 insertions(+), 64 deletions(-) diff --git a/include/cache.h b/include/cache.h index b9db1a8f..baa2bb29 100644 --- a/include/cache.h +++ b/include/cache.h @@ -45,4 +45,18 @@ static inline uint32_t djb_hash(const char *key) return hash; } +#define NFT_CACHE_HSIZE 8192 + +struct netlink_ctx; +struct table; +struct chain; +struct handle; + +struct nftnl_chain_list *chain_cache_dump(struct netlink_ctx *ctx, int *err); +int chain_cache_init(struct netlink_ctx *ctx, struct table *table, + struct nftnl_chain_list *chain_cache); +void chain_cache_add(struct chain *chain, struct table *table); +struct chain *chain_cache_find(const struct table *table, + const struct handle *handle); + #endif /* _NFT_CACHE_H_ */ diff --git a/include/netlink.h b/include/netlink.h index ad2247e9..b78277a8 100644 --- a/include/netlink.h +++ b/include/netlink.h @@ -64,7 +64,6 @@ struct netlink_ctx { struct nft_ctx *nft; struct list_head *msgs; struct list_head list; - struct list_head list_bindings; struct set *set; const void *data; uint32_t seqnum; diff --git a/include/rule.h b/include/rule.h index f2f82cc0..62d25be2 100644 --- a/include/rule.h +++ b/include/rule.h @@ -8,6 +8,7 @@ #include /* For NFTNL_CTTIMEOUT_ARRAY_MAX. */ #include #include +#include /** * struct handle_spec - handle ID @@ -153,6 +154,7 @@ struct table { struct handle handle; struct location location; struct scope scope; + struct list_head *chain_htable; struct list_head chains; struct list_head sets; struct list_head objs; @@ -217,6 +219,7 @@ struct hook_spec { */ struct chain { struct list_head list; + struct list_head hlist; struct handle handle; struct location location; unsigned int refcnt; @@ -242,7 +245,6 @@ extern const char *chain_hookname_lookup(const char *name); extern struct chain *chain_alloc(const char *name); extern struct chain *chain_get(struct chain *chain); extern void chain_free(struct chain *chain); -extern void chain_add_hash(struct chain *chain, struct table *table); extern struct chain *chain_lookup(const struct table *table, const struct handle *h); extern struct chain *chain_lookup_fuzzy(const struct handle *h, diff --git a/src/cache.c b/src/cache.c index 7797ff6b..ed260900 100644 --- a/src/cache.c +++ b/src/cache.c @@ -12,6 +12,9 @@ #include #include #include +#include +#include +#include static unsigned int evaluate_cache_add(struct cmd *cmd, unsigned int flags) { @@ -164,3 +167,92 @@ unsigned int cache_evaluate(struct nft_ctx *nft, struct list_head *cmds) return flags; } + +struct chain_cache_dump_ctx { + struct netlink_ctx *nlctx; + struct table *table; +}; + +static int chain_cache_cb(struct nftnl_chain *nlc, void *arg) +{ + struct chain_cache_dump_ctx *ctx = arg; + const char *chain_name, *table_name; + uint32_t hash, family; + struct chain *chain; + + table_name = nftnl_chain_get_str(nlc, NFTNL_CHAIN_TABLE); + chain_name = nftnl_chain_get_str(nlc, NFTNL_CHAIN_NAME); + family = nftnl_chain_get_u32(nlc, NFTNL_CHAIN_FAMILY); + + if (strcmp(table_name, ctx->table->handle.table.name) || + family != ctx->table->handle.family) + return 0; + + hash = djb_hash(chain_name) % NFT_CACHE_HSIZE; + chain = netlink_delinearize_chain(ctx->nlctx, nlc); + + if (chain->flags & CHAIN_F_BINDING) { + list_add_tail(&chain->list, &ctx->table->chain_bindings); + } else { + list_add_tail(&chain->hlist, &ctx->table->chain_htable[hash]); + list_add_tail(&chain->list, &ctx->table->chains); + } + + nftnl_chain_list_del(nlc); + nftnl_chain_free(nlc); + + return 0; +} + +int chain_cache_init(struct netlink_ctx *ctx, struct table *table, + struct nftnl_chain_list *chain_list) +{ + struct chain_cache_dump_ctx dump_ctx = { + .nlctx = ctx, + .table = table, + }; + nftnl_chain_list_foreach(chain_list, chain_cache_cb, &dump_ctx); + + return 0; +} + +struct nftnl_chain_list *chain_cache_dump(struct netlink_ctx *ctx, int *err) +{ + struct nftnl_chain_list *chain_list; + + chain_list = mnl_nft_chain_dump(ctx, AF_UNSPEC); + if (chain_list == NULL) { + if (errno == EINTR) { + *err = -1; + return NULL; + } + *err = 0; + return NULL; + } + + return chain_list; +} + +void chain_cache_add(struct chain *chain, struct table *table) +{ + uint32_t hash; + + hash = djb_hash(chain->handle.chain.name) % NFT_CACHE_HSIZE; + list_add_tail(&chain->hlist, &table->chain_htable[hash]); + list_add_tail(&chain->list, &table->chains); +} + +struct chain *chain_cache_find(const struct table *table, + const struct handle *handle) +{ + struct chain *chain; + uint32_t hash; + + hash = djb_hash(handle->chain.name) % NFT_CACHE_HSIZE; + list_for_each_entry(chain, &table->chain_htable[hash], hlist) { + if (!strcmp(chain->handle.chain.name, handle->chain.name)) + return chain; + } + + return NULL; +} diff --git a/src/evaluate.c b/src/evaluate.c index b64ed3c0..320a464f 100644 --- a/src/evaluate.c +++ b/src/evaluate.c @@ -3855,7 +3855,7 @@ static int rule_cache_update(struct eval_ctx *ctx, enum cmd_ops op) if (!table) return table_not_found(ctx); - chain = chain_lookup(table, &rule->handle); + chain = chain_cache_find(table, &rule->handle); if (!chain) return chain_not_found(ctx); @@ -3999,12 +3999,12 @@ static int chain_evaluate(struct eval_ctx *ctx, struct chain *chain) if (chain_lookup(table, &ctx->cmd->handle) == NULL) { chain = chain_alloc(NULL); handle_merge(&chain->handle, &ctx->cmd->handle); - chain_add_hash(chain, table); + chain_cache_add(chain, table); } return 0; } else if (!(chain->flags & CHAIN_F_BINDING)) { if (chain_lookup(table, &chain->handle) == NULL) - chain_add_hash(chain_get(chain), table); + chain_cache_add(chain_get(chain), table); } if (chain->flags & CHAIN_F_BASECHAIN) { diff --git a/src/netlink.c b/src/netlink.c index 77e0d41e..0db5e175 100644 --- a/src/netlink.c +++ b/src/netlink.c @@ -537,52 +537,6 @@ struct chain *netlink_delinearize_chain(struct netlink_ctx *ctx, return chain; } -static int list_chain_cb(struct nftnl_chain *nlc, void *arg) -{ - struct netlink_ctx *ctx = arg; - const struct handle *h = ctx->data; - const char *table; - const char *name; - struct chain *chain; - uint32_t family; - - table = nftnl_chain_get_str(nlc, NFTNL_CHAIN_TABLE); - name = nftnl_chain_get_str(nlc, NFTNL_CHAIN_NAME); - family = nftnl_chain_get_u32(nlc, NFTNL_CHAIN_FAMILY); - - if (h->family != family || strcmp(table, h->table.name) != 0) - return 0; - if (h->chain.name && strcmp(name, h->chain.name) != 0) - return 0; - - chain = netlink_delinearize_chain(ctx, nlc); - if (chain->flags & CHAIN_F_BINDING) - list_add_tail(&chain->list, &ctx->list_bindings); - else - list_add_tail(&chain->list, &ctx->list); - - return 0; -} - -int netlink_list_chains(struct netlink_ctx *ctx, const struct handle *h) -{ - struct nftnl_chain_list *chain_cache; - - chain_cache = mnl_nft_chain_dump(ctx, h->family); - if (chain_cache == NULL) { - if (errno == EINTR) - return -1; - - return 0; - } - - ctx->data = h; - nftnl_chain_list_foreach(chain_cache, list_chain_cb, ctx); - nftnl_chain_list_free(chain_cache); - - return 0; -} - struct table *netlink_delinearize_table(struct netlink_ctx *ctx, const struct nftnl_table *nlt) { diff --git a/src/rule.c b/src/rule.c index 2b5685c2..a925d844 100644 --- a/src/rule.c +++ b/src/rule.c @@ -152,11 +152,18 @@ 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 rule *rule, *nrule; struct table *table; struct chain *chain; struct set *set; - int ret; + int ret = 0; + + if (flags & NFT_CACHE_CHAIN_BIT) { + chain_list = chain_cache_dump(ctx, &ret); + if (!chain_list) + return ret; + } list_for_each_entry(table, &ctx->nft->cache.list, list) { if (flags & NFT_CACHE_SET_BIT) { @@ -174,13 +181,9 @@ static int cache_init_objects(struct netlink_ctx *ctx, unsigned int flags) } } if (flags & NFT_CACHE_CHAIN_BIT) { - ret = netlink_list_chains(ctx, &table->handle); + ret = chain_cache_init(ctx, table, chain_list); if (ret < 0) return -1; - - list_splice_tail_init(&ctx->list, &table->chains); - list_splice_tail_init(&ctx->list_bindings, - &table->chain_bindings); } if (flags & NFT_CACHE_FLOWTABLE_BIT) { ret = netlink_list_flowtables(ctx, &table->handle); @@ -198,7 +201,7 @@ static int cache_init_objects(struct netlink_ctx *ctx, unsigned int flags) if (flags & NFT_CACHE_RULE_BIT) { ret = netlink_list_rules(ctx, &table->handle); list_for_each_entry_safe(rule, nrule, &ctx->list, list) { - chain = chain_lookup(table, &rule->handle); + chain = chain_cache_find(table, &rule->handle); if (!chain) chain = chain_binding_lookup(table, rule->handle.chain.name); @@ -208,6 +211,10 @@ static int cache_init_objects(struct netlink_ctx *ctx, unsigned int flags) return -1; } } + + if (flags & NFT_CACHE_CHAIN_BIT) + nftnl_chain_list_free(chain_list); + return 0; } @@ -256,7 +263,6 @@ int cache_update(struct nft_ctx *nft, unsigned int flags, struct list_head *msgs { struct netlink_ctx ctx = { .list = LIST_HEAD_INIT(ctx.list), - .list_bindings = LIST_HEAD_INIT(ctx.list_bindings), .nft = nft, .msgs = msgs, }; @@ -926,11 +932,6 @@ void chain_free(struct chain *chain) xfree(chain); } -void chain_add_hash(struct chain *chain, struct table *table) -{ - list_add_tail(&chain->list, &table->chains); -} - struct chain *chain_lookup(const struct table *table, const struct handle *h) { struct chain *chain; @@ -1295,6 +1296,7 @@ void chain_print_plain(const struct chain *chain, struct output_ctx *octx) struct table *table_alloc(void) { struct table *table; + int i; table = xzalloc(sizeof(*table)); init_list_head(&table->chains); @@ -1305,6 +1307,11 @@ struct table *table_alloc(void) init_list_head(&table->scope.symbols); table->refcnt = 1; + table->chain_htable = + xmalloc(sizeof(struct list_head) * NFT_CACHE_HSIZE); + for (i = 0; i < NFT_CACHE_HSIZE; i++) + init_list_head(&table->chain_htable[i]); + return table; } @@ -1329,6 +1336,7 @@ void table_free(struct table *table) obj_free(obj); handle_free(&table->handle); scope_release(&table->scope); + xfree(table->chain_htable); xfree(table); } -- cgit v1.2.3