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 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 struct expr_symbol *expr_symtab_add_field(struct shash *symtab,
 252                                           const char *name, enum mf_field_id,
 253                                           const char *prereqs,
 254                                           bool must_crossproduct);
 255 struct expr_symbol *expr_symtab_add_subfield(struct shash *symtab,
 256                                              const char *name,
 257                                              const char *prereqs,
 258                                              const char *subfield);
 259 struct expr_symbol *expr_symtab_add_string(struct shash *symtab,
 260                                            const char *name, enum mf_field_id,
 261                                            const char *prereqs);
 262 struct expr_symbol *expr_symtab_add_predicate(struct shash *symtab,
 263                                               const char *name,
 264                                               const char *expansion);
 265 void expr_symtab_destroy(struct shash *symtab);
 266 \f
 267 /* Expression type. */
 268 enum expr_type {
 269     EXPR_T_CMP,                 /* Compare symbol with constant. */
 270     EXPR_T_AND,                 /* Logical AND of 2 or more subexpressions. */
 271     EXPR_T_OR,                  /* Logical OR of 2 or more subexpressions. */
 272     EXPR_T_BOOLEAN,             /* True or false constant. */
 273 };
 274
 275 /* Relational operator. */
 276 enum expr_relop {
 277     EXPR_R_EQ,                  /* == */
 278     EXPR_R_NE,                  /* != */
 279     EXPR_R_LT,                  /* < */
 280     EXPR_R_LE,                  /* <= */
 281     EXPR_R_GT,                  /* > */
 282     EXPR_R_GE,                  /* >= */
 283 };
 284 const char *expr_relop_to_string(enum expr_relop);
 285 bool expr_relop_from_token(enum lex_type type, enum expr_relop *relop);
 286
 287 /* An abstract syntax tree for a matching expression.
 288  *
 289  * The expression code maintains and relies on a few important invariants:
 290  *
 291  *     - An EXPR_T_AND or EXPR_T_OR node never has a child of the same type.
 292  *       (Any such children could be merged into their parent.)  A node may
 293  *       have grandchildren of its own type.
 294  *
 295  *       As a consequence, every nonterminal node at the same distance from the
 296  *       root has the same type.
 297  *
 298  *     - EXPR_T_AND and EXPR_T_OR nodes must have at least two children.
 299  *
 300  *     - An EXPR_T_CMP node always has a nonzero mask, and never has a 1-bit
 301  *       in its value in a position where the mask is a 0-bit.
 302  *
 303  * The expr_honors_invariants() function can check invariants. */
 304 struct expr {
 305     struct ovs_list node;       /* In parent EXPR_T_AND or EXPR_T_OR if any. */
 306     enum expr_type type;        /* Expression type. */
 307
 308     union {
 309         /* EXPR_T_CMP.
 310          *
 311          * The symbol is on the left, e.g. "field < constant". */
 312         struct {
 313             const struct expr_symbol *symbol;
 314             enum expr_relop relop;
 315
 316             union {
 317                 char *string;
 318                 struct {
 319                     union mf_subvalue value;
 320                     union mf_subvalue mask;
 321                 };
 322             };
 323         } cmp;
 324
 325         /* EXPR_T_AND, EXPR_T_OR. */
 326         struct ovs_list andor;
 327
 328         /* EXPR_T_BOOLEAN. */
 329         bool boolean;
 330     };
 331 };
 332
 333 struct expr *expr_create_boolean(bool b);
 334 struct expr *expr_create_andor(enum expr_type);
 335 struct expr *expr_combine(enum expr_type, struct expr *a, struct expr *b);
 336
 337 static inline struct expr *
 338 expr_from_node(const struct ovs_list *node)
 339 {
 340     return CONTAINER_OF(node, struct expr, node);
 341 }
 342
 343 void expr_format(const struct expr *, struct ds *);
 344 void expr_print(const struct expr *);
 345 struct expr *expr_parse(struct lexer *, const struct shash *symtab,
 346                         char **errorp);
 347 struct expr *expr_parse_string(const char *, const struct shash *symtab,
 348                                char **errorp);
 349
 350 struct expr *expr_clone(struct expr *);
 351 void expr_destroy(struct expr *);
 352
 353 struct expr *expr_annotate(struct expr *, const struct shash *symtab,
 354                            char **errorp);
 355 struct expr *expr_simplify(struct expr *);
 356 struct expr *expr_normalize(struct expr *);
 357
 358 bool expr_honors_invariants(const struct expr *);
 359 bool expr_is_simplified(const struct expr *);
 360 bool expr_is_normalized(const struct expr *);
 361 \f
 362 /* Converting expressions to OpenFlow flows. */
 363
 364 /* An OpenFlow match generated from a Boolean expression.  See
 365  * expr_to_matches() for more information. */
 366 struct expr_match {
 367     struct hmap_node hmap_node;
 368     struct match match;
 369     struct cls_conjunction *conjunctions;
 370     size_t n, allocated;
 371 };
 372
 373 uint32_t expr_to_matches(const struct expr *, const struct simap *ports,
 374                          struct hmap *matches);
 375 void expr_matches_destroy(struct hmap *matches);
 376 void expr_matches_print(const struct hmap *matches, FILE *);
 377 \f
 378 /* Action parsing helper. */
 379
 380 char *expr_parse_assignment(struct lexer *lexer, const struct shash *symtab,
 381                             const struct simap *ports, struct ofpbuf *ofpacts,
 382                             struct expr **prereqsp);
 383
 384 #endif /* ovn/expr.h */