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

From: Numan Siddique <nusiddiq@redhat.com>

If there are multiple ACLs associated with a port group and they
match on a range of some field, then ovn-controller doesn't install
the flows properly and this results in broken ACL functionality.

For example, if there is a port group - pg1 with logical ports - [p1, p2]
and if there are below ACLs (only match condition is shown)

1 -  outport == @pg1 && ip4 && tcp.dst >= 500 && tcp.dst <= 501
2 -  outport == @pg1 && ip4 && tcp.dst >= 600 && tcp.dst <= 601

The first ACL will result in the below OF flows

1.  conj_id=1,tcp
2.  tcp,reg15=0x11: conjunction(1, 1/2)
3.  tcp,reg15=0x12: conjunction(1, 1/2)
5.  tcp,tp_dst=500: conjunction(1, 2/2)
6.  tcp,tp_dst=501: conjunction(1, 2/2)

The second ACL will result in the below OF flows
7.  conj_id=2,tcp
8.  tcp,reg15=0x11: conjunction(2, 1/2)
9.  tcp,reg15=0x12: conjunction(2, 1/2)
11. tcp,tp_dst=600: conjunction(2, 2/2)
12. tcp,tp_dst=601: conjunction(2, 3/2)

The OF flows (2) and (8) have the exact match but with different action.
This results in only one of the flows getting installed. The same goes
for the flows (3) and (9). And this completely breaks the ACL functionality
for such scenarios.

In order to fix this issue, this patch excludes the 'inport' and 'outport' symbols
from conjunction. With this patch we will have the below flows.

tcp,reg15=0x11,tp_dst=500
tcp,reg15=0x11,tp_dst=501
tcp,reg15=0x12,tp_dst=500
tcp,reg15=0x12,tp_dst=501
tcp,reg15=0x13,tp_dst=500
tcp,reg15=0x13,tp_dst=501
tcp,reg15=0x11,tp_dst=600
tcp,reg15=0x11,tp_dst=601
tcp,reg15=0x12,tp_dst=600
tcp,reg15=0x12,tp_dst=601
tcp,reg15=0x13,tp_dst=600
tcp,reg15=0x13,tp_dst=601

Signed-off-by: Numan Siddique <nusiddiq@redhat.com>
---
 lib/expr.c   |  2 +-
 tests/ovn.at | 26 ++++++++++++++++++++++++++
 2 files changed, 27 insertions(+), 1 deletion(-)

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.

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.

On 9/13/19 4:49 PM, nusiddiq@redhat.com wrote:
> From: Numan Siddique <nusiddiq@redhat.com>
> 
> If there are multiple ACLs associated with a port group and they
> match on a range of some field, then ovn-controller doesn't install
> the flows properly and this results in broken ACL functionality.
> 
> For example, if there is a port group - pg1 with logical ports - [p1, p2]
> and if there are below ACLs (only match condition is shown)
> 
> 1 -  outport == @pg1 && ip4 && tcp.dst >= 500 && tcp.dst <= 501
> 2 -  outport == @pg1 && ip4 && tcp.dst >= 600 && tcp.dst <= 601
> 
> The first ACL will result in the below OF flows
> 
> 1.  conj_id=1,tcp
> 2.  tcp,reg15=0x11: conjunction(1, 1/2)
> 3.  tcp,reg15=0x12: conjunction(1, 1/2)
> 5.  tcp,tp_dst=500: conjunction(1, 2/2)
> 6.  tcp,tp_dst=501: conjunction(1, 2/2)
> 
> The second ACL will result in the below OF flows
> 7.  conj_id=2,tcp
> 8.  tcp,reg15=0x11: conjunction(2, 1/2)
> 9.  tcp,reg15=0x12: conjunction(2, 1/2)
> 11. tcp,tp_dst=600: conjunction(2, 2/2)
> 12. tcp,tp_dst=601: conjunction(2, 3/2)
> 
> The OF flows (2) and (8) have the exact match but with different action.
> This results in only one of the flows getting installed. The same goes
> for the flows (3) and (9). And this completely breaks the ACL functionality
> for such scenarios.
> 
> In order to fix this issue, this patch excludes the 'inport' and 'outport' symbols
> from conjunction. With this patch we will have the below flows.
> 
> tcp,reg15=0x11,tp_dst=500
> tcp,reg15=0x11,tp_dst=501
> tcp,reg15=0x12,tp_dst=500
> tcp,reg15=0x12,tp_dst=501
> tcp,reg15=0x13,tp_dst=500
> tcp,reg15=0x13,tp_dst=501
> tcp,reg15=0x11,tp_dst=600
> tcp,reg15=0x11,tp_dst=601
> tcp,reg15=0x12,tp_dst=600
> tcp,reg15=0x12,tp_dst=601
> tcp,reg15=0x13,tp_dst=600
> tcp,reg15=0x13,tp_dst=601
> 
> Signed-off-by: Numan Siddique <nusiddiq@redhat.com>
> ---
>   lib/expr.c   |  2 +-
>   tests/ovn.at | 26 ++++++++++++++++++++++++++
>   2 files changed, 27 insertions(+), 1 deletion(-)
> 
> diff --git a/lib/expr.c b/lib/expr.c
> index e4c650f7c..c0871e1e8 100644
> --- a/lib/expr.c
> +++ b/lib/expr.c
> @@ -1499,7 +1499,7 @@ expr_symtab_add_string(struct shash *symtab, const char *name,
>       const struct mf_field *field = mf_from_id(id);
>       struct expr_symbol *symbol;
>   
> -    symbol = add_symbol(symtab, name, 0, prereqs, EXPR_L_NOMINAL, false,
> +    symbol = add_symbol(symtab, name, 0, prereqs, EXPR_L_NOMINAL, true,
>                           field->writable);
>       symbol->field = field;
>       return symbol;
> diff --git a/tests/ovn.at b/tests/ovn.at
> index 2a35b4e15..14d9f59b0 100644
> --- a/tests/ovn.at
> +++ b/tests/ovn.at
> @@ -589,6 +589,24 @@ ip,reg14=0x6
>   ipv6,reg14=0x5
>   ipv6,reg14=0x6
>   ])
> +AT_CHECK([expr_to_flow 'inport == {"eth0", "eth1", "eth2"} && ip4 && tcp && tcp.dst == {500, 501}'], [0], [dnl
> +tcp,reg14=0x5,tp_dst=500
> +tcp,reg14=0x5,tp_dst=501
> +tcp,reg14=0x6,tp_dst=500
> +tcp,reg14=0x6,tp_dst=501
> +])
> +AT_CHECK([expr_to_flow 'outport == {"eth0", "eth1", "eth2"} && ip4 && tcp && tcp.src == {400, 401} && tcp.dst == {500, 501}'], [0], [dnl
> +conj_id=1,tcp,reg15=0x5
> +conj_id=2,tcp,reg15=0x6
> +tcp,reg15=0x5,tp_dst=500: conjunction(1, 0/2)
> +tcp,reg15=0x5,tp_dst=501: conjunction(1, 0/2)
> +tcp,reg15=0x5,tp_src=400: conjunction(1, 1/2)
> +tcp,reg15=0x5,tp_src=401: conjunction(1, 1/2)
> +tcp,reg15=0x6,tp_dst=500: conjunction(2, 0/2)
> +tcp,reg15=0x6,tp_dst=501: conjunction(2, 0/2)
> +tcp,reg15=0x6,tp_src=400: conjunction(2, 1/2)
> +tcp,reg15=0x6,tp_src=401: conjunction(2, 1/2)
> +])
>   AT_CHECK([expr_to_flow 'inport == "eth0" && inport == "eth1"'], [0], [dnl
>   (no flows)
>   ])
> @@ -693,6 +711,14 @@ reg15=0x11
>   reg15=0x12
>   reg15=0x13
>   ])
> +AT_CHECK([expr_to_flow 'outport == @pg1 && ip4.src == {10.0.0.4, 10.0.0.5}'], [0], [dnl
> +ip,reg15=0x11,nw_src=10.0.0.4
> +ip,reg15=0x11,nw_src=10.0.0.5
> +ip,reg15=0x12,nw_src=10.0.0.4
> +ip,reg15=0x12,nw_src=10.0.0.5
> +ip,reg15=0x13,nw_src=10.0.0.4
> +ip,reg15=0x13,nw_src=10.0.0.5
> +])
>   AT_CHECK([expr_to_flow 'outport == {@pg_empty}'], [0], [dnl
>   (no flows)
>   ])
>

