From patchwork Wed Apr 5 19:48:12 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ilya Maximets X-Patchwork-Id: 1765720 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.138; helo=smtp1.osuosl.org; envelope-from=ovs-dev-bounces@openvswitch.org; receiver=) Received: from smtp1.osuosl.org (smtp1.osuosl.org [140.211.166.138]) (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 4PsFY3158Fz1yYP for ; Thu, 6 Apr 2023 05:48:07 +1000 (AEST) Received: from localhost (localhost [127.0.0.1]) by smtp1.osuosl.org (Postfix) with ESMTP id CFCA58216F; Wed, 5 Apr 2023 19:48:03 +0000 (UTC) DKIM-Filter: OpenDKIM Filter v2.11.0 smtp1.osuosl.org CFCA58216F X-Virus-Scanned: amavisd-new at osuosl.org Received: from smtp1.osuosl.org ([127.0.0.1]) by localhost (smtp1.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id nM7glPcSYDIE; Wed, 5 Apr 2023 19:48:02 +0000 (UTC) Received: from lists.linuxfoundation.org (lf-lists.osuosl.org [140.211.9.56]) by smtp1.osuosl.org (Postfix) with ESMTPS id 4050082130; Wed, 5 Apr 2023 19:48:01 +0000 (UTC) DKIM-Filter: OpenDKIM Filter v2.11.0 smtp1.osuosl.org 4050082130 Received: from lf-lists.osuosl.org (localhost [127.0.0.1]) by lists.linuxfoundation.org (Postfix) with ESMTP id 14BF6C008A; Wed, 5 Apr 2023 19:48:00 +0000 (UTC) X-Original-To: ovs-dev@openvswitch.org Delivered-To: ovs-dev@lists.linuxfoundation.org Received: from smtp3.osuosl.org (smtp3.osuosl.org [IPv6:2605:bc80:3010::136]) by lists.linuxfoundation.org (Postfix) with ESMTP id 4A777C008A for ; Wed, 5 Apr 2023 19:47:59 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp3.osuosl.org (Postfix) with ESMTP id 1894460F2F for ; Wed, 5 Apr 2023 19:47:59 +0000 (UTC) DKIM-Filter: OpenDKIM Filter v2.11.0 smtp3.osuosl.org 1894460F2F 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 TIkKumhwOkm6 for ; Wed, 5 Apr 2023 19:47:57 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.8.0 DKIM-Filter: OpenDKIM Filter v2.11.0 smtp3.osuosl.org 47C8D60BF1 Received: from relay2-d.mail.gandi.net (relay2-d.mail.gandi.net [IPv6:2001:4b98:dc4:8::222]) by smtp3.osuosl.org (Postfix) with ESMTPS id 47C8D60BF1 for ; Wed, 5 Apr 2023 19:47:57 +0000 (UTC) Received: (Authenticated sender: i.maximets@ovn.org) by mail.gandi.net (Postfix) with ESMTPSA id 8ABBF40005; Wed, 5 Apr 2023 19:47:54 +0000 (UTC) From: Ilya Maximets To: ovs-dev@openvswitch.org Date: Wed, 5 Apr 2023 21:48:12 +0200 Message-Id: <20230405194813.548329-2-i.maximets@ovn.org> X-Mailer: git-send-email 2.39.2 In-Reply-To: <20230405194813.548329-1-i.maximets@ovn.org> References: <20230405194813.548329-1-i.maximets@ovn.org> MIME-Version: 1.0 Cc: Nadia Pinaeva , Dumitru Ceara , Ilya Maximets Subject: [ovs-dev] [PATCH ovn v4 1/2] 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". In addition to removal of exact duplicates introducing scan and removal of supersets of other existing sub-expressions to reduce the amount of generated flows. This adds extra computations, 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 Superset lookups are performed only if there are expressions with more bits in the mask than in the current one. So, there is no extra cost for equality checks on normal address sets, like port group sets, where all the IPs are exect matches or have the same prefix length otherwise. Also, the superset optimization is not performed if expression is tracking an address set. This is done in order to preserve ability to use address set I-P even if the user specified overlapping addresses and CIDRs. Note: having exact duplicates in user-specified sets is highly unlikely, because of database constraints. Use of bitmaps instead of subvalue functions significantly speeds up processing since most of the subvalue space is an all-zero empty space. Reported-at: https://bugzilla.redhat.com/show_bug.cgi?id=2177197 Reported-by: Nadia Pinaeva Signed-off-by: Ilya Maximets --- include/ovn/expr.h | 1 + lib/expr.c | 253 +++++++++++++++++++++++++++++++++++---------- tests/ovn.at | 12 +++ 3 files changed, 211 insertions(+), 55 deletions(-) diff --git a/include/ovn/expr.h b/include/ovn/expr.h index 80d95ff67..c48f82398 100644 --- a/include/ovn/expr.h +++ b/include/ovn/expr.h @@ -384,6 +384,7 @@ struct expr { struct { union mf_subvalue value; union mf_subvalue mask; + size_t mask_n_bits; }; }; } cmp; diff --git a/lib/expr.c b/lib/expr.c index 0a6f7e574..0cf54d486 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,198 @@ crush_and_string(struct expr *expr, const struct expr_symbol *symbol) return expr_fix(expr); } +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 if (a->cmp.mask_n_bits != b->cmp.mask_n_bits) { + return a->cmp.mask_n_bits < b->cmp.mask_n_bits ? -1 : 1; + } 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); +} + +/* Similar to mf_subvalue_intersect(), but only checks the possibility of + * intersection without producing a result. */ +static bool +expr_bitmap_intersect_check(const unsigned long *a_value, + const unsigned long *a_mask, + const unsigned long *b_value, + const unsigned long *b_mask, + size_t bit_width) +{ + for (size_t i = 0; i < bitmap_n_longs(bit_width); i++) { + if ((a_value[i] ^ b_value[i]) & (a_mask[i] & b_mask[i])) { + return false; + } + } + return true; +} + +/* 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) +{ + ovs_assert(expr->type == EXPR_T_OR); + + /* Calculate offset within subfield and a width that can be used + * in a bitmap. */ + const size_t sz = CHAR_BIT * sizeof expr->cmp.value.be64[0]; + const size_t bit_width = ROUND_UP(symbol->width, sz); + const size_t ofs = ARRAY_SIZE(expr->cmp.value.be64) - bit_width / sz; + + /* Sort subexpressions by number of bits in the mask, value and the mask + * itself, to bring together duplicates and have expressions ordered by + * mask sizes. */ + size_t n = ovs_list_size(&expr->andor); + struct expr **subs = xmalloc(n * sizeof *subs); + bool modified = false; + /* Linked list over the 'subs' array to quickly skip deleted elements, + * i.e. the index of the next potentially non-NULL element. */ + size_t *next = xmalloc(n * sizeof *next); + + size_t i = 0, j, max_n_bits = 0; + struct expr *sub; + LIST_FOR_EACH (sub, node, &expr->andor) { + if (symbol->width) { + const unsigned long *sub_mask; + + sub_mask = (unsigned long *) &sub->cmp.mask.be64[ofs]; + sub->cmp.mask_n_bits = bitmap_count1(sub_mask, bit_width); + max_n_bits = MAX(max_n_bits, sub->cmp.mask_n_bits); + } + next[i] = i + 1; /* Link 'i' -> 'i + 1'. */ + subs[i++] = sub; + } + ovs_assert(i == n); + + qsort(subs, n, sizeof *subs, compare_cmps_cb); + + /* Eliminate duplicates. */ + size_t last = 0; + for (i = 1; i < n; i++) { + if (compare_cmps_3way(subs[last], subs[i])) { + next[last] = i; + last = i; + } else { + expr_destroy(subs[i]); + subs[i] = NULL; + modified = true; + } + } + + if (!symbol->width || symbol->level != EXPR_L_ORDINAL + || (!modified && expr->as_name)) { + /* Not a fully maskable field or this expression is tracking an + * address set. Don't try to optimize to preserve address set I-P. */ + goto done; + } + + /* Build a mask size index. 'mask_index[n_bits]' is an index in 'subs', + * where expressions with 'n_bits' bits in mask start. */ + size_t *mask_index, n_bits; + size_t index_size = (max_n_bits + 2) * sizeof *mask_index; + + mask_index = xmalloc(index_size); + /* Initialize to maximum unsigned values. */ + memset(mask_index, 0xff, index_size); + + for (i = 0; i < n; i = next[i]) { + if (subs[i]) { + n_bits = subs[i]->cmp.mask_n_bits; + mask_index[n_bits] = MIN(mask_index[n_bits], i); + } + } + + /* Fill the gaps, so they point to an index with more bits. */ + for (i = max_n_bits; i > 0; i--) { + mask_index[i] = MIN(mask_index[i], mask_index[i + 1]); + } + + /* Find and eliminate supersets. */ + for (i = 0; i < n; i = next[i]) { + if (!subs[i]) { + continue; + } + /* 'subs' are sorted based on the number of bits in the mask. + * For an expression to be a subset, it has to have more bits. */ + n_bits = subs[i]->cmp.mask_n_bits; + if (mask_index[n_bits + 1] > n) { + break; + } + for (last = 0, j = mask_index[n_bits + 1]; j < n; j = next[j]) { + struct expr *a = subs[i], *b = subs[j]; + + ovs_assert(i != j); + if (!b) { + continue; + } + + const unsigned long *a_value, *a_mask, *b_value, *b_mask; + a_value = (unsigned long *) &a->cmp.value.be64[ofs]; + b_value = (unsigned long *) &b->cmp.value.be64[ofs]; + a_mask = (unsigned long *) &a->cmp.mask.be64[ofs]; + b_mask = (unsigned long *) &b->cmp.mask.be64[ofs]; + + if (expr_bitmap_intersect_check(a_value, a_mask, b_value, b_mask, + bit_width) + && bitmap_is_superset(b_mask, a_mask, bit_width)) { + /* 'a' is the same expression with a smaller mask. */ + expr_destroy(subs[j]); + subs[j] = NULL; + modified = true; + + /* Shorten the path for the next round. */ + if (last) { + next[last] = next[j]; /* Skip the 'j'. */ + } else { + /* The first element with 'n_bits + 1' bits was removed. */ + mask_index[n_bits + 1] = next[j]; + } + } else { + last = j; /* 'j' is the last non-NULL element seen. */ + } + } + } + free(mask_index); + +done: + ovs_list_init(&expr->andor); + for (i = 0; i < n; i++) { + if (subs[i]) { + ovs_list_push_back(&expr->andor, &subs[i]->node); + } + } + + if (modified) { + /* Members modified, so untrack address set. */ + free(expr->as_name); + expr->as_name = NULL; + } + + free(next); + free(subs); + return expr; +} + /* Implementation of crush_cmps() for expr->type == EXPR_T_AND and a * numeric-typed 'symbol'. */ static struct expr * @@ -2679,31 +2873,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 +2892,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 a892691ca..7dfe0df24 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])