[ovs-dev] [PATCH v2] expr: Properly handle several cases involving string variables.
Justin Pettit
jpettit at nicira.com
Fri Sep 11 22:56:24 UTC 2015
Thanks for fixing the issue and improving the tests.
Acked-by: Justin Pettit <jpettit at nicira.com>
--Justin
> On Aug 29, 2015, at 1:39 PM, Ben Pfaff <blp at nicira.com> wrote:
>
> 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 <jpettit at nicira.com>
> Signed-off-by: Ben Pfaff <blp at 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
>
More information about the dev
mailing list