Acked-by: Daniel Alvarez <dalvarez@redhat.com>


On Fri, Sep 13, 2019 at 11:02 PM Mark Michelson <mmichels@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 a lot everyone!
Daniel
>
> On 9/13/19 4:49 PM, nusiddiq@redhat.com wrote:
> > From: Numan Siddique <nusiddiq@redhat.com>
> >
> > If there are multiple ACLs associated with a port group and they
> > match on a range of some field, then ovn-controller doesn't install
> > the flows properly and this results in broken ACL functionality.
> >
> > For example, if there is a port group - pg1 with logical ports - [p1, p2]
> > and if there are below ACLs (only match condition is shown)
> >
> > 1 -  outport == @pg1 && ip4 && tcp.dst >= 500 && tcp.dst <= 501
> > 2 -  outport == @pg1 && ip4 && tcp.dst >= 600 && tcp.dst <= 601
> >
> > The first ACL will result in the below OF flows
> >
> > 1.  conj_id=1,tcp
> > 2.  tcp,reg15=0x11: conjunction(1, 1/2)
> > 3.  tcp,reg15=0x12: conjunction(1, 1/2)
> > 5.  tcp,tp_dst=500: conjunction(1, 2/2)
> > 6.  tcp,tp_dst=501: conjunction(1, 2/2)
> >
> > The second ACL will result in the below OF flows
> > 7.  conj_id=2,tcp
> > 8.  tcp,reg15=0x11: conjunction(2, 1/2)
> > 9.  tcp,reg15=0x12: conjunction(2, 1/2)
> > 11. tcp,tp_dst=600: conjunction(2, 2/2)
> > 12. tcp,tp_dst=601: conjunction(2, 3/2)
> >
> > The OF flows (2) and (8) have the exact match but with different action.
> > This results in only one of the flows getting installed. The same goes
> > for the flows (3) and (9). And this completely breaks the ACL functionality
> > for such scenarios.
> >
> > In order to fix this issue, this patch excludes the 'inport' and 'outport' symbols
> > from conjunction. With this patch we will have the below flows.
> >
> > tcp,reg15=0x11,tp_dst=500
> > tcp,reg15=0x11,tp_dst=501
> > tcp,reg15=0x12,tp_dst=500
> > tcp,reg15=0x12,tp_dst=501
> > tcp,reg15=0x13,tp_dst=500
> > tcp,reg15=0x13,tp_dst=501
> > tcp,reg15=0x11,tp_dst=600
> > tcp,reg15=0x11,tp_dst=601
> > tcp,reg15=0x12,tp_dst=600
> > tcp,reg15=0x12,tp_dst=601
> > tcp,reg15=0x13,tp_dst=600
> > tcp,reg15=0x13,tp_dst=601
> >
> > Signed-off-by: Numan Siddique <nusiddiq@redhat.com>
> > ---
> >   lib/expr.c   |  2 +-
> >   tests/ovn.at | 26 ++++++++++++++++++++++++++
> >   2 files changed, 27 insertions(+), 1 deletion(-)
> >
> > diff --git a/lib/expr.c b/lib/expr.c
> > index e4c650f7c..c0871e1e8 100644
> > --- a/lib/expr.c
> > +++ b/lib/expr.c
> > @@ -1499,7 +1499,7 @@ expr_symtab_add_string(struct shash *symtab, const char *name,
> >       const struct mf_field *field = mf_from_id(id);
> >       struct expr_symbol *symbol;
> >
> > -    symbol = add_symbol(symtab, name, 0, prereqs, EXPR_L_NOMINAL, false,
> > +    symbol = add_symbol(symtab, name, 0, prereqs, EXPR_L_NOMINAL, true,
> >                           field->writable);
> >       symbol->field = field;
> >       return symbol;
> > diff --git a/tests/ovn.at b/tests/ovn.at
> > index 2a35b4e15..14d9f59b0 100644
> > --- a/tests/ovn.at
> > +++ b/tests/ovn.at
> > @@ -589,6 +589,24 @@ ip,reg14=0x6
> >   ipv6,reg14=0x5
> >   ipv6,reg14=0x6
> >   ])
> > +AT_CHECK([expr_to_flow 'inport == {"eth0", "eth1", "eth2"} && ip4 && tcp && tcp.dst == {500, 501}'], [0], [dnl
> > +tcp,reg14=0x5,tp_dst=500
> > +tcp,reg14=0x5,tp_dst=501
> > +tcp,reg14=0x6,tp_dst=500
> > +tcp,reg14=0x6,tp_dst=501
> > +])
> > +AT_CHECK([expr_to_flow 'outport == {"eth0", "eth1", "eth2"} && ip4 && tcp && tcp.src == {400, 401} && tcp.dst == {500, 501}'], [0], [dnl
> > +conj_id=1,tcp,reg15=0x5
> > +conj_id=2,tcp,reg15=0x6
> > +tcp,reg15=0x5,tp_dst=500: conjunction(1, 0/2)
> > +tcp,reg15=0x5,tp_dst=501: conjunction(1, 0/2)
> > +tcp,reg15=0x5,tp_src=400: conjunction(1, 1/2)
> > +tcp,reg15=0x5,tp_src=401: conjunction(1, 1/2)
> > +tcp,reg15=0x6,tp_dst=500: conjunction(2, 0/2)
> > +tcp,reg15=0x6,tp_dst=501: conjunction(2, 0/2)
> > +tcp,reg15=0x6,tp_src=400: conjunction(2, 1/2)
> > +tcp,reg15=0x6,tp_src=401: conjunction(2, 1/2)
> > +])
> >   AT_CHECK([expr_to_flow 'inport == "eth0" && inport == "eth1"'], [0], [dnl
> >   (no flows)
> >   ])
> > @@ -693,6 +711,14 @@ reg15=0x11
> >   reg15=0x12
> >   reg15=0x13
> >   ])
> > +AT_CHECK([expr_to_flow 'outport == @pg1 && ip4.src == {10.0.0.4, 10.0.0.5}'], [0], [dnl
> > +ip,reg15=0x11,nw_src=10.0.0.4
> > +ip,reg15=0x11,nw_src=10.0.0.5
> > +ip,reg15=0x12,nw_src=10.0.0.4
> > +ip,reg15=0x12,nw_src=10.0.0.5
> > +ip,reg15=0x13,nw_src=10.0.0.4
> > +ip,reg15=0x13,nw_src=10.0.0.5
> > +])
> >   AT_CHECK([expr_to_flow 'outport == {@pg_empty}'], [0], [dnl
> >   (no flows)
> >   ])
> >
>
> _______________________________________________
> dev mailing list
> dev@openvswitch.org
> https://mail.openvswitch.org/mailman/listinfo/ovs-dev

