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