From patchwork Mon Mar 20 10:38:07 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ilya Maximets X-Patchwork-Id: 1758932 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=2605:bc80:3010::137; helo=smtp4.osuosl.org; envelope-from=ovs-dev-bounces@openvswitch.org; receiver=) Received: from smtp4.osuosl.org (smtp4.osuosl.org [IPv6:2605:bc80:3010::137]) (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 4PgB5l4CCQz1yWp for ; Mon, 20 Mar 2023 21:38:03 +1100 (AEDT) Received: from localhost (localhost [127.0.0.1]) by smtp4.osuosl.org (Postfix) with ESMTP id BD8CE415D7; Mon, 20 Mar 2023 10:38:00 +0000 (UTC) DKIM-Filter: OpenDKIM Filter v2.11.0 smtp4.osuosl.org BD8CE415D7 X-Virus-Scanned: amavisd-new at osuosl.org Received: from smtp4.osuosl.org ([127.0.0.1]) by localhost (smtp4.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id UAAdyOrwozJz; Mon, 20 Mar 2023 10:37:59 +0000 (UTC) Received: from lists.linuxfoundation.org (lf-lists.osuosl.org [140.211.9.56]) by smtp4.osuosl.org (Postfix) with ESMTPS id 4A00C414CE; Mon, 20 Mar 2023 10:37:58 +0000 (UTC) DKIM-Filter: OpenDKIM Filter v2.11.0 smtp4.osuosl.org 4A00C414CE Received: from lf-lists.osuosl.org (localhost [127.0.0.1]) by lists.linuxfoundation.org (Postfix) with ESMTP id 1AB12C0071; Mon, 20 Mar 2023 10:37:58 +0000 (UTC) X-Original-To: ovs-dev@openvswitch.org Delivered-To: ovs-dev@lists.linuxfoundation.org Received: from smtp4.osuosl.org (smtp4.osuosl.org [140.211.166.137]) by lists.linuxfoundation.org (Postfix) with ESMTP id 60E73C0032 for ; Mon, 20 Mar 2023 10:37:56 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp4.osuosl.org (Postfix) with ESMTP id 2EA0D41484 for ; Mon, 20 Mar 2023 10:37:56 +0000 (UTC) DKIM-Filter: OpenDKIM Filter v2.11.0 smtp4.osuosl.org 2EA0D41484 X-Virus-Scanned: amavisd-new at osuosl.org Received: from smtp4.osuosl.org ([127.0.0.1]) by localhost (smtp4.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 4TJX92xxnpJM for ; Mon, 20 Mar 2023 10:37:54 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.8.0 DKIM-Filter: OpenDKIM Filter v2.11.0 smtp4.osuosl.org 1E3DA40905 Received: from relay9-d.mail.gandi.net (relay9-d.mail.gandi.net [IPv6:2001:4b98:dc4:8::229]) by smtp4.osuosl.org (Postfix) with ESMTPS id 1E3DA40905 for ; Mon, 20 Mar 2023 10:37:53 +0000 (UTC) Received: (Authenticated sender: i.maximets@ovn.org) by mail.gandi.net (Postfix) with ESMTPSA id E5B8CFF802; Mon, 20 Mar 2023 10:37:50 +0000 (UTC) From: Ilya Maximets To: ovs-dev@openvswitch.org Date: Mon, 20 Mar 2023 11:38:07 +0100 Message-Id: <20230320103809.3121679-2-i.maximets@ovn.org> X-Mailer: git-send-email 2.39.2 In-Reply-To: <20230320103809.3121679-1-i.maximets@ovn.org> References: <20230320103809.3121679-1-i.maximets@ovn.org> MIME-Version: 1.0 Cc: Nadia Pinaeva , Ilya Maximets , Dumitru Ceara Subject: [ovs-dev] [PATCH ovn v2 1/3] 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. "ip4.src != {172.168.13.0/24, 172.168.14.0/24, 172.168.15.0/24}" Brefore: $ ./tests/ovstest test-ovn expr-to-flows <<< "$expr" | wc -l 2894 After: $ ./tests/ovstest test-ovn expr-to-flows <<< "$expr" | wc -l 23 Reported-at: https://bugzilla.redhat.com/show_bug.cgi?id=2177197 Reported-by: Nadia Pinaeva Signed-off-by: Ilya Maximets --- lib/expr.c | 129 +++++++++++++++++++++++++++++---------------------- tests/ovn.at | 12 +++++ 2 files changed, 86 insertions(+), 55 deletions(-) diff --git a/lib/expr.c b/lib/expr.c index 0a6f7e574..f9f3b6991 100644 --- a/lib/expr.c +++ b/lib/expr.c @@ -15,21 +15,23 @@ */ #include +#include "bitmap.h" #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 +2522,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 || symbol->level != EXPR_L_ORDINAL) { + 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 +2749,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 +2768,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); } diff --git a/tests/ovn.at b/tests/ovn.at index fa786112c..de239dd69 100644 --- a/tests/ovn.at +++ b/tests/ovn.at @@ -822,6 +822,18 @@ ip,nw_src=10.0.0.1,nw_dst=172.27.0.65 ip,nw_src=10.0.0.2,nw_dst=172.27.0.65 ip,nw_src=10.0.0.3,nw_dst=172.27.0.65 ]) +AT_CHECK([expr_to_flow 'ip4.src == 172.168.13.0/16 && ip4.src != {172.168.13.0/24, 172.168.14.0/24}'], [0], [dnl +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.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.3.0/255.255.3.0 +ip,nw_src=172.168.32.0/255.255.32.0 +ip,nw_src=172.168.64.0/255.255.64.0 +]) +dnl Negative match flow explosion. +AT_CHECK([test $(expr_to_flow 'ip4.src != {172.168.13.0/24, 172.168.14.0/24, 172.168.15.0/24}' | wc -l) -le 30]) AT_CLEANUP AT_SETUP([converting expressions to flows -- port groups])