linux-kernel - Re: [PATCH-cpuset v5 1/2] Union-Find: add a new module in kernel library

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: <ZnXsUnAi7VnX0tZJ@slm.duckdns.org>
Date: Fri, 21 Jun 2024 11:10:42 -1000
From: Tejun Heo <tj@...nel.org>
To: Xavier <xavier_qy@....com>
Cc: longman@...hat.com, mkoutny@...e.com, lizefan.x@...edance.com,
	hannes@...xchg.org, cgroups@...r.kernel.org,
	linux-kernel@...r.kernel.org
Subject: Re: [PATCH-cpuset v5 1/2] Union-Find: add a new module in kernel
 library

Hello,

On Fri, Jun 21, 2024 at 04:49:51PM +0800, Xavier wrote:
> +/* 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 kzalloc(sizeof(struct uf_node) * node_num, GFP_KERNEL);
> +}

This is a very unusual pattern for kernel data structure. Most data
structures allow the member entry to be embedded in other structs or
allocated in user-defined ways. Do they need to be allocated consecutively?
If so, this might be problematic as e.g. 4096 entries, which doesn't sound
too high, would already require consecutive 64k allocation, which is getting
close to vmalloc territory if not already there.

> +struct uf_node *uf_find(struct uf_node *node)
> +{
> +	struct uf_node *parent;
> +
> +	if (!node->parent) {
> +		node->parent = node;
> +		return node;
> +	}
> +
> +	/*Find the root node and perform path compression at the same time*/
> +	while (node->parent != node) {
> +		parent = node->parent;
> +		node->parent = parent->parent;
> +		node = 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 = uf_find(node1);
> +	struct uf_node *root2 = uf_find(node2);
> +
> +	if (root1 != root2) {
> +		if (root1->rank < root2->rank) {
> +			root1->parent = root2;
> +		} else if (root1->rank > root2->rank) {
> +			root2->parent = root1;
> +		} else {
> +			root2->parent = root1;
> +			root1->rank++;
> +		}
> +	}
> +}

Code doesn't seem to suggest allocation needs to be consecutive tho. This is
a bit too generic to route through the cgroup tree without wider reviews.
When you post the next revision, can you please include Linus Torvalds
<torvalds@...ux-foundation.org> and Andrew Morton
<akpm@...ux-foundation.org> and point to some other possible usages in
kernel?

Thanks.

-- 
tejun