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.
21 #include "command-line.h"
22 #include "fatal-signal.h"
24 #include "openvswitch/dynamic-string.h"
25 #include "openvswitch/match.h"
26 #include "openvswitch/ofp-actions.h"
27 #include "openvswitch/ofpbuf.h"
28 #include "openvswitch/vlog.h"
29 #include "ovn/lib/actions.h"
30 #include "ovn/lib/expr.h"
31 #include "ovn/lib/lex.h"
32 #include "ovn/lib/ovn-dhcp.h"
33 #include "ovs-thread.h"
39 /* --relops: Bitmap of the relational operators to test, in exhaustive test. */
40 static unsigned int test_relops;
42 /* --nvars: Number of numeric variables to test, in exhaustive test. */
43 static int test_nvars = 2;
45 /* --svars: Number of string variables to test, in exhaustive test. */
46 static int test_svars = 2;
48 /* --bits: Number of bits per variable, in exhaustive test. */
49 static int test_bits = 3;
51 /* --operation: The operation to test, in exhaustive test. */
52 static enum { OP_CONVERT, OP_SIMPLIFY, OP_NORMALIZE, OP_FLOW } operation
55 /* --parallel: Number of parallel processes to use in test. */
56 static int test_parallel = 1;
58 /* -m, --more: Message verbosity */
62 compare_token(const struct lex_token *a, const struct lex_token *b)
64 if (a->type != b->type) {
65 fprintf(stderr, "type differs: %d -> %d\n", a->type, b->type);
69 if (!((a->s && b->s && !strcmp(a->s, b->s))
70 || (!a->s && !b->s))) {
71 fprintf(stderr, "string differs: %s -> %s\n",
72 a->s ? a->s : "(null)",
73 b->s ? b->s : "(null)");
77 if (a->type == LEX_T_INTEGER || a->type == LEX_T_MASKED_INTEGER) {
78 if (memcmp(&a->value, &b->value, sizeof a->value)) {
79 fprintf(stderr, "value differs\n");
83 if (a->type == LEX_T_MASKED_INTEGER
84 && memcmp(&a->mask, &b->mask, sizeof a->mask)) {
85 fprintf(stderr, "mask differs\n");
89 if (a->format != b->format
90 && !(a->format == LEX_F_HEXADECIMAL
91 && b->format == LEX_F_DECIMAL
92 && a->value.integer == 0)) {
93 fprintf(stderr, "format differs: %d -> %d\n",
94 a->format, b->format);
100 test_lex(struct ovs_cmdl_context *ctx OVS_UNUSED)
107 while (!ds_get_test_line(&input, stdin)) {
110 lexer_init(&lexer, ds_cstr(&input));
112 while (lexer_get(&lexer) != LEX_T_END) {
113 size_t len = output.length;
114 lex_token_format(&lexer.token, &output);
116 /* Check that the formatted version can really be parsed back
118 if (lexer.token.type != LEX_T_ERROR) {
119 const char *s = ds_cstr(&output) + len;
124 compare_token(&lexer.token, &l2.token);
127 ds_put_char(&output, ' ');
129 lexer_destroy(&lexer);
131 ds_chomp(&output, ' ');
132 puts(ds_cstr(&output));
139 create_symtab(struct shash *symtab)
143 /* Reserve a pair of registers for the logical inport and outport. A full
144 * 32-bit register each is bigger than we need, but the expression code
145 * doesn't yet support string fields that occupy less than a full OXM. */
146 expr_symtab_add_string(symtab, "inport", MFF_REG14, NULL);
147 expr_symtab_add_string(symtab, "outport", MFF_REG15, NULL);
149 expr_symtab_add_field(symtab, "xreg0", MFF_XREG0, NULL, false);
150 expr_symtab_add_field(symtab, "xreg1", MFF_XREG1, NULL, false);
151 expr_symtab_add_field(symtab, "xreg2", MFF_XREG2, NULL, false);
153 expr_symtab_add_subfield(symtab, "reg0", NULL, "xreg0[32..63]");
154 expr_symtab_add_subfield(symtab, "reg1", NULL, "xreg0[0..31]");
155 expr_symtab_add_subfield(symtab, "reg2", NULL, "xreg1[32..63]");
156 expr_symtab_add_subfield(symtab, "reg3", NULL, "xreg1[0..31]");
157 expr_symtab_add_subfield(symtab, "reg4", NULL, "xreg2[32..63]");
158 expr_symtab_add_subfield(symtab, "reg5", NULL, "xreg2[0..31]");
160 expr_symtab_add_field(symtab, "eth.src", MFF_ETH_SRC, NULL, false);
161 expr_symtab_add_field(symtab, "eth.dst", MFF_ETH_DST, NULL, false);
162 expr_symtab_add_field(symtab, "eth.type", MFF_ETH_TYPE, NULL, true);
164 expr_symtab_add_field(symtab, "vlan.tci", MFF_VLAN_TCI, NULL, false);
165 expr_symtab_add_predicate(symtab, "vlan.present", "vlan.tci[12]");
166 expr_symtab_add_subfield(symtab, "vlan.pcp", "vlan.present",
168 expr_symtab_add_subfield(symtab, "vlan.vid", "vlan.present",
171 expr_symtab_add_predicate(symtab, "ip4", "eth.type == 0x800");
172 expr_symtab_add_predicate(symtab, "ip6", "eth.type == 0x86dd");
173 expr_symtab_add_predicate(symtab, "ip", "ip4 || ip6");
174 expr_symtab_add_field(symtab, "ip.proto", MFF_IP_PROTO, "ip", true);
175 expr_symtab_add_field(symtab, "ip.dscp", MFF_IP_DSCP, "ip", false);
176 expr_symtab_add_field(symtab, "ip.ecn", MFF_IP_ECN, "ip", false);
177 expr_symtab_add_field(symtab, "ip.ttl", MFF_IP_TTL, "ip", false);
179 expr_symtab_add_field(symtab, "ip4.src", MFF_IPV4_SRC, "ip4", false);
180 expr_symtab_add_field(symtab, "ip4.dst", MFF_IPV4_DST, "ip4", false);
182 expr_symtab_add_predicate(symtab, "icmp4", "ip4 && ip.proto == 1");
183 expr_symtab_add_field(symtab, "icmp4.type", MFF_ICMPV4_TYPE, "icmp4",
185 expr_symtab_add_field(symtab, "icmp4.code", MFF_ICMPV4_CODE, "icmp4",
188 expr_symtab_add_field(symtab, "ip6.src", MFF_IPV6_SRC, "ip6", false);
189 expr_symtab_add_field(symtab, "ip6.dst", MFF_IPV6_DST, "ip6", false);
190 expr_symtab_add_field(symtab, "ip6.label", MFF_IPV6_LABEL, "ip6", false);
192 expr_symtab_add_predicate(symtab, "icmp6", "ip6 && ip.proto == 58");
193 expr_symtab_add_field(symtab, "icmp6.type", MFF_ICMPV6_TYPE, "icmp6",
195 expr_symtab_add_field(symtab, "icmp6.code", MFF_ICMPV6_CODE, "icmp6",
198 expr_symtab_add_predicate(symtab, "icmp", "icmp4 || icmp6");
200 expr_symtab_add_field(symtab, "ip.frag", MFF_IP_FRAG, "ip", false);
201 expr_symtab_add_predicate(symtab, "ip.is_frag", "ip.frag[0]");
202 expr_symtab_add_predicate(symtab, "ip.later_frag", "ip.frag[1]");
203 expr_symtab_add_predicate(symtab, "ip.first_frag", "ip.is_frag && !ip.later_frag");
205 expr_symtab_add_predicate(symtab, "arp", "eth.type == 0x806");
206 expr_symtab_add_field(symtab, "arp.op", MFF_ARP_OP, "arp", false);
207 expr_symtab_add_field(symtab, "arp.spa", MFF_ARP_SPA, "arp", false);
208 expr_symtab_add_field(symtab, "arp.sha", MFF_ARP_SHA, "arp", false);
209 expr_symtab_add_field(symtab, "arp.tpa", MFF_ARP_TPA, "arp", false);
210 expr_symtab_add_field(symtab, "arp.tha", MFF_ARP_THA, "arp", false);
212 expr_symtab_add_predicate(symtab, "nd", "icmp6.type == {135, 136} && icmp6.code == 0");
213 expr_symtab_add_field(symtab, "nd.target", MFF_ND_TARGET, "nd", false);
214 expr_symtab_add_field(symtab, "nd.sll", MFF_ND_SLL,
215 "nd && icmp6.type == 135", false);
216 expr_symtab_add_field(symtab, "nd.tll", MFF_ND_TLL,
217 "nd && icmp6.type == 136", false);
219 expr_symtab_add_predicate(symtab, "tcp", "ip.proto == 6");
220 expr_symtab_add_field(symtab, "tcp.src", MFF_TCP_SRC, "tcp", false);
221 expr_symtab_add_field(symtab, "tcp.dst", MFF_TCP_DST, "tcp", false);
222 expr_symtab_add_field(symtab, "tcp.flags", MFF_TCP_FLAGS, "tcp", false);
224 expr_symtab_add_predicate(symtab, "udp", "ip.proto == 17");
225 expr_symtab_add_field(symtab, "udp.src", MFF_UDP_SRC, "udp", false);
226 expr_symtab_add_field(symtab, "udp.dst", MFF_UDP_DST, "udp", false);
228 expr_symtab_add_predicate(symtab, "sctp", "ip.proto == 132");
229 expr_symtab_add_field(symtab, "sctp.src", MFF_SCTP_SRC, "sctp", false);
230 expr_symtab_add_field(symtab, "sctp.dst", MFF_SCTP_DST, "sctp", false);
232 /* For negative testing. */
233 expr_symtab_add_field(symtab, "bad_prereq", MFF_XREG0, "xyzzy", false);
234 expr_symtab_add_field(symtab, "self_recurse", MFF_XREG0,
235 "self_recurse != 0", false);
236 expr_symtab_add_field(symtab, "mutual_recurse_1", MFF_XREG0,
237 "mutual_recurse_2 != 0", false);
238 expr_symtab_add_field(symtab, "mutual_recurse_2", MFF_XREG0,
239 "mutual_recurse_1 != 0", false);
240 expr_symtab_add_string(symtab, "big_string", MFF_XREG0, NULL);
244 create_dhcp_opts(struct hmap *dhcp_opts)
246 hmap_init(dhcp_opts);
247 dhcp_opt_add(dhcp_opts, "offerip", 0, "ipv4");
248 dhcp_opt_add(dhcp_opts, "netmask", 1, "ipv4");
249 dhcp_opt_add(dhcp_opts, "router", 3, "ipv4");
250 dhcp_opt_add(dhcp_opts, "dns_server", 6, "ipv4");
251 dhcp_opt_add(dhcp_opts, "log_server", 7, "ipv4");
252 dhcp_opt_add(dhcp_opts, "lpr_server", 9, "ipv4");
253 dhcp_opt_add(dhcp_opts, "domain", 15, "str");
254 dhcp_opt_add(dhcp_opts, "swap_server", 16, "ipv4");
255 dhcp_opt_add(dhcp_opts, "policy_filter", 21, "ipv4");
256 dhcp_opt_add(dhcp_opts, "router_solicitation", 32, "ipv4");
257 dhcp_opt_add(dhcp_opts, "nis_server", 41, "ipv4");
258 dhcp_opt_add(dhcp_opts, "ntp_server", 42, "ipv4");
259 dhcp_opt_add(dhcp_opts, "server_id", 54, "ipv4");
260 dhcp_opt_add(dhcp_opts, "tftp_server", 66, "ipv4");
261 dhcp_opt_add(dhcp_opts, "classless_static_route", 121, "static_routes");
262 dhcp_opt_add(dhcp_opts, "ip_forward_enable", 19, "bool");
263 dhcp_opt_add(dhcp_opts, "router_discovery", 31, "bool");
264 dhcp_opt_add(dhcp_opts, "ethernet_encap", 36, "bool");
265 dhcp_opt_add(dhcp_opts, "default_ttl", 23, "uint8");
266 dhcp_opt_add(dhcp_opts, "tcp_ttl", 37, "uint8");
267 dhcp_opt_add(dhcp_opts, "mtu", 26, "uint16");
268 dhcp_opt_add(dhcp_opts, "lease_time", 51, "uint32");
272 create_macros(struct shash *macros)
276 static const char *const addrs1[] = {
277 "10.0.0.1", "10.0.0.2", "10.0.0.3",
279 static const char *const addrs2[] = {
282 static const char *const addrs3[] = {
283 "00:00:00:00:00:01", "00:00:00:00:00:02", "00:00:00:00:00:03",
286 expr_macros_add(macros, "set1", addrs1, 3);
287 expr_macros_add(macros, "set2", addrs2, 3);
288 expr_macros_add(macros, "set3", addrs3, 3);
292 lookup_port_cb(const void *ports_, const char *port_name, unsigned int *portp)
294 const struct simap *ports = ports_;
295 const struct simap_node *node = simap_find(ports, port_name);
304 test_parse_expr__(int steps)
311 create_symtab(&symtab);
312 create_macros(¯os);
315 simap_put(&ports, "eth0", 5);
316 simap_put(&ports, "eth1", 6);
317 simap_put(&ports, "LOCAL", ofp_to_u16(OFPP_LOCAL));
320 while (!ds_get_test_line(&input, stdin)) {
324 expr = expr_parse_string(ds_cstr(&input), &symtab, ¯os, &error);
325 if (!error && steps > 0) {
326 expr = expr_annotate(expr, &symtab, &error);
330 expr = expr_simplify(expr);
333 expr = expr_normalize(expr);
334 ovs_assert(expr_is_normalized(expr));
341 expr_to_matches(expr, lookup_port_cb, &ports, &matches);
342 expr_matches_print(&matches, stdout);
343 expr_matches_destroy(&matches);
345 struct ds output = DS_EMPTY_INITIALIZER;
346 expr_format(expr, &output);
347 puts(ds_cstr(&output));
358 simap_destroy(&ports);
359 expr_symtab_destroy(&symtab);
360 shash_destroy(&symtab);
361 expr_macros_destroy(¯os);
362 shash_destroy(¯os);
366 test_parse_expr(struct ovs_cmdl_context *ctx OVS_UNUSED)
368 test_parse_expr__(0);
372 test_annotate_expr(struct ovs_cmdl_context *ctx OVS_UNUSED)
374 test_parse_expr__(1);
378 test_simplify_expr(struct ovs_cmdl_context *ctx OVS_UNUSED)
380 test_parse_expr__(2);
384 test_normalize_expr(struct ovs_cmdl_context *ctx OVS_UNUSED)
386 test_parse_expr__(3);
390 test_expr_to_flows(struct ovs_cmdl_context *ctx OVS_UNUSED)
392 test_parse_expr__(4);
395 /* Evaluate an expression. */
397 static bool evaluate_expr(const struct expr *, unsigned int subst, int n_bits);
400 evaluate_andor_expr(const struct expr *expr, unsigned int subst, int n_bits,
403 const struct expr *sub;
405 LIST_FOR_EACH (sub, node, &expr->andor) {
406 if (evaluate_expr(sub, subst, n_bits) == short_circuit) {
407 return short_circuit;
410 return !short_circuit;
414 evaluate_cmp_expr(const struct expr *expr, unsigned int subst, int n_bits)
416 int var_idx = atoi(expr->cmp.symbol->name + 1);
417 if (expr->cmp.symbol->name[0] == 'n') {
418 unsigned var_mask = (1u << n_bits) - 1;
419 unsigned int arg1 = (subst >> (var_idx * n_bits)) & var_mask;
420 unsigned int arg2 = ntohll(expr->cmp.value.integer);
421 unsigned int mask = ntohll(expr->cmp.mask.integer);
423 ovs_assert(!(mask & ~var_mask));
424 ovs_assert(!(arg2 & ~var_mask));
425 ovs_assert(!(arg2 & ~mask));
428 switch (expr->cmp.relop) {
450 } else if (expr->cmp.symbol->name[0] == 's') {
451 unsigned int arg1 = (subst >> (test_nvars * n_bits + var_idx)) & 1;
452 unsigned int arg2 = atoi(expr->cmp.string);
459 /* Evaluates 'expr' and returns its Boolean result. 'subst' provides the value
460 * for the variables, which must be 'n_bits' bits each and be named "a", "b",
461 * "c", etc. The value of variable "a" is the least-significant 'n_bits' bits
462 * of 'subst', the value of "b" is the next 'n_bits' bits, and so on. */
464 evaluate_expr(const struct expr *expr, unsigned int subst, int n_bits)
466 switch (expr->type) {
468 return evaluate_cmp_expr(expr, subst, n_bits);
471 return evaluate_andor_expr(expr, subst, n_bits, false);
474 return evaluate_andor_expr(expr, subst, n_bits, true);
477 return expr->boolean;
485 test_evaluate_expr(struct ovs_cmdl_context *ctx)
487 int a = atoi(ctx->argv[1]);
488 int b = atoi(ctx->argv[2]);
489 int c = atoi(ctx->argv[3]);
490 unsigned int subst = a | (b << 3) || (c << 6);
495 expr_symtab_add_field(&symtab, "xreg0", MFF_XREG0, NULL, false);
496 expr_symtab_add_field(&symtab, "xreg1", MFF_XREG1, NULL, false);
497 expr_symtab_add_field(&symtab, "xreg2", MFF_XREG1, NULL, false);
498 expr_symtab_add_subfield(&symtab, "a", NULL, "xreg0[0..2]");
499 expr_symtab_add_subfield(&symtab, "b", NULL, "xreg1[0..2]");
500 expr_symtab_add_subfield(&symtab, "c", NULL, "xreg2[0..2]");
503 while (!ds_get_test_line(&input, stdin)) {
507 expr = expr_parse_string(ds_cstr(&input), &symtab, NULL, &error);
509 expr = expr_annotate(expr, &symtab, &error);
512 printf("%d\n", evaluate_expr(expr, subst, 3));
521 expr_symtab_destroy(&symtab);
522 shash_destroy(&symtab);
527 * The "compositions" of a positive integer N are all of the ways that one can
528 * add up positive integers to sum to N. For example, the compositions of 3
529 * are 3, 2+1, 1+2, and 1+1+1.
531 * We use compositions to find all the ways to break up N terms of a Boolean
532 * expression into subexpressions. Suppose we want to generate all expressions
533 * with 3 terms. The compositions of 3 (ignoring 3 itself) provide the
534 * possibilities (x && x) || x, x || (x && x), and x || x || x. (Of course one
535 * can exchange && for || in each case.) One must recursively compose the
536 * sub-expressions whose values are 3 or greater; that is what the "tree shape"
537 * concept later covers.
539 * To iterate through all compositions of, e.g., 5:
541 * unsigned int state;
545 * for (n = first_composition(ARRAY_SIZE(s), &state, s); n > 0;
546 * n = next_composition(&state, s, n)) {
547 * // Do something with composition 's' with 'n' elements.
550 * Algorithm from D. E. Knuth, _The Art of Computer Programming, Vol. 4A:
551 * Combinatorial Algorithms, Part 1_, section 7.2.1.1, answer to exercise
555 /* Begins iteration through the compositions of 'n'. Initializes 's' to the
556 * number of elements in the first composition of 'n' and returns that number
557 * of elements. The first composition in fact is always 'n' itself, so the
558 * return value will be 1.
560 * Initializes '*state' to some internal state information. The caller must
561 * maintain this state (and 's') for use by next_composition().
563 * 's' must have room for at least 'n' elements. */
565 first_composition(int n, unsigned int *state, int s[])
572 /* Advances 's', with 'sn' elements, to the next composition and returns the
573 * number of elements in this new composition, or 0 if no compositions are
574 * left. 'state' is the same internal state passed to first_composition(). */
576 next_composition(unsigned int *state, int s[], int sn)
607 test_composition(struct ovs_cmdl_context *ctx)
609 int n = atoi(ctx->argv[1]);
613 for (int sn = first_composition(n, &state, s); sn;
614 sn = next_composition(&state, s, sn)) {
615 for (int i = 0; i < sn; i++) {
616 printf("%d%c", s[i], i == sn - 1 ? '\n' : ' ');
623 * This code generates all possible Boolean expressions with a specified number
624 * of terms N (equivalent to the number of external nodes in a tree).
626 * See test_tree_shape() for a simple example. */
628 /* An array of these structures describes the shape of a tree.
630 * A single element of struct tree_shape describes a single node in the tree.
631 * The node has 'sn' direct children. From left to right, for i in 0...sn-1,
632 * s[i] is 1 if the child is a leaf node, otherwise the child is a subtree and
633 * s[i] is the number of leaf nodes within that subtree. In the latter case,
634 * the subtree is described by another struct tree_shape within the enclosing
635 * array. The tree_shapes are ordered in the array in in-order.
644 init_tree_shape__(struct tree_shape ts[], int n)
651 /* Skip the first composition intentionally. */
652 ts->sn = first_composition(n, &ts->state, ts->s);
653 ts->sn = next_composition(&ts->state, ts->s, ts->sn);
654 for (int i = 0; i < ts->sn; i++) {
655 n_tses += init_tree_shape__(&ts[n_tses], ts->s[i]);
660 /* Initializes 'ts[]' as the first in the set of all of possible shapes of
661 * trees with 'n' leaves. Returns the number of "struct tree_shape"s in the
662 * first tree shape. */
664 init_tree_shape(struct tree_shape ts[], int n)
677 return init_tree_shape__(ts, n);
681 /* Advances 'ts', which currently has 'n_tses' elements, to the next possible
682 * tree shape with the number of leaves passed to init_tree_shape(). Returns
683 * the number of "struct tree_shape"s in the next shape, or 0 if all tree
684 * shapes have been visited. */
686 next_tree_shape(struct tree_shape ts[], int n_tses)
688 if (n_tses == 1 && ts->sn == 2 && ts->s[0] == 1 && ts->s[1] == 1) {
692 struct tree_shape *p = &ts[n_tses - 1];
693 p->sn = p->sn > 1 ? next_composition(&p->state, p->s, p->sn) : 0;
695 for (int i = 0; i < p->sn; i++) {
696 n_tses += init_tree_shape__(&ts[n_tses], p->s[i]);
706 print_tree_shape(const struct tree_shape ts[], int n_tses)
708 for (int i = 0; i < n_tses; i++) {
712 for (int j = 0; j < ts[i].sn; j++) {
724 test_tree_shape(struct ovs_cmdl_context *ctx)
726 int n = atoi(ctx->argv[1]);
727 struct tree_shape ts[50];
730 for (n_tses = init_tree_shape(ts, n); n_tses;
731 n_tses = next_tree_shape(ts, n_tses)) {
732 print_tree_shape(ts, n_tses);
737 /* Iteration through all possible terminal expressions (e.g. EXPR_T_CMP and
738 * EXPR_T_BOOLEAN expressions).
740 * Given a tree shape, this allows the code to try all possible ways to plug in
745 * struct expr terminal;
746 * const struct expr_symbol *vars = ...;
750 * init_terminal(&terminal, vars[0]);
752 * // Something with 'terminal'.
753 * } while (next_terminal(&terminal, vars, n_vars, n_bits));
756 /* Sets 'expr' to the first possible terminal expression. 'var' should be the
757 * first variable in the ones to be tested. */
759 init_terminal(struct expr *expr, int phase,
760 const struct expr_symbol *nvars[], int n_nvars,
761 const struct expr_symbol *svars[], int n_svars)
763 if (phase < 1 && n_nvars) {
764 expr->type = EXPR_T_CMP;
765 expr->cmp.symbol = nvars[0];
766 expr->cmp.relop = rightmost_1bit_idx(test_relops);
767 memset(&expr->cmp.value, 0, sizeof expr->cmp.value);
768 memset(&expr->cmp.mask, 0, sizeof expr->cmp.mask);
769 expr->cmp.value.integer = htonll(0);
770 expr->cmp.mask.integer = htonll(1);
774 if (phase < 2 && n_svars) {
775 expr->type = EXPR_T_CMP;
776 expr->cmp.symbol = svars[0];
777 expr->cmp.relop = EXPR_R_EQ;
778 expr->cmp.string = xstrdup("0");
782 expr->type = EXPR_T_BOOLEAN;
783 expr->boolean = false;
786 /* Returns 'x' with the rightmost contiguous string of 1s changed to 0s,
787 * e.g. 01011100 => 01000000. See H. S. Warren, Jr., _Hacker's Delight_, 2nd
788 * ed., section 2-1. */
790 turn_off_rightmost_1s(unsigned int x)
792 return ((x & -x) + x) & x;
795 static const struct expr_symbol *
796 next_var(const struct expr_symbol *symbol,
797 const struct expr_symbol *vars[], int n_vars)
799 for (int i = 0; i < n_vars; i++) {
800 if (symbol == vars[i]) {
801 return i + 1 >= n_vars ? NULL : vars[i + 1];
807 static enum expr_relop
808 next_relop(enum expr_relop relop)
810 unsigned int remaining_relops = test_relops & ~((1u << (relop + 1)) - 1);
811 return (remaining_relops
812 ? rightmost_1bit_idx(remaining_relops)
813 : rightmost_1bit_idx(test_relops));
816 /* Advances 'expr' to the next possible terminal expression within the 'n_vars'
817 * variables of 'n_bits' bits each in 'vars[]'. */
819 next_terminal(struct expr *expr,
820 const struct expr_symbol *nvars[], int n_nvars, int n_bits,
821 const struct expr_symbol *svars[], int n_svars)
823 if (expr->type == EXPR_T_BOOLEAN) {
827 expr->boolean = true;
832 if (!expr->cmp.symbol->width) {
833 int next_value = atoi(expr->cmp.string) + 1;
834 free(expr->cmp.string);
835 if (next_value > 1) {
836 expr->cmp.symbol = next_var(expr->cmp.symbol, svars, n_svars);
837 if (!expr->cmp.symbol) {
838 init_terminal(expr, 2, nvars, n_nvars, svars, n_svars);
843 expr->cmp.string = xasprintf("%d", next_value);
849 next = (ntohll(expr->cmp.value.integer)
850 + (ntohll(expr->cmp.mask.integer) << n_bits));
853 unsigned m = next >> n_bits;
854 unsigned v = next & ((1u << n_bits) - 1);
855 if (next >= (1u << (2 * n_bits))) {
856 enum expr_relop old_relop = expr->cmp.relop;
857 expr->cmp.relop = next_relop(old_relop);
858 if (expr->cmp.relop <= old_relop) {
859 expr->cmp.symbol = next_var(expr->cmp.symbol, nvars, n_nvars);
860 if (!expr->cmp.symbol) {
861 init_terminal(expr, 1, nvars, n_nvars, svars, n_svars);
867 /* Skip: empty mask is pathological. */
869 /* Skip: 1-bits in value correspond to 0-bits in mask. */
870 } else if (turn_off_rightmost_1s(m)
871 && (expr->cmp.relop != EXPR_R_EQ &&
872 expr->cmp.relop != EXPR_R_NE)) {
873 /* Skip: can't have discontiguous mask for > >= < <=. */
875 expr->cmp.value.integer = htonll(v);
876 expr->cmp.mask.integer = htonll(m);
883 make_terminal(struct expr ***terminalp)
885 struct expr *e = expr_create_boolean(true);
892 build_simple_tree(enum expr_type type, int n, struct expr ***terminalp)
895 struct expr *e = expr_create_andor(type);
896 for (int i = 0; i < 2; i++) {
897 struct expr *sub = make_terminal(terminalp);
898 ovs_list_push_back(&e->andor, &sub->node);
902 return make_terminal(terminalp);
909 build_tree_shape(enum expr_type type, const struct tree_shape **tsp,
910 struct expr ***terminalp)
912 const struct tree_shape *ts = *tsp;
915 struct expr *e = expr_create_andor(type);
916 enum expr_type t = type == EXPR_T_AND ? EXPR_T_OR : EXPR_T_AND;
917 for (int i = 0; i < ts->sn; i++) {
918 struct expr *sub = (ts->s[i] > 2
919 ? build_tree_shape(t, tsp, terminalp)
920 : build_simple_tree(t, ts->s[i], terminalp));
921 ovs_list_push_back(&e->andor, &sub->node);
931 free_rule(struct test_rule *test_rule)
933 cls_rule_destroy(&test_rule->cr);
938 test_tree_shape_exhaustively(struct expr *expr, struct shash *symtab,
939 struct expr *terminals[], int n_terminals,
940 const struct expr_symbol *nvars[], int n_nvars,
942 const struct expr_symbol *svars[], int n_svars)
944 struct simap string_map = SIMAP_INITIALIZER(&string_map);
945 simap_put(&string_map, "0", 0);
946 simap_put(&string_map, "1", 1);
950 const unsigned int var_mask = (1u << n_bits) - 1;
951 for (int i = 0; i < n_terminals; i++) {
952 init_terminal(terminals[i], 0, nvars, n_nvars, svars, n_svars);
955 struct ds s = DS_EMPTY_INITIALIZER;
957 memset(&f, 0, sizeof f);
959 for (int i = n_terminals - 1; ; i--) {
962 simap_destroy(&string_map);
965 if (next_terminal(terminals[i], nvars, n_nvars, n_bits,
969 init_terminal(terminals[i], 0, nvars, n_nvars, svars, n_svars);
971 ovs_assert(expr_honors_invariants(expr));
975 struct expr *modified;
976 if (operation == OP_CONVERT) {
978 expr_format(expr, &s);
981 modified = expr_parse_string(ds_cstr(&s), symtab, NULL, &error);
983 fprintf(stderr, "%s fails to parse (%s)\n",
987 } else if (operation >= OP_SIMPLIFY) {
988 modified = expr_simplify(expr_clone(expr));
989 ovs_assert(expr_honors_invariants(modified));
991 if (operation >= OP_NORMALIZE) {
992 modified = expr_normalize(modified);
993 ovs_assert(expr_is_normalized(modified));
998 struct classifier cls;
999 if (operation >= OP_FLOW) {
1000 struct expr_match *m;
1001 struct test_rule *test_rule;
1003 expr_to_matches(modified, lookup_port_cb, &string_map, &matches);
1005 classifier_init(&cls, NULL);
1006 HMAP_FOR_EACH (m, hmap_node, &matches) {
1007 test_rule = xmalloc(sizeof *test_rule);
1008 cls_rule_init(&test_rule->cr, &m->match, 0);
1009 classifier_insert(&cls, &test_rule->cr, CLS_MIN_VERSION,
1010 m->conjunctions, m->n);
1013 for (int subst = 0; subst < 1 << (n_bits * n_nvars + n_svars);
1015 bool expected = evaluate_expr(expr, subst, n_bits);
1016 bool actual = evaluate_expr(modified, subst, n_bits);
1017 if (actual != expected) {
1018 struct ds expr_s, modified_s;
1021 expr_format(expr, &expr_s);
1023 ds_init(&modified_s);
1024 expr_format(modified, &modified_s);
1027 "%s evaluates to %d, but %s evaluates to %d, for",
1028 ds_cstr(&expr_s), expected,
1029 ds_cstr(&modified_s), actual);
1030 for (int i = 0; i < n_nvars; i++) {
1034 fprintf(stderr, " n%d = 0x%x", i,
1035 (subst >> (n_bits * i)) & var_mask);
1037 for (int i = 0; i < n_svars; i++) {
1038 fprintf(stderr, ", s%d = \"%d\"", i,
1039 (subst >> (n_bits * n_nvars + i)) & 1);
1045 if (operation >= OP_FLOW) {
1046 for (int i = 0; i < n_nvars; i++) {
1047 f.regs[i] = (subst >> (i * n_bits)) & var_mask;
1049 for (int i = 0; i < n_svars; i++) {
1050 f.regs[n_nvars + i] = ((subst >> (n_nvars * n_bits + i))
1053 bool found = classifier_lookup(&cls, CLS_MIN_VERSION,
1055 if (expected != found) {
1056 struct ds expr_s, modified_s;
1059 expr_format(expr, &expr_s);
1061 ds_init(&modified_s);
1062 expr_format(modified, &modified_s);
1065 "%s and %s evaluate to %d, for",
1066 ds_cstr(&expr_s), ds_cstr(&modified_s), expected);
1067 for (int i = 0; i < n_nvars; i++) {
1071 fprintf(stderr, " n%d = 0x%x", i,
1072 (subst >> (n_bits * i)) & var_mask);
1074 for (int i = 0; i < n_svars; i++) {
1075 fprintf(stderr, ", s%d = \"%d\"", i,
1076 (subst >> (n_bits * n_nvars + i)) & 1);
1078 fputs(".\n", stderr);
1080 fprintf(stderr, "Converted to classifier:\n");
1081 expr_matches_print(&matches, stderr);
1083 "However, %s flow was found in the classifier.\n",
1084 found ? "a" : "no");
1089 if (operation >= OP_FLOW) {
1090 struct test_rule *test_rule;
1092 CLS_FOR_EACH (test_rule, cr, &cls) {
1093 classifier_remove(&cls, &test_rule->cr);
1094 ovsrcu_postpone(free_rule, test_rule);
1096 classifier_destroy(&cls);
1099 expr_matches_destroy(&matches);
1101 expr_destroy(modified);
1107 wait_pid(pid_t *pids, int *n)
1112 pid = waitpid(WAIT_ANY, &status, 0);
1114 ovs_fatal(errno, "waitpid failed");
1115 } else if (WIFEXITED(status)) {
1116 if (WEXITSTATUS(status)) {
1117 exit(WEXITSTATUS(status));
1119 } else if (WIFSIGNALED(status)) {
1120 raise(WTERMSIG(status));
1126 for (int i = 0; i < *n; i++) {
1127 if (pids[i] == pid) {
1128 pids[i] = pids[--*n];
1132 ovs_fatal(0, "waitpid returned unknown child");
1137 test_exhaustive(struct ovs_cmdl_context *ctx OVS_UNUSED)
1139 int n_terminals = atoi(ctx->argv[1]);
1140 struct tree_shape ts[50];
1143 struct shash symtab;
1144 const struct expr_symbol *nvars[4];
1145 const struct expr_symbol *svars[4];
1147 ovs_assert(test_nvars <= ARRAY_SIZE(nvars));
1148 ovs_assert(test_svars <= ARRAY_SIZE(svars));
1149 ovs_assert(test_nvars + test_svars <= FLOW_N_REGS);
1151 shash_init(&symtab);
1152 for (int i = 0; i < test_nvars; i++) {
1153 char *name = xasprintf("n%d", i);
1154 nvars[i] = expr_symtab_add_field(&symtab, name, MFF_REG0 + i, NULL,
1158 for (int i = 0; i < test_svars; i++) {
1159 char *name = xasprintf("s%d", i);
1160 svars[i] = expr_symtab_add_string(&symtab, name,
1161 MFF_REG0 + test_nvars + i, NULL);
1166 pid_t *children = xmalloc(test_parallel * sizeof *children);
1171 for (int i = 0; i < 2; i++) {
1172 enum expr_type base_type = i ? EXPR_T_OR : EXPR_T_AND;
1174 for (n_tses = init_tree_shape(ts, n_terminals); n_tses;
1175 n_tses = next_tree_shape(ts, n_tses)) {
1176 const struct tree_shape *tsp = ts;
1177 struct expr *terminals[50];
1178 struct expr **terminalp = terminals;
1179 struct expr *expr = build_tree_shape(base_type, &tsp, &terminalp);
1180 ovs_assert(terminalp == &terminals[n_terminals]);
1182 if (verbosity > 0) {
1183 print_tree_shape(ts, n_tses);
1185 struct ds s = DS_EMPTY_INITIALIZER;
1186 expr_format(expr, &s);
1192 if (test_parallel > 1) {
1193 pid_t pid = xfork();
1195 test_tree_shape_exhaustively(expr, &symtab,
1196 terminals, n_terminals,
1197 nvars, test_nvars, test_bits,
1202 if (n_children >= test_parallel) {
1203 wait_pid(children, &n_children);
1205 children[n_children++] = pid;
1210 n_tested += test_tree_shape_exhaustively(
1211 expr, &symtab, terminals, n_terminals,
1212 nvars, test_nvars, test_bits,
1219 while (n_children > 0) {
1220 wait_pid(children, &n_children);
1226 switch (operation) {
1228 printf("converting");
1231 printf("simplifying");
1234 printf("normalizing");
1237 printf("converting to flows");
1241 printf(" %d expressions of %d terminals", n_tested, n_terminals);
1243 printf(" all %d-terminal expressions", n_terminals);
1245 if (test_nvars || test_svars) {
1248 printf(" %d numeric vars (each %d bits) in terms of operators",
1249 test_nvars, test_bits);
1250 for (unsigned int relops = test_relops; relops;
1251 relops = zero_rightmost_1bit(relops)) {
1252 enum expr_relop r = rightmost_1bit_idx(relops);
1253 printf(" %s", expr_relop_to_string(r));
1256 if (test_nvars && test_svars) {
1260 printf(" %d string vars", test_svars);
1263 printf(" in terms of Boolean constants only");
1267 expr_symtab_destroy(&symtab);
1268 shash_destroy(&symtab);
1274 test_parse_actions(struct ovs_cmdl_context *ctx OVS_UNUSED)
1276 struct shash symtab;
1277 struct hmap dhcp_opts;
1278 struct simap ports, ct_zones;
1281 create_symtab(&symtab);
1282 create_dhcp_opts(&dhcp_opts);
1284 /* Initialize group ids. */
1285 struct group_table group_table;
1286 group_table.group_ids = bitmap_allocate(MAX_OVN_GROUPS);
1287 bitmap_set1(group_table.group_ids, 0); /* Group id 0 is invalid. */
1288 hmap_init(&group_table.desired_groups);
1289 hmap_init(&group_table.existing_groups);
1292 simap_put(&ports, "eth0", 5);
1293 simap_put(&ports, "eth1", 6);
1294 simap_put(&ports, "LOCAL", ofp_to_u16(OFPP_LOCAL));
1295 simap_init(&ct_zones);
1298 while (!ds_get_test_line(&input, stdin)) {
1299 struct ofpbuf ofpacts;
1300 struct expr *prereqs;
1303 ofpbuf_init(&ofpacts, 0);
1305 struct action_params ap = {
1307 .dhcp_opts = &dhcp_opts,
1308 .lookup_port = lookup_port_cb,
1310 .ct_zones = &ct_zones,
1311 .group_table = &group_table,
1316 .output_ptable = 64,
1319 error = actions_parse_string(ds_cstr(&input), &ap, &ofpacts, &prereqs);
1324 ds_put_cstr(&output, "actions=");
1325 ofpacts_format(ofpacts.data, ofpacts.size, &output);
1326 ds_put_cstr(&output, ", prereqs=");
1328 expr_format(prereqs, &output);
1330 ds_put_char(&output, '1');
1332 puts(ds_cstr(&output));
1333 ds_destroy(&output);
1339 expr_destroy(prereqs);
1340 ofpbuf_uninit(&ofpacts);
1344 simap_destroy(&ports);
1345 simap_destroy(&ct_zones);
1346 expr_symtab_destroy(&symtab);
1347 shash_destroy(&symtab);
1351 parse_relops(const char *s)
1353 unsigned int relops = 0;
1356 lexer_init(&lexer, s);
1359 enum expr_relop relop;
1361 if (expr_relop_from_token(lexer.token.type, &relop)) {
1362 relops |= 1u << relop;
1365 ovs_fatal(0, "%s: relational operator expected at `%.*s'",
1366 s, (int) (lexer.input - lexer.start), lexer.start);
1368 lexer_match(&lexer, LEX_T_COMMA);
1369 } while (lexer.token.type != LEX_T_END);
1370 lexer_destroy(&lexer);
1379 %s: OVN test utility\n\
1380 usage: test-ovn %s [OPTIONS] COMMAND [ARG...]\n\
1383 Lexically analyzes OVN input from stdin and print them back on stdout.\n\
1390 Parses OVN expressions from stdin and print them back on stdout after\n\
1391 differing degrees of analysis. Available fields are based on packet\n\
1394 evaluate-expr A B C\n\
1395 Parses OVN expressions from stdin, evaluate them with assigned values,\n\
1396 and print the results on stdout. Available fields are 'a', 'b', and 'c'\n\
1397 of 3 bits each. A, B, and C should be in the range 0 to 7.\n\
1400 Prints all the compositions of N on stdout.\n\
1403 Prints all the tree shapes with N terminals on stdout.\n\
1406 Tests that all possible Boolean expressions with N terminals are properly\n\
1407 simplified, normalized, and converted to flows. Available options:\n\
1409 --operation=OPERATION Operation to test, one of: convert, simplify,\n\
1410 normalize, flow. Default: flow. 'normalize' includes 'simplify',\n\
1411 'flow' includes 'simplify' and 'normalize'.\n\
1412 --parallel=N Number of processes to use in parallel, default 1.\n\
1414 --nvars=N Number of numeric vars to test, in range 0...4, default 2.\n\
1415 --bits=N Number of bits per variable, in range 1...3, default 3.\n\
1416 --relops=OPERATORS Test only the specified Boolean operators.\n\
1417 OPERATORS may include == != < <= > >=, space or\n\
1418 comma separated. Default is all operators.\n\
1420 --svars=N Number of string vars to test, in range 0...4, default 2.\n\
1423 Parses OVN actions from stdin and prints the equivalent OpenFlow actions\n\
1426 program_name, program_name);
1431 test_ovn_main(int argc, char *argv[])
1434 OPT_RELOPS = UCHAR_MAX + 1,
1441 static const struct option long_options[] = {
1442 {"relops", required_argument, NULL, OPT_RELOPS},
1443 {"nvars", required_argument, NULL, OPT_NVARS},
1444 {"svars", required_argument, NULL, OPT_SVARS},
1445 {"bits", required_argument, NULL, OPT_BITS},
1446 {"operation", required_argument, NULL, OPT_OPERATION},
1447 {"parallel", required_argument, NULL, OPT_PARALLEL},
1448 {"more", no_argument, NULL, 'm'},
1449 {"help", no_argument, NULL, 'h'},
1452 char *short_options = ovs_cmdl_long_options_to_short_options(long_options);
1454 set_program_name(argv[0]);
1456 test_relops = parse_relops("== != < <= > >=");
1458 int option_index = 0;
1459 int c = getopt_long (argc, argv, short_options, long_options,
1467 test_relops = parse_relops(optarg);
1471 test_nvars = atoi(optarg);
1472 if (test_nvars < 0 || test_nvars > 4) {
1473 ovs_fatal(0, "number of numeric variables must be "
1479 test_svars = atoi(optarg);
1480 if (test_svars < 0 || test_svars > 4) {
1481 ovs_fatal(0, "number of string variables must be "
1487 test_bits = atoi(optarg);
1488 if (test_bits < 1 || test_bits > 3) {
1489 ovs_fatal(0, "number of bits must be between 1 and 3");
1494 if (!strcmp(optarg, "convert")) {
1495 operation = OP_CONVERT;
1496 } else if (!strcmp(optarg, "simplify")) {
1497 operation = OP_SIMPLIFY;
1498 } else if (!strcmp(optarg, "normalize")) {
1499 operation = OP_NORMALIZE;
1500 } else if (!strcmp(optarg, "flow")) {
1501 operation = OP_FLOW;
1503 ovs_fatal(0, "%s: unknown operation", optarg);
1508 test_parallel = atoi(optarg);
1525 free(short_options);
1527 static const struct ovs_cmdl_command commands[] = {
1529 {"lex", NULL, 0, 0, test_lex},
1532 {"parse-expr", NULL, 0, 0, test_parse_expr},
1533 {"annotate-expr", NULL, 0, 0, test_annotate_expr},
1534 {"simplify-expr", NULL, 0, 0, test_simplify_expr},
1535 {"normalize-expr", NULL, 0, 0, test_normalize_expr},
1536 {"expr-to-flows", NULL, 0, 0, test_expr_to_flows},
1537 {"evaluate-expr", NULL, 1, 1, test_evaluate_expr},
1538 {"composition", NULL, 1, 1, test_composition},
1539 {"tree-shape", NULL, 1, 1, test_tree_shape},
1540 {"exhaustive", NULL, 1, 1, test_exhaustive},
1543 {"parse-actions", NULL, 0, 0, test_parse_actions},
1545 {NULL, NULL, 0, 0, NULL},
1547 struct ovs_cmdl_context ctx;
1548 ctx.argc = argc - optind;
1549 ctx.argv = argv + optind;
1550 ovs_cmdl_run_command(&ctx, commands);
1553 OVSTEST_REGISTER("test-ovn", test_ovn_main);