From e0840f11b05204c318a894df983e7ab20a3597da Mon Sep 17 00:00:00 2001 From: Ben Pfaff Date: Wed, 15 Apr 2015 16:49:50 -0700 Subject: [PATCH] expr: New module for Boolean expressions on fields, for use in OVN. Known weaknesses: * String fields can't be converted to flows yet. A subsequent commit will fix this. * Flows aren't optimal in some situations likely to be common. I don't think either of those is a reason not to commit this; this is a solid base to build on. Signed-off-by: Ben Pfaff Acked-by: Russell Bryant --- ovn/TODO | 25 - ovn/lib/automake.mk | 6 +- ovn/lib/expr.c | 2351 +++++++++++++++++++++++++++++++++++++++++++ ovn/lib/expr.h | 367 +++++++ ovn/ovn-sb.xml | 353 +++++-- tests/ovn.at | 253 +++++ tests/test-ovn.c | 1176 ++++++++++++++++++++++ 7 files changed, 4403 insertions(+), 128 deletions(-) create mode 100644 ovn/lib/expr.c create mode 100644 ovn/lib/expr.h diff --git a/ovn/TODO b/ovn/TODO index f5ff888a9..3b5d97e50 100644 --- a/ovn/TODO +++ b/ovn/TODO @@ -4,31 +4,6 @@ the same syntax and I imagine the same code ought to be useful in ovn-nbd for ACL match expressions. -** Definition of data structures to represent a match expression as a - syntax tree. - -** Definition of data structures to represent variables (fields). - - Fields need names and prerequisites. Most fields are numeric and - thus need widths. We need also need a way to represent nominal - fields (currently just logical port names). It might be - appropriate to associate fields directly with OXM/NXM code points; - we have to decide whether we want OVN to use the OVS flow structure - or work with OXM more directly. - - Probably should be defined so that the data structure is also - useful for references to fields in action parsing. - -** Parsing into syntax tree. - -** Semantic checking against variable definitions. - -** Applying prerequisites. - -** Simplification into conjunction-of-disjunctions (CoD) form. - -** Transformation from CoD form into OXM matches. - * ovn-controller ** Flow table handling in ovn-controller. diff --git a/ovn/lib/automake.mk b/ovn/lib/automake.mk index 9b5351d1e..91a4fe871 100644 --- a/ovn/lib/automake.mk +++ b/ovn/lib/automake.mk @@ -1,2 +1,6 @@ lib_LTLIBRARIES += ovn/lib/libovn.la -ovn_lib_libovn_la_SOURCES = ovn/lib/lex.c ovn/lib/lex.h +ovn_lib_libovn_la_SOURCES = \ + ovn/lib/expr.c \ + ovn/lib/expr.h \ + ovn/lib/lex.c \ + ovn/lib/lex.h diff --git a/ovn/lib/expr.c b/ovn/lib/expr.c new file mode 100644 index 000000000..e648dbd1b --- /dev/null +++ b/ovn/lib/expr.c @@ -0,0 +1,2351 @@ +/* + * Copyright (c) 2015 Nicira, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include +#include "expr.h" +#include "dynamic-string.h" +#include "json.h" +#include "lex.h" +#include "match.h" +#include "shash.h" +#include "openvswitch/vlog.h" + +VLOG_DEFINE_THIS_MODULE(expr); + +/* Returns the name of measurement level 'level'. */ +const char * +expr_level_to_string(enum expr_level level) +{ + switch (level) { + case EXPR_L_NOMINAL: return "nominal"; + case EXPR_L_BOOLEAN: return "Boolean"; + case EXPR_L_ORDINAL: return "ordinal"; + default: OVS_NOT_REACHED(); + } +} + +/* Relational operators. */ + +/* Returns a string form of relational operator 'relop'. */ +const char * +expr_relop_to_string(enum expr_relop relop) +{ + switch (relop) { + case EXPR_R_EQ: return "=="; + case EXPR_R_NE: return "!="; + case EXPR_R_LT: return "<"; + case EXPR_R_LE: return "<="; + case EXPR_R_GT: return ">"; + case EXPR_R_GE: return ">="; + default: OVS_NOT_REACHED(); + } +} + +bool +expr_relop_from_token(enum lex_type type, enum expr_relop *relop) +{ + enum expr_relop r; + + switch ((int) type) { + case LEX_T_EQ: r = EXPR_R_EQ; break; + case LEX_T_NE: r = EXPR_R_NE; break; + case LEX_T_LT: r = EXPR_R_LT; break; + case LEX_T_LE: r = EXPR_R_LE; break; + case LEX_T_GT: r = EXPR_R_GT; break; + case LEX_T_GE: r = EXPR_R_GE; break; + default: return false; + } + + if (relop) { + *relop = r; + } + return true; +} + +/* Returns the relational operator that 'relop' becomes if you turn the + * relation's operands around, e.g. EXPR_R_EQ does not change because "a == b" + * and "b == a" are equivalent, but EXPR_R_LE becomes EXPR_R_GE because "a <= + * b" is equivalent to "b >= a". */ +static enum expr_relop +expr_relop_turn(enum expr_relop relop) +{ + switch (relop) { + case EXPR_R_EQ: return EXPR_R_EQ; + case EXPR_R_NE: return EXPR_R_NE; + case EXPR_R_LT: return EXPR_R_GT; + case EXPR_R_LE: return EXPR_R_GE; + case EXPR_R_GT: return EXPR_R_LT; + case EXPR_R_GE: return EXPR_R_LE; + default: OVS_NOT_REACHED(); + } +} + +/* Returns the relational operator that is the opposite of 'relop'. */ +static enum expr_relop +expr_relop_invert(enum expr_relop relop) +{ + switch (relop) { + case EXPR_R_EQ: return EXPR_R_NE; + case EXPR_R_NE: return EXPR_R_EQ; + case EXPR_R_LT: return EXPR_R_GE; + case EXPR_R_LE: return EXPR_R_GT; + case EXPR_R_GT: return EXPR_R_LE; + case EXPR_R_GE: return EXPR_R_LT; + default: OVS_NOT_REACHED(); + } +} + +/* Constructing and manipulating expressions. */ + +/* Creates and returns a logical AND or OR expression (according to 'type', + * which must be EXPR_T_AND or EXPR_T_OR) that initially has no + * sub-expressions. (To satisfy the invariants for expressions, the caller + * must add at least two sub-expressions whose types are different from + * 'type'.) */ +struct expr * +expr_create_andor(enum expr_type type) +{ + struct expr *e = xmalloc(sizeof *e); + e->type = type; + list_init(&e->andor); + return e; +} + +/* Returns a logical AND or OR expression (according to 'type', which must be + * EXPR_T_AND or EXPR_T_OR) whose sub-expressions are 'a' and 'b', with some + * flexibility: + * + * - If 'a' or 'b' is NULL, just returns the other one (which means that if + * that other one is not of the given 'type', then the returned + * expression is not either). + * + * - If 'a' or 'b', or both, have type 'type', then they are combined into + * a single node that satisfies the invariants for expressions. */ +struct expr * +expr_combine(enum expr_type type, struct expr *a, struct expr *b) +{ + if (!a) { + return b; + } else if (!b) { + return a; + } else if (a->type == type) { + if (b->type == type) { + list_splice(&a->andor, b->andor.next, &b->andor); + free(b); + } else { + list_push_back(&a->andor, &b->node); + } + return a; + } else if (b->type == type) { + list_push_front(&b->andor, &a->node); + return b; + } else { + struct expr *e = expr_create_andor(type); + list_push_back(&e->andor, &a->node); + list_push_back(&e->andor, &b->node); + return e; + } +} + +static void +expr_insert_andor(struct expr *andor, struct expr *before, struct expr *new) +{ + if (new->type == andor->type) { + if (andor->type == EXPR_T_AND) { + /* Conjunction junction, what's your function? */ + } + list_splice(&before->node, new->andor.next, &new->andor); + free(new); + } else { + list_insert(&before->node, &new->node); + } +} + +/* Returns an EXPR_T_BOOLEAN expression with value 'b'. */ +struct expr * +expr_create_boolean(bool b) +{ + struct expr *e = xmalloc(sizeof *e); + e->type = EXPR_T_BOOLEAN; + e->boolean = b; + return e; +} + +static void +expr_not(struct expr *expr) +{ + struct expr *sub; + + switch (expr->type) { + case EXPR_T_CMP: + expr->cmp.relop = expr_relop_invert(expr->cmp.relop); + break; + + case EXPR_T_AND: + case EXPR_T_OR: + LIST_FOR_EACH (sub, node, &expr->andor) { + expr_not(sub); + } + expr->type = expr->type == EXPR_T_AND ? EXPR_T_OR : EXPR_T_AND; + break; + + case EXPR_T_BOOLEAN: + expr->boolean = !expr->boolean; + break; + default: + OVS_NOT_REACHED(); + } +} + +static struct expr * +expr_fix_andor(struct expr *expr, bool short_circuit) +{ + struct expr *sub, *next; + + LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) { + if (sub->type == EXPR_T_BOOLEAN) { + if (sub->boolean == short_circuit) { + expr_destroy(expr); + return expr_create_boolean(short_circuit); + } else { + list_remove(&sub->node); + expr_destroy(sub); + } + } + } + + if (list_is_short(&expr->andor)) { + if (list_is_empty(&expr->andor)) { + free(expr); + return expr_create_boolean(!short_circuit); + } else { + sub = expr_from_node(list_front(&expr->andor)); + free(expr); + return sub; + } + } else { + return expr; + } +} + +static struct expr * +expr_fix(struct expr *expr) +{ + switch (expr->type) { + case EXPR_T_CMP: + return expr; + + case EXPR_T_AND: + return expr_fix_andor(expr, false); + + case EXPR_T_OR: + return expr_fix_andor(expr, true); + + case EXPR_T_BOOLEAN: + return expr; + + default: + OVS_NOT_REACHED(); + } +} + +/* Formatting. */ + +static void +find_bitwise_range(const union mf_subvalue *sv, int width, + int *startp, int *n_bitsp) +{ + unsigned int start = bitwise_scan(sv, sizeof *sv, true, 0, width); + if (start < width) { + unsigned int end = bitwise_scan(sv, sizeof *sv, false, start, width); + if (end >= width + || bitwise_scan(sv, sizeof *sv, true, end, width) >= width) { + *startp = start; + *n_bitsp = end - start; + return; + } + } + *startp = *n_bitsp = 0; +} + +static void +expr_format_string(const char *s, struct ds *ds) +{ + struct json json = { + .type = JSON_STRING, + .u.string = CONST_CAST(char *, s), + }; + json_to_ds(&json, 0, ds); +} + +static void +expr_format_cmp(const struct expr *e, struct ds *s) +{ + /* The common case is numerical comparisons. + * Handle string comparisons as a special case. */ + if (!e->cmp.symbol->width) { + ds_put_format(s, "%s %s ", e->cmp.symbol->name, + expr_relop_to_string(e->cmp.relop)); + expr_format_string(e->cmp.string, s); + return; + } + + int ofs, n; + find_bitwise_range(&e->cmp.mask, e->cmp.symbol->width, &ofs, &n); + if (n == 1 && (e->cmp.relop == EXPR_R_EQ || e->cmp.relop == EXPR_R_NE)) { + bool positive; + + positive = bitwise_get_bit(&e->cmp.value, sizeof e->cmp.value, ofs); + positive ^= e->cmp.relop == EXPR_R_NE; + if (!positive) { + ds_put_char(s, '!'); + } + ds_put_cstr(s, e->cmp.symbol->name); + if (e->cmp.symbol->width > 1) { + ds_put_format(s, "[%d]", ofs); + } + return; + } + + ds_put_cstr(s, e->cmp.symbol->name); + if (n > 0 && n < e->cmp.symbol->width) { + if (n > 1) { + ds_put_format(s, "[%d..%d]", ofs, ofs + n - 1); + } else { + ds_put_format(s, "[%d]", ofs); + } + } + + ds_put_format(s, " %s ", expr_relop_to_string(e->cmp.relop)); + + if (n) { + union mf_subvalue value; + + memset(&value, 0, sizeof value); + bitwise_copy(&e->cmp.value, sizeof e->cmp.value, ofs, + &value, sizeof value, 0, + n); + mf_format_subvalue(&value, s); + } else { + mf_format_subvalue(&e->cmp.value, s); + ds_put_char(s, '/'); + mf_format_subvalue(&e->cmp.mask, s); + } +} + +static void +expr_format_andor(const struct expr *e, const char *op, struct ds *s) +{ + struct expr *sub; + int i = 0; + + LIST_FOR_EACH (sub, node, &e->andor) { + if (i++) { + ds_put_format(s, " %s ", op); + } + + if (sub->type == EXPR_T_AND || sub->type == EXPR_T_OR) { + ds_put_char(s, '('); + expr_format(sub, s); + ds_put_char(s, ')'); + } else { + expr_format(sub, s); + } + } +} + +/* Appends a string form of 'e' to 's'. The string form is acceptable for + * parsing back into an equivalent expression. */ +void +expr_format(const struct expr *e, struct ds *s) +{ + switch (e->type) { + case EXPR_T_CMP: + expr_format_cmp(e, s); + break; + + case EXPR_T_AND: + expr_format_andor(e, "&&", s); + break; + + case EXPR_T_OR: + expr_format_andor(e, "||", s); + break; + + case EXPR_T_BOOLEAN: + ds_put_char(s, e->boolean ? '1' : '0'); + break; + } +} + +/* Prints a string form of 'e' on stdout, followed by a new-line. */ +void +expr_print(const struct expr *e) +{ + struct ds output; + + ds_init(&output); + expr_format(e, &output); + puts(ds_cstr(&output)); + ds_destroy(&output); +} + +/* Parsing. */ + +/* Type of a "union expr_constant" or "struct expr_constant_set". */ +enum expr_constant_type { + EXPR_C_INTEGER, + EXPR_C_STRING +}; + +/* A string or integer constant (one must know which from context). */ +union expr_constant { + /* Integer constant. + * + * The width of a constant isn't always clear, e.g. if you write "1", + * there's no way to tell whether you mean for that to be a 1-bit constant + * or a 128-bit constant or somewhere in between. */ + struct { + union mf_subvalue value; + union mf_subvalue mask; /* Only initialized if 'masked'. */ + bool masked; + + enum lex_format format; /* From the constant's lex_token. */ + }; + + /* Null-terminated string constant. */ + char *string; +}; + +/* A collection of "union expr_constant"s of the same type. */ +struct expr_constant_set { + union expr_constant *values; /* Constants. */ + size_t n_values; /* Number of constants. */ + enum expr_constant_type type; /* Type of the constants. */ + bool in_curlies; /* Whether the constants were in {}. */ +}; + +/* A reference to a symbol or a subfield of a symbol. + * + * For string fields, ofs and n_bits are 0. */ +struct expr_field { + const struct expr_symbol *symbol; /* The symbol. */ + int ofs; /* Starting bit offset. */ + int n_bits; /* Number of bits. */ +}; + +/* Context maintained during expr_parse(). */ +struct expr_context { + struct lexer *lexer; /* Lexer for pulling more tokens. */ + const struct shash *symtab; /* Symbol table. */ + char *error; /* Error, if any, otherwise NULL. */ + bool not; /* True inside odd number of NOT operators. */ +}; + +struct expr *expr_parse__(struct expr_context *); +static void expr_not(struct expr *); +static void expr_constant_set_destroy(struct expr_constant_set *); +static bool parse_field(struct expr_context *, struct expr_field *); + +static bool +expr_error_handle_common(struct expr_context *ctx) +{ + if (ctx->error) { + /* Already have an error, suppress this one since the cascade seems + * unlikely to be useful. */ + return true; + } else if (ctx->lexer->token.type == LEX_T_ERROR) { + /* The lexer signaled an error. Nothing at the expression level + * accepts an error token, so we'll inevitably end up here with some + * meaningless parse error. Report the lexical error instead. */ + ctx->error = xstrdup(ctx->lexer->token.s); + return true; + } else { + return false; + } +} + +static void OVS_PRINTF_FORMAT(2, 3) +expr_error(struct expr_context *ctx, const char *message, ...) +{ + if (expr_error_handle_common(ctx)) { + return; + } + + va_list args; + va_start(args, message); + ctx->error = xvasprintf(message, args); + va_end(args); +} + +static void OVS_PRINTF_FORMAT(2, 3) +expr_syntax_error(struct expr_context *ctx, const char *message, ...) +{ + if (expr_error_handle_common(ctx)) { + return; + } + + struct ds s; + + ds_init(&s); + ds_put_cstr(&s, "Syntax error "); + if (ctx->lexer->token.type == LEX_T_END) { + ds_put_cstr(&s, "at end of input "); + } else if (ctx->lexer->start) { + ds_put_format(&s, "at `%.*s' ", + (int) (ctx->lexer->input - ctx->lexer->start), + ctx->lexer->start); + } + + va_list args; + va_start(args, message); + ds_put_format_valist(&s, message, args); + va_end(args); + + ctx->error = ds_steal_cstr(&s); +} + +static struct expr * +make_cmp__(const struct expr_field *f, enum expr_relop r, + const union expr_constant *c) +{ + struct expr *e = xzalloc(sizeof *e); + e->type = EXPR_T_CMP; + e->cmp.symbol = f->symbol; + e->cmp.relop = r; + if (f->symbol->width) { + bitwise_copy(&c->value, sizeof c->value, 0, + &e->cmp.value, sizeof e->cmp.value, f->ofs, + f->n_bits); + if (c->masked) { + bitwise_copy(&c->mask, sizeof c->mask, 0, + &e->cmp.mask, sizeof e->cmp.mask, f->ofs, + f->n_bits); + } else { + bitwise_one(&e->cmp.mask, sizeof e->cmp.mask, f->ofs, + f->n_bits); + } + } else { + e->cmp.string = xstrdup(c->string); + } + return e; +} + +/* Returns the minimum reasonable width for integer constant 'c'. */ +static int +expr_constant_width(const union expr_constant *c) +{ + if (c->masked) { + return mf_subvalue_width(&c->mask); + } + + switch (c->format) { + case LEX_F_DECIMAL: + case LEX_F_HEXADECIMAL: + return mf_subvalue_width(&c->value); + + case LEX_F_IPV4: + return 32; + + case LEX_F_IPV6: + return 128; + + case LEX_F_ETHERNET: + return 48; + + default: + OVS_NOT_REACHED(); + } +} + +static struct expr * +make_cmp(struct expr_context *ctx, + const struct expr_field *f, enum expr_relop r, + struct expr_constant_set *cs) +{ + struct expr *e = NULL; + + if (cs->type != (f->symbol->width ? EXPR_C_INTEGER : EXPR_C_STRING)) { + expr_error(ctx, "Can't compare %s field %s to %s constant.", + f->symbol->width ? "integer" : "string", + f->symbol->name, + cs->type == EXPR_C_INTEGER ? "integer" : "string"); + goto exit; + } + + if (r != EXPR_R_EQ && r != EXPR_R_NE) { + if (cs->in_curlies) { + expr_error(ctx, "Only == and != operators may be used " + "with value sets."); + goto exit; + } + if (f->symbol->level == EXPR_L_NOMINAL || + f->symbol->level == EXPR_L_BOOLEAN) { + expr_error(ctx, "Only == and != operators may be used " + "with %s field %s.", + expr_level_to_string(f->symbol->level), + f->symbol->name); + goto exit; + } + if (cs->values[0].masked) { + expr_error(ctx, "Only == and != operators may be used with " + "masked constants. Consider using subfields instead " + "(e.g. eth.src[0..15] > 0x1111 in place of " + "eth.src > 00:00:00:00:11:11/00:00:00:00:ff:ff)."); + goto exit; + } + } + + if (f->symbol->level == EXPR_L_NOMINAL) { + if (f->symbol->expansion) { + for (size_t i = 0; i < cs->n_values; i++) { + const union mf_subvalue *value = &cs->values[i].value; + bool positive = (value->integer & htonll(1)) != 0; + positive ^= r == EXPR_R_NE; + positive ^= ctx->not; + if (!positive) { + const char *name = f->symbol->name; + expr_error(ctx, "Nominal predicate %s may only be tested " + "positively, e.g. `%s' or `%s == 1' but not " + "`!%s' or `%s == 0'.", + name, name, name, name, name); + goto exit; + } + } + } else if (r != (ctx->not ? EXPR_R_NE : EXPR_R_EQ)) { + expr_error(ctx, "Nominal field %s may only be tested for " + "equality (taking enclosing `!' operators into " + "account).", f->symbol->name); + goto exit; + } + } + + if (f->symbol->width) { + for (size_t i = 0; i < cs->n_values; i++) { + int w = expr_constant_width(&cs->values[i]); + if (w > f->symbol->width) { + expr_error(ctx, "Cannot compare %d-bit constant against " + "%d-bit field %s.", + w, f->symbol->width, f->symbol->name); + goto exit; + } + } + } + + e = make_cmp__(f, r, &cs->values[0]); + for (size_t i = 1; i < cs->n_values; i++) { + e = expr_combine(r == EXPR_R_EQ ? EXPR_T_OR : EXPR_T_AND, + e, make_cmp__(f, r, &cs->values[i])); + } +exit: + expr_constant_set_destroy(cs); + return e; +} + +static bool +expr_get_int(struct expr_context *ctx, int *value) +{ + if (ctx->lexer->token.type == LEX_T_INTEGER + && ctx->lexer->token.format == LEX_F_DECIMAL + && ntohll(ctx->lexer->token.value.integer) <= INT_MAX) { + *value = ntohll(ctx->lexer->token.value.integer); + lexer_get(ctx->lexer); + return true; + } else { + expr_syntax_error(ctx, "expecting small integer."); + return false; + } +} + +static bool +parse_field(struct expr_context *ctx, struct expr_field *f) +{ + const struct expr_symbol *symbol; + + if (ctx->lexer->token.type != LEX_T_ID) { + expr_syntax_error(ctx, "expecting field name."); + return false; + } + + symbol = shash_find_data(ctx->symtab, ctx->lexer->token.s); + if (!symbol) { + expr_syntax_error(ctx, "expecting field name."); + return false; + } + lexer_get(ctx->lexer); + + f->symbol = symbol; + if (lexer_match(ctx->lexer, LEX_T_LSQUARE)) { + int low, high; + + if (!symbol->width) { + expr_error(ctx, "Cannot select subfield of string field %s.", + symbol->name); + return false; + } + + if (!expr_get_int(ctx, &low)) { + return false; + } + if (lexer_match(ctx->lexer, LEX_T_ELLIPSIS)) { + if (!expr_get_int(ctx, &high)) { + return false; + } + } else { + high = low; + } + + if (!lexer_match(ctx->lexer, LEX_T_RSQUARE)) { + expr_syntax_error(ctx, "expecting `]'."); + return false; + } + + if (low > high) { + expr_error(ctx, "Invalid bit range %d to %d.", low, high); + return false; + } else if (high >= symbol->width) { + expr_error(ctx, "Cannot select bits %d to %d of %d-bit field %s.", + low, high, symbol->width, symbol->name); + return false; + } else if (symbol->level == EXPR_L_NOMINAL + && (low != 0 || high != symbol->width - 1)) { + expr_error(ctx, "Cannot select subfield of nominal field %s.", + symbol->name); + return false; + } + + f->ofs = low; + f->n_bits = high - low + 1; + } else { + f->ofs = 0; + f->n_bits = symbol->width; + } + + return true; +} + +static bool +parse_relop(struct expr_context *ctx, enum expr_relop *relop) +{ + if (expr_relop_from_token(ctx->lexer->token.type, relop)) { + lexer_get(ctx->lexer); + return true; + } else { + expr_syntax_error(ctx, "expecting relational operator."); + return false; + } +} + +static bool +assign_constant_set_type(struct expr_context *ctx, + struct expr_constant_set *cs, + enum expr_constant_type type) +{ + if (!cs->n_values || cs->type == type) { + cs->type = type; + return true; + } else { + expr_syntax_error(ctx, "expecting %s.", + cs->type == EXPR_C_INTEGER ? "integer" : "string"); + return false; + } +} + +static bool +parse_constant(struct expr_context *ctx, struct expr_constant_set *cs, + size_t *allocated_values) +{ + if (cs->n_values >= *allocated_values) { + cs->values = x2nrealloc(cs->values, allocated_values, + sizeof *cs->values); + } + + if (ctx->lexer->token.type == LEX_T_STRING) { + if (!assign_constant_set_type(ctx, cs, EXPR_C_STRING)) { + return false; + } + cs->values[cs->n_values++].string = xstrdup(ctx->lexer->token.s); + lexer_get(ctx->lexer); + return true; + } else if (ctx->lexer->token.type == LEX_T_INTEGER || + ctx->lexer->token.type == LEX_T_MASKED_INTEGER) { + if (!assign_constant_set_type(ctx, cs, EXPR_C_INTEGER)) { + return false; + } + + union expr_constant *c = &cs->values[cs->n_values++]; + c->value = ctx->lexer->token.value; + c->format = ctx->lexer->token.format; + c->masked = ctx->lexer->token.type == LEX_T_MASKED_INTEGER; + if (c->masked) { + c->mask = ctx->lexer->token.mask; + } + lexer_get(ctx->lexer); + return true; + } else { + expr_syntax_error(ctx, "expecting constant."); + return false; + } +} + +/* Parses a single or {}-enclosed set of integer or string constants into 'cs', + * which the caller need not have initialized. Returns true on success, in + * which case the caller owns 'cs', false on failure, in which case 'cs' is + * indeterminate. */ +static bool +parse_constant_set(struct expr_context *ctx, struct expr_constant_set *cs) +{ + size_t allocated_values = 0; + bool ok; + + memset(cs, 0, sizeof *cs); + if (lexer_match(ctx->lexer, LEX_T_LCURLY)) { + ok = true; + cs->in_curlies = true; + do { + if (!parse_constant(ctx, cs, &allocated_values)) { + ok = false; + break; + } + lexer_match(ctx->lexer, LEX_T_COMMA); + } while (!lexer_match(ctx->lexer, LEX_T_RCURLY)); + } else { + ok = parse_constant(ctx, cs, &allocated_values); + } + if (!ok) { + expr_constant_set_destroy(cs); + } + return ok; +} + +static void +expr_constant_set_destroy(struct expr_constant_set *cs) +{ + if (cs) { + if (cs->type == EXPR_C_STRING) { + for (size_t i = 0; i < cs->n_values; i++) { + free(cs->values[i].string); + } + } + free(cs->values); + } +} + +static struct expr * +expr_parse_primary(struct expr_context *ctx, bool *atomic) +{ + *atomic = false; + if (lexer_match(ctx->lexer, LEX_T_LPAREN)) { + struct expr *e = expr_parse__(ctx); + if (!lexer_match(ctx->lexer, LEX_T_RPAREN)) { + expr_destroy(e); + expr_syntax_error(ctx, "expecting `)'."); + return NULL; + } + *atomic = true; + return e; + } + + if (ctx->lexer->token.type == LEX_T_ID) { + struct expr_field f; + enum expr_relop r; + struct expr_constant_set c; + + if (!parse_field(ctx, &f)) { + return NULL; + } + + if (!expr_relop_from_token(ctx->lexer->token.type, &r)) { + if (f.n_bits > 1 && !ctx->not) { + expr_error(ctx, "Explicit `!= 0' is required for inequality " + "test of multibit field against 0."); + return NULL; + } + + *atomic = true; + + union expr_constant *cst = xzalloc(sizeof *cst); + cst->format = LEX_F_HEXADECIMAL; + cst->masked = false; + + c.type = EXPR_C_INTEGER; + c.values = cst; + c.n_values = 1; + c.in_curlies = false; + return make_cmp(ctx, &f, EXPR_R_NE, &c); + } else if (parse_relop(ctx, &r) && parse_constant_set(ctx, &c)) { + return make_cmp(ctx, &f, r, &c); + } else { + return NULL; + } + } else { + struct expr_constant_set c1; + if (!parse_constant_set(ctx, &c1)) { + return NULL; + } + + if (!expr_relop_from_token(ctx->lexer->token.type, NULL) + && c1.n_values == 1 + && c1.type == EXPR_C_INTEGER + && c1.values[0].format == LEX_F_DECIMAL + && !c1.values[0].masked + && !c1.in_curlies) { + uint64_t x = ntohll(c1.values[0].value.integer); + if (x <= 1) { + *atomic = true; + expr_constant_set_destroy(&c1); + return expr_create_boolean(x); + } + } + + enum expr_relop r1; + struct expr_field f; + if (!parse_relop(ctx, &r1) || !parse_field(ctx, &f)) { + expr_constant_set_destroy(&c1); + return NULL; + } + + if (!expr_relop_from_token(ctx->lexer->token.type, NULL)) { + return make_cmp(ctx, &f, expr_relop_turn(r1), &c1); + } + + enum expr_relop r2; + struct expr_constant_set c2; + if (!parse_relop(ctx, &r2) || !parse_constant_set(ctx, &c2)) { + expr_constant_set_destroy(&c1); + return NULL; + } else { + /* Reject "1 == field == 2", "1 < field > 2", and so on. */ + if (!(((r1 == EXPR_R_LT || r1 == EXPR_R_LE) && + (r2 == EXPR_R_LT || r2 == EXPR_R_LE)) || + ((r1 == EXPR_R_GT || r1 == EXPR_R_GE) && + (r2 == EXPR_R_GT || r2 == EXPR_R_GE)))) { + expr_error(ctx, "Range expressions must have the form " + "`x < field < y' or `x > field > y', with each " + "`<' optionally replaced by `<=' or `>' by `>=')."); + expr_constant_set_destroy(&c1); + expr_constant_set_destroy(&c2); + return NULL; + } + + struct expr *e1 = make_cmp(ctx, &f, expr_relop_turn(r1), &c1); + struct expr *e2 = make_cmp(ctx, &f, r2, &c2); + if (ctx->error) { + expr_destroy(e1); + expr_destroy(e2); + return NULL; + } + return expr_combine(EXPR_T_AND, e1, e2); + } + } +} + +static struct expr * +expr_parse_not(struct expr_context *ctx) +{ + bool atomic; + + if (lexer_match(ctx->lexer, LEX_T_LOG_NOT)) { + ctx->not = !ctx->not; + struct expr *expr = expr_parse_primary(ctx, &atomic); + ctx->not = !ctx->not; + + if (expr) { + if (!atomic) { + expr_error(ctx, "Missing parentheses around operand of !."); + expr_destroy(expr); + return NULL; + } + expr_not(expr); + } + return expr; + } else { + return expr_parse_primary(ctx, &atomic); + } +} + +struct expr * +expr_parse__(struct expr_context *ctx) +{ + struct expr *e = expr_parse_not(ctx); + if (!e) { + return NULL; + } + + enum lex_type lex_type = ctx->lexer->token.type; + if (lex_type == LEX_T_LOG_AND || lex_type == LEX_T_LOG_OR) { + enum expr_type expr_type + = lex_type == LEX_T_LOG_AND ? EXPR_T_AND : EXPR_T_OR; + + lexer_get(ctx->lexer); + do { + struct expr *e2 = expr_parse_not(ctx); + if (!e2) { + expr_destroy(e); + return NULL; + } + e = expr_combine(expr_type, e, e2); + } while (lexer_match(ctx->lexer, lex_type)); + if (ctx->lexer->token.type == LEX_T_LOG_AND + || ctx->lexer->token.type == LEX_T_LOG_OR) { + expr_destroy(e); + expr_error(ctx, + "&& and || must be parenthesized when used together."); + return NULL; + } + } + return e; +} + +/* Parses an expression using the symbols in 'symtab' from 'lexer'. If + * successful, returns the new expression and sets '*errorp' to NULL. On + * failure, returns NULL and sets '*errorp' to an explanatory error message. + * The caller must eventually free the returned expression (with + * expr_destroy()) or error (with free()). */ +struct expr * +expr_parse(struct lexer *lexer, const struct shash *symtab, char **errorp) +{ + struct expr_context ctx; + + ctx.lexer = lexer; + ctx.symtab = symtab; + ctx.error = NULL; + ctx.not = false; + + struct expr *e = expr_parse__(&ctx); + *errorp = ctx.error; + ovs_assert((ctx.error != NULL) != (e != NULL)); + return e; +} + +/* Like expr_parse(), but the expression is taken from 's'. */ +struct expr * +expr_parse_string(const char *s, const struct shash *symtab, char **errorp) +{ + struct lexer lexer; + struct expr *expr; + + lexer_init(&lexer, s); + lexer_get(&lexer); + expr = expr_parse(&lexer, symtab, errorp); + if (!errorp && lexer.token.type != LEX_T_END) { + *errorp = xstrdup("Extra tokens at end of input."); + expr_destroy(expr); + expr = NULL; + } + lexer_destroy(&lexer); + + return expr; +} + +static struct expr_symbol * +add_symbol(struct shash *symtab, const char *name, int width, + const char *prereqs, enum expr_level level, + bool must_crossproduct) +{ + struct expr_symbol *symbol = xzalloc(sizeof *symbol); + symbol->name = xstrdup(name); + symbol->prereqs = prereqs && prereqs[0] ? xstrdup(prereqs) : NULL; + symbol->width = width; + symbol->level = level; + symbol->must_crossproduct = must_crossproduct; + shash_add_assert(symtab, symbol->name, symbol); + return symbol; +} + +/* Adds field 'id' to symbol table 'symtab' under the given 'name'. Whenever + * 'name' is referenced, expression annotation (see expr_annotate()) will + * ensure that 'prereqs' are also true. If 'must_crossproduct' is true, then + * conversion to flows will never attempt to use the field as a conjunctive + * match dimension (see "Crossproducting" in the large comment on struct + * expr_symbol in expr.h for an example). + * + * A given field 'id' must only be used for a single symbol in a symbol table. + * Use subfields to duplicate or subset a field (you can even make a subfield + * include all the bits of the "parent" field if you like). */ +struct expr_symbol * +expr_symtab_add_field(struct shash *symtab, const char *name, + enum mf_field_id id, const char *prereqs, + bool must_crossproduct) +{ + const struct mf_field *field = mf_from_id(id); + struct expr_symbol *symbol; + + symbol = add_symbol(symtab, name, field->n_bits, prereqs, + (field->maskable == MFM_FULLY + ? EXPR_L_ORDINAL + : EXPR_L_NOMINAL), + must_crossproduct); + symbol->field = field; + return symbol; +} + +static bool +parse_field_from_string(const char *s, const struct shash *symtab, + struct expr_field *field, char **errorp) +{ + struct lexer lexer; + lexer_init(&lexer, s); + lexer_get(&lexer); + + struct expr_context ctx; + ctx.lexer = &lexer; + ctx.symtab = symtab; + ctx.error = NULL; + ctx.not = false; + + bool ok = parse_field(&ctx, field); + if (!ok) { + *errorp = ctx.error; + } else if (lexer.token.type != LEX_T_END) { + *errorp = xstrdup("Extra tokens at end of input."); + ok = false; + } + + lexer_destroy(&lexer); + + return ok; +} + +/* Adds 'name' as a subfield of a larger field in 'symtab'. Whenever + * 'name' is referenced, expression annotation (see expr_annotate()) will + * ensure that 'prereqs' are also true. + * + * 'subfield' must describe the subfield as a string, e.g. "vlan.tci[0..11]" + * for the low 12 bits of a larger field named "vlan.tci". */ +struct expr_symbol * +expr_symtab_add_subfield(struct shash *symtab, const char *name, + const char *prereqs, const char *subfield) +{ + struct expr_symbol *symbol; + struct expr_field f; + char *error; + + if (!parse_field_from_string(subfield, symtab, &f, &error)) { + VLOG_WARN("%s: error parsing %s subfield (%s)", subfield, name, error); + free(error); + return NULL; + } + + enum expr_level level = f.symbol->level; + if (level != EXPR_L_ORDINAL) { + VLOG_WARN("can't define %s as subfield of %s field %s", + name, expr_level_to_string(level), f.symbol->name); + } + + symbol = add_symbol(symtab, name, f.n_bits, prereqs, level, false); + symbol->expansion = xstrdup(subfield); + return symbol; +} + +/* Adds a string-valued symbol named 'name' to 'symtab' with the specified + * 'prereqs'. */ +struct expr_symbol * +expr_symtab_add_string(struct shash *symtab, const char *name, + const char *prereqs) +{ + return add_symbol(symtab, name, 0, prereqs, EXPR_L_NOMINAL, false); +} + +static enum expr_level +expr_get_level(const struct expr *expr) +{ + const struct expr *sub; + enum expr_level level = EXPR_L_ORDINAL; + + switch (expr->type) { + case EXPR_T_CMP: + return (expr->cmp.symbol->level == EXPR_L_NOMINAL + ? EXPR_L_NOMINAL + : EXPR_L_BOOLEAN); + + case EXPR_T_AND: + case EXPR_T_OR: + LIST_FOR_EACH (sub, node, &expr->andor) { + enum expr_level sub_level = expr_get_level(sub); + level = MIN(level, sub_level); + } + return level; + + case EXPR_T_BOOLEAN: + return EXPR_L_BOOLEAN; + + default: + OVS_NOT_REACHED(); + } +} + +static enum expr_level +expr_parse_level(const char *s, const struct shash *symtab, char **errorp) +{ + struct expr *expr = expr_parse_string(s, symtab, errorp); + enum expr_level level = expr ? expr_get_level(expr) : EXPR_L_NOMINAL; + expr_destroy(expr); + return level; +} + +/* Adds a predicate symbol, whose value is the given Boolean 'expression', + * named 'name' to 'symtab'. For example, "ip4 && ip4.proto == 1" might be an + * appropriate predicate named "tcp4". */ +struct expr_symbol * +expr_symtab_add_predicate(struct shash *symtab, const char *name, + const char *expansion) +{ + struct expr_symbol *symbol; + enum expr_level level; + char *error; + + level = expr_parse_level(expansion, symtab, &error); + if (error) { + VLOG_WARN("%s: error parsing %s expansion (%s)", + expansion, name, error); + free(error); + return NULL; + } + + symbol = add_symbol(symtab, name, 1, NULL, level, false); + symbol->expansion = xstrdup(expansion); + return symbol; +} + +/* Destroys 'symtab' and all of its symbols. */ +void +expr_symtab_destroy(struct shash *symtab) +{ + struct shash_node *node, *next; + + SHASH_FOR_EACH_SAFE (node, next, symtab) { + struct expr_symbol *symbol = node->data; + + shash_delete(symtab, node); + free(symbol->name); + free(symbol->prereqs); + free(symbol->expansion); + free(symbol); + } +} + +/* Cloning. */ + +static struct expr * +expr_clone_cmp(struct expr *expr) +{ + struct expr *new = xmemdup(expr, sizeof *expr); + if (!new->cmp.symbol->width) { + new->cmp.string = xstrdup(new->cmp.string); + } + return new; +} + +static struct expr * +expr_clone_andor(struct expr *expr) +{ + struct expr *new = expr_create_andor(expr->type); + struct expr *sub; + + LIST_FOR_EACH (sub, node, &expr->andor) { + struct expr *new_sub = expr_clone(sub); + list_push_back(&new->andor, &new_sub->node); + } + return new; +} + +/* Returns a clone of 'expr'. This is a "deep copy": neither the returned + * expression nor any of its substructure will be shared with 'expr'. */ +struct expr * +expr_clone(struct expr *expr) +{ + switch (expr->type) { + case EXPR_T_CMP: + return expr_clone_cmp(expr); + + case EXPR_T_AND: + case EXPR_T_OR: + return expr_clone_andor(expr); + + case EXPR_T_BOOLEAN: + return expr_create_boolean(expr->boolean); + } + OVS_NOT_REACHED(); +} + +/* Destroys 'expr' and all of the sub-expressions it references. */ +void +expr_destroy(struct expr *expr) +{ + if (!expr) { + return; + } + + struct expr *sub, *next; + + switch (expr->type) { + case EXPR_T_CMP: + if (!expr->cmp.symbol->width) { + free(expr->cmp.string); + } + break; + + case EXPR_T_AND: + case EXPR_T_OR: + LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) { + list_remove(&sub->node); + expr_destroy(sub); + } + break; + + case EXPR_T_BOOLEAN: + break; + } + free(expr); +} + +/* Annotation. */ + +/* An element in a linked list of symbols. + * + * Used to detect when a symbol is being expanded recursively, to allow + * flagging an error. */ +struct annotation_nesting { + struct ovs_list node; + const struct expr_symbol *symbol; +}; + +struct expr *expr_annotate__(struct expr *, const struct shash *symtab, + struct ovs_list *nesting, char **errorp); + +static struct expr * +parse_and_annotate(const char *s, const struct shash *symtab, + struct ovs_list *nesting, char **errorp) +{ + char *error; + struct expr *expr; + + expr = expr_parse_string(s, symtab, &error); + if (expr) { + expr = expr_annotate__(expr, symtab, nesting, &error); + } + if (!expr) { + *errorp = xasprintf("Error parsing expression `%s' encountered as " + "prerequisite or predicate of initial expression: " + "%s", s, error); + free(error); + } + return expr; +} + +static struct expr * +expr_annotate_cmp(struct expr *expr, const struct shash *symtab, + struct ovs_list *nesting, char **errorp) +{ + const struct expr_symbol *symbol = expr->cmp.symbol; + const struct annotation_nesting *iter; + LIST_FOR_EACH (iter, node, nesting) { + if (iter->symbol == symbol) { + *errorp = xasprintf("Recursive expansion of symbol `%s'.", + symbol->name); + expr_destroy(expr); + return NULL; + } + } + + struct annotation_nesting an; + an.symbol = symbol; + list_push_back(nesting, &an.node); + + struct expr *prereqs = NULL; + if (symbol->prereqs) { + prereqs = parse_and_annotate(symbol->prereqs, symtab, nesting, errorp); + if (!prereqs) { + goto error; + } + } + + if (symbol->expansion) { + if (symbol->level == EXPR_L_ORDINAL) { + struct expr_field field; + + if (!parse_field_from_string(symbol->expansion, symtab, + &field, errorp)) { + goto error; + } + + expr->cmp.symbol = field.symbol; + mf_subvalue_shift(&expr->cmp.value, field.ofs); + mf_subvalue_shift(&expr->cmp.mask, field.ofs); + } else { + struct expr *expansion; + + expansion = parse_and_annotate(symbol->expansion, symtab, + nesting, errorp); + if (!expansion) { + goto error; + } + + bool positive = (expr->cmp.value.integer & htonll(1)) != 0; + positive ^= expr->cmp.relop == EXPR_R_NE; + if (!positive) { + expr_not(expansion); + } + + expr_destroy(expr); + expr = expansion; + } + } + + list_remove(&an.node); + return prereqs ? expr_combine(EXPR_T_AND, expr, prereqs) : expr; + +error: + expr_destroy(expr); + expr_destroy(prereqs); + list_remove(&an.node); + return NULL; +} + +struct expr * +expr_annotate__(struct expr *expr, const struct shash *symtab, + struct ovs_list *nesting, char **errorp) +{ + switch (expr->type) { + case EXPR_T_CMP: + return expr_annotate_cmp(expr, symtab, nesting, errorp); + + case EXPR_T_AND: + case EXPR_T_OR: { + struct expr *sub, *next; + + LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) { + list_remove(&sub->node); + struct expr *new_sub = expr_annotate__(sub, symtab, + nesting, errorp); + if (!new_sub) { + expr_destroy(expr); + return NULL; + } + expr_insert_andor(expr, next, new_sub); + } + *errorp = NULL; + return expr; + } + + case EXPR_T_BOOLEAN: + *errorp = NULL; + return expr; + + default: + OVS_NOT_REACHED(); + } +} + +/* "Annotates" 'expr', which does the following: + * + * - Applies prerequisites, by locating each comparison operator whose + * field has a prerequisite and adding a logical AND against those + * prerequisites. + * + * - Expands references to subfield symbols, by replacing them by + * references to their underlying field symbols (suitably shifted). + * + * - Expands references to predicate symbols, by replacing them by the + * expressions that they expand to. + * + * In each case, annotation occurs recursively as necessary. */ +struct expr * +expr_annotate(struct expr *expr, const struct shash *symtab, char **errorp) +{ + struct ovs_list nesting = OVS_LIST_INITIALIZER(&nesting); + return expr_annotate__(expr, symtab, &nesting, errorp); +} + +static struct expr * +expr_simplify_ne(struct expr *expr) +{ + struct expr *new = NULL; + const union mf_subvalue *value = &expr->cmp.value; + const union mf_subvalue *mask = &expr->cmp.mask; + int w = expr->cmp.symbol->width; + int i; + + for (i = 0; (i = bitwise_scan(mask, sizeof *mask, true, i, w)) < w; i++) { + struct expr *e; + + e = xzalloc(sizeof *e); + e->type = EXPR_T_CMP; + e->cmp.symbol = expr->cmp.symbol; + e->cmp.relop = EXPR_R_EQ; + bitwise_put_bit(&e->cmp.value, sizeof e->cmp.value, i, + !bitwise_get_bit(value, sizeof *value, i)); + bitwise_put1(&e->cmp.mask, sizeof e->cmp.mask, i); + + new = expr_combine(EXPR_T_OR, new, e); + } + ovs_assert(new); + + expr_destroy(expr); + + return new; +} + +static struct expr * +expr_simplify_relational(struct expr *expr) +{ + const union mf_subvalue *value = &expr->cmp.value; + int start, n_bits, end; + + find_bitwise_range(&expr->cmp.mask, expr->cmp.symbol->width, + &start, &n_bits); + ovs_assert(n_bits > 0); + end = start + n_bits; + + struct expr *new; + if (expr->cmp.relop == EXPR_R_LE || expr->cmp.relop == EXPR_R_GE) { + new = xmemdup(expr, sizeof *expr); + new->cmp.relop = EXPR_R_EQ; + } else { + new = NULL; + } + + bool b = expr->cmp.relop == EXPR_R_LT || expr->cmp.relop == EXPR_R_LE; + for (int z = bitwise_scan(value, sizeof *value, b, start, end); + z < end; + z = bitwise_scan(value, sizeof *value, b, z + 1, end)) { + struct expr *e; + + e = xmemdup(expr, sizeof *expr); + e->cmp.relop = EXPR_R_EQ; + bitwise_toggle_bit(&e->cmp.value, sizeof e->cmp.value, z); + bitwise_zero(&e->cmp.value, sizeof e->cmp.value, start, z - start); + bitwise_zero(&e->cmp.mask, sizeof e->cmp.mask, start, z - start); + new = expr_combine(EXPR_T_OR, new, e); + } + expr_destroy(expr); + return new ? new : expr_create_boolean(false); +} + +/* Takes ownership of 'expr' and returns an equivalent expression whose + * EXPR_T_CMP nodes use only tests for equality (EXPR_R_EQ). */ +struct expr * +expr_simplify(struct expr *expr) +{ + struct expr *sub, *next; + + switch (expr->type) { + case EXPR_T_CMP: + return (expr->cmp.relop == EXPR_R_EQ || !expr->cmp.symbol->width ? expr + : expr->cmp.relop == EXPR_R_NE ? expr_simplify_ne(expr) + : expr_simplify_relational(expr)); + + case EXPR_T_AND: + case EXPR_T_OR: + LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) { + list_remove(&sub->node); + expr_insert_andor(expr, next, expr_simplify(sub)); + } + return expr_fix(expr); + + case EXPR_T_BOOLEAN: + return expr; + } + OVS_NOT_REACHED(); +} + +static const struct expr_symbol * +expr_is_cmp(const struct expr *expr) +{ + switch (expr->type) { + case EXPR_T_CMP: + return expr->cmp.symbol; + + case EXPR_T_AND: + case EXPR_T_OR: { + const struct expr_symbol *prev = NULL; + struct expr *sub; + + LIST_FOR_EACH (sub, node, &expr->andor) { + const struct expr_symbol *symbol = expr_is_cmp(sub); + if (!symbol || (prev && symbol != prev)) { + return NULL; + } + prev = symbol; + } + return prev; + } + + case EXPR_T_BOOLEAN: + return NULL; + + default: + OVS_NOT_REACHED(); + } +} + +struct expr_sort { + struct expr *expr; + const struct expr_symbol *relop; + enum expr_type type; +}; + +static int +compare_expr_sort(const void *a_, const void *b_) +{ + const struct expr_sort *a = a_; + const struct expr_sort *b = b_; + + if (a->type != b->type) { + return a->type < b->type ? -1 : 1; + } else if (a->relop) { + int cmp = strcmp(a->relop->name, b->relop->name); + if (cmp) { + return cmp; + } + + enum expr_type a_type = a->expr->type; + enum expr_type b_type = a->expr->type; + return a_type < b_type ? -1 : a_type > b_type; + } else if (a->type == EXPR_T_AND || a->type == EXPR_T_OR) { + size_t a_len = list_size(&a->expr->andor); + size_t b_len = list_size(&b->expr->andor); + return a_len < b_len ? -1 : a_len > b_len; + } else { + return 0; + } +} + +static struct expr *crush_cmps(struct expr *, const struct expr_symbol *); + +static struct expr * +crush_and(struct expr *expr, const struct expr_symbol *symbol) +{ + ovs_assert(!list_is_short(&expr->andor)); + + union mf_subvalue value, mask; + memset(&value, 0, sizeof value); + memset(&mask, 0, sizeof mask); + + 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 (!mf_subvalue_intersect(&value, &mask, + &new->cmp.value, &new->cmp.mask, + &value, &mask)) { + expr_destroy(new); + expr_destroy(expr); + return expr_create_boolean(false); + } + expr_destroy(new); + 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 (list_is_empty(&expr->andor)) { + if (is_all_zeros(&mask, sizeof mask)) { + expr_destroy(expr); + return expr_create_boolean(true); + } else { + struct expr *cmp; + cmp = xmalloc(sizeof *cmp); + cmp->type = EXPR_T_CMP; + cmp->cmp.symbol = symbol; + cmp->cmp.relop = EXPR_R_EQ; + cmp->cmp.value = value; + cmp->cmp.mask = mask; + expr_destroy(expr); + return cmp; + } + } else if (list_is_short(&expr->andor)) { + /* Transform "a && (b || c || d)" into "ab || ac || ad" where "ab" is + * computed as "a && b", etc. */ + struct expr *disjuncts = expr_from_node(list_pop_front(&expr->andor)); + struct expr *or; + + or = xmalloc(sizeof *or); + or->type = EXPR_T_OR; + list_init(&or->andor); + + ovs_assert(disjuncts->type == EXPR_T_OR); + LIST_FOR_EACH_SAFE (sub, next, node, &disjuncts->andor) { + ovs_assert(sub->type == EXPR_T_CMP); + list_remove(&sub->node); + if (mf_subvalue_intersect(&value, &mask, + &sub->cmp.value, &sub->cmp.mask, + &sub->cmp.value, &sub->cmp.mask)) { + list_push_back(&or->andor, &sub->node); + } else { + free(sub); + } + } + free(disjuncts); + free(expr); + if (list_is_empty(&or->andor)) { + free(or); + return expr_create_boolean(false); + } else if (list_is_short(&or->andor)) { + struct expr *cmp = expr_from_node(list_pop_front(&or->andor)); + free(or); + return cmp; + } else { + return or; + } + } else { + /* Transform "x && (a0 || a1) && (b0 || b1) && ..." into + * "(xa0b0 || xa0b1 || xa1b0 || xa1b1) && ...". */ + struct expr *as = expr_from_node(list_pop_front(&expr->andor)); + struct expr *bs = expr_from_node(list_pop_front(&expr->andor)); + struct expr *new = NULL; + struct expr *or; + + or = xmalloc(sizeof *or); + or->type = EXPR_T_OR; + list_init(&or->andor); + + struct expr *a; + LIST_FOR_EACH (a, node, &as->andor) { + union mf_subvalue a_value, a_mask; + + ovs_assert(a->type == EXPR_T_CMP); + if (!mf_subvalue_intersect(&value, &mask, + &a->cmp.value, &a->cmp.mask, + &a_value, &a_mask)) { + continue; + } + + struct expr *b; + LIST_FOR_EACH (b, node, &bs->andor) { + ovs_assert(b->type == EXPR_T_CMP); + if (!new) { + new = xmalloc(sizeof *new); + new->type = EXPR_T_CMP; + new->cmp.symbol = symbol; + new->cmp.relop = EXPR_R_EQ; + } + if (mf_subvalue_intersect(&a_value, &a_mask, + &b->cmp.value, &b->cmp.mask, + &new->cmp.value, &new->cmp.mask)) { + list_push_back(&or->andor, &new->node); + new = NULL; + } + } + } + expr_destroy(as); + expr_destroy(bs); + free(new); + + if (list_is_empty(&or->andor)) { + expr_destroy(expr); + free(or); + return expr_create_boolean(false); + } else if (list_is_short(&or->andor)) { + struct expr *cmp = expr_from_node(list_pop_front(&or->andor)); + free(or); + if (list_is_empty(&expr->andor)) { + expr_destroy(expr); + return crush_cmps(cmp, symbol); + } else { + return crush_cmps(expr_combine(EXPR_T_AND, cmp, expr), symbol); + } + } else if (!list_is_empty(&expr->andor)) { + struct expr *e = expr_combine(EXPR_T_AND, or, expr); + ovs_assert(!list_is_short(&e->andor)); + return crush_cmps(e, symbol); + } else { + expr_destroy(expr); + return crush_cmps(or, symbol); + } + } +} + +static int +compare_expr(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; +} + +static struct expr * +crush_or(struct expr *expr, const struct expr_symbol *symbol) +{ + struct expr *sub, *next = NULL; + + /* First, crush all the subexpressions. That might eliminate the + * OR-expression entirely; if so, return the result. */ + LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) { + list_remove(&sub->node); + expr_insert_andor(expr, next, crush_cmps(sub, symbol)); + } + expr = expr_fix(expr); + if (expr->type != EXPR_T_OR) { + return expr; + } + + /* Eliminate duplicates by sorting the subexpressions. */ + size_t n = list_size(&expr->andor); + struct expr **subs = xmalloc(n * sizeof *subs); + + size_t i = 0; + LIST_FOR_EACH (sub, node, &expr->andor) { + subs[i++] = sub; + } + ovs_assert(i == n); + + qsort(subs, n, sizeof *subs, compare_expr); + + 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)) { + list_push_back(&expr->andor, &b->node); + } else { + free(b); + } + } + free(subs); + return expr_fix(expr); +} + +/* Converts 'expr', which must be a cmp in the sense determined by + * expr_is_cmp(). Returns a cmp, a disjunction of cmps, or a boolean. */ +static struct expr * +crush_cmps(struct expr *expr, const struct expr_symbol *symbol) +{ + switch (expr->type) { + case EXPR_T_OR: + return crush_or(expr, symbol); + + case EXPR_T_AND: + return crush_and(expr, symbol); + + case EXPR_T_CMP: + return expr; + + case EXPR_T_BOOLEAN: + return expr; + + default: + OVS_NOT_REACHED(); + } +} + +static struct expr * +expr_sort(struct expr *expr) +{ + size_t n = list_size(&expr->andor); + struct expr_sort *subs = xmalloc(n * sizeof *subs); + struct expr *sub; + size_t i; + + i = 0; + LIST_FOR_EACH (sub, node, &expr->andor) { + subs[i].expr = sub; + subs[i].relop = expr_is_cmp(sub); + subs[i].type = subs[i].relop ? EXPR_T_CMP : sub->type; + i++; + } + ovs_assert(i == n); + + qsort(subs, n, sizeof *subs, compare_expr_sort); + + list_init(&expr->andor); + for (int i = 0; i < n; ) { + if (subs[i].relop) { + int j; + for (j = i + 1; j < n; j++) { + if (subs[i].relop != subs[j].relop) { + break; + } + } + + struct expr *crushed; + if (j == i + 1) { + crushed = crush_cmps(subs[i].expr, subs[i].relop); + } else { + struct expr *combined = subs[i].expr; + for (int k = i + 1; k < j; k++) { + combined = expr_combine(EXPR_T_AND, combined, + subs[k].expr); + } + ovs_assert(!list_is_short(&combined->andor)); + crushed = crush_cmps(combined, subs[i].relop); + } + if (crushed->type == EXPR_T_BOOLEAN) { + if (!crushed->boolean) { + for (int k = j; k < n; k++) { + expr_destroy(subs[k].expr); + } + expr_destroy(expr); + expr = crushed; + break; + } else { + free(crushed); + } + } else { + expr = expr_combine(EXPR_T_AND, expr, crushed); + } + i = j; + } else { + expr = expr_combine(EXPR_T_AND, expr, subs[i++].expr); + } + } + free(subs); + + return expr; +} + +static struct expr *expr_normalize_or(struct expr *expr); + +/* Returns 'expr', which is an AND, reduced to OR(AND(clause)) where + * a clause is a cmp or a disjunction of cmps on a single field. */ +static struct expr * +expr_normalize_and(struct expr *expr) +{ + ovs_assert(expr->type == EXPR_T_AND); + + expr = expr_sort(expr); + if (expr->type != EXPR_T_AND) { + ovs_assert(expr->type == EXPR_T_BOOLEAN); + return 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) { + continue; + } else if (mf_subvalue_intersect(&a->cmp.value, &a->cmp.mask, + &b->cmp.value, &b->cmp.mask, + &b->cmp.value, &b->cmp.mask)) { + list_remove(&a->node); + expr_destroy(a); + } else { + expr_destroy(expr); + return expr_create_boolean(false); + } + } + if (list_is_short(&expr->andor)) { + struct expr *sub = expr_from_node(list_front(&expr->andor)); + free(expr); + return sub; + } + + struct expr *sub; + LIST_FOR_EACH (sub, node, &expr->andor) { + if (sub->type == EXPR_T_CMP) { + continue; + } + + ovs_assert(sub->type == EXPR_T_OR); + const struct expr_symbol *symbol = expr_is_cmp(sub); + if (!symbol || symbol->must_crossproduct) { + struct expr *or = expr_create_andor(EXPR_T_OR); + struct expr *k; + + LIST_FOR_EACH (k, node, &sub->andor) { + struct expr *and = expr_create_andor(EXPR_T_AND); + struct expr *m; + + LIST_FOR_EACH (m, node, &expr->andor) { + struct expr *term = m == sub ? k : m; + if (term->type == EXPR_T_AND) { + struct expr *p; + + LIST_FOR_EACH (p, node, &term->andor) { + struct expr *new = expr_clone(p); + list_push_back(&and->andor, &new->node); + } + } else { + struct expr *new = expr_clone(term); + list_push_back(&and->andor, &new->node); + } + } + list_push_back(&or->andor, &and->node); + } + expr_destroy(expr); + return expr_normalize_or(or); + } + } + return expr; +} + +static struct expr * +expr_normalize_or(struct expr *expr) +{ + struct expr *sub, *next; + + LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) { + if (sub->type == EXPR_T_AND) { + list_remove(&sub->node); + + struct expr *new = expr_normalize_and(sub); + if (new->type == EXPR_T_BOOLEAN) { + if (new->boolean) { + expr_destroy(expr); + return new; + } + free(new); + } else { + expr_insert_andor(expr, next, new); + } + } else { + ovs_assert(sub->type == EXPR_T_CMP); + } + } + if (list_is_empty(&expr->andor)) { + free(expr); + return expr_create_boolean(false); + } + if (list_is_short(&expr->andor)) { + struct expr *sub = expr_from_node(list_pop_front(&expr->andor)); + free(expr); + return sub; + } + + return expr; +} + +/* Takes ownership of 'expr', which is either a constant "true" or "false" or + * an expression in terms of only relationals, AND, and OR. Returns either a + * constant "true" or "false" or 'expr' reduced to OR(AND(clause)) where a + * clause is a cmp or a disjunction of cmps on a single field. This form is + * significant because it is a form that can be directly converted to OpenFlow + * flows with the Open vSwitch "conjunctive match" extension. + * + * 'expr' must already have been simplified, with expr_simplify(). */ +struct expr * +expr_normalize(struct expr *expr) +{ + switch (expr->type) { + case EXPR_T_CMP: + return expr; + + case EXPR_T_AND: + return expr_normalize_and(expr); + + case EXPR_T_OR: + return expr_normalize_or(expr); + + case EXPR_T_BOOLEAN: + return expr; + } + OVS_NOT_REACHED(); +} + +/* Creates, initializes, and returns a new 'struct expr_match'. If 'm' is + * nonnull then it is copied into the new expr_match, otherwise the new + * expr_match's 'match' member is initialized to a catch-all match for the + * caller to refine in-place. + * + * If 'conj_id' is nonzero, adds one conjunction based on 'conj_id', 'clause', + * and 'n_clauses' to the returned 'struct expr_match', otherwise the + * expr_match will not have any conjunctions. + * + * The caller should use expr_match_add() to add the expr_match to a hash table + * after it is finalized. */ +static struct expr_match * +expr_match_new(const struct match *m, uint8_t clause, uint8_t n_clauses, + uint32_t conj_id) +{ + struct expr_match *match = xmalloc(sizeof *match); + if (m) { + match->match = *m; + } else { + match_init_catchall(&match->match); + } + if (conj_id) { + match->conjunctions = xmalloc(sizeof *match->conjunctions); + match->conjunctions[0].id = conj_id; + match->conjunctions[0].clause = clause; + match->conjunctions[0].n_clauses = n_clauses; + match->n = 1; + match->allocated = 1; + } else { + match->conjunctions = NULL; + match->n = 0; + match->allocated = 0; + } + return match; +} + +/* Adds 'match' to hash table 'matches', which becomes the new owner of + * 'match'. + * + * This might actually destroy 'match' because it gets merged together with + * some existing conjunction.*/ +static void +expr_match_add(struct hmap *matches, struct expr_match *match) +{ + uint32_t hash = match_hash(&match->match, 0); + struct expr_match *m; + + HMAP_FOR_EACH_WITH_HASH (m, hmap_node, hash, matches) { + if (match_equal(&m->match, &match->match)) { + if (!m->n || !match->n) { + free(m->conjunctions); + m->conjunctions = NULL; + m->n = 0; + m->allocated = 0; + } else { + ovs_assert(match->n == 1); + if (m->n >= m->allocated) { + m->conjunctions = x2nrealloc(m->conjunctions, + &m->allocated, + sizeof *m->conjunctions); + } + m->conjunctions[m->n++] = match->conjunctions[0]; + } + free(match->conjunctions); + free(match); + return; + } + } + + hmap_insert(matches, &match->hmap_node, hash); +} + +static void +constrain_match(const struct expr *expr, struct match *m) +{ + ovs_assert(expr->type == EXPR_T_CMP); + ovs_assert(expr->cmp.symbol->width); + mf_mask_subfield(expr->cmp.symbol->field, &expr->cmp.value, + &expr->cmp.mask, m); +} + +static void +add_disjunction(const struct expr *or, struct match *m, uint8_t clause, + uint8_t n_clauses, uint32_t conj_id, struct hmap *matches) +{ + struct expr *sub; + + ovs_assert(or->type == EXPR_T_OR); + LIST_FOR_EACH (sub, node, &or->andor) { + struct expr_match *match = expr_match_new(m, clause, n_clauses, + conj_id); + constrain_match(sub, &match->match); + expr_match_add(matches, match); + } +} + +static void +add_conjunction(const struct expr *and, uint32_t *n_conjsp, + struct hmap *matches) +{ + struct match match; + int n_clauses = 0; + struct expr *sub; + + match_init_catchall(&match); + + ovs_assert(and->type == EXPR_T_AND); + LIST_FOR_EACH (sub, node, &and->andor) { + switch (sub->type) { + case EXPR_T_CMP: + constrain_match(sub, &match); + break; + case EXPR_T_OR: + n_clauses++; + break; + case EXPR_T_AND: + case EXPR_T_BOOLEAN: + OVS_NOT_REACHED(); + } + } + + if (!n_clauses) { + expr_match_add(matches, expr_match_new(&match, 0, 0, 0)); + } else if (n_clauses == 1) { + LIST_FOR_EACH (sub, node, &and->andor) { + if (sub->type == EXPR_T_OR) { + add_disjunction(sub, &match, 0, 0, 0, matches); + } + } + } else { + int clause = 0; + (*n_conjsp)++; + LIST_FOR_EACH (sub, node, &and->andor) { + if (sub->type == EXPR_T_OR) { + add_disjunction(sub, &match, clause++, n_clauses, *n_conjsp, + matches); + } + } + } +} + +static void +add_cmp_flow(const struct expr *cmp, struct hmap *matches) +{ + struct expr_match *m = expr_match_new(NULL, 0, 0, 0); + constrain_match(cmp, &m->match); + expr_match_add(matches, m); +} + +/* Converts 'expr', which must be in the form returned by expr_normalize(), to + * a collection of Open vSwitch flows in 'matches', which this function + * initializes to an hmap of "struct expr_match" structures. */ +uint32_t +expr_to_matches(const struct expr *expr, struct hmap *matches) +{ + uint32_t n_conjs = 0; + + hmap_init(matches); + switch (expr->type) { + case EXPR_T_CMP: + add_cmp_flow(expr, matches); + break; + + case EXPR_T_AND: + add_conjunction(expr, &n_conjs, matches); + break; + + case EXPR_T_OR: + if (expr_is_cmp(expr)) { + struct expr *sub; + + LIST_FOR_EACH (sub, node, &expr->andor) { + add_cmp_flow(sub, matches); + } + } else { + struct expr *sub; + + LIST_FOR_EACH (sub, node, &expr->andor) { + if (sub->type == EXPR_T_AND) { + add_conjunction(sub, &n_conjs, matches); + } else { + add_cmp_flow(sub, matches); + } + } + } + break; + + case EXPR_T_BOOLEAN: + if (expr->boolean) { + struct expr_match *m = expr_match_new(NULL, 0, 0, 0); + expr_match_add(matches, m); + } else { + /* No match. */ + } + break; + } + return n_conjs; +} + +/* Returns true if 'expr' honors the invariants for expressions (see the large + * comment above "struct expr" in expr.h), false otherwise. */ +bool +expr_honors_invariants(const struct expr *expr) +{ + const struct expr *sub; + + switch (expr->type) { + case EXPR_T_CMP: + if (expr->cmp.symbol->width) { + for (int i = 0; i < ARRAY_SIZE(expr->cmp.value.be64); i++) { + if (expr->cmp.value.be64[i] & ~expr->cmp.mask.be64[i]) { + return false; + } + } + } + return true; + + case EXPR_T_AND: + case EXPR_T_OR: + if (list_is_short(&expr->andor)) { + return false; + } + LIST_FOR_EACH (sub, node, &expr->andor) { + if (sub->type == expr->type || !expr_honors_invariants(sub)) { + return false; + } + } + return true; + + case EXPR_T_BOOLEAN: + return true; + + default: + OVS_NOT_REACHED(); + } +} + +static bool +expr_is_normalized_and(const struct expr *expr) +{ + /* XXX should also check that no symbol is repeated. */ + const struct expr *sub; + + LIST_FOR_EACH (sub, node, &expr->andor) { + if (!expr_is_cmp(sub)) { + return false; + } + } + return true; +} + +/* Returns true if 'expr' is in the form returned by expr_normalize(), false + * otherwise. */ +bool +expr_is_normalized(const struct expr *expr) +{ + switch (expr->type) { + case EXPR_T_CMP: + return true; + + case EXPR_T_AND: + return expr_is_normalized_and(expr); + + case EXPR_T_OR: + if (!expr_is_cmp(expr)) { + const struct expr *sub; + + LIST_FOR_EACH (sub, node, &expr->andor) { + if (!expr_is_cmp(sub) && !expr_is_normalized_and(sub)) { + return false; + } + } + } + return true; + + case EXPR_T_BOOLEAN: + return true; + + default: + OVS_NOT_REACHED(); + } +} diff --git a/ovn/lib/expr.h b/ovn/lib/expr.h new file mode 100644 index 000000000..ab13c1b8e --- /dev/null +++ b/ovn/lib/expr.h @@ -0,0 +1,367 @@ +/* + * Copyright (c) 2015 Nicira, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef OVN_EXPR_H +#define OVN_EXPR_H 1 + +/* OVN matching expression tree + * ============================ + * + * The data structures here form an abstract expression tree for matching + * expressions in OVN. + * + * The abstract syntax tree representation of a matching expression is one of: + * + * - A Boolean literal ("true" or "false"). + * + * - A comparison of a field (or part of a field) against a constant + * with one of the operators == != < <= > >=. + * + * - The logical AND or OR of two or more matching expressions. + * + * Literals and comparisons are called "terminal" nodes, logical AND and OR + * nodes are "nonterminal" nodes. + * + * The syntax for expressions includes a few other concepts that are not part + * of the abstract syntax tree. In these examples, x is a field, a, b, and c + * are constants, and e1 and e2 are arbitrary expressions: + * + * - Logical NOT. The parser implements NOT by inverting the sense of the + * operand: !(x == a) becomes x != a, !(e1 && e2) becomes !e1 || !e2, and + * so on. + * + * - Set membership. The parser translates x == {a, b, c} into + * x == a || x == b || x == c. + * + * - Reversed comparisons. The parser translates a < x into x > a. + * + * - Range expressions. The parser translates a < x < b into + * x > a && x < b. + */ + +#include "classifier.h" +#include "lex.h" +#include "hmap.h" +#include "list.h" +#include "match.h" +#include "meta-flow.h" + +struct ds; +struct shash; + +/* "Measurement level" of a field. See "Level of Measurement" in the large + * comment on struct expr_symbol below for more information. */ +enum expr_level { + EXPR_L_NOMINAL, + + /* Boolean values are nominal, however because of their simple nature OVN + * can allow both equality and inequality tests on them. */ + EXPR_L_BOOLEAN, + + /* Ordinal values can at least be ordered on a scale. OVN allows equality + * and inequality and relational tests on ordinal values. These are the + * fields on which OVS allows bitwise matching. */ + EXPR_L_ORDINAL +}; + +const char *expr_level_to_string(enum expr_level); + +/* A symbol. + * + * + * Name + * ==== + * + * Every symbol must have a name. To be useful, the name must satisfy the + * lexer's syntax for an identifier. + * + * + * Width + * ===== + * + * Every symbol has a width. For integer symbols, this is the number of bits + * in the value; for string symbols, this is 0. + * + * + * Types + * ===== + * + * There are three kinds of symbols: + * + * Fields: + * + * One might, for example, define a field named "vlan.tci" to refer to + * MFF_VLAN_TCI. For integer fields, 'field' specifies the referent; for + * string fields, 'field' is NULL. + * + * 'expansion' is NULL. + * + * Integer fields can be nominal or ordinal (see below). String fields are + * always nominal. + * + * Subfields: + * + * 'expansion' is a string that specifies a subfield of some larger field, + * e.g. "vlan.tci[0..11]" for a field that represents a VLAN VID. + * + * 'field' is NULL. + * + * Only ordinal fields (see below) may have subfields, and subfields are + * always ordinal. + * + * Predicates: + * + * A predicate is an arbitrary Boolean expression that can be used in an + * expression much like a 1-bit field. 'expansion' specifies the Boolean + * expression, e.g. "ip4" might expand to "eth.type == 0x800". The + * expansion of a predicate might refer to other predicates, e.g. "icmp4" + * might expand to "ip4 && ip4.proto == 1". + * + * 'field' is NULL. + * + * A predicate whose expansion refers to any nominal field or predicate + * (see below) is nominal; other predicates have Boolean level of + * measurement. + * + * + * Level of Measurement + * ==================== + * + * See http://en.wikipedia.org/wiki/Level_of_measurement for the statistical + * concept on which this classification is based. There are three levels: + * + * Ordinal: + * + * In statistics, ordinal values can be ordered on a scale. Here, we + * consider a field (or subfield) to be ordinal if its bits can be examined + * individually. This is true for the OpenFlow fields that OpenFlow or + * Open vSwitch makes "maskable". + * + * OVN supports all the usual arithmetic relations (== != < <= > >=) on + * ordinal fields and their subfields, because all of these can be + * implemented as collections of bitwise tests. + * + * Nominal: + * + * In statistics, nominal values cannot be usefully compared except for + * equality. This is true of OpenFlow port numbers, Ethernet types, and IP + * protocols are examples: all of these are just identifiers assigned + * arbitrarily with no deeper meaning. In OpenFlow and Open vSwitch, bits + * in these fields generally aren't individually addressable. + * + * OVN only supports arithmetic tests for equality on nominal fields, + * because OpenFlow and Open vSwitch provide no way for a flow to + * efficiently implement other comparisons on them. (A test for inequality + * can be sort of built out of two flows with different priorities, but OVN + * matching expressions always generate flows with a single priority.) + * + * String fields are always nominal. + * + * Boolean: + * + * A nominal field that has only two values, 0 and 1, is somewhat + * exceptional, since it is easy to support both equality and inequality + * tests on such a field: either one can be implemented as a test for 0 or + * 1. + * + * Only predicates (see above) have a Boolean level of measurement. + * + * This isn't a standard level of measurement. + * + * + * Prerequisites + * ============= + * + * Any symbol can have prerequisites, which are specified as a string giving an + * additional expression that must be true whenever the symbol is referenced. + * For example, the "icmp4.type" symbol might have prerequisite "icmp4", which + * would cause an expression "icmp4.type == 0" to be interpreted as "icmp4.type + * == 0 && icmp4", which would in turn expand to "icmp4.type == 0 && eth.type + * == 0x800 && ip4.proto == 1" (assuming "icmp4" is a predicate defined as + * suggested under "Types" above). + * + * + * Crossproducting + * =============== + * + * Ordinarily OVN is willing to consider using any field as a dimension in the + * Open vSwitch "conjunctive match" extension (see ovs-ofctl(8)). However, + * some fields can't actually be used that way because they are necessary as + * prerequisites. For example, from an expression like "tcp.src == {1,2,3} + * && tcp.dst == {4,5,6}", OVN might naturally generate flows like this: + * + * conj_id=1,actions=... + * ip,actions=conjunction(1,1/3) + * ip6,actions=conjunction(1,1/3) + * tp_src=1,actions=conjunction(1,2/3) + * tp_src=2,actions=conjunction(1,2/3) + * tp_src=2,actions=conjunction(1,2/3) + * tp_dst=4,actions=conjunction(1,3/3) + * tp_dst=5,actions=conjunction(1,3/3) + * tp_dst=6,actions=conjunction(1,3/3) + * + * but that's not valid because any flow that matches on tp_src or tp_dst must + * also match on either ip or ip6. Thus, one would mark eth.type as "must + * crossproduct", to force generating flows like this: + * + * conj_id=1,actions=... + * ip,tp_src=1,actions=conjunction(1,1/2) + * ip,tp_src=2,actions=conjunction(1,1/2) + * ip,tp_src=2,actions=conjunction(1,1/2) + * ip6,tp_src=1,actions=conjunction(1,1/2) + * ip6,tp_src=2,actions=conjunction(1,1/2) + * ip6,tp_src=2,actions=conjunction(1,1/2) + * ip,tp_dst=4,actions=conjunction(1,2/2) + * ip,tp_dst=5,actions=conjunction(1,2/2) + * ip,tp_dst=6,actions=conjunction(1,2/2) + * ip6,tp_dst=4,actions=conjunction(1,2/2) + * ip6,tp_dst=5,actions=conjunction(1,2/2) + * ip6,tp_dst=6,actions=conjunction(1,2/2) + * + * which are acceptable. + */ +struct expr_symbol { + char *name; + int width; + + const struct mf_field *field; + char *expansion; + + enum expr_level level; + + char *prereqs; + bool must_crossproduct; +}; + +struct expr_symbol *expr_symtab_add_field(struct shash *symtab, + const char *name, enum mf_field_id, + const char *prereqs, + bool must_crossproduct); +struct expr_symbol *expr_symtab_add_subfield(struct shash *symtab, + const char *name, + const char *prereqs, + const char *subfield); +struct expr_symbol *expr_symtab_add_string(struct shash *symtab, + const char *name, + const char *prereqs); +struct expr_symbol *expr_symtab_add_predicate(struct shash *symtab, + const char *name, + const char *expansion); +void expr_symtab_destroy(struct shash *symtab); + +/* Expression type. */ +enum expr_type { + EXPR_T_CMP, /* Compare symbol with constant. */ + EXPR_T_AND, /* Logical AND of 2 or more subexpressions. */ + EXPR_T_OR, /* Logical OR of 2 or more subexpressions. */ + EXPR_T_BOOLEAN, /* True or false constant. */ +}; + +/* Relational operator. */ +enum expr_relop { + EXPR_R_EQ, /* == */ + EXPR_R_NE, /* != */ + EXPR_R_LT, /* < */ + EXPR_R_LE, /* <= */ + EXPR_R_GT, /* > */ + EXPR_R_GE, /* >= */ +}; +const char *expr_relop_to_string(enum expr_relop); +bool expr_relop_from_token(enum lex_type type, enum expr_relop *relop); + +/* An abstract syntax tree for a matching expression. + * + * The expression code maintains and relies on a few important invariants: + * + * - An EXPR_T_AND or EXPR_T_OR node never has a child of the same type. + * (Any such children could be merged into their parent.) A node may + * have grandchildren of its own type. + * + * As a consequence, every nonterminal node at the same distance from the + * root of the root has the same type. + * + * - EXPR_T_AND and EXPR_T_OR nodes must have at least two children. + * + * - An EXPR_T_CMP node always has a nonzero mask, and never has a 1-bit + * in its value in a position where the mask is a 0-bit. + * + * The expr_honors_invariants() function can check invariants. */ +struct expr { + struct ovs_list node; /* In parent EXPR_T_AND or EXPR_T_OR if any. */ + enum expr_type type; /* Expression type. */ + + union { + /* EXPR_T_CMP. + * + * The symbol is on the left, e.g. "field < constant". */ + struct { + const struct expr_symbol *symbol; + enum expr_relop relop; + + union { + char *string; + struct { + union mf_subvalue value; + union mf_subvalue mask; + }; + }; + } cmp; + + /* EXPR_T_AND, EXPR_T_OR. */ + struct ovs_list andor; + + /* EXPR_T_BOOLEAN. */ + bool boolean; + }; +}; + +struct expr *expr_create_boolean(bool b); +struct expr *expr_create_andor(enum expr_type); +struct expr *expr_combine(enum expr_type, struct expr *a, struct expr *b); + +static inline struct expr * +expr_from_node(const struct ovs_list *node) +{ + return CONTAINER_OF(node, struct expr, node); +} + +void expr_format(const struct expr *, struct ds *); +void expr_print(const struct expr *); +struct expr *expr_parse(struct lexer *, const struct shash *, char **errorp); +struct expr *expr_parse_string(const char *, const struct shash *, + char **errorp); + +struct expr *expr_clone(struct expr *); +void expr_destroy(struct expr *); + +struct expr *expr_annotate(struct expr *, const struct shash *, char **errorp); +struct expr *expr_simplify(struct expr *); +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 *); + +struct expr_match { + struct hmap_node hmap_node; + struct match match; + struct cls_conjunction *conjunctions; + size_t n, allocated; +}; + +uint32_t expr_to_matches(const struct expr *, struct hmap *); + +#endif /* ovn/expr.h */ diff --git a/ovn/ovn-sb.xml b/ovn/ovn-sb.xml index 978ce11cf..2c6017b83 100644 --- a/ovn/ovn-sb.xml +++ b/ovn/ovn-sb.xml @@ -246,135 +246,268 @@

