From patchwork Sat Aug 13 16:30:28 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ben Pfaff X-Patchwork-Id: 658984 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from archives.nicira.com (archives.nicira.com [96.126.127.54]) by ozlabs.org (Postfix) with ESMTP id 3sBS1k3K1Sz9syB for ; Sun, 14 Aug 2016 02:31:22 +1000 (AEST) Received: from archives.nicira.com (localhost [127.0.0.1]) by archives.nicira.com (Postfix) with ESMTP id 6D61F10B84; Sat, 13 Aug 2016 09:30:52 -0700 (PDT) X-Original-To: dev@openvswitch.org Delivered-To: dev@openvswitch.org Received: from mx1e3.cudamail.com (mx1.cudamail.com [69.90.118.67]) by archives.nicira.com (Postfix) with ESMTPS id 71C0A108E3 for ; Sat, 13 Aug 2016 09:30:49 -0700 (PDT) Received: from bar5.cudamail.com (localhost [127.0.0.1]) by mx1e3.cudamail.com (Postfix) with ESMTPS id 08862420205 for ; Sat, 13 Aug 2016 10:30:49 -0600 (MDT) X-ASG-Debug-ID: 1471105848-09eadd687428b90001-byXFYA Received: from mx3-pf1.cudamail.com ([192.168.14.2]) by bar5.cudamail.com with ESMTP id IBypCVc0gFNfeKRD (version=TLSv1 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO) for ; Sat, 13 Aug 2016 10:30:48 -0600 (MDT) X-Barracuda-Envelope-From: blp@ovn.org X-Barracuda-RBL-Trusted-Forwarder: 192.168.14.2 Received: from unknown (HELO relay4-d.mail.gandi.net) (217.70.183.196) by mx3-pf1.cudamail.com with ESMTPS (DHE-RSA-AES256-SHA encrypted); 13 Aug 2016 16:30:48 -0000 Received-SPF: pass (mx3-pf1.cudamail.com: SPF record at ovn.org designates 217.70.183.196 as permitted sender) X-Barracuda-Apparent-Source-IP: 217.70.183.196 X-Barracuda-RBL-IP: 217.70.183.196 Received: from mfilter17-d.gandi.net (mfilter17-d.gandi.net [217.70.178.145]) by relay4-d.mail.gandi.net (Postfix) with ESMTP id BC939172094; Sat, 13 Aug 2016 18:30:46 +0200 (CEST) X-Virus-Scanned: Debian amavisd-new at mfilter17-d.gandi.net Received: from relay4-d.mail.gandi.net ([IPv6:::ffff:217.70.183.196]) by mfilter17-d.gandi.net (mfilter17-d.gandi.net [::ffff:10.0.15.180]) (amavisd-new, port 10024) with ESMTP id D4ogh7uK3iVS; Sat, 13 Aug 2016 18:30:44 +0200 (CEST) X-Originating-IP: 173.228.112.241 Received: from sigabrt.gateway.sonic.net (173-228-112-241.dsl.dynamic.fusionbroadband.com [173.228.112.241]) (Authenticated sender: blp@ovn.org) by relay4-d.mail.gandi.net (Postfix) with ESMTPSA id C2CD917209A; Sat, 13 Aug 2016 18:30:43 +0200 (CEST) X-CudaMail-Envelope-Sender: blp@ovn.org From: Ben Pfaff To: dev@openvswitch.org X-CudaMail-Whitelist-To: dev@openvswitch.org X-CudaMail-MID: CM-V1-812009182 X-CudaMail-DTE: 081316 X-CudaMail-Originating-IP: 217.70.183.196 Date: Sat, 13 Aug 2016 09:30:28 -0700 X-ASG-Orig-Subj: [##CM-V1-812009182##][PATCH v4 6/8] expr: New function expr_evaluate(). Message-Id: <1471105830-30204-7-git-send-email-blp@ovn.org> X-Mailer: git-send-email 2.1.3 In-Reply-To: <1471105830-30204-1-git-send-email-blp@ovn.org> References: <1471105830-30204-1-git-send-email-blp@ovn.org> X-Barracuda-Connect: UNKNOWN[192.168.14.2] X-Barracuda-Start-Time: 1471105848 X-Barracuda-Encrypted: DHE-RSA-AES256-SHA X-Barracuda-URL: https://web.cudamail.com:443/cgi-mod/mark.cgi X-ASG-Whitelist: Header =?UTF-8?B?eFwtY3VkYW1haWxcLXdoaXRlbGlzdFwtdG8=?= X-Virus-Scanned: by bsmtpd at cudamail.com X-Barracuda-BRTS-Status: 1 Cc: Ben Pfaff Subject: [ovs-dev] [PATCH v4 6/8] expr: New function expr_evaluate(). X-BeenThere: dev@openvswitch.org X-Mailman-Version: 2.1.16 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , MIME-Version: 1.0 Errors-To: dev-bounces@openvswitch.org Sender: "dev" An upcoming commit will need to evaluate individual expressions outside the context of a classifier. test-ovn already had a function to do this but it wasn't general-purpose, so this commit makes a general-purpose version and adopts it for use in test-ovn as well. Signed-off-by: Ben Pfaff Acked-by: Ryan Moats --- include/ovn/expr.h | 6 +++ ovn/lib/expr.c | 118 +++++++++++++++++++++++++++++++++++++++++++++++- tests/test-ovn.c | 130 ++++++++++------------------------------------------- 3 files changed, 147 insertions(+), 107 deletions(-) diff --git a/include/ovn/expr.h b/include/ovn/expr.h index e1c1886..fa603bb 100644 --- a/include/ovn/expr.h +++ b/include/ovn/expr.h @@ -61,6 +61,7 @@ struct ds; struct expr; +struct flow; struct ofpbuf; struct shash; struct simap; @@ -380,6 +381,11 @@ struct expr *expr_normalize(struct expr *); bool expr_honors_invariants(const struct expr *); bool expr_is_simplified(const struct expr *); bool expr_is_normalized(const struct expr *); + +bool expr_evaluate(const struct expr *, const struct flow *uflow, + bool (*lookup_port)(const void *aux, const char *port_name, + unsigned int *portp), + const void *aux); /* Converting expressions to OpenFlow flows. */ diff --git a/ovn/lib/expr.c b/ovn/lib/expr.c index c3a26f5..f90c7d1 100644 --- a/ovn/lib/expr.c +++ b/ovn/lib/expr.c @@ -119,6 +119,22 @@ expr_relop_invert(enum expr_relop relop) default: OVS_NOT_REACHED(); } } + +/* Checks whether 'relop' is true for strcmp()-like 3-way comparison result + * 'cmp'. */ +static bool +expr_relop_test(enum expr_relop relop, int cmp) +{ + switch (relop) { + case EXPR_R_EQ: return cmp == 0; + case EXPR_R_NE: return cmp != 0; + case EXPR_R_LT: return cmp < 0; + case EXPR_R_LE: return cmp <= 0; + case EXPR_R_GT: return cmp > 0; + case EXPR_R_GE: return cmp >= 0; + default: OVS_NOT_REACHED(); + } +} /* Constructing and manipulating expressions. */ @@ -2445,9 +2461,17 @@ expr_match_add(struct hmap *matches, struct expr_match *match) hmap_insert(matches, &match->hmap_node, hash); } +/* Applies EXPR_T_CMP-typed 'expr' to 'm'. This will only work properly if 'm' + * doesn't already match on 'expr->cmp.symbol', because it replaces any + * existing match on that symbol instead of intersecting with it. + * + * If 'expr' is a comparison on a string field, uses 'lookup_port' and 'aux' to + * convert the string to a port number. In such a case, if the port can't be + * found, returns false. In all other cases, returns true. */ static bool constrain_match(const struct expr *expr, - bool (*lookup_port)(const void *aux, const char *port_name, + bool (*lookup_port)(const void *aux, + const char *port_name, unsigned int *portp), const void *aux, struct match *m) { @@ -2788,6 +2812,98 @@ expr_is_normalized(const struct expr *expr) OVS_NOT_REACHED(); } } + +static bool +expr_evaluate_andor(const struct expr *e, const struct flow *f, + bool short_circuit, + bool (*lookup_port)(const void *aux, const char *port_name, + unsigned int *portp), + const void *aux) +{ + const struct expr *sub; + + LIST_FOR_EACH (sub, node, &e->andor) { + if (expr_evaluate(sub, f, lookup_port, aux) == short_circuit) { + return short_circuit; + } + } + return !short_circuit; +} + +static bool +expr_evaluate_cmp(const struct expr *e, const struct flow *f, + bool (*lookup_port)(const void *aux, const char *port_name, + unsigned int *portp), + const void *aux) +{ + const struct expr_symbol *s = e->cmp.symbol; + const struct mf_field *field = s->field; + + int cmp; + if (e->cmp.symbol->width) { + int n_bytes = field->n_bytes; + const uint8_t *cst = &e->cmp.value.u8[sizeof e->cmp.value - n_bytes]; + const uint8_t *mask = &e->cmp.mask.u8[sizeof e->cmp.mask - n_bytes]; + + /* Get field value and mask off undesired bits. */ + union mf_value value; + mf_get_value(field, f, &value); + for (int i = 0; i < field->n_bytes; i++) { + value.b[i] &= mask[i]; + } + + /* Compare against constant. */ + cmp = memcmp(&value, cst, n_bytes); + } else { + /* Get field value. */ + struct mf_subfield sf = { .field = field, .ofs = 0, + .n_bits = field->n_bits }; + uint64_t value = mf_get_subfield(&sf, f); + + /* Get constant. */ + unsigned int cst; + if (!lookup_port(aux, e->cmp.string, &cst)) { + return false; + } + + /* Compare. */ + cmp = value < cst ? -1 : value > cst; + } + + return expr_relop_test(e->cmp.relop, cmp); +} + +/* Evaluates 'e' against microflow 'uflow' and returns the result. + * + * 'lookup_port' must be a function to map from a port name to a port number + * and 'aux' auxiliary data to pass to it; see expr_to_matches() for more + * details. + * + * This isn't particularly fast. For performance-sensitive tasks, use + * expr_to_matches() and the classifier. */ +bool +expr_evaluate(const struct expr *e, const struct flow *uflow, + bool (*lookup_port)(const void *aux, const char *port_name, + unsigned int *portp), + const void *aux) +{ + switch (e->type) { + case EXPR_T_CMP: + return expr_evaluate_cmp(e, uflow, lookup_port, aux); + + case EXPR_T_AND: + return expr_evaluate_andor(e, uflow, false, lookup_port, aux); + + case EXPR_T_OR: + return expr_evaluate_andor(e, uflow, true, lookup_port, aux); + + case EXPR_T_BOOLEAN: + return e->boolean; + + default: + OVS_NOT_REACHED(); + } +} /* Action parsing helper. */ diff --git a/tests/test-ovn.c b/tests/test-ovn.c index e62c2fe..712c54a 100644 --- a/tests/test-ovn.c +++ b/tests/test-ovn.c @@ -327,91 +327,12 @@ test_dump_symtab(struct ovs_cmdl_context *ctx OVS_UNUSED) /* Evaluate an expression. */ -static bool evaluate_expr(const struct expr *, unsigned int subst, int n_bits); - -static bool -evaluate_andor_expr(const struct expr *expr, unsigned int subst, int n_bits, - bool short_circuit) -{ - const struct expr *sub; - - LIST_FOR_EACH (sub, node, &expr->andor) { - if (evaluate_expr(sub, subst, n_bits) == short_circuit) { - return short_circuit; - } - } - return !short_circuit; -} - -static bool -evaluate_cmp_expr(const struct expr *expr, unsigned int subst, int n_bits) -{ - int var_idx = atoi(expr->cmp.symbol->name + 1); - if (expr->cmp.symbol->name[0] == 'n') { - unsigned var_mask = (1u << n_bits) - 1; - unsigned int arg1 = (subst >> (var_idx * n_bits)) & var_mask; - unsigned int arg2 = ntohll(expr->cmp.value.integer); - unsigned int mask = ntohll(expr->cmp.mask.integer); - - ovs_assert(!(mask & ~var_mask)); - ovs_assert(!(arg2 & ~var_mask)); - ovs_assert(!(arg2 & ~mask)); - - arg1 &= mask; - switch (expr->cmp.relop) { - case EXPR_R_EQ: - return arg1 == arg2; - - case EXPR_R_NE: - return arg1 != arg2; - - case EXPR_R_LT: - return arg1 < arg2; - - case EXPR_R_LE: - return arg1 <= arg2; - - case EXPR_R_GT: - return arg1 > arg2; - - case EXPR_R_GE: - return arg1 >= arg2; - - default: - OVS_NOT_REACHED(); - } - } else if (expr->cmp.symbol->name[0] == 's') { - unsigned int arg1 = (subst >> (test_nvars * n_bits + var_idx)) & 1; - unsigned int arg2 = atoi(expr->cmp.string); - return arg1 == arg2; - } else { - OVS_NOT_REACHED(); - } -} - -/* Evaluates 'expr' and returns its Boolean result. 'subst' provides the value - * for the variables, which must be 'n_bits' bits each and be named "a", "b", - * "c", etc. The value of variable "a" is the least-significant 'n_bits' bits - * of 'subst', the value of "b" is the next 'n_bits' bits, and so on. */ static bool -evaluate_expr(const struct expr *expr, unsigned int subst, int n_bits) +lookup_atoi_cb(const void *aux OVS_UNUSED, const char *port_name, + unsigned int *portp) { - switch (expr->type) { - case EXPR_T_CMP: - return evaluate_cmp_expr(expr, subst, n_bits); - - case EXPR_T_AND: - return evaluate_andor_expr(expr, subst, n_bits, false); - - case EXPR_T_OR: - return evaluate_andor_expr(expr, subst, n_bits, true); - - case EXPR_T_BOOLEAN: - return expr->boolean; - - default: - OVS_NOT_REACHED(); - } + *portp = atoi(port_name); + return true; } static void @@ -420,17 +341,18 @@ test_evaluate_expr(struct ovs_cmdl_context *ctx) int a = atoi(ctx->argv[1]); int b = atoi(ctx->argv[2]); int c = atoi(ctx->argv[3]); - unsigned int subst = a | (b << 3) || (c << 6); + struct flow uflow = { .regs = { a, b, c } }; + struct shash symtab; struct ds input; shash_init(&symtab); - expr_symtab_add_field(&symtab, "xreg0", MFF_XREG0, NULL, false); - expr_symtab_add_field(&symtab, "xreg1", MFF_XREG1, NULL, false); - expr_symtab_add_field(&symtab, "xreg2", MFF_XREG1, NULL, false); - expr_symtab_add_subfield(&symtab, "a", NULL, "xreg0[0..2]"); - expr_symtab_add_subfield(&symtab, "b", NULL, "xreg1[0..2]"); - expr_symtab_add_subfield(&symtab, "c", NULL, "xreg2[0..2]"); + expr_symtab_add_field(&symtab, "reg0", MFF_REG0, NULL, false); + expr_symtab_add_field(&symtab, "reg1", MFF_REG1, NULL, false); + expr_symtab_add_field(&symtab, "reg2", MFF_REG1, NULL, false); + expr_symtab_add_subfield(&symtab, "a", NULL, "reg0[0..2]"); + expr_symtab_add_subfield(&symtab, "b", NULL, "reg1[0..2]"); + expr_symtab_add_subfield(&symtab, "c", NULL, "reg2[0..2]"); ds_init(&input); while (!ds_get_test_line(&input, stdin)) { @@ -442,7 +364,7 @@ test_evaluate_expr(struct ovs_cmdl_context *ctx) expr = expr_annotate(expr, &symtab, &error); } if (!error) { - printf("%d\n", evaluate_expr(expr, subst, 3)); + printf("%d\n", expr_evaluate(expr, &uflow, lookup_atoi_cb, NULL)); } else { puts(error); free(error); @@ -874,10 +796,6 @@ test_tree_shape_exhaustively(struct expr *expr, struct shash *symtab, int n_bits, const struct expr_symbol *svars[], int n_svars) { - struct simap string_map = SIMAP_INITIALIZER(&string_map); - simap_put(&string_map, "0", 0); - simap_put(&string_map, "1", 1); - int n_tested = 0; const unsigned int var_mask = (1u << n_bits) - 1; @@ -892,7 +810,6 @@ test_tree_shape_exhaustively(struct expr *expr, struct shash *symtab, for (int i = n_terminals - 1; ; i--) { if (!i) { ds_destroy(&s); - simap_destroy(&string_map); return n_tested; } if (next_terminal(terminals[i], nvars, n_nvars, n_bits, @@ -933,7 +850,7 @@ test_tree_shape_exhaustively(struct expr *expr, struct shash *symtab, struct expr_match *m; struct test_rule *test_rule; - expr_to_matches(modified, lookup_port_cb, &string_map, &matches); + expr_to_matches(modified, lookup_atoi_cb, NULL, &matches); classifier_init(&cls, NULL); HMAP_FOR_EACH (m, hmap_node, &matches) { @@ -945,8 +862,16 @@ test_tree_shape_exhaustively(struct expr *expr, struct shash *symtab, } for (int subst = 0; subst < 1 << (n_bits * n_nvars + n_svars); subst++) { - bool expected = evaluate_expr(expr, subst, n_bits); - bool actual = evaluate_expr(modified, subst, n_bits); + for (int i = 0; i < n_nvars; i++) { + f.regs[i] = (subst >> (i * n_bits)) & var_mask; + } + for (int i = 0; i < n_svars; i++) { + f.regs[n_nvars + i] = ((subst >> (n_nvars * n_bits + i)) + & 1); + } + + bool expected = expr_evaluate(expr, &f, lookup_atoi_cb, NULL); + bool actual = expr_evaluate(modified, &f, lookup_atoi_cb, NULL); if (actual != expected) { struct ds expr_s, modified_s; @@ -976,13 +901,6 @@ test_tree_shape_exhaustively(struct expr *expr, struct shash *symtab, } if (operation >= OP_FLOW) { - for (int i = 0; i < n_nvars; i++) { - f.regs[i] = (subst >> (i * n_bits)) & var_mask; - } - for (int i = 0; i < n_svars; i++) { - f.regs[n_nvars + i] = ((subst >> (n_nvars * n_bits + i)) - & 1); - } bool found = classifier_lookup(&cls, OVS_VERSION_MIN, &f, NULL) != NULL; if (expected != found) {