The expr test cases covered string variables poorly and thus a number of
bugs and omissions slipped through. This fixes them and generalizes the
test cases to better cover string variables.
Reported-by: Justin Pettit <jpet...@nicira.com>
Signed-off-by: Ben Pfaff <b...@nicira.com>
---
v1->v2: Fix return type of compare_cmps_3way().
ovn/lib/expr.c | 160 ++++++++++++++++++++++++++----
tests/ovn.at | 93 ++++++++++++++----
tests/test-ovn.c | 295 +++++++++++++++++++++++++++++++++++++------------------
3 files changed, 414 insertions(+), 134 deletions(-)
diff --git a/ovn/lib/expr.c b/ovn/lib/expr.c
index 7289a9b..71d817b 100644
--- a/ovn/lib/expr.c
+++ b/ovn/lib/expr.c
@@ -23,6 +23,7 @@
#include "ofp-actions.h"
#include "shash.h"
#include "simap.h"
+#include "sset.h"
#include "openvswitch/vlog.h"
VLOG_DEFINE_THIS_MODULE(expr);
@@ -1643,9 +1644,119 @@ compare_expr_sort(const void *a_, const void *b_)
static struct expr *crush_cmps(struct expr *, const struct expr_symbol *);
-/* Implementation of crush_cmps() for expr->type == EXPR_T_AND. */
+static bool
+disjunction_matches_string(const struct expr *or, const char *s)
+{
+ const struct expr *sub;
+
+ LIST_FOR_EACH (sub, node, &or->andor) {
+ if (!strcmp(sub->cmp.string, s)) {
+ return true;
+ }
+ }
+
+ return false;
+}
+
+/* Implementation of crush_cmps() for expr->type == EXPR_T_AND and a
+ * string-typed 'symbol'. */
+static struct expr *
+crush_and_string(struct expr *expr, const struct expr_symbol *symbol)
+{
+ ovs_assert(!list_is_short(&expr->andor));
+
+ struct expr *singleton = NULL;
+
+ /* First crush each subexpression into either a single EXPR_T_CMP or an
+ * EXPR_T_OR with EXPR_T_CMP subexpressions. */
+ struct expr *sub, *next = NULL;
+ LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
+ list_remove(&sub->node);
+ struct expr *new = crush_cmps(sub, symbol);
+ switch (new->type) {
+ case EXPR_T_CMP:
+ if (!singleton) {
+ list_insert(&next->node, &new->node);
+ singleton = new;
+ } else {
+ bool match = !strcmp(new->cmp.string, singleton->cmp.string);
+ expr_destroy(new);
+ if (!match) {
+ expr_destroy(expr);
+ return expr_create_boolean(false);
+ }
+ }
+ break;
+ case EXPR_T_AND:
+ OVS_NOT_REACHED();
+ case EXPR_T_OR:
+ list_insert(&next->node, &new->node);
+ break;
+ case EXPR_T_BOOLEAN:
+ if (!new->boolean) {
+ expr_destroy(expr);
+ return new;
+ }
+ free(new);
+ break;
+ }
+ }
+
+ /* If we have a singleton, then the result is either the singleton itself
+ * (if the ORs allow the singleton) or false. */
+ if (singleton) {
+ LIST_FOR_EACH (sub, node, &expr->andor) {
+ if (sub->type == EXPR_T_OR
+ && !disjunction_matches_string(sub, singleton->cmp.string)) {
+ expr_destroy(expr);
+ return expr_create_boolean(false);
+ }
+ }
+ list_remove(&singleton->node);
+ expr_destroy(expr);
+ return singleton;
+ }
+
+ /* Otherwise the result is the intersection of all of the ORs. */
+ struct sset result = SSET_INITIALIZER(&result);
+ LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
+ struct sset strings = SSET_INITIALIZER(&strings);
+ const struct expr *s;
+ LIST_FOR_EACH (s, node, &sub->andor) {
+ sset_add(&strings, s->cmp.string);
+ }
+ if (sset_is_empty(&result)) {
+ sset_swap(&result, &strings);
+ } else {
+ sset_intersect(&result, &strings);
+ }
+ sset_destroy(&strings);
+
+ if (sset_is_empty(&result)) {
+ expr_destroy(expr);
+ sset_destroy(&result);
+ return expr_create_boolean(false);
+ }
+ }
+
+ expr_destroy(expr);
+ expr = expr_create_andor(EXPR_T_OR);
+
+ const char *string;
+ SSET_FOR_EACH (string, &result) {
+ sub = xmalloc(sizeof *sub);
+ sub->type = EXPR_T_CMP;
+ sub->cmp.symbol = symbol;
+ sub->cmp.string = xstrdup(string);
+ list_push_back(&expr->andor, &sub->node);
+ }
+ return expr_fix(expr);
+}
+
+/* Implementation of crush_cmps() for expr->type == EXPR_T_AND and a
+ * numeric-typed 'symbol'. */
static struct expr *
-crush_and(struct expr *expr, const struct expr_symbol *symbol)
+crush_and_numeric(struct expr *expr, const struct expr_symbol *symbol)
{
ovs_assert(!list_is_short(&expr->andor));
@@ -1800,17 +1911,28 @@ crush_and(struct expr *expr, const struct expr_symbol
*symbol)
}
static int
-compare_expr(const void *a_, const void *b_)
+compare_cmps_3way(const struct expr *a, const struct expr *b)
+{
+ ovs_assert(a->cmp.symbol == b->cmp.symbol);
+ if (!a->cmp.symbol->width) {
+ return strcmp(a->cmp.string, b->cmp.string);
+ } else {
+ int d = memcmp(&a->cmp.value, &b->cmp.value, sizeof a->cmp.value);
+ if (!d) {
+ d = memcmp(&a->cmp.mask, &b->cmp.mask, sizeof a->cmp.mask);
+ }
+ return d;
+ }
+}
+
+static int
+compare_cmps_cb(const void *a_, const void *b_)
{
const struct expr *const *ap = a_;
const struct expr *const *bp = b_;
const struct expr *a = *ap;
const struct expr *b = *bp;
- int d = memcmp(&a->cmp.value, &b->cmp.value, sizeof a->cmp.value);
- if (!d) {
- d = memcmp(&a->cmp.mask, &b->cmp.mask, sizeof a->cmp.mask);
- }
- return d;
+ return compare_cmps_3way(a, b);
}
/* Implementation of crush_cmps() for expr->type == EXPR_T_OR. */
@@ -1841,15 +1963,15 @@ crush_or(struct expr *expr, const struct expr_symbol
*symbol)
}
ovs_assert(i == n);
- qsort(subs, n, sizeof *subs, compare_expr);
+ qsort(subs, n, sizeof *subs, compare_cmps_cb);
+ /* Eliminate duplicates. */
list_init(&expr->andor);
list_push_back(&expr->andor, &subs[0]->node);
for (i = 1; i < n; i++) {
struct expr *a = expr_from_node(list_back(&expr->andor));
struct expr *b = subs[i];
- if (memcmp(&a->cmp.value, &b->cmp.value, sizeof a->cmp.value)
- || memcmp(&a->cmp.mask, &b->cmp.mask, sizeof a->cmp.mask)) {
+ if (compare_cmps_3way(a, b)) {
list_push_back(&expr->andor, &b->node);
} else {
free(b);
@@ -1871,7 +1993,9 @@ crush_cmps(struct expr *expr, const struct expr_symbol
*symbol)
return crush_or(expr, symbol);
case EXPR_T_AND:
- return crush_and(expr, symbol);
+ return (symbol->width
+ ? crush_and_numeric(expr, symbol)
+ : crush_and_string(expr, symbol));
case EXPR_T_CMP:
return expr;
@@ -1967,12 +2091,14 @@ expr_normalize_and(struct expr *expr)
struct expr *a, *b;
LIST_FOR_EACH_SAFE (a, b, node, &expr->andor) {
if (&b->node == &expr->andor
- || a->type != EXPR_T_CMP || b->type != EXPR_T_CMP) {
- } else if (a->cmp.symbol != b->cmp.symbol) {
+ || a->type != EXPR_T_CMP || b->type != EXPR_T_CMP
+ || a->cmp.symbol != b->cmp.symbol) {
continue;
- } else if (mf_subvalue_intersect(&a->cmp.value, &a->cmp.mask,
- &b->cmp.value, &b->cmp.mask,
- &b->cmp.value, &b->cmp.mask)) {
+ } else if (a->cmp.symbol->width
+ ? mf_subvalue_intersect(&a->cmp.value, &a->cmp.mask,
+ &b->cmp.value, &b->cmp.mask,
+ &b->cmp.value, &b->cmp.mask)
+ : !strcmp(a->cmp.string, b->cmp.string)) {
list_remove(&a->node);
expr_destroy(a);
} else {
diff --git a/tests/ovn.at b/tests/ovn.at
index d1696de..f5d1468 100644
--- a/tests/ovn.at
+++ b/tests/ovn.at
@@ -300,51 +300,99 @@ sed 's/.* => //' test-cases.txt > expout
AT_CHECK([ovstest test-ovn annotate-expr < input.txt], [0], [expout])
AT_CLEANUP
-AT_SETUP([ovn -- expression conversion (1)])
+AT_SETUP([ovn -- 1-term expression conversion])
AT_CHECK([ovstest test-ovn exhaustive --operation=convert 1], [0],
- [Tested converting all 1-terminal expressions with 2 vars each of 3 bits in
terms of operators == != < <= > >=.
+ [Tested converting all 1-terminal expressions with 2 numeric vars (each 3
bits) in terms of operators == != < <= > >= and 2 string vars.
])
AT_CLEANUP
-AT_SETUP([ovn -- expression conversion (2)])
+AT_SETUP([ovn -- 2-term expression conversion])
AT_CHECK([ovstest test-ovn exhaustive --operation=convert 2], [0],
- [Tested converting 562 expressions of 2 terminals with 2 vars each of 3 bits
in terms of operators == != < <= > >=.
+ [Tested converting 570 expressions of 2 terminals with 2 numeric vars (each
3 bits) in terms of operators == != < <= > >= and 2 string vars.
])
AT_CLEANUP
-AT_SETUP([ovn -- expression conversion (3)])
+AT_SETUP([ovn -- 3-term expression conversion])
AT_CHECK([ovstest test-ovn exhaustive --operation=convert --bits=2 3], [0],
- [Tested converting 57618 expressions of 3 terminals with 2 vars each of 2
bits in terms of operators == != < <= > >=.
+ [Tested converting 62418 expressions of 3 terminals with 2 numeric vars
(each 2 bits) in terms of operators == != < <= > >= and 2 string vars.
])
AT_CLEANUP
-AT_SETUP([ovn -- expression simplification])
-AT_CHECK([ovstest test-ovn exhaustive --operation=simplify --vars=2 3], [0],
- [Tested simplifying 477138 expressions of 3 terminals with 2 vars each of 3
bits in terms of operators == != < <= > >=.
+AT_SETUP([ovn -- 3-term numeric expression simplification])
+AT_CHECK([ovstest test-ovn exhaustive --operation=simplify --nvars=2 --svars=0
3], [0],
+ [Tested simplifying 477138 expressions of 3 terminals with 2 numeric vars
(each 3 bits) in terms of operators == != < <= > >=.
])
AT_CLEANUP
-AT_SETUP([ovn -- expression normalization (1)])
-AT_CHECK([ovstest test-ovn exhaustive --operation=normalize --vars=3 --bits=1
4], [0],
- [Tested normalizing 1207162 expressions of 4 terminals with 3 vars each of 1
bits in terms of operators == != < <= > >=.
+AT_SETUP([ovn -- 4-term string expression simplification])
+AT_CHECK([ovstest test-ovn exhaustive --operation=simplify --nvars=0 --svars=4
4], [0],
+ [Tested simplifying 21978 expressions of 4 terminals with 4 string vars.
])
AT_CLEANUP
-AT_SETUP([ovn -- expression normalization (1)])
-AT_CHECK([ovstest test-ovn exhaustive --operation=normalize --vars=3 --bits=1
--relops='==' 5], [0],
- [Tested normalizing 368550 expressions of 5 terminals with 3 vars each of 1
bits in terms of operators ==.
+AT_SETUP([ovn -- 3-term mixed expression simplification])
+AT_CHECK([ovstest test-ovn exhaustive --operation=simplify --nvars=1 --svars=1
3], [0],
+ [Tested simplifying 124410 expressions of 3 terminals with 1 numeric vars
(each 3 bits) in terms of operators == != < <= > >= and 1 string vars.
])
AT_CLEANUP
-AT_SETUP([ovn -- converting expressions to flows (1)])
-AT_CHECK([ovstest test-ovn exhaustive --operation=flow --vars=2 --bits=2
--relops='==' 4], [0],
- [Tested converting to flows 128282 expressions of 4 terminals with 2 vars
each of 2 bits in terms of operators ==.
+AT_SETUP([ovn -- 4-term numeric expression normalization])
+AT_CHECK([ovstest test-ovn exhaustive --operation=normalize --nvars=3
--svars=0 --bits=1 4], [0],
+ [Tested normalizing 1207162 expressions of 4 terminals with 3 numeric vars
(each 1 bits) in terms of operators == != < <= > >=.
])
AT_CLEANUP
-AT_SETUP([ovn -- converting expressions to flows (2)])
-AT_CHECK([ovstest test-ovn exhaustive --operation=flow --vars=3 --bits=3
--relops='==' 3], [0],
- [Tested converting to flows 38394 expressions of 3 terminals with 3 vars
each of 3 bits in terms of operators ==.
+AT_SETUP([ovn -- 4-term string expression normalization])
+AT_CHECK([ovstest test-ovn exhaustive --operation=normalize --nvars=0
--svars=3 --bits=1 4], [0],
+ [Tested normalizing 11242 expressions of 4 terminals with 3 string vars.
+])
+AT_CLEANUP
+
+AT_SETUP([ovn -- 4-term mixed expression normalization])
+AT_CHECK([ovstest test-ovn exhaustive --operation=normalize --nvars=1 --bits=1
--svars=2 4], [0],
+ [Tested normalizing 128282 expressions of 4 terminals with 1 numeric vars
(each 1 bits) in terms of operators == != < <= > >= and 2 string vars.
+])
+AT_CLEANUP
+
+AT_SETUP([ovn -- 5-term numeric expression normalization])
+AT_CHECK([ovstest test-ovn exhaustive --operation=normalize --nvars=3
--svars=0 --bits=1 --relops='==' 5], [0],
+ [Tested normalizing 368550 expressions of 5 terminals with 3 numeric vars
(each 1 bits) in terms of operators ==.
+])
+AT_CLEANUP
+
+AT_SETUP([ovn -- 5-term string expression normalization])
+AT_CHECK([ovstest test-ovn exhaustive --operation=normalize --nvars=0
--svars=3 --bits=1 --relops='==' 5], [0],
+ [Tested normalizing 368550 expressions of 5 terminals with 3 string vars.
+])
+AT_CLEANUP
+
+AT_SETUP([ovn -- 5-term mixed expression normalization])
+AT_CHECK([ovstest test-ovn exhaustive --operation=normalize --nvars=1
--svars=1 --bits=1 --relops='==' 5], [0],
+ [Tested normalizing 116550 expressions of 5 terminals with 1 numeric vars
(each 1 bits) in terms of operators == and 1 string vars.
+])
+AT_CLEANUP
+
+AT_SETUP([ovn -- 4-term numeric expressions to flows])
+AT_CHECK([ovstest test-ovn exhaustive --operation=flow --nvars=2 --svars=0
--bits=2 --relops='==' 4], [0],
+ [Tested converting to flows 128282 expressions of 4 terminals with 2 numeric
vars (each 2 bits) in terms of operators ==.
+])
+AT_CLEANUP
+
+AT_SETUP([ovn -- 4-term string expressions to flows])
+AT_CHECK([ovstest test-ovn exhaustive --operation=flow --nvars=0 --svars=4 4],
[0],
+ [Tested converting to flows 21978 expressions of 4 terminals with 4 string
vars.
+])
+AT_CLEANUP
+
+AT_SETUP([ovn -- 4-term mixed expressions to flows])
+AT_CHECK([ovstest test-ovn exhaustive --operation=flow --nvars=1 --bits=2
--svars=1 --relops='==' 4], [0],
+ [Tested converting to flows 37994 expressions of 4 terminals with 1 numeric
vars (each 2 bits) in terms of operators == and 1 string vars.
+])
+AT_CLEANUP
+
+AT_SETUP([ovn -- 3-term numeric expressions to flows])
+AT_CHECK([ovstest test-ovn exhaustive --operation=flow --nvars=3 --svars=0
--bits=3 --relops='==' 3], [0],
+ [Tested converting to flows 38394 expressions of 3 terminals with 3 numeric
vars (each 3 bits) in terms of operators ==.
])
AT_CLEANUP
@@ -379,6 +427,9 @@ ip,reg6=0x6
ipv6,reg6=0x5
ipv6,reg6=0x6
])
+AT_CHECK([expr_to_flow 'inport == "eth0" && inport == "eth1"'], [0], [dnl
+(no flows)
+])
AT_CLEANUP
AT_SETUP([ovn -- action parsing])
diff --git a/tests/test-ovn.c b/tests/test-ovn.c
index 60b87de..ecb3b5c 100644
--- a/tests/test-ovn.c
+++ b/tests/test-ovn.c
@@ -37,8 +37,11 @@
/* --relops: Bitmap of the relational operators to test, in exhaustive test. */
static unsigned int test_relops;
-/* --vars: Number of variables to test, in exhaustive test. */
-static int test_vars = 2;
+/* --nvars: Number of numeric variables to test, in exhaustive test. */
+static int test_nvars = 2;
+
+/* --svars: Number of string variables to test, in exhaustive test. */
+static int test_svars = 2;
/* --bits: Number of bits per variable, in exhaustive test. */
static int test_bits = 3;
@@ -343,37 +346,45 @@ evaluate_andor_expr(const struct expr *expr, unsigned int
subst, int n_bits,
static bool
evaluate_cmp_expr(const struct expr *expr, unsigned int subst, int n_bits)
{
- int var_idx = expr->cmp.symbol->name[0] - 'a';
- 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;
+ 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);
- case EXPR_R_NE:
- return arg1 != arg2;
+ ovs_assert(!(mask & ~var_mask));
+ ovs_assert(!(arg2 & ~var_mask));
+ ovs_assert(!(arg2 & ~mask));
- case EXPR_R_LT:
- return arg1 < arg2;
+ arg1 &= mask;
+ switch (expr->cmp.relop) {
+ case EXPR_R_EQ:
+ return arg1 == arg2;
- case EXPR_R_LE:
- return arg1 <= arg2;
+ case EXPR_R_NE:
+ return arg1 != arg2;
- case EXPR_R_GT:
- return arg1 > arg2;
+ case EXPR_R_LT:
+ return arg1 < arg2;
- case EXPR_R_GE:
- return arg1 >= arg2;
+ case EXPR_R_LE:
+ return arg1 <= arg2;
- default:
+ 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();
}
}
@@ -678,15 +689,31 @@ test_tree_shape(struct ovs_cmdl_context *ctx)
/* Sets 'expr' to the first possible terminal expression. 'var' should be the
* first variable in the ones to be tested. */
static void
-init_terminal(struct expr *expr, const struct expr_symbol *var)
+init_terminal(struct expr *expr, int phase,
+ const struct expr_symbol *nvars[], int n_nvars,
+ const struct expr_symbol *svars[], int n_svars)
{
- expr->type = EXPR_T_CMP;
- expr->cmp.symbol = var;
- expr->cmp.relop = rightmost_1bit_idx(test_relops);
- memset(&expr->cmp.value, 0, sizeof expr->cmp.value);
- memset(&expr->cmp.mask, 0, sizeof expr->cmp.mask);
- expr->cmp.value.integer = htonll(0);
- expr->cmp.mask.integer = htonll(1);
+ if (phase < 1 && n_nvars) {
+ expr->type = EXPR_T_CMP;
+ expr->cmp.symbol = nvars[0];
+ expr->cmp.relop = rightmost_1bit_idx(test_relops);
+ memset(&expr->cmp.value, 0, sizeof expr->cmp.value);
+ memset(&expr->cmp.mask, 0, sizeof expr->cmp.mask);
+ expr->cmp.value.integer = htonll(0);
+ expr->cmp.mask.integer = htonll(1);
+ return;
+ }
+
+ if (phase < 2 && n_svars) {
+ expr->type = EXPR_T_CMP;
+ expr->cmp.symbol = svars[0];
+ expr->cmp.relop = EXPR_R_EQ;
+ expr->cmp.string = xstrdup("0");
+ return;
+ }
+
+ expr->type = EXPR_T_BOOLEAN;
+ expr->boolean = false;
}
/* Returns 'x' with the rightmost contiguous string of 1s changed to 0s,
@@ -722,8 +749,9 @@ next_relop(enum expr_relop relop)
/* Advances 'expr' to the next possible terminal expression within the 'n_vars'
* variables of 'n_bits' bits each in 'vars[]'. */
static bool
-next_terminal(struct expr *expr, const struct expr_symbol *vars[], int n_vars,
- int n_bits)
+next_terminal(struct expr *expr,
+ const struct expr_symbol *nvars[], int n_nvars, int n_bits,
+ const struct expr_symbol *svars[], int n_svars)
{
if (expr->type == EXPR_T_BOOLEAN) {
if (expr->boolean) {
@@ -734,6 +762,21 @@ next_terminal(struct expr *expr, const struct expr_symbol
*vars[], int n_vars,
}
}
+ if (!expr->cmp.symbol->width) {
+ int next_value = atoi(expr->cmp.string) + 1;
+ free(expr->cmp.string);
+ if (next_value > 1) {
+ expr->cmp.symbol = next_var(expr->cmp.symbol, svars, n_svars);
+ if (!expr->cmp.symbol) {
+ init_terminal(expr, 2, nvars, n_nvars, svars, n_svars);
+ return true;
+ }
+ next_value = 0;
+ }
+ expr->cmp.string = xasprintf("%d", next_value);
+ return true;
+ }
+
unsigned int next;
next = (ntohll(expr->cmp.value.integer)
@@ -746,10 +789,9 @@ next_terminal(struct expr *expr, const struct expr_symbol
*vars[], int n_vars,
enum expr_relop old_relop = expr->cmp.relop;
expr->cmp.relop = next_relop(old_relop);
if (expr->cmp.relop <= old_relop) {
- expr->cmp.symbol = next_var(expr->cmp.symbol,vars, n_vars);
+ expr->cmp.symbol = next_var(expr->cmp.symbol, nvars, n_nvars);
if (!expr->cmp.symbol) {
- expr->type = EXPR_T_BOOLEAN;
- expr->boolean = false;
+ init_terminal(expr, 1, nvars, n_nvars, svars, n_svars);
return true;
}
}
@@ -828,14 +870,19 @@ free_rule(struct test_rule *test_rule)
static int
test_tree_shape_exhaustively(struct expr *expr, struct shash *symtab,
struct expr *terminals[], int n_terminals,
- const struct expr_symbol *vars[], int n_vars,
- int n_bits)
+ const struct expr_symbol *nvars[], int n_nvars,
+ 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;
for (int i = 0; i < n_terminals; i++) {
- init_terminal(terminals[i], vars[0]);
+ init_terminal(terminals[i], 0, nvars, n_nvars, svars, n_svars);
}
struct ds s = DS_EMPTY_INITIALIZER;
@@ -845,12 +892,14 @@ 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], vars, n_vars, n_bits)) {
+ if (next_terminal(terminals[i], nvars, n_nvars, n_bits,
+ svars, n_svars)) {
break;
}
- init_terminal(terminals[i], vars[0]);
+ init_terminal(terminals[i], 0, nvars, n_nvars, svars, n_svars);
}
ovs_assert(expr_honors_invariants(expr));
@@ -884,7 +933,7 @@ test_tree_shape_exhaustively(struct expr *expr, struct
shash *symtab,
struct expr_match *m;
struct test_rule *test_rule;
- expr_to_matches(modified, NULL, &matches);
+ expr_to_matches(modified, &string_map, &matches);
classifier_init(&cls, NULL);
HMAP_FOR_EACH (m, hmap_node, &matches) {
@@ -894,7 +943,8 @@ test_tree_shape_exhaustively(struct expr *expr, struct
shash *symtab,
m->conjunctions, m->n);
}
}
- for (int subst = 0; subst < 1 << (n_bits * n_vars); subst++) {
+ 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);
if (actual != expected) {
@@ -910,21 +960,29 @@ test_tree_shape_exhaustively(struct expr *expr, struct
shash *symtab,
"%s evaluates to %d, but %s evaluates to %d, for",
ds_cstr(&expr_s), expected,
ds_cstr(&modified_s), actual);
- for (int i = 0; i < n_vars; i++) {
+ for (int i = 0; i < n_nvars; i++) {
if (i > 0) {
fputs(",", stderr);
}
- fprintf(stderr, " %c = 0x%x", 'a' + i,
+ fprintf(stderr, " n%d = 0x%x", i,
(subst >> (n_bits * i)) & var_mask);
}
+ for (int i = 0; i < n_svars; i++) {
+ fprintf(stderr, ", s%d = \"%d\"", i,
+ (subst >> (n_bits * n_nvars + i)) & 1);
+ }
putc('\n', stderr);
exit(EXIT_FAILURE);
}
if (operation >= OP_FLOW) {
- for (int i = 0; i < n_vars; i++) {
+ 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, CLS_MIN_VERSION,
&f, NULL) != NULL;
if (expected != found) {
@@ -939,13 +997,17 @@ test_tree_shape_exhaustively(struct expr *expr, struct
shash *symtab,
fprintf(stderr,
"%s and %s evaluate to %d, for",
ds_cstr(&expr_s), ds_cstr(&modified_s), expected);
- for (int i = 0; i < n_vars; i++) {
+ for (int i = 0; i < n_nvars; i++) {
if (i > 0) {
fputs(",", stderr);
}
- fprintf(stderr, " %c = 0x%x", 'a' + i,
+ fprintf(stderr, " n%d = 0x%x", i,
(subst >> (n_bits * i)) & var_mask);
}
+ for (int i = 0; i < n_svars; i++) {
+ fprintf(stderr, ", s%d = \"%d\"", i,
+ (subst >> (n_bits * n_nvars + i)) & 1);
+ }
fputs(".\n", stderr);
fprintf(stderr, "Converted to classifier:\n");
@@ -1012,16 +1074,25 @@ test_exhaustive(struct ovs_cmdl_context *ctx OVS_UNUSED)
int n_tses;
struct shash symtab;
- const struct expr_symbol *vars[4];
+ const struct expr_symbol *nvars[4];
+ const struct expr_symbol *svars[4];
- ovs_assert(test_vars <= ARRAY_SIZE(vars));
+ ovs_assert(test_nvars <= ARRAY_SIZE(nvars));
+ ovs_assert(test_svars <= ARRAY_SIZE(svars));
+ ovs_assert(test_nvars + test_svars <= FLOW_N_REGS);
shash_init(&symtab);
- for (int i = 0; i < test_vars; i++) {
- char name[2] = { 'a' + i, '\0' };
-
- vars[i] = expr_symtab_add_field(&symtab, name, MFF_REG0 + i, NULL,
- false);
+ for (int i = 0; i < test_nvars; i++) {
+ char *name = xasprintf("n%d", i);
+ nvars[i] = expr_symtab_add_field(&symtab, name, MFF_REG0 + i, NULL,
+ false);
+ free(name);
+ }
+ for (int i = 0; i < test_svars; i++) {
+ char *name = xasprintf("s%d", i);
+ svars[i] = expr_symtab_add_string(&symtab, name,
+ MFF_REG0 + test_nvars + i, NULL);
+ free(name);
}
#ifndef _WIN32
@@ -1056,7 +1127,8 @@ test_exhaustive(struct ovs_cmdl_context *ctx OVS_UNUSED)
if (!pid) {
test_tree_shape_exhaustively(expr, &symtab,
terminals, n_terminals,
- vars, test_vars, test_bits);
+ nvars, test_nvars, test_bits,
+ svars, test_svars);
expr_destroy(expr);
exit(0);
} else {
@@ -1070,7 +1142,8 @@ test_exhaustive(struct ovs_cmdl_context *ctx OVS_UNUSED)
{
n_tested += test_tree_shape_exhaustively(
expr, &symtab, terminals, n_terminals,
- vars, test_vars, test_bits);
+ nvars, test_nvars, test_bits,
+ svars, test_svars);
}
expr_destroy(expr);
}
@@ -1102,12 +1175,25 @@ test_exhaustive(struct ovs_cmdl_context *ctx OVS_UNUSED)
} else {
printf(" all %d-terminal expressions", n_terminals);
}
- printf(" with %d vars each of %d bits in terms of operators",
- test_vars, test_bits);
- for (unsigned int relops = test_relops; relops;
- relops = zero_rightmost_1bit(relops)) {
- enum expr_relop r = rightmost_1bit_idx(relops);
- printf(" %s", expr_relop_to_string(r));
+ if (test_nvars || test_svars) {
+ printf(" with");
+ if (test_nvars) {
+ printf(" %d numeric vars (each %d bits) in terms of operators",
+ test_nvars, test_bits);
+ for (unsigned int relops = test_relops; relops;
+ relops = zero_rightmost_1bit(relops)) {
+ enum expr_relop r = rightmost_1bit_idx(relops);
+ printf(" %s", expr_relop_to_string(r));
+ }
+ }
+ if (test_nvars && test_svars) {
+ printf (" and");
+ }
+ if (test_svars) {
+ printf(" %d string vars", test_svars);
+ }
+ } else {
+ printf(" in terms of Boolean constants only");
}
printf(".\n");
@@ -1227,15 +1313,19 @@ tree-shape N\n\
exhaustive N\n\
Tests that all possible Boolean expressions with N terminals are properly\n\
simplified, normalized, and converted to flows. Available options:\n\
- --relops=OPERATORS Test only the specified Boolean operators.\n\
- OPERATORS may include == != < <= > >=, space or\n\
- comma separated. Default is all operators.\n\
- --vars=N Number of variables to test, in range 1...4, default 2.\n\
- --bits=N Number of bits per variable, in range 1...3, default 3.\n\
+ Overall options:\n\
--operation=OPERATION Operation to test, one of: convert, simplify,\n\
normalize, flow. Default: flow. 'normalize' includes 'simplify',\n\
- 'flow' includes 'simplify' and 'normaize'.\n\
+ 'flow' includes 'simplify' and 'normalize'.\n\
--parallel=N Number of processes to use in parallel, default 1.\n\
+ Numeric vars:\n\
+ --nvars=N Number of numeric vars to test, in range 0...4, default 2.\n\
+ --bits=N Number of bits per variable, in range 1...3, default 3.\n\
+ --relops=OPERATORS Test only the specified Boolean operators.\n\
+ OPERATORS may include == != < <= > >=, space or\n\
+ comma separated. Default is all operators.\n\
+ String vars:\n\
+ --svars=N Number of string vars to test, in range 0...4, default 2.\n\
",
program_name, program_name);
exit(EXIT_SUCCESS);
@@ -1244,30 +1334,34 @@ exhaustive N\n\
static void
test_ovn_main(int argc, char *argv[])
{
+ enum {
+ OPT_RELOPS = UCHAR_MAX + 1,
+ OPT_NVARS,
+ OPT_SVARS,
+ OPT_BITS,
+ OPT_OPERATION,
+ OPT_PARALLEL
+ };
+ static const struct option long_options[] = {
+ {"relops", required_argument, NULL, OPT_RELOPS},
+ {"nvars", required_argument, NULL, OPT_NVARS},
+ {"svars", required_argument, NULL, OPT_SVARS},
+ {"bits", required_argument, NULL, OPT_BITS},
+ {"operation", required_argument, NULL, OPT_OPERATION},
+ {"parallel", required_argument, NULL, OPT_PARALLEL},
+ {"more", no_argument, NULL, 'm'},
+ {"help", no_argument, NULL, 'h'},
+ {NULL, 0, NULL, 0},
+ };
+ char *short_options = ovs_cmdl_long_options_to_short_options(long_options);
+
set_program_name(argv[0]);
test_relops = parse_relops("== != < <= > >=");
for (;;) {
- enum {
- OPT_RELOPS = UCHAR_MAX + 1,
- OPT_VARS,
- OPT_BITS,
- OPT_OPERATION,
- OPT_PARALLEL
- };
-
- static const struct option options[] = {
- {"relops", required_argument, NULL, OPT_RELOPS},
- {"vars", required_argument, NULL, OPT_VARS},
- {"bits", required_argument, NULL, OPT_BITS},
- {"operation", required_argument, NULL, OPT_OPERATION},
- {"parallel", required_argument, NULL, OPT_PARALLEL},
- {"more", no_argument, NULL, 'm'},
- {"help", no_argument, NULL, 'h'},
- {NULL, 0, NULL, 0},
- };
int option_index = 0;
- int c = getopt_long (argc, argv, "", options, &option_index);
+ int c = getopt_long (argc, argv, short_options, long_options,
+ &option_index);
if (c == -1) {
break;
@@ -1277,10 +1371,19 @@ test_ovn_main(int argc, char *argv[])
test_relops = parse_relops(optarg);
break;
- case OPT_VARS:
- test_vars = atoi(optarg);
- if (test_vars < 1 || test_vars > 4) {
- ovs_fatal(0, "number of variables must be between 1 and 4");
+ case OPT_NVARS:
+ test_nvars = atoi(optarg);
+ if (test_nvars < 0 || test_nvars > 4) {
+ ovs_fatal(0, "number of numeric variables must be "
+ "between 0 and 4");
+ }
+ break;
+
+ case OPT_SVARS:
+ test_svars = atoi(optarg);
+ if (test_svars < 0 || test_svars > 4) {
+ ovs_fatal(0, "number of string variables must be "
+ "between 0 and 4");
}
break;
--
2.1.3
_______________________________________________
dev mailing list
dev@openvswitch.org
http://openvswitch.org/mailman/listinfo/dev