- Matching expressions have two important kinds of primary expression: - fields and constants. A field names a piece of - data or metadata. The supported fields are: + The most important components of match expression are + comparisons between symbols and + constants, e.g. ip4.dst == 192.168.0.1, + ip.proto == 6, arp.op == 1, eth.type == + 0x800. The logical AND operator && and + logical OR operator || can combine comparisons into a + larger expression.

-
    -
  • - metadata reg0 ... reg7 - xreg0 ... xreg3 -
    • -
  • inport outport queue
    • -
  • eth.src eth.dst eth.type
    • -
  • vlan.tci vlan.vid vlan.pcp vlan.present
    • -
  • ip.proto ip.dscp ip.ecn ip.ttl ip.frag
    • -
  • ip4.src ip4.dst
    • -
  • ip6.src ip6.dst ip6.label
    • -
  • arp.op arp.spa arp.tpa arp.sha arp.tha
    • -
  • tcp.src tcp.dst tcp.flags
    • -
  • udp.src udp.dst
    • -
  • sctp.src sctp.dst
    • -
  • icmp4.type icmp4.code
    • -
  • icmp6.type icmp6.code
    • -
  • nd.target nd.sll nd.tll
    • -
-

- Subfields may be addressed using a [] suffix, - e.g. tcp.src[0..7] refers to the low 8 bits of the TCP - source port. A subfield may be used in any context a field is allowed. + Matching expressions also support parentheses for grouping, the logical + NOT prefix operator !, and literals 0 and + 1 to express ``false'' or ``true,'' respectively. The + latter is useful by itself as a catch-all expression that matches every + packet.

