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