tests/test-ovn.c

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