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