-

- Some fields have prerequisites. OVN implicitly adds clauses to satisfy - these. For example, arp.op == 1 is equivalent to - eth.type == 0x0806 && arp.op == 1, and - tcp.src == 80 is equivalent to (eth.type == 0x0800 - || eth.type == 0x86dd) && ip.proto == 6 && tcp.src == - 80. -

+

Symbols

- Most fields have integer values. Integer constants may be expressed in - several forms: decimal integers, hexadecimal integers prefixed by - 0x, dotted-quad IPv4 addresses, IPv6 addresses in their - standard forms, and as Ethernet addresses as colon-separated hex - digits. A constant in any of these forms may be followed by a slash - and a second constant (the mask) in the same form, to form a masked - constant. IPv4 and IPv6 masks may be given as integers, to express - CIDR prefixes. + Type. Symbols have integer or string + type. Integer symbols have a width in bits.

- The inport and outport fields have string - values. The useful values are names from - the and table. + Kinds. There are three kinds of symbols:

+
    +
  • +

    + Fields. A field symbol represents a packet header or + metadata field. For example, a field + named vlan.tci might represent the VLAN TCI field in a + packet. +

    + +

    + A field symbol can have integer or string type. Integer fields can + be nominal or ordinal (see Level of Measurement, + below). +

    +
    • + +
  • +

    + Subfields. A subfield represents a subset of bits from + a larger field. For example, a field vlan.vid might + be defined as an alias for vlan.tci[0..11]. Subfields + are provided for syntactic convenience, because it is always + possible to instead refer to a subset of bits from a field + directly. +

    + +

    + Only ordinal fields (see Level of Measurement, + below) may have subfields. Subfields are always ordinal. +

    +
    • + +
  • +

    + Predicates. A predicate is shorthand for a Boolean + expression. Predicates may be used much like 1-bit fields. For + example, ip4 might expand to eth.type == + 0x800. Predicates are provided for syntactic convenience, + because it is always possible to instead specify the underlying + expression directly. +

    + +

    + A predicate whose expansion refers to any nominal field or + predicate (see Level of Measurement, below) is nominal; + other predicates have Boolean level of measurement. +

    +
    • +
