[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 :-)