ovn/lib/expr.h

   1 /*
   2  * Copyright (c) 2015, 2016 Nicira, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at:
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #ifndef OVN_EXPR_H
  18 #define OVN_EXPR_H 1
  19
  20 /* OVN matching expression tree
  21  * ============================
  22  *
  23  * The data structures here form an abstract expression tree for matching
  24  * expressions in OVN.
  25  *
  26  * The abstract syntax tree representation of a matching expression is one of:
  27  *
  28  *    - A Boolean literal ("true" or "false").
  29  *
  30  *    - A comparison of a field (or part of a field) against a constant
  31  *      with one of the operators == != < <= > >=.
  32  *
  33  *    - The logical AND or OR of two or more matching expressions.
  34  *
  35  * Literals and comparisons are called "terminal" nodes, logical AND and OR
  36  * nodes are "nonterminal" nodes.
  37  *
  38  * The syntax for expressions includes a few other concepts that are not part
  39  * of the abstract syntax tree.  In these examples, x is a field, a, b, and c
  40  * are constants, and e1 and e2 are arbitrary expressions:
  41  *
  42  *    - Logical NOT.  The parser implements NOT by inverting the sense of the
  43  *      operand: !(x == a) becomes x != a, !(e1 && e2) becomes !e1 || !e2, and
  44  *      so on.
  45  *
  46  *    - Set membership.  The parser translates x == {a, b, c} into
  47  *      x == a || x == b || x == c.
  48  *
  49  *    - Reversed comparisons.  The parser translates a < x into x > a.
  50  *
  51  *    - Range expressions.  The parser translates a < x < b into
  52  *      x > a && x < b.
  53  */
  54
  55 #include "classifier.h"
  56 #include "lex.h"
  57 #include "openvswitch/hmap.h"
  58 #include "openvswitch/list.h"
  59 #include "openvswitch/match.h"
  60 #include "openvswitch/meta-flow.h"
  61
  62 struct ds;
  63 struct ofpbuf;
  64 struct shash;
  65 struct simap;
  66
  67 /* "Measurement level" of a field.  See "Level of Measurement" in the large
  68  * comment on struct expr_symbol below for more information. */
  69 enum expr_level {
  70     EXPR_L_NOMINAL,
  71
  72     /* Boolean values are nominal, however because of their simple nature OVN
  73      * can allow both equality and inequality tests on them. */
  74     EXPR_L_BOOLEAN,
  75
  76     /* Ordinal values can at least be ordered on a scale.  OVN allows equality
  77      * and inequality and relational tests on ordinal values.  These are the
  78      * fields on which OVS allows bitwise matching. */
  79     EXPR_L_ORDINAL
  80 };
  81
  82 const char *expr_level_to_string(enum expr_level);
  83 \f
  84 /* A symbol.
  85  *
  86  *
  87  * Name
  88  * ====
  89  *
  90  * Every symbol must have a name.  To be useful, the name must satisfy the
  91  * lexer's syntax for an identifier.
  92  *
  93  *
  94  * Width
  95  * =====
  96  *
  97  * Every symbol has a width.  For integer symbols, this is the number of bits
  98  * in the value; for string symbols, this is 0.
  99  *
 100  *
 101  * Types
 102  * =====
 103  *
 104  * There are three kinds of symbols:
 105  *
 106  *   Fields:
 107  *
 108  *     One might, for example, define a field named "vlan.tci" to refer to
 109  *     MFF_VLAN_TCI.  For integer fields, 'field' specifies the referent; for
 110  *     string fields, 'field' is NULL.
 111  *
 112  *     'expansion' is NULL.
 113  *
 114  *     Integer fields can be nominal or ordinal (see below).  String fields are
 115  *     always nominal.
 116  *
 117  *   Subfields:
 118  *
 119  *     'expansion' is a string that specifies a subfield of some larger field,
 120  *     e.g. "vlan.tci[0..11]" for a field that represents a VLAN VID.
 121  *
 122  *     'field' is NULL.
 123  *
 124  *     Only ordinal fields (see below) may have subfields, and subfields are
 125  *     always ordinal.
 126  *
 127  *   Predicates:
 128  *
 129  *     A predicate is an arbitrary Boolean expression that can be used in an
 130  *     expression much like a 1-bit field.  'expansion' specifies the Boolean
 131  *     expression, e.g. "ip4" might expand to "eth.type == 0x800".  The
 132  *     expansion of a predicate might refer to other predicates, e.g. "icmp4"
 133  *     might expand to "ip4 && ip4.proto == 1".
 134  *
 135  *     'field' is NULL.
 136  *
 137  *     A predicate whose expansion refers to any nominal field or predicate
 138  *     (see below) is nominal; other predicates have Boolean level of
 139  *     measurement.
 140  *
 141  *
 142  * Level of Measurement
 143  * ====================
 144  *
 145  * See http://en.wikipedia.org/wiki/Level_of_measurement for the statistical
 146  * concept on which this classification is based.  There are three levels:
 147  *
 148  *   Ordinal:
 149  *
 150  *     In statistics, ordinal values can be ordered on a scale.  Here, we
 151  *     consider a field (or subfield) to be ordinal if its bits can be examined
 152  *     individually.  This is true for the OpenFlow fields that OpenFlow or
 153  *     Open vSwitch makes "maskable".
 154  *
 155  *     OVN supports all the usual arithmetic relations (== != < <= > >=) on
 156  *     ordinal fields and their subfields, because all of these can be
 157  *     implemented as collections of bitwise tests.
 158  *
 159  *   Nominal:
 160  *
 161  *     In statistics, nominal values cannot be usefully compared except for
 162  *     equality.  This is true of OpenFlow port numbers, Ethernet types, and IP
 163  *     protocols are examples: all of these are just identifiers assigned
 164  *     arbitrarily with no deeper meaning.  In OpenFlow and Open vSwitch, bits
 165  *     in these fields generally aren't individually addressable.
 166  *
 167  *     OVN only supports arithmetic tests for equality on nominal fields,
 168  *     because OpenFlow and Open vSwitch provide no way for a flow to
 169  *     efficiently implement other comparisons on them.  (A test for inequality
 170  *     can be sort of built out of two flows with different priorities, but OVN
 171  *     matching expressions always generate flows with a single priority.)
 172  *
 173  *     String fields are always nominal.
 174  *
 175  *   Boolean:
 176  *
 177  *     A nominal field that has only two values, 0 and 1, is somewhat
 178  *     exceptional, since it is easy to support both equality and inequality
 179  *     tests on such a field: either one can be implemented as a test for 0 or
 180  *     1.
 181  *
 182  *     Only predicates (see above) have a Boolean level of measurement.
 183  *
 184  *     This isn't a standard level of measurement.
 185  *
 186  *
 187  * Prerequisites
 188  * =============
 189  *
 190  * Any symbol can have prerequisites, which are specified as a string giving an
 191  * additional expression that must be true whenever the symbol is referenced.
 192  * For example, the "icmp4.type" symbol might have prerequisite "icmp4", which
 193  * would cause an expression "icmp4.type == 0" to be interpreted as "icmp4.type
 194  * == 0 && icmp4", which would in turn expand to "icmp4.type == 0 && eth.type
 195  * == 0x800 && ip4.proto == 1" (assuming "icmp4" is a predicate defined as
 196  * suggested under "Types" above).
 197  *
 198  *
 199  * Crossproducting
 200  * ===============
 201  *
 202  * Ordinarily OVN is willing to consider using any field as a dimension in the
 203  * Open vSwitch "conjunctive match" extension (see ovs-ofctl(8)).  However,
 204  * some fields can't actually be used that way because they are necessary as
 205  * prerequisites.  For example, from an expression like "tcp.src == {1,2,3}
 206  * && tcp.dst == {4,5,6}", OVN might naturally generate flows like this:
 207  *
 208  *     conj_id=1,actions=...
 209  *     ip,actions=conjunction(1,1/3)
 210  *     ip6,actions=conjunction(1,1/3)
 211  *     tp_src=1,actions=conjunction(1,2/3)
 212  *     tp_src=2,actions=conjunction(1,2/3)
 213  *     tp_src=3,actions=conjunction(1,2/3)
 214  *     tp_dst=4,actions=conjunction(1,3/3)
 215  *     tp_dst=5,actions=conjunction(1,3/3)
 216  *     tp_dst=6,actions=conjunction(1,3/3)
 217  *
 218  * but that's not valid because any flow that matches on tp_src or tp_dst must
 219  * also match on either ip or ip6.  Thus, one would mark eth.type as "must
 220  * crossproduct", to force generating flows like this:
 221  *
 222  *     conj_id=1,actions=...
 223  *     ip,tp_src=1,actions=conjunction(1,1/2)
 224  *     ip,tp_src=2,actions=conjunction(1,1/2)
 225  *     ip,tp_src=3,actions=conjunction(1,1/2)
 226  *     ip6,tp_src=1,actions=conjunction(1,1/2)
 227  *     ip6,tp_src=2,actions=conjunction(1,1/2)
 228  *     ip6,tp_src=3,actions=conjunction(1,1/2)
 229  *     ip,tp_dst=4,actions=conjunction(1,2/2)
 230  *     ip,tp_dst=5,actions=conjunction(1,2/2)
 231  *     ip,tp_dst=6,actions=conjunction(1,2/2)
 232  *     ip6,tp_dst=4,actions=conjunction(1,2/2)
 233  *     ip6,tp_dst=5,actions=conjunction(1,2/2)
 234  *     ip6,tp_dst=6,actions=conjunction(1,2/2)
 235  *
 236  * which are acceptable.
 237  */
 238 struct expr_symbol {
 239     char *name;
 240     int width;
 241
 242     const struct mf_field *field;
 243     char *expansion;
 244
 245     enum expr_level level;
 246
 247     char *prereqs;
 248     bool must_crossproduct;
 249 };
 250
 251 /* A reference to a symbol or a subfield of a symbol.
 252  *
 253  * For string fields, ofs and n_bits are 0. */
 254 struct expr_field {
 255     const struct expr_symbol *symbol; /* The symbol. */
 256     int ofs;                          /* Starting bit offset. */
 257     int n_bits;                       /* Number of bits. */
 258 };
 259
 260 struct expr_symbol *expr_symtab_add_field(struct shash *symtab,
 261                                           const char *name, enum mf_field_id,
 262                                           const char *prereqs,
 263                                           bool must_crossproduct);
 264 struct expr_symbol *expr_symtab_add_subfield(struct shash *symtab,
 265                                              const char *name,
 266                                              const char *prereqs,
 267                                              const char *subfield);
 268 struct expr_symbol *expr_symtab_add_string(struct shash *symtab,
 269                                            const char *name, enum mf_field_id,
 270                                            const char *prereqs);
 271 struct expr_symbol *expr_symtab_add_predicate(struct shash *symtab,
 272                                               const char *name,
 273                                               const char *expansion);
 274 void expr_symtab_destroy(struct shash *symtab);
 275 \f
 276 /* Expression type. */
 277 enum expr_type {
 278     EXPR_T_CMP,                 /* Compare symbol with constant. */
 279     EXPR_T_AND,                 /* Logical AND of 2 or more subexpressions. */
 280     EXPR_T_OR,                  /* Logical OR of 2 or more subexpressions. */
 281     EXPR_T_BOOLEAN,             /* True or false constant. */
 282 };
 283
 284 /* Relational operator. */
 285 enum expr_relop {
 286     EXPR_R_EQ,                  /* == */
 287     EXPR_R_NE,                  /* != */
 288     EXPR_R_LT,                  /* < */
 289     EXPR_R_LE,                  /* <= */
 290     EXPR_R_GT,                  /* > */
 291     EXPR_R_GE,                  /* >= */
 292 };
 293 const char *expr_relop_to_string(enum expr_relop);
 294 bool expr_relop_from_token(enum lex_type type, enum expr_relop *relop);
 295
 296 /* An abstract syntax tree for a matching expression.
 297  *
 298  * The expression code maintains and relies on a few important invariants:
 299  *
 300  *     - An EXPR_T_AND or EXPR_T_OR node never has a child of the same type.
 301  *       (Any such children could be merged into their parent.)  A node may
 302  *       have grandchildren of its own type.
 303  *
 304  *       As a consequence, every nonterminal node at the same distance from the
 305  *       root has the same type.
 306  *
 307  *     - EXPR_T_AND and EXPR_T_OR nodes must have at least two children.
 308  *
 309  *     - An EXPR_T_CMP node always has a nonzero mask, and never has a 1-bit
 310  *       in its value in a position where the mask is a 0-bit.
 311  *
 312  * The expr_honors_invariants() function can check invariants. */
 313 struct expr {
 314     struct ovs_list node;       /* In parent EXPR_T_AND or EXPR_T_OR if any. */
 315     enum expr_type type;        /* Expression type. */
 316
 317     union {
 318         /* EXPR_T_CMP.
 319          *
 320          * The symbol is on the left, e.g. "field < constant". */
 321         struct {
 322             const struct expr_symbol *symbol;
 323             enum expr_relop relop;
 324
 325             union {
 326                 char *string;
 327                 struct {
 328                     union mf_subvalue value;
 329                     union mf_subvalue mask;
 330                 };
 331             };
 332         } cmp;
 333
 334         /* EXPR_T_AND, EXPR_T_OR. */
 335         struct ovs_list andor;
 336
 337         /* EXPR_T_BOOLEAN. */
 338         bool boolean;
 339     };
 340 };
 341
 342 struct expr *expr_create_boolean(bool b);
 343 struct expr *expr_create_andor(enum expr_type);
 344 struct expr *expr_combine(enum expr_type, struct expr *a, struct expr *b);
 345
 346 static inline struct expr *
 347 expr_from_node(const struct ovs_list *node)
 348 {
 349     return CONTAINER_OF(node, struct expr, node);
 350 }
 351
 352 void expr_format(const struct expr *, struct ds *);
 353 void expr_print(const struct expr *);
 354 struct expr *expr_parse(struct lexer *, const struct shash *symtab,
 355                         const struct shash *macros,
 356                         char **errorp);
 357 struct expr *expr_parse_string(const char *, const struct shash *symtab,
 358                                const struct shash *macros,
 359                                char **errorp);
 360
 361 struct expr *expr_clone(struct expr *);
 362 void expr_destroy(struct expr *);
 363
 364 struct expr *expr_annotate(struct expr *, const struct shash *symtab,
 365                            char **errorp);
 366 struct expr *expr_simplify(struct expr *);
 367 struct expr *expr_normalize(struct expr *);
 368
 369 bool expr_honors_invariants(const struct expr *);
 370 bool expr_is_simplified(const struct expr *);
 371 bool expr_is_normalized(const struct expr *);
 372 \f
 373 /* Converting expressions to OpenFlow flows. */
 374
 375 /* An OpenFlow match generated from a Boolean expression.  See
 376  * expr_to_matches() for more information. */
 377 struct expr_match {
 378     struct hmap_node hmap_node;
 379     struct match match;
 380     struct cls_conjunction *conjunctions;
 381     size_t n, allocated;
 382 };
 383
 384 uint32_t expr_to_matches(const struct expr *,
 385                          bool (*lookup_port)(const void *aux,
 386                                              const char *port_name,
 387                                              unsigned int *portp),
 388                          const void *aux,
 389                          struct hmap *matches);
 390 void expr_matches_destroy(struct hmap *matches);
 391 void expr_matches_print(const struct hmap *matches, FILE *);
 392 \f
 393 /* Action parsing helper. */
 394
 395 char *expr_parse_assignment(struct lexer *lexer, struct expr_field *dst,
 396                             const struct shash *symtab,
 397                             bool (*lookup_port)(const void *aux,
 398                                                 const char *port_name,
 399                                                 unsigned int *portp),
 400                             const void *aux,
 401                             struct ofpbuf *ofpacts, struct expr **prereqsp)
 402     OVS_WARN_UNUSED_RESULT;
 403 char *expr_parse_exchange(struct lexer *lexer, struct expr_field *dst,
 404                           const struct shash *symtab,
 405                           bool (*lookup_port)(const void *aux,
 406                                               const char *port_name,
 407                                               unsigned int *portp),
 408                           const void *aux,
 409                           struct ofpbuf *ofpacts, struct expr **prereqsp)
 410     OVS_WARN_UNUSED_RESULT;
 411 char *expr_parse_field(struct lexer *lexer, const struct shash *symtab,
 412                        struct expr_field *field)
 413     OVS_WARN_UNUSED_RESULT;
 414 char *expr_expand_field(struct lexer *lexer, const struct shash *symtab,
 415                         const struct expr_field *orig_field,
 416                         int n_bits, bool rw,
 417                         struct mf_subfield *sf, struct expr **prereqsp)
 418     OVS_WARN_UNUSED_RESULT;
 419
 420 /* Type of a "union expr_constant" or "struct expr_constant_set". */
 421 enum expr_constant_type {
 422     EXPR_C_INTEGER,
 423     EXPR_C_STRING
 424 };
 425
 426 /* A string or integer constant (one must know which from context). */
 427 union expr_constant {
 428     /* Integer constant.
 429      *
 430      * The width of a constant isn't always clear, e.g. if you write "1",
 431      * there's no way to tell whether you mean for that to be a 1-bit constant
 432      * or a 128-bit constant or somewhere in between. */
 433     struct {
 434         union mf_subvalue value;
 435         union mf_subvalue mask; /* Only initialized if 'masked'. */
 436         bool masked;
 437
 438         enum lex_format format; /* From the constant's lex_token. */
 439     };
 440
 441     /* Null-terminated string constant. */
 442     char *string;
 443 };
 444
 445 /* A collection of "union expr_constant"s of the same type. */
 446 struct expr_constant_set {
 447     union expr_constant *values;  /* Constants. */
 448     size_t n_values;              /* Number of constants. */
 449     enum expr_constant_type type; /* Type of the constants. */
 450     bool in_curlies;              /* Whether the constants were in {}. */
 451 };
 452
 453 char *expr_parse_constant_set(struct lexer *, const struct shash *symtab,
 454                               struct expr_constant_set *cs)
 455     OVS_WARN_UNUSED_RESULT;
 456 void expr_constant_set_destroy(struct expr_constant_set *cs);
 457
 458 \f
 459 /* Address sets, aka "macros".
 460  *
 461  * Instead of referring to a set of value as:
 462  *    {addr1, addr2, ..., addrN}
 463  * You can register a set of values and refer to them as:
 464  *    $name
 465  * The macros should all have integer/masked-integer values.
 466  * The values that don't qualify are ignored.
 467  */
 468
 469 void expr_macros_add(struct shash *macros, const char *name,
 470                      const char * const *values, size_t n_values);
 471 void expr_macros_remove(struct shash *macros, const char *name);
 472 void expr_macros_destroy(struct shash *macros);
 473
 474 #endif /* ovn/expr.h */