From patchwork Fri Mar 17 19:25:09 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ilya Maximets X-Patchwork-Id: 1758364 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=openvswitch.org (client-ip=140.211.166.136; helo=smtp3.osuosl.org; envelope-from=ovs-dev-bounces@openvswitch.org; receiver=) Received: from smtp3.osuosl.org (smtp3.osuosl.org [140.211.166.136]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-384) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4PdYx54kC4z1yWs for ; Sat, 18 Mar 2023 06:24:57 +1100 (AEDT) Received: from localhost (localhost [127.0.0.1]) by smtp3.osuosl.org (Postfix) with ESMTP id 672BF61B14; Fri, 17 Mar 2023 19:24:55 +0000 (UTC) DKIM-Filter: OpenDKIM Filter v2.11.0 smtp3.osuosl.org 672BF61B14 X-Virus-Scanned: amavisd-new at osuosl.org Received: from smtp3.osuosl.org ([127.0.0.1]) by localhost (smtp3.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id Ei89MY6Ex-xS; Fri, 17 Mar 2023 19:24:54 +0000 (UTC) Received: from lists.linuxfoundation.org (lf-lists.osuosl.org [IPv6:2605:bc80:3010:104::8cd3:938]) by smtp3.osuosl.org (Postfix) with ESMTPS id 3763760F6B; Fri, 17 Mar 2023 19:24:53 +0000 (UTC) DKIM-Filter: OpenDKIM Filter v2.11.0 smtp3.osuosl.org 3763760F6B Received: from lf-lists.osuosl.org (localhost [127.0.0.1]) by lists.linuxfoundation.org (Postfix) with ESMTP id 164D3C0071; Fri, 17 Mar 2023 19:24:53 +0000 (UTC) X-Original-To: ovs-dev@openvswitch.org Delivered-To: ovs-dev@lists.linuxfoundation.org Received: from smtp2.osuosl.org (smtp2.osuosl.org [140.211.166.133]) by lists.linuxfoundation.org (Postfix) with ESMTP id 832A8C0032 for ; Fri, 17 Mar 2023 19:24:51 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp2.osuosl.org (Postfix) with ESMTP id 4BD03400A4 for ; Fri, 17 Mar 2023 19:24:51 +0000 (UTC) DKIM-Filter: OpenDKIM Filter v2.11.0 smtp2.osuosl.org 4BD03400A4 X-Virus-Scanned: amavisd-new at osuosl.org Received: from smtp2.osuosl.org ([127.0.0.1]) by localhost (smtp2.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id jk-6M-KKBopu for ; Fri, 17 Mar 2023 19:24:50 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.8.0 DKIM-Filter: OpenDKIM Filter v2.11.0 smtp2.osuosl.org B649840025 Received: from relay6-d.mail.gandi.net (relay6-d.mail.gandi.net [217.70.183.198]) by smtp2.osuosl.org (Postfix) with ESMTPS id B649840025 for ; Fri, 17 Mar 2023 19:24:49 +0000 (UTC) Received: (Authenticated sender: i.maximets@ovn.org) by mail.gandi.net (Postfix) with ESMTPSA id 42D14C0004; Fri, 17 Mar 2023 19:24:45 +0000 (UTC) From: Ilya Maximets To: ovs-dev@openvswitch.org Date: Fri, 17 Mar 2023 20:25:09 +0100 Message-Id: <20230317192509.1513631-1-i.maximets@ovn.org> X-Mailer: git-send-email 2.39.2 MIME-Version: 1.0 Cc: Nadia Pinaeva , Ilya Maximets , Dumitru Ceara Subject: [ovs-dev] [PATCH ovn] expr: Remove supersets from OR expressions. X-BeenThere: ovs-dev@openvswitch.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: ovs-dev-bounces@openvswitch.org Sender: "dev" While crushing OR expressions, OVN removes exact replicas of sub expressions. However, there could be many CMP expressions that are supersets of each other. These are most likely to be created as a result of cross-product while expanding brackets in the AND expression in crush_and_numeric(), i.e. while converting "x && (a0 || a1) && (b0 || b1)" into "xa0b0 || xa0b1 || xa1b0 || xa1b1". Replacing the removal of exact duplicates with scan and removal of supersets of other existing sub-expressions to reduce the amount of generated flows. This operation is less efficient in comparison, but should save time later, since less flows will be generated. Example: "ip4.src == 172.168.0.0/16 && ip4.src!={172.168.13.0/24, 172.168.15.0/24}" Processing of this expression yields 42 flows: $ ./tests/ovstest test-ovn expr-to-flows <<< "$expr" ip,nw_src=172.168.0.0/255.255.1.0 ip,nw_src=172.168.0.0/255.255.10.0 ip,nw_src=172.168.0.0/255.255.12.0 ip,nw_src=172.168.0.0/255.255.3.0 ip,nw_src=172.168.0.0/255.255.4.0 ip,nw_src=172.168.0.0/255.255.5.0 ip,nw_src=172.168.0.0/255.255.6.0 ip,nw_src=172.168.0.0/255.255.8.0 ip,nw_src=172.168.0.0/255.255.9.0 ip,nw_src=172.168.128.0/17 <... 32 more flows ...> We can see that many flows above do overlap, e.g. 255.255.3.0 mask is a superset of 255.255.1.0. Everything that matches 255.255.3.0, will match 255.255.1.0 as well (the value is the same). By removing all the unnecessary supersets, the set of flows can be reduced from 42 down to 7: ip,nw_src=172.168.0.0/255.255.1.0 ip,nw_src=172.168.0.0/255.255.4.0 ip,nw_src=172.168.0.0/255.255.8.0 ip,nw_src=172.168.128.0/17 ip,nw_src=172.168.16.0/255.255.16.0 ip,nw_src=172.168.32.0/255.255.32.0 ip,nw_src=172.168.64.0/255.255.64.0 This change should be particularly useful for expressions with inequality checks, like the one above. Such expressions are frequent among ACL rules. Reported-at: https://bugzilla.redhat.com/show_bug.cgi?id=2177197 Reported-by: Nadia Pinaeva Signed-off-by: Ilya Maximets --- lib/expr.c | 128 ++++++++++++++++++++++++++++++----------------------- 1 file changed, 73 insertions(+), 55 deletions(-) diff --git a/lib/expr.c b/lib/expr.c index 0a6f7e574..4aa8873b6 100644 --- a/lib/expr.c +++ b/lib/expr.c @@ -16,20 +16,21 @@ #include #include "byte-order.h" -#include "openvswitch/json.h" +#include "hmapx.h" #include "nx-match.h" #include "openvswitch/dynamic-string.h" +#include "openvswitch/json.h" #include "openvswitch/match.h" #include "openvswitch/ofp-actions.h" -#include "openvswitch/vlog.h" #include "openvswitch/shash.h" +#include "openvswitch/vlog.h" +#include "ovn-util.h" #include "ovn/expr.h" #include "ovn/lex.h" #include "ovn/logical-fields.h" #include "simap.h" #include "sset.h" #include "util.h" -#include "ovn-util.h" VLOG_DEFINE_THIS_MODULE(expr); @@ -2520,6 +2521,74 @@ crush_and_string(struct expr *expr, const struct expr_symbol *symbol) return expr_fix(expr); } +/* This function expects an OR expression with already crushed sub + * expressions, so they are plain comparisons. Result is the same + * expression, but with unnecessary sub-expressions removed. */ +static struct expr * +crush_or_supersets(struct expr *expr, const struct expr_symbol *symbol) +{ + struct hmapx to_delete = HMAPX_INITIALIZER(&to_delete); + + ovs_assert(expr->type == EXPR_T_OR); + if (!symbol->width) { + return expr; + } + + struct expr *a; + LIST_FOR_EACH (a, node, &expr->andor) { + ovs_assert(a->type == EXPR_T_CMP); + + if (hmapx_contains(&to_delete, a)) { + continue; + } + + struct expr *b; + LIST_FOR_EACH (b, node, &expr->andor) { + union mf_subvalue tmp_value, tmp_mask; + + if (a == b || hmapx_contains(&to_delete, b)) { + continue; + } + + /* Conflicting sub-expressions cannot superseed each other. */ + if (mf_subvalue_intersect(&a->cmp.value, &a->cmp.mask, + &b->cmp.value, &b->cmp.mask, + &tmp_value, &tmp_mask)) { + const size_t sz = sizeof a->cmp.mask * CHAR_BIT; + const unsigned long *a_mask, *b_mask; + + a_mask = (unsigned long *) a->cmp.mask.be64; + b_mask = (unsigned long *) b->cmp.mask.be64; + + /* Check if 'a' is a superset of 'b' or the other way around. + * Keep the smaller mask. */ + if (bitmap_is_superset(a_mask, b_mask, sz)) { + hmapx_add(&to_delete, a); + break; + } else if (bitmap_is_superset(b_mask, a_mask, sz)) { + hmapx_add(&to_delete, b); + } + } + } + } + + if (hmapx_count(&to_delete)) { + /* Members modified, so untrack address set. */ + free(expr->as_name); + expr->as_name = NULL; + } + + struct hmapx_node *node; + HMAPX_FOR_EACH (node, &to_delete) { + a = (struct expr *) node->data; + ovs_list_remove(&a->node); + expr_destroy(a); + } + hmapx_destroy(&to_delete); + + return expr; +} + /* Implementation of crush_cmps() for expr->type == EXPR_T_AND and a * numeric-typed 'symbol'. */ static struct expr * @@ -2679,31 +2748,6 @@ crush_and_numeric(struct expr *expr, const struct expr_symbol *symbol) } } -static int -compare_cmps_3way(const struct expr *a, const struct expr *b) -{ - ovs_assert(a->cmp.symbol == b->cmp.symbol); - if (!a->cmp.symbol->width) { - return strcmp(a->cmp.string, b->cmp.string); - } else { - int d = memcmp(&a->cmp.value, &b->cmp.value, sizeof a->cmp.value); - if (!d) { - d = memcmp(&a->cmp.mask, &b->cmp.mask, sizeof a->cmp.mask); - } - return d; - } -} - -static int -compare_cmps_cb(const void *a_, const void *b_) -{ - const struct expr *const *ap = a_; - const struct expr *const *bp = b_; - const struct expr *a = *ap; - const struct expr *b = *bp; - return compare_cmps_3way(a, b); -} - /* Implementation of crush_cmps() for expr->type == EXPR_T_OR. */ static struct expr * crush_or(struct expr *expr, const struct expr_symbol *symbol) @@ -2723,34 +2767,8 @@ crush_or(struct expr *expr, const struct expr_symbol *symbol) return expr; } - /* Sort subexpressions by value and mask, to bring together duplicates. */ - size_t n = ovs_list_size(&expr->andor); - struct expr **subs = xmalloc(n * sizeof *subs); - - size_t i = 0; - LIST_FOR_EACH (sub, node, &expr->andor) { - subs[i++] = sub; - } - ovs_assert(i == n); - - qsort(subs, n, sizeof *subs, compare_cmps_cb); + expr = crush_or_supersets(expr, symbol); - /* Eliminate duplicates. */ - ovs_list_init(&expr->andor); - ovs_list_push_back(&expr->andor, &subs[0]->node); - for (i = 1; i < n; i++) { - struct expr *a = expr_from_node(ovs_list_back(&expr->andor)); - struct expr *b = subs[i]; - if (compare_cmps_3way(a, b)) { - ovs_list_push_back(&expr->andor, &b->node); - } else { - expr_destroy(b); - /* Member modified, so untrack address set. */ - free(expr->as_name); - expr->as_name = NULL; - } - } - free(subs); return expr_fix(expr); }