linux-kernel - Re: Re: [PATCH v3] cpuset: use Union-Find to optimize the merging of cpumasks

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [day] [month] [year] [list]

Message-ID: <666bb346733087.27442573.c05259ad@m1.mail.sina.com.cn>
Date: Fri, 14 Jun 2024 11:04:38 +0800
From: "Xavier" <ghostxavier@...a.com>
To: "Michal Koutný" <mkoutny@...e.com>
Cc: "Waiman Long" <longman@...hat.com>, "lizefan.x" <lizefan.x@...edance.com>,
 "tj" <tj@...nel.org>, "hannes" <hannes@...xchg.org>,
 "cgroups" <cgroups@...r.kernel.org>,
 "linux-kernel" <linux-kernel@...r.kernel.org>
Subject: Re: Re: [PATCH v3] cpuset: use Union-Find to optimize the merging
 of cpumasks

Hi Michal Koutný,

Thank you for your feedback. I think your idea is good, and I will resubmit it after Longman's new patch of cpuset is merged.

Best regards,
Xavier

>
>----- Original Message -----
>From: Michal Koutný <mkoutny@...e.com>
>To: Xavier <ghostxavier@...a.com>
>Cc: longman@...hat.com, lizefan.x@...edance.com, tj@...nel.org,  hannes@...xchg.org, cgroups@...r.kernel.org, linux-kernel@...r.kernel.org
>Subject: Re: [PATCH v3] cpuset: use Union-Find to optimize the merging of cpumasks
>Date: 2024-06-11 01:19
>
>Hello.
>On Mon, Jun 03, 2024 at 08:31:01PM GMT, Xavier <ghostxavier@...a.com> wrote:
>> 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.
>Nice that you found such an application. (As Waiman wrote, the
>efficiency is not so important here and it may not be dencreased but I
>still think it makes the code more understandable by using standard data
>structures.)
>Have you looked whether there are other instances of U-F in the kernel?
>(My quick search didn't show any.) Still, I think it'd be a good idea to
>decouple this into two commits -- 1) implementation of the new U-F (into
>lib/), 2) application within cpuset.
>> +/*define a union find node struct*/
>> +struct uf_node {
>> +	int parent;
>I think this would be better as `struct uf_node *`.
>> +	int rank;
>> +};
>`unsigned int` if rank cannot be negative?
>> +	/* Each node is initially its own parent */
>> +	for (i = 0; i < csn; i++) {
>> +		nodes[i].parent = i;
>> +		nodes[i].rank = 0;
>> +	}
>With the suggestion above, nodes could start with parent = NULL and
>self-parent be corrected during the first find_root -- thus whole array
>could be simply init'd to zeroes with kzalloc.
>My 0.02€,
>Michal