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 the only thing we gain is a shorter expression as prerequisites for each symbol appear only once. Documentation comments have been contributed by Ben Pfaff. Signed-off-by: Jakub Sitnicki <j...@redhat.com> --- ovn/lib/expr.c | 75 ++++++++++++++++++++++++++++++++++++++++++++++++++-------- tests/ovn.at | 9 +++++-- 2 files changed, 72 insertions(+), 12 deletions(-) diff --git a/ovn/lib/expr.c b/ovn/lib/expr.c index 5840ef871..148ac869e 100644 --- a/ovn/lib/expr.c +++ b/ovn/lib/expr.c @@ -1658,8 +1658,8 @@ 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 *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, @@ -1670,7 +1670,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, nesting, &error); } if (expr) { *errorp = NULL; @@ -1685,7 +1685,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 +1703,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 +1744,65 @@ expr_annotate_cmp(struct expr *expr, const struct shash *symtab, return NULL; } -struct expr * +/* Append (logical AND) prerequisites 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) { + expr_destroy(expr); + return NULL; + } + } + + return prereqs ? expr_combine(EXPR_T_AND, expr, prereqs) : expr; +} + +static const struct expr_symbol *expr_get_unique_symbol( + const struct expr *expr); + +/* 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). */ +static 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: { struct expr *sub, *next; + /* 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 false, though, we're not supposed to handle + * prereqs at all (because our caller is already doing it). */ + if (append_prereqs) { + const struct expr_symbol *sym = expr_get_unique_symbol(expr); + if (sym) { + append_prereqs = false; + expr = expr_append_prereqs(expr, sym, symtab, nesting, errorp); + if (!expr) { + return NULL; + } + } + } + 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, append_prereqs, nesting, errorp); if (!new_sub) { expr_destroy(expr); @@ -1780,6 +1824,17 @@ expr_annotate__(struct expr *expr, const struct shash *symtab, } } +/* Same interface and purpose as expr_annotate(), with an additional parameter + * for internal bookkeeping. + * + * Uses 'nesting' to ensure that a given symbol is not recursively expanded. */ +static struct expr * +expr_annotate_(struct expr *expr, const struct shash *symtab, + struct ovs_list *nesting, char **errorp) +{ + return expr_annotate__(expr, symtab, true, nesting, errorp); +} + /* "Annotates" 'expr', which does the following: * * - Applies prerequisites, by locating each comparison operator whose @@ -1802,7 +1857,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, &nesting, errorp); } static struct expr * diff --git a/tests/ovn.at b/tests/ovn.at index 4a5316510..69daffe75 100644 --- a/tests/ovn.at +++ b/tests/ovn.at @@ -361,13 +361,18 @@ AT_CLEANUP AT_SETUP([ovn -- expression annotation]) dnl Input precedes =>, expected output follows =>. +dnl Empty lines and lines starting with # are ignored. 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 +# Nested expressions over a single symbol should be annotated with symbol's +# prerequisites only once, at the top level. +tcp.dst == 1 || (tcp.dst >= 2 && tcp.dst <= 3) => (tcp.dst == 0x1 || (tcp.dst >= 0x2 && tcp.dst <= 0x3)) && ip.proto == 0x6 && (eth.type == 0x800 || eth.type == 0x86dd) + ip => eth.type == 0x800 || eth.type == 0x86dd ip == 1 => eth.type == 0x800 || eth.type == 0x86dd ip[0] == 1 => eth.type == 0x800 || eth.type == 0x86dd @@ -1060,7 +1065,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 d...@openvswitch.org https://mail.openvswitch.org/mailman/listinfo/ovs-dev