# [ovs-dev] [PATCH] Factor prerequisites out of AND/OR trees with unique symbol

Jakub Sitnicki jkbs at redhat.com
Thu Apr 26 19:54:06 UTC 2018

```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 <jkbs at 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[],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
```