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",
205 static const char *const addrs4
[] = { NULL
};
207 expr_addr_sets_add(addr_sets
, "set1", addrs1
, 3);
208 expr_addr_sets_add(addr_sets
, "set2", addrs2
, 3);
209 expr_addr_sets_add(addr_sets
, "set3", addrs3
, 3);
210 expr_addr_sets_add(addr_sets
, "set4", addrs4
, 0);
214 lookup_port_cb(const void *ports_
, const char *port_name
, unsigned int *portp
)
216 const struct simap
*ports
= ports_
;
217 const struct simap_node
*node
= simap_find(ports
, port_name
);
226 is_chassis_resident_cb(const void *ports_
, const char *port_name
)
228 const struct simap
*ports
= ports_
;
229 const struct simap_node
*node
= simap_find(ports
, port_name
);
237 test_parse_expr__(int steps
)
240 struct shash addr_sets
;
244 create_symtab(&symtab
);
245 create_addr_sets(&addr_sets
);
248 simap_put(&ports
, "eth0", 5);
249 simap_put(&ports
, "eth1", 6);
250 simap_put(&ports
, "LOCAL", ofp_to_u16(OFPP_LOCAL
));
253 while (!ds_get_test_line(&input
, stdin
)) {
257 expr
= expr_parse_string(ds_cstr(&input
), &symtab
, &addr_sets
, &error
);
258 if (!error
&& steps
> 0) {
259 expr
= expr_annotate(expr
, &symtab
, &error
);
263 expr
= expr_simplify(expr
, is_chassis_resident_cb
, &ports
);
266 expr
= expr_normalize(expr
);
267 ovs_assert(expr_is_normalized(expr
));
274 expr_to_matches(expr
, lookup_port_cb
, &ports
, &matches
);
275 expr_matches_print(&matches
, stdout
);
276 expr_matches_destroy(&matches
);
278 struct ds output
= DS_EMPTY_INITIALIZER
;
279 expr_format(expr
, &output
);
280 puts(ds_cstr(&output
));
291 simap_destroy(&ports
);
292 expr_symtab_destroy(&symtab
);
293 shash_destroy(&symtab
);
294 expr_addr_sets_destroy(&addr_sets
);
295 shash_destroy(&addr_sets
);
299 test_parse_expr(struct ovs_cmdl_context
*ctx OVS_UNUSED
)
301 test_parse_expr__(0);
305 test_annotate_expr(struct ovs_cmdl_context
*ctx OVS_UNUSED
)
307 test_parse_expr__(1);
311 test_simplify_expr(struct ovs_cmdl_context
*ctx OVS_UNUSED
)
313 test_parse_expr__(2);
317 test_normalize_expr(struct ovs_cmdl_context
*ctx OVS_UNUSED
)
319 test_parse_expr__(3);
323 test_expr_to_flows(struct ovs_cmdl_context
*ctx OVS_UNUSED
)
325 test_parse_expr__(4);
328 /* Print the symbol table. */
331 test_dump_symtab(struct ovs_cmdl_context
*ctx OVS_UNUSED
)
334 create_symtab(&symtab
);
336 const struct shash_node
**nodes
= shash_sort(&symtab
);
337 for (size_t i
= 0; i
< shash_count(&symtab
); i
++) {
338 const struct expr_symbol
*symbol
= nodes
[i
]->data
;
339 struct ds s
= DS_EMPTY_INITIALIZER
;
340 expr_symbol_format(symbol
, &s
);
346 expr_symtab_destroy(&symtab
);
347 shash_destroy(&symtab
);
350 /* Evaluate an expression. */
353 lookup_atoi_cb(const void *aux OVS_UNUSED
, const char *port_name
,
356 *portp
= atoi(port_name
);
361 test_evaluate_expr(struct ovs_cmdl_context
*ctx
)
366 ovn_init_symtab(&symtab
);
369 char *error
= expr_parse_microflow(ctx
->argv
[1], &symtab
, NULL
,
370 lookup_atoi_cb
, NULL
, &uflow
);
372 ovs_fatal(0, "%s", error
);
376 while (!ds_get_test_line(&input
, stdin
)) {
379 expr
= expr_parse_string(ds_cstr(&input
), &symtab
, NULL
, &error
);
381 expr
= expr_annotate(expr
, &symtab
, &error
);
384 printf("%d\n", expr_evaluate(expr
, &uflow
, lookup_atoi_cb
, NULL
));
393 expr_symtab_destroy(&symtab
);
394 shash_destroy(&symtab
);
399 * The "compositions" of a positive integer N are all of the ways that one can
400 * add up positive integers to sum to N. For example, the compositions of 3
401 * are 3, 2+1, 1+2, and 1+1+1.
403 * We use compositions to find all the ways to break up N terms of a Boolean
404 * expression into subexpressions. Suppose we want to generate all expressions
405 * with 3 terms. The compositions of 3 (ignoring 3 itself) provide the
406 * possibilities (x && x) || x, x || (x && x), and x || x || x. (Of course one
407 * can exchange && for || in each case.) One must recursively compose the
408 * sub-expressions whose values are 3 or greater; that is what the "tree shape"
409 * concept later covers.
411 * To iterate through all compositions of, e.g., 5:
413 * unsigned int state;
417 * for (n = first_composition(ARRAY_SIZE(s), &state, s); n > 0;
418 * n = next_composition(&state, s, n)) {
419 * // Do something with composition 's' with 'n' elements.
422 * Algorithm from D. E. Knuth, _The Art of Computer Programming, Vol. 4A:
423 * Combinatorial Algorithms, Part 1_, section 7.2.1.1, answer to exercise
427 /* Begins iteration through the compositions of 'n'. Initializes 's' to the
428 * number of elements in the first composition of 'n' and returns that number
429 * of elements. The first composition in fact is always 'n' itself, so the
430 * return value will be 1.
432 * Initializes '*state' to some internal state information. The caller must
433 * maintain this state (and 's') for use by next_composition().
435 * 's' must have room for at least 'n' elements. */
437 first_composition(int n
, unsigned int *state
, int s
[])
444 /* Advances 's', with 'sn' elements, to the next composition and returns the
445 * number of elements in this new composition, or 0 if no compositions are
446 * left. 'state' is the same internal state passed to first_composition(). */
448 next_composition(unsigned int *state
, int s
[], int sn
)
479 test_composition(struct ovs_cmdl_context
*ctx
)
481 int n
= atoi(ctx
->argv
[1]);
485 for (int sn
= first_composition(n
, &state
, s
); sn
;
486 sn
= next_composition(&state
, s
, sn
)) {
487 for (int i
= 0; i
< sn
; i
++) {
488 printf("%d%c", s
[i
], i
== sn
- 1 ? '\n' : ' ');
495 * This code generates all possible Boolean expressions with a specified number
496 * of terms N (equivalent to the number of external nodes in a tree).
498 * See test_tree_shape() for a simple example. */
500 /* An array of these structures describes the shape of a tree.
502 * A single element of struct tree_shape describes a single node in the tree.
503 * The node has 'sn' direct children. From left to right, for i in 0...sn-1,
504 * s[i] is 1 if the child is a leaf node, otherwise the child is a subtree and
505 * s[i] is the number of leaf nodes within that subtree. In the latter case,
506 * the subtree is described by another struct tree_shape within the enclosing
507 * array. The tree_shapes are ordered in the array in in-order.
516 init_tree_shape__(struct tree_shape ts
[], int n
)
523 /* Skip the first composition intentionally. */
524 ts
->sn
= first_composition(n
, &ts
->state
, ts
->s
);
525 ts
->sn
= next_composition(&ts
->state
, ts
->s
, ts
->sn
);
526 for (int i
= 0; i
< ts
->sn
; i
++) {
527 n_tses
+= init_tree_shape__(&ts
[n_tses
], ts
->s
[i
]);
532 /* Initializes 'ts[]' as the first in the set of all of possible shapes of
533 * trees with 'n' leaves. Returns the number of "struct tree_shape"s in the
534 * first tree shape. */
536 init_tree_shape(struct tree_shape ts
[], int n
)
549 return init_tree_shape__(ts
, n
);
553 /* Advances 'ts', which currently has 'n_tses' elements, to the next possible
554 * tree shape with the number of leaves passed to init_tree_shape(). Returns
555 * the number of "struct tree_shape"s in the next shape, or 0 if all tree
556 * shapes have been visited. */
558 next_tree_shape(struct tree_shape ts
[], int n_tses
)
560 if (n_tses
== 1 && ts
->sn
== 2 && ts
->s
[0] == 1 && ts
->s
[1] == 1) {
564 struct tree_shape
*p
= &ts
[n_tses
- 1];
565 p
->sn
= p
->sn
> 1 ? next_composition(&p
->state
, p
->s
, p
->sn
) : 0;
567 for (int i
= 0; i
< p
->sn
; i
++) {
568 n_tses
+= init_tree_shape__(&ts
[n_tses
], p
->s
[i
]);
578 print_tree_shape(const struct tree_shape ts
[], int n_tses
)
580 for (int i
= 0; i
< n_tses
; i
++) {
584 for (int j
= 0; j
< ts
[i
].sn
; j
++) {
596 test_tree_shape(struct ovs_cmdl_context
*ctx
)
598 int n
= atoi(ctx
->argv
[1]);
599 struct tree_shape ts
[50];
602 for (n_tses
= init_tree_shape(ts
, n
); n_tses
;
603 n_tses
= next_tree_shape(ts
, n_tses
)) {
604 print_tree_shape(ts
, n_tses
);
609 /* Iteration through all possible terminal expressions (e.g. EXPR_T_CMP and
610 * EXPR_T_BOOLEAN expressions).
612 * Given a tree shape, this allows the code to try all possible ways to plug in
617 * struct expr terminal;
618 * const struct expr_symbol *vars = ...;
622 * init_terminal(&terminal, vars[0]);
624 * // Something with 'terminal'.
625 * } while (next_terminal(&terminal, vars, n_vars, n_bits));
628 /* Sets 'expr' to the first possible terminal expression. 'var' should be the
629 * first variable in the ones to be tested. */
631 init_terminal(struct expr
*expr
, int phase
,
632 const struct expr_symbol
*nvars
[], int n_nvars
,
633 const struct expr_symbol
*svars
[], int n_svars
)
635 if (phase
< 1 && n_nvars
) {
636 expr
->type
= EXPR_T_CMP
;
637 expr
->cmp
.symbol
= nvars
[0];
638 expr
->cmp
.relop
= rightmost_1bit_idx(test_relops
);
639 memset(&expr
->cmp
.value
, 0, sizeof expr
->cmp
.value
);
640 memset(&expr
->cmp
.mask
, 0, sizeof expr
->cmp
.mask
);
641 expr
->cmp
.value
.integer
= htonll(0);
642 expr
->cmp
.mask
.integer
= htonll(0);
646 if (phase
< 2 && n_svars
) {
647 expr
->type
= EXPR_T_CMP
;
648 expr
->cmp
.symbol
= svars
[0];
649 expr
->cmp
.relop
= EXPR_R_EQ
;
650 expr
->cmp
.string
= xstrdup("0");
654 expr
->type
= EXPR_T_BOOLEAN
;
655 expr
->boolean
= false;
658 /* Returns 'x' with the rightmost contiguous string of 1s changed to 0s,
659 * e.g. 01011100 => 01000000. See H. S. Warren, Jr., _Hacker's Delight_, 2nd
660 * ed., section 2-1. */
662 turn_off_rightmost_1s(unsigned int x
)
664 return ((x
& -x
) + x
) & x
;
667 static const struct expr_symbol
*
668 next_var(const struct expr_symbol
*symbol
,
669 const struct expr_symbol
*vars
[], int n_vars
)
671 for (int i
= 0; i
< n_vars
; i
++) {
672 if (symbol
== vars
[i
]) {
673 return i
+ 1 >= n_vars
? NULL
: vars
[i
+ 1];
679 static enum expr_relop
680 next_relop(enum expr_relop relop
)
682 unsigned int remaining_relops
= test_relops
& ~((1u << (relop
+ 1)) - 1);
683 return (remaining_relops
684 ? rightmost_1bit_idx(remaining_relops
)
685 : rightmost_1bit_idx(test_relops
));
688 /* Advances 'expr' to the next possible terminal expression within the 'n_vars'
689 * variables of 'n_bits' bits each in 'vars[]'. */
691 next_terminal(struct expr
*expr
,
692 const struct expr_symbol
*nvars
[], int n_nvars
, int n_bits
,
693 const struct expr_symbol
*svars
[], int n_svars
)
695 if (expr
->type
== EXPR_T_BOOLEAN
) {
699 expr
->boolean
= true;
704 if (!expr
->cmp
.symbol
->width
) {
705 int next_value
= atoi(expr
->cmp
.string
) + 1;
706 free(expr
->cmp
.string
);
707 if (next_value
> 1) {
708 expr
->cmp
.symbol
= next_var(expr
->cmp
.symbol
, svars
, n_svars
);
709 if (!expr
->cmp
.symbol
) {
710 init_terminal(expr
, 2, nvars
, n_nvars
, svars
, n_svars
);
715 expr
->cmp
.string
= xasprintf("%d", next_value
);
721 next
= (ntohll(expr
->cmp
.value
.integer
)
722 + (ntohll(expr
->cmp
.mask
.integer
) << n_bits
));
725 unsigned m
= next
>> n_bits
;
726 unsigned v
= next
& ((1u << n_bits
) - 1);
727 if (next
>= (1u << (2 * n_bits
))) {
728 enum expr_relop old_relop
= expr
->cmp
.relop
;
729 expr
->cmp
.relop
= next_relop(old_relop
);
730 if (expr
->cmp
.relop
<= old_relop
) {
731 expr
->cmp
.symbol
= next_var(expr
->cmp
.symbol
, nvars
, n_nvars
);
732 if (!expr
->cmp
.symbol
) {
733 init_terminal(expr
, 1, nvars
, n_nvars
, svars
, n_svars
);
739 /* Skip: 1-bits in value correspond to 0-bits in mask. */
740 } else if ((!m
|| turn_off_rightmost_1s(m
))
741 && (expr
->cmp
.relop
!= EXPR_R_EQ
&&
742 expr
->cmp
.relop
!= EXPR_R_NE
)) {
743 /* Skip: can't have discontiguous or all-0 mask for > >= < <=. */
745 expr
->cmp
.value
.integer
= htonll(v
);
746 expr
->cmp
.mask
.integer
= htonll(m
);
753 make_terminal(struct expr
***terminalp
)
755 struct expr
*e
= expr_create_boolean(true);
762 build_simple_tree(enum expr_type type
, int n
, struct expr
***terminalp
)
765 struct expr
*e
= expr_create_andor(type
);
766 for (int i
= 0; i
< 2; i
++) {
767 struct expr
*sub
= make_terminal(terminalp
);
768 ovs_list_push_back(&e
->andor
, &sub
->node
);
772 return make_terminal(terminalp
);
779 build_tree_shape(enum expr_type type
, const struct tree_shape
**tsp
,
780 struct expr
***terminalp
)
782 const struct tree_shape
*ts
= *tsp
;
785 struct expr
*e
= expr_create_andor(type
);
786 enum expr_type t
= type
== EXPR_T_AND
? EXPR_T_OR
: EXPR_T_AND
;
787 for (int i
= 0; i
< ts
->sn
; i
++) {
788 struct expr
*sub
= (ts
->s
[i
] > 2
789 ? build_tree_shape(t
, tsp
, terminalp
)
790 : build_simple_tree(t
, ts
->s
[i
], terminalp
));
791 ovs_list_push_back(&e
->andor
, &sub
->node
);
801 free_rule(struct test_rule
*test_rule
)
803 cls_rule_destroy(&test_rule
->cr
);
808 tree_shape_is_chassis_resident_cb(const void *c_aux OVS_UNUSED
,
809 const char *port_name OVS_UNUSED
)
815 test_tree_shape_exhaustively(struct expr
*expr
, struct shash
*symtab
,
816 struct expr
*terminals
[], int n_terminals
,
817 const struct expr_symbol
*nvars
[], int n_nvars
,
819 const struct expr_symbol
*svars
[], int n_svars
)
823 const unsigned int var_mask
= (1u << n_bits
) - 1;
824 for (int i
= 0; i
< n_terminals
; i
++) {
825 init_terminal(terminals
[i
], 0, nvars
, n_nvars
, svars
, n_svars
);
828 struct ds s
= DS_EMPTY_INITIALIZER
;
830 memset(&f
, 0, sizeof f
);
832 for (int i
= n_terminals
- 1; ; i
--) {
837 if (next_terminal(terminals
[i
], nvars
, n_nvars
, n_bits
,
841 init_terminal(terminals
[i
], 0, nvars
, n_nvars
, svars
, n_svars
);
843 ovs_assert(expr_honors_invariants(expr
));
847 struct expr
*modified
;
848 if (operation
== OP_CONVERT
) {
850 expr_format(expr
, &s
);
853 modified
= expr_parse_string(ds_cstr(&s
), symtab
, NULL
, &error
);
855 fprintf(stderr
, "%s fails to parse (%s)\n",
859 } else if (operation
>= OP_SIMPLIFY
) {
860 modified
= expr_simplify(expr_clone(expr
),
861 tree_shape_is_chassis_resident_cb
,
863 ovs_assert(expr_honors_invariants(modified
));
865 if (operation
>= OP_NORMALIZE
) {
866 modified
= expr_normalize(modified
);
867 ovs_assert(expr_is_normalized(modified
));
872 struct classifier cls
;
873 if (operation
>= OP_FLOW
) {
874 struct expr_match
*m
;
875 struct test_rule
*test_rule
;
877 expr_to_matches(modified
, lookup_atoi_cb
, NULL
, &matches
);
879 classifier_init(&cls
, NULL
);
880 HMAP_FOR_EACH (m
, hmap_node
, &matches
) {
881 test_rule
= xmalloc(sizeof *test_rule
);
882 cls_rule_init(&test_rule
->cr
, &m
->match
, 0);
883 classifier_insert(&cls
, &test_rule
->cr
, OVS_VERSION_MIN
,
884 m
->conjunctions
, m
->n
);
887 for (int subst
= 0; subst
< 1 << (n_bits
* n_nvars
+ n_svars
);
889 for (int i
= 0; i
< n_nvars
; i
++) {
890 f
.regs
[i
] = (subst
>> (i
* n_bits
)) & var_mask
;
892 for (int i
= 0; i
< n_svars
; i
++) {
893 f
.regs
[n_nvars
+ i
] = ((subst
>> (n_nvars
* n_bits
+ i
))
897 bool expected
= expr_evaluate(expr
, &f
, lookup_atoi_cb
, NULL
);
898 bool actual
= expr_evaluate(modified
, &f
, lookup_atoi_cb
, NULL
);
899 if (actual
!= expected
) {
900 struct ds expr_s
, modified_s
;
903 expr_format(expr
, &expr_s
);
905 ds_init(&modified_s
);
906 expr_format(modified
, &modified_s
);
909 "%s evaluates to %d, but %s evaluates to %d, for",
910 ds_cstr(&expr_s
), expected
,
911 ds_cstr(&modified_s
), actual
);
912 for (int i
= 0; i
< n_nvars
; i
++) {
916 fprintf(stderr
, " n%d = 0x%x", i
,
917 (subst
>> (n_bits
* i
)) & var_mask
);
919 for (int i
= 0; i
< n_svars
; i
++) {
920 fprintf(stderr
, ", s%d = \"%d\"", i
,
921 (subst
>> (n_bits
* n_nvars
+ i
)) & 1);
927 if (operation
>= OP_FLOW
) {
928 bool found
= classifier_lookup(&cls
, OVS_VERSION_MIN
,
930 if (expected
!= found
) {
931 struct ds expr_s
, modified_s
;
934 expr_format(expr
, &expr_s
);
936 ds_init(&modified_s
);
937 expr_format(modified
, &modified_s
);
940 "%s and %s evaluate to %d, for",
941 ds_cstr(&expr_s
), ds_cstr(&modified_s
), expected
);
942 for (int i
= 0; i
< n_nvars
; i
++) {
946 fprintf(stderr
, " n%d = 0x%x", i
,
947 (subst
>> (n_bits
* i
)) & var_mask
);
949 for (int i
= 0; i
< n_svars
; i
++) {
950 fprintf(stderr
, ", s%d = \"%d\"", i
,
951 (subst
>> (n_bits
* n_nvars
+ i
)) & 1);
953 fputs(".\n", stderr
);
955 fprintf(stderr
, "Converted to classifier:\n");
956 expr_matches_print(&matches
, stderr
);
958 "However, %s flow was found in the classifier.\n",
964 if (operation
>= OP_FLOW
) {
965 struct test_rule
*test_rule
;
967 CLS_FOR_EACH (test_rule
, cr
, &cls
) {
968 classifier_remove(&cls
, &test_rule
->cr
);
969 ovsrcu_postpone(free_rule
, test_rule
);
971 classifier_destroy(&cls
);
974 expr_matches_destroy(&matches
);
976 expr_destroy(modified
);
982 wait_pid(pid_t
*pids
, int *n
)
987 pid
= waitpid(-1, &status
, 0);
989 ovs_fatal(errno
, "waitpid failed");
990 } else if (WIFEXITED(status
)) {
991 if (WEXITSTATUS(status
)) {
992 exit(WEXITSTATUS(status
));
994 } else if (WIFSIGNALED(status
)) {
995 raise(WTERMSIG(status
));
1001 for (int i
= 0; i
< *n
; i
++) {
1002 if (pids
[i
] == pid
) {
1003 pids
[i
] = pids
[--*n
];
1007 ovs_fatal(0, "waitpid returned unknown child");
1012 test_exhaustive(struct ovs_cmdl_context
*ctx OVS_UNUSED
)
1014 int n_terminals
= atoi(ctx
->argv
[1]);
1015 struct tree_shape ts
[50];
1018 struct shash symtab
;
1019 const struct expr_symbol
*nvars
[4];
1020 const struct expr_symbol
*svars
[4];
1022 ovs_assert(test_nvars
<= ARRAY_SIZE(nvars
));
1023 ovs_assert(test_svars
<= ARRAY_SIZE(svars
));
1024 ovs_assert(test_nvars
+ test_svars
<= FLOW_N_REGS
);
1026 shash_init(&symtab
);
1027 for (int i
= 0; i
< test_nvars
; i
++) {
1028 char *name
= xasprintf("n%d", i
);
1029 nvars
[i
] = expr_symtab_add_field(&symtab
, name
, MFF_REG0
+ i
, NULL
,
1033 for (int i
= 0; i
< test_svars
; i
++) {
1034 char *name
= xasprintf("s%d", i
);
1035 svars
[i
] = expr_symtab_add_string(&symtab
, name
,
1036 MFF_REG0
+ test_nvars
+ i
, NULL
);
1041 pid_t
*children
= xmalloc(test_parallel
* sizeof *children
);
1046 for (int i
= 0; i
< 2; i
++) {
1047 enum expr_type base_type
= i
? EXPR_T_OR
: EXPR_T_AND
;
1049 for (n_tses
= init_tree_shape(ts
, n_terminals
); n_tses
;
1050 n_tses
= next_tree_shape(ts
, n_tses
)) {
1051 const struct tree_shape
*tsp
= ts
;
1052 struct expr
*terminals
[50];
1053 struct expr
**terminalp
= terminals
;
1054 struct expr
*expr
= build_tree_shape(base_type
, &tsp
, &terminalp
);
1055 ovs_assert(terminalp
== &terminals
[n_terminals
]);
1057 if (verbosity
> 0) {
1058 print_tree_shape(ts
, n_tses
);
1060 struct ds s
= DS_EMPTY_INITIALIZER
;
1061 expr_format(expr
, &s
);
1067 if (test_parallel
> 1) {
1068 pid_t pid
= xfork();
1070 test_tree_shape_exhaustively(expr
, &symtab
,
1071 terminals
, n_terminals
,
1072 nvars
, test_nvars
, test_bits
,
1077 if (n_children
>= test_parallel
) {
1078 wait_pid(children
, &n_children
);
1080 children
[n_children
++] = pid
;
1085 n_tested
+= test_tree_shape_exhaustively(
1086 expr
, &symtab
, terminals
, n_terminals
,
1087 nvars
, test_nvars
, test_bits
,
1094 while (n_children
> 0) {
1095 wait_pid(children
, &n_children
);
1101 switch (operation
) {
1103 printf("converting");
1106 printf("simplifying");
1109 printf("normalizing");
1112 printf("converting to flows");
1116 printf(" %d expressions of %d terminals", n_tested
, n_terminals
);
1118 printf(" all %d-terminal expressions", n_terminals
);
1120 if (test_nvars
|| test_svars
) {
1123 printf(" %d numeric vars (each %d bits) in terms of operators",
1124 test_nvars
, test_bits
);
1125 for (unsigned int relops
= test_relops
; relops
;
1126 relops
= zero_rightmost_1bit(relops
)) {
1127 enum expr_relop r
= rightmost_1bit_idx(relops
);
1128 printf(" %s", expr_relop_to_string(r
));
1131 if (test_nvars
&& test_svars
) {
1135 printf(" %d string vars", test_svars
);
1138 printf(" in terms of Boolean constants only");
1142 expr_symtab_destroy(&symtab
);
1143 shash_destroy(&symtab
);
1147 test_expr_to_packets(struct ovs_cmdl_context
*ctx OVS_UNUSED
)
1149 struct shash symtab
;
1152 create_symtab(&symtab
);
1155 while (!ds_get_test_line(&input
, stdin
)) {
1157 char *error
= expr_parse_microflow(ds_cstr(&input
), &symtab
, NULL
,
1158 lookup_atoi_cb
, NULL
, &uflow
);
1165 uint64_t packet_stub
[128 / 8];
1166 struct dp_packet packet
;
1167 dp_packet_use_stub(&packet
, packet_stub
, sizeof packet_stub
);
1168 flow_compose(&packet
, &uflow
, 0);
1170 struct ds output
= DS_EMPTY_INITIALIZER
;
1171 const uint8_t *buf
= dp_packet_data(&packet
);
1172 for (int i
= 0; i
< dp_packet_size(&packet
); i
++) {
1173 uint8_t val
= buf
[i
];
1174 ds_put_format(&output
, "%02"PRIx8
, val
);
1176 puts(ds_cstr(&output
));
1177 ds_destroy(&output
);
1179 dp_packet_uninit(&packet
);
1183 expr_symtab_destroy(&symtab
);
1184 shash_destroy(&symtab
);
1190 test_parse_actions(struct ovs_cmdl_context
*ctx OVS_UNUSED
)
1192 struct shash symtab
;
1193 struct hmap dhcp_opts
;
1194 struct hmap dhcpv6_opts
;
1199 create_symtab(&symtab
);
1200 create_dhcp_opts(&dhcp_opts
, &dhcpv6_opts
);
1202 /* Initialize group ids. */
1203 struct group_table group_table
;
1204 group_table
.group_ids
= bitmap_allocate(MAX_OVN_GROUPS
);
1205 bitmap_set1(group_table
.group_ids
, 0); /* Group id 0 is invalid. */
1206 hmap_init(&group_table
.desired_groups
);
1207 hmap_init(&group_table
.existing_groups
);
1210 simap_put(&ports
, "eth0", 5);
1211 simap_put(&ports
, "eth1", 6);
1212 simap_put(&ports
, "LOCAL", ofp_to_u16(OFPP_LOCAL
));
1215 while (!ds_get_test_line(&input
, stdin
)) {
1216 struct ofpbuf ovnacts
;
1217 struct expr
*prereqs
;
1220 puts(ds_cstr(&input
));
1222 ofpbuf_init(&ovnacts
, 0);
1224 const struct ovnact_parse_params pp
= {
1226 .dhcp_opts
= &dhcp_opts
,
1227 .dhcpv6_opts
= &dhcpv6_opts
,
1231 error
= ovnacts_parse_string(ds_cstr(&input
), &pp
, &ovnacts
, &prereqs
);
1233 /* Convert the parsed representation back to a string and print it,
1234 * if it's different from the input. */
1235 struct ds ovnacts_s
= DS_EMPTY_INITIALIZER
;
1236 ovnacts_format(ovnacts
.data
, ovnacts
.size
, &ovnacts_s
);
1237 if (strcmp(ds_cstr(&input
), ds_cstr(&ovnacts_s
))) {
1238 printf(" formats as %s\n", ds_cstr(&ovnacts_s
));
1241 /* Encode the actions into OpenFlow and print. */
1242 const struct ovnact_encode_params ep
= {
1243 .lookup_port
= lookup_port_cb
,
1246 .group_table
= &group_table
,
1248 .pipeline
= OVNACT_P_INGRESS
,
1249 .ingress_ptable
= 8,
1250 .egress_ptable
= 40,
1251 .output_ptable
= 64,
1252 .mac_bind_ptable
= 65,
1254 struct ofpbuf ofpacts
;
1255 ofpbuf_init(&ofpacts
, 0);
1256 ovnacts_encode(ovnacts
.data
, ovnacts
.size
, &ep
, &ofpacts
);
1257 struct ds ofpacts_s
= DS_EMPTY_INITIALIZER
;
1258 ofpacts_format(ofpacts
.data
, ofpacts
.size
, NULL
, &ofpacts_s
);
1259 printf(" encodes as %s\n", ds_cstr(&ofpacts_s
));
1260 ds_destroy(&ofpacts_s
);
1261 ofpbuf_uninit(&ofpacts
);
1263 /* Print prerequisites if any. */
1265 struct ds prereqs_s
= DS_EMPTY_INITIALIZER
;
1266 expr_format(prereqs
, &prereqs_s
);
1267 printf(" has prereqs %s\n", ds_cstr(&prereqs_s
));
1268 ds_destroy(&prereqs_s
);
1271 /* Now re-parse and re-format the string to verify that it's
1272 * round-trippable. */
1273 struct ofpbuf ovnacts2
;
1274 struct expr
*prereqs2
;
1275 ofpbuf_init(&ovnacts2
, 0);
1276 error
= ovnacts_parse_string(ds_cstr(&ovnacts_s
), &pp
, &ovnacts2
,
1279 struct ds ovnacts2_s
= DS_EMPTY_INITIALIZER
;
1280 ovnacts_format(ovnacts2
.data
, ovnacts2
.size
, &ovnacts2_s
);
1281 if (strcmp(ds_cstr(&ovnacts_s
), ds_cstr(&ovnacts2_s
))) {
1282 printf(" bad reformat: %s\n", ds_cstr(&ovnacts2_s
));
1285 ds_destroy(&ovnacts2_s
);
1287 printf(" reparse error: %s\n", error
);
1291 expr_destroy(prereqs2
);
1293 ovnacts_free(ovnacts2
.data
, ovnacts2
.size
);
1294 ofpbuf_uninit(&ovnacts2
);
1295 ds_destroy(&ovnacts_s
);
1297 printf(" %s\n", error
);
1301 expr_destroy(prereqs
);
1302 ovnacts_free(ovnacts
.data
, ovnacts
.size
);
1303 ofpbuf_uninit(&ovnacts
);
1307 simap_destroy(&ports
);
1308 expr_symtab_destroy(&symtab
);
1309 shash_destroy(&symtab
);
1310 dhcp_opts_destroy(&dhcp_opts
);
1311 dhcp_opts_destroy(&dhcpv6_opts
);
1313 exit(ok
? EXIT_SUCCESS
: EXIT_FAILURE
);
1317 parse_relops(const char *s
)
1319 unsigned int relops
= 0;
1322 lexer_init(&lexer
, s
);
1325 enum expr_relop relop
;
1327 if (expr_relop_from_token(lexer
.token
.type
, &relop
)) {
1328 relops
|= 1u << relop
;
1331 ovs_fatal(0, "%s: relational operator expected at `%.*s'",
1332 s
, (int) (lexer
.input
- lexer
.start
), lexer
.start
);
1334 lexer_match(&lexer
, LEX_T_COMMA
);
1335 } while (lexer
.token
.type
!= LEX_T_END
);
1336 lexer_destroy(&lexer
);
1345 %s: OVN test utility\n\
1346 usage: test-ovn %s [OPTIONS] COMMAND [ARG...]\n\
1349 Lexically analyzes OVN input from stdin and print them back on stdout.\n\
1356 Parses OVN expressions from stdin and prints them back on stdout after\n\
1357 differing degrees of analysis. Available fields are based on packet\n\
1361 Parses OVN expressions from stdin and prints out matching packets in\n\
1362 hexadecimal on stdout.\n\
1364 evaluate-expr MICROFLOW\n\
1365 Parses OVN expressions from stdin and evaluates them against the flow\n\
1366 specified in MICROFLOW, which must be an expression that constrains\n\
1367 the packet, e.g. \"ip4 && tcp.src == 80\" for a TCP packet with source\n\
1368 port 80, and prints the results on stdout, either 1 for true or 0 for\n\
1369 false. Use quoted integers, e.g. \"123\", for string fields.\n\
1371 Example: for MICROFLOW of \"ip4 && tcp.src == 80\", \"eth.type == 0x800\"\n\
1372 evaluates to true, \"udp\" evaluates to false, and \"udp || tcp\"\n\
1373 evaluates to true.\n\
1376 Prints all the compositions of N on stdout.\n\
1379 Prints all the tree shapes with N terminals on stdout.\n\
1382 Tests that all possible Boolean expressions with N terminals are properly\n\
1383 simplified, normalized, and converted to flows. Available options:\n\
1385 --operation=OPERATION Operation to test, one of: convert, simplify,\n\
1386 normalize, flow. Default: flow. 'normalize' includes 'simplify',\n\
1387 'flow' includes 'simplify' and 'normalize'.\n\
1388 --parallel=N Number of processes to use in parallel, default 1.\n\
1390 --nvars=N Number of numeric vars to test, in range 0...4, default 2.\n\
1391 --bits=N Number of bits per variable, in range 1...3, default 3.\n\
1392 --relops=OPERATORS Test only the specified Boolean operators.\n\
1393 OPERATORS may include == != < <= > >=, space or\n\
1394 comma separated. Default is all operators.\n\
1396 --svars=N Number of string vars to test, in range 0...4, default 2.\n\
1399 Parses OVN actions from stdin and prints the equivalent OpenFlow actions\n\
1402 program_name
, program_name
);
1407 test_ovn_main(int argc
, char *argv
[])
1410 OPT_RELOPS
= UCHAR_MAX
+ 1,
1417 static const struct option long_options
[] = {
1418 {"relops", required_argument
, NULL
, OPT_RELOPS
},
1419 {"nvars", required_argument
, NULL
, OPT_NVARS
},
1420 {"svars", required_argument
, NULL
, OPT_SVARS
},
1421 {"bits", required_argument
, NULL
, OPT_BITS
},
1422 {"operation", required_argument
, NULL
, OPT_OPERATION
},
1423 {"parallel", required_argument
, NULL
, OPT_PARALLEL
},
1424 {"more", no_argument
, NULL
, 'm'},
1425 {"help", no_argument
, NULL
, 'h'},
1428 char *short_options
= ovs_cmdl_long_options_to_short_options(long_options
);
1430 set_program_name(argv
[0]);
1432 test_relops
= parse_relops("== != < <= > >=");
1434 int option_index
= 0;
1435 int c
= getopt_long (argc
, argv
, short_options
, long_options
,
1443 test_relops
= parse_relops(optarg
);
1447 test_nvars
= atoi(optarg
);
1448 if (test_nvars
< 0 || test_nvars
> 4) {
1449 ovs_fatal(0, "number of numeric variables must be "
1455 test_svars
= atoi(optarg
);
1456 if (test_svars
< 0 || test_svars
> 4) {
1457 ovs_fatal(0, "number of string variables must be "
1463 test_bits
= atoi(optarg
);
1464 if (test_bits
< 1 || test_bits
> 3) {
1465 ovs_fatal(0, "number of bits must be between 1 and 3");
1470 if (!strcmp(optarg
, "convert")) {
1471 operation
= OP_CONVERT
;
1472 } else if (!strcmp(optarg
, "simplify")) {
1473 operation
= OP_SIMPLIFY
;
1474 } else if (!strcmp(optarg
, "normalize")) {
1475 operation
= OP_NORMALIZE
;
1476 } else if (!strcmp(optarg
, "flow")) {
1477 operation
= OP_FLOW
;
1479 ovs_fatal(0, "%s: unknown operation", optarg
);
1484 test_parallel
= atoi(optarg
);
1502 free(short_options
);
1504 static const struct ovs_cmdl_command commands
[] = {
1506 {"lex", NULL
, 0, 0, test_lex
, OVS_RO
},
1509 {"dump-symtab", NULL
, 0, 0, test_dump_symtab
, OVS_RO
},
1512 {"parse-expr", NULL
, 0, 0, test_parse_expr
, OVS_RO
},
1513 {"annotate-expr", NULL
, 0, 0, test_annotate_expr
, OVS_RO
},
1514 {"simplify-expr", NULL
, 0, 0, test_simplify_expr
, OVS_RO
},
1515 {"normalize-expr", NULL
, 0, 0, test_normalize_expr
, OVS_RO
},
1516 {"expr-to-flows", NULL
, 0, 0, test_expr_to_flows
, OVS_RO
},
1517 {"evaluate-expr", NULL
, 1, 1, test_evaluate_expr
, OVS_RO
},
1518 {"composition", NULL
, 1, 1, test_composition
, OVS_RO
},
1519 {"tree-shape", NULL
, 1, 1, test_tree_shape
, OVS_RO
},
1520 {"exhaustive", NULL
, 1, 1, test_exhaustive
, OVS_RO
},
1521 {"expr-to-packets", NULL
, 0, 0, test_expr_to_packets
, OVS_RO
},
1524 {"parse-actions", NULL
, 0, 0, test_parse_actions
, OVS_RO
},
1526 {NULL
, NULL
, 0, 0, NULL
, OVS_RO
},
1528 struct ovs_cmdl_context ctx
;
1529 ctx
.argc
= argc
- optind
;
1530 ctx
.argv
= argv
+ optind
;
1531 ovs_cmdl_run_command(&ctx
, commands
);
1534 OVSTEST_REGISTER("test-ovn", test_ovn_main
);