tests/test-ovn.c

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