On Sat, Sep 14, 2019 at 2:41 AM Daniel Alvarez Sanchez <dalvarez@redhat.com>
wrote:

> Acked-by: Daniel Alvarez <dalvarez@redhat.com>
>
>
> On Fri, Sep 13, 2019 at 11:02 PM Mark Michelson <mmichels@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.

Thanks
Numan


> Thanks a lot everyone!
> Daniel
> >
> > On 9/13/19 4:49 PM, nusiddiq@redhat.com wrote:
> > > From: Numan Siddique <nusiddiq@redhat.com>
> > >
> > > If there are multiple ACLs associated with a port group and they
> > > match on a range of some field, then ovn-controller doesn't install
> > > the flows properly and this results in broken ACL functionality.
> > >
> > > For example, if there is a port group - pg1 with logical ports - [p1,
> p2]
> > > and if there are below ACLs (only match condition is shown)
> > >
> > > 1 -  outport == @pg1 && ip4 && tcp.dst >= 500 && tcp.dst <= 501
> > > 2 -  outport == @pg1 && ip4 && tcp.dst >= 600 && tcp.dst <= 601
> > >
> > > The first ACL will result in the below OF flows
> > >
> > > 1.  conj_id=1,tcp
> > > 2.  tcp,reg15=0x11: conjunction(1, 1/2)
> > > 3.  tcp,reg15=0x12: conjunction(1, 1/2)
> > > 5.  tcp,tp_dst=500: conjunction(1, 2/2)
> > > 6.  tcp,tp_dst=501: conjunction(1, 2/2)
> > >
> > > The second ACL will result in the below OF flows
> > > 7.  conj_id=2,tcp
> > > 8.  tcp,reg15=0x11: conjunction(2, 1/2)
> > > 9.  tcp,reg15=0x12: conjunction(2, 1/2)
> > > 11. tcp,tp_dst=600: conjunction(2, 2/2)
> > > 12. tcp,tp_dst=601: conjunction(2, 3/2)
> > >
> > > The OF flows (2) and (8) have the exact match but with different
> action.
> > > This results in only one of the flows getting installed. The same goes
> > > for the flows (3) and (9). And this completely breaks the ACL
> functionality
> > > for such scenarios.
> > >
> > > In order to fix this issue, this patch excludes the 'inport' and
> 'outport' symbols
> > > from conjunction. With this patch we will have the below flows.
> > >
> > > tcp,reg15=0x11,tp_dst=500
> > > tcp,reg15=0x11,tp_dst=501
> > > tcp,reg15=0x12,tp_dst=500
> > > tcp,reg15=0x12,tp_dst=501
> > > tcp,reg15=0x13,tp_dst=500
> > > tcp,reg15=0x13,tp_dst=501
> > > tcp,reg15=0x11,tp_dst=600
> > > tcp,reg15=0x11,tp_dst=601
> > > tcp,reg15=0x12,tp_dst=600
> > > tcp,reg15=0x12,tp_dst=601
> > > tcp,reg15=0x13,tp_dst=600
> > > tcp,reg15=0x13,tp_dst=601
> > >
> > > Signed-off-by: Numan Siddique <nusiddiq@redhat.com>
> > > ---
> > >   lib/expr.c   |  2 +-
> > >   tests/ovn.at | 26 ++++++++++++++++++++++++++
> > >   2 files changed, 27 insertions(+), 1 deletion(-)
> > >
> > > diff --git a/lib/expr.c b/lib/expr.c
> > > index e4c650f7c..c0871e1e8 100644
> > > --- a/lib/expr.c
> > > +++ b/lib/expr.c
> > > @@ -1499,7 +1499,7 @@ expr_symtab_add_string(struct shash *symtab,
> const char *name,
> > >       const struct mf_field *field = mf_from_id(id);
> > >       struct expr_symbol *symbol;
> > >
> > > -    symbol = add_symbol(symtab, name, 0, prereqs, EXPR_L_NOMINAL,
> false,
> > > +    symbol = add_symbol(symtab, name, 0, prereqs, EXPR_L_NOMINAL,
> true,
> > >                           field->writable);
> > >       symbol->field = field;
> > >       return symbol;
> > > diff --git a/tests/ovn.at b/tests/ovn.at
> > > index 2a35b4e15..14d9f59b0 100644
> > > --- a/tests/ovn.at
> > > +++ b/tests/ovn.at
> > > @@ -589,6 +589,24 @@ ip,reg14=0x6
> > >   ipv6,reg14=0x5
> > >   ipv6,reg14=0x6
> > >   ])
> > > +AT_CHECK([expr_to_flow 'inport == {"eth0", "eth1", "eth2"} && ip4 &&
> tcp && tcp.dst == {500, 501}'], [0], [dnl
> > > +tcp,reg14=0x5,tp_dst=500
> > > +tcp,reg14=0x5,tp_dst=501
> > > +tcp,reg14=0x6,tp_dst=500
> > > +tcp,reg14=0x6,tp_dst=501
> > > +])
> > > +AT_CHECK([expr_to_flow 'outport == {"eth0", "eth1", "eth2"} && ip4 &&
> tcp && tcp.src == {400, 401} && tcp.dst == {500, 501}'], [0], [dnl
> > > +conj_id=1,tcp,reg15=0x5
> > > +conj_id=2,tcp,reg15=0x6
> > > +tcp,reg15=0x5,tp_dst=500: conjunction(1, 0/2)
> > > +tcp,reg15=0x5,tp_dst=501: conjunction(1, 0/2)
> > > +tcp,reg15=0x5,tp_src=400: conjunction(1, 1/2)
> > > +tcp,reg15=0x5,tp_src=401: conjunction(1, 1/2)
> > > +tcp,reg15=0x6,tp_dst=500: conjunction(2, 0/2)
> > > +tcp,reg15=0x6,tp_dst=501: conjunction(2, 0/2)
> > > +tcp,reg15=0x6,tp_src=400: conjunction(2, 1/2)
> > > +tcp,reg15=0x6,tp_src=401: conjunction(2, 1/2)
> > > +])
> > >   AT_CHECK([expr_to_flow 'inport == "eth0" && inport == "eth1"'], [0],
> [dnl
> > >   (no flows)
> > >   ])
> > > @@ -693,6 +711,14 @@ reg15=0x11
> > >   reg15=0x12
> > >   reg15=0x13
> > >   ])
> > > +AT_CHECK([expr_to_flow 'outport == @pg1 && ip4.src == {10.0.0.4,
> 10.0.0.5}'], [0], [dnl
> > > +ip,reg15=0x11,nw_src=10.0.0.4
> > > +ip,reg15=0x11,nw_src=10.0.0.5
> > > +ip,reg15=0x12,nw_src=10.0.0.4
> > > +ip,reg15=0x12,nw_src=10.0.0.5
> > > +ip,reg15=0x13,nw_src=10.0.0.4
> > > +ip,reg15=0x13,nw_src=10.0.0.5
> > > +])
> > >   AT_CHECK([expr_to_flow 'outport == {@pg_empty}'], [0], [dnl
> > >   (no flows)
> > >   ])
> > >
> >
> > _______________________________________________
> > dev mailing list
> > dev@openvswitch.org
> > https://mail.openvswitch.org/mailman/listinfo/ovs-dev
>

