diff mbox series

[ovs-dev] Factor prerequisites out of AND/OR trees with unique symbol

Message ID 20180426195406.8921-1-jkbs@redhat.com
State Changes Requested
Headers show
Series [ovs-dev] Factor prerequisites out of AND/OR trees with unique symbol | expand

Commit Message

Jakub Sitnicki April 26, 2018, 7:54 p.m. UTC 
Appending prerequisites to sub-expressions of OR that are all over one
symbol prevents the expression-to-matches converter from applying
conjunctive matching. This happens during the annotation phase.

input:      s1 == { c1, c2 } && s2 == { c3, c4 }
expanded:   (s1 == c1 || s1 == c2) && (s2 == c3 || s2 == c4)
annotated:  ((p1 && s1 == c1) || (p1 && s1 == c2)) &&
            ((p2 && s2 == c3) || (p2 && s2 == c4))
normalized: (p1 && p2 && s1 == c1 && s2 == c3) ||
            (p1 && p2 && s1 == c1 && s2 == c4) ||
	    (p1 && p2 && s1 == c2 && s2 == c3) ||
	    (p1 && p2 && s1 == c2 && s2 == c4)

Where s1,s2 - symbols, c1..c4 - constants, p1,p2 - prerequisites.

Since sub-expressions of OR trees that are over one symbol all have the
same prerequisites, we can factor them out leaving the OR tree in tact,
and enabling the converter to apply conjunctive matching to
AND(OR(clause)) trees.

Going back to our example this change gives us:

input:      s1 == { c1, c2 } && s2 == { c3, c4 }
expanded:   (s1 == c1 || s1 == c2) && (s2 == c3 || s2 == c4)
annotated:  (s1 == c1 || s1 == c2) && p1 && (s2 == c3 || s2 == c4) && p2
normalized: p1 && p2 && (s1 == c1 || s1 == c2) && (s2 == c3 || s2 == c4)

We also factor out the prerequisites out of pure AND or mixed AND/OR
trees to keep the common code path, but in this case we don't gain
anything.

Signed-off-by: Jakub Sitnicki <jkbs@redhat.com>
---

This is an alternative to "Enhance conjunctive match support in OVN" patch from
Numan Siddique [1].

[1] https://patchwork.ozlabs.org/patch/874433/

 ovn/lib/expr.c | 55 +++++++++++++++++++++++++++++++++++++++++++++----------
 tests/ovn.at   |  4 ++--
 2 files changed, 47 insertions(+), 12 deletions(-)

--
2.14.3

Comments

Mark Michelson May 7, 2018, 4:27 p.m. UTC | #1 
Hi Jakub,

I finally got around to taking a look at this. I made up some imaginary 
expressions to try to see if I could find a way that this would break, 
but it looks good to me in each case.

Acked-by: Mark Michelson <mmichels@redhat.com>

