--- /dev/null
- cls_rule_init(&test_rule->cr, &m->match, 0);
+/*
+ * 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 "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 "ofp-actions.h"
+#include "ofpbuf.h"
+#include "ovn/lib/actions.h"
+#include "ovn/lib/expr.h"
+#include "ovn/lib/lex.h"
+#include "ovs-thread.h"
+#include "ovstest.h"
+#include "shash.h"
+#include "simap.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)
+{
+ if (a->type != b->type) {
+ fprintf(stderr, "type differs: %d -> %d\n", a->type, b->type);
+ return;
+ }
+
+ if (!((a->s && b->s && !strcmp(a->s, b->s))
+ || (!a->s && !b->s))) {
+ fprintf(stderr, "string differs: %s -> %s\n",
+ a->s ? a->s : "(null)",
+ b->s ? b->s : "(null)");
+ return;
+ }
+
+ if (a->type == LEX_T_INTEGER || a->type == LEX_T_MASKED_INTEGER) {
+ if (memcmp(&a->value, &b->value, sizeof a->value)) {
+ fprintf(stderr, "value differs\n");
+ return;
+ }
+
+ if (a->type == LEX_T_MASKED_INTEGER
+ && memcmp(&a->mask, &b->mask, sizeof a->mask)) {
+ fprintf(stderr, "mask differs\n");
+ return;
+ }
+
+ if (a->format != b->format
+ && !(a->format == LEX_F_HEXADECIMAL
+ && b->format == LEX_F_DECIMAL
+ && a->value.integer == 0)) {
+ fprintf(stderr, "format differs: %d -> %d\n",
+ a->format, b->format);
+ }
+ }
+}
+
+static void
+test_lex(struct ovs_cmdl_context *ctx OVS_UNUSED)
+{
+ struct ds input;
+ struct ds output;
+
+ ds_init(&input);
+ ds_init(&output);
+ while (!ds_get_line(&input, stdin)) {
+ struct lexer lexer;
+
+ lexer_init(&lexer, ds_cstr(&input));
+ ds_clear(&output);
+ while (lexer_get(&lexer) != LEX_T_END) {
+ size_t len = output.length;
+ lex_token_format(&lexer.token, &output);
+
+ /* Check that the formatted version can really be parsed back
+ * losslessly. */
+ if (lexer.token.type != LEX_T_ERROR) {
+ const char *s = ds_cstr(&output) + len;
+ struct lexer l2;
+
+ lexer_init(&l2, s);
+ lexer_get(&l2);
+ compare_token(&lexer.token, &l2.token);
+ lexer_destroy(&l2);
+ }
+ ds_put_char(&output, ' ');
+ }
+ lexer_destroy(&lexer);
+
+ ds_chomp(&output, ' ');
+ puts(ds_cstr(&output));
+ }
+ ds_destroy(&input);
+ ds_destroy(&output);
+}
+
+static void
+create_symtab(struct shash *symtab)
+{
+ shash_init(symtab);
+
+ /* Reserve a pair of registers for the logical inport and outport. A full
+ * 32-bit register each is bigger than we need, but the expression code
+ * doesn't yet support string fields that occupy less than a full OXM. */
+ expr_symtab_add_string(symtab, "inport", MFF_REG6, NULL);
+ expr_symtab_add_string(symtab, "outport", MFF_REG7, 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_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_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 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;
+ 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) {
+ 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);
+ }
+ expr_destroy(expr);
+ }
+ ds_destroy(&input);
+
+ simap_destroy(&ports);
+ 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);
+}
+
+static void
+test_expr_to_flows(struct ovs_cmdl_context *ctx OVS_UNUSED)
+{
+ test_parse_expr__(4);
+}
+\f
+/* 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);
+}
+\f
+/* 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' : ' ');
+ }
+ }
+}
+\f
+/* 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');
+ }
+}
+\f
+/* 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;
+ }
+ }
+}
+\f
+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;
+
+ expr_to_matches(modified, NULL, &matches);
+
+ classifier_init(&cls, NULL);
+ HMAP_FOR_EACH (m, hmap_node, &matches) {
+ test_rule = xmalloc(sizeof *test_rule);
- bool found = classifier_lookup(&cls, &f, NULL) != NULL;
++ cls_rule_init(&test_rule->cr, &m->match, 0, CLS_MIN_VERSION);
+ classifier_insert(&cls, &test_rule->cr, m->conjunctions, m->n);
+ }
+ }
+ 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, CLS_MIN_VERSION,
++ &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");
+ expr_matches_print(&matches, stderr);
+ fprintf(stderr,
+ "However, %s flow was found in the classifier.\n",
+ found ? "a" : "no");
+ exit(EXIT_FAILURE);
+ }
+ }
+ }
+ if (operation >= OP_FLOW) {
+ 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();
+
+ expr_matches_destroy(&matches);
+ }
+ expr_destroy(modified);
+ }
+}
+
+#ifndef _WIN32
+static void
+wait_pid(pid_t *pids, int *n)
+{
+ int status;
+ pid_t pid;
+
+ pid = waitpid(WAIT_ANY, &status, 0);
+ if (pid < 0) {
+ ovs_fatal(errno, "waitpid failed");
+ } else if (WIFEXITED(status)) {
+ if (WEXITSTATUS(status)) {
+ exit(WEXITSTATUS(status));
+ }
+ } else if (WIFSIGNALED(status)) {
+ raise(WTERMSIG(status));
+ exit(1);
+ } else {
+ OVS_NOT_REACHED();
+ }
+
+ for (int i = 0; i < *n; i++) {
+ if (pids[i] == pid) {
+ pids[i] = pids[--*n];
+ return;
+ }
+ }
+ ovs_fatal(0, "waitpid returned unknown child");
+}
+#endif
+
+static void
+test_exhaustive(struct ovs_cmdl_context *ctx OVS_UNUSED)
+{
+ int n_terminals = atoi(ctx->argv[1]);
+ struct tree_shape ts[50];
+ int n_tses;
+
+ struct shash symtab;
+ const struct expr_symbol *vars[4];
+
+ ovs_assert(test_vars <= ARRAY_SIZE(vars));
+
+ shash_init(&symtab);
+ for (int i = 0; i < test_vars; i++) {
+ char name[2] = { 'a' + i, '\0' };
+
+ vars[i] = expr_symtab_add_field(&symtab, name, MFF_REG0 + i, NULL,
+ false);
+ }
+
+#ifndef _WIN32
+ pid_t *children = xmalloc(test_parallel * sizeof *children);
+ int n_children = 0;
+#endif
+
+ int n_tested = 0;
+ for (int i = 0; i < 2; i++) {
+ enum expr_type base_type = i ? EXPR_T_OR : EXPR_T_AND;
+
+ for (n_tses = init_tree_shape(ts, n_terminals); n_tses;
+ n_tses = next_tree_shape(ts, n_tses)) {
+ const struct tree_shape *tsp = ts;
+ struct expr *terminals[50];
+ struct expr **terminalp = terminals;
+ struct expr *expr = build_tree_shape(base_type, &tsp, &terminalp);
+ ovs_assert(terminalp == &terminals[n_terminals]);
+
+ if (verbosity > 0) {
+ print_tree_shape(ts, n_tses);
+ printf(": ");
+ struct ds s = DS_EMPTY_INITIALIZER;
+ expr_format(expr, &s);
+ puts(ds_cstr(&s));
+ ds_destroy(&s);
+ }
+
+#ifndef _WIN32
+ if (test_parallel > 1) {
+ pid_t pid = xfork();
+ if (!pid) {
+ test_tree_shape_exhaustively(expr, &symtab,
+ terminals, n_terminals,
+ vars, test_vars, test_bits);
+ expr_destroy(expr);
+ exit(0);
+ } else {
+ if (n_children >= test_parallel) {
+ wait_pid(children, &n_children);
+ }
+ children[n_children++] = pid;
+ }
+ } else
+#endif
+ {
+ n_tested += test_tree_shape_exhaustively(
+ expr, &symtab, terminals, n_terminals,
+ vars, test_vars, test_bits);
+ }
+ expr_destroy(expr);
+ }
+ }
+#ifndef _WIN32
+ while (n_children > 0) {
+ wait_pid(children, &n_children);
+ }
+ free(children);
+#endif
+
+ printf("Tested ");
+ switch (operation) {
+ case OP_CONVERT:
+ printf("converting");
+ break;
+ case OP_SIMPLIFY:
+ printf("simplifying");
+ break;
+ case OP_NORMALIZE:
+ printf("normalizing");
+ break;
+ case OP_FLOW:
+ printf("converting to flows");
+ break;
+ }
+ if (n_tested) {
+ printf(" %d expressions of %d terminals", n_tested, n_terminals);
+ } else {
+ printf(" all %d-terminal expressions", n_terminals);
+ }
+ printf(" with %d vars each of %d bits in terms of operators",
+ test_vars, test_bits);
+ for (unsigned int relops = test_relops; relops;
+ relops = zero_rightmost_1bit(relops)) {
+ enum expr_relop r = rightmost_1bit_idx(relops);
+ printf(" %s", expr_relop_to_string(r));
+ }
+ printf(".\n");
+
+ expr_symtab_destroy(&symtab);
+ shash_destroy(&symtab);
+}
+\f
+/* Actions. */
+
+static void
+test_parse_actions(struct ovs_cmdl_context *ctx OVS_UNUSED)
+{
+ 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 ofpbuf ofpacts;
+ struct expr *prereqs;
+ char *error;
+
+ ofpbuf_init(&ofpacts, 0);
+ error = actions_parse_string(ds_cstr(&input), &symtab, &ports, 11,
+ &ofpacts, &prereqs);
+ if (!error) {
+ struct ds output;
+
+ ds_init(&output);
+ ds_put_cstr(&output, "actions=");
+ ofpacts_format(ofpacts.data, ofpacts.size, &output);
+ ds_put_cstr(&output, ", prereqs=");
+ if (prereqs) {
+ expr_format(prereqs, &output);
+ } else {
+ ds_put_char(&output, '1');
+ }
+ puts(ds_cstr(&output));
+ ds_destroy(&output);
+ } else {
+ puts(error);
+ free(error);
+ }
+
+ expr_destroy(prereqs);
+ ofpbuf_uninit(&ofpacts);
+ }
+ ds_destroy(&input);
+
+ simap_destroy(&ports);
+ expr_symtab_destroy(&symtab);
+ shash_destroy(&symtab);
+}
+\f
+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\
+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\
+\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[] = {
+ /* Lexer. */
+ {"lex", NULL, 0, 0, test_lex},
+
+ /* Expressions. */
+ {"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},
+ {"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},
+ {"exhaustive", NULL, 1, 1, test_exhaustive},
+
+ /* Actions. */
+ {"parse-actions", NULL, 0, 0, test_parse_actions},
+
+ {NULL, NULL, 0, 0, NULL},
+ };
+ struct ovs_cmdl_context ctx;
+ ctx.argc = argc - optind;
+ ctx.argv = argv + optind;
+ ovs_cmdl_run_command(&ctx, commands);
+}
+
+OVSTEST_REGISTER("test-ovn", test_ovn_main);
projects / cascardo / ovs.git / commitdiff