On Sat, Sep 14, 2019 at 12:40 AM Numan Siddique <nusiddiq@redhat.com> wrote:
>
>
>
> On Sat, Sep 14, 2019 at 2:41 AM Daniel Alvarez Sanchez <
dalvarez@redhat.com> wrote:
>>
>> Acked-by: Daniel Alvarez <dalvarez@redhat.com>
>>
>>
>> On Fri, Sep 13, 2019 at 11:02 PM Mark Michelson <mmichels@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.

Thanks,
Han

On Sat, Sep 14, 2019 at 9:09 AM Han Zhou <zhouhan@gmail.com> wrote:
>
>
>
> On Sat, Sep 14, 2019 at 12:40 AM Numan Siddique <nusiddiq@redhat.com>
wrote:
> >
> >
> >
> > On Sat, Sep 14, 2019 at 2:41 AM Daniel Alvarez Sanchez <
dalvarez@redhat.com> wrote:
> >>
> >> Acked-by: Daniel Alvarez <dalvarez@redhat.com>
> >>
> >>
> >> On Fri, Sep 13, 2019 at 11:02 PM Mark Michelson <mmichels@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.

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

On Sat, Sep 14, 2019 at 7:16 PM Han Zhou <zhouhan@gmail.com> wrote:
>
>
>
> On Sat, Sep 14, 2019 at 9:09 AM Han Zhou <zhouhan@gmail.com> wrote:
> >
> >
> >
> > On Sat, Sep 14, 2019 at 12:40 AM Numan Siddique <nusiddiq@redhat.com> wrote:
> > >
> > >
> > >
> > > On Sat, Sep 14, 2019 at 2:41 AM Daniel Alvarez Sanchez <dalvarez@redhat.com> wrote:
> > >>
> > >> Acked-by: Daniel Alvarez <dalvarez@redhat.com>
> > >>
> > >>
> > >> On Fri, Sep 13, 2019 at 11:02 PM Mark Michelson <mmichels@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."

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.

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

On Mon, Sep 16, 2019 at 4:15 AM Dumitru Ceara <dceara@redhat.com> wrote:
>
> On Sat, Sep 14, 2019 at 7:16 PM Han Zhou <zhouhan@gmail.com> wrote:
> >
> >
> >
> > On Sat, Sep 14, 2019 at 9:09 AM Han Zhou <zhouhan@gmail.com> wrote:
> > >
> > >
> > >
> > > On Sat, Sep 14, 2019 at 12:40 AM Numan Siddique <nusiddiq@redhat.com>
wrote:
> > > >
> > > >
> > > >
> > > > On Sat, Sep 14, 2019 at 2:41 AM Daniel Alvarez Sanchez <
dalvarez@redhat.com> wrote:
> > > >>
> > > >> Acked-by: Daniel Alvarez <dalvarez@redhat.com>
> > > >>
> > > >>
> > > >> On Fri, Sep 13, 2019 at 11:02 PM Mark Michelson <
mmichels@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.

>
> 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

