On Tue, 8 May 2018 18:08:54 +0530 Numan Siddique <[email protected]> wrote:
> On Tue, May 8, 2018 at 5:39 PM, Jakub Sitnicki <[email protected]> wrote: > > > On Tue, 8 May 2018 11:47:34 +0530 > > Numan Siddique <[email protected]> wrote: > > > > > On Mon, May 7, 2018 at 9:57 PM, Mark Michelson <[email protected]> > > 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 <[email protected]> > > > > > > > > > > > > Same here. I tested with all the combinations I could think of. > > > > > > Acked-by: Numan Siddique <[email protected]> > > > > @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 <[email protected]> > > > >> --- > > > >> > > > >> 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 > > > >> [email protected] > > > >> https://mail.openvswitch.org/mailman/listinfo/ovs-dev > > > >> > > > >> > > > > _______________________________________________ > > > > dev mailing list > > > > [email protected] > > > > https://mail.openvswitch.org/mailman/listinfo/ovs-dev > > > > > > > > _______________________________________________ dev mailing list [email protected] https://mail.openvswitch.org/mailman/listinfo/ovs-dev
