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