On 9/16/19 12:04 PM, Han Zhou wrote:
> 
> 
> On Mon, Sep 16, 2019 at 4:15 AM Dumitru Ceara <dceara@redhat.com 
> <mailto:dceara@redhat.com>> wrote:
>  >
>  > On Sat, Sep 14, 2019 at 7:16 PM Han Zhou <zhouhan@gmail.com 
> <mailto:zhouhan@gmail.com>> wrote:
>  > >
>  > >
>  > >
>  > > On Sat, Sep 14, 2019 at 9:09 AM Han Zhou <zhouhan@gmail.com 
> <mailto:zhouhan@gmail.com>> wrote:
>  > > >
>  > > >
>  > > >
>  > > > On Sat, Sep 14, 2019 at 12:40 AM Numan Siddique 
> <nusiddiq@redhat.com <mailto:nusiddiq@redhat.com>> wrote:
>  > > > >
>  > > > >
>  > > > >
>  > > > > On Sat, Sep 14, 2019 at 2:41 AM Daniel Alvarez Sanchez 
> <dalvarez@redhat.com <mailto:dalvarez@redhat.com>> wrote:
>  > > > >>
>  > > > >> Acked-by: Daniel Alvarez <dalvarez@redhat.com 
> <mailto:dalvarez@redhat.com>>
>  > > > >>
>  > > > >>
>  > > > >> On Fri, Sep 13, 2019 at 11:02 PM Mark Michelson 
> <mmichels@redhat.com <mailto:mmichels@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

On Tue, Sep 17, 2019 at 5:21 AM Mark Michelson <mmichels@redhat.com> wrote:
>
> On 9/16/19 12:04 PM, Han Zhou wrote:
> >
> >
> > On Mon, Sep 16, 2019 at 4:15 AM Dumitru Ceara <dceara@redhat.com
> > <mailto:dceara@redhat.com>> wrote:
> >  >
> >  > On Sat, Sep 14, 2019 at 7:16 PM Han Zhou <zhouhan@gmail.com
> > <mailto:zhouhan@gmail.com>> wrote:
> >  > >
> >  > >
> >  > >
> >  > > On Sat, Sep 14, 2019 at 9:09 AM Han Zhou <zhouhan@gmail.com
> > <mailto:zhouhan@gmail.com>> wrote:
> >  > > >
> >  > > >
> >  > > >
> >  > > > On Sat, Sep 14, 2019 at 12:40 AM Numan Siddique
> > <nusiddiq@redhat.com <mailto:nusiddiq@redhat.com>> wrote:
> >  > > > >
> >  > > > >
> >  > > > >
> >  > > > > On Sat, Sep 14, 2019 at 2:41 AM Daniel Alvarez Sanchez
> > <dalvarez@redhat.com <mailto:dalvarez@redhat.com>> wrote:
> >  > > > >>
> >  > > > >> Acked-by: Daniel Alvarez <dalvarez@redhat.com
> > <mailto:dalvarez@redhat.com>>
> >  > > > >>
> >  > > > >>
> >  > > > >> On Fri, Sep 13, 2019 at 11:02 PM Mark Michelson
> > <mmichels@redhat.com <mailto:mmichels@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.
>

Hi Mark,

Thanks for pointing out. Unfortunately you are right :)
So I guess the only option we have now is to play around with priorities.
Although it might be tricky, it should work. And the best part is, priority
can also solve the "partial overlapping" problem I mentioned earlier, such
as:
> >  > > tcp.src == {1000, 1001} && tcp.dst == {500, 501}
> >  > > tcp.src == {1001, 1002} && tcp.dst == {600, 601}

Here is some more thinking about the priority solution. Today for any
user-defined ACL priority (PA), there is a corresponding OVS flow priority
(PO). PA to PO is one-to-one mapping. Now to solve the overlapping problem,
there can be more than one PO [POx..POy] mapped for each PA. The problem is
how to maintain the mappings between these two. I think there are 2 options:

Option1: Whenever there is duplicate flow encountered for user-defined
priority PA, increase the range of PO from [POx..POy] to [POx..POy+1].

This approach requires dynamically adjust priorities for existing flows.
For example, initially there are flows:
1: user-defined priority 100, OVS priority 1100: <match 1>, <action 1>
2: user-defined priority 101, OVS priority 1101: <match 2>, <action 2>

Now there is a logical flow requires conjunction:
3: user-defined priority 100, OVS priority 1100: A and B, <action 3>

And then there is another logical flow requires conjunction, with
overlapping to the previous one:
4: user-defined priority 100, OVS priority <?>: A and C, <action 4>

To handle the overlapping, we need to increase the range corresponding to
100. It was 1100, and now it needs to be 1100 and 1101. So we will have to
adjust priority of the flow 2 from 1101 to 1102, to preserve the original
priority order. This will have high cost, and worst thing is, it will
disrupt Incremental Processing.

Option2: Preserve N priorities in the range of OVS flow [POx..POx+N) for
each user-defined PA. If there are more than N ACLs with overlapping
conjunction sets, it is not supported.

This approach avoids the priority readjustment problem, sacrificing the
number of priorities and number of overlapping conjunction that we can
support. The bigger N is, the less number of user-defined priority can be
supported; the smaller N is, the less number of overlapping conjunction can
be supported.
Although each one has its pros and cons, I prefer option2 more than
option1, because conjunction is mainly for performance. If we end up with a
solution that sacrifice performance it may not worth enabling conjunction
at all.

As a further improvement, we may still apply the conjunction combining
approach that I proposed just when the actions are also identical (which
may be the case in most real world scenarios), to eliminate the *fake*
overlapping conjunctions, before using different priorities, so that we
have more priorities left to play with real overlapping scenarios.

Thanks,
Han

> >
> >  >
> >  > 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
>

