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