[ovs-dev] [PATCH ovn v2] expr: crush the result of a sorted OR expression.

[Mark Michelson]

On 5/14/21 3:22 PM, Numan Siddique wrote:
> On Fri, May 14, 2021 at 3:19 PM Numan Siddique <numans at ovn.org> wrote:
>>
>> On Fri, May 7, 2021 at 9:03 AM Mark Michelson <mmichels at redhat.com> wrote:
>>>
>>> On 5/7/21 8:03 AM, Dumitru Ceara wrote:
>>>> On 5/6/21 10:49 PM, Mark Michelson wrote:
>>>>> ACLs and logical router policies leave the user open to crafting
>>>>> creative matches, such as this one:
>>>>>
>>>>> (ip4.dst == 172.27.0.65/32) && ip4.src == $as && ip4.dst != 10.128.0.0/11
>>>>>
>>>>> Ideally, that final part of the match would just be omitted, but in some
>>>>> CMSes this kind of thing gets generated. If we zero in on the ip4.dst
>>>>> part of the match, then initially, this gets parsed into the expression:
>>>>>
>>>>> ip4.dst == 0xac1b0041 && ip4.dst[21..31] != 0x54
>>>>>
>>>>> After annotation, simplification, and evaluating conditions, this
>>>>> becomes:
>>>>>
>>>>> ip4.dst == 0xac1b0041 && (ip4.dst[21] || ip4.dst[22] || !ip4.dst[23] ||
>>>>> ip4.dst[24] || !ip4.dst[25] || ip4.dst[26] || !ip4.dst[27] ||
>>>>> ip4.dst[28] || ip4.dst[29] || ip4.dst[30] || ip4.dst[31])
>>>>>
>>>>> At this point, we call expr_normalize(), which then calls expr_sort().
>>>>> expr_sort() attempts to turn expressions of the type
>>>>>
>>>>> a && (b || c || d)
>>>>>
>>>>> into
>>>>>
>>>>> ab && ac && ad
>>>>
>>>> Hmm, I guess you meant "ab || ac || ad" here, right?
>>>
>>> Whoops, yes that's correct. I'll amend the commit log when I merge if
>>> this gets approved. If a v3 is required for some other reason, then I'll
>>> amend the commit log in that version.
>>>
>>>>
>>>>>
>>>>> In this particular case, it turns the expression into
>>>>>
>>>>> (ip4.dst == 0xac1b0041 || ip4.dst == 0xac1b0041 || ip4.dst == 0xac1b0041
>>>>> || ip4.dst == 0xac1b0041 || ip4.dst == 0xac1b0041)
>>>>>
>>>>> In other words, the same expression repeated 5 times.
>>>>>
>>>>> Because the address set in the original match expands to multiple
>>>>> addresses, and it is ANDed with the above disjunction, a conjunctive
>>>>> match is created. This results in the following OF flow being created:
>>>>>
>>>>> nw_dst=172.27.0.65,action=conjunction(2,1/2),conjunction(2,1/2),
>>>>>                             conjunction(2,1/2),conjunction(2,1/2),
>>>>>                         conjunction(2,1/2)
>>>>>
>>>>> If multiple ACLs or logical router policies perform similar matches,
>>>>> this can cause the number of conjunction actions on the flow to balloon,
>>>>> possibly even reaching the point where the flow size is larger than 64K.
>>>>>
>>>>> This patch seeks to fix the issue by crushing the resulting OR that is
>>>>> created from expr_sort(). In the example match, this changes the ip4.dst
>>>>> match to just:
>>>>>
>>>>> ip4.dst == 0xac1b0041
>>>>>
>>>>> Because it is now a single comparison, there's no conjunctive match
>>>>> needed, and the generated OF is as expected.
>>>>
>>>> Thanks for the very detailed commit log, it really makes the problem
>>>> you're trying to solve very clear!
>>>>
>>>>>
>>>>> Reported at: https://bugzilla.redhat.com/show_bug.cgi?id=1955161
>>>>> Signed-off-by: Mark Michelson <mmichels at redhat.com>
>>>>> ---
>>>>
>>>> I think the change is OK, but it might be good for other people to
>>>> review this too before pushing this patch.  With that in mind:
>>>>
>>>> Acked-by: Dumitru Ceara <dceara at redhat.com>
>>
>> Can you please add a test case for this ?
>>
>> Either you can enhance this test case here -
>> https://github.com/ovn-org/ovn/blob/master/tests/ovn.at#L716
>> or add a new one.
>>
>> With a test case added:
>> Acked-by: Numan Siddique <numans at ovn.org>
> 
> Oops.  My bad. There's already a test case.  Please ignore my comment.
> 
> Thanks
> Numan

Thanks Numan and Dumitru. I made the correction to the commit message 
and pushed to master, branch-21.03, and branch-20.12.

> 
>>
>> Thanks
>> Numan
>>
>>>>
>>>> Regards,
>>>> Dumitru
>>>>
>>>
>>> _______________________________________________
>>> dev mailing list
>>> dev at openvswitch.org
>>> https://mail.openvswitch.org/mailman/listinfo/ovs-dev
>>>
>