On 04/26/2018 03:54 PM, Jakub Sitnicki wrote:
> Appending prerequisites to sub-expressions of OR that are all over one
> symbol prevents the expression-to-matches converter from applying
> conjunctive matching. This happens during the annotation phase.
> 
> input:      s1 == { c1, c2 } && s2 == { c3, c4 }
> expanded:   (s1 == c1 || s1 == c2) && (s2 == c3 || s2 == c4)
> annotated:  ((p1 && s1 == c1) || (p1 && s1 == c2)) &&
>              ((p2 && s2 == c3) || (p2 && s2 == c4))
> normalized: (p1 && p2 && s1 == c1 && s2 == c3) ||
>              (p1 && p2 && s1 == c1 && s2 == c4) ||
> 	    (p1 && p2 && s1 == c2 && s2 == c3) ||
> 	    (p1 && p2 && s1 == c2 && s2 == c4)
> 
> Where s1,s2 - symbols, c1..c4 - constants, p1,p2 - prerequisites.
> 
> Since sub-expressions of OR trees that are over one symbol all have the
> same prerequisites, we can factor them out leaving the OR tree in tact,
> and enabling the converter to apply conjunctive matching to
> AND(OR(clause)) trees.
> 
> Going back to our example this change gives us:
> 
> input:      s1 == { c1, c2 } && s2 == { c3, c4 }
> expanded:   (s1 == c1 || s1 == c2) && (s2 == c3 || s2 == c4)
> annotated:  (s1 == c1 || s1 == c2) && p1 && (s2 == c3 || s2 == c4) && p2
> normalized: p1 && p2 && (s1 == c1 || s1 == c2) && (s2 == c3 || s2 == c4)
> 
> We also factor out the prerequisites out of pure AND or mixed AND/OR
> trees to keep the common code path, but in this case we don't gain
> anything.
> 
> Signed-off-by: Jakub Sitnicki <jkbs@redhat.com>
> ---
> 
> This is an alternative to "Enhance conjunctive match support in OVN" patch from
> Numan Siddique [1].
> 
> [1] https://patchwork.ozlabs.org/patch/874433/
> 
>   ovn/lib/expr.c | 55 +++++++++++++++++++++++++++++++++++++++++++++----------
>   tests/ovn.at   |  4 ++--
>   2 files changed, 47 insertions(+), 12 deletions(-)
> 
> diff --git a/ovn/lib/expr.c b/ovn/lib/expr.c
> index 5840ef871..9dd8d6f17 100644
> --- a/ovn/lib/expr.c
> +++ b/ovn/lib/expr.c
> @@ -32,6 +32,13 @@
> 
>   VLOG_DEFINE_THIS_MODULE(expr);
> 
> +static const struct expr_symbol *
> +expr_get_unique_symbol(const struct expr *expr);
> +
> +struct expr *
> +expr_annotate__(struct expr *expr, const struct shash *symtab,
> +                bool append_prereqs, struct ovs_list *nesting, char **errorp);
> +
>   static struct expr *parse_and_annotate(const char *s,
>                                          const struct shash *symtab,
>                                          struct ovs_list *nesting,
> @@ -1658,9 +1665,6 @@ struct annotation_nesting {
>       const struct expr_symbol *symbol;
>   };
> 
> -struct expr *expr_annotate__(struct expr *, const struct shash *symtab,
> -                             struct ovs_list *nesting, char **errorp);
> -
>   static struct expr *
>   parse_and_annotate(const char *s, const struct shash *symtab,
>                      struct ovs_list *nesting, char **errorp)
> @@ -1670,7 +1674,7 @@ parse_and_annotate(const char *s, const struct shash *symtab,
> 
>       expr = expr_parse_string(s, symtab, NULL, NULL, &error);
>       if (expr) {
> -        expr = expr_annotate__(expr, symtab, nesting, &error);
> +        expr = expr_annotate__(expr, symtab, true, nesting, &error);
>       }
>       if (expr) {
>           *errorp = NULL;
> @@ -1685,7 +1689,7 @@ parse_and_annotate(const char *s, const struct shash *symtab,
> 
>   static struct expr *
>   expr_annotate_cmp(struct expr *expr, const struct shash *symtab,
> -                  struct ovs_list *nesting, char **errorp)
> +                  bool append_prereqs, struct ovs_list *nesting, char **errorp)
>   {
>       const struct expr_symbol *symbol = expr->cmp.symbol;
>       const struct annotation_nesting *iter;
> @@ -1703,7 +1707,7 @@ expr_annotate_cmp(struct expr *expr, const struct shash *symtab,
>       ovs_list_push_back(nesting, &an.node);
> 
>       struct expr *prereqs = NULL;
> -    if (symbol->prereqs) {
> +    if (append_prereqs && symbol->prereqs) {
>           prereqs = parse_and_annotate(symbol->prereqs, symtab, nesting, errorp);
>           if (!prereqs) {
>               goto error;
> @@ -1744,21 +1748,46 @@ expr_annotate_cmp(struct expr *expr, const struct shash *symtab,
>       return NULL;
>   }
> 
> +/* Append (logical AND) prereqs for given symbol to the expression. */
> +static struct expr *
> +expr_append_prereqs(struct expr *expr, const struct expr_symbol *symbol,
> +                    const struct shash *symtab, struct ovs_list *nesting,
> +                    char **errorp)
> +{
> +    struct expr *prereqs = NULL;
> +
> +    if (symbol->prereqs) {
> +        prereqs = parse_and_annotate(symbol->prereqs, symtab, nesting, errorp);
> +        if (!prereqs) {
> +            goto error;
> +        }
> +    }
> +
> +    return prereqs ? expr_combine(EXPR_T_AND, expr, prereqs) : expr;
> +
> +error:
> +    expr_destroy(expr);
> +    expr_destroy(prereqs);
> +    return NULL;
> +}
> +
>   struct expr *
>   expr_annotate__(struct expr *expr, const struct shash *symtab,
> -                struct ovs_list *nesting, char **errorp)
> +                bool append_prereqs, struct ovs_list *nesting, char **errorp)
>   {
>       switch (expr->type) {
>       case EXPR_T_CMP:
> -        return expr_annotate_cmp(expr, symtab, nesting, errorp);
> +        return expr_annotate_cmp(expr, symtab, append_prereqs, nesting,
> +                                 errorp);
> 
>       case EXPR_T_AND:
>       case EXPR_T_OR: {
> +        const struct expr_symbol *unique_symbol = expr_get_unique_symbol(expr);
>           struct expr *sub, *next;
> 
>           LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
>               ovs_list_remove(&sub->node);
> -            struct expr *new_sub = expr_annotate__(sub, symtab,
> +            struct expr *new_sub = expr_annotate__(sub, symtab, !unique_symbol,
>                                                      nesting, errorp);
>               if (!new_sub) {
>                   expr_destroy(expr);
> @@ -1767,6 +1796,12 @@ expr_annotate__(struct expr *expr, const struct shash *symtab,
>               expr_insert_andor(expr, next, new_sub);
>           }
>           *errorp = NULL;
> +
> +        if (unique_symbol) {
> +            expr = expr_append_prereqs(expr, unique_symbol, symtab, nesting,
> +                                       errorp);
> +        }
> +
>           return expr;
>       }
> 
> @@ -1802,7 +1837,7 @@ struct expr *
>   expr_annotate(struct expr *expr, const struct shash *symtab, char **errorp)
>   {
>       struct ovs_list nesting = OVS_LIST_INITIALIZER(&nesting);
> -    return expr_annotate__(expr, symtab, &nesting, errorp);
> +    return expr_annotate__(expr, symtab, true, &nesting, errorp);
>   }
>   
>   static struct expr *
> diff --git a/tests/ovn.at b/tests/ovn.at
> index 8fe4c522a..4abf44b06 100644
> --- a/tests/ovn.at
> +++ b/tests/ovn.at
> @@ -365,7 +365,7 @@ AT_DATA([test-cases.txt], [[
>   ip4.src == 1.2.3.4 => ip4.src == 0x1020304 && eth.type == 0x800
>   ip4.src != 1.2.3.4 => ip4.src != 0x1020304 && eth.type == 0x800
>   ip.proto == 123 => ip.proto == 0x7b && (eth.type == 0x800 || eth.type == 0x86dd)
> -ip.proto == {123, 234} => (ip.proto == 0x7b && (eth.type == 0x800 || eth.type == 0x86dd)) || (ip.proto == 0xea && (eth.type == 0x800 || eth.type == 0x86dd))
> +ip.proto == {123, 234} => (ip.proto == 0x7b || ip.proto == 0xea) && (eth.type == 0x800 || eth.type == 0x86dd)
>   ip4.src == 1.2.3.4 && ip4.dst == 5.6.7.8 => ip4.src == 0x1020304 && eth.type == 0x800 && ip4.dst == 0x5060708 && eth.type == 0x800
> 
>   ip => eth.type == 0x800 || eth.type == 0x86dd
> @@ -1161,7 +1161,7 @@ get_nd(xxreg0, ip6.dst);
>   # put_nd
>   put_nd(inport, nd.target, nd.sll);
>       encodes as push:NXM_NX_XXREG0[],push:NXM_OF_ETH_SRC[],push:NXM_NX_ND_SLL[],push:NXM_NX_ND_TARGET[],pop:NXM_NX_XXREG0[],pop:NXM_OF_ETH_SRC[],controller(userdata=00.00.00.04.00.00.00.00),pop:NXM_OF_ETH_SRC[],pop:NXM_NX_XXREG0[]
> -    has prereqs ((icmp6.type == 0x87 && eth.type == 0x86dd && ip.proto == 0x3a && (eth.type == 0x800 || eth.type == 0x86dd)) || (icmp6.type == 0x88 && eth.type == 0x86dd && ip.proto == 0x3a && (eth.type == 0x800 || eth.type == 0x86dd))) && icmp6.code == 0 && eth.type == 0x86dd && ip.proto == 0x3a && (eth.type == 0x800 || eth.type == 0x86dd) && ip.ttl == 0xff && (eth.type == 0x800 || eth.type == 0x86dd) && icmp6.type == 0x87 && eth.type == 0x86dd && ip.proto == 0x3a && (eth.type == 0x800 || eth.type == 0x86dd) && icmp6.code == 0 && eth.type == 0x86dd && ip.proto == 0x3a && (eth.type == 0x800 || eth.type == 0x86dd) && ip.ttl == 0xff && (eth.type == 0x800 || eth.type == 0x86dd)
> +    has prereqs (icmp6.type == 0x87 || icmp6.type == 0x88) && eth.type == 0x86dd && ip.proto == 0x3a && (eth.type == 0x800 || eth.type == 0x86dd) && icmp6.code == 0 && eth.type == 0x86dd && ip.proto == 0x3a && (eth.type == 0x800 || eth.type == 0x86dd) && ip.ttl == 0xff && (eth.type == 0x800 || eth.type == 0x86dd) && icmp6.type == 0x87 && eth.type == 0x86dd && ip.proto == 0x3a && (eth.type == 0x800 || eth.type == 0x86dd) && icmp6.code == 0 && eth.type == 0x86dd && ip.proto == 0x3a && (eth.type == 0x800 || eth.type == 0x86dd) && ip.ttl == 0xff && (eth.type == 0x800 || eth.type == 0x86dd)
> 
>   # put_dhcpv6_opts
>   reg1[0] = put_dhcpv6_opts(ia_addr = ae70::4, server_id = 00:00:00:00:10:02);
> --
> 2.14.3
> _______________________________________________
> dev mailing list
> dev@openvswitch.org
> https://mail.openvswitch.org/mailman/listinfo/ovs-dev
>
Numan Siddique May 8, 2018, 6:17 a.m. UTC | #2 
On Mon, May 7, 2018 at 9:57 PM, Mark Michelson <mmichels@redhat.com> wrote:

> Hi Jakub,
>
> I finally got around to taking a look at this. I made up some imaginary
> expressions to try to see if I could find a way that this would break, but
> it looks good to me in each case.
>
> Acked-by: Mark Michelson <mmichels@redhat.com>



Same here. I tested with all the combinations I could think of.

Acked-by: Numan Siddique <nusiddiq@redhat.com>


>
>
> On 04/26/2018 03:54 PM, Jakub Sitnicki wrote:
>
>> Appending prerequisites to sub-expressions of OR that are all over one
>> symbol prevents the expression-to-matches converter from applying
>> conjunctive matching. This happens during the annotation phase.
>>
>> input:      s1 == { c1, c2 } && s2 == { c3, c4 }
>> expanded:   (s1 == c1 || s1 == c2) && (s2 == c3 || s2 == c4)
>> annotated:  ((p1 && s1 == c1) || (p1 && s1 == c2)) &&
>>              ((p2 && s2 == c3) || (p2 && s2 == c4))
>> normalized: (p1 && p2 && s1 == c1 && s2 == c3) ||
>>              (p1 && p2 && s1 == c1 && s2 == c4) ||
>>             (p1 && p2 && s1 == c2 && s2 == c3) ||
>>             (p1 && p2 && s1 == c2 && s2 == c4)
>>
>> Where s1,s2 - symbols, c1..c4 - constants, p1,p2 - prerequisites.
>>
>> Since sub-expressions of OR trees that are over one symbol all have the
>> same prerequisites, we can factor them out leaving the OR tree in tact,
>> and enabling the converter to apply conjunctive matching to
>> AND(OR(clause)) trees.
>>
>> Going back to our example this change gives us:
>>
>> input:      s1 == { c1, c2 } && s2 == { c3, c4 }
>> expanded:   (s1 == c1 || s1 == c2) && (s2 == c3 || s2 == c4)
>> annotated:  (s1 == c1 || s1 == c2) && p1 && (s2 == c3 || s2 == c4) && p2
>> normalized: p1 && p2 && (s1 == c1 || s1 == c2) && (s2 == c3 || s2 == c4)
>>
>> We also factor out the prerequisites out of pure AND or mixed AND/OR
>> trees to keep the common code path, but in this case we don't gain
>> anything.
>>
>> Signed-off-by: Jakub Sitnicki <jkbs@redhat.com>
>> ---
>>
>> This is an alternative to "Enhance conjunctive match support in OVN"
>> patch from
>> Numan Siddique [1].
>>
>> [1] https://patchwork.ozlabs.org/patch/874433/
>>
>>   ovn/lib/expr.c | 55 ++++++++++++++++++++++++++++++
>> +++++++++++++++----------
>>   tests/ovn.at   |  4 ++--
>>   2 files changed, 47 insertions(+), 12 deletions(-)
>>
>> diff --git a/ovn/lib/expr.c b/ovn/lib/expr.c
>> index 5840ef871..9dd8d6f17 100644
>> --- a/ovn/lib/expr.c
>> +++ b/ovn/lib/expr.c
>> @@ -32,6 +32,13 @@
>>
>>   VLOG_DEFINE_THIS_MODULE(expr);
>>
>> +static const struct expr_symbol *
>> +expr_get_unique_symbol(const struct expr *expr);
>> +
>> +struct expr *
>> +expr_annotate__(struct expr *expr, const struct shash *symtab,
>> +                bool append_prereqs, struct ovs_list *nesting, char
>> **errorp);
>> +
>>   static struct expr *parse_and_annotate(const char *s,
>>                                          const struct shash *symtab,
>>                                          struct ovs_list *nesting,
>> @@ -1658,9 +1665,6 @@ struct annotation_nesting {
>>       const struct expr_symbol *symbol;
>>   };
>>
>> -struct expr *expr_annotate__(struct expr *, const struct shash *symtab,
>> -                             struct ovs_list *nesting, char **errorp);
>> -
>>   static struct expr *
>>   parse_and_annotate(const char *s, const struct shash *symtab,
>>                      struct ovs_list *nesting, char **errorp)
>> @@ -1670,7 +1674,7 @@ parse_and_annotate(const char *s, const struct
>> shash *symtab,
>>
>>       expr = expr_parse_string(s, symtab, NULL, NULL, &error);
>>       if (expr) {
>> -        expr = expr_annotate__(expr, symtab, nesting, &error);
>> +        expr = expr_annotate__(expr, symtab, true, nesting, &error);
>>       }
>>       if (expr) {
>>           *errorp = NULL;
>> @@ -1685,7 +1689,7 @@ parse_and_annotate(const char *s, const struct
>> shash *symtab,
>>
>>   static struct expr *
>>   expr_annotate_cmp(struct expr *expr, const struct shash *symtab,
>> -                  struct ovs_list *nesting, char **errorp)
>> +                  bool append_prereqs, struct ovs_list *nesting, char
>> **errorp)
>>   {
>>       const struct expr_symbol *symbol = expr->cmp.symbol;
>>       const struct annotation_nesting *iter;
>> @@ -1703,7 +1707,7 @@ expr_annotate_cmp(struct expr *expr, const struct
>> shash *symtab,
>>       ovs_list_push_back(nesting, &an.node);
>>
>>       struct expr *prereqs = NULL;
>> -    if (symbol->prereqs) {
>> +    if (append_prereqs && symbol->prereqs) {
>>           prereqs = parse_and_annotate(symbol->prereqs, symtab, nesting,
>> errorp);
>>           if (!prereqs) {
>>               goto error;
>> @@ -1744,21 +1748,46 @@ expr_annotate_cmp(struct expr *expr, const struct
>> shash *symtab,
>>       return NULL;
>>   }
>>
>> +/* Append (logical AND) prereqs for given symbol to the expression. */
>> +static struct expr *
>> +expr_append_prereqs(struct expr *expr, const struct expr_symbol *symbol,
>> +                    const struct shash *symtab, struct ovs_list *nesting,
>> +                    char **errorp)
>> +{
>> +    struct expr *prereqs = NULL;
>> +
>> +    if (symbol->prereqs) {
>> +        prereqs = parse_and_annotate(symbol->prereqs, symtab, nesting,
>> errorp);
>> +        if (!prereqs) {
>> +            goto error;
>> +        }
>> +    }
>> +
>> +    return prereqs ? expr_combine(EXPR_T_AND, expr, prereqs) : expr;
>> +
>> +error:
>> +    expr_destroy(expr);
>> +    expr_destroy(prereqs);
>> +    return NULL;
>> +}
>> +
>>   struct expr *
>>   expr_annotate__(struct expr *expr, const struct shash *symtab,
>> -                struct ovs_list *nesting, char **errorp)
>> +                bool append_prereqs, struct ovs_list *nesting, char
>> **errorp)
>>   {
>>       switch (expr->type) {
>>       case EXPR_T_CMP:
>> -        return expr_annotate_cmp(expr, symtab, nesting, errorp);
>> +        return expr_annotate_cmp(expr, symtab, append_prereqs, nesting,
>> +                                 errorp);
>>
>>       case EXPR_T_AND:
>>       case EXPR_T_OR: {
>> +        const struct expr_symbol *unique_symbol =
>> expr_get_unique_symbol(expr);
>>           struct expr *sub, *next;
>>
>>           LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
>>               ovs_list_remove(&sub->node);
>> -            struct expr *new_sub = expr_annotate__(sub, symtab,
>> +            struct expr *new_sub = expr_annotate__(sub, symtab,
>> !unique_symbol,
>>                                                      nesting, errorp);
>>               if (!new_sub) {
>>                   expr_destroy(expr);
>> @@ -1767,6 +1796,12 @@ expr_annotate__(struct expr *expr, const struct
>> shash *symtab,
>>               expr_insert_andor(expr, next, new_sub);
>>           }
>>           *errorp = NULL;
>> +
>> +        if (unique_symbol) {
>> +            expr = expr_append_prereqs(expr, unique_symbol, symtab,
>> nesting,
>> +                                       errorp);
>> +        }
>> +
>>           return expr;
>>       }
>>
>> @@ -1802,7 +1837,7 @@ struct expr *
>>   expr_annotate(struct expr *expr, const struct shash *symtab, char
>> **errorp)
>>   {
>>       struct ovs_list nesting = OVS_LIST_INITIALIZER(&nesting);
>> -    return expr_annotate__(expr, symtab, &nesting, errorp);
>> +    return expr_annotate__(expr, symtab, true, &nesting, errorp);
>>   }
>>
>>   static struct expr *
>> diff --git a/tests/ovn.at b/tests/ovn.at
>> index 8fe4c522a..4abf44b06 100644
>> --- a/tests/ovn.at
>> +++ b/tests/ovn.at
>> @@ -365,7 +365,7 @@ AT_DATA([test-cases.txt], [[
>>   ip4.src == 1.2.3.4 => ip4.src == 0x1020304 && eth.type == 0x800
>>   ip4.src != 1.2.3.4 => ip4.src != 0x1020304 && eth.type == 0x800
>>   ip.proto == 123 => ip.proto == 0x7b && (eth.type == 0x800 || eth.type
>> == 0x86dd)
>> -ip.proto == {123, 234} => (ip.proto == 0x7b && (eth.type == 0x800 ||
>> eth.type == 0x86dd)) || (ip.proto == 0xea && (eth.type == 0x800 || eth.type
>> == 0x86dd))
>> +ip.proto == {123, 234} => (ip.proto == 0x7b || ip.proto == 0xea) &&
>> (eth.type == 0x800 || eth.type == 0x86dd)
>>   ip4.src == 1.2.3.4 && ip4.dst == 5.6.7.8 => ip4.src == 0x1020304 &&
>> eth.type == 0x800 && ip4.dst == 0x5060708 && eth.type == 0x800
>>
>>   ip => eth.type == 0x800 || eth.type == 0x86dd
>> @@ -1161,7 +1161,7 @@ get_nd(xxreg0, ip6.dst);
>>   # put_nd
>>   put_nd(inport, nd.target, nd.sll);
>>       encodes as push:NXM_NX_XXREG0[],push:NXM_
>> OF_ETH_SRC[],push:NXM_NX_ND_SLL[],push:NXM_NX_ND_TARGET[],po
>> p:NXM_NX_XXREG0[],pop:NXM_OF_ETH_SRC[],controller(userdata=
>> 00.00.00.04.00.00.00.00),pop:NXM_OF_ETH_SRC[],pop:NXM_NX_XXREG0[]
>> -    has prereqs ((icmp6.type == 0x87 && eth.type == 0x86dd && ip.proto
>> == 0x3a && (eth.type == 0x800 || eth.type == 0x86dd)) || (icmp6.type ==
>> 0x88 && eth.type == 0x86dd && ip.proto == 0x3a && (eth.type == 0x800 ||
>> eth.type == 0x86dd))) && icmp6.code == 0 && eth.type == 0x86dd && ip.proto
>> == 0x3a && (eth.type == 0x800 || eth.type == 0x86dd) && ip.ttl == 0xff &&
>> (eth.type == 0x800 || eth.type == 0x86dd) && icmp6.type == 0x87 && eth.type
>> == 0x86dd && ip.proto == 0x3a && (eth.type == 0x800 || eth.type == 0x86dd)
>> && icmp6.code == 0 && eth.type == 0x86dd && ip.proto == 0x3a && (eth.type
>> == 0x800 || eth.type == 0x86dd) && ip.ttl == 0xff && (eth.type == 0x800 ||
>> eth.type == 0x86dd)
>> +    has prereqs (icmp6.type == 0x87 || icmp6.type == 0x88) && eth.type
>> == 0x86dd && ip.proto == 0x3a && (eth.type == 0x800 || eth.type == 0x86dd)
>> && icmp6.code == 0 && eth.type == 0x86dd && ip.proto == 0x3a && (eth.type
>> == 0x800 || eth.type == 0x86dd) && ip.ttl == 0xff && (eth.type == 0x800 ||
>> eth.type == 0x86dd) && icmp6.type == 0x87 && eth.type == 0x86dd && ip.proto
>> == 0x3a && (eth.type == 0x800 || eth.type == 0x86dd) && icmp6.code == 0 &&
>> eth.type == 0x86dd && ip.proto == 0x3a && (eth.type == 0x800 || eth.type ==
>> 0x86dd) && ip.ttl == 0xff && (eth.type == 0x800 || eth.type == 0x86dd)
>>
>>   # put_dhcpv6_opts
>>   reg1[0] = put_dhcpv6_opts(ia_addr = ae70::4, server_id =
>> 00:00:00:00:10:02);
>> --
>> 2.14.3
>> _______________________________________________
>> dev mailing list
>> dev@openvswitch.org
>> https://mail.openvswitch.org/mailman/listinfo/ovs-dev
>>
>>
> _______________________________________________
> dev mailing list
> dev@openvswitch.org
> https://mail.openvswitch.org/mailman/listinfo/ovs-dev
>
Jakub Sitnicki May 8, 2018, 12:09 p.m. UTC | #3 
On Tue, 8 May 2018 11:47:34 +0530
Numan Siddique <nusiddiq@redhat.com> wrote:

> On Mon, May 7, 2018 at 9:57 PM, Mark Michelson <mmichels@redhat.com> wrote:
> 
> > Hi Jakub,
> >
> > I finally got around to taking a look at this. I made up some imaginary
> > expressions to try to see if I could find a way that this would break, but
> > it looks good to me in each case.
> >
> > Acked-by: Mark Michelson <mmichels@redhat.com>  
> 
> 
> 
> Same here. I tested with all the combinations I could think of.
> 
> Acked-by: Numan Siddique <nusiddiq@redhat.com>

@Mark, @Numan, thanks for taking the time to test it out and review.

@Numan, are you planning on submitting the tests from your
conjunctive match support patchset? They are really valuable. If you
would like, I can help with it.

Thanks,
Jakub

> 
> 
> >
> >
> > On 04/26/2018 03:54 PM, Jakub Sitnicki wrote:
> >  
> >> Appending prerequisites to sub-expressions of OR that are all over one
> >> symbol prevents the expression-to-matches converter from applying
> >> conjunctive matching. This happens during the annotation phase.
> >>
> >> input:      s1 == { c1, c2 } && s2 == { c3, c4 }
> >> expanded:   (s1 == c1 || s1 == c2) && (s2 == c3 || s2 == c4)
> >> annotated:  ((p1 && s1 == c1) || (p1 && s1 == c2)) &&
> >>              ((p2 && s2 == c3) || (p2 && s2 == c4))
> >> normalized: (p1 && p2 && s1 == c1 && s2 == c3) ||
> >>              (p1 && p2 && s1 == c1 && s2 == c4) ||
> >>             (p1 && p2 && s1 == c2 && s2 == c3) ||
> >>             (p1 && p2 && s1 == c2 && s2 == c4)
> >>
> >> Where s1,s2 - symbols, c1..c4 - constants, p1,p2 - prerequisites.
> >>
> >> Since sub-expressions of OR trees that are over one symbol all have the
> >> same prerequisites, we can factor them out leaving the OR tree in tact,
> >> and enabling the converter to apply conjunctive matching to
> >> AND(OR(clause)) trees.
> >>
> >> Going back to our example this change gives us:
> >>
> >> input:      s1 == { c1, c2 } && s2 == { c3, c4 }
> >> expanded:   (s1 == c1 || s1 == c2) && (s2 == c3 || s2 == c4)
> >> annotated:  (s1 == c1 || s1 == c2) && p1 && (s2 == c3 || s2 == c4) && p2
> >> normalized: p1 && p2 && (s1 == c1 || s1 == c2) && (s2 == c3 || s2 == c4)
> >>
> >> We also factor out the prerequisites out of pure AND or mixed AND/OR
> >> trees to keep the common code path, but in this case we don't gain
> >> anything.
> >>
> >> Signed-off-by: Jakub Sitnicki <jkbs@redhat.com>
> >> ---
> >>
> >> This is an alternative to "Enhance conjunctive match support in OVN"
> >> patch from
> >> Numan Siddique [1].
> >>
> >> [1] https://patchwork.ozlabs.org/patch/874433/
> >>
> >>   ovn/lib/expr.c | 55 ++++++++++++++++++++++++++++++
> >> +++++++++++++++----------
> >>   tests/ovn.at   |  4 ++--
> >>   2 files changed, 47 insertions(+), 12 deletions(-)
> >>
> >> diff --git a/ovn/lib/expr.c b/ovn/lib/expr.c
> >> index 5840ef871..9dd8d6f17 100644
> >> --- a/ovn/lib/expr.c
> >> +++ b/ovn/lib/expr.c
> >> @@ -32,6 +32,13 @@
> >>
> >>   VLOG_DEFINE_THIS_MODULE(expr);
> >>
> >> +static const struct expr_symbol *
> >> +expr_get_unique_symbol(const struct expr *expr);
> >> +
> >> +struct expr *
> >> +expr_annotate__(struct expr *expr, const struct shash *symtab,
> >> +                bool append_prereqs, struct ovs_list *nesting, char
> >> **errorp);
> >> +
> >>   static struct expr *parse_and_annotate(const char *s,
> >>                                          const struct shash *symtab,
> >>                                          struct ovs_list *nesting,
> >> @@ -1658,9 +1665,6 @@ struct annotation_nesting {
> >>       const struct expr_symbol *symbol;
> >>   };
> >>
> >> -struct expr *expr_annotate__(struct expr *, const struct shash *symtab,
> >> -                             struct ovs_list *nesting, char **errorp);
> >> -
> >>   static struct expr *
> >>   parse_and_annotate(const char *s, const struct shash *symtab,
> >>                      struct ovs_list *nesting, char **errorp)
> >> @@ -1670,7 +1674,7 @@ parse_and_annotate(const char *s, const struct
> >> shash *symtab,
> >>
> >>       expr = expr_parse_string(s, symtab, NULL, NULL, &error);
> >>       if (expr) {
> >> -        expr = expr_annotate__(expr, symtab, nesting, &error);
> >> +        expr = expr_annotate__(expr, symtab, true, nesting, &error);
> >>       }
> >>       if (expr) {
> >>           *errorp = NULL;
> >> @@ -1685,7 +1689,7 @@ parse_and_annotate(const char *s, const struct
> >> shash *symtab,
> >>
> >>   static struct expr *
> >>   expr_annotate_cmp(struct expr *expr, const struct shash *symtab,
> >> -                  struct ovs_list *nesting, char **errorp)
> >> +                  bool append_prereqs, struct ovs_list *nesting, char
> >> **errorp)
> >>   {
> >>       const struct expr_symbol *symbol = expr->cmp.symbol;
> >>       const struct annotation_nesting *iter;
> >> @@ -1703,7 +1707,7 @@ expr_annotate_cmp(struct expr *expr, const struct
> >> shash *symtab,
> >>       ovs_list_push_back(nesting, &an.node);
> >>
> >>       struct expr *prereqs = NULL;
> >> -    if (symbol->prereqs) {
> >> +    if (append_prereqs && symbol->prereqs) {
> >>           prereqs = parse_and_annotate(symbol->prereqs, symtab, nesting,
> >> errorp);
> >>           if (!prereqs) {
> >>               goto error;
> >> @@ -1744,21 +1748,46 @@ expr_annotate_cmp(struct expr *expr, const struct
> >> shash *symtab,
> >>       return NULL;
> >>   }
> >>
> >> +/* Append (logical AND) prereqs for given symbol to the expression. */
> >> +static struct expr *
> >> +expr_append_prereqs(struct expr *expr, const struct expr_symbol *symbol,
> >> +                    const struct shash *symtab, struct ovs_list *nesting,
> >> +                    char **errorp)
> >> +{
> >> +    struct expr *prereqs = NULL;
> >> +
> >> +    if (symbol->prereqs) {
> >> +        prereqs = parse_and_annotate(symbol->prereqs, symtab, nesting,
> >> errorp);
> >> +        if (!prereqs) {
> >> +            goto error;
> >> +        }
> >> +    }
> >> +
> >> +    return prereqs ? expr_combine(EXPR_T_AND, expr, prereqs) : expr;
> >> +
> >> +error:
> >> +    expr_destroy(expr);
> >> +    expr_destroy(prereqs);
> >> +    return NULL;
> >> +}
> >> +
> >>   struct expr *
> >>   expr_annotate__(struct expr *expr, const struct shash *symtab,
> >> -                struct ovs_list *nesting, char **errorp)
> >> +                bool append_prereqs, struct ovs_list *nesting, char
> >> **errorp)
> >>   {
> >>       switch (expr->type) {
> >>       case EXPR_T_CMP:
> >> -        return expr_annotate_cmp(expr, symtab, nesting, errorp);
> >> +        return expr_annotate_cmp(expr, symtab, append_prereqs, nesting,
> >> +                                 errorp);
> >>
> >>       case EXPR_T_AND:
> >>       case EXPR_T_OR: {
> >> +        const struct expr_symbol *unique_symbol =
> >> expr_get_unique_symbol(expr);
> >>           struct expr *sub, *next;
> >>
> >>           LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
> >>               ovs_list_remove(&sub->node);
> >> -            struct expr *new_sub = expr_annotate__(sub, symtab,
> >> +            struct expr *new_sub = expr_annotate__(sub, symtab,
> >> !unique_symbol,
> >>                                                      nesting, errorp);
> >>               if (!new_sub) {
> >>                   expr_destroy(expr);
> >> @@ -1767,6 +1796,12 @@ expr_annotate__(struct expr *expr, const struct
> >> shash *symtab,
> >>               expr_insert_andor(expr, next, new_sub);
> >>           }
> >>           *errorp = NULL;
> >> +
> >> +        if (unique_symbol) {
> >> +            expr = expr_append_prereqs(expr, unique_symbol, symtab,
> >> nesting,
> >> +                                       errorp);
> >> +        }
> >> +
> >>           return expr;
> >>       }
> >>
> >> @@ -1802,7 +1837,7 @@ struct expr *
> >>   expr_annotate(struct expr *expr, const struct shash *symtab, char
> >> **errorp)
> >>   {
> >>       struct ovs_list nesting = OVS_LIST_INITIALIZER(&nesting);
> >> -    return expr_annotate__(expr, symtab, &nesting, errorp);
> >> +    return expr_annotate__(expr, symtab, true, &nesting, errorp);
> >>   }
> >>
> >>   static struct expr *
> >> diff --git a/tests/ovn.at b/tests/ovn.at
> >> index 8fe4c522a..4abf44b06 100644
> >> --- a/tests/ovn.at
> >> +++ b/tests/ovn.at
> >> @@ -365,7 +365,7 @@ AT_DATA([test-cases.txt], [[
> >>   ip4.src == 1.2.3.4 => ip4.src == 0x1020304 && eth.type == 0x800
> >>   ip4.src != 1.2.3.4 => ip4.src != 0x1020304 && eth.type == 0x800
> >>   ip.proto == 123 => ip.proto == 0x7b && (eth.type == 0x800 || eth.type
> >> == 0x86dd)
> >> -ip.proto == {123, 234} => (ip.proto == 0x7b && (eth.type == 0x800 ||
> >> eth.type == 0x86dd)) || (ip.proto == 0xea && (eth.type == 0x800 || eth.type
> >> == 0x86dd))
> >> +ip.proto == {123, 234} => (ip.proto == 0x7b || ip.proto == 0xea) &&
> >> (eth.type == 0x800 || eth.type == 0x86dd)
> >>   ip4.src == 1.2.3.4 && ip4.dst == 5.6.7.8 => ip4.src == 0x1020304 &&
> >> eth.type == 0x800 && ip4.dst == 0x5060708 && eth.type == 0x800
> >>
> >>   ip => eth.type == 0x800 || eth.type == 0x86dd
> >> @@ -1161,7 +1161,7 @@ get_nd(xxreg0, ip6.dst);
> >>   # put_nd
> >>   put_nd(inport, nd.target, nd.sll);
> >>       encodes as push:NXM_NX_XXREG0[],push:NXM_
> >> OF_ETH_SRC[],push:NXM_NX_ND_SLL[],push:NXM_NX_ND_TARGET[],po
> >> p:NXM_NX_XXREG0[],pop:NXM_OF_ETH_SRC[],controller(userdata=
> >> 00.00.00.04.00.00.00.00),pop:NXM_OF_ETH_SRC[],pop:NXM_NX_XXREG0[]
> >> -    has prereqs ((icmp6.type == 0x87 && eth.type == 0x86dd && ip.proto
> >> == 0x3a && (eth.type == 0x800 || eth.type == 0x86dd)) || (icmp6.type ==
> >> 0x88 && eth.type == 0x86dd && ip.proto == 0x3a && (eth.type == 0x800 ||
> >> eth.type == 0x86dd))) && icmp6.code == 0 && eth.type == 0x86dd && ip.proto
> >> == 0x3a && (eth.type == 0x800 || eth.type == 0x86dd) && ip.ttl == 0xff &&
> >> (eth.type == 0x800 || eth.type == 0x86dd) && icmp6.type == 0x87 && eth.type
> >> == 0x86dd && ip.proto == 0x3a && (eth.type == 0x800 || eth.type == 0x86dd)
> >> && icmp6.code == 0 && eth.type == 0x86dd && ip.proto == 0x3a && (eth.type
> >> == 0x800 || eth.type == 0x86dd) && ip.ttl == 0xff && (eth.type == 0x800 ||
> >> eth.type == 0x86dd)
> >> +    has prereqs (icmp6.type == 0x87 || icmp6.type == 0x88) && eth.type
> >> == 0x86dd && ip.proto == 0x3a && (eth.type == 0x800 || eth.type == 0x86dd)
> >> && icmp6.code == 0 && eth.type == 0x86dd && ip.proto == 0x3a && (eth.type
> >> == 0x800 || eth.type == 0x86dd) && ip.ttl == 0xff && (eth.type == 0x800 ||
> >> eth.type == 0x86dd) && icmp6.type == 0x87 && eth.type == 0x86dd && ip.proto
> >> == 0x3a && (eth.type == 0x800 || eth.type == 0x86dd) && icmp6.code == 0 &&
> >> eth.type == 0x86dd && ip.proto == 0x3a && (eth.type == 0x800 || eth.type ==
> >> 0x86dd) && ip.ttl == 0xff && (eth.type == 0x800 || eth.type == 0x86dd)
> >>
> >>   # put_dhcpv6_opts
> >>   reg1[0] = put_dhcpv6_opts(ia_addr = ae70::4, server_id =
> >> 00:00:00:00:10:02);
> >> --
> >> 2.14.3
> >> _______________________________________________
> >> dev mailing list
> >> dev@openvswitch.org
> >> https://mail.openvswitch.org/mailman/listinfo/ovs-dev
> >>
> >>  
> > _______________________________________________
> > dev mailing list
> > dev@openvswitch.org
> > https://mail.openvswitch.org/mailman/listinfo/ovs-dev
> >
Numan Siddique May 8, 2018, 12:38 p.m. UTC | #4 
On Tue, May 8, 2018 at 5:39 PM, Jakub Sitnicki <jkbs@redhat.com> wrote:

> On Tue, 8 May 2018 11:47:34 +0530
> Numan Siddique <nusiddiq@redhat.com> wrote:
>
> > On Mon, May 7, 2018 at 9:57 PM, Mark Michelson <mmichels@redhat.com>
> wrote:
> >
> > > Hi Jakub,
> > >
> > > I finally got around to taking a look at this. I made up some imaginary
> > > expressions to try to see if I could find a way that this would break,
> but
> > > it looks good to me in each case.
> > >
> > > Acked-by: Mark Michelson <mmichels@redhat.com>
> >
> >
> >
> > Same here. I tested with all the combinations I could think of.
> >
> > Acked-by: Numan Siddique <nusiddiq@redhat.com>
>
> @Mark, @Numan, thanks for taking the time to test it out and review.
>
> @Numan, are you planning on submitting the tests from your
> conjunctive match support patchset? They are really valuable. If you
> would like, I can help with it.
>

It would be great if you can take those tests and merge in your patch, if
you are fine with it :)

Thanks
Numan


>
> Thanks,
> Jakub
>
> >
> >
> > >
> > >
> > > On 04/26/2018 03:54 PM, Jakub Sitnicki wrote:
> > >
> > >> Appending prerequisites to sub-expressions of OR that are all over one
> > >> symbol prevents the expression-to-matches converter from applying
> > >> conjunctive matching. This happens during the annotation phase.
> > >>
> > >> input:      s1 == { c1, c2 } && s2 == { c3, c4 }
> > >> expanded:   (s1 == c1 || s1 == c2) && (s2 == c3 || s2 == c4)
> > >> annotated:  ((p1 && s1 == c1) || (p1 && s1 == c2)) &&
> > >>              ((p2 && s2 == c3) || (p2 && s2 == c4))
> > >> normalized: (p1 && p2 && s1 == c1 && s2 == c3) ||
> > >>              (p1 && p2 && s1 == c1 && s2 == c4) ||
> > >>             (p1 && p2 && s1 == c2 && s2 == c3) ||
> > >>             (p1 && p2 && s1 == c2 && s2 == c4)
> > >>
> > >> Where s1,s2 - symbols, c1..c4 - constants, p1,p2 - prerequisites.
> > >>
> > >> Since sub-expressions of OR trees that are over one symbol all have
> the
> > >> same prerequisites, we can factor them out leaving the OR tree in
> tact,
> > >> and enabling the converter to apply conjunctive matching to
> > >> AND(OR(clause)) trees.
> > >>
> > >> Going back to our example this change gives us:
> > >>
> > >> input:      s1 == { c1, c2 } && s2 == { c3, c4 }
> > >> expanded:   (s1 == c1 || s1 == c2) && (s2 == c3 || s2 == c4)
> > >> annotated:  (s1 == c1 || s1 == c2) && p1 && (s2 == c3 || s2 == c4) &&
> p2
> > >> normalized: p1 && p2 && (s1 == c1 || s1 == c2) && (s2 == c3 || s2 ==
> c4)
> > >>
> > >> We also factor out the prerequisites out of pure AND or mixed AND/OR
> > >> trees to keep the common code path, but in this case we don't gain
> > >> anything.
> > >>
> > >> Signed-off-by: Jakub Sitnicki <jkbs@redhat.com>
> > >> ---
> > >>
> > >> This is an alternative to "Enhance conjunctive match support in OVN"
> > >> patch from
> > >> Numan Siddique [1].
> > >>
> > >> [1] https://patchwork.ozlabs.org/patch/874433/
> > >>
> > >>   ovn/lib/expr.c | 55 ++++++++++++++++++++++++++++++
> > >> +++++++++++++++----------
> > >>   tests/ovn.at   |  4 ++--
> > >>   2 files changed, 47 insertions(+), 12 deletions(-)
> > >>
> > >> diff --git a/ovn/lib/expr.c b/ovn/lib/expr.c
> > >> index 5840ef871..9dd8d6f17 100644
> > >> --- a/ovn/lib/expr.c
> > >> +++ b/ovn/lib/expr.c
> > >> @@ -32,6 +32,13 @@
> > >>
> > >>   VLOG_DEFINE_THIS_MODULE(expr);
> > >>
> > >> +static const struct expr_symbol *
> > >> +expr_get_unique_symbol(const struct expr *expr);
> > >> +
> > >> +struct expr *
> > >> +expr_annotate__(struct expr *expr, const struct shash *symtab,
> > >> +                bool append_prereqs, struct ovs_list *nesting, char
> > >> **errorp);
> > >> +
> > >>   static struct expr *parse_and_annotate(const char *s,
> > >>                                          const struct shash *symtab,
> > >>                                          struct ovs_list *nesting,
> > >> @@ -1658,9 +1665,6 @@ struct annotation_nesting {
> > >>       const struct expr_symbol *symbol;
> > >>   };
> > >>
> > >> -struct expr *expr_annotate__(struct expr *, const struct shash
> *symtab,
> > >> -                             struct ovs_list *nesting, char
> **errorp);
> > >> -
> > >>   static struct expr *
> > >>   parse_and_annotate(const char *s, const struct shash *symtab,
> > >>                      struct ovs_list *nesting, char **errorp)
> > >> @@ -1670,7 +1674,7 @@ parse_and_annotate(const char *s, const struct
> > >> shash *symtab,
> > >>
> > >>       expr = expr_parse_string(s, symtab, NULL, NULL, &error);
> > >>       if (expr) {
> > >> -        expr = expr_annotate__(expr, symtab, nesting, &error);
> > >> +        expr = expr_annotate__(expr, symtab, true, nesting, &error);
> > >>       }
> > >>       if (expr) {
> > >>           *errorp = NULL;
> > >> @@ -1685,7 +1689,7 @@ parse_and_annotate(const char *s, const struct
> > >> shash *symtab,
> > >>
> > >>   static struct expr *
> > >>   expr_annotate_cmp(struct expr *expr, const struct shash *symtab,
> > >> -                  struct ovs_list *nesting, char **errorp)
> > >> +                  bool append_prereqs, struct ovs_list *nesting, char
> > >> **errorp)
> > >>   {
> > >>       const struct expr_symbol *symbol = expr->cmp.symbol;
> > >>       const struct annotation_nesting *iter;
> > >> @@ -1703,7 +1707,7 @@ expr_annotate_cmp(struct expr *expr, const
> struct
> > >> shash *symtab,
> > >>       ovs_list_push_back(nesting, &an.node);
> > >>
> > >>       struct expr *prereqs = NULL;
> > >> -    if (symbol->prereqs) {
> > >> +    if (append_prereqs && symbol->prereqs) {
> > >>           prereqs = parse_and_annotate(symbol->prereqs, symtab,
> nesting,
> > >> errorp);
> > >>           if (!prereqs) {
> > >>               goto error;
> > >> @@ -1744,21 +1748,46 @@ expr_annotate_cmp(struct expr *expr, const
> struct
> > >> shash *symtab,
> > >>       return NULL;
> > >>   }
> > >>
> > >> +/* Append (logical AND) prereqs for given symbol to the expression.
> */
> > >> +static struct expr *
> > >> +expr_append_prereqs(struct expr *expr, const struct expr_symbol
> *symbol,
> > >> +                    const struct shash *symtab, struct ovs_list
> *nesting,
> > >> +                    char **errorp)
> > >> +{
> > >> +    struct expr *prereqs = NULL;
> > >> +
> > >> +    if (symbol->prereqs) {
> > >> +        prereqs = parse_and_annotate(symbol->prereqs, symtab,
> nesting,
> > >> errorp);
> > >> +        if (!prereqs) {
> > >> +            goto error;
> > >> +        }
> > >> +    }
> > >> +
> > >> +    return prereqs ? expr_combine(EXPR_T_AND, expr, prereqs) : expr;
> > >> +
> > >> +error:
> > >> +    expr_destroy(expr);
> > >> +    expr_destroy(prereqs);
> > >> +    return NULL;
> > >> +}
> > >> +
> > >>   struct expr *
> > >>   expr_annotate__(struct expr *expr, const struct shash *symtab,
> > >> -                struct ovs_list *nesting, char **errorp)
> > >> +                bool append_prereqs, struct ovs_list *nesting, char
> > >> **errorp)
> > >>   {
> > >>       switch (expr->type) {
> > >>       case EXPR_T_CMP:
> > >> -        return expr_annotate_cmp(expr, symtab, nesting, errorp);
> > >> +        return expr_annotate_cmp(expr, symtab, append_prereqs,
> nesting,
> > >> +                                 errorp);
> > >>
> > >>       case EXPR_T_AND:
> > >>       case EXPR_T_OR: {
> > >> +        const struct expr_symbol *unique_symbol =
> > >> expr_get_unique_symbol(expr);
> > >>           struct expr *sub, *next;
> > >>
> > >>           LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
> > >>               ovs_list_remove(&sub->node);
> > >> -            struct expr *new_sub = expr_annotate__(sub, symtab,
> > >> +            struct expr *new_sub = expr_annotate__(sub, symtab,
> > >> !unique_symbol,
> > >>                                                      nesting, errorp);
> > >>               if (!new_sub) {
> > >>                   expr_destroy(expr);
> > >> @@ -1767,6 +1796,12 @@ expr_annotate__(struct expr *expr, const struct
> > >> shash *symtab,
> > >>               expr_insert_andor(expr, next, new_sub);
> > >>           }
> > >>           *errorp = NULL;
> > >> +
> > >> +        if (unique_symbol) {
> > >> +            expr = expr_append_prereqs(expr, unique_symbol, symtab,
> > >> nesting,
> > >> +                                       errorp);
> > >> +        }
> > >> +
> > >>           return expr;
> > >>       }
> > >>
> > >> @@ -1802,7 +1837,7 @@ struct expr *
> > >>   expr_annotate(struct expr *expr, const struct shash *symtab, char
> > >> **errorp)
> > >>   {
> > >>       struct ovs_list nesting = OVS_LIST_INITIALIZER(&nesting);
> > >> -    return expr_annotate__(expr, symtab, &nesting, errorp);
> > >> +    return expr_annotate__(expr, symtab, true, &nesting, errorp);
> > >>   }
> > >>
> > >>   static struct expr *
> > >> diff --git a/tests/ovn.at b/tests/ovn.at
> > >> index 8fe4c522a..4abf44b06 100644
> > >> --- a/tests/ovn.at
> > >> +++ b/tests/ovn.at
> > >> @@ -365,7 +365,7 @@ AT_DATA([test-cases.txt], [[
> > >>   ip4.src == 1.2.3.4 => ip4.src == 0x1020304 && eth.type == 0x800
> > >>   ip4.src != 1.2.3.4 => ip4.src != 0x1020304 && eth.type == 0x800
> > >>   ip.proto == 123 => ip.proto == 0x7b && (eth.type == 0x800 ||
> eth.type
> > >> == 0x86dd)
> > >> -ip.proto == {123, 234} => (ip.proto == 0x7b && (eth.type == 0x800 ||
> > >> eth.type == 0x86dd)) || (ip.proto == 0xea && (eth.type == 0x800 ||
> eth.type
> > >> == 0x86dd))
> > >> +ip.proto == {123, 234} => (ip.proto == 0x7b || ip.proto == 0xea) &&
> > >> (eth.type == 0x800 || eth.type == 0x86dd)
> > >>   ip4.src == 1.2.3.4 && ip4.dst == 5.6.7.8 => ip4.src == 0x1020304 &&
> > >> eth.type == 0x800 && ip4.dst == 0x5060708 && eth.type == 0x800
> > >>
> > >>   ip => eth.type == 0x800 || eth.type == 0x86dd
> > >> @@ -1161,7 +1161,7 @@ get_nd(xxreg0, ip6.dst);
> > >>   # put_nd
> > >>   put_nd(inport, nd.target, nd.sll);
> > >>       encodes as push:NXM_NX_XXREG0[],push:NXM_
> > >> OF_ETH_SRC[],push:NXM_NX_ND_SLL[],push:NXM_NX_ND_TARGET[],po
> > >> p:NXM_NX_XXREG0[],pop:NXM_OF_ETH_SRC[],controller(userdata=
> > >> 00.00.00.04.00.00.00.00),pop:NXM_OF_ETH_SRC[],pop:NXM_NX_XXREG0[]
> > >> -    has prereqs ((icmp6.type == 0x87 && eth.type == 0x86dd &&
> ip.proto
> > >> == 0x3a && (eth.type == 0x800 || eth.type == 0x86dd)) || (icmp6.type
> ==
> > >> 0x88 && eth.type == 0x86dd && ip.proto == 0x3a && (eth.type == 0x800
> ||
> > >> eth.type == 0x86dd))) && icmp6.code == 0 && eth.type == 0x86dd &&
> ip.proto
> > >> == 0x3a && (eth.type == 0x800 || eth.type == 0x86dd) && ip.ttl ==
> 0xff &&
> > >> (eth.type == 0x800 || eth.type == 0x86dd) && icmp6.type == 0x87 &&
> eth.type
> > >> == 0x86dd && ip.proto == 0x3a && (eth.type == 0x800 || eth.type ==
> 0x86dd)
> > >> && icmp6.code == 0 && eth.type == 0x86dd && ip.proto == 0x3a &&
> (eth.type
> > >> == 0x800 || eth.type == 0x86dd) && ip.ttl == 0xff && (eth.type ==
> 0x800 ||
> > >> eth.type == 0x86dd)
> > >> +    has prereqs (icmp6.type == 0x87 || icmp6.type == 0x88) &&
> eth.type
> > >> == 0x86dd && ip.proto == 0x3a && (eth.type == 0x800 || eth.type ==
> 0x86dd)
> > >> && icmp6.code == 0 && eth.type == 0x86dd && ip.proto == 0x3a &&
> (eth.type
> > >> == 0x800 || eth.type == 0x86dd) && ip.ttl == 0xff && (eth.type ==
> 0x800 ||
> > >> eth.type == 0x86dd) && icmp6.type == 0x87 && eth.type == 0x86dd &&
> ip.proto
> > >> == 0x3a && (eth.type == 0x800 || eth.type == 0x86dd) && icmp6.code ==
> 0 &&
> > >> eth.type == 0x86dd && ip.proto == 0x3a && (eth.type == 0x800 ||
> eth.type ==
> > >> 0x86dd) && ip.ttl == 0xff && (eth.type == 0x800 || eth.type == 0x86dd)
> > >>
> > >>   # put_dhcpv6_opts
> > >>   reg1[0] = put_dhcpv6_opts(ia_addr = ae70::4, server_id =
> > >> 00:00:00:00:10:02);
> > >> --
> > >> 2.14.3
> > >> _______________________________________________
> > >> dev mailing list
> > >> dev@openvswitch.org
> > >> https://mail.openvswitch.org/mailman/listinfo/ovs-dev
> > >>
> > >>
> > > _______________________________________________
> > > dev mailing list
> > > dev@openvswitch.org
> > > https://mail.openvswitch.org/mailman/listinfo/ovs-dev
> > >
>
>
Jakub Sitnicki May 8, 2018, 3:52 p.m. UTC | #5 
On Tue, 8 May 2018 18:08:54 +0530
Numan Siddique <nusiddiq@redhat.com> wrote:

> On Tue, May 8, 2018 at 5:39 PM, Jakub Sitnicki <jkbs@redhat.com> wrote:
> 
> > On Tue, 8 May 2018 11:47:34 +0530
> > Numan Siddique <nusiddiq@redhat.com> wrote:
> >  
> > > On Mon, May 7, 2018 at 9:57 PM, Mark Michelson <mmichels@redhat.com>  
> > wrote:  
> > >  
> > > > Hi Jakub,
> > > >
> > > > I finally got around to taking a look at this. I made up some imaginary
> > > > expressions to try to see if I could find a way that this would break,  
> > but  
> > > > it looks good to me in each case.
> > > >
> > > > Acked-by: Mark Michelson <mmichels@redhat.com>  
> > >
> > >
> > >
> > > Same here. I tested with all the combinations I could think of.
> > >
> > > Acked-by: Numan Siddique <nusiddiq@redhat.com>  
> >
> > @Mark, @Numan, thanks for taking the time to test it out and review.
> >
> > @Numan, are you planning on submitting the tests from your
> > conjunctive match support patchset? They are really valuable. If you
> > would like, I can help with it.
> >  
> 
> It would be great if you can take those tests and merge in your patch, if
> you are fine with it :)

Sure thing. I will pull it into the patchset and submit with v2.

-Jakub

> 
> Thanks
> Numan
> 
> 
> >
> > Thanks,
> > Jakub
> >  
> > >
> > >  
> > > >
> > > >
> > > > On 04/26/2018 03:54 PM, Jakub Sitnicki wrote:
> > > >  
> > > >> Appending prerequisites to sub-expressions of OR that are all over one
> > > >> symbol prevents the expression-to-matches converter from applying
> > > >> conjunctive matching. This happens during the annotation phase.
> > > >>
> > > >> input:      s1 == { c1, c2 } && s2 == { c3, c4 }
> > > >> expanded:   (s1 == c1 || s1 == c2) && (s2 == c3 || s2 == c4)
> > > >> annotated:  ((p1 && s1 == c1) || (p1 && s1 == c2)) &&
> > > >>              ((p2 && s2 == c3) || (p2 && s2 == c4))
> > > >> normalized: (p1 && p2 && s1 == c1 && s2 == c3) ||
> > > >>              (p1 && p2 && s1 == c1 && s2 == c4) ||
> > > >>             (p1 && p2 && s1 == c2 && s2 == c3) ||
> > > >>             (p1 && p2 && s1 == c2 && s2 == c4)
> > > >>
> > > >> Where s1,s2 - symbols, c1..c4 - constants, p1,p2 - prerequisites.
> > > >>
> > > >> Since sub-expressions of OR trees that are over one symbol all have  
> > the  
> > > >> same prerequisites, we can factor them out leaving the OR tree in  
> > tact,  
> > > >> and enabling the converter to apply conjunctive matching to
> > > >> AND(OR(clause)) trees.
> > > >>
> > > >> Going back to our example this change gives us:
> > > >>
> > > >> input:      s1 == { c1, c2 } && s2 == { c3, c4 }
> > > >> expanded:   (s1 == c1 || s1 == c2) && (s2 == c3 || s2 == c4)
> > > >> annotated:  (s1 == c1 || s1 == c2) && p1 && (s2 == c3 || s2 == c4) &&  
> > p2  
> > > >> normalized: p1 && p2 && (s1 == c1 || s1 == c2) && (s2 == c3 || s2 ==  
> > c4)  
> > > >>
> > > >> We also factor out the prerequisites out of pure AND or mixed AND/OR
> > > >> trees to keep the common code path, but in this case we don't gain
> > > >> anything.
> > > >>
> > > >> Signed-off-by: Jakub Sitnicki <jkbs@redhat.com>
> > > >> ---
> > > >>
> > > >> This is an alternative to "Enhance conjunctive match support in OVN"
> > > >> patch from
> > > >> Numan Siddique [1].
> > > >>
> > > >> [1] https://patchwork.ozlabs.org/patch/874433/
> > > >>
> > > >>   ovn/lib/expr.c | 55 ++++++++++++++++++++++++++++++
> > > >> +++++++++++++++----------
> > > >>   tests/ovn.at   |  4 ++--
> > > >>   2 files changed, 47 insertions(+), 12 deletions(-)
> > > >>
> > > >> diff --git a/ovn/lib/expr.c b/ovn/lib/expr.c
> > > >> index 5840ef871..9dd8d6f17 100644
> > > >> --- a/ovn/lib/expr.c
> > > >> +++ b/ovn/lib/expr.c
> > > >> @@ -32,6 +32,13 @@
> > > >>
> > > >>   VLOG_DEFINE_THIS_MODULE(expr);
> > > >>
> > > >> +static const struct expr_symbol *
> > > >> +expr_get_unique_symbol(const struct expr *expr);
> > > >> +
> > > >> +struct expr *
> > > >> +expr_annotate__(struct expr *expr, const struct shash *symtab,
> > > >> +                bool append_prereqs, struct ovs_list *nesting, char
> > > >> **errorp);
> > > >> +
> > > >>   static struct expr *parse_and_annotate(const char *s,
> > > >>                                          const struct shash *symtab,
> > > >>                                          struct ovs_list *nesting,
> > > >> @@ -1658,9 +1665,6 @@ struct annotation_nesting {
> > > >>       const struct expr_symbol *symbol;
> > > >>   };
> > > >>
> > > >> -struct expr *expr_annotate__(struct expr *, const struct shash  
> > *symtab,  
> > > >> -                             struct ovs_list *nesting, char  
> > **errorp);  
> > > >> -
> > > >>   static struct expr *
> > > >>   parse_and_annotate(const char *s, const struct shash *symtab,
> > > >>                      struct ovs_list *nesting, char **errorp)
> > > >> @@ -1670,7 +1674,7 @@ parse_and_annotate(const char *s, const struct
> > > >> shash *symtab,
> > > >>
> > > >>       expr = expr_parse_string(s, symtab, NULL, NULL, &error);
> > > >>       if (expr) {
> > > >> -        expr = expr_annotate__(expr, symtab, nesting, &error);
> > > >> +        expr = expr_annotate__(expr, symtab, true, nesting, &error);
> > > >>       }
> > > >>       if (expr) {
> > > >>           *errorp = NULL;
> > > >> @@ -1685,7 +1689,7 @@ parse_and_annotate(const char *s, const struct
> > > >> shash *symtab,
> > > >>
> > > >>   static struct expr *
> > > >>   expr_annotate_cmp(struct expr *expr, const struct shash *symtab,
> > > >> -                  struct ovs_list *nesting, char **errorp)
> > > >> +                  bool append_prereqs, struct ovs_list *nesting, char
> > > >> **errorp)
> > > >>   {
> > > >>       const struct expr_symbol *symbol = expr->cmp.symbol;
> > > >>       const struct annotation_nesting *iter;
> > > >> @@ -1703,7 +1707,7 @@ expr_annotate_cmp(struct expr *expr, const  
> > struct  
> > > >> shash *symtab,
> > > >>       ovs_list_push_back(nesting, &an.node);
> > > >>
> > > >>       struct expr *prereqs = NULL;
> > > >> -    if (symbol->prereqs) {
> > > >> +    if (append_prereqs && symbol->prereqs) {
> > > >>           prereqs = parse_and_annotate(symbol->prereqs, symtab,  
> > nesting,  
> > > >> errorp);
> > > >>           if (!prereqs) {
> > > >>               goto error;
> > > >> @@ -1744,21 +1748,46 @@ expr_annotate_cmp(struct expr *expr, const  
> > struct  
> > > >> shash *symtab,
> > > >>       return NULL;
> > > >>   }
> > > >>
> > > >> +/* Append (logical AND) prereqs for given symbol to the expression.  
> > */  
> > > >> +static struct expr *
> > > >> +expr_append_prereqs(struct expr *expr, const struct expr_symbol  
> > *symbol,  
> > > >> +                    const struct shash *symtab, struct ovs_list  
> > *nesting,  
> > > >> +                    char **errorp)
> > > >> +{
> > > >> +    struct expr *prereqs = NULL;
> > > >> +
> > > >> +    if (symbol->prereqs) {
> > > >> +        prereqs = parse_and_annotate(symbol->prereqs, symtab,  
> > nesting,  
> > > >> errorp);
> > > >> +        if (!prereqs) {
> > > >> +            goto error;
> > > >> +        }
> > > >> +    }
> > > >> +
> > > >> +    return prereqs ? expr_combine(EXPR_T_AND, expr, prereqs) : expr;
> > > >> +
> > > >> +error:
> > > >> +    expr_destroy(expr);
> > > >> +    expr_destroy(prereqs);
> > > >> +    return NULL;
> > > >> +}
> > > >> +
> > > >>   struct expr *
> > > >>   expr_annotate__(struct expr *expr, const struct shash *symtab,
> > > >> -                struct ovs_list *nesting, char **errorp)
> > > >> +                bool append_prereqs, struct ovs_list *nesting, char
> > > >> **errorp)
> > > >>   {
> > > >>       switch (expr->type) {
> > > >>       case EXPR_T_CMP:
> > > >> -        return expr_annotate_cmp(expr, symtab, nesting, errorp);
> > > >> +        return expr_annotate_cmp(expr, symtab, append_prereqs,  
> > nesting,  
> > > >> +                                 errorp);
> > > >>
> > > >>       case EXPR_T_AND:
> > > >>       case EXPR_T_OR: {
> > > >> +        const struct expr_symbol *unique_symbol =
> > > >> expr_get_unique_symbol(expr);
> > > >>           struct expr *sub, *next;
> > > >>
> > > >>           LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
> > > >>               ovs_list_remove(&sub->node);
> > > >> -            struct expr *new_sub = expr_annotate__(sub, symtab,
> > > >> +            struct expr *new_sub = expr_annotate__(sub, symtab,
> > > >> !unique_symbol,
> > > >>                                                      nesting, errorp);
> > > >>               if (!new_sub) {
> > > >>                   expr_destroy(expr);
> > > >> @@ -1767,6 +1796,12 @@ expr_annotate__(struct expr *expr, const struct
> > > >> shash *symtab,
> > > >>               expr_insert_andor(expr, next, new_sub);
> > > >>           }
> > > >>           *errorp = NULL;
> > > >> +
> > > >> +        if (unique_symbol) {
> > > >> +            expr = expr_append_prereqs(expr, unique_symbol, symtab,
> > > >> nesting,
> > > >> +                                       errorp);
> > > >> +        }
> > > >> +
> > > >>           return expr;
> > > >>       }
> > > >>
> > > >> @@ -1802,7 +1837,7 @@ struct expr *
> > > >>   expr_annotate(struct expr *expr, const struct shash *symtab, char
> > > >> **errorp)
> > > >>   {
> > > >>       struct ovs_list nesting = OVS_LIST_INITIALIZER(&nesting);
> > > >> -    return expr_annotate__(expr, symtab, &nesting, errorp);
> > > >> +    return expr_annotate__(expr, symtab, true, &nesting, errorp);
> > > >>   }
> > > >>
> > > >>   static struct expr *
> > > >> diff --git a/tests/ovn.at b/tests/ovn.at
> > > >> index 8fe4c522a..4abf44b06 100644
> > > >> --- a/tests/ovn.at
> > > >> +++ b/tests/ovn.at
> > > >> @@ -365,7 +365,7 @@ AT_DATA([test-cases.txt], [[
> > > >>   ip4.src == 1.2.3.4 => ip4.src == 0x1020304 && eth.type == 0x800
> > > >>   ip4.src != 1.2.3.4 => ip4.src != 0x1020304 && eth.type == 0x800
> > > >>   ip.proto == 123 => ip.proto == 0x7b && (eth.type == 0x800 ||  
> > eth.type  
> > > >> == 0x86dd)
> > > >> -ip.proto == {123, 234} => (ip.proto == 0x7b && (eth.type == 0x800 ||
> > > >> eth.type == 0x86dd)) || (ip.proto == 0xea && (eth.type == 0x800 ||  
> > eth.type  
> > > >> == 0x86dd))
> > > >> +ip.proto == {123, 234} => (ip.proto == 0x7b || ip.proto == 0xea) &&
> > > >> (eth.type == 0x800 || eth.type == 0x86dd)
> > > >>   ip4.src == 1.2.3.4 && ip4.dst == 5.6.7.8 => ip4.src == 0x1020304 &&
> > > >> eth.type == 0x800 && ip4.dst == 0x5060708 && eth.type == 0x800
> > > >>
> > > >>   ip => eth.type == 0x800 || eth.type == 0x86dd
> > > >> @@ -1161,7 +1161,7 @@ get_nd(xxreg0, ip6.dst);
> > > >>   # put_nd
> > > >>   put_nd(inport, nd.target, nd.sll);
> > > >>       encodes as push:NXM_NX_XXREG0[],push:NXM_
> > > >> OF_ETH_SRC[],push:NXM_NX_ND_SLL[],push:NXM_NX_ND_TARGET[],po
> > > >> p:NXM_NX_XXREG0[],pop:NXM_OF_ETH_SRC[],controller(userdata=
> > > >> 00.00.00.04.00.00.00.00),pop:NXM_OF_ETH_SRC[],pop:NXM_NX_XXREG0[]
> > > >> -    has prereqs ((icmp6.type == 0x87 && eth.type == 0x86dd &&  
> > ip.proto  
> > > >> == 0x3a && (eth.type == 0x800 || eth.type == 0x86dd)) || (icmp6.type  
> > ==  
> > > >> 0x88 && eth.type == 0x86dd && ip.proto == 0x3a && (eth.type == 0x800  
> > ||  
> > > >> eth.type == 0x86dd))) && icmp6.code == 0 && eth.type == 0x86dd &&  
> > ip.proto  
> > > >> == 0x3a && (eth.type == 0x800 || eth.type == 0x86dd) && ip.ttl ==  
> > 0xff &&  
> > > >> (eth.type == 0x800 || eth.type == 0x86dd) && icmp6.type == 0x87 &&  
> > eth.type  
> > > >> == 0x86dd && ip.proto == 0x3a && (eth.type == 0x800 || eth.type ==  
> > 0x86dd)  
> > > >> && icmp6.code == 0 && eth.type == 0x86dd && ip.proto == 0x3a &&  
> > (eth.type  
> > > >> == 0x800 || eth.type == 0x86dd) && ip.ttl == 0xff && (eth.type ==  
> > 0x800 ||  
> > > >> eth.type == 0x86dd)
> > > >> +    has prereqs (icmp6.type == 0x87 || icmp6.type == 0x88) &&  
> > eth.type  
> > > >> == 0x86dd && ip.proto == 0x3a && (eth.type == 0x800 || eth.type ==  
> > 0x86dd)  
> > > >> && icmp6.code == 0 && eth.type == 0x86dd && ip.proto == 0x3a &&  
> > (eth.type  
> > > >> == 0x800 || eth.type == 0x86dd) && ip.ttl == 0xff && (eth.type ==  
> > 0x800 ||  
> > > >> eth.type == 0x86dd) && icmp6.type == 0x87 && eth.type == 0x86dd &&  
> > ip.proto  
> > > >> == 0x3a && (eth.type == 0x800 || eth.type == 0x86dd) && icmp6.code ==  
> > 0 &&  
> > > >> eth.type == 0x86dd && ip.proto == 0x3a && (eth.type == 0x800 ||  
> > eth.type ==  
> > > >> 0x86dd) && ip.ttl == 0xff && (eth.type == 0x800 || eth.type == 0x86dd)
> > > >>
> > > >>   # put_dhcpv6_opts
> > > >>   reg1[0] = put_dhcpv6_opts(ia_addr = ae70::4, server_id =
> > > >> 00:00:00:00:10:02);
> > > >> --
> > > >> 2.14.3
> > > >> _______________________________________________
> > > >> dev mailing list
> > > >> dev@openvswitch.org
> > > >> https://mail.openvswitch.org/mailman/listinfo/ovs-dev
> > > >>
> > > >>  
> > > > _______________________________________________
> > > > dev mailing list
> > > > dev@openvswitch.org
> > > > https://mail.openvswitch.org/mailman/listinfo/ovs-dev
> > > >  
> >
> >
Ben Pfaff May 9, 2018, 8:02 p.m. UTC | #6 
On Thu, Apr 26, 2018 at 09:54:06PM +0200, Jakub Sitnicki wrote:
> Appending prerequisites to sub-expressions of OR that are all over one
> symbol prevents the expression-to-matches converter from applying
> conjunctive matching. This happens during the annotation phase.
> 
> input:      s1 == { c1, c2 } && s2 == { c3, c4 }
> expanded:   (s1 == c1 || s1 == c2) && (s2 == c3 || s2 == c4)
> annotated:  ((p1 && s1 == c1) || (p1 && s1 == c2)) &&
>             ((p2 && s2 == c3) || (p2 && s2 == c4))
> normalized: (p1 && p2 && s1 == c1 && s2 == c3) ||
>             (p1 && p2 && s1 == c1 && s2 == c4) ||
> 	    (p1 && p2 && s1 == c2 && s2 == c3) ||
> 	    (p1 && p2 && s1 == c2 && s2 == c4)
> 
> Where s1,s2 - symbols, c1..c4 - constants, p1,p2 - prerequisites.
> 
> Since sub-expressions of OR trees that are over one symbol all have the
> same prerequisites, we can factor them out leaving the OR tree in tact,
> and enabling the converter to apply conjunctive matching to
> AND(OR(clause)) trees.
> 
> Going back to our example this change gives us:
> 
> input:      s1 == { c1, c2 } && s2 == { c3, c4 }
> expanded:   (s1 == c1 || s1 == c2) && (s2 == c3 || s2 == c4)
> annotated:  (s1 == c1 || s1 == c2) && p1 && (s2 == c3 || s2 == c4) && p2
> normalized: p1 && p2 && (s1 == c1 || s1 == c2) && (s2 == c3 || s2 == c4)
> 
> We also factor out the prerequisites out of pure AND or mixed AND/OR
> trees to keep the common code path, but in this case we don't gain
> anything.
> 
> Signed-off-by: Jakub Sitnicki <jkbs@redhat.com>

This is nice.  Thank you.

I suggest folding in the following to better document and to better
match usual OVS style:

diff --git a/ovn/lib/expr.c b/ovn/lib/expr.c
index 9dd8d6f17abe..bac8e1efd53f 100644
--- a/ovn/lib/expr.c
+++ b/ovn/lib/expr.c
@@ -32,13 +32,10 @@
 
 VLOG_DEFINE_THIS_MODULE(expr);
 
-static const struct expr_symbol *
-expr_get_unique_symbol(const struct expr *expr);
-
-struct expr *
-expr_annotate__(struct expr *expr, const struct shash *symtab,
-                bool append_prereqs, struct ovs_list *nesting, char **errorp);
-
+static const struct expr_symbol *expr_get_unique_symbol(const struct expr *);
+struct expr *expr_annotate__(struct expr *, const struct shash *symtab,
+                             bool append_prereqs, struct ovs_list *nesting,
+                             char **errorp);
 static struct expr *parse_and_annotate(const char *s,
                                        const struct shash *symtab,
                                        struct ovs_list *nesting,
@@ -1771,6 +1768,15 @@ error:
     return NULL;
 }
 
+/* Same interface and purpose as expr_annotate(), with a couple of additional
+ * parameters for internal bookkeeping.
+ *
+ * Uses 'nesting' to ensure that a given symbol is not recursively expanded.
+ *
+ * Ordinarily, annotation adds prerequisites to the expression, and that's what
+ * this function does if 'append_prereqs' is true.  If 'append_prereqs' is
+ * false, this function ignores prerequisites (in which case the caller must
+ * have arranged to deal with them). */
 struct expr *
 expr_annotate__(struct expr *expr, const struct shash *symtab,
                 bool append_prereqs, struct ovs_list *nesting, char **errorp)

I also wonder about the following, because it seems like currently the
append_prereqs parameter is only being honored for a single level of
AND/OR, not when expr_annotate__() recurses:

diff --git a/ovn/lib/expr.c b/ovn/lib/expr.c
index 9dd8d6f17abe..a33b4eb46933 100644
--- a/ovn/lib/expr.c
+++ b/ovn/lib/expr.c
@@ -1782,12 +1788,25 @@ expr_annotate__(struct expr *expr, const struct shash *symtab,
 
     case EXPR_T_AND:
     case EXPR_T_OR: {
-        const struct expr_symbol *unique_symbol = expr_get_unique_symbol(expr);
+        /* Detect whether every term in 'expr' mentions the same symbol.  If
+         * so, then suppress prerequisites for that symbol for those terms and
+         * instead apply them once at our higher level.
+         *
+         * If 'append_prereqs' is true, though, we're not supposed to handle
+         * prereqs at all (because our caller is already doing it). */
+        const struct expr_symbol *unique_symbol = NULL;
+        if (!append_prereqs) {
+            unique_symbol = expr_get_unique_symbol(expr);
+            if (unique_symbol) {
+                append_prereqs = false;
+            }
+        }
+
         struct expr *sub, *next;
 
         LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
             ovs_list_remove(&sub->node);
-            struct expr *new_sub = expr_annotate__(sub, symtab, !unique_symbol,
+            struct expr *new_sub = expr_annotate__(sub, symtab, append_prereqs,
                                                    nesting, errorp);
             if (!new_sub) {
                 expr_destroy(expr);

However this patch, while it seems reasonable, causes some test failures
due to the difference that it produces and I'm not sure whether the new
results are actually superior to the old ones.
Jakub Sitnicki May 10, 2018, 12:41 p.m. UTC | #7 
On Wed, 9 May 2018 13:02:55 -0700
Ben Pfaff <blp@ovn.org> wrote:

> On Thu, Apr 26, 2018 at 09:54:06PM +0200, Jakub Sitnicki wrote:
> > Appending prerequisites to sub-expressions of OR that are all over one
> > symbol prevents the expression-to-matches converter from applying
> > conjunctive matching. This happens during the annotation phase.
> > 
> > input:      s1 == { c1, c2 } && s2 == { c3, c4 }
> > expanded:   (s1 == c1 || s1 == c2) && (s2 == c3 || s2 == c4)
> > annotated:  ((p1 && s1 == c1) || (p1 && s1 == c2)) &&
> >             ((p2 && s2 == c3) || (p2 && s2 == c4))
> > normalized: (p1 && p2 && s1 == c1 && s2 == c3) ||
> >             (p1 && p2 && s1 == c1 && s2 == c4) ||
> > 	    (p1 && p2 && s1 == c2 && s2 == c3) ||
> > 	    (p1 && p2 && s1 == c2 && s2 == c4)
> > 
> > Where s1,s2 - symbols, c1..c4 - constants, p1,p2 - prerequisites.
> > 
> > Since sub-expressions of OR trees that are over one symbol all have the
> > same prerequisites, we can factor them out leaving the OR tree in tact,
> > and enabling the converter to apply conjunctive matching to
> > AND(OR(clause)) trees.
> > 
> > Going back to our example this change gives us:
> > 
> > input:      s1 == { c1, c2 } && s2 == { c3, c4 }
> > expanded:   (s1 == c1 || s1 == c2) && (s2 == c3 || s2 == c4)
> > annotated:  (s1 == c1 || s1 == c2) && p1 && (s2 == c3 || s2 == c4) && p2
> > normalized: p1 && p2 && (s1 == c1 || s1 == c2) && (s2 == c3 || s2 == c4)
> > 
> > We also factor out the prerequisites out of pure AND or mixed AND/OR
> > trees to keep the common code path, but in this case we don't gain
> > anything.
> > 
> > Signed-off-by: Jakub Sitnicki <jkbs@redhat.com>  
> 
> This is nice.  Thank you.
> 
> I suggest folding in the following to better document and to better
> match usual OVS style:
> 
> diff --git a/ovn/lib/expr.c b/ovn/lib/expr.c
> index 9dd8d6f17abe..bac8e1efd53f 100644
> --- a/ovn/lib/expr.c
> +++ b/ovn/lib/expr.c
> @@ -32,13 +32,10 @@
>  
>  VLOG_DEFINE_THIS_MODULE(expr);
>  
> -static const struct expr_symbol *
> -expr_get_unique_symbol(const struct expr *expr);
> -
> -struct expr *
> -expr_annotate__(struct expr *expr, const struct shash *symtab,
> -                bool append_prereqs, struct ovs_list *nesting, char **errorp);
> -
> +static const struct expr_symbol *expr_get_unique_symbol(const struct expr *);
> +struct expr *expr_annotate__(struct expr *, const struct shash *symtab,
> +                             bool append_prereqs, struct ovs_list *nesting,
> +                             char **errorp);
>  static struct expr *parse_and_annotate(const char *s,
>                                         const struct shash *symtab,
>                                         struct ovs_list *nesting,
> @@ -1771,6 +1768,15 @@ error:
>      return NULL;
>  }
>  
> +/* Same interface and purpose as expr_annotate(), with a couple of additional
> + * parameters for internal bookkeeping.
> + *
> + * Uses 'nesting' to ensure that a given symbol is not recursively expanded.
> + *
> + * Ordinarily, annotation adds prerequisites to the expression, and that's what
> + * this function does if 'append_prereqs' is true.  If 'append_prereqs' is
> + * false, this function ignores prerequisites (in which case the caller must
> + * have arranged to deal with them). */
>  struct expr *
>  expr_annotate__(struct expr *expr, const struct shash *symtab,
>                  bool append_prereqs, struct ovs_list *nesting, char **errorp)
> 
> I also wonder about the following, because it seems like currently the
> append_prereqs parameter is only being honored for a single level of
> AND/OR, not when expr_annotate__() recurses:
> 
> diff --git a/ovn/lib/expr.c b/ovn/lib/expr.c
> index 9dd8d6f17abe..a33b4eb46933 100644
> --- a/ovn/lib/expr.c
> +++ b/ovn/lib/expr.c
> @@ -1782,12 +1788,25 @@ expr_annotate__(struct expr *expr, const struct shash *symtab,
>  
>      case EXPR_T_AND:
>      case EXPR_T_OR: {
> -        const struct expr_symbol *unique_symbol = expr_get_unique_symbol(expr);
> +        /* Detect whether every term in 'expr' mentions the same symbol.  If
> +         * so, then suppress prerequisites for that symbol for those terms and
> +         * instead apply them once at our higher level.
> +         *
> +         * If 'append_prereqs' is true, though, we're not supposed to handle
> +         * prereqs at all (because our caller is already doing it). */
> +        const struct expr_symbol *unique_symbol = NULL;
> +        if (!append_prereqs) {
> +            unique_symbol = expr_get_unique_symbol(expr);
> +            if (unique_symbol) {
> +                append_prereqs = false;
> +            }
> +        }
> +
>          struct expr *sub, *next;
>  
>          LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
>              ovs_list_remove(&sub->node);
> -            struct expr *new_sub = expr_annotate__(sub, symtab, !unique_symbol,
> +            struct expr *new_sub = expr_annotate__(sub, symtab, append_prereqs,
>                                                     nesting, errorp);
>              if (!new_sub) {
>                  expr_destroy(expr);
> 
> However this patch, while it seems reasonable, causes some test failures
> due to the difference that it produces and I'm not sure whether the new
> results are actually superior to the old ones.

Thank you for the review and the style fixes. I'll have to mull over the
recursive case, this is something I have not considered, before I roll
out a v2.

-Jakub
diff mbox series

Patch

diff --git a/ovn/lib/expr.c b/ovn/lib/expr.c
index 5840ef871..9dd8d6f17 100644
--- a/ovn/lib/expr.c
+++ b/ovn/lib/expr.c
@@ -32,6 +32,13 @@ 

 VLOG_DEFINE_THIS_MODULE(expr);

+static const struct expr_symbol *
+expr_get_unique_symbol(const struct expr *expr);
+
+struct expr *
+expr_annotate__(struct expr *expr, const struct shash *symtab,
+                bool append_prereqs, struct ovs_list *nesting, char **errorp);
+
 static struct expr *parse_and_annotate(const char *s,
                                        const struct shash *symtab,
                                        struct ovs_list *nesting,
@@ -1658,9 +1665,6 @@  struct annotation_nesting {
     const struct expr_symbol *symbol;
 };

-struct expr *expr_annotate__(struct expr *, const struct shash *symtab,
-                             struct ovs_list *nesting, char **errorp);
-
 static struct expr *
 parse_and_annotate(const char *s, const struct shash *symtab,
                    struct ovs_list *nesting, char **errorp)
@@ -1670,7 +1674,7 @@  parse_and_annotate(const char *s, const struct shash *symtab,

     expr = expr_parse_string(s, symtab, NULL, NULL, &error);
     if (expr) {
-        expr = expr_annotate__(expr, symtab, nesting, &error);
+        expr = expr_annotate__(expr, symtab, true, nesting, &error);
     }
     if (expr) {
         *errorp = NULL;
@@ -1685,7 +1689,7 @@  parse_and_annotate(const char *s, const struct shash *symtab,

 static struct expr *
 expr_annotate_cmp(struct expr *expr, const struct shash *symtab,
-                  struct ovs_list *nesting, char **errorp)
+                  bool append_prereqs, struct ovs_list *nesting, char **errorp)
 {
     const struct expr_symbol *symbol = expr->cmp.symbol;
     const struct annotation_nesting *iter;
@@ -1703,7 +1707,7 @@  expr_annotate_cmp(struct expr *expr, const struct shash *symtab,
     ovs_list_push_back(nesting, &an.node);

     struct expr *prereqs = NULL;
-    if (symbol->prereqs) {
+    if (append_prereqs && symbol->prereqs) {
         prereqs = parse_and_annotate(symbol->prereqs, symtab, nesting, errorp);
         if (!prereqs) {
             goto error;
@@ -1744,21 +1748,46 @@  expr_annotate_cmp(struct expr *expr, const struct shash *symtab,
     return NULL;
 }

+/* Append (logical AND) prereqs for given symbol to the expression. */
+static struct expr *
+expr_append_prereqs(struct expr *expr, const struct expr_symbol *symbol,
+                    const struct shash *symtab, struct ovs_list *nesting,
+                    char **errorp)
+{
+    struct expr *prereqs = NULL;
+
+    if (symbol->prereqs) {
+        prereqs = parse_and_annotate(symbol->prereqs, symtab, nesting, errorp);
+        if (!prereqs) {
+            goto error;
+        }
+    }
+
+    return prereqs ? expr_combine(EXPR_T_AND, expr, prereqs) : expr;
+
+error:
+    expr_destroy(expr);
+    expr_destroy(prereqs);
+    return NULL;
+}
+
 struct expr *
 expr_annotate__(struct expr *expr, const struct shash *symtab,
-                struct ovs_list *nesting, char **errorp)
+                bool append_prereqs, struct ovs_list *nesting, char **errorp)
 {
     switch (expr->type) {
     case EXPR_T_CMP:
-        return expr_annotate_cmp(expr, symtab, nesting, errorp);
+        return expr_annotate_cmp(expr, symtab, append_prereqs, nesting,
+                                 errorp);

     case EXPR_T_AND:
     case EXPR_T_OR: {
+        const struct expr_symbol *unique_symbol = expr_get_unique_symbol(expr);
         struct expr *sub, *next;

         LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
             ovs_list_remove(&sub->node);
-            struct expr *new_sub = expr_annotate__(sub, symtab,
+            struct expr *new_sub = expr_annotate__(sub, symtab, !unique_symbol,
                                                    nesting, errorp);
             if (!new_sub) {
                 expr_destroy(expr);
@@ -1767,6 +1796,12 @@  expr_annotate__(struct expr *expr, const struct shash *symtab,
             expr_insert_andor(expr, next, new_sub);
         }
         *errorp = NULL;
+
+        if (unique_symbol) {
+            expr = expr_append_prereqs(expr, unique_symbol, symtab, nesting,
+                                       errorp);
+        }
+
         return expr;
     }

@@ -1802,7 +1837,7 @@  struct expr *
 expr_annotate(struct expr *expr, const struct shash *symtab, char **errorp)
 {
     struct ovs_list nesting = OVS_LIST_INITIALIZER(&nesting);
-    return expr_annotate__(expr, symtab, &nesting, errorp);
+    return expr_annotate__(expr, symtab, true, &nesting, errorp);
 }
 
 static struct expr *
diff --git a/tests/ovn.at b/tests/ovn.at
index 8fe4c522a..4abf44b06 100644
--- a/tests/ovn.at
+++ b/tests/ovn.at
@@ -365,7 +365,7 @@  AT_DATA([test-cases.txt], [[
 ip4.src == 1.2.3.4 => ip4.src == 0x1020304 && eth.type == 0x800
 ip4.src != 1.2.3.4 => ip4.src != 0x1020304 && eth.type == 0x800
 ip.proto == 123 => ip.proto == 0x7b && (eth.type == 0x800 || eth.type == 0x86dd)
-ip.proto == {123, 234} => (ip.proto == 0x7b && (eth.type == 0x800 || eth.type == 0x86dd)) || (ip.proto == 0xea && (eth.type == 0x800 || eth.type == 0x86dd))
+ip.proto == {123, 234} => (ip.proto == 0x7b || ip.proto == 0xea) && (eth.type == 0x800 || eth.type == 0x86dd)
 ip4.src == 1.2.3.4 && ip4.dst == 5.6.7.8 => ip4.src == 0x1020304 && eth.type == 0x800 && ip4.dst == 0x5060708 && eth.type == 0x800

 ip => eth.type == 0x800 || eth.type == 0x86dd
@@ -1161,7 +1161,7 @@  get_nd(xxreg0, ip6.dst);
 # put_nd
 put_nd(inport, nd.target, nd.sll);
     encodes as push:NXM_NX_XXREG0[],push:NXM_OF_ETH_SRC[],push:NXM_NX_ND_SLL[],push:NXM_NX_ND_TARGET[],pop:NXM_NX_XXREG0[],pop:NXM_OF_ETH_SRC[],controller(userdata=00.00.00.04.00.00.00.00),pop:NXM_OF_ETH_SRC[],pop:NXM_NX_XXREG0[]
-    has prereqs ((icmp6.type == 0x87 && eth.type == 0x86dd && ip.proto == 0x3a && (eth.type == 0x800 || eth.type == 0x86dd)) || (icmp6.type == 0x88 && eth.type == 0x86dd && ip.proto == 0x3a && (eth.type == 0x800 || eth.type == 0x86dd))) && icmp6.code == 0 && eth.type == 0x86dd && ip.proto == 0x3a && (eth.type == 0x800 || eth.type == 0x86dd) && ip.ttl == 0xff && (eth.type == 0x800 || eth.type == 0x86dd) && icmp6.type == 0x87 && eth.type == 0x86dd && ip.proto == 0x3a && (eth.type == 0x800 || eth.type == 0x86dd) && icmp6.code == 0 && eth.type == 0x86dd && ip.proto == 0x3a && (eth.type == 0x800 || eth.type == 0x86dd) && ip.ttl == 0xff && (eth.type == 0x800 || eth.type == 0x86dd)
+    has prereqs (icmp6.type == 0x87 || icmp6.type == 0x88) && eth.type == 0x86dd && ip.proto == 0x3a && (eth.type == 0x800 || eth.type == 0x86dd) && icmp6.code == 0 && eth.type == 0x86dd && ip.proto == 0x3a && (eth.type == 0x800 || eth.type == 0x86dd) && ip.ttl == 0xff && (eth.type == 0x800 || eth.type == 0x86dd) && icmp6.type == 0x87 && eth.type == 0x86dd && ip.proto == 0x3a && (eth.type == 0x800 || eth.type == 0x86dd) && icmp6.code == 0 && eth.type == 0x86dd && ip.proto == 0x3a && (eth.type == 0x800 || eth.type == 0x86dd) && ip.ttl == 0xff && (eth.type == 0x800 || eth.type == 0x86dd)

 # put_dhcpv6_opts
 reg1[0] = put_dhcpv6_opts(ia_addr = ae70::4, server_id = 00:00:00:00:10:02);