+

- The available operators, from highest to lowest precedence, are: + Level of Measurement. See + http://en.wikipedia.org/wiki/Level_of_measurement for the statistical + concept on which this classification is based. There are three + levels:

    -
  • ()
    • -
  • == != < <= > >= in not in
    • -
  • !
    • -
  • &&
    • -
  • ||
    • +
  • +

    + Ordinal. In statistics, ordinal values can be ordered + on a scale. OVN considers a field (or subfield) to be ordinal if + its bits can be examined individually. This is true for the + OpenFlow fields that OpenFlow or Open vSwitch makes ``maskable.'' +

    + +

    + Any use of a nominal field may specify a single bit or a range of + bits, e.g. vlan.tci[13..15] refers to the PCP field + within the VLAN TCI, and eth.dst[40] refers to the + multicast bit in the Ethernet destination address. +

    + +

    + OVN supports all the usual arithmetic relations (==, + !=, <, <=, + >, and >=) on ordinal fields and + their subfields, because OVN can implement these in OpenFlow and + Open vSwitch as collections of bitwise tests. +

    +
    • + +
  • +

    + Nominal. In statistics, nominal values cannot be + usefully compared except for equality. This is true of OpenFlow + port numbers, Ethernet types, and IP protocols are examples: all of + these are just identifiers assigned arbitrarily with no deeper + meaning. In OpenFlow and Open vSwitch, bits in these fields + generally aren't individually addressable. +

    + +

    + OVN only supports arithmetic tests for equality on nominal fields, + because OpenFlow and Open vSwitch provide no way for a flow to + efficiently implement other comparisons on them. (A test for + inequality can be sort of built out of two flows with different + priorities, but OVN matching expressions always generate flows with + a single priority.) +

    + +

    + String fields are always nominal. +

    +
    • + +
  • +

    + Boolean. A nominal field that has only two values, 0 + and 1, is somewhat exceptional, since it is easy to support both + equality and inequality tests on such a field: either one can be + implemented as a test for 0 or 1. +

    + +

    + Only predicates (see above) have a Boolean level of measurement. +

    + +

    + This isn't a standard level of measurement. +

    +

