Bug 2177197 - ACL subnet exclusion is not optimally traslated to ovs flows
Summary: ACL subnet exclusion is not optimally traslated to ovs flows
Keywords:
Status: MODIFIED
Alias: None
Product: Red Hat Enterprise Linux Fast Datapath
Classification: Red Hat
Component: ovn23.06
Version: RHEL 8.0
Hardware: Unspecified
OS: Unspecified
high
unspecified
Target Milestone: ---
: ---
Assignee: Ilya Maximets
QA Contact: Ehsan Elahi
URL:
Whiteboard:
Depends On:
Blocks:
TreeView+ depends on / blocked
 
Reported: 2023-03-10 11:28 UTC by Nadia Pinaeva
Modified: 2023-07-13 07:35 UTC (History)
6 users (show)

Fixed In Version: ovn23.06-23.06.0-beta.118.el8fdp
Doc Type: If docs needed, set a value
Doc Text:
Clone Of:
Environment:
Last Closed:
Target Upstream Version:
Embargoed:


Attachments (Terms of Use)


Links
System ID Private Priority Status Summary Last Updated
Red Hat Issue Tracker FD-2727 0 None None None 2023-03-10 11:30:05 UTC

Description Nadia Pinaeva 2023-03-10 11:28:20 UTC
Description of problem:
ACLs with Match like "ip4.src == 172.168.0.0/16 && ip4.src != {172.168.13.0/24}" are translated into positive subnet match.
When there is only 1 subnet in the exclusion, it works fine, but if we add a second subnet, it will generate more flows than actually needed (see the following example).

"ip4.src == 172.168.0.0/16 && ip4.src != {172.168.13.0/24, 172.168.14.128/28}"
will be translated to 72 flows, when the optimal number is 12.

in the following note the first 2 octets are omitted
172.168.13.0/24 =           00001101.*
172.168.14.128/28 =         00001110.1000****

Expected 12 flows to be:
                            ******10.***1*
                            ******10.**1*
                            ******10.*1*
172.168.0.0/255.255.1.0 =   ******10.0*
172.168.2.0/255.255.2.0 =   ******11.*
172.168.0.0/255.255.2.0 =   ******00.*
172.168.0.0/255.255.4.0 =   *****0**.*
172.168.0.0/255.255.8.0 =   ****0***.*
172.168.16.0/255.255.16.0 = ***1****.*
172.168.32.0/255.255.32.0 = **1*****.*
172.168.64.0/255.255.64.0 = *1******.*
       172.168.128.0/17=    1*******.* 

Actually have 72 flows, here is a subset of them
172.168.0.16/255.255.1.16 = *******0.***1****
172.168.0.32/255.255.1.32 = *******0.**1*****
172.168.0.64/255.255.1.64 = *******0.*1******
172.168.0.0/255.255.1.128 = *******0.0*******
172.168.2.16/255.255.2.16 = ******1*.***1****
172.168.2.32/255.255.2.32 = ******1*.**1*****
172.168.2.64/255.255.2.64 = ******1*.*1******
172.168.2.0/255.255.2.128 = ******1*.0*******
172.168.0.0/255.255.3.0 =   ******00.*
172.168.3.0/255.255.3.0 =   ******11.*
172.168.0.0/255.255.4.0 =   *****0**.*
172.168.0.16/255.255.4.16 = *****0**.***1****
172.168.0.32/255.255.4.32 = *****0**.**1*****
172.168.0.64/255.255.4.64 = *****0**.*1******
172.168.0.0/255.255.4.128 = *****0**.0*******
172.168.0.0/255.255.5.0   = *****0*0.*
172.168.1.0/255.255.5.0   = *****0*1.*
172.168.0.0/255.255.6.0   = *****00*.*
172.168.2.0/255.255.6.0   = *****01*.*

looks like some of the flows can be deleted, e.g.
172.168.0.0/255.255.4.0 =   *****0**.*
172.168.0.16/255.255.4.16 = *****0**.***1****
172.168.0.32/255.255.4.32 = *****0**.**1*****
172.168.0.64/255.255.4.64 = *****0**.*1******
172.168.0.0/255.255.4.128 = *****0**.0*******
only the first rule may be left


Additional info:
I used a python lib to compare the subnet exclusion results, e.g. for the provided example
```
from ipaddress import ip_network, collapse_addresses

n1 = ip_network('172.168.0.0/16', False)
n2 = ip_network('172.168.13.0/24', False)
n3 = ip_network('172.168.14.128/28', False)

l = []
for i in n1.address_exclude(n2):
    if n3.subnet_of(i):
        l.extend(list(i.address_exclude(n3)))
    else:
        l.append(i)
print(l, len(l))
```
the subnets will be different from what ovn generates, but the number is the same, and the logic is somewhat similar. This is binary view of what the script generates for a given example.

172.168.128.0/17 =  1*******.*
172.168.64.0/18 =   01******.*
172.168.32.0/19 =   001*****.*
172.168.16.0/20 =   0001****.*
172.168.0.0/21 =    00000***.*
172.168.8.0/22 =    000010**.*
172.168.12.0/24 =   00001100.*
172.168.15.0/24 =   00001111.*
172.168.14.0/25 =   00001110.0*
172.168.14.192/26 = 00001110.11*
172.168.14.160/27 = 00001110.101*
172.168.14.144/28 = 00001110.1001*

Comment 1 Ilya Maximets 2023-03-17 19:26:26 UTC
I found a fairly simple way to get rid of most of the unnecessary flows
and posted a patch here:
  https://patchwork.ozlabs.org/project/ovn/patch/20230317192509.1513631-1-i.maximets@ovn.org/

Comment 2 Ilya Maximets 2023-03-17 19:29:43 UTC
Proposed change ends up with 16 flows in the provided example instead
of 79 with current OVN.

$ ./tests/ovstest  test-ovn expr-to-flows <<< "ip4.src == 172.168.0.0/16 && ip4.src != {172.168.13.0/24, 172.168.14.128/28}" | sort
ip,nw_src=172.168.0.0/255.255.1.128
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.8.0
ip,nw_src=172.168.0.16/255.255.1.16
ip,nw_src=172.168.0.32/255.255.1.32
ip,nw_src=172.168.0.64/255.255.1.64
ip,nw_src=172.168.128.0/17
ip,nw_src=172.168.16.0/255.255.16.0
ip,nw_src=172.168.2.0/255.255.2.128
ip,nw_src=172.168.2.16/255.255.2.16
ip,nw_src=172.168.2.32/255.255.2.32
ip,nw_src=172.168.2.64/255.255.2.64
ip,nw_src=172.168.3.0/255.255.3.0
ip,nw_src=172.168.32.0/255.255.32.0
ip,nw_src=172.168.64.0/255.255.64.0

Comment 3 Ilya Maximets 2023-03-20 12:31:30 UTC
Posted v2 including also aggregation of sub-expressions, e.g.
aggregation of multiple subnets into larger ones:
  https://patchwork.ozlabs.org/project/ovn/list/?series=347051

Comment 4 Ilya Maximets 2023-03-27 12:33:26 UTC
Moving back to ASSIGNED as it requires a bit more work.

Comment 5 Ilya Maximets 2023-03-29 16:44:24 UTC
v3 is posted for review:
  https://patchwork.ozlabs.org/project/ovn/list/?series=348628

Comment 6 OVN Bot 2023-05-11 04:10:33 UTC
ovn23.06 fast-datapath-rhel-9 clone created at https://bugzilla.redhat.com/show_bug.cgi?id=2203018


Note You need to log in before you can comment on or make changes to this bug.