[ovs-dev] [PATCH v3 7/9] expr: New function expr_evaluate().
Ben Pfaff
blp at ovn.org
Mon Aug 8 18:21:50 UTC 2016
An upcoming commit will need to evaluate individual expressions outside the
context of a classifier. test-ovn already had a function to do this but it
wasn't general-purpose, so this commit makes a general-purpose version and
adopts it for use in test-ovn as well.
Signed-off-by: Ben Pfaff <blp at ovn.org>
---
include/ovn/expr.h | 6 +++
ovn/lib/expr.c | 118 +++++++++++++++++++++++++++++++++++++++++++++++-
tests/test-ovn.c | 130 ++++++++++-------------------------------------------
3 files changed, 147 insertions(+), 107 deletions(-)
diff --git a/include/ovn/expr.h b/include/ovn/expr.h
index e1c1886..fa603bb 100644
--- a/include/ovn/expr.h
+++ b/include/ovn/expr.h
@@ -61,6 +61,7 @@
struct ds;
struct expr;
+struct flow;
struct ofpbuf;
struct shash;
struct simap;
@@ -380,6 +381,11 @@ struct expr *expr_normalize(struct expr *);
bool expr_honors_invariants(const struct expr *);
bool expr_is_simplified(const struct expr *);
bool expr_is_normalized(const struct expr *);
+
+bool expr_evaluate(const struct expr *, const struct flow *uflow,
+ bool (*lookup_port)(const void *aux, const char *port_name,
+ unsigned int *portp),
+ const void *aux);
/* Converting expressions to OpenFlow flows. */
diff --git a/ovn/lib/expr.c b/ovn/lib/expr.c
index c3a26f5..f90c7d1 100644
--- a/ovn/lib/expr.c
+++ b/ovn/lib/expr.c
@@ -119,6 +119,22 @@ expr_relop_invert(enum expr_relop relop)
default: OVS_NOT_REACHED();
}
}
+
+/* Checks whether 'relop' is true for strcmp()-like 3-way comparison result
+ * 'cmp'. */
+static bool
+expr_relop_test(enum expr_relop relop, int cmp)
+{
+ switch (relop) {
+ case EXPR_R_EQ: return cmp == 0;
+ case EXPR_R_NE: return cmp != 0;
+ case EXPR_R_LT: return cmp < 0;
+ case EXPR_R_LE: return cmp <= 0;
+ case EXPR_R_GT: return cmp > 0;
+ case EXPR_R_GE: return cmp >= 0;
+ default: OVS_NOT_REACHED();
+ }
+}
/* Constructing and manipulating expressions. */
@@ -2445,9 +2461,17 @@ expr_match_add(struct hmap *matches, struct expr_match *match)
hmap_insert(matches, &match->hmap_node, hash);
}
+/* Applies EXPR_T_CMP-typed 'expr' to 'm'. This will only work properly if 'm'
+ * doesn't already match on 'expr->cmp.symbol', because it replaces any
+ * existing match on that symbol instead of intersecting with it.
+ *
+ * If 'expr' is a comparison on a string field, uses 'lookup_port' and 'aux' to
+ * convert the string to a port number. In such a case, if the port can't be
+ * found, returns false. In all other cases, returns true. */
static bool
constrain_match(const struct expr *expr,
- bool (*lookup_port)(const void *aux, const char *port_name,
+ bool (*lookup_port)(const void *aux,
+ const char *port_name,
unsigned int *portp),
const void *aux, struct match *m)
{
@@ -2788,6 +2812,98 @@ expr_is_normalized(const struct expr *expr)
OVS_NOT_REACHED();
}
}
+
+static bool
+expr_evaluate_andor(const struct expr *e, const struct flow *f,
+ bool short_circuit,
+ bool (*lookup_port)(const void *aux, const char *port_name,
+ unsigned int *portp),
+ const void *aux)
+{
+ const struct expr *sub;
+
+ LIST_FOR_EACH (sub, node, &e->andor) {
+ if (expr_evaluate(sub, f, lookup_port, aux) == short_circuit) {
+ return short_circuit;
+ }
+ }
+ return !short_circuit;
+}
+
+static bool
+expr_evaluate_cmp(const struct expr *e, const struct flow *f,
+ bool (*lookup_port)(const void *aux, const char *port_name,
+ unsigned int *portp),
+ const void *aux)
+{
+ const struct expr_symbol *s = e->cmp.symbol;
+ const struct mf_field *field = s->field;
+
+ int cmp;
+ if (e->cmp.symbol->width) {
+ int n_bytes = field->n_bytes;
+ const uint8_t *cst = &e->cmp.value.u8[sizeof e->cmp.value - n_bytes];
+ const uint8_t *mask = &e->cmp.mask.u8[sizeof e->cmp.mask - n_bytes];
+
+ /* Get field value and mask off undesired bits. */
+ union mf_value value;
+ mf_get_value(field, f, &value);
+ for (int i = 0; i < field->n_bytes; i++) {
+ value.b[i] &= mask[i];
+ }
+
+ /* Compare against constant. */
+ cmp = memcmp(&value, cst, n_bytes);
+ } else {
+ /* Get field value. */
+ struct mf_subfield sf = { .field = field, .ofs = 0,
+ .n_bits = field->n_bits };
+ uint64_t value = mf_get_subfield(&sf, f);
+
+ /* Get constant. */
+ unsigned int cst;
+ if (!lookup_port(aux, e->cmp.string, &cst)) {
+ return false;
+ }
+
+ /* Compare. */
+ cmp = value < cst ? -1 : value > cst;
+ }
+
+ return expr_relop_test(e->cmp.relop, cmp);
+}
+
+/* Evaluates 'e' against microflow 'uflow' and returns the result.
+ *
+ * 'lookup_port' must be a function to map from a port name to a port number
+ * and 'aux' auxiliary data to pass to it; see expr_to_matches() for more
+ * details.
+ *
+ * This isn't particularly fast. For performance-sensitive tasks, use
+ * expr_to_matches() and the classifier. */
+bool
+expr_evaluate(const struct expr *e, const struct flow *uflow,
+ bool (*lookup_port)(const void *aux, const char *port_name,
+ unsigned int *portp),
+ const void *aux)
+{
+ switch (e->type) {
+ case EXPR_T_CMP:
+ return expr_evaluate_cmp(e, uflow, lookup_port, aux);
+
+ case EXPR_T_AND:
+ return expr_evaluate_andor(e, uflow, false, lookup_port, aux);
+
+ case EXPR_T_OR:
+ return expr_evaluate_andor(e, uflow, true, lookup_port, aux);
+
+ case EXPR_T_BOOLEAN:
+ return e->boolean;
+
+ default:
+ OVS_NOT_REACHED();
+ }
+}
/* Action parsing helper. */
diff --git a/tests/test-ovn.c b/tests/test-ovn.c
index e62c2fe..712c54a 100644
--- a/tests/test-ovn.c
+++ b/tests/test-ovn.c
@@ -327,91 +327,12 @@ test_dump_symtab(struct ovs_cmdl_context *ctx OVS_UNUSED)
/* Evaluate an expression. */
-static bool evaluate_expr(const struct expr *, unsigned int subst, int n_bits);
-
-static bool
-evaluate_andor_expr(const struct expr *expr, unsigned int subst, int n_bits,
- bool short_circuit)
-{
- const struct expr *sub;
-
- LIST_FOR_EACH (sub, node, &expr->andor) {
- if (evaluate_expr(sub, subst, n_bits) == short_circuit) {
- return short_circuit;
- }
- }
- return !short_circuit;
-}
-
-static bool
-evaluate_cmp_expr(const struct expr *expr, unsigned int subst, int n_bits)
-{
- int var_idx = atoi(expr->cmp.symbol->name + 1);
- if (expr->cmp.symbol->name[0] == 'n') {
- unsigned var_mask = (1u << n_bits) - 1;
- unsigned int arg1 = (subst >> (var_idx * n_bits)) & var_mask;
- unsigned int arg2 = ntohll(expr->cmp.value.integer);
- unsigned int mask = ntohll(expr->cmp.mask.integer);
-
- ovs_assert(!(mask & ~var_mask));
- ovs_assert(!(arg2 & ~var_mask));
- ovs_assert(!(arg2 & ~mask));
-
- arg1 &= mask;
- switch (expr->cmp.relop) {
- case EXPR_R_EQ:
- return arg1 == arg2;
-
- case EXPR_R_NE:
- return arg1 != arg2;
-
- case EXPR_R_LT:
- return arg1 < arg2;
-
- case EXPR_R_LE:
- return arg1 <= arg2;
-
- case EXPR_R_GT:
- return arg1 > arg2;
-
- case EXPR_R_GE:
- return arg1 >= arg2;
-
- default:
- OVS_NOT_REACHED();
- }
- } else if (expr->cmp.symbol->name[0] == 's') {
- unsigned int arg1 = (subst >> (test_nvars * n_bits + var_idx)) & 1;
- unsigned int arg2 = atoi(expr->cmp.string);
- return arg1 == arg2;
- } else {
- OVS_NOT_REACHED();
- }
-}
-
-/* Evaluates 'expr' and returns its Boolean result. 'subst' provides the value
- * for the variables, which must be 'n_bits' bits each and be named "a", "b",
- * "c", etc. The value of variable "a" is the least-significant 'n_bits' bits
- * of 'subst', the value of "b" is the next 'n_bits' bits, and so on. */
static bool
-evaluate_expr(const struct expr *expr, unsigned int subst, int n_bits)
+lookup_atoi_cb(const void *aux OVS_UNUSED, const char *port_name,
+ unsigned int *portp)
{
- switch (expr->type) {
- case EXPR_T_CMP:
- return evaluate_cmp_expr(expr, subst, n_bits);
-
- case EXPR_T_AND:
- return evaluate_andor_expr(expr, subst, n_bits, false);
-
- case EXPR_T_OR:
- return evaluate_andor_expr(expr, subst, n_bits, true);
-
- case EXPR_T_BOOLEAN:
- return expr->boolean;
-
- default:
- OVS_NOT_REACHED();
- }
+ *portp = atoi(port_name);
+ return true;
}
static void
@@ -420,17 +341,18 @@ test_evaluate_expr(struct ovs_cmdl_context *ctx)
int a = atoi(ctx->argv[1]);
int b = atoi(ctx->argv[2]);
int c = atoi(ctx->argv[3]);
- unsigned int subst = a | (b << 3) || (c << 6);
+ struct flow uflow = { .regs = { a, b, c } };
+
struct shash symtab;
struct ds input;
shash_init(&symtab);
- expr_symtab_add_field(&symtab, "xreg0", MFF_XREG0, NULL, false);
- expr_symtab_add_field(&symtab, "xreg1", MFF_XREG1, NULL, false);
- expr_symtab_add_field(&symtab, "xreg2", MFF_XREG1, NULL, false);
- expr_symtab_add_subfield(&symtab, "a", NULL, "xreg0[0..2]");
- expr_symtab_add_subfield(&symtab, "b", NULL, "xreg1[0..2]");
- expr_symtab_add_subfield(&symtab, "c", NULL, "xreg2[0..2]");
+ expr_symtab_add_field(&symtab, "reg0", MFF_REG0, NULL, false);
+ expr_symtab_add_field(&symtab, "reg1", MFF_REG1, NULL, false);
+ expr_symtab_add_field(&symtab, "reg2", MFF_REG1, NULL, false);
+ expr_symtab_add_subfield(&symtab, "a", NULL, "reg0[0..2]");
+ expr_symtab_add_subfield(&symtab, "b", NULL, "reg1[0..2]");
+ expr_symtab_add_subfield(&symtab, "c", NULL, "reg2[0..2]");
ds_init(&input);
while (!ds_get_test_line(&input, stdin)) {
@@ -442,7 +364,7 @@ test_evaluate_expr(struct ovs_cmdl_context *ctx)
expr = expr_annotate(expr, &symtab, &error);
}
if (!error) {
- printf("%d\n", evaluate_expr(expr, subst, 3));
+ printf("%d\n", expr_evaluate(expr, &uflow, lookup_atoi_cb, NULL));
} else {
puts(error);
free(error);
@@ -874,10 +796,6 @@ test_tree_shape_exhaustively(struct expr *expr, struct shash *symtab,
int n_bits,
const struct expr_symbol *svars[], int n_svars)
{
- struct simap string_map = SIMAP_INITIALIZER(&string_map);
- simap_put(&string_map, "0", 0);
- simap_put(&string_map, "1", 1);
-
int n_tested = 0;
const unsigned int var_mask = (1u << n_bits) - 1;
@@ -892,7 +810,6 @@ test_tree_shape_exhaustively(struct expr *expr, struct shash *symtab,
for (int i = n_terminals - 1; ; i--) {
if (!i) {
ds_destroy(&s);
- simap_destroy(&string_map);
return n_tested;
}
if (next_terminal(terminals[i], nvars, n_nvars, n_bits,
@@ -933,7 +850,7 @@ test_tree_shape_exhaustively(struct expr *expr, struct shash *symtab,
struct expr_match *m;
struct test_rule *test_rule;
- expr_to_matches(modified, lookup_port_cb, &string_map, &matches);
+ expr_to_matches(modified, lookup_atoi_cb, NULL, &matches);
classifier_init(&cls, NULL);
HMAP_FOR_EACH (m, hmap_node, &matches) {
@@ -945,8 +862,16 @@ test_tree_shape_exhaustively(struct expr *expr, struct shash *symtab,
}
for (int subst = 0; subst < 1 << (n_bits * n_nvars + n_svars);
subst++) {
- bool expected = evaluate_expr(expr, subst, n_bits);
- bool actual = evaluate_expr(modified, subst, n_bits);
+ for (int i = 0; i < n_nvars; i++) {
+ f.regs[i] = (subst >> (i * n_bits)) & var_mask;
+ }
+ for (int i = 0; i < n_svars; i++) {
+ f.regs[n_nvars + i] = ((subst >> (n_nvars * n_bits + i))
+ & 1);
+ }
+
+ bool expected = expr_evaluate(expr, &f, lookup_atoi_cb, NULL);
+ bool actual = expr_evaluate(modified, &f, lookup_atoi_cb, NULL);
if (actual != expected) {
struct ds expr_s, modified_s;
@@ -976,13 +901,6 @@ test_tree_shape_exhaustively(struct expr *expr, struct shash *symtab,
}
if (operation >= OP_FLOW) {
- for (int i = 0; i < n_nvars; i++) {
- f.regs[i] = (subst >> (i * n_bits)) & var_mask;
- }
- for (int i = 0; i < n_svars; i++) {
- f.regs[n_nvars + i] = ((subst >> (n_nvars * n_bits + i))
- & 1);
- }
bool found = classifier_lookup(&cls, OVS_VERSION_MIN,
&f, NULL) != NULL;
if (expected != found) {
--
2.1.3
More information about the dev
mailing list