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 : : #include <config.h>
18 : : #include "byte-order.h"
19 : : #include "openvswitch/json.h"
20 : : #include "logical-fields.h"
21 : : #include "nx-match.h"
22 : : #include "openvswitch/dynamic-string.h"
23 : : #include "openvswitch/match.h"
24 : : #include "openvswitch/ofp-actions.h"
25 : : #include "openvswitch/vlog.h"
26 : : #include "openvswitch/shash.h"
27 : : #include "ovn/expr.h"
28 : : #include "ovn/lex.h"
29 : : #include "simap.h"
30 : : #include "sset.h"
31 : : #include "util.h"
32 : :
33 : 1270 : VLOG_DEFINE_THIS_MODULE(expr);
34 : :
35 : : static struct expr *parse_and_annotate(const char *s,
36 : : const struct shash *symtab,
37 : : struct ovs_list *nesting,
38 : : char **errorp);
39 : :
40 : : /* Returns the name of measurement level 'level'. */
41 : : const char *
42 : 3 : expr_level_to_string(enum expr_level level)
43 : : {
44 [ + + - - ]: 3 : switch (level) {
45 : 2 : case EXPR_L_NOMINAL: return "nominal";
46 : 1 : case EXPR_L_BOOLEAN: return "Boolean";
47 : 0 : case EXPR_L_ORDINAL: return "ordinal";
48 : 0 : default: OVS_NOT_REACHED();
49 : : }
50 : : }
51 : :
52 : : /* Relational operators. */
53 : :
54 : : /* Returns a string form of relational operator 'relop'. */
55 : : const char *
56 : 103574 : expr_relop_to_string(enum expr_relop relop)
57 : : {
58 [ + + + + : 103574 : switch (relop) {
+ + - ]
59 : 14906 : case EXPR_R_EQ: return "==";
60 : 9900 : case EXPR_R_NE: return "!=";
61 : 19692 : case EXPR_R_LT: return "<";
62 : 19692 : case EXPR_R_LE: return "<=";
63 : 19692 : case EXPR_R_GT: return ">";
64 : 19692 : case EXPR_R_GE: return ">=";
65 : 0 : default: OVS_NOT_REACHED();
66 : : }
67 : : }
68 : :
69 : : bool
70 : 11762436 : expr_relop_from_token(enum lex_type type, enum expr_relop *relop)
71 : : {
72 : : enum expr_relop r;
73 : :
74 [ + + + + : 11762436 : switch ((int) type) {
+ + + ]
75 : 7757218 : case LEX_T_EQ: r = EXPR_R_EQ; break;
76 : 19844 : case LEX_T_NE: r = EXPR_R_NE; break;
77 : 39408 : case LEX_T_LT: r = EXPR_R_LT; break;
78 : 39416 : case LEX_T_LE: r = EXPR_R_LE; break;
79 : 39418 : case LEX_T_GT: r = EXPR_R_GT; break;
80 : 39408 : case LEX_T_GE: r = EXPR_R_GE; break;
81 : 3827724 : default: return false;
82 : : }
83 : :
84 [ + + ]: 7934712 : if (relop) {
85 : 7934659 : *relop = r;
86 : : }
87 : 7934712 : return true;
88 : : }
89 : :
90 : : /* Returns the relational operator that 'relop' becomes if you turn the
91 : : * relation's operands around, e.g. EXPR_R_EQ does not change because "a == b"
92 : : * and "b == a" are equivalent, but EXPR_R_LE becomes EXPR_R_GE because "a <=
93 : : * b" is equivalent to "b >= a". */
94 : : static enum expr_relop
95 : 31 : expr_relop_turn(enum expr_relop relop)
96 : : {
97 [ + + + + : 31 : switch (relop) {
+ + - ]
98 : 2 : case EXPR_R_EQ: return EXPR_R_EQ;
99 : 3 : case EXPR_R_NE: return EXPR_R_NE;
100 : 6 : case EXPR_R_LT: return EXPR_R_GT;
101 : 8 : case EXPR_R_LE: return EXPR_R_GE;
102 : 6 : case EXPR_R_GT: return EXPR_R_LT;
103 : 6 : case EXPR_R_GE: return EXPR_R_LE;
104 : 0 : default: OVS_NOT_REACHED();
105 : : }
106 : : }
107 : :
108 : : /* Returns the relational operator that is the opposite of 'relop'. */
109 : : static enum expr_relop
110 : 73253 : expr_relop_invert(enum expr_relop relop)
111 : : {
112 [ + + + + : 73253 : switch (relop) {
+ + - ]
113 : 21 : case EXPR_R_EQ: return EXPR_R_NE;
114 : 73206 : case EXPR_R_NE: return EXPR_R_EQ;
115 : 6 : case EXPR_R_LT: return EXPR_R_GE;
116 : 7 : case EXPR_R_LE: return EXPR_R_GT;
117 : 6 : case EXPR_R_GT: return EXPR_R_LE;
118 : 7 : case EXPR_R_GE: return EXPR_R_LT;
119 : 0 : default: OVS_NOT_REACHED();
120 : : }
121 : : }
122 : :
123 : : /* Checks whether 'relop' is true for strcmp()-like 3-way comparison result
124 : : * 'cmp'. */
125 : : static bool
126 : 291501108 : expr_relop_test(enum expr_relop relop, int cmp)
127 : : {
128 [ + + + + : 291501108 : switch (relop) {
+ + - ]
129 : 251226612 : case EXPR_R_EQ: return cmp == 0;
130 : 8734016 : case EXPR_R_NE: return cmp != 0;
131 : 7885120 : case EXPR_R_LT: return cmp < 0;
132 : 7885120 : case EXPR_R_LE: return cmp <= 0;
133 : 7885120 : case EXPR_R_GT: return cmp > 0;
134 : 7885120 : case EXPR_R_GE: return cmp >= 0;
135 : 0 : default: OVS_NOT_REACHED();
136 : : }
137 : : }
138 : :
139 : : /* Constructing and manipulating expressions. */
140 : :
141 : : /* Creates and returns a logical AND or OR expression (according to 'type',
142 : : * which must be EXPR_T_AND or EXPR_T_OR) that initially has no
143 : : * sub-expressions. (To satisfy the invariants for expressions, the caller
144 : : * must add at least two sub-expressions whose types are different from
145 : : * 'type'.) */
146 : : struct expr *
147 : 16612355 : expr_create_andor(enum expr_type type)
148 : : {
149 : 16612355 : struct expr *e = xmalloc(sizeof *e);
150 : 16612355 : e->type = type;
151 : 16612355 : ovs_list_init(&e->andor);
152 : 16612355 : return e;
153 : : }
154 : :
155 : : /* Returns a logical AND or OR expression (according to 'type', which must be
156 : : * EXPR_T_AND or EXPR_T_OR) whose sub-expressions are 'a' and 'b', with some
157 : : * flexibility:
158 : : *
159 : : * - If 'a' or 'b' is NULL, just returns the other one (which means that if
160 : : * that other one is not of the given 'type', then the returned
161 : : * expression is not either).
162 : : *
163 : : * - If 'a' or 'b', or both, have type 'type', then they are combined into
164 : : * a single node that satisfies the invariants for expressions. */
165 : : struct expr *
166 : 18303339 : expr_combine(enum expr_type type, struct expr *a, struct expr *b)
167 : : {
168 [ + + ]: 18303339 : if (!a) {
169 : 1934890 : return b;
170 [ - + ]: 16368449 : } else if (!b) {
171 : 0 : return a;
172 [ + + ]: 16368449 : } else if (a->type == type) {
173 [ + + ]: 10122478 : if (b->type == type) {
174 : 138370 : ovs_list_splice(&a->andor, b->andor.next, &b->andor);
175 : 138370 : free(b);
176 : : } else {
177 : 9984108 : ovs_list_push_back(&a->andor, &b->node);
178 : : }
179 : 10122478 : return a;
180 [ + + ]: 6245971 : } else if (b->type == type) {
181 : 620551 : ovs_list_push_front(&b->andor, &a->node);
182 : 620551 : return b;
183 : : } else {
184 : 5625420 : struct expr *e = expr_create_andor(type);
185 : 5625420 : ovs_list_push_back(&e->andor, &a->node);
186 : 5625420 : ovs_list_push_back(&e->andor, &b->node);
187 : 5625420 : return e;
188 : : }
189 : : }
190 : :
191 : : static void
192 : 32151913 : expr_insert_andor(struct expr *andor, struct expr *before, struct expr *new)
193 : : {
194 [ + + ]: 32151913 : if (new->type == andor->type) {
195 : 1892104 : if (andor->type == EXPR_T_AND) {
196 : : /* Conjunction junction, what's your function? */
197 : : }
198 : 1892104 : ovs_list_splice(&before->node, new->andor.next, &new->andor);
199 : 1892104 : free(new);
200 : : } else {
201 : 30259809 : ovs_list_insert(&before->node, &new->node);
202 : : }
203 : 32151913 : }
204 : :
205 : : /* Returns an EXPR_T_BOOLEAN expression with value 'b'. */
206 : : struct expr *
207 : 3812591 : expr_create_boolean(bool b)
208 : : {
209 : 3812591 : struct expr *e = xmalloc(sizeof *e);
210 : 3812591 : e->type = EXPR_T_BOOLEAN;
211 : 3812591 : e->boolean = b;
212 : 3812591 : return e;
213 : : }
214 : :
215 : : static void
216 : 73277 : expr_not(struct expr *expr)
217 : : {
218 : : struct expr *sub;
219 : :
220 [ + + + - ]: 73277 : switch (expr->type) {
221 : : case EXPR_T_CMP:
222 : 73253 : expr->cmp.relop = expr_relop_invert(expr->cmp.relop);
223 : 73253 : break;
224 : :
225 : : case EXPR_T_AND:
226 : : case EXPR_T_OR:
227 [ + + ]: 68 : LIST_FOR_EACH (sub, node, &expr->andor) {
228 : 46 : expr_not(sub);
229 : : }
230 [ + + ]: 22 : expr->type = expr->type == EXPR_T_AND ? EXPR_T_OR : EXPR_T_AND;
231 : 22 : break;
232 : :
233 : : case EXPR_T_BOOLEAN:
234 : 2 : expr->boolean = !expr->boolean;
235 : 2 : break;
236 : : default:
237 : 0 : OVS_NOT_REACHED();
238 : : }
239 : 73277 : }
240 : :
241 : : static struct expr *
242 : 13197059 : expr_fix_andor(struct expr *expr, bool short_circuit)
243 : : {
244 : : struct expr *sub, *next;
245 : :
246 [ + + ][ + + ]: 42793431 : LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
247 [ + + ]: 30560388 : if (sub->type == EXPR_T_BOOLEAN) {
248 [ + + ]: 2584148 : if (sub->boolean == short_circuit) {
249 : 964016 : expr_destroy(expr);
250 : 964016 : return expr_create_boolean(short_circuit);
251 : : } else {
252 : 1620132 : ovs_list_remove(&sub->node);
253 : 1620132 : expr_destroy(sub);
254 : : }
255 : : }
256 : : }
257 : :
258 [ + + ]: 12233043 : if (ovs_list_is_short(&expr->andor)) {
259 [ + + ]: 1117661 : if (ovs_list_is_empty(&expr->andor)) {
260 : 69210 : free(expr);
261 : 69210 : return expr_create_boolean(!short_circuit);
262 : : } else {
263 : 1048451 : sub = expr_from_node(ovs_list_front(&expr->andor));
264 : 1048451 : free(expr);
265 : 1048451 : return sub;
266 : : }
267 : : } else {
268 : 11115382 : return expr;
269 : : }
270 : : }
271 : :
272 : : /* Returns 'expr' modified so that top-level oddities are fixed up:
273 : : *
274 : : * - Eliminates any EXPR_T_BOOLEAN operands at the top level.
275 : : *
276 : : * - Replaces one-operand EXPR_T_AND or EXPR_T_OR by its subexpression. */
277 : : static struct expr *
278 : 13197059 : expr_fix(struct expr *expr)
279 : : {
280 [ - + + - : 13197059 : switch (expr->type) {
- ]
281 : : case EXPR_T_CMP:
282 : 0 : return expr;
283 : :
284 : : case EXPR_T_AND:
285 : 4121478 : return expr_fix_andor(expr, false);
286 : :
287 : : case EXPR_T_OR:
288 : 9075581 : return expr_fix_andor(expr, true);
289 : :
290 : : case EXPR_T_BOOLEAN:
291 : 0 : return expr;
292 : :
293 : : default:
294 : 0 : OVS_NOT_REACHED();
295 : : }
296 : : }
297 : :
298 : : /* Formatting. */
299 : :
300 : : static void
301 : 3387300 : find_bitwise_range(const union mf_subvalue *sv, int width,
302 : : int *startp, int *n_bitsp)
303 : : {
304 : 3387300 : unsigned int start = bitwise_scan(sv, sizeof *sv, true, 0, width);
305 [ + - ]: 3387300 : if (start < width) {
306 : 3387300 : unsigned int end = bitwise_scan(sv, sizeof *sv, false, start, width);
307 [ + + ]: 3387300 : if (end >= width
308 [ + + ]: 3387080 : || bitwise_scan(sv, sizeof *sv, true, end, width) >= width) {
309 : 3387268 : *startp = start;
310 : 3387268 : *n_bitsp = end - start;
311 : 3387268 : return;
312 : : }
313 : : }
314 : 32 : *startp = *n_bitsp = 0;
315 : : }
316 : :
317 : : static void
318 : 186190 : expr_format_cmp(const struct expr *e, struct ds *s)
319 : : {
320 : : /* The common case is numerical comparisons.
321 : : * Handle string comparisons as a special case. */
322 [ + + ]: 186190 : if (!e->cmp.symbol->width) {
323 : 4906 : ds_put_format(s, "%s %s ", e->cmp.symbol->name,
324 : : expr_relop_to_string(e->cmp.relop));
325 : 4906 : json_string_escape(e->cmp.string, s);
326 : 87569 : return;
327 : : }
328 : :
329 : : int ofs, n;
330 : 181284 : find_bitwise_range(&e->cmp.mask, e->cmp.symbol->width, &ofs, &n);
331 [ + + ][ + + ]: 181284 : if (n == 1 && (e->cmp.relop == EXPR_R_EQ || e->cmp.relop == EXPR_R_NE)) {
[ + + ]
332 : : bool positive;
333 : :
334 : 82663 : positive = bitwise_get_bit(&e->cmp.value, sizeof e->cmp.value, ofs);
335 : 82663 : positive ^= e->cmp.relop == EXPR_R_NE;
336 [ + + ]: 82663 : if (!positive) {
337 : 72803 : ds_put_char(s, '!');
338 : : }
339 : 82663 : ds_put_cstr(s, e->cmp.symbol->name);
340 [ + + ]: 82663 : if (e->cmp.symbol->width > 1) {
341 : 82631 : ds_put_format(s, "[%d]", ofs);
342 : : }
343 : 82663 : return;
344 : : }
345 : :
346 : 98621 : ds_put_cstr(s, e->cmp.symbol->name);
347 [ + + ][ + + ]: 98621 : if (n > 0 && n < e->cmp.symbol->width) {
348 [ + + ]: 98414 : if (n > 1) {
349 : 59150 : ds_put_format(s, "[%d..%d]", ofs, ofs + n - 1);
350 : : } else {
351 : 39264 : ds_put_format(s, "[%d]", ofs);
352 : : }
353 : : }
354 : :
355 : 98621 : ds_put_format(s, " %s ", expr_relop_to_string(e->cmp.relop));
356 : :
357 [ + + ]: 98621 : if (n) {
358 : : union mf_subvalue value;
359 : :
360 : 98589 : memset(&value, 0, sizeof value);
361 : 98589 : bitwise_copy(&e->cmp.value, sizeof e->cmp.value, ofs,
362 : : &value, sizeof value, 0,
363 : : n);
364 : 98589 : mf_format_subvalue(&value, s);
365 : : } else {
366 : 32 : mf_format_subvalue(&e->cmp.value, s);
367 : 32 : ds_put_char(s, '/');
368 : 98621 : mf_format_subvalue(&e->cmp.mask, s);
369 : : }
370 : : }
371 : :
372 : : static void
373 : 104673 : expr_format_andor(const struct expr *e, const char *op, struct ds *s)
374 : : {
375 : : struct expr *sub;
376 : 104673 : int i = 0;
377 : :
378 [ + + ]: 334864 : LIST_FOR_EACH (sub, node, &e->andor) {
379 [ + + ]: 230191 : if (i++) {
380 : 125518 : ds_put_format(s, " %s ", op);
381 : : }
382 : :
383 [ + + ][ + + ]: 230191 : if (sub->type == EXPR_T_AND || sub->type == EXPR_T_OR) {
384 : 41639 : ds_put_char(s, '(');
385 : 41639 : expr_format(sub, s);
386 : 41639 : ds_put_char(s, ')');
387 : : } else {
388 : 188552 : expr_format(sub, s);
389 : : }
390 : : }
391 : 104673 : }
392 : :
393 : : /* Appends a string form of 'e' to 's'. The string form is acceptable for
394 : : * parsing back into an equivalent expression. */
395 : : void
396 : 293319 : expr_format(const struct expr *e, struct ds *s)
397 : : {
398 [ + + + + : 293319 : switch (e->type) {
- ]
399 : : case EXPR_T_CMP:
400 : 186190 : expr_format_cmp(e, s);
401 : 186190 : break;
402 : :
403 : : case EXPR_T_AND:
404 : 52336 : expr_format_andor(e, "&&", s);
405 : 52336 : break;
406 : :
407 : : case EXPR_T_OR:
408 : 52337 : expr_format_andor(e, "||", s);
409 : 52337 : break;
410 : :
411 : : case EXPR_T_BOOLEAN:
412 [ + + ]: 2456 : ds_put_char(s, e->boolean ? '1' : '0');
413 : 2456 : break;
414 : : }
415 : 293319 : }
416 : :
417 : : /* Prints a string form of 'e' on stdout, followed by a new-line. */
418 : : void
419 : 0 : expr_print(const struct expr *e)
420 : : {
421 : : struct ds output;
422 : :
423 : 0 : ds_init(&output);
424 : 0 : expr_format(e, &output);
425 : 0 : puts(ds_cstr(&output));
426 : 0 : ds_destroy(&output);
427 : 0 : }
428 : :
429 : : /* Parsing. */
430 : :
431 : : /* Context maintained during expr_parse(). */
432 : : struct expr_context {
433 : : struct lexer *lexer; /* Lexer for pulling more tokens. */
434 : : const struct shash *symtab; /* Symbol table. */
435 : : const struct shash *macros; /* Table of macros. */
436 : : bool not; /* True inside odd number of NOT operators. */
437 : : };
438 : :
439 : : struct expr *expr_parse__(struct expr_context *);
440 : : static void expr_not(struct expr *);
441 : : static bool parse_field(struct expr_context *, struct expr_field *);
442 : :
443 : : static struct expr *
444 : 7733031 : make_cmp__(const struct expr_field *f, enum expr_relop r,
445 : : const union expr_constant *c)
446 : : {
447 : 7733031 : struct expr *e = xzalloc(sizeof *e);
448 : 7733031 : e->type = EXPR_T_CMP;
449 : 7733031 : e->cmp.symbol = f->symbol;
450 : 7733031 : e->cmp.relop = r;
451 [ + + ]: 7733031 : if (f->symbol->width) {
452 : 7479247 : bitwise_copy(&c->value, sizeof c->value, 0,
453 : 14958494 : &e->cmp.value, sizeof e->cmp.value, f->ofs,
454 : 7479247 : f->n_bits);
455 [ + + ]: 7479247 : if (c->masked) {
456 : 36825 : bitwise_copy(&c->mask, sizeof c->mask, 0,
457 : 73650 : &e->cmp.mask, sizeof e->cmp.mask, f->ofs,
458 : 36825 : f->n_bits);
459 : : } else {
460 : 7479247 : bitwise_one(&e->cmp.mask, sizeof e->cmp.mask, f->ofs,
461 : 7442422 : f->n_bits);
462 : : }
463 : : } else {
464 : 253784 : e->cmp.string = xstrdup(c->string);
465 : : }
466 : 7733031 : return e;
467 : : }
468 : :
469 : : /* Returns the minimum reasonable width for integer constant 'c'. */
470 : : static int
471 : 8004382 : expr_constant_width(const union expr_constant *c)
472 : : {
473 [ + + ]: 8004382 : if (c->masked) {
474 : 36826 : return mf_subvalue_width(&c->mask);
475 : : }
476 : :
477 [ + + + + : 7967556 : switch (c->format) {
- ]
478 : : case LEX_F_DECIMAL:
479 : : case LEX_F_HEXADECIMAL:
480 : 7295147 : return mf_subvalue_width(&c->value);
481 : :
482 : : case LEX_F_IPV4:
483 : 213673 : return 32;
484 : :
485 : : case LEX_F_IPV6:
486 : 141686 : return 128;
487 : :
488 : : case LEX_F_ETHERNET:
489 : 317050 : return 48;
490 : :
491 : : default:
492 : 0 : OVS_NOT_REACHED();
493 : : }
494 : : }
495 : :
496 : : static bool
497 : 8286353 : type_check(struct expr_context *ctx, const struct expr_field *f,
498 : : struct expr_constant_set *cs)
499 : : {
500 [ + + ]: 8286353 : if (cs->type != (f->symbol->width ? EXPR_C_INTEGER : EXPR_C_STRING)) {
501 [ + + ][ + + ]: 2 : lexer_error(ctx->lexer,
502 : : "%s field %s is not compatible with %s constant.",
503 : 2 : f->symbol->width ? "Integer" : "String",
504 : 2 : f->symbol->name,
505 : 2 : cs->type == EXPR_C_INTEGER ? "integer" : "string");
506 : 2 : return false;
507 : : }
508 : :
509 [ + + ]: 8286351 : if (f->symbol->width) {
510 [ + + ]: 15940024 : for (size_t i = 0; i < cs->n_values; i++) {
511 : 8004382 : int w = expr_constant_width(&cs->values[i]);
512 [ + + ]: 8004382 : if (w > f->symbol->width) {
513 : 1 : lexer_error(ctx->lexer,
514 : : "%d-bit constant is not compatible with %d-bit "
515 : 2 : "field %s.", w, f->symbol->width, f->symbol->name);
516 : 1 : return false;
517 : : }
518 : : }
519 : : }
520 : :
521 : 8286350 : return true;
522 : : }
523 : :
524 : : static struct expr *
525 : 7664303 : make_cmp(struct expr_context *ctx,
526 : : const struct expr_field *f, enum expr_relop r,
527 : : struct expr_constant_set *cs)
528 : : {
529 : 7664303 : struct expr *e = NULL;
530 : :
531 [ + + ]: 7664303 : if (!type_check(ctx, f, cs)) {
532 : 3 : goto exit;
533 : : }
534 : :
535 [ + + ][ + + ]: 7664300 : if (r != EXPR_R_EQ && r != EXPR_R_NE) {
536 [ + + ]: 78745 : if (cs->in_curlies) {
537 : 1 : lexer_error(ctx->lexer, "Only == and != operators may be used "
538 : : "with value sets.");
539 : 1 : goto exit;
540 : : }
541 [ + + ][ + + ]: 78744 : if (f->symbol->level == EXPR_L_NOMINAL ||
542 : 78742 : f->symbol->level == EXPR_L_BOOLEAN) {
543 : 3 : lexer_error(ctx->lexer, "Only == and != operators may be used "
544 : : "with %s field %s.",
545 : 3 : expr_level_to_string(f->symbol->level),
546 : 3 : f->symbol->name);
547 : 3 : goto exit;
548 : : }
549 [ + + ]: 78741 : if (cs->values[0].masked) {
550 : 1 : lexer_error(ctx->lexer, "Only == and != operators may be used "
551 : : "with masked constants. Consider using subfields "
552 : : "instead (e.g. eth.src[0..15] > 0x1111 in place of "
553 : : "eth.src > 00:00:00:00:11:11/00:00:00:00:ff:ff).");
554 : 1 : goto exit;
555 : : }
556 : : }
557 : :
558 [ + + ]: 7664295 : if (f->symbol->level == EXPR_L_NOMINAL) {
559 [ + + ]: 7025393 : if (f->symbol->predicate) {
560 [ - + ]: 3558571 : ovs_assert(f->symbol->width > 0);
561 [ + + ]: 7117140 : for (size_t i = 0; i < cs->n_values; i++) {
562 : 3558571 : const union mf_subvalue *value = &cs->values[i].value;
563 : 3558571 : bool positive = (value->integer & htonll(1)) != 0;
564 : 3558571 : positive ^= r == EXPR_R_NE;
565 : 3558571 : positive ^= ctx->not;
566 [ + + ]: 3558571 : if (!positive) {
567 : 2 : const char *name = f->symbol->name;
568 : 2 : lexer_error(ctx->lexer,
569 : : "Nominal predicate %s may only be tested "
570 : : "positively, e.g. `%s' or `%s == 1' but not "
571 : : "`!%s' or `%s == 0'.",
572 : : name, name, name, name, name);
573 : 2 : goto exit;
574 : : }
575 : : }
576 [ + + ][ + + ]: 3466822 : } else if (r != (ctx->not ? EXPR_R_NE : EXPR_R_EQ)) {
577 : 4 : lexer_error(ctx->lexer, "Nominal field %s may only be tested for "
578 : : "equality (taking enclosing `!' operators into "
579 : 4 : "account).", f->symbol->name);
580 : 4 : goto exit;
581 : : }
582 : : }
583 : :
584 : 7664289 : e = make_cmp__(f, r, &cs->values[0]);
585 [ + + ]: 7733031 : for (size_t i = 1; i < cs->n_values; i++) {
586 [ + + ]: 68742 : e = expr_combine(r == EXPR_R_EQ ? EXPR_T_OR : EXPR_T_AND,
587 : 68742 : e, make_cmp__(f, r, &cs->values[i]));
588 : : }
589 : : exit:
590 : 7664303 : expr_constant_set_destroy(cs);
591 : 7664303 : return e;
592 : : }
593 : :
594 : : static bool
595 : 8831636 : parse_field(struct expr_context *ctx, struct expr_field *f)
596 : : {
597 : : const struct expr_symbol *symbol;
598 : :
599 [ + + ]: 8831636 : if (ctx->lexer->token.type != LEX_T_ID) {
600 : 11 : lexer_syntax_error(ctx->lexer, "expecting field name");
601 : 11 : return false;
602 : : }
603 : :
604 : 8831625 : symbol = shash_find_data(ctx->symtab, ctx->lexer->token.s);
605 [ + + ]: 8831625 : if (!symbol) {
606 : 4 : lexer_syntax_error(ctx->lexer, "expecting field name");
607 : 4 : return false;
608 : : }
609 : 8831621 : lexer_get(ctx->lexer);
610 : :
611 : 8831621 : f->symbol = symbol;
612 [ + + ]: 8831621 : if (lexer_match(ctx->lexer, LEX_T_LSQUARE)) {
613 : : int low, high;
614 : :
615 [ + + ]: 238299 : if (!symbol->width) {
616 : 2 : lexer_error(ctx->lexer,
617 : : "Cannot select subfield of string field %s.",
618 : : symbol->name);
619 : 10 : return false;
620 : : }
621 : :
622 [ + + ]: 238297 : if (!lexer_force_int(ctx->lexer, &low)) {
623 : 3 : return false;
624 : : }
625 [ + + ]: 238294 : if (lexer_match(ctx->lexer, LEX_T_ELLIPSIS)) {
626 [ - + ]: 62685 : if (!lexer_force_int(ctx->lexer, &high)) {
627 : 0 : return false;
628 : : }
629 : : } else {
630 : 175609 : high = low;
631 : : }
632 : :
633 [ + + ]: 238294 : if (!lexer_force_match(ctx->lexer, LEX_T_RSQUARE)) {
634 : 1 : return false;
635 : : }
636 : :
637 [ + + ]: 238293 : if (low > high) {
638 : 1 : lexer_error(ctx->lexer, "Invalid bit range %d to %d.", low, high);
639 : 1 : return false;
640 [ + + ]: 238292 : } else if (high >= symbol->width) {
641 : 1 : lexer_error(ctx->lexer,
642 : : "Cannot select bits %d to %d of %d-bit field %s.",
643 : : low, high, symbol->width, symbol->name);
644 : 1 : return false;
645 [ + + ]: 238291 : } else if (symbol->level == EXPR_L_NOMINAL
646 [ + + ][ - + ]: 4 : && (low != 0 || high != symbol->width - 1)) {
647 : 2 : lexer_error(ctx->lexer,
648 : : "Cannot select subfield of nominal field %s.",
649 : : symbol->name);
650 : 2 : return false;
651 : : }
652 : :
653 : 238289 : f->ofs = low;
654 : 238289 : f->n_bits = high - low + 1;
655 : : } else {
656 : 8593322 : f->ofs = 0;
657 : 8593322 : f->n_bits = symbol->width;
658 : : }
659 : :
660 : 8831611 : return true;
661 : : }
662 : :
663 : : static bool
664 : 3967235 : parse_relop(struct expr_context *ctx, enum expr_relop *relop)
665 : : {
666 [ + + ]: 3967235 : if (expr_relop_from_token(ctx->lexer->token.type, relop)) {
667 : 3967233 : lexer_get(ctx->lexer);
668 : 3967233 : return true;
669 : : } else {
670 : 2 : lexer_syntax_error(ctx->lexer, "expecting relational operator");
671 : 2 : return false;
672 : : }
673 : : }
674 : :
675 : : static bool
676 : 4789028 : assign_constant_set_type(struct expr_context *ctx,
677 : : struct expr_constant_set *cs,
678 : : enum expr_constant_type type)
679 : : {
680 [ + + ][ + + ]: 4789028 : if (!cs->n_values || cs->type == type) {
681 : 4789027 : cs->type = type;
682 : 4789027 : return true;
683 : : } else {
684 [ + - ]: 1 : lexer_syntax_error(ctx->lexer, "expecting %s",
685 : 1 : cs->type == EXPR_C_INTEGER ? "integer" : "string");
686 : 1 : return false;
687 : : }
688 : : }
689 : :
690 : : static bool
691 : 117 : parse_macros(struct expr_context *ctx, struct expr_constant_set *cs,
692 : : size_t *allocated_values)
693 : : {
694 : 117 : struct expr_constant_set *addr_set
695 : 117 : = (ctx->macros
696 : 117 : ? shash_find_data(ctx->macros, ctx->lexer->token.s)
697 [ + - ]: 117 : : NULL);
698 [ + + ]: 117 : if (!addr_set) {
699 : 2 : lexer_syntax_error(ctx->lexer, "expecting address set name");
700 : 2 : return false;
701 : : }
702 : :
703 [ - + ]: 115 : if (!assign_constant_set_type(ctx, cs, EXPR_C_INTEGER)) {
704 : 0 : return false;
705 : : }
706 : :
707 : 115 : size_t n_values = cs->n_values + addr_set->n_values;
708 [ + - ]: 115 : if (n_values >= *allocated_values) {
709 : 115 : cs->values = xrealloc(cs->values, n_values * sizeof *cs->values);
710 : 115 : *allocated_values = n_values;
711 : : }
712 [ + + ]: 460 : for (size_t i = 0; i < addr_set->n_values; i++) {
713 : 345 : cs->values[cs->n_values++] = addr_set->values[i];
714 : : }
715 : :
716 : 115 : return true;
717 : : }
718 : :
719 : : static bool
720 : 4789035 : parse_constant(struct expr_context *ctx, struct expr_constant_set *cs,
721 : : size_t *allocated_values)
722 : : {
723 [ + + ]: 4789035 : if (cs->n_values >= *allocated_values) {
724 : 4788889 : cs->values = x2nrealloc(cs->values, allocated_values,
725 : : sizeof *cs->values);
726 : : }
727 : :
728 [ + + ]: 4789035 : if (ctx->lexer->token.type == LEX_T_STRING) {
729 [ + + ]: 350721 : if (!assign_constant_set_type(ctx, cs, EXPR_C_STRING)) {
730 : 1 : return false;
731 : : }
732 : 350720 : cs->values[cs->n_values++].string = xstrdup(ctx->lexer->token.s);
733 : 350720 : lexer_get(ctx->lexer);
734 : 350720 : return true;
735 [ + + ][ + + ]: 4438314 : } else if (ctx->lexer->token.type == LEX_T_INTEGER ||
736 : 36954 : ctx->lexer->token.type == LEX_T_MASKED_INTEGER) {
737 [ - + ]: 4438192 : if (!assign_constant_set_type(ctx, cs, EXPR_C_INTEGER)) {
738 : 0 : return false;
739 : : }
740 : :
741 : 4438192 : union expr_constant *c = &cs->values[cs->n_values++];
742 : 4438192 : c->value = ctx->lexer->token.value;
743 : 4438192 : c->format = ctx->lexer->token.format;
744 : 4438192 : c->masked = ctx->lexer->token.type == LEX_T_MASKED_INTEGER;
745 [ + + ]: 4438192 : if (c->masked) {
746 : 36832 : c->mask = ctx->lexer->token.mask;
747 : : }
748 : 4438192 : lexer_get(ctx->lexer);
749 : 4438192 : return true;
750 [ + + ]: 122 : } else if (ctx->lexer->token.type == LEX_T_MACRO) {
751 [ + + ]: 117 : if (!parse_macros(ctx, cs, allocated_values)) {
752 : 2 : return false;
753 : : }
754 : 115 : lexer_get(ctx->lexer);
755 : 115 : return true;
756 : : } else {
757 : 5 : lexer_syntax_error(ctx->lexer, "expecting constant");
758 : 5 : return false;
759 : : }
760 : : }
761 : :
762 : : /* Parses a single or {}-enclosed set of integer or string constants into 'cs',
763 : : * which the caller need not have initialized. Returns true on success, in
764 : : * which case the caller owns 'cs', false on failure, in which case 'cs' is
765 : : * indeterminate. */
766 : : static bool
767 : 4098447 : parse_constant_set(struct expr_context *ctx, struct expr_constant_set *cs)
768 : : {
769 : 4098447 : size_t allocated_values = 0;
770 : : bool ok;
771 : :
772 : 4098447 : memset(cs, 0, sizeof *cs);
773 [ + + ]: 4098447 : if (lexer_match(ctx->lexer, LEX_T_LCURLY)) {
774 : 85760 : ok = true;
775 : 85760 : cs->in_curlies = true;
776 : : do {
777 [ + + ]: 154296 : if (!parse_constant(ctx, cs, &allocated_values)) {
778 : 4 : ok = false;
779 : 4 : break;
780 : : }
781 : 154292 : lexer_match(ctx->lexer, LEX_T_COMMA);
782 [ + + ]: 154296 : } while (!lexer_match(ctx->lexer, LEX_T_RCURLY));
783 : : } else {
784 : 4012687 : ok = parse_constant(ctx, cs, &allocated_values);
785 : : }
786 [ + + ]: 4098447 : if (!ok) {
787 : 6 : expr_constant_set_destroy(cs);
788 : : }
789 : 4098447 : return ok;
790 : : }
791 : :
792 : : /* Parses from 'lexer' a single integer or string constant compatible with the
793 : : * type of 'f' into 'c'.
794 : : *
795 : : * Returns true if successful, false if an error occurred. Upon return,
796 : : * returns true if and only if lexer->error is NULL. On failure, 'c' is
797 : : * indeterminate. */
798 : : bool
799 : 622052 : expr_constant_parse(struct lexer *lexer, const struct expr_field *f,
800 : : union expr_constant *c)
801 : : {
802 [ - + ]: 622052 : if (lexer->error) {
803 : 0 : return false;
804 : : }
805 : :
806 : 622052 : struct expr_context ctx = { .lexer = lexer };
807 : :
808 : : struct expr_constant_set cs;
809 : 622052 : memset(&cs, 0, sizeof cs);
810 : 622052 : size_t allocated_values = 0;
811 [ + + ]: 622052 : if (parse_constant(&ctx, &cs, &allocated_values)
812 [ + - ]: 622050 : && type_check(&ctx, f, &cs)) {
813 : 622050 : *c = cs.values[0];
814 : 622050 : cs.n_values = 0;
815 : : }
816 : 622052 : expr_constant_set_destroy(&cs);
817 : :
818 : 622052 : return !lexer->error;
819 : : }
820 : :
821 : : /* Appends to 's' a re-parseable representation of constant 'c' with the given
822 : : * 'type'. */
823 : : void
824 : 80 : expr_constant_format(const union expr_constant *c,
825 : : enum expr_constant_type type, struct ds *s)
826 : : {
827 [ + + ]: 80 : if (type == EXPR_C_STRING) {
828 : 12 : json_string_escape(c->string, s);
829 : : } else {
830 : : struct lex_token token;
831 [ + + ]: 68 : token.type = c->masked ? LEX_T_MASKED_INTEGER : LEX_T_INTEGER;
832 : 68 : token.s = NULL;
833 : 68 : token.format = c->format;
834 : 68 : token.value = c->value;
835 [ + + ]: 68 : if (c->masked) {
836 : 6 : token.mask = c->mask;
837 : : }
838 : :
839 : 68 : lex_token_format(&token, s);
840 : : }
841 : 80 : }
842 : :
843 : : /* Frees the contents of 'c', which has the specified 'type'.
844 : : *
845 : : * Does not free(c). */
846 : : void
847 : 622050 : expr_constant_destroy(const union expr_constant *c,
848 : : enum expr_constant_type type)
849 : : {
850 [ + - ][ + + ]: 622050 : if (c && type == EXPR_C_STRING) {
851 : 96927 : free(c->string);
852 : : }
853 : 622050 : }
854 : :
855 : : /* Parses from 'lexer' a single or {}-enclosed set of at least one integer or
856 : : * string constants into 'cs', which the caller need not have initialized.
857 : : *
858 : : * Returns true if successful, false if an error occurred. Upon return,
859 : : * returns true if and only if lexer->error is NULL. On failure, 'cs' is
860 : : * indeterminate. */
861 : : bool
862 : 585 : expr_constant_set_parse(struct lexer *lexer, struct expr_constant_set *cs)
863 : : {
864 [ + - ]: 585 : if (!lexer->error) {
865 : 585 : struct expr_context ctx = { .lexer = lexer };
866 : 585 : parse_constant_set(&ctx, cs);
867 : : }
868 : 585 : return !lexer->error;
869 : : }
870 : :
871 : : /* Appends to 's' a re-parseable representation of 'cs'. */
872 : : void
873 : 42 : expr_constant_set_format(const struct expr_constant_set *cs, struct ds *s)
874 : : {
875 [ + + ][ - + ]: 42 : bool curlies = cs->in_curlies || cs->n_values != 1;
876 [ + + ]: 42 : if (curlies) {
877 : 6 : ds_put_char(s, '{');
878 : : }
879 : :
880 [ + + ]: 98 : for (const union expr_constant *c = cs->values;
881 : 56 : c < &cs->values[cs->n_values]; c++) {
882 [ + + ]: 56 : if (c != cs->values) {
883 : 14 : ds_put_cstr(s, ", ");
884 : : }
885 : :
886 : 56 : expr_constant_format(c, cs->type, s);
887 : : }
888 : :
889 [ + + ]: 42 : if (curlies) {
890 : 6 : ds_put_char(s, '}');
891 : : }
892 : 42 : }
893 : :
894 : : void
895 : 8417754 : expr_constant_set_destroy(struct expr_constant_set *cs)
896 : : {
897 [ + - ]: 8417754 : if (cs) {
898 [ + + ]: 8417754 : if (cs->type == EXPR_C_STRING) {
899 [ + + ]: 604508 : for (size_t i = 0; i < cs->n_values; i++) {
900 : 253793 : free(cs->values[i].string);
901 : : }
902 : : }
903 : 8417754 : free(cs->values);
904 : : }
905 : 8417754 : }
906 : :
907 : : /* Adds a macro named 'name' to 'macros', replacing any existing macro with the
908 : : * given name. */
909 : : void
910 : 171 : expr_macros_add(struct shash *macros, const char *name,
911 : : const char *const *values, size_t n_values)
912 : : {
913 : : /* Replace any existing entry for this name. */
914 : 171 : expr_macros_remove(macros, name);
915 : :
916 : 171 : struct expr_constant_set *cs = xzalloc(sizeof *cs);
917 : 171 : cs->type = EXPR_C_INTEGER;
918 : 171 : cs->in_curlies = true;
919 : 171 : cs->n_values = 0;
920 : 171 : cs->values = xmalloc(n_values * sizeof *cs->values);
921 [ + + ]: 680 : for (size_t i = 0; i < n_values; i++) {
922 : : /* Use the lexer to convert each macro into the proper
923 : : * integer format. */
924 : : struct lexer lex;
925 : 509 : lexer_init(&lex, values[i]);
926 : 509 : lexer_get(&lex);
927 [ - + ]: 509 : if (lex.token.type != LEX_T_INTEGER
928 [ # # ]: 0 : && lex.token.type != LEX_T_MASKED_INTEGER) {
929 [ # # ]: 0 : VLOG_WARN("Invalid address set entry: '%s', token type: %d",
930 : : values[i], lex.token.type);
931 : : } else {
932 : 509 : union expr_constant *c = &cs->values[cs->n_values++];
933 : 509 : c->value = lex.token.value;
934 : 509 : c->format = lex.token.format;
935 : 509 : c->masked = lex.token.type == LEX_T_MASKED_INTEGER;
936 [ - + ]: 509 : if (c->masked) {
937 : 0 : c->mask = lex.token.mask;
938 : : }
939 : : }
940 : 509 : lexer_destroy(&lex);
941 : : }
942 : :
943 : 171 : shash_add(macros, name, cs);
944 : 171 : }
945 : :
946 : : void
947 : 171 : expr_macros_remove(struct shash *macros, const char *name)
948 : : {
949 : 171 : struct expr_constant_set *cs = shash_find_and_delete(macros, name);
950 [ - + ]: 171 : if (cs) {
951 : 0 : expr_constant_set_destroy(cs);
952 : 0 : free(cs);
953 : : }
954 : 171 : }
955 : :
956 : : /* Destroy all contents of 'macros'. */
957 : : void
958 : 3187 : expr_macros_destroy(struct shash *macros)
959 : : {
960 : : struct shash_node *node, *next;
961 : :
962 [ + + ][ - + ]: 3358 : SHASH_FOR_EACH_SAFE (node, next, macros) {
[ + + ]
963 : 171 : struct expr_constant_set *cs = node->data;
964 : :
965 : 171 : shash_delete(macros, node);
966 : 171 : expr_constant_set_destroy(cs);
967 : 171 : free(cs);
968 : : }
969 : 3187 : }
970 : :
971 : : static struct expr *
972 : 7863926 : expr_parse_primary(struct expr_context *ctx, bool *atomic)
973 : : {
974 : 7863926 : *atomic = false;
975 [ + + ]: 7863926 : if (lexer_match(ctx->lexer, LEX_T_LPAREN)) {
976 : 68990 : struct expr *e = expr_parse__(ctx);
977 [ + + ]: 68990 : if (!lexer_force_match(ctx->lexer, LEX_T_RPAREN)) {
978 : 1 : expr_destroy(e);
979 : 1 : return NULL;
980 : : }
981 : 68989 : *atomic = true;
982 : 68989 : return e;
983 : : }
984 : :
985 [ + + ]: 7794936 : if (ctx->lexer->token.type == LEX_T_ID) {
986 : : struct expr_field f;
987 : : enum expr_relop r;
988 : : struct expr_constant_set c;
989 : :
990 [ + + ]: 7664273 : if (!parse_field(ctx, &f)) {
991 : 11 : return NULL;
992 : : }
993 : :
994 [ + + ]: 7664262 : if (!expr_relop_from_token(ctx->lexer->token.type, &r)) {
995 [ + + ][ + + ]: 3697082 : if (!f.n_bits || ctx->lexer->token.type == LEX_T_EQUALS) {
996 : 2 : lexer_syntax_error(ctx->lexer,
997 : : "expecting relational operator");
998 : 2 : return NULL;
999 [ + + ][ + + ]: 3697080 : } else if (f.n_bits > 1 && !ctx->not) {
1000 : 2 : lexer_error(ctx->lexer,
1001 : : "Explicit `!= 0' is required for inequality "
1002 : : "test of multibit field against 0.");
1003 : 2 : return NULL;
1004 : : }
1005 : :
1006 : 3697078 : *atomic = true;
1007 : :
1008 : 3697078 : union expr_constant *cst = xzalloc(sizeof *cst);
1009 : 3697078 : cst->format = LEX_F_HEXADECIMAL;
1010 : 3697078 : cst->masked = false;
1011 : :
1012 : 3697078 : c.type = EXPR_C_INTEGER;
1013 : 3697078 : c.values = cst;
1014 : 3697078 : c.n_values = 1;
1015 : 3697078 : c.in_curlies = false;
1016 : 3697078 : return make_cmp(ctx, &f, EXPR_R_NE, &c);
1017 [ + - ][ + + ]: 3967180 : } else if (parse_relop(ctx, &r) && parse_constant_set(ctx, &c)) {
1018 : 3967176 : return make_cmp(ctx, &f, r, &c);
1019 : : } else {
1020 : 7664273 : return NULL;
1021 : : }
1022 : : } else {
1023 : : struct expr_constant_set c1;
1024 [ + + ]: 130663 : if (!parse_constant_set(ctx, &c1)) {
1025 : 2 : return NULL;
1026 : : }
1027 : :
1028 [ + + ]: 130661 : if (!expr_relop_from_token(ctx->lexer->token.type, NULL)
1029 [ + - ]: 130627 : && c1.n_values == 1
1030 [ + - ]: 130627 : && c1.type == EXPR_C_INTEGER
1031 [ + - ]: 130627 : && c1.values[0].format == LEX_F_DECIMAL
1032 [ + - ]: 130627 : && !c1.values[0].masked
1033 [ + - ]: 130627 : && !c1.in_curlies) {
1034 : 130627 : uint64_t x = ntohll(c1.values[0].value.integer);
1035 [ + + ]: 130627 : if (x <= 1) {
1036 : 130625 : *atomic = true;
1037 : 130625 : expr_constant_set_destroy(&c1);
1038 : 130625 : return expr_create_boolean(x);
1039 : : }
1040 : : }
1041 : :
1042 : : enum expr_relop r1;
1043 : : struct expr_field f;
1044 [ + + ][ + + ]: 36 : if (!parse_relop(ctx, &r1) || !parse_field(ctx, &f)) {
1045 : 4 : expr_constant_set_destroy(&c1);
1046 : 4 : return NULL;
1047 : : }
1048 : :
1049 [ + + ]: 32 : if (!expr_relop_from_token(ctx->lexer->token.type, NULL)) {
1050 : 13 : return make_cmp(ctx, &f, expr_relop_turn(r1), &c1);
1051 : : }
1052 : :
1053 : : enum expr_relop r2;
1054 : : struct expr_constant_set c2;
1055 [ + - ][ - + ]: 19 : if (!parse_relop(ctx, &r2) || !parse_constant_set(ctx, &c2)) {
1056 : 0 : expr_constant_set_destroy(&c1);
1057 : 0 : return NULL;
1058 : : } else {
1059 : : /* Reject "1 == field == 2", "1 < field > 2", and so on. */
1060 [ + + ][ + + ]: 19 : if (!(((r1 == EXPR_R_LT || r1 == EXPR_R_LE) &&
[ + + ][ + + ]
1061 [ - + ]: 6 : (r2 == EXPR_R_LT || r2 == EXPR_R_LE)) ||
1062 [ + + ][ + + ]: 9 : ((r1 == EXPR_R_GT || r1 == EXPR_R_GE) &&
1063 [ - + ]: 4 : (r2 == EXPR_R_GT || r2 == EXPR_R_GE)))) {
1064 : 1 : lexer_error(ctx->lexer, "Range expressions must have the "
1065 : : "form `x < field < y' or `x > field > y', with "
1066 : : "each `<' optionally replaced by `<=' or `>' by "
1067 : : "`>=').");
1068 : 1 : expr_constant_set_destroy(&c1);
1069 : 1 : expr_constant_set_destroy(&c2);
1070 : 1 : return NULL;
1071 : : }
1072 : :
1073 : 18 : struct expr *e1 = make_cmp(ctx, &f, expr_relop_turn(r1), &c1);
1074 : 18 : struct expr *e2 = make_cmp(ctx, &f, r2, &c2);
1075 [ - + ]: 18 : if (ctx->lexer->error) {
1076 : 0 : expr_destroy(e1);
1077 : 0 : expr_destroy(e2);
1078 : 0 : return NULL;
1079 : : }
1080 : 130663 : return expr_combine(EXPR_T_AND, e1, e2);
1081 : : }
1082 : : }
1083 : : }
1084 : :
1085 : : static struct expr *
1086 : 7863926 : expr_parse_not(struct expr_context *ctx)
1087 : : {
1088 : : bool atomic;
1089 : :
1090 [ + + ]: 7863926 : if (lexer_match(ctx->lexer, LEX_T_LOG_NOT)) {
1091 : 73233 : ctx->not = !ctx->not;
1092 : 73233 : struct expr *expr = expr_parse_primary(ctx, &atomic);
1093 : 73233 : ctx->not = !ctx->not;
1094 : :
1095 [ + + ]: 73233 : if (expr) {
1096 [ + + ]: 73228 : if (!atomic) {
1097 : 1 : lexer_error(ctx->lexer,
1098 : : "Missing parentheses around operand of !.");
1099 : 1 : expr_destroy(expr);
1100 : 1 : return NULL;
1101 : : }
1102 : 73227 : expr_not(expr);
1103 : : }
1104 : 73232 : return expr;
1105 : : } else {
1106 : 7863926 : return expr_parse_primary(ctx, &atomic);
1107 : : }
1108 : : }
1109 : :
1110 : : struct expr *
1111 : 6149475 : expr_parse__(struct expr_context *ctx)
1112 : : {
1113 : 6149475 : struct expr *e = expr_parse_not(ctx);
1114 [ + + ]: 6149475 : if (!e) {
1115 : 46 : return NULL;
1116 : : }
1117 : :
1118 : 6149429 : enum lex_type lex_type = ctx->lexer->token.type;
1119 [ + + ][ + + ]: 6149429 : if (lex_type == LEX_T_LOG_AND || lex_type == LEX_T_LOG_OR) {
1120 [ + + ]: 1489522 : enum expr_type expr_type
1121 : : = lex_type == LEX_T_LOG_AND ? EXPR_T_AND : EXPR_T_OR;
1122 : :
1123 : 1489522 : lexer_get(ctx->lexer);
1124 : : do {
1125 : 1714451 : struct expr *e2 = expr_parse_not(ctx);
1126 [ - + ]: 1714451 : if (!e2) {
1127 : 0 : expr_destroy(e);
1128 : 0 : return NULL;
1129 : : }
1130 : 1714451 : e = expr_combine(expr_type, e, e2);
1131 [ + + ]: 1714451 : } while (lexer_match(ctx->lexer, lex_type));
1132 [ + + ]: 1489522 : if (ctx->lexer->token.type == LEX_T_LOG_AND
1133 [ - + ]: 1489521 : || ctx->lexer->token.type == LEX_T_LOG_OR) {
1134 : 1 : expr_destroy(e);
1135 : 1 : lexer_error(ctx->lexer,
1136 : : "&& and || must be parenthesized when used together.");
1137 : 1 : return NULL;
1138 : : }
1139 : : }
1140 : 6149428 : return e;
1141 : : }
1142 : :
1143 : : /* Parses an expression from 'lexer' using the symbols in 'symtab' and macros
1144 : : * in 'macros'. If successful, returns the new expression; on failure, returns
1145 : : * NULL. Returns nonnull if and only if lexer->error is NULL. */
1146 : : struct expr *
1147 : 6080485 : expr_parse(struct lexer *lexer, const struct shash *symtab,
1148 : : const struct shash *macros)
1149 : : {
1150 : 6080485 : struct expr_context ctx = { .lexer = lexer,
1151 : : .symtab = symtab,
1152 : : .macros = macros };
1153 [ + - ]: 6080485 : return lexer->error ? NULL : expr_parse__(&ctx);
1154 : : }
1155 : :
1156 : : /* Parses the expression in 's' using the symbols in 'symtab' and macros in
1157 : : * 'macros'. If successful, returns the new expression and sets '*errorp' to
1158 : : * NULL. On failure, returns NULL and sets '*errorp' to an explanatory error
1159 : : * message. The caller must eventually free the returned expression (with
1160 : : * expr_destroy()) or error (with free()). */
1161 : : struct expr *
1162 : 6080485 : expr_parse_string(const char *s, const struct shash *symtab,
1163 : : const struct shash *macros, char **errorp)
1164 : : {
1165 : : struct lexer lexer;
1166 : :
1167 : 6080485 : lexer_init(&lexer, s);
1168 : 6080485 : lexer_get(&lexer);
1169 : 6080485 : struct expr *expr = expr_parse(&lexer, symtab, macros);
1170 : 6080485 : lexer_force_end(&lexer);
1171 : 6080485 : *errorp = lexer_steal_error(&lexer);
1172 [ + + ]: 6080485 : if (*errorp) {
1173 : 44 : expr_destroy(expr);
1174 : 44 : expr = NULL;
1175 : : }
1176 : 6080485 : lexer_destroy(&lexer);
1177 : :
1178 : 6080485 : return expr;
1179 : : }
1180 : :
1181 : : /* Parses a field or subfield from 'lexer' into 'field', obtaining field names
1182 : : * from 'symtab'. Returns true if successful, false if an error occurred.
1183 : : * Upon return, returns true if and only if lexer->error is NULL. */
1184 : : bool
1185 : 1165721 : expr_field_parse(struct lexer *lexer, const struct shash *symtab,
1186 : : struct expr_field *field, struct expr **prereqsp)
1187 : : {
1188 : 1165721 : struct expr_context ctx = { .lexer = lexer, .symtab = symtab };
1189 [ + + ][ + + ]: 1165721 : if (parse_field(&ctx, field) && field->symbol->predicate) {
1190 : 4 : lexer_error(lexer, "Predicate symbol %s used where lvalue required.",
1191 : 4 : field->symbol->name);
1192 : : }
1193 [ + + ]: 1165721 : if (!lexer->error) {
1194 : 1165701 : const struct expr_symbol *symbol = field->symbol;
1195 [ + - ]: 1311777 : while (symbol) {
1196 [ + + ]: 1311777 : if (symbol->prereqs) {
1197 : : char *error;
1198 : 525761 : struct ovs_list nesting = OVS_LIST_INITIALIZER(&nesting);
1199 : 525761 : struct expr *e = parse_and_annotate(symbol->prereqs, symtab,
1200 : : &nesting, &error);
1201 [ + + ]: 525761 : if (error) {
1202 : 2 : lexer_error(lexer, "%s", error);
1203 : 2 : free(error);
1204 : 2 : break;
1205 : : }
1206 : 525759 : *prereqsp = expr_combine(EXPR_T_AND, *prereqsp, e);
1207 : : }
1208 : :
1209 [ + + ]: 1311775 : if (!symbol->parent) {
1210 : 1165699 : break;
1211 : : }
1212 : 146076 : symbol = symbol->parent;
1213 : : }
1214 : : }
1215 [ + + ]: 1165721 : if (!lexer->error) {
1216 : 1165699 : return true;
1217 : : }
1218 : 22 : memset(field, 0, sizeof *field);
1219 : 1165721 : return false;
1220 : : }
1221 : :
1222 : : /* Appends to 's' a re-parseable representation of 'field'. */
1223 : : void
1224 : 158 : expr_field_format(const struct expr_field *field, struct ds *s)
1225 : : {
1226 : 158 : ds_put_cstr(s, field->symbol->name);
1227 [ + + ][ + + ]: 158 : if (field->ofs || field->n_bits != field->symbol->width) {
1228 [ + + ]: 82 : if (field->n_bits != 1) {
1229 : 42 : ds_put_format(s, "[%d..%d]",
1230 : 42 : field->ofs, field->ofs + field->n_bits - 1);
1231 : : } else {
1232 : 40 : ds_put_format(s, "[%d]", field->ofs);
1233 : : }
1234 : : }
1235 : 158 : }
1236 : :
1237 : : void
1238 : 180 : expr_symbol_format(const struct expr_symbol *symbol, struct ds *s)
1239 : : {
1240 : 180 : ds_put_format(s, "%s = ", symbol->name);
1241 [ + + ]: 180 : if (symbol->parent) {
1242 : 144 : struct expr_field f = { symbol->parent,
1243 : 48 : symbol->parent_ofs,
1244 : 48 : symbol->width };
1245 : 48 : expr_field_format(&f, s);
1246 [ + + ]: 132 : } else if (symbol->predicate) {
1247 : 38 : ds_put_cstr(s, symbol->predicate);
1248 : : } else {
1249 : 94 : nx_format_field_name(symbol->field->id, OFP13_VERSION, s);
1250 : : }
1251 : 180 : }
1252 : :
1253 : : static struct expr_symbol *
1254 : 5858 : add_symbol(struct shash *symtab, const char *name, int width,
1255 : : const char *prereqs, enum expr_level level,
1256 : : bool must_crossproduct, bool rw)
1257 : : {
1258 : 5858 : struct expr_symbol *symbol = xzalloc(sizeof *symbol);
1259 : 5858 : symbol->name = xstrdup(name);
1260 [ + + ][ + - ]: 5858 : symbol->prereqs = prereqs && prereqs[0] ? xstrdup(prereqs) : NULL;
1261 : 5858 : symbol->width = width;
1262 : 5858 : symbol->level = level;
1263 : 5858 : symbol->must_crossproduct = must_crossproduct;
1264 : 5858 : symbol->rw = rw;
1265 : 5858 : shash_add_assert(symtab, symbol->name, symbol);
1266 : 5858 : return symbol;
1267 : : }
1268 : :
1269 : : /* Adds field 'id' to symbol table 'symtab' under the given 'name'. Whenever
1270 : : * 'name' is referenced, expression annotation (see expr_annotate()) will
1271 : : * ensure that 'prereqs' are also true. If 'must_crossproduct' is true, then
1272 : : * conversion to flows will never attempt to use the field as a conjunctive
1273 : : * match dimension (see "Crossproducting" in the large comment on struct
1274 : : * expr_symbol in expr.h for an example).
1275 : : *
1276 : : * A given field 'id' must only be used for a single symbol in a symbol table.
1277 : : * Use subfields to duplicate or subset a field (you can even make a subfield
1278 : : * include all the bits of the "parent" field if you like). */
1279 : : struct expr_symbol *
1280 : 2795 : expr_symtab_add_field(struct shash *symtab, const char *name,
1281 : : enum mf_field_id id, const char *prereqs,
1282 : : bool must_crossproduct)
1283 : : {
1284 : 2795 : const struct mf_field *field = mf_from_id(id);
1285 : : struct expr_symbol *symbol;
1286 : :
1287 [ + + ]: 2795 : symbol = add_symbol(symtab, name, field->n_bits, prereqs,
1288 : 2795 : (field->maskable == MFM_FULLY
1289 : : ? EXPR_L_ORDINAL
1290 : : : EXPR_L_NOMINAL),
1291 : 2795 : must_crossproduct, field->writable);
1292 : 2795 : symbol->field = field;
1293 : 2795 : return symbol;
1294 : : }
1295 : :
1296 : : static bool
1297 : 1608 : parse_field_from_string(const char *s, const struct shash *symtab,
1298 : : struct expr_field *field, char **errorp)
1299 : : {
1300 : : struct lexer lexer;
1301 : 1608 : lexer_init(&lexer, s);
1302 : 1608 : lexer_get(&lexer);
1303 : :
1304 : 1608 : struct expr_context ctx = { .lexer = &lexer, .symtab = symtab };
1305 : 1608 : parse_field(&ctx, field);
1306 : 1608 : lexer_force_end(&lexer);
1307 : 1608 : *errorp = lexer_steal_error(&lexer);
1308 : 1608 : lexer_destroy(&lexer);
1309 : :
1310 : 1608 : return !*errorp;
1311 : : }
1312 : :
1313 : : /* Adds 'name' as a subfield of a larger field in 'symtab'. Whenever
1314 : : * 'name' is referenced, expression annotation (see expr_annotate()) will
1315 : : * ensure that 'prereqs' are also true.
1316 : : *
1317 : : * 'subfield' must describe the subfield as a string, e.g. "vlan.tci[0..11]"
1318 : : * for the low 12 bits of a larger field named "vlan.tci". */
1319 : : struct expr_symbol *
1320 : 1608 : expr_symtab_add_subfield(struct shash *symtab, const char *name,
1321 : : const char *prereqs, const char *subfield)
1322 : : {
1323 : : struct expr_symbol *symbol;
1324 : : struct expr_field f;
1325 : : char *error;
1326 : :
1327 [ - + ]: 1608 : if (!parse_field_from_string(subfield, symtab, &f, &error)) {
1328 [ # # ]: 0 : VLOG_WARN("%s: error parsing %s subfield (%s)", subfield, name, error);
1329 : 0 : free(error);
1330 : 0 : return NULL;
1331 : : }
1332 : :
1333 : 1608 : enum expr_level level = f.symbol->level;
1334 [ - + ]: 1608 : if (level != EXPR_L_ORDINAL) {
1335 [ # # ]: 0 : VLOG_WARN("can't define %s as subfield of %s field %s",
1336 : : name, expr_level_to_string(level), f.symbol->name);
1337 : : }
1338 : :
1339 : 1608 : symbol = add_symbol(symtab, name, f.n_bits, prereqs, level, false,
1340 : 1608 : f.symbol->rw);
1341 : 1608 : symbol->parent = f.symbol;
1342 : 1608 : symbol->parent_ofs = f.ofs;
1343 : 1608 : return symbol;
1344 : : }
1345 : :
1346 : : /* Adds a string-valued symbol named 'name' to 'symtab' with the specified
1347 : : * 'prereqs'. */
1348 : : struct expr_symbol *
1349 : 182 : expr_symtab_add_string(struct shash *symtab, const char *name,
1350 : : enum mf_field_id id, const char *prereqs)
1351 : : {
1352 : 182 : const struct mf_field *field = mf_from_id(id);
1353 : : struct expr_symbol *symbol;
1354 : :
1355 : 182 : symbol = add_symbol(symtab, name, 0, prereqs, EXPR_L_NOMINAL, false,
1356 : 182 : field->writable);
1357 : 182 : symbol->field = field;
1358 : 182 : return symbol;
1359 : : }
1360 : :
1361 : : static enum expr_level
1362 : 2680 : expr_get_level(const struct expr *expr)
1363 : : {
1364 : : const struct expr *sub;
1365 : 2680 : enum expr_level level = EXPR_L_ORDINAL;
1366 : :
1367 [ + + - - ]: 2680 : switch (expr->type) {
1368 : : case EXPR_T_CMP:
1369 : 2077 : return (expr->cmp.symbol->level == EXPR_L_NOMINAL
1370 : : ? EXPR_L_NOMINAL
1371 : 2077 : : EXPR_L_BOOLEAN);
1372 : :
1373 : : case EXPR_T_AND:
1374 : : case EXPR_T_OR:
1375 [ + + ]: 2010 : LIST_FOR_EACH (sub, node, &expr->andor) {
1376 : 1407 : enum expr_level sub_level = expr_get_level(sub);
1377 : 1407 : level = MIN(level, sub_level);
1378 : : }
1379 : 603 : return level;
1380 : :
1381 : : case EXPR_T_BOOLEAN:
1382 : 0 : return EXPR_L_BOOLEAN;
1383 : :
1384 : : default:
1385 : 0 : OVS_NOT_REACHED();
1386 : : }
1387 : : }
1388 : :
1389 : : static enum expr_level
1390 : 1273 : expr_parse_level(const char *s, const struct shash *symtab, char **errorp)
1391 : : {
1392 : 1273 : struct expr *expr = expr_parse_string(s, symtab, NULL, errorp);
1393 [ + - ]: 1273 : enum expr_level level = expr ? expr_get_level(expr) : EXPR_L_NOMINAL;
1394 : 1273 : expr_destroy(expr);
1395 : 1273 : return level;
1396 : : }
1397 : :
1398 : : /* Adds a predicate symbol, whose value is the given Boolean 'expression',
1399 : : * named 'name' to 'symtab'. For example, "ip4 && ip4.proto == 6" might be an
1400 : : * appropriate predicate named "tcp4". */
1401 : : struct expr_symbol *
1402 : 1273 : expr_symtab_add_predicate(struct shash *symtab, const char *name,
1403 : : const char *expansion)
1404 : : {
1405 : : struct expr_symbol *symbol;
1406 : : enum expr_level level;
1407 : : char *error;
1408 : :
1409 : 1273 : level = expr_parse_level(expansion, symtab, &error);
1410 [ - + ]: 1273 : if (error) {
1411 [ # # ]: 0 : VLOG_WARN("%s: error parsing %s expansion (%s)",
1412 : : expansion, name, error);
1413 : 0 : free(error);
1414 : 0 : return NULL;
1415 : : }
1416 : :
1417 : 1273 : symbol = add_symbol(symtab, name, 1, NULL, level, false, false);
1418 : 1273 : symbol->predicate = xstrdup(expansion);
1419 : 1273 : return symbol;
1420 : : }
1421 : :
1422 : : /* Destroys 'symtab' and all of its symbols. */
1423 : : void
1424 : 83 : expr_symtab_destroy(struct shash *symtab)
1425 : : {
1426 : : struct shash_node *node, *next;
1427 : :
1428 [ + + ][ - + ]: 5941 : SHASH_FOR_EACH_SAFE (node, next, symtab) {
[ + + ]
1429 : 5858 : struct expr_symbol *symbol = node->data;
1430 : :
1431 : 5858 : shash_delete(symtab, node);
1432 : 5858 : free(symbol->name);
1433 : 5858 : free(symbol->prereqs);
1434 : 5858 : free(symbol->predicate);
1435 : 5858 : free(symbol);
1436 : : }
1437 : 83 : }
1438 : :
1439 : : /* Cloning. */
1440 : :
1441 : : static struct expr *
1442 : 18213603 : expr_clone_cmp(struct expr *expr)
1443 : : {
1444 : 18213603 : struct expr *new = xmemdup(expr, sizeof *expr);
1445 [ + + ]: 18213603 : if (!new->cmp.symbol->width) {
1446 : 3028350 : new->cmp.string = xstrdup(new->cmp.string);
1447 : : }
1448 : 18213603 : return new;
1449 : : }
1450 : :
1451 : : static struct expr *
1452 : 8114060 : expr_clone_andor(struct expr *expr)
1453 : : {
1454 : 8114060 : struct expr *new = expr_create_andor(expr->type);
1455 : : struct expr *sub;
1456 : :
1457 [ + + ]: 26781394 : LIST_FOR_EACH (sub, node, &expr->andor) {
1458 : 18667334 : struct expr *new_sub = expr_clone(sub);
1459 : 18667334 : ovs_list_push_back(&new->andor, &new_sub->node);
1460 : : }
1461 : 8114060 : return new;
1462 : : }
1463 : :
1464 : : /* Returns a clone of 'expr'. This is a "deep copy": neither the returned
1465 : : * expression nor any of its substructure will be shared with 'expr'. */
1466 : : struct expr *
1467 : 27562607 : expr_clone(struct expr *expr)
1468 : : {
1469 [ + + + - ]: 27562607 : switch (expr->type) {
1470 : : case EXPR_T_CMP:
1471 : 18213603 : return expr_clone_cmp(expr);
1472 : :
1473 : : case EXPR_T_AND:
1474 : : case EXPR_T_OR:
1475 : 8114060 : return expr_clone_andor(expr);
1476 : :
1477 : : case EXPR_T_BOOLEAN:
1478 : 1234944 : return expr_create_boolean(expr->boolean);
1479 : : }
1480 : 0 : OVS_NOT_REACHED();
1481 : : }
1482 : :
1483 : : /* Destroys 'expr' and all of the sub-expressions it references. */
1484 : : void
1485 : 46963736 : expr_destroy(struct expr *expr)
1486 : : {
1487 [ + + ]: 46963736 : if (!expr) {
1488 : 271 : return;
1489 : : }
1490 : :
1491 : : struct expr *sub, *next;
1492 : :
1493 [ + + + - ]: 46963465 : switch (expr->type) {
1494 : : case EXPR_T_CMP:
1495 [ + + ]: 31704745 : if (!expr->cmp.symbol->width) {
1496 : 3283068 : free(expr->cmp.string);
1497 : : }
1498 : 31704745 : break;
1499 : :
1500 : : case EXPR_T_AND:
1501 : : case EXPR_T_OR:
1502 [ + + ][ + + ]: 35869904 : LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
1503 : 23897978 : ovs_list_remove(&sub->node);
1504 : 23897978 : expr_destroy(sub);
1505 : : }
1506 : 11971926 : break;
1507 : :
1508 : : case EXPR_T_BOOLEAN:
1509 : 3286794 : break;
1510 : : }
1511 : 46963465 : free(expr);
1512 : : }
1513 : :
1514 : : /* Annotation. */
1515 : :
1516 : : /* An element in a linked list of symbols.
1517 : : *
1518 : : * Used to detect when a symbol is being expanded recursively, to allow
1519 : : * flagging an error. */
1520 : : struct annotation_nesting {
1521 : : struct ovs_list node;
1522 : : const struct expr_symbol *symbol;
1523 : : };
1524 : :
1525 : : struct expr *expr_annotate__(struct expr *, const struct shash *symtab,
1526 : : struct ovs_list *nesting, char **errorp);
1527 : :
1528 : : static struct expr *
1529 : 5307153 : parse_and_annotate(const char *s, const struct shash *symtab,
1530 : : struct ovs_list *nesting, char **errorp)
1531 : : {
1532 : : char *error;
1533 : : struct expr *expr;
1534 : :
1535 : 5307153 : expr = expr_parse_string(s, symtab, NULL, &error);
1536 [ + + ]: 5307153 : if (expr) {
1537 : 5307151 : expr = expr_annotate__(expr, symtab, nesting, &error);
1538 : : }
1539 [ + + ]: 5307153 : if (expr) {
1540 : 5307144 : *errorp = NULL;
1541 : : } else {
1542 : 9 : *errorp = xasprintf("Error parsing expression `%s' encountered as "
1543 : : "prerequisite or predicate of initial expression: "
1544 : : "%s", s, error);
1545 : 9 : free(error);
1546 : : }
1547 : 5307153 : return expr;
1548 : : }
1549 : :
1550 : : static struct expr *
1551 : 8371055 : expr_annotate_cmp(struct expr *expr, const struct shash *symtab,
1552 : : struct ovs_list *nesting, char **errorp)
1553 : : {
1554 : 8371055 : const struct expr_symbol *symbol = expr->cmp.symbol;
1555 : : const struct annotation_nesting *iter;
1556 [ + + ]: 27051359 : LIST_FOR_EACH (iter, node, nesting) {
1557 [ + + ]: 18680308 : if (iter->symbol == symbol) {
1558 : 4 : *errorp = xasprintf("Recursive expansion of symbol `%s'.",
1559 : : symbol->name);
1560 : 4 : expr_destroy(expr);
1561 : 4 : return NULL;
1562 : : }
1563 : : }
1564 : :
1565 : : struct annotation_nesting an;
1566 : 8371051 : an.symbol = symbol;
1567 : 8371051 : ovs_list_push_back(nesting, &an.node);
1568 : :
1569 : 8371051 : struct expr *prereqs = NULL;
1570 [ + + ]: 8371051 : if (symbol->prereqs) {
1571 : 1210142 : prereqs = parse_and_annotate(symbol->prereqs, symtab, nesting, errorp);
1572 [ + + ]: 1210142 : if (!prereqs) {
1573 : 7 : goto error;
1574 : : }
1575 : : }
1576 : :
1577 [ + + ]: 8371044 : if (symbol->parent) {
1578 : 114724 : expr->cmp.symbol = symbol->parent;
1579 : 114724 : mf_subvalue_shift(&expr->cmp.value, symbol->parent_ofs);
1580 : 114724 : mf_subvalue_shift(&expr->cmp.mask, symbol->parent_ofs);
1581 [ + + ]: 8256320 : } else if (symbol->predicate) {
1582 : : struct expr *predicate;
1583 : :
1584 : 3571250 : predicate = parse_and_annotate(symbol->predicate, symtab,
1585 : : nesting, errorp);
1586 [ - + ]: 3571250 : if (!predicate) {
1587 : 0 : goto error;
1588 : : }
1589 : :
1590 : 3571250 : bool positive = (expr->cmp.value.integer & htonll(1)) != 0;
1591 : 3571250 : positive ^= expr->cmp.relop == EXPR_R_NE;
1592 [ + + ]: 3571250 : if (!positive) {
1593 : 4 : expr_not(predicate);
1594 : : }
1595 : :
1596 : 3571250 : expr_destroy(expr);
1597 : 3571250 : expr = predicate;
1598 : : }
1599 : :
1600 : 8371044 : *errorp = NULL;
1601 : 8371044 : ovs_list_remove(&an.node);
1602 [ + + ]: 8371044 : return prereqs ? expr_combine(EXPR_T_AND, expr, prereqs) : expr;
1603 : :
1604 : : error:
1605 : 7 : expr_destroy(expr);
1606 : 7 : expr_destroy(prereqs);
1607 : 7 : ovs_list_remove(&an.node);
1608 : 8371055 : return NULL;
1609 : : }
1610 : :
1611 : : struct expr *
1612 : 10122927 : expr_annotate__(struct expr *expr, const struct shash *symtab,
1613 : : struct ovs_list *nesting, char **errorp)
1614 : : {
1615 [ + + + - ]: 10122927 : switch (expr->type) {
1616 : : case EXPR_T_CMP:
1617 : 8371055 : return expr_annotate_cmp(expr, symtab, nesting, errorp);
1618 : :
1619 : : case EXPR_T_AND:
1620 : : case EXPR_T_OR: {
1621 : : struct expr *sub, *next;
1622 : :
1623 [ + + ][ + + ]: 5808470 : LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
1624 : 4184766 : ovs_list_remove(&sub->node);
1625 : 4184766 : struct expr *new_sub = expr_annotate__(sub, symtab,
1626 : : nesting, errorp);
1627 [ - + ]: 4184766 : if (!new_sub) {
1628 : 0 : expr_destroy(expr);
1629 : 0 : return NULL;
1630 : : }
1631 : 4184766 : expr_insert_andor(expr, next, new_sub);
1632 : : }
1633 : 1623704 : *errorp = NULL;
1634 : 1623704 : return expr;
1635 : : }
1636 : :
1637 : : case EXPR_T_BOOLEAN:
1638 : 128168 : *errorp = NULL;
1639 : 128168 : return expr;
1640 : :
1641 : : default:
1642 : 0 : OVS_NOT_REACHED();
1643 : : }
1644 : : }
1645 : :
1646 : : /* "Annotates" 'expr', which does the following:
1647 : : *
1648 : : * - Applies prerequisites, by locating each comparison operator whose
1649 : : * field has a prerequisite and adding a logical AND against those
1650 : : * prerequisites.
1651 : : *
1652 : : * - Expands references to subfield symbols, by replacing them by
1653 : : * references to their underlying field symbols (suitably shifted).
1654 : : *
1655 : : * - Expands references to predicate symbols, by replacing them by the
1656 : : * expressions that they expand to.
1657 : : *
1658 : : * In each case, annotation occurs recursively as necessary.
1659 : : *
1660 : : * If successful, returns the annotated expression and sets '*errorp' to NULL.
1661 : : * On failure, returns NULL and sets '*errorp' to an explanatory error message,
1662 : : * which the caller must free. In either case, the caller transfers ownership
1663 : : * of 'expr' and receives ownership of the returned expression, if any. */
1664 : : struct expr *
1665 : 631010 : expr_annotate(struct expr *expr, const struct shash *symtab, char **errorp)
1666 : : {
1667 : 631010 : struct ovs_list nesting = OVS_LIST_INITIALIZER(&nesting);
1668 : 631010 : return expr_annotate__(expr, symtab, &nesting, errorp);
1669 : : }
1670 : :
1671 : : static struct expr *
1672 : 877562 : expr_simplify_ne(struct expr *expr)
1673 : : {
1674 : 877562 : struct expr *new = NULL;
1675 : 877562 : const union mf_subvalue *value = &expr->cmp.value;
1676 : 877562 : const union mf_subvalue *mask = &expr->cmp.mask;
1677 : 877562 : int w = expr->cmp.symbol->width;
1678 : : int i;
1679 : :
1680 [ + + ]: 1993012 : for (i = 0; (i = bitwise_scan(mask, sizeof *mask, true, i, w)) < w; i++) {
1681 : : struct expr *e;
1682 : :
1683 : 1115450 : e = xzalloc(sizeof *e);
1684 : 1115450 : e->type = EXPR_T_CMP;
1685 : 1115450 : e->cmp.symbol = expr->cmp.symbol;
1686 : 1115450 : e->cmp.relop = EXPR_R_EQ;
1687 : 1115450 : bitwise_put_bit(&e->cmp.value, sizeof e->cmp.value, i,
1688 : 1115450 : !bitwise_get_bit(value, sizeof *value, i));
1689 : 1115450 : bitwise_put1(&e->cmp.mask, sizeof e->cmp.mask, i);
1690 : :
1691 : 1115450 : new = expr_combine(EXPR_T_OR, new, e);
1692 : : }
1693 [ - + ]: 877562 : ovs_assert(new);
1694 : :
1695 : 877562 : expr_destroy(expr);
1696 : :
1697 : 877562 : return new;
1698 : : }
1699 : :
1700 : : static struct expr *
1701 : 3206016 : expr_simplify_relational(struct expr *expr)
1702 : : {
1703 : 3206016 : const union mf_subvalue *value = &expr->cmp.value;
1704 : : int start, n_bits, end;
1705 : :
1706 : 3206016 : find_bitwise_range(&expr->cmp.mask, expr->cmp.symbol->width,
1707 : : &start, &n_bits);
1708 [ - + ]: 3206016 : ovs_assert(n_bits > 0);
1709 : 3206016 : end = start + n_bits;
1710 : :
1711 : : struct expr *new;
1712 [ + + ][ + + ]: 3206016 : if (expr->cmp.relop == EXPR_R_LE || expr->cmp.relop == EXPR_R_GE) {
1713 : 1603008 : new = xmemdup(expr, sizeof *expr);
1714 : 1603008 : new->cmp.relop = EXPR_R_EQ;
1715 : : } else {
1716 : 1603008 : new = NULL;
1717 : : }
1718 : :
1719 [ + + ][ + + ]: 3206016 : bool b = expr->cmp.relop == EXPR_R_LT || expr->cmp.relop == EXPR_R_LE;
1720 [ + + ]: 5216832 : for (int z = bitwise_scan(value, sizeof *value, b, start, end);
1721 : : z < end;
1722 : 2010816 : z = bitwise_scan(value, sizeof *value, b, z + 1, end)) {
1723 : : struct expr *e;
1724 : :
1725 : 2010816 : e = xmemdup(expr, sizeof *expr);
1726 : 2010816 : e->cmp.relop = EXPR_R_EQ;
1727 : 2010816 : bitwise_toggle_bit(&e->cmp.value, sizeof e->cmp.value, z);
1728 : 2010816 : bitwise_zero(&e->cmp.value, sizeof e->cmp.value, start, z - start);
1729 : 2010816 : bitwise_zero(&e->cmp.mask, sizeof e->cmp.mask, start, z - start);
1730 : 2010816 : new = expr_combine(EXPR_T_OR, new, e);
1731 : : }
1732 : 3206016 : expr_destroy(expr);
1733 [ + + ]: 3206016 : return new ? new : expr_create_boolean(false);
1734 : : }
1735 : :
1736 : : /* Takes ownership of 'expr' and returns an equivalent expression whose
1737 : : * EXPR_T_CMP nodes use only tests for equality (EXPR_R_EQ). */
1738 : : struct expr *
1739 : 24531936 : expr_simplify(struct expr *expr)
1740 : : {
1741 : : struct expr *sub, *next;
1742 : :
1743 [ + + + - ]: 24531936 : switch (expr->type) {
1744 : : case EXPR_T_CMP:
1745 [ + - ]: 18799585 : return (expr->cmp.relop == EXPR_R_EQ || !expr->cmp.symbol->width ? expr
1746 [ + + ]: 18799585 : : expr->cmp.relop == EXPR_R_NE ? expr_simplify_ne(expr)
1747 [ + + ]: 4083578 : : expr_simplify_relational(expr));
1748 : :
1749 : : case EXPR_T_AND:
1750 : : case EXPR_T_OR:
1751 [ + + ][ + + ]: 29303253 : LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
1752 : 20850436 : ovs_list_remove(&sub->node);
1753 : 20850436 : expr_insert_andor(expr, next, expr_simplify(sub));
1754 : : }
1755 : 8452817 : return expr_fix(expr);
1756 : :
1757 : : case EXPR_T_BOOLEAN:
1758 : 1363112 : return expr;
1759 : : }
1760 : 0 : OVS_NOT_REACHED();
1761 : : }
1762 : :
1763 : : static const struct expr_symbol *
1764 : 38154222 : expr_is_cmp(const struct expr *expr)
1765 : : {
1766 [ + + - - ]: 38154222 : switch (expr->type) {
1767 : : case EXPR_T_CMP:
1768 : 29542371 : return expr->cmp.symbol;
1769 : :
1770 : : case EXPR_T_AND:
1771 : : case EXPR_T_OR: {
1772 : 8611851 : const struct expr_symbol *prev = NULL;
1773 : : struct expr *sub;
1774 : :
1775 [ + + ]: 19285788 : LIST_FOR_EACH (sub, node, &expr->andor) {
1776 : 16588227 : const struct expr_symbol *symbol = expr_is_cmp(sub);
1777 [ + + ][ + + ]: 16588227 : if (!symbol || (prev && symbol != prev)) {
[ + + ]
1778 : 5914290 : return NULL;
1779 : : }
1780 : 10673937 : prev = symbol;
1781 : : }
1782 : 2697561 : return prev;
1783 : : }
1784 : :
1785 : : case EXPR_T_BOOLEAN:
1786 : 0 : return NULL;
1787 : :
1788 : : default:
1789 : 0 : OVS_NOT_REACHED();
1790 : : }
1791 : : }
1792 : :
1793 : : struct expr_sort {
1794 : : struct expr *expr;
1795 : : const struct expr_symbol *relop;
1796 : : enum expr_type type;
1797 : : };
1798 : :
1799 : : static int
1800 : 14938575 : compare_expr_sort(const void *a_, const void *b_)
1801 : : {
1802 : 14938575 : const struct expr_sort *a = a_;
1803 : 14938575 : const struct expr_sort *b = b_;
1804 : :
1805 [ + + ]: 14938575 : if (a->type != b->type) {
1806 [ + + ]: 1055160 : return a->type < b->type ? -1 : 1;
1807 [ + + ]: 13883415 : } else if (a->relop) {
1808 : 13833511 : int cmp = strcmp(a->relop->name, b->relop->name);
1809 [ + + ]: 13833511 : if (cmp) {
1810 : 9245492 : return cmp;
1811 : : }
1812 : :
1813 : 4588019 : enum expr_type a_type = a->expr->type;
1814 : 4588019 : enum expr_type b_type = a->expr->type;
1815 [ + - ]: 4588019 : return a_type < b_type ? -1 : a_type > b_type;
1816 [ + - ][ + - ]: 49904 : } else if (a->type == EXPR_T_AND || a->type == EXPR_T_OR) {
1817 : 49904 : size_t a_len = ovs_list_size(&a->expr->andor);
1818 : 49904 : size_t b_len = ovs_list_size(&b->expr->andor);
1819 [ + + ]: 49904 : return a_len < b_len ? -1 : a_len > b_len;
1820 : : } else {
1821 : 0 : return 0;
1822 : : }
1823 : : }
1824 : :
1825 : : static struct expr *crush_cmps(struct expr *, const struct expr_symbol *);
1826 : :
1827 : : static bool
1828 : 10954 : disjunction_matches_string(const struct expr *or, const char *s)
1829 : : {
1830 : : const struct expr *sub;
1831 : :
1832 [ + - ]: 14951 : LIST_FOR_EACH (sub, node, &or->andor) {
1833 [ + + ]: 14951 : if (!strcmp(sub->cmp.string, s)) {
1834 : 10954 : return true;
1835 : : }
1836 : : }
1837 : :
1838 : 0 : return false;
1839 : : }
1840 : :
1841 : : /* Implementation of crush_cmps() for expr->type == EXPR_T_AND and a
1842 : : * string-typed 'symbol'. */
1843 : : static struct expr *
1844 : 272563 : crush_and_string(struct expr *expr, const struct expr_symbol *symbol)
1845 : : {
1846 [ - + ]: 272563 : ovs_assert(!ovs_list_is_short(&expr->andor));
1847 : :
1848 : 272563 : struct expr *singleton = NULL;
1849 : :
1850 : : /* First crush each subexpression into either a single EXPR_T_CMP or an
1851 : : * EXPR_T_OR with EXPR_T_CMP subexpressions. */
1852 : 272563 : struct expr *sub, *next = NULL;
1853 [ + + ][ + + ]: 691167 : LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
1854 : 553524 : ovs_list_remove(&sub->node);
1855 : 553524 : struct expr *new = crush_cmps(sub, symbol);
1856 [ + - + + : 553524 : switch (new->type) {
- ]
1857 : : case EXPR_T_CMP:
1858 [ + + ]: 542026 : if (!singleton) {
1859 : 272449 : ovs_list_insert(&next->node, &new->node);
1860 : 272449 : singleton = new;
1861 : : } else {
1862 : 269577 : bool match = !strcmp(new->cmp.string, singleton->cmp.string);
1863 : 269577 : expr_destroy(new);
1864 [ + + ]: 269577 : if (!match) {
1865 : 134912 : expr_destroy(expr);
1866 : 134912 : return expr_create_boolean(false);
1867 : : }
1868 : : }
1869 : 407114 : break;
1870 : : case EXPR_T_AND:
1871 : 0 : OVS_NOT_REACHED();
1872 : : case EXPR_T_OR:
1873 : 11490 : ovs_list_insert(&next->node, &new->node);
1874 : 11490 : break;
1875 : : case EXPR_T_BOOLEAN:
1876 [ + - ]: 8 : if (!new->boolean) {
1877 : 8 : expr_destroy(expr);
1878 : 8 : return new;
1879 : : }
1880 : 0 : free(new);
1881 : 0 : break;
1882 : : }
1883 : : }
1884 : :
1885 : : /* If we have a singleton, then the result is either the singleton itself
1886 : : * (if the ORs allow the singleton) or false. */
1887 [ + + ]: 137643 : if (singleton) {
1888 [ + + ]: 286020 : LIST_FOR_EACH (sub, node, &expr->andor) {
1889 [ + + ]: 148487 : if (sub->type == EXPR_T_OR
1890 [ - + ]: 10954 : && !disjunction_matches_string(sub, singleton->cmp.string)) {
1891 : 0 : expr_destroy(expr);
1892 : 0 : return expr_create_boolean(false);
1893 : : }
1894 : : }
1895 : 137533 : ovs_list_remove(&singleton->node);
1896 : 137533 : expr_destroy(expr);
1897 : 137533 : return singleton;
1898 : : }
1899 : :
1900 : : /* Otherwise the result is the intersection of all of the ORs. */
1901 : 110 : struct sset result = SSET_INITIALIZER(&result);
1902 [ + + ][ + + ]: 330 : LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
1903 : 220 : struct sset strings = SSET_INITIALIZER(&strings);
1904 : : const struct expr *s;
1905 [ + + ]: 660 : LIST_FOR_EACH (s, node, &sub->andor) {
1906 : 440 : sset_add(&strings, s->cmp.string);
1907 : : }
1908 [ + + ]: 220 : if (sset_is_empty(&result)) {
1909 : 110 : sset_swap(&result, &strings);
1910 : : } else {
1911 : 110 : sset_intersect(&result, &strings);
1912 : : }
1913 : 220 : sset_destroy(&strings);
1914 : :
1915 [ - + ]: 220 : if (sset_is_empty(&result)) {
1916 : 0 : expr_destroy(expr);
1917 : 0 : sset_destroy(&result);
1918 : 0 : return expr_create_boolean(false);
1919 : : }
1920 : : }
1921 : :
1922 : 110 : expr_destroy(expr);
1923 : 110 : expr = expr_create_andor(EXPR_T_OR);
1924 : :
1925 : : const char *string;
1926 [ + - ][ + + ]: 330 : SSET_FOR_EACH (string, &result) {
[ + + ]
1927 : 220 : sub = xmalloc(sizeof *sub);
1928 : 220 : sub->type = EXPR_T_CMP;
1929 : 220 : sub->cmp.relop = EXPR_R_EQ;
1930 : 220 : sub->cmp.symbol = symbol;
1931 : 220 : sub->cmp.string = xstrdup(string);
1932 : 220 : ovs_list_push_back(&expr->andor, &sub->node);
1933 : : }
1934 : 110 : sset_destroy(&result);
1935 : 272563 : return expr_fix(expr);
1936 : : }
1937 : :
1938 : : /* Implementation of crush_cmps() for expr->type == EXPR_T_AND and a
1939 : : * numeric-typed 'symbol'. */
1940 : : static struct expr *
1941 : 1900435 : crush_and_numeric(struct expr *expr, const struct expr_symbol *symbol)
1942 : : {
1943 [ - + ]: 1900435 : ovs_assert(!ovs_list_is_short(&expr->andor));
1944 : :
1945 : : union mf_subvalue value, mask;
1946 : 1900435 : memset(&value, 0, sizeof value);
1947 : 1900435 : memset(&mask, 0, sizeof mask);
1948 : :
1949 : 1900435 : struct expr *sub, *next = NULL;
1950 [ + + ][ + + ]: 7436109 : LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
1951 : 6069212 : ovs_list_remove(&sub->node);
1952 : 6069212 : struct expr *new = crush_cmps(sub, symbol);
1953 [ + - + + : 6069212 : switch (new->type) {
- ]
1954 : : case EXPR_T_CMP:
1955 [ + + ]: 4204661 : if (!mf_subvalue_intersect(&value, &mask,
1956 : 4204661 : &new->cmp.value, &new->cmp.mask,
1957 : : &value, &mask)) {
1958 : 533522 : expr_destroy(new);
1959 : 533522 : expr_destroy(expr);
1960 : 533522 : return expr_create_boolean(false);
1961 : : }
1962 : 3671139 : expr_destroy(new);
1963 : 3671139 : break;
1964 : : case EXPR_T_AND:
1965 : 0 : OVS_NOT_REACHED();
1966 : : case EXPR_T_OR:
1967 : 1864535 : ovs_list_insert(&next->node, &new->node);
1968 : 1864535 : break;
1969 : : case EXPR_T_BOOLEAN:
1970 [ + - ]: 16 : if (!new->boolean) {
1971 : 16 : expr_destroy(expr);
1972 : 16 : return new;
1973 : : }
1974 : 0 : expr_destroy(new);
1975 : 0 : break;
1976 : : }
1977 : : }
1978 [ + + ]: 1366897 : if (ovs_list_is_empty(&expr->andor)) {
1979 [ - + ]: 777347 : if (is_all_zeros(&mask, sizeof mask)) {
1980 : 0 : expr_destroy(expr);
1981 : 0 : return expr_create_boolean(true);
1982 : : } else {
1983 : : struct expr *cmp;
1984 : 777347 : cmp = xmalloc(sizeof *cmp);
1985 : 777347 : cmp->type = EXPR_T_CMP;
1986 : 777347 : cmp->cmp.symbol = symbol;
1987 : 777347 : cmp->cmp.relop = EXPR_R_EQ;
1988 : 777347 : cmp->cmp.value = value;
1989 : 777347 : cmp->cmp.mask = mask;
1990 : 777347 : expr_destroy(expr);
1991 : 777347 : return cmp;
1992 : : }
1993 [ + + ]: 589550 : } else if (ovs_list_is_short(&expr->andor)) {
1994 : : /* Transform "a && (b || c || d)" into "ab || ac || ad" where "ab" is
1995 : : * computed as "a && b", etc. */
1996 : 353040 : struct expr *disjuncts = expr_from_node(ovs_list_pop_front(&expr->andor));
1997 : : struct expr *or;
1998 : :
1999 : 353040 : or = xmalloc(sizeof *or);
2000 : 353040 : or->type = EXPR_T_OR;
2001 : 353040 : ovs_list_init(&or->andor);
2002 : :
2003 [ - + ]: 353040 : ovs_assert(disjuncts->type == EXPR_T_OR);
2004 [ + + ][ + + ]: 1060464 : LIST_FOR_EACH_SAFE (sub, next, node, &disjuncts->andor) {
2005 [ - + ]: 707424 : ovs_assert(sub->type == EXPR_T_CMP);
2006 : 707424 : ovs_list_remove(&sub->node);
2007 [ + + ]: 707424 : if (mf_subvalue_intersect(&value, &mask,
2008 : 707424 : &sub->cmp.value, &sub->cmp.mask,
2009 : : &sub->cmp.value, &sub->cmp.mask)) {
2010 : 355964 : ovs_list_push_back(&or->andor, &sub->node);
2011 : : } else {
2012 : 351460 : expr_destroy(sub);
2013 : : }
2014 : : }
2015 : 353040 : free(disjuncts);
2016 : 353040 : free(expr);
2017 [ + + ]: 353040 : if (ovs_list_is_empty(&or->andor)) {
2018 : 3508 : free(or);
2019 : 3508 : return expr_create_boolean(false);
2020 [ + + ]: 349532 : } else if (ovs_list_is_short(&or->andor)) {
2021 : 343300 : struct expr *cmp = expr_from_node(ovs_list_pop_front(&or->andor));
2022 : 343300 : free(or);
2023 : 343300 : return cmp;
2024 : : } else {
2025 : 6232 : return or;
2026 : : }
2027 : : } else {
2028 : : /* Transform "x && (a0 || a1) && (b0 || b1) && ..." into
2029 : : * "(xa0b0 || xa0b1 || xa1b0 || xa1b1) && ...". */
2030 : 236510 : struct expr *as = expr_from_node(ovs_list_pop_front(&expr->andor));
2031 : 236510 : struct expr *bs = expr_from_node(ovs_list_pop_front(&expr->andor));
2032 : 236510 : struct expr *new = NULL;
2033 : : struct expr *or;
2034 : :
2035 : 236510 : or = xmalloc(sizeof *or);
2036 : 236510 : or->type = EXPR_T_OR;
2037 : 236510 : ovs_list_init(&or->andor);
2038 : :
2039 : : struct expr *a;
2040 [ + + ]: 709530 : LIST_FOR_EACH (a, node, &as->andor) {
2041 : : union mf_subvalue a_value, a_mask;
2042 : :
2043 [ - + ]: 473020 : ovs_assert(a->type == EXPR_T_CMP);
2044 [ + + ]: 473020 : if (!mf_subvalue_intersect(&value, &mask,
2045 : 473020 : &a->cmp.value, &a->cmp.mask,
2046 : : &a_value, &a_mask)) {
2047 : 223962 : continue;
2048 : : }
2049 : :
2050 : : struct expr *b;
2051 [ + + ]: 747174 : LIST_FOR_EACH (b, node, &bs->andor) {
2052 [ - + ]: 498116 : ovs_assert(b->type == EXPR_T_CMP);
2053 [ + + ]: 498116 : if (!new) {
2054 : 278146 : new = xmalloc(sizeof *new);
2055 : 278146 : new->type = EXPR_T_CMP;
2056 : 278146 : new->cmp.symbol = symbol;
2057 : 278146 : new->cmp.relop = EXPR_R_EQ;
2058 : : }
2059 [ + + ]: 498116 : if (mf_subvalue_intersect(&a_value, &a_mask,
2060 : 498116 : &b->cmp.value, &b->cmp.mask,
2061 : : &new->cmp.value, &new->cmp.mask)) {
2062 : 249226 : ovs_list_push_back(&or->andor, &new->node);
2063 : 249226 : new = NULL;
2064 : : }
2065 : : }
2066 : : }
2067 : 236510 : expr_destroy(as);
2068 : 236510 : expr_destroy(bs);
2069 : 236510 : free(new);
2070 : :
2071 [ + + ]: 236510 : if (ovs_list_is_empty(&or->andor)) {
2072 : 24 : expr_destroy(expr);
2073 : 24 : free(or);
2074 : 24 : return expr_create_boolean(false);
2075 [ + + ]: 236486 : } else if (ovs_list_is_short(&or->andor)) {
2076 : 224090 : struct expr *cmp = expr_from_node(ovs_list_pop_front(&or->andor));
2077 : 224090 : free(or);
2078 [ + + ]: 224090 : if (ovs_list_is_empty(&expr->andor)) {
2079 : 27397 : expr_destroy(expr);
2080 : 27397 : return crush_cmps(cmp, symbol);
2081 : : } else {
2082 : 196693 : return crush_cmps(expr_combine(EXPR_T_AND, cmp, expr), symbol);
2083 : : }
2084 [ + + ]: 12396 : } else if (!ovs_list_is_empty(&expr->andor)) {
2085 : 112 : struct expr *e = expr_combine(EXPR_T_AND, or, expr);
2086 [ - + ]: 112 : ovs_assert(!ovs_list_is_short(&e->andor));
2087 : 112 : return crush_cmps(e, symbol);
2088 : : } else {
2089 : 12284 : expr_destroy(expr);
2090 : 1900435 : return crush_cmps(or, symbol);
2091 : : }
2092 : : }
2093 : : }
2094 : :
2095 : : static int
2096 : 4886321 : compare_cmps_3way(const struct expr *a, const struct expr *b)
2097 : : {
2098 [ - + ]: 4886321 : ovs_assert(a->cmp.symbol == b->cmp.symbol);
2099 [ + + ]: 4886321 : if (!a->cmp.symbol->width) {
2100 : 116049 : return strcmp(a->cmp.string, b->cmp.string);
2101 : : } else {
2102 : 4770272 : int d = memcmp(&a->cmp.value, &b->cmp.value, sizeof a->cmp.value);
2103 [ + + ]: 4770272 : if (!d) {
2104 : 289783 : d = memcmp(&a->cmp.mask, &b->cmp.mask, sizeof a->cmp.mask);
2105 : : }
2106 : 4770272 : return d;
2107 : : }
2108 : : }
2109 : :
2110 : : static int
2111 : 2457351 : compare_cmps_cb(const void *a_, const void *b_)
2112 : : {
2113 : 2457351 : const struct expr *const *ap = a_;
2114 : 2457351 : const struct expr *const *bp = b_;
2115 : 2457351 : const struct expr *a = *ap;
2116 : 2457351 : const struct expr *b = *bp;
2117 : 2457351 : return compare_cmps_3way(a, b);
2118 : : }
2119 : :
2120 : : /* Implementation of crush_cmps() for expr->type == EXPR_T_OR. */
2121 : : static struct expr *
2122 : 2378986 : crush_or(struct expr *expr, const struct expr_symbol *symbol)
2123 : : {
2124 : 2378986 : struct expr *sub, *next = NULL;
2125 : :
2126 : : /* First, crush all the subexpressions. That might eliminate the
2127 : : * OR-expression entirely; if so, return the result. Otherwise, 'expr'
2128 : : * is now a disjunction of cmps over the same symbol. */
2129 [ + + ][ + + ]: 7201534 : LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
2130 : 4822548 : ovs_list_remove(&sub->node);
2131 : 4822548 : expr_insert_andor(expr, next, crush_cmps(sub, symbol));
2132 : : }
2133 : 2378986 : expr = expr_fix(expr);
2134 [ + + ]: 2378986 : if (expr->type != EXPR_T_OR) {
2135 : 13840 : return expr;
2136 : : }
2137 : :
2138 : : /* Sort subexpressions by value and mask, to bring together duplicates. */
2139 : 2365146 : size_t n = ovs_list_size(&expr->andor);
2140 : 2365146 : struct expr **subs = xmalloc(n * sizeof *subs);
2141 : :
2142 : 2365146 : size_t i = 0;
2143 [ + + ]: 7159262 : LIST_FOR_EACH (sub, node, &expr->andor) {
2144 : 4794116 : subs[i++] = sub;
2145 : : }
2146 [ - + ]: 2365146 : ovs_assert(i == n);
2147 : :
2148 : 2365146 : qsort(subs, n, sizeof *subs, compare_cmps_cb);
2149 : :
2150 : : /* Eliminate duplicates. */
2151 : 2365146 : ovs_list_init(&expr->andor);
2152 : 2365146 : ovs_list_push_back(&expr->andor, &subs[0]->node);
2153 [ + + ]: 4794116 : for (i = 1; i < n; i++) {
2154 : 2428970 : struct expr *a = expr_from_node(ovs_list_back(&expr->andor));
2155 : 2428970 : struct expr *b = subs[i];
2156 [ + + ]: 2428970 : if (compare_cmps_3way(a, b)) {
2157 : 2268414 : ovs_list_push_back(&expr->andor, &b->node);
2158 : : } else {
2159 : 160556 : expr_destroy(b);
2160 : : }
2161 : : }
2162 : 2365146 : free(subs);
2163 : 2365146 : return expr_fix(expr);
2164 : : }
2165 : :
2166 : : /* Takes ownership of 'expr', which must be a cmp in the sense determined by
2167 : : * 'expr_is_cmp(expr)', where 'symbol' is the symbol returned by that function.
2168 : : * Returns an equivalent expression owned by the caller that is a single
2169 : : * EXPR_T_CMP or a disjunction of them or a EXPR_T_BOOLEAN. */
2170 : : static struct expr *
2171 : 19259723 : crush_cmps(struct expr *expr, const struct expr_symbol *symbol)
2172 : : {
2173 [ + + + - : 19259723 : switch (expr->type) {
- ]
2174 : : case EXPR_T_OR:
2175 : 2378986 : return crush_or(expr, symbol);
2176 : :
2177 : : case EXPR_T_AND:
2178 : 2172998 : return (symbol->width
2179 : : ? crush_and_numeric(expr, symbol)
2180 [ + + ]: 2172998 : : crush_and_string(expr, symbol));
2181 : :
2182 : : case EXPR_T_CMP:
2183 : 14707739 : return expr;
2184 : :
2185 : : case EXPR_T_BOOLEAN:
2186 : 0 : return expr;
2187 : :
2188 : : default:
2189 : 0 : OVS_NOT_REACHED();
2190 : : }
2191 : : }
2192 : :
2193 : : static struct expr *
2194 : 4137402 : expr_sort(struct expr *expr)
2195 : : {
2196 : 4137402 : size_t n = ovs_list_size(&expr->andor);
2197 : 4137402 : struct expr_sort *subs = xmalloc(n * sizeof *subs);
2198 : : struct expr *sub;
2199 : : size_t i;
2200 : :
2201 : 4137402 : i = 0;
2202 [ + + ]: 16474573 : LIST_FOR_EACH (sub, node, &expr->andor) {
2203 : 12337171 : subs[i].expr = sub;
2204 : 12337171 : subs[i].relop = expr_is_cmp(sub);
2205 [ + + ]: 12337171 : subs[i].type = subs[i].relop ? EXPR_T_CMP : sub->type;
2206 : 12337171 : i++;
2207 : : }
2208 [ - + ]: 4137402 : ovs_assert(i == n);
2209 : :
2210 : 4137402 : qsort(subs, n, sizeof *subs, compare_expr_sort);
2211 : :
2212 : 4137402 : ovs_list_init(&expr->andor);
2213 [ + + ]: 11943854 : for (int i = 0; i < n; ) {
2214 [ + + ]: 8463330 : if (subs[i].relop) {
2215 : : int j;
2216 [ + + ]: 10999820 : for (j = i + 1; j < n; j++) {
2217 [ + + ]: 7914948 : if (subs[i].relop != subs[j].relop) {
2218 : 4493081 : break;
2219 : : }
2220 : : }
2221 : :
2222 : : struct expr *crushed;
2223 [ + + ]: 7577953 : if (j == i + 1) {
2224 : 5637936 : crushed = crush_cmps(subs[i].expr, subs[i].relop);
2225 : : } else {
2226 : 1940017 : struct expr *combined = subs[i].expr;
2227 [ + + ]: 5361884 : for (int k = i + 1; k < j; k++) {
2228 : 3421867 : combined = expr_combine(EXPR_T_AND, combined,
2229 : 3421867 : subs[k].expr);
2230 : : }
2231 [ - + ]: 1940017 : ovs_assert(!ovs_list_is_short(&combined->andor));
2232 : 1940017 : crushed = crush_cmps(combined, subs[i].relop);
2233 : : }
2234 [ + + ]: 7577953 : if (crushed->type == EXPR_T_BOOLEAN) {
2235 [ + - ]: 656878 : if (!crushed->boolean) {
2236 [ + + ]: 1108852 : for (int k = j; k < n; k++) {
2237 : 451974 : expr_destroy(subs[k].expr);
2238 : : }
2239 : 656878 : expr_destroy(expr);
2240 : 656878 : expr = crushed;
2241 : 656878 : break;
2242 : : } else {
2243 : 0 : free(crushed);
2244 : : }
2245 : : } else {
2246 : 6921075 : expr = expr_combine(EXPR_T_AND, expr, crushed);
2247 : : }
2248 : 6921075 : i = j;
2249 : : } else {
2250 : 885377 : expr = expr_combine(EXPR_T_AND, expr, subs[i++].expr);
2251 : : }
2252 : : }
2253 : 4137402 : free(subs);
2254 : :
2255 : 4137402 : return expr;
2256 : : }
2257 : :
2258 : : static struct expr *expr_normalize_or(struct expr *expr);
2259 : :
2260 : : /* Returns 'expr', which is an AND, reduced to OR(AND(clause)) where
2261 : : * a clause is a cmp or a disjunction of cmps on a single field. */
2262 : : static struct expr *
2263 : 4137402 : expr_normalize_and(struct expr *expr)
2264 : : {
2265 [ - + ]: 4137402 : ovs_assert(expr->type == EXPR_T_AND);
2266 : :
2267 : 4137402 : expr = expr_sort(expr);
2268 [ + + ]: 4137402 : if (expr->type != EXPR_T_AND) {
2269 [ - + ]: 656878 : ovs_assert(expr->type == EXPR_T_BOOLEAN);
2270 : 656878 : return expr;
2271 : : }
2272 : :
2273 : : struct expr *a, *b;
2274 [ + + ][ + + ]: 11093838 : LIST_FOR_EACH_SAFE (a, b, node, &expr->andor) {
2275 [ + + ]: 7613314 : if (&b->node == &expr->andor
2276 [ + + ][ + + ]: 4132790 : || a->type != EXPR_T_CMP || b->type != EXPR_T_CMP
2277 [ + - ]: 2939412 : || a->cmp.symbol != b->cmp.symbol) {
2278 : 7613314 : continue;
2279 [ # # ][ # # ]: 0 : } else if (a->cmp.symbol->width
2280 : 0 : ? mf_subvalue_intersect(&a->cmp.value, &a->cmp.mask,
2281 : 0 : &b->cmp.value, &b->cmp.mask,
2282 : : &b->cmp.value, &b->cmp.mask)
2283 : 0 : : !strcmp(a->cmp.string, b->cmp.string)) {
2284 : 0 : ovs_list_remove(&a->node);
2285 : 0 : expr_destroy(a);
2286 : : } else {
2287 : 0 : expr_destroy(expr);
2288 : 0 : return expr_create_boolean(false);
2289 : : }
2290 : : }
2291 [ + + ]: 3480524 : if (ovs_list_is_short(&expr->andor)) {
2292 : 456197 : struct expr *sub = expr_from_node(ovs_list_front(&expr->andor));
2293 : 456197 : free(expr);
2294 : 456197 : return sub;
2295 : : }
2296 : :
2297 : : struct expr *sub;
2298 [ + + ]: 9221097 : LIST_FOR_EACH (sub, node, &expr->andor) {
2299 [ + + ]: 7069719 : if (sub->type == EXPR_T_CMP) {
2300 : 5854329 : continue;
2301 : : }
2302 : :
2303 [ - + ]: 1215390 : ovs_assert(sub->type == EXPR_T_OR);
2304 : 1215390 : const struct expr_symbol *symbol = expr_is_cmp(sub);
2305 [ + + ][ + + ]: 1215390 : if (!symbol || symbol->must_crossproduct) {
2306 : 872949 : struct expr *or = expr_create_andor(EXPR_T_OR);
2307 : : struct expr *k;
2308 : :
2309 [ + + ]: 2871529 : LIST_FOR_EACH (k, node, &sub->andor) {
2310 : 1998580 : struct expr *and = expr_create_andor(EXPR_T_AND);
2311 : : struct expr *m;
2312 : :
2313 [ + + ]: 7046488 : LIST_FOR_EACH (m, node, &expr->andor) {
2314 [ + + ]: 5047908 : struct expr *term = m == sub ? k : m;
2315 [ + + ]: 5047908 : if (term->type == EXPR_T_AND) {
2316 : : struct expr *p;
2317 : :
2318 [ + + ]: 1575699 : LIST_FOR_EACH (p, node, &term->andor) {
2319 : 1186277 : struct expr *new = expr_clone(p);
2320 : 1186277 : ovs_list_push_back(&and->andor, &new->node);
2321 : : }
2322 : : } else {
2323 : 4658486 : struct expr *new = expr_clone(term);
2324 : 4658486 : ovs_list_push_back(&and->andor, &new->node);
2325 : : }
2326 : : }
2327 : 1998580 : ovs_list_push_back(&or->andor, &and->node);
2328 : : }
2329 : 872949 : expr_destroy(expr);
2330 : 872949 : return expr_normalize_or(or);
2331 : : }
2332 : : }
2333 : 2151378 : return expr;
2334 : : }
2335 : :
2336 : : static struct expr *
2337 : 1842624 : expr_normalize_or(struct expr *expr)
2338 : : {
2339 : : struct expr *sub, *next;
2340 : :
2341 [ + + ][ + + ]: 6236157 : LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
2342 [ + + ]: 4393533 : if (sub->type == EXPR_T_AND) {
2343 : 2817916 : ovs_list_remove(&sub->node);
2344 : :
2345 : 2817916 : struct expr *new = expr_normalize_and(sub);
2346 [ + + ]: 2817916 : if (new->type == EXPR_T_BOOLEAN) {
2347 [ - + ]: 523753 : if (new->boolean) {
2348 : 0 : expr_destroy(expr);
2349 : 0 : return new;
2350 : : }
2351 : 523753 : free(new);
2352 : : } else {
2353 : 2817916 : expr_insert_andor(expr, next, new);
2354 : : }
2355 : : } else {
2356 [ - + ]: 1575617 : ovs_assert(sub->type == EXPR_T_CMP);
2357 : : }
2358 : : }
2359 [ + + ]: 1842624 : if (ovs_list_is_empty(&expr->andor)) {
2360 : 23242 : free(expr);
2361 : 23242 : return expr_create_boolean(false);
2362 : : }
2363 [ + + ]: 1819382 : if (ovs_list_is_short(&expr->andor)) {
2364 : 325403 : struct expr *sub = expr_from_node(ovs_list_pop_front(&expr->andor));
2365 : 325403 : free(expr);
2366 : 325403 : return sub;
2367 : : }
2368 : :
2369 : 1493979 : return expr;
2370 : : }
2371 : :
2372 : : /* Takes ownership of 'expr', which is either a constant "true" or "false" or
2373 : : * an expression in terms of only relationals, AND, and OR. Returns either a
2374 : : * constant "true" or "false" or 'expr' reduced to OR(AND(clause)) where a
2375 : : * clause is a cmp or a disjunction of cmps on a single field. This form is
2376 : : * significant because it is a form that can be directly converted to OpenFlow
2377 : : * flows with the Open vSwitch "conjunctive match" extension.
2378 : : *
2379 : : * 'expr' must already have been simplified, with expr_simplify(). */
2380 : : struct expr *
2381 : 3057974 : expr_normalize(struct expr *expr)
2382 : : {
2383 [ + + + + : 3057974 : switch (expr->type) {
- ]
2384 : : case EXPR_T_CMP:
2385 : 370933 : return expr;
2386 : :
2387 : : case EXPR_T_AND:
2388 : 1319486 : return expr_normalize_and(expr);
2389 : :
2390 : : case EXPR_T_OR:
2391 : 969675 : return expr_normalize_or(expr);
2392 : :
2393 : : case EXPR_T_BOOLEAN:
2394 : 397880 : return expr;
2395 : : }
2396 : 0 : OVS_NOT_REACHED();
2397 : : }
2398 : :
2399 : : /* Creates, initializes, and returns a new 'struct expr_match'. If 'm' is
2400 : : * nonnull then it is copied into the new expr_match, otherwise the new
2401 : : * expr_match's 'match' member is initialized to a catch-all match for the
2402 : : * caller to refine in-place.
2403 : : *
2404 : : * If 'conj_id' is nonzero, adds one conjunction based on 'conj_id', 'clause',
2405 : : * and 'n_clauses' to the returned 'struct expr_match', otherwise the
2406 : : * expr_match will not have any conjunctions.
2407 : : *
2408 : : * The caller should use expr_match_add() to add the expr_match to a hash table
2409 : : * after it is finalized. */
2410 : : static struct expr_match *
2411 : 1131472 : expr_match_new(const struct match *m, uint8_t clause, uint8_t n_clauses,
2412 : : uint32_t conj_id)
2413 : : {
2414 : 1131472 : struct expr_match *match = xmalloc(sizeof *match);
2415 [ + + ]: 1131472 : if (m) {
2416 : 571993 : match->match = *m;
2417 : : } else {
2418 : 559479 : match_init_catchall(&match->match);
2419 : : }
2420 [ + + ]: 1131472 : if (conj_id) {
2421 : 1648 : match->conjunctions = xmalloc(sizeof *match->conjunctions);
2422 : 1648 : match->conjunctions[0].id = conj_id;
2423 : 1648 : match->conjunctions[0].clause = clause;
2424 : 1648 : match->conjunctions[0].n_clauses = n_clauses;
2425 : 1648 : match->n = 1;
2426 : 1648 : match->allocated = 1;
2427 : : } else {
2428 : 1129824 : match->conjunctions = NULL;
2429 : 1129824 : match->n = 0;
2430 : 1129824 : match->allocated = 0;
2431 : : }
2432 : 1131472 : return match;
2433 : : }
2434 : :
2435 : : /* Adds 'match' to hash table 'matches', which becomes the new owner of
2436 : : * 'match'.
2437 : : *
2438 : : * This might actually destroy 'match' because it gets merged together with
2439 : : * some existing conjunction.*/
2440 : : static void
2441 : 1131468 : expr_match_add(struct hmap *matches, struct expr_match *match)
2442 : : {
2443 : 1131468 : uint32_t hash = match_hash(&match->match, 0);
2444 : : struct expr_match *m;
2445 : :
2446 [ + + ][ - + ]: 1131468 : HMAP_FOR_EACH_WITH_HASH (m, hmap_node, hash, matches) {
2447 [ + - ]: 10809 : if (match_equal(&m->match, &match->match)) {
2448 [ - + ][ # # ]: 10809 : if (!m->n || !match->n) {
2449 : 10809 : free(m->conjunctions);
2450 : 10809 : m->conjunctions = NULL;
2451 : 10809 : m->n = 0;
2452 : 10809 : m->allocated = 0;
2453 : : } else {
2454 [ # # ]: 0 : ovs_assert(match->n == 1);
2455 [ # # ]: 0 : if (m->n >= m->allocated) {
2456 : 0 : m->conjunctions = x2nrealloc(m->conjunctions,
2457 : : &m->allocated,
2458 : : sizeof *m->conjunctions);
2459 : : }
2460 : 0 : m->conjunctions[m->n++] = match->conjunctions[0];
2461 : : }
2462 : 10809 : free(match->conjunctions);
2463 : 10809 : free(match);
2464 : 10809 : return;
2465 : : }
2466 : : }
2467 : :
2468 : 1120659 : hmap_insert(matches, &match->hmap_node, hash);
2469 : : }
2470 : :
2471 : : /* Applies EXPR_T_CMP-typed 'expr' to 'm'. This will only work properly if 'm'
2472 : : * doesn't already match on 'expr->cmp.symbol', because it replaces any
2473 : : * existing match on that symbol instead of intersecting with it.
2474 : : *
2475 : : * If 'expr' is a comparison on a string field, uses 'lookup_port' and 'aux' to
2476 : : * convert the string to a port number. In such a case, if the port can't be
2477 : : * found, returns false. In all other cases, returns true. */
2478 : : static bool
2479 : 1990085 : constrain_match(const struct expr *expr,
2480 : : bool (*lookup_port)(const void *aux,
2481 : : const char *port_name,
2482 : : unsigned int *portp),
2483 : : const void *aux, struct match *m)
2484 : : {
2485 [ - + ]: 1990085 : ovs_assert(expr->type == EXPR_T_CMP);
2486 [ + + ]: 1990085 : if (expr->cmp.symbol->width) {
2487 : 1636889 : mf_mask_subfield(expr->cmp.symbol->field, &expr->cmp.value,
2488 : : &expr->cmp.mask, m);
2489 : : } else {
2490 : : unsigned int port;
2491 [ + + ]: 353196 : if (!lookup_port(aux, expr->cmp.string, &port)) {
2492 : 6 : return false;
2493 : : }
2494 : :
2495 : : struct mf_subfield sf;
2496 : 353190 : sf.field = expr->cmp.symbol->field;
2497 : 353190 : sf.ofs = 0;
2498 : 353190 : sf.n_bits = expr->cmp.symbol->field->n_bits;
2499 : :
2500 : : union mf_subvalue x;
2501 : 353190 : memset(&x, 0, sizeof x);
2502 : 353190 : x.integer = htonll(port);
2503 : :
2504 : 353190 : mf_write_subfield(&sf, &x, m);
2505 : : }
2506 : 1990079 : return true;
2507 : : }
2508 : :
2509 : : static bool
2510 : 28787 : add_disjunction(const struct expr *or,
2511 : : bool (*lookup_port)(const void *aux, const char *port_name,
2512 : : unsigned int *portp),
2513 : : const void *aux,
2514 : : struct match *m, uint8_t clause, uint8_t n_clauses,
2515 : : uint32_t conj_id, struct hmap *matches)
2516 : : {
2517 : : struct expr *sub;
2518 : 28787 : int n = 0;
2519 : :
2520 [ - + ]: 28787 : ovs_assert(or->type == EXPR_T_OR);
2521 [ + + ]: 87225 : LIST_FOR_EACH (sub, node, &or->andor) {
2522 : 58438 : struct expr_match *match = expr_match_new(m, clause, n_clauses,
2523 : : conj_id);
2524 [ + + ]: 58438 : if (constrain_match(sub, lookup_port, aux, &match->match)) {
2525 : 58436 : expr_match_add(matches, match);
2526 : 58436 : n++;
2527 : : } else {
2528 : 2 : free(match->conjunctions);
2529 : 2 : free(match);
2530 : : }
2531 : : }
2532 : :
2533 : : /* If n == 1, then this didn't really need to be a disjunction. Oh well,
2534 : : * that shouldn't happen much. */
2535 : 28787 : return n > 0;
2536 : : }
2537 : :
2538 : : static void
2539 : 541520 : add_conjunction(const struct expr *and,
2540 : : bool (*lookup_port)(const void *aux, const char *port_name,
2541 : : unsigned int *portp),
2542 : : const void *aux, uint32_t *n_conjsp, struct hmap *matches)
2543 : : {
2544 : : struct match match;
2545 : 541520 : int n_clauses = 0;
2546 : : struct expr *sub;
2547 : :
2548 : 541520 : match_init_catchall(&match);
2549 : :
2550 [ - + ]: 541520 : ovs_assert(and->type == EXPR_T_AND);
2551 [ + + ]: 2076913 : LIST_FOR_EACH (sub, node, &and->andor) {
2552 [ + + - - ]: 1535395 : switch (sub->type) {
2553 : : case EXPR_T_CMP:
2554 [ + + ]: 1506608 : if (!constrain_match(sub, lookup_port, aux, &match)) {
2555 : 2 : return;
2556 : : }
2557 : 1506606 : break;
2558 : : case EXPR_T_OR:
2559 : 28787 : n_clauses++;
2560 : 28787 : break;
2561 : : case EXPR_T_AND:
2562 : : case EXPR_T_BOOLEAN:
2563 : 0 : OVS_NOT_REACHED();
2564 : : }
2565 : : }
2566 : :
2567 [ + + ]: 541518 : if (!n_clauses) {
2568 : 513143 : expr_match_add(matches, expr_match_new(&match, 0, 0, 0));
2569 [ + + ]: 28375 : } else if (n_clauses == 1) {
2570 [ + + ]: 84067 : LIST_FOR_EACH (sub, node, &and->andor) {
2571 [ + + ]: 56104 : if (sub->type == EXPR_T_OR) {
2572 : 27963 : add_disjunction(sub, lookup_port, aux, &match, 0, 0, 0,
2573 : : matches);
2574 : : }
2575 : : }
2576 : : } else {
2577 : 412 : int clause = 0;
2578 : 412 : (*n_conjsp)++;
2579 [ + + ]: 1236 : LIST_FOR_EACH (sub, node, &and->andor) {
2580 [ + - ]: 824 : if (sub->type == EXPR_T_OR) {
2581 [ - + ]: 824 : if (!add_disjunction(sub, lookup_port, aux, &match, clause++,
2582 : : n_clauses, *n_conjsp, matches)) {
2583 : : /* This clause can't ever match, so we might as well skip
2584 : : * adding the other clauses--the overall disjunctive flow
2585 : : * can't ever match. Ideally we would also back out all of
2586 : : * the clauses we already added, but that seems like a lot
2587 : : * of trouble for a case that might never occur in
2588 : : * practice. */
2589 : 0 : return;
2590 : : }
2591 : : }
2592 : : }
2593 : :
2594 : : /* Add the flow that matches on conj_id. */
2595 : 412 : match_set_conj_id(&match, *n_conjsp);
2596 : 541518 : expr_match_add(matches, expr_match_new(&match, 0, 0, 0));
2597 : : }
2598 : : }
2599 : :
2600 : : static void
2601 : 425039 : add_cmp_flow(const struct expr *cmp,
2602 : : bool (*lookup_port)(const void *aux, const char *port_name,
2603 : : unsigned int *portp),
2604 : : const void *aux, struct hmap *matches)
2605 : : {
2606 : 425039 : struct expr_match *m = expr_match_new(NULL, 0, 0, 0);
2607 [ + + ]: 425039 : if (constrain_match(cmp, lookup_port, aux, &m->match)) {
2608 : 425037 : expr_match_add(matches, m);
2609 : : } else {
2610 : 2 : free(m);
2611 : : }
2612 : 425039 : }
2613 : :
2614 : : /* Converts 'expr', which must be in the form returned by expr_normalize(), to
2615 : : * a collection of Open vSwitch flows in 'matches', which this function
2616 : : * initializes to an hmap of "struct expr_match" structures. Returns the
2617 : : * number of conjunctive match IDs consumed by 'matches', which uses
2618 : : * conjunctive match IDs beginning with 0; the caller must offset or remap them
2619 : : * into the desired range as necessary.
2620 : : *
2621 : : * The matches inserted into 'matches' will be of three distinct kinds:
2622 : : *
2623 : : * - Ordinary flows. The caller should add these OpenFlow flows with
2624 : : * its desired actions.
2625 : : *
2626 : : * - Conjunctive flows, distinguished by 'n > 0' in the expr_match
2627 : : * structure. The caller should add these OpenFlow flows with the
2628 : : * conjunction(id, k/n) actions as specified in the 'conjunctions' array,
2629 : : * remapping the ids.
2630 : : *
2631 : : * - conj_id flows, distinguished by matching on the "conj_id" field. The
2632 : : * caller should remap the conj_id and add the OpenFlow flow with its
2633 : : * desired actions.
2634 : : *
2635 : : * 'lookup_port' must be a function to map from a port name to a port number.
2636 : : * When successful, 'lookup_port' stores the port number into '*portp' and
2637 : : * returns true; when there is no port by the given name, it returns false.
2638 : : * 'aux' is passed to 'lookup_port' as auxiliary data. Any comparisons against
2639 : : * string fields in 'expr' are translated into integers through this function.
2640 : : * A comparison against a string that is not in 'ports' acts like a Boolean
2641 : : * "false"; that is, it will always fail to match. For a simple expression,
2642 : : * this means that the overall expression always fails to match, but an
2643 : : * expression with a disjunction on the string field might still match on other
2644 : : * port names.
2645 : : *
2646 : : * (This treatment of string fields might be too simplistic in general, but it
2647 : : * seems reasonable for now when string fields are used only for ports.) */
2648 : : uint32_t
2649 : 857638 : expr_to_matches(const struct expr *expr,
2650 : : bool (*lookup_port)(const void *aux, const char *port_name,
2651 : : unsigned int *portp),
2652 : : const void *aux, struct hmap *matches)
2653 : : {
2654 : 857638 : uint32_t n_conjs = 0;
2655 : :
2656 : 857638 : hmap_init(matches);
2657 [ + + + + : 857638 : switch (expr->type) {
- ]
2658 : : case EXPR_T_CMP:
2659 : 217327 : add_cmp_flow(expr, lookup_port, aux, matches);
2660 : 217327 : break;
2661 : :
2662 : : case EXPR_T_AND:
2663 : 279761 : add_conjunction(expr, lookup_port, aux, &n_conjs, matches);
2664 : 279761 : break;
2665 : :
2666 : : case EXPR_T_OR:
2667 [ + + ]: 199681 : if (expr_is_cmp(expr)) {
2668 : : struct expr *sub;
2669 : :
2670 [ + + ]: 72645 : LIST_FOR_EACH (sub, node, &expr->andor) {
2671 : 50876 : add_cmp_flow(sub, lookup_port, aux, matches);
2672 : : }
2673 : : } else {
2674 : : struct expr *sub;
2675 : :
2676 [ + + ]: 596507 : LIST_FOR_EACH (sub, node, &expr->andor) {
2677 [ + + ]: 418595 : if (sub->type == EXPR_T_AND) {
2678 : 261759 : add_conjunction(sub, lookup_port, aux, &n_conjs, matches);
2679 : : } else {
2680 : 156836 : add_cmp_flow(sub, lookup_port, aux, matches);
2681 : : }
2682 : : }
2683 : : }
2684 : 199681 : break;
2685 : :
2686 : : case EXPR_T_BOOLEAN:
2687 [ + + ]: 160869 : if (expr->boolean) {
2688 : 134440 : struct expr_match *m = expr_match_new(NULL, 0, 0, 0);
2689 : 134440 : expr_match_add(matches, m);
2690 : : } else {
2691 : : /* No match. */
2692 : : }
2693 : 160869 : break;
2694 : : }
2695 : 857638 : return n_conjs;
2696 : : }
2697 : :
2698 : : /* Destroys all of the 'struct expr_match'es in 'matches', as well as the
2699 : : * 'matches' hmap itself. */
2700 : : void
2701 : 857638 : expr_matches_destroy(struct hmap *matches)
2702 : : {
2703 : : struct expr_match *m;
2704 : :
2705 [ + + ][ - + ]: 1978297 : HMAP_FOR_EACH_POP (m, hmap_node, matches) {
[ + + ]
2706 : 1120659 : free(m->conjunctions);
2707 : 1120659 : free(m);
2708 : : }
2709 : 857638 : hmap_destroy(matches);
2710 : 857638 : }
2711 : :
2712 : : /* Prints a representation of the 'struct expr_match'es in 'matches' to
2713 : : * 'stream'. */
2714 : : void
2715 : 18 : expr_matches_print(const struct hmap *matches, FILE *stream)
2716 : : {
2717 [ + + ]: 18 : if (hmap_is_empty(matches)) {
2718 : 3 : fputs("(no flows)\n", stream);
2719 : 3 : return;
2720 : : }
2721 : :
2722 : : const struct expr_match *m;
2723 [ + + ][ - + ]: 60 : HMAP_FOR_EACH (m, hmap_node, matches) {
2724 : 45 : char *s = match_to_string(&m->match, OFP_DEFAULT_PRIORITY);
2725 : 45 : fputs(s, stream);
2726 : 45 : free(s);
2727 : :
2728 [ - + ]: 45 : if (m->n) {
2729 [ # # ]: 0 : for (int i = 0; i < m->n; i++) {
2730 : 0 : const struct cls_conjunction *c = &m->conjunctions[i];
2731 [ # # ]: 0 : fprintf(stream, "%c conjunction(%"PRIu32", %d/%d)",
2732 : 0 : i == 0 ? ':' : ',', c->id, c->clause, c->n_clauses);
2733 : : }
2734 : : }
2735 : 45 : putc('\n', stream);
2736 : : }
2737 : : }
2738 : :
2739 : : /* Returns true if 'expr' honors the invariants for expressions (see the large
2740 : : * comment above "struct expr" in expr.h), false otherwise. */
2741 : : bool
2742 : 36122046 : expr_honors_invariants(const struct expr *expr)
2743 : : {
2744 : : const struct expr *sub;
2745 : :
2746 [ + + + - ]: 36122046 : switch (expr->type) {
2747 : : case EXPR_T_CMP:
2748 [ + + ]: 21566560 : if (expr->cmp.symbol->width) {
2749 [ + + ]: 307576784 : for (int i = 0; i < ARRAY_SIZE(expr->cmp.value.be64); i++) {
2750 [ - + ]: 289484032 : if (expr->cmp.value.be64[i] & ~expr->cmp.mask.be64[i]) {
2751 : 0 : return false;
2752 : : }
2753 : : }
2754 : : }
2755 : 21566560 : return true;
2756 : :
2757 : : case EXPR_T_AND:
2758 : : case EXPR_T_OR:
2759 [ - + ]: 13017364 : if (ovs_list_is_short(&expr->andor)) {
2760 : 0 : return false;
2761 : : }
2762 [ + + ]: 42975402 : LIST_FOR_EACH (sub, node, &expr->andor) {
2763 [ + - ][ - + ]: 29958038 : if (sub->type == expr->type || !expr_honors_invariants(sub)) {
2764 : 0 : return false;
2765 : : }
2766 : : }
2767 : 13017364 : return true;
2768 : :
2769 : : case EXPR_T_BOOLEAN:
2770 : 1538122 : return true;
2771 : :
2772 : : default:
2773 : 0 : OVS_NOT_REACHED();
2774 : : }
2775 : : }
2776 : :
2777 : : static bool
2778 : 1738093 : expr_is_normalized_and(const struct expr *expr)
2779 : : {
2780 : : /* XXX should also check that no symbol is repeated. */
2781 : : const struct expr *sub;
2782 : :
2783 [ + + ]: 5390391 : LIST_FOR_EACH (sub, node, &expr->andor) {
2784 [ - + ]: 3652298 : if (!expr_is_cmp(sub)) {
2785 : 0 : return false;
2786 : : }
2787 : : }
2788 : 1738093 : return true;
2789 : : }
2790 : :
2791 : : /* Returns true if 'expr' is in the form returned by expr_normalize(), false
2792 : : * otherwise. */
2793 : : bool
2794 : 2427002 : expr_is_normalized(const struct expr *expr)
2795 : : {
2796 [ + + + + : 2427002 : switch (expr->type) {
- ]
2797 : : case EXPR_T_CMP:
2798 : 347973 : return true;
2799 : :
2800 : : case EXPR_T_AND:
2801 : 413136 : return expr_is_normalized_and(expr);
2802 : :
2803 : : case EXPR_T_OR:
2804 [ + + ]: 1239814 : if (!expr_is_cmp(expr)) {
2805 : : const struct expr *sub;
2806 : :
2807 [ + + ]: 4040083 : LIST_FOR_EACH (sub, node, &expr->andor) {
2808 [ + + ][ - + ]: 2921641 : if (!expr_is_cmp(sub) && !expr_is_normalized_and(sub)) {
2809 : 0 : return false;
2810 : : }
2811 : : }
2812 : : }
2813 : 1239814 : return true;
2814 : :
2815 : : case EXPR_T_BOOLEAN:
2816 : 426079 : return true;
2817 : :
2818 : : default:
2819 : 0 : OVS_NOT_REACHED();
2820 : : }
2821 : : }
2822 : :
2823 : : static bool
2824 : 229615212 : expr_evaluate_andor(const struct expr *e, const struct flow *f,
2825 : : bool short_circuit,
2826 : : bool (*lookup_port)(const void *aux, const char *port_name,
2827 : : unsigned int *portp),
2828 : : const void *aux)
2829 : : {
2830 : : const struct expr *sub;
2831 : :
2832 [ + + ]: 444541308 : LIST_FOR_EACH (sub, node, &e->andor) {
2833 [ + + ]: 379316868 : if (expr_evaluate(sub, f, lookup_port, aux) == short_circuit) {
2834 : 164390772 : return short_circuit;
2835 : : }
2836 : : }
2837 : 65224440 : return !short_circuit;
2838 : : }
2839 : :
2840 : : static bool
2841 : 291501108 : expr_evaluate_cmp(const struct expr *e, const struct flow *f,
2842 : : bool (*lookup_port)(const void *aux, const char *port_name,
2843 : : unsigned int *portp),
2844 : : const void *aux)
2845 : : {
2846 : 291501108 : const struct expr_symbol *s = e->cmp.symbol;
2847 : 291501108 : const struct mf_field *field = s->field;
2848 : :
2849 : : int cmp;
2850 [ + + ]: 291501108 : if (e->cmp.symbol->width) {
2851 : 276253968 : int n_bytes = field->n_bytes;
2852 : 276253968 : const uint8_t *cst = &e->cmp.value.u8[sizeof e->cmp.value - n_bytes];
2853 : 276253968 : const uint8_t *mask = &e->cmp.mask.u8[sizeof e->cmp.mask - n_bytes];
2854 : :
2855 : : /* Get field value and mask off undesired bits. */
2856 : : union mf_value value;
2857 : 276253968 : mf_get_value(field, f, &value);
2858 [ + + ]: 1381269840 : for (int i = 0; i < field->n_bytes; i++) {
2859 : 1105015872 : value.b[i] &= mask[i];
2860 : : }
2861 : :
2862 : : /* Compare against constant. */
2863 : 276253968 : cmp = memcmp(&value, cst, n_bytes);
2864 : : } else {
2865 : : /* Get field value. */
2866 : 30494280 : struct mf_subfield sf = { .field = field, .ofs = 0,
2867 : 15247140 : .n_bits = field->n_bits };
2868 : 15247140 : uint64_t value = mf_get_subfield(&sf, f);
2869 : :
2870 : : /* Get constant. */
2871 : : unsigned int cst;
2872 [ - + ]: 15247140 : if (!lookup_port(aux, e->cmp.string, &cst)) {
2873 : 0 : return false;
2874 : : }
2875 : :
2876 : : /* Compare. */
2877 [ + + ]: 15247140 : cmp = value < cst ? -1 : value > cst;
2878 : : }
2879 : :
2880 : 291501108 : return expr_relop_test(e->cmp.relop, cmp);
2881 : : }
2882 : :
2883 : : /* Evaluates 'e' against microflow 'uflow' and returns the result.
2884 : : *
2885 : : * 'lookup_port' must be a function to map from a port name to a port number
2886 : : * and 'aux' auxiliary data to pass to it; see expr_to_matches() for more
2887 : : * details.
2888 : : *
2889 : : * This isn't particularly fast. For performance-sensitive tasks, use
2890 : : * expr_to_matches() and the classifier. */
2891 : : bool
2892 : 532360948 : expr_evaluate(const struct expr *e, const struct flow *uflow,
2893 : : bool (*lookup_port)(const void *aux, const char *port_name,
2894 : : unsigned int *portp),
2895 : : const void *aux)
2896 : : {
2897 [ + + + + : 532360948 : switch (e->type) {
- ]
2898 : : case EXPR_T_CMP:
2899 : 291501108 : return expr_evaluate_cmp(e, uflow, lookup_port, aux);
2900 : :
2901 : : case EXPR_T_AND:
2902 : 111191920 : return expr_evaluate_andor(e, uflow, false, lookup_port, aux);
2903 : :
2904 : : case EXPR_T_OR:
2905 : 118423292 : return expr_evaluate_andor(e, uflow, true, lookup_port, aux);
2906 : :
2907 : : case EXPR_T_BOOLEAN:
2908 : 11244628 : return e->boolean;
2909 : :
2910 : : default:
2911 : 0 : OVS_NOT_REACHED();
2912 : : }
2913 : : }
2914 : :
2915 : : /* Action parsing helper. */
2916 : :
2917 : : /* Checks that 'f' is 'n_bits' wide (where 'n_bits == 0' means that 'f' must be
2918 : : * a string field) and, if 'rw' is true, that 'f' is modifiable. Returns NULL
2919 : : * if 'f' is acceptable, otherwise a malloc()'d error message that the caller
2920 : : * must free(). */
2921 : : char * OVS_WARN_UNUSED_RESULT
2922 : 1165682 : expr_type_check(const struct expr_field *f, int n_bits, bool rw)
2923 : : {
2924 [ + + ]: 1165682 : if (n_bits != f->n_bits) {
2925 [ + + ][ + + ]: 7 : if (n_bits && f->n_bits) {
2926 : 3 : return xasprintf("Cannot use %d-bit field %s[%d..%d] "
2927 : : "where %d-bit field is required.",
2928 : 3 : f->n_bits, f->symbol->name,
2929 : 3 : f->ofs, f->ofs + f->n_bits - 1,
2930 : : n_bits);
2931 [ + + ]: 4 : } else if (n_bits) {
2932 : 2 : return xasprintf("Cannot use string field %s where numeric "
2933 : 2 : "field is required.", f->symbol->name);
2934 : : } else {
2935 : 2 : return xasprintf("Cannot use numeric field %s where string "
2936 : 2 : "field is required.", f->symbol->name);
2937 : : }
2938 : : }
2939 : :
2940 [ + + ][ + + ]: 1165675 : if (rw && !f->symbol->rw) {
2941 : 4 : return xasprintf("Field %s is not modifiable.", f->symbol->name);
2942 : : }
2943 : :
2944 : 1165671 : return NULL;
2945 : : }
2946 : :
2947 : : /* Returns the mf_subfield that corresponds to 'f'. */
2948 : : struct mf_subfield
2949 : 1215515 : expr_resolve_field(const struct expr_field *f)
2950 : : {
2951 : 1215515 : const struct expr_symbol *symbol = f->symbol;
2952 : 1215515 : int ofs = f->ofs;
2953 : :
2954 [ + + ]: 1361551 : while (symbol->parent) {
2955 : 146036 : ofs += symbol->parent_ofs;
2956 : 146036 : symbol = symbol->parent;
2957 : : }
2958 : :
2959 [ + + ]: 1215515 : int n_bits = symbol->width ? f->n_bits : symbol->field->n_bits;
2960 : 1215515 : return (struct mf_subfield) { symbol->field, ofs, n_bits };
2961 : : }
2962 : :
2963 : : static struct expr *
2964 : 0 : expr_parse_microflow__(struct lexer *lexer,
2965 : : const struct shash *symtab,
2966 : : bool (*lookup_port)(const void *aux,
2967 : : const char *port_name,
2968 : : unsigned int *portp),
2969 : : const void *aux,
2970 : : struct expr *e, struct flow *uflow)
2971 : : {
2972 : : char *error;
2973 : 0 : e = expr_annotate(e, symtab, &error);
2974 [ # # ]: 0 : if (error) {
2975 : 0 : lexer_error(lexer, "%s", error);
2976 : 0 : free(error);
2977 : 0 : return NULL;
2978 : : }
2979 : :
2980 : 0 : struct ds annotated = DS_EMPTY_INITIALIZER;
2981 : 0 : expr_format(e, &annotated);
2982 : :
2983 : 0 : e = expr_simplify(e);
2984 : 0 : e = expr_normalize(e);
2985 : :
2986 : 0 : struct match m = MATCH_CATCHALL_INITIALIZER;
2987 : :
2988 [ # # # # : 0 : switch (e->type) {
# ]
2989 : : case EXPR_T_BOOLEAN:
2990 [ # # ]: 0 : if (!e->boolean) {
2991 : 0 : lexer_error(lexer, "Constraints are contradictory.");
2992 : : }
2993 : 0 : break;
2994 : :
2995 : : case EXPR_T_OR:
2996 : 0 : lexer_error(lexer, "Constraints are ambiguous: %s.",
2997 : : ds_cstr(&annotated));
2998 : 0 : break;
2999 : :
3000 : : case EXPR_T_CMP:
3001 : 0 : constrain_match(e, lookup_port, aux, &m);
3002 : 0 : break;
3003 : :
3004 : : case EXPR_T_AND: {
3005 : : struct expr *sub;
3006 [ # # ]: 0 : LIST_FOR_EACH (sub, node, &e->andor) {
3007 [ # # ]: 0 : if (sub->type == EXPR_T_CMP) {
3008 : 0 : constrain_match(sub, lookup_port, aux, &m);
3009 : : } else {
3010 [ # # ]: 0 : ovs_assert(sub->type == EXPR_T_OR);
3011 : 0 : lexer_error(lexer, "Constraints are ambiguous: %s.",
3012 : : ds_cstr(&annotated));
3013 : 0 : break;
3014 : : }
3015 : : }
3016 : : }
3017 : 0 : break;
3018 : :
3019 : : default:
3020 : 0 : OVS_NOT_REACHED();
3021 : : }
3022 : 0 : ds_destroy(&annotated);
3023 : :
3024 : 0 : *uflow = m.flow;
3025 : 0 : return e;
3026 : : }
3027 : :
3028 : : /* Parses 's' as a microflow, using symbols from 'symtab', macros from
3029 : : * 'macros', and looking up port numbers using 'lookup_port' and 'aux'. On
3030 : : * success, stores the result in 'uflow' and returns NULL, otherwise zeros
3031 : : * 'uflow' and returns an error message that the caller must free().
3032 : : *
3033 : : * A "microflow" is a description of a single stream of packets, such as half a
3034 : : * TCP connection. 's' uses the syntax of an OVN logical expression to express
3035 : : * constraints that describe the microflow. For example, "ip4 && tcp.src ==
3036 : : * 80" would set uflow->dl_type to ETH_TYPE_IP, uflow->nw_proto to IPPROTO_TCP,
3037 : : * and uflow->tp_src to 80.
3038 : : *
3039 : : * Microflow expressions can be erroneous in two ways. First, they can be
3040 : : * ambiguous. For example, "tcp.src == 80" is ambiguous because it does not
3041 : : * state IPv4 or IPv6 as the Ethernet type. "ip4 && tcp.src > 1024" is also
3042 : : * ambiguous because it does not constrain bits of tcp.src to particular
3043 : : * values. Second, they can be contradictory, e.g. "ip4 && ip6". This
3044 : : * function will report both types of errors.
3045 : : *
3046 : : * This function isn't that smart, so it can yield errors for some "clever"
3047 : : * formulations of particular microflows that area accepted other ways. For
3048 : : * example, all of the following expressions are equivalent:
3049 : : * ip4 && tcp.src[1..15] == 0x28
3050 : : * ip4 && tcp.src > 79 && tcp.src < 82
3051 : : * ip4 && 80 <= tcp.src <= 81
3052 : : * ip4 && tcp.src == {80, 81}
3053 : : * but as of this writing this function only accepts the first two, rejecting
3054 : : * the last two as ambiguous. Just don't be too clever. */
3055 : : char * OVS_WARN_UNUSED_RESULT
3056 : 0 : expr_parse_microflow(const char *s, const struct shash *symtab,
3057 : : const struct shash *macros,
3058 : : bool (*lookup_port)(const void *aux,
3059 : : const char *port_name,
3060 : : unsigned int *portp),
3061 : : const void *aux, struct flow *uflow)
3062 : : {
3063 : : struct lexer lexer;
3064 : 0 : lexer_init(&lexer, s);
3065 : 0 : lexer_get(&lexer);
3066 : :
3067 : 0 : struct expr *e = expr_parse(&lexer, symtab, macros);
3068 : 0 : lexer_force_end(&lexer);
3069 : :
3070 [ # # ]: 0 : if (e) {
3071 : 0 : e = expr_parse_microflow__(&lexer, symtab, lookup_port, aux, e, uflow);
3072 : : }
3073 : :
3074 : 0 : char *error = lexer_steal_error(&lexer);
3075 : 0 : lexer_destroy(&lexer);
3076 : 0 : expr_destroy(e);
3077 : :
3078 [ # # ]: 0 : if (error) {
3079 : 0 : memset(uflow, 0, sizeof *uflow);
3080 : : }
3081 : 0 : return error;
3082 : : }
|
