From: Ben Pfaff Date: Sun, 14 Jun 2015 01:10:46 +0000 (-0700) Subject: Merge "master" into "ovn". X-Git-Tag: v2.5.0~1065 X-Git-Url: http://git.cascardo.eti.br/?p=cascardo%2Fovs.git;a=commitdiff_plain;h=03ce866e44835e43f04747cfc65b2c592d780165 Merge "master" into "ovn". This allows OVN to take advantage of the client scalability changes that have been committed to ovsdb-server on master recently. Conflicts: Makefile.am lib/learn.c --- 03ce866e44835e43f04747cfc65b2c592d780165 diff --cc Makefile.am index 1dd5d2ba8,59a14667d..fc623e6de --- a/Makefile.am +++ b/Makefile.am @@@ -377,4 -379,4 +379,5 @@@ include tutorial/automake.m include vtep/automake.mk include datapath-windows/automake.mk include datapath-windows/include/automake.mk + include windows/automake.mk +include ovn/automake.mk diff --cc lib/util.h index 55fb50cfb,59276e357..4dcb492f8 --- a/lib/util.h +++ b/lib/util.h @@@ -549,12 -550,14 +552,19 @@@ void bitwise_put(uint64_t value unsigned int n_bits); uint64_t bitwise_get(const void *src, unsigned int src_len, unsigned int src_ofs, unsigned int n_bits); +bool bitwise_get_bit(const void *src, unsigned int len, unsigned int ofs); +void bitwise_put0(void *dst, unsigned int len, unsigned int ofs); +void bitwise_put1(void *dst, unsigned int len, unsigned int ofs); +void bitwise_put_bit(void *dst, unsigned int len, unsigned int ofs, bool); +void bitwise_toggle_bit(void *dst, unsigned int len, unsigned int ofs); + /* Returns non-zero if the parameters have equal value. */ + static inline int + ovs_u128_equals(const ovs_u128 *a, const ovs_u128 *b) + { + return (a->u64.hi == b->u64.hi) && (a->u64.lo == b->u64.lo); + } + void xsleep(unsigned int seconds); #ifdef _WIN32 diff --cc tests/test-ovn.c index 1a005b80e,000000000..fc6ea4b73 mode 100644,000000..100644 --- a/tests/test-ovn.c +++ b/tests/test-ovn.c @@@ -1,1351 -1,0 +1,1352 @@@ +/* + * Copyright (c) 2015 Nicira, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include +#include "command-line.h" +#include +#include +#include +#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); +} + +/* 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; + + expr_to_matches(modified, NULL, &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); ++ 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, &f, NULL) != NULL; ++ 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); +} + +/* 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); +} + +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);