]>
Commit | Line | Data |
---|---|---|
10b1662b | 1 | /* |
4c99cb18 | 2 | * Copyright (c) 2015, 2016, 2017 Nicira, Inc. |
10b1662b BP |
3 | * |
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: | |
7 | * | |
8 | * http://www.apache.org/licenses/LICENSE-2.0 | |
9 | * | |
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. | |
15 | */ | |
16 | ||
17 | #include <config.h> | |
e0840f11 | 18 | #include <errno.h> |
10b1662b | 19 | #include <getopt.h> |
e0840f11 | 20 | #include <sys/wait.h> |
16936e4d | 21 | |
b598f214 | 22 | #include "command-line.h" |
1e028b17 | 23 | #include "dp-packet.h" |
10b1662b | 24 | #include "fatal-signal.h" |
f4248336 | 25 | #include "flow.h" |
b598f214 | 26 | #include "openvswitch/dynamic-string.h" |
e29747e4 | 27 | #include "openvswitch/match.h" |
b598f214 | 28 | #include "openvswitch/ofp-actions.h" |
64c96779 | 29 | #include "openvswitch/ofpbuf.h" |
b598f214 | 30 | #include "openvswitch/vlog.h" |
8b2ed684 AR |
31 | #include "ovn/actions.h" |
32 | #include "ovn/expr.h" | |
33 | #include "ovn/lex.h" | |
7700eea0 | 34 | #include "ovn/lib/logical-fields.h" |
16936e4d | 35 | #include "ovn/lib/ovn-l7.h" |
ad35c0c5 | 36 | #include "ovn/lib/extend-table.h" |
e0840f11 | 37 | #include "ovs-thread.h" |
10b1662b | 38 | #include "ovstest.h" |
ee89ea7b | 39 | #include "openvswitch/shash.h" |
f386a8a7 | 40 | #include "simap.h" |
10b1662b | 41 | #include "util.h" |
10b1662b | 42 | |
e0840f11 BP |
43 | /* --relops: Bitmap of the relational operators to test, in exhaustive test. */ |
44 | static unsigned int test_relops; | |
45 | ||
9d4aecca BP |
46 | /* --nvars: Number of numeric variables to test, in exhaustive test. */ |
47 | static int test_nvars = 2; | |
48 | ||
49 | /* --svars: Number of string variables to test, in exhaustive test. */ | |
50 | static int test_svars = 2; | |
e0840f11 BP |
51 | |
52 | /* --bits: Number of bits per variable, in exhaustive test. */ | |
53 | static int test_bits = 3; | |
54 | ||
55 | /* --operation: The operation to test, in exhaustive test. */ | |
56 | static enum { OP_CONVERT, OP_SIMPLIFY, OP_NORMALIZE, OP_FLOW } operation | |
57 | = OP_FLOW; | |
58 | ||
59 | /* --parallel: Number of parallel processes to use in test. */ | |
60 | static int test_parallel = 1; | |
61 | ||
62 | /* -m, --more: Message verbosity */ | |
63 | static int verbosity; | |
64 | ||
10b1662b BP |
65 | static void |
66 | compare_token(const struct lex_token *a, const struct lex_token *b) | |
67 | { | |
68 | if (a->type != b->type) { | |
69 | fprintf(stderr, "type differs: %d -> %d\n", a->type, b->type); | |
70 | return; | |
71 | } | |
72 | ||
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)"); | |
78 | return; | |
79 | } | |
80 | ||
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"); | |
84 | return; | |
85 | } | |
86 | ||
87 | if (a->type == LEX_T_MASKED_INTEGER | |
88 | && memcmp(&a->mask, &b->mask, sizeof a->mask)) { | |
89 | fprintf(stderr, "mask differs\n"); | |
90 | return; | |
91 | } | |
92 | ||
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); | |
99 | } | |
100 | } | |
101 | } | |
102 | ||
103 | static void | |
104 | test_lex(struct ovs_cmdl_context *ctx OVS_UNUSED) | |
105 | { | |
106 | struct ds input; | |
107 | struct ds output; | |
108 | ||
109 | ds_init(&input); | |
110 | ds_init(&output); | |
a20c96c6 | 111 | while (!ds_get_test_line(&input, stdin)) { |
10b1662b BP |
112 | struct lexer lexer; |
113 | ||
114 | lexer_init(&lexer, ds_cstr(&input)); | |
115 | ds_clear(&output); | |
116 | while (lexer_get(&lexer) != LEX_T_END) { | |
117 | size_t len = output.length; | |
118 | lex_token_format(&lexer.token, &output); | |
119 | ||
120 | /* Check that the formatted version can really be parsed back | |
121 | * losslessly. */ | |
122 | if (lexer.token.type != LEX_T_ERROR) { | |
123 | const char *s = ds_cstr(&output) + len; | |
124 | struct lexer l2; | |
125 | ||
126 | lexer_init(&l2, s); | |
127 | lexer_get(&l2); | |
128 | compare_token(&lexer.token, &l2.token); | |
129 | lexer_destroy(&l2); | |
130 | } | |
131 | ds_put_char(&output, ' '); | |
132 | } | |
133 | lexer_destroy(&lexer); | |
134 | ||
135 | ds_chomp(&output, ' '); | |
136 | puts(ds_cstr(&output)); | |
137 | } | |
138 | ds_destroy(&input); | |
139 | ds_destroy(&output); | |
140 | } | |
141 | ||
e0840f11 BP |
142 | static void |
143 | create_symtab(struct shash *symtab) | |
144 | { | |
7700eea0 | 145 | ovn_init_symtab(symtab); |
e0840f11 BP |
146 | |
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); | |
5ee054fb | 155 | expr_symtab_add_string(symtab, "big_string", MFF_XREG0, NULL); |
e0840f11 BP |
156 | } |
157 | ||
42814145 | 158 | static void |
52ed5fcc NS |
159 | create_gen_opts(struct hmap *dhcp_opts, struct hmap *dhcpv6_opts, |
160 | struct hmap *nd_ra_opts) | |
42814145 NS |
161 | { |
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"); | |
01cfdb2f NS |
185 | |
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"); | |
52ed5fcc NS |
192 | |
193 | /* IPv6 ND RA options. */ | |
194 | hmap_init(nd_ra_opts); | |
195 | nd_ra_opts_init(nd_ra_opts); | |
42814145 NS |
196 | } |
197 | ||
2c5cbb15 | 198 | static void |
b34e898f | 199 | create_addr_sets(struct shash *addr_sets) |
2c5cbb15 | 200 | { |
b34e898f | 201 | shash_init(addr_sets); |
2c5cbb15 RB |
202 | |
203 | static const char *const addrs1[] = { | |
204 | "10.0.0.1", "10.0.0.2", "10.0.0.3", | |
205 | }; | |
206 | static const char *const addrs2[] = { | |
207 | "::1", "::2", "::3", | |
208 | }; | |
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", | |
211 | }; | |
69414092 | 212 | static const char *const addrs4[] = { NULL }; |
2c5cbb15 | 213 | |
b34e898f JP |
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); | |
f3a4e992 | 217 | expr_addr_sets_add(addr_sets, "set4", addrs4, 0); |
2c5cbb15 RB |
218 | } |
219 | ||
f1c16a85 BP |
220 | static bool |
221 | lookup_port_cb(const void *ports_, const char *port_name, unsigned int *portp) | |
222 | { | |
223 | const struct simap *ports = ports_; | |
224 | const struct simap_node *node = simap_find(ports, port_name); | |
225 | if (!node) { | |
226 | return false; | |
227 | } | |
228 | *portp = node->data; | |
229 | return true; | |
230 | } | |
231 | ||
ba8d3816 MS |
232 | static bool |
233 | is_chassis_resident_cb(const void *ports_, const char *port_name) | |
234 | { | |
235 | const struct simap *ports = ports_; | |
236 | const struct simap_node *node = simap_find(ports, port_name); | |
237 | if (node) { | |
238 | return true; | |
239 | } | |
240 | return false; | |
241 | } | |
242 | ||
e0840f11 BP |
243 | static void |
244 | test_parse_expr__(int steps) | |
245 | { | |
246 | struct shash symtab; | |
b34e898f | 247 | struct shash addr_sets; |
f386a8a7 | 248 | struct simap ports; |
e0840f11 BP |
249 | struct ds input; |
250 | ||
251 | create_symtab(&symtab); | |
b34e898f | 252 | create_addr_sets(&addr_sets); |
f386a8a7 BP |
253 | |
254 | simap_init(&ports); | |
255 | simap_put(&ports, "eth0", 5); | |
256 | simap_put(&ports, "eth1", 6); | |
257 | simap_put(&ports, "LOCAL", ofp_to_u16(OFPP_LOCAL)); | |
258 | ||
e0840f11 BP |
259 | ds_init(&input); |
260 | while (!ds_get_test_line(&input, stdin)) { | |
261 | struct expr *expr; | |
262 | char *error; | |
263 | ||
b34e898f | 264 | expr = expr_parse_string(ds_cstr(&input), &symtab, &addr_sets, &error); |
e0840f11 BP |
265 | if (!error && steps > 0) { |
266 | expr = expr_annotate(expr, &symtab, &error); | |
267 | } | |
268 | if (!error) { | |
269 | if (steps > 1) { | |
ba8d3816 | 270 | expr = expr_simplify(expr, is_chassis_resident_cb, &ports); |
e0840f11 BP |
271 | } |
272 | if (steps > 2) { | |
273 | expr = expr_normalize(expr); | |
274 | ovs_assert(expr_is_normalized(expr)); | |
275 | } | |
276 | } | |
277 | if (!error) { | |
f386a8a7 BP |
278 | if (steps > 3) { |
279 | struct hmap matches; | |
280 | ||
f1c16a85 | 281 | expr_to_matches(expr, lookup_port_cb, &ports, &matches); |
f386a8a7 BP |
282 | expr_matches_print(&matches, stdout); |
283 | expr_matches_destroy(&matches); | |
284 | } else { | |
285 | struct ds output = DS_EMPTY_INITIALIZER; | |
286 | expr_format(expr, &output); | |
287 | puts(ds_cstr(&output)); | |
288 | ds_destroy(&output); | |
289 | } | |
e0840f11 BP |
290 | } else { |
291 | puts(error); | |
292 | free(error); | |
293 | } | |
294 | expr_destroy(expr); | |
295 | } | |
296 | ds_destroy(&input); | |
297 | ||
f386a8a7 | 298 | simap_destroy(&ports); |
e0840f11 BP |
299 | expr_symtab_destroy(&symtab); |
300 | shash_destroy(&symtab); | |
b34e898f JP |
301 | expr_addr_sets_destroy(&addr_sets); |
302 | shash_destroy(&addr_sets); | |
e0840f11 BP |
303 | } |
304 | ||
305 | static void | |
306 | test_parse_expr(struct ovs_cmdl_context *ctx OVS_UNUSED) | |
307 | { | |
308 | test_parse_expr__(0); | |
309 | } | |
310 | ||
311 | static void | |
312 | test_annotate_expr(struct ovs_cmdl_context *ctx OVS_UNUSED) | |
313 | { | |
314 | test_parse_expr__(1); | |
315 | } | |
316 | ||
317 | static void | |
318 | test_simplify_expr(struct ovs_cmdl_context *ctx OVS_UNUSED) | |
319 | { | |
320 | test_parse_expr__(2); | |
321 | } | |
322 | ||
323 | static void | |
324 | test_normalize_expr(struct ovs_cmdl_context *ctx OVS_UNUSED) | |
325 | { | |
326 | test_parse_expr__(3); | |
327 | } | |
f386a8a7 BP |
328 | |
329 | static void | |
330 | test_expr_to_flows(struct ovs_cmdl_context *ctx OVS_UNUSED) | |
331 | { | |
332 | test_parse_expr__(4); | |
333 | } | |
e0840f11 | 334 | \f |
7700eea0 BP |
335 | /* Print the symbol table. */ |
336 | ||
337 | static void | |
338 | test_dump_symtab(struct ovs_cmdl_context *ctx OVS_UNUSED) | |
339 | { | |
340 | struct shash symtab; | |
341 | create_symtab(&symtab); | |
342 | ||
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); | |
348 | puts(ds_cstr(&s)); | |
349 | ds_destroy(&s); | |
350 | } | |
351 | ||
85d87d16 | 352 | free(nodes); |
7700eea0 BP |
353 | expr_symtab_destroy(&symtab); |
354 | shash_destroy(&symtab); | |
355 | } | |
356 | \f | |
e0840f11 BP |
357 | /* Evaluate an expression. */ |
358 | ||
e0840f11 | 359 | static bool |
803a6f3d BP |
360 | lookup_atoi_cb(const void *aux OVS_UNUSED, const char *port_name, |
361 | unsigned int *portp) | |
e0840f11 | 362 | { |
803a6f3d BP |
363 | *portp = atoi(port_name); |
364 | return true; | |
e0840f11 BP |
365 | } |
366 | ||
367 | static void | |
368 | test_evaluate_expr(struct ovs_cmdl_context *ctx) | |
369 | { | |
e0840f11 BP |
370 | struct shash symtab; |
371 | struct ds input; | |
372 | ||
d5b33279 BP |
373 | ovn_init_symtab(&symtab); |
374 | ||
375 | struct flow uflow; | |
376 | char *error = expr_parse_microflow(ctx->argv[1], &symtab, NULL, | |
377 | lookup_atoi_cb, NULL, &uflow); | |
378 | if (error) { | |
379 | ovs_fatal(0, "%s", error); | |
380 | } | |
e0840f11 BP |
381 | |
382 | ds_init(&input); | |
383 | while (!ds_get_test_line(&input, stdin)) { | |
384 | struct expr *expr; | |
e0840f11 | 385 | |
2c5cbb15 | 386 | expr = expr_parse_string(ds_cstr(&input), &symtab, NULL, &error); |
e0840f11 BP |
387 | if (!error) { |
388 | expr = expr_annotate(expr, &symtab, &error); | |
389 | } | |
390 | if (!error) { | |
803a6f3d | 391 | printf("%d\n", expr_evaluate(expr, &uflow, lookup_atoi_cb, NULL)); |
e0840f11 BP |
392 | } else { |
393 | puts(error); | |
394 | free(error); | |
395 | } | |
396 | expr_destroy(expr); | |
397 | } | |
398 | ds_destroy(&input); | |
399 | ||
400 | expr_symtab_destroy(&symtab); | |
401 | shash_destroy(&symtab); | |
402 | } | |
403 | \f | |
404 | /* Compositions. | |
405 | * | |
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. | |
409 | * | |
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. | |
417 | * | |
418 | * To iterate through all compositions of, e.g., 5: | |
419 | * | |
420 | * unsigned int state; | |
421 | * int s[5]; | |
422 | * int n; | |
423 | * | |
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. | |
427 | * } | |
428 | * | |
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 | |
431 | * 12(a). | |
432 | */ | |
433 | ||
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. | |
438 | * | |
439 | * Initializes '*state' to some internal state information. The caller must | |
440 | * maintain this state (and 's') for use by next_composition(). | |
441 | * | |
442 | * 's' must have room for at least 'n' elements. */ | |
443 | static int | |
444 | first_composition(int n, unsigned int *state, int s[]) | |
445 | { | |
446 | *state = 0; | |
447 | s[0] = n; | |
448 | return 1; | |
449 | } | |
450 | ||
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(). */ | |
454 | static int | |
455 | next_composition(unsigned int *state, int s[], int sn) | |
456 | { | |
457 | int j = sn - 1; | |
458 | if (++*state & 1) { | |
459 | if (s[j] > 1) { | |
460 | s[j]--; | |
461 | s[j + 1] = 1; | |
462 | j++; | |
463 | } else { | |
464 | j--; | |
465 | s[j]++; | |
466 | } | |
467 | } else { | |
468 | if (s[j - 1] > 1) { | |
469 | s[j - 1]--; | |
470 | s[j + 1] = s[j]; | |
471 | s[j] = 1; | |
472 | j++; | |
473 | } else { | |
474 | j--; | |
e0840f11 BP |
475 | if (!j) { |
476 | return 0; | |
477 | } | |
42d36b58 AZ |
478 | s[j] = s[j + 1]; |
479 | s[j - 1]++; | |
e0840f11 BP |
480 | } |
481 | } | |
482 | return j + 1; | |
483 | } | |
484 | ||
485 | static void | |
486 | test_composition(struct ovs_cmdl_context *ctx) | |
487 | { | |
488 | int n = atoi(ctx->argv[1]); | |
489 | unsigned int state; | |
490 | int s[50]; | |
491 | ||
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' : ' '); | |
496 | } | |
497 | } | |
498 | } | |
499 | \f | |
500 | /* Tree shapes. | |
501 | * | |
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). | |
504 | * | |
505 | * See test_tree_shape() for a simple example. */ | |
506 | ||
507 | /* An array of these structures describes the shape of a tree. | |
508 | * | |
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. | |
515 | */ | |
516 | struct tree_shape { | |
517 | unsigned int state; | |
518 | int s[50]; | |
519 | int sn; | |
520 | }; | |
521 | ||
522 | static int | |
523 | init_tree_shape__(struct tree_shape ts[], int n) | |
524 | { | |
525 | if (n <= 2) { | |
526 | return 0; | |
527 | } | |
528 | ||
529 | int n_tses = 1; | |
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]); | |
535 | } | |
536 | return n_tses; | |
537 | } | |
538 | ||
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. */ | |
542 | static int | |
543 | init_tree_shape(struct tree_shape ts[], int n) | |
544 | { | |
545 | switch (n) { | |
546 | case 1: | |
547 | ts->sn = 1; | |
548 | ts->s[0] = 1; | |
549 | return 1; | |
550 | case 2: | |
551 | ts->sn = 2; | |
552 | ts->s[0] = 1; | |
553 | ts->s[1] = 1; | |
554 | return 1; | |
555 | default: | |
556 | return init_tree_shape__(ts, n); | |
557 | } | |
558 | } | |
559 | ||
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. */ | |
564 | static int | |
565 | next_tree_shape(struct tree_shape ts[], int n_tses) | |
566 | { | |
567 | if (n_tses == 1 && ts->sn == 2 && ts->s[0] == 1 && ts->s[1] == 1) { | |
568 | return 0; | |
569 | } | |
570 | while (n_tses > 0) { | |
571 | struct tree_shape *p = &ts[n_tses - 1]; | |
572 | p->sn = p->sn > 1 ? next_composition(&p->state, p->s, p->sn) : 0; | |
573 | if (p->sn) { | |
574 | for (int i = 0; i < p->sn; i++) { | |
575 | n_tses += init_tree_shape__(&ts[n_tses], p->s[i]); | |
576 | } | |
577 | break; | |
578 | } | |
579 | n_tses--; | |
580 | } | |
581 | return n_tses; | |
582 | } | |
583 | ||
584 | static void | |
585 | print_tree_shape(const struct tree_shape ts[], int n_tses) | |
586 | { | |
587 | for (int i = 0; i < n_tses; i++) { | |
588 | if (i) { | |
589 | printf(", "); | |
590 | } | |
591 | for (int j = 0; j < ts[i].sn; j++) { | |
592 | int k = ts[i].s[j]; | |
593 | if (k > 9) { | |
594 | printf("(%d)", k); | |
595 | } else { | |
596 | printf("%d", k); | |
597 | } | |
598 | } | |
599 | } | |
600 | } | |
601 | ||
602 | static void | |
603 | test_tree_shape(struct ovs_cmdl_context *ctx) | |
604 | { | |
605 | int n = atoi(ctx->argv[1]); | |
606 | struct tree_shape ts[50]; | |
607 | int n_tses; | |
608 | ||
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); | |
612 | putchar('\n'); | |
613 | } | |
614 | } | |
615 | \f | |
616 | /* Iteration through all possible terminal expressions (e.g. EXPR_T_CMP and | |
617 | * EXPR_T_BOOLEAN expressions). | |
618 | * | |
619 | * Given a tree shape, this allows the code to try all possible ways to plug in | |
620 | * terms. | |
621 | * | |
622 | * Example use: | |
623 | * | |
624 | * struct expr terminal; | |
625 | * const struct expr_symbol *vars = ...; | |
626 | * int n_vars = ...; | |
627 | * int n_bits = ...; | |
628 | * | |
629 | * init_terminal(&terminal, vars[0]); | |
630 | * do { | |
631 | * // Something with 'terminal'. | |
632 | * } while (next_terminal(&terminal, vars, n_vars, n_bits)); | |
633 | */ | |
634 | ||
635 | /* Sets 'expr' to the first possible terminal expression. 'var' should be the | |
636 | * first variable in the ones to be tested. */ | |
637 | static void | |
9d4aecca BP |
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) | |
e0840f11 | 641 | { |
9d4aecca BP |
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); | |
8c3caa2c | 649 | expr->cmp.mask.integer = htonll(0); |
9d4aecca BP |
650 | return; |
651 | } | |
652 | ||
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"); | |
658 | return; | |
659 | } | |
660 | ||
661 | expr->type = EXPR_T_BOOLEAN; | |
662 | expr->boolean = false; | |
e0840f11 BP |
663 | } |
664 | ||
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. */ | |
668 | static unsigned int | |
669 | turn_off_rightmost_1s(unsigned int x) | |
670 | { | |
671 | return ((x & -x) + x) & x; | |
672 | } | |
673 | ||
674 | static const struct expr_symbol * | |
675 | next_var(const struct expr_symbol *symbol, | |
676 | const struct expr_symbol *vars[], int n_vars) | |
677 | { | |
678 | for (int i = 0; i < n_vars; i++) { | |
679 | if (symbol == vars[i]) { | |
680 | return i + 1 >= n_vars ? NULL : vars[i + 1]; | |
681 | } | |
682 | } | |
683 | OVS_NOT_REACHED(); | |
684 | } | |
685 | ||
686 | static enum expr_relop | |
687 | next_relop(enum expr_relop relop) | |
688 | { | |
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)); | |
693 | } | |
694 | ||
695 | /* Advances 'expr' to the next possible terminal expression within the 'n_vars' | |
696 | * variables of 'n_bits' bits each in 'vars[]'. */ | |
697 | static bool | |
9d4aecca BP |
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) | |
e0840f11 BP |
701 | { |
702 | if (expr->type == EXPR_T_BOOLEAN) { | |
703 | if (expr->boolean) { | |
704 | return false; | |
705 | } else { | |
706 | expr->boolean = true; | |
707 | return true; | |
708 | } | |
709 | } | |
710 | ||
9d4aecca BP |
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); | |
718 | return true; | |
719 | } | |
720 | next_value = 0; | |
721 | } | |
722 | expr->cmp.string = xasprintf("%d", next_value); | |
723 | return true; | |
724 | } | |
725 | ||
e0840f11 BP |
726 | unsigned int next; |
727 | ||
728 | next = (ntohll(expr->cmp.value.integer) | |
729 | + (ntohll(expr->cmp.mask.integer) << n_bits)); | |
730 | for (;;) { | |
731 | next++; | |
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) { | |
9d4aecca | 738 | expr->cmp.symbol = next_var(expr->cmp.symbol, nvars, n_nvars); |
e0840f11 | 739 | if (!expr->cmp.symbol) { |
9d4aecca | 740 | init_terminal(expr, 1, nvars, n_nvars, svars, n_svars); |
e0840f11 BP |
741 | return true; |
742 | } | |
743 | } | |
8c3caa2c | 744 | next = UINT_MAX; |
e0840f11 BP |
745 | } else if (v & ~m) { |
746 | /* Skip: 1-bits in value correspond to 0-bits in mask. */ | |
8c3caa2c | 747 | } else if ((!m || turn_off_rightmost_1s(m)) |
e0840f11 BP |
748 | && (expr->cmp.relop != EXPR_R_EQ && |
749 | expr->cmp.relop != EXPR_R_NE)) { | |
8c3caa2c | 750 | /* Skip: can't have discontiguous or all-0 mask for > >= < <=. */ |
e0840f11 BP |
751 | } else { |
752 | expr->cmp.value.integer = htonll(v); | |
753 | expr->cmp.mask.integer = htonll(m); | |
754 | return true; | |
755 | } | |
756 | } | |
757 | } | |
758 | \f | |
759 | static struct expr * | |
760 | make_terminal(struct expr ***terminalp) | |
761 | { | |
762 | struct expr *e = expr_create_boolean(true); | |
763 | **terminalp = e; | |
764 | (*terminalp)++; | |
765 | return e; | |
766 | } | |
767 | ||
768 | static struct expr * | |
769 | build_simple_tree(enum expr_type type, int n, struct expr ***terminalp) | |
770 | { | |
771 | if (n == 2) { | |
772 | struct expr *e = expr_create_andor(type); | |
773 | for (int i = 0; i < 2; i++) { | |
774 | struct expr *sub = make_terminal(terminalp); | |
417e7e66 | 775 | ovs_list_push_back(&e->andor, &sub->node); |
e0840f11 BP |
776 | } |
777 | return e; | |
778 | } else if (n == 1) { | |
779 | return make_terminal(terminalp); | |
780 | } else { | |
781 | OVS_NOT_REACHED(); | |
782 | } | |
783 | } | |
784 | ||
785 | static struct expr * | |
786 | build_tree_shape(enum expr_type type, const struct tree_shape **tsp, | |
787 | struct expr ***terminalp) | |
788 | { | |
789 | const struct tree_shape *ts = *tsp; | |
790 | (*tsp)++; | |
791 | ||
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)); | |
417e7e66 | 798 | ovs_list_push_back(&e->andor, &sub->node); |
e0840f11 BP |
799 | } |
800 | return e; | |
801 | } | |
802 | ||
803 | struct test_rule { | |
804 | struct cls_rule cr; | |
805 | }; | |
806 | ||
807 | static void | |
808 | free_rule(struct test_rule *test_rule) | |
809 | { | |
810 | cls_rule_destroy(&test_rule->cr); | |
811 | free(test_rule); | |
812 | } | |
813 | ||
ba8d3816 MS |
814 | static bool |
815 | tree_shape_is_chassis_resident_cb(const void *c_aux OVS_UNUSED, | |
816 | const char *port_name OVS_UNUSED) | |
817 | { | |
818 | return true; | |
819 | } | |
820 | ||
e0840f11 BP |
821 | static int |
822 | test_tree_shape_exhaustively(struct expr *expr, struct shash *symtab, | |
823 | struct expr *terminals[], int n_terminals, | |
9d4aecca BP |
824 | const struct expr_symbol *nvars[], int n_nvars, |
825 | int n_bits, | |
826 | const struct expr_symbol *svars[], int n_svars) | |
e0840f11 BP |
827 | { |
828 | int n_tested = 0; | |
829 | ||
830 | const unsigned int var_mask = (1u << n_bits) - 1; | |
831 | for (int i = 0; i < n_terminals; i++) { | |
9d4aecca | 832 | init_terminal(terminals[i], 0, nvars, n_nvars, svars, n_svars); |
e0840f11 BP |
833 | } |
834 | ||
835 | struct ds s = DS_EMPTY_INITIALIZER; | |
836 | struct flow f; | |
837 | memset(&f, 0, sizeof f); | |
838 | for (;;) { | |
839 | for (int i = n_terminals - 1; ; i--) { | |
840 | if (!i) { | |
841 | ds_destroy(&s); | |
842 | return n_tested; | |
843 | } | |
9d4aecca BP |
844 | if (next_terminal(terminals[i], nvars, n_nvars, n_bits, |
845 | svars, n_svars)) { | |
e0840f11 BP |
846 | break; |
847 | } | |
9d4aecca | 848 | init_terminal(terminals[i], 0, nvars, n_nvars, svars, n_svars); |
e0840f11 BP |
849 | } |
850 | ovs_assert(expr_honors_invariants(expr)); | |
851 | ||
852 | n_tested++; | |
853 | ||
854 | struct expr *modified; | |
855 | if (operation == OP_CONVERT) { | |
856 | ds_clear(&s); | |
857 | expr_format(expr, &s); | |
858 | ||
859 | char *error; | |
2c5cbb15 | 860 | modified = expr_parse_string(ds_cstr(&s), symtab, NULL, &error); |
e0840f11 BP |
861 | if (error) { |
862 | fprintf(stderr, "%s fails to parse (%s)\n", | |
863 | ds_cstr(&s), error); | |
864 | exit(EXIT_FAILURE); | |
865 | } | |
866 | } else if (operation >= OP_SIMPLIFY) { | |
ba8d3816 MS |
867 | modified = expr_simplify(expr_clone(expr), |
868 | tree_shape_is_chassis_resident_cb, | |
869 | NULL); | |
e0840f11 BP |
870 | ovs_assert(expr_honors_invariants(modified)); |
871 | ||
872 | if (operation >= OP_NORMALIZE) { | |
873 | modified = expr_normalize(modified); | |
eb202465 | 874 | ovs_assert(expr_honors_invariants(modified)); |
e0840f11 BP |
875 | ovs_assert(expr_is_normalized(modified)); |
876 | } | |
877 | } | |
878 | ||
879 | struct hmap matches; | |
880 | struct classifier cls; | |
881 | if (operation >= OP_FLOW) { | |
882 | struct expr_match *m; | |
883 | struct test_rule *test_rule; | |
e0840f11 | 884 | |
803a6f3d | 885 | expr_to_matches(modified, lookup_atoi_cb, NULL, &matches); |
e0840f11 BP |
886 | |
887 | classifier_init(&cls, NULL); | |
888 | HMAP_FOR_EACH (m, hmap_node, &matches) { | |
889 | test_rule = xmalloc(sizeof *test_rule); | |
bd53aa17 | 890 | cls_rule_init(&test_rule->cr, &m->match, 0); |
44e0c35d | 891 | classifier_insert(&cls, &test_rule->cr, OVS_VERSION_MIN, |
bd53aa17 | 892 | m->conjunctions, m->n); |
e0840f11 | 893 | } |
e0840f11 | 894 | } |
9d4aecca BP |
895 | for (int subst = 0; subst < 1 << (n_bits * n_nvars + n_svars); |
896 | subst++) { | |
803a6f3d BP |
897 | for (int i = 0; i < n_nvars; i++) { |
898 | f.regs[i] = (subst >> (i * n_bits)) & var_mask; | |
899 | } | |
900 | for (int i = 0; i < n_svars; i++) { | |
901 | f.regs[n_nvars + i] = ((subst >> (n_nvars * n_bits + i)) | |
902 | & 1); | |
903 | } | |
904 | ||
905 | bool expected = expr_evaluate(expr, &f, lookup_atoi_cb, NULL); | |
906 | bool actual = expr_evaluate(modified, &f, lookup_atoi_cb, NULL); | |
e0840f11 BP |
907 | if (actual != expected) { |
908 | struct ds expr_s, modified_s; | |
909 | ||
910 | ds_init(&expr_s); | |
911 | expr_format(expr, &expr_s); | |
912 | ||
913 | ds_init(&modified_s); | |
914 | expr_format(modified, &modified_s); | |
915 | ||
916 | fprintf(stderr, | |
917 | "%s evaluates to %d, but %s evaluates to %d, for", | |
918 | ds_cstr(&expr_s), expected, | |
919 | ds_cstr(&modified_s), actual); | |
9d4aecca | 920 | for (int i = 0; i < n_nvars; i++) { |
e0840f11 BP |
921 | if (i > 0) { |
922 | fputs(",", stderr); | |
923 | } | |
9d4aecca | 924 | fprintf(stderr, " n%d = 0x%x", i, |
e0840f11 BP |
925 | (subst >> (n_bits * i)) & var_mask); |
926 | } | |
9d4aecca BP |
927 | for (int i = 0; i < n_svars; i++) { |
928 | fprintf(stderr, ", s%d = \"%d\"", i, | |
929 | (subst >> (n_bits * n_nvars + i)) & 1); | |
930 | } | |
e0840f11 BP |
931 | putc('\n', stderr); |
932 | exit(EXIT_FAILURE); | |
933 | } | |
934 | ||
935 | if (operation >= OP_FLOW) { | |
44e0c35d | 936 | bool found = classifier_lookup(&cls, OVS_VERSION_MIN, |
03ce866e | 937 | &f, NULL) != NULL; |
e0840f11 BP |
938 | if (expected != found) { |
939 | struct ds expr_s, modified_s; | |
940 | ||
941 | ds_init(&expr_s); | |
942 | expr_format(expr, &expr_s); | |
943 | ||
944 | ds_init(&modified_s); | |
945 | expr_format(modified, &modified_s); | |
946 | ||
947 | fprintf(stderr, | |
948 | "%s and %s evaluate to %d, for", | |
949 | ds_cstr(&expr_s), ds_cstr(&modified_s), expected); | |
9d4aecca | 950 | for (int i = 0; i < n_nvars; i++) { |
e0840f11 BP |
951 | if (i > 0) { |
952 | fputs(",", stderr); | |
953 | } | |
9d4aecca | 954 | fprintf(stderr, " n%d = 0x%x", i, |
e0840f11 BP |
955 | (subst >> (n_bits * i)) & var_mask); |
956 | } | |
9d4aecca BP |
957 | for (int i = 0; i < n_svars; i++) { |
958 | fprintf(stderr, ", s%d = \"%d\"", i, | |
959 | (subst >> (n_bits * n_nvars + i)) & 1); | |
960 | } | |
e0840f11 BP |
961 | fputs(".\n", stderr); |
962 | ||
963 | fprintf(stderr, "Converted to classifier:\n"); | |
f386a8a7 | 964 | expr_matches_print(&matches, stderr); |
e0840f11 BP |
965 | fprintf(stderr, |
966 | "However, %s flow was found in the classifier.\n", | |
967 | found ? "a" : "no"); | |
968 | exit(EXIT_FAILURE); | |
969 | } | |
970 | } | |
971 | } | |
972 | if (operation >= OP_FLOW) { | |
e0840f11 BP |
973 | struct test_rule *test_rule; |
974 | ||
975 | CLS_FOR_EACH (test_rule, cr, &cls) { | |
46ab60bf | 976 | classifier_remove_assert(&cls, &test_rule->cr); |
e0840f11 BP |
977 | ovsrcu_postpone(free_rule, test_rule); |
978 | } | |
979 | classifier_destroy(&cls); | |
980 | ovsrcu_quiesce(); | |
981 | ||
f386a8a7 | 982 | expr_matches_destroy(&matches); |
e0840f11 BP |
983 | } |
984 | expr_destroy(modified); | |
985 | } | |
986 | } | |
987 | ||
988 | #ifndef _WIN32 | |
989 | static void | |
990 | wait_pid(pid_t *pids, int *n) | |
991 | { | |
992 | int status; | |
993 | pid_t pid; | |
994 | ||
0c36c1e5 | 995 | pid = waitpid(-1, &status, 0); |
e0840f11 BP |
996 | if (pid < 0) { |
997 | ovs_fatal(errno, "waitpid failed"); | |
998 | } else if (WIFEXITED(status)) { | |
999 | if (WEXITSTATUS(status)) { | |
1000 | exit(WEXITSTATUS(status)); | |
1001 | } | |
1002 | } else if (WIFSIGNALED(status)) { | |
1003 | raise(WTERMSIG(status)); | |
1004 | exit(1); | |
1005 | } else { | |
1006 | OVS_NOT_REACHED(); | |
1007 | } | |
1008 | ||
1009 | for (int i = 0; i < *n; i++) { | |
1010 | if (pids[i] == pid) { | |
1011 | pids[i] = pids[--*n]; | |
1012 | return; | |
1013 | } | |
1014 | } | |
1015 | ovs_fatal(0, "waitpid returned unknown child"); | |
1016 | } | |
1017 | #endif | |
1018 | ||
1019 | static void | |
1020 | test_exhaustive(struct ovs_cmdl_context *ctx OVS_UNUSED) | |
1021 | { | |
1022 | int n_terminals = atoi(ctx->argv[1]); | |
1023 | struct tree_shape ts[50]; | |
1024 | int n_tses; | |
1025 | ||
1026 | struct shash symtab; | |
9d4aecca BP |
1027 | const struct expr_symbol *nvars[4]; |
1028 | const struct expr_symbol *svars[4]; | |
e0840f11 | 1029 | |
9d4aecca BP |
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); | |
e0840f11 BP |
1033 | |
1034 | shash_init(&symtab); | |
9d4aecca BP |
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, | |
1038 | false); | |
1039 | free(name); | |
1040 | } | |
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); | |
1045 | free(name); | |
e0840f11 BP |
1046 | } |
1047 | ||
1048 | #ifndef _WIN32 | |
1049 | pid_t *children = xmalloc(test_parallel * sizeof *children); | |
1050 | int n_children = 0; | |
1051 | #endif | |
1052 | ||
1053 | int n_tested = 0; | |
1054 | for (int i = 0; i < 2; i++) { | |
1055 | enum expr_type base_type = i ? EXPR_T_OR : EXPR_T_AND; | |
1056 | ||
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]); | |
1064 | ||
1065 | if (verbosity > 0) { | |
1066 | print_tree_shape(ts, n_tses); | |
1067 | printf(": "); | |
1068 | struct ds s = DS_EMPTY_INITIALIZER; | |
1069 | expr_format(expr, &s); | |
1070 | puts(ds_cstr(&s)); | |
1071 | ds_destroy(&s); | |
1072 | } | |
1073 | ||
1074 | #ifndef _WIN32 | |
1075 | if (test_parallel > 1) { | |
1076 | pid_t pid = xfork(); | |
1077 | if (!pid) { | |
1078 | test_tree_shape_exhaustively(expr, &symtab, | |
1079 | terminals, n_terminals, | |
9d4aecca BP |
1080 | nvars, test_nvars, test_bits, |
1081 | svars, test_svars); | |
e0840f11 BP |
1082 | expr_destroy(expr); |
1083 | exit(0); | |
1084 | } else { | |
1085 | if (n_children >= test_parallel) { | |
1086 | wait_pid(children, &n_children); | |
1087 | } | |
1088 | children[n_children++] = pid; | |
1089 | } | |
1090 | } else | |
1091 | #endif | |
1092 | { | |
1093 | n_tested += test_tree_shape_exhaustively( | |
1094 | expr, &symtab, terminals, n_terminals, | |
9d4aecca BP |
1095 | nvars, test_nvars, test_bits, |
1096 | svars, test_svars); | |
e0840f11 BP |
1097 | } |
1098 | expr_destroy(expr); | |
1099 | } | |
1100 | } | |
1101 | #ifndef _WIN32 | |
1102 | while (n_children > 0) { | |
1103 | wait_pid(children, &n_children); | |
1104 | } | |
1105 | free(children); | |
1106 | #endif | |
1107 | ||
1108 | printf("Tested "); | |
1109 | switch (operation) { | |
1110 | case OP_CONVERT: | |
1111 | printf("converting"); | |
1112 | break; | |
1113 | case OP_SIMPLIFY: | |
1114 | printf("simplifying"); | |
1115 | break; | |
1116 | case OP_NORMALIZE: | |
1117 | printf("normalizing"); | |
1118 | break; | |
1119 | case OP_FLOW: | |
1120 | printf("converting to flows"); | |
1121 | break; | |
1122 | } | |
1123 | if (n_tested) { | |
1124 | printf(" %d expressions of %d terminals", n_tested, n_terminals); | |
1125 | } else { | |
1126 | printf(" all %d-terminal expressions", n_terminals); | |
1127 | } | |
9d4aecca BP |
1128 | if (test_nvars || test_svars) { |
1129 | printf(" with"); | |
1130 | if (test_nvars) { | |
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)); | |
1137 | } | |
1138 | } | |
1139 | if (test_nvars && test_svars) { | |
1140 | printf (" and"); | |
1141 | } | |
1142 | if (test_svars) { | |
1143 | printf(" %d string vars", test_svars); | |
1144 | } | |
1145 | } else { | |
1146 | printf(" in terms of Boolean constants only"); | |
e0840f11 BP |
1147 | } |
1148 | printf(".\n"); | |
1149 | ||
1150 | expr_symtab_destroy(&symtab); | |
1151 | shash_destroy(&symtab); | |
1152 | } | |
1e028b17 JP |
1153 | |
1154 | static void | |
1155 | test_expr_to_packets(struct ovs_cmdl_context *ctx OVS_UNUSED) | |
1156 | { | |
1157 | struct shash symtab; | |
1158 | struct ds input; | |
1159 | ||
1160 | create_symtab(&symtab); | |
1161 | ||
1162 | ds_init(&input); | |
1163 | while (!ds_get_test_line(&input, stdin)) { | |
1164 | struct flow uflow; | |
1165 | char *error = expr_parse_microflow(ds_cstr(&input), &symtab, NULL, | |
1166 | lookup_atoi_cb, NULL, &uflow); | |
1167 | if (error) { | |
1168 | puts(error); | |
1169 | free(error); | |
1170 | continue; | |
1171 | } | |
1172 | ||
1173 | uint64_t packet_stub[128 / 8]; | |
1174 | struct dp_packet packet; | |
1175 | dp_packet_use_stub(&packet, packet_stub, sizeof packet_stub); | |
6f068379 | 1176 | flow_compose(&packet, &uflow, NULL, 64); |
1e028b17 JP |
1177 | |
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); | |
1183 | } | |
1184 | puts(ds_cstr(&output)); | |
1185 | ds_destroy(&output); | |
1186 | ||
1187 | dp_packet_uninit(&packet); | |
1188 | } | |
1189 | ds_destroy(&input); | |
1190 | ||
1191 | expr_symtab_destroy(&symtab); | |
1192 | shash_destroy(&symtab); | |
1193 | } | |
e0840f11 | 1194 | \f |
3b7cb7e1 BP |
1195 | /* Actions. */ |
1196 | ||
1197 | static void | |
1198 | test_parse_actions(struct ovs_cmdl_context *ctx OVS_UNUSED) | |
1199 | { | |
1200 | struct shash symtab; | |
42814145 | 1201 | struct hmap dhcp_opts; |
01cfdb2f | 1202 | struct hmap dhcpv6_opts; |
52ed5fcc | 1203 | struct hmap nd_ra_opts; |
1e31e242 | 1204 | struct simap ports; |
3b7cb7e1 | 1205 | struct ds input; |
d5a76da4 | 1206 | bool ok = true; |
3b7cb7e1 BP |
1207 | |
1208 | create_symtab(&symtab); | |
52ed5fcc | 1209 | create_gen_opts(&dhcp_opts, &dhcpv6_opts, &nd_ra_opts); |
3b7cb7e1 | 1210 | |
467085fd | 1211 | /* Initialize group ids. */ |
ad35c0c5 GL |
1212 | struct ovn_extend_table group_table; |
1213 | ovn_extend_table_init(&group_table); | |
467085fd | 1214 | |
66d89287 GL |
1215 | /* Initialize meter ids for QoS. */ |
1216 | struct ovn_extend_table meter_table; | |
1217 | ovn_extend_table_init(&meter_table); | |
1218 | ||
3b7cb7e1 BP |
1219 | simap_init(&ports); |
1220 | simap_put(&ports, "eth0", 5); | |
1221 | simap_put(&ports, "eth1", 6); | |
1222 | simap_put(&ports, "LOCAL", ofp_to_u16(OFPP_LOCAL)); | |
1223 | ||
1224 | ds_init(&input); | |
1225 | while (!ds_get_test_line(&input, stdin)) { | |
d5a76da4 | 1226 | struct ofpbuf ovnacts; |
3b7cb7e1 BP |
1227 | struct expr *prereqs; |
1228 | char *error; | |
1229 | ||
d5a76da4 | 1230 | puts(ds_cstr(&input)); |
1d7b2ece | 1231 | |
d5a76da4 BP |
1232 | ofpbuf_init(&ovnacts, 0); |
1233 | ||
1234 | const struct ovnact_parse_params pp = { | |
1d7b2ece | 1235 | .symtab = &symtab, |
42814145 | 1236 | .dhcp_opts = &dhcp_opts, |
01cfdb2f | 1237 | .dhcpv6_opts = &dhcpv6_opts, |
52ed5fcc | 1238 | .nd_ra_opts = &nd_ra_opts, |
00c875d0 | 1239 | .n_tables = 24, |
1d7b2ece | 1240 | .cur_ltable = 10, |
1d7b2ece | 1241 | }; |
d5a76da4 | 1242 | error = ovnacts_parse_string(ds_cstr(&input), &pp, &ovnacts, &prereqs); |
3b7cb7e1 | 1243 | if (!error) { |
d5a76da4 BP |
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)); | |
1250 | } | |
3b7cb7e1 | 1251 | |
d5a76da4 BP |
1252 | /* Encode the actions into OpenFlow and print. */ |
1253 | const struct ovnact_encode_params ep = { | |
1254 | .lookup_port = lookup_port_cb, | |
1255 | .aux = &ports, | |
c2e954a1 | 1256 | .is_switch = true, |
d5a76da4 | 1257 | .group_table = &group_table, |
66d89287 | 1258 | .meter_table = &meter_table, |
d5a76da4 | 1259 | |
4c99cb18 | 1260 | .pipeline = OVNACT_P_INGRESS, |
00c875d0 MS |
1261 | .ingress_ptable = 8, |
1262 | .egress_ptable = 40, | |
d5a76da4 BP |
1263 | .output_ptable = 64, |
1264 | .mac_bind_ptable = 65, | |
1265 | }; | |
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; | |
efefbcae BP |
1270 | struct ofpact_format_params fp = { .s = &ofpacts_s }; |
1271 | ofpacts_format(ofpacts.data, ofpacts.size, &fp); | |
d5a76da4 BP |
1272 | printf(" encodes as %s\n", ds_cstr(&ofpacts_s)); |
1273 | ds_destroy(&ofpacts_s); | |
1274 | ofpbuf_uninit(&ofpacts); | |
1275 | ||
1276 | /* Print prerequisites if any. */ | |
3b7cb7e1 | 1277 | if (prereqs) { |
d5a76da4 BP |
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); | |
1282 | } | |
1283 | ||
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, | |
1290 | &prereqs2); | |
1291 | if (!error) { | |
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)); | |
1296 | ok = false; | |
1297 | } | |
1298 | ds_destroy(&ovnacts2_s); | |
3b7cb7e1 | 1299 | } else { |
d5a76da4 BP |
1300 | printf(" reparse error: %s\n", error); |
1301 | free(error); | |
1302 | ok = false; | |
3b7cb7e1 | 1303 | } |
d5a76da4 BP |
1304 | expr_destroy(prereqs2); |
1305 | ||
85d87d16 RM |
1306 | ovnacts_free(ovnacts2.data, ovnacts2.size); |
1307 | ofpbuf_uninit(&ovnacts2); | |
d5a76da4 | 1308 | ds_destroy(&ovnacts_s); |
3b7cb7e1 | 1309 | } else { |
d5a76da4 | 1310 | printf(" %s\n", error); |
3b7cb7e1 BP |
1311 | free(error); |
1312 | } | |
1313 | ||
1314 | expr_destroy(prereqs); | |
85d87d16 | 1315 | ovnacts_free(ovnacts.data, ovnacts.size); |
d5a76da4 | 1316 | ofpbuf_uninit(&ovnacts); |
3b7cb7e1 BP |
1317 | } |
1318 | ds_destroy(&input); | |
1319 | ||
1320 | simap_destroy(&ports); | |
1321 | expr_symtab_destroy(&symtab); | |
1322 | shash_destroy(&symtab); | |
01cfdb2f NS |
1323 | dhcp_opts_destroy(&dhcp_opts); |
1324 | dhcp_opts_destroy(&dhcpv6_opts); | |
52ed5fcc | 1325 | nd_ra_opts_destroy(&nd_ra_opts); |
d5a76da4 | 1326 | exit(ok ? EXIT_SUCCESS : EXIT_FAILURE); |
3b7cb7e1 BP |
1327 | } |
1328 | \f | |
e0840f11 BP |
1329 | static unsigned int |
1330 | parse_relops(const char *s) | |
1331 | { | |
1332 | unsigned int relops = 0; | |
1333 | struct lexer lexer; | |
1334 | ||
1335 | lexer_init(&lexer, s); | |
1336 | lexer_get(&lexer); | |
1337 | do { | |
1338 | enum expr_relop relop; | |
1339 | ||
1340 | if (expr_relop_from_token(lexer.token.type, &relop)) { | |
1341 | relops |= 1u << relop; | |
1342 | lexer_get(&lexer); | |
1343 | } else { | |
1344 | ovs_fatal(0, "%s: relational operator expected at `%.*s'", | |
1345 | s, (int) (lexer.input - lexer.start), lexer.start); | |
1346 | } | |
1347 | lexer_match(&lexer, LEX_T_COMMA); | |
1348 | } while (lexer.token.type != LEX_T_END); | |
1349 | lexer_destroy(&lexer); | |
1350 | ||
1351 | return relops; | |
1352 | } | |
1353 | ||
1354 | static void | |
1355 | usage(void) | |
1356 | { | |
1357 | printf("\ | |
1358 | %s: OVN test utility\n\ | |
1359 | usage: test-ovn %s [OPTIONS] COMMAND [ARG...]\n\ | |
1360 | \n\ | |
1361 | lex\n\ | |
1362 | Lexically analyzes OVN input from stdin and print them back on stdout.\n\ | |
1363 | \n\ | |
1364 | parse-expr\n\ | |
1365 | annotate-expr\n\ | |
1366 | simplify-expr\n\ | |
1367 | normalize-expr\n\ | |
f386a8a7 | 1368 | expr-to-flows\n\ |
1e028b17 | 1369 | Parses OVN expressions from stdin and prints them back on stdout after\n\ |
e0840f11 BP |
1370 | differing degrees of analysis. Available fields are based on packet\n\ |
1371 | headers.\n\ | |
1372 | \n\ | |
1e028b17 JP |
1373 | expr-to-packets\n\ |
1374 | Parses OVN expressions from stdin and prints out matching packets in\n\ | |
1375 | hexadecimal on stdout.\n\ | |
1376 | \n\ | |
d5b33279 BP |
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\ | |
1383 | \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\ | |
e0840f11 BP |
1387 | \n\ |
1388 | composition N\n\ | |
1389 | Prints all the compositions of N on stdout.\n\ | |
1390 | \n\ | |
1391 | tree-shape N\n\ | |
1392 | Prints all the tree shapes with N terminals on stdout.\n\ | |
1393 | \n\ | |
1394 | exhaustive N\n\ | |
1395 | Tests that all possible Boolean expressions with N terminals are properly\n\ | |
1396 | simplified, normalized, and converted to flows. Available options:\n\ | |
9d4aecca | 1397 | Overall options:\n\ |
e0840f11 BP |
1398 | --operation=OPERATION Operation to test, one of: convert, simplify,\n\ |
1399 | normalize, flow. Default: flow. 'normalize' includes 'simplify',\n\ | |
9d4aecca | 1400 | 'flow' includes 'simplify' and 'normalize'.\n\ |
e0840f11 | 1401 | --parallel=N Number of processes to use in parallel, default 1.\n\ |
9d4aecca BP |
1402 | Numeric vars:\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\ | |
1408 | String vars:\n\ | |
1409 | --svars=N Number of string vars to test, in range 0...4, default 2.\n\ | |
caff23ca BP |
1410 | \n\ |
1411 | parse-actions\n\ | |
1412 | Parses OVN actions from stdin and prints the equivalent OpenFlow actions\n\ | |
1413 | on stdout.\n\ | |
e0840f11 BP |
1414 | ", |
1415 | program_name, program_name); | |
1416 | exit(EXIT_SUCCESS); | |
1417 | } | |
1418 | ||
10b1662b BP |
1419 | static void |
1420 | test_ovn_main(int argc, char *argv[]) | |
1421 | { | |
9d4aecca BP |
1422 | enum { |
1423 | OPT_RELOPS = UCHAR_MAX + 1, | |
1424 | OPT_NVARS, | |
1425 | OPT_SVARS, | |
1426 | OPT_BITS, | |
1427 | OPT_OPERATION, | |
1428 | OPT_PARALLEL | |
1429 | }; | |
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'}, | |
1439 | {NULL, 0, NULL, 0}, | |
1440 | }; | |
1441 | char *short_options = ovs_cmdl_long_options_to_short_options(long_options); | |
1442 | ||
10b1662b BP |
1443 | set_program_name(argv[0]); |
1444 | ||
e0840f11 BP |
1445 | test_relops = parse_relops("== != < <= > >="); |
1446 | for (;;) { | |
e0840f11 | 1447 | int option_index = 0; |
9d4aecca BP |
1448 | int c = getopt_long (argc, argv, short_options, long_options, |
1449 | &option_index); | |
e0840f11 BP |
1450 | |
1451 | if (c == -1) { | |
1452 | break; | |
1453 | } | |
1454 | switch (c) { | |
1455 | case OPT_RELOPS: | |
1456 | test_relops = parse_relops(optarg); | |
1457 | break; | |
1458 | ||
9d4aecca BP |
1459 | case OPT_NVARS: |
1460 | test_nvars = atoi(optarg); | |
1461 | if (test_nvars < 0 || test_nvars > 4) { | |
1462 | ovs_fatal(0, "number of numeric variables must be " | |
1463 | "between 0 and 4"); | |
1464 | } | |
1465 | break; | |
1466 | ||
1467 | case OPT_SVARS: | |
1468 | test_svars = atoi(optarg); | |
1469 | if (test_svars < 0 || test_svars > 4) { | |
1470 | ovs_fatal(0, "number of string variables must be " | |
1471 | "between 0 and 4"); | |
e0840f11 BP |
1472 | } |
1473 | break; | |
1474 | ||
1475 | case OPT_BITS: | |
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"); | |
1479 | } | |
1480 | break; | |
1481 | ||
1482 | case OPT_OPERATION: | |
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; | |
1491 | } else { | |
1492 | ovs_fatal(0, "%s: unknown operation", optarg); | |
1493 | } | |
1494 | break; | |
1495 | ||
1496 | case OPT_PARALLEL: | |
1497 | test_parallel = atoi(optarg); | |
1498 | break; | |
1499 | ||
1500 | case 'm': | |
1501 | verbosity++; | |
1502 | break; | |
1503 | ||
1504 | case 'h': | |
1505 | usage(); | |
73c7216a | 1506 | /* fall through */ |
e0840f11 BP |
1507 | |
1508 | case '?': | |
1509 | exit(1); | |
1510 | ||
1511 | default: | |
1512 | abort(); | |
1513 | } | |
1514 | } | |
d2730f4c | 1515 | free(short_options); |
e0840f11 | 1516 | |
10b1662b | 1517 | static const struct ovs_cmdl_command commands[] = { |
3b7cb7e1 | 1518 | /* Lexer. */ |
1f4a7252 | 1519 | {"lex", NULL, 0, 0, test_lex, OVS_RO}, |
3b7cb7e1 | 1520 | |
7700eea0 | 1521 | /* Symbol table. */ |
1f4a7252 | 1522 | {"dump-symtab", NULL, 0, 0, test_dump_symtab, OVS_RO}, |
7700eea0 | 1523 | |
3b7cb7e1 | 1524 | /* Expressions. */ |
1f4a7252 RM |
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}, | |
1e028b17 | 1534 | {"expr-to-packets", NULL, 0, 0, test_expr_to_packets, OVS_RO}, |
3b7cb7e1 BP |
1535 | |
1536 | /* Actions. */ | |
1f4a7252 | 1537 | {"parse-actions", NULL, 0, 0, test_parse_actions, OVS_RO}, |
3b7cb7e1 | 1538 | |
1f4a7252 | 1539 | {NULL, NULL, 0, 0, NULL, OVS_RO}, |
10b1662b BP |
1540 | }; |
1541 | struct ovs_cmdl_context ctx; | |
1542 | ctx.argc = argc - optind; | |
1543 | ctx.argv = argv + optind; | |
1544 | ovs_cmdl_run_command(&ctx, commands); | |
1545 | } | |
1546 | ||
1547 | OVSTEST_REGISTER("test-ovn", test_ovn_main); |