[ovs-dev] [PATCH ovn] Exclude inport and outport symbol tables from conjunction

Tue Sep 17 12:21:22 UTC 2019

On 9/16/19 12:04 PM, Han Zhou wrote:
> 
> 
> On Mon, Sep 16, 2019 at 4:15 AM Dumitru Ceara <dceara at redhat.com 
> <mailto:dceara at redhat.com>> wrote:
>  >
>  > On Sat, Sep 14, 2019 at 7:16 PM Han Zhou <zhouhan at gmail.com 
> <mailto:zhouhan at gmail.com>> wrote:
>  > >
>  > >
>  > >
>  > > On Sat, Sep 14, 2019 at 9:09 AM Han Zhou <zhouhan at gmail.com 
> <mailto:zhouhan at gmail.com>> wrote:
>  > > >
>  > > >
>  > > >
>  > > > On Sat, Sep 14, 2019 at 12:40 AM Numan Siddique 
> <nusiddiq at redhat.com <mailto:nusiddiq at redhat.com>> wrote:
>  > > > >
>  > > > >
>  > > > >
>  > > > > On Sat, Sep 14, 2019 at 2:41 AM Daniel Alvarez Sanchez 
> <dalvarez at redhat.com <mailto:dalvarez at redhat.com>> wrote:
>  > > > >>
>  > > > >> Acked-by: Daniel Alvarez <dalvarez at redhat.com 
> <mailto:dalvarez at redhat.com>>
>  > > > >>
>  > > > >>
>  > > > >> On Fri, Sep 13, 2019 at 11:02 PM Mark Michelson 
> <mmichels at redhat.com <mailto:mmichels at redhat.com>> wrote:
>  > > > >> >
>  > > > >> > Acked-by: Mark Michelson
>  > > > >> >
>  > > > >> > It sucks that we lose the efficiency of the conjunctive 
> match altogether
>  > > > >> > on port groups because of this error, but I understand this 
> is a huge
>  > > > >> > bug and needs fixing.
>  > > > >> If I'm not mistaken, from OpenStack standpoint conjunction was 
> *only*
>  > > > >> being used when using port groups and ACLs that matched on 
> port ranges
>  > > > >> ( e.g tcp.dst >= X && tcp.dst <=Y) which was not working. 
> Therefore
>  > > > >> we're not losing performance because it was already broken 
> (given that
>  > > > >> there was more than one ACL like that).
>  > > > >>
>  > > > >> >
>  > > > >> > Perhaps it would be good to start up a discussion on this 
> list about a
>  > > > >> > more longterm solution that would allow for conjunctive 
> matches with no
>  > > > >> > ambiguity.
>  > > > >> Agreed! We already discussed some ideas on IRC but it'd be 
> awesome to
>  > > > >> have a thread and brainstorm there.
>  > > > >>
>  > > > >
>  > > > > Thanks for the reviews. I applied this to master.
>  > > > > Agree we can discuss it further and come up with ideas.
>  > > > >
>  > > > > I know Dumitru has some idea to make use of conjunctions for 
> port groups.
>  > > > > CC'ing Han if he has any comments on ideas.
>  > > > >
>  > > >
>  > > > Hi Numan,
>  > > >
>  > > > This is a good finding. However, I think it is not specifically a 
> problem of port group. It seems to be a more general problem and this 
> patch fixes only a special case.
>  > > > For example, would there be similar problem for below ACLs 
> without port groups:
>  > > >
>  > > > ip4 && tcp.src >= 1000 && tcp.src <= 1001 && tcp.dst >= 500 && 
> tcp.dst <= 501
>  > > > ip4 && tcp.src >= 1000 && tcp.src <= 1001 && tcp.dst >= 600 && 
> tcp.dst <= 601
>  > > >
>  > > > Another example is with address set:
>  > > >
>  > > > ip4 && ip4.src == $as1 && tcp.dst >= 500 && tcp.dst <= 501
>  > > > ip4 && ip4.src == $as1 && tcp.dst >= 600 && tcp.dst <= 601
>  > > >
>  > > > Or even without range:
>  > > > ip4 && tcp.src == {1000, 1001} && tcp.dst == {500, 501}
>  > > > ip4 && tcp.src == {1000, 1001} && tcp.dst == {600, 601}
>  > > >
>  > > > You may think of more examples. Whenever there are multiple 
> conjunctionable ACLs with same match as part of the conjunction, it 
> should result in such problem.
>  > > >
>  > > > A quick fix to all these problems may be just abandon 
> conjunction, but I believe there are better ways to address it.
>  > > >
>  > > > First of all, these matches can be rewritten by combining them in 
> a single ACL with "OR" operator, e.g.:
>  > > >
>  > > > outport == @pg1 && ip4 && tcp.dst >= 500 && tcp.dst <= 501
>  > > > outport == @pg1 && ip4 && tcp.dst >= 600 && tcp.dst <= 601
>  > > >
>  > > > can be rewritten as ====>
>  > > >
>  > > > outport == @pg1 && ip4 && (tcp.dst >= 500 && tcp.dst <= 501 || 
> tcp.dst >= 600 && tcp.dst <= 601)
>  > > >
>  > > > Similar can be done for all above examples. So, a workaround to 
> the problem is from user side (e.g. OpenStack) to make sure always 
> combining ACLs with "OR" if there are common conjunctionable matches 
> between different ACLs. However, a better way would be in ovn-northd 
> itself to detect and combine such ACLs internally, before generating the 
> final logical flows in SB. It may be more convenient to be done in 
> ovn-controller, because we are not even parsing the ACLs in ovn-northd 
> today, but the cost of such pre-processing would be duplicated in all 
> HVs. It surely will increase CPU cost for doing such combination, but 
> I'd not worry too much if we do it properly at each LS level instead of 
> for all ACLs.
>  > >
>  > > I just thought a little more about combining the conjunctions. It 
> seems we can do it without pre-processing by just handling duplicated 
> flows in ofctrl_add_flow(). Currently we just drop duplicated flows, but 
> we can check that if the action is conjuncture and the conjuncture ID is 
> different, we can perform a combination by using existing flow's 
> conjunction id to update all the flows related to that to-be-added 
> duplicated flow. This way, the combination is performed on-the-fly, 
> without introduce too much cost and without introduce parsing in 
> ovn-northd either.
>  >
>  > Hi Han,
>  >
>  > Will this actually work without a change in OVS? I wonder because in
>  > the ovs-fields man page [1] I see:
>  >
>  > "Conjunctive flows must not overlap with each other, at
>  >  a given priority, that is, any given packet must be
>  >  able to match at most one conjunctive flow at a given
>  >  priority. Overlapping conjunctive flows yield
>  >  unpredictable results."
> 
> Hi Dumitru, the approach of combining ACLs should eliminate the 
> overlapping conjunction problem for ACLs with common expressions, 
> because a single ACL/logical-flow will be translated to a single 
> conjunction. The combination is generally for ACLs with form :
>    A and B
>    A and C
> If A is (a1 or a2), B is (b1 or b2 ), C is (c1 or c2), the initial 
> conjunction matches of current (incorrect) implementation will be:
> conj_id=1234 actions=...
> a1 conjunction(1234, 1/4)
> a2 conjunction(1234, 2/4)
> b1 conjunction(1234, 3/4)
> b2 conjunction(1234, 4/4)
> 
> conj_id=1235 actions=...
> a1 conjunction(1235, 1/4)
> a2 conjunction(1235, 2/4)
> c1 conjunction(1235, 3/4)
> c2 conjunction(1235, 4/4)
> 
> The a1 and a2 matches are overlapping between these two sets.
> In fact, the ACLs are equivalent to:
>    A and (B or C), which is equivalent to: (a1 or a2) and (b1 or b2 or 
> c1 or c2)
> So, if combined with the approach I mentioned, the conjunction matches 
> will be:
> conj_id=1234 actions=...
> a1 conjunction(1234, 1/6)
> a2 conjunction(1234, 2/6)
> b1 conjunction(1234, 3/6)
> b2 conjunction(1234, 4/6)
> c1 conjunction(1234, 5/6)
> c2 conjunction(1234, 6/6)
> 
> The overlapping problem is solved for this use case, and it reduces 
> total number of flows, which can also be considered an *compiler 
> optimization* for logical flows translation in ovn-controller. I don't 
> think any change is needed from OVS.

