From nobody Wed Dec 17 12:19:41 2025 Received: from m16.mail.163.com (m16.mail.163.com [117.135.210.2]) by smtp.subspace.kernel.org (Postfix) with ESMTP id 81DEC1A01D4; Thu, 4 Jul 2024 06:28:13 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=117.135.210.2 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1720074497; cv=none; b=NFKdFZAP+PjWGKQg4QhDk9tT+Vj6YjMV+V3PBDW6zkuvNfJZdPSVEA2ldD7R3lrYfldj4mzrvH5ih21hpPduh+X0ZEmFhKYsQEyeltIkXx2aVEpqS4VPRyWqMzT1KiVE4fcCDrnDL0El+ZgUq4pB7447qAiBymZsVBzkKLERjG8= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1720074497; c=relaxed/simple; bh=kplW0kimTIit4XDwDpITKPd1EYrOar/Bpo6fErrWpKU=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version:Content-Type; b=rGlshb3cNdH5EiC5xe+EAt/XDriGAhciXnOZIOjWqXbYLRyuJlhIpBO9ZTQLhe69lW53HfHr0djS8azOpifH8nWWNtmu3BwdtLNOIWnoYN8u7+GJB3z+Hz8jG2SqkX2Sk25TcIhM/ru40ijUg/o/gF0PmeTNfjjHD+Ha1a69Qcs= 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=TvHWcV/I; arc=none smtp.client-ip=117.135.210.2 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="TvHWcV/I" 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=xgOy7J8lGlrACKI0I+9kb/kJr8SxxiYg7g94kmyQ0wI=; b=TvHWcV/IgpgQJA6KiS0QMaO2pVPoj2Sa/NehMVFR4IbJVxJHF3Fbk5MdIGKVxS wsBXv8Cq5v+pfdSxJrBlNM26H9tFJlwz92hXRN3mxZQE5K2igKdEydKW5PG0y3z2 n315dojR/2FtjOi2LC/Ej8vnGpUo0hf3ybdStjmDS3fqs= Received: from localhost (unknown [101.132.132.191]) by gzga-smtp-mta-g2-3 (Coremail) with SMTP id _____wD334IvQIZmF8xjBQ--.53023S2; Thu, 04 Jul 2024 14:24:47 +0800 (CST) From: Xavier To: tj@kernel.org, longman@redhat.com, mkoutny@suse.com Cc: akpm@linux-foundation.org, lizefan.x@bytedance.com, hannes@cmpxchg.org, cgroups@vger.kernel.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org, Xavier Subject: [PATCH-cpuset v11 1/2] Union-Find: add a new module in kernel library Date: Thu, 4 Jul 2024 14:24:43 +0800 Message-Id: <20240704062444.262211-2-xavier_qy@163.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240704062444.262211-1-xavier_qy@163.com> References: <20240704062444.262211-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: _____wD334IvQIZmF8xjBQ--.53023S2 X-Coremail-Antispam: 1Uf129KBjvJXoWfJw48ur4DKr1xJw1kKw48Zwb_yoWkuF48pF sxG34fZw4DJryUC340krW5Zw4SvayrGrWUGa1xJa10yrsayr10qF4jyw1rtr95GryIkFy8 XF4aqw1rZw1jy3DanT9S1TB71UUUUU7qnTZGkaVYY2UrUUUUjbIjqfuFe4nvWSU5nxnvy2 9KBjDUYxBIdaVFxhVjvjDU0xZFpf9x07Ur5rsUUUUU= X-CM-SenderInfo: 50dyxvpubt5qqrwthudrp/xtbBchMSEGWXwA24JwAAsD 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 Acked-by: Waiman Long --- Documentation/core-api/union_find.rst | 102 ++++++++++++++++++ .../zh_CN/core-api/union_find.rst | 87 +++++++++++++++ MAINTAINERS | 9 ++ include/linux/union_find.h | 41 +++++++ lib/Makefile | 2 +- lib/union_find.c | 49 +++++++++ 6 files changed, 289 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..2bf0290c91 --- /dev/null +++ b/Documentation/core-api/union_find.rst @@ -0,0 +1,102 @@ +.. 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 +-------------------- + +You can complete the initialization using either static or initialization +interface. Initialize the parent pointer to point to itself and set the ra= nk +to 0. +Example:: + + struct uf_node my_node =3D UF_INIT_NODE(my_node); +or + uf_node_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(&node_1); + struct uf_node *root2 =3D uf_find(&node_2); + 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(&node_1, &node_2); 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..a56de57147 --- /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=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=8F=AF=E4=BB=A5=E9=87=87=E7=94=A8=E9=9D=99=E6=80=81=E6=88=96=E5=88=9D= =E5=A7=8B=E5=8C=96=E6=8E=A5=E5=8F=A3=E5=AE=8C=E6=88=90=E5=88=9D=E5=A7=8B=E5= =8C=96=E6=93=8D=E4=BD=9C=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=8Cra= nk =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 UF_INIT_NODE(my_node); +=E6=88=96 + uf_node_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(&node_1); + struct uf_node *root2 =3D uf_find(&node_2); + 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(&node_1, &node_2); 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..cfd49263c1 --- /dev/null +++ b/include/linux/union_find.h @@ -0,0 +1,41 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +#ifndef __LINUX_UNION_FIND_H +#define __LINUX_UNION_FIND_H +/** + * union_find.h - union-find data structure implementation + * + * This header provides functions and structures to implement the union-fi= nd + * data structure. The union-find data structure is used to manage disjoint + * sets and supports efficient union and find operations. + * + * See Documentation/core-api/union_find.rst for documentation and samples. + */ + +struct uf_node { + struct uf_node *parent; + unsigned int rank; +}; + +/* This macro is used for static initialization of a union-find node. */ +#define UF_INIT_NODE(node) {.parent =3D &node, .rank =3D 0} + +/** + * uf_node_init - Initialize a union-find node + * @node: pointer to the union-find node to be initialized + * + * This function sets the parent of the node to itself and + * initializes its rank to 0. + */ +static inline void uf_node_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..413b0f8adf --- /dev/null +++ b/lib/union_find.c @@ -0,0 +1,49 @@ +// SPDX-License-Identifier: GPL-2.0 +#include + +/** + * uf_find - Find the root of a node and perform path compression + * @node: the node to find the root of + * + * This function returns the root of the node by following the parent + * pointers. It also performs path compression, making the tree shallower. + * + * Returns the root node of the set containing node. + */ +struct uf_node *uf_find(struct uf_node *node) +{ + struct uf_node *parent; + + while (node->parent !=3D node) { + parent =3D node->parent; + node->parent =3D parent->parent; + node =3D parent; + } + return node; +} + +/** + * uf_union - Merge two sets, using union by rank + * @node1: the first node + * @node2: the second node + * + * This function merges the sets containing node1 and node2, by comparing + * the ranks to keep the tree balanced. + */ +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=3D root2) + return; + + 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.0 From nobody Wed Dec 17 12:19:41 2025 Received: from m16.mail.163.com (m16.mail.163.com [220.197.31.4]) by smtp.subspace.kernel.org (Postfix) with ESMTP id 01A291A01B9; Thu, 4 Jul 2024 06:28:03 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=220.197.31.4 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1720074487; cv=none; b=MGVp4BPXAtUhPZxtwxZhcuBMxQey2avt9pWLvM0+nYHTh02enWxTKE1CRxb6YM5GJMNCBfwn27ZaPPMyAAaMduBBXJhr7begYNrX/6k7dwm9acNA0ftzTaBYUAfU3jeAD+VA0Gu+GYlpRkBIJZJBr+pomSnEIFAsV6IR78+3/J4= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1720074487; c=relaxed/simple; bh=j8f4F6U7OmgvmUX8RWRePj3hrnRbcNZyfud6G/4CkHA=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=BjCLp2uV6ziksVbRLd9q42AZQJRh1zBQS8hnUIcY0QogSdlYcMIzibnx7i11b2fH+gh2TFVuHqlk3mv3CkFm2Wu2q/y2w92YxKFIxUfDThbp994Hc9SeV7TTdI3aQS2lMcSl4aWZ/2GHT7QxSqjSlYNyIobk0yqFgtRIrCppIL8= 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=j871npQo; arc=none smtp.client-ip=220.197.31.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="j871npQo" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=163.com; s=s110527; h=From:Subject:Date:Message-Id:MIME-Version; bh=SYdzR PxUxpKzIGV/bEvZ/ka95x8s627MSi9kzBpkydI=; b=j871npQozJoJEaL1BbFPK pI7sUK47WT6PL+I4Uu5L8oh9YsC/OYZfZUE2i5lCJ5L5rvbTpmFIKiwz5VIwfVUE Whby09RSjSR8HkjxUyWuCe4jmGkf2V6OlWQm6vsfU3IwIwlFfEGBfXsYizcZf8el U8q2Lo2e8n7xUMP8y3/sQ4= Received: from localhost (unknown [101.132.132.191]) by gzga-smtp-mta-g1-3 (Coremail) with SMTP id _____wDnL50wQIZmp5AdBg--.65239S2; Thu, 04 Jul 2024 14:24:49 +0800 (CST) From: Xavier To: tj@kernel.org, longman@redhat.com, mkoutny@suse.com Cc: akpm@linux-foundation.org, lizefan.x@bytedance.com, hannes@cmpxchg.org, cgroups@vger.kernel.org, linux-kernel@vger.kernel.org, torvalds@linux-foundation.org, Xavier Subject: [PATCH-cpuset v11 2/2] cpuset: use Union-Find to optimize the merging of cpumasks Date: Thu, 4 Jul 2024 14:24:44 +0800 Message-Id: <20240704062444.262211-3-xavier_qy@163.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240704062444.262211-1-xavier_qy@163.com> References: <20240704062444.262211-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: _____wDnL50wQIZmp5AdBg--.65239S2 X-Coremail-Antispam: 1Uf129KBjvJXoWxKw15WFy3Zr1UXr17Xr1UKFg_yoW7uw4xpF 4fK3y2vrWrtry7Gws2kayxZw1ak397JayUtw13Gw1FyrnrA3Z29Fy0gFsIkFWUZrWDCF1U uF9Igr47WF1qkrJanT9S1TB71UUUUU7qnTZGkaVYY2UrUUUUjbIjqfuFe4nvWSU5nxnvy2 9KBjDUYxBIdaVFxhVjvjDU0xZFpf9x07UbBMNUUUUU= X-CM-SenderInfo: 50dyxvpubt5qqrwthudrp/xtbBchESEGWXwA24BgAAsg 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 Acked-by: Waiman Long --- kernel/cgroup/cpuset.c | 114 ++++++++++++++++------------------------- 1 file changed, 44 insertions(+), 70 deletions(-) diff --git a/kernel/cgroup/cpuset.c b/kernel/cgroup/cpuset.c index fe76045aa5..0037371986 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 @@ -208,6 +206,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 /* @@ -988,18 +989,15 @@ static inline int nr_cpusets(void) * were changed (added or removed.) * * Finding the best partition (set of domains): - * The triple nested loops below over i, j, k scan over the - * load balanced cpusets (using the array of cpuset pointers in - * csa[]) looking for pairs of cpusets that have overlapping - * cpus_allowed, but which don't have the same 'pn' partition - * number and gives them in the same partition number. It keeps - * looping on the 'restart' label until it can no longer find - * any such pairs. + * The double nested loops below over i, j scan over the load + * balanced cpusets (using the array of cpuset pointers in csa[]) + * looking for pairs of cpusets that have overlapping cpus_allowed + * and merging them using a union-find algorithm. + * + * The union of the cpus_allowed masks from the set of all cpusets + * having the same root then form the one element of the partition + * (one sched domain) to be passed to partition_sched_domains(). * - * The union of the cpus_allowed masks from the set of - * all cpusets having the same 'pn' value then form the one - * element of the partition (one sched domain) to be passed to - * partition_sched_domains(). */ static int generate_sched_domains(cpumask_var_t **domains, struct sched_domain_attr **attributes) @@ -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,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 +1101,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; - - 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) { + for (i =3D 0; i < csn; i++) + uf_node_init(&csa[i]->node); =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(&csa[i]->node, &csa[j]->node); } } + + /* 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++; + } + } else { + ndoms =3D csn; } =20 /* @@ -1159,44 +1152,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.0