On Tue, Sep 17, 2019 at 6:49 PM Han Zhou <zhouhan@gmail.com> wrote:
>
>
>
> On Tue, Sep 17, 2019 at 5:21 AM Mark Michelson <mmichels@redhat.com> wrote:
> >
> > On 9/16/19 12:04 PM, Han Zhou wrote:
> > >
> > >
> > > On Mon, Sep 16, 2019 at 4:15 AM Dumitru Ceara <dceara@redhat.com
> > > <mailto:dceara@redhat.com>> wrote:
> > >  >
> > >  > On Sat, Sep 14, 2019 at 7:16 PM Han Zhou <zhouhan@gmail.com
> > > <mailto:zhouhan@gmail.com>> wrote:
> > >  > >
> > >  > >
> > >  > >
> > >  > > On Sat, Sep 14, 2019 at 9:09 AM Han Zhou <zhouhan@gmail.com
> > > <mailto:zhouhan@gmail.com>> wrote:
> > >  > > >
> > >  > > >
> > >  > > >
> > >  > > > On Sat, Sep 14, 2019 at 12:40 AM Numan Siddique
> > > <nusiddiq@redhat.com <mailto:nusiddiq@redhat.com>> wrote:
> > >  > > > >
> > >  > > > >
> > >  > > > >
> > >  > > > > On Sat, Sep 14, 2019 at 2:41 AM Daniel Alvarez Sanchez
> > > <dalvarez@redhat.com <mailto:dalvarez@redhat.com>> wrote:
> > >  > > > >>
> > >  > > > >> Acked-by: Daniel Alvarez <dalvarez@redhat.com
> > > <mailto:dalvarez@redhat.com>>
> > >  > > > >>
> > >  > > > >>
> > >  > > > >> On Fri, Sep 13, 2019 at 11:02 PM Mark Michelson
> > > <mmichels@redhat.com <mailto:mmichels@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.
> >
>
> Hi Mark,
>
> Thanks for pointing out. Unfortunately you are right :)
> So I guess the only option we have now is to play around with priorities. Although it might be tricky, it should work. And the best part is, priority can also solve the "partial overlapping" problem I mentioned earlier, such as:
> > >  > > tcp.src == {1000, 1001} && tcp.dst == {500, 501}
> > >  > > tcp.src == {1001, 1002} && tcp.dst == {600, 601}
>
> Here is some more thinking about the priority solution. Today for any user-defined ACL priority (PA), there is a corresponding OVS flow priority (PO). PA to PO is one-to-one mapping. Now to solve the overlapping problem, there can be more than one PO [POx..POy] mapped for each PA. The problem is how to maintain the mappings between these two. I think there are 2 options:
>
> Option1: Whenever there is duplicate flow encountered for user-defined priority PA, increase the range of PO from [POx..POy] to [POx..POy+1].
>
> This approach requires dynamically adjust priorities for existing flows. For example, initially there are flows:
> 1: user-defined priority 100, OVS priority 1100: <match 1>, <action 1>
> 2: user-defined priority 101, OVS priority 1101: <match 2>, <action 2>
>
> Now there is a logical flow requires conjunction:
> 3: user-defined priority 100, OVS priority 1100: A and B, <action 3>
>
> And then there is another logical flow requires conjunction, with overlapping to the previous one:
> 4: user-defined priority 100, OVS priority <?>: A and C, <action 4>
>
> To handle the overlapping, we need to increase the range corresponding to 100. It was 1100, and now it needs to be 1100 and 1101. So we will have to adjust priority of the flow 2 from 1101 to 1102, to preserve the original priority order. This will have high cost, and worst thing is, it will disrupt Incremental Processing.
>
> Option2: Preserve N priorities in the range of OVS flow [POx..POx+N) for each user-defined PA. If there are more than N ACLs with overlapping conjunction sets, it is not supported.
>
> This approach avoids the priority readjustment problem, sacrificing the number of priorities and number of overlapping conjunction that we can support. The bigger N is, the less number of user-defined priority can be supported; the smaller N is, the less number of overlapping conjunction can be supported.
> Although each one has its pros and cons, I prefer option2 more than option1, because conjunction is mainly for performance. If we end up with a solution that sacrifice performance it may not worth enabling conjunction at all.

Hi Han,

I agree that Option2 is preferable due to the cost of reassigning
priorities in Option1. What worries me is that we decrease the
available number of user priorities by a fixed factor for all cases,
even if there are no overlapping conjunction sets in the config. Based
on your idea I had the following optimization in mind:

Add a new table, let's call it "ACL-collision" for now. When an ACL is
added the following operations would be performed by ovn-controller:
- Try to add the ACL to the regular ACL table with priority PO. If
there's no overlap on matches for any of the generated flows at
priority PO then stop.
- Otherwise, keep the first overlapping flow of the existing ACL and
new ACL at priority PO in the ACL table but change its action to
resubmit the packet to the "ACL-collision" table.
- Add the remaining flows of the old ACL and new ACL to table
"ACL-collision" making sure that we assign different priorities to
flows from the two ACLs.
- In table "ACL-collision" add a low priority "match-all" flow that
will resubmit the packet back to the ACL table to continue regular ACL
matching.

This approach would not affect any existing deployments where there
are no overlapping conjunction sets.
Also, it should maintain logical ordering of PA priorities because the
first term of the conjunction flows (the one in the ACL table) keeps
the same PO priority as now (that corresponds to PA).

The disadvantage is that we add another step in the pipeline for
packets that match the common part of the overlapping conjunction sets
potentially increasing latency/jitter.

Do you think this would work? Are there any other cases to take care of?

Thanks,
Dumitru

>
> As a further improvement, we may still apply the conjunction combining approach that I proposed just when the actions are also identical (which may be the case in most real world scenarios), to eliminate the *fake* overlapping conjunctions, before using different priorities, so that we have more priorities left to play with real overlapping scenarios.
>
> Thanks,
> Han
>
> > >
> > >  >
> > >  > 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
> >

