From nobody Mon Feb 9 05:43:05 2026 Received: from m15.mail.163.com (m15.mail.163.com [45.254.50.220]) by smtp.subspace.kernel.org (Postfix) with ESMTP id D909D1C9ED5; Fri, 28 Jun 2024 16:15:18 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=45.254.50.220 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1719591322; cv=none; b=rlYBAx9PRLNBJdB84io7hER8Ziymkl4whlBZ1va+AavgUeWisVsDSZdy7IUxqGM1R3/7PMGuBBrZQZ4FDsGKNybOImUmC2gtETh5t4fDyBzAukEOloQHn3e89+1j7LjBrZ2E7Lsi/x5hCx0W2uUbeBVZQl5HbpRQzowQVMvjIlo= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1719591322; c=relaxed/simple; bh=D/snAQlDcQQ9do7vedFVD99WGAZq3G7CxJRNItcEF6o=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version:Content-Type; b=uPfihEloLOXoYcB/+c4djFckgfRaxzb4YxQpjVkZ3qP4Pscf/MDOoVFQamJwqRjGAJiR4fB2IZdmYA9w/95iLoIszC7Lj/NccpoKNrXWI8q8CXyC2RAsDuUZhZfjds892lmb12hkeVImoqwzrcAD1U1cps4KCD8O+Az1ozuIvHI= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=163.com; spf=pass smtp.mailfrom=163.com; dkim=pass (1024-bit key) header.d=163.com header.i=@163.com header.b=WdY0Ck48; arc=none smtp.client-ip=45.254.50.220 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=163.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=163.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (1024-bit key) header.d=163.com header.i=@163.com header.b="WdY0Ck48" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=163.com; s=s110527; h=From:Subject:Date:Message-Id:MIME-Version: Content-Type; bh=eMeYN2wilMNzDh96F/mc42pvimeH08nOZXveOIA/3YE=; b=WdY0Ck48zety3wJt1JoC/u68kEOmbJsC0MPzvEZN06WAyVoibpSeAGI1a38UQJ p+lW1Ajv0ZyU3uD83ViEyNhBteNC4qgkPcXfNkVgxy6n3mlMfIQyrjwRMMhE7HMT K3N0QmAXt0/NdLxhmjZclKgC9c2AimW/mV37r4uaDYs2Y= Received: from localhost (unknown [101.132.132.191]) by gzga-smtp-mta-g0-4 (Coremail) with SMTP id _____wDnz0IQ4X5mFkZgAw--.61883S2; Sat, 29 Jun 2024 00:13:04 +0800 (CST) From: Xavier To: tj@kernel.org Cc: longman@redhat.com, mkoutny@suse.com, lizefan.x@bytedance.com, hannes@cmpxchg.org, cgroups@vger.kernel.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org, akpm@linux-foundation.org, Xavier Subject: [PATCH-cpuset v8 1/2] Union-Find: add a new module in kernel library Date: Sat, 29 Jun 2024 00:13:01 +0800 Message-Id: <20240628161302.240043-2-xavier_qy@163.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240628161302.240043-1-xavier_qy@163.com> References: <20240628161302.240043-1-xavier_qy@163.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable X-CM-TRANSID: _____wDnz0IQ4X5mFkZgAw--.61883S2 X-Coremail-Antispam: 1Uf129KBjvJXoWfJw48ury7GFyUCw47Ww4Durg_yoWDKF13pF ZxGryfAw4DJryUury0krW5Aw4Sva4rGrWUGa1xJ3W0yrnIyr10qF4jy34rtr95Gry2yFy8 XF4agw4rZ3WUJ3DanT9S1TB71UUUUU7qnTZGkaVYY2UrUUUUjbIjqfuFe4nvWSU5nxnvy2 9KBjDUYxBIdaVFxhVjvjDU0xZFpf9x07UoUDXUUUUU= X-CM-SenderInfo: 50dyxvpubt5qqrwthudrp/1tbiYxQMEGV4JBMeeQAAsm This patch implements a union-find data structure in the kernel library, which includes operations for allocating nodes, freeing nodes, finding the root of a node, and merging two nodes. Signed-off-by: Xavier --- Documentation/core-api/union_find.rst | 101 ++++++++++++++++++ .../zh_CN/core-api/union_find.rst | 86 +++++++++++++++ MAINTAINERS | 9 ++ include/linux/union_find.h | 24 +++++ lib/Makefile | 2 +- lib/union_find.c | 33 ++++++ 6 files changed, 254 insertions(+), 1 deletion(-) create mode 100644 Documentation/core-api/union_find.rst create mode 100644 Documentation/translations/zh_CN/core-api/union_find.rst create mode 100644 include/linux/union_find.h create mode 100644 lib/union_find.c diff --git a/Documentation/core-api/union_find.rst b/Documentation/core-api= /union_find.rst new file mode 100644 index 0000000000..38d63b16e5 --- /dev/null +++ b/Documentation/core-api/union_find.rst @@ -0,0 +1,101 @@ +.. SPDX-License-Identifier: GPL-2.0 + +=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D +Union-Find in Linux +=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D + + +:Date: June 21, 2024 +:Author: Xavier + +What is Union-Find, and what is it used for? +------------------------------------------------ + +Union-Find is a data structure used to handle the merging and querying +of disjoint sets. The primary operations supported by Union-Find are: + + Initialization: Resetting each element as an individual set, with + each set's initial parent node pointing to itself. + Find: Determine which set a particular element belongs to, usually by + returning a =E2=80=9Crepresentative element=E2=80=9D of that set. This o= peration + is used to check if two elements are in the same set. + Union: Merge two sets into one. + +As a data structure used to maintain sets (groups), Union-Find is commonly +utilized to solve problems related to offline queries, dynamic connectivit= y, +and graph theory. It is also a key component in Kruskal's algorithm for +computing the minimum spanning tree, which is crucial in scenarios like +network routing. Consequently, Union-Find is widely referenced. Additional= ly, +Union-Find has applications in symbolic computation, register allocation, +and more. + +Space Complexity: O(n), where n is the number of nodes. + +Time Complexity: Using path compression can reduce the time complexity of +the find operation, and using union by rank can reduce the time complexity +of the union operation. These optimizations reduce the average time +complexity of each find and union operation to O(=CE=B1(n)), where =CE=B1(= n) is the +inverse Ackermann function. This can be roughly considered a constant time +complexity for practical purposes. + +This document covers use of the Linux union-find implementation. For more +information on the nature and implementation of Union-Find, see: + + Wikipedia entry on union-find + https://en.wikipedia.org/wiki/Disjoint-set_data_structure + +Linux implementation of union-find +----------------------------------- + +Linux's union-find implementation resides in the file "lib/union_find.c". +To use it, "#include ". + +The Union-Find data structure is defined as follows:: + + struct uf_node { + struct uf_node *parent; + unsigned int rank; + }; + +In this structure, parent points to the parent node of the current node. +The rank field represents the height of the current tree. During a union +operation, the tree with the smaller rank is attached under the tree with = the +larger rank to maintain balance. + +Initializing Union-Find +-------------------- + +When initializing the Union-Find data structure, a single pointer to the +Union-Find instance needs to be passed. Initialize the parent pointer to p= oint +to itself and set the rank to 0. +Example:: + + struct uf_node *my_node =3D vzalloc(sizeof(struct uf_node)); + uf_nodes_init(my_node); + +Find the Root Node of Union-Find +-------------------------------- + +This operation is mainly used to determine whether two nodes belong to the= same +set in the Union-Find. If they have the same root, they are in the same se= t. +During the find operation, path compression is performed to improve the +efficiency of subsequent find operations. +Example:: + + int connected; + struct uf_node *root1 =3D uf_find(&my_node[0]); + struct uf_node *root2 =3D uf_find(&my_node[1]); + if (root1 =3D=3D root2) + connected =3D 1; + else + connected =3D 0; + +Union Two Sets in Union-Find +---------------------------- + +To union two sets in the Union-Find, you first find their respective root = nodes +and then link the smaller node to the larger node based on the rank of the= root +nodes. +Example:: + + uf_union(&my_node[0], &my_node[1]); diff --git a/Documentation/translations/zh_CN/core-api/union_find.rst b/Doc= umentation/translations/zh_CN/core-api/union_find.rst new file mode 100644 index 0000000000..e1b5ae88da --- /dev/null +++ b/Documentation/translations/zh_CN/core-api/union_find.rst @@ -0,0 +1,86 @@ +.. SPDX-License-Identifier: GPL-2.0 +.. include:: ../disclaimer-zh_CN.rst + +:Original: Documentation/core-api/union_find.rst + +=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D +Linux=E4=B8=AD=E7=9A=84=E5=B9=B6=E6=9F=A5=E9=9B=86=EF=BC=88Union-Find=EF= =BC=89 +=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D + + +:=E6=97=A5=E6=9C=9F: 2024=E5=B9=B46=E6=9C=8821=E6=97=A5 +:=E4=BD=9C=E8=80=85: Xavier + +=E4=BD=95=E4=B8=BA=E5=B9=B6=E6=9F=A5=E9=9B=86=EF=BC=8C=E5=AE=83=E6=9C=89= =E4=BB=80=E4=B9=88=E7=94=A8=EF=BC=9F +--------------------- + +=E5=B9=B6=E6=9F=A5=E9=9B=86=E6=98=AF=E4=B8=80=E7=A7=8D=E6=95=B0=E6=8D=AE= =E7=BB=93=E6=9E=84=EF=BC=8C=E7=94=A8=E4=BA=8E=E5=A4=84=E7=90=86=E4=B8=80=E4= =BA=9B=E4=B8=8D=E4=BA=A4=E9=9B=86=E7=9A=84=E5=90=88=E5=B9=B6=E5=8F=8A=E6=9F= =A5=E8=AF=A2=E9=97=AE=E9=A2=98=E3=80=82=E5=B9=B6=E6=9F=A5=E9=9B=86=E6=94=AF= =E6=8C=81=E7=9A=84=E4=B8=BB=E8=A6=81=E6=93=8D=E4=BD=9C=EF=BC=9A + =E5=88=9D=E5=A7=8B=E5=8C=96=EF=BC=9A=E5=B0=86=E6=AF=8F=E4=B8=AA=E5=85=83= =E7=B4=A0=E5=88=9D=E5=A7=8B=E5=8C=96=E4=B8=BA=E5=8D=95=E7=8B=AC=E7=9A=84=E9= =9B=86=E5=90=88=EF=BC=8C=E6=AF=8F=E4=B8=AA=E9=9B=86=E5=90=88=E7=9A=84=E5=88= =9D=E5=A7=8B=E7=88=B6=E8=8A=82=E7=82=B9=E6=8C=87=E5=90=91=E8=87=AA=E8=BA=AB + =E6=9F=A5=E8=AF=A2=EF=BC=9A=E6=9F=A5=E8=AF=A2=E6=9F=90=E4=B8=AA=E5=85=83= =E7=B4=A0=E5=B1=9E=E4=BA=8E=E5=93=AA=E4=B8=AA=E9=9B=86=E5=90=88=EF=BC=8C=E9= =80=9A=E5=B8=B8=E6=98=AF=E8=BF=94=E5=9B=9E=E9=9B=86=E5=90=88=E4=B8=AD=E7=9A= =84=E4=B8=80=E4=B8=AA=E2=80=9C=E4=BB=A3=E8=A1=A8=E5=85=83=E7=B4=A0=E2=80=9D= =E3=80=82=E8=BF=99=E4=B8=AA=E6=93=8D=E4=BD=9C=E6=98=AF=E4=B8=BA + =E4=BA=86=E5=88=A4=E6=96=AD=E4=B8=A4=E4=B8=AA=E5=85=83=E7=B4=A0=E6=98=AF= =E5=90=A6=E5=9C=A8=E5=90=8C=E4=B8=80=E4=B8=AA=E9=9B=86=E5=90=88=E4=B9=8B=E4= =B8=AD=E3=80=82 + =E5=90=88=E5=B9=B6=EF=BC=9A=E5=B0=86=E4=B8=A4=E4=B8=AA=E9=9B=86=E5=90=88= =E5=90=88=E5=B9=B6=E4=B8=BA=E4=B8=80=E4=B8=AA=E3=80=82 + +=E5=B9=B6=E6=9F=A5=E9=9B=86=E4=BD=9C=E4=B8=BA=E4=B8=80=E7=A7=8D=E7=94=A8= =E4=BA=8E=E7=BB=B4=E6=8A=A4=E9=9B=86=E5=90=88=EF=BC=88=E7=BB=84=EF=BC=89=E7= =9A=84=E6=95=B0=E6=8D=AE=E7=BB=93=E6=9E=84=EF=BC=8C=E5=AE=83=E9=80=9A=E5=B8= =B8=E7=94=A8=E4=BA=8E=E8=A7=A3=E5=86=B3=E4=B8=80=E4=BA=9B=E7=A6=BB=E7=BA=BF= =E6=9F=A5=E8=AF=A2=E3=80=81=E5=8A=A8=E6=80=81=E8=BF=9E=E9=80=9A=E6=80=A7=E5= =92=8C +=E5=9B=BE=E8=AE=BA=E7=AD=89=E7=9B=B8=E5=85=B3=E9=97=AE=E9=A2=98=EF=BC=8C= =E5=90=8C=E6=97=B6=E4=B9=9F=E6=98=AF=E7=94=A8=E4=BA=8E=E8=AE=A1=E7=AE=97=E6= =9C=80=E5=B0=8F=E7=94=9F=E6=88=90=E6=A0=91=E7=9A=84=E5=85=8B=E9=B2=81=E6=96= =AF=E5=85=8B=E5=B0=94=E7=AE=97=E6=B3=95=E4=B8=AD=E7=9A=84=E5=85=B3=E9=94=AE= =EF=BC=8C=E7=94=B1=E4=BA=8E=E6=9C=80=E5=B0=8F=E7=94=9F=E6=88=90=E6=A0=91=E5= =9C=A8 +=E7=BD=91=E7=BB=9C=E8=B7=AF=E7=94=B1=E7=AD=89=E5=9C=BA=E6=99=AF=E4=B8=8B= =E5=8D=81=E5=88=86=E9=87=8D=E8=A6=81=EF=BC=8C=E5=B9=B6=E6=9F=A5=E9=9B=86=E4= =B9=9F=E5=BE=97=E5=88=B0=E4=BA=86=E5=B9=BF=E6=B3=9B=E7=9A=84=E5=BC=95=E7=94= =A8=E3=80=82=E6=AD=A4=E5=A4=96=EF=BC=8C=E5=B9=B6=E6=9F=A5=E9=9B=86=E5=9C=A8= =E7=AC=A6=E5=8F=B7=E8=AE=A1=E7=AE=97=EF=BC=8C=E5=AF=84=E5=AD=98=E5=99=A8=E5= =88=86 +=E9=85=8D=E7=AD=89=E6=96=B9=E9=9D=A2=E4=B9=9F=E6=9C=89=E5=BA=94=E7=94=A8= =E3=80=82 + +=E7=A9=BA=E9=97=B4=E5=A4=8D=E6=9D=82=E5=BA=A6: O(n)=EF=BC=8Cn=E4=B8=BA=E8= =8A=82=E7=82=B9=E6=95=B0=E3=80=82 + +=E6=97=B6=E9=97=B4=E5=A4=8D=E6=9D=82=E5=BA=A6=EF=BC=9A=E4=BD=BF=E7=94=A8= =E8=B7=AF=E5=BE=84=E5=8E=8B=E7=BC=A9=E5=8F=AF=E4=BB=A5=E5=87=8F=E5=B0=91=E6= =9F=A5=E6=89=BE=E6=93=8D=E4=BD=9C=E7=9A=84=E6=97=B6=E9=97=B4=E5=A4=8D=E6=9D= =82=E5=BA=A6=EF=BC=8C=E4=BD=BF=E7=94=A8=E6=8C=89=E7=A7=A9=E5=90=88=E5=B9=B6= =E5=8F=AF=E4=BB=A5=E5=87=8F=E5=B0=91=E5=90=88=E5=B9=B6=E6=93=8D=E4=BD=9C=E7= =9A=84 +=E6=97=B6=E9=97=B4=E5=A4=8D=E6=9D=82=E5=BA=A6=EF=BC=8C=E4=BD=BF=E5=BE=97= =E5=B9=B6=E6=9F=A5=E9=9B=86=E6=AF=8F=E4=B8=AA=E6=9F=A5=E8=AF=A2=E5=92=8C=E5= =90=88=E5=B9=B6=E6=93=8D=E4=BD=9C=E7=9A=84=E5=B9=B3=E5=9D=87=E6=97=B6=E9=97= =B4=E5=A4=8D=E6=9D=82=E5=BA=A6=E4=BB=85=E4=B8=BAO(=CE=B1(n))=EF=BC=8C=E5=85= =B6=E4=B8=AD=CE=B1(n)=E6=98=AF=E5=8F=8D=E9=98=BF +=E5=85=8B=E6=9B=BC=E5=87=BD=E6=95=B0=EF=BC=8C=E5=8F=AF=E4=BB=A5=E7=B2=97= =E7=95=A5=E5=9C=B0=E8=AE=A4=E4=B8=BA=E5=B9=B6=E6=9F=A5=E9=9B=86=E7=9A=84=E6= =93=8D=E4=BD=9C=E6=9C=89=E5=B8=B8=E6=95=B0=E7=9A=84=E6=97=B6=E9=97=B4=E5=A4= =8D=E6=9D=82=E5=BA=A6=E3=80=82 + +=E6=9C=AC=E6=96=87=E6=A1=A3=E6=B6=B5=E7=9B=96=E4=BA=86=E5=AF=B9Linux=E5=B9= =B6=E6=9F=A5=E9=9B=86=E5=AE=9E=E7=8E=B0=E7=9A=84=E4=BD=BF=E7=94=A8=E6=96=B9= =E6=B3=95=E3=80=82=E6=9B=B4=E5=A4=9A=E5=85=B3=E4=BA=8E=E5=B9=B6=E6=9F=A5=E9= =9B=86=E7=9A=84=E6=80=A7=E8=B4=A8=E5=92=8C=E5=AE=9E=E7=8E=B0=E7=9A=84=E4=BF= =A1=E6=81=AF=EF=BC=8C=E5=8F=82=E8=A7=81=EF=BC=9A + + =E7=BB=B4=E5=9F=BA=E7=99=BE=E7=A7=91=E5=B9=B6=E6=9F=A5=E9=9B=86=E8=AF=8D= =E6=9D=A1 + https://en.wikipedia.org/wiki/Disjoint-set_data_structure + +=E5=B9=B6=E6=9F=A5=E9=9B=86=E7=9A=84Linux=E5=AE=9E=E7=8E=B0 +---------------- + +Linux=E7=9A=84=E5=B9=B6=E6=9F=A5=E9=9B=86=E5=AE=9E=E7=8E=B0=E5=9C=A8=E6=96= =87=E4=BB=B6=E2=80=9Clib/union_find.c=E2=80=9D=E4=B8=AD=E3=80=82=E8=A6=81= =E4=BD=BF=E7=94=A8=E5=AE=83=EF=BC=8C=E9=9C=80=E8=A6=81 +=E2=80=9C#include =E2=80=9D=E3=80=82 + +=E5=B9=B6=E6=9F=A5=E9=9B=86=E7=9A=84=E6=95=B0=E6=8D=AE=E7=BB=93=E6=9E=84= =E5=AE=9A=E4=B9=89=E5=A6=82=E4=B8=8B:: + + struct uf_node { + struct uf_node *parent; + unsigned int rank; + }; +=E5=85=B6=E4=B8=ADparent=E4=B8=BA=E5=BD=93=E5=89=8D=E8=8A=82=E7=82=B9=E7= =9A=84=E7=88=B6=E8=8A=82=E7=82=B9=EF=BC=8Crank=E4=B8=BA=E5=BD=93=E5=89=8D= =E6=A0=91=E7=9A=84=E9=AB=98=E5=BA=A6=EF=BC=8C=E5=9C=A8=E5=90=88=E5=B9=B6=E6= =97=B6=E5=B0=86rank=E5=B0=8F=E7=9A=84=E8=8A=82=E7=82=B9=E6=8E=A5=E5=88=B0ra= nk=E5=A4=A7 +=E7=9A=84=E8=8A=82=E7=82=B9=E4=B8=8B=E9=9D=A2=E4=BB=A5=E5=A2=9E=E5=8A=A0= =E5=B9=B3=E8=A1=A1=E6=80=A7=E3=80=82 + +=E5=88=9D=E5=A7=8B=E5=8C=96=E5=B9=B6=E6=9F=A5=E9=9B=86 +--------- + +=E5=88=9D=E5=A7=8B=E5=8C=96=E5=B9=B6=E6=9F=A5=E9=9B=86=E6=97=B6=E9=9C=80= =E8=A6=81=E4=BC=A0=E5=85=A5=E5=B9=B6=E6=9F=A5=E9=9B=86=E5=AE=9E=E4=BE=8B=E7= =9A=84=E4=B8=80=E4=B8=AA=E6=8C=87=E9=92=88=E3=80=82=E5=88=9D=E5=A7=8B=E5=8C= =96=E6=97=B6=EF=BC=8Cparent =E6=8C=87=E9=92=88=E6=8C=87=E5=90=91=E8=87=AA= =E8=BA=AB=EF=BC=8Crank =E8=AE=BE=E7=BD=AE +=E4=B8=BA 0=E3=80=82 +=E7=A4=BA=E4=BE=8B:: + + struct uf_node *my_node =3D vzalloc(sizeof(struct uf_node)); + uf_nodes_init(my_node); + +=E6=9F=A5=E6=89=BE=E5=B9=B6=E6=9F=A5=E9=9B=86=E7=9A=84=E6=A0=B9=E8=8A=82= =E7=82=B9 +---------------- + +=E4=B8=BB=E8=A6=81=E7=94=A8=E4=BA=8E=E5=88=A4=E6=96=AD=E4=B8=A4=E4=B8=AA= =E5=B9=B6=E6=9F=A5=E9=9B=86=E6=98=AF=E5=90=A6=E5=B1=9E=E4=BA=8E=E4=B8=80=E4= =B8=AA=E9=9B=86=E5=90=88=EF=BC=8C=E5=A6=82=E6=9E=9C=E6=A0=B9=E7=9B=B8=E5=90= =8C=EF=BC=8C=E9=82=A3=E4=B9=88=E4=BB=96=E4=BB=AC=E5=B0=B1=E6=98=AF=E4=B8=80= =E4=B8=AA=E9=9B=86=E5=90=88=E3=80=82=E5=9C=A8=E6=9F=A5=E6=89=BE=E8=BF=87=E7= =A8=8B=E4=B8=AD +=E4=BC=9A=E5=AF=B9=E8=B7=AF=E5=BE=84=E8=BF=9B=E8=A1=8C=E5=8E=8B=E7=BC=A9= =EF=BC=8C=E6=8F=90=E9=AB=98=E5=90=8E=E7=BB=AD=E6=9F=A5=E6=89=BE=E6=95=88=E7= =8E=87=E3=80=82 +=E7=A4=BA=E4=BE=8B:: + + int connected; + struct uf_node *root1 =3D uf_find(&my_node[0]); + struct uf_node *root2 =3D uf_find(&my_node[1]); + if (root1 =3D=3D root2) + connected =3D 1; + else + connected =3D 0; + +=E5=90=88=E5=B9=B6=E4=B8=A4=E4=B8=AA=E5=B9=B6=E6=9F=A5=E9=9B=86 +------------- + +=E5=AF=B9=E4=BA=8E=E4=B8=A4=E4=B8=AA=E7=9B=B8=E4=BA=A4=E7=9A=84=E5=B9=B6= =E6=9F=A5=E9=9B=86=E8=BF=9B=E8=A1=8C=E5=90=88=E5=B9=B6=EF=BC=8C=E4=BC=9A=E9= =A6=96=E5=85=88=E6=9F=A5=E6=89=BE=E5=AE=83=E4=BB=AC=E5=90=84=E8=87=AA=E7=9A= =84=E6=A0=B9=E8=8A=82=E7=82=B9=EF=BC=8C=E7=84=B6=E5=90=8E=E6=A0=B9=E6=8D=AE= =E6=A0=B9=E8=8A=82=E7=82=B9=E7=A7=A9=E5=A4=A7=E5=B0=8F=EF=BC=8C=E5=B0=86=E5= =B0=8F=E7=9A=84 +=E8=8A=82=E7=82=B9=E8=BF=9E=E6=8E=A5=E5=88=B0=E5=A4=A7=E7=9A=84=E8=8A=82= =E7=82=B9=E4=B8=8B=E9=9D=A2=E3=80=82 +=E7=A4=BA=E4=BE=8B:: + + uf_union(&my_node[0], &my_node[1]); diff --git a/MAINTAINERS b/MAINTAINERS index 2ca8f35dfe..16171dbca3 100644 --- a/MAINTAINERS +++ b/MAINTAINERS @@ -23051,6 +23051,15 @@ F: drivers/cdrom/cdrom.c F: include/linux/cdrom.h F: include/uapi/linux/cdrom.h =20 +UNION-FIND +M: Xavier +L: linux-kernel@vger.kernel.org +S: Maintained +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 + UNIVERSAL FLASH STORAGE HOST CONTROLLER DRIVER R: Alim Akhtar R: Avri Altman diff --git a/include/linux/union_find.h b/include/linux/union_find.h new file mode 100644 index 0000000000..56571c93a5 --- /dev/null +++ b/include/linux/union_find.h @@ -0,0 +1,24 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +#ifndef __LINUX_UNION_FIND_H +#define __LINUX_UNION_FIND_H + +/* Define a union-find node struct */ +struct uf_node { + struct uf_node *parent; + unsigned int rank; +}; + +/* Allocate nodes and initialize to 0 */ +static inline void uf_nodes_init(struct uf_node *node) +{ + node->parent =3D node; + node->rank =3D 0; +} + +/* find the root of a node*/ +struct uf_node *uf_find(struct uf_node *node); + +/* Merge two intersecting nodes */ +void uf_union(struct uf_node *node1, struct uf_node *node2); + +#endif /*__LINUX_UNION_FIND_H*/ diff --git a/lib/Makefile b/lib/Makefile index 3b17690456..e1769e6f03 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -34,7 +34,7 @@ lib-y :=3D ctype.o string.o vsprintf.o cmdline.o \ is_single_threaded.o plist.o decompress.o kobject_uevent.o \ earlycpio.o seq_buf.o siphash.o dec_and_lock.o \ nmi_backtrace.o win_minmax.o memcat_p.o \ - buildid.o objpool.o + buildid.o objpool.o union_find.o =20 lib-$(CONFIG_PRINTK) +=3D dump_stack.o lib-$(CONFIG_SMP) +=3D cpumask.o diff --git a/lib/union_find.c b/lib/union_find.c new file mode 100644 index 0000000000..bb48b4b129 --- /dev/null +++ b/lib/union_find.c @@ -0,0 +1,33 @@ +// SPDX-License-Identifier: GPL-2.0 +#include + +struct uf_node *uf_find(struct uf_node *node) +{ + struct uf_node *parent; + + /*Find the root node and perform path compression at the same time*/ + while (node->parent !=3D node) { + parent =3D node->parent; + node->parent =3D parent->parent; + node =3D parent; + } + return node; +} + +/*Function to merge two sets, using union by rank*/ +void 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); + + if (root1 !=3D root2) { + if (root1->rank < root2->rank) { + root1->parent =3D root2; + } else if (root1->rank > root2->rank) { + root2->parent =3D root1; + } else { + root2->parent =3D root1; + root1->rank++; + } + } +} --=20 2.45.2 From nobody Mon Feb 9 05:43:05 2026 Received: from m16.mail.163.com (m16.mail.163.com [220.197.31.5]) by smtp.subspace.kernel.org (Postfix) with ESMTP id 1AD42158DDC; Fri, 28 Jun 2024 16:14:08 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=220.197.31.5 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1719591251; cv=none; b=bYOfqV8GFJc/WuoTqd1FcO/IZ6XR6vXG4xi2hWpE/7NjGye5Tl7+uPS1Lqt2OnMqnJ2Uojvf3F7MPwHt+sKVFkZHewh1gG/pbQg474nJH/oGBhH4D5Y8FHdCdJSedq7nmmQZLAQB8O+XS5jyhWLh9BR91X6v/ozTnckMKvjvUi4= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1719591251; c=relaxed/simple; bh=/ZLjV4AtG6PE9RE64qHOYEVdhdNaKhQgUm25uI4izAI=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=q4snwVZLlMRNwz4vPt0Jy5hlYOu6vm4sjZ1UVXGZYQZr1SxjW/jOgvNCNUqXeajAG+WF52Bbvi3dqb5Pwvrwmo96VwdC47igZs3tV9zlp1q4f3PDZBltnA2+kOX3DwRZT79tknx1Yn9HlcjLchwLfaAMMfFYrY242dNJ0odHuG4= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=163.com; spf=pass smtp.mailfrom=163.com; dkim=pass (1024-bit key) header.d=163.com header.i=@163.com header.b=pSQNcblq; arc=none smtp.client-ip=220.197.31.5 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=163.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=163.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (1024-bit key) header.d=163.com header.i=@163.com header.b="pSQNcblq" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=163.com; s=s110527; h=From:Subject:Date:Message-Id:MIME-Version; bh=e26+2 q+3hBU2DBzF5851MuqgEXt4Q/cdEKTEV/s7sag=; b=pSQNcblqjulPYUuVA1ewP bWx080z7JFM3P2O9bxeinUlDmYzbrJrm5dLbggXVXuQeQ1wDWcw9ycoWKjAg1S/h ChMqJ2UsMDooZJce0bHBm8jKxN9oFrlmXbOnsEoYelo5eVrJQgbaxHJcHdBKREbj 0J42/kHedGtk1ZAFIlCfR8= Received: from localhost (unknown [101.132.132.191]) by gzga-smtp-mta-g3-5 (Coremail) with SMTP id _____wDX_yoR4X5m0+qRAw--.37690S2; Sat, 29 Jun 2024 00:13:05 +0800 (CST) From: Xavier To: tj@kernel.org Cc: longman@redhat.com, mkoutny@suse.com, lizefan.x@bytedance.com, hannes@cmpxchg.org, cgroups@vger.kernel.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org, akpm@linux-foundation.org, Xavier Subject: [PATCH-cpuset v8 2/2] cpuset: use Union-Find to optimize the merging of cpumasks Date: Sat, 29 Jun 2024 00:13:02 +0800 Message-Id: <20240628161302.240043-3-xavier_qy@163.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240628161302.240043-1-xavier_qy@163.com> References: <20240628161302.240043-1-xavier_qy@163.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 X-CM-TRANSID: _____wDX_yoR4X5m0+qRAw--.37690S2 X-Coremail-Antispam: 1Uf129KBjvJXoWxAFWfur4kKFyUZFWUJrW3Awb_yoWruF1fpF sakay2qrWrJryUGwsakay8Zw1ak3ykJayUtwnxGw1rtr17A3Z29a40qFs3KFWUZrWq9F1U uF9Igr47Wr18KFJanT9S1TB71UUUUU7qnTZGkaVYY2UrUUUUjbIjqfuFe4nvWSU5nxnvy2 9KBjDUYxBIdaVFxhVjvjDU0xZFpf9x07Ubo7tUUUUU= X-CM-SenderInfo: 50dyxvpubt5qqrwthudrp/xtbBchAMEGWXv5R4dgABso Content-Type: text/plain; charset="utf-8" The process of constructing scheduling domains involves multiple loops and repeated evaluations, leading to numerous redundant and ineffective assessments that impact code efficiency. Here, we use Union-Find to optimize the merging of cpumasks. By employing path compression and union by rank, we effectively reduce the number of lookups and merge comparisons. Signed-off-by: Xavier --- kernel/cgroup/cpuset.c | 96 ++++++++++++++++-------------------------- 1 file changed, 37 insertions(+), 59 deletions(-) diff --git a/kernel/cgroup/cpuset.c b/kernel/cgroup/cpuset.c index fe76045aa5..c435814ba8 100644 --- a/kernel/cgroup/cpuset.c +++ b/kernel/cgroup/cpuset.c @@ -45,6 +45,8 @@ #include #include #include +#include +#include =20 DEFINE_STATIC_KEY_FALSE(cpusets_pre_enable_key); DEFINE_STATIC_KEY_FALSE(cpusets_enabled_key); @@ -172,9 +174,6 @@ struct cpuset { */ int attach_in_progress; =20 - /* partition number for rebuild_sched_domains() */ - int pn; - /* for custom sched domain */ int relax_domain_level; =20 @@ -208,6 +207,9 @@ struct cpuset { =20 /* Remote partition silbling list anchored at remote_children */ struct list_head remote_sibling; + + /* Used to merge intersecting subsets for generate_sched_domains*/ + struct uf_node node; }; =20 /* @@ -1007,7 +1009,7 @@ static int generate_sched_domains(cpumask_var_t **dom= ains, struct cpuset *cp; /* top-down scan of cpusets */ struct cpuset **csa; /* array of all cpuset ptrs */ int csn; /* how many cpuset ptrs in csa so far */ - int i, j, k; /* indices for partition finding loops */ + int i, j; /* indices for partition finding loops */ cpumask_var_t *doms; /* resulting partition; i.e. sched domains */ struct sched_domain_attr *dattr; /* attributes for custom domains */ int ndoms =3D 0; /* number of sched domains in result */ @@ -1015,6 +1017,7 @@ static int generate_sched_domains(cpumask_var_t **dom= ains, struct cgroup_subsys_state *pos_css; bool root_load_balance =3D is_sched_load_balance(&top_cpuset); bool cgrpv2 =3D cgroup_subsys_on_dfl(cpuset_cgrp_subsys); + int nslot_update; =20 doms =3D NULL; dattr =3D NULL; @@ -1102,31 +1105,25 @@ static int generate_sched_domains(cpumask_var_t **d= omains, if (root_load_balance && (csn =3D=3D 1)) goto single_root_domain; =20 - for (i =3D 0; i < csn; i++) - csa[i]->pn =3D i; - ndoms =3D csn; - -restart: - /* Find the best partition (set of sched domains) */ - for (i =3D 0; i < csn; i++) { - struct cpuset *a =3D csa[i]; - int apn =3D a->pn; + if (!cgrpv2) { + for (i =3D 0; i < csn; i++) + uf_nodes_init(&csa[i]->node); =20 - for (j =3D 0; j < csn; j++) { - struct cpuset *b =3D csa[j]; - int bpn =3D b->pn; - - if (apn !=3D bpn && cpusets_overlap(a, b)) { - for (k =3D 0; k < csn; k++) { - struct cpuset *c =3D csa[k]; - - if (c->pn =3D=3D bpn) - c->pn =3D apn; - } - ndoms--; /* one less element */ - goto restart; + /* Merge overlapping cpusets */ + for (i =3D 0; i < csn; i++) { + for (j =3D i + 1; j < csn; j++) { + if (cpusets_overlap(csa[i], csa[j])) + uf_union(&csa[i]->node, &csa[j]->node); } } + + /* Count the total number of domains */ + for (i =3D 0; i < csn; i++) { + if (csa[i]->node.parent =3D=3D &csa[i]->node) + ndoms++; + } + } else { + ndoms =3D csn; } =20 /* @@ -1159,44 +1156,25 @@ static int generate_sched_domains(cpumask_var_t **d= omains, } =20 for (nslot =3D 0, i =3D 0; i < csn; i++) { - struct cpuset *a =3D csa[i]; - struct cpumask *dp; - int apn =3D a->pn; - - if (apn < 0) { - /* Skip completed partitions */ - continue; - } - - dp =3D doms[nslot]; - - if (nslot =3D=3D ndoms) { - static int warnings =3D 10; - if (warnings) { - pr_warn("rebuild_sched_domains confused: nslot %d, ndoms %d, csn %d, i= %d, apn %d\n", - nslot, ndoms, csn, i, apn); - warnings--; - } - continue; - } - - cpumask_clear(dp); - if (dattr) - *(dattr + nslot) =3D SD_ATTR_INIT; + nslot_update =3D 0; for (j =3D i; j < csn; j++) { - struct cpuset *b =3D csa[j]; - - if (apn =3D=3D b->pn) { - cpumask_or(dp, dp, b->effective_cpus); + if (uf_find(&csa[j]->node) =3D=3D &csa[i]->node) { + struct cpumask *dp =3D doms[nslot]; + + if (i =3D=3D j) { + nslot_update =3D 1; + cpumask_clear(dp); + if (dattr) + *(dattr + nslot) =3D SD_ATTR_INIT; + } + cpumask_or(dp, dp, csa[j]->effective_cpus); cpumask_and(dp, dp, housekeeping_cpumask(HK_TYPE_DOMAIN)); if (dattr) - update_domain_attr_tree(dattr + nslot, b); - - /* Done with this partition */ - b->pn =3D -1; + update_domain_attr_tree(dattr + nslot, csa[j]); } } - nslot++; + if (nslot_update) + nslot++; } BUG_ON(nslot !=3D ndoms); =20 --=20 2.45.2