2 * Copyright (c) 2015, 2016 Nicira, Inc.
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:
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
18 #include "byte-order.h"
22 #include "logical-fields.h"
23 #include "openvswitch/dynamic-string.h"
24 #include "openvswitch/match.h"
25 #include "openvswitch/ofp-actions.h"
26 #include "openvswitch/vlog.h"
31 VLOG_DEFINE_THIS_MODULE(expr);
33 /* Returns the name of measurement level 'level'. */
35 expr_level_to_string(enum expr_level level)
38 case EXPR_L_NOMINAL: return "nominal";
39 case EXPR_L_BOOLEAN: return "Boolean";
40 case EXPR_L_ORDINAL: return "ordinal";
41 default: OVS_NOT_REACHED();
45 /* Relational operators. */
47 /* Returns a string form of relational operator 'relop'. */
49 expr_relop_to_string(enum expr_relop relop)
52 case EXPR_R_EQ: return "==";
53 case EXPR_R_NE: return "!=";
54 case EXPR_R_LT: return "<";
55 case EXPR_R_LE: return "<=";
56 case EXPR_R_GT: return ">";
57 case EXPR_R_GE: return ">=";
58 default: OVS_NOT_REACHED();
63 expr_relop_from_token(enum lex_type type, enum expr_relop *relop)
68 case LEX_T_EQ: r = EXPR_R_EQ; break;
69 case LEX_T_NE: r = EXPR_R_NE; break;
70 case LEX_T_LT: r = EXPR_R_LT; break;
71 case LEX_T_LE: r = EXPR_R_LE; break;
72 case LEX_T_GT: r = EXPR_R_GT; break;
73 case LEX_T_GE: r = EXPR_R_GE; break;
74 default: return false;
83 /* Returns the relational operator that 'relop' becomes if you turn the
84 * relation's operands around, e.g. EXPR_R_EQ does not change because "a == b"
85 * and "b == a" are equivalent, but EXPR_R_LE becomes EXPR_R_GE because "a <=
86 * b" is equivalent to "b >= a". */
87 static enum expr_relop
88 expr_relop_turn(enum expr_relop relop)
91 case EXPR_R_EQ: return EXPR_R_EQ;
92 case EXPR_R_NE: return EXPR_R_NE;
93 case EXPR_R_LT: return EXPR_R_GT;
94 case EXPR_R_LE: return EXPR_R_GE;
95 case EXPR_R_GT: return EXPR_R_LT;
96 case EXPR_R_GE: return EXPR_R_LE;
97 default: OVS_NOT_REACHED();
101 /* Returns the relational operator that is the opposite of 'relop'. */
102 static enum expr_relop
103 expr_relop_invert(enum expr_relop relop)
106 case EXPR_R_EQ: return EXPR_R_NE;
107 case EXPR_R_NE: return EXPR_R_EQ;
108 case EXPR_R_LT: return EXPR_R_GE;
109 case EXPR_R_LE: return EXPR_R_GT;
110 case EXPR_R_GT: return EXPR_R_LE;
111 case EXPR_R_GE: return EXPR_R_LT;
112 default: OVS_NOT_REACHED();
116 /* Constructing and manipulating expressions. */
118 /* Creates and returns a logical AND or OR expression (according to 'type',
119 * which must be EXPR_T_AND or EXPR_T_OR) that initially has no
120 * sub-expressions. (To satisfy the invariants for expressions, the caller
121 * must add at least two sub-expressions whose types are different from
124 expr_create_andor(enum expr_type type)
126 struct expr *e = xmalloc(sizeof *e);
128 ovs_list_init(&e->andor);
132 /* Returns a logical AND or OR expression (according to 'type', which must be
133 * EXPR_T_AND or EXPR_T_OR) whose sub-expressions are 'a' and 'b', with some
136 * - If 'a' or 'b' is NULL, just returns the other one (which means that if
137 * that other one is not of the given 'type', then the returned
138 * expression is not either).
140 * - If 'a' or 'b', or both, have type 'type', then they are combined into
141 * a single node that satisfies the invariants for expressions. */
143 expr_combine(enum expr_type type, struct expr *a, struct expr *b)
149 } else if (a->type == type) {
150 if (b->type == type) {
151 ovs_list_splice(&a->andor, b->andor.next, &b->andor);
154 ovs_list_push_back(&a->andor, &b->node);
157 } else if (b->type == type) {
158 ovs_list_push_front(&b->andor, &a->node);
161 struct expr *e = expr_create_andor(type);
162 ovs_list_push_back(&e->andor, &a->node);
163 ovs_list_push_back(&e->andor, &b->node);
169 expr_insert_andor(struct expr *andor, struct expr *before, struct expr *new)
171 if (new->type == andor->type) {
172 if (andor->type == EXPR_T_AND) {
173 /* Conjunction junction, what's your function? */
175 ovs_list_splice(&before->node, new->andor.next, &new->andor);
178 ovs_list_insert(&before->node, &new->node);
182 /* Returns an EXPR_T_BOOLEAN expression with value 'b'. */
184 expr_create_boolean(bool b)
186 struct expr *e = xmalloc(sizeof *e);
187 e->type = EXPR_T_BOOLEAN;
193 expr_not(struct expr *expr)
197 switch (expr->type) {
199 expr->cmp.relop = expr_relop_invert(expr->cmp.relop);
204 LIST_FOR_EACH (sub, node, &expr->andor) {
207 expr->type = expr->type == EXPR_T_AND ? EXPR_T_OR : EXPR_T_AND;
211 expr->boolean = !expr->boolean;
219 expr_fix_andor(struct expr *expr, bool short_circuit)
221 struct expr *sub, *next;
223 LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
224 if (sub->type == EXPR_T_BOOLEAN) {
225 if (sub->boolean == short_circuit) {
227 return expr_create_boolean(short_circuit);
229 ovs_list_remove(&sub->node);
235 if (ovs_list_is_short(&expr->andor)) {
236 if (ovs_list_is_empty(&expr->andor)) {
238 return expr_create_boolean(!short_circuit);
240 sub = expr_from_node(ovs_list_front(&expr->andor));
249 /* Returns 'expr' modified so that top-level oddities are fixed up:
251 * - Eliminates any EXPR_T_BOOLEAN operands at the top level.
253 * - Replaces one-operand EXPR_T_AND or EXPR_T_OR by its subexpression. */
255 expr_fix(struct expr *expr)
257 switch (expr->type) {
262 return expr_fix_andor(expr, false);
265 return expr_fix_andor(expr, true);
278 find_bitwise_range(const union mf_subvalue *sv, int width,
279 int *startp, int *n_bitsp)
281 unsigned int start = bitwise_scan(sv, sizeof *sv, true, 0, width);
283 unsigned int end = bitwise_scan(sv, sizeof *sv, false, start, width);
285 || bitwise_scan(sv, sizeof *sv, true, end, width) >= width) {
287 *n_bitsp = end - start;
291 *startp = *n_bitsp = 0;
295 expr_format_cmp(const struct expr *e, struct ds *s)
297 /* The common case is numerical comparisons.
298 * Handle string comparisons as a special case. */
299 if (!e->cmp.symbol->width) {
300 ds_put_format(s, "%s %s ", e->cmp.symbol->name,
301 expr_relop_to_string(e->cmp.relop));
302 json_string_escape(e->cmp.string, s);
307 find_bitwise_range(&e->cmp.mask, e->cmp.symbol->width, &ofs, &n);
308 if (n == 1 && (e->cmp.relop == EXPR_R_EQ || e->cmp.relop == EXPR_R_NE)) {
311 positive = bitwise_get_bit(&e->cmp.value, sizeof e->cmp.value, ofs);
312 positive ^= e->cmp.relop == EXPR_R_NE;
316 ds_put_cstr(s, e->cmp.symbol->name);
317 if (e->cmp.symbol->width > 1) {
318 ds_put_format(s, "[%d]", ofs);
323 ds_put_cstr(s, e->cmp.symbol->name);
324 if (n > 0 && n < e->cmp.symbol->width) {
326 ds_put_format(s, "[%d..%d]", ofs, ofs + n - 1);
328 ds_put_format(s, "[%d]", ofs);
332 ds_put_format(s, " %s ", expr_relop_to_string(e->cmp.relop));
335 union mf_subvalue value;
337 memset(&value, 0, sizeof value);
338 bitwise_copy(&e->cmp.value, sizeof e->cmp.value, ofs,
339 &value, sizeof value, 0,
341 mf_format_subvalue(&value, s);
343 mf_format_subvalue(&e->cmp.value, s);
345 mf_format_subvalue(&e->cmp.mask, s);
350 expr_format_andor(const struct expr *e, const char *op, struct ds *s)
355 LIST_FOR_EACH (sub, node, &e->andor) {
357 ds_put_format(s, " %s ", op);
360 if (sub->type == EXPR_T_AND || sub->type == EXPR_T_OR) {
370 /* Appends a string form of 'e' to 's'. The string form is acceptable for
371 * parsing back into an equivalent expression. */
373 expr_format(const struct expr *e, struct ds *s)
377 expr_format_cmp(e, s);
381 expr_format_andor(e, "&&", s);
385 expr_format_andor(e, "||", s);
389 ds_put_char(s, e->boolean ? '1' : '0');
394 /* Prints a string form of 'e' on stdout, followed by a new-line. */
396 expr_print(const struct expr *e)
401 expr_format(e, &output);
402 puts(ds_cstr(&output));
408 /* Type of a "union expr_constant" or "struct expr_constant_set". */
409 enum expr_constant_type {
414 /* A string or integer constant (one must know which from context). */
415 union expr_constant {
418 * The width of a constant isn't always clear, e.g. if you write "1",
419 * there's no way to tell whether you mean for that to be a 1-bit constant
420 * or a 128-bit constant or somewhere in between. */
422 union mf_subvalue value;
423 union mf_subvalue mask; /* Only initialized if 'masked'. */
426 enum lex_format format; /* From the constant's lex_token. */
429 /* Null-terminated string constant. */
433 /* A collection of "union expr_constant"s of the same type. */
434 struct expr_constant_set {
435 union expr_constant *values; /* Constants. */
436 size_t n_values; /* Number of constants. */
437 enum expr_constant_type type; /* Type of the constants. */
438 bool in_curlies; /* Whether the constants were in {}. */
441 /* A reference to a symbol or a subfield of a symbol.
443 * For string fields, ofs and n_bits are 0. */
445 const struct expr_symbol *symbol; /* The symbol. */
446 int ofs; /* Starting bit offset. */
447 int n_bits; /* Number of bits. */
450 /* Context maintained during expr_parse(). */
451 struct expr_context {
452 struct lexer *lexer; /* Lexer for pulling more tokens. */
453 const struct shash *symtab; /* Symbol table. */
454 char *error; /* Error, if any, otherwise NULL. */
455 bool not; /* True inside odd number of NOT operators. */
458 struct expr *expr_parse__(struct expr_context *);
459 static void expr_not(struct expr *);
460 static void expr_constant_set_destroy(struct expr_constant_set *);
461 static bool parse_field(struct expr_context *, struct expr_field *);
464 expr_error_handle_common(struct expr_context *ctx)
467 /* Already have an error, suppress this one since the cascade seems
468 * unlikely to be useful. */
470 } else if (ctx->lexer->token.type == LEX_T_ERROR) {
471 /* The lexer signaled an error. Nothing at the expression level
472 * accepts an error token, so we'll inevitably end up here with some
473 * meaningless parse error. Report the lexical error instead. */
474 ctx->error = xstrdup(ctx->lexer->token.s);
481 static void OVS_PRINTF_FORMAT(2, 3)
482 expr_error(struct expr_context *ctx, const char *message, ...)
484 if (expr_error_handle_common(ctx)) {
489 va_start(args, message);
490 ctx->error = xvasprintf(message, args);
494 static void OVS_PRINTF_FORMAT(2, 3)
495 expr_syntax_error(struct expr_context *ctx, const char *message, ...)
497 if (expr_error_handle_common(ctx)) {
504 ds_put_cstr(&s, "Syntax error ");
505 if (ctx->lexer->token.type == LEX_T_END) {
506 ds_put_cstr(&s, "at end of input ");
507 } else if (ctx->lexer->start) {
508 ds_put_format(&s, "at `%.*s' ",
509 (int) (ctx->lexer->input - ctx->lexer->start),
514 va_start(args, message);
515 ds_put_format_valist(&s, message, args);
518 ctx->error = ds_steal_cstr(&s);
522 make_cmp__(const struct expr_field *f, enum expr_relop r,
523 const union expr_constant *c)
525 struct expr *e = xzalloc(sizeof *e);
526 e->type = EXPR_T_CMP;
527 e->cmp.symbol = f->symbol;
529 if (f->symbol->width) {
530 bitwise_copy(&c->value, sizeof c->value, 0,
531 &e->cmp.value, sizeof e->cmp.value, f->ofs,
534 bitwise_copy(&c->mask, sizeof c->mask, 0,
535 &e->cmp.mask, sizeof e->cmp.mask, f->ofs,
538 bitwise_one(&e->cmp.mask, sizeof e->cmp.mask, f->ofs,
542 e->cmp.string = xstrdup(c->string);
547 /* Returns the minimum reasonable width for integer constant 'c'. */
549 expr_constant_width(const union expr_constant *c)
552 return mf_subvalue_width(&c->mask);
557 case LEX_F_HEXADECIMAL:
558 return mf_subvalue_width(&c->value);
575 type_check(struct expr_context *ctx, const struct expr_field *f,
576 struct expr_constant_set *cs)
578 if (cs->type != (f->symbol->width ? EXPR_C_INTEGER : EXPR_C_STRING)) {
579 expr_error(ctx, "%s field %s is not compatible with %s constant.",
580 f->symbol->width ? "Integer" : "String",
582 cs->type == EXPR_C_INTEGER ? "integer" : "string");
586 if (f->symbol->width) {
587 for (size_t i = 0; i < cs->n_values; i++) {
588 int w = expr_constant_width(&cs->values[i]);
589 if (w > f->symbol->width) {
590 expr_error(ctx, "%d-bit constant is not compatible with "
592 w, f->symbol->width, f->symbol->name);
602 make_cmp(struct expr_context *ctx,
603 const struct expr_field *f, enum expr_relop r,
604 struct expr_constant_set *cs)
606 struct expr *e = NULL;
608 if (!type_check(ctx, f, cs)) {
612 if (r != EXPR_R_EQ && r != EXPR_R_NE) {
613 if (cs->in_curlies) {
614 expr_error(ctx, "Only == and != operators may be used "
618 if (f->symbol->level == EXPR_L_NOMINAL ||
619 f->symbol->level == EXPR_L_BOOLEAN) {
620 expr_error(ctx, "Only == and != operators may be used "
622 expr_level_to_string(f->symbol->level),
626 if (cs->values[0].masked) {
627 expr_error(ctx, "Only == and != operators may be used with "
628 "masked constants. Consider using subfields instead "
629 "(e.g. eth.src[0..15] > 0x1111 in place of "
630 "eth.src > 00:00:00:00:11:11/00:00:00:00:ff:ff).");
635 if (f->symbol->level == EXPR_L_NOMINAL) {
636 if (f->symbol->expansion) {
637 ovs_assert(f->symbol->width > 0);
638 for (size_t i = 0; i < cs->n_values; i++) {
639 const union mf_subvalue *value = &cs->values[i].value;
640 bool positive = (value->integer & htonll(1)) != 0;
641 positive ^= r == EXPR_R_NE;
642 positive ^= ctx->not;
644 const char *name = f->symbol->name;
645 expr_error(ctx, "Nominal predicate %s may only be tested "
646 "positively, e.g. `%s' or `%s == 1' but not "
647 "`!%s' or `%s == 0'.",
648 name, name, name, name, name);
652 } else if (r != (ctx->not ? EXPR_R_NE : EXPR_R_EQ)) {
653 expr_error(ctx, "Nominal field %s may only be tested for "
654 "equality (taking enclosing `!' operators into "
655 "account).", f->symbol->name);
660 e = make_cmp__(f, r, &cs->values[0]);
661 for (size_t i = 1; i < cs->n_values; i++) {
662 e = expr_combine(r == EXPR_R_EQ ? EXPR_T_OR : EXPR_T_AND,
663 e, make_cmp__(f, r, &cs->values[i]));
666 expr_constant_set_destroy(cs);
671 expr_get_int(struct expr_context *ctx, int *value)
673 bool ok = lexer_get_int(ctx->lexer, value);
675 expr_syntax_error(ctx, "expecting small integer.");
681 parse_field(struct expr_context *ctx, struct expr_field *f)
683 const struct expr_symbol *symbol;
685 if (ctx->lexer->token.type != LEX_T_ID) {
686 expr_syntax_error(ctx, "expecting field name.");
690 symbol = shash_find_data(ctx->symtab, ctx->lexer->token.s);
692 expr_syntax_error(ctx, "expecting field name.");
695 lexer_get(ctx->lexer);
698 if (lexer_match(ctx->lexer, LEX_T_LSQUARE)) {
701 if (!symbol->width) {
702 expr_error(ctx, "Cannot select subfield of string field %s.",
707 if (!expr_get_int(ctx, &low)) {
710 if (lexer_match(ctx->lexer, LEX_T_ELLIPSIS)) {
711 if (!expr_get_int(ctx, &high)) {
718 if (!lexer_match(ctx->lexer, LEX_T_RSQUARE)) {
719 expr_syntax_error(ctx, "expecting `]'.");
724 expr_error(ctx, "Invalid bit range %d to %d.", low, high);
726 } else if (high >= symbol->width) {
727 expr_error(ctx, "Cannot select bits %d to %d of %d-bit field %s.",
728 low, high, symbol->width, symbol->name);
730 } else if (symbol->level == EXPR_L_NOMINAL
731 && (low != 0 || high != symbol->width - 1)) {
732 expr_error(ctx, "Cannot select subfield of nominal field %s.",
738 f->n_bits = high - low + 1;
741 f->n_bits = symbol->width;
748 parse_relop(struct expr_context *ctx, enum expr_relop *relop)
750 if (expr_relop_from_token(ctx->lexer->token.type, relop)) {
751 lexer_get(ctx->lexer);
754 expr_syntax_error(ctx, "expecting relational operator.");
760 assign_constant_set_type(struct expr_context *ctx,
761 struct expr_constant_set *cs,
762 enum expr_constant_type type)
764 if (!cs->n_values || cs->type == type) {
768 expr_syntax_error(ctx, "expecting %s.",
769 cs->type == EXPR_C_INTEGER ? "integer" : "string");
775 parse_constant(struct expr_context *ctx, struct expr_constant_set *cs,
776 size_t *allocated_values)
778 if (cs->n_values >= *allocated_values) {
779 cs->values = x2nrealloc(cs->values, allocated_values,
783 if (ctx->lexer->token.type == LEX_T_STRING) {
784 if (!assign_constant_set_type(ctx, cs, EXPR_C_STRING)) {
787 cs->values[cs->n_values++].string = xstrdup(ctx->lexer->token.s);
788 lexer_get(ctx->lexer);
790 } else if (ctx->lexer->token.type == LEX_T_INTEGER ||
791 ctx->lexer->token.type == LEX_T_MASKED_INTEGER) {
792 if (!assign_constant_set_type(ctx, cs, EXPR_C_INTEGER)) {
796 union expr_constant *c = &cs->values[cs->n_values++];
797 c->value = ctx->lexer->token.value;
798 c->format = ctx->lexer->token.format;
799 c->masked = ctx->lexer->token.type == LEX_T_MASKED_INTEGER;
801 c->mask = ctx->lexer->token.mask;
803 lexer_get(ctx->lexer);
806 expr_syntax_error(ctx, "expecting constant.");
811 /* Parses a single or {}-enclosed set of integer or string constants into 'cs',
812 * which the caller need not have initialized. Returns true on success, in
813 * which case the caller owns 'cs', false on failure, in which case 'cs' is
816 parse_constant_set(struct expr_context *ctx, struct expr_constant_set *cs)
818 size_t allocated_values = 0;
821 memset(cs, 0, sizeof *cs);
822 if (lexer_match(ctx->lexer, LEX_T_LCURLY)) {
824 cs->in_curlies = true;
826 if (!parse_constant(ctx, cs, &allocated_values)) {
830 lexer_match(ctx->lexer, LEX_T_COMMA);
831 } while (!lexer_match(ctx->lexer, LEX_T_RCURLY));
833 ok = parse_constant(ctx, cs, &allocated_values);
836 expr_constant_set_destroy(cs);
842 expr_constant_set_destroy(struct expr_constant_set *cs)
845 if (cs->type == EXPR_C_STRING) {
846 for (size_t i = 0; i < cs->n_values; i++) {
847 free(cs->values[i].string);
855 expr_parse_primary(struct expr_context *ctx, bool *atomic)
858 if (lexer_match(ctx->lexer, LEX_T_LPAREN)) {
859 struct expr *e = expr_parse__(ctx);
860 if (!lexer_match(ctx->lexer, LEX_T_RPAREN)) {
862 expr_syntax_error(ctx, "expecting `)'.");
869 if (ctx->lexer->token.type == LEX_T_ID) {
872 struct expr_constant_set c;
874 if (!parse_field(ctx, &f)) {
878 if (!expr_relop_from_token(ctx->lexer->token.type, &r)) {
879 if (f.n_bits > 1 && !ctx->not) {
880 expr_error(ctx, "Explicit `!= 0' is required for inequality "
881 "test of multibit field against 0.");
887 union expr_constant *cst = xzalloc(sizeof *cst);
888 cst->format = LEX_F_HEXADECIMAL;
891 c.type = EXPR_C_INTEGER;
894 c.in_curlies = false;
895 return make_cmp(ctx, &f, EXPR_R_NE, &c);
896 } else if (parse_relop(ctx, &r) && parse_constant_set(ctx, &c)) {
897 return make_cmp(ctx, &f, r, &c);
902 struct expr_constant_set c1;
903 if (!parse_constant_set(ctx, &c1)) {
907 if (!expr_relop_from_token(ctx->lexer->token.type, NULL)
909 && c1.type == EXPR_C_INTEGER
910 && c1.values[0].format == LEX_F_DECIMAL
911 && !c1.values[0].masked
913 uint64_t x = ntohll(c1.values[0].value.integer);
916 expr_constant_set_destroy(&c1);
917 return expr_create_boolean(x);
923 if (!parse_relop(ctx, &r1) || !parse_field(ctx, &f)) {
924 expr_constant_set_destroy(&c1);
928 if (!expr_relop_from_token(ctx->lexer->token.type, NULL)) {
929 return make_cmp(ctx, &f, expr_relop_turn(r1), &c1);
933 struct expr_constant_set c2;
934 if (!parse_relop(ctx, &r2) || !parse_constant_set(ctx, &c2)) {
935 expr_constant_set_destroy(&c1);
938 /* Reject "1 == field == 2", "1 < field > 2", and so on. */
939 if (!(((r1 == EXPR_R_LT || r1 == EXPR_R_LE) &&
940 (r2 == EXPR_R_LT || r2 == EXPR_R_LE)) ||
941 ((r1 == EXPR_R_GT || r1 == EXPR_R_GE) &&
942 (r2 == EXPR_R_GT || r2 == EXPR_R_GE)))) {
943 expr_error(ctx, "Range expressions must have the form "
944 "`x < field < y' or `x > field > y', with each "
945 "`<' optionally replaced by `<=' or `>' by `>=').");
946 expr_constant_set_destroy(&c1);
947 expr_constant_set_destroy(&c2);
951 struct expr *e1 = make_cmp(ctx, &f, expr_relop_turn(r1), &c1);
952 struct expr *e2 = make_cmp(ctx, &f, r2, &c2);
958 return expr_combine(EXPR_T_AND, e1, e2);
964 expr_parse_not(struct expr_context *ctx)
968 if (lexer_match(ctx->lexer, LEX_T_LOG_NOT)) {
969 ctx->not = !ctx->not;
970 struct expr *expr = expr_parse_primary(ctx, &atomic);
971 ctx->not = !ctx->not;
975 expr_error(ctx, "Missing parentheses around operand of !.");
983 return expr_parse_primary(ctx, &atomic);
988 expr_parse__(struct expr_context *ctx)
990 struct expr *e = expr_parse_not(ctx);
995 enum lex_type lex_type = ctx->lexer->token.type;
996 if (lex_type == LEX_T_LOG_AND || lex_type == LEX_T_LOG_OR) {
997 enum expr_type expr_type
998 = lex_type == LEX_T_LOG_AND ? EXPR_T_AND : EXPR_T_OR;
1000 lexer_get(ctx->lexer);
1002 struct expr *e2 = expr_parse_not(ctx);
1007 e = expr_combine(expr_type, e, e2);
1008 } while (lexer_match(ctx->lexer, lex_type));
1009 if (ctx->lexer->token.type == LEX_T_LOG_AND
1010 || ctx->lexer->token.type == LEX_T_LOG_OR) {
1013 "&& and || must be parenthesized when used together.");
1020 /* Parses an expression using the symbols in 'symtab' from 'lexer'. If
1021 * successful, returns the new expression and sets '*errorp' to NULL. On
1022 * failure, returns NULL and sets '*errorp' to an explanatory error message.
1023 * The caller must eventually free the returned expression (with
1024 * expr_destroy()) or error (with free()). */
1026 expr_parse(struct lexer *lexer, const struct shash *symtab, char **errorp)
1028 struct expr_context ctx;
1031 ctx.symtab = symtab;
1035 struct expr *e = expr_parse__(&ctx);
1036 *errorp = ctx.error;
1037 ovs_assert((ctx.error != NULL) != (e != NULL));
1041 /* Like expr_parse(), but the expression is taken from 's'. */
1043 expr_parse_string(const char *s, const struct shash *symtab, char **errorp)
1048 lexer_init(&lexer, s);
1050 expr = expr_parse(&lexer, symtab, errorp);
1051 if (!*errorp && lexer.token.type != LEX_T_END) {
1052 *errorp = xstrdup("Extra tokens at end of input.");
1056 lexer_destroy(&lexer);
1061 static struct expr_symbol *
1062 add_symbol(struct shash *symtab, const char *name, int width,
1063 const char *prereqs, enum expr_level level,
1064 bool must_crossproduct)
1066 struct expr_symbol *symbol = xzalloc(sizeof *symbol);
1067 symbol->name = xstrdup(name);
1068 symbol->prereqs = prereqs && prereqs[0] ? xstrdup(prereqs) : NULL;
1069 symbol->width = width;
1070 symbol->level = level;
1071 symbol->must_crossproduct = must_crossproduct;
1072 shash_add_assert(symtab, symbol->name, symbol);
1076 /* Adds field 'id' to symbol table 'symtab' under the given 'name'. Whenever
1077 * 'name' is referenced, expression annotation (see expr_annotate()) will
1078 * ensure that 'prereqs' are also true. If 'must_crossproduct' is true, then
1079 * conversion to flows will never attempt to use the field as a conjunctive
1080 * match dimension (see "Crossproducting" in the large comment on struct
1081 * expr_symbol in expr.h for an example).
1083 * A given field 'id' must only be used for a single symbol in a symbol table.
1084 * Use subfields to duplicate or subset a field (you can even make a subfield
1085 * include all the bits of the "parent" field if you like). */
1086 struct expr_symbol *
1087 expr_symtab_add_field(struct shash *symtab, const char *name,
1088 enum mf_field_id id, const char *prereqs,
1089 bool must_crossproduct)
1091 const struct mf_field *field = mf_from_id(id);
1092 struct expr_symbol *symbol;
1094 symbol = add_symbol(symtab, name, field->n_bits, prereqs,
1095 (field->maskable == MFM_FULLY
1099 symbol->field = field;
1104 parse_field_from_string(const char *s, const struct shash *symtab,
1105 struct expr_field *field, char **errorp)
1108 lexer_init(&lexer, s);
1111 struct expr_context ctx;
1113 ctx.symtab = symtab;
1117 bool ok = parse_field(&ctx, field);
1119 *errorp = ctx.error;
1120 } else if (lexer.token.type != LEX_T_END) {
1121 *errorp = xstrdup("Extra tokens at end of input.");
1125 lexer_destroy(&lexer);
1130 /* Adds 'name' as a subfield of a larger field in 'symtab'. Whenever
1131 * 'name' is referenced, expression annotation (see expr_annotate()) will
1132 * ensure that 'prereqs' are also true.
1134 * 'subfield' must describe the subfield as a string, e.g. "vlan.tci[0..11]"
1135 * for the low 12 bits of a larger field named "vlan.tci". */
1136 struct expr_symbol *
1137 expr_symtab_add_subfield(struct shash *symtab, const char *name,
1138 const char *prereqs, const char *subfield)
1140 struct expr_symbol *symbol;
1141 struct expr_field f;
1144 if (!parse_field_from_string(subfield, symtab, &f, &error)) {
1145 VLOG_WARN("%s: error parsing %s subfield (%s)", subfield, name, error);
1150 enum expr_level level = f.symbol->level;
1151 if (level != EXPR_L_ORDINAL) {
1152 VLOG_WARN("can't define %s as subfield of %s field %s",
1153 name, expr_level_to_string(level), f.symbol->name);
1156 symbol = add_symbol(symtab, name, f.n_bits, prereqs, level, false);
1157 symbol->expansion = xstrdup(subfield);
1161 /* Adds a string-valued symbol named 'name' to 'symtab' with the specified
1163 struct expr_symbol *
1164 expr_symtab_add_string(struct shash *symtab, const char *name,
1165 enum mf_field_id id, const char *prereqs)
1167 const struct mf_field *field = mf_from_id(id);
1168 struct expr_symbol *symbol;
1170 symbol = add_symbol(symtab, name, 0, prereqs, EXPR_L_NOMINAL, false);
1171 symbol->field = field;
1175 static enum expr_level
1176 expr_get_level(const struct expr *expr)
1178 const struct expr *sub;
1179 enum expr_level level = EXPR_L_ORDINAL;
1181 switch (expr->type) {
1183 return (expr->cmp.symbol->level == EXPR_L_NOMINAL
1189 LIST_FOR_EACH (sub, node, &expr->andor) {
1190 enum expr_level sub_level = expr_get_level(sub);
1191 level = MIN(level, sub_level);
1195 case EXPR_T_BOOLEAN:
1196 return EXPR_L_BOOLEAN;
1203 static enum expr_level
1204 expr_parse_level(const char *s, const struct shash *symtab, char **errorp)
1206 struct expr *expr = expr_parse_string(s, symtab, errorp);
1207 enum expr_level level = expr ? expr_get_level(expr) : EXPR_L_NOMINAL;
1212 /* Adds a predicate symbol, whose value is the given Boolean 'expression',
1213 * named 'name' to 'symtab'. For example, "ip4 && ip4.proto == 6" might be an
1214 * appropriate predicate named "tcp4". */
1215 struct expr_symbol *
1216 expr_symtab_add_predicate(struct shash *symtab, const char *name,
1217 const char *expansion)
1219 struct expr_symbol *symbol;
1220 enum expr_level level;
1223 level = expr_parse_level(expansion, symtab, &error);
1225 VLOG_WARN("%s: error parsing %s expansion (%s)",
1226 expansion, name, error);
1231 symbol = add_symbol(symtab, name, 1, NULL, level, false);
1232 symbol->expansion = xstrdup(expansion);
1236 /* Destroys 'symtab' and all of its symbols. */
1238 expr_symtab_destroy(struct shash *symtab)
1240 struct shash_node *node, *next;
1242 SHASH_FOR_EACH_SAFE (node, next, symtab) {
1243 struct expr_symbol *symbol = node->data;
1245 shash_delete(symtab, node);
1247 free(symbol->prereqs);
1248 free(symbol->expansion);
1255 static struct expr *
1256 expr_clone_cmp(struct expr *expr)
1258 struct expr *new = xmemdup(expr, sizeof *expr);
1259 if (!new->cmp.symbol->width) {
1260 new->cmp.string = xstrdup(new->cmp.string);
1265 static struct expr *
1266 expr_clone_andor(struct expr *expr)
1268 struct expr *new = expr_create_andor(expr->type);
1271 LIST_FOR_EACH (sub, node, &expr->andor) {
1272 struct expr *new_sub = expr_clone(sub);
1273 ovs_list_push_back(&new->andor, &new_sub->node);
1278 /* Returns a clone of 'expr'. This is a "deep copy": neither the returned
1279 * expression nor any of its substructure will be shared with 'expr'. */
1281 expr_clone(struct expr *expr)
1283 switch (expr->type) {
1285 return expr_clone_cmp(expr);
1289 return expr_clone_andor(expr);
1291 case EXPR_T_BOOLEAN:
1292 return expr_create_boolean(expr->boolean);
1297 /* Destroys 'expr' and all of the sub-expressions it references. */
1299 expr_destroy(struct expr *expr)
1305 struct expr *sub, *next;
1307 switch (expr->type) {
1309 if (!expr->cmp.symbol->width) {
1310 free(expr->cmp.string);
1316 LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
1317 ovs_list_remove(&sub->node);
1322 case EXPR_T_BOOLEAN:
1330 /* An element in a linked list of symbols.
1332 * Used to detect when a symbol is being expanded recursively, to allow
1333 * flagging an error. */
1334 struct annotation_nesting {
1335 struct ovs_list node;
1336 const struct expr_symbol *symbol;
1339 struct expr *expr_annotate__(struct expr *, const struct shash *symtab,
1340 struct ovs_list *nesting, char **errorp);
1342 static struct expr *
1343 parse_and_annotate(const char *s, const struct shash *symtab,
1344 struct ovs_list *nesting, char **errorp)
1349 expr = expr_parse_string(s, symtab, &error);
1351 expr = expr_annotate__(expr, symtab, nesting, &error);
1356 *errorp = xasprintf("Error parsing expression `%s' encountered as "
1357 "prerequisite or predicate of initial expression: "
1364 static struct expr *
1365 expr_annotate_cmp(struct expr *expr, const struct shash *symtab,
1366 struct ovs_list *nesting, char **errorp)
1368 const struct expr_symbol *symbol = expr->cmp.symbol;
1369 const struct annotation_nesting *iter;
1370 LIST_FOR_EACH (iter, node, nesting) {
1371 if (iter->symbol == symbol) {
1372 *errorp = xasprintf("Recursive expansion of symbol `%s'.",
1379 struct annotation_nesting an;
1381 ovs_list_push_back(nesting, &an.node);
1383 struct expr *prereqs = NULL;
1384 if (symbol->prereqs) {
1385 prereqs = parse_and_annotate(symbol->prereqs, symtab, nesting, errorp);
1391 if (symbol->expansion) {
1392 if (symbol->level == EXPR_L_ORDINAL) {
1393 struct expr_field field;
1395 if (!parse_field_from_string(symbol->expansion, symtab,
1400 expr->cmp.symbol = field.symbol;
1401 mf_subvalue_shift(&expr->cmp.value, field.ofs);
1402 mf_subvalue_shift(&expr->cmp.mask, field.ofs);
1404 struct expr *expansion;
1406 expansion = parse_and_annotate(symbol->expansion, symtab,
1412 bool positive = (expr->cmp.value.integer & htonll(1)) != 0;
1413 positive ^= expr->cmp.relop == EXPR_R_NE;
1415 expr_not(expansion);
1423 ovs_list_remove(&an.node);
1424 return prereqs ? expr_combine(EXPR_T_AND, expr, prereqs) : expr;
1428 expr_destroy(prereqs);
1429 ovs_list_remove(&an.node);
1434 expr_annotate__(struct expr *expr, const struct shash *symtab,
1435 struct ovs_list *nesting, char **errorp)
1437 switch (expr->type) {
1439 return expr_annotate_cmp(expr, symtab, nesting, errorp);
1443 struct expr *sub, *next;
1445 LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
1446 ovs_list_remove(&sub->node);
1447 struct expr *new_sub = expr_annotate__(sub, symtab,
1453 expr_insert_andor(expr, next, new_sub);
1459 case EXPR_T_BOOLEAN:
1468 /* "Annotates" 'expr', which does the following:
1470 * - Applies prerequisites, by locating each comparison operator whose
1471 * field has a prerequisite and adding a logical AND against those
1474 * - Expands references to subfield symbols, by replacing them by
1475 * references to their underlying field symbols (suitably shifted).
1477 * - Expands references to predicate symbols, by replacing them by the
1478 * expressions that they expand to.
1480 * In each case, annotation occurs recursively as necessary.
1482 * On failure, returns NULL and sets '*errorp' to an explanatory error
1483 * message, which the caller must free. */
1485 expr_annotate(struct expr *expr, const struct shash *symtab, char **errorp)
1487 struct ovs_list nesting = OVS_LIST_INITIALIZER(&nesting);
1488 return expr_annotate__(expr, symtab, &nesting, errorp);
1491 static struct expr *
1492 expr_simplify_ne(struct expr *expr)
1494 struct expr *new = NULL;
1495 const union mf_subvalue *value = &expr->cmp.value;
1496 const union mf_subvalue *mask = &expr->cmp.mask;
1497 int w = expr->cmp.symbol->width;
1500 for (i = 0; (i = bitwise_scan(mask, sizeof *mask, true, i, w)) < w; i++) {
1503 e = xzalloc(sizeof *e);
1504 e->type = EXPR_T_CMP;
1505 e->cmp.symbol = expr->cmp.symbol;
1506 e->cmp.relop = EXPR_R_EQ;
1507 bitwise_put_bit(&e->cmp.value, sizeof e->cmp.value, i,
1508 !bitwise_get_bit(value, sizeof *value, i));
1509 bitwise_put1(&e->cmp.mask, sizeof e->cmp.mask, i);
1511 new = expr_combine(EXPR_T_OR, new, e);
1520 static struct expr *
1521 expr_simplify_relational(struct expr *expr)
1523 const union mf_subvalue *value = &expr->cmp.value;
1524 int start, n_bits, end;
1526 find_bitwise_range(&expr->cmp.mask, expr->cmp.symbol->width,
1528 ovs_assert(n_bits > 0);
1529 end = start + n_bits;
1532 if (expr->cmp.relop == EXPR_R_LE || expr->cmp.relop == EXPR_R_GE) {
1533 new = xmemdup(expr, sizeof *expr);
1534 new->cmp.relop = EXPR_R_EQ;
1539 bool b = expr->cmp.relop == EXPR_R_LT || expr->cmp.relop == EXPR_R_LE;
1540 for (int z = bitwise_scan(value, sizeof *value, b, start, end);
1542 z = bitwise_scan(value, sizeof *value, b, z + 1, end)) {
1545 e = xmemdup(expr, sizeof *expr);
1546 e->cmp.relop = EXPR_R_EQ;
1547 bitwise_toggle_bit(&e->cmp.value, sizeof e->cmp.value, z);
1548 bitwise_zero(&e->cmp.value, sizeof e->cmp.value, start, z - start);
1549 bitwise_zero(&e->cmp.mask, sizeof e->cmp.mask, start, z - start);
1550 new = expr_combine(EXPR_T_OR, new, e);
1553 return new ? new : expr_create_boolean(false);
1556 /* Takes ownership of 'expr' and returns an equivalent expression whose
1557 * EXPR_T_CMP nodes use only tests for equality (EXPR_R_EQ). */
1559 expr_simplify(struct expr *expr)
1561 struct expr *sub, *next;
1563 switch (expr->type) {
1565 return (expr->cmp.relop == EXPR_R_EQ || !expr->cmp.symbol->width ? expr
1566 : expr->cmp.relop == EXPR_R_NE ? expr_simplify_ne(expr)
1567 : expr_simplify_relational(expr));
1571 LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
1572 ovs_list_remove(&sub->node);
1573 expr_insert_andor(expr, next, expr_simplify(sub));
1575 return expr_fix(expr);
1577 case EXPR_T_BOOLEAN:
1583 static const struct expr_symbol *
1584 expr_is_cmp(const struct expr *expr)
1586 switch (expr->type) {
1588 return expr->cmp.symbol;
1592 const struct expr_symbol *prev = NULL;
1595 LIST_FOR_EACH (sub, node, &expr->andor) {
1596 const struct expr_symbol *symbol = expr_is_cmp(sub);
1597 if (!symbol || (prev && symbol != prev)) {
1605 case EXPR_T_BOOLEAN:
1615 const struct expr_symbol *relop;
1616 enum expr_type type;
1620 compare_expr_sort(const void *a_, const void *b_)
1622 const struct expr_sort *a = a_;
1623 const struct expr_sort *b = b_;
1625 if (a->type != b->type) {
1626 return a->type < b->type ? -1 : 1;
1627 } else if (a->relop) {
1628 int cmp = strcmp(a->relop->name, b->relop->name);
1633 enum expr_type a_type = a->expr->type;
1634 enum expr_type b_type = a->expr->type;
1635 return a_type < b_type ? -1 : a_type > b_type;
1636 } else if (a->type == EXPR_T_AND || a->type == EXPR_T_OR) {
1637 size_t a_len = ovs_list_size(&a->expr->andor);
1638 size_t b_len = ovs_list_size(&b->expr->andor);
1639 return a_len < b_len ? -1 : a_len > b_len;
1645 static struct expr *crush_cmps(struct expr *, const struct expr_symbol *);
1648 disjunction_matches_string(const struct expr *or, const char *s)
1650 const struct expr *sub;
1652 LIST_FOR_EACH (sub, node, &or->andor) {
1653 if (!strcmp(sub->cmp.string, s)) {
1661 /* Implementation of crush_cmps() for expr->type == EXPR_T_AND and a
1662 * string-typed 'symbol'. */
1663 static struct expr *
1664 crush_and_string(struct expr *expr, const struct expr_symbol *symbol)
1666 ovs_assert(!ovs_list_is_short(&expr->andor));
1668 struct expr *singleton = NULL;
1670 /* First crush each subexpression into either a single EXPR_T_CMP or an
1671 * EXPR_T_OR with EXPR_T_CMP subexpressions. */
1672 struct expr *sub, *next = NULL;
1673 LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
1674 ovs_list_remove(&sub->node);
1675 struct expr *new = crush_cmps(sub, symbol);
1676 switch (new->type) {
1679 ovs_list_insert(&next->node, &new->node);
1682 bool match = !strcmp(new->cmp.string, singleton->cmp.string);
1686 return expr_create_boolean(false);
1693 ovs_list_insert(&next->node, &new->node);
1695 case EXPR_T_BOOLEAN:
1696 if (!new->boolean) {
1705 /* If we have a singleton, then the result is either the singleton itself
1706 * (if the ORs allow the singleton) or false. */
1708 LIST_FOR_EACH (sub, node, &expr->andor) {
1709 if (sub->type == EXPR_T_OR
1710 && !disjunction_matches_string(sub, singleton->cmp.string)) {
1712 return expr_create_boolean(false);
1715 ovs_list_remove(&singleton->node);
1720 /* Otherwise the result is the intersection of all of the ORs. */
1721 struct sset result = SSET_INITIALIZER(&result);
1722 LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
1723 struct sset strings = SSET_INITIALIZER(&strings);
1724 const struct expr *s;
1725 LIST_FOR_EACH (s, node, &sub->andor) {
1726 sset_add(&strings, s->cmp.string);
1728 if (sset_is_empty(&result)) {
1729 sset_swap(&result, &strings);
1731 sset_intersect(&result, &strings);
1733 sset_destroy(&strings);
1735 if (sset_is_empty(&result)) {
1737 sset_destroy(&result);
1738 return expr_create_boolean(false);
1743 expr = expr_create_andor(EXPR_T_OR);
1746 SSET_FOR_EACH (string, &result) {
1747 sub = xmalloc(sizeof *sub);
1748 sub->type = EXPR_T_CMP;
1749 sub->cmp.symbol = symbol;
1750 sub->cmp.string = xstrdup(string);
1751 ovs_list_push_back(&expr->andor, &sub->node);
1753 sset_destroy(&result);
1754 return expr_fix(expr);
1757 /* Implementation of crush_cmps() for expr->type == EXPR_T_AND and a
1758 * numeric-typed 'symbol'. */
1759 static struct expr *
1760 crush_and_numeric(struct expr *expr, const struct expr_symbol *symbol)
1762 ovs_assert(!ovs_list_is_short(&expr->andor));
1764 union mf_subvalue value, mask;
1765 memset(&value, 0, sizeof value);
1766 memset(&mask, 0, sizeof mask);
1768 struct expr *sub, *next = NULL;
1769 LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
1770 ovs_list_remove(&sub->node);
1771 struct expr *new = crush_cmps(sub, symbol);
1772 switch (new->type) {
1774 if (!mf_subvalue_intersect(&value, &mask,
1775 &new->cmp.value, &new->cmp.mask,
1779 return expr_create_boolean(false);
1786 ovs_list_insert(&next->node, &new->node);
1788 case EXPR_T_BOOLEAN:
1789 if (!new->boolean) {
1797 if (ovs_list_is_empty(&expr->andor)) {
1798 if (is_all_zeros(&mask, sizeof mask)) {
1800 return expr_create_boolean(true);
1803 cmp = xmalloc(sizeof *cmp);
1804 cmp->type = EXPR_T_CMP;
1805 cmp->cmp.symbol = symbol;
1806 cmp->cmp.relop = EXPR_R_EQ;
1807 cmp->cmp.value = value;
1808 cmp->cmp.mask = mask;
1812 } else if (ovs_list_is_short(&expr->andor)) {
1813 /* Transform "a && (b || c || d)" into "ab || ac || ad" where "ab" is
1814 * computed as "a && b", etc. */
1815 struct expr *disjuncts = expr_from_node(ovs_list_pop_front(&expr->andor));
1818 or = xmalloc(sizeof *or);
1819 or->type = EXPR_T_OR;
1820 ovs_list_init(&or->andor);
1822 ovs_assert(disjuncts->type == EXPR_T_OR);
1823 LIST_FOR_EACH_SAFE (sub, next, node, &disjuncts->andor) {
1824 ovs_assert(sub->type == EXPR_T_CMP);
1825 ovs_list_remove(&sub->node);
1826 if (mf_subvalue_intersect(&value, &mask,
1827 &sub->cmp.value, &sub->cmp.mask,
1828 &sub->cmp.value, &sub->cmp.mask)) {
1829 ovs_list_push_back(&or->andor, &sub->node);
1836 if (ovs_list_is_empty(&or->andor)) {
1838 return expr_create_boolean(false);
1839 } else if (ovs_list_is_short(&or->andor)) {
1840 struct expr *cmp = expr_from_node(ovs_list_pop_front(&or->andor));
1847 /* Transform "x && (a0 || a1) && (b0 || b1) && ..." into
1848 * "(xa0b0 || xa0b1 || xa1b0 || xa1b1) && ...". */
1849 struct expr *as = expr_from_node(ovs_list_pop_front(&expr->andor));
1850 struct expr *bs = expr_from_node(ovs_list_pop_front(&expr->andor));
1851 struct expr *new = NULL;
1854 or = xmalloc(sizeof *or);
1855 or->type = EXPR_T_OR;
1856 ovs_list_init(&or->andor);
1859 LIST_FOR_EACH (a, node, &as->andor) {
1860 union mf_subvalue a_value, a_mask;
1862 ovs_assert(a->type == EXPR_T_CMP);
1863 if (!mf_subvalue_intersect(&value, &mask,
1864 &a->cmp.value, &a->cmp.mask,
1865 &a_value, &a_mask)) {
1870 LIST_FOR_EACH (b, node, &bs->andor) {
1871 ovs_assert(b->type == EXPR_T_CMP);
1873 new = xmalloc(sizeof *new);
1874 new->type = EXPR_T_CMP;
1875 new->cmp.symbol = symbol;
1876 new->cmp.relop = EXPR_R_EQ;
1878 if (mf_subvalue_intersect(&a_value, &a_mask,
1879 &b->cmp.value, &b->cmp.mask,
1880 &new->cmp.value, &new->cmp.mask)) {
1881 ovs_list_push_back(&or->andor, &new->node);
1890 if (ovs_list_is_empty(&or->andor)) {
1893 return expr_create_boolean(false);
1894 } else if (ovs_list_is_short(&or->andor)) {
1895 struct expr *cmp = expr_from_node(ovs_list_pop_front(&or->andor));
1897 if (ovs_list_is_empty(&expr->andor)) {
1899 return crush_cmps(cmp, symbol);
1901 return crush_cmps(expr_combine(EXPR_T_AND, cmp, expr), symbol);
1903 } else if (!ovs_list_is_empty(&expr->andor)) {
1904 struct expr *e = expr_combine(EXPR_T_AND, or, expr);
1905 ovs_assert(!ovs_list_is_short(&e->andor));
1906 return crush_cmps(e, symbol);
1909 return crush_cmps(or, symbol);
1915 compare_cmps_3way(const struct expr *a, const struct expr *b)
1917 ovs_assert(a->cmp.symbol == b->cmp.symbol);
1918 if (!a->cmp.symbol->width) {
1919 return strcmp(a->cmp.string, b->cmp.string);
1921 int d = memcmp(&a->cmp.value, &b->cmp.value, sizeof a->cmp.value);
1923 d = memcmp(&a->cmp.mask, &b->cmp.mask, sizeof a->cmp.mask);
1930 compare_cmps_cb(const void *a_, const void *b_)
1932 const struct expr *const *ap = a_;
1933 const struct expr *const *bp = b_;
1934 const struct expr *a = *ap;
1935 const struct expr *b = *bp;
1936 return compare_cmps_3way(a, b);
1939 /* Implementation of crush_cmps() for expr->type == EXPR_T_OR. */
1940 static struct expr *
1941 crush_or(struct expr *expr, const struct expr_symbol *symbol)
1943 struct expr *sub, *next = NULL;
1945 /* First, crush all the subexpressions. That might eliminate the
1946 * OR-expression entirely; if so, return the result. Otherwise, 'expr'
1947 * is now a disjunction of cmps over the same symbol. */
1948 LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
1949 ovs_list_remove(&sub->node);
1950 expr_insert_andor(expr, next, crush_cmps(sub, symbol));
1952 expr = expr_fix(expr);
1953 if (expr->type != EXPR_T_OR) {
1957 /* Sort subexpressions by value and mask, to bring together duplicates. */
1958 size_t n = ovs_list_size(&expr->andor);
1959 struct expr **subs = xmalloc(n * sizeof *subs);
1962 LIST_FOR_EACH (sub, node, &expr->andor) {
1967 qsort(subs, n, sizeof *subs, compare_cmps_cb);
1969 /* Eliminate duplicates. */
1970 ovs_list_init(&expr->andor);
1971 ovs_list_push_back(&expr->andor, &subs[0]->node);
1972 for (i = 1; i < n; i++) {
1973 struct expr *a = expr_from_node(ovs_list_back(&expr->andor));
1974 struct expr *b = subs[i];
1975 if (compare_cmps_3way(a, b)) {
1976 ovs_list_push_back(&expr->andor, &b->node);
1982 return expr_fix(expr);
1985 /* Takes ownership of 'expr', which must be a cmp in the sense determined by
1986 * 'expr_is_cmp(expr)', where 'symbol' is the symbol returned by that function.
1987 * Returns an equivalent expression owned by the caller that is a single
1988 * EXPR_T_CMP or a disjunction of them or a EXPR_T_BOOLEAN. */
1989 static struct expr *
1990 crush_cmps(struct expr *expr, const struct expr_symbol *symbol)
1992 switch (expr->type) {
1994 return crush_or(expr, symbol);
1997 return (symbol->width
1998 ? crush_and_numeric(expr, symbol)
1999 : crush_and_string(expr, symbol));
2004 case EXPR_T_BOOLEAN:
2012 static struct expr *
2013 expr_sort(struct expr *expr)
2015 size_t n = ovs_list_size(&expr->andor);
2016 struct expr_sort *subs = xmalloc(n * sizeof *subs);
2021 LIST_FOR_EACH (sub, node, &expr->andor) {
2023 subs[i].relop = expr_is_cmp(sub);
2024 subs[i].type = subs[i].relop ? EXPR_T_CMP : sub->type;
2029 qsort(subs, n, sizeof *subs, compare_expr_sort);
2031 ovs_list_init(&expr->andor);
2032 for (int i = 0; i < n; ) {
2033 if (subs[i].relop) {
2035 for (j = i + 1; j < n; j++) {
2036 if (subs[i].relop != subs[j].relop) {
2041 struct expr *crushed;
2043 crushed = crush_cmps(subs[i].expr, subs[i].relop);
2045 struct expr *combined = subs[i].expr;
2046 for (int k = i + 1; k < j; k++) {
2047 combined = expr_combine(EXPR_T_AND, combined,
2050 ovs_assert(!ovs_list_is_short(&combined->andor));
2051 crushed = crush_cmps(combined, subs[i].relop);
2053 if (crushed->type == EXPR_T_BOOLEAN) {
2054 if (!crushed->boolean) {
2055 for (int k = j; k < n; k++) {
2056 expr_destroy(subs[k].expr);
2065 expr = expr_combine(EXPR_T_AND, expr, crushed);
2069 expr = expr_combine(EXPR_T_AND, expr, subs[i++].expr);
2077 static struct expr *expr_normalize_or(struct expr *expr);
2079 /* Returns 'expr', which is an AND, reduced to OR(AND(clause)) where
2080 * a clause is a cmp or a disjunction of cmps on a single field. */
2081 static struct expr *
2082 expr_normalize_and(struct expr *expr)
2084 ovs_assert(expr->type == EXPR_T_AND);
2086 expr = expr_sort(expr);
2087 if (expr->type != EXPR_T_AND) {
2088 ovs_assert(expr->type == EXPR_T_BOOLEAN);
2093 LIST_FOR_EACH_SAFE (a, b, node, &expr->andor) {
2094 if (&b->node == &expr->andor
2095 || a->type != EXPR_T_CMP || b->type != EXPR_T_CMP
2096 || a->cmp.symbol != b->cmp.symbol) {
2098 } else if (a->cmp.symbol->width
2099 ? mf_subvalue_intersect(&a->cmp.value, &a->cmp.mask,
2100 &b->cmp.value, &b->cmp.mask,
2101 &b->cmp.value, &b->cmp.mask)
2102 : !strcmp(a->cmp.string, b->cmp.string)) {
2103 ovs_list_remove(&a->node);
2107 return expr_create_boolean(false);
2110 if (ovs_list_is_short(&expr->andor)) {
2111 struct expr *sub = expr_from_node(ovs_list_front(&expr->andor));
2117 LIST_FOR_EACH (sub, node, &expr->andor) {
2118 if (sub->type == EXPR_T_CMP) {
2122 ovs_assert(sub->type == EXPR_T_OR);
2123 const struct expr_symbol *symbol = expr_is_cmp(sub);
2124 if (!symbol || symbol->must_crossproduct) {
2125 struct expr *or = expr_create_andor(EXPR_T_OR);
2128 LIST_FOR_EACH (k, node, &sub->andor) {
2129 struct expr *and = expr_create_andor(EXPR_T_AND);
2132 LIST_FOR_EACH (m, node, &expr->andor) {
2133 struct expr *term = m == sub ? k : m;
2134 if (term->type == EXPR_T_AND) {
2137 LIST_FOR_EACH (p, node, &term->andor) {
2138 struct expr *new = expr_clone(p);
2139 ovs_list_push_back(&and->andor, &new->node);
2142 struct expr *new = expr_clone(term);
2143 ovs_list_push_back(&and->andor, &new->node);
2146 ovs_list_push_back(&or->andor, &and->node);
2149 return expr_normalize_or(or);
2155 static struct expr *
2156 expr_normalize_or(struct expr *expr)
2158 struct expr *sub, *next;
2160 LIST_FOR_EACH_SAFE (sub, next, node, &expr->andor) {
2161 if (sub->type == EXPR_T_AND) {
2162 ovs_list_remove(&sub->node);
2164 struct expr *new = expr_normalize_and(sub);
2165 if (new->type == EXPR_T_BOOLEAN) {
2172 expr_insert_andor(expr, next, new);
2175 ovs_assert(sub->type == EXPR_T_CMP);
2178 if (ovs_list_is_empty(&expr->andor)) {
2180 return expr_create_boolean(false);
2182 if (ovs_list_is_short(&expr->andor)) {
2183 struct expr *sub = expr_from_node(ovs_list_pop_front(&expr->andor));
2191 /* Takes ownership of 'expr', which is either a constant "true" or "false" or
2192 * an expression in terms of only relationals, AND, and OR. Returns either a
2193 * constant "true" or "false" or 'expr' reduced to OR(AND(clause)) where a
2194 * clause is a cmp or a disjunction of cmps on a single field. This form is
2195 * significant because it is a form that can be directly converted to OpenFlow
2196 * flows with the Open vSwitch "conjunctive match" extension.
2198 * 'expr' must already have been simplified, with expr_simplify(). */
2200 expr_normalize(struct expr *expr)
2202 switch (expr->type) {
2207 return expr_normalize_and(expr);
2210 return expr_normalize_or(expr);
2212 case EXPR_T_BOOLEAN:
2218 /* Creates, initializes, and returns a new 'struct expr_match'. If 'm' is
2219 * nonnull then it is copied into the new expr_match, otherwise the new
2220 * expr_match's 'match' member is initialized to a catch-all match for the
2221 * caller to refine in-place.
2223 * If 'conj_id' is nonzero, adds one conjunction based on 'conj_id', 'clause',
2224 * and 'n_clauses' to the returned 'struct expr_match', otherwise the
2225 * expr_match will not have any conjunctions.
2227 * The caller should use expr_match_add() to add the expr_match to a hash table
2228 * after it is finalized. */
2229 static struct expr_match *
2230 expr_match_new(const struct match *m, uint8_t clause, uint8_t n_clauses,
2233 struct expr_match *match = xmalloc(sizeof *match);
2237 match_init_catchall(&match->match);
2240 match->conjunctions = xmalloc(sizeof *match->conjunctions);
2241 match->conjunctions[0].id = conj_id;
2242 match->conjunctions[0].clause = clause;
2243 match->conjunctions[0].n_clauses = n_clauses;
2245 match->allocated = 1;
2247 match->conjunctions = NULL;
2249 match->allocated = 0;
2254 /* Adds 'match' to hash table 'matches', which becomes the new owner of
2257 * This might actually destroy 'match' because it gets merged together with
2258 * some existing conjunction.*/
2260 expr_match_add(struct hmap *matches, struct expr_match *match)
2262 uint32_t hash = match_hash(&match->match, 0);
2263 struct expr_match *m;
2265 HMAP_FOR_EACH_WITH_HASH (m, hmap_node, hash, matches) {
2266 if (match_equal(&m->match, &match->match)) {
2267 if (!m->n || !match->n) {
2268 free(m->conjunctions);
2269 m->conjunctions = NULL;
2273 ovs_assert(match->n == 1);
2274 if (m->n >= m->allocated) {
2275 m->conjunctions = x2nrealloc(m->conjunctions,
2277 sizeof *m->conjunctions);
2279 m->conjunctions[m->n++] = match->conjunctions[0];
2281 free(match->conjunctions);
2287 hmap_insert(matches, &match->hmap_node, hash);
2291 constrain_match(const struct expr *expr,
2292 bool (*lookup_port)(const void *aux, const char *port_name,
2293 unsigned int *portp),
2294 const void *aux, struct match *m)
2296 ovs_assert(expr->type == EXPR_T_CMP);
2297 if (expr->cmp.symbol->width) {
2298 mf_mask_subfield(expr->cmp.symbol->field, &expr->cmp.value,
2299 &expr->cmp.mask, m);
2302 if (!lookup_port(aux, expr->cmp.string, &port)) {
2306 struct mf_subfield sf;
2307 sf.field = expr->cmp.symbol->field;
2309 sf.n_bits = expr->cmp.symbol->field->n_bits;
2311 union mf_subvalue x;
2312 memset(&x, 0, sizeof x);
2313 x.integer = htonll(port);
2315 mf_write_subfield(&sf, &x, m);
2321 add_disjunction(const struct expr *or,
2322 bool (*lookup_port)(const void *aux, const char *port_name,
2323 unsigned int *portp),
2325 struct match *m, uint8_t clause, uint8_t n_clauses,
2326 uint32_t conj_id, struct hmap *matches)
2331 ovs_assert(or->type == EXPR_T_OR);
2332 LIST_FOR_EACH (sub, node, &or->andor) {
2333 struct expr_match *match = expr_match_new(m, clause, n_clauses,
2335 if (constrain_match(sub, lookup_port, aux, &match->match)) {
2336 expr_match_add(matches, match);
2339 free(match->conjunctions);
2344 /* If n == 1, then this didn't really need to be a disjunction. Oh well,
2345 * that shouldn't happen much. */
2350 add_conjunction(const struct expr *and,
2351 bool (*lookup_port)(const void *aux, const char *port_name,
2352 unsigned int *portp),
2353 const void *aux, uint32_t *n_conjsp, struct hmap *matches)
2359 match_init_catchall(&match);
2361 ovs_assert(and->type == EXPR_T_AND);
2362 LIST_FOR_EACH (sub, node, &and->andor) {
2363 switch (sub->type) {
2365 if (!constrain_match(sub, lookup_port, aux, &match)) {
2373 case EXPR_T_BOOLEAN:
2379 expr_match_add(matches, expr_match_new(&match, 0, 0, 0));
2380 } else if (n_clauses == 1) {
2381 LIST_FOR_EACH (sub, node, &and->andor) {
2382 if (sub->type == EXPR_T_OR) {
2383 add_disjunction(sub, lookup_port, aux, &match, 0, 0, 0,
2390 LIST_FOR_EACH (sub, node, &and->andor) {
2391 if (sub->type == EXPR_T_OR) {
2392 if (!add_disjunction(sub, lookup_port, aux, &match, clause++,
2393 n_clauses, *n_conjsp, matches)) {
2394 /* This clause can't ever match, so we might as well skip
2395 * adding the other clauses--the overall disjunctive flow
2396 * can't ever match. Ideally we would also back out all of
2397 * the clauses we already added, but that seems like a lot
2398 * of trouble for a case that might never occur in
2405 /* Add the flow that matches on conj_id. */
2406 match_set_conj_id(&match, *n_conjsp);
2407 expr_match_add(matches, expr_match_new(&match, 0, 0, 0));
2412 add_cmp_flow(const struct expr *cmp,
2413 bool (*lookup_port)(const void *aux, const char *port_name,
2414 unsigned int *portp),
2415 const void *aux, struct hmap *matches)
2417 struct expr_match *m = expr_match_new(NULL, 0, 0, 0);
2418 if (constrain_match(cmp, lookup_port, aux, &m->match)) {
2419 expr_match_add(matches, m);
2425 /* Converts 'expr', which must be in the form returned by expr_normalize(), to
2426 * a collection of Open vSwitch flows in 'matches', which this function
2427 * initializes to an hmap of "struct expr_match" structures. Returns the
2428 * number of conjunctive match IDs consumed by 'matches', which uses
2429 * conjunctive match IDs beginning with 0; the caller must offset or remap them
2430 * into the desired range as necessary.
2432 * The matches inserted into 'matches' will be of three distinct kinds:
2434 * - Ordinary flows. The caller should add these OpenFlow flows with
2435 * its desired actions.
2437 * - Conjunctive flows, distinguished by 'n > 0' in the expr_match
2438 * structure. The caller should add these OpenFlow flows with the
2439 * conjunction(id, k/n) actions as specified in the 'conjunctions' array,
2440 * remapping the ids.
2442 * - conj_id flows, distinguished by matching on the "conj_id" field. The
2443 * caller should remap the conj_id and add the OpenFlow flow with its
2446 * 'lookup_port' must be a function to map from a port name to a port number.
2447 * When successful, 'lookup_port' stores the port number into '*portp' and
2448 * returns true; when there is no port by the given name, it returns false.
2449 * 'aux' is passed to 'lookup_port' as auxiliary data. Any comparisons against
2450 * string fields in 'expr' are translated into integers through this function.
2451 * A comparison against a string that is not in 'ports' acts like a Boolean
2452 * "false"; that is, it will always fail to match. For a simple expression,
2453 * this means that the overall expression always fails to match, but an
2454 * expression with a disjunction on the string field might still match on other
2457 * (This treatment of string fields might be too simplistic in general, but it
2458 * seems reasonable for now when string fields are used only for ports.) */
2460 expr_to_matches(const struct expr *expr,
2461 bool (*lookup_port)(const void *aux, const char *port_name,
2462 unsigned int *portp),
2463 const void *aux, struct hmap *matches)
2465 uint32_t n_conjs = 0;
2468 switch (expr->type) {
2470 add_cmp_flow(expr, lookup_port, aux, matches);
2474 add_conjunction(expr, lookup_port, aux, &n_conjs, matches);
2478 if (expr_is_cmp(expr)) {
2481 LIST_FOR_EACH (sub, node, &expr->andor) {
2482 add_cmp_flow(sub, lookup_port, aux, matches);
2487 LIST_FOR_EACH (sub, node, &expr->andor) {
2488 if (sub->type == EXPR_T_AND) {
2489 add_conjunction(sub, lookup_port, aux, &n_conjs, matches);
2491 add_cmp_flow(sub, lookup_port, aux, matches);
2497 case EXPR_T_BOOLEAN:
2498 if (expr->boolean) {
2499 struct expr_match *m = expr_match_new(NULL, 0, 0, 0);
2500 expr_match_add(matches, m);
2509 /* Destroys all of the 'struct expr_match'es in 'matches', as well as the
2510 * 'matches' hmap itself. */
2512 expr_matches_destroy(struct hmap *matches)
2514 struct expr_match *m, *n;
2516 HMAP_FOR_EACH_SAFE (m, n, hmap_node, matches) {
2517 hmap_remove(matches, &m->hmap_node);
2518 free(m->conjunctions);
2521 hmap_destroy(matches);
2524 /* Prints a representation of the 'struct expr_match'es in 'matches' to
2527 expr_matches_print(const struct hmap *matches, FILE *stream)
2529 if (hmap_is_empty(matches)) {
2530 fputs("(no flows)\n", stream);
2534 const struct expr_match *m;
2535 HMAP_FOR_EACH (m, hmap_node, matches) {
2536 char *s = match_to_string(&m->match, OFP_DEFAULT_PRIORITY);
2541 for (int i = 0; i < m->n; i++) {
2542 const struct cls_conjunction *c = &m->conjunctions[i];
2543 fprintf(stream, "%c conjunction(%"PRIu32", %d/%d)",
2544 i == 0 ? ':' : ',', c->id, c->clause, c->n_clauses);
2551 /* Returns true if 'expr' honors the invariants for expressions (see the large
2552 * comment above "struct expr" in expr.h), false otherwise. */
2554 expr_honors_invariants(const struct expr *expr)
2556 const struct expr *sub;
2558 switch (expr->type) {
2560 if (expr->cmp.symbol->width) {
2561 for (int i = 0; i < ARRAY_SIZE(expr->cmp.value.be64); i++) {
2562 if (expr->cmp.value.be64[i] & ~expr->cmp.mask.be64[i]) {
2571 if (ovs_list_is_short(&expr->andor)) {
2574 LIST_FOR_EACH (sub, node, &expr->andor) {
2575 if (sub->type == expr->type || !expr_honors_invariants(sub)) {
2581 case EXPR_T_BOOLEAN:
2590 expr_is_normalized_and(const struct expr *expr)
2592 /* XXX should also check that no symbol is repeated. */
2593 const struct expr *sub;
2595 LIST_FOR_EACH (sub, node, &expr->andor) {
2596 if (!expr_is_cmp(sub)) {
2603 /* Returns true if 'expr' is in the form returned by expr_normalize(), false
2606 expr_is_normalized(const struct expr *expr)
2608 switch (expr->type) {
2613 return expr_is_normalized_and(expr);
2616 if (!expr_is_cmp(expr)) {
2617 const struct expr *sub;
2619 LIST_FOR_EACH (sub, node, &expr->andor) {
2620 if (!expr_is_cmp(sub) && !expr_is_normalized_and(sub)) {
2627 case EXPR_T_BOOLEAN:
2635 /* Action parsing helper. */
2637 /* Expands 'f' repeatedly as long as it has an expansion, that is, as long as
2638 * it is a subfield or a predicate. Adds any prerequisites for 'f' to
2641 * If 'rw', verifies that 'f' is a read/write field.
2643 * Returns true if successful, false if an error was encountered (in which case
2644 * 'ctx->error' reports the particular error). */
2646 expand_symbol(struct expr_context *ctx, bool rw,
2647 struct expr_field *f, struct expr **prereqsp)
2649 const struct expr_symbol *orig_symbol = f->symbol;
2651 if (f->symbol->expansion && f->symbol->level != EXPR_L_ORDINAL) {
2652 expr_error(ctx, "Predicate symbol %s used where lvalue required.",
2658 /* Accumulate prerequisites. */
2659 if (f->symbol->prereqs) {
2660 struct ovs_list nesting = OVS_LIST_INITIALIZER(&nesting);
2663 e = parse_and_annotate(f->symbol->prereqs, ctx->symtab, &nesting,
2666 expr_error(ctx, "%s", error);
2670 *prereqsp = expr_combine(EXPR_T_AND, *prereqsp, e);
2673 /* If there's no expansion, we're done. */
2674 if (!f->symbol->expansion) {
2679 struct expr_field expansion;
2681 if (!parse_field_from_string(f->symbol->expansion, ctx->symtab,
2682 &expansion, &error)) {
2683 expr_error(ctx, "%s", error);
2687 f->symbol = expansion.symbol;
2688 f->ofs += expansion.ofs;
2691 if (rw && !f->symbol->field->writable) {
2692 expr_error(ctx, "Field %s is not modifiable.", orig_symbol->name);
2700 mf_subfield_from_expr_field(const struct expr_field *f, struct mf_subfield *sf)
2702 sf->field = f->symbol->field;
2704 sf->n_bits = f->n_bits ? f->n_bits : f->symbol->field->n_bits;
2708 init_stack_action(const struct expr_field *f, struct ofpact_stack *stack)
2710 mf_subfield_from_expr_field(f, &stack->subfield);
2713 static struct expr *
2714 parse_assignment(struct expr_context *ctx,
2715 bool (*lookup_port)(const void *aux, const char *port_name,
2716 unsigned int *portp),
2717 const void *aux, struct ofpbuf *ofpacts)
2719 struct expr *prereqs = NULL;
2721 /* Parse destination and do basic checking. */
2722 struct expr_field dst;
2723 if (!parse_field(ctx, &dst)) {
2726 bool exchange = lexer_match(ctx->lexer, LEX_T_EXCHANGE);
2727 if (!exchange && !lexer_match(ctx->lexer, LEX_T_EQUALS)) {
2728 expr_syntax_error(ctx, "expecting `='.");
2731 const struct expr_symbol *orig_dst = dst.symbol;
2732 if (!expand_symbol(ctx, true, &dst, &prereqs)) {
2736 if (exchange || ctx->lexer->token.type == LEX_T_ID) {
2737 struct expr_field src;
2738 if (!parse_field(ctx, &src)) {
2741 const struct expr_symbol *orig_src = src.symbol;
2742 if (!expand_symbol(ctx, exchange, &src, &prereqs)) {
2746 if ((dst.symbol->width != 0) != (src.symbol->width != 0)) {
2749 "Can't exchange %s field (%s) with %s field (%s).",
2750 orig_dst->width ? "integer" : "string",
2752 orig_src->width ? "integer" : "string",
2755 expr_error(ctx, "Can't assign %s field (%s) to %s field (%s).",
2756 orig_src->width ? "integer" : "string",
2758 orig_dst->width ? "integer" : "string",
2764 if (dst.n_bits != src.n_bits) {
2767 "Can't exchange %d-bit field with %d-bit field.",
2768 dst.n_bits, src.n_bits);
2771 "Can't assign %d-bit value to %d-bit destination.",
2772 src.n_bits, dst.n_bits);
2775 } else if (!dst.n_bits
2776 && dst.symbol->field->n_bits != src.symbol->field->n_bits) {
2777 expr_error(ctx, "String fields %s and %s are incompatible for "
2778 "%s.", orig_dst->name, orig_src->name,
2779 exchange ? "exchange" : "assignment");
2784 init_stack_action(&src, ofpact_put_STACK_PUSH(ofpacts));
2785 init_stack_action(&dst, ofpact_put_STACK_PUSH(ofpacts));
2786 init_stack_action(&src, ofpact_put_STACK_POP(ofpacts));
2787 init_stack_action(&dst, ofpact_put_STACK_POP(ofpacts));
2789 struct ofpact_reg_move *move = ofpact_put_REG_MOVE(ofpacts);
2790 mf_subfield_from_expr_field(&src, &move->src);
2791 mf_subfield_from_expr_field(&dst, &move->dst);
2794 struct expr_constant_set cs;
2795 if (!parse_constant_set(ctx, &cs)) {
2799 if (!type_check(ctx, &dst, &cs)) {
2800 goto exit_destroy_cs;
2802 if (cs.in_curlies) {
2803 expr_error(ctx, "Assignments require a single value.");
2804 goto exit_destroy_cs;
2807 union expr_constant *c = cs.values;
2808 struct ofpact_set_field *sf = ofpact_put_SET_FIELD(ofpacts);
2809 sf->field = dst.symbol->field;
2810 if (dst.symbol->width) {
2811 mf_subvalue_shift(&c->value, dst.ofs);
2813 memset(&c->mask, 0, sizeof c->mask);
2814 bitwise_one(&c->mask, sizeof c->mask, dst.ofs, dst.n_bits);
2816 mf_subvalue_shift(&c->mask, dst.ofs);
2820 &c->value.u8[sizeof c->value - sf->field->n_bytes],
2821 sf->field->n_bytes);
2823 &c->mask.u8[sizeof c->mask - sf->field->n_bytes],
2824 sf->field->n_bytes);
2827 if (!lookup_port(aux, c->string, &port)) {
2830 bitwise_put(port, &sf->value,
2831 sf->field->n_bytes, 0, sf->field->n_bits);
2832 bitwise_one(&sf->mask, sf->field->n_bytes, 0, sf->field->n_bits);
2834 /* If the logical input port is being zeroed, clear the OpenFlow
2835 * ingress port also, to allow a packet to be sent back to its
2837 if (!port && sf->field->id == MFF_LOG_INPORT) {
2838 sf = ofpact_put_SET_FIELD(ofpacts);
2839 sf->field = mf_from_id(MFF_IN_PORT);
2840 bitwise_one(&sf->mask,
2841 sf->field->n_bytes, 0, sf->field->n_bits);
2846 expr_constant_set_destroy(&cs);
2853 /* A helper for actions_parse(), to parse an OVN assignment action in the form
2854 * "field = value" or "field1 = field2", or a "exchange" action in the form
2855 * "field1 <-> field2", into 'ofpacts'. The parameters and return value match
2856 * those for actions_parse(). */
2858 expr_parse_assignment(struct lexer *lexer, const struct shash *symtab,
2859 bool (*lookup_port)(const void *aux,
2860 const char *port_name,
2861 unsigned int *portp),
2863 struct ofpbuf *ofpacts, struct expr **prereqsp)
2865 struct expr_context ctx;
2867 ctx.symtab = symtab;
2871 struct expr *prereqs = parse_assignment(&ctx, lookup_port, aux, ofpacts);
2873 expr_destroy(prereqs);
2876 *prereqsp = prereqs;
2881 expr_parse_field(struct lexer *lexer, int n_bits, bool rw,
2882 const struct shash *symtab,
2883 struct mf_subfield *sf, struct expr **prereqsp)
2885 struct expr *prereqs = NULL;
2886 struct expr_context ctx;
2888 ctx.symtab = symtab;
2892 struct expr_field field;
2893 if (!parse_field(&ctx, &field)) {
2897 const struct expr_field orig_field = field;
2898 if (!expand_symbol(&ctx, rw, &field, &prereqs)) {
2901 ovs_assert(field.n_bits == orig_field.n_bits);
2903 if (n_bits != field.n_bits) {
2904 if (n_bits && field.n_bits) {
2905 expr_error(&ctx, "Cannot use %d-bit field %s[%d..%d] "
2906 "where %d-bit field is required.",
2907 orig_field.n_bits, orig_field.symbol->name,
2908 orig_field.ofs, orig_field.ofs + orig_field.n_bits - 1,
2910 } else if (n_bits) {
2911 expr_error(&ctx, "Cannot use string field %s where numeric "
2912 "field is required.",
2913 orig_field.symbol->name);
2915 expr_error(&ctx, "Cannot use numeric field %s where string "
2916 "field is required.",
2917 orig_field.symbol->name);
2923 mf_subfield_from_expr_field(&field, sf);
2924 *prereqsp = prereqs;
2926 memset(sf, 0, sizeof *sf);
2927 expr_destroy(prereqs);