[ovs-dev] [PATCH ovn 5/5] expr: New module for Boolean expressions on fields, for use in OVN.
Ben Pfaff
blp at nicira.com
Tue Mar 31 03:57:23 UTC 2015
Known weaknesses:
* String fields can't be converted to flows yet.
* 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 yet;
this is a solid base to build on.
Signed-off-by: Ben Pfaff <blp at nicira.com>
---
ovn/TODO | 25 -
ovn/automake.mk | 2 +-
ovn/expr.c | 2315 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
ovn/expr.h | 367 +++++++++
ovn/ovn.xml | 355 ++++++---
tests/ovn.at | 253 ++++++
tests/test-ovn.c | 1175 +++++++++++++++++++++++++++
7 files changed, 4366 insertions(+), 126 deletions(-)
create mode 100644 ovn/expr.c
create mode 100644 ovn/expr.h
diff --git a/ovn/TODO b/ovn/TODO
index d91c3cf..5414155 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/automake.mk b/ovn/automake.mk
index 940340c..c422345 100644
--- a/ovn/automake.mk
+++ b/ovn/automake.mk
@@ -75,7 +75,7 @@ SUFFIXES += .xml
--version=$(VERSION) $< > $@.tmp && mv $@.tmp $@
lib_LTLIBRARIES += lib/libovn.la
-lib_libovn_la_SOURCES = ovn/lex.c ovn/lex.h
+lib_libovn_la_SOURCES = ovn/expr.c ovn/expr.h ovn/lex.c ovn/lex.h
EXTRA_DIST += ovn/TODO
diff --git a/ovn/expr.c b/ovn/expr.c
new file mode 100644
index 0000000..cd6f729
--- /dev/null
+++ b/ovn/expr.c
@@ -0,0 +1,2315 @@
+/*
+ * 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 <config.h>
+#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;
+ json.type = JSON_STRING;
+ json.u.string = CONST_CAST(char *, s);
+ json_to_ds(&json, 0, ds);
+}
+
+static void
+expr_format_cmp(const struct expr *e, struct ds *s)
+{
+ if (e->cmp.symbol->width) {
+ 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);
+ }
+ } else {
+ ds_put_format(s, "%s %s ", e->cmp.symbol->name,
+ expr_relop_to_string(e->cmp.relop));
+ expr_format_string(e->cmp.string, 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 void OVS_PRINTF_FORMAT(2, 3)
+expr_error(struct expr_context *ctx, const char *message, ...)
+{
+ if (!ctx->error) {
+ if (ctx->lexer->token.type == LEX_T_ERROR) {
+ ctx->error = xstrdup(ctx->lexer->token.s);
+ } else {
+ 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 (!ctx->error) {
+ if (ctx->lexer->token.type == LEX_T_ERROR) {
+ ctx->error = xstrdup(ctx->lexer->token.s);
+ } else {
+ 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;
+ }
+}
+
+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);
+ 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 expr_create_boolean(false);
+ }
+ 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();
+}
+
+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;
+ }
+ 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;
+}
+
+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);
+ match_init_catchall(&m->match);
+ 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);
+ match_init_catchall(&m->match);
+ 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/expr.h b/ovn/expr.h
new file mode 100644
index 0000000..ab13c1b
--- /dev/null
+++ b/ovn/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.xml b/ovn/ovn.xml
index e8d9bc9..2a5fecc 100644
--- a/ovn/ovn.xml
+++ b/ovn/ovn.xml
@@ -245,141 +245,296 @@
</p>
<p>
- Matching expressions have two important kinds of primary expression:
- <dfn>fields</dfn> and <dfn>constants</dfn>. A field names a piece of
- data or metadata. The supported fields are:
+ The most important components of match expression are
+ <dfn>comparisons</dfn> between <dfn>symbols</dfn> and
+ <dfn>constants</dfn>, e.g. <code>ip4.dst == 192.168.0.1</code>,
+ <code>ip.proto == 6</code>, <code>arp.op == 1</code>, <code>eth.type ==
+ 0x800</code>. The logical AND operator <code>&&</code> and
+ logical OR operator <code>||</code> can combine comparisons into a
+ larger expression.
</p>
- <ul>
- <li>
- <code>metadata</code> <code>reg0</code> ... <code>reg7</code>
- <code>xreg0</code> ... <code>xreg3</code>
- </li>
- <li><code>inport</code> <code>outport</code> <code>queue</code></li>
- <li><code>eth.src</code> <code>eth.dst</code> <code>eth.type</code></li>
- <li><code>vlan.tci</code> <code>vlan.vid</code> <code>vlan.pcp</code> <code>vlan.present</code></li>
- <li><code>ip.proto</code> <code>ip.dscp</code> <code>ip.ecn</code> <code>ip.ttl</code> <code>ip.frag</code></li>
- <li><code>ip4.src</code> <code>ip4.dst</code></li>
- <li><code>ip6.src</code> <code>ip6.dst</code> <code>ip6.label</code></li>
- <li><code>arp.op</code> <code>arp.spa</code> <code>arp.tpa</code> <code>arp.sha</code> <code>arp.tha</code></li>
- <li><code>tcp.src</code> <code>tcp.dst</code> <code>tcp.flags</code></li>
- <li><code>udp.src</code> <code>udp.dst</code></li>
- <li><code>sctp.src</code> <code>sctp.dst</code></li>
- <li><code>icmp4.type</code> <code>icmp4.code</code></li>
- <li><code>icmp6.type</code> <code>icmp6.code</code></li>
- <li><code>nd.target</code> <code>nd.sll</code> <code>nd.tll</code></li>
- </ul>
-
<p>
- Subfields may be addressed using a <code>[]</code> suffix,
- e.g. <code>tcp.src[0..7]</code> 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 <code>!</code>, and literals <code>0</code> and
+ <code>1</code> to express ``false'' or ``true,'' respectively. The
+ latter is useful by itself as a catch-all expression that matches every
+ packet.
</p>
- <p>
- Some fields have prerequisites. OVN implicitly adds clauses to satisfy
- these. For example, <code>arp.op == 1</code> is equivalent to
- <code>eth.type == 0x0806 && arp.op == 1</code>, and
- <code>tcp.src == 80</code> is equivalent to <code>(eth.type == 0x0800
- || eth.type == 0x86dd) && ip.proto == 6 && tcp.src ==
- 80</code>.
- </p>
+ <p><em>Symbols</em></p>
<p>
- Most fields have integer values. Integer constants may be expressed in
- several forms: decimal integers, hexadecimal integers prefixed by
- <code>0x</code>, 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.
+ <em>Type</em>. Symbols have <dfn>integer</dfn> or <dfn>string</dfn>
+ type. Integer symbols have a <dfn>width</dfn> in bits.
</p>
<p>
- The <code>inport</code> and <code>outport</code> fields have string
- values. The useful values are <ref column="logical_port"/> names from
- the <ref column="Bindings"/> and <ref column="Gateway"/> table.
+ <em>Kinds</em>. There are three kinds of symbols:
</p>
+ <ul>
+ <li>
+ <p>
+ <dfn>Fields</dfn>. A field symbol represents a packet header or
+ metadata field. For example, a field
+ named <code>vlan.tci</code> might represent the VLAN TCI field in a
+ packet.
+ </p>
+
+ <p>
+ A field symbol can have integer or string type. Integer fields can
+ be nominal or ordinal (see <em>Level of Measurement</em>,
+ below).
+ </p>
+ </li>
+
+ <li>
+ <p>
+ <dfn>Subfields</dfn>. A subfield represents a subset of bits from
+ a larger field. For example, a field <code>vlan.vid</code> might
+ be defined as an alias for <code>vlan.tci[0..11]</code>. Subfields
+ are provided for syntactic convenience, because it is always
+ possible to instead refer to a subset of bits from a field
+ directly.
+ </p>
+
+ <p>
+ Only ordinal fields (see <em>Level of Measurement</em>,
+ below) may have subfields. Subfields are always ordinal.
+ </p>
+ </li>
+
+ <li>
+ <p>
+ <dfn>Predicates</dfn>. A predicate is shorthand for a Boolean
+ expression. Predicates may be used much like 1-bit fields. For
+ example, <code>ip4</code> might expand to <code>eth.type ==
+ 0x800</code>. Predicates are provided for syntactic convenience,
+ because it is always possible to instead specify the underlying
+ expression directly.
+ </p>
+
+ <p>
+ A predicate whose expansion refers to any nominal field or
+ predicate (see <em>Level of Measurement</em>, below) is nominal;
+ other predicates have Boolean level of measurement.
+ </p>
+ </li>
+ </ul>
+
<p>
- The available operators, from highest to lowest precedence, are:
+ <em>Level of Measurement</em>. See
+ http://en.wikipedia.org/wiki/Level_of_measurement for the statistical
+ concept on which this classification is based. There are three
+ levels:
</p>
<ul>
- <li><code>()</code></li>
- <li><code>== != < <= > >= in not in</code></li>
- <li><code>!</code></li>
- <li><code>&&</code></li>
- <li><code>||</code></li>
+ <li>
+ <p>
+ <dfn>Ordinal</dfn>. 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.''
+ </p>
+
+ <p>
+ Any use of a nominal field may specify a single bit or a range of
+ bits, e.g. <code>vlan.tci[13..15]</code> refers to the PCP field
+ within the VLAN TCI, and <code>eth.dst[40]</code> refers to the
+ multicast bit in the Ethernet destination address.
+ </p>
+
+ <p>
+ OVN supports all the usual arithmetic relations (<code>==</code>,
+ <code>!=</code>, <code><</code>, <code><=</code>,
+ <code>></code>, and <code>>=</code>) on ordinal fields and
+ their subfields, because OVN can implement these in OpenFlow and
+ Open vSwitch as collections of bitwise tests.
+ </p>
+ </li>
+
+ <li>
+ <p>
+ <dfn>Nominal</dfn>. 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.
+ </p>
+
+ <p>
+ 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.)
+ </p>
+
+ <p>
+ String fields are always nominal.
+ </p>
+ </li>
+
+ <li>
+ <p>
+ <dfn>Boolean</dfn>. 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.
+ </p>
+
+ <p>
+ Only predicates (see above) have a Boolean level of measurement.
+ </p>
+
+ <p>
+ This isn't a standard level of measurement.
+ </p>
+ </li>
</ul>
<p>
- The <code>()</code> operator is used for grouping.
+ <em>Prerequisites</em>. Any symbol can have prerequisites, which are
+ additional condition implied by the use of the symbol. For example,
+ For example, <code>icmp4.type</code> symbol might have prerequisite
+ <code>icmp4</code>, which would cause an expression <code>icmp4.type ==
+ 0</code> to be interpreted as <code>icmp4.type == 0 &&
+ icmp4</code>, which would in turn expand to <code>icmp4.type == 0
+ && eth.type == 0x800 && ip4.proto == 1</code> (assuming
+ <code>icmp4</code> is a predicate defined as suggested under
+ <em>Types</em> above).
+ </p>
+
+ <p><em>Relational operators</em></p>
+
+ <p>
+ All of the standard relational operators <code>==</code>,
+ <code>!=</code>, <code><</code>, <code><=</code>,
+ <code>></code>, and <code>>=</code> are supported. Nominal
+ fields support only <code>==</code> and <code>!=</code>, and only in a
+ positive sense when outer <code>!</code> are taken into account,
+ e.g. given string field <code>inport</code>, <code>inport ==
+ "eth0"</code> and <code>!(inport != "eth0")</code> are acceptable, but
+ not <code>inport != "eth0"</code>.
</p>
<p>
- The equality operator <code>==</code> is the most important operator.
- Its operands must be a field and an optionally masked constant, in
- either order. The <code>==</code> operator yields true when the
- field's value equals the constant's value for all the bits included in
- the mask. The <code>==</code> operator translates simply and naturally
- to OpenFlow.
+ The implementation of <code>==</code> (or <code>!=</code> when it is
+ negated), is more efficient than that of the other relational
+ operators.
</p>
+ <p><em>Constants</em></p>
+
<p>
- The inequality operator <code>!=</code> yields the inverse of
- <code>==</code> but its syntax and use are the same. Implementation of
- the inequality operator is expensive.
+ Integer constants may be expressed in decimal, hexadecimal prefixed by
+ <code>0x</code>, 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.
</p>
<p>
- 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. <code>tcp.src < 1024</code>. Implementation of the
- relational operators is expensive.
+ 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 <ref
+ column="logical_port"/> names from the <ref column="Bindings"/> and
+ <ref column="Gateway"/> table.
</p>
<p>
- The set membership operator <code>in</code>, with syntax
- ``<code><var>field</var> in { <var>constant1</var>,
- <var>constant2</var>,</code> ... <code>}</code>'', is syntactic sugar
- for ``<code>(<var>field</var> == <var>constant1</var> ||
- <var>field</var> == <var>constant2</var> || </code>...<code>)</code>.
- Conversely, ``<code><var>field</var> not in { <var>constant1</var>,
- <var>constant2</var>, </code>...<code> }</code>'' is syntactic sugar
- for ``<code>(<var>field</var> != <var>constant1</var> &&
+ Some operators support sets of constants written inside curly braces
+ <code>{</code> ... <code>}</code>. Commas between elements of a set,
+ and after the last elements, are optional. With <code>==</code>,
+ ``<code><var>field</var> == { <var>constant1</var>,
+ <var>constant2</var>,</code> ... <code>}</code>'' is syntactic sugar
+ for ``<code><var>field</var> == <var>constant1</var> ||
+ <var>field</var> == <var>constant2</var> || </code>...<code></code>.
+ Similarly, ``<code><var>field</var> != { <var>constant1</var>,
+ <var>constant2</var>, </code>...<code> }</code>'' is equivalent to
+ ``<code><var>field</var> != <var>constant1</var> &&
<var>field</var> != <var>constant2</var> &&
- </code>...<code>)</code>''.
+ </code>...<code></code>''.
</p>
+ <p><em>Miscellaneous</em></p>
+
<p>
- The unary prefix operator <code>!</code> yields its operand's inverse.
+ Comparisons may name the symbol or the constant first,
+ e.g. <code>tcp.src == 80</code> and <code>80 == tcp.src</code> are both
+ acceptable.
</p>
<p>
- The logical AND operator <code>&&</code> yields true only if
- both of its operands are true.
+ Tests for a range may be expressed using a syntax like <code>1024 <=
+ tcp.src <= 49151</code>, which is equivalent to <code>1024 <=
+ tcp.src && tcp.src <= 49151</code>.
</p>
<p>
- The logical OR operator <code>||</code> 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 <code><var>symobl</var> == 1</code>, e.g. <code>vlan.present</code>
+ is equivalent to <code>vlan.present == 1</code>. The same is true for
+ one-bit subfields, e.g. <code>vlan.tci[12]</code>. 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 <code>tcp.src != 0</code> the comparison
+ against 0 is required.
</p>
<p>
- Finally, the keywords <code>true</code> and <code>false</code> may also
- be used in matching expressions. <code>true</code> is useful by itself
- as a catch-all expression that matches every packet.
+ <em>Operator precedence</em> 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: <code>&&</code> and
+ <code>||</code> require parentheses when used together, and
+ <code>!</code> requires parentheses when applied to a relational
+ expression. Thus, in <code>(eth.type == 0x800 || eth.type == 0x86dd)
+ && ip.proto == 6</code> or <code>!(arp.op == 1)</code>, the
+ parentheses are mandatory.
</p>
+ <ul>
+ <li><code>()</code></li>
+ <li><code>== != < <= > >=</code></li>
+ <li><code>!</code></li>
+ <li><code>&& ||</code></li>
+ </ul>
+
<p>
- (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.)
+ <em>Comments</em> may be introduced by <code>//</code>, which extends
+ to the next new-line, or bracketed by <code>/*</code> and
+ <code>*/</code>.
</p>
+
+ <p><em>Symbols</em></p>
+
+ <ul>
+ <li>
+ <code>metadata</code> <code>reg0</code> ... <code>reg7</code>
+ <code>xreg0</code> ... <code>xreg3</code>
+ </li>
+ <li><code>inport</code> <code>outport</code> <code>queue</code></li>
+ <li><code>eth.src</code> <code>eth.dst</code> <code>eth.type</code></li>
+ <li><code>vlan.tci</code> <code>vlan.vid</code> <code>vlan.pcp</code> <code>vlan.present</code></li>
+ <li><code>ip.proto</code> <code>ip.dscp</code> <code>ip.ecn</code> <code>ip.ttl</code> <code>ip.frag</code></li>
+ <li><code>ip4.src</code> <code>ip4.dst</code></li>
+ <li><code>ip6.src</code> <code>ip6.dst</code> <code>ip6.label</code></li>
+ <li><code>arp.op</code> <code>arp.spa</code> <code>arp.tpa</code> <code>arp.sha</code> <code>arp.tha</code></li>
+ <li><code>tcp.src</code> <code>tcp.dst</code> <code>tcp.flags</code></li>
+ <li><code>udp.src</code> <code>udp.dst</code></li>
+ <li><code>sctp.src</code> <code>sctp.dst</code></li>
+ <li><code>icmp4.type</code> <code>icmp4.code</code></li>
+ <li><code>icmp6.type</code> <code>icmp6.code</code></li>
+ <li><code>nd.target</code> <code>nd.sll</code> <code>nd.tll</code></li>
+ </ul>
+
</column>
<column name="actions">
@@ -410,24 +565,24 @@
</p>
<dl>
- <dt><code>learn</code></dt>
+ <dt><code>learn</code></dt>
- <dt><code>conntrack</code></dt>
+ <dt><code>conntrack</code></dt>
- <dt><code>with(<var>field</var>=<var>value</var>) { <var>action</var>, </code>...<code> }</code></dt>
- <dd>execute <var>actions</var> with temporary changes to <var>fields</var></dd>
+ <dt><code>with(<var>field</var>=<var>value</var>) { <var>action</var>, </code>...<code> }</code></dt>
+ <dd>execute <var>actions</var> with temporary changes to <var>fields</var></dd>
- <dt><code>dec_ttl { <var>action</var>, </code>...<code> } { <var>action</var>; </code>...<code>}</code></dt>
- <dd>
- decrement TTL; execute first set of actions if
- successful, second set if TTL decrement fails
- </dd>
+ <dt><code>dec_ttl { <var>action</var>, </code>...<code> } { <var>action</var>; </code>...<code>}</code></dt>
+ <dd>
+ decrement TTL; execute first set of actions if
+ successful, second set if TTL decrement fails
+ </dd>
- <dt><code>icmp_reply { <var>action</var>, </code>...<code> }</code></dt>
- <dd>generate ICMP reply from packet, execute <var>action</var>s</dd>
+ <dt><code>icmp_reply { <var>action</var>, </code>...<code> }</code></dt>
+ <dd>generate ICMP reply from packet, execute <var>action</var>s</dd>
- <dt><code>arp { <var>action</var>, </code>...<code> }</code></dt>
- <dd>generate ARP from packet, execute <var>action</var>s</dd>
+ <dt><code>arp { <var>action</var>, </code>...<code> }</code></dt>
+ <dd>generate ARP from packet, execute <var>action</var>s</dd>
</dl>
<p>
diff --git a/tests/ovn.at b/tests/ovn.at
index d28a684..fa89cbe 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 2229d4e..aef4e45 100644
--- a/tests/test-ovn.c
+++ b/tests/test-ovn.c
@@ -16,15 +16,39 @@
#include <config.h>
#include "command-line.h"
+#include <errno.h>
#include <getopt.h>
+#include <sys/wait.h>
#include "dynamic-string.h"
#include "fatal-signal.h"
#include "match.h"
+#include "ovn/expr.h"
#include "ovn/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,12 +126,1163 @@ test_lex(struct ovs_cmdl_context *ctx OVS_UNUSED)
}
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);
+ }
+ }
+ }
+#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.1.3
More information about the dev
mailing list