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