linux-kernel - Re: [PATCH-cpuset v8 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: <ZoMXN3G72xtCLjgp@slm.duckdns.org>
Date: Mon, 1 Jul 2024 10:53:11 -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, torvalds@...ux-foundation.org,
	akpm@...ux-foundation.org
Subject: Re: [PATCH-cpuset v8 1/2] Union-Find: add a new module in kernel
 library

Hello, Xavier.

On Sat, Jun 29, 2024 at 12:13:01AM +0800, Xavier wrote:
...
> +Initializing Union-Find
> +--------------------
> +
> +When initializing the Union-Find data structure, a single pointer to the
> +Union-Find instance needs to be passed. Initialize the parent pointer to point
> +to itself and set the rank to 0.
> +Example::
> +
> +	struct uf_node *my_node = vzalloc(sizeof(struct uf_node));
> +	uf_nodes_init(my_node);

It'd be better to replace the example with something which follows typical
kernel usage.

> diff --git a/include/linux/union_find.h b/include/linux/union_find.h
> new file mode 100644
> index 0000000000..56571c93a5
> --- /dev/null
> +++ b/include/linux/union_find.h
> @@ -0,0 +1,24 @@
> +/* SPDX-License-Identifier: GPL-2.0 */

It'd probably be useful to have a brief overview of what this is about and
point to the documentation here.

> +/* Define a union-find node struct */

I don't think the comment is contributing anything.

> +struct uf_node {
> +	struct uf_node *parent;
> +	unsigned int rank;
> +};
> +
> +/* Allocate nodes and initialize to 0 */

and this comment doesn't match what the code is doing. It's neither
allocating or setting everything to zero. Also, please use function comment
style (w/ /** and @ arg descriptions).

> +static inline void uf_nodes_init(struct uf_node *node)
> +{
> +	node->parent = node;
> +	node->rank = 0;
> +}

We'd also need an initializer for static cases.

> +/* 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);

Please use function comment style comments above the implementatino of each
function.

> +struct uf_node *uf_find(struct uf_node *node)
> +{
> +	struct uf_node *parent;
> +
> +	/*Find the root node and perform path compression at the same time*/

Spaces?

> +	while (node->parent != node) {
> +		parent = node->parent;
> +		node->parent = parent->parent;
> +		node = parent;
> +	}
> +	return node;
> +}
> +
> +/*Function to merge two sets, using union by rank*/

Ditto.

Overall, this looks okay to me and the cgroup conversion does look nice.
However, it'd be really nice if you could find another place where this can
be applied.

Thanks.

-- 
tejun