2 * Copyright (c) 2015, 2016, 2017 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.
22 #include "command-line.h"
23 #include "dp-packet.h"
24 #include "fatal-signal.h"
26 #include "openvswitch/dynamic-string.h"
27 #include "openvswitch/match.h"
28 #include "openvswitch/ofp-actions.h"
29 #include "openvswitch/ofpbuf.h"
30 #include "openvswitch/vlog.h"
31 #include "ovn/actions.h"
34 #include "ovn/lib/logical-fields.h"
35 #include "ovn/lib/ovn-l7.h"
36 #include "ovn/lib/extend-table.h"
37 #include "ovs-thread.h"
39 #include "openvswitch/shash.h"
43 /* --relops: Bitmap of the relational operators to test, in exhaustive test. */
44 static unsigned int test_relops
;
46 /* --nvars: Number of numeric variables to test, in exhaustive test. */
47 static int test_nvars
= 2;
49 /* --svars: Number of string variables to test, in exhaustive test. */
50 static int test_svars
= 2;
52 /* --bits: Number of bits per variable, in exhaustive test. */
53 static int test_bits
= 3;
55 /* --operation: The operation to test, in exhaustive test. */
56 static enum { OP_CONVERT
, OP_SIMPLIFY
, OP_NORMALIZE
, OP_FLOW
} operation
59 /* --parallel: Number of parallel processes to use in test. */
60 static int test_parallel
= 1;
62 /* -m, --more: Message verbosity */
66 compare_token(const struct lex_token
*a
, const struct lex_token
*b
)
68 if (a
->type
!= b
->type
) {
69 fprintf(stderr
, "type differs: %d -> %d\n", a
->type
, b
->type
);
73 if (!((a
->s
&& b
->s
&& !strcmp(a
->s
, b
->s
))
74 || (!a
->s
&& !b
->s
))) {
75 fprintf(stderr
, "string differs: %s -> %s\n",
76 a
->s
? a
->s
: "(null)",
77 b
->s
? b
->s
: "(null)");
81 if (a
->type
== LEX_T_INTEGER
|| a
->type
== LEX_T_MASKED_INTEGER
) {
82 if (memcmp(&a
->value
, &b
->value
, sizeof a
->value
)) {
83 fprintf(stderr
, "value differs\n");
87 if (a
->type
== LEX_T_MASKED_INTEGER
88 && memcmp(&a
->mask
, &b
->mask
, sizeof a
->mask
)) {
89 fprintf(stderr
, "mask differs\n");
93 if (a
->format
!= b
->format
94 && !(a
->format
== LEX_F_HEXADECIMAL
95 && b
->format
== LEX_F_DECIMAL
96 && a
->value
.integer
== 0)) {
97 fprintf(stderr
, "format differs: %d -> %d\n",
98 a
->format
, b
->format
);
104 test_lex(struct ovs_cmdl_context
*ctx OVS_UNUSED
)
111 while (!ds_get_test_line(&input
, stdin
)) {
114 lexer_init(&lexer
, ds_cstr(&input
));
116 while (lexer_get(&lexer
) != LEX_T_END
) {
117 size_t len
= output
.length
;
118 lex_token_format(&lexer
.token
, &output
);
120 /* Check that the formatted version can really be parsed back
122 if (lexer
.token
.type
!= LEX_T_ERROR
) {
123 const char *s
= ds_cstr(&output
) + len
;
128 compare_token(&lexer
.token
, &l2
.token
);
131 ds_put_char(&output
, ' ');
133 lexer_destroy(&lexer
);
135 ds_chomp(&output
, ' ');
136 puts(ds_cstr(&output
));
143 create_symtab(struct shash
*symtab
)
145 ovn_init_symtab(symtab
);
147 /* For negative testing. */
148 expr_symtab_add_field(symtab
, "bad_prereq", MFF_XREG0
, "xyzzy", false);
149 expr_symtab_add_field(symtab
, "self_recurse", MFF_XREG0
,
150 "self_recurse != 0", false);
151 expr_symtab_add_field(symtab
, "mutual_recurse_1", MFF_XREG0
,
152 "mutual_recurse_2 != 0", false);
153 expr_symtab_add_field(symtab
, "mutual_recurse_2", MFF_XREG0
,
154 "mutual_recurse_1 != 0", false);
155 expr_symtab_add_string(symtab
, "big_string", MFF_XREG0
, NULL
);
159 create_gen_opts(struct hmap
*dhcp_opts
, struct hmap
*dhcpv6_opts
,
160 struct hmap
*nd_ra_opts
)
162 hmap_init(dhcp_opts
);
163 dhcp_opt_add(dhcp_opts
, "offerip", 0, "ipv4");
164 dhcp_opt_add(dhcp_opts
, "netmask", 1, "ipv4");
165 dhcp_opt_add(dhcp_opts
, "router", 3, "ipv4");
166 dhcp_opt_add(dhcp_opts
, "dns_server", 6, "ipv4");
167 dhcp_opt_add(dhcp_opts
, "log_server", 7, "ipv4");
168 dhcp_opt_add(dhcp_opts
, "lpr_server", 9, "ipv4");
169 dhcp_opt_add(dhcp_opts
, "domain", 15, "str");
170 dhcp_opt_add(dhcp_opts
, "swap_server", 16, "ipv4");
171 dhcp_opt_add(dhcp_opts
, "policy_filter", 21, "ipv4");
172 dhcp_opt_add(dhcp_opts
, "router_solicitation", 32, "ipv4");
173 dhcp_opt_add(dhcp_opts
, "nis_server", 41, "ipv4");
174 dhcp_opt_add(dhcp_opts
, "ntp_server", 42, "ipv4");
175 dhcp_opt_add(dhcp_opts
, "server_id", 54, "ipv4");
176 dhcp_opt_add(dhcp_opts
, "tftp_server", 66, "ipv4");
177 dhcp_opt_add(dhcp_opts
, "classless_static_route", 121, "static_routes");
178 dhcp_opt_add(dhcp_opts
, "ip_forward_enable", 19, "bool");
179 dhcp_opt_add(dhcp_opts
, "router_discovery", 31, "bool");
180 dhcp_opt_add(dhcp_opts
, "ethernet_encap", 36, "bool");
181 dhcp_opt_add(dhcp_opts
, "default_ttl", 23, "uint8");
182 dhcp_opt_add(dhcp_opts
, "tcp_ttl", 37, "uint8");
183 dhcp_opt_add(dhcp_opts
, "mtu", 26, "uint16");
184 dhcp_opt_add(dhcp_opts
, "lease_time", 51, "uint32");
186 /* DHCPv6 options. */
187 hmap_init(dhcpv6_opts
);
188 dhcp_opt_add(dhcpv6_opts
, "server_id", 2, "mac");
189 dhcp_opt_add(dhcpv6_opts
, "ia_addr", 5, "ipv6");
190 dhcp_opt_add(dhcpv6_opts
, "dns_server", 23, "ipv6");
191 dhcp_opt_add(dhcpv6_opts
, "domain_search", 24, "str");
193 /* IPv6 ND RA options. */
194 hmap_init(nd_ra_opts
);
195 nd_ra_opts_init(nd_ra_opts
);
199 create_addr_sets(struct shash
*addr_sets
)
201 shash_init(addr_sets
);
203 static const char *const addrs1
[] = {
204 "10.0.0.1", "10.0.0.2", "10.0.0.3",
206 static const char *const addrs2
[] = {
209 static const char *const addrs3
[] = {
210 "00:00:00:00:00:01", "00:00:00:00:00:02", "00:00:00:00:00:03",
212 static const char *const addrs4
[] = { NULL
};
214 expr_addr_sets_add(addr_sets
, "set1", addrs1
, 3);
215 expr_addr_sets_add(addr_sets
, "set2", addrs2
, 3);
216 expr_addr_sets_add(addr_sets
, "set3", addrs3
, 3);
217 expr_addr_sets_add(addr_sets
, "set4", addrs4
, 0);
221 lookup_port_cb(const void *ports_
, const char *port_name
, unsigned int *portp
)
223 const struct simap
*ports
= ports_
;
224 const struct simap_node
*node
= simap_find(ports
, port_name
);
233 is_chassis_resident_cb(const void *ports_
, const char *port_name
)
235 const struct simap
*ports
= ports_
;
236 const struct simap_node
*node
= simap_find(ports
, port_name
);
244 test_parse_expr__(int steps
)
247 struct shash addr_sets
;
251 create_symtab(&symtab
);
252 create_addr_sets(&addr_sets
);
255 simap_put(&ports
, "eth0", 5);
256 simap_put(&ports
, "eth1", 6);
257 simap_put(&ports
, "LOCAL", ofp_to_u16(OFPP_LOCAL
));
260 while (!ds_get_test_line(&input
, stdin
)) {
264 expr
= expr_parse_string(ds_cstr(&input
), &symtab
, &addr_sets
, &error
);
265 if (!error
&& steps
> 0) {
266 expr
= expr_annotate(expr
, &symtab
, &error
);
270 expr
= expr_simplify(expr
, is_chassis_resident_cb
, &ports
);
273 expr
= expr_normalize(expr
);
274 ovs_assert(expr_is_normalized(expr
));
281 expr_to_matches(expr
, lookup_port_cb
, &ports
, &matches
);
282 expr_matches_print(&matches
, stdout
);
283 expr_matches_destroy(&matches
);
285 struct ds output
= DS_EMPTY_INITIALIZER
;
286 expr_format(expr
, &output
);
287 puts(ds_cstr(&output
));
298 simap_destroy(&ports
);
299 expr_symtab_destroy(&symtab
);
300 shash_destroy(&symtab
);
301 expr_addr_sets_destroy(&addr_sets
);
302 shash_destroy(&addr_sets
);
306 test_parse_expr(struct ovs_cmdl_context
*ctx OVS_UNUSED
)
308 test_parse_expr__(0);
312 test_annotate_expr(struct ovs_cmdl_context
*ctx OVS_UNUSED
)
314 test_parse_expr__(1);
318 test_simplify_expr(struct ovs_cmdl_context
*ctx OVS_UNUSED
)
320 test_parse_expr__(2);
324 test_normalize_expr(struct ovs_cmdl_context
*ctx OVS_UNUSED
)
326 test_parse_expr__(3);
330 test_expr_to_flows(struct ovs_cmdl_context
*ctx OVS_UNUSED
)
332 test_parse_expr__(4);
335 /* Print the symbol table. */
338 test_dump_symtab(struct ovs_cmdl_context
*ctx OVS_UNUSED
)
341 create_symtab(&symtab
);
343 const struct shash_node
**nodes
= shash_sort(&symtab
);
344 for (size_t i
= 0; i
< shash_count(&symtab
); i
++) {
345 const struct expr_symbol
*symbol
= nodes
[i
]->data
;
346 struct ds s
= DS_EMPTY_INITIALIZER
;
347 expr_symbol_format(symbol
, &s
);
353 expr_symtab_destroy(&symtab
);
354 shash_destroy(&symtab
);
357 /* Evaluate an expression. */
360 lookup_atoi_cb(const void *aux OVS_UNUSED
, const char *port_name
,
363 *portp
= atoi(port_name
);
368 test_evaluate_expr(struct ovs_cmdl_context
*ctx
)
373 ovn_init_symtab(&symtab
);
376 char *error
= expr_parse_microflow(ctx
->argv
[1], &symtab
, NULL
,
377 lookup_atoi_cb
, NULL
, &uflow
);
379 ovs_fatal(0, "%s", error
);
383 while (!ds_get_test_line(&input
, stdin
)) {
386 expr
= expr_parse_string(ds_cstr(&input
), &symtab
, NULL
, &error
);
388 expr
= expr_annotate(expr
, &symtab
, &error
);
391 printf("%d\n", expr_evaluate(expr
, &uflow
, lookup_atoi_cb
, NULL
));
400 expr_symtab_destroy(&symtab
);
401 shash_destroy(&symtab
);
406 * The "compositions" of a positive integer N are all of the ways that one can
407 * add up positive integers to sum to N. For example, the compositions of 3
408 * are 3, 2+1, 1+2, and 1+1+1.
410 * We use compositions to find all the ways to break up N terms of a Boolean
411 * expression into subexpressions. Suppose we want to generate all expressions
412 * with 3 terms. The compositions of 3 (ignoring 3 itself) provide the
413 * possibilities (x && x) || x, x || (x && x), and x || x || x. (Of course one
414 * can exchange && for || in each case.) One must recursively compose the
415 * sub-expressions whose values are 3 or greater; that is what the "tree shape"
416 * concept later covers.
418 * To iterate through all compositions of, e.g., 5:
420 * unsigned int state;
424 * for (n = first_composition(ARRAY_SIZE(s), &state, s); n > 0;
425 * n = next_composition(&state, s, n)) {
426 * // Do something with composition 's' with 'n' elements.
429 * Algorithm from D. E. Knuth, _The Art of Computer Programming, Vol. 4A:
430 * Combinatorial Algorithms, Part 1_, section 7.2.1.1, answer to exercise
434 /* Begins iteration through the compositions of 'n'. Initializes 's' to the
435 * number of elements in the first composition of 'n' and returns that number
436 * of elements. The first composition in fact is always 'n' itself, so the
437 * return value will be 1.
439 * Initializes '*state' to some internal state information. The caller must
440 * maintain this state (and 's') for use by next_composition().
442 * 's' must have room for at least 'n' elements. */
444 first_composition(int n
, unsigned int *state
, int s
[])
451 /* Advances 's', with 'sn' elements, to the next composition and returns the
452 * number of elements in this new composition, or 0 if no compositions are
453 * left. 'state' is the same internal state passed to first_composition(). */
455 next_composition(unsigned int *state
, int s
[], int sn
)
486 test_composition(struct ovs_cmdl_context
*ctx
)
488 int n
= atoi(ctx
->argv
[1]);
492 for (int sn
= first_composition(n
, &state
, s
); sn
;
493 sn
= next_composition(&state
, s
, sn
)) {
494 for (int i
= 0; i
< sn
; i
++) {
495 printf("%d%c", s
[i
], i
== sn
- 1 ? '\n' : ' ');
502 * This code generates all possible Boolean expressions with a specified number
503 * of terms N (equivalent to the number of external nodes in a tree).
505 * See test_tree_shape() for a simple example. */
507 /* An array of these structures describes the shape of a tree.
509 * A single element of struct tree_shape describes a single node in the tree.
510 * The node has 'sn' direct children. From left to right, for i in 0...sn-1,
511 * s[i] is 1 if the child is a leaf node, otherwise the child is a subtree and
512 * s[i] is the number of leaf nodes within that subtree. In the latter case,
513 * the subtree is described by another struct tree_shape within the enclosing
514 * array. The tree_shapes are ordered in the array in in-order.
523 init_tree_shape__(struct tree_shape ts
[], int n
)
530 /* Skip the first composition intentionally. */
531 ts
->sn
= first_composition(n
, &ts
->state
, ts
->s
);
532 ts
->sn
= next_composition(&ts
->state
, ts
->s
, ts
->sn
);
533 for (int i
= 0; i
< ts
->sn
; i
++) {
534 n_tses
+= init_tree_shape__(&ts
[n_tses
], ts
->s
[i
]);
539 /* Initializes 'ts[]' as the first in the set of all of possible shapes of
540 * trees with 'n' leaves. Returns the number of "struct tree_shape"s in the
541 * first tree shape. */
543 init_tree_shape(struct tree_shape ts
[], int n
)
556 return init_tree_shape__(ts
, n
);
560 /* Advances 'ts', which currently has 'n_tses' elements, to the next possible
561 * tree shape with the number of leaves passed to init_tree_shape(). Returns
562 * the number of "struct tree_shape"s in the next shape, or 0 if all tree
563 * shapes have been visited. */
565 next_tree_shape(struct tree_shape ts
[], int n_tses
)
567 if (n_tses
== 1 && ts
->sn
== 2 && ts
->s
[0] == 1 && ts
->s
[1] == 1) {
571 struct tree_shape
*p
= &ts
[n_tses
- 1];
572 p
->sn
= p
->sn
> 1 ? next_composition(&p
->state
, p
->s
, p
->sn
) : 0;
574 for (int i
= 0; i
< p
->sn
; i
++) {
575 n_tses
+= init_tree_shape__(&ts
[n_tses
], p
->s
[i
]);
585 print_tree_shape(const struct tree_shape ts
[], int n_tses
)
587 for (int i
= 0; i
< n_tses
; i
++) {
591 for (int j
= 0; j
< ts
[i
].sn
; j
++) {
603 test_tree_shape(struct ovs_cmdl_context
*ctx
)
605 int n
= atoi(ctx
->argv
[1]);
606 struct tree_shape ts
[50];
609 for (n_tses
= init_tree_shape(ts
, n
); n_tses
;
610 n_tses
= next_tree_shape(ts
, n_tses
)) {
611 print_tree_shape(ts
, n_tses
);
616 /* Iteration through all possible terminal expressions (e.g. EXPR_T_CMP and
617 * EXPR_T_BOOLEAN expressions).
619 * Given a tree shape, this allows the code to try all possible ways to plug in
624 * struct expr terminal;
625 * const struct expr_symbol *vars = ...;
629 * init_terminal(&terminal, vars[0]);
631 * // Something with 'terminal'.
632 * } while (next_terminal(&terminal, vars, n_vars, n_bits));
635 /* Sets 'expr' to the first possible terminal expression. 'var' should be the
636 * first variable in the ones to be tested. */
638 init_terminal(struct expr
*expr
, int phase
,
639 const struct expr_symbol
*nvars
[], int n_nvars
,
640 const struct expr_symbol
*svars
[], int n_svars
)
642 if (phase
< 1 && n_nvars
) {
643 expr
->type
= EXPR_T_CMP
;
644 expr
->cmp
.symbol
= nvars
[0];
645 expr
->cmp
.relop
= rightmost_1bit_idx(test_relops
);
646 memset(&expr
->cmp
.value
, 0, sizeof expr
->cmp
.value
);
647 memset(&expr
->cmp
.mask
, 0, sizeof expr
->cmp
.mask
);
648 expr
->cmp
.value
.integer
= htonll(0);
649 expr
->cmp
.mask
.integer
= htonll(0);
653 if (phase
< 2 && n_svars
) {
654 expr
->type
= EXPR_T_CMP
;
655 expr
->cmp
.symbol
= svars
[0];
656 expr
->cmp
.relop
= EXPR_R_EQ
;
657 expr
->cmp
.string
= xstrdup("0");
661 expr
->type
= EXPR_T_BOOLEAN
;
662 expr
->boolean
= false;
665 /* Returns 'x' with the rightmost contiguous string of 1s changed to 0s,
666 * e.g. 01011100 => 01000000. See H. S. Warren, Jr., _Hacker's Delight_, 2nd
667 * ed., section 2-1. */
669 turn_off_rightmost_1s(unsigned int x
)
671 return ((x
& -x
) + x
) & x
;
674 static const struct expr_symbol
*
675 next_var(const struct expr_symbol
*symbol
,
676 const struct expr_symbol
*vars
[], int n_vars
)
678 for (int i
= 0; i
< n_vars
; i
++) {
679 if (symbol
== vars
[i
]) {
680 return i
+ 1 >= n_vars
? NULL
: vars
[i
+ 1];
686 static enum expr_relop
687 next_relop(enum expr_relop relop
)
689 unsigned int remaining_relops
= test_relops
& ~((1u << (relop
+ 1)) - 1);
690 return (remaining_relops
691 ? rightmost_1bit_idx(remaining_relops
)
692 : rightmost_1bit_idx(test_relops
));
695 /* Advances 'expr' to the next possible terminal expression within the 'n_vars'
696 * variables of 'n_bits' bits each in 'vars[]'. */
698 next_terminal(struct expr
*expr
,
699 const struct expr_symbol
*nvars
[], int n_nvars
, int n_bits
,
700 const struct expr_symbol
*svars
[], int n_svars
)
702 if (expr
->type
== EXPR_T_BOOLEAN
) {
706 expr
->boolean
= true;
711 if (!expr
->cmp
.symbol
->width
) {
712 int next_value
= atoi(expr
->cmp
.string
) + 1;
713 free(expr
->cmp
.string
);
714 if (next_value
> 1) {
715 expr
->cmp
.symbol
= next_var(expr
->cmp
.symbol
, svars
, n_svars
);
716 if (!expr
->cmp
.symbol
) {
717 init_terminal(expr
, 2, nvars
, n_nvars
, svars
, n_svars
);
722 expr
->cmp
.string
= xasprintf("%d", next_value
);
728 next
= (ntohll(expr
->cmp
.value
.integer
)
729 + (ntohll(expr
->cmp
.mask
.integer
) << n_bits
));
732 unsigned m
= next
>> n_bits
;
733 unsigned v
= next
& ((1u << n_bits
) - 1);
734 if (next
>= (1u << (2 * n_bits
))) {
735 enum expr_relop old_relop
= expr
->cmp
.relop
;
736 expr
->cmp
.relop
= next_relop(old_relop
);
737 if (expr
->cmp
.relop
<= old_relop
) {
738 expr
->cmp
.symbol
= next_var(expr
->cmp
.symbol
, nvars
, n_nvars
);
739 if (!expr
->cmp
.symbol
) {
740 init_terminal(expr
, 1, nvars
, n_nvars
, svars
, n_svars
);
746 /* Skip: 1-bits in value correspond to 0-bits in mask. */
747 } else if ((!m
|| turn_off_rightmost_1s(m
))
748 && (expr
->cmp
.relop
!= EXPR_R_EQ
&&
749 expr
->cmp
.relop
!= EXPR_R_NE
)) {
750 /* Skip: can't have discontiguous or all-0 mask for > >= < <=. */
752 expr
->cmp
.value
.integer
= htonll(v
);
753 expr
->cmp
.mask
.integer
= htonll(m
);
760 make_terminal(struct expr
***terminalp
)
762 struct expr
*e
= expr_create_boolean(true);
769 build_simple_tree(enum expr_type type
, int n
, struct expr
***terminalp
)
772 struct expr
*e
= expr_create_andor(type
);
773 for (int i
= 0; i
< 2; i
++) {
774 struct expr
*sub
= make_terminal(terminalp
);
775 ovs_list_push_back(&e
->andor
, &sub
->node
);
779 return make_terminal(terminalp
);
786 build_tree_shape(enum expr_type type
, const struct tree_shape
**tsp
,
787 struct expr
***terminalp
)
789 const struct tree_shape
*ts
= *tsp
;
792 struct expr
*e
= expr_create_andor(type
);
793 enum expr_type t
= type
== EXPR_T_AND
? EXPR_T_OR
: EXPR_T_AND
;
794 for (int i
= 0; i
< ts
->sn
; i
++) {
795 struct expr
*sub
= (ts
->s
[i
] > 2
796 ? build_tree_shape(t
, tsp
, terminalp
)
797 : build_simple_tree(t
, ts
->s
[i
], terminalp
));
798 ovs_list_push_back(&e
->andor
, &sub
->node
);
808 free_rule(struct test_rule
*test_rule
)
810 cls_rule_destroy(&test_rule
->cr
);
815 tree_shape_is_chassis_resident_cb(const void *c_aux OVS_UNUSED
,
816 const char *port_name OVS_UNUSED
)
822 test_tree_shape_exhaustively(struct expr
*expr
, struct shash
*symtab
,
823 struct expr
*terminals
[], int n_terminals
,
824 const struct expr_symbol
*nvars
[], int n_nvars
,
826 const struct expr_symbol
*svars
[], int n_svars
)
830 const unsigned int var_mask
= (1u << n_bits
) - 1;
831 for (int i
= 0; i
< n_terminals
; i
++) {
832 init_terminal(terminals
[i
], 0, nvars
, n_nvars
, svars
, n_svars
);
835 struct ds s
= DS_EMPTY_INITIALIZER
;
837 memset(&f
, 0, sizeof f
);
839 for (int i
= n_terminals
- 1; ; i
--) {
844 if (next_terminal(terminals
[i
], nvars
, n_nvars
, n_bits
,
848 init_terminal(terminals
[i
], 0, nvars
, n_nvars
, svars
, n_svars
);
850 ovs_assert(expr_honors_invariants(expr
));
854 struct expr
*modified
;
855 if (operation
== OP_CONVERT
) {
857 expr_format(expr
, &s
);
860 modified
= expr_parse_string(ds_cstr(&s
), symtab
, NULL
, &error
);
862 fprintf(stderr
, "%s fails to parse (%s)\n",
866 } else if (operation
>= OP_SIMPLIFY
) {
867 modified
= expr_simplify(expr_clone(expr
),
868 tree_shape_is_chassis_resident_cb
,
870 ovs_assert(expr_honors_invariants(modified
));
872 if (operation
>= OP_NORMALIZE
) {
873 modified
= expr_normalize(modified
);
874 ovs_assert(expr_honors_invariants(modified
));
875 ovs_assert(expr_is_normalized(modified
));
880 struct classifier cls
;
881 if (operation
>= OP_FLOW
) {
882 struct expr_match
*m
;
883 struct test_rule
*test_rule
;
885 expr_to_matches(modified
, lookup_atoi_cb
, 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
, OVS_VERSION_MIN
,
892 m
->conjunctions
, m
->n
);
895 for (int subst
= 0; subst
< 1 << (n_bits
* n_nvars
+ n_svars
);
897 for (int i
= 0; i
< n_nvars
; i
++) {
898 f
.regs
[i
] = (subst
>> (i
* n_bits
)) & var_mask
;
900 for (int i
= 0; i
< n_svars
; i
++) {
901 f
.regs
[n_nvars
+ i
] = ((subst
>> (n_nvars
* n_bits
+ i
))
905 bool expected
= expr_evaluate(expr
, &f
, lookup_atoi_cb
, NULL
);
906 bool actual
= expr_evaluate(modified
, &f
, lookup_atoi_cb
, NULL
);
907 if (actual
!= expected
) {
908 struct ds expr_s
, modified_s
;
911 expr_format(expr
, &expr_s
);
913 ds_init(&modified_s
);
914 expr_format(modified
, &modified_s
);
917 "%s evaluates to %d, but %s evaluates to %d, for",
918 ds_cstr(&expr_s
), expected
,
919 ds_cstr(&modified_s
), actual
);
920 for (int i
= 0; i
< n_nvars
; i
++) {
924 fprintf(stderr
, " n%d = 0x%x", i
,
925 (subst
>> (n_bits
* i
)) & var_mask
);
927 for (int i
= 0; i
< n_svars
; i
++) {
928 fprintf(stderr
, ", s%d = \"%d\"", i
,
929 (subst
>> (n_bits
* n_nvars
+ i
)) & 1);
935 if (operation
>= OP_FLOW
) {
936 bool found
= classifier_lookup(&cls
, OVS_VERSION_MIN
,
938 if (expected
!= found
) {
939 struct ds expr_s
, modified_s
;
942 expr_format(expr
, &expr_s
);
944 ds_init(&modified_s
);
945 expr_format(modified
, &modified_s
);
948 "%s and %s evaluate to %d, for",
949 ds_cstr(&expr_s
), ds_cstr(&modified_s
), expected
);
950 for (int i
= 0; i
< n_nvars
; i
++) {
954 fprintf(stderr
, " n%d = 0x%x", i
,
955 (subst
>> (n_bits
* i
)) & var_mask
);
957 for (int i
= 0; i
< n_svars
; i
++) {
958 fprintf(stderr
, ", s%d = \"%d\"", i
,
959 (subst
>> (n_bits
* n_nvars
+ i
)) & 1);
961 fputs(".\n", stderr
);
963 fprintf(stderr
, "Converted to classifier:\n");
964 expr_matches_print(&matches
, stderr
);
966 "However, %s flow was found in the classifier.\n",
972 if (operation
>= OP_FLOW
) {
973 struct test_rule
*test_rule
;
975 CLS_FOR_EACH (test_rule
, cr
, &cls
) {
976 classifier_remove_assert(&cls
, &test_rule
->cr
);
977 ovsrcu_postpone(free_rule
, test_rule
);
979 classifier_destroy(&cls
);
982 expr_matches_destroy(&matches
);
984 expr_destroy(modified
);
990 wait_pid(pid_t
*pids
, int *n
)
995 pid
= waitpid(-1, &status
, 0);
997 ovs_fatal(errno
, "waitpid failed");
998 } else if (WIFEXITED(status
)) {
999 if (WEXITSTATUS(status
)) {
1000 exit(WEXITSTATUS(status
));
1002 } else if (WIFSIGNALED(status
)) {
1003 raise(WTERMSIG(status
));
1009 for (int i
= 0; i
< *n
; i
++) {
1010 if (pids
[i
] == pid
) {
1011 pids
[i
] = pids
[--*n
];
1015 ovs_fatal(0, "waitpid returned unknown child");
1020 test_exhaustive(struct ovs_cmdl_context
*ctx OVS_UNUSED
)
1022 int n_terminals
= atoi(ctx
->argv
[1]);
1023 struct tree_shape ts
[50];
1026 struct shash symtab
;
1027 const struct expr_symbol
*nvars
[4];
1028 const struct expr_symbol
*svars
[4];
1030 ovs_assert(test_nvars
<= ARRAY_SIZE(nvars
));
1031 ovs_assert(test_svars
<= ARRAY_SIZE(svars
));
1032 ovs_assert(test_nvars
+ test_svars
<= FLOW_N_REGS
);
1034 shash_init(&symtab
);
1035 for (int i
= 0; i
< test_nvars
; i
++) {
1036 char *name
= xasprintf("n%d", i
);
1037 nvars
[i
] = expr_symtab_add_field(&symtab
, name
, MFF_REG0
+ i
, NULL
,
1041 for (int i
= 0; i
< test_svars
; i
++) {
1042 char *name
= xasprintf("s%d", i
);
1043 svars
[i
] = expr_symtab_add_string(&symtab
, name
,
1044 MFF_REG0
+ test_nvars
+ i
, NULL
);
1049 pid_t
*children
= xmalloc(test_parallel
* sizeof *children
);
1054 for (int i
= 0; i
< 2; i
++) {
1055 enum expr_type base_type
= i
? EXPR_T_OR
: EXPR_T_AND
;
1057 for (n_tses
= init_tree_shape(ts
, n_terminals
); n_tses
;
1058 n_tses
= next_tree_shape(ts
, n_tses
)) {
1059 const struct tree_shape
*tsp
= ts
;
1060 struct expr
*terminals
[50];
1061 struct expr
**terminalp
= terminals
;
1062 struct expr
*expr
= build_tree_shape(base_type
, &tsp
, &terminalp
);
1063 ovs_assert(terminalp
== &terminals
[n_terminals
]);
1065 if (verbosity
> 0) {
1066 print_tree_shape(ts
, n_tses
);
1068 struct ds s
= DS_EMPTY_INITIALIZER
;
1069 expr_format(expr
, &s
);
1075 if (test_parallel
> 1) {
1076 pid_t pid
= xfork();
1078 test_tree_shape_exhaustively(expr
, &symtab
,
1079 terminals
, n_terminals
,
1080 nvars
, test_nvars
, test_bits
,
1085 if (n_children
>= test_parallel
) {
1086 wait_pid(children
, &n_children
);
1088 children
[n_children
++] = pid
;
1093 n_tested
+= test_tree_shape_exhaustively(
1094 expr
, &symtab
, terminals
, n_terminals
,
1095 nvars
, test_nvars
, test_bits
,
1102 while (n_children
> 0) {
1103 wait_pid(children
, &n_children
);
1109 switch (operation
) {
1111 printf("converting");
1114 printf("simplifying");
1117 printf("normalizing");
1120 printf("converting to flows");
1124 printf(" %d expressions of %d terminals", n_tested
, n_terminals
);
1126 printf(" all %d-terminal expressions", n_terminals
);
1128 if (test_nvars
|| test_svars
) {
1131 printf(" %d numeric vars (each %d bits) in terms of operators",
1132 test_nvars
, test_bits
);
1133 for (unsigned int relops
= test_relops
; relops
;
1134 relops
= zero_rightmost_1bit(relops
)) {
1135 enum expr_relop r
= rightmost_1bit_idx(relops
);
1136 printf(" %s", expr_relop_to_string(r
));
1139 if (test_nvars
&& test_svars
) {
1143 printf(" %d string vars", test_svars
);
1146 printf(" in terms of Boolean constants only");
1150 expr_symtab_destroy(&symtab
);
1151 shash_destroy(&symtab
);
1155 test_expr_to_packets(struct ovs_cmdl_context
*ctx OVS_UNUSED
)
1157 struct shash symtab
;
1160 create_symtab(&symtab
);
1163 while (!ds_get_test_line(&input
, stdin
)) {
1165 char *error
= expr_parse_microflow(ds_cstr(&input
), &symtab
, NULL
,
1166 lookup_atoi_cb
, NULL
, &uflow
);
1173 uint64_t packet_stub
[128 / 8];
1174 struct dp_packet packet
;
1175 dp_packet_use_stub(&packet
, packet_stub
, sizeof packet_stub
);
1176 flow_compose(&packet
, &uflow
, NULL
, 64);
1178 struct ds output
= DS_EMPTY_INITIALIZER
;
1179 const uint8_t *buf
= dp_packet_data(&packet
);
1180 for (int i
= 0; i
< dp_packet_size(&packet
); i
++) {
1181 uint8_t val
= buf
[i
];
1182 ds_put_format(&output
, "%02"PRIx8
, val
);
1184 puts(ds_cstr(&output
));
1185 ds_destroy(&output
);
1187 dp_packet_uninit(&packet
);
1191 expr_symtab_destroy(&symtab
);
1192 shash_destroy(&symtab
);
1198 test_parse_actions(struct ovs_cmdl_context
*ctx OVS_UNUSED
)
1200 struct shash symtab
;
1201 struct hmap dhcp_opts
;
1202 struct hmap dhcpv6_opts
;
1203 struct hmap nd_ra_opts
;
1208 create_symtab(&symtab
);
1209 create_gen_opts(&dhcp_opts
, &dhcpv6_opts
, &nd_ra_opts
);
1211 /* Initialize group ids. */
1212 struct ovn_extend_table group_table
;
1213 ovn_extend_table_init(&group_table
);
1215 /* Initialize meter ids for QoS. */
1216 struct ovn_extend_table meter_table
;
1217 ovn_extend_table_init(&meter_table
);
1220 simap_put(&ports
, "eth0", 5);
1221 simap_put(&ports
, "eth1", 6);
1222 simap_put(&ports
, "LOCAL", ofp_to_u16(OFPP_LOCAL
));
1225 while (!ds_get_test_line(&input
, stdin
)) {
1226 struct ofpbuf ovnacts
;
1227 struct expr
*prereqs
;
1230 puts(ds_cstr(&input
));
1232 ofpbuf_init(&ovnacts
, 0);
1234 const struct ovnact_parse_params pp
= {
1236 .dhcp_opts
= &dhcp_opts
,
1237 .dhcpv6_opts
= &dhcpv6_opts
,
1238 .nd_ra_opts
= &nd_ra_opts
,
1242 error
= ovnacts_parse_string(ds_cstr(&input
), &pp
, &ovnacts
, &prereqs
);
1244 /* Convert the parsed representation back to a string and print it,
1245 * if it's different from the input. */
1246 struct ds ovnacts_s
= DS_EMPTY_INITIALIZER
;
1247 ovnacts_format(ovnacts
.data
, ovnacts
.size
, &ovnacts_s
);
1248 if (strcmp(ds_cstr(&input
), ds_cstr(&ovnacts_s
))) {
1249 printf(" formats as %s\n", ds_cstr(&ovnacts_s
));
1252 /* Encode the actions into OpenFlow and print. */
1253 const struct ovnact_encode_params ep
= {
1254 .lookup_port
= lookup_port_cb
,
1257 .group_table
= &group_table
,
1258 .meter_table
= &meter_table
,
1260 .pipeline
= OVNACT_P_INGRESS
,
1261 .ingress_ptable
= 8,
1262 .egress_ptable
= 40,
1263 .output_ptable
= 64,
1264 .mac_bind_ptable
= 65,
1266 struct ofpbuf ofpacts
;
1267 ofpbuf_init(&ofpacts
, 0);
1268 ovnacts_encode(ovnacts
.data
, ovnacts
.size
, &ep
, &ofpacts
);
1269 struct ds ofpacts_s
= DS_EMPTY_INITIALIZER
;
1270 struct ofpact_format_params fp
= { .s
= &ofpacts_s
};
1271 ofpacts_format(ofpacts
.data
, ofpacts
.size
, &fp
);
1272 printf(" encodes as %s\n", ds_cstr(&ofpacts_s
));
1273 ds_destroy(&ofpacts_s
);
1274 ofpbuf_uninit(&ofpacts
);
1276 /* Print prerequisites if any. */
1278 struct ds prereqs_s
= DS_EMPTY_INITIALIZER
;
1279 expr_format(prereqs
, &prereqs_s
);
1280 printf(" has prereqs %s\n", ds_cstr(&prereqs_s
));
1281 ds_destroy(&prereqs_s
);
1284 /* Now re-parse and re-format the string to verify that it's
1285 * round-trippable. */
1286 struct ofpbuf ovnacts2
;
1287 struct expr
*prereqs2
;
1288 ofpbuf_init(&ovnacts2
, 0);
1289 error
= ovnacts_parse_string(ds_cstr(&ovnacts_s
), &pp
, &ovnacts2
,
1292 struct ds ovnacts2_s
= DS_EMPTY_INITIALIZER
;
1293 ovnacts_format(ovnacts2
.data
, ovnacts2
.size
, &ovnacts2_s
);
1294 if (strcmp(ds_cstr(&ovnacts_s
), ds_cstr(&ovnacts2_s
))) {
1295 printf(" bad reformat: %s\n", ds_cstr(&ovnacts2_s
));
1298 ds_destroy(&ovnacts2_s
);
1300 printf(" reparse error: %s\n", error
);
1304 expr_destroy(prereqs2
);
1306 ovnacts_free(ovnacts2
.data
, ovnacts2
.size
);
1307 ofpbuf_uninit(&ovnacts2
);
1308 ds_destroy(&ovnacts_s
);
1310 printf(" %s\n", error
);
1314 expr_destroy(prereqs
);
1315 ovnacts_free(ovnacts
.data
, ovnacts
.size
);
1316 ofpbuf_uninit(&ovnacts
);
1320 simap_destroy(&ports
);
1321 expr_symtab_destroy(&symtab
);
1322 shash_destroy(&symtab
);
1323 dhcp_opts_destroy(&dhcp_opts
);
1324 dhcp_opts_destroy(&dhcpv6_opts
);
1325 nd_ra_opts_destroy(&nd_ra_opts
);
1326 exit(ok
? EXIT_SUCCESS
: EXIT_FAILURE
);
1330 parse_relops(const char *s
)
1332 unsigned int relops
= 0;
1335 lexer_init(&lexer
, s
);
1338 enum expr_relop relop
;
1340 if (expr_relop_from_token(lexer
.token
.type
, &relop
)) {
1341 relops
|= 1u << relop
;
1344 ovs_fatal(0, "%s: relational operator expected at `%.*s'",
1345 s
, (int) (lexer
.input
- lexer
.start
), lexer
.start
);
1347 lexer_match(&lexer
, LEX_T_COMMA
);
1348 } while (lexer
.token
.type
!= LEX_T_END
);
1349 lexer_destroy(&lexer
);
1358 %s: OVN test utility\n\
1359 usage: test-ovn %s [OPTIONS] COMMAND [ARG...]\n\
1362 Lexically analyzes OVN input from stdin and print them back on stdout.\n\
1369 Parses OVN expressions from stdin and prints them back on stdout after\n\
1370 differing degrees of analysis. Available fields are based on packet\n\
1374 Parses OVN expressions from stdin and prints out matching packets in\n\
1375 hexadecimal on stdout.\n\
1377 evaluate-expr MICROFLOW\n\
1378 Parses OVN expressions from stdin and evaluates them against the flow\n\
1379 specified in MICROFLOW, which must be an expression that constrains\n\
1380 the packet, e.g. \"ip4 && tcp.src == 80\" for a TCP packet with source\n\
1381 port 80, and prints the results on stdout, either 1 for true or 0 for\n\
1382 false. Use quoted integers, e.g. \"123\", for string fields.\n\
1384 Example: for MICROFLOW of \"ip4 && tcp.src == 80\", \"eth.type == 0x800\"\n\
1385 evaluates to true, \"udp\" evaluates to false, and \"udp || tcp\"\n\
1386 evaluates to true.\n\
1389 Prints all the compositions of N on stdout.\n\
1392 Prints all the tree shapes with N terminals on stdout.\n\
1395 Tests that all possible Boolean expressions with N terminals are properly\n\
1396 simplified, normalized, and converted to flows. Available options:\n\
1398 --operation=OPERATION Operation to test, one of: convert, simplify,\n\
1399 normalize, flow. Default: flow. 'normalize' includes 'simplify',\n\
1400 'flow' includes 'simplify' and 'normalize'.\n\
1401 --parallel=N Number of processes to use in parallel, default 1.\n\
1403 --nvars=N Number of numeric vars to test, in range 0...4, default 2.\n\
1404 --bits=N Number of bits per variable, in range 1...3, default 3.\n\
1405 --relops=OPERATORS Test only the specified Boolean operators.\n\
1406 OPERATORS may include == != < <= > >=, space or\n\
1407 comma separated. Default is all operators.\n\
1409 --svars=N Number of string vars to test, in range 0...4, default 2.\n\
1412 Parses OVN actions from stdin and prints the equivalent OpenFlow actions\n\
1415 program_name
, program_name
);
1420 test_ovn_main(int argc
, char *argv
[])
1423 OPT_RELOPS
= UCHAR_MAX
+ 1,
1430 static const struct option long_options
[] = {
1431 {"relops", required_argument
, NULL
, OPT_RELOPS
},
1432 {"nvars", required_argument
, NULL
, OPT_NVARS
},
1433 {"svars", required_argument
, NULL
, OPT_SVARS
},
1434 {"bits", required_argument
, NULL
, OPT_BITS
},
1435 {"operation", required_argument
, NULL
, OPT_OPERATION
},
1436 {"parallel", required_argument
, NULL
, OPT_PARALLEL
},
1437 {"more", no_argument
, NULL
, 'm'},
1438 {"help", no_argument
, NULL
, 'h'},
1441 char *short_options
= ovs_cmdl_long_options_to_short_options(long_options
);
1443 set_program_name(argv
[0]);
1445 test_relops
= parse_relops("== != < <= > >=");
1447 int option_index
= 0;
1448 int c
= getopt_long (argc
, argv
, short_options
, long_options
,
1456 test_relops
= parse_relops(optarg
);
1460 test_nvars
= atoi(optarg
);
1461 if (test_nvars
< 0 || test_nvars
> 4) {
1462 ovs_fatal(0, "number of numeric variables must be "
1468 test_svars
= atoi(optarg
);
1469 if (test_svars
< 0 || test_svars
> 4) {
1470 ovs_fatal(0, "number of string variables must be "
1476 test_bits
= atoi(optarg
);
1477 if (test_bits
< 1 || test_bits
> 3) {
1478 ovs_fatal(0, "number of bits must be between 1 and 3");
1483 if (!strcmp(optarg
, "convert")) {
1484 operation
= OP_CONVERT
;
1485 } else if (!strcmp(optarg
, "simplify")) {
1486 operation
= OP_SIMPLIFY
;
1487 } else if (!strcmp(optarg
, "normalize")) {
1488 operation
= OP_NORMALIZE
;
1489 } else if (!strcmp(optarg
, "flow")) {
1490 operation
= OP_FLOW
;
1492 ovs_fatal(0, "%s: unknown operation", optarg
);
1497 test_parallel
= atoi(optarg
);
1515 free(short_options
);
1517 static const struct ovs_cmdl_command commands
[] = {
1519 {"lex", NULL
, 0, 0, test_lex
, OVS_RO
},
1522 {"dump-symtab", NULL
, 0, 0, test_dump_symtab
, OVS_RO
},
1525 {"parse-expr", NULL
, 0, 0, test_parse_expr
, OVS_RO
},
1526 {"annotate-expr", NULL
, 0, 0, test_annotate_expr
, OVS_RO
},
1527 {"simplify-expr", NULL
, 0, 0, test_simplify_expr
, OVS_RO
},
1528 {"normalize-expr", NULL
, 0, 0, test_normalize_expr
, OVS_RO
},
1529 {"expr-to-flows", NULL
, 0, 0, test_expr_to_flows
, OVS_RO
},
1530 {"evaluate-expr", NULL
, 1, 1, test_evaluate_expr
, OVS_RO
},
1531 {"composition", NULL
, 1, 1, test_composition
, OVS_RO
},
1532 {"tree-shape", NULL
, 1, 1, test_tree_shape
, OVS_RO
},
1533 {"exhaustive", NULL
, 1, 1, test_exhaustive
, OVS_RO
},
1534 {"expr-to-packets", NULL
, 0, 0, test_expr_to_packets
, OVS_RO
},
1537 {"parse-actions", NULL
, 0, 0, test_parse_actions
, OVS_RO
},
1539 {NULL
, NULL
, 0, 0, NULL
, OVS_RO
},
1541 struct ovs_cmdl_context ctx
;
1542 ctx
.argc
= argc
- optind
;
1543 ctx
.argv
= argv
+ optind
;
1544 ovs_cmdl_run_command(&ctx
, commands
);
1547 OVSTEST_REGISTER("test-ovn", test_ovn_main
);