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 "ovn/lib/expr.h"
26 #include "ovn/lib/lex.h"
27 #include "ovs-thread.h"
32 #include "openvswitch/vlog.h"
34 /* --relops: Bitmap of the relational operators to test, in exhaustive test. */
35 static unsigned int test_relops;
37 /* --vars: Number of variables to test, in exhaustive test. */
38 static int test_vars = 2;
40 /* --bits: Number of bits per variable, in exhaustive test. */
41 static int test_bits = 3;
43 /* --operation: The operation to test, in exhaustive test. */
44 static enum { OP_CONVERT, OP_SIMPLIFY, OP_NORMALIZE, OP_FLOW } operation
47 /* --parallel: Number of parallel processes to use in test. */
48 static int test_parallel = 1;
50 /* -m, --more: Message verbosity */
54 compare_token(const struct lex_token *a, const struct lex_token *b)
56 if (a->type != b->type) {
57 fprintf(stderr, "type differs: %d -> %d\n", a->type, b->type);
61 if (!((a->s && b->s && !strcmp(a->s, b->s))
62 || (!a->s && !b->s))) {
63 fprintf(stderr, "string differs: %s -> %s\n",
64 a->s ? a->s : "(null)",
65 b->s ? b->s : "(null)");
69 if (a->type == LEX_T_INTEGER || a->type == LEX_T_MASKED_INTEGER) {
70 if (memcmp(&a->value, &b->value, sizeof a->value)) {
71 fprintf(stderr, "value differs\n");
75 if (a->type == LEX_T_MASKED_INTEGER
76 && memcmp(&a->mask, &b->mask, sizeof a->mask)) {
77 fprintf(stderr, "mask differs\n");
81 if (a->format != b->format
82 && !(a->format == LEX_F_HEXADECIMAL
83 && b->format == LEX_F_DECIMAL
84 && a->value.integer == 0)) {
85 fprintf(stderr, "format differs: %d -> %d\n",
86 a->format, b->format);
92 test_lex(struct ovs_cmdl_context *ctx OVS_UNUSED)
99 while (!ds_get_line(&input, stdin)) {
102 lexer_init(&lexer, ds_cstr(&input));
104 while (lexer_get(&lexer) != LEX_T_END) {
105 size_t len = output.length;
106 lex_token_format(&lexer.token, &output);
108 /* Check that the formatted version can really be parsed back
110 if (lexer.token.type != LEX_T_ERROR) {
111 const char *s = ds_cstr(&output) + len;
116 compare_token(&lexer.token, &l2.token);
119 ds_put_char(&output, ' ');
121 lexer_destroy(&lexer);
123 ds_chomp(&output, ' ');
124 puts(ds_cstr(&output));
131 create_symtab(struct shash *symtab)
135 expr_symtab_add_string(symtab, "inport", MFF_IN_PORT, NULL);
136 expr_symtab_add_string(symtab, "outport", MFF_ACTSET_OUTPUT, NULL);
138 expr_symtab_add_field(symtab, "xreg0", MFF_XREG0, NULL, false);
139 expr_symtab_add_field(symtab, "xreg1", MFF_XREG1, NULL, false);
140 expr_symtab_add_field(symtab, "xreg2", MFF_XREG2, NULL, false);
141 expr_symtab_add_field(symtab, "xreg3", MFF_XREG3, NULL, false);
143 expr_symtab_add_subfield(symtab, "reg0", NULL, "xreg0[32..63]");
144 expr_symtab_add_subfield(symtab, "reg1", NULL, "xreg0[0..31]");
145 expr_symtab_add_subfield(symtab, "reg2", NULL, "xreg1[32..63]");
146 expr_symtab_add_subfield(symtab, "reg3", NULL, "xreg1[0..31]");
147 expr_symtab_add_subfield(symtab, "reg4", NULL, "xreg2[32..63]");
148 expr_symtab_add_subfield(symtab, "reg5", NULL, "xreg2[0..31]");
149 expr_symtab_add_subfield(symtab, "reg6", NULL, "xreg3[32..63]");
150 expr_symtab_add_subfield(symtab, "reg7", NULL, "xreg3[0..31]");
152 expr_symtab_add_field(symtab, "eth.src", MFF_ETH_SRC, NULL, false);
153 expr_symtab_add_field(symtab, "eth.dst", MFF_ETH_DST, NULL, false);
154 expr_symtab_add_field(symtab, "eth.type", MFF_ETH_TYPE, NULL, true);
156 expr_symtab_add_field(symtab, "vlan.tci", MFF_VLAN_TCI, NULL, false);
157 expr_symtab_add_predicate(symtab, "vlan.present", "vlan.tci[12]");
158 expr_symtab_add_subfield(symtab, "vlan.pcp", "vlan.present",
160 expr_symtab_add_subfield(symtab, "vlan.vid", "vlan.present",
163 expr_symtab_add_predicate(symtab, "ip4", "eth.type == 0x800");
164 expr_symtab_add_predicate(symtab, "ip6", "eth.type == 0x86dd");
165 expr_symtab_add_predicate(symtab, "ip", "ip4 || ip6");
166 expr_symtab_add_field(symtab, "ip.proto", MFF_IP_PROTO, "ip", true);
167 expr_symtab_add_field(symtab, "ip.dscp", MFF_IP_DSCP, "ip", false);
168 expr_symtab_add_field(symtab, "ip.ecn", MFF_IP_ECN, "ip", false);
169 expr_symtab_add_field(symtab, "ip.ttl", MFF_IP_TTL, "ip", false);
171 expr_symtab_add_field(symtab, "ip4.src", MFF_IPV4_SRC, "ip4", false);
172 expr_symtab_add_field(symtab, "ip4.dst", MFF_IPV4_DST, "ip4", false);
174 expr_symtab_add_predicate(symtab, "icmp4", "ip4 && ip.proto == 1");
175 expr_symtab_add_field(symtab, "icmp4.type", MFF_ICMPV4_TYPE, "icmp4",
177 expr_symtab_add_field(symtab, "icmp4.code", MFF_ICMPV4_CODE, "icmp4",
180 expr_symtab_add_field(symtab, "ip6.src", MFF_IPV6_SRC, "ip6", false);
181 expr_symtab_add_field(symtab, "ip6.dst", MFF_IPV6_DST, "ip6", false);
182 expr_symtab_add_field(symtab, "ip6.label", MFF_IPV6_LABEL, "ip6", false);
184 expr_symtab_add_predicate(symtab, "icmp6", "ip6 && ip.proto == 58");
185 expr_symtab_add_field(symtab, "icmp6.type", MFF_ICMPV6_TYPE, "icmp6",
187 expr_symtab_add_field(symtab, "icmp6.code", MFF_ICMPV6_CODE, "icmp6",
190 expr_symtab_add_predicate(symtab, "icmp", "icmp4 || icmp6");
192 expr_symtab_add_field(symtab, "ip.frag", MFF_IP_FRAG, "ip", false);
193 expr_symtab_add_predicate(symtab, "ip.is_frag", "ip.frag[0]");
194 expr_symtab_add_predicate(symtab, "ip.later_frag", "ip.frag[1]");
195 expr_symtab_add_predicate(symtab, "ip.first_frag", "ip.is_frag && !ip.later_frag");
197 expr_symtab_add_predicate(symtab, "arp", "eth.type == 0x806");
198 expr_symtab_add_field(symtab, "arp.op", MFF_ARP_OP, "arp", false);
199 expr_symtab_add_field(symtab, "arp.spa", MFF_ARP_SPA, "arp", false);
200 expr_symtab_add_field(symtab, "arp.sha", MFF_ARP_SHA, "arp", false);
201 expr_symtab_add_field(symtab, "arp.tpa", MFF_ARP_TPA, "arp", false);
202 expr_symtab_add_field(symtab, "arp.tha", MFF_ARP_THA, "arp", false);
204 expr_symtab_add_predicate(symtab, "nd", "icmp6.type == {135, 136} && icmp6.code == 0");
205 expr_symtab_add_field(symtab, "nd.target", MFF_ND_TARGET, "nd", false);
206 expr_symtab_add_field(symtab, "nd.sll", MFF_ND_SLL,
207 "nd && icmp6.type == 135", false);
208 expr_symtab_add_field(symtab, "nd.tll", MFF_ND_TLL,
209 "nd && icmp6.type == 136", false);
211 expr_symtab_add_predicate(symtab, "tcp", "ip.proto == 6");
212 expr_symtab_add_field(symtab, "tcp.src", MFF_TCP_SRC, "tcp", false);
213 expr_symtab_add_field(symtab, "tcp.dst", MFF_TCP_DST, "tcp", false);
214 expr_symtab_add_field(symtab, "tcp.flags", MFF_TCP_FLAGS, "tcp", false);
216 expr_symtab_add_predicate(symtab, "udp", "ip.proto == 17");
217 expr_symtab_add_field(symtab, "udp.src", MFF_UDP_SRC, "udp", false);
218 expr_symtab_add_field(symtab, "udp.dst", MFF_UDP_DST, "udp", false);
220 expr_symtab_add_predicate(symtab, "sctp", "ip.proto == 132");
221 expr_symtab_add_field(symtab, "sctp.src", MFF_SCTP_SRC, "sctp", false);
222 expr_symtab_add_field(symtab, "sctp.dst", MFF_SCTP_DST, "sctp", false);
224 /* For negative testing. */
225 expr_symtab_add_field(symtab, "bad_prereq", MFF_XREG0, "xyzzy", false);
226 expr_symtab_add_field(symtab, "self_recurse", MFF_XREG0,
227 "self_recurse != 0", false);
228 expr_symtab_add_field(symtab, "mutual_recurse_1", MFF_XREG0,
229 "mutual_recurse_2 != 0", false);
230 expr_symtab_add_field(symtab, "mutual_recurse_2", MFF_XREG0,
231 "mutual_recurse_1 != 0", false);
235 test_parse_expr__(int steps)
241 create_symtab(&symtab);
244 simap_put(&ports, "eth0", 5);
245 simap_put(&ports, "eth1", 6);
246 simap_put(&ports, "LOCAL", ofp_to_u16(OFPP_LOCAL));
249 while (!ds_get_test_line(&input, stdin)) {
253 expr = expr_parse_string(ds_cstr(&input), &symtab, &error);
254 if (!error && steps > 0) {
255 expr = expr_annotate(expr, &symtab, &error);
259 expr = expr_simplify(expr);
262 expr = expr_normalize(expr);
263 ovs_assert(expr_is_normalized(expr));
270 expr_to_matches(expr, &ports, &matches);
271 expr_matches_print(&matches, stdout);
272 expr_matches_destroy(&matches);
274 struct ds output = DS_EMPTY_INITIALIZER;
275 expr_format(expr, &output);
276 puts(ds_cstr(&output));
287 simap_destroy(&ports);
288 expr_symtab_destroy(&symtab);
289 shash_destroy(&symtab);
293 test_parse_expr(struct ovs_cmdl_context *ctx OVS_UNUSED)
295 test_parse_expr__(0);
299 test_annotate_expr(struct ovs_cmdl_context *ctx OVS_UNUSED)
301 test_parse_expr__(1);
305 test_simplify_expr(struct ovs_cmdl_context *ctx OVS_UNUSED)
307 test_parse_expr__(2);
311 test_normalize_expr(struct ovs_cmdl_context *ctx OVS_UNUSED)
313 test_parse_expr__(3);
317 test_expr_to_flows(struct ovs_cmdl_context *ctx OVS_UNUSED)
319 test_parse_expr__(4);
322 /* Evaluate an expression. */
324 static bool evaluate_expr(const struct expr *, unsigned int subst, int n_bits);
327 evaluate_andor_expr(const struct expr *expr, unsigned int subst, int n_bits,
330 const struct expr *sub;
332 LIST_FOR_EACH (sub, node, &expr->andor) {
333 if (evaluate_expr(sub, subst, n_bits) == short_circuit) {
334 return short_circuit;
337 return !short_circuit;
341 evaluate_cmp_expr(const struct expr *expr, unsigned int subst, int n_bits)
343 int var_idx = expr->cmp.symbol->name[0] - 'a';
344 unsigned var_mask = (1u << n_bits) - 1;
345 unsigned int arg1 = (subst >> (var_idx * n_bits)) & var_mask;
346 unsigned int arg2 = ntohll(expr->cmp.value.integer);
347 unsigned int mask = ntohll(expr->cmp.mask.integer);
349 ovs_assert(!(mask & ~var_mask));
350 ovs_assert(!(arg2 & ~var_mask));
351 ovs_assert(!(arg2 & ~mask));
354 switch (expr->cmp.relop) {
378 /* Evaluates 'expr' and returns its Boolean result. 'subst' provides the value
379 * for the variables, which must be 'n_bits' bits each and be named "a", "b",
380 * "c", etc. The value of variable "a" is the least-significant 'n_bits' bits
381 * of 'subst', the value of "b" is the next 'n_bits' bits, and so on. */
383 evaluate_expr(const struct expr *expr, unsigned int subst, int n_bits)
385 switch (expr->type) {
387 return evaluate_cmp_expr(expr, subst, n_bits);
390 return evaluate_andor_expr(expr, subst, n_bits, false);
393 return evaluate_andor_expr(expr, subst, n_bits, true);
396 return expr->boolean;
404 test_evaluate_expr(struct ovs_cmdl_context *ctx)
406 int a = atoi(ctx->argv[1]);
407 int b = atoi(ctx->argv[2]);
408 int c = atoi(ctx->argv[3]);
409 unsigned int subst = a | (b << 3) || (c << 6);
414 expr_symtab_add_field(&symtab, "xreg0", MFF_XREG0, NULL, false);
415 expr_symtab_add_field(&symtab, "xreg1", MFF_XREG1, NULL, false);
416 expr_symtab_add_field(&symtab, "xreg2", MFF_XREG1, NULL, false);
417 expr_symtab_add_subfield(&symtab, "a", NULL, "xreg0[0..2]");
418 expr_symtab_add_subfield(&symtab, "b", NULL, "xreg1[0..2]");
419 expr_symtab_add_subfield(&symtab, "c", NULL, "xreg2[0..2]");
422 while (!ds_get_test_line(&input, stdin)) {
426 expr = expr_parse_string(ds_cstr(&input), &symtab, &error);
428 expr = expr_annotate(expr, &symtab, &error);
431 printf("%d\n", evaluate_expr(expr, subst, 3));
440 expr_symtab_destroy(&symtab);
441 shash_destroy(&symtab);
446 * The "compositions" of a positive integer N are all of the ways that one can
447 * add up positive integers to sum to N. For example, the compositions of 3
448 * are 3, 2+1, 1+2, and 1+1+1.
450 * We use compositions to find all the ways to break up N terms of a Boolean
451 * expression into subexpressions. Suppose we want to generate all expressions
452 * with 3 terms. The compositions of 3 (ignoring 3 itself) provide the
453 * possibilities (x && x) || x, x || (x && x), and x || x || x. (Of course one
454 * can exchange && for || in each case.) One must recursively compose the
455 * sub-expressions whose values are 3 or greater; that is what the "tree shape"
456 * concept later covers.
458 * To iterate through all compositions of, e.g., 5:
460 * unsigned int state;
464 * for (n = first_composition(ARRAY_SIZE(s), &state, s); n > 0;
465 * n = next_composition(&state, s, n)) {
466 * // Do something with composition 's' with 'n' elements.
469 * Algorithm from D. E. Knuth, _The Art of Computer Programming, Vol. 4A:
470 * Combinatorial Algorithms, Part 1_, section 7.2.1.1, answer to exercise
474 /* Begins iteration through the compositions of 'n'. Initializes 's' to the
475 * number of elements in the first composition of 'n' and returns that number
476 * of elements. The first composition in fact is always 'n' itself, so the
477 * return value will be 1.
479 * Initializes '*state' to some internal state information. The caller must
480 * maintain this state (and 's') for use by next_composition().
482 * 's' must have room for at least 'n' elements. */
484 first_composition(int n, unsigned int *state, int s[])
491 /* Advances 's', with 'sn' elements, to the next composition and returns the
492 * number of elements in this new composition, or 0 if no compositions are
493 * left. 'state' is the same internal state passed to first_composition(). */
495 next_composition(unsigned int *state, int s[], int sn)
526 test_composition(struct ovs_cmdl_context *ctx)
528 int n = atoi(ctx->argv[1]);
532 for (int sn = first_composition(n, &state, s); sn;
533 sn = next_composition(&state, s, sn)) {
534 for (int i = 0; i < sn; i++) {
535 printf("%d%c", s[i], i == sn - 1 ? '\n' : ' ');
542 * This code generates all possible Boolean expressions with a specified number
543 * of terms N (equivalent to the number of external nodes in a tree).
545 * See test_tree_shape() for a simple example. */
547 /* An array of these structures describes the shape of a tree.
549 * A single element of struct tree_shape describes a single node in the tree.
550 * The node has 'sn' direct children. From left to right, for i in 0...sn-1,
551 * s[i] is 1 if the child is a leaf node, otherwise the child is a subtree and
552 * s[i] is the number of leaf nodes within that subtree. In the latter case,
553 * the subtree is described by another struct tree_shape within the enclosing
554 * array. The tree_shapes are ordered in the array in in-order.
563 init_tree_shape__(struct tree_shape ts[], int n)
570 /* Skip the first composition intentionally. */
571 ts->sn = first_composition(n, &ts->state, ts->s);
572 ts->sn = next_composition(&ts->state, ts->s, ts->sn);
573 for (int i = 0; i < ts->sn; i++) {
574 n_tses += init_tree_shape__(&ts[n_tses], ts->s[i]);
579 /* Initializes 'ts[]' as the first in the set of all of possible shapes of
580 * trees with 'n' leaves. Returns the number of "struct tree_shape"s in the
581 * first tree shape. */
583 init_tree_shape(struct tree_shape ts[], int n)
596 return init_tree_shape__(ts, n);
600 /* Advances 'ts', which currently has 'n_tses' elements, to the next possible
601 * tree shape with the number of leaves passed to init_tree_shape(). Returns
602 * the number of "struct tree_shape"s in the next shape, or 0 if all tree
603 * shapes have been visited. */
605 next_tree_shape(struct tree_shape ts[], int n_tses)
607 if (n_tses == 1 && ts->sn == 2 && ts->s[0] == 1 && ts->s[1] == 1) {
611 struct tree_shape *p = &ts[n_tses - 1];
612 p->sn = p->sn > 1 ? next_composition(&p->state, p->s, p->sn) : 0;
614 for (int i = 0; i < p->sn; i++) {
615 n_tses += init_tree_shape__(&ts[n_tses], p->s[i]);
625 print_tree_shape(const struct tree_shape ts[], int n_tses)
627 for (int i = 0; i < n_tses; i++) {
631 for (int j = 0; j < ts[i].sn; j++) {
643 test_tree_shape(struct ovs_cmdl_context *ctx)
645 int n = atoi(ctx->argv[1]);
646 struct tree_shape ts[50];
649 for (n_tses = init_tree_shape(ts, n); n_tses;
650 n_tses = next_tree_shape(ts, n_tses)) {
651 print_tree_shape(ts, n_tses);
656 /* Iteration through all possible terminal expressions (e.g. EXPR_T_CMP and
657 * EXPR_T_BOOLEAN expressions).
659 * Given a tree shape, this allows the code to try all possible ways to plug in
664 * struct expr terminal;
665 * const struct expr_symbol *vars = ...;
669 * init_terminal(&terminal, vars[0]);
671 * // Something with 'terminal'.
672 * } while (next_terminal(&terminal, vars, n_vars, n_bits));
675 /* Sets 'expr' to the first possible terminal expression. 'var' should be the
676 * first variable in the ones to be tested. */
678 init_terminal(struct expr *expr, const struct expr_symbol *var)
680 expr->type = EXPR_T_CMP;
681 expr->cmp.symbol = var;
682 expr->cmp.relop = rightmost_1bit_idx(test_relops);
683 memset(&expr->cmp.value, 0, sizeof expr->cmp.value);
684 memset(&expr->cmp.mask, 0, sizeof expr->cmp.mask);
685 expr->cmp.value.integer = htonll(0);
686 expr->cmp.mask.integer = htonll(1);
689 /* Returns 'x' with the rightmost contiguous string of 1s changed to 0s,
690 * e.g. 01011100 => 01000000. See H. S. Warren, Jr., _Hacker's Delight_, 2nd
691 * ed., section 2-1. */
693 turn_off_rightmost_1s(unsigned int x)
695 return ((x & -x) + x) & x;
698 static const struct expr_symbol *
699 next_var(const struct expr_symbol *symbol,
700 const struct expr_symbol *vars[], int n_vars)
702 for (int i = 0; i < n_vars; i++) {
703 if (symbol == vars[i]) {
704 return i + 1 >= n_vars ? NULL : vars[i + 1];
710 static enum expr_relop
711 next_relop(enum expr_relop relop)
713 unsigned int remaining_relops = test_relops & ~((1u << (relop + 1)) - 1);
714 return (remaining_relops
715 ? rightmost_1bit_idx(remaining_relops)
716 : rightmost_1bit_idx(test_relops));
719 /* Advances 'expr' to the next possible terminal expression within the 'n_vars'
720 * variables of 'n_bits' bits each in 'vars[]'. */
722 next_terminal(struct expr *expr, const struct expr_symbol *vars[], int n_vars,
725 if (expr->type == EXPR_T_BOOLEAN) {
729 expr->boolean = true;
736 next = (ntohll(expr->cmp.value.integer)
737 + (ntohll(expr->cmp.mask.integer) << n_bits));
740 unsigned m = next >> n_bits;
741 unsigned v = next & ((1u << n_bits) - 1);
742 if (next >= (1u << (2 * n_bits))) {
743 enum expr_relop old_relop = expr->cmp.relop;
744 expr->cmp.relop = next_relop(old_relop);
745 if (expr->cmp.relop <= old_relop) {
746 expr->cmp.symbol = next_var(expr->cmp.symbol,vars, n_vars);
747 if (!expr->cmp.symbol) {
748 expr->type = EXPR_T_BOOLEAN;
749 expr->boolean = false;
755 /* Skip: empty mask is pathological. */
757 /* Skip: 1-bits in value correspond to 0-bits in mask. */
758 } else if (turn_off_rightmost_1s(m)
759 && (expr->cmp.relop != EXPR_R_EQ &&
760 expr->cmp.relop != EXPR_R_NE)) {
761 /* Skip: can't have discontiguous mask for > >= < <=. */
763 expr->cmp.value.integer = htonll(v);
764 expr->cmp.mask.integer = htonll(m);
771 make_terminal(struct expr ***terminalp)
773 struct expr *e = expr_create_boolean(true);
780 build_simple_tree(enum expr_type type, int n, struct expr ***terminalp)
783 struct expr *e = expr_create_andor(type);
784 for (int i = 0; i < 2; i++) {
785 struct expr *sub = make_terminal(terminalp);
786 list_push_back(&e->andor, &sub->node);
790 return make_terminal(terminalp);
797 build_tree_shape(enum expr_type type, const struct tree_shape **tsp,
798 struct expr ***terminalp)
800 const struct tree_shape *ts = *tsp;
803 struct expr *e = expr_create_andor(type);
804 enum expr_type t = type == EXPR_T_AND ? EXPR_T_OR : EXPR_T_AND;
805 for (int i = 0; i < ts->sn; i++) {
806 struct expr *sub = (ts->s[i] > 2
807 ? build_tree_shape(t, tsp, terminalp)
808 : build_simple_tree(t, ts->s[i], terminalp));
809 list_push_back(&e->andor, &sub->node);
819 free_rule(struct test_rule *test_rule)
821 cls_rule_destroy(&test_rule->cr);
826 test_tree_shape_exhaustively(struct expr *expr, struct shash *symtab,
827 struct expr *terminals[], int n_terminals,
828 const struct expr_symbol *vars[], int n_vars,
833 const unsigned int var_mask = (1u << n_bits) - 1;
834 for (int i = 0; i < n_terminals; i++) {
835 init_terminal(terminals[i], vars[0]);
838 struct ds s = DS_EMPTY_INITIALIZER;
840 memset(&f, 0, sizeof f);
842 for (int i = n_terminals - 1; ; i--) {
847 if (next_terminal(terminals[i], vars, n_vars, n_bits)) {
850 init_terminal(terminals[i], vars[0]);
852 ovs_assert(expr_honors_invariants(expr));
856 struct expr *modified;
857 if (operation == OP_CONVERT) {
859 expr_format(expr, &s);
862 modified = expr_parse_string(ds_cstr(&s), symtab, &error);
864 fprintf(stderr, "%s fails to parse (%s)\n",
868 } else if (operation >= OP_SIMPLIFY) {
869 modified = expr_simplify(expr_clone(expr));
870 ovs_assert(expr_honors_invariants(modified));
872 if (operation >= OP_NORMALIZE) {
873 modified = expr_normalize(modified);
874 ovs_assert(expr_is_normalized(modified));
879 struct classifier cls;
880 if (operation >= OP_FLOW) {
881 struct expr_match *m;
882 struct test_rule *test_rule;
885 n_conjs = expr_to_matches(modified, NULL, &matches);
887 classifier_init(&cls, NULL);
888 HMAP_FOR_EACH (m, hmap_node, &matches) {
889 test_rule = xmalloc(sizeof *test_rule);
890 cls_rule_init(&test_rule->cr, &m->match, 0);
891 classifier_insert(&cls, &test_rule->cr, m->conjunctions, m->n);
893 for (uint32_t conj_id = 1; conj_id <= n_conjs; conj_id++) {
895 match_init_catchall(&match);
896 match_set_conj_id(&match, conj_id);
898 test_rule = xmalloc(sizeof *test_rule);
899 cls_rule_init(&test_rule->cr, &match, 0);
900 classifier_insert(&cls, &test_rule->cr, NULL, 0);
903 for (int subst = 0; subst < 1 << (n_bits * n_vars); subst++) {
904 bool expected = evaluate_expr(expr, subst, n_bits);
905 bool actual = evaluate_expr(modified, subst, n_bits);
906 if (actual != expected) {
907 struct ds expr_s, modified_s;
910 expr_format(expr, &expr_s);
912 ds_init(&modified_s);
913 expr_format(modified, &modified_s);
916 "%s evaluates to %d, but %s evaluates to %d, for",
917 ds_cstr(&expr_s), expected,
918 ds_cstr(&modified_s), actual);
919 for (int i = 0; i < n_vars; i++) {
923 fprintf(stderr, " %c = 0x%x", 'a' + i,
924 (subst >> (n_bits * i)) & var_mask);
930 if (operation >= OP_FLOW) {
931 for (int i = 0; i < n_vars; i++) {
932 f.regs[i] = (subst >> (i * n_bits)) & var_mask;
934 bool found = classifier_lookup(&cls, &f, NULL) != NULL;
935 if (expected != found) {
936 struct ds expr_s, modified_s;
939 expr_format(expr, &expr_s);
941 ds_init(&modified_s);
942 expr_format(modified, &modified_s);
945 "%s and %s evaluate to %d, for",
946 ds_cstr(&expr_s), ds_cstr(&modified_s), expected);
947 for (int i = 0; i < n_vars; i++) {
951 fprintf(stderr, " %c = 0x%x", 'a' + i,
952 (subst >> (n_bits * i)) & var_mask);
954 fputs(".\n", stderr);
956 fprintf(stderr, "Converted to classifier:\n");
957 expr_matches_print(&matches, stderr);
959 "However, %s flow was found in the classifier.\n",
965 if (operation >= OP_FLOW) {
966 struct test_rule *test_rule;
968 CLS_FOR_EACH (test_rule, cr, &cls) {
969 classifier_remove(&cls, &test_rule->cr);
970 ovsrcu_postpone(free_rule, test_rule);
972 classifier_destroy(&cls);
975 expr_matches_destroy(&matches);
977 expr_destroy(modified);
983 wait_pid(pid_t *pids, int *n)
988 pid = waitpid(WAIT_ANY, &status, 0);
990 ovs_fatal(errno, "waitpid failed");
991 } else if (WIFEXITED(status)) {
992 if (WEXITSTATUS(status)) {
993 exit(WEXITSTATUS(status));
995 } else if (WIFSIGNALED(status)) {
996 raise(WTERMSIG(status));
1002 for (int i = 0; i < *n; i++) {
1003 if (pids[i] == pid) {
1004 pids[i] = pids[--*n];
1008 ovs_fatal(0, "waitpid returned unknown child");
1013 test_exhaustive(struct ovs_cmdl_context *ctx OVS_UNUSED)
1015 int n_terminals = atoi(ctx->argv[1]);
1016 struct tree_shape ts[50];
1019 struct shash symtab;
1020 const struct expr_symbol *vars[4];
1022 ovs_assert(test_vars <= ARRAY_SIZE(vars));
1024 shash_init(&symtab);
1025 for (int i = 0; i < test_vars; i++) {
1026 char name[2] = { 'a' + i, '\0' };
1028 vars[i] = expr_symtab_add_field(&symtab, name, MFF_REG0 + i, NULL,
1033 pid_t *children = xmalloc(test_parallel * sizeof *children);
1038 for (int i = 0; i < 2; i++) {
1039 enum expr_type base_type = i ? EXPR_T_OR : EXPR_T_AND;
1041 for (n_tses = init_tree_shape(ts, n_terminals); n_tses;
1042 n_tses = next_tree_shape(ts, n_tses)) {
1043 const struct tree_shape *tsp = ts;
1044 struct expr *terminals[50];
1045 struct expr **terminalp = terminals;
1046 struct expr *expr = build_tree_shape(base_type, &tsp, &terminalp);
1047 ovs_assert(terminalp == &terminals[n_terminals]);
1049 if (verbosity > 0) {
1050 print_tree_shape(ts, n_tses);
1052 struct ds s = DS_EMPTY_INITIALIZER;
1053 expr_format(expr, &s);
1059 if (test_parallel > 1) {
1060 pid_t pid = xfork();
1062 test_tree_shape_exhaustively(expr, &symtab,
1063 terminals, n_terminals,
1064 vars, test_vars, test_bits);
1068 if (n_children >= test_parallel) {
1069 wait_pid(children, &n_children);
1071 children[n_children++] = pid;
1076 n_tested += test_tree_shape_exhaustively(
1077 expr, &symtab, terminals, n_terminals,
1078 vars, test_vars, test_bits);
1084 while (n_children > 0) {
1085 wait_pid(children, &n_children);
1091 switch (operation) {
1093 printf("converting");
1096 printf("simplifying");
1099 printf("normalizing");
1102 printf("converting to flows");
1106 printf(" %d expressions of %d terminals", n_tested, n_terminals);
1108 printf(" all %d-terminal expressions", n_terminals);
1110 printf(" with %d vars each of %d bits in terms of operators",
1111 test_vars, test_bits);
1112 for (unsigned int relops = test_relops; relops;
1113 relops = zero_rightmost_1bit(relops)) {
1114 enum expr_relop r = rightmost_1bit_idx(relops);
1115 printf(" %s", expr_relop_to_string(r));
1119 expr_symtab_destroy(&symtab);
1120 shash_destroy(&symtab);
1124 parse_relops(const char *s)
1126 unsigned int relops = 0;
1129 lexer_init(&lexer, s);
1132 enum expr_relop relop;
1134 if (expr_relop_from_token(lexer.token.type, &relop)) {
1135 relops |= 1u << relop;
1138 ovs_fatal(0, "%s: relational operator expected at `%.*s'",
1139 s, (int) (lexer.input - lexer.start), lexer.start);
1141 lexer_match(&lexer, LEX_T_COMMA);
1142 } while (lexer.token.type != LEX_T_END);
1143 lexer_destroy(&lexer);
1152 %s: OVN test utility\n\
1153 usage: test-ovn %s [OPTIONS] COMMAND [ARG...]\n\
1156 Lexically analyzes OVN input from stdin and print them back on stdout.\n\
1163 Parses OVN expressions from stdin and print them back on stdout after\n\
1164 differing degrees of analysis. Available fields are based on packet\n\
1167 evaluate-expr A B C\n\
1168 Parses OVN expressions from stdin, evaluate them with assigned values,\n\
1169 and print the results on stdout. Available fields are 'a', 'b', and 'c'\n\
1170 of 3 bits each. A, B, and C should be in the range 0 to 7.\n\
1173 Prints all the compositions of N on stdout.\n\
1176 Prints all the tree shapes with N terminals on stdout.\n\
1179 Tests that all possible Boolean expressions with N terminals are properly\n\
1180 simplified, normalized, and converted to flows. Available options:\n\
1181 --relops=OPERATORS Test only the specified Boolean operators.\n\
1182 OPERATORS may include == != < <= > >=, space or\n\
1183 comma separated. Default is all operators.\n\
1184 --vars=N Number of variables to test, in range 1...4, default 2.\n\
1185 --bits=N Number of bits per variable, in range 1...3, default 3.\n\
1186 --operation=OPERATION Operation to test, one of: convert, simplify,\n\
1187 normalize, flow. Default: flow. 'normalize' includes 'simplify',\n\
1188 'flow' includes 'simplify' and 'normaize'.\n\
1189 --parallel=N Number of processes to use in parallel, default 1.\n\
1191 program_name, program_name);
1196 test_ovn_main(int argc, char *argv[])
1198 set_program_name(argv[0]);
1200 test_relops = parse_relops("== != < <= > >=");
1203 OPT_RELOPS = UCHAR_MAX + 1,
1210 static const struct option options[] = {
1211 {"relops", required_argument, NULL, OPT_RELOPS},
1212 {"vars", required_argument, NULL, OPT_VARS},
1213 {"bits", required_argument, NULL, OPT_BITS},
1214 {"operation", required_argument, NULL, OPT_OPERATION},
1215 {"parallel", required_argument, NULL, OPT_PARALLEL},
1216 {"more", no_argument, NULL, 'm'},
1217 {"help", no_argument, NULL, 'h'},
1220 int option_index = 0;
1221 int c = getopt_long (argc, argv, "", options, &option_index);
1228 test_relops = parse_relops(optarg);
1232 test_vars = atoi(optarg);
1233 if (test_vars < 1 || test_vars > 4) {
1234 ovs_fatal(0, "number of variables must be between 1 and 4");
1239 test_bits = atoi(optarg);
1240 if (test_bits < 1 || test_bits > 3) {
1241 ovs_fatal(0, "number of bits must be between 1 and 3");
1246 if (!strcmp(optarg, "convert")) {
1247 operation = OP_CONVERT;
1248 } else if (!strcmp(optarg, "simplify")) {
1249 operation = OP_SIMPLIFY;
1250 } else if (!strcmp(optarg, "normalize")) {
1251 operation = OP_NORMALIZE;
1252 } else if (!strcmp(optarg, "flow")) {
1253 operation = OP_FLOW;
1255 ovs_fatal(0, "%s: unknown operation", optarg);
1260 test_parallel = atoi(optarg);
1278 static const struct ovs_cmdl_command commands[] = {
1279 {"lex", NULL, 0, 0, test_lex},
1280 {"parse-expr", NULL, 0, 0, test_parse_expr},
1281 {"annotate-expr", NULL, 0, 0, test_annotate_expr},
1282 {"simplify-expr", NULL, 0, 0, test_simplify_expr},
1283 {"normalize-expr", NULL, 0, 0, test_normalize_expr},
1284 {"expr-to-flows", NULL, 0, 0, test_expr_to_flows},
1285 {"evaluate-expr", NULL, 1, 1, test_evaluate_expr},
1286 {"composition", NULL, 1, 1, test_composition},
1287 {"tree-shape", NULL, 1, 1, test_tree_shape},
1288 {"exhaustive", NULL, 1, 1, test_exhaustive},
1289 {NULL, NULL, 0, 0, NULL},
1291 struct ovs_cmdl_context ctx;
1292 ctx.argc = argc - optind;
1293 ctx.argv = argv + optind;
1294 ovs_cmdl_run_command(&ctx, commands);
1297 OVSTEST_REGISTER("test-ovn", test_ovn_main);