Branch data Line data Source code
1 : : /*
2 : : * Copyright (c) 2015, 2016 Nicira, Inc.
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>
18 : : #include <errno.h>
19 : : #include <getopt.h>
20 : : #include <sys/wait.h>
21 : : #include "command-line.h"
22 : : #include "fatal-signal.h"
23 : : #include "flow.h"
24 : : #include "openvswitch/dynamic-string.h"
25 : : #include "openvswitch/match.h"
26 : : #include "openvswitch/ofp-actions.h"
27 : : #include "openvswitch/ofpbuf.h"
28 : : #include "openvswitch/vlog.h"
29 : : #include "ovn/actions.h"
30 : : #include "ovn/expr.h"
31 : : #include "ovn/lex.h"
32 : : #include "ovn/lib/logical-fields.h"
33 : : #include "ovn/lib/ovn-dhcp.h"
34 : : #include "ovs-thread.h"
35 : : #include "ovstest.h"
36 : : #include "openvswitch/shash.h"
37 : : #include "simap.h"
38 : : #include "util.h"
39 : :
40 : : /* --relops: Bitmap of the relational operators to test, in exhaustive test. */
41 : : static unsigned int test_relops;
42 : :
43 : : /* --nvars: Number of numeric variables to test, in exhaustive test. */
44 : : static int test_nvars = 2;
45 : :
46 : : /* --svars: Number of string variables to test, in exhaustive test. */
47 : : static int test_svars = 2;
48 : :
49 : : /* --bits: Number of bits per variable, in exhaustive test. */
50 : : static int test_bits = 3;
51 : :
52 : : /* --operation: The operation to test, in exhaustive test. */
53 : : static enum { OP_CONVERT, OP_SIMPLIFY, OP_NORMALIZE, OP_FLOW } operation
54 : : = OP_FLOW;
55 : :
56 : : /* --parallel: Number of parallel processes to use in test. */
57 : : static int test_parallel = 1;
58 : :
59 : : /* -m, --more: Message verbosity */
60 : : static int verbosity;
61 : :
62 : : static void
63 : 101 : compare_token(const struct lex_token *a, const struct lex_token *b)
64 : : {
65 [ - + ]: 101 : if (a->type != b->type) {
66 : 0 : fprintf(stderr, "type differs: %d -> %d\n", a->type, b->type);
67 : 0 : return;
68 : : }
69 : :
70 [ + + ][ + - ]: 101 : if (!((a->s && b->s && !strcmp(a->s, b->s))
[ - + ][ + - ]
71 [ - + ]: 76 : || (!a->s && !b->s))) {
72 [ # # ][ # # ]: 0 : fprintf(stderr, "string differs: %s -> %s\n",
73 : 0 : a->s ? a->s : "(null)",
74 : 0 : b->s ? b->s : "(null)");
75 : 0 : return;
76 : : }
77 : :
78 [ + + ][ + + ]: 101 : if (a->type == LEX_T_INTEGER || a->type == LEX_T_MASKED_INTEGER) {
79 [ - + ]: 53 : if (memcmp(&a->value, &b->value, sizeof a->value)) {
80 : 0 : fprintf(stderr, "value differs\n");
81 : 0 : return;
82 : : }
83 : :
84 [ + + ]: 53 : if (a->type == LEX_T_MASKED_INTEGER
85 [ - + ]: 22 : && memcmp(&a->mask, &b->mask, sizeof a->mask)) {
86 : 0 : fprintf(stderr, "mask differs\n");
87 : 0 : return;
88 : : }
89 : :
90 [ + + ]: 53 : if (a->format != b->format
91 [ + - ][ - + ]: 6 : && !(a->format == LEX_F_HEXADECIMAL
92 [ + - ]: 3 : && b->format == LEX_F_DECIMAL
93 : 3 : && a->value.integer == 0)) {
94 : 0 : fprintf(stderr, "format differs: %d -> %d\n",
95 : 0 : a->format, b->format);
96 : : }
97 : : }
98 : : }
99 : :
100 : : static void
101 : 1 : test_lex(struct ovs_cmdl_context *ctx OVS_UNUSED)
102 : : {
103 : : struct ds input;
104 : : struct ds output;
105 : :
106 : 1 : ds_init(&input);
107 : 1 : ds_init(&output);
108 [ + + ]: 77 : while (!ds_get_test_line(&input, stdin)) {
109 : : struct lexer lexer;
110 : :
111 : 76 : lexer_init(&lexer, ds_cstr(&input));
112 : 76 : ds_clear(&output);
113 [ + + ]: 200 : while (lexer_get(&lexer) != LEX_T_END) {
114 : 124 : size_t len = output.length;
115 : 124 : lex_token_format(&lexer.token, &output);
116 : :
117 : : /* Check that the formatted version can really be parsed back
118 : : * losslessly. */
119 [ + + ]: 124 : if (lexer.token.type != LEX_T_ERROR) {
120 : 101 : const char *s = ds_cstr(&output) + len;
121 : : struct lexer l2;
122 : :
123 : 101 : lexer_init(&l2, s);
124 : 101 : lexer_get(&l2);
125 : 101 : compare_token(&lexer.token, &l2.token);
126 : 101 : lexer_destroy(&l2);
127 : : }
128 : 124 : ds_put_char(&output, ' ');
129 : : }
130 : 76 : lexer_destroy(&lexer);
131 : :
132 : 76 : ds_chomp(&output, ' ');
133 : 76 : puts(ds_cstr(&output));
134 : : }
135 : 1 : ds_destroy(&input);
136 : 1 : ds_destroy(&output);
137 : 1 : }
138 : :
139 : : static void
140 : 23 : create_symtab(struct shash *symtab)
141 : : {
142 : 23 : ovn_init_symtab(symtab);
143 : :
144 : : /* For negative testing. */
145 : 23 : expr_symtab_add_field(symtab, "bad_prereq", MFF_XREG0, "xyzzy", false);
146 : 23 : expr_symtab_add_field(symtab, "self_recurse", MFF_XREG0,
147 : : "self_recurse != 0", false);
148 : 23 : expr_symtab_add_field(symtab, "mutual_recurse_1", MFF_XREG0,
149 : : "mutual_recurse_2 != 0", false);
150 : 23 : expr_symtab_add_field(symtab, "mutual_recurse_2", MFF_XREG0,
151 : : "mutual_recurse_1 != 0", false);
152 : 23 : expr_symtab_add_string(symtab, "big_string", MFF_XREG0, NULL);
153 : 23 : }
154 : :
155 : : static void
156 : 1 : create_dhcp_opts(struct hmap *dhcp_opts, struct hmap *dhcpv6_opts)
157 : : {
158 : 1 : hmap_init(dhcp_opts);
159 : 1 : dhcp_opt_add(dhcp_opts, "offerip", 0, "ipv4");
160 : 1 : dhcp_opt_add(dhcp_opts, "netmask", 1, "ipv4");
161 : 1 : dhcp_opt_add(dhcp_opts, "router", 3, "ipv4");
162 : 1 : dhcp_opt_add(dhcp_opts, "dns_server", 6, "ipv4");
163 : 1 : dhcp_opt_add(dhcp_opts, "log_server", 7, "ipv4");
164 : 1 : dhcp_opt_add(dhcp_opts, "lpr_server", 9, "ipv4");
165 : 1 : dhcp_opt_add(dhcp_opts, "domain", 15, "str");
166 : 1 : dhcp_opt_add(dhcp_opts, "swap_server", 16, "ipv4");
167 : 1 : dhcp_opt_add(dhcp_opts, "policy_filter", 21, "ipv4");
168 : 1 : dhcp_opt_add(dhcp_opts, "router_solicitation", 32, "ipv4");
169 : 1 : dhcp_opt_add(dhcp_opts, "nis_server", 41, "ipv4");
170 : 1 : dhcp_opt_add(dhcp_opts, "ntp_server", 42, "ipv4");
171 : 1 : dhcp_opt_add(dhcp_opts, "server_id", 54, "ipv4");
172 : 1 : dhcp_opt_add(dhcp_opts, "tftp_server", 66, "ipv4");
173 : 1 : dhcp_opt_add(dhcp_opts, "classless_static_route", 121, "static_routes");
174 : 1 : dhcp_opt_add(dhcp_opts, "ip_forward_enable", 19, "bool");
175 : 1 : dhcp_opt_add(dhcp_opts, "router_discovery", 31, "bool");
176 : 1 : dhcp_opt_add(dhcp_opts, "ethernet_encap", 36, "bool");
177 : 1 : dhcp_opt_add(dhcp_opts, "default_ttl", 23, "uint8");
178 : 1 : dhcp_opt_add(dhcp_opts, "tcp_ttl", 37, "uint8");
179 : 1 : dhcp_opt_add(dhcp_opts, "mtu", 26, "uint16");
180 : 1 : dhcp_opt_add(dhcp_opts, "lease_time", 51, "uint32");
181 : :
182 : : /* DHCPv6 options. */
183 : 1 : hmap_init(dhcpv6_opts);
184 : 1 : dhcp_opt_add(dhcpv6_opts, "server_id", 2, "mac");
185 : 1 : dhcp_opt_add(dhcpv6_opts, "ia_addr", 5, "ipv6");
186 : 1 : dhcp_opt_add(dhcpv6_opts, "dns_server", 23, "ipv6");
187 : 1 : dhcp_opt_add(dhcpv6_opts, "domain_search", 24, "str");
188 : 1 : }
189 : :
190 : : static void
191 : 20 : create_macros(struct shash *macros)
192 : : {
193 : 20 : shash_init(macros);
194 : :
195 : : static const char *const addrs1[] = {
196 : : "10.0.0.1", "10.0.0.2", "10.0.0.3",
197 : : };
198 : : static const char *const addrs2[] = {
199 : : "::1", "::2", "::3",
200 : : };
201 : : static const char *const addrs3[] = {
202 : : "00:00:00:00:00:01", "00:00:00:00:00:02", "00:00:00:00:00:03",
203 : : };
204 : :
205 : 20 : expr_macros_add(macros, "set1", addrs1, 3);
206 : 20 : expr_macros_add(macros, "set2", addrs2, 3);
207 : 20 : expr_macros_add(macros, "set3", addrs3, 3);
208 : 20 : }
209 : :
210 : : static bool
211 : 23 : lookup_port_cb(const void *ports_, const char *port_name, unsigned int *portp)
212 : : {
213 : 23 : const struct simap *ports = ports_;
214 : 23 : const struct simap_node *node = simap_find(ports, port_name);
215 [ + + ]: 23 : if (!node) {
216 : 8 : return false;
217 : : }
218 : 15 : *portp = node->data;
219 : 15 : return true;
220 : : }
221 : :
222 : : static void
223 : 20 : test_parse_expr__(int steps)
224 : : {
225 : : struct shash symtab;
226 : : struct shash macros;
227 : : struct simap ports;
228 : : struct ds input;
229 : :
230 : 20 : create_symtab(&symtab);
231 : 20 : create_macros(¯os);
232 : :
233 : 20 : simap_init(&ports);
234 : 20 : simap_put(&ports, "eth0", 5);
235 : 20 : simap_put(&ports, "eth1", 6);
236 : 20 : simap_put(&ports, "LOCAL", ofp_to_u16(OFPP_LOCAL));
237 : :
238 : 20 : ds_init(&input);
239 [ + + ]: 188 : while (!ds_get_test_line(&input, stdin)) {
240 : : struct expr *expr;
241 : : char *error;
242 : :
243 : 168 : expr = expr_parse_string(ds_cstr(&input), &symtab, ¯os, &error);
244 [ + + ][ + + ]: 168 : if (!error && steps > 0) {
245 : 38 : expr = expr_annotate(expr, &symtab, &error);
246 : : }
247 [ + + ]: 168 : if (!error) {
248 [ + + ]: 122 : if (steps > 1) {
249 : 18 : expr = expr_simplify(expr);
250 : : }
251 [ + + ]: 122 : if (steps > 2) {
252 : 18 : expr = expr_normalize(expr);
253 [ - + ]: 18 : ovs_assert(expr_is_normalized(expr));
254 : : }
255 : : }
256 [ + + ]: 168 : if (!error) {
257 [ + + ]: 122 : if (steps > 3) {
258 : : struct hmap matches;
259 : :
260 : 18 : expr_to_matches(expr, lookup_port_cb, &ports, &matches);
261 : 18 : expr_matches_print(&matches, stdout);
262 : 18 : expr_matches_destroy(&matches);
263 : : } else {
264 : 104 : struct ds output = DS_EMPTY_INITIALIZER;
265 : 104 : expr_format(expr, &output);
266 : 104 : puts(ds_cstr(&output));
267 : 122 : ds_destroy(&output);
268 : : }
269 : : } else {
270 : 46 : puts(error);
271 : 46 : free(error);
272 : : }
273 : 168 : expr_destroy(expr);
274 : : }
275 : 20 : ds_destroy(&input);
276 : :
277 : 20 : simap_destroy(&ports);
278 : 20 : expr_symtab_destroy(&symtab);
279 : 20 : shash_destroy(&symtab);
280 : 20 : expr_macros_destroy(¯os);
281 : 20 : shash_destroy(¯os);
282 : 20 : }
283 : :
284 : : static void
285 : 1 : test_parse_expr(struct ovs_cmdl_context *ctx OVS_UNUSED)
286 : : {
287 : 1 : test_parse_expr__(0);
288 : 1 : }
289 : :
290 : : static void
291 : 1 : test_annotate_expr(struct ovs_cmdl_context *ctx OVS_UNUSED)
292 : : {
293 : 1 : test_parse_expr__(1);
294 : 1 : }
295 : :
296 : : static void
297 : 0 : test_simplify_expr(struct ovs_cmdl_context *ctx OVS_UNUSED)
298 : : {
299 : 0 : test_parse_expr__(2);
300 : 0 : }
301 : :
302 : : static void
303 : 0 : test_normalize_expr(struct ovs_cmdl_context *ctx OVS_UNUSED)
304 : : {
305 : 0 : test_parse_expr__(3);
306 : 0 : }
307 : :
308 : : static void
309 : 18 : test_expr_to_flows(struct ovs_cmdl_context *ctx OVS_UNUSED)
310 : : {
311 : 18 : test_parse_expr__(4);
312 : 18 : }
313 : :
314 : : /* Print the symbol table. */
315 : :
316 : : static void
317 : 2 : test_dump_symtab(struct ovs_cmdl_context *ctx OVS_UNUSED)
318 : : {
319 : : struct shash symtab;
320 : 2 : create_symtab(&symtab);
321 : :
322 : 2 : const struct shash_node **nodes = shash_sort(&symtab);
323 [ + + ]: 182 : for (size_t i = 0; i < shash_count(&symtab); i++) {
324 : 180 : const struct expr_symbol *symbol = nodes[i]->data;
325 : 180 : struct ds s = DS_EMPTY_INITIALIZER;
326 : 180 : expr_symbol_format(symbol, &s);
327 : 180 : puts(ds_cstr(&s));
328 : 180 : ds_destroy(&s);
329 : : }
330 : :
331 : 2 : free(nodes);
332 : 2 : expr_symtab_destroy(&symtab);
333 : 2 : shash_destroy(&symtab);
334 : 2 : }
335 : :
336 : : /* Evaluate an expression. */
337 : :
338 : : static bool
339 : 15318443 : lookup_atoi_cb(const void *aux OVS_UNUSED, const char *port_name,
340 : : unsigned int *portp)
341 : : {
342 : 15318443 : *portp = atoi(port_name);
343 : 15318443 : return true;
344 : : }
345 : :
346 : : static void
347 : 0 : test_evaluate_expr(struct ovs_cmdl_context *ctx)
348 : : {
349 : : struct shash symtab;
350 : : struct ds input;
351 : :
352 : 0 : ovn_init_symtab(&symtab);
353 : :
354 : : struct flow uflow;
355 : 0 : char *error = expr_parse_microflow(ctx->argv[1], &symtab, NULL,
356 : : lookup_atoi_cb, NULL, &uflow);
357 [ # # ]: 0 : if (error) {
358 : 0 : ovs_fatal(0, "%s", error);
359 : : }
360 : :
361 : 0 : ds_init(&input);
362 [ # # ]: 0 : while (!ds_get_test_line(&input, stdin)) {
363 : : struct expr *expr;
364 : : char *error;
365 : :
366 : 0 : expr = expr_parse_string(ds_cstr(&input), &symtab, NULL, &error);
367 [ # # ]: 0 : if (!error) {
368 : 0 : expr = expr_annotate(expr, &symtab, &error);
369 : : }
370 [ # # ]: 0 : if (!error) {
371 : 0 : printf("%d\n", expr_evaluate(expr, &uflow, lookup_atoi_cb, NULL));
372 : : } else {
373 : 0 : puts(error);
374 : 0 : free(error);
375 : : }
376 : 0 : expr_destroy(expr);
377 : : }
378 : 0 : ds_destroy(&input);
379 : :
380 : 0 : expr_symtab_destroy(&symtab);
381 : 0 : shash_destroy(&symtab);
382 : 0 : }
383 : :
384 : : /* Compositions.
385 : : *
386 : : * The "compositions" of a positive integer N are all of the ways that one can
387 : : * add up positive integers to sum to N. For example, the compositions of 3
388 : : * are 3, 2+1, 1+2, and 1+1+1.
389 : : *
390 : : * We use compositions to find all the ways to break up N terms of a Boolean
391 : : * expression into subexpressions. Suppose we want to generate all expressions
392 : : * with 3 terms. The compositions of 3 (ignoring 3 itself) provide the
393 : : * possibilities (x && x) || x, x || (x && x), and x || x || x. (Of course one
394 : : * can exchange && for || in each case.) One must recursively compose the
395 : : * sub-expressions whose values are 3 or greater; that is what the "tree shape"
396 : : * concept later covers.
397 : : *
398 : : * To iterate through all compositions of, e.g., 5:
399 : : *
400 : : * unsigned int state;
401 : : * int s[5];
402 : : * int n;
403 : : *
404 : : * for (n = first_composition(ARRAY_SIZE(s), &state, s); n > 0;
405 : : * n = next_composition(&state, s, n)) {
406 : : * // Do something with composition 's' with 'n' elements.
407 : : * }
408 : : *
409 : : * Algorithm from D. E. Knuth, _The Art of Computer Programming, Vol. 4A:
410 : : * Combinatorial Algorithms, Part 1_, section 7.2.1.1, answer to exercise
411 : : * 12(a).
412 : : */
413 : :
414 : : /* Begins iteration through the compositions of 'n'. Initializes 's' to the
415 : : * number of elements in the first composition of 'n' and returns that number
416 : : * of elements. The first composition in fact is always 'n' itself, so the
417 : : * return value will be 1.
418 : : *
419 : : * Initializes '*state' to some internal state information. The caller must
420 : : * maintain this state (and 's') for use by next_composition().
421 : : *
422 : : * 's' must have room for at least 'n' elements. */
423 : : static int
424 : 122 : first_composition(int n, unsigned int *state, int s[])
425 : : {
426 : 122 : *state = 0;
427 : 122 : s[0] = n;
428 : 122 : return 1;
429 : : }
430 : :
431 : : /* Advances 's', with 'sn' elements, to the next composition and returns the
432 : : * number of elements in this new composition, or 0 if no compositions are
433 : : * left. 'state' is the same internal state passed to first_composition(). */
434 : : static int
435 : 664 : next_composition(unsigned int *state, int s[], int sn)
436 : : {
437 : 664 : int j = sn - 1;
438 [ + + ]: 664 : if (++*state & 1) {
439 [ + + ]: 332 : if (s[j] > 1) {
440 : 166 : s[j]--;
441 : 166 : s[j + 1] = 1;
442 : 166 : j++;
443 : : } else {
444 : 166 : j--;
445 : 332 : s[j]++;
446 : : }
447 : : } else {
448 [ + + ]: 332 : if (s[j - 1] > 1) {
449 : 166 : s[j - 1]--;
450 : 166 : s[j + 1] = s[j];
451 : 166 : s[j] = 1;
452 : 166 : j++;
453 : : } else {
454 : 166 : j--;
455 : 166 : s[j] = s[j + 1];
456 : 166 : s[j - 1]++;
457 [ + + ]: 166 : if (!j) {
458 : 122 : return 0;
459 : : }
460 : : }
461 : : }
462 : 542 : return j + 1;
463 : : }
464 : :
465 : : static void
466 : 0 : test_composition(struct ovs_cmdl_context *ctx)
467 : : {
468 : 0 : int n = atoi(ctx->argv[1]);
469 : : unsigned int state;
470 : : int s[50];
471 : :
472 [ # # ]: 0 : for (int sn = first_composition(n, &state, s); sn;
473 : 0 : sn = next_composition(&state, s, sn)) {
474 [ # # ]: 0 : for (int i = 0; i < sn; i++) {
475 [ # # ]: 0 : printf("%d%c", s[i], i == sn - 1 ? '\n' : ' ');
476 : : }
477 : : }
478 : 0 : }
479 : :
480 : : /* Tree shapes.
481 : : *
482 : : * This code generates all possible Boolean expressions with a specified number
483 : : * of terms N (equivalent to the number of external nodes in a tree).
484 : : *
485 : : * See test_tree_shape() for a simple example. */
486 : :
487 : : /* An array of these structures describes the shape of a tree.
488 : : *
489 : : * A single element of struct tree_shape describes a single node in the tree.
490 : : * The node has 'sn' direct children. From left to right, for i in 0...sn-1,
491 : : * s[i] is 1 if the child is a leaf node, otherwise the child is a subtree and
492 : : * s[i] is the number of leaf nodes within that subtree. In the latter case,
493 : : * the subtree is described by another struct tree_shape within the enclosing
494 : : * array. The tree_shapes are ordered in the array in in-order.
495 : : */
496 : : struct tree_shape {
497 : : unsigned int state;
498 : : int s[50];
499 : : int sn;
500 : : };
501 : :
502 : : static int
503 : 1434 : init_tree_shape__(struct tree_shape ts[], int n)
504 : : {
505 [ + + ]: 1434 : if (n <= 2) {
506 : 1312 : return 0;
507 : : }
508 : :
509 : 122 : int n_tses = 1;
510 : : /* Skip the first composition intentionally. */
511 : 122 : ts->sn = first_composition(n, &ts->state, ts->s);
512 : 122 : ts->sn = next_composition(&ts->state, ts->s, ts->sn);
513 [ + + ]: 366 : for (int i = 0; i < ts->sn; i++) {
514 : 244 : n_tses += init_tree_shape__(&ts[n_tses], ts->s[i]);
515 : : }
516 : 122 : return n_tses;
517 : : }
518 : :
519 : : /* Initializes 'ts[]' as the first in the set of all of possible shapes of
520 : : * trees with 'n' leaves. Returns the number of "struct tree_shape"s in the
521 : : * first tree shape. */
522 : : static int
523 : 32 : init_tree_shape(struct tree_shape ts[], int n)
524 : : {
525 [ + + + ]: 32 : switch (n) {
526 : : case 1:
527 : 2 : ts->sn = 1;
528 : 2 : ts->s[0] = 1;
529 : 2 : return 1;
530 : : case 2:
531 : 2 : ts->sn = 2;
532 : 2 : ts->s[0] = 1;
533 : 2 : ts->s[1] = 1;
534 : 2 : return 1;
535 : : default:
536 : 28 : return init_tree_shape__(ts, n);
537 : : }
538 : : }
539 : :
540 : : /* Advances 'ts', which currently has 'n_tses' elements, to the next possible
541 : : * tree shape with the number of leaves passed to init_tree_shape(). Returns
542 : : * the number of "struct tree_shape"s in the next shape, or 0 if all tree
543 : : * shapes have been visited. */
544 : : static int
545 : 452 : next_tree_shape(struct tree_shape ts[], int n_tses)
546 : : {
547 [ + + ][ + + ]: 452 : if (n_tses == 1 && ts->sn == 2 && ts->s[0] == 1 && ts->s[1] == 1) {
[ + + ][ + + ]
548 : 2 : return 0;
549 : : }
550 [ + + ]: 574 : while (n_tses > 0) {
551 : 544 : struct tree_shape *p = &ts[n_tses - 1];
552 [ + + ]: 544 : p->sn = p->sn > 1 ? next_composition(&p->state, p->s, p->sn) : 0;
553 [ + + ]: 544 : if (p->sn) {
554 [ + + ]: 1582 : for (int i = 0; i < p->sn; i++) {
555 : 1162 : n_tses += init_tree_shape__(&ts[n_tses], p->s[i]);
556 : : }
557 : 420 : break;
558 : : }
559 : 124 : n_tses--;
560 : : }
561 : 450 : return n_tses;
562 : : }
563 : :
564 : : static void
565 : 0 : print_tree_shape(const struct tree_shape ts[], int n_tses)
566 : : {
567 [ # # ]: 0 : for (int i = 0; i < n_tses; i++) {
568 [ # # ]: 0 : if (i) {
569 : 0 : printf(", ");
570 : : }
571 [ # # ]: 0 : for (int j = 0; j < ts[i].sn; j++) {
572 : 0 : int k = ts[i].s[j];
573 [ # # ]: 0 : if (k > 9) {
574 : 0 : printf("(%d)", k);
575 : : } else {
576 : 0 : printf("%d", k);
577 : : }
578 : : }
579 : : }
580 : 0 : }
581 : :
582 : : static void
583 : 0 : test_tree_shape(struct ovs_cmdl_context *ctx)
584 : : {
585 : 0 : int n = atoi(ctx->argv[1]);
586 : : struct tree_shape ts[50];
587 : : int n_tses;
588 : :
589 [ # # ]: 0 : for (n_tses = init_tree_shape(ts, n); n_tses;
590 : 0 : n_tses = next_tree_shape(ts, n_tses)) {
591 : 0 : print_tree_shape(ts, n_tses);
592 : 0 : putchar('\n');
593 : : }
594 : 0 : }
595 : :
596 : : /* Iteration through all possible terminal expressions (e.g. EXPR_T_CMP and
597 : : * EXPR_T_BOOLEAN expressions).
598 : : *
599 : : * Given a tree shape, this allows the code to try all possible ways to plug in
600 : : * terms.
601 : : *
602 : : * Example use:
603 : : *
604 : : * struct expr terminal;
605 : : * const struct expr_symbol *vars = ...;
606 : : * int n_vars = ...;
607 : : * int n_bits = ...;
608 : : *
609 : : * init_terminal(&terminal, vars[0]);
610 : : * do {
611 : : * // Something with 'terminal'.
612 : : * } while (next_terminal(&terminal, vars, n_vars, n_bits));
613 : : */
614 : :
615 : : /* Sets 'expr' to the first possible terminal expression. 'var' should be the
616 : : * first variable in the ones to be tested. */
617 : : static void
618 : 417736 : init_terminal(struct expr *expr, int phase,
619 : : const struct expr_symbol *nvars[], int n_nvars,
620 : : const struct expr_symbol *svars[], int n_svars)
621 : : {
622 [ + + ][ + + ]: 417736 : if (phase < 1 && n_nvars) {
623 : 132136 : expr->type = EXPR_T_CMP;
624 : 132136 : expr->cmp.symbol = nvars[0];
625 : 132136 : expr->cmp.relop = rightmost_1bit_idx(test_relops);
626 : 132136 : memset(&expr->cmp.value, 0, sizeof expr->cmp.value);
627 : 132136 : memset(&expr->cmp.mask, 0, sizeof expr->cmp.mask);
628 : 132136 : expr->cmp.value.integer = htonll(0);
629 : 132136 : expr->cmp.mask.integer = htonll(1);
630 : 132136 : return;
631 : : }
632 : :
633 [ + + ][ + + ]: 285600 : if (phase < 2 && n_svars) {
634 : 95654 : expr->type = EXPR_T_CMP;
635 : 95654 : expr->cmp.symbol = svars[0];
636 : 95654 : expr->cmp.relop = EXPR_R_EQ;
637 : 95654 : expr->cmp.string = xstrdup("0");
638 : 95654 : return;
639 : : }
640 : :
641 : 189946 : expr->type = EXPR_T_BOOLEAN;
642 : 189946 : expr->boolean = false;
643 : : }
644 : :
645 : : /* Returns 'x' with the rightmost contiguous string of 1s changed to 0s,
646 : : * e.g. 01011100 => 01000000. See H. S. Warren, Jr., _Hacker's Delight_, 2nd
647 : : * ed., section 2-1. */
648 : : static unsigned int
649 : 2408526 : turn_off_rightmost_1s(unsigned int x)
650 : : {
651 : 2408526 : return ((x & -x) + x) & x;
652 : : }
653 : :
654 : : static const struct expr_symbol *
655 : 538464 : next_var(const struct expr_symbol *symbol,
656 : : const struct expr_symbol *vars[], int n_vars)
657 : : {
658 [ + - ]: 1005852 : for (int i = 0; i < n_vars; i++) {
659 [ + + ]: 1005852 : if (symbol == vars[i]) {
660 [ + + ]: 538464 : return i + 1 >= n_vars ? NULL : vars[i + 1];
661 : : }
662 : : }
663 : 0 : OVS_NOT_REACHED();
664 : : }
665 : :
666 : : static enum expr_relop
667 : 866844 : next_relop(enum expr_relop relop)
668 : : {
669 : 866844 : unsigned int remaining_relops = test_relops & ~((1u << (relop + 1)) - 1);
670 [ + + ]: 1733688 : return (remaining_relops
671 : 554650 : ? rightmost_1bit_idx(remaining_relops)
672 : 312194 : : rightmost_1bit_idx(test_relops));
673 : : }
674 : :
675 : : /* Advances 'expr' to the next possible terminal expression within the 'n_vars'
676 : : * variables of 'n_bits' bits each in 'vars[]'. */
677 : : static bool
678 : 3303444 : next_terminal(struct expr *expr,
679 : : const struct expr_symbol *nvars[], int n_nvars, int n_bits,
680 : : const struct expr_symbol *svars[], int n_svars)
681 : : {
682 [ + + ]: 3303444 : if (expr->type == EXPR_T_BOOLEAN) {
683 [ + + ]: 379892 : if (expr->boolean) {
684 : 189946 : return false;
685 : : } else {
686 : 189946 : expr->boolean = true;
687 : 189946 : return true;
688 : : }
689 : : }
690 : :
691 [ + + ]: 2923552 : if (!expr->cmp.symbol->width) {
692 : 452540 : int next_value = atoi(expr->cmp.string) + 1;
693 : 452540 : free(expr->cmp.string);
694 [ + + ]: 452540 : if (next_value > 1) {
695 : 226270 : expr->cmp.symbol = next_var(expr->cmp.symbol, svars, n_svars);
696 [ + + ]: 226270 : if (!expr->cmp.symbol) {
697 : 94940 : init_terminal(expr, 2, nvars, n_nvars, svars, n_svars);
698 : 94940 : return true;
699 : : }
700 : 131330 : next_value = 0;
701 : : }
702 : 357600 : expr->cmp.string = xasprintf("%d", next_value);
703 : 357600 : return true;
704 : : }
705 : :
706 : : unsigned int next;
707 : :
708 : 4942024 : next = (ntohll(expr->cmp.value.integer)
709 : 2471012 : + (ntohll(expr->cmp.mask.integer) << n_bits));
710 : : for (;;) {
711 : 5100416 : next++;
712 : 5100416 : unsigned m = next >> n_bits;
713 : 5100416 : unsigned v = next & ((1u << n_bits) - 1);
714 [ + + ]: 5100416 : if (next >= (1u << (2 * n_bits))) {
715 : 866844 : enum expr_relop old_relop = expr->cmp.relop;
716 : 866844 : expr->cmp.relop = next_relop(old_relop);
717 [ + + ]: 866844 : if (expr->cmp.relop <= old_relop) {
718 : 312194 : expr->cmp.symbol = next_var(expr->cmp.symbol, nvars, n_nvars);
719 [ + + ]: 312194 : if (!expr->cmp.symbol) {
720 : 130806 : init_terminal(expr, 1, nvars, n_nvars, svars, n_svars);
721 : 130806 : return true;
722 : : }
723 : : }
724 : 736038 : next = 0;
725 [ + + ]: 4233572 : } else if (m == 0) {
726 : : /* Skip: empty mask is pathological. */
727 [ + + ]: 3324714 : } else if (v & ~m) {
728 : : /* Skip: 1-bits in value correspond to 0-bits in mask. */
729 [ + + ]: 2408526 : } else if (turn_off_rightmost_1s(m)
730 [ + + ][ + + ]: 108312 : && (expr->cmp.relop != EXPR_R_EQ &&
731 : 85400 : expr->cmp.relop != EXPR_R_NE)) {
732 : : /* Skip: can't have discontiguous mask for > >= < <=. */
733 : : } else {
734 : 2340206 : expr->cmp.value.integer = htonll(v);
735 : 2340206 : expr->cmp.mask.integer = htonll(m);
736 : 2340206 : return true;
737 : : }
738 : 2629404 : }
739 : : }
740 : :
741 : : static struct expr *
742 : 2044 : make_terminal(struct expr ***terminalp)
743 : : {
744 : 2044 : struct expr *e = expr_create_boolean(true);
745 : 2044 : **terminalp = e;
746 : 2044 : (*terminalp)++;
747 : 2044 : return e;
748 : : }
749 : :
750 : : static struct expr *
751 : 1638 : build_simple_tree(enum expr_type type, int n, struct expr ***terminalp)
752 : : {
753 [ + + ]: 1638 : if (n == 2) {
754 : 406 : struct expr *e = expr_create_andor(type);
755 [ + + ]: 1218 : for (int i = 0; i < 2; i++) {
756 : 812 : struct expr *sub = make_terminal(terminalp);
757 : 812 : ovs_list_push_back(&e->andor, &sub->node);
758 : : }
759 : 406 : return e;
760 [ + - ]: 1232 : } else if (n == 1) {
761 : 1232 : return make_terminal(terminalp);
762 : : } else {
763 : 0 : OVS_NOT_REACHED();
764 : : }
765 : : }
766 : :
767 : : static struct expr *
768 : 830 : build_tree_shape(enum expr_type type, const struct tree_shape **tsp,
769 : : struct expr ***terminalp)
770 : : {
771 : 830 : const struct tree_shape *ts = *tsp;
772 : 830 : (*tsp)++;
773 : :
774 : 830 : struct expr *e = expr_create_andor(type);
775 [ + + ]: 830 : enum expr_type t = type == EXPR_T_AND ? EXPR_T_OR : EXPR_T_AND;
776 [ + + ]: 2846 : for (int i = 0; i < ts->sn; i++) {
777 : 4032 : struct expr *sub = (ts->s[i] > 2
778 : : ? build_tree_shape(t, tsp, terminalp)
779 [ + + ]: 2016 : : build_simple_tree(t, ts->s[i], terminalp));
780 : 2016 : ovs_list_push_back(&e->andor, &sub->node);
781 : : }
782 : 830 : return e;
783 : : }
784 : :
785 : : struct test_rule {
786 : : struct cls_rule cr;
787 : : };
788 : :
789 : : static void
790 : 376924 : free_rule(struct test_rule *test_rule)
791 : : {
792 : 376924 : cls_rule_destroy(&test_rule->cr);
793 : 376924 : free(test_rule);
794 : 376924 : }
795 : :
796 : : static int
797 : 452 : test_tree_shape_exhaustively(struct expr *expr, struct shash *symtab,
798 : : struct expr *terminals[], int n_terminals,
799 : : const struct expr_symbol *nvars[], int n_nvars,
800 : : int n_bits,
801 : : const struct expr_symbol *svars[], int n_svars)
802 : : {
803 : 452 : int n_tested = 0;
804 : :
805 : 452 : const unsigned int var_mask = (1u << n_bits) - 1;
806 [ + + ]: 2496 : for (int i = 0; i < n_terminals; i++) {
807 : 2044 : init_terminal(terminals[i], 0, nvars, n_nvars, svars, n_svars);
808 : : }
809 : :
810 : 452 : struct ds s = DS_EMPTY_INITIALIZER;
811 : : struct flow f;
812 : 452 : memset(&f, 0, sizeof f);
813 : : for (;;) {
814 : 3113950 : for (int i = n_terminals - 1; ; i--) {
815 [ + + ]: 3303896 : if (!i) {
816 : 452 : ds_destroy(&s);
817 : 452 : return n_tested;
818 : : }
819 [ + + ]: 3303444 : if (next_terminal(terminals[i], nvars, n_nvars, n_bits,
820 : : svars, n_svars)) {
821 : 3113498 : break;
822 : : }
823 : 189946 : init_terminal(terminals[i], 0, nvars, n_nvars, svars, n_svars);
824 : 189946 : }
825 [ - + ]: 3113498 : ovs_assert(expr_honors_invariants(expr));
826 : :
827 : 3113498 : n_tested++;
828 : :
829 : : struct expr *modified;
830 [ + + ]: 3113498 : if (operation == OP_CONVERT) {
831 : 62988 : ds_clear(&s);
832 : 62988 : expr_format(expr, &s);
833 : :
834 : : char *error;
835 : 62988 : modified = expr_parse_string(ds_cstr(&s), symtab, NULL, &error);
836 [ - + ]: 62988 : if (error) {
837 : 0 : fprintf(stderr, "%s fails to parse (%s)\n",
838 : : ds_cstr(&s), error);
839 : 62988 : exit(EXIT_FAILURE);
840 : : }
841 [ + - ]: 3050510 : } else if (operation >= OP_SIMPLIFY) {
842 : 3050510 : modified = expr_simplify(expr_clone(expr));
843 [ - + ]: 3050510 : ovs_assert(expr_honors_invariants(modified));
844 : :
845 [ + + ]: 3050510 : if (operation >= OP_NORMALIZE) {
846 : 2426984 : modified = expr_normalize(modified);
847 [ - + ]: 2426984 : ovs_assert(expr_is_normalized(modified));
848 : : }
849 : : }
850 : :
851 : : struct hmap matches;
852 : : struct classifier cls;
853 [ + + ]: 3113498 : if (operation >= OP_FLOW) {
854 : : struct expr_match *m;
855 : : struct test_rule *test_rule;
856 : :
857 : 226648 : expr_to_matches(modified, lookup_atoi_cb, NULL, &matches);
858 : :
859 : 226648 : classifier_init(&cls, NULL);
860 [ + + ][ - + ]: 603572 : HMAP_FOR_EACH (m, hmap_node, &matches) {
861 : 376924 : test_rule = xmalloc(sizeof *test_rule);
862 : 376924 : cls_rule_init(&test_rule->cr, &m->match, 0);
863 : 376924 : classifier_insert(&cls, &test_rule->cr, OVS_VERSION_MIN,
864 : 376924 : m->conjunctions, m->n);
865 : : }
866 : : }
867 [ + + ]: 79635538 : for (int subst = 0; subst < 1 << (n_bits * n_nvars + n_svars);
868 : 76522040 : subst++) {
869 [ + + ]: 250559312 : for (int i = 0; i < n_nvars; i++) {
870 : 174037272 : f.regs[i] = (subst >> (i * n_bits)) & var_mask;
871 : : }
872 [ + + ]: 101544800 : for (int i = 0; i < n_svars; i++) {
873 : 25022760 : f.regs[n_nvars + i] = ((subst >> (n_nvars * n_bits + i))
874 : : & 1);
875 : : }
876 : :
877 : 76522040 : bool expected = expr_evaluate(expr, &f, lookup_atoi_cb, NULL);
878 : 76522040 : bool actual = expr_evaluate(modified, &f, lookup_atoi_cb, NULL);
879 [ - + ]: 76522040 : if (actual != expected) {
880 : : struct ds expr_s, modified_s;
881 : :
882 : 0 : ds_init(&expr_s);
883 : 0 : expr_format(expr, &expr_s);
884 : :
885 : 0 : ds_init(&modified_s);
886 : 0 : expr_format(modified, &modified_s);
887 : :
888 : 0 : fprintf(stderr,
889 : : "%s evaluates to %d, but %s evaluates to %d, for",
890 : : ds_cstr(&expr_s), expected,
891 : : ds_cstr(&modified_s), actual);
892 [ # # ]: 0 : for (int i = 0; i < n_nvars; i++) {
893 [ # # ]: 0 : if (i > 0) {
894 : 0 : fputs(",", stderr);
895 : : }
896 : 0 : fprintf(stderr, " n%d = 0x%x", i,
897 : 0 : (subst >> (n_bits * i)) & var_mask);
898 : : }
899 [ # # ]: 0 : for (int i = 0; i < n_svars; i++) {
900 : 0 : fprintf(stderr, ", s%d = \"%d\"", i,
901 : 0 : (subst >> (n_bits * n_nvars + i)) & 1);
902 : : }
903 : 0 : putc('\n', stderr);
904 : 0 : exit(EXIT_FAILURE);
905 : : }
906 : :
907 [ + + ]: 76522040 : if (operation >= OP_FLOW) {
908 : 22365840 : bool found = classifier_lookup(&cls, OVS_VERSION_MIN,
909 : : &f, NULL) != NULL;
910 [ - + ]: 22365840 : if (expected != found) {
911 : : struct ds expr_s, modified_s;
912 : :
913 : 0 : ds_init(&expr_s);
914 : 0 : expr_format(expr, &expr_s);
915 : :
916 : 0 : ds_init(&modified_s);
917 : 0 : expr_format(modified, &modified_s);
918 : :
919 : 0 : fprintf(stderr,
920 : : "%s and %s evaluate to %d, for",
921 : : ds_cstr(&expr_s), ds_cstr(&modified_s), expected);
922 [ # # ]: 0 : for (int i = 0; i < n_nvars; i++) {
923 [ # # ]: 0 : if (i > 0) {
924 : 0 : fputs(",", stderr);
925 : : }
926 : 0 : fprintf(stderr, " n%d = 0x%x", i,
927 : 0 : (subst >> (n_bits * i)) & var_mask);
928 : : }
929 [ # # ]: 0 : for (int i = 0; i < n_svars; i++) {
930 : 0 : fprintf(stderr, ", s%d = \"%d\"", i,
931 : 0 : (subst >> (n_bits * n_nvars + i)) & 1);
932 : : }
933 : 0 : fputs(".\n", stderr);
934 : :
935 : 0 : fprintf(stderr, "Converted to classifier:\n");
936 : 0 : expr_matches_print(&matches, stderr);
937 [ # # ]: 0 : fprintf(stderr,
938 : : "However, %s flow was found in the classifier.\n",
939 : : found ? "a" : "no");
940 : 0 : exit(EXIT_FAILURE);
941 : : }
942 : : }
943 : : }
944 [ + + ]: 3113498 : if (operation >= OP_FLOW) {
945 : : struct test_rule *test_rule;
946 : :
947 [ + + ][ + + ]: 603572 : CLS_FOR_EACH (test_rule, cr, &cls) {
948 : 376924 : classifier_remove(&cls, &test_rule->cr);
949 : 376924 : ovsrcu_postpone(free_rule, test_rule);
950 : : }
951 : 226648 : classifier_destroy(&cls);
952 : 226648 : ovsrcu_quiesce();
953 : :
954 : 226648 : expr_matches_destroy(&matches);
955 : : }
956 : 3113498 : expr_destroy(modified);
957 : 3113498 : }
958 : : }
959 : :
960 : : #ifndef _WIN32
961 : : static void
962 : 0 : wait_pid(pid_t *pids, int *n)
963 : : {
964 : : int status;
965 : : pid_t pid;
966 : :
967 : 0 : pid = waitpid(WAIT_ANY, &status, 0);
968 [ # # ]: 0 : if (pid < 0) {
969 : 0 : ovs_fatal(errno, "waitpid failed");
970 [ # # ]: 0 : } else if (WIFEXITED(status)) {
971 [ # # ]: 0 : if (WEXITSTATUS(status)) {
972 : 0 : exit(WEXITSTATUS(status));
973 : : }
974 [ # # ]: 0 : } else if (WIFSIGNALED(status)) {
975 : 0 : raise(WTERMSIG(status));
976 : 0 : exit(1);
977 : : } else {
978 : 0 : OVS_NOT_REACHED();
979 : : }
980 : :
981 [ # # ]: 0 : for (int i = 0; i < *n; i++) {
982 [ # # ]: 0 : if (pids[i] == pid) {
983 : 0 : pids[i] = pids[--*n];
984 : 0 : return;
985 : : }
986 : : }
987 : 0 : ovs_fatal(0, "waitpid returned unknown child");
988 : : }
989 : : #endif
990 : :
991 : : static void
992 : 16 : test_exhaustive(struct ovs_cmdl_context *ctx OVS_UNUSED)
993 : : {
994 : 16 : int n_terminals = atoi(ctx->argv[1]);
995 : : struct tree_shape ts[50];
996 : : int n_tses;
997 : :
998 : : struct shash symtab;
999 : : const struct expr_symbol *nvars[4];
1000 : : const struct expr_symbol *svars[4];
1001 : :
1002 [ - + ]: 16 : ovs_assert(test_nvars <= ARRAY_SIZE(nvars));
1003 [ - + ]: 16 : ovs_assert(test_svars <= ARRAY_SIZE(svars));
1004 [ - + ]: 16 : ovs_assert(test_nvars + test_svars <= FLOW_N_REGS);
1005 : :
1006 : 16 : shash_init(&symtab);
1007 [ + + ]: 39 : for (int i = 0; i < test_nvars; i++) {
1008 : 23 : char *name = xasprintf("n%d", i);
1009 : 23 : nvars[i] = expr_symtab_add_field(&symtab, name, MFF_REG0 + i, NULL,
1010 : : false);
1011 : 23 : free(name);
1012 : : }
1013 [ + + ]: 41 : for (int i = 0; i < test_svars; i++) {
1014 : 25 : char *name = xasprintf("s%d", i);
1015 : 25 : svars[i] = expr_symtab_add_string(&symtab, name,
1016 : : MFF_REG0 + test_nvars + i, NULL);
1017 : 25 : free(name);
1018 : : }
1019 : :
1020 : : #ifndef _WIN32
1021 : 16 : pid_t *children = xmalloc(test_parallel * sizeof *children);
1022 : 16 : int n_children = 0;
1023 : : #endif
1024 : :
1025 : 16 : int n_tested = 0;
1026 [ + + ]: 48 : for (int i = 0; i < 2; i++) {
1027 [ + + ]: 32 : enum expr_type base_type = i ? EXPR_T_OR : EXPR_T_AND;
1028 : :
1029 [ + + ]: 484 : for (n_tses = init_tree_shape(ts, n_terminals); n_tses;
1030 : 452 : n_tses = next_tree_shape(ts, n_tses)) {
1031 : 452 : const struct tree_shape *tsp = ts;
1032 : : struct expr *terminals[50];
1033 : 452 : struct expr **terminalp = terminals;
1034 : 452 : struct expr *expr = build_tree_shape(base_type, &tsp, &terminalp);
1035 [ - + ]: 452 : ovs_assert(terminalp == &terminals[n_terminals]);
1036 : :
1037 [ - + ]: 452 : if (verbosity > 0) {
1038 : 0 : print_tree_shape(ts, n_tses);
1039 : 0 : printf(": ");
1040 : 0 : struct ds s = DS_EMPTY_INITIALIZER;
1041 : 0 : expr_format(expr, &s);
1042 : 0 : puts(ds_cstr(&s));
1043 : 0 : ds_destroy(&s);
1044 : : }
1045 : :
1046 : : #ifndef _WIN32
1047 [ - + ]: 452 : if (test_parallel > 1) {
1048 : 0 : pid_t pid = xfork();
1049 [ # # ]: 0 : if (!pid) {
1050 : 0 : test_tree_shape_exhaustively(expr, &symtab,
1051 : : terminals, n_terminals,
1052 : : nvars, test_nvars, test_bits,
1053 : : svars, test_svars);
1054 : 0 : expr_destroy(expr);
1055 : 0 : exit(0);
1056 : : } else {
1057 [ # # ]: 0 : if (n_children >= test_parallel) {
1058 : 0 : wait_pid(children, &n_children);
1059 : : }
1060 : 0 : children[n_children++] = pid;
1061 : : }
1062 : : } else
1063 : : #endif
1064 : : {
1065 : 452 : n_tested += test_tree_shape_exhaustively(
1066 : : expr, &symtab, terminals, n_terminals,
1067 : : nvars, test_nvars, test_bits,
1068 : : svars, test_svars);
1069 : : }
1070 : 452 : expr_destroy(expr);
1071 : : }
1072 : : }
1073 : : #ifndef _WIN32
1074 [ - + ]: 16 : while (n_children > 0) {
1075 : 0 : wait_pid(children, &n_children);
1076 : : }
1077 : 16 : free(children);
1078 : : #endif
1079 : :
1080 : 16 : printf("Tested ");
1081 [ + + + + : 16 : switch (operation) {
- ]
1082 : : case OP_CONVERT:
1083 : 3 : printf("converting");
1084 : 3 : break;
1085 : : case OP_SIMPLIFY:
1086 : 3 : printf("simplifying");
1087 : 3 : break;
1088 : : case OP_NORMALIZE:
1089 : 6 : printf("normalizing");
1090 : 6 : break;
1091 : : case OP_FLOW:
1092 : 4 : printf("converting to flows");
1093 : 4 : break;
1094 : : }
1095 [ + + ]: 16 : if (n_tested) {
1096 : 15 : printf(" %d expressions of %d terminals", n_tested, n_terminals);
1097 : : } else {
1098 : 1 : printf(" all %d-terminal expressions", n_terminals);
1099 : : }
1100 [ + + ][ + - ]: 16 : if (test_nvars || test_svars) {
1101 : 16 : printf(" with");
1102 [ + + ]: 16 : if (test_nvars) {
1103 : 12 : printf(" %d numeric vars (each %d bits) in terms of operators",
1104 : : test_nvars, test_bits);
1105 [ + + ]: 59 : for (unsigned int relops = test_relops; relops;
1106 : 47 : relops = zero_rightmost_1bit(relops)) {
1107 : 47 : enum expr_relop r = rightmost_1bit_idx(relops);
1108 : 47 : printf(" %s", expr_relop_to_string(r));
1109 : : }
1110 : : }
1111 [ + + ][ + + ]: 16 : if (test_nvars && test_svars) {
1112 : 7 : printf (" and");
1113 : : }
1114 [ + + ]: 27 : if (test_svars) {
1115 : 11 : printf(" %d string vars", test_svars);
1116 : : }
1117 : : } else {
1118 : 0 : printf(" in terms of Boolean constants only");
1119 : : }
1120 : 16 : printf(".\n");
1121 : :
1122 : 16 : expr_symtab_destroy(&symtab);
1123 : 16 : shash_destroy(&symtab);
1124 : 16 : }
1125 : :
1126 : : /* Actions. */
1127 : :
1128 : : static void
1129 : 1 : test_parse_actions(struct ovs_cmdl_context *ctx OVS_UNUSED)
1130 : : {
1131 : : struct shash symtab;
1132 : : struct hmap dhcp_opts;
1133 : : struct hmap dhcpv6_opts;
1134 : : struct simap ports, ct_zones;
1135 : : struct ds input;
1136 : 1 : bool ok = true;
1137 : :
1138 : 1 : create_symtab(&symtab);
1139 : 1 : create_dhcp_opts(&dhcp_opts, &dhcpv6_opts);
1140 : :
1141 : : /* Initialize group ids. */
1142 : : struct group_table group_table;
1143 : 1 : group_table.group_ids = bitmap_allocate(MAX_OVN_GROUPS);
1144 : 1 : bitmap_set1(group_table.group_ids, 0); /* Group id 0 is invalid. */
1145 : 1 : hmap_init(&group_table.desired_groups);
1146 : 1 : hmap_init(&group_table.existing_groups);
1147 : :
1148 : 1 : simap_init(&ports);
1149 : 1 : simap_put(&ports, "eth0", 5);
1150 : 1 : simap_put(&ports, "eth1", 6);
1151 : 1 : simap_put(&ports, "LOCAL", ofp_to_u16(OFPP_LOCAL));
1152 : 1 : simap_init(&ct_zones);
1153 : :
1154 : 1 : ds_init(&input);
1155 [ + + ]: 133 : while (!ds_get_test_line(&input, stdin)) {
1156 : : struct ofpbuf ovnacts;
1157 : : struct expr *prereqs;
1158 : : char *error;
1159 : :
1160 : 132 : puts(ds_cstr(&input));
1161 : :
1162 : 132 : ofpbuf_init(&ovnacts, 0);
1163 : :
1164 : 132 : const struct ovnact_parse_params pp = {
1165 : : .symtab = &symtab,
1166 : : .dhcp_opts = &dhcp_opts,
1167 : : .dhcpv6_opts = &dhcpv6_opts,
1168 : : .n_tables = 16,
1169 : : .cur_ltable = 10,
1170 : : };
1171 : 132 : error = ovnacts_parse_string(ds_cstr(&input), &pp, &ovnacts, &prereqs);
1172 [ + + ]: 132 : if (!error) {
1173 : : /* Convert the parsed representation back to a string and print it,
1174 : : * if it's different from the input. */
1175 : 59 : struct ds ovnacts_s = DS_EMPTY_INITIALIZER;
1176 : 59 : ovnacts_format(ovnacts.data, ovnacts.size, &ovnacts_s);
1177 [ + + ]: 59 : if (strcmp(ds_cstr(&input), ds_cstr(&ovnacts_s))) {
1178 : 20 : printf(" formats as %s\n", ds_cstr(&ovnacts_s));
1179 : : }
1180 : :
1181 : : /* Encode the actions into OpenFlow and print. */
1182 : 59 : const struct ovnact_encode_params ep = {
1183 : : .lookup_port = lookup_port_cb,
1184 : : .aux = &ports,
1185 : : .is_switch = true,
1186 : : .ct_zones = &ct_zones,
1187 : : .group_table = &group_table,
1188 : :
1189 : : .first_ptable = 16,
1190 : : .output_ptable = 64,
1191 : : .mac_bind_ptable = 65,
1192 : : };
1193 : : struct ofpbuf ofpacts;
1194 : 59 : ofpbuf_init(&ofpacts, 0);
1195 : 59 : ovnacts_encode(ovnacts.data, ovnacts.size, &ep, &ofpacts);
1196 : 59 : struct ds ofpacts_s = DS_EMPTY_INITIALIZER;
1197 : 59 : ofpacts_format(ofpacts.data, ofpacts.size, &ofpacts_s);
1198 : 59 : printf(" encodes as %s\n", ds_cstr(&ofpacts_s));
1199 : 59 : ds_destroy(&ofpacts_s);
1200 : 59 : ofpbuf_uninit(&ofpacts);
1201 : :
1202 : : /* Print prerequisites if any. */
1203 [ + + ]: 59 : if (prereqs) {
1204 : 36 : struct ds prereqs_s = DS_EMPTY_INITIALIZER;
1205 : 36 : expr_format(prereqs, &prereqs_s);
1206 : 36 : printf(" has prereqs %s\n", ds_cstr(&prereqs_s));
1207 : 36 : ds_destroy(&prereqs_s);
1208 : : }
1209 : :
1210 : : /* Now re-parse and re-format the string to verify that it's
1211 : : * round-trippable. */
1212 : : struct ofpbuf ovnacts2;
1213 : : struct expr *prereqs2;
1214 : 59 : ofpbuf_init(&ovnacts2, 0);
1215 : 59 : error = ovnacts_parse_string(ds_cstr(&ovnacts_s), &pp, &ovnacts2,
1216 : : &prereqs2);
1217 [ + - ]: 59 : if (!error) {
1218 : 59 : struct ds ovnacts2_s = DS_EMPTY_INITIALIZER;
1219 : 59 : ovnacts_format(ovnacts2.data, ovnacts2.size, &ovnacts2_s);
1220 [ - + ]: 59 : if (strcmp(ds_cstr(&ovnacts_s), ds_cstr(&ovnacts2_s))) {
1221 : 0 : printf(" bad reformat: %s\n", ds_cstr(&ovnacts2_s));
1222 : 0 : ok = false;
1223 : : }
1224 : 59 : ds_destroy(&ovnacts2_s);
1225 : : } else {
1226 : 0 : printf(" reparse error: %s\n", error);
1227 : 0 : free(error);
1228 : 0 : ok = false;
1229 : : }
1230 : 59 : expr_destroy(prereqs2);
1231 : :
1232 : 59 : ovnacts_free(ovnacts2.data, ovnacts2.size);
1233 : 59 : ofpbuf_uninit(&ovnacts2);
1234 : 59 : ds_destroy(&ovnacts_s);
1235 : : } else {
1236 : 73 : printf(" %s\n", error);
1237 : 73 : free(error);
1238 : : }
1239 : :
1240 : 132 : expr_destroy(prereqs);
1241 : 132 : ovnacts_free(ovnacts.data, ovnacts.size);
1242 : 132 : ofpbuf_uninit(&ovnacts);
1243 : : }
1244 : 1 : ds_destroy(&input);
1245 : :
1246 : 1 : simap_destroy(&ports);
1247 : 1 : simap_destroy(&ct_zones);
1248 : 1 : expr_symtab_destroy(&symtab);
1249 : 1 : shash_destroy(&symtab);
1250 : 1 : dhcp_opts_destroy(&dhcp_opts);
1251 : 1 : dhcp_opts_destroy(&dhcpv6_opts);
1252 : :
1253 [ + - ]: 1 : exit(ok ? EXIT_SUCCESS : EXIT_FAILURE);
1254 : : }
1255 : :
1256 : : static unsigned int
1257 : 46 : parse_relops(const char *s)
1258 : : {
1259 : 46 : unsigned int relops = 0;
1260 : : struct lexer lexer;
1261 : :
1262 : 46 : lexer_init(&lexer, s);
1263 : 46 : lexer_get(&lexer);
1264 : : do {
1265 : : enum expr_relop relop;
1266 : :
1267 [ + - ]: 246 : if (expr_relop_from_token(lexer.token.type, &relop)) {
1268 : 246 : relops |= 1u << relop;
1269 : 246 : lexer_get(&lexer);
1270 : : } else {
1271 : 0 : ovs_fatal(0, "%s: relational operator expected at `%.*s'",
1272 : 0 : s, (int) (lexer.input - lexer.start), lexer.start);
1273 : : }
1274 : 246 : lexer_match(&lexer, LEX_T_COMMA);
1275 [ + + ]: 246 : } while (lexer.token.type != LEX_T_END);
1276 : 46 : lexer_destroy(&lexer);
1277 : :
1278 : 46 : return relops;
1279 : : }
1280 : :
1281 : : static void
1282 : 0 : usage(void)
1283 : : {
1284 : 0 : printf("\
1285 : : %s: OVN test utility\n\
1286 : : usage: test-ovn %s [OPTIONS] COMMAND [ARG...]\n\
1287 : : \n\
1288 : : lex\n\
1289 : : Lexically analyzes OVN input from stdin and print them back on stdout.\n\
1290 : : \n\
1291 : : parse-expr\n\
1292 : : annotate-expr\n\
1293 : : simplify-expr\n\
1294 : : normalize-expr\n\
1295 : : expr-to-flows\n\
1296 : : Parses OVN expressions from stdin and print them back on stdout after\n\
1297 : : differing degrees of analysis. Available fields are based on packet\n\
1298 : : headers.\n\
1299 : : \n\
1300 : : evaluate-expr MICROFLOW\n\
1301 : : Parses OVN expressions from stdin and evaluates them against the flow\n\
1302 : : specified in MICROFLOW, which must be an expression that constrains\n\
1303 : : the packet, e.g. \"ip4 && tcp.src == 80\" for a TCP packet with source\n\
1304 : : port 80, and prints the results on stdout, either 1 for true or 0 for\n\
1305 : : false. Use quoted integers, e.g. \"123\", for string fields.\n\
1306 : : \n\
1307 : : Example: for MICROFLOW of \"ip4 && tcp.src == 80\", \"eth.type == 0x800\"\n\
1308 : : evaluates to true, \"udp\" evaluates to false, and \"udp || tcp\"\n\
1309 : : evaluates to true.\n\
1310 : : \n\
1311 : : composition N\n\
1312 : : Prints all the compositions of N on stdout.\n\
1313 : : \n\
1314 : : tree-shape N\n\
1315 : : Prints all the tree shapes with N terminals on stdout.\n\
1316 : : \n\
1317 : : exhaustive N\n\
1318 : : Tests that all possible Boolean expressions with N terminals are properly\n\
1319 : : simplified, normalized, and converted to flows. Available options:\n\
1320 : : Overall options:\n\
1321 : : --operation=OPERATION Operation to test, one of: convert, simplify,\n\
1322 : : normalize, flow. Default: flow. 'normalize' includes 'simplify',\n\
1323 : : 'flow' includes 'simplify' and 'normalize'.\n\
1324 : : --parallel=N Number of processes to use in parallel, default 1.\n\
1325 : : Numeric vars:\n\
1326 : : --nvars=N Number of numeric vars to test, in range 0...4, default 2.\n\
1327 : : --bits=N Number of bits per variable, in range 1...3, default 3.\n\
1328 : : --relops=OPERATORS Test only the specified Boolean operators.\n\
1329 : : OPERATORS may include == != < <= > >=, space or\n\
1330 : : comma separated. Default is all operators.\n\
1331 : : String vars:\n\
1332 : : --svars=N Number of string vars to test, in range 0...4, default 2.\n\
1333 : : \n\
1334 : : parse-actions\n\
1335 : : Parses OVN actions from stdin and prints the equivalent OpenFlow actions\n\
1336 : : on stdout.\n\
1337 : : ",
1338 : : program_name, program_name);
1339 : 0 : exit(EXIT_SUCCESS);
1340 : : }
1341 : :
1342 : : static void
1343 : 40 : test_ovn_main(int argc, char *argv[])
1344 : : {
1345 : : enum {
1346 : : OPT_RELOPS = UCHAR_MAX + 1,
1347 : : OPT_NVARS,
1348 : : OPT_SVARS,
1349 : : OPT_BITS,
1350 : : OPT_OPERATION,
1351 : : OPT_PARALLEL
1352 : : };
1353 : : static const struct option long_options[] = {
1354 : : {"relops", required_argument, NULL, OPT_RELOPS},
1355 : : {"nvars", required_argument, NULL, OPT_NVARS},
1356 : : {"svars", required_argument, NULL, OPT_SVARS},
1357 : : {"bits", required_argument, NULL, OPT_BITS},
1358 : : {"operation", required_argument, NULL, OPT_OPERATION},
1359 : : {"parallel", required_argument, NULL, OPT_PARALLEL},
1360 : : {"more", no_argument, NULL, 'm'},
1361 : : {"help", no_argument, NULL, 'h'},
1362 : : {NULL, 0, NULL, 0},
1363 : : };
1364 : 40 : char *short_options = ovs_cmdl_long_options_to_short_options(long_options);
1365 : :
1366 : 40 : set_program_name(argv[0]);
1367 : :
1368 : 40 : test_relops = parse_relops("== != < <= > >=");
1369 : : for (;;) {
1370 : 98 : int option_index = 0;
1371 : 98 : int c = getopt_long (argc, argv, short_options, long_options,
1372 : : &option_index);
1373 : :
1374 [ + + ]: 98 : if (c == -1) {
1375 : 40 : break;
1376 : : }
1377 [ + + + + : 58 : switch (c) {
+ - - - -
- ]
1378 : : case OPT_RELOPS:
1379 : 6 : test_relops = parse_relops(optarg);
1380 : 6 : break;
1381 : :
1382 : : case OPT_NVARS:
1383 : 13 : test_nvars = atoi(optarg);
1384 [ + - ][ - + ]: 13 : if (test_nvars < 0 || test_nvars > 4) {
1385 : 0 : ovs_fatal(0, "number of numeric variables must be "
1386 : : "between 0 and 4");
1387 : : }
1388 : 13 : break;
1389 : :
1390 : : case OPT_SVARS:
1391 : 13 : test_svars = atoi(optarg);
1392 [ + - ][ - + ]: 13 : if (test_svars < 0 || test_svars > 4) {
1393 : 0 : ovs_fatal(0, "number of string variables must be "
1394 : : "between 0 and 4");
1395 : : }
1396 : 13 : break;
1397 : :
1398 : : case OPT_BITS:
1399 : 10 : test_bits = atoi(optarg);
1400 [ + - ][ - + ]: 10 : if (test_bits < 1 || test_bits > 3) {
1401 : 0 : ovs_fatal(0, "number of bits must be between 1 and 3");
1402 : : }
1403 : 10 : break;
1404 : :
1405 : : case OPT_OPERATION:
1406 [ + + ]: 16 : if (!strcmp(optarg, "convert")) {
1407 : 3 : operation = OP_CONVERT;
1408 [ + + ]: 13 : } else if (!strcmp(optarg, "simplify")) {
1409 : 3 : operation = OP_SIMPLIFY;
1410 [ + + ]: 10 : } else if (!strcmp(optarg, "normalize")) {
1411 : 6 : operation = OP_NORMALIZE;
1412 [ + - ]: 4 : } else if (!strcmp(optarg, "flow")) {
1413 : 4 : operation = OP_FLOW;
1414 : : } else {
1415 : 0 : ovs_fatal(0, "%s: unknown operation", optarg);
1416 : : }
1417 : 16 : break;
1418 : :
1419 : : case OPT_PARALLEL:
1420 : 0 : test_parallel = atoi(optarg);
1421 : 0 : break;
1422 : :
1423 : : case 'm':
1424 : 0 : verbosity++;
1425 : 0 : break;
1426 : :
1427 : : case 'h':
1428 : 0 : usage();
1429 : :
1430 : : case '?':
1431 : 0 : exit(1);
1432 : :
1433 : : default:
1434 : 0 : abort();
1435 : : }
1436 : 58 : }
1437 : 40 : free(short_options);
1438 : :
1439 : : static const struct ovs_cmdl_command commands[] = {
1440 : : /* Lexer. */
1441 : : {"lex", NULL, 0, 0, test_lex, OVS_RO},
1442 : :
1443 : : /* Symbol table. */
1444 : : {"dump-symtab", NULL, 0, 0, test_dump_symtab, OVS_RO},
1445 : :
1446 : : /* Expressions. */
1447 : : {"parse-expr", NULL, 0, 0, test_parse_expr, OVS_RO},
1448 : : {"annotate-expr", NULL, 0, 0, test_annotate_expr, OVS_RO},
1449 : : {"simplify-expr", NULL, 0, 0, test_simplify_expr, OVS_RO},
1450 : : {"normalize-expr", NULL, 0, 0, test_normalize_expr, OVS_RO},
1451 : : {"expr-to-flows", NULL, 0, 0, test_expr_to_flows, OVS_RO},
1452 : : {"evaluate-expr", NULL, 1, 1, test_evaluate_expr, OVS_RO},
1453 : : {"composition", NULL, 1, 1, test_composition, OVS_RO},
1454 : : {"tree-shape", NULL, 1, 1, test_tree_shape, OVS_RO},
1455 : : {"exhaustive", NULL, 1, 1, test_exhaustive, OVS_RO},
1456 : :
1457 : : /* Actions. */
1458 : : {"parse-actions", NULL, 0, 0, test_parse_actions, OVS_RO},
1459 : :
1460 : : {NULL, NULL, 0, 0, NULL, OVS_RO},
1461 : : };
1462 : : struct ovs_cmdl_context ctx;
1463 : 40 : ctx.argc = argc - optind;
1464 : 40 : ctx.argv = argv + optind;
1465 : 40 : ovs_cmdl_run_command(&ctx, commands);
1466 : 39 : }
1467 : :
1468 : 1253 : OVSTEST_REGISTER("test-ovn", test_ovn_main);
|
