From patchwork Fri May 16 21:25:15 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ilya Maximets X-Patchwork-Id: 2086942 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.137; helo=smtp4.osuosl.org; envelope-from=ovs-dev-bounces@openvswitch.org; receiver=patchwork.ozlabs.org) Received: from smtp4.osuosl.org (smtp4.osuosl.org [140.211.166.137]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (secp384r1) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4Zzg8v70tvz1yPv for ; Sat, 17 May 2025 07:25:19 +1000 (AEST) Received: from localhost (localhost [127.0.0.1]) by smtp4.osuosl.org (Postfix) with ESMTP id 7456C415B5; Fri, 16 May 2025 21:25:33 +0000 (UTC) X-Virus-Scanned: amavis at osuosl.org Received: from smtp4.osuosl.org ([127.0.0.1]) by localhost (smtp4.osuosl.org [127.0.0.1]) (amavis, port 10024) with ESMTP id RZN1r03nVOKO; Fri, 16 May 2025 21:25:32 +0000 (UTC) X-Comment: SPF check N/A for local connections - client-ip=2605:bc80:3010:104::8cd3:938; helo=lists.linuxfoundation.org; envelope-from=ovs-dev-bounces@openvswitch.org; receiver= DKIM-Filter: OpenDKIM Filter v2.11.0 smtp4.osuosl.org 9520240758 Received: from lists.linuxfoundation.org (lf-lists.osuosl.org [IPv6:2605:bc80:3010:104::8cd3:938]) by smtp4.osuosl.org (Postfix) with ESMTPS id 9520240758; Fri, 16 May 2025 21:25:32 +0000 (UTC) Received: from lf-lists.osuosl.org (localhost [127.0.0.1]) by lists.linuxfoundation.org (Postfix) with ESMTP id 74DA9C007B; Fri, 16 May 2025 21:25:32 +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 8FA8DC007B for ; Fri, 16 May 2025 21:25:30 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp4.osuosl.org (Postfix) with ESMTP id 6637F40798 for ; Fri, 16 May 2025 21:25:30 +0000 (UTC) X-Virus-Scanned: amavis at osuosl.org Received: from smtp4.osuosl.org ([127.0.0.1]) by localhost (smtp4.osuosl.org [127.0.0.1]) (amavis, port 10024) with ESMTP id b51DsvAjzDIu for ; Fri, 16 May 2025 21:25:30 +0000 (UTC) Received-SPF: Pass (mailfrom) identity=mailfrom; client-ip=209.85.218.66; helo=mail-ej1-f66.google.com; envelope-from=i.maximets.ovn@gmail.com; receiver= DMARC-Filter: OpenDMARC Filter v1.4.2 smtp4.osuosl.org 86B4140758 Authentication-Results: smtp4.osuosl.org; dmarc=none (p=none dis=none) header.from=ovn.org DKIM-Filter: OpenDKIM Filter v2.11.0 smtp4.osuosl.org 86B4140758 Received: from mail-ej1-f66.google.com (mail-ej1-f66.google.com [209.85.218.66]) by smtp4.osuosl.org (Postfix) with ESMTPS id 86B4140758 for ; Fri, 16 May 2025 21:25:29 +0000 (UTC) Received: by mail-ej1-f66.google.com with SMTP id a640c23a62f3a-ad52dfe06ceso153724366b.3 for ; Fri, 16 May 2025 14:25:29 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1747430728; x=1748035528; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=G1OXtlGzF4JpFddkKhiHn7aOl6Z1JxodhYxG3KKLaDQ=; b=scxy2H9HPp5u/y+dKdPtcs1o/e62ITFt6oPwRoE6IpuYgI/dAz+qAUy7yHDdy627Pd NBfEjdi3c3GRFaVK4YtNKbtff+VXRv8McXIhfqSS1CiVM1PPGuinr5WlHqrEZSUTQ1Xx dDGH3CJtACguxFk7BEJBSch0OkZsGT23Y3YMjMQuLjPMxPYdIADHRBIZl8Lc5A2BhsiR E/GUS235Utw8Idb0xbbRulmZZe/8w2GvmFIXaJ3wQzXrOajmtoyi56DSbx/id/amgXP3 x6xIE6CcRRGr8N6HFOLCdfDrt/wD1dw2oXSZ+9PB+ZC4rlGeft89AR3s6CamCi36CsL8 0lXg== X-Gm-Message-State: AOJu0YwYL8GUBv+73GtLrEmnRlKzyqnda85J90iKneOt1HmTN2bdXmCD TOeGPVLCM37i31FHe3VqQaHL0/Jp/WRBeuvluR55+rjk4Iuog8qLYfdaoz5C65XJ X-Gm-Gg: ASbGnctTw+LS0rqx7IpRwI0puXXx+ClnoG5SVnJJ9DJdZnasgyaTp9ZkMWKcEUhlp0y T65wmdsxRLsvHQQfSofYS4IvMXMZQU3KJMmL/KT+JgLG/S2WzMuc08oXOP0kzt0Yj49gboDrLOr hlOrz53SNVuY3nXzB4AbwjvxtDI8GMcmr1UG1g5rl1USoKJi+30vuxxtzIwCu6QPyw2V8CXftzq Euu8ykXX7iQ3EPLpk+/iWh5xn2Jxjji59Xhcom6Cn1PBE6sG4n9EzGfwmKiHv6AHevl0H5b/dNy iP8ZkfgB7Asacmuix4BLYHekiR/xoTrOXv/jAh5HgVZ7utg3/LzzqXAPZbqirN7b/xIKccsGPcB UiPt6j5UDPXooTg0z X-Google-Smtp-Source: AGHT+IH6YaYFne+Zh4s7u7TmjGa85o3HURyC3/4jxTluPalVijCDpB5udk19qRywt4DZO+aDk6MvEw== X-Received: by 2002:a17:907:97c1:b0:ad5:50da:691f with SMTP id a640c23a62f3a-ad550da7c37mr4411666b.59.1747430727298; Fri, 16 May 2025 14:25:27 -0700 (PDT) Received: from im-t490s.redhat.com (78-80-121-182.customers.tmcz.cz. [78.80.121.182]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-ad52d490789sm212047266b.130.2025.05.16.14.25.26 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 16 May 2025 14:25:26 -0700 (PDT) From: Ilya Maximets To: ovs-dev@openvswitch.org Date: Fri, 16 May 2025 23:25:15 +0200 Message-ID: <20250516212521.733714-2-i.maximets@ovn.org> X-Mailer: git-send-email 2.49.0 In-Reply-To: <20250516212521.733714-1-i.maximets@ovn.org> References: <20250516212521.733714-1-i.maximets@ovn.org> MIME-Version: 1.0 Subject: [ovs-dev] [PATCH 1/3] tests: classifier: Fix the rule number check during trie verification. X-BeenThere: ovs-dev@openvswitch.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: Ilya Maximets Errors-To: ovs-dev-bounces@openvswitch.org Sender: "dev" Same rule can be in multiple prefix trees and so it is possible that the total number of rules in all trees exceeds the total number of rules in the classifier. But the number of rules in a single prefix tree still can't exceed the total number of rules in the classifier. Move the check accordingly. Note: checkpatch complains about usage of the assert(), but it is everywhere in this file and so, not changing in just this one place. Fixes: f358a2cb2e54 ("lib/classifier: RCUify prefix trie code.") Signed-off-by: Ilya Maximets Acked-by: Eelco Chaudron --- tests/test-classifier.c | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/tests/test-classifier.c b/tests/test-classifier.c index 2c1604a01..ee022ba1e 100644 --- a/tests/test-classifier.c +++ b/tests/test-classifier.c @@ -509,15 +509,15 @@ static void verify_tries(struct classifier *cls) OVS_NO_THREAD_SAFETY_ANALYSIS { - unsigned int n_rules = 0; + unsigned int n_rules; int i; for (i = 0; i < cls->n_tries; i++) { const struct mf_field * cls_field = ovsrcu_get(struct mf_field *, &cls->tries[i].field); - n_rules += trie_verify(&cls->tries[i].root, 0, cls_field->n_bits); + n_rules = trie_verify(&cls->tries[i].root, 0, cls_field->n_bits); + assert(n_rules <= cls->n_rules); } - assert(n_rules <= cls->n_rules); } static void From patchwork Fri May 16 21:25:16 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ilya Maximets X-Patchwork-Id: 2086943 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=patchwork.ozlabs.org) 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 (secp384r1) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4Zzg936zT5z1yPv for ; Sat, 17 May 2025 07:25:27 +1000 (AEST) Received: from localhost (localhost [127.0.0.1]) by smtp4.osuosl.org (Postfix) with ESMTP id 1B75E419BA; Fri, 16 May 2025 21:25:37 +0000 (UTC) X-Virus-Scanned: amavis at osuosl.org Received: from smtp4.osuosl.org ([127.0.0.1]) by localhost (smtp4.osuosl.org [127.0.0.1]) (amavis, port 10024) with ESMTP id T447hJnDH3as; Fri, 16 May 2025 21:25:35 +0000 (UTC) X-Comment: SPF check N/A for local connections - client-ip=2605:bc80:3010:104::8cd3:938; helo=lists.linuxfoundation.org; envelope-from=ovs-dev-bounces@openvswitch.org; receiver= DKIM-Filter: OpenDKIM Filter v2.11.0 smtp4.osuosl.org 84D0541988 Received: from lists.linuxfoundation.org (lf-lists.osuosl.org [IPv6:2605:bc80:3010:104::8cd3:938]) by smtp4.osuosl.org (Postfix) with ESMTPS id 84D0541988; Fri, 16 May 2025 21:25:35 +0000 (UTC) Received: from lf-lists.osuosl.org (localhost [127.0.0.1]) by lists.linuxfoundation.org (Postfix) with ESMTP id 31325C0923; Fri, 16 May 2025 21:25:35 +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 C8D1AC007B for ; Fri, 16 May 2025 21:25:33 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp3.osuosl.org (Postfix) with ESMTP id C5B0E613A5 for ; Fri, 16 May 2025 21:25:33 +0000 (UTC) X-Virus-Scanned: amavis at osuosl.org Received: from smtp3.osuosl.org ([127.0.0.1]) by localhost (smtp3.osuosl.org [127.0.0.1]) (amavis, port 10024) with ESMTP id jBsJO0-jc0bc for ; Fri, 16 May 2025 21:25:32 +0000 (UTC) Received-SPF: Pass (mailfrom) identity=mailfrom; client-ip=209.85.218.65; helo=mail-ej1-f65.google.com; envelope-from=i.maximets.ovn@gmail.com; receiver= DMARC-Filter: OpenDMARC Filter v1.4.2 smtp3.osuosl.org 71EB161387 Authentication-Results: smtp3.osuosl.org; dmarc=none (p=none dis=none) header.from=ovn.org DKIM-Filter: OpenDKIM Filter v2.11.0 smtp3.osuosl.org 71EB161387 Received: from mail-ej1-f65.google.com (mail-ej1-f65.google.com [209.85.218.65]) by smtp3.osuosl.org (Postfix) with ESMTPS id 71EB161387 for ; Fri, 16 May 2025 21:25:31 +0000 (UTC) Received: by mail-ej1-f65.google.com with SMTP id a640c23a62f3a-ad5297704aaso323604866b.2 for ; Fri, 16 May 2025 14:25:31 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1747430729; x=1748035529; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=XoDliIj/zyssnzlhn1c7Jz5ie0aFJ1L0N+i6ZXFyRj8=; b=feuaHQEEtor93rlUwu12oyrW1WMJ87m3I9qhjdDJUwtJd/87wrub60qiZ7sgMjncv5 tihHLQ+zwbNrg4ExBgmjFsEMgDaczn4MEyjwpuTKVc6Pc8UP7FSTVsCcDFv2oP/QIFhH LLYivqG9uvl3g/tLfGRGiveMsVkz9uIWZKwIZZabKPO1RBy4m7gkjIGrYSuM1+tShdOW wPjyJJz1XvS3BzHMqCPa9Hu1JZUILVWOURzSiDxo9YPZndiOGzr0Ab6oNe9x8eqB1Qcb 5wezdQyR2eDVwBBLjimKgfKtWhVl48qtjLxVI9Sdf1/TCMUQm6IunfqvPTbaqRNUtcxi jUVg== X-Gm-Message-State: AOJu0Yy3LIlCNNzDveDpS6FQThD11qh+QF2gqf3yaXVFu/UaLrPkIcXF FmG/N1sWH90mGPw2n+eeLMGQidntKatPg7CSGTgPZSPmay4gZzeRCQYe9hDtHrVM X-Gm-Gg: ASbGnctmDI4bJVOoTaD8EuUgTnvANxoeSn2monGx1zqVBuuqL+CKCUEyI2V51TCIyGI dfMrdixACaGvusHnJq5FH6DsWS1XOSGSqWM+fl94gBEV3HC/Rrg11Q5Z5XlfYRcr7bqAyG0MfbP KYOdiJAonDNegsRnh6pzjs9WeVvBbt/X8igw1423l6p2vqIeAL7rQVNCgJfHe8yGioyzsM7eVpa LzlXto0rtteYV/HsZ6SqACb/3xgdFt5QJS92/iXFMcLlT/O/v+7Kn/ZYMuF7t4CMLSaFmTndNm8 rfMVOCRwj/5T2OELsAALt4LyzFuwP5XA7hA2oBzZy/F5+zt3coZ9smRbQouL0gBEtthbR6lsTlv PuSwHu0/2O8hsm2ZRH1IYakcD+yk= X-Google-Smtp-Source: AGHT+IG3dHY/5fZIUjsxyPLycsKAIkfbt6RTP+v5yguvqYT2qUotttVaWReJSeqmMBpzMVByNZ7Idw== X-Received: by 2002:a17:907:3d0c:b0:ad2:378f:99ef with SMTP id a640c23a62f3a-ad52d45ad86mr476681566b.8.1747430728895; Fri, 16 May 2025 14:25:28 -0700 (PDT) Received: from im-t490s.redhat.com (78-80-121-182.customers.tmcz.cz. [78.80.121.182]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-ad52d490789sm212047266b.130.2025.05.16.14.25.28 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 16 May 2025 14:25:28 -0700 (PDT) From: Ilya Maximets To: ovs-dev@openvswitch.org Date: Fri, 16 May 2025 23:25:16 +0200 Message-ID: <20250516212521.733714-3-i.maximets@ovn.org> X-Mailer: git-send-email 2.49.0 In-Reply-To: <20250516212521.733714-1-i.maximets@ovn.org> References: <20250516212521.733714-1-i.maximets@ovn.org> MIME-Version: 1.0 Subject: [ovs-dev] [PATCH 2/3] classifier: Fix race for prefix tree configuration. X-BeenThere: ovs-dev@openvswitch.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: Ilya Maximets Errors-To: ovs-dev-bounces@openvswitch.org Sender: "dev" The thread fence in the classifier is supposed to ensure that when the subtable->trie_plen is updated, the actual prefix tree is ready to be used. On the write side in trie_init(), the fence is between the tree configuration and the 'trie_plen' update. On the reader's side however, the fence is at the beginning of the classifier_lookup__(), and both reads of the 'trie_plen' and the accesses to the tree itself are happening afterwards. And since both types of the reads are on the same side of the fence, the fence is kind of pointless and doesn't guarantee any memory ordering. So, readers can be accessing partially initialized prefix trees. Another problem with the configuration is that cls->n_tries is updated without any synchronization as well. The comment on the fence says that it also synchronizes for the cls->n_tries, but that doesn't make a lot of sense. In practice, cls->n_tries is read multiple times throughout the classifier_lookup__() and each of these reads may give a different value if there is a concurrent update, causing the reader to access trees that are not initialized or in the middle of being destroyed, leading to OVS crashes while the user updates the flow table prefixes. First thing that needs to be fixed here is to only read cls->n_tries once to avoid obvious crashes with access to uninitialized trie_ctx[] entries. The second thing is that we need a proper memory synchronization that will guarantee that our prefix trees are fully initialized when readers access them. In the current logic we would need to issue a thread fence after every read of a subtable->trie_plen value, i.e., we'd need a fence per subtable lookup. This would be very expensive and wasteful, considering the prefix tree configuration normally happens only once somewhere at startup. What we can do instead is to convert cls->n_tries into atomic and use it as a synchronization point: Writer (classifier_set_prefix_fields): 1. Before making any changes, set cls->n_tries to zero. Relaxed memory order can be used here, because we'll have a full memory barrier at the next step. 2. ovsrcu_synchronize() to wait for all threads to stop using tries. 3. Update tries while nobody is using them. 4. Set cls->n_tries to a new value with memory_order_release. Reader (classifier_lookup): 1. Read the cls->n_tries with the memory_order_acquire. 2. Use that once read value throughout. RCU in this scenario will ensure that every thread no longer uses the prefix trees when we're about to change them. The acquire-release semantics on the cls->n_tries just saves us from calling the ovsrcu_synchronize() the second time once we're done with the whole reconfiguration. We're just updating the number and making all the previous changes visible on CPUs that acquire it. Alternative solution might be to go full RCU and make the array of trees itself RCU-protected. This way we would not need to do any extra RCU synchronization or managing the memory ordering. However, that would mean having multiple layers of RCU with trees and rules in them potentially surviving multiple grace periods, which I would like to avoid, if possible. Previous code was also trying to be smart and not disable prefix tree lookups for prefixes that are not changing. We're sacrificing this functionality in the name of simpler code. Attempt to make that work would either require a full conversion to RCU or a per-subtable synchronization. Lookups can be done without the prefix match optimizations for a brief period of time. This doesn't affect correctness of the resulted datapath flows. In the actual implementation instead of dropping cls->n_tries to zero at step one, we can keep the access to the first N tries that are not going to change by setting the cls->n_tries to the index of the first trie that will be updated. So, we'll not be disabling all the prefix match optimizations completely. There was an attempt to solve this problem already in commit: a6117059904b ("classifier: Prevent tries vs n_tries race leading to NULL dereference.") But it was focused on one particular crash and didn't take into account a wider issue with the memory ordering on these trees in general. The changes made in that commit are mostly reverted as not needed anymore. Fixes: f358a2cb2e54 ("lib/classifier: RCUify prefix trie code.") Reported-at: https://mail.openvswitch.org/pipermail/ovs-dev/2025-April/422765.html Reported-by: Numan Siddique Signed-off-by: Ilya Maximets Acked-by: Eelco Chaudron --- lib/classifier.c | 196 ++++++++++++++++++++-------------------- lib/classifier.h | 10 +- tests/test-classifier.c | 14 +-- 3 files changed, 112 insertions(+), 108 deletions(-) diff --git a/lib/classifier.c b/lib/classifier.c index 55f23b976..7efa15022 100644 --- a/lib/classifier.c +++ b/lib/classifier.c @@ -115,7 +115,7 @@ static const struct cls_match *find_match_wc(const struct cls_subtable *, ovs_version_t version, const struct flow *, struct trie_ctx *, - unsigned int n_tries, + uint32_t n_tries, struct flow_wildcards *); static struct cls_match *find_equal(const struct cls_subtable *, const struct miniflow *, uint32_t hash); @@ -149,7 +149,7 @@ static unsigned int trie_lookup(const struct cls_trie *, const struct flow *, static unsigned int trie_lookup_value(const rcu_trie_ptr *, const ovs_be32 value[], ovs_be32 plens[], unsigned int value_bits); -static void trie_destroy(rcu_trie_ptr *); +static void trie_destroy(struct cls_trie *); static void trie_insert(struct cls_trie *, const struct cls_rule *, int mlen); static void trie_insert_prefix(rcu_trie_ptr *, const ovs_be32 *prefix, int mlen); @@ -334,10 +334,8 @@ classifier_init(struct classifier *cls, const uint8_t *flow_segments) cls->flow_segments[cls->n_flow_segments++] = *flow_segments++; } } - cls->n_tries = 0; - for (int i = 0; i < CLS_MAX_TRIES; i++) { - trie_init(cls, i, NULL); - } + memset(cls->tries, 0, sizeof cls->tries); + atomic_store_explicit(&cls->n_tries, 0, memory_order_release); cls->publish = true; } @@ -349,10 +347,11 @@ classifier_destroy(struct classifier *cls) { if (cls) { struct cls_subtable *subtable; - int i; + uint32_t i, n_tries; - for (i = 0; i < cls->n_tries; i++) { - trie_destroy(&cls->tries[i].root); + atomic_read_relaxed(&cls->n_tries, &n_tries); + for (i = 0; i < n_tries; i++) { + trie_destroy(&cls->tries[i]); } CMAP_FOR_EACH (subtable, cmap_node, &cls->subtables_map) { @@ -370,11 +369,14 @@ classifier_set_prefix_fields(struct classifier *cls, const enum mf_field_id *trie_fields, unsigned int n_fields) { - const struct mf_field * new_fields[CLS_MAX_TRIES]; + const struct mf_field *new_fields[CLS_MAX_TRIES]; struct mf_bitmap fields = MF_BITMAP_INITIALIZER; - int i, n_tries = 0; + uint32_t i, n_tries = 0, old_n_tries; + uint32_t first_changed = 0; bool changed = false; + atomic_read_relaxed(&cls->n_tries, &old_n_tries); + for (i = 0; i < n_fields && n_tries < CLS_MAX_TRIES; i++) { const struct mf_field *field = mf_from_id(trie_fields[i]); if (field->flow_be32ofs < 0 || field->n_bits % 32) { @@ -393,52 +395,47 @@ classifier_set_prefix_fields(struct classifier *cls, bitmap_set1(fields.bm, trie_fields[i]); new_fields[n_tries] = NULL; - const struct mf_field *cls_field - = ovsrcu_get(struct mf_field *, &cls->tries[n_tries].field); - if (n_tries >= cls->n_tries || field != cls_field) { + if (n_tries >= old_n_tries || field != cls->tries[n_tries].field) { new_fields[n_tries] = field; + if (!changed) { + first_changed = n_tries; + } changed = true; } n_tries++; } - if (changed || n_tries < cls->n_tries) { - struct cls_subtable *subtable; - - /* Trie configuration needs to change. Disable trie lookups - * for the tries that are changing and wait all the current readers - * with the old configuration to be done. */ - changed = false; - CMAP_FOR_EACH (subtable, cmap_node, &cls->subtables_map) { - for (i = 0; i < cls->n_tries; i++) { - if ((i < n_tries && new_fields[i]) || i >= n_tries) { - if (subtable->trie_plen[i]) { - subtable->trie_plen[i] = 0; - changed = true; - } - } - } - } - /* Synchronize if any readers were using tries. The readers may - * temporarily function without the trie lookup based optimizations. */ - if (changed) { - /* ovsrcu_synchronize() functions as a memory barrier, so it does - * not matter that subtable->trie_plen is not atomic. */ - ovsrcu_synchronize(); + if (changed || n_tries < old_n_tries) { + if (!changed) { + /* Threre are no new or changed fields, only removing a few. */ + first_changed = n_tries; } + /* Trie configuration needs to change. Disable trie lookups and wait + * for all the current readers to be done with the old configuration. + * The readers may temporarily function without the trie lookup based + * optimizations. Keeping the few first entries that didn't change + * accessible. + * + * This store can be relaxed because ovsrcu_synchronize() functions as + * a memory barrier. */ + atomic_store_relaxed(&cls->n_tries, first_changed); + ovsrcu_synchronize(); - /* Now set up the tries. */ - for (i = 0; i < n_tries; i++) { + /* Now set up the tries for new and changed fields. */ + for (i = first_changed; i < n_tries; i++) { if (new_fields[i]) { + trie_destroy(&cls->tries[i]); trie_init(cls, i, new_fields[i]); } } /* Destroy the rest, if any. */ - for (; i < cls->n_tries; i++) { - trie_init(cls, i, NULL); + for (; i < old_n_tries; i++) { + trie_destroy(&cls->tries[i]); } - cls->n_tries = n_tries; + /* Re-enable trie lookups. Using release memory order, so all the + * previous stores are visible in the classifier_lookup(). */ + atomic_store_explicit(&cls->n_tries, n_tries, memory_order_release); return true; } @@ -451,18 +448,17 @@ trie_init(struct classifier *cls, int trie_idx, const struct mf_field *field) struct cls_trie *trie = &cls->tries[trie_idx]; struct cls_subtable *subtable; - if (trie_idx < cls->n_tries) { - trie_destroy(&trie->root); - } else { - ovsrcu_set_hidden(&trie->root, NULL); - } - ovsrcu_set_hidden(&trie->field, CONST_CAST(struct mf_field *, field)); + ovs_assert(field); + ovs_assert(!trie->field); + + trie->field = field; + ovsrcu_set_hidden(&trie->root, NULL); /* Add existing rules to the new trie. */ CMAP_FOR_EACH (subtable, cmap_node, &cls->subtables_map) { unsigned int plen; - plen = field ? minimask_get_prefix_len(&subtable->mask, field) : 0; + plen = minimask_get_prefix_len(&subtable->mask, field); if (plen) { struct cls_match *head; @@ -470,9 +466,7 @@ trie_init(struct classifier *cls, int trie_idx, const struct mf_field *field) trie_insert(trie, head->cls_rule, plen); } } - /* Initialize subtable's prefix length on this field. This will - * allow readers to use the trie. */ - atomic_thread_fence(memory_order_release); + /* Initialize subtable's prefix length on this field. */ subtable->trie_plen[trie_idx] = plen; } } @@ -527,10 +521,10 @@ classifier_replace(struct classifier *cls, const struct cls_rule *rule, struct cls_match *head; unsigned int mask_offset; size_t n_rules = 0; + uint32_t i, n_tries; uint8_t n_indices; uint32_t basis; uint32_t hash; - unsigned int i; /* 'new' is initially invisible to lookups. */ new = cls_match_alloc(rule, version, conjs, n_conjs); @@ -558,7 +552,8 @@ classifier_replace(struct classifier *cls, const struct cls_rule *rule, * * Concurrent readers might miss seeing the rule until this update, * which might require being fixed up by revalidation later. */ - for (i = 0; i < cls->n_tries; i++) { + atomic_read_relaxed(&cls->n_tries, &n_tries); + for (i = 0; i < n_tries; i++) { if (subtable->trie_plen[i]) { trie_insert(&cls->tries[i], rule, subtable->trie_plen[i]); } @@ -715,9 +710,9 @@ classifier_remove(struct classifier *cls, const struct cls_rule *cls_rule) struct cls_subtable *subtable; uint32_t basis = 0, hash, ihash[CLS_MAX_INDICES]; unsigned int mask_offset; + uint32_t i, n_tries; uint8_t n_indices; size_t n_rules; - unsigned int i; rule = get_cls_match_protected(cls_rule); if (!rule) { @@ -780,7 +775,8 @@ classifier_remove(struct classifier *cls, const struct cls_rule *cls_rule) trie_remove_prefix(&subtable->ports_trie, &masked_ports, subtable->ports_mask_len); } - for (i = 0; i < cls->n_tries; i++) { + atomic_read_relaxed(&cls->n_tries, &n_tries); + for (i = 0; i < n_tries; i++) { if (subtable->trie_plen[i]) { trie_remove(&cls->tries[i], cls_rule, subtable->trie_plen[i]); } @@ -845,6 +841,7 @@ classifier_remove_assert(struct classifier *cls, struct trie_ctx { const struct cls_trie *trie; bool lookup_done; /* Status of the lookup. */ + uint8_t be32ofs; /* U32 offset of the field in question. */ unsigned int maskbits; /* Prefix length needed to avoid false matches. */ union trie_prefix match_plens; /* Bitmask of prefix lengths with possible * matches. */ @@ -854,6 +851,7 @@ static void trie_ctx_init(struct trie_ctx *ctx, const struct cls_trie *trie) { ctx->trie = trie; + ctx->be32ofs = trie->field->flow_be32ofs; ctx->lookup_done = false; } @@ -988,13 +986,18 @@ classifier_lookup__(const struct classifier *cls, ovs_version_t version, size_t n_soft = 0, allocated_soft = ARRAY_SIZE(soft_stub); int soft_pri = INT_MIN; /* n_soft ? MAX(soft[*]->priority) : INT_MIN. */ - /* Synchronize for cls->n_tries and subtable->trie_plen. They can change - * when table configuration changes, which happens typically only on - * startup. */ - atomic_thread_fence(memory_order_acquire); + uint32_t n_tries; + + /* Using memory_order_acquire on cls->n_tries to make sure that all the + * configuration changes for these tries are fully visible after the read. + * + * Trie configuration changes typically happen on startup, but can also + * happen in runtime. */ + atomic_read_explicit(&CONST_CAST(struct classifier *, cls)->n_tries, + &n_tries, memory_order_acquire); /* Initialize trie contexts for find_match_wc(). */ - for (int i = 0; i < cls->n_tries; i++) { + for (uint32_t i = 0; i < n_tries; i++) { trie_ctx_init(&trie_ctx[i], &cls->tries[i]); } @@ -1006,8 +1009,7 @@ classifier_lookup__(const struct classifier *cls, ovs_version_t version, /* Skip subtables with no match, or where the match is lower-priority * than some certain match we've already found. */ - match = find_match_wc(subtable, version, flow, trie_ctx, cls->n_tries, - wc); + match = find_match_wc(subtable, version, flow, trie_ctx, n_tries, wc); if (!match || match->priority <= hard_pri) { continue; } @@ -1535,8 +1537,8 @@ static struct cls_subtable * insert_subtable(struct classifier *cls, const struct minimask *mask) { uint32_t hash = minimask_hash(mask, 0); + uint32_t i, n_tries, index = 0; struct cls_subtable *subtable; - int i, index = 0; struct flowmap stage_map; uint8_t prev; size_t count = miniflow_n_values(&mask->masks); @@ -1574,11 +1576,10 @@ insert_subtable(struct classifier *cls, const struct minimask *mask) } *CONST_CAST(uint8_t *, &subtable->n_indices) = index; - for (i = 0; i < cls->n_tries; i++) { - const struct mf_field *field - = ovsrcu_get(struct mf_field *, &cls->tries[i].field); - subtable->trie_plen[i] - = field ? minimask_get_prefix_len(mask, field) : 0; + atomic_read_relaxed(&cls->n_tries, &n_tries); + for (i = 0; i < n_tries; i++) { + subtable->trie_plen[i] = minimask_get_prefix_len(mask, + cls->tries[i].field); } /* Ports trie. */ @@ -1610,29 +1611,22 @@ static unsigned int be_get_bit_at(const ovs_be32 value[], unsigned int ofs); /* Return 'true' if can skip rest of the subtable based on the prefix trie * lookup results. */ static inline bool -check_tries(struct trie_ctx trie_ctx[CLS_MAX_TRIES], unsigned int n_tries, +check_tries(struct trie_ctx trie_ctx[CLS_MAX_TRIES], uint32_t n_tries, const unsigned int field_plen[CLS_MAX_TRIES], const struct flowmap range_map, const struct flow *flow, struct flow_wildcards *wc) { - int j; + uint32_t j; /* Check if we could avoid fully unwildcarding the next level of * fields using the prefix tries. The trie checks are done only as * needed to avoid folding in additional bits to the wildcards mask. */ for (j = 0; j < n_tries; j++) { - /* Is the trie field relevant for this subtable? */ - if (field_plen[j]) { - struct trie_ctx *ctx = &trie_ctx[j]; - const struct mf_field *ctx_field - = ovsrcu_get(struct mf_field *, &ctx->trie->field); - - /* Is the trie field within the current range of fields? */ - if (!ctx_field - || !flowmap_is_set(&range_map, ctx_field->flow_be32ofs / 2)) { - continue; - } + struct trie_ctx *ctx = &trie_ctx[j]; + /* Is the trie field relevant for this subtable, and + * is the trie field within the current range of fields? */ + if (field_plen[j] && flowmap_is_set(&range_map, ctx->be32ofs / 2)) { /* On-demand trie lookup. */ if (!ctx->lookup_done) { memset(&ctx->match_plens, 0, sizeof ctx->match_plens); @@ -1653,16 +1647,14 @@ check_tries(struct trie_ctx trie_ctx[CLS_MAX_TRIES], unsigned int n_tries, * than this subtable would otherwise. */ if (ctx->maskbits <= field_plen[j]) { /* Unwildcard the bits and skip the rest. */ - mask_set_prefix_bits(wc, ctx_field->flow_be32ofs, - ctx->maskbits); + mask_set_prefix_bits(wc, ctx->be32ofs, ctx->maskbits); /* Note: Prerequisite already unwildcarded, as the only * prerequisite of the supported trie lookup fields is * the ethertype, which is always unwildcarded. */ return true; } /* Can skip if the field is already unwildcarded. */ - if (mask_prefix_bits_set(wc, ctx_field->flow_be32ofs, - ctx->maskbits)) { + if (mask_prefix_bits_set(wc, ctx->be32ofs, ctx->maskbits)) { return true; } } @@ -1727,7 +1719,7 @@ find_match(const struct cls_subtable *subtable, ovs_version_t version, static const struct cls_match * find_match_wc(const struct cls_subtable *subtable, ovs_version_t version, const struct flow *flow, struct trie_ctx *trie_ctx, - unsigned int n_tries, struct flow_wildcards *wc) + uint32_t n_tries, struct flow_wildcards *wc) { if (OVS_UNLIKELY(!wc)) { return find_match(subtable, version, flow, @@ -1740,7 +1732,7 @@ find_match_wc(const struct cls_subtable *subtable, ovs_version_t version, unsigned int mask_offset = 0; bool adjust_ports_mask = false; ovs_be32 ports_mask; - int i; + uint32_t i; /* Try to finish early by checking fields in segments. */ for (i = 0; i < subtable->n_indices; i++) { @@ -1950,18 +1942,29 @@ trie_node_rcu_realloc(const struct trie_node *node) } static void -trie_destroy(rcu_trie_ptr *trie) +trie_destroy__(rcu_trie_ptr *trie) { struct trie_node *node = ovsrcu_get_protected(struct trie_node *, trie); if (node) { ovsrcu_set_hidden(trie, NULL); - trie_destroy(&node->edges[0]); - trie_destroy(&node->edges[1]); + trie_destroy__(&node->edges[0]); + trie_destroy__(&node->edges[1]); trie_node_destroy(node); } } +static void +trie_destroy(struct cls_trie *trie) +{ + if (!trie) { + return; + } + + trie_destroy__(&trie->root); + trie->field = NULL; +} + static bool trie_is_leaf(const struct trie_node *trie) { @@ -2070,12 +2073,12 @@ static unsigned int trie_lookup(const struct cls_trie *trie, const struct flow *flow, union trie_prefix *plens) { - const struct mf_field *mf = ovsrcu_get(struct mf_field *, &trie->field); + const struct mf_field *mf = trie->field; /* Check that current flow matches the prerequisites for the trie * field. Some match fields are used for multiple purposes, so we * must check that the trie is relevant for this flow. */ - if (mf && mf_are_prereqs_ok(mf, flow, NULL)) { + if (mf_are_prereqs_ok(mf, flow, NULL)) { return trie_lookup_value(&trie->root, &((ovs_be32 *)flow)[mf->flow_be32ofs], &plens->be32, mf->n_bits); @@ -2122,9 +2125,8 @@ minimask_get_prefix_len(const struct minimask *minimask, * happened to be zeros. */ static const ovs_be32 * -minimatch_get_prefix(const struct minimatch *match, rcu_field_ptr *field) +minimatch_get_prefix(const struct minimatch *match, const struct mf_field *mf) { - struct mf_field *mf = ovsrcu_get_protected(struct mf_field *, field); size_t u64_ofs = mf->flow_be32ofs / 2; return (OVS_FORCE const ovs_be32 *)miniflow_get__(match->flow, u64_ofs) @@ -2138,7 +2140,7 @@ static void trie_insert(struct cls_trie *trie, const struct cls_rule *rule, int mlen) { trie_insert_prefix(&trie->root, - minimatch_get_prefix(&rule->match, &trie->field), mlen); + minimatch_get_prefix(&rule->match, trie->field), mlen); } static void @@ -2193,7 +2195,7 @@ static void trie_remove(struct cls_trie *trie, const struct cls_rule *rule, int mlen) { trie_remove_prefix(&trie->root, - minimatch_get_prefix(&rule->match, &trie->field), mlen); + minimatch_get_prefix(&rule->match, trie->field), mlen); } /* 'mlen' must be the (non-zero) CIDR prefix length of the 'trie->field' mask diff --git a/lib/classifier.h b/lib/classifier.h index 7928601e0..77a3ae5cf 100644 --- a/lib/classifier.h +++ b/lib/classifier.h @@ -314,15 +314,13 @@ extern "C" { struct cls_subtable; struct cls_match; -struct mf_field; -typedef OVSRCU_TYPE(struct mf_field *) rcu_field_ptr; struct trie_node; typedef OVSRCU_TYPE(struct trie_node *) rcu_trie_ptr; /* Prefix trie for a 'field' */ struct cls_trie { - rcu_field_ptr field; /* Trie field, or NULL. */ - rcu_trie_ptr root; /* NULL if none. */ + const struct mf_field *field; /* Trie field, or NULL. */ + rcu_trie_ptr root; /* NULL if none. */ }; enum { @@ -340,7 +338,9 @@ struct classifier { struct pvector subtables; struct cmap partitions; /* Contains "struct cls_partition"s. */ struct cls_trie tries[CLS_MAX_TRIES]; /* Prefix tries. */ - unsigned int n_tries; + atomic_uint32_t n_tries; /* Number of tries. Also serves as a + * memory synchronization point for trie + * configuration. */ bool publish; /* Make changes visible to lookups? */ }; diff --git a/tests/test-classifier.c b/tests/test-classifier.c index ee022ba1e..7f6ba50ee 100644 --- a/tests/test-classifier.c +++ b/tests/test-classifier.c @@ -418,6 +418,7 @@ compare_classifiers(struct classifier *cls, size_t n_invisible_rules, const struct cls_rule *cr0, *cr1, *cr2; struct flow flow; struct flow_wildcards wc; + uint32_t n_tries; unsigned int x; flow_wildcards_init_catchall(&wc); @@ -439,7 +440,8 @@ compare_classifiers(struct classifier *cls, size_t n_invisible_rules, flow.nw_tos = nw_dscp_values[get_value(&x, N_NW_DSCP_VALUES)]; /* This assertion is here to suppress a GCC 4.9 array-bounds warning */ - ovs_assert(cls->n_tries <= CLS_MAX_TRIES); + atomic_read_relaxed(&cls->n_tries, &n_tries); + ovs_assert(n_tries <= CLS_MAX_TRIES); cr0 = classifier_lookup(cls, version, &flow, &wc, NULL); cr1 = tcls_lookup(tcls, &flow); @@ -510,12 +512,12 @@ verify_tries(struct classifier *cls) OVS_NO_THREAD_SAFETY_ANALYSIS { unsigned int n_rules; - int i; + uint32_t i, n_tries; - for (i = 0; i < cls->n_tries; i++) { - const struct mf_field * cls_field - = ovsrcu_get(struct mf_field *, &cls->tries[i].field); - n_rules = trie_verify(&cls->tries[i].root, 0, cls_field->n_bits); + atomic_read_explicit(&cls->n_tries, &n_tries, memory_order_acquire); + for (i = 0; i < n_tries; i++) { + n_rules = trie_verify(&cls->tries[i].root, 0, + cls->tries[i].field->n_bits); assert(n_rules <= cls->n_rules); } } From patchwork Fri May 16 21:25:17 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ilya Maximets X-Patchwork-Id: 2086944 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=patchwork.ozlabs.org) 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 (secp384r1) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4Zzg960Vh1z1yPv for ; Sat, 17 May 2025 07:25:30 +1000 (AEST) Received: from localhost (localhost [127.0.0.1]) by smtp4.osuosl.org (Postfix) with ESMTP id BCF38419E5; Fri, 16 May 2025 21:25:41 +0000 (UTC) X-Virus-Scanned: amavis at osuosl.org Received: from smtp4.osuosl.org ([127.0.0.1]) by localhost (smtp4.osuosl.org [127.0.0.1]) (amavis, port 10024) with ESMTP id JSkGauQSrPyJ; Fri, 16 May 2025 21:25:38 +0000 (UTC) X-Comment: SPF check N/A for local connections - client-ip=2605:bc80:3010:104::8cd3:938; helo=lists.linuxfoundation.org; envelope-from=ovs-dev-bounces@openvswitch.org; receiver= DKIM-Filter: OpenDKIM Filter v2.11.0 smtp4.osuosl.org B00DD419B2 Received: from lists.linuxfoundation.org (lf-lists.osuosl.org [IPv6:2605:bc80:3010:104::8cd3:938]) by smtp4.osuosl.org (Postfix) with ESMTPS id B00DD419B2; Fri, 16 May 2025 21:25:37 +0000 (UTC) Received: from lf-lists.osuosl.org (localhost [127.0.0.1]) by lists.linuxfoundation.org (Postfix) with ESMTP id 76BAEC08A9; Fri, 16 May 2025 21:25:37 +0000 (UTC) X-Original-To: ovs-dev@openvswitch.org Delivered-To: ovs-dev@lists.linuxfoundation.org Received: from smtp3.osuosl.org (smtp3.osuosl.org [140.211.166.136]) by lists.linuxfoundation.org (Postfix) with ESMTP id 10DBBC0AB8 for ; Fri, 16 May 2025 21:25:36 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp3.osuosl.org (Postfix) with ESMTP id B977761373 for ; Fri, 16 May 2025 21:25:34 +0000 (UTC) X-Virus-Scanned: amavis at osuosl.org Received: from smtp3.osuosl.org ([127.0.0.1]) by localhost (smtp3.osuosl.org [127.0.0.1]) (amavis, port 10024) with ESMTP id Aa_Kaky043lB for ; Fri, 16 May 2025 21:25:34 +0000 (UTC) Received-SPF: Pass (mailfrom) identity=mailfrom; client-ip=209.85.218.67; helo=mail-ej1-f67.google.com; envelope-from=i.maximets.ovn@gmail.com; receiver= DMARC-Filter: OpenDMARC Filter v1.4.2 smtp3.osuosl.org B0CC76138F Authentication-Results: smtp3.osuosl.org; dmarc=none (p=none dis=none) header.from=ovn.org DKIM-Filter: OpenDKIM Filter v2.11.0 smtp3.osuosl.org B0CC76138F Received: from mail-ej1-f67.google.com (mail-ej1-f67.google.com [209.85.218.67]) by smtp3.osuosl.org (Postfix) with ESMTPS id B0CC76138F for ; Fri, 16 May 2025 21:25:33 +0000 (UTC) Received: by mail-ej1-f67.google.com with SMTP id a640c23a62f3a-ad5273c1fd7so357661266b.1 for ; Fri, 16 May 2025 14:25:33 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1747430731; x=1748035531; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=Ho4RPiqBmJdSUrg47Viww9UPcYk5zM0fs1p3bt24PK8=; b=TCS+k5dt0TTzC+8WpdF5aM2IIHM0ofcdKtnKhPP6ZApI4JHe8xu4IhP2LEg8jGNgxL PxonKjOAWfahFVoC0DTj2duvfEOCGk2nuYi3+NvkHtFeNLNfdE2mlHGoya8q0OVcCZ8B AnIrKDWJV53iQzsH5PJAWKvryL6ojsBrMHL/P4WHGppumZ8aOK0VW5eMUnXCycEHA69M fe6GmTsGv49hoOy23Jlftl6w/sYx1lqVfk+6aqVOStVwLx6GI+rS7JjQVC/Qf1s0KeHA EEafRrV4Pu8nt96MheoHgXo8dGDVOYojYDguI764bFs08I1Eu5ubowBCfGXkIIq+FgtF Ch9A== X-Gm-Message-State: AOJu0YwxIe/ivgj8XSAG1S61Eh/OvYGVUde8nyePBntJYbYgWsRbvXtD UUcB2GBiWrgyUI70ygREGX/RHOkhrGhd5444WRGXpE3hzAL5Qsh7p+LF5ZTz7ik4 X-Gm-Gg: ASbGncujcOEZ1EpOqZelrdc+2f7jQc9eMy3cumIv6pwg55WtxxxKf1usEZmVbSADIoD cssFCxugjurr1FjuRFP34nxcF9tLv8RiusFOeSwafQvlwZi/2gpgU8SZ/uasYEXwYoI+/3xPDbS xnUQSaaqTC7ye6SY/WV4GDgFzYLOvOO/4VlKwIWRiDR+3MFADEk6Chap1ZaMEnrT+P/vSo9u9k6 u5iHQncQEZb6S21J5BEdhrptJBD3Lm4n8NqYcyVUJJEzpsrcGxJUgnLRi0kgbMZOY7fsX5PSD/z Liov2ZzDT3bsz2lShiVeMDf9IENn87/++qqv3FggcGAxkU1qRiHXV3IFKEO3mcr88/d2GKOUAVa RpqocR8vZ8jfSZlMTfPLpAFHJnB8= X-Google-Smtp-Source: AGHT+IFGT2sMybHookA8kJxLgnxMnGKJ5RWvaiaW16uq6Ag5nhco5BLoguyS6iGjy9F2Vb/dU0Bl4g== X-Received: by 2002:a17:907:7da2:b0:ad2:2ef3:cc1b with SMTP id a640c23a62f3a-ad536b7bd28mr381056866b.7.1747430731389; Fri, 16 May 2025 14:25:31 -0700 (PDT) Received: from im-t490s.redhat.com (78-80-121-182.customers.tmcz.cz. [78.80.121.182]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-ad52d490789sm212047266b.130.2025.05.16.14.25.30 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 16 May 2025 14:25:31 -0700 (PDT) From: Ilya Maximets To: ovs-dev@openvswitch.org Date: Fri, 16 May 2025 23:25:17 +0200 Message-ID: <20250516212521.733714-4-i.maximets@ovn.org> X-Mailer: git-send-email 2.49.0 In-Reply-To: <20250516212521.733714-1-i.maximets@ovn.org> References: <20250516212521.733714-1-i.maximets@ovn.org> MIME-Version: 1.0 Subject: [ovs-dev] [PATCH 3/3] tests: classifier: Add a stress test for prefixes reconfiguration. X-BeenThere: ovs-dev@openvswitch.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: Ilya Maximets Errors-To: ovs-dev-bounces@openvswitch.org Sender: "dev" This test is reusing the benchmark infrastructure, but it has some pre-defined parameters, so it's easier to run in the test suite. The benchmark code is adjusted to start another thread that does prefix updates continuously in a loop and the lookup threads are updated to be able to enter quiescent state periodically, so the reconfiguration can proceed. This test is a reproducer for the crashes fixed in the previous commit. Signed-off-by: Ilya Maximets Acked-by: Eelco Chaudron --- tests/classifier.at | 5 +++ tests/test-classifier.c | 98 ++++++++++++++++++++++++++++++++++++++--- 2 files changed, 97 insertions(+), 6 deletions(-) diff --git a/tests/classifier.at b/tests/classifier.at index dfadf5e5a..bfa1b119c 100644 --- a/tests/classifier.at +++ b/tests/classifier.at @@ -17,6 +17,11 @@ m4_foreach( AT_CHECK([ovstest test-classifier m4_bpatsubst(testname, [versioned], [--versioned])], [0], [], []) AT_CLEANUP])]) +AT_BANNER([flow classifier stress tests]) +AT_SETUP([flow classifier - prefixes reconfiguration stress test]) +AT_CHECK([ovstest test-classifier stress-prefixes], [0], [stdout]) +AT_CLEANUP + AT_BANNER([miniflow unit tests]) m4_foreach( [testname], diff --git a/tests/test-classifier.c b/tests/test-classifier.c index 7f6ba50ee..6ac276d2e 100644 --- a/tests/test-classifier.c +++ b/tests/test-classifier.c @@ -37,6 +37,7 @@ #include "command-line.h" #include "fatal-signal.h" #include "flow.h" +#include "openvswitch/vlog.h" #include "ovstest.h" #include "ovs-atomic.h" #include "ovs-thread.h" @@ -757,11 +758,22 @@ shuffle_u32s(uint32_t *p, size_t n) *q = tmp; } } + +static void +shuffle_fields(enum mf_field_id *p, size_t n) +{ + for (; n > 1; n--, p++) { + enum mf_field_id *q = &p[random_range(n)]; + enum mf_field_id tmp = *p; + *p = *q; + *q = tmp; + } +} /* Classifier tests. */ -static enum mf_field_id trie_fields[2] = { - MFF_IPV4_DST, MFF_IPV4_SRC +static enum mf_field_id trie_fields[4] = { + MFF_IPV4_DST, MFF_IPV4_SRC, MFF_IPV6_DST, MFF_IPV6_SRC, }; static void @@ -1286,7 +1298,7 @@ static int n_tables; /* Number of subtables. */ static int n_threads; /* Number of threads to search and mutate. */ static int n_lookups; /* Number of lookups each thread performs. */ -static void benchmark(bool use_wc); +static void benchmark(bool use_wc, bool stress_prefixes); static int elapsed(const struct timeval *start) @@ -1337,9 +1349,29 @@ run_benchmarks(struct ovs_cmdl_context *ctx) n_rules, n_priorities, n_tables, n_threads, n_lookups); puts("\nWithout wildcards: \n"); - benchmark(false); + benchmark(false, false); puts("\nWith wildcards: \n"); - benchmark(true); + benchmark(true, false); +} + +static void +run_prefix_stress(struct ovs_cmdl_context *ctx OVS_UNUSED) +{ + vlog_set_levels(NULL, VLF_ANY_DESTINATION, VLL_OFF); + vlog_set_levels(NULL, VLF_CONSOLE, VLL_WARN); + + n_rules = 10000; + n_priorities = 2; + n_tables = 30; + n_threads = 2; + n_lookups = 2000000; + + printf("\nStress testing prefixes with:\n" + "%d rules with %d priorities in %d tables, " + "%d threads doing %d lookups each\n", + n_rules, n_priorities, n_tables, n_threads, n_lookups); + + benchmark(true, true); } struct cls_aux { @@ -1347,6 +1379,7 @@ struct cls_aux { size_t n_lookup_flows; struct flow *lookup_flows; bool use_wc; + bool quiesce; atomic_int hits; atomic_int misses; }; @@ -1382,15 +1415,47 @@ lookup_classifier(void *aux_) } else { misses++; } + if (aux->quiesce) { + ovsrcu_quiesce(); + } } atomic_add(&aux->hits, hits, &old_hits); atomic_add(&aux->misses, misses, &old_misses); return NULL; } +struct prefix_aux { + struct classifier *cls; + atomic_bool running; + size_t n_updates; +}; + +static void * +update_prefixes(void *aux_) +{ + struct prefix_aux *aux = aux_; + size_t n, n_updates = 0; + bool running = true; + + random_set_seed(1); + + while (running) { + n_updates++; + + shuffle_fields(trie_fields, ARRAY_SIZE(trie_fields)); + n = random_range(ARRAY_SIZE(trie_fields) + 1); + classifier_set_prefix_fields(aux->cls, trie_fields, n); + verify_tries(aux->cls); + + atomic_read_relaxed(&aux->running, &running); + } + aux->n_updates = n_updates; + return NULL; +} + /* Benchmark classification. */ static void -benchmark(bool use_wc) +benchmark(bool use_wc, bool stress_prefixes) { struct classifier cls; ovs_version_t version = OVS_VERSION_MIN; @@ -1421,6 +1486,7 @@ benchmark(bool use_wc) /* Create lookup flows. */ aux.use_wc = use_wc; + aux.quiesce = stress_prefixes; aux.cls = &cls; aux.n_lookup_flows = 2 * N_FLOW_VALUES; aux.lookup_flows = xzalloc(aux.n_lookup_flows * sizeof *aux.lookup_flows); @@ -1465,6 +1531,18 @@ benchmark(bool use_wc) } } + pthread_t prefix_thread; + struct prefix_aux paux; + + if (stress_prefixes) { + paux.cls = &cls; + paux.n_updates = 0; + atomic_init(&paux.running, true); + + prefix_thread = ovs_thread_create("prefixes", update_prefixes, &paux); + ovsrcu_quiesce_start(); + } + /* Lookup. */ xgettimeofday(&start); threads = xmalloc(n_threads * sizeof *threads); @@ -1479,6 +1557,13 @@ benchmark(bool use_wc) free(threads); + if (stress_prefixes) { + atomic_store_relaxed(&paux.running, false); + xpthread_join(prefix_thread, NULL); + printf("Prefixes updated %"PRIuSIZE" times.\n", paux.n_updates); + ovsrcu_quiesce_end(); + } + int hits, misses; atomic_read(&aux.hits, &hits); atomic_read(&aux.misses, &misses); @@ -1852,6 +1937,7 @@ static const struct ovs_cmdl_command commands[] = { {"many-rules-in-two-tables", NULL, 0, 0, test_many_rules_in_two_tables, OVS_RO }, {"many-rules-in-five-tables", NULL, 0, 0, test_many_rules_in_five_tables, OVS_RO }, {"benchmark", NULL, 0, 5, run_benchmarks, OVS_RO }, + {"stress-prefixes", NULL, 0, 0, run_prefix_stress, OVS_RO }, /* Miniflow and minimask tests. */ {"miniflow", NULL, 0, 0, test_miniflow, OVS_RO },