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