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.
21 #include "command-line.h"
22 #include "dp-packet.h"
23 #include "fatal-signal.h"
25 #include "openvswitch/dynamic-string.h"
26 #include "openvswitch/match.h"
27 #include "openvswitch/ofp-actions.h"
28 #include "openvswitch/ofpbuf.h"
29 #include "openvswitch/vlog.h"
30 #include "ovn/actions.h"
33 #include "ovn/lib/logical-fields.h"
34 #include "ovn/lib/ovn-dhcp.h"
35 #include "ovs-thread.h"
37 #include "openvswitch/shash.h"
41 /* --relops: Bitmap of the relational operators to test, in exhaustive test. */
42 static unsigned int test_relops
;
44 /* --nvars: Number of numeric variables to test, in exhaustive test. */
45 static int test_nvars
= 2;
47 /* --svars: Number of string variables to test, in exhaustive test. */
48 static int test_svars
= 2;
50 /* --bits: Number of bits per variable, in exhaustive test. */
51 static int test_bits
= 3;
53 /* --operation: The operation to test, in exhaustive test. */
54 static enum { OP_CONVERT
, OP_SIMPLIFY
, OP_NORMALIZE
, OP_FLOW
} operation
57 /* --parallel: Number of parallel processes to use in test. */
58 static int test_parallel
= 1;
60 /* -m, --more: Message verbosity */
64 compare_token(const struct lex_token
*a
, const struct lex_token
*b
)
66 if (a
->type
!= b
->type
) {
67 fprintf(stderr
, "type differs: %d -> %d\n", a
->type
, b
->type
);
71 if (!((a
->s
&& b
->s
&& !strcmp(a
->s
, b
->s
))
72 || (!a
->s
&& !b
->s
))) {
73 fprintf(stderr
, "string differs: %s -> %s\n",
74 a
->s
? a
->s
: "(null)",
75 b
->s
? b
->s
: "(null)");
79 if (a
->type
== LEX_T_INTEGER
|| a
->type
== LEX_T_MASKED_INTEGER
) {
80 if (memcmp(&a
->value
, &b
->value
, sizeof a
->value
)) {
81 fprintf(stderr
, "value differs\n");
85 if (a
->type
== LEX_T_MASKED_INTEGER
86 && memcmp(&a
->mask
, &b
->mask
, sizeof a
->mask
)) {
87 fprintf(stderr
, "mask differs\n");
91 if (a
->format
!= b
->format
92 && !(a
->format
== LEX_F_HEXADECIMAL
93 && b
->format
== LEX_F_DECIMAL
94 && a
->value
.integer
== 0)) {
95 fprintf(stderr
, "format differs: %d -> %d\n",
96 a
->format
, b
->format
);
102 test_lex(struct ovs_cmdl_context
*ctx OVS_UNUSED
)
109 while (!ds_get_test_line(&input
, stdin
)) {
112 lexer_init(&lexer
, ds_cstr(&input
));
114 while (lexer_get(&lexer
) != LEX_T_END
) {
115 size_t len
= output
.length
;
116 lex_token_format(&lexer
.token
, &output
);
118 /* Check that the formatted version can really be parsed back
120 if (lexer
.token
.type
!= LEX_T_ERROR
) {
121 const char *s
= ds_cstr(&output
) + len
;
126 compare_token(&lexer
.token
, &l2
.token
);
129 ds_put_char(&output
, ' ');
131 lexer_destroy(&lexer
);
133 ds_chomp(&output
, ' ');
134 puts(ds_cstr(&output
));
141 create_symtab(struct shash
*symtab
)
143 ovn_init_symtab(symtab
);
145 /* For negative testing. */
146 expr_symtab_add_field(symtab
, "bad_prereq", MFF_XREG0
, "xyzzy", false);
147 expr_symtab_add_field(symtab
, "self_recurse", MFF_XREG0
,
148 "self_recurse != 0", false);
149 expr_symtab_add_field(symtab
, "mutual_recurse_1", MFF_XREG0
,
150 "mutual_recurse_2 != 0", false);
151 expr_symtab_add_field(symtab
, "mutual_recurse_2", MFF_XREG0
,
152 "mutual_recurse_1 != 0", false);
153 expr_symtab_add_string(symtab
, "big_string", MFF_XREG0
, NULL
);
157 create_dhcp_opts(struct hmap
*dhcp_opts
, struct hmap
*dhcpv6_opts
)
159 hmap_init(dhcp_opts
);
160 dhcp_opt_add(dhcp_opts
, "offerip", 0, "ipv4");
161 dhcp_opt_add(dhcp_opts
, "netmask", 1, "ipv4");
162 dhcp_opt_add(dhcp_opts
, "router", 3, "ipv4");
163 dhcp_opt_add(dhcp_opts
, "dns_server", 6, "ipv4");
164 dhcp_opt_add(dhcp_opts
, "log_server", 7, "ipv4");
165 dhcp_opt_add(dhcp_opts
, "lpr_server", 9, "ipv4");
166 dhcp_opt_add(dhcp_opts
, "domain", 15, "str");
167 dhcp_opt_add(dhcp_opts
, "swap_server", 16, "ipv4");
168 dhcp_opt_add(dhcp_opts
, "policy_filter", 21, "ipv4");
169 dhcp_opt_add(dhcp_opts
, "router_solicitation", 32, "ipv4");
170 dhcp_opt_add(dhcp_opts
, "nis_server", 41, "ipv4");
171 dhcp_opt_add(dhcp_opts
, "ntp_server", 42, "ipv4");
172 dhcp_opt_add(dhcp_opts
, "server_id", 54, "ipv4");
173 dhcp_opt_add(dhcp_opts
, "tftp_server", 66, "ipv4");
174 dhcp_opt_add(dhcp_opts
, "classless_static_route", 121, "static_routes");
175 dhcp_opt_add(dhcp_opts
, "ip_forward_enable", 19, "bool");
176 dhcp_opt_add(dhcp_opts
, "router_discovery", 31, "bool");
177 dhcp_opt_add(dhcp_opts
, "ethernet_encap", 36, "bool");
178 dhcp_opt_add(dhcp_opts
, "default_ttl", 23, "uint8");
179 dhcp_opt_add(dhcp_opts
, "tcp_ttl", 37, "uint8");
180 dhcp_opt_add(dhcp_opts
, "mtu", 26, "uint16");
181 dhcp_opt_add(dhcp_opts
, "lease_time", 51, "uint32");
183 /* DHCPv6 options. */
184 hmap_init(dhcpv6_opts
);
185 dhcp_opt_add(dhcpv6_opts
, "server_id", 2, "mac");
186 dhcp_opt_add(dhcpv6_opts
, "ia_addr", 5, "ipv6");
187 dhcp_opt_add(dhcpv6_opts
, "dns_server", 23, "ipv6");
188 dhcp_opt_add(dhcpv6_opts
, "domain_search", 24, "str");
192 create_addr_sets(struct shash
*addr_sets
)
194 shash_init(addr_sets
);
196 static const char *const addrs1
[] = {
197 "10.0.0.1", "10.0.0.2", "10.0.0.3",
199 static const char *const addrs2
[] = {
202 static const char *const addrs3
[] = {
203 "00:00:00:00:00:01", "00:00:00:00:00:02", "00:00:00:00:00:03",
206 expr_addr_sets_add(addr_sets
, "set1", addrs1
, 3);
207 expr_addr_sets_add(addr_sets
, "set2", addrs2
, 3);
208 expr_addr_sets_add(addr_sets
, "set3", addrs3
, 3);
212 lookup_port_cb(const void *ports_
, const char *port_name
, unsigned int *portp
)
214 const struct simap
*ports
= ports_
;
215 const struct simap_node
*node
= simap_find(ports
, port_name
);
224 is_chassis_resident_cb(const void *ports_
, const char *port_name
)
226 const struct simap
*ports
= ports_
;
227 const struct simap_node
*node
= simap_find(ports
, port_name
);
235 test_parse_expr__(int steps
)
238 struct shash addr_sets
;
242 create_symtab(&symtab
);
243 create_addr_sets(&addr_sets
);
246 simap_put(&ports
, "eth0", 5);
247 simap_put(&ports
, "eth1", 6);
248 simap_put(&ports
, "LOCAL", ofp_to_u16(OFPP_LOCAL
));
251 while (!ds_get_test_line(&input
, stdin
)) {
255 expr
= expr_parse_string(ds_cstr(&input
), &symtab
, &addr_sets
, &error
);
256 if (!error
&& steps
> 0) {
257 expr
= expr_annotate(expr
, &symtab
, &error
);
261 expr
= expr_simplify(expr
, is_chassis_resident_cb
, &ports
);
264 expr
= expr_normalize(expr
);
265 ovs_assert(expr_is_normalized(expr
));
272 expr_to_matches(expr
, lookup_port_cb
, &ports
, &matches
);
273 expr_matches_print(&matches
, stdout
);
274 expr_matches_destroy(&matches
);
276 struct ds output
= DS_EMPTY_INITIALIZER
;
277 expr_format(expr
, &output
);
278 puts(ds_cstr(&output
));
289 simap_destroy(&ports
);
290 expr_symtab_destroy(&symtab
);
291 shash_destroy(&symtab
);
292 expr_addr_sets_destroy(&addr_sets
);
293 shash_destroy(&addr_sets
);
297 test_parse_expr(struct ovs_cmdl_context
*ctx OVS_UNUSED
)
299 test_parse_expr__(0);
303 test_annotate_expr(struct ovs_cmdl_context
*ctx OVS_UNUSED
)
305 test_parse_expr__(1);
309 test_simplify_expr(struct ovs_cmdl_context
*ctx OVS_UNUSED
)
311 test_parse_expr__(2);
315 test_normalize_expr(struct ovs_cmdl_context
*ctx OVS_UNUSED
)
317 test_parse_expr__(3);
321 test_expr_to_flows(struct ovs_cmdl_context
*ctx OVS_UNUSED
)
323 test_parse_expr__(4);
326 /* Print the symbol table. */
329 test_dump_symtab(struct ovs_cmdl_context
*ctx OVS_UNUSED
)
332 create_symtab(&symtab
);
334 const struct shash_node
**nodes
= shash_sort(&symtab
);
335 for (size_t i
= 0; i
< shash_count(&symtab
); i
++) {
336 const struct expr_symbol
*symbol
= nodes
[i
]->data
;
337 struct ds s
= DS_EMPTY_INITIALIZER
;
338 expr_symbol_format(symbol
, &s
);
344 expr_symtab_destroy(&symtab
);
345 shash_destroy(&symtab
);
348 /* Evaluate an expression. */
351 lookup_atoi_cb(const void *aux OVS_UNUSED
, const char *port_name
,
354 *portp
= atoi(port_name
);
359 test_evaluate_expr(struct ovs_cmdl_context
*ctx
)
364 ovn_init_symtab(&symtab
);
367 char *error
= expr_parse_microflow(ctx
->argv
[1], &symtab
, NULL
,
368 lookup_atoi_cb
, NULL
, &uflow
);
370 ovs_fatal(0, "%s", error
);
374 while (!ds_get_test_line(&input
, stdin
)) {
377 expr
= expr_parse_string(ds_cstr(&input
), &symtab
, NULL
, &error
);
379 expr
= expr_annotate(expr
, &symtab
, &error
);
382 printf("%d\n", expr_evaluate(expr
, &uflow
, lookup_atoi_cb
, NULL
));
391 expr_symtab_destroy(&symtab
);
392 shash_destroy(&symtab
);
397 * The "compositions" of a positive integer N are all of the ways that one can
398 * add up positive integers to sum to N. For example, the compositions of 3
399 * are 3, 2+1, 1+2, and 1+1+1.
401 * We use compositions to find all the ways to break up N terms of a Boolean
402 * expression into subexpressions. Suppose we want to generate all expressions
403 * with 3 terms. The compositions of 3 (ignoring 3 itself) provide the
404 * possibilities (x && x) || x, x || (x && x), and x || x || x. (Of course one
405 * can exchange && for || in each case.) One must recursively compose the
406 * sub-expressions whose values are 3 or greater; that is what the "tree shape"
407 * concept later covers.
409 * To iterate through all compositions of, e.g., 5:
411 * unsigned int state;
415 * for (n = first_composition(ARRAY_SIZE(s), &state, s); n > 0;
416 * n = next_composition(&state, s, n)) {
417 * // Do something with composition 's' with 'n' elements.
420 * Algorithm from D. E. Knuth, _The Art of Computer Programming, Vol. 4A:
421 * Combinatorial Algorithms, Part 1_, section 7.2.1.1, answer to exercise
425 /* Begins iteration through the compositions of 'n'. Initializes 's' to the
426 * number of elements in the first composition of 'n' and returns that number
427 * of elements. The first composition in fact is always 'n' itself, so the
428 * return value will be 1.
430 * Initializes '*state' to some internal state information. The caller must
431 * maintain this state (and 's') for use by next_composition().
433 * 's' must have room for at least 'n' elements. */
435 first_composition(int n
, unsigned int *state
, int s
[])
442 /* Advances 's', with 'sn' elements, to the next composition and returns the
443 * number of elements in this new composition, or 0 if no compositions are
444 * left. 'state' is the same internal state passed to first_composition(). */
446 next_composition(unsigned int *state
, int s
[], int sn
)
477 test_composition(struct ovs_cmdl_context
*ctx
)
479 int n
= atoi(ctx
->argv
[1]);
483 for (int sn
= first_composition(n
, &state
, s
); sn
;
484 sn
= next_composition(&state
, s
, sn
)) {
485 for (int i
= 0; i
< sn
; i
++) {
486 printf("%d%c", s
[i
], i
== sn
- 1 ? '\n' : ' ');
493 * This code generates all possible Boolean expressions with a specified number
494 * of terms N (equivalent to the number of external nodes in a tree).
496 * See test_tree_shape() for a simple example. */
498 /* An array of these structures describes the shape of a tree.
500 * A single element of struct tree_shape describes a single node in the tree.
501 * The node has 'sn' direct children. From left to right, for i in 0...sn-1,
502 * s[i] is 1 if the child is a leaf node, otherwise the child is a subtree and
503 * s[i] is the number of leaf nodes within that subtree. In the latter case,
504 * the subtree is described by another struct tree_shape within the enclosing
505 * array. The tree_shapes are ordered in the array in in-order.
514 init_tree_shape__(struct tree_shape ts
[], int n
)
521 /* Skip the first composition intentionally. */
522 ts
->sn
= first_composition(n
, &ts
->state
, ts
->s
);
523 ts
->sn
= next_composition(&ts
->state
, ts
->s
, ts
->sn
);
524 for (int i
= 0; i
< ts
->sn
; i
++) {
525 n_tses
+= init_tree_shape__(&ts
[n_tses
], ts
->s
[i
]);
530 /* Initializes 'ts[]' as the first in the set of all of possible shapes of
531 * trees with 'n' leaves. Returns the number of "struct tree_shape"s in the
532 * first tree shape. */
534 init_tree_shape(struct tree_shape ts
[], int n
)
547 return init_tree_shape__(ts
, n
);
551 /* Advances 'ts', which currently has 'n_tses' elements, to the next possible
552 * tree shape with the number of leaves passed to init_tree_shape(). Returns
553 * the number of "struct tree_shape"s in the next shape, or 0 if all tree
554 * shapes have been visited. */
556 next_tree_shape(struct tree_shape ts
[], int n_tses
)
558 if (n_tses
== 1 && ts
->sn
== 2 && ts
->s
[0] == 1 && ts
->s
[1] == 1) {
562 struct tree_shape
*p
= &ts
[n_tses
- 1];
563 p
->sn
= p
->sn
> 1 ? next_composition(&p
->state
, p
->s
, p
->sn
) : 0;
565 for (int i
= 0; i
< p
->sn
; i
++) {
566 n_tses
+= init_tree_shape__(&ts
[n_tses
], p
->s
[i
]);
576 print_tree_shape(const struct tree_shape ts
[], int n_tses
)
578 for (int i
= 0; i
< n_tses
; i
++) {
582 for (int j
= 0; j
< ts
[i
].sn
; j
++) {
594 test_tree_shape(struct ovs_cmdl_context
*ctx
)
596 int n
= atoi(ctx
->argv
[1]);
597 struct tree_shape ts
[50];
600 for (n_tses
= init_tree_shape(ts
, n
); n_tses
;
601 n_tses
= next_tree_shape(ts
, n_tses
)) {
602 print_tree_shape(ts
, n_tses
);
607 /* Iteration through all possible terminal expressions (e.g. EXPR_T_CMP and
608 * EXPR_T_BOOLEAN expressions).
610 * Given a tree shape, this allows the code to try all possible ways to plug in
615 * struct expr terminal;
616 * const struct expr_symbol *vars = ...;
620 * init_terminal(&terminal, vars[0]);
622 * // Something with 'terminal'.
623 * } while (next_terminal(&terminal, vars, n_vars, n_bits));
626 /* Sets 'expr' to the first possible terminal expression. 'var' should be the
627 * first variable in the ones to be tested. */
629 init_terminal(struct expr
*expr
, int phase
,
630 const struct expr_symbol
*nvars
[], int n_nvars
,
631 const struct expr_symbol
*svars
[], int n_svars
)
633 if (phase
< 1 && n_nvars
) {
634 expr
->type
= EXPR_T_CMP
;
635 expr
->cmp
.symbol
= nvars
[0];
636 expr
->cmp
.relop
= rightmost_1bit_idx(test_relops
);
637 memset(&expr
->cmp
.value
, 0, sizeof expr
->cmp
.value
);
638 memset(&expr
->cmp
.mask
, 0, sizeof expr
->cmp
.mask
);
639 expr
->cmp
.value
.integer
= htonll(0);
640 expr
->cmp
.mask
.integer
= htonll(0);
644 if (phase
< 2 && n_svars
) {
645 expr
->type
= EXPR_T_CMP
;
646 expr
->cmp
.symbol
= svars
[0];
647 expr
->cmp
.relop
= EXPR_R_EQ
;
648 expr
->cmp
.string
= xstrdup("0");
652 expr
->type
= EXPR_T_BOOLEAN
;
653 expr
->boolean
= false;
656 /* Returns 'x' with the rightmost contiguous string of 1s changed to 0s,
657 * e.g. 01011100 => 01000000. See H. S. Warren, Jr., _Hacker's Delight_, 2nd
658 * ed., section 2-1. */
660 turn_off_rightmost_1s(unsigned int x
)
662 return ((x
& -x
) + x
) & x
;
665 static const struct expr_symbol
*
666 next_var(const struct expr_symbol
*symbol
,
667 const struct expr_symbol
*vars
[], int n_vars
)
669 for (int i
= 0; i
< n_vars
; i
++) {
670 if (symbol
== vars
[i
]) {
671 return i
+ 1 >= n_vars
? NULL
: vars
[i
+ 1];
677 static enum expr_relop
678 next_relop(enum expr_relop relop
)
680 unsigned int remaining_relops
= test_relops
& ~((1u << (relop
+ 1)) - 1);
681 return (remaining_relops
682 ? rightmost_1bit_idx(remaining_relops
)
683 : rightmost_1bit_idx(test_relops
));
686 /* Advances 'expr' to the next possible terminal expression within the 'n_vars'
687 * variables of 'n_bits' bits each in 'vars[]'. */
689 next_terminal(struct expr
*expr
,
690 const struct expr_symbol
*nvars
[], int n_nvars
, int n_bits
,
691 const struct expr_symbol
*svars
[], int n_svars
)
693 if (expr
->type
== EXPR_T_BOOLEAN
) {
697 expr
->boolean
= true;
702 if (!expr
->cmp
.symbol
->width
) {
703 int next_value
= atoi(expr
->cmp
.string
) + 1;
704 free(expr
->cmp
.string
);
705 if (next_value
> 1) {
706 expr
->cmp
.symbol
= next_var(expr
->cmp
.symbol
, svars
, n_svars
);
707 if (!expr
->cmp
.symbol
) {
708 init_terminal(expr
, 2, nvars
, n_nvars
, svars
, n_svars
);
713 expr
->cmp
.string
= xasprintf("%d", next_value
);
719 next
= (ntohll(expr
->cmp
.value
.integer
)
720 + (ntohll(expr
->cmp
.mask
.integer
) << n_bits
));
723 unsigned m
= next
>> n_bits
;
724 unsigned v
= next
& ((1u << n_bits
) - 1);
725 if (next
>= (1u << (2 * n_bits
))) {
726 enum expr_relop old_relop
= expr
->cmp
.relop
;
727 expr
->cmp
.relop
= next_relop(old_relop
);
728 if (expr
->cmp
.relop
<= old_relop
) {
729 expr
->cmp
.symbol
= next_var(expr
->cmp
.symbol
, nvars
, n_nvars
);
730 if (!expr
->cmp
.symbol
) {
731 init_terminal(expr
, 1, nvars
, n_nvars
, svars
, n_svars
);
737 /* Skip: 1-bits in value correspond to 0-bits in mask. */
738 } else if ((!m
|| turn_off_rightmost_1s(m
))
739 && (expr
->cmp
.relop
!= EXPR_R_EQ
&&
740 expr
->cmp
.relop
!= EXPR_R_NE
)) {
741 /* Skip: can't have discontiguous or all-0 mask for > >= < <=. */
743 expr
->cmp
.value
.integer
= htonll(v
);
744 expr
->cmp
.mask
.integer
= htonll(m
);
751 make_terminal(struct expr
***terminalp
)
753 struct expr
*e
= expr_create_boolean(true);
760 build_simple_tree(enum expr_type type
, int n
, struct expr
***terminalp
)
763 struct expr
*e
= expr_create_andor(type
);
764 for (int i
= 0; i
< 2; i
++) {
765 struct expr
*sub
= make_terminal(terminalp
);
766 ovs_list_push_back(&e
->andor
, &sub
->node
);
770 return make_terminal(terminalp
);
777 build_tree_shape(enum expr_type type
, const struct tree_shape
**tsp
,
778 struct expr
***terminalp
)
780 const struct tree_shape
*ts
= *tsp
;
783 struct expr
*e
= expr_create_andor(type
);
784 enum expr_type t
= type
== EXPR_T_AND
? EXPR_T_OR
: EXPR_T_AND
;
785 for (int i
= 0; i
< ts
->sn
; i
++) {
786 struct expr
*sub
= (ts
->s
[i
] > 2
787 ? build_tree_shape(t
, tsp
, terminalp
)
788 : build_simple_tree(t
, ts
->s
[i
], terminalp
));
789 ovs_list_push_back(&e
->andor
, &sub
->node
);
799 free_rule(struct test_rule
*test_rule
)
801 cls_rule_destroy(&test_rule
->cr
);
806 tree_shape_is_chassis_resident_cb(const void *c_aux OVS_UNUSED
,
807 const char *port_name OVS_UNUSED
)
813 test_tree_shape_exhaustively(struct expr
*expr
, struct shash
*symtab
,
814 struct expr
*terminals
[], int n_terminals
,
815 const struct expr_symbol
*nvars
[], int n_nvars
,
817 const struct expr_symbol
*svars
[], int n_svars
)
821 const unsigned int var_mask
= (1u << n_bits
) - 1;
822 for (int i
= 0; i
< n_terminals
; i
++) {
823 init_terminal(terminals
[i
], 0, nvars
, n_nvars
, svars
, n_svars
);
826 struct ds s
= DS_EMPTY_INITIALIZER
;
828 memset(&f
, 0, sizeof f
);
830 for (int i
= n_terminals
- 1; ; i
--) {
835 if (next_terminal(terminals
[i
], nvars
, n_nvars
, n_bits
,
839 init_terminal(terminals
[i
], 0, nvars
, n_nvars
, svars
, n_svars
);
841 ovs_assert(expr_honors_invariants(expr
));
845 struct expr
*modified
;
846 if (operation
== OP_CONVERT
) {
848 expr_format(expr
, &s
);
851 modified
= expr_parse_string(ds_cstr(&s
), symtab
, NULL
, &error
);
853 fprintf(stderr
, "%s fails to parse (%s)\n",
857 } else if (operation
>= OP_SIMPLIFY
) {
858 modified
= expr_simplify(expr_clone(expr
),
859 tree_shape_is_chassis_resident_cb
,
861 ovs_assert(expr_honors_invariants(modified
));
863 if (operation
>= OP_NORMALIZE
) {
864 modified
= expr_normalize(modified
);
865 ovs_assert(expr_is_normalized(modified
));
870 struct classifier cls
;
871 if (operation
>= OP_FLOW
) {
872 struct expr_match
*m
;
873 struct test_rule
*test_rule
;
875 expr_to_matches(modified
, lookup_atoi_cb
, NULL
, &matches
);
877 classifier_init(&cls
, NULL
);
878 HMAP_FOR_EACH (m
, hmap_node
, &matches
) {
879 test_rule
= xmalloc(sizeof *test_rule
);
880 cls_rule_init(&test_rule
->cr
, &m
->match
, 0);
881 classifier_insert(&cls
, &test_rule
->cr
, OVS_VERSION_MIN
,
882 m
->conjunctions
, m
->n
);
885 for (int subst
= 0; subst
< 1 << (n_bits
* n_nvars
+ n_svars
);
887 for (int i
= 0; i
< n_nvars
; i
++) {
888 f
.regs
[i
] = (subst
>> (i
* n_bits
)) & var_mask
;
890 for (int i
= 0; i
< n_svars
; i
++) {
891 f
.regs
[n_nvars
+ i
] = ((subst
>> (n_nvars
* n_bits
+ i
))
895 bool expected
= expr_evaluate(expr
, &f
, lookup_atoi_cb
, NULL
);
896 bool actual
= expr_evaluate(modified
, &f
, lookup_atoi_cb
, NULL
);
897 if (actual
!= expected
) {
898 struct ds expr_s
, modified_s
;
901 expr_format(expr
, &expr_s
);
903 ds_init(&modified_s
);
904 expr_format(modified
, &modified_s
);
907 "%s evaluates to %d, but %s evaluates to %d, for",
908 ds_cstr(&expr_s
), expected
,
909 ds_cstr(&modified_s
), actual
);
910 for (int i
= 0; i
< n_nvars
; i
++) {
914 fprintf(stderr
, " n%d = 0x%x", i
,
915 (subst
>> (n_bits
* i
)) & var_mask
);
917 for (int i
= 0; i
< n_svars
; i
++) {
918 fprintf(stderr
, ", s%d = \"%d\"", i
,
919 (subst
>> (n_bits
* n_nvars
+ i
)) & 1);
925 if (operation
>= OP_FLOW
) {
926 bool found
= classifier_lookup(&cls
, OVS_VERSION_MIN
,
928 if (expected
!= found
) {
929 struct ds expr_s
, modified_s
;
932 expr_format(expr
, &expr_s
);
934 ds_init(&modified_s
);
935 expr_format(modified
, &modified_s
);
938 "%s and %s evaluate to %d, for",
939 ds_cstr(&expr_s
), ds_cstr(&modified_s
), expected
);
940 for (int i
= 0; i
< n_nvars
; i
++) {
944 fprintf(stderr
, " n%d = 0x%x", i
,
945 (subst
>> (n_bits
* i
)) & var_mask
);
947 for (int i
= 0; i
< n_svars
; i
++) {
948 fprintf(stderr
, ", s%d = \"%d\"", i
,
949 (subst
>> (n_bits
* n_nvars
+ i
)) & 1);
951 fputs(".\n", stderr
);
953 fprintf(stderr
, "Converted to classifier:\n");
954 expr_matches_print(&matches
, stderr
);
956 "However, %s flow was found in the classifier.\n",
962 if (operation
>= OP_FLOW
) {
963 struct test_rule
*test_rule
;
965 CLS_FOR_EACH (test_rule
, cr
, &cls
) {
966 classifier_remove(&cls
, &test_rule
->cr
);
967 ovsrcu_postpone(free_rule
, test_rule
);
969 classifier_destroy(&cls
);
972 expr_matches_destroy(&matches
);
974 expr_destroy(modified
);
980 wait_pid(pid_t
*pids
, int *n
)
985 pid
= waitpid(-1, &status
, 0);
987 ovs_fatal(errno
, "waitpid failed");
988 } else if (WIFEXITED(status
)) {
989 if (WEXITSTATUS(status
)) {
990 exit(WEXITSTATUS(status
));
992 } else if (WIFSIGNALED(status
)) {
993 raise(WTERMSIG(status
));
999 for (int i
= 0; i
< *n
; i
++) {
1000 if (pids
[i
] == pid
) {
1001 pids
[i
] = pids
[--*n
];
1005 ovs_fatal(0, "waitpid returned unknown child");
1010 test_exhaustive(struct ovs_cmdl_context
*ctx OVS_UNUSED
)
1012 int n_terminals
= atoi(ctx
->argv
[1]);
1013 struct tree_shape ts
[50];
1016 struct shash symtab
;
1017 const struct expr_symbol
*nvars
[4];
1018 const struct expr_symbol
*svars
[4];
1020 ovs_assert(test_nvars
<= ARRAY_SIZE(nvars
));
1021 ovs_assert(test_svars
<= ARRAY_SIZE(svars
));
1022 ovs_assert(test_nvars
+ test_svars
<= FLOW_N_REGS
);
1024 shash_init(&symtab
);
1025 for (int i
= 0; i
< test_nvars
; i
++) {
1026 char *name
= xasprintf("n%d", i
);
1027 nvars
[i
] = expr_symtab_add_field(&symtab
, name
, MFF_REG0
+ i
, NULL
,
1031 for (int i
= 0; i
< test_svars
; i
++) {
1032 char *name
= xasprintf("s%d", i
);
1033 svars
[i
] = expr_symtab_add_string(&symtab
, name
,
1034 MFF_REG0
+ test_nvars
+ i
, NULL
);
1039 pid_t
*children
= xmalloc(test_parallel
* sizeof *children
);
1044 for (int i
= 0; i
< 2; i
++) {
1045 enum expr_type base_type
= i
? EXPR_T_OR
: EXPR_T_AND
;
1047 for (n_tses
= init_tree_shape(ts
, n_terminals
); n_tses
;
1048 n_tses
= next_tree_shape(ts
, n_tses
)) {
1049 const struct tree_shape
*tsp
= ts
;
1050 struct expr
*terminals
[50];
1051 struct expr
**terminalp
= terminals
;
1052 struct expr
*expr
= build_tree_shape(base_type
, &tsp
, &terminalp
);
1053 ovs_assert(terminalp
== &terminals
[n_terminals
]);
1055 if (verbosity
> 0) {
1056 print_tree_shape(ts
, n_tses
);
1058 struct ds s
= DS_EMPTY_INITIALIZER
;
1059 expr_format(expr
, &s
);
1065 if (test_parallel
> 1) {
1066 pid_t pid
= xfork();
1068 test_tree_shape_exhaustively(expr
, &symtab
,
1069 terminals
, n_terminals
,
1070 nvars
, test_nvars
, test_bits
,
1075 if (n_children
>= test_parallel
) {
1076 wait_pid(children
, &n_children
);
1078 children
[n_children
++] = pid
;
1083 n_tested
+= test_tree_shape_exhaustively(
1084 expr
, &symtab
, terminals
, n_terminals
,
1085 nvars
, test_nvars
, test_bits
,
1092 while (n_children
> 0) {
1093 wait_pid(children
, &n_children
);
1099 switch (operation
) {
1101 printf("converting");
1104 printf("simplifying");
1107 printf("normalizing");
1110 printf("converting to flows");
1114 printf(" %d expressions of %d terminals", n_tested
, n_terminals
);
1116 printf(" all %d-terminal expressions", n_terminals
);
1118 if (test_nvars
|| test_svars
) {
1121 printf(" %d numeric vars (each %d bits) in terms of operators",
1122 test_nvars
, test_bits
);
1123 for (unsigned int relops
= test_relops
; relops
;
1124 relops
= zero_rightmost_1bit(relops
)) {
1125 enum expr_relop r
= rightmost_1bit_idx(relops
);
1126 printf(" %s", expr_relop_to_string(r
));
1129 if (test_nvars
&& test_svars
) {
1133 printf(" %d string vars", test_svars
);
1136 printf(" in terms of Boolean constants only");
1140 expr_symtab_destroy(&symtab
);
1141 shash_destroy(&symtab
);
1145 test_expr_to_packets(struct ovs_cmdl_context
*ctx OVS_UNUSED
)
1147 struct shash symtab
;
1150 create_symtab(&symtab
);
1153 while (!ds_get_test_line(&input
, stdin
)) {
1155 char *error
= expr_parse_microflow(ds_cstr(&input
), &symtab
, NULL
,
1156 lookup_atoi_cb
, NULL
, &uflow
);
1163 uint64_t packet_stub
[128 / 8];
1164 struct dp_packet packet
;
1165 dp_packet_use_stub(&packet
, packet_stub
, sizeof packet_stub
);
1166 flow_compose(&packet
, &uflow
, 0);
1168 struct ds output
= DS_EMPTY_INITIALIZER
;
1169 const uint8_t *buf
= dp_packet_data(&packet
);
1170 for (int i
= 0; i
< dp_packet_size(&packet
); i
++) {
1171 uint8_t val
= buf
[i
];
1172 ds_put_format(&output
, "%02"PRIx8
, val
);
1174 puts(ds_cstr(&output
));
1175 ds_destroy(&output
);
1177 dp_packet_uninit(&packet
);
1181 expr_symtab_destroy(&symtab
);
1182 shash_destroy(&symtab
);
1188 test_parse_actions(struct ovs_cmdl_context
*ctx OVS_UNUSED
)
1190 struct shash symtab
;
1191 struct hmap dhcp_opts
;
1192 struct hmap dhcpv6_opts
;
1197 create_symtab(&symtab
);
1198 create_dhcp_opts(&dhcp_opts
, &dhcpv6_opts
);
1200 /* Initialize group ids. */
1201 struct group_table group_table
;
1202 group_table
.group_ids
= bitmap_allocate(MAX_OVN_GROUPS
);
1203 bitmap_set1(group_table
.group_ids
, 0); /* Group id 0 is invalid. */
1204 hmap_init(&group_table
.desired_groups
);
1205 hmap_init(&group_table
.existing_groups
);
1208 simap_put(&ports
, "eth0", 5);
1209 simap_put(&ports
, "eth1", 6);
1210 simap_put(&ports
, "LOCAL", ofp_to_u16(OFPP_LOCAL
));
1213 while (!ds_get_test_line(&input
, stdin
)) {
1214 struct ofpbuf ovnacts
;
1215 struct expr
*prereqs
;
1218 puts(ds_cstr(&input
));
1220 ofpbuf_init(&ovnacts
, 0);
1222 const struct ovnact_parse_params pp
= {
1224 .dhcp_opts
= &dhcp_opts
,
1225 .dhcpv6_opts
= &dhcpv6_opts
,
1229 error
= ovnacts_parse_string(ds_cstr(&input
), &pp
, &ovnacts
, &prereqs
);
1231 /* Convert the parsed representation back to a string and print it,
1232 * if it's different from the input. */
1233 struct ds ovnacts_s
= DS_EMPTY_INITIALIZER
;
1234 ovnacts_format(ovnacts
.data
, ovnacts
.size
, &ovnacts_s
);
1235 if (strcmp(ds_cstr(&input
), ds_cstr(&ovnacts_s
))) {
1236 printf(" formats as %s\n", ds_cstr(&ovnacts_s
));
1239 /* Encode the actions into OpenFlow and print. */
1240 const struct ovnact_encode_params ep
= {
1241 .lookup_port
= lookup_port_cb
,
1244 .group_table
= &group_table
,
1246 .pipeline
= OVNACT_P_INGRESS
,
1247 .ingress_ptable
= 8,
1248 .egress_ptable
= 40,
1249 .output_ptable
= 64,
1250 .mac_bind_ptable
= 65,
1252 struct ofpbuf ofpacts
;
1253 ofpbuf_init(&ofpacts
, 0);
1254 ovnacts_encode(ovnacts
.data
, ovnacts
.size
, &ep
, &ofpacts
);
1255 struct ds ofpacts_s
= DS_EMPTY_INITIALIZER
;
1256 ofpacts_format(ofpacts
.data
, ofpacts
.size
, NULL
, &ofpacts_s
);
1257 printf(" encodes as %s\n", ds_cstr(&ofpacts_s
));
1258 ds_destroy(&ofpacts_s
);
1259 ofpbuf_uninit(&ofpacts
);
1261 /* Print prerequisites if any. */
1263 struct ds prereqs_s
= DS_EMPTY_INITIALIZER
;
1264 expr_format(prereqs
, &prereqs_s
);
1265 printf(" has prereqs %s\n", ds_cstr(&prereqs_s
));
1266 ds_destroy(&prereqs_s
);
1269 /* Now re-parse and re-format the string to verify that it's
1270 * round-trippable. */
1271 struct ofpbuf ovnacts2
;
1272 struct expr
*prereqs2
;
1273 ofpbuf_init(&ovnacts2
, 0);
1274 error
= ovnacts_parse_string(ds_cstr(&ovnacts_s
), &pp
, &ovnacts2
,
1277 struct ds ovnacts2_s
= DS_EMPTY_INITIALIZER
;
1278 ovnacts_format(ovnacts2
.data
, ovnacts2
.size
, &ovnacts2_s
);
1279 if (strcmp(ds_cstr(&ovnacts_s
), ds_cstr(&ovnacts2_s
))) {
1280 printf(" bad reformat: %s\n", ds_cstr(&ovnacts2_s
));
1283 ds_destroy(&ovnacts2_s
);
1285 printf(" reparse error: %s\n", error
);
1289 expr_destroy(prereqs2
);
1291 ovnacts_free(ovnacts2
.data
, ovnacts2
.size
);
1292 ofpbuf_uninit(&ovnacts2
);
1293 ds_destroy(&ovnacts_s
);
1295 printf(" %s\n", error
);
1299 expr_destroy(prereqs
);
1300 ovnacts_free(ovnacts
.data
, ovnacts
.size
);
1301 ofpbuf_uninit(&ovnacts
);
1305 simap_destroy(&ports
);
1306 expr_symtab_destroy(&symtab
);
1307 shash_destroy(&symtab
);
1308 dhcp_opts_destroy(&dhcp_opts
);
1309 dhcp_opts_destroy(&dhcpv6_opts
);
1311 exit(ok
? EXIT_SUCCESS
: EXIT_FAILURE
);
1315 parse_relops(const char *s
)
1317 unsigned int relops
= 0;
1320 lexer_init(&lexer
, s
);
1323 enum expr_relop relop
;
1325 if (expr_relop_from_token(lexer
.token
.type
, &relop
)) {
1326 relops
|= 1u << relop
;
1329 ovs_fatal(0, "%s: relational operator expected at `%.*s'",
1330 s
, (int) (lexer
.input
- lexer
.start
), lexer
.start
);
1332 lexer_match(&lexer
, LEX_T_COMMA
);
1333 } while (lexer
.token
.type
!= LEX_T_END
);
1334 lexer_destroy(&lexer
);
1343 %s: OVN test utility\n\
1344 usage: test-ovn %s [OPTIONS] COMMAND [ARG...]\n\
1347 Lexically analyzes OVN input from stdin and print them back on stdout.\n\
1354 Parses OVN expressions from stdin and prints them back on stdout after\n\
1355 differing degrees of analysis. Available fields are based on packet\n\
1359 Parses OVN expressions from stdin and prints out matching packets in\n\
1360 hexadecimal on stdout.\n\
1362 evaluate-expr MICROFLOW\n\
1363 Parses OVN expressions from stdin and evaluates them against the flow\n\
1364 specified in MICROFLOW, which must be an expression that constrains\n\
1365 the packet, e.g. \"ip4 && tcp.src == 80\" for a TCP packet with source\n\
1366 port 80, and prints the results on stdout, either 1 for true or 0 for\n\
1367 false. Use quoted integers, e.g. \"123\", for string fields.\n\
1369 Example: for MICROFLOW of \"ip4 && tcp.src == 80\", \"eth.type == 0x800\"\n\
1370 evaluates to true, \"udp\" evaluates to false, and \"udp || tcp\"\n\
1371 evaluates to true.\n\
1374 Prints all the compositions of N on stdout.\n\
1377 Prints all the tree shapes with N terminals on stdout.\n\
1380 Tests that all possible Boolean expressions with N terminals are properly\n\
1381 simplified, normalized, and converted to flows. Available options:\n\
1383 --operation=OPERATION Operation to test, one of: convert, simplify,\n\
1384 normalize, flow. Default: flow. 'normalize' includes 'simplify',\n\
1385 'flow' includes 'simplify' and 'normalize'.\n\
1386 --parallel=N Number of processes to use in parallel, default 1.\n\
1388 --nvars=N Number of numeric vars to test, in range 0...4, default 2.\n\
1389 --bits=N Number of bits per variable, in range 1...3, default 3.\n\
1390 --relops=OPERATORS Test only the specified Boolean operators.\n\
1391 OPERATORS may include == != < <= > >=, space or\n\
1392 comma separated. Default is all operators.\n\
1394 --svars=N Number of string vars to test, in range 0...4, default 2.\n\
1397 Parses OVN actions from stdin and prints the equivalent OpenFlow actions\n\
1400 program_name
, program_name
);
1405 test_ovn_main(int argc
, char *argv
[])
1408 OPT_RELOPS
= UCHAR_MAX
+ 1,
1415 static const struct option long_options
[] = {
1416 {"relops", required_argument
, NULL
, OPT_RELOPS
},
1417 {"nvars", required_argument
, NULL
, OPT_NVARS
},
1418 {"svars", required_argument
, NULL
, OPT_SVARS
},
1419 {"bits", required_argument
, NULL
, OPT_BITS
},
1420 {"operation", required_argument
, NULL
, OPT_OPERATION
},
1421 {"parallel", required_argument
, NULL
, OPT_PARALLEL
},
1422 {"more", no_argument
, NULL
, 'm'},
1423 {"help", no_argument
, NULL
, 'h'},
1426 char *short_options
= ovs_cmdl_long_options_to_short_options(long_options
);
1428 set_program_name(argv
[0]);
1430 test_relops
= parse_relops("== != < <= > >=");
1432 int option_index
= 0;
1433 int c
= getopt_long (argc
, argv
, short_options
, long_options
,
1441 test_relops
= parse_relops(optarg
);
1445 test_nvars
= atoi(optarg
);
1446 if (test_nvars
< 0 || test_nvars
> 4) {
1447 ovs_fatal(0, "number of numeric variables must be "
1453 test_svars
= atoi(optarg
);
1454 if (test_svars
< 0 || test_svars
> 4) {
1455 ovs_fatal(0, "number of string variables must be "
1461 test_bits
= atoi(optarg
);
1462 if (test_bits
< 1 || test_bits
> 3) {
1463 ovs_fatal(0, "number of bits must be between 1 and 3");
1468 if (!strcmp(optarg
, "convert")) {
1469 operation
= OP_CONVERT
;
1470 } else if (!strcmp(optarg
, "simplify")) {
1471 operation
= OP_SIMPLIFY
;
1472 } else if (!strcmp(optarg
, "normalize")) {
1473 operation
= OP_NORMALIZE
;
1474 } else if (!strcmp(optarg
, "flow")) {
1475 operation
= OP_FLOW
;
1477 ovs_fatal(0, "%s: unknown operation", optarg
);
1482 test_parallel
= atoi(optarg
);
1500 free(short_options
);
1502 static const struct ovs_cmdl_command commands
[] = {
1504 {"lex", NULL
, 0, 0, test_lex
, OVS_RO
},
1507 {"dump-symtab", NULL
, 0, 0, test_dump_symtab
, OVS_RO
},
1510 {"parse-expr", NULL
, 0, 0, test_parse_expr
, OVS_RO
},
1511 {"annotate-expr", NULL
, 0, 0, test_annotate_expr
, OVS_RO
},
1512 {"simplify-expr", NULL
, 0, 0, test_simplify_expr
, OVS_RO
},
1513 {"normalize-expr", NULL
, 0, 0, test_normalize_expr
, OVS_RO
},
1514 {"expr-to-flows", NULL
, 0, 0, test_expr_to_flows
, OVS_RO
},
1515 {"evaluate-expr", NULL
, 1, 1, test_evaluate_expr
, OVS_RO
},
1516 {"composition", NULL
, 1, 1, test_composition
, OVS_RO
},
1517 {"tree-shape", NULL
, 1, 1, test_tree_shape
, OVS_RO
},
1518 {"exhaustive", NULL
, 1, 1, test_exhaustive
, OVS_RO
},
1519 {"expr-to-packets", NULL
, 0, 0, test_expr_to_packets
, OVS_RO
},
1522 {"parse-actions", NULL
, 0, 0, test_parse_actions
, OVS_RO
},
1524 {NULL
, NULL
, 0, 0, NULL
, OVS_RO
},
1526 struct ovs_cmdl_context ctx
;
1527 ctx
.argc
= argc
- optind
;
1528 ctx
.argv
= argv
+ optind
;
1529 ovs_cmdl_run_command(&ctx
, commands
);
1532 OVSTEST_REGISTER("test-ovn", test_ovn_main
);