| Message ID | 20210506204922.2287892-1-mmichels@redhat.com |
|---|---|
| State | Accepted |
| Headers | show |
| Series | [ovs-dev,v2] expr: crush the result of a sorted OR expression. | expand |
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? > > 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@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@redhat.com> Regards, Dumitru
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@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@redhat.com> > > Regards, > Dumitru >
On Fri, May 7, 2021 at 9:03 AM Mark Michelson <mmichels@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@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@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@ovn.org> Thanks Numan > > > > Regards, > > Dumitru > > > > _______________________________________________ > dev mailing list > dev@openvswitch.org > https://mail.openvswitch.org/mailman/listinfo/ovs-dev >
On Fri, May 14, 2021 at 3:19 PM Numan Siddique <numans@ovn.org> wrote: > > On Fri, May 7, 2021 at 9:03 AM Mark Michelson <mmichels@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@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@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@ovn.org> Oops. My bad. There's already a test case. Please ignore my comment. Thanks Numan > > Thanks > Numan > > > > > > > Regards, > > > Dumitru > > > > > > > _______________________________________________ > > dev mailing list > > dev@openvswitch.org > > https://mail.openvswitch.org/mailman/listinfo/ovs-dev > >
On 5/14/21 3:22 PM, Numan Siddique wrote: > On Fri, May 14, 2021 at 3:19 PM Numan Siddique <numans@ovn.org> wrote: >> >> On Fri, May 7, 2021 at 9:03 AM Mark Michelson <mmichels@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@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@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@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@openvswitch.org >>> https://mail.openvswitch.org/mailman/listinfo/ovs-dev >>> >
diff --git a/lib/expr.c b/lib/expr.c index cfc1082e1..244ff3139 100644 --- a/lib/expr.c +++ b/lib/expr.c @@ -2468,7 +2468,7 @@ crush_and_numeric(struct expr *expr, const struct expr_symbol *symbol) free(or); return cmp; } else { - return or; + return crush_cmps(or, symbol); } } else { /* Transform "x && (a0 || a1) && (b0 || b1) && ..." into diff --git a/tests/ovn.at b/tests/ovn.at index fe6a7c85b..0c1df24a4 100644 --- a/tests/ovn.at +++ b/tests/ovn.at @@ -693,6 +693,11 @@ ip,nw_src=4.0.0.0/4.0.0.0 ip,nw_src=64.0.0.0/64.0.0.0 ip,nw_src=8.0.0.0/8.0.0.0 ]) +AT_CHECK([expr_to_flow 'ip4.dst == 172.27.0.65 && ip4.src == $set1 && ip4.dst != 10.128.0.0/14'], [0], [dnl +ip,nw_src=10.0.0.1,nw_dst=172.27.0.65 +ip,nw_src=10.0.0.2,nw_dst=172.27.0.65 +ip,nw_src=10.0.0.3,nw_dst=172.27.0.65 +]) AT_CLEANUP AT_SETUP([ovn -- converting expressions to flows -- port groups])
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 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. Reported at: https://bugzilla.redhat.com/show_bug.cgi?id=1955161 Signed-off-by: Mark Michelson <mmichels@redhat.com> --- lib/expr.c | 2 +- tests/ovn.at | 5 +++++ 2 files changed, 6 insertions(+), 1 deletion(-)