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@xxxxxxxxxxxxxxxxxxxx> and Andrew Morton
<akpm@xxxxxxxxxxxxxxxxxxxx> and point to some other possible usages in
kernel?
Thanks.
--
tejun
