Signed-off-by: Ben Pfaff <[email protected]>
---
v2->v3: This patch added to series.
v3->v4: Remainder of series applied; this patch now incorporates feedback
from Russell.
ovn/lib/expr.c | 164 +++++++++++++++++++++++++++++++++++++++++++++----------
ovn/lib/expr.h | 8 ++-
tests/ovn.at | 33 +++++++++++
tests/test-ovn.c | 67 ++++++++++++-----------
4 files changed, 209 insertions(+), 63 deletions(-)
diff --git a/ovn/lib/expr.c b/ovn/lib/expr.c
index e648dbd..507f34b 100644
--- a/ovn/lib/expr.c
+++ b/ovn/lib/expr.c
@@ -21,6 +21,7 @@
#include "lex.h"
#include "match.h"
#include "shash.h"
+#include "simap.h"
#include "openvswitch/vlog.h"
VLOG_DEFINE_THIS_MODULE(expr);
@@ -1155,9 +1156,14 @@ expr_symtab_add_subfield(struct shash *symtab, const
char *name,
* 'prereqs'. */
struct expr_symbol *
expr_symtab_add_string(struct shash *symtab, const char *name,
- const char *prereqs)
+ enum mf_field_id id, const char *prereqs)
{
- return add_symbol(symtab, name, 0, prereqs, EXPR_L_NOMINAL, false);
+ const struct mf_field *field = mf_from_id(id);
+ struct expr_symbol *symbol;
+
+ symbol = add_symbol(symtab, name, 0, prereqs, EXPR_L_NOMINAL, false);
+ symbol->field = field;
+ return symbol;
}
static enum expr_level
@@ -2139,33 +2145,64 @@ expr_match_add(struct hmap *matches, struct expr_match
*match)
hmap_insert(matches, &match->hmap_node, hash);
}
-static void
-constrain_match(const struct expr *expr, struct match *m)
+static bool
+constrain_match(const struct expr *expr, const struct simap *ports,
+ 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);
+ if (expr->cmp.symbol->width) {
+ mf_mask_subfield(expr->cmp.symbol->field, &expr->cmp.value,
+ &expr->cmp.mask, m);
+ } else {
+ const struct simap_node *node;
+ node = ports ? simap_find(ports, expr->cmp.string) : NULL;
+ if (!node) {
+ return false;
+ }
+
+ struct mf_subfield sf;
+ sf.field = expr->cmp.symbol->field;
+ sf.ofs = 0;
+ sf.n_bits = expr->cmp.symbol->field->n_bits;
+
+ union mf_subvalue x;
+ memset(&x, 0, sizeof x);
+ x.integer = htonll(node->data);
+
+ mf_write_subfield(&sf, &x, m);
+ }
+ return true;
}
-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)
+static bool
+add_disjunction(const struct expr *or, const struct simap *ports,
+ struct match *m, uint8_t clause, uint8_t n_clauses,
+ uint32_t conj_id, struct hmap *matches)
{
struct expr *sub;
+ int n = 0;
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);
+ if (constrain_match(sub, ports, &match->match)) {
+ expr_match_add(matches, match);
+ n++;
+ } else {
+ free(match->conjunctions);
+ free(match);
+ }
}
+
+ /* If n == 1, then this didn't really need to be a disjunction. Oh well,
+ * that shouldn't happen much. */
+ return n > 0;
}
static void
-add_conjunction(const struct expr *and, uint32_t *n_conjsp,
- struct hmap *matches)
+add_conjunction(const struct expr *and, const struct simap *ports,
+ uint32_t *n_conjsp, struct hmap *matches)
{
struct match match;
int n_clauses = 0;
@@ -2177,7 +2214,9 @@ add_conjunction(const struct expr *and, uint32_t
*n_conjsp,
LIST_FOR_EACH (sub, node, &and->andor) {
switch (sub->type) {
case EXPR_T_CMP:
- constrain_match(sub, &match);
+ if (!constrain_match(sub, ports, &match)) {
+ return;
+ }
break;
case EXPR_T_OR:
n_clauses++;
@@ -2193,7 +2232,7 @@ add_conjunction(const struct expr *and, uint32_t
*n_conjsp,
} 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);
+ add_disjunction(sub, ports, &match, 0, 0, 0, matches);
}
}
} else {
@@ -2201,37 +2240,64 @@ add_conjunction(const struct expr *and, uint32_t
*n_conjsp,
(*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);
+ if (!add_disjunction(sub, ports, &match, clause++,
+ n_clauses, *n_conjsp, matches)) {
+ /* This clause can't ever match, so we might as well skip
+ * adding the other clauses--the overall disjunctive flow
+ * can't ever match. Ideally we would also back out all of
+ * the clauses we already added, but that seems like a lot
+ * of trouble for a case that might never occur in
+ * practice. */
+ return;
+ }
}
}
}
}
static void
-add_cmp_flow(const struct expr *cmp, struct hmap *matches)
+add_cmp_flow(const struct expr *cmp, const struct simap *ports,
+ struct hmap *matches)
{
struct expr_match *m = expr_match_new(NULL, 0, 0, 0);
- constrain_match(cmp, &m->match);
- expr_match_add(matches, m);
+ if (constrain_match(cmp, ports, &m->match)) {
+ expr_match_add(matches, m);
+ } else {
+ free(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. */
+ * initializes to an hmap of "struct expr_match" structures. Returns the
+ * number of conjunctive match IDs consumed by 'matches', which uses
+ * conjunctive match IDs beginning with 0; the caller must offset or remap them
+ * into the desired range as necessary.
+ *
+ * 'ports' must be a map from strings (presumably names of ports) to integers.
+ * Any comparisons against string fields in 'expr' are translated into integers
+ * through this map. A comparison against a string that is not in 'ports' acts
+ * like a Boolean "false"; that is, it will always fail to match. For a simple
+ * expression, this means that the overall expression always fails to match,
+ * but an expression with a disjunction on the string field might still match
+ * on other port names.
+ *
+ * (This treatment of string fields might be too simplistic in general, but it
+ * seems reasonable for now when string fields are used only for ports.) */
uint32_t
-expr_to_matches(const struct expr *expr, struct hmap *matches)
+expr_to_matches(const struct expr *expr, const struct simap *ports,
+ struct hmap *matches)
{
uint32_t n_conjs = 0;
hmap_init(matches);
switch (expr->type) {
case EXPR_T_CMP:
- add_cmp_flow(expr, matches);
+ add_cmp_flow(expr, ports, matches);
break;
case EXPR_T_AND:
- add_conjunction(expr, &n_conjs, matches);
+ add_conjunction(expr, ports, &n_conjs, matches);
break;
case EXPR_T_OR:
@@ -2239,16 +2305,16 @@ expr_to_matches(const struct expr *expr, struct hmap
*matches)
struct expr *sub;
LIST_FOR_EACH (sub, node, &expr->andor) {
- add_cmp_flow(sub, matches);
+ add_cmp_flow(sub, ports, matches);
}
} else {
struct expr *sub;
LIST_FOR_EACH (sub, node, &expr->andor) {
if (sub->type == EXPR_T_AND) {
- add_conjunction(sub, &n_conjs, matches);
+ add_conjunction(sub, ports, &n_conjs, matches);
} else {
- add_cmp_flow(sub, matches);
+ add_cmp_flow(sub, ports, matches);
}
}
}
@@ -2265,6 +2331,48 @@ expr_to_matches(const struct expr *expr, struct hmap
*matches)
}
return n_conjs;
}
+
+/* Destroys all of the 'struct expr_match'es in 'matches', as well as the
+ * 'matches' hmap itself. */
+void
+expr_matches_destroy(struct hmap *matches)
+{
+ struct expr_match *m, *n;
+
+ HMAP_FOR_EACH_SAFE (m, n, hmap_node, matches) {
+ hmap_remove(matches, &m->hmap_node);
+ free(m->conjunctions);
+ free(m);
+ }
+ hmap_destroy(matches);
+}
+
+/* Prints a representation of the 'struct expr_match'es in 'matches' to
+ * 'stream'. */
+void
+expr_matches_print(const struct hmap *matches, FILE *stream)
+{
+ if (hmap_is_empty(matches)) {
+ fputs("(no flows)\n", stream);
+ return;
+ }
+
+ const struct expr_match *m;
+ HMAP_FOR_EACH (m, hmap_node, matches) {
+ char *s = match_to_string(&m->match, OFP_DEFAULT_PRIORITY);
+ fputs(s, stream);
+ free(s);
+
+ if (m->n) {
+ for (int i = 0; i < m->n; i++) {
+ const struct cls_conjunction *c = &m->conjunctions[i];
+ fprintf(stream, "%c conjunction(%"PRIu32", %d/%d)",
+ i == 0 ? ':' : ',', c->id, c->clause, c->n_clauses);
+ }
+ }
+ putc('\n', stream);
+ }
+}
/* Returns true if 'expr' honors the invariants for expressions (see the large
* comment above "struct expr" in expr.h), false otherwise. */
diff --git a/ovn/lib/expr.h b/ovn/lib/expr.h
index ab13c1b..54cec46 100644
--- a/ovn/lib/expr.h
+++ b/ovn/lib/expr.h
@@ -61,6 +61,7 @@
struct ds;
struct shash;
+struct simap;
/* "Measurement level" of a field. See "Level of Measurement" in the large
* comment on struct expr_symbol below for more information. */
@@ -255,7 +256,7 @@ struct expr_symbol *expr_symtab_add_subfield(struct shash
*symtab,
const char *prereqs,
const char *subfield);
struct expr_symbol *expr_symtab_add_string(struct shash *symtab,
- const char *name,
+ const char *name, enum mf_field_id,
const char *prereqs);
struct expr_symbol *expr_symtab_add_predicate(struct shash *symtab,
const char *name,
@@ -362,6 +363,9 @@ struct expr_match {
size_t n, allocated;
};
-uint32_t expr_to_matches(const struct expr *, struct hmap *);
+uint32_t expr_to_matches(const struct expr *, const struct simap *ports,
+ struct hmap *matches);
+void expr_matches_destroy(struct hmap *matches);
+void expr_matches_print(const struct hmap *matches, FILE *);
#endif /* ovn/expr.h */
diff --git a/tests/ovn.at b/tests/ovn.at
index fa89cbe..24479ec 100644
--- a/tests/ovn.at
+++ b/tests/ovn.at
@@ -346,3 +346,36 @@ AT_CHECK([ovstest test-ovn exhaustive --operation=flow
--vars=3 --bits=3 --relop
[Tested converting to flows 38394 expressions of 3 terminals with 3 vars
each of 3 bits in terms of operators ==.
])
AT_CLEANUP
+
+AT_SETUP([ovn -- converting expressions to flows -- string fields])
+expr_to_flow () {
+ echo "$1" | ovstest test-ovn expr-to-flows | sort
+}
+AT_CHECK([expr_to_flow 'inport == "eth0"'], [0], [in_port=5
+])
+AT_CHECK([expr_to_flow 'inport == "eth1"'], [0], [in_port=6
+])
+AT_CHECK([expr_to_flow 'inport == "eth2"'], [0], [(no flows)
+])
+AT_CHECK([expr_to_flow 'inport == "eth0" && ip'], [0], [dnl
+ip,in_port=5
+ipv6,in_port=5
+])
+AT_CHECK([expr_to_flow 'inport == "eth1" && ip'], [0], [dnl
+ip,in_port=6
+ipv6,in_port=6
+])
+AT_CHECK([expr_to_flow 'inport == "eth2" && ip'], [0], [(no flows)
+])
+AT_CHECK([expr_to_flow 'inport == {"eth0", "eth1", "eth2", "LOCAL"}'], [0],
+[in_port=5
+in_port=6
+in_port=LOCAL
+])
+AT_CHECK([expr_to_flow 'inport == {"eth0", "eth1", "eth2"} && ip'], [0], [dnl
+ip,in_port=5
+ip,in_port=6
+ipv6,in_port=5
+ipv6,in_port=6
+])
+AT_CLEANUP
diff --git a/tests/test-ovn.c b/tests/test-ovn.c
index a6d8b80..67093d5 100644
--- a/tests/test-ovn.c
+++ b/tests/test-ovn.c
@@ -27,6 +27,7 @@
#include "ovs-thread.h"
#include "ovstest.h"
#include "shash.h"
+#include "simap.h"
#include "util.h"
#include "openvswitch/vlog.h"
@@ -131,8 +132,8 @@ 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_string(symtab, "inport", MFF_IN_PORT, NULL);
+ expr_symtab_add_string(symtab, "outport", MFF_ACTSET_OUTPUT, NULL);
expr_symtab_add_field(symtab, "xreg0", MFF_XREG0, NULL, false);
expr_symtab_add_field(symtab, "xreg1", MFF_XREG1, NULL, false);
@@ -234,9 +235,16 @@ static void
test_parse_expr__(int steps)
{
struct shash symtab;
+ struct simap ports;
struct ds input;
create_symtab(&symtab);
+
+ simap_init(&ports);
+ simap_put(&ports, "eth0", 5);
+ simap_put(&ports, "eth1", 6);
+ simap_put(&ports, "LOCAL", ofp_to_u16(OFPP_LOCAL));
+
ds_init(&input);
while (!ds_get_test_line(&input, stdin)) {
struct expr *expr;
@@ -256,10 +264,18 @@ test_parse_expr__(int steps)
}
}
if (!error) {
- struct ds output = DS_EMPTY_INITIALIZER;
- expr_format(expr, &output);
- puts(ds_cstr(&output));
- ds_destroy(&output);
+ if (steps > 3) {
+ struct hmap matches;
+
+ expr_to_matches(expr, &ports, &matches);
+ expr_matches_print(&matches, stdout);
+ expr_matches_destroy(&matches);
+ } else {
+ struct ds output = DS_EMPTY_INITIALIZER;
+ expr_format(expr, &output);
+ puts(ds_cstr(&output));
+ ds_destroy(&output);
+ }
} else {
puts(error);
free(error);
@@ -268,6 +284,7 @@ test_parse_expr__(int steps)
}
ds_destroy(&input);
+ simap_destroy(&ports);
expr_symtab_destroy(&symtab);
shash_destroy(&symtab);
}
@@ -295,6 +312,12 @@ test_normalize_expr(struct ovs_cmdl_context *ctx
OVS_UNUSED)
{
test_parse_expr__(3);
}
+
+static void
+test_expr_to_flows(struct ovs_cmdl_context *ctx OVS_UNUSED)
+{
+ test_parse_expr__(4);
+}
/* Evaluate an expression. */
@@ -859,7 +882,7 @@ test_tree_shape_exhaustively(struct expr *expr, struct
shash *symtab,
struct test_rule *test_rule;
uint32_t n_conjs;
- n_conjs = expr_to_matches(modified, &matches);
+ n_conjs = expr_to_matches(modified, NULL, &matches);
classifier_init(&cls, NULL);
HMAP_FOR_EACH (m, hmap_node, &matches) {
@@ -931,25 +954,7 @@ test_tree_shape_exhaustively(struct expr *expr, struct
shash *symtab,
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);
- }
-
+ expr_matches_print(&matches, stderr);
fprintf(stderr,
"However, %s flow was found in the classifier.\n",
found ? "a" : "no");
@@ -958,7 +963,6 @@ test_tree_shape_exhaustively(struct expr *expr, struct
shash *symtab,
}
}
if (operation >= OP_FLOW) {
- struct expr_match *m, *n;
struct test_rule *test_rule;
CLS_FOR_EACH (test_rule, cr, &cls) {
@@ -968,12 +972,7 @@ test_tree_shape_exhaustively(struct expr *expr, struct
shash *symtab,
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_matches_destroy(&matches);
}
expr_destroy(modified);
}
@@ -1160,6 +1159,7 @@ parse-expr\n\
annotate-expr\n\
simplify-expr\n\
normalize-expr\n\
+expr-to-flows\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\
@@ -1281,6 +1281,7 @@ test_ovn_main(int argc, char *argv[])
{"annotate-expr", NULL, 0, 0, test_annotate_expr},
{"simplify-expr", NULL, 0, 0, test_simplify_expr},
{"normalize-expr", NULL, 0, 0, test_normalize_expr},
+ {"expr-to-flows", NULL, 0, 0, test_expr_to_flows},
{"evaluate-expr", NULL, 1, 1, test_evaluate_expr},
{"composition", NULL, 1, 1, test_composition},
{"tree-shape", NULL, 1, 1, test_tree_shape},
--
2.1.3
_______________________________________________
dev mailing list
[email protected]
http://openvswitch.org/mailman/listinfo/dev
