[PATCH nft 0/5] relax cache requirements, speed up incremental updates

[PATCH nft 0/5] relax cache requirements, speed up incremental updates

[Pablo Neira Ayuso]

Hi,

The following patchset relaxes cache requirements, this is based on the
observation that objects are fetched to report errors and provide hints.

This is a new attempt to speed up incremental updates following a
different approach, after reverting:

  e791dbe109b6 ("cache: recycle existing cache with incremental updates")

which is fragile because cache consistency checking needs more, it should
be still possible to explore in the future, but this seems a more simple
approach at this stage.

This is passing tests/shell and tests/py.

Pablo Neira Ayuso (5):
  cache: rule by index requires full cache
  cache: populate chains on demand from error path
  cache: populate objecs on demand from error path
  cache: populate flowtable on demand from error path
  cache: do not fetch set inconditionally on delete

 include/cache.h |  1 -
 src/cache.c     | 23 ++++++-----------------
 src/cmd.c       | 23 +++++++++++++++++++++++
 3 files changed, 29 insertions(+), 18 deletions(-)

-- 
2.30.2

[PATCH nft 1/5] cache: rule by index requires full cache

[Pablo Neira Ayuso]

In preparation for on-demand cache population with errors, set on
NFT_CACHE_FULL if rule index is used since this requires a full cache
with rules.

This is not a fix, follow up patches relax cache requirements, add
this patch in first place to make sure index does not break.

Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
 src/cache.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/src/cache.c b/src/cache.c
index e88cbae2ad95..42e60dfa1286 100644
--- a/src/cache.c
+++ b/src/cache.c
@@ -68,7 +68,7 @@ static unsigned int evaluate_cache_add(struct cmd *cmd, unsigned int flags)
 
 		if (cmd->handle.index.id ||
 		    cmd->handle.position.id)
-			flags |= NFT_CACHE_RULE | NFT_CACHE_UPDATE;
+			flags |= NFT_CACHE_FULL | NFT_CACHE_UPDATE;
 		break;
 	default:
 		break;
-- 
2.30.2

[PATCH nft 2/5] cache: populate chains on demand from error path

[Pablo Neira Ayuso]

Updates on verdict maps that require many non-base chains are slowed
down due to fetching existing non-base chains into the cache.

Chains are only required for error reporting hints if kernel reports
ENOENT. Populate the cache from this error path only.

Similar approach already exists from rule ENOENT error path since:

  deb7c5927fad ("cmd: add misspelling suggestions for rule commands")

however, NFT_CACHE_CHAIN was toggled inconditionally for rule
commands, rendering this on-demand cache population useless.

before this patch, running Neels' nft_slew benchmark (peak values):

  created idx 4992 in 52587950 ns   (128 in 7122 ms)
  ...
  deleted idx  128 in 43542500 ns   (127 in 6187 ms)

after this patch:

  created idx 4992 in 11361299 ns   (128 in 1612 ms)
  ...
  deleted idx 1664 in  5239633 ns   (128 in 733 ms)

Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
v2: fetch cache for EOPNOTSUPP errors too.
    update nft_slew results.

 include/cache.h |  1 -
 src/cache.c     |  4 ----
 src/cmd.c       | 11 +++++++++++
 3 files changed, 11 insertions(+), 5 deletions(-)

