From patchwork Wed Apr 5 19:48:11 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ilya Maximets X-Patchwork-Id: 1765719 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 4PsFXy2sP5z1yYP for ; Thu, 6 Apr 2023 05:48:02 +1000 (AEST) Received: from localhost (localhost [127.0.0.1]) by smtp1.osuosl.org (Postfix) with ESMTP id 525318211A; Wed, 5 Apr 2023 19:48:00 +0000 (UTC) DKIM-Filter: OpenDKIM Filter v2.11.0 smtp1.osuosl.org 525318211A 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 B9Yq64ITN5cT; Wed, 5 Apr 2023 19:47:59 +0000 (UTC) Received: from lists.linuxfoundation.org (lf-lists.osuosl.org [140.211.9.56]) by smtp1.osuosl.org (Postfix) with ESMTPS id A2C3381422; Wed, 5 Apr 2023 19:47:58 +0000 (UTC) DKIM-Filter: OpenDKIM Filter v2.11.0 smtp1.osuosl.org A2C3381422 Received: from lf-lists.osuosl.org (localhost [127.0.0.1]) by lists.linuxfoundation.org (Postfix) with ESMTP id 79168C0037; Wed, 5 Apr 2023 19:47: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 C73EFC002F for ; Wed, 5 Apr 2023 19:47:56 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp4.osuosl.org (Postfix) with ESMTP id 8FB4C41950 for ; Wed, 5 Apr 2023 19:47:56 +0000 (UTC) DKIM-Filter: OpenDKIM Filter v2.11.0 smtp4.osuosl.org 8FB4C41950 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 VIZ4AO1nqLHk for ; Wed, 5 Apr 2023 19:47:55 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.8.0 DKIM-Filter: OpenDKIM Filter v2.11.0 smtp4.osuosl.org 06AF841926 Received: from relay2-d.mail.gandi.net (relay2-d.mail.gandi.net [217.70.183.194]) by smtp4.osuosl.org (Postfix) with ESMTPS id 06AF841926 for ; Wed, 5 Apr 2023 19:47:54 +0000 (UTC) Received: (Authenticated sender: i.maximets@ovn.org) by mail.gandi.net (Postfix) with ESMTPSA id 88DA840004; Wed, 5 Apr 2023 19:47:52 +0000 (UTC) From: Ilya Maximets To: ovs-dev@openvswitch.org Date: Wed, 5 Apr 2023 21:48:11 +0200 Message-Id: <20230405194813.548329-1-i.maximets@ovn.org> X-Mailer: git-send-email 2.39.2 MIME-Version: 1.0 Cc: Dumitru Ceara , Ilya Maximets Subject: [ovs-dev] [PATCH ovn v4 0/2] expr: Optimize 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" This patch set covers removal of expressions which are subsets of other wider expressions. This allows to avoid flow explosion in case of negative matches. More details are in commit messages. Version 2: * Became a patch set. * Added tests and missing bitmap.h include. * Code switched to work with bitwise maskable fields only (ORDINAL). * Added a new patch to combine smaller expressions into wider ones. * Added a patch to fix a crash uncovered with expression aggregation. Version 3: * Dropped patch 3 for performance reasons for now, because it doesn't allow to make use of I-P in many cases. * Patch 1 re-worked to not cause performance issues for normal address sets generated in OVN. * Performance of the patch 1 significantly improved by not perfroming a full n^2 search and not comparing huge empty parts of subvalues. The patch became a bit less straightforward, but I hope it's still fairly readable. Version 4: * Added extra comments. * Added ACK from Han to patch 2. * Re-worked path shortening (next[]) to track the last non-NULL entry. * Restricted superset optmization to expressions that do not track address sets. To preserve ability to use I-P. [Han] Ilya Maximets (2): expr: Remove supersets from OR expressions. expr: Avoid crash if all sub-expressions crushed down to 'true'. include/ovn/expr.h | 1 + lib/expr.c | 255 +++++++++++++++++++++++++++++++++++---------- tests/ovn.at | 12 +++ 3 files changed, 212 insertions(+), 56 deletions(-)