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

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

[Chris Down]

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.

Let's improve this by filling the buffer from the end as we walk up,
and if the path fits, moving it into place directly.

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.

Fixes: 3abb1d90f5d9 ("kernfs: make kernfs_path*() behave in the style of strlcpy()")
Cc: <stable@vger.kernel.org>
Signed-off-by: Chris Down <chris@chrisdown.name>
---
 fs/kernfs/dir.c | 61 +++++++++++++++++++++++++++++++++++++++----------
 1 file changed, 49 insertions(+), 12 deletions(-)

diff --git a/fs/kernfs/dir.c b/fs/kernfs/dir.c
index 800af10d9511..1ac6a5ec451b 100644
--- a/fs/kernfs/dir.c
+++ b/fs/kernfs/dir.c
@@ -94,6 +94,14 @@ static struct kernfs_node *kernfs_common_ancestor(struct kernfs_node *a,
 	return a;
 }
 
+static void kernfs_reverse_path(char *buf, size_t len)
+{
+	size_t i;
+
+	for (i = 0; i < len / 2; i++)
+		swap(buf[i], buf[len - i - 1]);
+}
+
 /**
  * kernfs_path_from_node_locked - find a pseudo-absolute path to @kn_to,
  * where kn_from is treated as root of the path.
@@ -130,9 +138,14 @@ static int kernfs_path_from_node_locked(struct kernfs_node *kn_to,
 {
 	struct kernfs_node *kn, *common;
 	const char parent_str[] = "/..";
-	size_t depth_from, depth_to, len = 0;
+	size_t depth_from, len = 0, end, pos, room, n;
+	bool wrapped = false;
+	const char *name;
 	ssize_t copied;
-	int i, j;
+	int i;
+
+	if (!buflen)
+		return -E2BIG;
 
 	if (!kn_to)
 		return strscpy(buf, "(null)", buflen);
@@ -147,7 +160,6 @@ static int kernfs_path_from_node_locked(struct kernfs_node *kn_to,
 	if (WARN_ON(!common))
 		return -EINVAL;
 
-	depth_to = kernfs_depth(common, kn_to);
 	depth_from = kernfs_depth(common, kn_from);
 
 	buf[0] = '\0';
@@ -159,18 +171,43 @@ static int kernfs_path_from_node_locked(struct kernfs_node *kn_to,
 		len += copied;
 	}
 
-	/* Calculate how many bytes we need for the rest */
-	for (i = depth_to - 1; i >= 0; i--) {
-		const char *name;
-
-		for (kn = kn_to, j = 0; j < i; j++)
-			kn = rcu_dereference(kn->__parent);
-
+	/*
+	 * 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.
+	 */
+	end = buflen - 1;
+	room = end - len;
+	if (!room)
+		return len;
+
+	pos = end;
+	buf[end] = '\0';
+	for (kn = kn_to; kn != common; kn = rcu_dereference(kn->__parent)) {
 		name = rcu_dereference(kn->name);
-		len += scnprintf(buf + len, buflen - len, "/%s", name);
+		n = min(strlen(name), room - 1);
+		if (n + 1 > pos - len) {
+			size_t head = pos - len;
+
+			memcpy(buf + len, name + n - head, head);
+			n -= head;
+			pos = end;
+			wrapped = true;
+		}
+		pos -= n;
+		memcpy(buf + pos, name, n);
+		buf[--pos] = '/';
+	}
+
+	if (wrapped) {
+		/* Rotate the two pieces into path order. */
+		kernfs_reverse_path(buf + len, pos - len);
+		kernfs_reverse_path(buf + pos, end - pos);
+		kernfs_reverse_path(buf + len, room);
+		return end;
 	}
 
-	return len;
+	memmove(buf + len, buf + pos, end - pos + 1);
+	return len + (end - pos);
 }
 
 /**

base-commit: a42ae51fe3c36cef82dc687ea594ca232a785fd4
-- 
2.54.0

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

[Chris Down]

Chris Down writes:
>Fixes: 3abb1d90f5d9 ("kernfs: make kernfs_path*() behave in the style of strlcpy()")
>Cc: <stable@vger.kernel.org>

Note, I am not sure whether this is worthy of stable. But I have noticed that 
in some cases this build time can be pretty substantial with these locks held. 
But on the other hand it has been like this for quite a while, so maybe it 
doesn't matter :-)

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

[Tejun Heo]

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

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

[Chris Down]

Hi Tejun,

Thanks for taking a look!

Tejun Heo writes:
>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?

Agreed that nobody should be building anything like that on purpose, and
at the depths people actually use there isn't much in it. Here's the
median read of /proc/self/cgroup in a 4 CPU VM, with single character
names:

     depth    before    after
     4        304ns     258ns
     16       549ns     396ns
     64       2.8us     1.0us
     256      69us      4.2us
     1024     2.5ms     20us
     2046     12.0ms    43us

What bothers me more is that whoever picks the depth isn't the one who is
affected by it. cgroup.max.depth defaults to max, so anyone with a
delegated subtree can make a deep chain. Every read of /proc/<pid>/cgroup
for a task at the bottom of it then takes that long with css_set_lock held
and IRQs off. It doesn't take five digits for that to become problematic,
either. Here's the median fork() + exit on another CPU of the same VM
while one task does that in a loop:

     depth of reader    before    after
     (no reader)        51us      52us
     64                 56us      53us
     256                363us     60us
     1024               5.0ms     93us
     2046               21.9ms    117us

(In case you're wondering why 2046, that's about as deep as you can go
without brushing up against PATH_MAX.)

You're right that other things break down at depths like 15,000. Just
creating that chain takes minutes. But that only slows down whoever
creates it. This slows down fork and exit for everyone else.

>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?

Yeah, that's a lot nicer, thanks.

The one caller I found which relies on the start of the path being kept is
SEQ_printf_task_group_path() in sched/debug. Its fallback buffer appends
"..." when the path fills it, which will now be on the wrong side. That
code is moving to sched.h in tip at the moment, so I'll send the fix for
it there separately, rather than have the two conflict in -next.

Based on what you said, in v2 I'll also drop Fixes: and Cc: stable, since
this is now a change in behaviour rather than only a speedup.

Thanks!

Chris