From nobody Thu Nov 28 01:48:42 2024 Received: from mail-pg1-f178.google.com (mail-pg1-f178.google.com [209.85.215.178]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 3AB8A1BC58; Sat, 5 Oct 2024 21:50:01 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.215.178 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1728165002; cv=none; b=ZvCHQVrnzcDCNVk4QBuFoZ8Sj2xwwFymb1jUZXwwnTj5nzq5/cgAixq03C/Rz5aCnlT/fLN2Buj++5oL10SD+IcK8TCEAzWJKemCd6p83a2r3BGSci1pTldYYrHs+EN/ymE43lGzanFoil+jN19zwZwCmTRwt2ocgotwO5xRDfA= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1728165002; c=relaxed/simple; bh=AugDlfv+b6hscDAkW1E1n2aZ4MUkiHLw9DH7oM9tob8=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=dTuAg4A1YilQJYKLp1H82VTI4BAlOTqT7AKWQDykZJ1vJzP7+097SQgutI1OHL4emCDE9ntKIuNv77X4pk6tpZbKTGBBEctexw1/XMpwwXBk0L6SgdriD8jdape++n5rZdtPz5UR8avvtaMfR1cU+cVvICE3zu3u5G5D14CbxTo= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=LyRIP+fM; arc=none smtp.client-ip=209.85.215.178 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="LyRIP+fM" Received: by mail-pg1-f178.google.com with SMTP id 41be03b00d2f7-7db90a28cf6so2861045a12.0; Sat, 05 Oct 2024 14:50:01 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1728165001; x=1728769801; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=26n6rwkz8EuDUCSAPaRiQZLssj+wWU8kRKUT3JvSvtc=; b=LyRIP+fMVu3quP/Tn9bH+2Vt7CsPNNsMCksw1sMvDJ5APRVNv6MbhTiYjf+Gn++W/D 4rCCdIgC0kLNaHqcFhBPaMiL94A6wZIY6j4gN/NZ5Uxm/opUto81WrxDyCFWl19SWN5b o5SdYWDNrS75M8IneDy5gm7smNXpBSt5R/LPwfZ6KU0gza2vAMOX6yj72Ez+wHOVclTJ Ueuqkgp5cnwnM4vqzub8JwZCfts/59boAH2N89uCPG8ywNLBjmiCBaUYLsnYOQtmlpXk +yNfgSCNC6B8QbT3Io+AYYB4MoQZAU/prz1RcpzY8nVTQ7CsjA790ZbcAmQgWyv9O+6O rSTg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1728165001; x=1728769801; 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=26n6rwkz8EuDUCSAPaRiQZLssj+wWU8kRKUT3JvSvtc=; b=TXLHrNJGQbRhHE6G0WzV2oy0zKIkypxUVoSsf7JzRCR6JOiADcSUZNAvj6WF3QcSH5 wlQf1/2yHZWmbTFFzl1nYRG827dskrTCRFp6S7NewaigW70JVuq6Iq+/p9Tdg9nbV9ZC 2LfZ2gxua4MThyxGMoEYYb33tHzoUP/wcsAFEh39wWWff1+aGG0mx8IFMdy2pEGXQ3JE p5HcOrT9PB5HmgArFh6xW4CMaT2YCrGg8YChrMiSEpmvO9Nz8TgBRL/1zRwU7/Nymbyi W3xCJlGRUkb2uHcXIoHIJTHpB9woRqlbOW8T1pO9M3jyBwFK3tuS+S11IPH4pjjyIEGH qNsw== X-Forwarded-Encrypted: i=1; AJvYcCUIM51oVuOnx97Pk6lhRIpXLl+MbYLYQvPKCQHycVp7geKY5EYlSa2qFazJ9TPdFo+Cbe2I3ZxyTk3AB40G@vger.kernel.org, AJvYcCWPfenUcCKYTRevl6dlO7kD/wfC9KYNuNJac7cJen/gLBYdCDiOLFjeGcJ+j8OsjdPs5m8z4s9l@vger.kernel.org X-Gm-Message-State: AOJu0Yxam+I2fvBks2FXJavgyOM1c/R5LERoMkRSIYSyhKm8yLL6CYHC 01ssf3jN258pLF02N1+w3pUPapHWD4w6XSosk2s3voIkxJpHEB9e X-Google-Smtp-Source: AGHT+IEmG/yE6dQLY9qvFtGWv6Tot6sO+NFQmFItWrLf5jPrMwhdviMrD/l26lrg3ajLSABPXkl9lg== X-Received: by 2002:a17:903:2309:b0:20b:723a:cba1 with SMTP id d9443c01a7336-20be18731fbmr184103205ad.1.1728165000683; Sat, 05 Oct 2024 14:50:00 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id d9443c01a7336-20c13931055sm17165135ad.139.2024.10.05.14.49.58 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 05 Oct 2024 14:50:00 -0700 (PDT) From: Kuan-Wei Chiu To: xavier_qy@163.com, longman@redhat.com, lizefan.x@bytedance.com, tj@kernel.org, hannes@cmpxchg.org, mkoutny@suse.com, akpm@linux-foundation.org Cc: jserv@ccns.ncku.edu.tw, linux-kernel@vger.kernel.org, cgroups@vger.kernel.org, Kuan-Wei Chiu Subject: [PATCH 1/5] lib/union_find: Add EXPORT_SYMBOL() for uf_find() and uf_union() Date: Sun, 6 Oct 2024 05:49:34 +0800 Message-Id: <20241005214938.2147393-2-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20241005214938.2147393-1-visitorckw@gmail.com> References: <20241005214938.2147393-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Add EXPORT_SYMBOL() for the uf_find() and uf_union() functions to allow kernel modules, including the KUnit tests for the Union-Find data structure, to use these functions. This enhances the usability of the Union-Find implementation in a modular context, facilitating easier testing and integration. Signed-off-by: Kuan-Wei Chiu --- lib/union_find.c | 3 +++ 1 file changed, 3 insertions(+) diff --git a/lib/union_find.c b/lib/union_find.c index 413b0f8adf7a..c9fd30b8059c 100644 --- a/lib/union_find.c +++ b/lib/union_find.c @@ -1,4 +1,5 @@ // SPDX-License-Identifier: GPL-2.0 +#include #include =20 /** @@ -21,6 +22,7 @@ struct uf_node *uf_find(struct uf_node *node) } return node; } +EXPORT_SYMBOL(uf_find); =20 /** * uf_union - Merge two sets, using union by rank @@ -47,3 +49,4 @@ void uf_union(struct uf_node *node1, struct uf_node *node= 2) root1->rank++; } } +EXPORT_SYMBOL(uf_union); --=20 2.34.1 From nobody Thu Nov 28 01:48:42 2024 Received: from mail-pl1-f171.google.com (mail-pl1-f171.google.com [209.85.214.171]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 953CF170828; Sat, 5 Oct 2024 21:50:04 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.171 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1728165006; cv=none; b=b2M+eeFt7/4RWQe7/g4ldTKGTzpTSvmTsMEXSbC6hgIAEwM7+XDNsC+da4QNK7RwOBnQ5FLfpJPZm9iH6atC/T/Mbd8qqNTleif6pUvsLQ5pGDVTMjftAEPU32AffTrQOJlXVQm9uG8kTLNOgry6P+VrCnIePODEmPYeIpkqrzI= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1728165006; c=relaxed/simple; bh=FIuweSrtG+mcEyXr9hjv2sE4Z6ooLACWb0fLKdJTkfo=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=PZjH1kbY0Dh//guDBPci3dP+Iv1tY/IaxHsS/CL5FST9mp/edBw9IXXS2L10tKLQWv9wU3Zoi/8Iy5HKf1GHmPKHfRsAusPBKTSvDGdKLjIfjFkBJHyQ47V0i2K0LNLFlNX0q6ptw5bk1h4ND7/3WWuuqCQzFGb3NWYiXnynoeU= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=QCYkOdwE; arc=none smtp.client-ip=209.85.214.171 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="QCYkOdwE" Received: by mail-pl1-f171.google.com with SMTP id d9443c01a7336-207115e3056so29609755ad.2; Sat, 05 Oct 2024 14:50:04 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1728165004; x=1728769804; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=Xy+fzQoGdpErgau5hKCbmSyfAtB1CVjWDNKSp3x5/6M=; b=QCYkOdwEuBffkxGl39lEZRXDyJKpad18cUGT0t4/I+Yi2atLYPROek2+E1n2/pYt7l DCkSMsER6Dxs4JL5gzJGEJzBwKvPMeUOaIaM5UpiD06YD6vIOJTtk/24mlqCDFs0X0Dy jIxtpZIcH/GiyNwJF95BJWdWROz1Oswfvkf6u2G5+M6YA1S9SVJAkDyGrDfazz9UFPdF r4f9tBwOArOuGg52tnbQn86BgDhW1m3l9zF4Zv0nzsODD81R981TQd9Nw2dfFq5PkavH ptmX1qbG7pDOHK1XWyzrQNPi6BIY0eK2ozWj9yDtIT36mOzAJtMvbrhjjUVCpVoAy8UH dZmw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1728165004; x=1728769804; 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=Xy+fzQoGdpErgau5hKCbmSyfAtB1CVjWDNKSp3x5/6M=; b=TkMx50lZOV1rszUQpR7y6gb6iZ3PjF2wpK96EjjYHpbXu2ZhwjZ4F1v+j66mEK5ROG arF9rWTS13F0YcyPRbr+7GJylIgxFqBr0LvDgbg1RoQU1s8ezspZrtbPmafMKbYC+rHe 7vHcoDzPKdMX/y9H/9ueu/YwCNEfnmi8vjENWHaSJoV4+UgSgkwS48/th7Zjrm0jGJ4v 43/UPV5UGOF45f+w1iwCSN2jkHzA4xqBMo32GVWTPTqlMOo178ZXjyenEGJMRzDQaXtB vsL9jgTUdR06424N88nrTMm8BTqbArEbqr7xB7EL3wFOxSuIo0H+5khtCmuO2nQXklSL T8hA== X-Forwarded-Encrypted: i=1; AJvYcCVmbKWL3Ku3mmGyw9miscPv1prO8F1HLy+PF4ocv7BlyteJcCUPNGZoIFSsIfPBZTuyY8YoVTdv@vger.kernel.org, AJvYcCVuRSQm7Ap265ZDkkMous9qSN2F5bTU0BXEXsy/cNC56wk9ue052McLe8xFhOs5NM2Aki6sapC7B7eXp1m4@vger.kernel.org X-Gm-Message-State: AOJu0Yz2IfKqXyDeE07I+w3afZSEz5Tvst6YhB63rMnI+ND8WJaHPTqf ct4kkFHT0HQdPxIRfTAI6ro2ZjGzt6H25ID04bRFFKZZhjwF8FSb X-Google-Smtp-Source: AGHT+IFjm3s5QoZ8Wvo6+zkWC9E/2NcwqZAvehzgcrJPMMFjq0tbvkUUMfyWoM/7lRqDJxBRu/yxcA== X-Received: by 2002:a17:903:41ce:b0:20b:b39d:9735 with SMTP id d9443c01a7336-20bff1b044cmr95796015ad.54.1728165003852; Sat, 05 Oct 2024 14:50:03 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id d9443c01a7336-20c13931055sm17165135ad.139.2024.10.05.14.50.01 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 05 Oct 2024 14:50:03 -0700 (PDT) From: Kuan-Wei Chiu To: xavier_qy@163.com, longman@redhat.com, lizefan.x@bytedance.com, tj@kernel.org, hannes@cmpxchg.org, mkoutny@suse.com, akpm@linux-foundation.org Cc: jserv@ccns.ncku.edu.tw, linux-kernel@vger.kernel.org, cgroups@vger.kernel.org, Kuan-Wei Chiu Subject: [PATCH 2/5] lib/union_find: Change uf_union() return type to bool Date: Sun, 6 Oct 2024 05:49:35 +0800 Message-Id: <20241005214938.2147393-3-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20241005214938.2147393-1-visitorckw@gmail.com> References: <20241005214938.2147393-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Modify the uf_union() function to return a bool indicating whether a merge occurred. If the two nodes belong to the same set, the function returns false, indicating no merge took place. Otherwise, it completes the merge and returns true. This change allows the caller to easily determine the number of distinct groups by tracking successful merges, enhancing the usability of the Union-Find implementation. Signed-off-by: Kuan-Wei Chiu --- include/linux/union_find.h | 2 +- lib/union_find.c | 8 ++++++-- 2 files changed, 7 insertions(+), 3 deletions(-) diff --git a/include/linux/union_find.h b/include/linux/union_find.h index cfd49263c138..45c1a6fc6574 100644 --- a/include/linux/union_find.h +++ b/include/linux/union_find.h @@ -36,6 +36,6 @@ static inline void uf_node_init(struct uf_node *node) struct uf_node *uf_find(struct uf_node *node); =20 /* Merge two intersecting nodes */ -void uf_union(struct uf_node *node1, struct uf_node *node2); +bool uf_union(struct uf_node *node1, struct uf_node *node2); =20 #endif /* __LINUX_UNION_FIND_H */ diff --git a/lib/union_find.c b/lib/union_find.c index c9fd30b8059c..a20678da0220 100644 --- a/lib/union_find.c +++ b/lib/union_find.c @@ -31,14 +31,16 @@ EXPORT_SYMBOL(uf_find); * * This function merges the sets containing node1 and node2, by comparing * the ranks to keep the tree balanced. + * + * Returns true if the sets were merged, false if they were already in the= same set. */ -void uf_union(struct uf_node *node1, struct uf_node *node2) +bool uf_union(struct uf_node *node1, struct uf_node *node2) { struct uf_node *root1 =3D uf_find(node1); struct uf_node *root2 =3D uf_find(node2); =20 if (root1 =3D=3D root2) - return; + return false; =20 if (root1->rank < root2->rank) { root1->parent =3D root2; @@ -48,5 +50,7 @@ void uf_union(struct uf_node *node1, struct uf_node *node= 2) root2->parent =3D root1; root1->rank++; } + + return true; } EXPORT_SYMBOL(uf_union); --=20 2.34.1 From nobody Thu Nov 28 01:48:42 2024 Received: from mail-pl1-f180.google.com (mail-pl1-f180.google.com [209.85.214.180]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id CA2891714CD; Sat, 5 Oct 2024 21:50:07 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.180 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1728165009; cv=none; b=QfWIEJMjBDu/pBpSBG67JbG9lWqbJXCwjxz76tty3vNk8qADBp/lZRa6NQ/NXK8hHCR3XSYJyfwOstPI8LdMx1ayOjxgL+VZ2vyssSzzxkICHFpoE9Occh7sggOwMgOV2guxg3Lp1KosVMxa85U6GZLstHDJEo8H5i3TCfetpaw= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1728165009; c=relaxed/simple; bh=eIduj2a7RDmKLt4ahXC9kCLPei5SOm6je5RPRjT8kM4=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=RsscJJ71NGfrUk8VUrtIEddZscJOcb4pnXVlaNLWH4X7HMv/TpM2rd8k1PCQ7Av3bmf6dWjdNE4QaQZNDuBrZh19pg6xO5ji3A4xQL6+UGElvT0FPbS0gPaGVbORhM6sag7tnsA0aLHLd7TL7qEcMJVmKfTuTUvLsoJbsnW5WA4= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=BIc34CAo; arc=none smtp.client-ip=209.85.214.180 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="BIc34CAo" Received: by mail-pl1-f180.google.com with SMTP id d9443c01a7336-20b78ee6298so20847115ad.2; Sat, 05 Oct 2024 14:50:07 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1728165007; x=1728769807; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=dcSg+3d0QR+rdWz/nC3iZVkACTYk5EHJ8llhpn/oIv4=; b=BIc34CAonHpcX7omqIpDvk4jZMjAENbqD5lZEgUoH8+m/hiFmO0HDtt3no6x2hpE9B IFZB6oWdbIKSbWmr0qAAvuJWtKtbQmP8eemazy4HoO8OaAk/Vbegl7tHMo4xAPwlSd1h 4FXWo8akEcelAYFQz9kYDewI5RuPJJzlmMKmRL8rvc/7fO4hv6KYpj8bgM2oeLAoe1vR YPH7rlghj00QFJ3Oc97f4qiJtLRPQFBmnOyu81Y9Uv/OCyRPRNLDzrpw7hq0GleBwJKi FpwnYOjylByKj4tOxKMiRtyQVLcDHSL3JLnjuaKzfO/qTVD2ZCWLI+P1daNh3engXySP noHQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1728165007; x=1728769807; 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=dcSg+3d0QR+rdWz/nC3iZVkACTYk5EHJ8llhpn/oIv4=; b=RGjTaEXjuEqbYEXHkZOQX9G6IcLO35kY872fY18JsqiOLbjbia5Drr3aXl/CKTWZtR Ec05/8c3qAbhc82poBvCOdioTZJxy+GH2jCPxYunxJKxnYAux1GOSOlKJXZVg3pAEvn/ jVmUYCorCUsd/uNmeyxFQbXdlOfwjRQWucIwPTKRZ6R0FEVnf3ZikdpK/nIWduK+yUNK +TqVGTQo2UgWJWCfaIdJavd0g3Hzm21FAL19mdmIWM224yCxPDlgYNZfHAeIG20KzxDw Cbeh9hoE1LYhU5OfUVIBchqHDlaCHIzk3KNUKXz0pcK38+YAUbMuidOAHwAxl9CtdQTb hJiw== X-Forwarded-Encrypted: i=1; AJvYcCU3Qvn4QXt82ntFs0WtMHjE9sM5hiAsB3UlXtewNF2HaUVP9a1MMeZFpzivMr10H4PZQJZtklp3+lPycKn0@vger.kernel.org, AJvYcCXeP3mtfa5y5rVP84mfD4lpqtocnh9tb7dkTjoSKoEp8THkDe+WvCVm5W9OVQx3U6KyXLBlGbG8@vger.kernel.org X-Gm-Message-State: AOJu0YzI4VpautJ9pjTiOLf4s25rPaIQyjDp/b+LsC7ReZ4ipmccTHnN +e49ONbdJcu/Wi7XROky8MyvHhU6yCLZ+fhsRDAv2ZKU46rSbQhT X-Google-Smtp-Source: AGHT+IHvftSQJ5RfLJxXlqhYt4stFu9wgWyJ3Ff5j+BVn2RTShvzOQ1JRR1JY0RE3VOua2f1976QOw== X-Received: by 2002:a17:902:f60e:b0:20b:a41f:6e48 with SMTP id d9443c01a7336-20bfe011becmr139397605ad.27.1728165007055; Sat, 05 Oct 2024 14:50:07 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id d9443c01a7336-20c13931055sm17165135ad.139.2024.10.05.14.50.04 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 05 Oct 2024 14:50:06 -0700 (PDT) From: Kuan-Wei Chiu To: xavier_qy@163.com, longman@redhat.com, lizefan.x@bytedance.com, tj@kernel.org, hannes@cmpxchg.org, mkoutny@suse.com, akpm@linux-foundation.org Cc: jserv@ccns.ncku.edu.tw, linux-kernel@vger.kernel.org, cgroups@vger.kernel.org, Kuan-Wei Chiu Subject: [PATCH 3/5] lib: Add KUnit tests for Union-Find implementation Date: Sun, 6 Oct 2024 05:49:36 +0800 Message-Id: <20241005214938.2147393-4-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20241005214938.2147393-1-visitorckw@gmail.com> References: <20241005214938.2147393-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Introduce a KUnit test suite for the Union-Find data structure. The tests verify the functionality and correctness of the union and find operations, including edge cases such as handling duplicate unions. The addition of KUnit tests enhances the robustness of the Union-Find implementation by ensuring its correctness under various scenarios. Signed-off-by: Kuan-Wei Chiu --- Regarding the changes to the MAINTAINERS file, I'm also happy to help maintain/review patches related to union find. If I am qualified enough, may I send another patch to add myself later? :) MAINTAINERS | 1 + lib/Kconfig.debug | 12 +++++++ lib/Makefile | 1 + lib/union_find_kunit.c | 74 ++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 88 insertions(+) create mode 100644 lib/union_find_kunit.c diff --git a/MAINTAINERS b/MAINTAINERS index 5153c995d429..3b10ac1cdf63 100644 --- a/MAINTAINERS +++ b/MAINTAINERS @@ -23799,6 +23799,7 @@ F: Documentation/core-api/union_find.rst F: Documentation/translations/zh_CN/core-api/union_find.rst F: include/linux/union_find.h F: lib/union_find.c +F: lib/union_find_kunit.c =20 UNIVERSAL FLASH STORAGE HOST CONTROLLER DRIVER R: Alim Akhtar diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index 7315f643817a..376c86d34253 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -2841,6 +2841,18 @@ config SIPHASH_KUNIT_TEST This is intended to help people writing architecture-specific optimized versions. If unsure, say N. =20 +config UNION_FIND_KUNIT_TEST + tristate "KUnit Test for Union find" + depends on KUNIT + default KUNIT_ALL_TESTS + help + This option enables the KUnit tests for the Union-Find data structure. + These tests verify the functionality and correctness of the Union-Find + implementation, including union and find operations, as well as + edge cases such as handling of duplicate unions. + + If unsure, say N + config USERCOPY_KUNIT_TEST tristate "KUnit Test for user/kernel boundary protections" depends on KUNIT diff --git a/lib/Makefile b/lib/Makefile index 773adf88af41..03da92faf9b8 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -388,6 +388,7 @@ CFLAGS_fortify_kunit.o +=3D $(call cc-disable-warning, = stringop-truncation) CFLAGS_fortify_kunit.o +=3D $(DISABLE_STRUCTLEAK_PLUGIN) obj-$(CONFIG_FORTIFY_KUNIT_TEST) +=3D fortify_kunit.o obj-$(CONFIG_SIPHASH_KUNIT_TEST) +=3D siphash_kunit.o +obj-$(CONFIG_UNION_FIND_KUNIT_TEST) +=3D union_find_kunit.o obj-$(CONFIG_USERCOPY_KUNIT_TEST) +=3D usercopy_kunit.o =20 obj-$(CONFIG_GENERIC_LIB_DEVMEM_IS_ALLOWED) +=3D devmem_is_allowed.o diff --git a/lib/union_find_kunit.c b/lib/union_find_kunit.c new file mode 100644 index 000000000000..9bdf9e0e455e --- /dev/null +++ b/lib/union_find_kunit.c @@ -0,0 +1,74 @@ +// SPDX-License-Identifier: GPL-2.0-only + +#include +#include +#include + +static void test_union_and_find(struct kunit *test) +{ + struct uf_node node1, node2, node3; + struct uf_node *root1, *root2, *root3; + bool merged; + + /* Initialize the nodes */ + uf_node_init(&node1); + uf_node_init(&node2); + uf_node_init(&node3); + + /* Check the initial parent and rank */ + KUNIT_ASSERT_PTR_EQ(test, uf_find(&node1), &node1); + KUNIT_ASSERT_PTR_EQ(test, uf_find(&node2), &node2); + KUNIT_ASSERT_PTR_EQ(test, uf_find(&node3), &node3); + KUNIT_ASSERT_EQ(test, node1.rank, 0); + KUNIT_ASSERT_EQ(test, node2.rank, 0); + KUNIT_ASSERT_EQ(test, node3.rank, 0); + + /* Union node1 and node2 */ + merged =3D uf_union(&node1, &node2); + KUNIT_ASSERT_TRUE(test, merged); + + /* Assert that one of the nodes is now the parent of the other */ + root1 =3D uf_find(&node1); + root2 =3D uf_find(&node2); + KUNIT_ASSERT_PTR_EQ(test, root1, root2); + + /* Check rank after the first union */ + if (root1 =3D=3D &node1) { + KUNIT_ASSERT_EQ(test, node1.rank, 1); + KUNIT_ASSERT_EQ(test, node2.rank, 0); + } else { + KUNIT_ASSERT_EQ(test, node1.rank, 0); + KUNIT_ASSERT_EQ(test, node2.rank, 1); + } + + /* Attempt to union node1 and node2 again and check for false return */ + merged =3D uf_union(&node1, &node2); + KUNIT_ASSERT_FALSE(test, merged); + + /* Union node3 with the result of the previous union (node1 and node2) */ + uf_union(&node1, &node3); + + /* Assert that all nodes have the same root */ + root3 =3D uf_find(&node3); + KUNIT_ASSERT_PTR_EQ(test, root1, root3); + + /* Check rank after the second union */ + KUNIT_ASSERT_EQ(test, root1->rank, 1); + KUNIT_ASSERT_EQ(test, node3.rank, 0); +} + +static struct kunit_case union_find_test_cases[] =3D { + KUNIT_CASE(test_union_and_find), + {} +}; + +static struct kunit_suite union_find_test_suite =3D { + .name =3D "union_find_test_suite", + .test_cases =3D union_find_test_cases, +}; + +kunit_test_suites(&union_find_test_suite); + +MODULE_AUTHOR("Kuan-Wei Chiu "); +MODULE_DESCRIPTION("Union-find KUnit test suite"); +MODULE_LICENSE("GPL"); --=20 2.34.1 From nobody Thu Nov 28 01:48:42 2024 Received: from mail-pl1-f173.google.com (mail-pl1-f173.google.com [209.85.214.173]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 1CDA4175D34; Sat, 5 Oct 2024 21:50:10 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.173 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1728165012; cv=none; b=rMaLk0zFGQgt0o9CBjdEkBz2Pkqqb5TXZ/SA8fk6VS5B9VLuxTTzew2BOVWsaI2L1UY6JIa9CFjcoKc3X3zkyM8NtDUTiMROXY86x9AEN2xhga9g3npxQOn+Lpfcv7f4WDdWrAHqMVc4n6+R/xwSpFgD0LkJxrtFDU6ACwa1uvQ= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1728165012; c=relaxed/simple; bh=aAgtS/55DGRhNRVzeHNfrp0NQH4YCxQhxRW5I5lgpBE=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=Gd65VtgL8WJlteL6AFqn8SslYkh5GVucbNDZpZfQBglLhf+PijL+GZfCYFcKygEsutCNPGh8QtEPsjf1xMjlXDbhHWXL5370VdhBHCZfxIQChXlbgAih2uRW74PClrqX0vc45KoHqyeYW5iSEUlQy0kS9uxJumof4UNHm5GrJHg= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=lkr43FEr; arc=none smtp.client-ip=209.85.214.173 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="lkr43FEr" Received: by mail-pl1-f173.google.com with SMTP id d9443c01a7336-20b01da232aso25805585ad.1; Sat, 05 Oct 2024 14:50:10 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1728165010; x=1728769810; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=e/RDd3OgykNkc6odsd6hV7b7AYM8gkhtHwhum24D1j4=; b=lkr43FEraOaIYxSa8sPkuKRx1sKNpaJdKf/NR3IE/kN7w5eNphm1zpDrZid1YiD3mU WFACPLvcf+yUaSdMtyGs2p0SGHeehaMcJ0KCtK8vDtnM4f40invhgDDlqgRhDDlhxdCK G6NyYKauEGJm7khluSvBpD2R7arpi77kvyjwJLNFhU50OmuIji71A8ZvwtgE8ToVKM5x 699/rRn0++dlGAkNjkGOanLzxsDNg5FJYS/nsbgKIsmOfmaEQN8M2zqUbZuBDd+avPts ZSpunJ7le1OXzwmH+b+g2VKIC254PEd5DHC0vZ5HXa09bEs3mbzXxs22iNLZjpNAfX9g rgDg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1728165010; x=1728769810; 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=e/RDd3OgykNkc6odsd6hV7b7AYM8gkhtHwhum24D1j4=; b=CXvzu19kl7GDkhoym+TreED3/bR7UJjT7ecTc8zDFAJx0MCk5cYSKbUS6EiFHiD2tw 4osR07JSAYehsgRXY1oUSgqUgGR2lfckOseLJa2X1U+zOZXpxN4Qrpw7YsluBS7LY3Ty IqPqUeK3DW9+hjTCCZx41dND9jNwyEo29mb8hMPI270l457aQds0DkSrq0TJxWSX0XtR WGzCO+AouEuf/Y1ukWDsFC9ruZPhfq2tCppBTViLhwcqO37R2L+tXE3gHggD7wCcF7wK l/zOa3EahhhSioPei0uPGziiieOWLxFXd8T+shQW6q+UN4VoKGWAe5zneGXK1xMCwmau /4vQ== X-Forwarded-Encrypted: i=1; AJvYcCWl+nmWE0rHnqSsTI62plgsul6KdfqiJiSU8TFspT2nReDOscCt3zr5RjPmRPU9eQ3un4QdfCtoM58SOyY5@vger.kernel.org, AJvYcCXzH39y0n3Y8isAzhTGF358XPpaRgW8sag0y6TY38r9/lqzDKEuQ64yW61ua4NVBD6r1CwPndBA@vger.kernel.org X-Gm-Message-State: AOJu0Yw1vqvkQQZS5zyfn5f1mZLCvGPwXL65Yf5A1X099FUV/O5pLoqt K+T9+OBgew1zqi6AhQcHxQ4AqDiaNCrC9o4r2zMmMNtTDw57igcb X-Google-Smtp-Source: AGHT+IHkN85dFaHZp7eUqo5HXHSdqmnGE12VAhz/SoR3WLlRAERNoJSPWeMi/AYuB1cCyrPrjJZMaQ== X-Received: by 2002:a17:903:1c9:b0:20b:5ef8:10a6 with SMTP id d9443c01a7336-20bff391262mr103385635ad.8.1728165010287; Sat, 05 Oct 2024 14:50:10 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id d9443c01a7336-20c13931055sm17165135ad.139.2024.10.05.14.50.08 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 05 Oct 2024 14:50:09 -0700 (PDT) From: Kuan-Wei Chiu To: xavier_qy@163.com, longman@redhat.com, lizefan.x@bytedance.com, tj@kernel.org, hannes@cmpxchg.org, mkoutny@suse.com, akpm@linux-foundation.org Cc: jserv@ccns.ncku.edu.tw, linux-kernel@vger.kernel.org, cgroups@vger.kernel.org, Kuan-Wei Chiu Subject: [PATCH 4/5] lib/union_find: Optimize uf_find() with enhanced path compression Date: Sun, 6 Oct 2024 05:49:37 +0800 Message-Id: <20241005214938.2147393-5-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20241005214938.2147393-1-visitorckw@gmail.com> References: <20241005214938.2147393-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Optimize the uf_find() function to enhance its efficiency by implementing a more effective path compression strategy. The original implementation only updated the parent pointer of the current node to its grandparent, resulting in a relatively shallow tree. In the updated version, once the root of the node is identified, all nodes along the search path are updated to directly point to the root. This change minimizes the height of the tree and improves the efficiency for subsequent find operations, providing better performance for the Union-Find data structure. Signed-off-by: Kuan-Wei Chiu --- Note: Tested with the KUnit tests introduced in the previous patch. lib/union_find.c | 9 +++++++-- 1 file changed, 7 insertions(+), 2 deletions(-) diff --git a/lib/union_find.c b/lib/union_find.c index a20678da0220..7c553fa622c8 100644 --- a/lib/union_find.c +++ b/lib/union_find.c @@ -13,14 +13,19 @@ */ struct uf_node *uf_find(struct uf_node *node) { + struct uf_node *root =3D node; struct uf_node *parent; =20 + while (root->parent !=3D root) + root =3D root->parent; + while (node->parent !=3D node) { parent =3D node->parent; - node->parent =3D parent->parent; + node->parent =3D root; node =3D parent; } - return node; + + return root; } EXPORT_SYMBOL(uf_find); =20 --=20 2.34.1 From nobody Thu Nov 28 01:48:42 2024 Received: from mail-pl1-f176.google.com (mail-pl1-f176.google.com [209.85.214.176]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 10E2B176FB8; Sat, 5 Oct 2024 21:50:14 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.176 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1728165016; cv=none; b=K3SoAFJ59HjddyPTRujUW//eFNtBaTk+u3eZkJuAAiOfrN3gx7nai3riuKOPSYH5bBpS33zrSC5dkNC86sgzpLffTBnZpXdNnO9eSka8gm2FE6lu3509hJSPa+YoyZnTqYU4dEuVUAStGMI/meuovQQMH3+PMAJ3vVW3plenbH8= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1728165016; c=relaxed/simple; bh=i/BhTFLd48HomWyz8xZC68ePjxoABU2y+lp5CSpHwuE=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=pZUykJ/FdD0RIgIZ5Sh0wODsoSuX/7sWr2o/6U5CQLwHmw3ob7iArel+s14n5eDPIA1oY0ZHtVRn85YW991rGY0nXdoQlxodY1UEMu1QHTrDjJWui+vR+/Wois7ItKxMsqkxYwa1cTUrUf64st4caenJEZ7Gf6KokHF22lnNinU= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=RGE/D3xP; arc=none smtp.client-ip=209.85.214.176 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="RGE/D3xP" Received: by mail-pl1-f176.google.com with SMTP id d9443c01a7336-20b7259be6fso36227355ad.0; Sat, 05 Oct 2024 14:50:14 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1728165014; x=1728769814; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=zeXtZC/fnaI3e4fw3nt3kTvuPSe90+rJIZz1Zw6u5CM=; b=RGE/D3xPCa/5c0YdF4XgcpwPXqGJl3XAg+5V+GTGbKABwPs+vRYXO5SwncbUJn+Yec dqhNjavRE/gRzabgOfuSD6FmrIw/naoKQPHm+d8exfHBlYi/X4ukH+lT8+6v65P4uClx G8lyW2/7K1QfQi/2vLpRkEb29+xH1y35CMQcdPObgKG0KoWWbX7ltemparYyZ8W+595H Dw6j7cEy8uZimLtsqZbSUPoQvM7g89DAvmp0K5zsLFXzFJATEyUHupD8+VsjDFby+8D9 7U/Xp25IJ9W6ESh2MBmk9IEgVeTXlGkRiDisxr49wWWSGYJiZNXOQlw+bjt0flwlzQXO DCBw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1728165014; x=1728769814; 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=zeXtZC/fnaI3e4fw3nt3kTvuPSe90+rJIZz1Zw6u5CM=; b=BDQvXXgX/m/7QCXeivWeXtO8ZeAgPv9CX2i6G2Ptxkmqtpd1vFs3/bzpdzboibQQ9C 3aYuP0d2T0nwWBAIcWzctAa/Tsan1ltSBO+k5l/G4pfElS15ZXbqroruaEWGYPajQXg3 Ui5qsCjMOTBudD5SjN8hTj7tVzLd5gF4Cr0bj/7ZrIbz8pwxI6k/ot/07RlbBC5CkuRk d6FS4T4dlrpcKtcjRfBr26GA/UCrvmTEMhdJMVMz8KIXjFsWp0ThJ/3fPNYV06zTq20N 9EGqGljJdtjseIjE9WARaHCHuAi6wEs0u6rWlAFishDAiQ/6+WNVJgWIeZGd3JpWjVIc rvrA== X-Forwarded-Encrypted: i=1; AJvYcCV6RDcJqoYrrnAg1LoeYTVSL9kApX6SSqq2+f3lQ1zWeg9EecJU49uCIj2II9vkY0QSuRouVpeFKo3TjC7F@vger.kernel.org, AJvYcCVTLe7g0Ou7zDWoMDsiowR97CHSSDM8KhB/cEwBaM/1wR39DwB+Rfw2TFNb0UoRrNwTh4exhSIN@vger.kernel.org X-Gm-Message-State: AOJu0YwHIBjZsBK4aA9Ps9nXlQZ+Oz+dFjSsT10GYygpd1x38uiz9CoF x1nR99r33WkYfqhCR9FehVK/D8h4I75YcOsbo6FptmjKXa0L1omJ2uYD/w== X-Google-Smtp-Source: AGHT+IGJUD/oCRSpFBXNVaQbMpQpROalL480XnaY1oZ2gclVXGNcQnL7cRD4PLhtmkqn1wNPhgTXNg== X-Received: by 2002:a17:902:e74c:b0:206:9a3f:15e5 with SMTP id d9443c01a7336-20bfe043018mr105109485ad.32.1728165014380; Sat, 05 Oct 2024 14:50:14 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id d9443c01a7336-20c13931055sm17165135ad.139.2024.10.05.14.50.12 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 05 Oct 2024 14:50:13 -0700 (PDT) From: Kuan-Wei Chiu To: xavier_qy@163.com, longman@redhat.com, lizefan.x@bytedance.com, tj@kernel.org, hannes@cmpxchg.org, mkoutny@suse.com, akpm@linux-foundation.org Cc: jserv@ccns.ncku.edu.tw, linux-kernel@vger.kernel.org, cgroups@vger.kernel.org, Kuan-Wei Chiu Subject: [PATCH 5/5] cgroup/cpuset: Optimize total domain count using updated uf_union() Date: Sun, 6 Oct 2024 05:49:38 +0800 Message-Id: <20241005214938.2147393-6-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20241005214938.2147393-1-visitorckw@gmail.com> References: <20241005214938.2147393-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Improve the efficiency of calculating the total number of scheduling domains by using the updated uf_union function, which now returns a boolean to indicate if a merge occurred. Previously, an additional loop was needed to count root nodes for distinct groups. With this change, each successful merge reduces the domain count (ndoms) directly, eliminating the need for the final loop and enhancing performance. Signed-off-by: Kuan-Wei Chiu --- Note: Tested with test_cpuset_prs.sh kernel/cgroup/cpuset.c | 10 +++------- 1 file changed, 3 insertions(+), 7 deletions(-) diff --git a/kernel/cgroup/cpuset.c b/kernel/cgroup/cpuset.c index a4dd285cdf39..5e9301550d43 100644 --- a/kernel/cgroup/cpuset.c +++ b/kernel/cgroup/cpuset.c @@ -817,6 +817,8 @@ static int generate_sched_domains(cpumask_var_t **domai= ns, if (root_load_balance && (csn =3D=3D 1)) goto single_root_domain; =20 + ndoms =3D csn; + for (i =3D 0; i < csn; i++) uf_node_init(&csa[i]->node); =20 @@ -829,17 +831,11 @@ static int generate_sched_domains(cpumask_var_t **dom= ains, * partition root cpusets. */ WARN_ON_ONCE(cgrpv2); - uf_union(&csa[i]->node, &csa[j]->node); + ndoms -=3D uf_union(&csa[i]->node, &csa[j]->node); } } } =20 - /* Count the total number of domains */ - for (i =3D 0; i < csn; i++) { - if (uf_find(&csa[i]->node) =3D=3D &csa[i]->node) - ndoms++; - } - /* * Now we know how many domains to create. * Convert to and populate cpu masks. --=20 2.34.1