From b9e00458b9f357f6c9b301f95b276fd019da0692 Mon Sep 17 00:00:00 2001 From: Pablo Neira Ayuso Date: Sun, 1 May 2022 17:40:01 +0200 Subject: src: add dynamic register allocation infrastructure Starting Linux kernel 5.18-rc, operations on registers that already contain the expected data are turned into noop. Track operation on registers to use the same register through nftnl_reg_get(). This patch introduces an LRU eviction strategy when all the registers are in used. nftnl_reg_get_scratch() is used to allocate a register as scratchpad area: no tracking is performed in this case, although register eviction might occur. Acked-by: Phil Sutter Signed-off-by: Pablo Neira Ayuso --- src/regs.c | 225 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 225 insertions(+) create mode 100644 src/regs.c (limited to 'src/regs.c') diff --git a/src/regs.c b/src/regs.c new file mode 100644 index 0000000..8dd70b3 --- /dev/null +++ b/src/regs.c @@ -0,0 +1,225 @@ +/* + * (C) 2012-2022 by Pablo Neira Ayuso + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + */ + +/* Funded through the NGI0 PET Fund established by NLnet (https://nlnet.nl) + * with support from the European Commission's Next Generation Internet + * programme. + */ + +#include +#include +#include +#include +#include +#include + +#include + +#include "internal.h" + +EXPORT_SYMBOL(nftnl_regs_alloc); +struct nftnl_regs *nftnl_regs_alloc(uint32_t num_regs) +{ + struct nftnl_regs *regs; + + if (num_regs < 16) + num_regs = 16; + + regs = calloc(1, sizeof(struct nftnl_regs)); + if (!regs) + return NULL; + + regs->reg = calloc(num_regs, sizeof(struct nftnl_reg)); + if (!regs->reg) { + free(regs->reg); + return NULL; + } + + regs->num_regs = num_regs; + + return regs; +} + +EXPORT_SYMBOL(nftnl_regs_free); +void nftnl_regs_free(const struct nftnl_regs *regs) +{ + xfree(regs->reg); + xfree(regs); +} + +static enum nftnl_expr_type nftnl_expr_type(const struct nftnl_expr *expr) +{ + if (!strcmp(expr->ops->name, "meta")) + return NFT_EXPR_META; + else if (!strcmp(expr->ops->name, "payload")) + return NFT_EXPR_PAYLOAD; + + assert(0); + return NFT_EXPR_UNSPEC; +} + +static int nftnl_expr_reg_len(const struct nftnl_expr *expr) +{ + return expr->ops->reg.len(expr); +} + +static bool nftnl_expr_reg_cmp(const struct nftnl_regs *regs, + const struct nftnl_expr *expr, int i) +{ + if (regs->reg[i].type != nftnl_expr_type(expr)) + return false; + + return expr->ops->reg.cmp(®s->reg[i], expr); +} + +static void nft_expr_reg_update(struct nftnl_regs *regs, + const struct nftnl_expr *expr, int i) +{ + return expr->ops->reg.update(®s->reg[i], expr); +} + +static int reg_space(int i) +{ + return sizeof(uint32_t) * 16 - sizeof(uint32_t) * i; +} + +struct nftnl_reg_ctx { + uint64_t genid; + int reg; + int evict; +}; + +static void register_track(struct nftnl_reg_ctx *ctx, + const struct nftnl_regs *regs, int i, int len) +{ + if (ctx->reg >= 0 || regs->reg[i].word || reg_space(i) < len) + return; + + if (regs->reg[i].type == NFT_EXPR_UNSPEC) { + ctx->genid = regs->genid; + ctx->reg = i; + } else if (regs->reg[i].genid < ctx->genid) { + ctx->genid = regs->reg[i].genid; + ctx->evict = i; + } +} + +static void register_evict(struct nftnl_reg_ctx *ctx) +{ + if (ctx->reg < 0) { + assert(ctx->evict >= 0); + ctx->reg = ctx->evict; + } +} + +static void __register_update(struct nftnl_regs *regs, uint8_t reg, + int type, uint32_t len, uint8_t word, + uint64_t genid, const struct nftnl_expr *expr) +{ + regs->reg[reg].type = type; + regs->reg[reg].genid = genid; + regs->reg[reg].len = len; + regs->reg[reg].word = word; + nft_expr_reg_update(regs, expr, reg); +} + +static void __register_cancel(struct nftnl_regs *regs, int i) +{ + regs->reg[i].type = NFT_EXPR_UNSPEC; + regs->reg[i].word = 0; + regs->reg[i].len = 0; + regs->reg[i].genid = 0; +} + +static void register_cancel(struct nftnl_reg_ctx *ctx, struct nftnl_regs *regs, + int len) +{ + int i; + + for (i = ctx->reg; len > 0; i++, len -= sizeof(uint32_t)) { + if (regs->reg[i].type == NFT_EXPR_UNSPEC) + continue; + + __register_cancel(regs, i); + } + + while (i < regs->num_regs && regs->reg[i].word != 0) { + __register_cancel(regs, i); + i++; + } +} + +static void register_update(struct nftnl_reg_ctx *ctx, struct nftnl_regs *regs, + int type, uint32_t len, uint64_t genid, + const struct nftnl_expr *expr) +{ + register_cancel(ctx, regs, len); + __register_update(regs, ctx->reg, type, len, 0, genid, expr); +} + +static uint64_t reg_genid(struct nftnl_regs *regs) +{ + return ++regs->genid; +} + +EXPORT_SYMBOL(nftnl_reg_get); +uint32_t nftnl_reg_get(struct nftnl_regs *regs, const struct nftnl_expr *expr) +{ + struct nftnl_reg_ctx ctx = { + .reg = -1, + .evict = -1, + .genid = UINT64_MAX, + }; + enum nftnl_expr_type type; + uint64_t genid; + int i, j, len; + + type = nftnl_expr_type(expr); + len = nftnl_expr_reg_len(expr); + + for (i = 0; i < 16; i++) { + register_track(&ctx, regs, i, len); + + if (!nftnl_expr_reg_cmp(regs, expr, i)) + continue; + + regs->reg[i].genid = reg_genid(regs); + return i + NFT_REG32_00; + } + + register_evict(&ctx); + genid = reg_genid(regs); + register_update(&ctx, regs, type, len, genid, expr); + + len -= sizeof(uint32_t); + j = 1; + for (i = ctx.reg + 1; len > 0; i++, len -= sizeof(uint32_t)) + __register_update(regs, i, type, len, j++, genid, expr); + + return ctx.reg + NFT_REG32_00; +} + +EXPORT_SYMBOL(nftnl_reg_get_scratch); +uint32_t nftnl_reg_get_scratch(struct nftnl_regs *regs, uint32_t len) +{ + struct nftnl_reg_ctx ctx = { + .reg = -1, + .evict = -1, + .genid = UINT64_MAX, + }; + int i; + + for (i = 0; i < 16; i++) + register_track(&ctx, regs, i, len); + + register_evict(&ctx); + register_cancel(&ctx, regs, len); + + return ctx.reg + NFT_REG32_00; +} -- cgit v1.2.3