Re: [PATCH] kernfs: Build paths in linear time with respect to depth

[Tejun Heo <tj@kernel.org>]

Hello, Chris.

On Sat, Nov 07, 2026 at 07:16:46PM -0800, Chris Down wrote:
> kernfs nodes only point to their parent. To build a path top-down,
> kernfs_path_from_node_locked() walks back up from the leaf for each
> name, so the work grows with the square of the depth. Reading
> /proc/<pid>/cgroup does this with IRQs off and css_set_lock held, so a
> read from a deep delegated subtree can hold up fork and exit elsewhere
> on the machine, which is certainly suboptimal.
...
> In terms of operations, with a 15,000 deep path chain and a 4 KiB
> buffer:
>
> 1. Parent and name pointer reads go from 112.6 million to 75,003 with
>    this change
> 2. On my machine the second read of /proc/self/cgroup takes 99.86% less
>    time.

I don't think a 15,000 deep cgroup chain makes much sense as a use case.
A lot of other stuff in the controllers will break down at five-digit
depths, and quadratic isn't that expensive when the base number is
small. Did you see this overhead in more realistic scenarios?

> +	/*
> +	 * We can only walk towards the root. Fill from the end and wrap
> +	 * so that if the path is too long we keep its first bytes.
> +	 */

Even if it is worth doing, the implementation looks too convoluted. Most
of the complication seems to come from supporting wrapping to keep the
head of an overlong path. The only callers that care about what the
buffer holds on overflow are debug outputs. How about changing the
contract so that on overflow the buffer keeps the tail end of the path
instead of the head, which is more useful anyway, and the function
returns -E2BIG rather than the length?

Thanks.

--
tejun