linux-kernel - 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 for Android: free password hash cracker in your pocket

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

Date: Tue, 4 Jun 2024 11:02:57 -0400
From: Waiman Long <longman@...hat.com>
To: Xavier <ghostxavier@...a.com>
Cc: 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

On 6/3/24 08:31, Xavier 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.
>
> Signed-off-by: Xavier <ghostxavier@...a.com>
>
> Hi Longman,
>
> Thank you for your feedback on the previous version of the patch.
>
> Now I will respond to the three questions you raised:
> 1) The function comment describes the algorithm to find the set of
> domains. If you change the algorithm, you have to update the comment as
> well.
>
> Reply: Sorry for not paying attention to the comments before. The new patch (v3) has updated the comment content.
>
> 2) generate_sched_domains() is not in a performance critical path, so
> its performance is not as important. Also the csn array is typically not
> that big. Changing the algorithm may introduce new bugs which leads to
> the next point.
>
> Reply: Indeed, this function is not a critical path impacting performance, but it's always good to optimize efficiency. The optimization is limited to the internals of this function and does not affect other modules, so fixing the internal bug should have manageable risks.

In term of efficiency, your patch does eliminate the third iteration (k) 
in the csn iteration loop. However the new union_sets() function may go 
up the node hierarchy which can considered a third iteration in some 
way. So there is some saving, but not as significant as it looks. It 
does simplify the code and make it a bit easier to read.

>
> 3) How do you test your code to ensure its correctness?
> I applied your patch and run the ./test_cpuset_prs.sh got the following...
>
> Reply: I'm very sorry, this is my first time submitting a kernel patch and I don't know which test cases need to be run. I just constructed some scenarios locally to test, so the testing scope is limited. Thank you for providing the test cases. I have reproduced and resolved the issue, and have passed several other test cases in CGroup. But currently, I only have QEMU simulation environment, so my testing ability is limited. I hope you can help me with some comprehensive testing of my new version patch. Thank you very much.
>
> I hope you can pay further attention to the new patch.

Also your patch eliminates all the use of the cpuset->pn variable. So 
you cab remove it as it is no longer needed.

After a harder look at the generate_sched_domains() code, I have found a 
bug in the code with respect to the support of remote partition. I will 
send another patch to fix it. I also realize that the function was 
originally designed to support v1 cpuset. v2 cpuset is quite different 
and the code can be simplified for the v2 use case.

You are welcome to send a v4 patch on top of the new cpuset code base.

Thanks,
Longman