Use the new binding graph to validate incremental ruleset updates.
Perform full validation if the table is new, which is the case of the
initial ruleset reload. Subsequent incremental ruleset updates use the
validation list which contains chains with new rules or chains that can
be now reached via jump/goto from another rule/set element.
When validating a chain from commit/abort phase, backtrack to collect
the basechains that can reach this chain, then perform the validation of
rules in this chain. If no basechains can be reached, then skip
validation for this chain. However, if basechains are off the jump stack
limit, then resort to full ruleset validation. This is to prevent
inconsistent validation between the preparation and commit/abort phase
validations.
As for loop checking, stick to the existing approach which uses the jump
stack limit to detect cycles.
Signed-off-by: Pablo Neira Ayuso <pablo@xxxxxxxxxxxxx>
---
v2: nft_chain_validate_backtrack() bails out if chain stack is too deep
or loop is detected, then fallback to full validation. Loops in
chains that are not linked to basechains are allowed by now, so
let's fall back to full validation when is loop detected or chain
stack is too deep.
net/netfilter/nf_tables_api.c | 196 +++++++++++++++++++++++++++++++++-
1 file changed, 191 insertions(+), 5 deletions(-)
diff --git a/net/netfilter/nf_tables_api.c b/net/netfilter/nf_tables_api.c
index 1a3bc7857f78..ee4bd201ca05 100644
--- a/net/netfilter/nf_tables_api.c
+++ b/net/netfilter/nf_tables_api.c
@@ -10397,6 +10397,168 @@ static const struct nfnl_callback nf_tables_cb[NFT_MSG_MAX] = {
},
};
+struct nft_validate_ctx {
+ const struct nft_chain *chain;
+ int level;
+
+ const struct nft_chain **basechain;
+ uint32_t num_basechains;
+ uint32_t max_basechains;
+ int max_level;
+};
+
+static int nft_basechain_array_add(struct nft_validate_ctx *ctx,
+ const struct nft_chain *chain)
+{
+ const struct nft_chain **new_basechain;
+ uint32_t new_max_basechains;
+
+ if (ctx->num_basechains == ctx->max_basechains) {
+ new_max_basechains = ctx->max_basechains + 16;
+ new_basechain = krealloc_array(ctx->basechain,
+ new_max_basechains,
+ sizeof(struct nft_chain *),
+ GFP_KERNEL);
+ if (!new_basechain)
+ return -ENOMEM;
+
+ ctx->basechain = new_basechain;
+ ctx->max_basechains = new_max_basechains;
+ }
+ ctx->basechain[ctx->num_basechains++] = chain;
+
+ if (ctx->level > ctx->max_level)
+ ctx->max_level = ctx->level;
+
+ return 0;
+}
+
+static int nft_chain_validate_backtrack(struct nft_validate_ctx *ctx,
+ const struct list_head *backbinding_list)
+{
+ struct nft_binding *binding;
+ int err;
+
+ /* Basechain is unreachable, fall back to slow path validation. */
+ if (ctx->level >= NFT_JUMP_STACK_SIZE)
+ return -ELOOP;
+
+ list_for_each_entry(binding, backbinding_list, backlist) {
+ if (binding->from.type == NFT_BIND_CHAIN &&
+ binding->from.chain->flags & NFT_CHAIN_BASE &&
+ binding->use > 0) {
+ if (nft_basechain_array_add(ctx, binding->from.chain) < 0)
+ return -ENOMEM;
+
+ continue;
+ }
+
+ switch (binding->from.type) {
+ case NFT_BIND_CHAIN:
+ if (binding->use == 0)
+ break;
+
+ if (ctx->chain == binding->from.chain)
+ return -ELOOP;
+
+ ctx->level++;
+ err = nft_chain_validate_backtrack(ctx,
+ &binding->from.chain->backbinding_list);
+ if (err < 0)
+ return err;
+
+ ctx->level--;
+ break;
+ case NFT_BIND_SET:
+ if (binding->use == 0)
+ break;
+
+ /* no level update for sets. */
+ err = nft_chain_validate_backtrack(ctx,
+ &binding->from.set->backbinding_list);
+ if (err < 0)
+ return err;
+
+ break;
+ }
+ }
+
+ return 0;
+}
+
+static int nft_chain_validate_incremental(struct net *net,
+ const struct nft_chain *chain)
+{
+ struct nft_validate_ctx validate_ctx = {
+ .chain = chain,
+ };
+ uint32_t i;
+ int err;
+
+ validate_ctx.max_basechains = 16;
+ validate_ctx.basechain = kcalloc(16, sizeof(struct nft_chain *), GFP_KERNEL);
+ if (!validate_ctx.basechain)
+ return -ENOMEM;
+
+ if (nft_is_base_chain(chain)) {
+ err = nft_basechain_array_add(&validate_ctx, chain);
+ if (err < 0) {
+ kfree(validate_ctx.basechain);
+ return -ENOMEM;
+ }
+ } else {
+ validate_ctx.level = 1;
+ err = nft_chain_validate_backtrack(&validate_ctx,
+ &chain->backbinding_list);
+ if (err < 0) {
+ kfree(validate_ctx.basechain);
+ return err;
+ }
+ }
+
+ for (i = 0; i < validate_ctx.num_basechains; i++) {
+ struct nft_ctx ctx = {
+ .net = net,
+ .family = chain->table->family,
+ .table = chain->table,
+ .chain = (struct nft_chain *)validate_ctx.basechain[i],
+ .level = validate_ctx.max_level,
+ };
+
+ if (WARN_ON_ONCE(!nft_is_base_chain(validate_ctx.basechain[i])))
+ continue;
+
+ err = nft_chain_validate(&ctx, chain);
+ if (err < 0)
+ break;
+ }
+
+ kfree(validate_ctx.basechain);
+
+ return err;
+}
+
+static int nft_validate_incremental(struct net *net, struct nft_table *table)
+{
+ struct nftables_pernet *nft_net = nft_pernet(net);
+ struct nft_chain *chain, *next;
+ int err;
+
+ err = 0;
+ list_for_each_entry_safe(chain, next, &nft_net->validate_list, validate_list) {
+ if (chain->table != table)
+ continue;
+
+ if (err >= 0)
+ err = nft_chain_validate_incremental(net, chain);
+
+ list_del(&chain->validate_list);
+ chain->validate = 0;
+ }
+
+ return err;
+}
+
static void nft_validate_chain_release(struct net *net)
{
struct nftables_pernet *nft_net = nft_pernet(net);
@@ -10422,12 +10584,36 @@ static int nf_tables_validate(struct net *net)
nft_validate_state_update(table, NFT_VALIDATE_DO);
fallthrough;
case NFT_VALIDATE_DO:
- err = nft_table_validate(net, table);
- if (err < 0) {
- if (err == -EINTR)
- goto err_eintr;
+ /* If this table is new, then this is the initial
+ * ruleset restore, perform full table validation,
+ * otherwise, perform incremental validation.
+ */
+ if (!nft_is_active(net, table)) {
+ err = nft_table_validate(net, table);
+ if (err < 0) {
+ if (err == -EINTR)
+ goto err_eintr;
- return -EAGAIN;
+ return -EAGAIN;
+ }
+ } else {
+ err = nft_validate_incremental(net, table);
+ if (err < 0) {
+ if (err != -ENOMEM && err != -ELOOP)
+ return -EAGAIN;
+
+ /* Either no memory or it cannot reach
+ * basechain, then fallback to full
+ * validation.
+ */
+ err = nft_table_validate(net, table);
+ if (err < 0) {
+ if (err == -EINTR)
+ goto err_eintr;
+
+ return -EAGAIN;
+ }
+ }
}
nft_validate_state_update(table, NFT_VALIDATE_SKIP);
break;
--
2.30.2
