From nobody Wed Nov 27 22:24:32 2024 Received: from mail-pf1-f171.google.com (mail-pf1-f171.google.com [209.85.210.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 674A41D8A0B; Mon, 7 Oct 2024 15:28:48 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.171 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1728314929; cv=none; b=PMc7nwax/7I4aonu6JRonAJtoRo5Tppp1H4fD1dgVXAmwgvhGAWVyB8/6UrCCrtjvWdhMAc+ceiYiI4qyjT2Xd6gylqvT0Ddk84GhGWsKDnL5XnTcrIntIS/A/rbW0tsvOitMx7t9W60AXDBybaGrxU5Nby1cVjbqlf+vA+rQHA= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1728314929; c=relaxed/simple; bh=dJ66qSUhaS4Hdlu8QOl+O0n4+V+I4RKTJF4Ex7jtK20=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=r9DM++QL4MjUyQNKbKWuP+aeprDGDl8y7ujcpykjPe29bYszwqo4sizyU854O2ihgpCb3tN8NMc9uv2TAPN++LtBmk5PIvcWtTNg/MjdOyAcTu+lgpaPZPHTfusfBUGeXR8YyBkNqIqCp27AwkDj/g2wdZ3bYlJj7zfAWPcGZDs= 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=YWZzr5Dh; arc=none smtp.client-ip=209.85.210.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="YWZzr5Dh" Received: by mail-pf1-f171.google.com with SMTP id d2e1a72fcca58-71e05198d1dso665370b3a.1; Mon, 07 Oct 2024 08:28:48 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1728314928; x=1728919728; 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=voC1g86BkP/+V85qhBuuOhqNyxDK+S1jUgtJ05iE0V4=; b=YWZzr5DhS58ZINL91OPEpakgGc3aK6a8DwxdjjLoZzufdnq6vVY1R0PpdERbc4NlAA A+TT7z0QOITfk3q47rpKqeTgD8gTr2JqWPaBLCCJcSyzsZlO30Hy/GK1GjK0uKjW18ui tMhr/yuZABklWZND8rdOYEFpi/8xfScIr7L1i54dsUsq3pTgibMgguVBVwjzXSB3VWZ8 1Wfx3zY9+xBkPuTUQCe4BahGihjBwNLvOUaB1ws9fiaNJrXLw4uZlHRhMkvwvsn7DT/R KvCywTXmsZWDivzJdKO+VoyFlLnH+7BbLtpY9jvKtGNAKMlkiwYyor8xCkO+Uc47vIOh 04oA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1728314928; x=1728919728; 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=voC1g86BkP/+V85qhBuuOhqNyxDK+S1jUgtJ05iE0V4=; b=WIUz+f2qsWO9Tgzxl9bCOcTiod5ypwU4KJpN7+k6GRMw887JQ++DVsZcfINBZBft8b z5uy766mjdd0pbd/fj6BA7fPbOi8M9XNIyL7WbUUNCIK6gGMiKHj5WDOSk2DvwXkPAxy iUh/g4SQfrEx74TZ59qbarzC2YE+1ezSbqs2XpUcfXl5o5jIGgRPbHZLfUec7jS9m2II bMZAFaJJTBQOoWpJLjvdIu9AZsFJ23SDL6sSwfOnF408/eQjHtP+xvCMTibZ0IV79IgK UaMDRRUFa+elMLZykuDF8+q48ZsWnKexYFOEG/awpAisJrwArfoPRCX2NVgvggFuEoYv C5nA== X-Forwarded-Encrypted: i=1; AJvYcCWejRQ3ncgzDYz0ypd07Xhb0/4erXKcLAq6/FommRi8cz1epgbkjAoXWdFTOxep64MNSYoSnAEL@vger.kernel.org, AJvYcCX9EnHWcYcYdJRrc8z0698Pp5N0fB2P4K4u3rxATKXB75vo/cguWSXpRwv5TeSbfHVsHG+tH1yAI6dvPxEI@vger.kernel.org X-Gm-Message-State: AOJu0YzgEMQ8bmbDffln/6DNamMejw+uU4Cz459RwZSwhDJUZWKO51Ia n0lcNfl1ijJiRZP1pDGFj/bPK5w6+BWfsRgGg2Cax6z9DWSPeHo8 X-Google-Smtp-Source: AGHT+IEcBsvBOoXPaWjMiUr+UCxTG1R4zJVjDWwUz4MPamOaqvtGNKAjDi7vtp2lx7ueJWaymeKvrw== X-Received: by 2002:a05:6a00:124a:b0:71d:fe40:7e68 with SMTP id d2e1a72fcca58-71dfe40808emr8419097b3a.1.1728314927613; Mon, 07 Oct 2024 08:28:47 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id 41be03b00d2f7-7e9f6c4adeasm4360337a12.84.2024.10.07.08.28.45 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 07 Oct 2024 08:28:47 -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 v2 1/6] lib/union_find: Add EXPORT_SYMBOL() for uf_find() and uf_union() Date: Mon, 7 Oct 2024 23:28:28 +0800 Message-Id: <20241007152833.2282199-2-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20241007152833.2282199-1-visitorckw@gmail.com> References: <20241007152833.2282199-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 Wed Nov 27 22:24:32 2024 Received: from mail-ot1-f54.google.com (mail-ot1-f54.google.com [209.85.210.54]) (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 DC9BE1D9593; Mon, 7 Oct 2024 15:28:51 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.54 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1728314933; cv=none; b=orYVmXD45K0BMz/3bJyfk1wWGuPlTGxiJxcwHt5nYjp3x0Eht/3TEfB10G0mUOYpsd4zVrQRY+qVUh9ezXRq7Qk3j1w7KBTrNvWCDoEPm8Li4ftobK7Jz1CKbWvVHBPuCZv4Mn3ezTjSWmuE5cTMZTyKLhBQv4ArTSmoy5v9nOU= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1728314933; c=relaxed/simple; bh=pmII0JW/KQDCNY1pEAAKxAI6HvOubKGy6U2Nj7h8+N4=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=R5vhA+L0KUWsvAmgmh95BSkyC8QQbXCNJngadg/jYkRG79nKsge34k1XcOAAbN1GO34JpNQCmWcikCHGMAdLewp7mH9QAnSPvhe0QCmuW2oYFvisRFeKwpZeq9ZUNerxpiyP+uCfm/xvSu3K9n1Orpf1zh2NNG9C07QM59sJ6UA= 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=GQzccLln; arc=none smtp.client-ip=209.85.210.54 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="GQzccLln" Received: by mail-ot1-f54.google.com with SMTP id 46e09a7af769-710da656c0bso1758157a34.0; Mon, 07 Oct 2024 08:28:51 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1728314931; x=1728919731; 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=ClTLohECAof//FoFt3H1m3SEt+JHyEO+9qrUd3WdsjQ=; b=GQzccLlnVaxzJmPTwic39lv/wcYy5GIM/eURy82EAoKi0Q65Gu/YMzi8TTu5IityF0 L9o+krmbWUWneNnNwWi6YCN8z3rifRuup43ae4c0I0WMRsQkcGV6zalBK2rMHl8qkKHE 1CXUk3arVWM1GrFG58am8zKduO92mWE/fjZh4nSKTgXTojCG2m2Jbov0n1nG/YZmW4/h Wq3Ivgif9QfmWSd7QsQASdOChDYp+xsFTuld4qSupUq4nEgOo2BCmxszTlCKX3tN93uv njnJtO/9x19xMi9DIM2Bl4ryWpZzE3zCeKwjVVqPpGr8Jmz4MQM9+FoqfYTPVahs5/o9 JxfA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1728314931; x=1728919731; 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=ClTLohECAof//FoFt3H1m3SEt+JHyEO+9qrUd3WdsjQ=; b=No/qbNAuQucrpfubG0wn5uUpiiSDOCt7f0z/JXYGqic3bAq+HFWxwidqXn6gGVy9Ap 7BDWVDQojQbAbk3f+thcTZe+ik1q7EAzpxKsMC1O9pThL9z44FYbj9LCG/jMAn9nFOSK G/lFeQ7SGVF7BRv5nw042FrFnrNNzMQY+fJRgyELhIx1MjeiIyV1+m44eDUQHpglju4+ kF3myEZ528rY+ezCadYxEFr63uEyp7YRyfwJ4aBLcut+5rX7MbIygc+L5k9gXEmSMWYZ EqkcTpEdWlGZOMEHE7MM++4v+OGPlnFSvYJkMaksWlzt+OZr9PjTINFIcp4vw5Yj/5U9 YlrQ== X-Forwarded-Encrypted: i=1; AJvYcCWEb53QSnIyyy0OVjZuZDmzSCeqkXPEuf1uaET8A2DL7APxJxjo0gsmhYKZMqEPQqZS+ViGXuHarZrCgUSA@vger.kernel.org, AJvYcCXIANHU+a2+VCR59MkPjXt7fAzntMyr9TN2wIX2a14FL/YnazdWJsgmq+BToD2AA4oh/8d+14Gw@vger.kernel.org X-Gm-Message-State: AOJu0YzPll/LlrdYKmntkbk9L3jwgmxBDHJzUuOG4mla/WqY7y83H8XU wV9kiCEdNtT6i6Eott6fbzb6YLfw2gTV6DYg2k8nG8QTT4TNCpJn X-Google-Smtp-Source: AGHT+IGPFkSciSx6WIIbL+g3mcSC01w5WNqKfZ6UyyRwmbJxKmqft2jt9SQbyco8ycn9HnFWeYmqlA== X-Received: by 2002:a05:6830:a91:b0:712:4021:b043 with SMTP id 46e09a7af769-7154e97c082mr8285195a34.23.1728314930976; Mon, 07 Oct 2024 08:28:50 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id 41be03b00d2f7-7e9f6c4adeasm4360337a12.84.2024.10.07.08.28.48 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 07 Oct 2024 08:28:50 -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 v2 2/6] lib/union_find: Change uf_union() return type to bool Date: Mon, 7 Oct 2024 23:28:29 +0800 Message-Id: <20241007152833.2282199-3-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20241007152833.2282199-1-visitorckw@gmail.com> References: <20241007152833.2282199-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 Wed Nov 27 22:24:32 2024 Received: from mail-il1-f174.google.com (mail-il1-f174.google.com [209.85.166.174]) (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 4C2211DA0F1; Mon, 7 Oct 2024 15:28:55 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.166.174 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1728314936; cv=none; b=qEu/+Sv2wGpMYv3XKtfPFN3I4itfIuClbM6SQZNy5NBChn6NWjwNE8ahI9X71camaK1dfh+3Qbg99mS/k8r2sqiEC4Lk4btahti4keRku10xuKRvFsbZDJOTlQ7EUBuC8XljwF4Atdlc/OF2wfRaDmozJjJLLRby3KEgKFn8FPI= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1728314936; c=relaxed/simple; bh=56mTJe+siYhvNNQ3zivndYFHjNda7FgDUh+1vF7qwmU=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=umL2BEFIwpGZ5HtWNY+BrcdOVsasmDncrqzBw+Ejh/9NSdhzBiDc1DOtKjUoCu0TV/uFvrQGiYZRH0Fngx3FS+fROzMqwxK0b3VVL9tRYqPYtGUDNsXS7aip6/3uy+LzDGcS+PDKOLCelfM4p68rGWJILC9Unkl+I3bxBa/Tw8E= 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=h27J5lBF; arc=none smtp.client-ip=209.85.166.174 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="h27J5lBF" Received: by mail-il1-f174.google.com with SMTP id e9e14a558f8ab-3a27599274eso11781435ab.0; Mon, 07 Oct 2024 08:28:55 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1728314934; x=1728919734; 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=jfeDMwa0mGsEZvqgK4VshjmFCBwUkEJGgi7ASvgAtCo=; b=h27J5lBFAD150rhqurqk75I+ii38YEgsHd2Nq6nT2KAiTtLjQPndeGEMI5dX052Lu8 x1IcINE3ffDVBbtFZ2lI+y15YWYCezR1bkg2/y5i4o50ImF/lyNqrX76C4tkifNvgmwq yaMkwSymkPOsHhfLEe/6WZXA/ddAqmowWDMrTKEAfy+i4CeACJPMYU46wv2QadPK/YaY c3KEDrdNn7+rJj3Rd2e6TafwOZ5ijuDZ+JT7XPYUiun+o7tihnV9fpADsPGFkGQwkLa8 83wnGMvkgFh+1fvSBSWNjyOcArWAytGmMKclegB9vj0DmJHfZQohQoFOMpV/wj3muaIy AozQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1728314934; x=1728919734; 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=jfeDMwa0mGsEZvqgK4VshjmFCBwUkEJGgi7ASvgAtCo=; b=IAx2L1FaOQ4CwjhympZRTf5wWva6ZJRw1S3ZWq7kXOqaNkVkupl0syOOoRu0zl+Xnc QOYS5g1Pz+jfDxszZfsk0kMEZxQ5oDW6xkK4f8s971wh/9SS8tTTD4DA4uxV/kNX5oJl b0xyY6BH4jV669KYJZTFKJArSKhptdVRodnYnJEgHV7R3fzJQR5NYa9xwzgfoD5AOQiB 43kM0W2HvvF5aMxS51i0hgJ3O+/Ghd0VJs335uDBObbT7o0mHn28eBoJK1B0h4m/57Hl G08nYSVSI/hGrY5Cb76PIhqSYyh+6algQ5l3OUsdtrGEkehCjfjp7CKY1coY1NAd1fQq C07Q== X-Forwarded-Encrypted: i=1; AJvYcCUfcqbJau0v5tMM3bQ4djmg0eewIWbrGTg1hvOaDTz6blx3G4r8K5F+wjIUxeWhPeslJsjcpC5x@vger.kernel.org, AJvYcCUh8GJEOwV8Dh/FWjgcFAsz24+nYHEE6BznkFIVUom7spgr7zwFt5vEVCoG3MZ9Sr7U+2QRIS+ViJo8nbK/@vger.kernel.org X-Gm-Message-State: AOJu0Yyeu7NgyCVSO+ZpOPOsUcmuRufcsoqFqNXktwVakEFlwkPEvSmu Qc70p1lGqXF1Nwhd+HOJj60ZZjhJKIxnFO/GvIyNuUzmNIDev9J9 X-Google-Smtp-Source: AGHT+IGwFQ5Mj6pyuFxLgLgdveH2IKrWbSgcvPNfIHFse5w32d4E01+pki6CGjW6TeuhbjXz6yJ/JQ== X-Received: by 2002:a05:6e02:184c:b0:3a0:378a:884b with SMTP id e9e14a558f8ab-3a37597a23dmr104389405ab.3.1728314934238; Mon, 07 Oct 2024 08:28:54 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id 41be03b00d2f7-7e9f6c4adeasm4360337a12.84.2024.10.07.08.28.51 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 07 Oct 2024 08:28:53 -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 v2 3/6] lib: Add KUnit tests for union-find implementation Date: Mon, 7 Oct 2024 23:28:30 +0800 Message-Id: <20241007152833.2282199-4-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20241007152833.2282199-1-visitorckw@gmail.com> References: <20241007152833.2282199-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 --- 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 a097afd76ded..e503802c1549 100644 --- a/MAINTAINERS +++ b/MAINTAINERS @@ -23801,6 +23801,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..f8c09dd0590b 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 Wed Nov 27 22:24:32 2024 Received: from mail-pf1-f175.google.com (mail-pf1-f175.google.com [209.85.210.175]) (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 8CE611DA60F; Mon, 7 Oct 2024 15:28:58 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.175 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1728314940; cv=none; b=Q3wmg0IuY7ScTmU+AqtDQPDphO/jnBV3zPpjKL5OmxKSFbRD0Pe8zEyievct/VfqV5/NbE4BBamn1bumvZQc/SdJR7U7AQrUIayY1po7Y1vTKL38jbbkSCYNYNJUtQLOO8HzTixhffVsO/JISv1atLnrMS7+mhQIwo5/98Edztk= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1728314940; c=relaxed/simple; bh=gTjP83WTuybGiDFLufp9WtByb/SPoKCyFhxnlBLVOQs=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=Q9Vewq775u/Svd3o79J+lgG71NZXmPb2U6nCptgJ+rI20qv1vI2S7ZfFQXk/sO5dGzJAp+BLHDW0tgyUdfjK9uJC8/uEeRZh6ALCDBY2whu9V85h03fWiP+133ZG2LGGCNXD6cEIWgXetzL36JNfrHkPsqvck6fxL7NNqYxZ6R0= 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=dGmugt15; arc=none smtp.client-ip=209.85.210.175 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="dGmugt15" Received: by mail-pf1-f175.google.com with SMTP id d2e1a72fcca58-71df4620966so1925759b3a.0; Mon, 07 Oct 2024 08:28:58 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1728314938; x=1728919738; 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=rcMNpzO9xVZEqN5WJI+Z0rS/5IVpbeChfW9TRj+rYMw=; b=dGmugt15sbULWFc8yTf0ifaVHlKchG0WDSzhxJvgl/NuvMB7H3MSPNQFXChIwkNHUn YxFrPVqu8zyFmIdu6iAnPbrPSKPJdBlZtcyY/r0hePHeQMPHQ/lQWG8j7r0wpZSfWIvi b9ESOWTzFegbCNmP7r0dFfizBIPKeY2QK/xRr3ALbcpy1bazVegjllu6sb36Wi/IOJtl Z1MH67Y3LSI2I1NYR8pSuC60Azt/ML82AYV9CNDMCtsfEpiHsKtIcfEOTINL4gkHhjLS Nh22gSwG3GyZ1cXzXM46NH6KId1pWl8yJgJnZMsjYUSNme2TgQ1fK8tQ6d4zXDu2l4PI jXxQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1728314938; x=1728919738; 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=rcMNpzO9xVZEqN5WJI+Z0rS/5IVpbeChfW9TRj+rYMw=; b=qDHfOhubGWcNq2ApmAdHn2FXRvc3qQwOVZF/n9q6Ln5Qx3SbtBxmy7+Lh+BnOoY+ef FqMhZep9kZyIXUTdjqW7HPtsABI7GndV1Ipp/wFB639A1jquF8egd3r72/vjsFvIBOjO 8q5Bt2p4moxjQfnZmIh0UANU55UZ+3/+m145+yLaNzHyfn7/CKlBL/QNEr1+yWS2YuSO 0dLgcxbhZcoagne1BSw/YHIRJu7G4HXetl90bvpXt062mxTzREgY9upmULahKUZCey/D k80gT/UArlH9LWnTbnQs/o3Kzv1mDMTcvV8COVkSeEYiKGZHmG5BU1LgJ+v9djyJZiue 1ImQ== X-Forwarded-Encrypted: i=1; AJvYcCVZsmcg+tMrcTJuDiC4FuJ+EUTuMw2Peduox8TewxmDertmEX8t7vXFh+Jed/wRoidgkqcokz/slY29pGoI@vger.kernel.org, AJvYcCXKeSnCT4OYrkOvXXnr1V/YUYKMtksaVdeHrIi4IXXlNZ1+XQU4WT+w+/FyNf3LszLlCzdP6D2J@vger.kernel.org X-Gm-Message-State: AOJu0YzFBoqjD39R6J5iA2dvw9VNhOnpfxTi9v/dp8i8EkmR8rsGLjCG A+mY/UaVED9SsQW4GwWKNdJPI3/rlww4mHJfOekxYFKGzEeYyMn9 X-Google-Smtp-Source: AGHT+IFwU/p1ltG4BTXRfs8ffnBeYCy9p4lErF47u4sf4jnfTruMYwUh6Tohx6NLVKOYBv/8bI7xng== X-Received: by 2002:a05:6a20:1d98:b0:1d2:eb9d:9973 with SMTP id adf61e73a8af0-1d6dfabb82amr17414312637.39.1728314937823; Mon, 07 Oct 2024 08:28:57 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id 41be03b00d2f7-7e9f6c4adeasm4360337a12.84.2024.10.07.08.28.55 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 07 Oct 2024 08:28:57 -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 v2 4/6] lib/union_find: Optimize uf_find() with enhanced path compression Date: Mon, 7 Oct 2024 23:28:31 +0800 Message-Id: <20241007152833.2282199-5-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20241007152833.2282199-1-visitorckw@gmail.com> References: <20241007152833.2282199-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 | 11 ++++++++--- 1 file changed, 8 insertions(+), 3 deletions(-) diff --git a/lib/union_find.c b/lib/union_find.c index a20678da0220..d2b79065cbc8 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 (node->parent !=3D node) { + while (root->parent !=3D root) + root =3D root->parent; + + while (node->parent !=3D root) { 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 Wed Nov 27 22:24:32 2024 Received: from mail-oi1-f178.google.com (mail-oi1-f178.google.com [209.85.167.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 11C7D1DB35A; Mon, 7 Oct 2024 15:29:01 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.167.178 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1728314943; cv=none; b=QVelFO6VADw5Ku5EW8//VTCJz4ezuhZYaNk9mEnGaNMHC/XmPXZyulChl5PlOoIoZPva7cv8C9oiP/TzuwMINVQmi6AWWxubogGif3Fijj2m+E31OfOBSn7VS60V7yvtVS6NT+NJBdpP4diHhkSoFH9rfPkN5vxE834cw+NgpoE= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1728314943; c=relaxed/simple; bh=OMtfmt7UZCIHfOf7KAR4/uFdCOm7TfQjEgGNpTHnfL8=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=Gwzgvfe+ugNd5gnwEFYGhDZbjSPzKX8/RhMl/WSKEDMAgO7840OjSA6rdkV981NeEarqJw3oNkbZENdeFAI9vN3G5k3FbKaMuvJymue5gDytDXQJKBHQpRfeZguuWTt/dHTXEpsWPJ3NKLuntU2tb+fOLZSuURkA7oNIMpOhza8= 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=OV4ByXZ5; arc=none smtp.client-ip=209.85.167.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="OV4ByXZ5" Received: by mail-oi1-f178.google.com with SMTP id 5614622812f47-3e045525719so2843289b6e.2; Mon, 07 Oct 2024 08:29:01 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1728314941; x=1728919741; 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=TUEA4tpkfLGZlVDysJGJlt9DafoclzzPF7zKuIYvfmQ=; b=OV4ByXZ59kpI/G6LMUXx7St8TuvbCMpJdYwahud8TZ38RWvVV4RK3+FQp5xmoINDrl Fto2aB1cswNXMxWBxegZi3jrwyT+n4OKjYzPQKfjWU9SyS8HojjA16gbVwyYulmbxKzz 91hVsM3QBcShN+SSx2J3ykoJ3klq0BfpHtDyiZhRzwxAIGIM2gCh1hLIsf3/Y1xb/XQs Eg4zLreUXr9uP1/73IC1PYiY0mKqEn+syDkyampcgwZT8tn6g77vqyrbiFJDk9lpsdUT h2n90R5sfSZNFckQ5qUGl39Sh9yeNhGqMH0lwffrtO+7IQBtlozjqX1SD20buNYHDBki UECA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1728314941; x=1728919741; 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=TUEA4tpkfLGZlVDysJGJlt9DafoclzzPF7zKuIYvfmQ=; b=gtU4uUY4YW9YJloBZeznltJAdlqo5pOT6q4J/V+FPxMlb3AkhMYPY9YM+RaVVFghVI j19QidLx6g8LmyKFm8w8JYAlC47XHsuTgMepBdkAvBiX6hAxN34eP/VeGgKmeE3ZjjOl 0Ap4P18G9ciFOgKaAu5ikRmlc5LGcEL6DQyzPXSz/mMueQbluPekEAiv075tS/Z98rlB OSderh8algRtoaRXquwoUD/KJxA329/mrTFSzbe7+94e/hy14CENlrFszhJmT7zVbMCH 2j91QYkrjuvNabTANQEFz4rqi5fu6wLBwUVor7vqp0Y/ks5Eu8/aZcQ8ckOaQoBrHeqo Qxvw== X-Forwarded-Encrypted: i=1; AJvYcCWfqco+PE4CsUILSYsYsyH/xdI35SFmwRH7uwDvfqeP4bnWse8xfhZmUSrKsrXcC4PIIEgP8nq17VHYRCyg@vger.kernel.org, AJvYcCX6suzzdKSW9cvctMho2ioCNG2p3tVQ4Ru3uri66Yk5/rKaPQs1nKwbCpS9sCK8qG2melu2Kkdh@vger.kernel.org X-Gm-Message-State: AOJu0YyMeFnExeEMQ6pnWiB1cS06nk3LS7WSre5KG1hvofWH5pYLiIy3 XPyraGK9ZPI3ZfbVRAhOKrZaNEx+7/By2yif64jvpy8Bf+EayVTZliGcCA== X-Google-Smtp-Source: AGHT+IEbsvR2Q7CP/P+iNUTYbqnLzzq8TPA6J0V2in9TiXF4gmOs+v8wadba5eKZVpOf1AV5HpKv4A== X-Received: by 2002:a05:6808:3a10:b0:3db:3303:834c with SMTP id 5614622812f47-3e3c156c02emr7865565b6e.39.1728314941113; Mon, 07 Oct 2024 08:29:01 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id 41be03b00d2f7-7e9f6c4adeasm4360337a12.84.2024.10.07.08.28.58 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 07 Oct 2024 08:29: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 v2 5/6] cgroup/cpuset: Optimize domain counting using updated uf_union() Date: Mon, 7 Oct 2024 23:28:32 +0800 Message-Id: <20241007152833.2282199-6-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20241007152833.2282199-1-visitorckw@gmail.com> References: <20241007152833.2282199-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 Side note: I know this optimization provides limited efficiency improvements in this case, but since the union-find code is in the library and other users may need group counting in the future, and the required code change is minimal, I think it's still worthwhile. 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 From nobody Wed Nov 27 22:24:32 2024 Received: from mail-pf1-f174.google.com (mail-pf1-f174.google.com [209.85.210.174]) (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 17FA11DB555; Mon, 7 Oct 2024 15:29:04 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.174 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1728314946; cv=none; b=f8bNzURNOy/dVtaVpXlWgJ7LG1ht51OEDxDavOaWySFdhltz/E8eh7pSrZ0DqrE3ZUIBTrjCh2ygmyveKWzC5wdd5x/e2hlfrapuZspl1t1OeWbLxJlPHVmwd2f6KnHfLVdwWqEwpUQO0iOv4S3Lg5NNAkehVBVywp2QcwDGKTc= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1728314946; c=relaxed/simple; bh=lAFXFSmVQdntEsKGiZXrEtWfDysFXzmsqFsCELUq0l8=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=iRWarEg+FaB1Qy+JhTl7p6oPwWPyiJsDptUz9V4DNh3nRXuoIAwTNMguCYYIL+jeykb+qEl0OHD7NhGgMwa2KwexPDqNDjvu7ijSTj4oNvdHhwRY4zxGTDFOmelxY7TW9rb1Ka01/C3k5oxZrfnVpBpHNPzQw1XXTBSp+utKOu0= 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=TlRX04vr; arc=none smtp.client-ip=209.85.210.174 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="TlRX04vr" Received: by mail-pf1-f174.google.com with SMTP id d2e1a72fcca58-71def18fe1cso1674016b3a.0; Mon, 07 Oct 2024 08:29:04 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1728314944; x=1728919744; 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=yzLZEFlScs6iq6xva3+0NW6bF6ERo7epGwi/efUM6jE=; b=TlRX04vrt2JDmaaQYQRnOBF7mk8qQrNbBE+q3gk2r9NPx3nuaQnXIbbI302FP8srhS 7jgjzRQ3k/N+oPKcPTUNDLeRfVqBx/toTFNiLFoFyOAWxzFJNbMAz271hyPB0p0ODWDg UIjdQ1aoJSJi51OeOB/CdgDfs6NLkb8ZZuR62TlEK32gqqZxpkmcaa1kVPUTv2SBnMGd ABiQdQtBZjfrcQUtjT4YOwNy+/Ou7IqpJFha6JsncTQ4kdGJ3GLT+/6gppFSQHlQwPkw ZJvqmxYt1Ivmi3zXe3zhByvexPIFHteaEtDCOPb1pJbpI+fEsWcOxc2WQZ3RXcTdwMF8 rgMQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1728314944; x=1728919744; 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=yzLZEFlScs6iq6xva3+0NW6bF6ERo7epGwi/efUM6jE=; b=XPCWNgvmYFGhy9R1uo0fI2KtCtAmxRw0L8FluXnCKyX2eQ3nQgzrLDDNtw2KMMMIwF MuTVo9O9hvUl0M6aqoq/zQ0fCsvbOegQC8J0qmfxTWqIwrClk4H6cmocK7kXl9/APDHg gSkj7f4ZCTtcsd4BFKMjQLMzL43edrVgFwKcOFBZzqiAHEZ7r7jsbH3jE5fESG+muPZN w7n6Lb6M3c+ModkqIaB3EZRdSmLjV4CyCx16JxEx2ihwn9IKN/9L7w6M10HOdmXyepzY rgflrZDRKfZm2yXBcgunDUuFc5MuCt/IeSEUEr0i+/9SZhhLIXhWqzJu4OqwFzeaPvmm t0hg== X-Forwarded-Encrypted: i=1; AJvYcCVC3F1ivrAbqrrlx5aDRQ3zZo1LcHrOryzwGjHLz5dtHtmF+Mh60+0Z1t1yeK6VldpP6gJ41VNN@vger.kernel.org, AJvYcCWw8pvSZKlEqWgOX79ErCaFO78IHHbxyMool7dctrUYmT26i91XTYkYGDYhTDOe0eQIwOiS2OI0v6Yx9jy4@vger.kernel.org X-Gm-Message-State: AOJu0YyScVL8UA0Ewr18iZB5mXJ2BU98DB5sdj6lRSxqruFpeqtraEdO Vw1MgKFxSPg+zfv79cVlnB4szXU1IO/8PK71dNXFoj51+NpqFOh+ X-Google-Smtp-Source: AGHT+IFmaJYCgfcqvpx9xMLTLS2Sq4+nITc7aHu4JzeIwZmZ/djVHsSyztw51ABu/SMp/FED+S4UpQ== X-Received: by 2002:a05:6a00:2286:b0:719:8f48:ff01 with SMTP id d2e1a72fcca58-71de239d691mr20702748b3a.6.1728314944374; Mon, 07 Oct 2024 08:29:04 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id 41be03b00d2f7-7e9f6c4adeasm4360337a12.84.2024.10.07.08.29.02 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 07 Oct 2024 08:29: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 v2 6/6] MAINTAINERS: Add Kuan-Wei as co-maintainer for union-find Date: Mon, 7 Oct 2024 23:28:33 +0800 Message-Id: <20241007152833.2282199-7-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20241007152833.2282199-1-visitorckw@gmail.com> References: <20241007152833.2282199-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" I'm happy to help maintain and review patches for the union-find data structure. Add myself as a union-find maintainer. Signed-off-by: Kuan-Wei Chiu --- MAINTAINERS | 1 + 1 file changed, 1 insertion(+) diff --git a/MAINTAINERS b/MAINTAINERS index e503802c1549..c3b1a5641765 100644 --- a/MAINTAINERS +++ b/MAINTAINERS @@ -23795,6 +23795,7 @@ F: include/uapi/linux/cdrom.h =20 UNION-FIND M: Xavier +M: Kuan-Wei Chiu L: linux-kernel@vger.kernel.org S: Maintained F: Documentation/core-api/union_find.rst --=20 2.34.1