ovn/lib/expr.h

   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 #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 "hmap.h"
  58 #include "list.h"
  59 #include "match.h"
  60 #include "meta-flow.h"
  61
  62 struct ds;
  63 struct shash;
  64 struct simap;
  65
  66 /* "Measurement level" of a field.  See "Level of Measurement" in the large
  67  * comment on struct expr_symbol below for more information. */
  68 enum expr_level {
  69     EXPR_L_NOMINAL,
  70
  71     /* Boolean values are nominal, however because of their simple nature OVN
  72      * can allow both equality and inequality tests on them. */
  73     EXPR_L_BOOLEAN,
  74
  75     /* Ordinal values can at least be ordered on a scale.  OVN allows equality
  76      * and inequality and relational tests on ordinal values.  These are the
  77      * fields on which OVS allows bitwise matching. */
  78     EXPR_L_ORDINAL
  79 };
  80
  81 const char *expr_level_to_string(enum expr_level);
  82 \f
  83 /* A symbol.
  84  *
  85  *
  86  * Name
  87  * ====
  88  *
  89  * Every symbol must have a name.  To be useful, the name must satisfy the
  90  * lexer's syntax for an identifier.
  91  *
  92  *
  93  * Width
  94  * =====
  95  *
  96  * Every symbol has a width.  For integer symbols, this is the number of bits
  97  * in the value; for string symbols, this is 0.
  98  *
  99  *
 100  * Types
 101  * =====
 102  *
 103  * There are three kinds of symbols:
 104  *
 105  *   Fields:
 106  *
 107  *     One might, for example, define a field named "vlan.tci" to refer to
 108  *     MFF_VLAN_TCI.  For integer fields, 'field' specifies the referent; for
 109  *     string fields, 'field' is NULL.
 110  *
 111  *     'expansion' is NULL.
 112  *
 113  *     Integer fields can be nominal or ordinal (see below).  String fields are
 114  *     always nominal.
 115  *
 116  *   Subfields:
 117  *
 118  *     'expansion' is a string that specifies a subfield of some larger field,
 119  *     e.g. "vlan.tci[0..11]" for a field that represents a VLAN VID.
 120  *
 121  *     'field' is NULL.
 122  *
 123  *     Only ordinal fields (see below) may have subfields, and subfields are
 124  *     always ordinal.
 125  *
 126  *   Predicates:
 127  *
 128  *     A predicate is an arbitrary Boolean expression that can be used in an
 129  *     expression much like a 1-bit field.  'expansion' specifies the Boolean
 130  *     expression, e.g. "ip4" might expand to "eth.type == 0x800".  The
 131  *     expansion of a predicate might refer to other predicates, e.g. "icmp4"
 132  *     might expand to "ip4 && ip4.proto == 1".
 133  *
 134  *     'field' is NULL.
 135  *
 136  *     A predicate whose expansion refers to any nominal field or predicate
 137  *     (see below) is nominal; other predicates have Boolean level of
 138  *     measurement.
 139  *
 140  *
 141  * Level of Measurement
 142  * ====================
 143  *
 144  * See http://en.wikipedia.org/wiki/Level_of_measurement for the statistical
 145  * concept on which this classification is based.  There are three levels:
 146  *
 147  *   Ordinal:
 148  *
 149  *     In statistics, ordinal values can be ordered on a scale.  Here, we
 150  *     consider a field (or subfield) to be ordinal if its bits can be examined
 151  *     individually.  This is true for the OpenFlow fields that OpenFlow or
 152  *     Open vSwitch makes "maskable".
 153  *
 154  *     OVN supports all the usual arithmetic relations (== != < <= > >=) on
 155  *     ordinal fields and their subfields, because all of these can be
 156  *     implemented as collections of bitwise tests.
 157  *
 158  *   Nominal:
 159  *
 160  *     In statistics, nominal values cannot be usefully compared except for
 161  *     equality.  This is true of OpenFlow port numbers, Ethernet types, and IP
 162  *     protocols are examples: all of these are just identifiers assigned
 163  *     arbitrarily with no deeper meaning.  In OpenFlow and Open vSwitch, bits
 164  *     in these fields generally aren't individually addressable.
 165  *
 166  *     OVN only supports arithmetic tests for equality on nominal fields,
 167  *     because OpenFlow and Open vSwitch provide no way for a flow to
 168  *     efficiently implement other comparisons on them.  (A test for inequality
 169  *     can be sort of built out of two flows with different priorities, but OVN
 170  *     matching expressions always generate flows with a single priority.)
 171  *
 172  *     String fields are always nominal.
 173  *
 174  *   Boolean:
 175  *
 176  *     A nominal field that has only two values, 0 and 1, is somewhat
 177  *     exceptional, since it is easy to support both equality and inequality
 178  *     tests on such a field: either one can be implemented as a test for 0 or
 179  *     1.
 180  *
 181  *     Only predicates (see above) have a Boolean level of measurement.
 182  *
 183  *     This isn't a standard level of measurement.
 184  *
 185  *
 186  * Prerequisites
 187  * =============
 188  *
 189  * Any symbol can have prerequisites, which are specified as a string giving an
 190  * additional expression that must be true whenever the symbol is referenced.
 191  * For example, the "icmp4.type" symbol might have prerequisite "icmp4", which
 192  * would cause an expression "icmp4.type == 0" to be interpreted as "icmp4.type
 193  * == 0 && icmp4", which would in turn expand to "icmp4.type == 0 && eth.type
 194  * == 0x800 && ip4.proto == 1" (assuming "icmp4" is a predicate defined as
 195  * suggested under "Types" above).
 196  *
 197  *
 198  * Crossproducting
 199  * ===============
 200  *
 201  * Ordinarily OVN is willing to consider using any field as a dimension in the
 202  * Open vSwitch "conjunctive match" extension (see ovs-ofctl(8)).  However,
 203  * some fields can't actually be used that way because they are necessary as
 204  * prerequisites.  For example, from an expression like "tcp.src == {1,2,3}
 205  * && tcp.dst == {4,5,6}", OVN might naturally generate flows like this:
 206  *
 207  *     conj_id=1,actions=...
 208  *     ip,actions=conjunction(1,1/3)
 209  *     ip6,actions=conjunction(1,1/3)
 210  *     tp_src=1,actions=conjunction(1,2/3)
 211  *     tp_src=2,actions=conjunction(1,2/3)
 212  *     tp_src=2,actions=conjunction(1,2/3)
 213  *     tp_dst=4,actions=conjunction(1,3/3)
 214  *     tp_dst=5,actions=conjunction(1,3/3)
 215  *     tp_dst=6,actions=conjunction(1,3/3)
 216  *
 217  * but that's not valid because any flow that matches on tp_src or tp_dst must
 218  * also match on either ip or ip6.  Thus, one would mark eth.type as "must
 219  * crossproduct", to force generating flows like this:
 220  *
 221  *     conj_id=1,actions=...
 222  *     ip,tp_src=1,actions=conjunction(1,1/2)
 223  *     ip,tp_src=2,actions=conjunction(1,1/2)
 224  *     ip,tp_src=2,actions=conjunction(1,1/2)
 225  *     ip6,tp_src=1,actions=conjunction(1,1/2)
 226  *     ip6,tp_src=2,actions=conjunction(1,1/2)
 227  *     ip6,tp_src=2,actions=conjunction(1,1/2)
 228  *     ip,tp_dst=4,actions=conjunction(1,2/2)
 229  *     ip,tp_dst=5,actions=conjunction(1,2/2)
 230  *     ip,tp_dst=6,actions=conjunction(1,2/2)
 231  *     ip6,tp_dst=4,actions=conjunction(1,2/2)
 232  *     ip6,tp_dst=5,actions=conjunction(1,2/2)
 233  *     ip6,tp_dst=6,actions=conjunction(1,2/2)
 234  *
 235  * which are acceptable.
 236  */
 237 struct expr_symbol {
 238     char *name;
 239     int width;
 240
 241     const struct mf_field *field;
 242     char *expansion;
 243
 244     enum expr_level level;
 245
 246     char *prereqs;
 247     bool must_crossproduct;
 248 };
 249
 250 struct expr_symbol *expr_symtab_add_field(struct shash *symtab,
 251                                           const char *name, enum mf_field_id,
 252                                           const char *prereqs,
 253                                           bool must_crossproduct);
 254 struct expr_symbol *expr_symtab_add_subfield(struct shash *symtab,
 255                                              const char *name,
 256                                              const char *prereqs,
 257                                              const char *subfield);
 258 struct expr_symbol *expr_symtab_add_string(struct shash *symtab,
 259                                            const char *name, enum mf_field_id,
 260                                            const char *prereqs);
 261 struct expr_symbol *expr_symtab_add_predicate(struct shash *symtab,
 262                                               const char *name,
 263                                               const char *expansion);
 264 void expr_symtab_destroy(struct shash *symtab);
 265 \f
 266 /* Expression type. */
 267 enum expr_type {
 268     EXPR_T_CMP,                 /* Compare symbol with constant. */
 269     EXPR_T_AND,                 /* Logical AND of 2 or more subexpressions. */
 270     EXPR_T_OR,                  /* Logical OR of 2 or more subexpressions. */
 271     EXPR_T_BOOLEAN,             /* True or false constant. */
 272 };
 273
 274 /* Relational operator. */
 275 enum expr_relop {
 276     EXPR_R_EQ,                  /* == */
 277     EXPR_R_NE,                  /* != */
 278     EXPR_R_LT,                  /* < */
 279     EXPR_R_LE,                  /* <= */
 280     EXPR_R_GT,                  /* > */
 281     EXPR_R_GE,                  /* >= */
 282 };
 283 const char *expr_relop_to_string(enum expr_relop);
 284 bool expr_relop_from_token(enum lex_type type, enum expr_relop *relop);
 285
 286 /* An abstract syntax tree for a matching expression.
 287  *
 288  * The expression code maintains and relies on a few important invariants:
 289  *
 290  *     - An EXPR_T_AND or EXPR_T_OR node never has a child of the same type.
 291  *       (Any such children could be merged into their parent.)  A node may
 292  *       have grandchildren of its own type.
 293  *
 294  *       As a consequence, every nonterminal node at the same distance from the
 295  *       root of the root has the same type.
 296  *
 297  *     - EXPR_T_AND and EXPR_T_OR nodes must have at least two children.
 298  *
 299  *     - An EXPR_T_CMP node always has a nonzero mask, and never has a 1-bit
 300  *       in its value in a position where the mask is a 0-bit.
 301  *
 302  * The expr_honors_invariants() function can check invariants. */
 303 struct expr {
 304     struct ovs_list node;       /* In parent EXPR_T_AND or EXPR_T_OR if any. */
 305     enum expr_type type;        /* Expression type. */
 306
 307     union {
 308         /* EXPR_T_CMP.
 309          *
 310          * The symbol is on the left, e.g. "field < constant". */
 311         struct {
 312             const struct expr_symbol *symbol;
 313             enum expr_relop relop;
 314
 315             union {
 316                 char *string;
 317                 struct {
 318                     union mf_subvalue value;
 319                     union mf_subvalue mask;
 320                 };
 321             };
 322         } cmp;
 323
 324         /* EXPR_T_AND, EXPR_T_OR. */
 325         struct ovs_list andor;
 326
 327         /* EXPR_T_BOOLEAN. */
 328         bool boolean;
 329     };
 330 };
 331
 332 struct expr *expr_create_boolean(bool b);
 333 struct expr *expr_create_andor(enum expr_type);
 334 struct expr *expr_combine(enum expr_type, struct expr *a, struct expr *b);
 335
 336 static inline struct expr *
 337 expr_from_node(const struct ovs_list *node)
 338 {
 339     return CONTAINER_OF(node, struct expr, node);
 340 }
 341
 342 void expr_format(const struct expr *, struct ds *);
 343 void expr_print(const struct expr *);
 344 struct expr *expr_parse(struct lexer *, const struct shash *, char **errorp);
 345 struct expr *expr_parse_string(const char *, const struct shash *,
 346                                char **errorp);
 347
 348 struct expr *expr_clone(struct expr *);
 349 void expr_destroy(struct expr *);
 350
 351 struct expr *expr_annotate(struct expr *, const struct shash *, char **errorp);
 352 struct expr *expr_simplify(struct expr *);
 353 struct expr *expr_normalize(struct expr *);
 354
 355 bool expr_honors_invariants(const struct expr *);
 356 bool expr_is_simplified(const struct expr *);
 357 bool expr_is_normalized(const struct expr *);
 358 \f
 359 /* Converting expressions to OpenFlow flows. */
 360
 361 /* An OpenFlow match generated from a Boolean expression.  See
 362  * expr_to_matches() for more information. */
 363 struct expr_match {
 364     struct hmap_node hmap_node;
 365     struct match match;
 366     struct cls_conjunction *conjunctions;
 367     size_t n, allocated;
 368 };
 369
 370 uint32_t expr_to_matches(const struct expr *, const struct simap *ports,
 371                          struct hmap *matches);
 372 void expr_matches_destroy(struct hmap *matches);
 373 void expr_matches_print(const struct hmap *matches, FILE *);
 374
 375 #endif /* ovn/expr.h */