- The () operator is used for grouping. + Prerequisites. Any symbol can have prerequisites, which are + additional condition implied by the use of the symbol. For example, + For example, icmp4.type symbol might have prerequisite + icmp4, which would cause an expression icmp4.type == + 0 to be interpreted as icmp4.type == 0 && + icmp4, which would in turn expand to icmp4.type == 0 + && eth.type == 0x800 && ip4.proto == 1 (assuming + icmp4 is a predicate defined as suggested under + Types above).

+

Relational operators

+

- The equality operator == is the most important operator. - Its operands must be a field and an optionally masked constant, in - either order. The == operator yields true when the - field's value equals the constant's value for all the bits included in - the mask. The == operator translates simply and naturally - to OpenFlow. + All of the standard relational operators ==, + !=, <, <=, + >, and >= are supported. Nominal + fields support only == and !=, and only in a + positive sense when outer ! are taken into account, + e.g. given string field inport, inport == + "eth0" and !(inport != "eth0") are acceptable, but + not inport != "eth0".

- The inequality operator != yields the inverse of - == but its syntax and use are the same. Implementation of - the inequality operator is expensive. + The implementation of == (or != when it is + negated), is more efficient than that of the other relational + operators.

+

Constants

+

- The relational operators are <, <=, >, and >=. Their - operands must be a field and a constant, in either order; the constant - must not be masked. These operators are most commonly useful for L4 - ports, e.g. tcp.src < 1024. Implementation of the - relational operators is expensive. + Integer constants may be expressed in decimal, hexadecimal prefixed by + 0x, or as dotted-quad IPv4 addresses, IPv6 addresses in + their standard forms, or Ethernet addresses as colon-separated hex + digits. A constant in any of these forms may be followed by a slash + and a second constant (the mask) in the same form, to form a masked + constant. IPv4 and IPv6 masks may be given as integers, to express + CIDR prefixes. +

