2 * Copyright (c) 2015, 2016 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 "openvswitch/dynamic-string.h"
23 #include "fatal-signal.h"
24 #include "openvswitch/match.h"
25 #include "ofp-actions.h"
26 #include "openvswitch/ofpbuf.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 lookup_port_cb(const void *ports_, const char *port_name, unsigned int *portp)
244 const struct simap *ports = ports_;
245 const struct simap_node *node = simap_find(ports, port_name);
254 test_parse_expr__(int steps)
260 create_symtab(&symtab);
263 simap_put(&ports, "eth0", 5);
264 simap_put(&ports, "eth1", 6);
265 simap_put(&ports, "LOCAL", ofp_to_u16(OFPP_LOCAL));
268 while (!ds_get_test_line(&input, stdin)) {
272 expr = expr_parse_string(ds_cstr(&input), &symtab, &error);
273 if (!error && steps > 0) {
274 expr = expr_annotate(expr, &symtab, &error);
278 expr = expr_simplify(expr);
281 expr = expr_normalize(expr);
282 ovs_assert(expr_is_normalized(expr));
289 expr_to_matches(expr, lookup_port_cb, &ports, &matches);
290 expr_matches_print(&matches, stdout);
291 expr_matches_destroy(&matches);
293 struct ds output = DS_EMPTY_INITIALIZER;
294 expr_format(expr, &output);
295 puts(ds_cstr(&output));
306 simap_destroy(&ports);
307 expr_symtab_destroy(&symtab);
308 shash_destroy(&symtab);
312 test_parse_expr(struct ovs_cmdl_context *ctx OVS_UNUSED)
314 test_parse_expr__(0);
318 test_annotate_expr(struct ovs_cmdl_context *ctx OVS_UNUSED)
320 test_parse_expr__(1);
324 test_simplify_expr(struct ovs_cmdl_context *ctx OVS_UNUSED)
326 test_parse_expr__(2);
330 test_normalize_expr(struct ovs_cmdl_context *ctx OVS_UNUSED)
332 test_parse_expr__(3);
336 test_expr_to_flows(struct ovs_cmdl_context *ctx OVS_UNUSED)
338 test_parse_expr__(4);
341 /* Evaluate an expression. */
343 static bool evaluate_expr(const struct expr *, unsigned int subst, int n_bits);
346 evaluate_andor_expr(const struct expr *expr, unsigned int subst, int n_bits,
349 const struct expr *sub;
351 LIST_FOR_EACH (sub, node, &expr->andor) {
352 if (evaluate_expr(sub, subst, n_bits) == short_circuit) {
353 return short_circuit;
356 return !short_circuit;
360 evaluate_cmp_expr(const struct expr *expr, unsigned int subst, int n_bits)
362 int var_idx = atoi(expr->cmp.symbol->name + 1);
363 if (expr->cmp.symbol->name[0] == 'n') {
364 unsigned var_mask = (1u << n_bits) - 1;
365 unsigned int arg1 = (subst >> (var_idx * n_bits)) & var_mask;
366 unsigned int arg2 = ntohll(expr->cmp.value.integer);
367 unsigned int mask = ntohll(expr->cmp.mask.integer);
369 ovs_assert(!(mask & ~var_mask));
370 ovs_assert(!(arg2 & ~var_mask));
371 ovs_assert(!(arg2 & ~mask));
374 switch (expr->cmp.relop) {
396 } else if (expr->cmp.symbol->name[0] == 's') {
397 unsigned int arg1 = (subst >> (test_nvars * n_bits + var_idx)) & 1;
398 unsigned int arg2 = atoi(expr->cmp.string);
405 /* Evaluates 'expr' and returns its Boolean result. 'subst' provides the value
406 * for the variables, which must be 'n_bits' bits each and be named "a", "b",
407 * "c", etc. The value of variable "a" is the least-significant 'n_bits' bits
408 * of 'subst', the value of "b" is the next 'n_bits' bits, and so on. */
410 evaluate_expr(const struct expr *expr, unsigned int subst, int n_bits)
412 switch (expr->type) {
414 return evaluate_cmp_expr(expr, subst, n_bits);
417 return evaluate_andor_expr(expr, subst, n_bits, false);
420 return evaluate_andor_expr(expr, subst, n_bits, true);
423 return expr->boolean;
431 test_evaluate_expr(struct ovs_cmdl_context *ctx)
433 int a = atoi(ctx->argv[1]);
434 int b = atoi(ctx->argv[2]);
435 int c = atoi(ctx->argv[3]);
436 unsigned int subst = a | (b << 3) || (c << 6);
441 expr_symtab_add_field(&symtab, "xreg0", MFF_XREG0, NULL, false);
442 expr_symtab_add_field(&symtab, "xreg1", MFF_XREG1, NULL, false);
443 expr_symtab_add_field(&symtab, "xreg2", MFF_XREG1, NULL, false);
444 expr_symtab_add_subfield(&symtab, "a", NULL, "xreg0[0..2]");
445 expr_symtab_add_subfield(&symtab, "b", NULL, "xreg1[0..2]");
446 expr_symtab_add_subfield(&symtab, "c", NULL, "xreg2[0..2]");
449 while (!ds_get_test_line(&input, stdin)) {
453 expr = expr_parse_string(ds_cstr(&input), &symtab, &error);
455 expr = expr_annotate(expr, &symtab, &error);
458 printf("%d\n", evaluate_expr(expr, subst, 3));
467 expr_symtab_destroy(&symtab);
468 shash_destroy(&symtab);
473 * The "compositions" of a positive integer N are all of the ways that one can
474 * add up positive integers to sum to N. For example, the compositions of 3
475 * are 3, 2+1, 1+2, and 1+1+1.
477 * We use compositions to find all the ways to break up N terms of a Boolean
478 * expression into subexpressions. Suppose we want to generate all expressions
479 * with 3 terms. The compositions of 3 (ignoring 3 itself) provide the
480 * possibilities (x && x) || x, x || (x && x), and x || x || x. (Of course one
481 * can exchange && for || in each case.) One must recursively compose the
482 * sub-expressions whose values are 3 or greater; that is what the "tree shape"
483 * concept later covers.
485 * To iterate through all compositions of, e.g., 5:
487 * unsigned int state;
491 * for (n = first_composition(ARRAY_SIZE(s), &state, s); n > 0;
492 * n = next_composition(&state, s, n)) {
493 * // Do something with composition 's' with 'n' elements.
496 * Algorithm from D. E. Knuth, _The Art of Computer Programming, Vol. 4A:
497 * Combinatorial Algorithms, Part 1_, section 7.2.1.1, answer to exercise
501 /* Begins iteration through the compositions of 'n'. Initializes 's' to the
502 * number of elements in the first composition of 'n' and returns that number
503 * of elements. The first composition in fact is always 'n' itself, so the
504 * return value will be 1.
506 * Initializes '*state' to some internal state information. The caller must
507 * maintain this state (and 's') for use by next_composition().
509 * 's' must have room for at least 'n' elements. */
511 first_composition(int n, unsigned int *state, int s[])
518 /* Advances 's', with 'sn' elements, to the next composition and returns the
519 * number of elements in this new composition, or 0 if no compositions are
520 * left. 'state' is the same internal state passed to first_composition(). */
522 next_composition(unsigned int *state, int s[], int sn)
553 test_composition(struct ovs_cmdl_context *ctx)
555 int n = atoi(ctx->argv[1]);
559 for (int sn = first_composition(n, &state, s); sn;
560 sn = next_composition(&state, s, sn)) {
561 for (int i = 0; i < sn; i++) {
562 printf("%d%c", s[i], i == sn - 1 ? '\n' : ' ');
569 * This code generates all possible Boolean expressions with a specified number
570 * of terms N (equivalent to the number of external nodes in a tree).
572 * See test_tree_shape() for a simple example. */
574 /* An array of these structures describes the shape of a tree.
576 * A single element of struct tree_shape describes a single node in the tree.
577 * The node has 'sn' direct children. From left to right, for i in 0...sn-1,
578 * s[i] is 1 if the child is a leaf node, otherwise the child is a subtree and
579 * s[i] is the number of leaf nodes within that subtree. In the latter case,
580 * the subtree is described by another struct tree_shape within the enclosing
581 * array. The tree_shapes are ordered in the array in in-order.
590 init_tree_shape__(struct tree_shape ts[], int n)
597 /* Skip the first composition intentionally. */
598 ts->sn = first_composition(n, &ts->state, ts->s);
599 ts->sn = next_composition(&ts->state, ts->s, ts->sn);
600 for (int i = 0; i < ts->sn; i++) {
601 n_tses += init_tree_shape__(&ts[n_tses], ts->s[i]);
606 /* Initializes 'ts[]' as the first in the set of all of possible shapes of
607 * trees with 'n' leaves. Returns the number of "struct tree_shape"s in the
608 * first tree shape. */
610 init_tree_shape(struct tree_shape ts[], int n)
623 return init_tree_shape__(ts, n);
627 /* Advances 'ts', which currently has 'n_tses' elements, to the next possible
628 * tree shape with the number of leaves passed to init_tree_shape(). Returns
629 * the number of "struct tree_shape"s in the next shape, or 0 if all tree
630 * shapes have been visited. */
632 next_tree_shape(struct tree_shape ts[], int n_tses)
634 if (n_tses == 1 && ts->sn == 2 && ts->s[0] == 1 && ts->s[1] == 1) {
638 struct tree_shape *p = &ts[n_tses - 1];
639 p->sn = p->sn > 1 ? next_composition(&p->state, p->s, p->sn) : 0;
641 for (int i = 0; i < p->sn; i++) {
642 n_tses += init_tree_shape__(&ts[n_tses], p->s[i]);
652 print_tree_shape(const struct tree_shape ts[], int n_tses)
654 for (int i = 0; i < n_tses; i++) {
658 for (int j = 0; j < ts[i].sn; j++) {
670 test_tree_shape(struct ovs_cmdl_context *ctx)
672 int n = atoi(ctx->argv[1]);
673 struct tree_shape ts[50];
676 for (n_tses = init_tree_shape(ts, n); n_tses;
677 n_tses = next_tree_shape(ts, n_tses)) {
678 print_tree_shape(ts, n_tses);
683 /* Iteration through all possible terminal expressions (e.g. EXPR_T_CMP and
684 * EXPR_T_BOOLEAN expressions).
686 * Given a tree shape, this allows the code to try all possible ways to plug in
691 * struct expr terminal;
692 * const struct expr_symbol *vars = ...;
696 * init_terminal(&terminal, vars[0]);
698 * // Something with 'terminal'.
699 * } while (next_terminal(&terminal, vars, n_vars, n_bits));
702 /* Sets 'expr' to the first possible terminal expression. 'var' should be the
703 * first variable in the ones to be tested. */
705 init_terminal(struct expr *expr, int phase,
706 const struct expr_symbol *nvars[], int n_nvars,
707 const struct expr_symbol *svars[], int n_svars)
709 if (phase < 1 && n_nvars) {
710 expr->type = EXPR_T_CMP;
711 expr->cmp.symbol = nvars[0];
712 expr->cmp.relop = rightmost_1bit_idx(test_relops);
713 memset(&expr->cmp.value, 0, sizeof expr->cmp.value);
714 memset(&expr->cmp.mask, 0, sizeof expr->cmp.mask);
715 expr->cmp.value.integer = htonll(0);
716 expr->cmp.mask.integer = htonll(1);
720 if (phase < 2 && n_svars) {
721 expr->type = EXPR_T_CMP;
722 expr->cmp.symbol = svars[0];
723 expr->cmp.relop = EXPR_R_EQ;
724 expr->cmp.string = xstrdup("0");
728 expr->type = EXPR_T_BOOLEAN;
729 expr->boolean = false;
732 /* Returns 'x' with the rightmost contiguous string of 1s changed to 0s,
733 * e.g. 01011100 => 01000000. See H. S. Warren, Jr., _Hacker's Delight_, 2nd
734 * ed., section 2-1. */
736 turn_off_rightmost_1s(unsigned int x)
738 return ((x & -x) + x) & x;
741 static const struct expr_symbol *
742 next_var(const struct expr_symbol *symbol,
743 const struct expr_symbol *vars[], int n_vars)
745 for (int i = 0; i < n_vars; i++) {
746 if (symbol == vars[i]) {
747 return i + 1 >= n_vars ? NULL : vars[i + 1];
753 static enum expr_relop
754 next_relop(enum expr_relop relop)
756 unsigned int remaining_relops = test_relops & ~((1u << (relop + 1)) - 1);
757 return (remaining_relops
758 ? rightmost_1bit_idx(remaining_relops)
759 : rightmost_1bit_idx(test_relops));
762 /* Advances 'expr' to the next possible terminal expression within the 'n_vars'
763 * variables of 'n_bits' bits each in 'vars[]'. */
765 next_terminal(struct expr *expr,
766 const struct expr_symbol *nvars[], int n_nvars, int n_bits,
767 const struct expr_symbol *svars[], int n_svars)
769 if (expr->type == EXPR_T_BOOLEAN) {
773 expr->boolean = true;
778 if (!expr->cmp.symbol->width) {
779 int next_value = atoi(expr->cmp.string) + 1;
780 free(expr->cmp.string);
781 if (next_value > 1) {
782 expr->cmp.symbol = next_var(expr->cmp.symbol, svars, n_svars);
783 if (!expr->cmp.symbol) {
784 init_terminal(expr, 2, nvars, n_nvars, svars, n_svars);
789 expr->cmp.string = xasprintf("%d", next_value);
795 next = (ntohll(expr->cmp.value.integer)
796 + (ntohll(expr->cmp.mask.integer) << n_bits));
799 unsigned m = next >> n_bits;
800 unsigned v = next & ((1u << n_bits) - 1);
801 if (next >= (1u << (2 * n_bits))) {
802 enum expr_relop old_relop = expr->cmp.relop;
803 expr->cmp.relop = next_relop(old_relop);
804 if (expr->cmp.relop <= old_relop) {
805 expr->cmp.symbol = next_var(expr->cmp.symbol, nvars, n_nvars);
806 if (!expr->cmp.symbol) {
807 init_terminal(expr, 1, nvars, n_nvars, svars, n_svars);
813 /* Skip: empty mask is pathological. */
815 /* Skip: 1-bits in value correspond to 0-bits in mask. */
816 } else if (turn_off_rightmost_1s(m)
817 && (expr->cmp.relop != EXPR_R_EQ &&
818 expr->cmp.relop != EXPR_R_NE)) {
819 /* Skip: can't have discontiguous mask for > >= < <=. */
821 expr->cmp.value.integer = htonll(v);
822 expr->cmp.mask.integer = htonll(m);
829 make_terminal(struct expr ***terminalp)
831 struct expr *e = expr_create_boolean(true);
838 build_simple_tree(enum expr_type type, int n, struct expr ***terminalp)
841 struct expr *e = expr_create_andor(type);
842 for (int i = 0; i < 2; i++) {
843 struct expr *sub = make_terminal(terminalp);
844 ovs_list_push_back(&e->andor, &sub->node);
848 return make_terminal(terminalp);
855 build_tree_shape(enum expr_type type, const struct tree_shape **tsp,
856 struct expr ***terminalp)
858 const struct tree_shape *ts = *tsp;
861 struct expr *e = expr_create_andor(type);
862 enum expr_type t = type == EXPR_T_AND ? EXPR_T_OR : EXPR_T_AND;
863 for (int i = 0; i < ts->sn; i++) {
864 struct expr *sub = (ts->s[i] > 2
865 ? build_tree_shape(t, tsp, terminalp)
866 : build_simple_tree(t, ts->s[i], terminalp));
867 ovs_list_push_back(&e->andor, &sub->node);
877 free_rule(struct test_rule *test_rule)
879 cls_rule_destroy(&test_rule->cr);
884 test_tree_shape_exhaustively(struct expr *expr, struct shash *symtab,
885 struct expr *terminals[], int n_terminals,
886 const struct expr_symbol *nvars[], int n_nvars,
888 const struct expr_symbol *svars[], int n_svars)
890 struct simap string_map = SIMAP_INITIALIZER(&string_map);
891 simap_put(&string_map, "0", 0);
892 simap_put(&string_map, "1", 1);
896 const unsigned int var_mask = (1u << n_bits) - 1;
897 for (int i = 0; i < n_terminals; i++) {
898 init_terminal(terminals[i], 0, nvars, n_nvars, svars, n_svars);
901 struct ds s = DS_EMPTY_INITIALIZER;
903 memset(&f, 0, sizeof f);
905 for (int i = n_terminals - 1; ; i--) {
908 simap_destroy(&string_map);
911 if (next_terminal(terminals[i], nvars, n_nvars, n_bits,
915 init_terminal(terminals[i], 0, nvars, n_nvars, svars, n_svars);
917 ovs_assert(expr_honors_invariants(expr));
921 struct expr *modified;
922 if (operation == OP_CONVERT) {
924 expr_format(expr, &s);
927 modified = expr_parse_string(ds_cstr(&s), symtab, &error);
929 fprintf(stderr, "%s fails to parse (%s)\n",
933 } else if (operation >= OP_SIMPLIFY) {
934 modified = expr_simplify(expr_clone(expr));
935 ovs_assert(expr_honors_invariants(modified));
937 if (operation >= OP_NORMALIZE) {
938 modified = expr_normalize(modified);
939 ovs_assert(expr_is_normalized(modified));
944 struct classifier cls;
945 if (operation >= OP_FLOW) {
946 struct expr_match *m;
947 struct test_rule *test_rule;
949 expr_to_matches(modified, lookup_port_cb, &string_map, &matches);
951 classifier_init(&cls, NULL);
952 HMAP_FOR_EACH (m, hmap_node, &matches) {
953 test_rule = xmalloc(sizeof *test_rule);
954 cls_rule_init(&test_rule->cr, &m->match, 0);
955 classifier_insert(&cls, &test_rule->cr, CLS_MIN_VERSION,
956 m->conjunctions, m->n);
959 for (int subst = 0; subst < 1 << (n_bits * n_nvars + n_svars);
961 bool expected = evaluate_expr(expr, subst, n_bits);
962 bool actual = evaluate_expr(modified, subst, n_bits);
963 if (actual != expected) {
964 struct ds expr_s, modified_s;
967 expr_format(expr, &expr_s);
969 ds_init(&modified_s);
970 expr_format(modified, &modified_s);
973 "%s evaluates to %d, but %s evaluates to %d, for",
974 ds_cstr(&expr_s), expected,
975 ds_cstr(&modified_s), actual);
976 for (int i = 0; i < n_nvars; i++) {
980 fprintf(stderr, " n%d = 0x%x", i,
981 (subst >> (n_bits * i)) & var_mask);
983 for (int i = 0; i < n_svars; i++) {
984 fprintf(stderr, ", s%d = \"%d\"", i,
985 (subst >> (n_bits * n_nvars + i)) & 1);
991 if (operation >= OP_FLOW) {
992 for (int i = 0; i < n_nvars; i++) {
993 f.regs[i] = (subst >> (i * n_bits)) & var_mask;
995 for (int i = 0; i < n_svars; i++) {
996 f.regs[n_nvars + i] = ((subst >> (n_nvars * n_bits + i))
999 bool found = classifier_lookup(&cls, CLS_MIN_VERSION,
1001 if (expected != found) {
1002 struct ds expr_s, modified_s;
1005 expr_format(expr, &expr_s);
1007 ds_init(&modified_s);
1008 expr_format(modified, &modified_s);
1011 "%s and %s evaluate to %d, for",
1012 ds_cstr(&expr_s), ds_cstr(&modified_s), expected);
1013 for (int i = 0; i < n_nvars; i++) {
1017 fprintf(stderr, " n%d = 0x%x", i,
1018 (subst >> (n_bits * i)) & var_mask);
1020 for (int i = 0; i < n_svars; i++) {
1021 fprintf(stderr, ", s%d = \"%d\"", i,
1022 (subst >> (n_bits * n_nvars + i)) & 1);
1024 fputs(".\n", stderr);
1026 fprintf(stderr, "Converted to classifier:\n");
1027 expr_matches_print(&matches, stderr);
1029 "However, %s flow was found in the classifier.\n",
1030 found ? "a" : "no");
1035 if (operation >= OP_FLOW) {
1036 struct test_rule *test_rule;
1038 CLS_FOR_EACH (test_rule, cr, &cls) {
1039 classifier_remove(&cls, &test_rule->cr);
1040 ovsrcu_postpone(free_rule, test_rule);
1042 classifier_destroy(&cls);
1045 expr_matches_destroy(&matches);
1047 expr_destroy(modified);
1053 wait_pid(pid_t *pids, int *n)
1058 pid = waitpid(WAIT_ANY, &status, 0);
1060 ovs_fatal(errno, "waitpid failed");
1061 } else if (WIFEXITED(status)) {
1062 if (WEXITSTATUS(status)) {
1063 exit(WEXITSTATUS(status));
1065 } else if (WIFSIGNALED(status)) {
1066 raise(WTERMSIG(status));
1072 for (int i = 0; i < *n; i++) {
1073 if (pids[i] == pid) {
1074 pids[i] = pids[--*n];
1078 ovs_fatal(0, "waitpid returned unknown child");
1083 test_exhaustive(struct ovs_cmdl_context *ctx OVS_UNUSED)
1085 int n_terminals = atoi(ctx->argv[1]);
1086 struct tree_shape ts[50];
1089 struct shash symtab;
1090 const struct expr_symbol *nvars[4];
1091 const struct expr_symbol *svars[4];
1093 ovs_assert(test_nvars <= ARRAY_SIZE(nvars));
1094 ovs_assert(test_svars <= ARRAY_SIZE(svars));
1095 ovs_assert(test_nvars + test_svars <= FLOW_N_REGS);
1097 shash_init(&symtab);
1098 for (int i = 0; i < test_nvars; i++) {
1099 char *name = xasprintf("n%d", i);
1100 nvars[i] = expr_symtab_add_field(&symtab, name, MFF_REG0 + i, NULL,
1104 for (int i = 0; i < test_svars; i++) {
1105 char *name = xasprintf("s%d", i);
1106 svars[i] = expr_symtab_add_string(&symtab, name,
1107 MFF_REG0 + test_nvars + i, NULL);
1112 pid_t *children = xmalloc(test_parallel * sizeof *children);
1117 for (int i = 0; i < 2; i++) {
1118 enum expr_type base_type = i ? EXPR_T_OR : EXPR_T_AND;
1120 for (n_tses = init_tree_shape(ts, n_terminals); n_tses;
1121 n_tses = next_tree_shape(ts, n_tses)) {
1122 const struct tree_shape *tsp = ts;
1123 struct expr *terminals[50];
1124 struct expr **terminalp = terminals;
1125 struct expr *expr = build_tree_shape(base_type, &tsp, &terminalp);
1126 ovs_assert(terminalp == &terminals[n_terminals]);
1128 if (verbosity > 0) {
1129 print_tree_shape(ts, n_tses);
1131 struct ds s = DS_EMPTY_INITIALIZER;
1132 expr_format(expr, &s);
1138 if (test_parallel > 1) {
1139 pid_t pid = xfork();
1141 test_tree_shape_exhaustively(expr, &symtab,
1142 terminals, n_terminals,
1143 nvars, test_nvars, test_bits,
1148 if (n_children >= test_parallel) {
1149 wait_pid(children, &n_children);
1151 children[n_children++] = pid;
1156 n_tested += test_tree_shape_exhaustively(
1157 expr, &symtab, terminals, n_terminals,
1158 nvars, test_nvars, test_bits,
1165 while (n_children > 0) {
1166 wait_pid(children, &n_children);
1172 switch (operation) {
1174 printf("converting");
1177 printf("simplifying");
1180 printf("normalizing");
1183 printf("converting to flows");
1187 printf(" %d expressions of %d terminals", n_tested, n_terminals);
1189 printf(" all %d-terminal expressions", n_terminals);
1191 if (test_nvars || test_svars) {
1194 printf(" %d numeric vars (each %d bits) in terms of operators",
1195 test_nvars, test_bits);
1196 for (unsigned int relops = test_relops; relops;
1197 relops = zero_rightmost_1bit(relops)) {
1198 enum expr_relop r = rightmost_1bit_idx(relops);
1199 printf(" %s", expr_relop_to_string(r));
1202 if (test_nvars && test_svars) {
1206 printf(" %d string vars", test_svars);
1209 printf(" in terms of Boolean constants only");
1213 expr_symtab_destroy(&symtab);
1214 shash_destroy(&symtab);
1220 test_parse_actions(struct ovs_cmdl_context *ctx OVS_UNUSED)
1222 struct shash symtab;
1223 struct simap ports, ct_zones;
1226 create_symtab(&symtab);
1229 simap_put(&ports, "eth0", 5);
1230 simap_put(&ports, "eth1", 6);
1231 simap_put(&ports, "LOCAL", ofp_to_u16(OFPP_LOCAL));
1232 simap_init(&ct_zones);
1235 while (!ds_get_test_line(&input, stdin)) {
1236 struct ofpbuf ofpacts;
1237 struct expr *prereqs;
1240 ofpbuf_init(&ofpacts, 0);
1242 struct action_params ap = {
1244 .lookup_port = lookup_port_cb,
1246 .ct_zones = &ct_zones,
1251 .output_ptable = 64,
1254 error = actions_parse_string(ds_cstr(&input), &ap, &ofpacts, &prereqs);
1259 ds_put_cstr(&output, "actions=");
1260 ofpacts_format(ofpacts.data, ofpacts.size, &output);
1261 ds_put_cstr(&output, ", prereqs=");
1263 expr_format(prereqs, &output);
1265 ds_put_char(&output, '1');
1267 puts(ds_cstr(&output));
1268 ds_destroy(&output);
1274 expr_destroy(prereqs);
1275 ofpbuf_uninit(&ofpacts);
1279 simap_destroy(&ports);
1280 simap_destroy(&ct_zones);
1281 expr_symtab_destroy(&symtab);
1282 shash_destroy(&symtab);
1286 parse_relops(const char *s)
1288 unsigned int relops = 0;
1291 lexer_init(&lexer, s);
1294 enum expr_relop relop;
1296 if (expr_relop_from_token(lexer.token.type, &relop)) {
1297 relops |= 1u << relop;
1300 ovs_fatal(0, "%s: relational operator expected at `%.*s'",
1301 s, (int) (lexer.input - lexer.start), lexer.start);
1303 lexer_match(&lexer, LEX_T_COMMA);
1304 } while (lexer.token.type != LEX_T_END);
1305 lexer_destroy(&lexer);
1314 %s: OVN test utility\n\
1315 usage: test-ovn %s [OPTIONS] COMMAND [ARG...]\n\
1318 Lexically analyzes OVN input from stdin and print them back on stdout.\n\
1325 Parses OVN expressions from stdin and print them back on stdout after\n\
1326 differing degrees of analysis. Available fields are based on packet\n\
1329 evaluate-expr A B C\n\
1330 Parses OVN expressions from stdin, evaluate them with assigned values,\n\
1331 and print the results on stdout. Available fields are 'a', 'b', and 'c'\n\
1332 of 3 bits each. A, B, and C should be in the range 0 to 7.\n\
1335 Prints all the compositions of N on stdout.\n\
1338 Prints all the tree shapes with N terminals on stdout.\n\
1341 Tests that all possible Boolean expressions with N terminals are properly\n\
1342 simplified, normalized, and converted to flows. Available options:\n\
1344 --operation=OPERATION Operation to test, one of: convert, simplify,\n\
1345 normalize, flow. Default: flow. 'normalize' includes 'simplify',\n\
1346 'flow' includes 'simplify' and 'normalize'.\n\
1347 --parallel=N Number of processes to use in parallel, default 1.\n\
1349 --nvars=N Number of numeric vars to test, in range 0...4, default 2.\n\
1350 --bits=N Number of bits per variable, in range 1...3, default 3.\n\
1351 --relops=OPERATORS Test only the specified Boolean operators.\n\
1352 OPERATORS may include == != < <= > >=, space or\n\
1353 comma separated. Default is all operators.\n\
1355 --svars=N Number of string vars to test, in range 0...4, default 2.\n\
1358 Parses OVN actions from stdin and prints the equivalent OpenFlow actions\n\
1361 program_name, program_name);
1366 test_ovn_main(int argc, char *argv[])
1369 OPT_RELOPS = UCHAR_MAX + 1,
1376 static const struct option long_options[] = {
1377 {"relops", required_argument, NULL, OPT_RELOPS},
1378 {"nvars", required_argument, NULL, OPT_NVARS},
1379 {"svars", required_argument, NULL, OPT_SVARS},
1380 {"bits", required_argument, NULL, OPT_BITS},
1381 {"operation", required_argument, NULL, OPT_OPERATION},
1382 {"parallel", required_argument, NULL, OPT_PARALLEL},
1383 {"more", no_argument, NULL, 'm'},
1384 {"help", no_argument, NULL, 'h'},
1387 char *short_options = ovs_cmdl_long_options_to_short_options(long_options);
1389 set_program_name(argv[0]);
1391 test_relops = parse_relops("== != < <= > >=");
1393 int option_index = 0;
1394 int c = getopt_long (argc, argv, short_options, long_options,
1402 test_relops = parse_relops(optarg);
1406 test_nvars = atoi(optarg);
1407 if (test_nvars < 0 || test_nvars > 4) {
1408 ovs_fatal(0, "number of numeric variables must be "
1414 test_svars = atoi(optarg);
1415 if (test_svars < 0 || test_svars > 4) {
1416 ovs_fatal(0, "number of string variables must be "
1422 test_bits = atoi(optarg);
1423 if (test_bits < 1 || test_bits > 3) {
1424 ovs_fatal(0, "number of bits must be between 1 and 3");
1429 if (!strcmp(optarg, "convert")) {
1430 operation = OP_CONVERT;
1431 } else if (!strcmp(optarg, "simplify")) {
1432 operation = OP_SIMPLIFY;
1433 } else if (!strcmp(optarg, "normalize")) {
1434 operation = OP_NORMALIZE;
1435 } else if (!strcmp(optarg, "flow")) {
1436 operation = OP_FLOW;
1438 ovs_fatal(0, "%s: unknown operation", optarg);
1443 test_parallel = atoi(optarg);
1460 free(short_options);
1462 static const struct ovs_cmdl_command commands[] = {
1464 {"lex", NULL, 0, 0, test_lex},
1467 {"parse-expr", NULL, 0, 0, test_parse_expr},
1468 {"annotate-expr", NULL, 0, 0, test_annotate_expr},
1469 {"simplify-expr", NULL, 0, 0, test_simplify_expr},
1470 {"normalize-expr", NULL, 0, 0, test_normalize_expr},
1471 {"expr-to-flows", NULL, 0, 0, test_expr_to_flows},
1472 {"evaluate-expr", NULL, 1, 1, test_evaluate_expr},
1473 {"composition", NULL, 1, 1, test_composition},
1474 {"tree-shape", NULL, 1, 1, test_tree_shape},
1475 {"exhaustive", NULL, 1, 1, test_exhaustive},
1478 {"parse-actions", NULL, 0, 0, test_parse_actions},
1480 {NULL, NULL, 0, 0, NULL},
1482 struct ovs_cmdl_context ctx;
1483 ctx.argc = argc - optind;
1484 ctx.argv = argv + optind;
1485 ovs_cmdl_run_command(&ctx, commands);
1488 OVSTEST_REGISTER("test-ovn", test_ovn_main);