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