2 * Copyright (c) 2015 Nicira, Inc.
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at:
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
18 #include "command-line.h"
22 #include "dynamic-string.h"
23 #include "fatal-signal.h"
25 #include "ofp-actions.h"
27 #include "ovn/lib/actions.h"
28 #include "ovn/lib/expr.h"
29 #include "ovn/lib/lex.h"
30 #include "ovs-thread.h"
35 #include "openvswitch/vlog.h"
37 /* --relops: Bitmap of the relational operators to test, in exhaustive test. */
38 static unsigned int test_relops;
40 /* --vars: Number of variables to test, in exhaustive test. */
41 static int test_vars = 2;
43 /* --bits: Number of bits per variable, in exhaustive test. */
44 static int test_bits = 3;
46 /* --operation: The operation to test, in exhaustive test. */
47 static enum { OP_CONVERT, OP_SIMPLIFY, OP_NORMALIZE, OP_FLOW } operation
50 /* --parallel: Number of parallel processes to use in test. */
51 static int test_parallel = 1;
53 /* -m, --more: Message verbosity */
57 compare_token(const struct lex_token *a, const struct lex_token *b)
59 if (a->type != b->type) {
60 fprintf(stderr, "type differs: %d -> %d\n", a->type, b->type);
64 if (!((a->s && b->s && !strcmp(a->s, b->s))
65 || (!a->s && !b->s))) {
66 fprintf(stderr, "string differs: %s -> %s\n",
67 a->s ? a->s : "(null)",
68 b->s ? b->s : "(null)");
72 if (a->type == LEX_T_INTEGER || a->type == LEX_T_MASKED_INTEGER) {
73 if (memcmp(&a->value, &b->value, sizeof a->value)) {
74 fprintf(stderr, "value differs\n");
78 if (a->type == LEX_T_MASKED_INTEGER
79 && memcmp(&a->mask, &b->mask, sizeof a->mask)) {
80 fprintf(stderr, "mask differs\n");
84 if (a->format != b->format
85 && !(a->format == LEX_F_HEXADECIMAL
86 && b->format == LEX_F_DECIMAL
87 && a->value.integer == 0)) {
88 fprintf(stderr, "format differs: %d -> %d\n",
89 a->format, b->format);
95 test_lex(struct ovs_cmdl_context *ctx OVS_UNUSED)
102 while (!ds_get_line(&input, stdin)) {
105 lexer_init(&lexer, ds_cstr(&input));
107 while (lexer_get(&lexer) != LEX_T_END) {
108 size_t len = output.length;
109 lex_token_format(&lexer.token, &output);
111 /* Check that the formatted version can really be parsed back
113 if (lexer.token.type != LEX_T_ERROR) {
114 const char *s = ds_cstr(&output) + len;
119 compare_token(&lexer.token, &l2.token);
122 ds_put_char(&output, ' ');
124 lexer_destroy(&lexer);
126 ds_chomp(&output, ' ');
127 puts(ds_cstr(&output));
134 create_symtab(struct shash *symtab)
138 /* Reserve a pair of registers for the logical inport and outport. A full
139 * 32-bit register each is bigger than we need, but the expression code
140 * doesn't yet support string fields that occupy less than a full OXM. */
141 expr_symtab_add_string(symtab, "inport", MFF_REG6, NULL);
142 expr_symtab_add_string(symtab, "outport", MFF_REG7, NULL);
144 expr_symtab_add_field(symtab, "xreg0", MFF_XREG0, NULL, false);
145 expr_symtab_add_field(symtab, "xreg1", MFF_XREG1, NULL, false);
146 expr_symtab_add_field(symtab, "xreg2", MFF_XREG2, NULL, false);
148 expr_symtab_add_subfield(symtab, "reg0", NULL, "xreg0[32..63]");
149 expr_symtab_add_subfield(symtab, "reg1", NULL, "xreg0[0..31]");
150 expr_symtab_add_subfield(symtab, "reg2", NULL, "xreg1[32..63]");
151 expr_symtab_add_subfield(symtab, "reg3", NULL, "xreg1[0..31]");
152 expr_symtab_add_subfield(symtab, "reg4", NULL, "xreg2[32..63]");
153 expr_symtab_add_subfield(symtab, "reg5", NULL, "xreg2[0..31]");
155 expr_symtab_add_field(symtab, "eth.src", MFF_ETH_SRC, NULL, false);
156 expr_symtab_add_field(symtab, "eth.dst", MFF_ETH_DST, NULL, false);
157 expr_symtab_add_field(symtab, "eth.type", MFF_ETH_TYPE, NULL, true);
159 expr_symtab_add_field(symtab, "vlan.tci", MFF_VLAN_TCI, NULL, false);
160 expr_symtab_add_predicate(symtab, "vlan.present", "vlan.tci[12]");
161 expr_symtab_add_subfield(symtab, "vlan.pcp", "vlan.present",
163 expr_symtab_add_subfield(symtab, "vlan.vid", "vlan.present",
166 expr_symtab_add_predicate(symtab, "ip4", "eth.type == 0x800");
167 expr_symtab_add_predicate(symtab, "ip6", "eth.type == 0x86dd");
168 expr_symtab_add_predicate(symtab, "ip", "ip4 || ip6");
169 expr_symtab_add_field(symtab, "ip.proto", MFF_IP_PROTO, "ip", true);
170 expr_symtab_add_field(symtab, "ip.dscp", MFF_IP_DSCP, "ip", false);
171 expr_symtab_add_field(symtab, "ip.ecn", MFF_IP_ECN, "ip", false);
172 expr_symtab_add_field(symtab, "ip.ttl", MFF_IP_TTL, "ip", false);
174 expr_symtab_add_field(symtab, "ip4.src", MFF_IPV4_SRC, "ip4", false);
175 expr_symtab_add_field(symtab, "ip4.dst", MFF_IPV4_DST, "ip4", false);
177 expr_symtab_add_predicate(symtab, "icmp4", "ip4 && ip.proto == 1");
178 expr_symtab_add_field(symtab, "icmp4.type", MFF_ICMPV4_TYPE, "icmp4",
180 expr_symtab_add_field(symtab, "icmp4.code", MFF_ICMPV4_CODE, "icmp4",
183 expr_symtab_add_field(symtab, "ip6.src", MFF_IPV6_SRC, "ip6", false);
184 expr_symtab_add_field(symtab, "ip6.dst", MFF_IPV6_DST, "ip6", false);
185 expr_symtab_add_field(symtab, "ip6.label", MFF_IPV6_LABEL, "ip6", false);
187 expr_symtab_add_predicate(symtab, "icmp6", "ip6 && ip.proto == 58");
188 expr_symtab_add_field(symtab, "icmp6.type", MFF_ICMPV6_TYPE, "icmp6",
190 expr_symtab_add_field(symtab, "icmp6.code", MFF_ICMPV6_CODE, "icmp6",
193 expr_symtab_add_predicate(symtab, "icmp", "icmp4 || icmp6");
195 expr_symtab_add_field(symtab, "ip.frag", MFF_IP_FRAG, "ip", false);
196 expr_symtab_add_predicate(symtab, "ip.is_frag", "ip.frag[0]");
197 expr_symtab_add_predicate(symtab, "ip.later_frag", "ip.frag[1]");
198 expr_symtab_add_predicate(symtab, "ip.first_frag", "ip.is_frag && !ip.later_frag");
200 expr_symtab_add_predicate(symtab, "arp", "eth.type == 0x806");
201 expr_symtab_add_field(symtab, "arp.op", MFF_ARP_OP, "arp", false);
202 expr_symtab_add_field(symtab, "arp.spa", MFF_ARP_SPA, "arp", false);
203 expr_symtab_add_field(symtab, "arp.sha", MFF_ARP_SHA, "arp", false);
204 expr_symtab_add_field(symtab, "arp.tpa", MFF_ARP_TPA, "arp", false);
205 expr_symtab_add_field(symtab, "arp.tha", MFF_ARP_THA, "arp", false);
207 expr_symtab_add_predicate(symtab, "nd", "icmp6.type == {135, 136} && icmp6.code == 0");
208 expr_symtab_add_field(symtab, "nd.target", MFF_ND_TARGET, "nd", false);
209 expr_symtab_add_field(symtab, "nd.sll", MFF_ND_SLL,
210 "nd && icmp6.type == 135", false);
211 expr_symtab_add_field(symtab, "nd.tll", MFF_ND_TLL,
212 "nd && icmp6.type == 136", false);
214 expr_symtab_add_predicate(symtab, "tcp", "ip.proto == 6");
215 expr_symtab_add_field(symtab, "tcp.src", MFF_TCP_SRC, "tcp", false);
216 expr_symtab_add_field(symtab, "tcp.dst", MFF_TCP_DST, "tcp", false);
217 expr_symtab_add_field(symtab, "tcp.flags", MFF_TCP_FLAGS, "tcp", false);
219 expr_symtab_add_predicate(symtab, "udp", "ip.proto == 17");
220 expr_symtab_add_field(symtab, "udp.src", MFF_UDP_SRC, "udp", false);
221 expr_symtab_add_field(symtab, "udp.dst", MFF_UDP_DST, "udp", false);
223 expr_symtab_add_predicate(symtab, "sctp", "ip.proto == 132");
224 expr_symtab_add_field(symtab, "sctp.src", MFF_SCTP_SRC, "sctp", false);
225 expr_symtab_add_field(symtab, "sctp.dst", MFF_SCTP_DST, "sctp", false);
227 /* For negative testing. */
228 expr_symtab_add_field(symtab, "bad_prereq", MFF_XREG0, "xyzzy", false);
229 expr_symtab_add_field(symtab, "self_recurse", MFF_XREG0,
230 "self_recurse != 0", false);
231 expr_symtab_add_field(symtab, "mutual_recurse_1", MFF_XREG0,
232 "mutual_recurse_2 != 0", false);
233 expr_symtab_add_field(symtab, "mutual_recurse_2", MFF_XREG0,
234 "mutual_recurse_1 != 0", false);
238 test_parse_expr__(int steps)
244 create_symtab(&symtab);
247 simap_put(&ports, "eth0", 5);
248 simap_put(&ports, "eth1", 6);
249 simap_put(&ports, "LOCAL", ofp_to_u16(OFPP_LOCAL));
252 while (!ds_get_test_line(&input, stdin)) {
256 expr = expr_parse_string(ds_cstr(&input), &symtab, &error);
257 if (!error && steps > 0) {
258 expr = expr_annotate(expr, &symtab, &error);
262 expr = expr_simplify(expr);
265 expr = expr_normalize(expr);
266 ovs_assert(expr_is_normalized(expr));
273 expr_to_matches(expr, &ports, &matches);
274 expr_matches_print(&matches, stdout);
275 expr_matches_destroy(&matches);
277 struct ds output = DS_EMPTY_INITIALIZER;
278 expr_format(expr, &output);
279 puts(ds_cstr(&output));
290 simap_destroy(&ports);
291 expr_symtab_destroy(&symtab);
292 shash_destroy(&symtab);
296 test_parse_expr(struct ovs_cmdl_context *ctx OVS_UNUSED)
298 test_parse_expr__(0);
302 test_annotate_expr(struct ovs_cmdl_context *ctx OVS_UNUSED)
304 test_parse_expr__(1);
308 test_simplify_expr(struct ovs_cmdl_context *ctx OVS_UNUSED)
310 test_parse_expr__(2);
314 test_normalize_expr(struct ovs_cmdl_context *ctx OVS_UNUSED)
316 test_parse_expr__(3);
320 test_expr_to_flows(struct ovs_cmdl_context *ctx OVS_UNUSED)
322 test_parse_expr__(4);
325 /* Evaluate an expression. */
327 static bool evaluate_expr(const struct expr *, unsigned int subst, int n_bits);
330 evaluate_andor_expr(const struct expr *expr, unsigned int subst, int n_bits,
333 const struct expr *sub;
335 LIST_FOR_EACH (sub, node, &expr->andor) {
336 if (evaluate_expr(sub, subst, n_bits) == short_circuit) {
337 return short_circuit;
340 return !short_circuit;
344 evaluate_cmp_expr(const struct expr *expr, unsigned int subst, int n_bits)
346 int var_idx = expr->cmp.symbol->name[0] - 'a';
347 unsigned var_mask = (1u << n_bits) - 1;
348 unsigned int arg1 = (subst >> (var_idx * n_bits)) & var_mask;
349 unsigned int arg2 = ntohll(expr->cmp.value.integer);
350 unsigned int mask = ntohll(expr->cmp.mask.integer);
352 ovs_assert(!(mask & ~var_mask));
353 ovs_assert(!(arg2 & ~var_mask));
354 ovs_assert(!(arg2 & ~mask));
357 switch (expr->cmp.relop) {
381 /* Evaluates 'expr' and returns its Boolean result. 'subst' provides the value
382 * for the variables, which must be 'n_bits' bits each and be named "a", "b",
383 * "c", etc. The value of variable "a" is the least-significant 'n_bits' bits
384 * of 'subst', the value of "b" is the next 'n_bits' bits, and so on. */
386 evaluate_expr(const struct expr *expr, unsigned int subst, int n_bits)
388 switch (expr->type) {
390 return evaluate_cmp_expr(expr, subst, n_bits);
393 return evaluate_andor_expr(expr, subst, n_bits, false);
396 return evaluate_andor_expr(expr, subst, n_bits, true);
399 return expr->boolean;
407 test_evaluate_expr(struct ovs_cmdl_context *ctx)
409 int a = atoi(ctx->argv[1]);
410 int b = atoi(ctx->argv[2]);
411 int c = atoi(ctx->argv[3]);
412 unsigned int subst = a | (b << 3) || (c << 6);
417 expr_symtab_add_field(&symtab, "xreg0", MFF_XREG0, NULL, false);
418 expr_symtab_add_field(&symtab, "xreg1", MFF_XREG1, NULL, false);
419 expr_symtab_add_field(&symtab, "xreg2", MFF_XREG1, NULL, false);
420 expr_symtab_add_subfield(&symtab, "a", NULL, "xreg0[0..2]");
421 expr_symtab_add_subfield(&symtab, "b", NULL, "xreg1[0..2]");
422 expr_symtab_add_subfield(&symtab, "c", NULL, "xreg2[0..2]");
425 while (!ds_get_test_line(&input, stdin)) {
429 expr = expr_parse_string(ds_cstr(&input), &symtab, &error);
431 expr = expr_annotate(expr, &symtab, &error);
434 printf("%d\n", evaluate_expr(expr, subst, 3));
443 expr_symtab_destroy(&symtab);
444 shash_destroy(&symtab);
449 * The "compositions" of a positive integer N are all of the ways that one can
450 * add up positive integers to sum to N. For example, the compositions of 3
451 * are 3, 2+1, 1+2, and 1+1+1.
453 * We use compositions to find all the ways to break up N terms of a Boolean
454 * expression into subexpressions. Suppose we want to generate all expressions
455 * with 3 terms. The compositions of 3 (ignoring 3 itself) provide the
456 * possibilities (x && x) || x, x || (x && x), and x || x || x. (Of course one
457 * can exchange && for || in each case.) One must recursively compose the
458 * sub-expressions whose values are 3 or greater; that is what the "tree shape"
459 * concept later covers.
461 * To iterate through all compositions of, e.g., 5:
463 * unsigned int state;
467 * for (n = first_composition(ARRAY_SIZE(s), &state, s); n > 0;
468 * n = next_composition(&state, s, n)) {
469 * // Do something with composition 's' with 'n' elements.
472 * Algorithm from D. E. Knuth, _The Art of Computer Programming, Vol. 4A:
473 * Combinatorial Algorithms, Part 1_, section 7.2.1.1, answer to exercise
477 /* Begins iteration through the compositions of 'n'. Initializes 's' to the
478 * number of elements in the first composition of 'n' and returns that number
479 * of elements. The first composition in fact is always 'n' itself, so the
480 * return value will be 1.
482 * Initializes '*state' to some internal state information. The caller must
483 * maintain this state (and 's') for use by next_composition().
485 * 's' must have room for at least 'n' elements. */
487 first_composition(int n, unsigned int *state, int s[])
494 /* Advances 's', with 'sn' elements, to the next composition and returns the
495 * number of elements in this new composition, or 0 if no compositions are
496 * left. 'state' is the same internal state passed to first_composition(). */
498 next_composition(unsigned int *state, int s[], int sn)
529 test_composition(struct ovs_cmdl_context *ctx)
531 int n = atoi(ctx->argv[1]);
535 for (int sn = first_composition(n, &state, s); sn;
536 sn = next_composition(&state, s, sn)) {
537 for (int i = 0; i < sn; i++) {
538 printf("%d%c", s[i], i == sn - 1 ? '\n' : ' ');
545 * This code generates all possible Boolean expressions with a specified number
546 * of terms N (equivalent to the number of external nodes in a tree).
548 * See test_tree_shape() for a simple example. */
550 /* An array of these structures describes the shape of a tree.
552 * A single element of struct tree_shape describes a single node in the tree.
553 * The node has 'sn' direct children. From left to right, for i in 0...sn-1,
554 * s[i] is 1 if the child is a leaf node, otherwise the child is a subtree and
555 * s[i] is the number of leaf nodes within that subtree. In the latter case,
556 * the subtree is described by another struct tree_shape within the enclosing
557 * array. The tree_shapes are ordered in the array in in-order.
566 init_tree_shape__(struct tree_shape ts[], int n)
573 /* Skip the first composition intentionally. */
574 ts->sn = first_composition(n, &ts->state, ts->s);
575 ts->sn = next_composition(&ts->state, ts->s, ts->sn);
576 for (int i = 0; i < ts->sn; i++) {
577 n_tses += init_tree_shape__(&ts[n_tses], ts->s[i]);
582 /* Initializes 'ts[]' as the first in the set of all of possible shapes of
583 * trees with 'n' leaves. Returns the number of "struct tree_shape"s in the
584 * first tree shape. */
586 init_tree_shape(struct tree_shape ts[], int n)
599 return init_tree_shape__(ts, n);
603 /* Advances 'ts', which currently has 'n_tses' elements, to the next possible
604 * tree shape with the number of leaves passed to init_tree_shape(). Returns
605 * the number of "struct tree_shape"s in the next shape, or 0 if all tree
606 * shapes have been visited. */
608 next_tree_shape(struct tree_shape ts[], int n_tses)
610 if (n_tses == 1 && ts->sn == 2 && ts->s[0] == 1 && ts->s[1] == 1) {
614 struct tree_shape *p = &ts[n_tses - 1];
615 p->sn = p->sn > 1 ? next_composition(&p->state, p->s, p->sn) : 0;
617 for (int i = 0; i < p->sn; i++) {
618 n_tses += init_tree_shape__(&ts[n_tses], p->s[i]);
628 print_tree_shape(const struct tree_shape ts[], int n_tses)
630 for (int i = 0; i < n_tses; i++) {
634 for (int j = 0; j < ts[i].sn; j++) {
646 test_tree_shape(struct ovs_cmdl_context *ctx)
648 int n = atoi(ctx->argv[1]);
649 struct tree_shape ts[50];
652 for (n_tses = init_tree_shape(ts, n); n_tses;
653 n_tses = next_tree_shape(ts, n_tses)) {
654 print_tree_shape(ts, n_tses);
659 /* Iteration through all possible terminal expressions (e.g. EXPR_T_CMP and
660 * EXPR_T_BOOLEAN expressions).
662 * Given a tree shape, this allows the code to try all possible ways to plug in
667 * struct expr terminal;
668 * const struct expr_symbol *vars = ...;
672 * init_terminal(&terminal, vars[0]);
674 * // Something with 'terminal'.
675 * } while (next_terminal(&terminal, vars, n_vars, n_bits));
678 /* Sets 'expr' to the first possible terminal expression. 'var' should be the
679 * first variable in the ones to be tested. */
681 init_terminal(struct expr *expr, const struct expr_symbol *var)
683 expr->type = EXPR_T_CMP;
684 expr->cmp.symbol = var;
685 expr->cmp.relop = rightmost_1bit_idx(test_relops);
686 memset(&expr->cmp.value, 0, sizeof expr->cmp.value);
687 memset(&expr->cmp.mask, 0, sizeof expr->cmp.mask);
688 expr->cmp.value.integer = htonll(0);
689 expr->cmp.mask.integer = htonll(1);
692 /* Returns 'x' with the rightmost contiguous string of 1s changed to 0s,
693 * e.g. 01011100 => 01000000. See H. S. Warren, Jr., _Hacker's Delight_, 2nd
694 * ed., section 2-1. */
696 turn_off_rightmost_1s(unsigned int x)
698 return ((x & -x) + x) & x;
701 static const struct expr_symbol *
702 next_var(const struct expr_symbol *symbol,
703 const struct expr_symbol *vars[], int n_vars)
705 for (int i = 0; i < n_vars; i++) {
706 if (symbol == vars[i]) {
707 return i + 1 >= n_vars ? NULL : vars[i + 1];
713 static enum expr_relop
714 next_relop(enum expr_relop relop)
716 unsigned int remaining_relops = test_relops & ~((1u << (relop + 1)) - 1);
717 return (remaining_relops
718 ? rightmost_1bit_idx(remaining_relops)
719 : rightmost_1bit_idx(test_relops));
722 /* Advances 'expr' to the next possible terminal expression within the 'n_vars'
723 * variables of 'n_bits' bits each in 'vars[]'. */
725 next_terminal(struct expr *expr, const struct expr_symbol *vars[], int n_vars,
728 if (expr->type == EXPR_T_BOOLEAN) {
732 expr->boolean = true;
739 next = (ntohll(expr->cmp.value.integer)
740 + (ntohll(expr->cmp.mask.integer) << n_bits));
743 unsigned m = next >> n_bits;
744 unsigned v = next & ((1u << n_bits) - 1);
745 if (next >= (1u << (2 * n_bits))) {
746 enum expr_relop old_relop = expr->cmp.relop;
747 expr->cmp.relop = next_relop(old_relop);
748 if (expr->cmp.relop <= old_relop) {
749 expr->cmp.symbol = next_var(expr->cmp.symbol,vars, n_vars);
750 if (!expr->cmp.symbol) {
751 expr->type = EXPR_T_BOOLEAN;
752 expr->boolean = false;
758 /* Skip: empty mask is pathological. */
760 /* Skip: 1-bits in value correspond to 0-bits in mask. */
761 } else if (turn_off_rightmost_1s(m)
762 && (expr->cmp.relop != EXPR_R_EQ &&
763 expr->cmp.relop != EXPR_R_NE)) {
764 /* Skip: can't have discontiguous mask for > >= < <=. */
766 expr->cmp.value.integer = htonll(v);
767 expr->cmp.mask.integer = htonll(m);
774 make_terminal(struct expr ***terminalp)
776 struct expr *e = expr_create_boolean(true);
783 build_simple_tree(enum expr_type type, int n, struct expr ***terminalp)
786 struct expr *e = expr_create_andor(type);
787 for (int i = 0; i < 2; i++) {
788 struct expr *sub = make_terminal(terminalp);
789 list_push_back(&e->andor, &sub->node);
793 return make_terminal(terminalp);
800 build_tree_shape(enum expr_type type, const struct tree_shape **tsp,
801 struct expr ***terminalp)
803 const struct tree_shape *ts = *tsp;
806 struct expr *e = expr_create_andor(type);
807 enum expr_type t = type == EXPR_T_AND ? EXPR_T_OR : EXPR_T_AND;
808 for (int i = 0; i < ts->sn; i++) {
809 struct expr *sub = (ts->s[i] > 2
810 ? build_tree_shape(t, tsp, terminalp)
811 : build_simple_tree(t, ts->s[i], terminalp));
812 list_push_back(&e->andor, &sub->node);
822 free_rule(struct test_rule *test_rule)
824 cls_rule_destroy(&test_rule->cr);
829 test_tree_shape_exhaustively(struct expr *expr, struct shash *symtab,
830 struct expr *terminals[], int n_terminals,
831 const struct expr_symbol *vars[], int n_vars,
836 const unsigned int var_mask = (1u << n_bits) - 1;
837 for (int i = 0; i < n_terminals; i++) {
838 init_terminal(terminals[i], vars[0]);
841 struct ds s = DS_EMPTY_INITIALIZER;
843 memset(&f, 0, sizeof f);
845 for (int i = n_terminals - 1; ; i--) {
850 if (next_terminal(terminals[i], vars, n_vars, n_bits)) {
853 init_terminal(terminals[i], vars[0]);
855 ovs_assert(expr_honors_invariants(expr));
859 struct expr *modified;
860 if (operation == OP_CONVERT) {
862 expr_format(expr, &s);
865 modified = expr_parse_string(ds_cstr(&s), symtab, &error);
867 fprintf(stderr, "%s fails to parse (%s)\n",
871 } else if (operation >= OP_SIMPLIFY) {
872 modified = expr_simplify(expr_clone(expr));
873 ovs_assert(expr_honors_invariants(modified));
875 if (operation >= OP_NORMALIZE) {
876 modified = expr_normalize(modified);
877 ovs_assert(expr_is_normalized(modified));
882 struct classifier cls;
883 if (operation >= OP_FLOW) {
884 struct expr_match *m;
885 struct test_rule *test_rule;
887 expr_to_matches(modified, NULL, &matches);
889 classifier_init(&cls, NULL);
890 HMAP_FOR_EACH (m, hmap_node, &matches) {
891 test_rule = xmalloc(sizeof *test_rule);
892 cls_rule_init(&test_rule->cr, &m->match, 0, CLS_MIN_VERSION);
893 classifier_insert(&cls, &test_rule->cr, m->conjunctions, m->n);
896 for (int subst = 0; subst < 1 << (n_bits * n_vars); subst++) {
897 bool expected = evaluate_expr(expr, subst, n_bits);
898 bool actual = evaluate_expr(modified, subst, n_bits);
899 if (actual != expected) {
900 struct ds expr_s, modified_s;
903 expr_format(expr, &expr_s);
905 ds_init(&modified_s);
906 expr_format(modified, &modified_s);
909 "%s evaluates to %d, but %s evaluates to %d, for",
910 ds_cstr(&expr_s), expected,
911 ds_cstr(&modified_s), actual);
912 for (int i = 0; i < n_vars; i++) {
916 fprintf(stderr, " %c = 0x%x", 'a' + i,
917 (subst >> (n_bits * i)) & var_mask);
923 if (operation >= OP_FLOW) {
924 for (int i = 0; i < n_vars; i++) {
925 f.regs[i] = (subst >> (i * n_bits)) & var_mask;
927 bool found = classifier_lookup(&cls, CLS_MIN_VERSION,
929 if (expected != found) {
930 struct ds expr_s, modified_s;
933 expr_format(expr, &expr_s);
935 ds_init(&modified_s);
936 expr_format(modified, &modified_s);
939 "%s and %s evaluate to %d, for",
940 ds_cstr(&expr_s), ds_cstr(&modified_s), expected);
941 for (int i = 0; i < n_vars; i++) {
945 fprintf(stderr, " %c = 0x%x", 'a' + i,
946 (subst >> (n_bits * i)) & var_mask);
948 fputs(".\n", stderr);
950 fprintf(stderr, "Converted to classifier:\n");
951 expr_matches_print(&matches, stderr);
953 "However, %s flow was found in the classifier.\n",
959 if (operation >= OP_FLOW) {
960 struct test_rule *test_rule;
962 CLS_FOR_EACH (test_rule, cr, &cls) {
963 classifier_remove(&cls, &test_rule->cr);
964 ovsrcu_postpone(free_rule, test_rule);
966 classifier_destroy(&cls);
969 expr_matches_destroy(&matches);
971 expr_destroy(modified);
977 wait_pid(pid_t *pids, int *n)
982 pid = waitpid(WAIT_ANY, &status, 0);
984 ovs_fatal(errno, "waitpid failed");
985 } else if (WIFEXITED(status)) {
986 if (WEXITSTATUS(status)) {
987 exit(WEXITSTATUS(status));
989 } else if (WIFSIGNALED(status)) {
990 raise(WTERMSIG(status));
996 for (int i = 0; i < *n; i++) {
997 if (pids[i] == pid) {
998 pids[i] = pids[--*n];
1002 ovs_fatal(0, "waitpid returned unknown child");
1007 test_exhaustive(struct ovs_cmdl_context *ctx OVS_UNUSED)
1009 int n_terminals = atoi(ctx->argv[1]);
1010 struct tree_shape ts[50];
1013 struct shash symtab;
1014 const struct expr_symbol *vars[4];
1016 ovs_assert(test_vars <= ARRAY_SIZE(vars));
1018 shash_init(&symtab);
1019 for (int i = 0; i < test_vars; i++) {
1020 char name[2] = { 'a' + i, '\0' };
1022 vars[i] = expr_symtab_add_field(&symtab, name, MFF_REG0 + i, NULL,
1027 pid_t *children = xmalloc(test_parallel * sizeof *children);
1032 for (int i = 0; i < 2; i++) {
1033 enum expr_type base_type = i ? EXPR_T_OR : EXPR_T_AND;
1035 for (n_tses = init_tree_shape(ts, n_terminals); n_tses;
1036 n_tses = next_tree_shape(ts, n_tses)) {
1037 const struct tree_shape *tsp = ts;
1038 struct expr *terminals[50];
1039 struct expr **terminalp = terminals;
1040 struct expr *expr = build_tree_shape(base_type, &tsp, &terminalp);
1041 ovs_assert(terminalp == &terminals[n_terminals]);
1043 if (verbosity > 0) {
1044 print_tree_shape(ts, n_tses);
1046 struct ds s = DS_EMPTY_INITIALIZER;
1047 expr_format(expr, &s);
1053 if (test_parallel > 1) {
1054 pid_t pid = xfork();
1056 test_tree_shape_exhaustively(expr, &symtab,
1057 terminals, n_terminals,
1058 vars, test_vars, test_bits);
1062 if (n_children >= test_parallel) {
1063 wait_pid(children, &n_children);
1065 children[n_children++] = pid;
1070 n_tested += test_tree_shape_exhaustively(
1071 expr, &symtab, terminals, n_terminals,
1072 vars, test_vars, test_bits);
1078 while (n_children > 0) {
1079 wait_pid(children, &n_children);
1085 switch (operation) {
1087 printf("converting");
1090 printf("simplifying");
1093 printf("normalizing");
1096 printf("converting to flows");
1100 printf(" %d expressions of %d terminals", n_tested, n_terminals);
1102 printf(" all %d-terminal expressions", n_terminals);
1104 printf(" with %d vars each of %d bits in terms of operators",
1105 test_vars, test_bits);
1106 for (unsigned int relops = test_relops; relops;
1107 relops = zero_rightmost_1bit(relops)) {
1108 enum expr_relop r = rightmost_1bit_idx(relops);
1109 printf(" %s", expr_relop_to_string(r));
1113 expr_symtab_destroy(&symtab);
1114 shash_destroy(&symtab);
1120 test_parse_actions(struct ovs_cmdl_context *ctx OVS_UNUSED)
1122 struct shash symtab;
1126 create_symtab(&symtab);
1129 simap_put(&ports, "eth0", 5);
1130 simap_put(&ports, "eth1", 6);
1131 simap_put(&ports, "LOCAL", ofp_to_u16(OFPP_LOCAL));
1134 while (!ds_get_test_line(&input, stdin)) {
1135 struct ofpbuf ofpacts;
1136 struct expr *prereqs;
1139 ofpbuf_init(&ofpacts, 0);
1140 error = actions_parse_string(ds_cstr(&input), &symtab, &ports, 11,
1141 &ofpacts, &prereqs);
1146 ds_put_cstr(&output, "actions=");
1147 ofpacts_format(ofpacts.data, ofpacts.size, &output);
1148 ds_put_cstr(&output, ", prereqs=");
1150 expr_format(prereqs, &output);
1152 ds_put_char(&output, '1');
1154 puts(ds_cstr(&output));
1155 ds_destroy(&output);
1161 expr_destroy(prereqs);
1162 ofpbuf_uninit(&ofpacts);
1166 simap_destroy(&ports);
1167 expr_symtab_destroy(&symtab);
1168 shash_destroy(&symtab);
1172 parse_relops(const char *s)
1174 unsigned int relops = 0;
1177 lexer_init(&lexer, s);
1180 enum expr_relop relop;
1182 if (expr_relop_from_token(lexer.token.type, &relop)) {
1183 relops |= 1u << relop;
1186 ovs_fatal(0, "%s: relational operator expected at `%.*s'",
1187 s, (int) (lexer.input - lexer.start), lexer.start);
1189 lexer_match(&lexer, LEX_T_COMMA);
1190 } while (lexer.token.type != LEX_T_END);
1191 lexer_destroy(&lexer);
1200 %s: OVN test utility\n\
1201 usage: test-ovn %s [OPTIONS] COMMAND [ARG...]\n\
1204 Lexically analyzes OVN input from stdin and print them back on stdout.\n\
1211 Parses OVN expressions from stdin and print them back on stdout after\n\
1212 differing degrees of analysis. Available fields are based on packet\n\
1215 evaluate-expr A B C\n\
1216 Parses OVN expressions from stdin, evaluate them with assigned values,\n\
1217 and print the results on stdout. Available fields are 'a', 'b', and 'c'\n\
1218 of 3 bits each. A, B, and C should be in the range 0 to 7.\n\
1221 Prints all the compositions of N on stdout.\n\
1224 Prints all the tree shapes with N terminals on stdout.\n\
1227 Tests that all possible Boolean expressions with N terminals are properly\n\
1228 simplified, normalized, and converted to flows. Available options:\n\
1229 --relops=OPERATORS Test only the specified Boolean operators.\n\
1230 OPERATORS may include == != < <= > >=, space or\n\
1231 comma separated. Default is all operators.\n\
1232 --vars=N Number of variables to test, in range 1...4, default 2.\n\
1233 --bits=N Number of bits per variable, in range 1...3, default 3.\n\
1234 --operation=OPERATION Operation to test, one of: convert, simplify,\n\
1235 normalize, flow. Default: flow. 'normalize' includes 'simplify',\n\
1236 'flow' includes 'simplify' and 'normaize'.\n\
1237 --parallel=N Number of processes to use in parallel, default 1.\n\
1239 program_name, program_name);
1244 test_ovn_main(int argc, char *argv[])
1246 set_program_name(argv[0]);
1248 test_relops = parse_relops("== != < <= > >=");
1251 OPT_RELOPS = UCHAR_MAX + 1,
1258 static const struct option options[] = {
1259 {"relops", required_argument, NULL, OPT_RELOPS},
1260 {"vars", required_argument, NULL, OPT_VARS},
1261 {"bits", required_argument, NULL, OPT_BITS},
1262 {"operation", required_argument, NULL, OPT_OPERATION},
1263 {"parallel", required_argument, NULL, OPT_PARALLEL},
1264 {"more", no_argument, NULL, 'm'},
1265 {"help", no_argument, NULL, 'h'},
1268 int option_index = 0;
1269 int c = getopt_long (argc, argv, "", options, &option_index);
1276 test_relops = parse_relops(optarg);
1280 test_vars = atoi(optarg);
1281 if (test_vars < 1 || test_vars > 4) {
1282 ovs_fatal(0, "number of variables must be between 1 and 4");
1287 test_bits = atoi(optarg);
1288 if (test_bits < 1 || test_bits > 3) {
1289 ovs_fatal(0, "number of bits must be between 1 and 3");
1294 if (!strcmp(optarg, "convert")) {
1295 operation = OP_CONVERT;
1296 } else if (!strcmp(optarg, "simplify")) {
1297 operation = OP_SIMPLIFY;
1298 } else if (!strcmp(optarg, "normalize")) {
1299 operation = OP_NORMALIZE;
1300 } else if (!strcmp(optarg, "flow")) {
1301 operation = OP_FLOW;
1303 ovs_fatal(0, "%s: unknown operation", optarg);
1308 test_parallel = atoi(optarg);
1326 static const struct ovs_cmdl_command commands[] = {
1328 {"lex", NULL, 0, 0, test_lex},
1331 {"parse-expr", NULL, 0, 0, test_parse_expr},
1332 {"annotate-expr", NULL, 0, 0, test_annotate_expr},
1333 {"simplify-expr", NULL, 0, 0, test_simplify_expr},
1334 {"normalize-expr", NULL, 0, 0, test_normalize_expr},
1335 {"expr-to-flows", NULL, 0, 0, test_expr_to_flows},
1336 {"evaluate-expr", NULL, 1, 1, test_evaluate_expr},
1337 {"composition", NULL, 1, 1, test_composition},
1338 {"tree-shape", NULL, 1, 1, test_tree_shape},
1339 {"exhaustive", NULL, 1, 1, test_exhaustive},
1342 {"parse-actions", NULL, 0, 0, test_parse_actions},
1344 {NULL, NULL, 0, 0, NULL},
1346 struct ovs_cmdl_context ctx;
1347 ctx.argc = argc - optind;
1348 ctx.argv = argv + optind;
1349 ovs_cmdl_run_command(&ctx, commands);
1352 OVSTEST_REGISTER("test-ovn", test_ovn_main);