On 3/17/23 20:25, Ilya Maximets wrote:
> While crushing OR expressions, OVN removes exact replicas of sub
> expressions. However, there could be many CMP expressions that are
> supersets of each other. These are most likely to be created as a
> result of cross-product while expanding brackets in the AND expression
> in crush_and_numeric(), i.e. while converting
> "x && (a0 || a1) && (b0 || b1)" into "xa0b0 || xa0b1 || xa1b0 || xa1b1".
>
> Replacing the removal of exact duplicates with scan and removal of
> supersets of other existing sub-expressions to reduce the amount of
> generated flows. This operation is less efficient in comparison,
> but should save time later, since less flows will be generated.
>
> Example:
>
> "ip4.src == 172.168.0.0/16 && ip4.src!={172.168.13.0/24, 172.168.15.0/24}"
>
> Processing of this expression yields 42 flows:
>
> $ ./tests/ovstest test-ovn expr-to-flows <<< "$expr"
>
> ip,nw_src=172.168.0.0/255.255.1.0
> ip,nw_src=172.168.0.0/255.255.10.0
> ip,nw_src=172.168.0.0/255.255.12.0
> ip,nw_src=172.168.0.0/255.255.3.0
> ip,nw_src=172.168.0.0/255.255.4.0
> ip,nw_src=172.168.0.0/255.255.5.0
> ip,nw_src=172.168.0.0/255.255.6.0
> ip,nw_src=172.168.0.0/255.255.8.0
> ip,nw_src=172.168.0.0/255.255.9.0
> ip,nw_src=172.168.128.0/17
> <... 32 more flows ...>
>
> We can see that many flows above do overlap, e.g. 255.255.3.0
> mask is a superset of 255.255.1.0. Everything that matches
> 255.255.3.0, will match 255.255.1.0 as well (the value is the same).
>
> By removing all the unnecessary supersets, the set of flows can
> be reduced from 42 down to 7:
>
> ip,nw_src=172.168.0.0/255.255.1.0
> ip,nw_src=172.168.0.0/255.255.4.0
> ip,nw_src=172.168.0.0/255.255.8.0
> ip,nw_src=172.168.128.0/17
> ip,nw_src=172.168.16.0/255.255.16.0
> ip,nw_src=172.168.32.0/255.255.32.0
> ip,nw_src=172.168.64.0/255.255.64.0
>
> This change should be particularly useful for expressions with
> inequality checks, like the one above. Such expressions are
> frequent among ACL rules.
>
> Reported-at: https://bugzilla.redhat.com/show_bug.cgi?id=2177197
> Reported-by: Nadia Pinaeva <npina...@redhat.com>
> Signed-off-by: Ilya Maximets <i.maxim...@ovn.org>
> ---
> lib/expr.c | 128 ++++++++++++++++++++++++++++++-----------------------
> 1 file changed, 73 insertions(+), 55 deletions(-)
One more example:
Before:
$ ./tests/ovstest test-ovn expr-to-flows <<< "ip4.src != {172.168.13.0/24,
172.168.14.0/24, 172.168.15.0/24}" | wc -l
2894
After:
$ ./tests/ovstest test-ovn expr-to-flows <<< "ip4.src != {172.168.13.0/24,
172.168.14.0/24, 172.168.15.0/24}" | wc -l
23
$ ./tests/ovstest test-ovn expr-to-flows <<< "ip4.src != {172.168.13.0/24,
172.168.14.0/24, 172.168.15.0/24}" | sort
ip,nw_src=0.0.0.0/0.0.3.0
ip,nw_src=0.0.0.0/0.0.4.0
ip,nw_src=0.0.0.0/0.0.8.0
ip,nw_src=0.0.0.0/0.128.0.0
ip,nw_src=0.0.0.0/0.32.0.0
ip,nw_src=0.0.0.0/0.8.0.0
ip,nw_src=0.0.0.0/1
ip,nw_src=0.0.0.0/32.0.0.0
ip,nw_src=0.0.0.0/4.0.0.0
ip,nw_src=0.0.0.0/8.0.0.0
ip,nw_src=0.0.128.0/0.0.128.0
ip,nw_src=0.0.16.0/0.0.16.0
ip,nw_src=0.0.32.0/0.0.32.0
ip,nw_src=0.0.64.0/0.0.64.0
ip,nw_src=0.1.0.0/0.1.0.0
ip,nw_src=0.16.0.0/0.16.0.0
ip,nw_src=0.2.0.0/0.2.0.0
ip,nw_src=0.4.0.0/0.4.0.0
ip,nw_src=0.64.0.0/0.64.0.0
ip,nw_src=1.0.0.0/1.0.0.0
ip,nw_src=16.0.0.0/16.0.0.0
ip,nw_src=2.0.0.0/2.0.0.0
ip,nw_src=64.0.0.0/64.0.0.0
Best regards, Ilya Maximets.
_______________________________________________
dev mailing list
d...@openvswitch.org
https://mail.openvswitch.org/mailman/listinfo/ovs-dev