Unfortunately, this only works for ACLs that have the same action. 
Consider that you have the following:

A and B, allow
A and C, drop

You can't combine these ACLs into

A and (B or C)

since they have different ACL verdicts. You have to leave them separate.

Therefore, you end up with the same problem as before. The A part of the 
conjunction for each conjunctive match overlaps.

> 
>  >
>  > I guess another possibility is to detect flows that have overlapping
>  > sets of matches in ofctrl and change their priorities (along with all
>  > their other conjunction clauses) in order to differentiate the ACLs.
>  > That might turn out to be quite tricky though as we need to maintain
>  > the logical priority of ACLs defined by the user.
> 
> Yes, changing the priority may solve the problem, too, but as you 
> mentioned it may be tricky to calculate the appropriate priorities 
> taking into consideration of how many different priorities are required 
> for each logical flow translation and the user defined priority with the 
> constraint of a single *priority space*. I would support it, too, if it 
> turns out to be simple.
> 
>  >
>  > Thanks,
>  > Dumitru
>  >
>  > [1] http://man7.org/linux/man-pages/man7/ovs-fields.7.html
>  >
>  > >
>  > > In addition, there are more general cases that can't be handled by 
> combining ACLs, if there are overlapping sets in different ACLs. E.g.
>  > > tcp.src == {1000, 1001} && tcp.dst == {500, 501}
>  > > tcp.src == {1001, 1002} && tcp.dst == {600, 601}
>  > >
>  > > In this example, there is no way to combine these 2 ACLs because 
> there is no common components in the matches, but the first set in each 
> conjunctions are overlapping. So there will be flows generated something 
> like:
>  > > tcp.src=1001: conjunction(1, 1/2)
>  > > ...
>  > > tcp.src=1001: conjunction(2, 1/2)
>  > > ...
>  > > This causes the same duplicated flow problem and combining the two 
> set of conjunctions is incorrect.
>  > >
>  > > However, although this is valid case in theory, it seems not a real 
> problem in reality. Usually ACL will be defined with different 
> priorities if there are overlapping (but not identical) set of matches. 
> (At least they are not well designed ACLs - I might be wrong)
>  > >
>  > > cc Ben in case he had thought about these problems before.
>  > >
>  > > Thanks,
>  > > Han