linux-kernel - Re: [PATCH-cpuset v10 2/2] 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>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <zkkadtdssdgkndojsvfwbig3xwtqvfleyw3wbg6vewjntmklxe@xle6jq7jvkv5>
Date: Wed, 3 Jul 2024 11:40:49 +0200
From: Michal Koutný <mkoutny@...e.com>
To: Xavier <xavier_qy@....com>
Cc: tj@...nel.org, longman@...hat.com, akpm@...ux-foundation.org, 
	lizefan.x@...edance.com, hannes@...xchg.org, cgroups@...r.kernel.org, 
	linux-kernel@...r.kernel.org, torvalds@...ux-foundation.org
Subject: Re: [PATCH-cpuset v10 2/2] cpuset: use Union-Find to optimize the
 merging of cpumasks

On Wed, Jul 03, 2024 at 02:37:27PM GMT, Xavier <xavier_qy@....com> wrote:
> @@ -1102,31 +1101,25 @@ static int generate_sched_domains(cpumask_var_t **domains,
>  	if (root_load_balance && (csn == 1))
>  		goto single_root_domain;
>  
> -	for (i = 0; i < csn; i++)
> -		csa[i]->pn = i;
> -	ndoms = csn;
> -
> -restart:
> -	/* Find the best partition (set of sched domains) */
> -	for (i = 0; i < csn; i++) {
> -		struct cpuset *a = csa[i];
> -		int apn = a->pn;
> -
> -		for (j = 0; j < csn; j++) {
> -			struct cpuset *b = csa[j];
> -			int bpn = b->pn;
> -
> -			if (apn != bpn && cpusets_overlap(a, b)) {
> -				for (k = 0; k < csn; k++) {
> -					struct cpuset *c = csa[k];
> +	if (!cgrpv2) {

I'm surprised that original code wasn't branched on this on you add it
here. Why is UF used only for v1 code?

> +		for (i = 0; i < csn; i++)
> +			uf_node_init(&csa[i]->node);
>  
> -					if (c->pn == bpn)
> -						c->pn = apn;
> -				}
> -				ndoms--;	/* one less element */
> -				goto restart;
> +		/* Merge overlapping cpusets */
> +		for (i = 0; i < csn; i++) {
> +			for (j = 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 = 0; i < csn; i++) {
> +			if (csa[i]->node.parent == &csa[i]->node)
> +				ndoms++;

The naked parent access doesn't hide the UF abstraction well.
I'd consider uf_find(&csa[i]->node) == &csa[i]->node or a specific
helper like uf_is_representant(&csa[i]->node).

Thanks,
Michal

Download attachment "signature.asc" of type "application/pgp-signature" (229 bytes)