diff --git a/include/cache.h b/include/cache.h
index 8ca4a9a79c03..44e8430ce1fd 100644
--- a/include/cache.h
+++ b/include/cache.h
@@ -31,7 +31,6 @@ enum cache_level_flags {
 				  NFT_CACHE_SET_BIT |
 				  NFT_CACHE_SETELEM_BIT,
 	NFT_CACHE_RULE		= NFT_CACHE_TABLE_BIT |
-				  NFT_CACHE_CHAIN_BIT |
 				  NFT_CACHE_RULE_BIT,
 	NFT_CACHE_FULL		= __NFT_CACHE_MAX_BIT - 1,
 	NFT_CACHE_TERSE		= (1 << 27),
diff --git a/src/cache.c b/src/cache.c
index 42e60dfa1286..36c6f12d8720 100644
--- a/src/cache.c
+++ b/src/cache.c
@@ -30,7 +30,6 @@ static unsigned int evaluate_cache_add(struct cmd *cmd, unsigned int flags)
 			break;
 
 		flags |= NFT_CACHE_TABLE |
-			 NFT_CACHE_CHAIN |
 			 NFT_CACHE_SET |
 			 NFT_CACHE_OBJECT |
 			 NFT_CACHE_FLOWTABLE;
@@ -54,14 +53,12 @@ static unsigned int evaluate_cache_add(struct cmd *cmd, unsigned int flags)
 		break;
 	case CMD_OBJ_ELEMENTS:
 		flags |= NFT_CACHE_TABLE |
-			 NFT_CACHE_CHAIN |
 			 NFT_CACHE_SET |
 			 NFT_CACHE_OBJECT |
 			 NFT_CACHE_SETELEM_MAYBE;
 		break;
 	case CMD_OBJ_RULE:
 		flags |= NFT_CACHE_TABLE |
-			 NFT_CACHE_CHAIN |
 			 NFT_CACHE_SET |
 			 NFT_CACHE_OBJECT |
 			 NFT_CACHE_FLOWTABLE;
@@ -435,7 +432,6 @@ int nft_cache_evaluate(struct nft_ctx *nft, struct list_head *cmds,
 		case CMD_DELETE:
 		case CMD_DESTROY:
 			flags |= NFT_CACHE_TABLE |
-				 NFT_CACHE_CHAIN |
 				 NFT_CACHE_SET |
 				 NFT_CACHE_FLOWTABLE |
 				 NFT_CACHE_OBJECT;
diff --git a/src/cmd.c b/src/cmd.c
index 37d93abc2cd4..381f404266de 100644
--- a/src/cmd.c
+++ b/src/cmd.c
@@ -75,6 +75,10 @@ static int nft_cmd_enoent_chain(struct netlink_ctx *ctx, const struct cmd *cmd,
 	if (!cmd->handle.chain.name)
 		return 0;
 
+	if (nft_cache_update(ctx->nft, NFT_CACHE_TABLE | NFT_CACHE_CHAIN,
+			     ctx->msgs, NULL) < 0)
+		return 0;
+
 	chain = chain_lookup_fuzzy(&cmd->handle, &ctx->nft->cache, &table);
 	/* check table first. */
 	if (!table)
@@ -271,6 +275,13 @@ static int nft_cmd_chain_error(struct netlink_ctx *ctx, struct cmd *cmd,
 			return netlink_io_error(ctx, &chain->priority.loc,
 						"Chains of type \"nat\" must have a priority value above -200");
 
+		if (nft_cache_update(ctx->nft, NFT_CACHE_TABLE | NFT_CACHE_CHAIN,
+				     ctx->msgs, NULL) < 0) {
+			return netlink_io_error(ctx, &chain->loc,
+						"Chain of type \"%s\" is not supported, perhaps kernel support is missing?",
+						chain->type.str);
+		}
+
 		table = table_cache_find(&ctx->nft->cache.table_cache,
 					 cmd->handle.table.name, cmd->handle.family);
 		if (table) {
-- 
2.30.2

[PATCH nft 3/5] cache: populate objecs on demand from error path

[Pablo Neira Ayuso]

Objects are only required for error reporting hints if kernel reports
ENOENT. Populate the cache from this error path only.

Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
 src/cache.c | 6 +-----
 src/cmd.c   | 4 ++++
 2 files changed, 5 insertions(+), 5 deletions(-)

diff --git a/src/cache.c b/src/cache.c
index 36c6f12d8720..6ad8e2587806 100644
--- a/src/cache.c
+++ b/src/cache.c
@@ -31,7 +31,6 @@ static unsigned int evaluate_cache_add(struct cmd *cmd, unsigned int flags)
 
 		flags |= NFT_CACHE_TABLE |
 			 NFT_CACHE_SET |
-			 NFT_CACHE_OBJECT |
 			 NFT_CACHE_FLOWTABLE;
 		list_for_each_entry(set, &cmd->table->sets, list) {
 			if (set->automerge)
@@ -54,13 +53,11 @@ static unsigned int evaluate_cache_add(struct cmd *cmd, unsigned int flags)
 	case CMD_OBJ_ELEMENTS:
 		flags |= NFT_CACHE_TABLE |
 			 NFT_CACHE_SET |
-			 NFT_CACHE_OBJECT |
 			 NFT_CACHE_SETELEM_MAYBE;
 		break;
 	case CMD_OBJ_RULE:
 		flags |= NFT_CACHE_TABLE |
 			 NFT_CACHE_SET |
-			 NFT_CACHE_OBJECT |
 			 NFT_CACHE_FLOWTABLE;
 
 		if (cmd->handle.index.id ||
@@ -433,8 +430,7 @@ int nft_cache_evaluate(struct nft_ctx *nft, struct list_head *cmds,
 		case CMD_DESTROY:
 			flags |= NFT_CACHE_TABLE |
 				 NFT_CACHE_SET |
-				 NFT_CACHE_FLOWTABLE |
-				 NFT_CACHE_OBJECT;
+				 NFT_CACHE_FLOWTABLE;
 
 			flags = evaluate_cache_del(cmd, flags);
 			break;
diff --git a/src/cmd.c b/src/cmd.c
index 381f404266de..507796bdd6a8 100644
--- a/src/cmd.c
+++ b/src/cmd.c
@@ -169,6 +169,10 @@ static int nft_cmd_enoent_obj(struct netlink_ctx *ctx, const struct cmd *cmd,
 	if (!cmd->handle.obj.name)
 		return 0;
 
+	if (nft_cache_update(ctx->nft, NFT_CACHE_TABLE | NFT_CACHE_OBJECT,
+			     ctx->msgs, NULL) < 0)
+		return 0;
+
 	obj = obj_lookup_fuzzy(cmd->handle.obj.name, &ctx->nft->cache, &table);
 	/* check table first. */
 	if (!table)
-- 
2.30.2

[PATCH nft 4/5] cache: populate flowtable on demand from error path

[Pablo Neira Ayuso]

Flowtables are only required for error reporting hints if kernel reports
ENOENT. Populate the cache from this error path only.

Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
 src/cache.c | 9 +++------
 src/cmd.c   | 4 ++++
 2 files changed, 7 insertions(+), 6 deletions(-)

diff --git a/src/cache.c b/src/cache.c
index 6ad8e2587806..1fc03f2bbe50 100644
--- a/src/cache.c
+++ b/src/cache.c
@@ -30,8 +30,7 @@ static unsigned int evaluate_cache_add(struct cmd *cmd, unsigned int flags)
 			break;
 
 		flags |= NFT_CACHE_TABLE |
-			 NFT_CACHE_SET |
-			 NFT_CACHE_FLOWTABLE;
+			 NFT_CACHE_SET;
 		list_for_each_entry(set, &cmd->table->sets, list) {
 			if (set->automerge)
 				 flags |= NFT_CACHE_SETELEM_MAYBE;
@@ -57,8 +56,7 @@ static unsigned int evaluate_cache_add(struct cmd *cmd, unsigned int flags)
 		break;
 	case CMD_OBJ_RULE:
 		flags |= NFT_CACHE_TABLE |
-			 NFT_CACHE_SET |
-			 NFT_CACHE_FLOWTABLE;
+			 NFT_CACHE_SET;
 
 		if (cmd->handle.index.id ||
 		    cmd->handle.position.id)
@@ -429,8 +427,7 @@ int nft_cache_evaluate(struct nft_ctx *nft, struct list_head *cmds,
 		case CMD_DELETE:
 		case CMD_DESTROY:
 			flags |= NFT_CACHE_TABLE |
-				 NFT_CACHE_SET |
-				 NFT_CACHE_FLOWTABLE;
+				 NFT_CACHE_SET;
 
 			flags = evaluate_cache_del(cmd, flags);
 			break;
diff --git a/src/cmd.c b/src/cmd.c
index 507796bdd6a8..e64171e7c4df 100644
--- a/src/cmd.c
+++ b/src/cmd.c
@@ -201,6 +201,10 @@ static int nft_cmd_enoent_flowtable(struct netlink_ctx *ctx,
 	if (!cmd->handle.flowtable.name)
 		return 0;
 
+	if (nft_cache_update(ctx->nft, NFT_CACHE_TABLE | NFT_CACHE_FLOWTABLE,
+			     ctx->msgs, NULL) < 0)
+		return 0;
+
 	ft = flowtable_lookup_fuzzy(cmd->handle.flowtable.name,
 				    &ctx->nft->cache, &table);
 	/* check table first. */
-- 
2.30.2

[PATCH nft 5/5] cache: do not fetch set inconditionally on delete

[Pablo Neira Ayuso]

This is only required to remove elements, relax cache requirements for
anything else.

Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>
---
 src/cache.c | 6 +++---
 src/cmd.c   | 4 ++++
 2 files changed, 7 insertions(+), 3 deletions(-)

diff --git a/src/cache.c b/src/cache.c
index 1fc03f2bbe50..233147649263 100644
--- a/src/cache.c
+++ b/src/cache.c
@@ -73,7 +73,8 @@ static unsigned int evaluate_cache_del(struct cmd *cmd, unsigned int flags)
 {
 	switch (cmd->obj) {
 	case CMD_OBJ_ELEMENTS:
-		flags |= NFT_CACHE_SETELEM_MAYBE;
+		flags |= NFT_CACHE_SET |
+			 NFT_CACHE_SETELEM_MAYBE;
 		break;
 	default:
 		break;
@@ -426,8 +427,7 @@ int nft_cache_evaluate(struct nft_ctx *nft, struct list_head *cmds,
 			break;
 		case CMD_DELETE:
 		case CMD_DESTROY:
-			flags |= NFT_CACHE_TABLE |
-				 NFT_CACHE_SET;
+			flags |= NFT_CACHE_TABLE;
 
 			flags = evaluate_cache_del(cmd, flags);
 			break;
diff --git a/src/cmd.c b/src/cmd.c
index e64171e7c4df..9a572b5660c7 100644
--- a/src/cmd.c
+++ b/src/cmd.c
@@ -140,6 +140,10 @@ static int nft_cmd_enoent_set(struct netlink_ctx *ctx, const struct cmd *cmd,
 	if (!cmd->handle.set.name)
 		return 0;
 
+	if (nft_cache_update(ctx->nft, NFT_CACHE_TABLE | NFT_CACHE_SET,
+			     ctx->msgs, NULL) < 0)
+		return 0;
+
 	set = set_lookup_fuzzy(cmd->handle.set.name, &ctx->nft->cache, &table);
 	/* check table first. */
 	if (!table)
-- 
2.30.2

Re: [PATCH nft 0/5] relax cache requirements, speed up incremental updates

[Phil Sutter]

On Thu, Aug 15, 2024 at 01:37:07PM +0200, Pablo Neira Ayuso wrote:
> Hi,
> 
> The following patchset relaxes cache requirements, this is based on the
> observation that objects are fetched to report errors and provide hints.

This is nice as it applies to error path only, though the second cache
fetch is prone to race conditions. Did you consider retrying the whole
transaction with beefed-up cache in error case? I was about to mention
how it nicely integrates with transaction refresh in ERESTART case, but
then realized this is iptables code and nft doesn't retry in that case?!

Cheers, Phil

Re: [PATCH nft 0/5] relax cache requirements, speed up incremental updates

[Pablo Neira Ayuso]

On Thu, Aug 15, 2024 at 02:25:15PM +0200, Phil Sutter wrote:
> On Thu, Aug 15, 2024 at 01:37:07PM +0200, Pablo Neira Ayuso wrote:
> > Hi,
> > 
> > The following patchset relaxes cache requirements, this is based on the
> > observation that objects are fetched to report errors and provide hints.
> 
> This is nice as it applies to error path only, though the second cache
> fetch is prone to race conditions.

The call to nft_cache_update() ensures cache is consistent, old cache
is dropped and a new consistent cache is obtained. The hint could be
misleading (worst case) though since the cache could have different
generation ID that the transaction itself, but it is just a hint.

> Did you consider retrying the whole transaction with beefed-up cache
> in error case?

Why retry? I am assuming a batch where the user made a mistake, retry
will fail again.

> I was about to mention how it nicely integrates with transaction
> refresh in ERESTART case, but then realized this is iptables code
> and nft doesn't retry in that case?!

I think you are talking about different scenario, that is, userspace
sends an update but generation ID mismatches, kernel reports ERESTART
and nftables revamps, this is to catch an interference with another
process, that needs to be done in nft, but it is a different issue.

Re: [PATCH nft 0/5] relax cache requirements, speed up incremental updates

[Phil Sutter]

On Thu, Aug 15, 2024 at 02:46:02PM +0200, Pablo Neira Ayuso wrote:
> On Thu, Aug 15, 2024 at 02:25:15PM +0200, Phil Sutter wrote:
> > On Thu, Aug 15, 2024 at 01:37:07PM +0200, Pablo Neira Ayuso wrote:
> > > Hi,
> > > 
> > > The following patchset relaxes cache requirements, this is based on the
> > > observation that objects are fetched to report errors and provide hints.
> > 
> > This is nice as it applies to error path only, though the second cache
> > fetch is prone to race conditions.
> 
> The call to nft_cache_update() ensures cache is consistent, old cache
> is dropped and a new consistent cache is obtained. The hint could be
> misleading (worst case) though since the cache could have different
> generation ID that the transaction itself, but it is just a hint.
> 
> > Did you consider retrying the whole transaction with beefed-up cache
> > in error case?
> 
> Why retry? I am assuming a batch where the user made a mistake, retry
> will fail again.
> 
> > I was about to mention how it nicely integrates with transaction
> > refresh in ERESTART case, but then realized this is iptables code
> > and nft doesn't retry in that case?!
> 
> I think you are talking about different scenario, that is, userspace
> sends an update but generation ID mismatches, kernel reports ERESTART
> and nftables revamps, this is to catch an interference with another
> process, that needs to be done in nft, but it is a different issue.

Yes, I had incorrect error reporting in mind: Kernel reports ENOENT for
a chain which another process creates concurrently. The error path cache
update fetches the newly created chain and error reporting suggests to
use the exact chain user specified (I assume). It is indeed a
corner-case issue, though.

Cheers, Phil

Re: [PATCH nft 0/5] relax cache requirements, speed up incremental updates

[Pablo Neira Ayuso]

On Thu, Aug 15, 2024 at 03:10:13PM +0200, Phil Sutter wrote:
> On Thu, Aug 15, 2024 at 02:46:02PM +0200, Pablo Neira Ayuso wrote:
> > On Thu, Aug 15, 2024 at 02:25:15PM +0200, Phil Sutter wrote:
> > > On Thu, Aug 15, 2024 at 01:37:07PM +0200, Pablo Neira Ayuso wrote:
> > > > Hi,
> > > > 
> > > > The following patchset relaxes cache requirements, this is based on the
> > > > observation that objects are fetched to report errors and provide hints.
> > > 
> > > This is nice as it applies to error path only, though the second cache
> > > fetch is prone to race conditions.
> > 
> > The call to nft_cache_update() ensures cache is consistent, old cache
> > is dropped and a new consistent cache is obtained. The hint could be
> > misleading (worst case) though since the cache could have different
> > generation ID that the transaction itself, but it is just a hint.
> > 
> > > Did you consider retrying the whole transaction with beefed-up cache
> > > in error case?
> > 
> > Why retry? I am assuming a batch where the user made a mistake, retry
> > will fail again.
> > 
> > > I was about to mention how it nicely integrates with transaction
> > > refresh in ERESTART case, but then realized this is iptables code
> > > and nft doesn't retry in that case?!
> > 
> > I think you are talking about different scenario, that is, userspace
> > sends an update but generation ID mismatches, kernel reports ERESTART
> > and nftables revamps, this is to catch an interference with another
> > process, that needs to be done in nft, but it is a different issue.
> 
> Yes, I had incorrect error reporting in mind: Kernel reports ENOENT for
> a chain which another process creates concurrently. The error path cache
> update fetches the newly created chain and error reporting suggests to
> use the exact chain user specified (I assume).

IIRC, the fuzzy match code skips exact matches, worst case can be a
very hint.

> It is indeed a corner-case issue, though.

ERESTART handling can be useful for your rule index feature, where
consistency is fundamental to ensure that rule is added where the user
really wants.

Re: [PATCH nft 0/5] relax cache requirements, speed up incremental updates

[Eric Garver]

On Thu, Aug 15, 2024 at 01:37:07PM +0200, Pablo Neira Ayuso wrote:
> Hi,
> 
> The following patchset relaxes cache requirements, this is based on the
> observation that objects are fetched to report errors and provide hints.
> 
> This is a new attempt to speed up incremental updates following a
> different approach, after reverting:
> 
>   e791dbe109b6 ("cache: recycle existing cache with incremental updates")
> 
> which is fragile because cache consistency checking needs more, it should
> be still possible to explore in the future, but this seems a more simple
> approach at this stage.
> 
> This is passing tests/shell and tests/py.
> 
> Pablo Neira Ayuso (5):
>   cache: rule by index requires full cache
>   cache: populate chains on demand from error path
>   cache: populate objecs on demand from error path
>   cache: populate flowtable on demand from error path
>   cache: do not fetch set inconditionally on delete
> 
>  include/cache.h |  1 -
>  src/cache.c     | 23 ++++++-----------------
>  src/cmd.c       | 23 +++++++++++++++++++++++
>  3 files changed, 29 insertions(+), 18 deletions(-)

I applied this series to nft master and tested it against the latest
net-next and RHEL-9 kernels. No issues or regressions found.

Thanks Pablo!

Tested-by: Eric Garver <eric@garver.life>

Re: [PATCH nft 0/5] relax cache requirements, speed up incremental updates

[Pablo Neira Ayuso]

On Thu, Aug 15, 2024 at 11:08:58AM -0400, Eric Garver wrote:
> On Thu, Aug 15, 2024 at 01:37:07PM +0200, Pablo Neira Ayuso wrote:
> > Hi,
> > 
> > The following patchset relaxes cache requirements, this is based on the
> > observation that objects are fetched to report errors and provide hints.
> > 
> > This is a new attempt to speed up incremental updates following a
> > different approach, after reverting:
> > 
> >   e791dbe109b6 ("cache: recycle existing cache with incremental updates")
> > 
> > which is fragile because cache consistency checking needs more, it should
> > be still possible to explore in the future, but this seems a more simple
> > approach at this stage.
> > 
> > This is passing tests/shell and tests/py.
> > 
> > Pablo Neira Ayuso (5):
> >   cache: rule by index requires full cache
> >   cache: populate chains on demand from error path
> >   cache: populate objecs on demand from error path
> >   cache: populate flowtable on demand from error path
> >   cache: do not fetch set inconditionally on delete
> > 
> >  include/cache.h |  1 -
> >  src/cache.c     | 23 ++++++-----------------
> >  src/cmd.c       | 23 +++++++++++++++++++++++
> >  3 files changed, 29 insertions(+), 18 deletions(-)
> 
> I applied this series to nft master and tested it against the latest
> net-next and RHEL-9 kernels. No issues or regressions found.

Pushed out, thanks for testing.