On Wed, Sep 18, 2019 at 9:30 AM Dumitru Ceara <dceara@redhat.com> wrote:
>
> On Tue, Sep 17, 2019 at 6:49 PM Han Zhou <zhouhan@gmail.com> wrote:
> >
> >
> >
> > On Tue, Sep 17, 2019 at 5:21 AM Mark Michelson <mmichels@redhat.com> wrote:
> > >
> > > On 9/16/19 12:04 PM, Han Zhou wrote:
> > > >
> > > >
> > > > On Mon, Sep 16, 2019 at 4:15 AM Dumitru Ceara <dceara@redhat.com
> > > > <mailto:dceara@redhat.com>> wrote:
> > > >  >
> > > >  > On Sat, Sep 14, 2019 at 7:16 PM Han Zhou <zhouhan@gmail.com
> > > > <mailto:zhouhan@gmail.com>> wrote:
> > > >  > >
> > > >  > >
> > > >  > >
> > > >  > > On Sat, Sep 14, 2019 at 9:09 AM Han Zhou <zhouhan@gmail.com
> > > > <mailto:zhouhan@gmail.com>> wrote:
> > > >  > > >
> > > >  > > >
> > > >  > > >
> > > >  > > > On Sat, Sep 14, 2019 at 12:40 AM Numan Siddique
> > > > <nusiddiq@redhat.com <mailto:nusiddiq@redhat.com>> wrote:
> > > >  > > > >
> > > >  > > > >
> > > >  > > > >
> > > >  > > > > On Sat, Sep 14, 2019 at 2:41 AM Daniel Alvarez Sanchez
> > > > <dalvarez@redhat.com <mailto:dalvarez@redhat.com>> wrote:
> > > >  > > > >>
> > > >  > > > >> Acked-by: Daniel Alvarez <dalvarez@redhat.com
> > > > <mailto:dalvarez@redhat.com>>
> > > >  > > > >>
> > > >  > > > >>
> > > >  > > > >> On Fri, Sep 13, 2019 at 11:02 PM Mark Michelson
> > > > <mmichels@redhat.com <mailto:mmichels@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.
> > >
> >
> > Hi Mark,
> >
> > Thanks for pointing out. Unfortunately you are right :)
> > So I guess the only option we have now is to play around with priorities. Although it might be tricky, it should work. And the best part is, priority can also solve the "partial overlapping" problem I mentioned earlier, such as:
> > > >  > > tcp.src == {1000, 1001} && tcp.dst == {500, 501}
> > > >  > > tcp.src == {1001, 1002} && tcp.dst == {600, 601}
> >
> > Here is some more thinking about the priority solution. Today for any user-defined ACL priority (PA), there is a corresponding OVS flow priority (PO). PA to PO is one-to-one mapping. Now to solve the overlapping problem, there can be more than one PO [POx..POy] mapped for each PA. The problem is how to maintain the mappings between these two. I think there are 2 options:
> >
> > Option1: Whenever there is duplicate flow encountered for user-defined priority PA, increase the range of PO from [POx..POy] to [POx..POy+1].
> >
> > This approach requires dynamically adjust priorities for existing flows. For example, initially there are flows:
> > 1: user-defined priority 100, OVS priority 1100: <match 1>, <action 1>
> > 2: user-defined priority 101, OVS priority 1101: <match 2>, <action 2>
> >
> > Now there is a logical flow requires conjunction:
> > 3: user-defined priority 100, OVS priority 1100: A and B, <action 3>
> >
> > And then there is another logical flow requires conjunction, with overlapping to the previous one:
> > 4: user-defined priority 100, OVS priority <?>: A and C, <action 4>
> >
> > To handle the overlapping, we need to increase the range corresponding to 100. It was 1100, and now it needs to be 1100 and 1101. So we will have to adjust priority of the flow 2 from 1101 to 1102, to preserve the original priority order. This will have high cost, and worst thing is, it will disrupt Incremental Processing.
> >
> > Option2: Preserve N priorities in the range of OVS flow [POx..POx+N) for each user-defined PA. If there are more than N ACLs with overlapping conjunction sets, it is not supported.
> >
> > This approach avoids the priority readjustment problem, sacrificing the number of priorities and number of overlapping conjunction that we can support. The bigger N is, the less number of user-defined priority can be supported; the smaller N is, the less number of overlapping conjunction can be supported.
> > Although each one has its pros and cons, I prefer option2 more than option1, because conjunction is mainly for performance. If we end up with a solution that sacrifice performance it may not worth enabling conjunction at all.
>
> Hi Han,
>
> I agree that Option2 is preferable due to the cost of reassigning
> priorities in Option1. What worries me is that we decrease the
> available number of user priorities by a fixed factor for all cases,
> even if there are no overlapping conjunction sets in the config. Based
> on your idea I had the following optimization in mind:
>
> Add a new table, let's call it "ACL-collision" for now. When an ACL is
> added the following operations would be performed by ovn-controller:
> - Try to add the ACL to the regular ACL table with priority PO. If
> there's no overlap on matches for any of the generated flows at
> priority PO then stop.
> - Otherwise, keep the first overlapping flow of the existing ACL and
> new ACL at priority PO in the ACL table but change its action to
> resubmit the packet to the "ACL-collision" table.
> - Add the remaining flows of the old ACL and new ACL to table
> "ACL-collision" making sure that we assign different priorities to
> flows from the two ACLs.
> - In table "ACL-collision" add a low priority "match-all" flow that
> will resubmit the packet back to the ACL table to continue regular ACL
> matching.

I just realized that if we resubmit the packet back to the ACL table
we'd have to avoid matching the flow(s) that already moved the packet
to the ACL-collision table.
I'm not sure if that can be easily done though..

>
> This approach would not affect any existing deployments where there
> are no overlapping conjunction sets.
> Also, it should maintain logical ordering of PA priorities because the
> first term of the conjunction flows (the one in the ACL table) keeps
> the same PO priority as now (that corresponds to PA).
>
> The disadvantage is that we add another step in the pipeline for
> packets that match the common part of the overlapping conjunction sets
> potentially increasing latency/jitter.
>
> Do you think this would work? Are there any other cases to take care of?
>
> Thanks,
> Dumitru
>
> >
> > As a further improvement, we may still apply the conjunction combining approach that I proposed just when the actions are also identical (which may be the case in most real world scenarios), to eliminate the *fake* overlapping conjunctions, before using different priorities, so that we have more priorities left to play with real overlapping scenarios.
> >
> > Thanks,
> > Han
> >
> > > >
> > > >  >
> > > >  > 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
> > >