+ +

+ String constants have the same syntax as quoted strings in JSON (thus, + they are Unicode strings). String constants are used for naming + logical ports. Thus, the useful values are names from the and + table.

- The set membership operator in, with syntax - ``field in { constant1, - constant2, ... }'', is syntactic sugar - for ``(field == constant1 || - field == constant2 || ...). - Conversely, ``field not in { constant1, - constant2, ... }'' is syntactic sugar - for ``(field != constant1 && + Some operators support sets of constants written inside curly braces + { ... }. Commas between elements of a set, + and after the last elements, are optional. With ==, + ``field == { constant1, + constant2, ... }'' is syntactic sugar + for ``field == constant1 || + field == constant2 || .... + Similarly, ``field != { constant1, + constant2, ... }'' is equivalent to + ``field != constant1 && field != constant2 && - ...)''. + ...''.

+

Miscellaneous

+

- The unary prefix operator ! yields its operand's inverse. + Comparisons may name the symbol or the constant first, + e.g. tcp.src == 80 and 80 == tcp.src are both + acceptable.

- The logical AND operator && yields true only if - both of its operands are true. + Tests for a range may be expressed using a syntax like 1024 <= + tcp.src <= 49151, which is equivalent to 1024 <= + tcp.src && tcp.src <= 49151.

- The logical OR operator || yields true if at least one of - its operands is true. + For a one-bit field or predicate, a mention of its name is equivalent + to symobl == 1, e.g. vlan.present + is equivalent to vlan.present == 1. The same is true for + one-bit subfields, e.g. vlan.tci[12]. There is no + technical limitation to implementing the same for ordinal fields of all + widths, but the implementation is expensive enough that the syntax + parser requires writing an explicit comparison against zero to make + mistakes less likely, e.g. in tcp.src != 0 the comparison + against 0 is required.

- Finally, the keywords true and false may also - be used in matching expressions. true is useful by itself - as a catch-all expression that matches every packet. + Operator precedence is as shown below, from highest to lowest. + There are two exceptions where parentheses are required even though the + table would suggest that they are not: && and + || require parentheses when used together, and + ! requires parentheses when applied to a relational + expression. Thus, in (eth.type == 0x800 || eth.type == 0x86dd) + && ip.proto == 6 or !(arp.op == 1), the + parentheses are mandatory.

+
    +
  • ()
    • +
  • == != < <= > >=
    • +
  • !
    • +
  • && ||
    • +
+

Comments may be introduced by //, which extends to the next new-line. Comments within a line may be bracketed by @@ -382,12 +515,28 @@ supported.

-

- (The above is pretty ambitious. It probably makes sense to initially - implement only a subset of this specification. The full specification - is written out mainly to get an idea of what a fully general matching - expression language could include.) -

+

Symbols

+ +
    +
  • + metadata reg0 ... reg7 + xreg0 ... xreg3 +
    • +
  • inport outport queue
    • +
  • eth.src eth.dst eth.type
    • +
  • vlan.tci vlan.vid vlan.pcp vlan.present
    • +
  • ip.proto ip.dscp ip.ecn ip.ttl ip.frag
    • +
  • ip4.src ip4.dst
    • +
  • ip6.src ip6.dst ip6.label
    • +
  • arp.op arp.spa arp.tpa arp.sha arp.tha
    • +
  • tcp.src tcp.dst tcp.flags
    • +
  • udp.src udp.dst
    • +
  • sctp.src sctp.dst
    • +
  • icmp4.type icmp4.code
    • +
  • icmp6.type icmp6.code
    • +
  • nd.target nd.sll nd.tll
    • +
+ @@ -418,24 +567,24 @@

-
learn
+
learn
-
conntrack
+
conntrack
-
with(field=value) { action, ... }
-
execute actions with temporary changes to fields
+
with(field=value) { action, ... }
+
execute actions with temporary changes to fields
-
dec_ttl { action, ... } { action; ...}
-
- decrement TTL; execute first set of actions if - successful, second set if TTL decrement fails -
+
dec_ttl { action, ... } { action; ...}
+
+ decrement TTL; execute first set of actions if + successful, second set if TTL decrement fails +
-
icmp_reply { action, ... }
-
generate ICMP reply from packet, execute actions
+
icmp_reply { action, ... }
+
generate ICMP reply from packet, execute actions
-
arp { action, ... }
-
generate ARP from packet, execute actions
+
arp { action, ... }
+
generate ARP from packet, execute actions

