[ovs-dev] [PATCH v2] expr: Properly handle several cases involving string variables.
Ben Pfaff
blp at nicira.com
Sat Sep 12 03:01:30 UTC 2015
Thanks, I applied this to master.
On Fri, Sep 11, 2015 at 03:56:24PM -0700, Justin Pettit wrote:
> 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