From: Numan Siddique <nusid...@redhat.com>
Presently, if a logical flow has possible conjunctive matches, OVN expression
parser has support for that. But certain fields like ip4.src, ip4.dst are not
considered as dimensions in the conjunctive matches.
In order to support all the possible fields as dimensions, this patch has added
a new expression type 'EXPR_T_CONJ'. After a expression is simplified by
expr_simplify(), before calling expr_normalize(), a new function
expr_eval_conj() is called, which evaluates for possible dimensions for
conjunctive matches.
For example if the match expression is
"ip4 && ip4.src == {10.0.0.4, 10.0.0.5, 10.0.0.6} &&
ip4.dst == {20.0.0.4, 20.0.0.5, 20.0.0.6}"
expr_simplify() would have generated the expression as -
AND(CMP(IP4),
OR((CMP(ip4.src == 10.0.0.4), CMP(ip4.src == 10.0.0.5),
CMP(ip4.src == 10.0.0.6)),
OR((CMP(ip4.dst == 20.0.0.4), CMP(ip4.src == 20.0.0.5),
CMP(ip4.src == 20.0.0.6))).
expr_eval_conj() would return a new expression something like
CONJ(AND(CMP(IP4),
OR((CMP(ip4.src == 10.0.0.4), CMP(ip4.src == 10.0.0.5),
CMP(ip4.src == 10.0.0.6))),
AND(CMP(IP4),
OR((CMP(ip4.dst == 20.0.0.4), CMP(ip4.dst == 20.0.0.5),
CMP(ip4.dst == 20.0.0.6))))
expr_normalize() would normalize each individual 'AND' clause in the CONJ and
expr_to_matches() would add the necessary conjunctive matches.
TODO: If the proposed approach is reasonable, then test cases and necessary
code comments needs to be added.
Signed-off-by: Numan Siddique <nusid...@redhat.com>
---
include/ovn/expr.h | 7 ++-
ovn/controller/lflow.c | 2 +
ovn/lib/expr.c | 166 +++++++++++++++++++++++++++++++++++++++++++++++++
tests/test-ovn.c | 2 +-
4 files changed, 175 insertions(+), 2 deletions(-)
diff --git a/include/ovn/expr.h b/include/ovn/expr.h
index 711713e08..4259e5938 100644
--- a/include/ovn/expr.h
+++ b/include/ovn/expr.h
@@ -295,6 +295,7 @@ enum expr_type {
EXPR_T_CONDITION, /* Conditional to be evaluated in the
* controller during expr_simplify(),
* prior to constructing OpenFlow matches. */
+ EXPR_T_CONJ,
};
/* Expression condition type. */
@@ -366,12 +367,16 @@ struct expr {
/* XXX Should arguments for conditions be generic? */
char *string;
} cond;
+
+ /* EXPR_T_CONJ. */
+ struct ovs_list conj;
};
};
struct expr *expr_create_boolean(bool b);
struct expr *expr_create_andor(enum expr_type);
struct expr *expr_combine(enum expr_type, struct expr *a, struct expr *b);
+struct expr *expr_create_conj(enum expr_type);
static inline struct expr *
expr_from_node(const struct ovs_list *node)
@@ -500,5 +505,5 @@ void expr_addr_sets_add(struct shash *addr_sets, const char
*name,
const char * const *values, size_t n_values);
void expr_addr_sets_remove(struct shash *addr_sets, const char *name);
void expr_addr_sets_destroy(struct shash *addr_sets);
-
+struct expr *expr_eval_conj(struct expr *expr);
#endif /* ovn/expr.h */
diff --git a/ovn/controller/lflow.c b/ovn/controller/lflow.c
index 1e79a5355..13413c77d 100644
--- a/ovn/controller/lflow.c
+++ b/ovn/controller/lflow.c
@@ -289,6 +289,7 @@ consider_logical_flow(struct controller_ctx *ctx,
expr = expr_combine(EXPR_T_AND, expr, prereqs);
prereqs = NULL;
}
+
expr = expr_annotate(expr, &symtab, &error);
}
if (error) {
@@ -304,6 +305,7 @@ consider_logical_flow(struct controller_ctx *ctx,
struct condition_aux cond_aux = { ctx->ovnsb_idl, chassis, active_tunnels,
chassis_index};
expr = expr_simplify(expr, is_chassis_resident_cb, &cond_aux);
+ expr = expr_eval_conj(expr);
expr = expr_normalize(expr);
uint32_t n_conjs = expr_to_matches(expr, lookup_port_cb, &aux,
&matches);
diff --git a/ovn/lib/expr.c b/ovn/lib/expr.c
index 79ff45762..3d4c68dd8 100644
--- a/ovn/lib/expr.c
+++ b/ovn/lib/expr.c
@@ -152,6 +152,14 @@ expr_create_andor(enum expr_type type)
return e;
}
+struct expr *
+expr_create_conj(enum expr_type type)
+{
+ struct expr *e = xmalloc(sizeof *e);
+ e->type = type;
+ ovs_list_init(&e->conj);
+ return e;
+}
/* Returns a logical AND or OR expression (according to 'type', which must be
* EXPR_T_AND or EXPR_T_OR) whose sub-expressions are 'a' and 'b', with some
* flexibility:
@@ -238,6 +246,7 @@ expr_not(struct expr *expr)
expr->cond.not = !expr->cond.not;
break;
+ case EXPR_T_CONJ:
default:
OVS_NOT_REACHED();
}
@@ -298,6 +307,7 @@ expr_fix(struct expr *expr)
case EXPR_T_CONDITION:
return expr;
+ case EXPR_T_CONJ:
default:
OVS_NOT_REACHED();
}
@@ -442,6 +452,9 @@ expr_format(const struct expr *e, struct ds *s)
case EXPR_T_CONDITION:
expr_format_condition(e, s);
break;
+
+ case EXPR_T_CONJ:
+ break;
}
}
@@ -1452,6 +1465,9 @@ expr_get_level(const struct expr *expr)
case EXPR_T_CONDITION:
return EXPR_L_BOOLEAN;
+ case EXPR_T_CONJ:
+ return EXPR_T_CONJ;
+
default:
OVS_NOT_REACHED();
}
@@ -1540,6 +1556,19 @@ expr_clone_condition(struct expr *expr)
return new;
}
+static struct expr *
+expr_clone_conj(struct expr *expr)
+{
+ struct expr *new = expr_create_conj(expr->type);
+ struct expr *sub;
+
+ LIST_FOR_EACH (sub, node, &expr->conj) {
+ struct expr *new_sub = expr_clone(sub);
+ ovs_list_push_back(&new->conj, &new_sub->node);
+ }
+ return new;
+}
+
/* Returns a clone of 'expr'. This is a "deep copy": neither the returned
* expression nor any of its substructure will be shared with 'expr'. */
struct expr *
@@ -1558,6 +1587,9 @@ expr_clone(struct expr *expr)
case EXPR_T_CONDITION:
return expr_clone_condition(expr);
+
+ case EXPR_T_CONJ:
+ return expr_clone_conj(expr);
}
OVS_NOT_REACHED();
}
@@ -1593,6 +1625,13 @@ expr_destroy(struct expr *expr)
case EXPR_T_CONDITION:
free(expr->cond.string);
break;
+
+ case EXPR_T_CONJ:
+ LIST_FOR_EACH_SAFE (sub, next, node, &expr->conj) {
+ ovs_list_remove(&sub->node);
+ expr_destroy(sub);
+ }
+ break;
}
free(expr);
}
@@ -1725,6 +1764,7 @@ expr_annotate__(struct expr *expr, const struct shash
*symtab,
*errorp = NULL;
return expr;
+ case EXPR_T_CONJ:
default:
OVS_NOT_REACHED();
}
@@ -1918,6 +1958,9 @@ expr_simplify(struct expr *expr,
case EXPR_T_CONDITION:
return expr_simplify_condition(expr, is_chassis_resident, c_aux);
+
+ case EXPR_T_CONJ:
+ OVS_NOT_REACHED();
}
OVS_NOT_REACHED();
}
@@ -1946,6 +1989,7 @@ expr_is_cmp(const struct expr *expr)
case EXPR_T_BOOLEAN:
case EXPR_T_CONDITION:
+ case EXPR_T_CONJ:
return NULL;
default:
@@ -2043,6 +2087,7 @@ crush_and_string(struct expr *expr, const struct
expr_symbol *symbol)
free(new);
break;
case EXPR_T_CONDITION:
+ case EXPR_T_CONJ:
OVS_NOT_REACHED();
}
}
@@ -2139,6 +2184,7 @@ crush_and_numeric(struct expr *expr, const struct
expr_symbol *symbol)
expr_destroy(new);
break;
case EXPR_T_CONDITION:
+ case EXPR_T_CONJ:
OVS_NOT_REACHED();
}
}
@@ -2356,6 +2402,7 @@ crush_cmps(struct expr *expr, const struct expr_symbol
*symbol)
* called during expr_normalize, after expr_simplify which resolves
* all conditions. */
case EXPR_T_CONDITION:
+ case EXPR_T_CONJ:
default:
OVS_NOT_REACHED();
}
@@ -2564,6 +2611,20 @@ expr_normalize(struct expr *expr)
case EXPR_T_BOOLEAN:
return expr;
+ case EXPR_T_CONJ: {
+ struct expr *sub, *next;
+ LIST_FOR_EACH_SAFE (sub, next, node, &expr->conj) {
+ ovs_list_remove(&sub->node);
+ struct expr *new_sub = expr_normalize(sub);
+ if (!new_sub) {
+ expr_destroy(expr);
+ return NULL;
+ }
+ ovs_list_insert(&next->node, &new_sub->node);
+ }
+ return expr;
+ }
+
/* Should not hit expression type condition, since expr_normalize is
* only called after expr_simplify, which resolves all conditions. */
case EXPR_T_CONDITION:
@@ -2737,6 +2798,7 @@ add_conjunction(const struct expr *and,
case EXPR_T_AND:
case EXPR_T_BOOLEAN:
case EXPR_T_CONDITION:
+ case EXPR_T_CONJ:
default:
OVS_NOT_REACHED();
}
@@ -2870,6 +2932,34 @@ expr_to_matches(const struct expr *expr,
}
break;
+ case EXPR_T_CONJ: {
+ struct expr *sub;
+ n_conjs = 1;
+ size_t n_clauses = ovs_list_size(&expr->conj);
+ uint8_t clause = 0;
+ LIST_FOR_EACH (sub, node, &expr->conj) {
+ struct hmap conj_matches;
+ uint32_t sub_conjs = expr_to_matches(sub, lookup_port, aux,
+ &conj_matches);
+ ovs_assert(sub_conjs == 0);
+ struct expr_match *m;
+
+ HMAP_FOR_EACH (m, hmap_node, &conj_matches) {
+ expr_match_add(matches, expr_match_new(&m->match, clause,
+ n_clauses, n_conjs));
+ }
+ clause++;
+ expr_matches_destroy(&conj_matches);
+ }
+
+ /* Add the flow that matches on conj_id. */
+ struct match match;
+ match_init_catchall(&match);
+ match_set_conj_id(&match, n_conjs);
+ expr_match_add(matches, expr_match_new(&match, 0, 0, 0));
+ break;
+ }
+
/* Should not hit expression type condition, since expr_to_matches is
* only called after expr_simplify, which resolves all conditions. */
case EXPR_T_CONDITION:
@@ -2954,6 +3044,7 @@ expr_honors_invariants(const struct expr *expr)
case EXPR_T_CONDITION:
return true;
+ case EXPR_T_CONJ:
default:
OVS_NOT_REACHED();
}
@@ -3003,6 +3094,17 @@ expr_is_normalized(const struct expr *expr)
case EXPR_T_CONDITION:
return false;
+ case EXPR_T_CONJ: {
+ const struct expr *sub;
+
+ LIST_FOR_EACH (sub, node, &expr->conj) {
+ if (!expr_is_normalized(sub)) {
+ return false;
+ }
+ }
+ return true;
+ }
+
default:
OVS_NOT_REACHED();
}
@@ -3100,6 +3202,7 @@ expr_evaluate(const struct expr *e, const struct flow
*uflow,
* is_chassis_resident evaluates as true. */
return (e->cond.not ? false : true);
+ case EXPR_T_CONJ:
default:
OVS_NOT_REACHED();
}
@@ -3221,6 +3324,7 @@ expr_parse_microflow__(struct lexer *lexer,
/* Should not hit expression type condition, since
* expr_simplify was called above. */
case EXPR_T_CONDITION:
+ case EXPR_T_CONJ:
default:
OVS_NOT_REACHED();
}
@@ -3286,3 +3390,65 @@ expr_parse_microflow(const char *s, const struct shash
*symtab,
}
return error;
}
+
+/* Takes ownership of the simplified 'expr' returned by expr_simplify() and
+ * evaluates for possible conjunctive matches if it's of type AND.
+ * If the AND 'expr' has 2 or more OR clauses, then it returns a new expr of
+ * type EXPR_T_CONJ.
+ * Eg. If 'expr' is AND(CMP1, CMP2, CMP3, OR1, OR2, OR3), then it returns
+ * as CONJ(AND(CMP1, CMP2, OR1), AND(CMP1, CMP2, OR2), AND(CMP1, CMP2, OR3))
+ */
+struct expr *
+expr_eval_conj(struct expr *expr)
+{
+ if (expr->type != EXPR_T_AND) {
+ return expr;
+ }
+
+ /* We want to sort before checking for possible conjunctive matches.
+ * If the 'expr' has multiple OR clauses on the same field, expr_sort
+ * will combine them.
+ */
+ expr = expr_sort(expr);
+
+ if (expr->type != EXPR_T_AND) {
+ return expr;
+ }
+
+ struct expr *sub;
+ uint8_t n_dimensions = 0;
+ LIST_FOR_EACH (sub, node, &expr->andor) {
+ if (sub->type == EXPR_T_OR && ovs_list_size(&sub->andor) > 2) {
+ n_dimensions++;
+ }
+ }
+
+ if (n_dimensions < 2) {
+ return expr;
+ }
+
+ struct expr *conj_expr = expr_create_conj(EXPR_T_CONJ);
+ struct expr **conj_clause = xmalloc(n_dimensions * sizeof *conj_clause);;
+ for (uint8_t i = 0; i < n_dimensions; i++) {
+ conj_clause[i] = expr_create_andor(EXPR_T_AND);
+ ovs_list_push_back(&conj_expr->conj, &conj_clause[i]->node);
+ }
+
+ uint8_t j = 0;
+ LIST_FOR_EACH (sub, node, &expr->andor) {
+ if (sub->type == EXPR_T_OR && ovs_list_size(&sub->andor) > 2) {
+ struct expr *e = expr_clone(sub);
+ ovs_list_push_back(&conj_clause[j]->andor, &e->node);
+ j++;
+ } else {
+ for (uint8_t i = 0; i < n_dimensions; i++) {
+ struct expr *e = expr_clone(sub);
+ ovs_list_push_back(&conj_clause[i]->andor, &e->node);
+ }
+ }
+ }
+
+ expr_destroy(expr);
+ free(conj_clause);
+ return conj_expr;
+}
diff --git a/tests/test-ovn.c b/tests/test-ovn.c
index d4dfc8151..915123f54 100644
--- a/tests/test-ovn.c
+++ b/tests/test-ovn.c
@@ -270,6 +270,7 @@ test_parse_expr__(int steps)
expr = expr_simplify(expr, is_chassis_resident_cb, &ports);
}
if (steps > 2) {
+ expr = expr_eval_conj(expr);
expr = expr_normalize(expr);
ovs_assert(expr_is_normalized(expr));
}
@@ -294,7 +295,6 @@ test_parse_expr__(int steps)
expr_destroy(expr);
}
ds_destroy(&input);
-
simap_destroy(&ports);
expr_symtab_destroy(&symtab);
shash_destroy(&symtab);
