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

[Tejun Heo]

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