[nft,0/3] ruleset optimization infrastructure

Hi,

This patchset adds a new -o/--optimize option to enable ruleset
optimization.

The ruleset optimization first loads the ruleset in "dry run" mode to
validate that the original ruleset is correct. Then, on a second pass it
performs the ruleset optimization before adding the rules into the
kernel.

This infrastructure collects the statements that are used in rules. Then,
it builds a matrix of rules vs. statements. Then, it looks for common
statements in consecutive rules that are candidate to be merged. Finally,
it merges rules.

From libnftables perspective, there is a new API to enable this feature:

  bool nft_ctx_get_optimize(struct nft_ctx *ctx);
  void nft_ctx_set_optimize(struct nft_ctx *ctx, bool optimize);

This patchset adds support for three optimizations:

1) Collapse rules matching on a single selector into a set, which
   transforms:

  ip daddr 192.168.0.1 counter accept
  ip daddr 192.168.0.2 counter accept
  ip daddr 192.168.0.3 counter accept

  into:

  ip daddr { 192.168.0.1, 192.168.0.2, 192.168.0.3 } counter packets 0 bytes 0 accept

2) Collapse rules with the same selectors into a concatenation, which
   transforms:

   meta iifname eth1 ip saddr 1.1.1.1 ip daddr 2.2.2.3 accept
   meta iifname eth1 ip saddr 1.1.1.2 ip daddr 2.2.2.5 accept
   meta iifname eth2 ip saddr 1.1.1.3 ip daddr 2.2.2.6 accept

   into:

   meta iifname . ip saddr . ip daddr { eth1 . 1.1.1.1 . 2.2.2.6, eth1 . 1.1.1.2 . 2.2.2.5 , eth1 . 1.1.1.3 . 2.2.2.6 } accept

3) Collapse rules with same selector but different verdic into verdict map,
   which transforms:

   ct state invalid drop
   ct state established,related accept

   into:

   ct state vmap { established : accept, related : accept, invalid : drop }

Comments welcome,
Thanks.

Pablo Neira Ayuso (3):
  src: add ruleset optimization infrastructure
  optimize: merge rules with same selectors into a concatenation
  optimize: merge same selector with different verdict into verdict map

 include/nftables.h             |   4 +
 include/nftables/libnftables.h |   5 +
 src/Makefile.am                |   1 +
 src/libnftables.c              |  41 ++-
 src/libnftables.map            |   5 +
 src/main.c                     |   9 +-
 src/optimize.c                 | 524 +++++++++++++++++++++++++++++++++
 7 files changed, 586 insertions(+), 3 deletions(-)
 create mode 100644 src/optimize.c

On 12/15/21 20:56, Pablo Neira Ayuso wrote:
> Hi,
> 
> This patchset adds a new -o/--optimize option to enable ruleset
> optimization.
> 

Thanks for working on this. From what I see in the community, this feature will 
be of high value to some folks: users often struggle with doing this kind of 
optimizations by hand.

> The ruleset optimization first loads the ruleset in "dry run" mode to
> validate that the original ruleset is correct. Then, on a second pass it
> performs the ruleset optimization before adding the rules into the
> kernel.
> 

Could you please describe how to work with this if all I want is to check how an 
optimized version of my ruleset would look like, but not load it into the kernel?

The use case would be: I just need a diff between my ruleset.nft file and 
whatever the optimized version would be, without performing any actual change.

Of course this can be added later on if not supported in this patch.

> This infrastructure collects the statements that are used in rules. Then,
> it builds a matrix of rules vs. statements. Then, it looks for common
> statements in consecutive rules that are candidate to be merged. Finally,
> it merges rules.

clever!

Is this infra extensible enough to support scanning non-adjacent rules in the 
future?

ie, being able to transform:

* ip daddr 1.1.1.1 counter accept
* tcp dport 80 accept
* ip daddr 2.2.2.2 counter accept

into:

* ip daddr { 1.1.1., 2.2.2.2 } counter accept
* tcp dport 80 accept

Hi Arturo,

On Thu, Dec 16, 2021 at 12:54:02PM +0100, Arturo Borrero Gonzalez wrote:
> On 12/15/21 20:56, Pablo Neira Ayuso wrote:
> > Hi,
> > 
> > This patchset adds a new -o/--optimize option to enable ruleset
> > optimization.
> > 
> 
> Thanks for working on this. From what I see in the community, this feature
> will be of high value to some folks: users often struggle with doing this
> kind of optimizations by hand.
>
> > The ruleset optimization first loads the ruleset in "dry run" mode to
> > validate that the original ruleset is correct. Then, on a second pass it
> > performs the ruleset optimization before adding the rules into the
> > kernel.
> > 
> 
> Could you please describe how to work with this if all I want is to check
> how an optimized version of my ruleset would look like, but not load it into
> the kernel?
>
> The use case would be: I just need a diff between my ruleset.nft file and
> whatever the optimized version would be, without performing any actual
> change.

This is feasible. I could probably add a flags field instead of simple
boolean to the API so it is possible to specify an option such as:

        # nft -o offline -f ruleset.nft

which would print the ruleset listing without loading it.

> Of course this can be added later on if not supported in this patch.
>
> > This infrastructure collects the statements that are used in rules. Then,
> > it builds a matrix of rules vs. statements. Then, it looks for common
> > statements in consecutive rules that are candidate to be merged. Finally,
> > it merges rules.
> 
> clever!
> 
> Is this infra extensible enough to support scanning non-adjacent rules in
> the future?

This requires another step to group rules with the same statements
whenever possible, such routine would need to make sure that the rule
verdict is the same and that no stateful statements (eg. limit) is
used.

> ie, being able to transform:
> 
> * ip daddr 1.1.1.1 counter accept
> * tcp dport 80 accept
> * ip daddr 2.2.2.2 counter accept
> 
> into:
> 
> * ip daddr { 1.1.1.1, 2.2.2.2 } counter accept
> * tcp dport 80 accept

or even this:

* ip daddr . tcp dport { 1.1.1.1 . 0-65535, 2.2.2.2 . 0-65535, 0.0.0.0/0 . 80 } counter accept

but this requires a Linux kernel >= 5.6.

There are a few more transformations that come to my mind, such as
packing several snat/dnat rules into a map.

I'll be posting v2 of this patchset with many fixes and tests soon.