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