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 /* --nvars: Number of numeric variables to test, in exhaustive test. */
41 static int test_nvars = 2;
43 /* --svars: Number of string variables to test, in exhaustive test. */
44 static int test_svars = 2;
46 /* --bits: Number of bits per variable, in exhaustive test. */
47 static int test_bits = 3;
49 /* --operation: The operation to test, in exhaustive test. */
50 static enum { OP_CONVERT, OP_SIMPLIFY, OP_NORMALIZE, OP_FLOW } operation
53 /* --parallel: Number of parallel processes to use in test. */
54 static int test_parallel = 1;
56 /* -m, --more: Message verbosity */
60 compare_token(const struct lex_token *a, const struct lex_token *b)
62 if (a->type != b->type) {
63 fprintf(stderr, "type differs: %d -> %d\n", a->type, b->type);
67 if (!((a->s && b->s && !strcmp(a->s, b->s))
68 || (!a->s && !b->s))) {
69 fprintf(stderr, "string differs: %s -> %s\n",
70 a->s ? a->s : "(null)",
71 b->s ? b->s : "(null)");
75 if (a->type == LEX_T_INTEGER || a->type == LEX_T_MASKED_INTEGER) {
76 if (memcmp(&a->value, &b->value, sizeof a->value)) {
77 fprintf(stderr, "value differs\n");
81 if (a->type == LEX_T_MASKED_INTEGER
82 && memcmp(&a->mask, &b->mask, sizeof a->mask)) {
83 fprintf(stderr, "mask differs\n");
87 if (a->format != b->format
88 && !(a->format == LEX_F_HEXADECIMAL
89 && b->format == LEX_F_DECIMAL
90 && a->value.integer == 0)) {
91 fprintf(stderr, "format differs: %d -> %d\n",
92 a->format, b->format);
98 test_lex(struct ovs_cmdl_context *ctx OVS_UNUSED)
105 while (!ds_get_test_line(&input, stdin)) {
108 lexer_init(&lexer, ds_cstr(&input));
110 while (lexer_get(&lexer) != LEX_T_END) {
111 size_t len = output.length;
112 lex_token_format(&lexer.token, &output);
114 /* Check that the formatted version can really be parsed back
116 if (lexer.token.type != LEX_T_ERROR) {
117 const char *s = ds_cstr(&output) + len;
122 compare_token(&lexer.token, &l2.token);
125 ds_put_char(&output, ' ');
127 lexer_destroy(&lexer);
129 ds_chomp(&output, ' ');
130 puts(ds_cstr(&output));
137 create_symtab(struct shash *symtab)
141 /* Reserve a pair of registers for the logical inport and outport. A full
142 * 32-bit register each is bigger than we need, but the expression code
143 * doesn't yet support string fields that occupy less than a full OXM. */
144 expr_symtab_add_string(symtab, "inport", MFF_REG6, NULL);
145 expr_symtab_add_string(symtab, "outport", MFF_REG7, NULL);
147 expr_symtab_add_field(symtab, "xreg0", MFF_XREG0, NULL, false);
148 expr_symtab_add_field(symtab, "xreg1", MFF_XREG1, NULL, false);
149 expr_symtab_add_field(symtab, "xreg2", MFF_XREG2, NULL, false);
151 expr_symtab_add_subfield(symtab, "reg0", NULL, "xreg0[32..63]");
152 expr_symtab_add_subfield(symtab, "reg1", NULL, "xreg0[0..31]");
153 expr_symtab_add_subfield(symtab, "reg2", NULL, "xreg1[32..63]");
154 expr_symtab_add_subfield(symtab, "reg3", NULL, "xreg1[0..31]");
155 expr_symtab_add_subfield(symtab, "reg4", NULL, "xreg2[32..63]");
156 expr_symtab_add_subfield(symtab, "reg5", NULL, "xreg2[0..31]");
158 expr_symtab_add_field(symtab, "eth.src", MFF_ETH_SRC, NULL, false);
159 expr_symtab_add_field(symtab, "eth.dst", MFF_ETH_DST, NULL, false);
160 expr_symtab_add_field(symtab, "eth.type", MFF_ETH_TYPE, NULL, true);
162 expr_symtab_add_field(symtab, "vlan.tci", MFF_VLAN_TCI, NULL, false);
163 expr_symtab_add_predicate(symtab, "vlan.present", "vlan.tci[12]");
164 expr_symtab_add_subfield(symtab, "vlan.pcp", "vlan.present",
166 expr_symtab_add_subfield(symtab, "vlan.vid", "vlan.present",
169 expr_symtab_add_predicate(symtab, "ip4", "eth.type == 0x800");
170 expr_symtab_add_predicate(symtab, "ip6", "eth.type == 0x86dd");
171 expr_symtab_add_predicate(symtab, "ip", "ip4 || ip6");
172 expr_symtab_add_field(symtab, "ip.proto", MFF_IP_PROTO, "ip", true);
173 expr_symtab_add_field(symtab, "ip.dscp", MFF_IP_DSCP, "ip", false);
174 expr_symtab_add_field(symtab, "ip.ecn", MFF_IP_ECN, "ip", false);
175 expr_symtab_add_field(symtab, "ip.ttl", MFF_IP_TTL, "ip", false);
177 expr_symtab_add_field(symtab, "ip4.src", MFF_IPV4_SRC, "ip4", false);
178 expr_symtab_add_field(symtab, "ip4.dst", MFF_IPV4_DST, "ip4", false);
180 expr_symtab_add_predicate(symtab, "icmp4", "ip4 && ip.proto == 1");
181 expr_symtab_add_field(symtab, "icmp4.type", MFF_ICMPV4_TYPE, "icmp4",
183 expr_symtab_add_field(symtab, "icmp4.code", MFF_ICMPV4_CODE, "icmp4",
186 expr_symtab_add_field(symtab, "ip6.src", MFF_IPV6_SRC, "ip6", false);
187 expr_symtab_add_field(symtab, "ip6.dst", MFF_IPV6_DST, "ip6", false);
188 expr_symtab_add_field(symtab, "ip6.label", MFF_IPV6_LABEL, "ip6", false);
190 expr_symtab_add_predicate(symtab, "icmp6", "ip6 && ip.proto == 58");
191 expr_symtab_add_field(symtab, "icmp6.type", MFF_ICMPV6_TYPE, "icmp6",
193 expr_symtab_add_field(symtab, "icmp6.code", MFF_ICMPV6_CODE, "icmp6",
196 expr_symtab_add_predicate(symtab, "icmp", "icmp4 || icmp6");
198 expr_symtab_add_field(symtab, "ip.frag", MFF_IP_FRAG, "ip", false);
199 expr_symtab_add_predicate(symtab, "ip.is_frag", "ip.frag[0]");
200 expr_symtab_add_predicate(symtab, "ip.later_frag", "ip.frag[1]");
201 expr_symtab_add_predicate(symtab, "ip.first_frag", "ip.is_frag && !ip.later_frag");
203 expr_symtab_add_predicate(symtab, "arp", "eth.type == 0x806");
204 expr_symtab_add_field(symtab, "arp.op", MFF_ARP_OP, "arp", false);
205 expr_symtab_add_field(symtab, "arp.spa", MFF_ARP_SPA, "arp", false);
206 expr_symtab_add_field(symtab, "arp.sha", MFF_ARP_SHA, "arp", false);
207 expr_symtab_add_field(symtab, "arp.tpa", MFF_ARP_TPA, "arp", false);
208 expr_symtab_add_field(symtab, "arp.tha", MFF_ARP_THA, "arp", false);
210 expr_symtab_add_predicate(symtab, "nd", "icmp6.type == {135, 136} && icmp6.code == 0");
211 expr_symtab_add_field(symtab, "nd.target", MFF_ND_TARGET, "nd", false);
212 expr_symtab_add_field(symtab, "nd.sll", MFF_ND_SLL,
213 "nd && icmp6.type == 135", false);
214 expr_symtab_add_field(symtab, "nd.tll", MFF_ND_TLL,
215 "nd && icmp6.type == 136", false);
217 expr_symtab_add_predicate(symtab, "tcp", "ip.proto == 6");
218 expr_symtab_add_field(symtab, "tcp.src", MFF_TCP_SRC, "tcp", false);
219 expr_symtab_add_field(symtab, "tcp.dst", MFF_TCP_DST, "tcp", false);
220 expr_symtab_add_field(symtab, "tcp.flags", MFF_TCP_FLAGS, "tcp", false);
222 expr_symtab_add_predicate(symtab, "udp", "ip.proto == 17");
223 expr_symtab_add_field(symtab, "udp.src", MFF_UDP_SRC, "udp", false);
224 expr_symtab_add_field(symtab, "udp.dst", MFF_UDP_DST, "udp", false);
226 expr_symtab_add_predicate(symtab, "sctp", "ip.proto == 132");
227 expr_symtab_add_field(symtab, "sctp.src", MFF_SCTP_SRC, "sctp", false);
228 expr_symtab_add_field(symtab, "sctp.dst", MFF_SCTP_DST, "sctp", false);
230 /* For negative testing. */
231 expr_symtab_add_field(symtab, "bad_prereq", MFF_XREG0, "xyzzy", false);
232 expr_symtab_add_field(symtab, "self_recurse", MFF_XREG0,
233 "self_recurse != 0", false);
234 expr_symtab_add_field(symtab, "mutual_recurse_1", MFF_XREG0,
235 "mutual_recurse_2 != 0", false);
236 expr_symtab_add_field(symtab, "mutual_recurse_2", MFF_XREG0,
237 "mutual_recurse_1 != 0", false);
238 expr_symtab_add_string(symtab, "big_string", MFF_XREG0, NULL);
242 test_parse_expr__(int steps)
248 create_symtab(&symtab);
251 simap_put(&ports, "eth0", 5);
252 simap_put(&ports, "eth1", 6);
253 simap_put(&ports, "LOCAL", ofp_to_u16(OFPP_LOCAL));
256 while (!ds_get_test_line(&input, stdin)) {
260 expr = expr_parse_string(ds_cstr(&input), &symtab, &error);
261 if (!error && steps > 0) {
262 expr = expr_annotate(expr, &symtab, &error);
266 expr = expr_simplify(expr);
269 expr = expr_normalize(expr);
270 ovs_assert(expr_is_normalized(expr));
277 expr_to_matches(expr, &ports, &matches);
278 expr_matches_print(&matches, stdout);
279 expr_matches_destroy(&matches);
281 struct ds output = DS_EMPTY_INITIALIZER;
282 expr_format(expr, &output);
283 puts(ds_cstr(&output));
294 simap_destroy(&ports);
295 expr_symtab_destroy(&symtab);
296 shash_destroy(&symtab);
300 test_parse_expr(struct ovs_cmdl_context *ctx OVS_UNUSED)
302 test_parse_expr__(0);
306 test_annotate_expr(struct ovs_cmdl_context *ctx OVS_UNUSED)
308 test_parse_expr__(1);
312 test_simplify_expr(struct ovs_cmdl_context *ctx OVS_UNUSED)
314 test_parse_expr__(2);
318 test_normalize_expr(struct ovs_cmdl_context *ctx OVS_UNUSED)
320 test_parse_expr__(3);
324 test_expr_to_flows(struct ovs_cmdl_context *ctx OVS_UNUSED)
326 test_parse_expr__(4);
329 /* Evaluate an expression. */
331 static bool evaluate_expr(const struct expr *, unsigned int subst, int n_bits);
334 evaluate_andor_expr(const struct expr *expr, unsigned int subst, int n_bits,
337 const struct expr *sub;
339 LIST_FOR_EACH (sub, node, &expr->andor) {
340 if (evaluate_expr(sub, subst, n_bits) == short_circuit) {
341 return short_circuit;
344 return !short_circuit;
348 evaluate_cmp_expr(const struct expr *expr, unsigned int subst, int n_bits)
350 int var_idx = atoi(expr->cmp.symbol->name + 1);
351 if (expr->cmp.symbol->name[0] == 'n') {
352 unsigned var_mask = (1u << n_bits) - 1;
353 unsigned int arg1 = (subst >> (var_idx * n_bits)) & var_mask;
354 unsigned int arg2 = ntohll(expr->cmp.value.integer);
355 unsigned int mask = ntohll(expr->cmp.mask.integer);
357 ovs_assert(!(mask & ~var_mask));
358 ovs_assert(!(arg2 & ~var_mask));
359 ovs_assert(!(arg2 & ~mask));
362 switch (expr->cmp.relop) {
384 } else if (expr->cmp.symbol->name[0] == 's') {
385 unsigned int arg1 = (subst >> (test_nvars * n_bits + var_idx)) & 1;
386 unsigned int arg2 = atoi(expr->cmp.string);
393 /* Evaluates 'expr' and returns its Boolean result. 'subst' provides the value
394 * for the variables, which must be 'n_bits' bits each and be named "a", "b",
395 * "c", etc. The value of variable "a" is the least-significant 'n_bits' bits
396 * of 'subst', the value of "b" is the next 'n_bits' bits, and so on. */
398 evaluate_expr(const struct expr *expr, unsigned int subst, int n_bits)
400 switch (expr->type) {
402 return evaluate_cmp_expr(expr, subst, n_bits);
405 return evaluate_andor_expr(expr, subst, n_bits, false);
408 return evaluate_andor_expr(expr, subst, n_bits, true);
411 return expr->boolean;
419 test_evaluate_expr(struct ovs_cmdl_context *ctx)
421 int a = atoi(ctx->argv[1]);
422 int b = atoi(ctx->argv[2]);
423 int c = atoi(ctx->argv[3]);
424 unsigned int subst = a | (b << 3) || (c << 6);
429 expr_symtab_add_field(&symtab, "xreg0", MFF_XREG0, NULL, false);
430 expr_symtab_add_field(&symtab, "xreg1", MFF_XREG1, NULL, false);
431 expr_symtab_add_field(&symtab, "xreg2", MFF_XREG1, NULL, false);
432 expr_symtab_add_subfield(&symtab, "a", NULL, "xreg0[0..2]");
433 expr_symtab_add_subfield(&symtab, "b", NULL, "xreg1[0..2]");
434 expr_symtab_add_subfield(&symtab, "c", NULL, "xreg2[0..2]");
437 while (!ds_get_test_line(&input, stdin)) {
441 expr = expr_parse_string(ds_cstr(&input), &symtab, &error);
443 expr = expr_annotate(expr, &symtab, &error);
446 printf("%d\n", evaluate_expr(expr, subst, 3));
455 expr_symtab_destroy(&symtab);
456 shash_destroy(&symtab);
461 * The "compositions" of a positive integer N are all of the ways that one can
462 * add up positive integers to sum to N. For example, the compositions of 3
463 * are 3, 2+1, 1+2, and 1+1+1.
465 * We use compositions to find all the ways to break up N terms of a Boolean
466 * expression into subexpressions. Suppose we want to generate all expressions
467 * with 3 terms. The compositions of 3 (ignoring 3 itself) provide the
468 * possibilities (x && x) || x, x || (x && x), and x || x || x. (Of course one
469 * can exchange && for || in each case.) One must recursively compose the
470 * sub-expressions whose values are 3 or greater; that is what the "tree shape"
471 * concept later covers.
473 * To iterate through all compositions of, e.g., 5:
475 * unsigned int state;
479 * for (n = first_composition(ARRAY_SIZE(s), &state, s); n > 0;
480 * n = next_composition(&state, s, n)) {
481 * // Do something with composition 's' with 'n' elements.
484 * Algorithm from D. E. Knuth, _The Art of Computer Programming, Vol. 4A:
485 * Combinatorial Algorithms, Part 1_, section 7.2.1.1, answer to exercise
489 /* Begins iteration through the compositions of 'n'. Initializes 's' to the
490 * number of elements in the first composition of 'n' and returns that number
491 * of elements. The first composition in fact is always 'n' itself, so the
492 * return value will be 1.
494 * Initializes '*state' to some internal state information. The caller must
495 * maintain this state (and 's') for use by next_composition().
497 * 's' must have room for at least 'n' elements. */
499 first_composition(int n, unsigned int *state, int s[])
506 /* Advances 's', with 'sn' elements, to the next composition and returns the
507 * number of elements in this new composition, or 0 if no compositions are
508 * left. 'state' is the same internal state passed to first_composition(). */
510 next_composition(unsigned int *state, int s[], int sn)
541 test_composition(struct ovs_cmdl_context *ctx)
543 int n = atoi(ctx->argv[1]);
547 for (int sn = first_composition(n, &state, s); sn;
548 sn = next_composition(&state, s, sn)) {
549 for (int i = 0; i < sn; i++) {
550 printf("%d%c", s[i], i == sn - 1 ? '\n' : ' ');
557 * This code generates all possible Boolean expressions with a specified number
558 * of terms N (equivalent to the number of external nodes in a tree).
560 * See test_tree_shape() for a simple example. */
562 /* An array of these structures describes the shape of a tree.
564 * A single element of struct tree_shape describes a single node in the tree.
565 * The node has 'sn' direct children. From left to right, for i in 0...sn-1,
566 * s[i] is 1 if the child is a leaf node, otherwise the child is a subtree and
567 * s[i] is the number of leaf nodes within that subtree. In the latter case,
568 * the subtree is described by another struct tree_shape within the enclosing
569 * array. The tree_shapes are ordered in the array in in-order.
578 init_tree_shape__(struct tree_shape ts[], int n)
585 /* Skip the first composition intentionally. */
586 ts->sn = first_composition(n, &ts->state, ts->s);
587 ts->sn = next_composition(&ts->state, ts->s, ts->sn);
588 for (int i = 0; i < ts->sn; i++) {
589 n_tses += init_tree_shape__(&ts[n_tses], ts->s[i]);
594 /* Initializes 'ts[]' as the first in the set of all of possible shapes of
595 * trees with 'n' leaves. Returns the number of "struct tree_shape"s in the
596 * first tree shape. */
598 init_tree_shape(struct tree_shape ts[], int n)
611 return init_tree_shape__(ts, n);
615 /* Advances 'ts', which currently has 'n_tses' elements, to the next possible
616 * tree shape with the number of leaves passed to init_tree_shape(). Returns
617 * the number of "struct tree_shape"s in the next shape, or 0 if all tree
618 * shapes have been visited. */
620 next_tree_shape(struct tree_shape ts[], int n_tses)
622 if (n_tses == 1 && ts->sn == 2 && ts->s[0] == 1 && ts->s[1] == 1) {
626 struct tree_shape *p = &ts[n_tses - 1];
627 p->sn = p->sn > 1 ? next_composition(&p->state, p->s, p->sn) : 0;
629 for (int i = 0; i < p->sn; i++) {
630 n_tses += init_tree_shape__(&ts[n_tses], p->s[i]);
640 print_tree_shape(const struct tree_shape ts[], int n_tses)
642 for (int i = 0; i < n_tses; i++) {
646 for (int j = 0; j < ts[i].sn; j++) {
658 test_tree_shape(struct ovs_cmdl_context *ctx)
660 int n = atoi(ctx->argv[1]);
661 struct tree_shape ts[50];
664 for (n_tses = init_tree_shape(ts, n); n_tses;
665 n_tses = next_tree_shape(ts, n_tses)) {
666 print_tree_shape(ts, n_tses);
671 /* Iteration through all possible terminal expressions (e.g. EXPR_T_CMP and
672 * EXPR_T_BOOLEAN expressions).
674 * Given a tree shape, this allows the code to try all possible ways to plug in
679 * struct expr terminal;
680 * const struct expr_symbol *vars = ...;
684 * init_terminal(&terminal, vars[0]);
686 * // Something with 'terminal'.
687 * } while (next_terminal(&terminal, vars, n_vars, n_bits));
690 /* Sets 'expr' to the first possible terminal expression. 'var' should be the
691 * first variable in the ones to be tested. */
693 init_terminal(struct expr *expr, int phase,
694 const struct expr_symbol *nvars[], int n_nvars,
695 const struct expr_symbol *svars[], int n_svars)
697 if (phase < 1 && n_nvars) {
698 expr->type = EXPR_T_CMP;
699 expr->cmp.symbol = nvars[0];
700 expr->cmp.relop = rightmost_1bit_idx(test_relops);
701 memset(&expr->cmp.value, 0, sizeof expr->cmp.value);
702 memset(&expr->cmp.mask, 0, sizeof expr->cmp.mask);
703 expr->cmp.value.integer = htonll(0);
704 expr->cmp.mask.integer = htonll(1);
708 if (phase < 2 && n_svars) {
709 expr->type = EXPR_T_CMP;
710 expr->cmp.symbol = svars[0];
711 expr->cmp.relop = EXPR_R_EQ;
712 expr->cmp.string = xstrdup("0");
716 expr->type = EXPR_T_BOOLEAN;
717 expr->boolean = false;
720 /* Returns 'x' with the rightmost contiguous string of 1s changed to 0s,
721 * e.g. 01011100 => 01000000. See H. S. Warren, Jr., _Hacker's Delight_, 2nd
722 * ed., section 2-1. */
724 turn_off_rightmost_1s(unsigned int x)
726 return ((x & -x) + x) & x;
729 static const struct expr_symbol *
730 next_var(const struct expr_symbol *symbol,
731 const struct expr_symbol *vars[], int n_vars)
733 for (int i = 0; i < n_vars; i++) {
734 if (symbol == vars[i]) {
735 return i + 1 >= n_vars ? NULL : vars[i + 1];
741 static enum expr_relop
742 next_relop(enum expr_relop relop)
744 unsigned int remaining_relops = test_relops & ~((1u << (relop + 1)) - 1);
745 return (remaining_relops
746 ? rightmost_1bit_idx(remaining_relops)
747 : rightmost_1bit_idx(test_relops));
750 /* Advances 'expr' to the next possible terminal expression within the 'n_vars'
751 * variables of 'n_bits' bits each in 'vars[]'. */
753 next_terminal(struct expr *expr,
754 const struct expr_symbol *nvars[], int n_nvars, int n_bits,
755 const struct expr_symbol *svars[], int n_svars)
757 if (expr->type == EXPR_T_BOOLEAN) {
761 expr->boolean = true;
766 if (!expr->cmp.symbol->width) {
767 int next_value = atoi(expr->cmp.string) + 1;
768 free(expr->cmp.string);
769 if (next_value > 1) {
770 expr->cmp.symbol = next_var(expr->cmp.symbol, svars, n_svars);
771 if (!expr->cmp.symbol) {
772 init_terminal(expr, 2, nvars, n_nvars, svars, n_svars);
777 expr->cmp.string = xasprintf("%d", next_value);
783 next = (ntohll(expr->cmp.value.integer)
784 + (ntohll(expr->cmp.mask.integer) << n_bits));
787 unsigned m = next >> n_bits;
788 unsigned v = next & ((1u << n_bits) - 1);
789 if (next >= (1u << (2 * n_bits))) {
790 enum expr_relop old_relop = expr->cmp.relop;
791 expr->cmp.relop = next_relop(old_relop);
792 if (expr->cmp.relop <= old_relop) {
793 expr->cmp.symbol = next_var(expr->cmp.symbol, nvars, n_nvars);
794 if (!expr->cmp.symbol) {
795 init_terminal(expr, 1, nvars, n_nvars, svars, n_svars);
801 /* Skip: empty mask is pathological. */
803 /* Skip: 1-bits in value correspond to 0-bits in mask. */
804 } else if (turn_off_rightmost_1s(m)
805 && (expr->cmp.relop != EXPR_R_EQ &&
806 expr->cmp.relop != EXPR_R_NE)) {
807 /* Skip: can't have discontiguous mask for > >= < <=. */
809 expr->cmp.value.integer = htonll(v);
810 expr->cmp.mask.integer = htonll(m);
817 make_terminal(struct expr ***terminalp)
819 struct expr *e = expr_create_boolean(true);
826 build_simple_tree(enum expr_type type, int n, struct expr ***terminalp)
829 struct expr *e = expr_create_andor(type);
830 for (int i = 0; i < 2; i++) {
831 struct expr *sub = make_terminal(terminalp);
832 list_push_back(&e->andor, &sub->node);
836 return make_terminal(terminalp);
843 build_tree_shape(enum expr_type type, const struct tree_shape **tsp,
844 struct expr ***terminalp)
846 const struct tree_shape *ts = *tsp;
849 struct expr *e = expr_create_andor(type);
850 enum expr_type t = type == EXPR_T_AND ? EXPR_T_OR : EXPR_T_AND;
851 for (int i = 0; i < ts->sn; i++) {
852 struct expr *sub = (ts->s[i] > 2
853 ? build_tree_shape(t, tsp, terminalp)
854 : build_simple_tree(t, ts->s[i], terminalp));
855 list_push_back(&e->andor, &sub->node);
865 free_rule(struct test_rule *test_rule)
867 cls_rule_destroy(&test_rule->cr);
872 test_tree_shape_exhaustively(struct expr *expr, struct shash *symtab,
873 struct expr *terminals[], int n_terminals,
874 const struct expr_symbol *nvars[], int n_nvars,
876 const struct expr_symbol *svars[], int n_svars)
878 struct simap string_map = SIMAP_INITIALIZER(&string_map);
879 simap_put(&string_map, "0", 0);
880 simap_put(&string_map, "1", 1);
884 const unsigned int var_mask = (1u << n_bits) - 1;
885 for (int i = 0; i < n_terminals; i++) {
886 init_terminal(terminals[i], 0, nvars, n_nvars, svars, n_svars);
889 struct ds s = DS_EMPTY_INITIALIZER;
891 memset(&f, 0, sizeof f);
893 for (int i = n_terminals - 1; ; i--) {
896 simap_destroy(&string_map);
899 if (next_terminal(terminals[i], nvars, n_nvars, n_bits,
903 init_terminal(terminals[i], 0, nvars, n_nvars, svars, n_svars);
905 ovs_assert(expr_honors_invariants(expr));
909 struct expr *modified;
910 if (operation == OP_CONVERT) {
912 expr_format(expr, &s);
915 modified = expr_parse_string(ds_cstr(&s), symtab, &error);
917 fprintf(stderr, "%s fails to parse (%s)\n",
921 } else if (operation >= OP_SIMPLIFY) {
922 modified = expr_simplify(expr_clone(expr));
923 ovs_assert(expr_honors_invariants(modified));
925 if (operation >= OP_NORMALIZE) {
926 modified = expr_normalize(modified);
927 ovs_assert(expr_is_normalized(modified));
932 struct classifier cls;
933 if (operation >= OP_FLOW) {
934 struct expr_match *m;
935 struct test_rule *test_rule;
937 expr_to_matches(modified, &string_map, &matches);
939 classifier_init(&cls, NULL);
940 HMAP_FOR_EACH (m, hmap_node, &matches) {
941 test_rule = xmalloc(sizeof *test_rule);
942 cls_rule_init(&test_rule->cr, &m->match, 0);
943 classifier_insert(&cls, &test_rule->cr, CLS_MIN_VERSION,
944 m->conjunctions, m->n);
947 for (int subst = 0; subst < 1 << (n_bits * n_nvars + n_svars);
949 bool expected = evaluate_expr(expr, subst, n_bits);
950 bool actual = evaluate_expr(modified, subst, n_bits);
951 if (actual != expected) {
952 struct ds expr_s, modified_s;
955 expr_format(expr, &expr_s);
957 ds_init(&modified_s);
958 expr_format(modified, &modified_s);
961 "%s evaluates to %d, but %s evaluates to %d, for",
962 ds_cstr(&expr_s), expected,
963 ds_cstr(&modified_s), actual);
964 for (int i = 0; i < n_nvars; i++) {
968 fprintf(stderr, " n%d = 0x%x", i,
969 (subst >> (n_bits * i)) & var_mask);
971 for (int i = 0; i < n_svars; i++) {
972 fprintf(stderr, ", s%d = \"%d\"", i,
973 (subst >> (n_bits * n_nvars + i)) & 1);
979 if (operation >= OP_FLOW) {
980 for (int i = 0; i < n_nvars; i++) {
981 f.regs[i] = (subst >> (i * n_bits)) & var_mask;
983 for (int i = 0; i < n_svars; i++) {
984 f.regs[n_nvars + i] = ((subst >> (n_nvars * n_bits + i))
987 bool found = classifier_lookup(&cls, CLS_MIN_VERSION,
989 if (expected != found) {
990 struct ds expr_s, modified_s;
993 expr_format(expr, &expr_s);
995 ds_init(&modified_s);
996 expr_format(modified, &modified_s);
999 "%s and %s evaluate to %d, for",
1000 ds_cstr(&expr_s), ds_cstr(&modified_s), expected);
1001 for (int i = 0; i < n_nvars; i++) {
1005 fprintf(stderr, " n%d = 0x%x", i,
1006 (subst >> (n_bits * i)) & var_mask);
1008 for (int i = 0; i < n_svars; i++) {
1009 fprintf(stderr, ", s%d = \"%d\"", i,
1010 (subst >> (n_bits * n_nvars + i)) & 1);
1012 fputs(".\n", stderr);
1014 fprintf(stderr, "Converted to classifier:\n");
1015 expr_matches_print(&matches, stderr);
1017 "However, %s flow was found in the classifier.\n",
1018 found ? "a" : "no");
1023 if (operation >= OP_FLOW) {
1024 struct test_rule *test_rule;
1026 CLS_FOR_EACH (test_rule, cr, &cls) {
1027 classifier_remove(&cls, &test_rule->cr);
1028 ovsrcu_postpone(free_rule, test_rule);
1030 classifier_destroy(&cls);
1033 expr_matches_destroy(&matches);
1035 expr_destroy(modified);
1041 wait_pid(pid_t *pids, int *n)
1046 pid = waitpid(WAIT_ANY, &status, 0);
1048 ovs_fatal(errno, "waitpid failed");
1049 } else if (WIFEXITED(status)) {
1050 if (WEXITSTATUS(status)) {
1051 exit(WEXITSTATUS(status));
1053 } else if (WIFSIGNALED(status)) {
1054 raise(WTERMSIG(status));
1060 for (int i = 0; i < *n; i++) {
1061 if (pids[i] == pid) {
1062 pids[i] = pids[--*n];
1066 ovs_fatal(0, "waitpid returned unknown child");
1071 test_exhaustive(struct ovs_cmdl_context *ctx OVS_UNUSED)
1073 int n_terminals = atoi(ctx->argv[1]);
1074 struct tree_shape ts[50];
1077 struct shash symtab;
1078 const struct expr_symbol *nvars[4];
1079 const struct expr_symbol *svars[4];
1081 ovs_assert(test_nvars <= ARRAY_SIZE(nvars));
1082 ovs_assert(test_svars <= ARRAY_SIZE(svars));
1083 ovs_assert(test_nvars + test_svars <= FLOW_N_REGS);
1085 shash_init(&symtab);
1086 for (int i = 0; i < test_nvars; i++) {
1087 char *name = xasprintf("n%d", i);
1088 nvars[i] = expr_symtab_add_field(&symtab, name, MFF_REG0 + i, NULL,
1092 for (int i = 0; i < test_svars; i++) {
1093 char *name = xasprintf("s%d", i);
1094 svars[i] = expr_symtab_add_string(&symtab, name,
1095 MFF_REG0 + test_nvars + i, NULL);
1100 pid_t *children = xmalloc(test_parallel * sizeof *children);
1105 for (int i = 0; i < 2; i++) {
1106 enum expr_type base_type = i ? EXPR_T_OR : EXPR_T_AND;
1108 for (n_tses = init_tree_shape(ts, n_terminals); n_tses;
1109 n_tses = next_tree_shape(ts, n_tses)) {
1110 const struct tree_shape *tsp = ts;
1111 struct expr *terminals[50];
1112 struct expr **terminalp = terminals;
1113 struct expr *expr = build_tree_shape(base_type, &tsp, &terminalp);
1114 ovs_assert(terminalp == &terminals[n_terminals]);
1116 if (verbosity > 0) {
1117 print_tree_shape(ts, n_tses);
1119 struct ds s = DS_EMPTY_INITIALIZER;
1120 expr_format(expr, &s);
1126 if (test_parallel > 1) {
1127 pid_t pid = xfork();
1129 test_tree_shape_exhaustively(expr, &symtab,
1130 terminals, n_terminals,
1131 nvars, test_nvars, test_bits,
1136 if (n_children >= test_parallel) {
1137 wait_pid(children, &n_children);
1139 children[n_children++] = pid;
1144 n_tested += test_tree_shape_exhaustively(
1145 expr, &symtab, terminals, n_terminals,
1146 nvars, test_nvars, test_bits,
1153 while (n_children > 0) {
1154 wait_pid(children, &n_children);
1160 switch (operation) {
1162 printf("converting");
1165 printf("simplifying");
1168 printf("normalizing");
1171 printf("converting to flows");
1175 printf(" %d expressions of %d terminals", n_tested, n_terminals);
1177 printf(" all %d-terminal expressions", n_terminals);
1179 if (test_nvars || test_svars) {
1182 printf(" %d numeric vars (each %d bits) in terms of operators",
1183 test_nvars, test_bits);
1184 for (unsigned int relops = test_relops; relops;
1185 relops = zero_rightmost_1bit(relops)) {
1186 enum expr_relop r = rightmost_1bit_idx(relops);
1187 printf(" %s", expr_relop_to_string(r));
1190 if (test_nvars && test_svars) {
1194 printf(" %d string vars", test_svars);
1197 printf(" in terms of Boolean constants only");
1201 expr_symtab_destroy(&symtab);
1202 shash_destroy(&symtab);
1208 test_parse_actions(struct ovs_cmdl_context *ctx OVS_UNUSED)
1210 struct shash symtab;
1211 struct simap ports, ct_zones;
1214 create_symtab(&symtab);
1217 simap_put(&ports, "eth0", 5);
1218 simap_put(&ports, "eth1", 6);
1219 simap_put(&ports, "LOCAL", ofp_to_u16(OFPP_LOCAL));
1220 simap_init(&ct_zones);
1223 while (!ds_get_test_line(&input, stdin)) {
1224 struct ofpbuf ofpacts;
1225 struct expr *prereqs;
1228 ofpbuf_init(&ofpacts, 0);
1229 error = actions_parse_string(ds_cstr(&input), &symtab, &ports,
1230 &ct_zones, 16, 16, 10, 64,
1231 &ofpacts, &prereqs);
1236 ds_put_cstr(&output, "actions=");
1237 ofpacts_format(ofpacts.data, ofpacts.size, &output);
1238 ds_put_cstr(&output, ", prereqs=");
1240 expr_format(prereqs, &output);
1242 ds_put_char(&output, '1');
1244 puts(ds_cstr(&output));
1245 ds_destroy(&output);
1251 expr_destroy(prereqs);
1252 ofpbuf_uninit(&ofpacts);
1256 simap_destroy(&ports);
1257 simap_destroy(&ct_zones);
1258 expr_symtab_destroy(&symtab);
1259 shash_destroy(&symtab);
1263 parse_relops(const char *s)
1265 unsigned int relops = 0;
1268 lexer_init(&lexer, s);
1271 enum expr_relop relop;
1273 if (expr_relop_from_token(lexer.token.type, &relop)) {
1274 relops |= 1u << relop;
1277 ovs_fatal(0, "%s: relational operator expected at `%.*s'",
1278 s, (int) (lexer.input - lexer.start), lexer.start);
1280 lexer_match(&lexer, LEX_T_COMMA);
1281 } while (lexer.token.type != LEX_T_END);
1282 lexer_destroy(&lexer);
1291 %s: OVN test utility\n\
1292 usage: test-ovn %s [OPTIONS] COMMAND [ARG...]\n\
1295 Lexically analyzes OVN input from stdin and print them back on stdout.\n\
1302 Parses OVN expressions from stdin and print them back on stdout after\n\
1303 differing degrees of analysis. Available fields are based on packet\n\
1306 evaluate-expr A B C\n\
1307 Parses OVN expressions from stdin, evaluate them with assigned values,\n\
1308 and print the results on stdout. Available fields are 'a', 'b', and 'c'\n\
1309 of 3 bits each. A, B, and C should be in the range 0 to 7.\n\
1312 Prints all the compositions of N on stdout.\n\
1315 Prints all the tree shapes with N terminals on stdout.\n\
1318 Tests that all possible Boolean expressions with N terminals are properly\n\
1319 simplified, normalized, and converted to flows. Available options:\n\
1321 --operation=OPERATION Operation to test, one of: convert, simplify,\n\
1322 normalize, flow. Default: flow. 'normalize' includes 'simplify',\n\
1323 'flow' includes 'simplify' and 'normalize'.\n\
1324 --parallel=N Number of processes to use in parallel, default 1.\n\
1326 --nvars=N Number of numeric vars to test, in range 0...4, default 2.\n\
1327 --bits=N Number of bits per variable, in range 1...3, default 3.\n\
1328 --relops=OPERATORS Test only the specified Boolean operators.\n\
1329 OPERATORS may include == != < <= > >=, space or\n\
1330 comma separated. Default is all operators.\n\
1332 --svars=N Number of string vars to test, in range 0...4, default 2.\n\
1334 program_name, program_name);
1339 test_ovn_main(int argc, char *argv[])
1342 OPT_RELOPS = UCHAR_MAX + 1,
1349 static const struct option long_options[] = {
1350 {"relops", required_argument, NULL, OPT_RELOPS},
1351 {"nvars", required_argument, NULL, OPT_NVARS},
1352 {"svars", required_argument, NULL, OPT_SVARS},
1353 {"bits", required_argument, NULL, OPT_BITS},
1354 {"operation", required_argument, NULL, OPT_OPERATION},
1355 {"parallel", required_argument, NULL, OPT_PARALLEL},
1356 {"more", no_argument, NULL, 'm'},
1357 {"help", no_argument, NULL, 'h'},
1360 char *short_options = ovs_cmdl_long_options_to_short_options(long_options);
1362 set_program_name(argv[0]);
1364 test_relops = parse_relops("== != < <= > >=");
1366 int option_index = 0;
1367 int c = getopt_long (argc, argv, short_options, long_options,
1375 test_relops = parse_relops(optarg);
1379 test_nvars = atoi(optarg);
1380 if (test_nvars < 0 || test_nvars > 4) {
1381 ovs_fatal(0, "number of numeric variables must be "
1387 test_svars = atoi(optarg);
1388 if (test_svars < 0 || test_svars > 4) {
1389 ovs_fatal(0, "number of string variables must be "
1395 test_bits = atoi(optarg);
1396 if (test_bits < 1 || test_bits > 3) {
1397 ovs_fatal(0, "number of bits must be between 1 and 3");
1402 if (!strcmp(optarg, "convert")) {
1403 operation = OP_CONVERT;
1404 } else if (!strcmp(optarg, "simplify")) {
1405 operation = OP_SIMPLIFY;
1406 } else if (!strcmp(optarg, "normalize")) {
1407 operation = OP_NORMALIZE;
1408 } else if (!strcmp(optarg, "flow")) {
1409 operation = OP_FLOW;
1411 ovs_fatal(0, "%s: unknown operation", optarg);
1416 test_parallel = atoi(optarg);
1434 static const struct ovs_cmdl_command commands[] = {
1436 {"lex", NULL, 0, 0, test_lex},
1439 {"parse-expr", NULL, 0, 0, test_parse_expr},
1440 {"annotate-expr", NULL, 0, 0, test_annotate_expr},
1441 {"simplify-expr", NULL, 0, 0, test_simplify_expr},
1442 {"normalize-expr", NULL, 0, 0, test_normalize_expr},
1443 {"expr-to-flows", NULL, 0, 0, test_expr_to_flows},
1444 {"evaluate-expr", NULL, 1, 1, test_evaluate_expr},
1445 {"composition", NULL, 1, 1, test_composition},
1446 {"tree-shape", NULL, 1, 1, test_tree_shape},
1447 {"exhaustive", NULL, 1, 1, test_exhaustive},
1450 {"parse-actions", NULL, 0, 0, test_parse_actions},
1452 {NULL, NULL, 0, 0, NULL},
1454 struct ovs_cmdl_context ctx;
1455 ctx.argc = argc - optind;
1456 ctx.argv = argv + optind;
1457 ovs_cmdl_run_command(&ctx, commands);
1460 OVSTEST_REGISTER("test-ovn", test_ovn_main);