From nobody Wed Dec 17 12:19:12 2025 Received: from m16.mail.163.com (m16.mail.163.com [220.197.31.5]) by smtp.subspace.kernel.org (Postfix) with ESMTP id 056334C6B; Sat, 22 Jun 2024 07:18:03 +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=1719040688; cv=none; b=rirn8/ENZmLwv7Qu1ANSwh41swoD8hkxqTeGZVIpslOtEQDj5MZcoVAnYEa1HisdoIuz3lRWv/j7kpPZZw5BemjBOfkP9gFGn0uarLYgfyoS3icedGCpRH8jJlRY4aie+j+5wWKFfSPXj//+w3aUfFqt/wZsM7YRNXrcVRCLF30= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1719040688; c=relaxed/simple; bh=spvWJbedj093uLTNzrJN9s9a/T84DD78yey/AIugRPQ=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version:Content-Type; b=qioEFBJZdeg5kSD4JKVZrJLEoVbg81SQMDEtolBQwRzn3canOofy6InRNqNiWNpgmAMRcHBjQsO3kHdlZjxBUZnsKzBzi86IkAHx93PR5/qMvZG2DJOK1PCd4itbFO24Nh23cgrHEyJkYKSCbpeFCdVh5mECkUxKD4UyekzyMKk= 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=J4fsIVaA; 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="J4fsIVaA" 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=MHwCUrqFvaTbLTSbC2zSi9DEqElhDfe0ymagxR80BZs=; b=J4fsIVaAFTshkpjD0TI6Q29CwERfaTgfN8+0OEn2hieLm5ppTTHh4lK7T8NxVc uT0/BxCnMZxbn3hloNRNEe1XQJph/rTtBFIlSV0BVO0JBA2sO79iSF/C0XaRAqTO +Qg0sVaF6/rlKuzp2qPX16NA4+bZHjtLcQLzCGpPxTm34= Received: from localhost (unknown [101.132.132.191]) by gzga-smtp-mta-g2-3 (Coremail) with SMTP id _____wD3_9vSeXZmqbwVAA--.6046S2; Sat, 22 Jun 2024 15:14:26 +0800 (CST) From: Xavier To: tj@kernel.org, longman@redhat.com Cc: 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 v6 1/2] Union-Find: add a new module in kernel library Date: Sat, 22 Jun 2024 15:14:23 +0800 Message-Id: <20240622071424.215778-2-xavier_qy@163.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240622071424.215778-1-xavier_qy@163.com> References: <20240622071424.215778-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: _____wD3_9vSeXZmqbwVAA--.6046S2 X-Coremail-Antispam: 1Uf129KBjvJXoWfJw48ury7Gw1ftw4kuFyxuFg_yoWkAF4kpF sxGryfZa1DJ34Uury0krW5Aw4Sva1rGrWUGa1xG3W0yrnxAr10qF1jy34rtr95Gry2kF18 XF4agr15A3WUJ3DanT9S1TB71UUUUU7qnTZGkaVYY2UrUUUUjbIjqfuFe4nvWSU5nxnvy2 9KBjDUYxBIdaVFxhVjvjDU0xZFpf9x07Uyv35UUUUU= X-CM-SenderInfo: 50dyxvpubt5qqrwthudrp/1tbiYwAGEGV4I4OGogAAss 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 | 110 ++++++++++++++++++ .../zh_CN/core-api/union_find.rst | 87 ++++++++++++++ MAINTAINERS | 9 ++ include/linux/union_find.h | 30 +++++ lib/Makefile | 2 +- lib/union_find.c | 38 ++++++ 6 files changed, 275 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..7109ad608a --- /dev/null +++ b/Documentation/core-api/union_find.rst @@ -0,0 +1,110 @@ +.. 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. +For efficiency, it is initialized to NULL and is assigned to point to itse= lf +during the first find operation. The rank field represents the height of t= he +current tree. During a union operation, the tree with the smaller rank is +attached under the tree with the larger rank to maintain balance. + +Creating Union-Find +-------------------- + +To create a Union-Find structure, you only need to pass the number of node= s in +the Union-Find. No additional initialization is required, and it returns a +pointer to the node array. +Example:: + + struct uf_node *my_node =3D uf_nodes_alloc(num); + +Destroying Union-Find +--------------------- + +To destroy the Union-Find structure, just pass the node pointer that was +returned during creation. +Example:: + + uf_nodes_free(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..071818e7db --- /dev/null +++ b/Documentation/translations/zh_CN/core-api/union_find.rst @@ -0,0 +1,87 @@ +.. 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=8C=E4=B8=BA=E4=BA=86=E6=8F=90=E9=AB= =98=E6=95=88=E7=8E=87=EF=BC=8C=E5=88=9D=E5=A7=8B=E5=8C=96=E6=97=B6=E4=B8=BA= =E7=A9=BA=EF=BC=8C=E5=B9=B6=E5=9C=A8=E7=AC=AC=E4=B8=80=E6=AC=A1=E6=9F=A5=E6= =89=BE=E6=97=B6=E6=8C=87=E5=90=91=E8=87=AA=E8=BA=AB=EF=BC=8C +rank=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=B0rank=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=9B=E5=BB=BA=E5=B9=B6=E6=9F=A5=E9=9B=86 +--------- + +=E5=88=9B=E5=BB=BA=E5=B9=B6=E6=9F=A5=E9=9B=86=E6=97=B6=E5=8F=AA=E9=9C=80= =E8=A6=81=E4=BC=A0=E5=85=A5=E5=B9=B6=E6=9F=A5=E9=9B=86=E7=9A=84=E8=8A=82=E7= =82=B9=E4=B8=AA=E6=95=B0=E5=8D=B3=E5=8F=AF=EF=BC=8C=E6=97=A0=E9=9C=80=E9=A2= =9D=E5=A4=96=E5=88=9D=E5=A7=8B=E5=8C=96=EF=BC=8C=E8=BF=94=E5=9B=9E=E8=8A=82= =E7=82=B9=E6=95=B0=E7=BB=84=E6=8C=87=E9=92=88=E3=80=82 +=E7=A4=BA=E4=BE=8B:: + struct uf_node *my_node =3D uf_nodes_alloc(num); + +=E9=94=80=E6=AF=81=E5=B9=B6=E6=9F=A5=E9=9B=86 +--------- + +=E9=94=80=E6=AF=81=E5=B9=B6=E6=9F=A5=E9=9B=86=E6=97=B6=EF=BC=8C=E5=8F=AA= =E9=9C=80=E4=BC=A0=E5=85=A5=E5=88=9B=E5=BB=BA=E6=97=B6=E8=BF=94=E5=9B=9E=E7= =9A=84=E8=8A=82=E7=82=B9=E6=95=B0=E7=BB=84=E6=8C=87=E9=92=88=E5=8D=B3=E5=8F= =AF=E3=80=82 +=E7=A4=BA=E4=BE=8B:: + uf_nodes_free(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 d6c90161c7..a1a467c591 100644 --- a/MAINTAINERS +++ b/MAINTAINERS @@ -23054,6 +23054,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..ca806f1531 --- /dev/null +++ b/include/linux/union_find.h @@ -0,0 +1,30 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +#ifndef __LINUX_UNION_FIND_H +#define __LINUX_UNION_FIND_H +#include + +/* Define a union-find node struct */ +struct uf_node { + struct uf_node *parent; + unsigned int rank; +}; + +/* Allocate nodes and initialize to 0 */ +static inline struct uf_node *uf_nodes_alloc(unsigned int node_num) +{ + return vzalloc(sizeof(struct uf_node) * node_num); +} + +/* Free nodes*/ +static inline void uf_nodes_free(struct uf_node *nodes) +{ + vfree(nodes); +} + +/* 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..2f77bae1ca --- /dev/null +++ b/lib/union_find.c @@ -0,0 +1,38 @@ +// SPDX-License-Identifier: GPL-2.0 +#include + +struct uf_node *uf_find(struct uf_node *node) +{ + struct uf_node *parent; + + if (!node->parent) { + node->parent =3D node; + return node; + } + + /*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 Wed Dec 17 12:19:12 2025 Received: from m16.mail.163.com (m16.mail.163.com [117.135.210.4]) by smtp.subspace.kernel.org (Postfix) with ESMTP id 2947F4C6B; Sat, 22 Jun 2024 07:17:51 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=117.135.210.4 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1719040676; cv=none; b=JT/oEJu1jFC+690dj8Ea6MxWe7Gorfx1D9NZNu/AlVXr+HnLj90qamtV/fJ3TFTCNDI6dOgwQ3Jn73QsQODBjG2qcgE/D/i80qpGgoNERrNU8foju9zwK2/8SjlMUb6Mcl2kiW3WJQAlL+IGfQ/4s4YjK7zR6xdehaGakD1wrnU= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1719040676; c=relaxed/simple; bh=T9O4nMfNL264snMcAy6vophUdVlTs3RvdJVMqt8zS+w=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=mV6G9zBS2L+nTOdBqghGZyMQeeT7LrxBJaiAJm5XAcpZczAUWof4tF8ULuqR2EE89yECTZmc3l1P17zWX/dyxUHABN5/Ack8wRbBiwEMVS8CSVcgCrhYueFHefdGJWVXLdtVirixOpluUw+oW5Oz9FQ9oKm2wQde4FyeNUr7QNc= 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=lGeJCGuR; arc=none smtp.client-ip=117.135.210.4 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="lGeJCGuR" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=163.com; s=s110527; h=From:Subject:Date:Message-Id:MIME-Version; bh=2bzIC 7usDj/I+d/64DMmEa2VWZHcXlRlo9WqOfdcwd4=; b=lGeJCGuRyzummNUru9dOS GQc0Ao2aVBmxDe1dickbop4B32JMPDakCovfpFThG6DVR9MLzlr8QVAVKpnihaa1 4vW0Wv23qP+Lg/lCJcTrMmHmUp17I3zYCp1RKNKEx9hsYwwmd5CXZMTzwfjfGFgR bVOyqgwy/HExb/lyetyseY= Received: from localhost (unknown [101.132.132.191]) by gzga-smtp-mta-g2-2 (Coremail) with SMTP id _____wD3HybTeXZmUqwUAA--.6297S2; Sat, 22 Jun 2024 15:14:28 +0800 (CST) From: Xavier To: tj@kernel.org, longman@redhat.com Cc: 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 v6 2/2] cpuset: use Union-Find to optimize the merging of cpumasks Date: Sat, 22 Jun 2024 15:14:24 +0800 Message-Id: <20240622071424.215778-3-xavier_qy@163.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240622071424.215778-1-xavier_qy@163.com> References: <20240622071424.215778-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: _____wD3HybTeXZmUqwUAA--.6297S2 X-Coremail-Antispam: 1Uf129KBjvJXoWxAFWfur4kKFyUZFWUJrW3Awb_yoWrCw47pF s3Gay29rWrJryUGwsYkay8Z34SkaykJa1Utw13Gw1rArnrA3Z2va40qFs5KFWUuryDCF1U uFnxKr47WryUKFDanT9S1TB71UUUUU7qnTZGkaVYY2UrUUUUjbIjqfuFe4nvWSU5nxnvy2 9KBjDUYxBIdaVFxhVjvjDU0xZFpf9x07U-J5wUUUUU= X-CM-SenderInfo: 50dyxvpubt5qqrwthudrp/1tbiYx0FEGV4I3AumQAFsX 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 | 97 +++++++++++++++++------------------------- 1 file changed, 38 insertions(+), 59 deletions(-) diff --git a/kernel/cgroup/cpuset.c b/kernel/cgroup/cpuset.c index fe76045aa5..98e9df57c4 100644 --- a/kernel/cgroup/cpuset.c +++ b/kernel/cgroup/cpuset.c @@ -45,6 +45,7 @@ #include #include #include +#include =20 DEFINE_STATIC_KEY_FALSE(cpusets_pre_enable_key); DEFINE_STATIC_KEY_FALSE(cpusets_enabled_key); @@ -172,9 +173,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 @@ -1007,7 +1005,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 +1013,8 @@ 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); + struct uf_node *nodes =3D NULL; + int nslot_update; =20 doms =3D NULL; dattr =3D NULL; @@ -1102,31 +1102,26 @@ 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; - - 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 (!cgrpv2) { + nodes =3D uf_nodes_alloc(csn); + if (!nodes) + goto done; =20 - 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(&nodes[i], &nodes[j]); } } + + /* Count the total number of domains */ + for (i =3D 0; i < csn; i++) { + if ((nodes[i].parent =3D=3D &nodes[i]) || !nodes[i].parent) + ndoms++; + } + } else { + ndoms =3D csn; } =20 /* @@ -1159,48 +1154,32 @@ 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(&nodes[j]) =3D=3D &nodes[i]) { + 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 done: + if (nodes) + uf_nodes_free(nodes); + kfree(csa); =20 /* --=20 2.45.2