On Wed, 9 May 2018 13:02:55 -0700
Ben Pfaff <b...@ovn.org> wrote:
> On Thu, Apr 26, 2018 at 09:54:06PM +0200, 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 nice. Thank you.
>
> I suggest folding in the following to better document and to better
> match usual OVS style:
>
> diff --git a/ovn/lib/expr.c b/ovn/lib/expr.c
> index 9dd8d6f17abe..bac8e1efd53f 100644
> --- a/ovn/lib/expr.c
> +++ b/ovn/lib/expr.c
> @@ -32,13 +32,10 @@
>
> 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 const struct expr_symbol *expr_get_unique_symbol(const struct expr *);
> +struct expr *expr_annotate__(struct 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,
> @@ -1771,6 +1768,15 @@ error:
> return NULL;
> }
>
> +/* Same interface and purpose as expr_annotate(), with a couple of additional
> + * parameters for internal bookkeeping.
> + *
> + * Uses 'nesting' to ensure that a given symbol is not recursively expanded.
> + *
> + * 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). */
> struct expr *
> expr_annotate__(struct expr *expr, const struct shash *symtab,
> bool append_prereqs, struct ovs_list *nesting, char **errorp)
>
> I also wonder about the following, because it seems like currently the
> append_prereqs parameter is only being honored for a single level of
> AND/OR, not when expr_annotate__() recurses:
>
> diff --git a/ovn/lib/expr.c b/ovn/lib/expr.c
> index 9dd8d6f17abe..a33b4eb46933 100644
> --- a/ovn/lib/expr.c
> +++ b/ovn/lib/expr.c
> @@ -1782,12 +1788,25 @@ expr_annotate__(struct expr *expr, const struct shash
> *symtab,
>
> case EXPR_T_AND:
> case EXPR_T_OR: {
> - const struct expr_symbol *unique_symbol =
> expr_get_unique_symbol(expr);
> + /* 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 true, though, we're not supposed to handle
> + * prereqs at all (because our caller is already doing it). */
> + const struct expr_symbol *unique_symbol = NULL;
> + if (!append_prereqs) {
> + unique_symbol = expr_get_unique_symbol(expr);
> + if (unique_symbol) {
> + append_prereqs = false;
> + }
> + }
> +
> 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,
> !unique_symbol,
> + struct expr *new_sub = expr_annotate__(sub, symtab,
> append_prereqs,
> nesting, errorp);
> if (!new_sub) {
> expr_destroy(expr);
>
> However this patch, while it seems reasonable, causes some test failures
> due to the difference that it produces and I'm not sure whether the new
> results are actually superior to the old ones.
Thank you for the review and the style fixes. I'll have to mull over the
recursive case, this is something I have not considered, before I roll
out a v2.
-Jakub
_______________________________________________
dev mailing list
d...@openvswitch.org
https://mail.openvswitch.org/mailman/listinfo/ovs-dev