On Wed, Sep 18, 2019 at 2:51 AM Dumitru Ceara <dceara@redhat.com> wrote:
>
> On Wed, Sep 18, 2019 at 9:30 AM Dumitru Ceara <dceara@redhat.com> wrote:
> >
> > On Tue, Sep 17, 2019 at 6:49 PM Han Zhou <zhouhan@gmail.com> wrote:
> > >
> > >
> > >
> > > On Tue, Sep 17, 2019 at 5:21 AM Mark Michelson <mmichels@redhat.com>
wrote:
> > > >
> > > > On 9/16/19 12:04 PM, Han Zhou wrote:
> > > > >
> > > > >
> > > > > On Mon, Sep 16, 2019 at 4:15 AM Dumitru Ceara <dceara@redhat.com
> > > > > <mailto:dceara@redhat.com>> wrote:
> > > > >  >
> > > > >  > On Sat, Sep 14, 2019 at 7:16 PM Han Zhou <zhouhan@gmail.com
> > > > > <mailto:zhouhan@gmail.com>> wrote:
> > > > >  > >
> > > > >  > >
> > > > >  > >
> > > > >  > > On Sat, Sep 14, 2019 at 9:09 AM Han Zhou <zhouhan@gmail.com
> > > > > <mailto:zhouhan@gmail.com>> wrote:
> > > > >  > > >
> > > > >  > > >
> > > > >  > > >
> > > > >  > > > On Sat, Sep 14, 2019 at 12:40 AM Numan Siddique
> > > > > <nusiddiq@redhat.com <mailto:nusiddiq@redhat.com>> wrote:
> > > > >  > > > >
> > > > >  > > > >
> > > > >  > > > >
> > > > >  > > > > On Sat, Sep 14, 2019 at 2:41 AM Daniel Alvarez Sanchez
> > > > > <dalvarez@redhat.com <mailto:dalvarez@redhat.com>> wrote:
> > > > >  > > > >>
> > > > >  > > > >> Acked-by: Daniel Alvarez <dalvarez@redhat.com
> > > > > <mailto:dalvarez@redhat.com>>
> > > > >  > > > >>
> > > > >  > > > >>
> > > > >  > > > >> On Fri, Sep 13, 2019 at 11:02 PM Mark Michelson
> > > > > <mmichels@redhat.com <mailto:mmichels@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.
> > > >
> > >
> > > Hi Mark,
> > >
> > > Thanks for pointing out. Unfortunately you are right :)
> > > So I guess the only option we have now is to play around with
priorities. Although it might be tricky, it should work. And the best part
is, priority can also solve the "partial overlapping" problem I mentioned
earlier, such as:
> > > > >  > > tcp.src == {1000, 1001} && tcp.dst == {500, 501}
> > > > >  > > tcp.src == {1001, 1002} && tcp.dst == {600, 601}
> > >
> > > Here is some more thinking about the priority solution. Today for any
user-defined ACL priority (PA), there is a corresponding OVS flow priority
(PO). PA to PO is one-to-one mapping. Now to solve the overlapping problem,
there can be more than one PO [POx..POy] mapped for each PA. The problem is
how to maintain the mappings between these two. I think there are 2 options:
> > >
> > > Option1: Whenever there is duplicate flow encountered for
user-defined priority PA, increase the range of PO from [POx..POy] to
[POx..POy+1].
> > >
> > > This approach requires dynamically adjust priorities for existing
flows. For example, initially there are flows:
> > > 1: user-defined priority 100, OVS priority 1100: <match 1>, <action 1>
> > > 2: user-defined priority 101, OVS priority 1101: <match 2>, <action 2>
> > >
> > > Now there is a logical flow requires conjunction:
> > > 3: user-defined priority 100, OVS priority 1100: A and B, <action 3>
> > >
> > > And then there is another logical flow requires conjunction, with
overlapping to the previous one:
> > > 4: user-defined priority 100, OVS priority <?>: A and C, <action 4>
> > >
> > > To handle the overlapping, we need to increase the range
corresponding to 100. It was 1100, and now it needs to be 1100 and 1101. So
we will have to adjust priority of the flow 2 from 1101 to 1102, to
preserve the original priority order. This will have high cost, and worst
thing is, it will disrupt Incremental Processing.
> > >
> > > Option2: Preserve N priorities in the range of OVS flow [POx..POx+N)
for each user-defined PA. If there are more than N ACLs with overlapping
conjunction sets, it is not supported.
> > >
> > > This approach avoids the priority readjustment problem, sacrificing
the number of priorities and number of overlapping conjunction that we can
support. The bigger N is, the less number of user-defined priority can be
supported; the smaller N is, the less number of overlapping conjunction can
be supported.
> > > Although each one has its pros and cons, I prefer option2 more than
option1, because conjunction is mainly for performance. If we end up with a
solution that sacrifice performance it may not worth enabling conjunction
at all.
> >
> > Hi Han,
> >
> > I agree that Option2 is preferable due to the cost of reassigning
> > priorities in Option1. What worries me is that we decrease the
> > available number of user priorities by a fixed factor for all cases,
> > even if there are no overlapping conjunction sets in the config. Based
> > on your idea I had the following optimization in mind:
> >
> > Add a new table, let's call it "ACL-collision" for now. When an ACL is
> > added the following operations would be performed by ovn-controller:
> > - Try to add the ACL to the regular ACL table with priority PO. If
> > there's no overlap on matches for any of the generated flows at
> > priority PO then stop.
> > - Otherwise, keep the first overlapping flow of the existing ACL and
> > new ACL at priority PO in the ACL table but change its action to
> > resubmit the packet to the "ACL-collision" table.
> > - Add the remaining flows of the old ACL and new ACL to table
> > "ACL-collision" making sure that we assign different priorities to
> > flows from the two ACLs.
> > - In table "ACL-collision" add a low priority "match-all" flow that
> > will resubmit the packet back to the ACL table to continue regular ACL
> > matching.
>
> I just realized that if we resubmit the packet back to the ACL table
> we'd have to avoid matching the flow(s) that already moved the packet
> to the ACL-collision table.
> I'm not sure if that can be easily done though..
>
> >
> > This approach would not affect any existing deployments where there
> > are no overlapping conjunction sets.
> > Also, it should maintain logical ordering of PA priorities because the
> > first term of the conjunction flows (the one in the ACL table) keeps
> > the same PO priority as now (that corresponds to PA).
> >
> > The disadvantage is that we add another step in the pipeline for
> > packets that match the common part of the overlapping conjunction sets
> > potentially increasing latency/jitter.
> >
> > Do you think this would work? Are there any other cases to take care of?
> >
> > Thanks,
> > Dumitru
> >
Hi Dumitru,

Sorry that I am not sure if I understand your proposal. When you say "keep
the first overlapping flow", what does it really mean? If there are N
elements overlapping in the sets, there will be N pairs of overlapping
flows, each with different match conditions, then how could the problem be
solved by only changing the operation on the first overlapping flow? Could
you explain a little more with the example:
> > > 1: user-defined priority 100, OVS priority 1100: <match 1>, <action 1>
> > > 2: user-defined priority 101, OVS priority 1101: <match 2>, <action 2>
> > >
> > > Now there is a logical flow requires conjunction:
> > > 3: user-defined priority 100, OVS priority 1100: A and B, <action 3>
> > >
> > > And then there is another logical flow requires conjunction, with
overlapping to the previous one:
> > > 4: user-defined priority 100, OVS priority <?>: A and C, <action 4>