diff --git a/tests/ovn.at b/tests/ovn.at index d28a684d9..fa89cbe5d 100644 --- a/tests/ovn.at +++ b/tests/ovn.at @@ -93,3 +93,256 @@ sed 's/ =>.*//' test-cases.txt > input.txt sed 's/.* => //' test-cases.txt > expout AT_CHECK([ovstest test-ovn lex < input.txt], [0], [expout]) AT_CLEANUP + +AT_SETUP([ovn -- expression parser]) +dnl For lines without =>, input and expected output are identical. +dnl For lines with =>, input precedes => and expected output follows =>. +AT_DATA([test-cases.txt], [[ +eth.type == 0x800 +eth.type==0x800 => eth.type == 0x800 +eth.type[0..15] == 0x800 => eth.type == 0x800 + +vlan.present +vlan.present == 1 => vlan.present +!(vlan.present == 0) => vlan.present +!(vlan.present != 1) => vlan.present +!vlan.present +vlan.present == 0 => !vlan.present +vlan.present != 1 => !vlan.present +!(vlan.present == 1) => !vlan.present +!(vlan.present != 0) => !vlan.present + +eth.dst[0] +eth.dst[0] == 1 => eth.dst[0] +eth.dst[0] != 0 => eth.dst[0] +!(eth.dst[0] == 0) => eth.dst[0] +!(eth.dst[0] != 1) => eth.dst[0] + +!eth.dst[0] +eth.dst[0] == 0 => !eth.dst[0] +eth.dst[0] != 1 => !eth.dst[0] +!(eth.dst[0] == 1) => !eth.dst[0] +!(eth.dst[0] != 0) => !eth.dst[0] + +vlan.tci[12..15] == 0x3 +vlan.tci == 0x3000/0xf000 => vlan.tci[12..15] == 0x3 +vlan.tci[12..15] != 0x3 +vlan.tci != 0x3000/0xf000 => vlan.tci[12..15] != 0x3 + +!vlan.pcp => vlan.pcp == 0 +!(vlan.pcp) => vlan.pcp == 0 +vlan.pcp == 0x4 +vlan.pcp != 0x4 +vlan.pcp > 0x4 +vlan.pcp >= 0x4 +vlan.pcp < 0x4 +vlan.pcp <= 0x4 +!(vlan.pcp != 0x4) => vlan.pcp == 0x4 +!(vlan.pcp == 0x4) => vlan.pcp != 0x4 +!(vlan.pcp <= 0x4) => vlan.pcp > 0x4 +!(vlan.pcp < 0x4) => vlan.pcp >= 0x4 +!(vlan.pcp >= 0x4) => vlan.pcp < 0x4 +!(vlan.pcp > 0x4) => vlan.pcp <= 0x4 +0x4 == vlan.pcp => vlan.pcp == 0x4 +0x4 != vlan.pcp => vlan.pcp != 0x4 +0x4 < vlan.pcp => vlan.pcp > 0x4 +0x4 <= vlan.pcp => vlan.pcp >= 0x4 +0x4 > vlan.pcp => vlan.pcp < 0x4 +0x4 >= vlan.pcp => vlan.pcp <= 0x4 +!(0x4 != vlan.pcp) => vlan.pcp == 0x4 +!(0x4 == vlan.pcp) => vlan.pcp != 0x4 +!(0x4 >= vlan.pcp) => vlan.pcp > 0x4 +!(0x4 > vlan.pcp) => vlan.pcp >= 0x4 +!(0x4 <= vlan.pcp) => vlan.pcp < 0x4 +!(0x4 < vlan.pcp) => vlan.pcp <= 0x4 + +1 < vlan.pcp < 4 => vlan.pcp > 0x1 && vlan.pcp < 0x4 +1 <= vlan.pcp <= 4 => vlan.pcp >= 0x1 && vlan.pcp <= 0x4 +1 < vlan.pcp <= 4 => vlan.pcp > 0x1 && vlan.pcp <= 0x4 +1 <= vlan.pcp < 4 => vlan.pcp >= 0x1 && vlan.pcp < 0x4 +1 <= vlan.pcp <= 4 => vlan.pcp >= 0x1 && vlan.pcp <= 0x4 +4 > vlan.pcp > 1 => vlan.pcp < 0x4 && vlan.pcp > 0x1 +4 >= vlan.pcp > 1 => vlan.pcp <= 0x4 && vlan.pcp > 0x1 +4 > vlan.pcp >= 1 => vlan.pcp < 0x4 && vlan.pcp >= 0x1 +4 >= vlan.pcp >= 1 => vlan.pcp <= 0x4 && vlan.pcp >= 0x1 +!(1 < vlan.pcp < 4) => vlan.pcp <= 0x1 || vlan.pcp >= 0x4 +!(1 <= vlan.pcp <= 4) => vlan.pcp < 0x1 || vlan.pcp > 0x4 +!(1 < vlan.pcp <= 4) => vlan.pcp <= 0x1 || vlan.pcp > 0x4 +!(1 <= vlan.pcp < 4) => vlan.pcp < 0x1 || vlan.pcp >= 0x4 +!(1 <= vlan.pcp <= 4) => vlan.pcp < 0x1 || vlan.pcp > 0x4 +!(4 > vlan.pcp > 1) => vlan.pcp >= 0x4 || vlan.pcp <= 0x1 +!(4 >= vlan.pcp > 1) => vlan.pcp > 0x4 || vlan.pcp <= 0x1 +!(4 > vlan.pcp >= 1) => vlan.pcp >= 0x4 || vlan.pcp < 0x1 +!(4 >= vlan.pcp >= 1) => vlan.pcp > 0x4 || vlan.pcp < 0x1 + +vlan.pcp == {1, 2, 3, 4} => vlan.pcp == 0x1 || vlan.pcp == 0x2 || vlan.pcp == 0x3 || vlan.pcp == 0x4 +vlan.pcp == 1 || ((vlan.pcp == 2 || vlan.pcp == 3) || vlan.pcp == 4) => vlan.pcp == 0x1 || vlan.pcp == 0x2 || vlan.pcp == 0x3 || vlan.pcp == 0x4 + +vlan.pcp != {1, 2, 3, 4} => vlan.pcp != 0x1 && vlan.pcp != 0x2 && vlan.pcp != 0x3 && vlan.pcp != 0x4 +vlan.pcp == 1 && ((vlan.pcp == 2 && vlan.pcp == 3) && vlan.pcp == 4) => vlan.pcp == 0x1 && vlan.pcp == 0x2 && vlan.pcp == 0x3 && vlan.pcp == 0x4 + +vlan.pcp == 1 && !((vlan.pcp == 2 && vlan.pcp == 3) && vlan.pcp == 4) => vlan.pcp == 0x1 && (vlan.pcp != 0x2 || vlan.pcp != 0x3 || vlan.pcp != 0x4) +vlan.pcp == 1 && (!(vlan.pcp == 2 && vlan.pcp == 3) && vlan.pcp == 4) => vlan.pcp == 0x1 && (vlan.pcp != 0x2 || vlan.pcp != 0x3) && vlan.pcp == 0x4 +vlan.pcp == 1 && !(!(vlan.pcp == 2 && vlan.pcp == 3) && vlan.pcp == 4) => vlan.pcp == 0x1 && ((vlan.pcp == 0x2 && vlan.pcp == 0x3) || vlan.pcp != 0x4) + +ip4.src == {10.0.0.0/8, 192.168.0.0/16, 172.16.20.0/24, 8.8.8.8} => ip4.src[24..31] == 0xa || ip4.src[16..31] == 0xc0a8 || ip4.src[8..31] == 0xac1014 || ip4.src == 0x8080808 +ip6.src == ::1 => ip6.src == 0x1 + +ip4.src == 1.2.3.4 => ip4.src == 0x1020304 +ip4.src == ::1.2.3.4/::ffff:ffff => ip4.src == 0x1020304 +ip6.src == ::1 => ip6.src == 0x1 + +1 +0 +!1 => 0 +!0 => 1 + +inport == "eth0" +!(inport != "eth0") => inport == "eth0" + +ip4.src == "eth0" => Can't compare integer field ip4.src to string constant. +inport == 1 => Can't compare string field inport to integer constant. + +ip4.src > {1, 2, 3} => Only == and != operators may be used with value sets. +eth.type > 0x800 => Only == and != operators may be used with nominal field eth.type. +vlan.present > 0 => Only == and != operators may be used with Boolean field vlan.present. + +inport != "eth0" => Nominal field inport may only be tested for equality (taking enclosing `!' operators into account). +!(inport == "eth0") => Nominal field inport may only be tested for equality (taking enclosing `!' operators into account). +eth.type != 0x800 => Nominal field eth.type may only be tested for equality (taking enclosing `!' operators into account). +!(eth.type == 0x800) => Nominal field eth.type may only be tested for equality (taking enclosing `!' operators into account). + +123 == 123 => Syntax error at `123' expecting field name. + +123 == xyzzy => Syntax error at `xyzzy' expecting field name. +xyzzy == 1 => Syntax error at `xyzzy' expecting field name. + +inport[1] == 1 => Cannot select subfield of string field inport. + +eth.type[] == 1 => Syntax error at `@:>@' expecting small integer. +eth.type[::1] == 1 => Syntax error at `::1' expecting small integer. +eth.type[18446744073709551615] == 1 => Syntax error at `18446744073709551615' expecting small integer. + +eth.type[5!] => Syntax error at `!' expecting `@:>@'. + +eth.type[5..1] => Invalid bit range 5 to 1. + +eth.type[12..16] => Cannot select bits 12 to 16 of 16-bit field eth.type. + +eth.type[10] == 1 => Cannot select subfield of nominal field eth.type. + +eth.type => Explicit `!= 0' is required for inequality test of multibit field against 0. + +!(!(vlan.pcp)) => Explicit `!= 0' is required for inequality test of multibit field against 0. + +123 => Syntax error at end of input expecting relational operator. + +123 x => Syntax error at `x' expecting relational operator. + +{1, "eth0"} => Syntax error at `"eth0"' expecting integer. + +eth.type == xyzzy => Syntax error at `xyzzy' expecting constant. + +(1 x) => Syntax error at `x' expecting `)'. + +!0x800 != eth.type => Missing parentheses around operand of !. + +eth.type == 0x800 || eth.type == 0x86dd && ip.proto == 17 => && and || must be parenthesized when used together. + +eth.dst == {} => Syntax error at `}' expecting constant. + +eth.src > 00:00:00:00:11:11/00:00:00:00:ff:ff => Only == and != operators may be used with masked constants. Consider using subfields instead (e.g. eth.src[0..15] > 0x1111 in place of eth.src > 00:00:00:00:11:11/00:00:00:00:ff:ff). + +ip4.src == ::1 => Cannot compare 128-bit constant against 32-bit field ip4.src. + +1 == eth.type == 2 => Range expressions must have the form `x < field < y' or `x > field > y', with each `<' optionally replaced by `<=' or `>' by `>='). +]]) +sed 's/ =>.*//' test-cases.txt > input.txt +sed 's/.* => //' test-cases.txt > expout +AT_CHECK([ovstest test-ovn parse-expr < input.txt], [0], [expout]) +AT_CLEANUP + +AT_SETUP([ovn -- expression annotation]) +dnl Input precedes =>, expected output follows =>. +AT_DATA([test-cases.txt], [[ +ip4.src == 1.2.3.4 => ip4.src == 0x1020304 && eth.type == 0x800 +ip4.src != 1.2.3.4 => ip4.src != 0x1020304 && eth.type == 0x800 +ip.proto == 123 => ip.proto == 0x7b && (eth.type == 0x800 || eth.type == 0x86dd) +ip.proto == {123, 234} => (ip.proto == 0x7b && (eth.type == 0x800 || eth.type == 0x86dd)) || (ip.proto == 0xea && (eth.type == 0x800 || eth.type == 0x86dd)) +ip4.src == 1.2.3.4 && ip4.dst == 5.6.7.8 => ip4.src == 0x1020304 && eth.type == 0x800 && ip4.dst == 0x5060708 && eth.type == 0x800 + +ip => eth.type == 0x800 || eth.type == 0x86dd +ip == 1 => eth.type == 0x800 || eth.type == 0x86dd +ip[0] == 1 => eth.type == 0x800 || eth.type == 0x86dd +ip > 0 => Only == and != operators may be used with nominal field ip. +!ip => Nominal predicate ip may only be tested positively, e.g. `ip' or `ip == 1' but not `!ip' or `ip == 0'. +ip == 0 => Nominal predicate ip may only be tested positively, e.g. `ip' or `ip == 1' but not `!ip' or `ip == 0'. + +vlan.present => vlan.tci[12] +!vlan.present => !vlan.tci[12] + +!vlan.pcp => vlan.tci[13..15] == 0 && vlan.tci[12] +vlan.pcp == 1 && vlan.vid == 2 => vlan.tci[13..15] == 0x1 && vlan.tci[12] && vlan.tci[0..11] == 0x2 && vlan.tci[12] +!reg0 && !reg1 && !reg2 && !reg3 => xreg0[32..63] == 0 && xreg0[0..31] == 0 && xreg1[32..63] == 0 && xreg1[0..31] == 0 + +ip.first_frag => ip.frag[0] && (eth.type == 0x800 || eth.type == 0x86dd) && (!ip.frag[1] || (eth.type != 0x800 && eth.type != 0x86dd)) +!ip.first_frag => !ip.frag[0] || (eth.type != 0x800 && eth.type != 0x86dd) || (ip.frag[1] && (eth.type == 0x800 || eth.type == 0x86dd)) +ip.later_frag => ip.frag[1] && (eth.type == 0x800 || eth.type == 0x86dd) + +bad_prereq != 0 => Error parsing expression `xyzzy' encountered as prerequisite or predicate of initial expression: Syntax error at `xyzzy' expecting field name. +self_recurse != 0 => Error parsing expression `self_recurse != 0' encountered as prerequisite or predicate of initial expression: Recursive expansion of symbol `self_recurse'. +mutual_recurse_1 != 0 => Error parsing expression `mutual_recurse_2 != 0' encountered as prerequisite or predicate of initial expression: Error parsing expression `mutual_recurse_1 != 0' encountered as prerequisite or predicate of initial expression: Recursive expansion of symbol `mutual_recurse_1'. +mutual_recurse_2 != 0 => Error parsing expression `mutual_recurse_1 != 0' encountered as prerequisite or predicate of initial expression: Error parsing expression `mutual_recurse_2 != 0' encountered as prerequisite or predicate of initial expression: Recursive expansion of symbol `mutual_recurse_2'. +]]) +sed 's/ =>.*//' test-cases.txt > input.txt +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_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 == != < <= > >=. +]) +AT_CLEANUP + +AT_SETUP([ovn -- expression conversion (2)]) +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 == != < <= > >=. +]) +AT_CLEANUP + +AT_SETUP([ovn -- expression conversion (3)]) +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 == != < <= > >=. +]) +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_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_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_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_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_CLEANUP diff --git a/tests/test-ovn.c b/tests/test-ovn.c index b2f183829..a6d8b8000 100644 --- a/tests/test-ovn.c +++ b/tests/test-ovn.c @@ -16,15 +16,39 @@ #include #include "command-line.h" +#include #include +#include #include "dynamic-string.h" #include "fatal-signal.h" #include "match.h" +#include "ovn/lib/expr.h" #include "ovn/lib/lex.h" +#include "ovs-thread.h" #include "ovstest.h" +#include "shash.h" #include "util.h" #include "openvswitch/vlog.h" +/* --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; + +/* --bits: Number of bits per variable, in exhaustive test. */ +static int test_bits = 3; + +/* --operation: The operation to test, in exhaustive test. */ +static enum { OP_CONVERT, OP_SIMPLIFY, OP_NORMALIZE, OP_FLOW } operation + = OP_FLOW; + +/* --parallel: Number of parallel processes to use in test. */ +static int test_parallel = 1; + +/* -m, --more: Message verbosity */ +static int verbosity; + static void compare_token(const struct lex_token *a, const struct lex_token *b) { @@ -102,13 +126,1165 @@ test_lex(struct ovs_cmdl_context *ctx OVS_UNUSED) ds_destroy(&output); } +static void +create_symtab(struct shash *symtab) +{ + shash_init(symtab); + + expr_symtab_add_string(symtab, "inport", NULL); + expr_symtab_add_string(symtab, "outport", NULL); + + 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_XREG2, NULL, false); + expr_symtab_add_field(symtab, "xreg3", MFF_XREG3, NULL, false); + + expr_symtab_add_subfield(symtab, "reg0", NULL, "xreg0[32..63]"); + expr_symtab_add_subfield(symtab, "reg1", NULL, "xreg0[0..31]"); + expr_symtab_add_subfield(symtab, "reg2", NULL, "xreg1[32..63]"); + expr_symtab_add_subfield(symtab, "reg3", NULL, "xreg1[0..31]"); + expr_symtab_add_subfield(symtab, "reg4", NULL, "xreg2[32..63]"); + expr_symtab_add_subfield(symtab, "reg5", NULL, "xreg2[0..31]"); + expr_symtab_add_subfield(symtab, "reg6", NULL, "xreg3[32..63]"); + expr_symtab_add_subfield(symtab, "reg7", NULL, "xreg3[0..31]"); + + expr_symtab_add_field(symtab, "eth.src", MFF_ETH_SRC, NULL, false); + expr_symtab_add_field(symtab, "eth.dst", MFF_ETH_DST, NULL, false); + expr_symtab_add_field(symtab, "eth.type", MFF_ETH_TYPE, NULL, true); + + expr_symtab_add_field(symtab, "vlan.tci", MFF_VLAN_TCI, NULL, false); + expr_symtab_add_predicate(symtab, "vlan.present", "vlan.tci[12]"); + expr_symtab_add_subfield(symtab, "vlan.pcp", "vlan.present", + "vlan.tci[13..15]"); + expr_symtab_add_subfield(symtab, "vlan.vid", "vlan.present", + "vlan.tci[0..11]"); + + expr_symtab_add_predicate(symtab, "ip4", "eth.type == 0x800"); + expr_symtab_add_predicate(symtab, "ip6", "eth.type == 0x86dd"); + expr_symtab_add_predicate(symtab, "ip", "ip4 || ip6"); + expr_symtab_add_field(symtab, "ip.proto", MFF_IP_PROTO, "ip", true); + expr_symtab_add_field(symtab, "ip.dscp", MFF_IP_DSCP, "ip", false); + expr_symtab_add_field(symtab, "ip.ecn", MFF_IP_ECN, "ip", false); + expr_symtab_add_field(symtab, "ip.ttl", MFF_IP_TTL, "ip", false); + + expr_symtab_add_field(symtab, "ip4.src", MFF_IPV4_SRC, "ip4", false); + expr_symtab_add_field(symtab, "ip4.dst", MFF_IPV4_DST, "ip4", false); + + expr_symtab_add_predicate(symtab, "icmp4", "ip4 && ip.proto == 1"); + expr_symtab_add_field(symtab, "icmp4.type", MFF_ICMPV4_TYPE, "icmp4", + false); + expr_symtab_add_field(symtab, "icmp4.code", MFF_ICMPV4_CODE, "icmp4", + false); + + expr_symtab_add_field(symtab, "ip6.src", MFF_IPV6_SRC, "ip6", false); + expr_symtab_add_field(symtab, "ip6.dst", MFF_IPV6_DST, "ip6", false); + expr_symtab_add_field(symtab, "ip6.label", MFF_IPV6_LABEL, "ip6", false); + + expr_symtab_add_predicate(symtab, "icmp6", "ip6 && ip.proto == 58"); + expr_symtab_add_field(symtab, "icmp6.type", MFF_ICMPV6_TYPE, "icmp6", + true); + expr_symtab_add_field(symtab, "icmp6.code", MFF_ICMPV6_CODE, "icmp6", + true); + + expr_symtab_add_predicate(symtab, "icmp", "icmp4 || icmp6"); + + expr_symtab_add_field(symtab, "ip.frag", MFF_IP_FRAG, "ip", false); + expr_symtab_add_predicate(symtab, "ip.is_frag", "ip.frag[0]"); + expr_symtab_add_predicate(symtab, "ip.later_frag", "ip.frag[1]"); + expr_symtab_add_predicate(symtab, "ip.first_frag", "ip.is_frag && !ip.later_frag"); + + expr_symtab_add_predicate(symtab, "arp", "eth.type == 0x806"); + expr_symtab_add_field(symtab, "arp.op", MFF_ARP_OP, "arp", false); + expr_symtab_add_field(symtab, "arp.spa", MFF_ARP_SPA, "arp", false); + expr_symtab_add_field(symtab, "arp.sha", MFF_ARP_SHA, "arp", false); + expr_symtab_add_field(symtab, "arp.tpa", MFF_ARP_TPA, "arp", false); + expr_symtab_add_field(symtab, "arp.tha", MFF_ARP_THA, "arp", false); + + expr_symtab_add_predicate(symtab, "nd", "icmp6.type == {135, 136} && icmp6.code == 0"); + expr_symtab_add_field(symtab, "nd.target", MFF_ND_TARGET, "nd", false); + expr_symtab_add_field(symtab, "nd.sll", MFF_ND_SLL, + "nd && icmp6.type == 135", false); + expr_symtab_add_field(symtab, "nd.tll", MFF_ND_TLL, + "nd && icmp6.type == 136", false); + + expr_symtab_add_predicate(symtab, "tcp", "ip.proto == 6"); + expr_symtab_add_field(symtab, "tcp.src", MFF_TCP_SRC, "tcp", false); + expr_symtab_add_field(symtab, "tcp.dst", MFF_TCP_DST, "tcp", false); + expr_symtab_add_field(symtab, "tcp.flags", MFF_TCP_FLAGS, "tcp", false); + + expr_symtab_add_predicate(symtab, "udp", "ip.proto == 17"); + expr_symtab_add_field(symtab, "udp.src", MFF_UDP_SRC, "udp", false); + expr_symtab_add_field(symtab, "udp.dst", MFF_UDP_DST, "udp", false); + + expr_symtab_add_predicate(symtab, "sctp", "ip.proto == 132"); + expr_symtab_add_field(symtab, "sctp.src", MFF_SCTP_SRC, "sctp", false); + expr_symtab_add_field(symtab, "sctp.dst", MFF_SCTP_DST, "sctp", false); + + /* For negative testing. */ + expr_symtab_add_field(symtab, "bad_prereq", MFF_XREG0, "xyzzy", false); + expr_symtab_add_field(symtab, "self_recurse", MFF_XREG0, + "self_recurse != 0", false); + expr_symtab_add_field(symtab, "mutual_recurse_1", MFF_XREG0, + "mutual_recurse_2 != 0", false); + expr_symtab_add_field(symtab, "mutual_recurse_2", MFF_XREG0, + "mutual_recurse_1 != 0", false); +} + +static void +test_parse_expr__(int steps) +{ + struct shash symtab; + struct ds input; + + create_symtab(&symtab); + ds_init(&input); + while (!ds_get_test_line(&input, stdin)) { + struct expr *expr; + char *error; + + expr = expr_parse_string(ds_cstr(&input), &symtab, &error); + if (!error && steps > 0) { + expr = expr_annotate(expr, &symtab, &error); + } + if (!error) { + if (steps > 1) { + expr = expr_simplify(expr); + } + if (steps > 2) { + expr = expr_normalize(expr); + ovs_assert(expr_is_normalized(expr)); + } + } + if (!error) { + struct ds output = DS_EMPTY_INITIALIZER; + expr_format(expr, &output); + puts(ds_cstr(&output)); + ds_destroy(&output); + } else { + puts(error); + free(error); + } + expr_destroy(expr); + } + ds_destroy(&input); + + expr_symtab_destroy(&symtab); + shash_destroy(&symtab); +} + +static void +test_parse_expr(struct ovs_cmdl_context *ctx OVS_UNUSED) +{ + test_parse_expr__(0); +} + +static void +test_annotate_expr(struct ovs_cmdl_context *ctx OVS_UNUSED) +{ + test_parse_expr__(1); +} + +static void +test_simplify_expr(struct ovs_cmdl_context *ctx OVS_UNUSED) +{ + test_parse_expr__(2); +} + +static void +test_normalize_expr(struct ovs_cmdl_context *ctx OVS_UNUSED) +{ + test_parse_expr__(3); +} + +/* 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 = 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; + + 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(); + } +} + +/* 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) +{ + 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(); + } +} + +static void +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 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]"); + + ds_init(&input); + while (!ds_get_test_line(&input, stdin)) { + struct expr *expr; + char *error; + + expr = expr_parse_string(ds_cstr(&input), &symtab, &error); + if (!error) { + expr = expr_annotate(expr, &symtab, &error); + } + if (!error) { + printf("%d\n", evaluate_expr(expr, subst, 3)); + } else { + puts(error); + free(error); + } + expr_destroy(expr); + } + ds_destroy(&input); + + expr_symtab_destroy(&symtab); + shash_destroy(&symtab); +} + +/* Compositions. + * + * The "compositions" of a positive integer N are all of the ways that one can + * add up positive integers to sum to N. For example, the compositions of 3 + * are 3, 2+1, 1+2, and 1+1+1. + * + * We use compositions to find all the ways to break up N terms of a Boolean + * expression into subexpressions. Suppose we want to generate all expressions + * with 3 terms. The compositions of 3 (ignoring 3 itself) provide the + * possibilities (x && x) || x, x || (x && x), and x || x || x. (Of course one + * can exchange && for || in each case.) One must recursively compose the + * sub-expressions whose values are 3 or greater; that is what the "tree shape" + * concept later covers. + * + * To iterate through all compositions of, e.g., 5: + * + * unsigned int state; + * int s[5]; + * int n; + * + * for (n = first_composition(ARRAY_SIZE(s), &state, s); n > 0; + * n = next_composition(&state, s, n)) { + * // Do something with composition 's' with 'n' elements. + * } + * + * Algorithm from D. E. Knuth, _The Art of Computer Programming, Vol. 4A: + * Combinatorial Algorithms, Part 1_, section 7.2.1.1, answer to exercise + * 12(a). + */ + +/* Begins iteration through the compositions of 'n'. Initializes 's' to the + * number of elements in the first composition of 'n' and returns that number + * of elements. The first composition in fact is always 'n' itself, so the + * return value will be 1. + * + * Initializes '*state' to some internal state information. The caller must + * maintain this state (and 's') for use by next_composition(). + * + * 's' must have room for at least 'n' elements. */ +static int +first_composition(int n, unsigned int *state, int s[]) +{ + *state = 0; + s[0] = n; + return 1; +} + +/* Advances 's', with 'sn' elements, to the next composition and returns the + * number of elements in this new composition, or 0 if no compositions are + * left. 'state' is the same internal state passed to first_composition(). */ +static int +next_composition(unsigned int *state, int s[], int sn) +{ + int j = sn - 1; + if (++*state & 1) { + if (s[j] > 1) { + s[j]--; + s[j + 1] = 1; + j++; + } else { + j--; + s[j]++; + } + } else { + if (s[j - 1] > 1) { + s[j - 1]--; + s[j + 1] = s[j]; + s[j] = 1; + j++; + } else { + j--; + s[j] = s[j + 1]; + s[j - 1]++; + if (!j) { + return 0; + } + } + } + return j + 1; +} + +static void +test_composition(struct ovs_cmdl_context *ctx) +{ + int n = atoi(ctx->argv[1]); + unsigned int state; + int s[50]; + + for (int sn = first_composition(n, &state, s); sn; + sn = next_composition(&state, s, sn)) { + for (int i = 0; i < sn; i++) { + printf("%d%c", s[i], i == sn - 1 ? '\n' : ' '); + } + } +} + +/* Tree shapes. + * + * This code generates all possible Boolean expressions with a specified number + * of terms N (equivalent to the number of external nodes in a tree). + * + * See test_tree_shape() for a simple example. */ + +/* An array of these structures describes the shape of a tree. + * + * A single element of struct tree_shape describes a single node in the tree. + * The node has 'sn' direct children. From left to right, for i in 0...sn-1, + * s[i] is 1 if the child is a leaf node, otherwise the child is a subtree and + * s[i] is the number of leaf nodes within that subtree. In the latter case, + * the subtree is described by another struct tree_shape within the enclosing + * array. The tree_shapes are ordered in the array in in-order. + */ +struct tree_shape { + unsigned int state; + int s[50]; + int sn; +}; + +static int +init_tree_shape__(struct tree_shape ts[], int n) +{ + if (n <= 2) { + return 0; + } + + int n_tses = 1; + /* Skip the first composition intentionally. */ + ts->sn = first_composition(n, &ts->state, ts->s); + ts->sn = next_composition(&ts->state, ts->s, ts->sn); + for (int i = 0; i < ts->sn; i++) { + n_tses += init_tree_shape__(&ts[n_tses], ts->s[i]); + } + return n_tses; +} + +/* Initializes 'ts[]' as the first in the set of all of possible shapes of + * trees with 'n' leaves. Returns the number of "struct tree_shape"s in the + * first tree shape. */ +static int +init_tree_shape(struct tree_shape ts[], int n) +{ + switch (n) { + case 1: + ts->sn = 1; + ts->s[0] = 1; + return 1; + case 2: + ts->sn = 2; + ts->s[0] = 1; + ts->s[1] = 1; + return 1; + default: + return init_tree_shape__(ts, n); + } +} + +/* Advances 'ts', which currently has 'n_tses' elements, to the next possible + * tree shape with the number of leaves passed to init_tree_shape(). Returns + * the number of "struct tree_shape"s in the next shape, or 0 if all tree + * shapes have been visited. */ +static int +next_tree_shape(struct tree_shape ts[], int n_tses) +{ + if (n_tses == 1 && ts->sn == 2 && ts->s[0] == 1 && ts->s[1] == 1) { + return 0; + } + while (n_tses > 0) { + struct tree_shape *p = &ts[n_tses - 1]; + p->sn = p->sn > 1 ? next_composition(&p->state, p->s, p->sn) : 0; + if (p->sn) { + for (int i = 0; i < p->sn; i++) { + n_tses += init_tree_shape__(&ts[n_tses], p->s[i]); + } + break; + } + n_tses--; + } + return n_tses; +} + +static void +print_tree_shape(const struct tree_shape ts[], int n_tses) +{ + for (int i = 0; i < n_tses; i++) { + if (i) { + printf(", "); + } + for (int j = 0; j < ts[i].sn; j++) { + int k = ts[i].s[j]; + if (k > 9) { + printf("(%d)", k); + } else { + printf("%d", k); + } + } + } +} + +static void +test_tree_shape(struct ovs_cmdl_context *ctx) +{ + int n = atoi(ctx->argv[1]); + struct tree_shape ts[50]; + int n_tses; + + for (n_tses = init_tree_shape(ts, n); n_tses; + n_tses = next_tree_shape(ts, n_tses)) { + print_tree_shape(ts, n_tses); + putchar('\n'); + } +} + +/* Iteration through all possible terminal expressions (e.g. EXPR_T_CMP and + * EXPR_T_BOOLEAN expressions). + * + * Given a tree shape, this allows the code to try all possible ways to plug in + * terms. + * + * Example use: + * + * struct expr terminal; + * const struct expr_symbol *vars = ...; + * int n_vars = ...; + * int n_bits = ...; + * + * init_terminal(&terminal, vars[0]); + * do { + * // Something with 'terminal'. + * } while (next_terminal(&terminal, vars, n_vars, n_bits)); + */ + +/* 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) +{ + 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); +} + +/* Returns 'x' with the rightmost contiguous string of 1s changed to 0s, + * e.g. 01011100 => 01000000. See H. S. Warren, Jr., _Hacker's Delight_, 2nd + * ed., section 2-1. */ +static unsigned int +turn_off_rightmost_1s(unsigned int x) +{ + return ((x & -x) + x) & x; +} + +static const struct expr_symbol * +next_var(const struct expr_symbol *symbol, + const struct expr_symbol *vars[], int n_vars) +{ + for (int i = 0; i < n_vars; i++) { + if (symbol == vars[i]) { + return i + 1 >= n_vars ? NULL : vars[i + 1]; + } + } + OVS_NOT_REACHED(); +} + +static enum expr_relop +next_relop(enum expr_relop relop) +{ + unsigned int remaining_relops = test_relops & ~((1u << (relop + 1)) - 1); + return (remaining_relops + ? rightmost_1bit_idx(remaining_relops) + : rightmost_1bit_idx(test_relops)); +} + +/* 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) +{ + if (expr->type == EXPR_T_BOOLEAN) { + if (expr->boolean) { + return false; + } else { + expr->boolean = true; + return true; + } + } + + unsigned int next; + + next = (ntohll(expr->cmp.value.integer) + + (ntohll(expr->cmp.mask.integer) << n_bits)); + for (;;) { + next++; + unsigned m = next >> n_bits; + unsigned v = next & ((1u << n_bits) - 1); + if (next >= (1u << (2 * n_bits))) { + 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); + if (!expr->cmp.symbol) { + expr->type = EXPR_T_BOOLEAN; + expr->boolean = false; + return true; + } + } + next = 0; + } else if (m == 0) { + /* Skip: empty mask is pathological. */ + } else if (v & ~m) { + /* Skip: 1-bits in value correspond to 0-bits in mask. */ + } else if (turn_off_rightmost_1s(m) + && (expr->cmp.relop != EXPR_R_EQ && + expr->cmp.relop != EXPR_R_NE)) { + /* Skip: can't have discontiguous mask for > >= < <=. */ + } else { + expr->cmp.value.integer = htonll(v); + expr->cmp.mask.integer = htonll(m); + return true; + } + } +} + +static struct expr * +make_terminal(struct expr ***terminalp) +{ + struct expr *e = expr_create_boolean(true); + **terminalp = e; + (*terminalp)++; + return e; +} + +static struct expr * +build_simple_tree(enum expr_type type, int n, struct expr ***terminalp) +{ + if (n == 2) { + struct expr *e = expr_create_andor(type); + for (int i = 0; i < 2; i++) { + struct expr *sub = make_terminal(terminalp); + list_push_back(&e->andor, &sub->node); + } + return e; + } else if (n == 1) { + return make_terminal(terminalp); + } else { + OVS_NOT_REACHED(); + } +} + +static struct expr * +build_tree_shape(enum expr_type type, const struct tree_shape **tsp, + struct expr ***terminalp) +{ + const struct tree_shape *ts = *tsp; + (*tsp)++; + + struct expr *e = expr_create_andor(type); + enum expr_type t = type == EXPR_T_AND ? EXPR_T_OR : EXPR_T_AND; + for (int i = 0; i < ts->sn; i++) { + struct expr *sub = (ts->s[i] > 2 + ? build_tree_shape(t, tsp, terminalp) + : build_simple_tree(t, ts->s[i], terminalp)); + list_push_back(&e->andor, &sub->node); + } + return e; +} + +struct test_rule { + struct cls_rule cr; +}; + +static void +free_rule(struct test_rule *test_rule) +{ + cls_rule_destroy(&test_rule->cr); + free(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) +{ + 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]); + } + + struct ds s = DS_EMPTY_INITIALIZER; + struct flow f; + memset(&f, 0, sizeof f); + for (;;) { + for (int i = n_terminals - 1; ; i--) { + if (!i) { + ds_destroy(&s); + return n_tested; + } + if (next_terminal(terminals[i], vars, n_vars, n_bits)) { + break; + } + init_terminal(terminals[i], vars[0]); + } + ovs_assert(expr_honors_invariants(expr)); + + n_tested++; + + struct expr *modified; + if (operation == OP_CONVERT) { + ds_clear(&s); + expr_format(expr, &s); + + char *error; + modified = expr_parse_string(ds_cstr(&s), symtab, &error); + if (error) { + fprintf(stderr, "%s fails to parse (%s)\n", + ds_cstr(&s), error); + exit(EXIT_FAILURE); + } + } else if (operation >= OP_SIMPLIFY) { + modified = expr_simplify(expr_clone(expr)); + ovs_assert(expr_honors_invariants(modified)); + + if (operation >= OP_NORMALIZE) { + modified = expr_normalize(modified); + ovs_assert(expr_is_normalized(modified)); + } + } + + struct hmap matches; + struct classifier cls; + if (operation >= OP_FLOW) { + struct expr_match *m; + struct test_rule *test_rule; + uint32_t n_conjs; + + n_conjs = expr_to_matches(modified, &matches); + + classifier_init(&cls, NULL); + HMAP_FOR_EACH (m, hmap_node, &matches) { + test_rule = xmalloc(sizeof *test_rule); + cls_rule_init(&test_rule->cr, &m->match, 0); + classifier_insert(&cls, &test_rule->cr, m->conjunctions, m->n); + } + for (uint32_t conj_id = 1; conj_id <= n_conjs; conj_id++) { + struct match match; + match_init_catchall(&match); + match_set_conj_id(&match, conj_id); + + test_rule = xmalloc(sizeof *test_rule); + cls_rule_init(&test_rule->cr, &match, 0); + classifier_insert(&cls, &test_rule->cr, NULL, 0); + } + } + for (int subst = 0; subst < 1 << (n_bits * n_vars); subst++) { + bool expected = evaluate_expr(expr, subst, n_bits); + bool actual = evaluate_expr(modified, subst, n_bits); + if (actual != expected) { + struct ds expr_s, modified_s; + + ds_init(&expr_s); + expr_format(expr, &expr_s); + + ds_init(&modified_s); + expr_format(modified, &modified_s); + + fprintf(stderr, + "%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++) { + if (i > 0) { + fputs(",", stderr); + } + fprintf(stderr, " %c = 0x%x", 'a' + i, + (subst >> (n_bits * i)) & var_mask); + } + putc('\n', stderr); + exit(EXIT_FAILURE); + } + + if (operation >= OP_FLOW) { + for (int i = 0; i < n_vars; i++) { + f.regs[i] = (subst >> (i * n_bits)) & var_mask; + } + bool found = classifier_lookup(&cls, &f, NULL) != NULL; + if (expected != found) { + struct ds expr_s, modified_s; + + ds_init(&expr_s); + expr_format(expr, &expr_s); + + ds_init(&modified_s); + expr_format(modified, &modified_s); + + 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++) { + if (i > 0) { + fputs(",", stderr); + } + fprintf(stderr, " %c = 0x%x", 'a' + i, + (subst >> (n_bits * i)) & var_mask); + } + fputs(".\n", stderr); + + fprintf(stderr, "Converted to classifier:\n"); + + struct expr_match *m; + HMAP_FOR_EACH (m, hmap_node, &matches) { + char *s = match_to_string(&m->match, + OFP_DEFAULT_PRIORITY); + fputs(s, stderr); + if (m->n) { + for (int i = 0; i < m->n; i++) { + const struct cls_conjunction *c + = &m->conjunctions[i]; + fprintf(stderr, + "%c conjunction(%"PRIu32", %d/%d)", + i == 0 ? ':' : ',', + c->id, c->clause, c->n_clauses); + } + } + putc('\n', stderr); + } + + fprintf(stderr, + "However, %s flow was found in the classifier.\n", + found ? "a" : "no"); + exit(EXIT_FAILURE); + } + } + } + if (operation >= OP_FLOW) { + struct expr_match *m, *n; + struct test_rule *test_rule; + + CLS_FOR_EACH (test_rule, cr, &cls) { + classifier_remove(&cls, &test_rule->cr); + ovsrcu_postpone(free_rule, test_rule); + } + classifier_destroy(&cls); + ovsrcu_quiesce(); + + HMAP_FOR_EACH_SAFE (m, n, hmap_node, &matches) { + hmap_remove(&matches, &m->hmap_node); + free(m->conjunctions); + free(m); + } + hmap_destroy(&matches); + } + expr_destroy(modified); + } +} + +#ifndef _WIN32 +static void +wait_pid(pid_t *pids, int *n) +{ + int status; + pid_t pid; + + pid = waitpid(WAIT_ANY, &status, 0); + if (pid < 0) { + ovs_fatal(errno, "waitpid failed"); + } else if (WIFEXITED(status)) { + if (WEXITSTATUS(status)) { + exit(WEXITSTATUS(status)); + } + } else if (WIFSIGNALED(status)) { + raise(WTERMSIG(status)); + exit(1); + } else { + OVS_NOT_REACHED(); + } + + for (int i = 0; i < *n; i++) { + if (pids[i] == pid) { + pids[i] = pids[--*n]; + return; + } + } + ovs_fatal(0, "waitpid returned unknown child"); +} +#endif + +static void +test_exhaustive(struct ovs_cmdl_context *ctx OVS_UNUSED) +{ + int n_terminals = atoi(ctx->argv[1]); + struct tree_shape ts[50]; + int n_tses; + + struct shash symtab; + const struct expr_symbol *vars[4]; + + ovs_assert(test_vars <= ARRAY_SIZE(vars)); + + 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); + } + +#ifndef _WIN32 + pid_t *children = xmalloc(test_parallel * sizeof *children); + int n_children = 0; +#endif + + int n_tested = 0; + for (int i = 0; i < 2; i++) { + enum expr_type base_type = i ? EXPR_T_OR : EXPR_T_AND; + + for (n_tses = init_tree_shape(ts, n_terminals); n_tses; + n_tses = next_tree_shape(ts, n_tses)) { + const struct tree_shape *tsp = ts; + struct expr *terminals[50]; + struct expr **terminalp = terminals; + struct expr *expr = build_tree_shape(base_type, &tsp, &terminalp); + ovs_assert(terminalp == &terminals[n_terminals]); + + if (verbosity > 0) { + print_tree_shape(ts, n_tses); + printf(": "); + struct ds s = DS_EMPTY_INITIALIZER; + expr_format(expr, &s); + puts(ds_cstr(&s)); + ds_destroy(&s); + } + +#ifndef _WIN32 + if (test_parallel > 1) { + pid_t pid = xfork(); + if (!pid) { + test_tree_shape_exhaustively(expr, &symtab, + terminals, n_terminals, + vars, test_vars, test_bits); + expr_destroy(expr); + exit(0); + } else { + if (n_children >= test_parallel) { + wait_pid(children, &n_children); + } + children[n_children++] = pid; + } + } else +#endif + { + n_tested += test_tree_shape_exhaustively( + expr, &symtab, terminals, n_terminals, + vars, test_vars, test_bits); + } + expr_destroy(expr); + } + } +#ifndef _WIN32 + while (n_children > 0) { + wait_pid(children, &n_children); + } + free(children); +#endif + + printf("Tested "); + switch (operation) { + case OP_CONVERT: + printf("converting"); + break; + case OP_SIMPLIFY: + printf("simplifying"); + break; + case OP_NORMALIZE: + printf("normalizing"); + break; + case OP_FLOW: + printf("converting to flows"); + break; + } + if (n_tested) { + printf(" %d expressions of %d terminals", n_tested, n_terminals); + } 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)); + } + printf(".\n"); + + expr_symtab_destroy(&symtab); + shash_destroy(&symtab); +} + +static unsigned int +parse_relops(const char *s) +{ + unsigned int relops = 0; + struct lexer lexer; + + lexer_init(&lexer, s); + lexer_get(&lexer); + do { + enum expr_relop relop; + + if (expr_relop_from_token(lexer.token.type, &relop)) { + relops |= 1u << relop; + lexer_get(&lexer); + } else { + ovs_fatal(0, "%s: relational operator expected at `%.*s'", + s, (int) (lexer.input - lexer.start), lexer.start); + } + lexer_match(&lexer, LEX_T_COMMA); + } while (lexer.token.type != LEX_T_END); + lexer_destroy(&lexer); + + return relops; +} + +static void +usage(void) +{ + printf("\ +%s: OVN test utility\n\ +usage: test-ovn %s [OPTIONS] COMMAND [ARG...]\n\ +\n\ +lex\n\ + Lexically analyzes OVN input from stdin and print them back on stdout.\n\ +\n\ +parse-expr\n\ +annotate-expr\n\ +simplify-expr\n\ +normalize-expr\n\ + Parses OVN expressions from stdin and print them back on stdout after\n\ + differing degrees of analysis. Available fields are based on packet\n\ + headers.\n\ +\n\ +evaluate-expr A B C\n\ + Parses OVN expressions from stdin, evaluate them with assigned values,\n\ + and print the results on stdout. Available fields are 'a', 'b', and 'c'\n\ + of 3 bits each. A, B, and C should be in the range 0 to 7.\n\ +\n\ +composition N\n\ + Prints all the compositions of N on stdout.\n\ +\n\ +tree-shape N\n\ + Prints all the tree shapes with N terminals on stdout.\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\ + --operation=OPERATION Operation to test, one of: convert, simplify,\n\ + normalize, flow. Default: flow. 'normalize' includes 'simplify',\n\ + 'flow' includes 'simplify' and 'normaize'.\n\ + --parallel=N Number of processes to use in parallel, default 1.\n\ +", + program_name, program_name); + exit(EXIT_SUCCESS); +} + static void test_ovn_main(int argc, char *argv[]) { 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); + + if (c == -1) { + break; + } + switch (c) { + case OPT_RELOPS: + 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"); + } + break; + + case OPT_BITS: + test_bits = atoi(optarg); + if (test_bits < 1 || test_bits > 3) { + ovs_fatal(0, "number of bits must be between 1 and 3"); + } + break; + + case OPT_OPERATION: + if (!strcmp(optarg, "convert")) { + operation = OP_CONVERT; + } else if (!strcmp(optarg, "simplify")) { + operation = OP_SIMPLIFY; + } else if (!strcmp(optarg, "normalize")) { + operation = OP_NORMALIZE; + } else if (!strcmp(optarg, "flow")) { + operation = OP_FLOW; + } else { + ovs_fatal(0, "%s: unknown operation", optarg); + } + break; + + case OPT_PARALLEL: + test_parallel = atoi(optarg); + break; + + case 'm': + verbosity++; + break; + + case 'h': + usage(); + + case '?': + exit(1); + + default: + abort(); + } + } + static const struct ovs_cmdl_command commands[] = { {"lex", NULL, 0, 0, test_lex}, + {"parse-expr", NULL, 0, 0, test_parse_expr}, + {"annotate-expr", NULL, 0, 0, test_annotate_expr}, + {"simplify-expr", NULL, 0, 0, test_simplify_expr}, + {"normalize-expr", NULL, 0, 0, test_normalize_expr}, + {"evaluate-expr", NULL, 1, 1, test_evaluate_expr}, + {"composition", NULL, 1, 1, test_composition}, + {"tree-shape", NULL, 1, 1, test_tree_shape}, + {"exhaustive", NULL, 1, 1, test_exhaustive}, {NULL, NULL, 0, 0, NULL}, }; struct ovs_cmdl_context ctx; -- 2.20.1