[PATCH 0/4] kernfs: remove kernfs_rwsem from dentry revalidation

[PATCH 0/4] kernfs: remove kernfs_rwsem from dentry revalidation

[Shakeel Butt]

At Meta, we are seeing important system daemons that poll cgroupfs and
sysfs geth stuck in kernfs_dop_revalidate() for minutes. The two that
hurt most are the ones we can least afford to lose: oomd, which decides
what to kill when a machine runs out of memory, and below[1], which
records the telemetry used to understand what happened afterwards.

kernfs_dop_revalidate() takes kernfs_rwsem for read once per path component
of every walk into a kernfs mount. Linux rwsems do not permit reader lock
stealing once a writer is queued, so one writer -- a cgroup created or
destroyed, a device renamed -- parks the entire incoming reader stream in
uninterruptible sleep. Daemons polling cgroup files in a loop are exactly
the workload that turns this into a convoy, and cgroup churn is exactly
what a busy machine does.

Nothing the callback reads needs the semaphore. kn->active is an atomic_t
already tested lock-free elsewhere, kn->__parent and kn->name are RCU
pointers, kn->ns can be compared rather than dereferenced, and
parent->dir.rev is a plain counter.

  1/4 uses the parent inode and name the VFS already passes to
      ->d_revalidate() rather than recovering them from mutable dentry
      fields, comparing the name by explicit length
  2/4 annotates the directory revision counter for lockless access
  3/4 compares namespace tags by pointer
  4/4 removes kernfs_rwsem from the callback

LOOKUP_RCU still returns -ECHILD. kernfs_iop_permission() forces every walk
out of RCU-walk before children are revalidated, so lifting it here would
have no effect until that path is fixed; left to a separate series.

Readers walking cgroupfs and sysfs while another thread churns cgroups,
renames netdevs and adds/removes devices, on an 8-CPU VM:

                    kernfs_rwsem read   contentions   revalidate among
                        acquisitions                  top call sites
  before                  48,593,360     1,744,517    #1 and #2
  after                    1,280,280       429,846    absent

Reader path-walk throughput improved 35-53% over the same workload.

Tested against an unpatched control of the same tree, built and booted with
KASAN, KCSAN (default and STRICT), PROVE_LOCKING, PROVE_RCU,
DEBUG_ATOMIC_SLEEP and LOCK_STAT. The deactivated, renamed and
namespace-moved reject paths and negative-dentry invalidation all behave as
before. KCSAN_STRICT over 180s reports no data race involving
kernfs_dop_revalidate() or any field it reads, and there are no KASAN,
lockdep or might-sleep reports across millions of concurrent path walks.
The only kernfs KCSAN reports are in kernfs_refresh_inode(), present
identically on the control and addressed separately.

Link: https://github.com/facebookincubator/below [1]

Shakeel Butt (4):
  kernfs: Use VFS lookup context in d_revalidate()
  kernfs: Prepare directory revisions for lockless reads
  kernfs: Avoid namespace dereference in d_revalidate()
  kernfs: Remove kernfs_rwsem from dentry revalidation

 fs/kernfs/dir.c             | 76 +++++++++++++++----------------------
 fs/kernfs/kernfs-internal.h |  9 ++---
 2 files changed, 35 insertions(+), 50 deletions(-)


base-commit: 7079a12d7506b07fb53b54a664bfad5fa9b16d70
-- 
2.53.0-Meta

[PATCH 1/4] kernfs: Use VFS lookup context in d_revalidate()

[Shakeel Butt]

The VFS supplies a stable parent inode and expected name to the
revalidation callback. Use them instead of recovering the same
information from mutable dentry fields.

Compare the name using its explicit length because it may point into the
pathname and need not be terminated at name->len. This also prepares the
callback for lockless operation.

Signed-off-by: Shakeel Butt <shakeel.butt@linux.dev>
---
 fs/kernfs/dir.c | 39 +++++++++++++++++----------------------
 1 file changed, 17 insertions(+), 22 deletions(-)

diff --git a/fs/kernfs/dir.c b/fs/kernfs/dir.c
index 82bbaeb326aa..541bb5525437 100644
--- a/fs/kernfs/dir.c
+++ b/fs/kernfs/dir.c
@@ -1171,23 +1171,19 @@ struct kernfs_node *kernfs_create_empty_dir(struct kernfs_node *parent,
 static int kernfs_dop_revalidate(struct inode *dir, const struct qstr *name,
 				 struct dentry *dentry, unsigned int flags)
 {
-	struct kernfs_node *kn, *parent;
+	struct kernfs_node *kn, *kn_parent;
+	struct kernfs_node *parent = dir->i_private;
 	struct kernfs_root *root;
+	const char *kn_name;
 
 	if (flags & LOOKUP_RCU)
 		return -ECHILD;
 
 	/* Negative hashed dentry? */
 	if (d_really_is_negative(dentry)) {
-		/* If the kernfs parent node has changed discard and
-		 * proceed to ->lookup.
-		 *
-		 * There's nothing special needed here when getting the
-		 * dentry parent, even if a concurrent rename is in
-		 * progress. That's because the dentry is negative so
-		 * it can only be the target of the rename and it will
-		 * be doing a d_move() not a replace. Consequently the
-		 * dentry d_parent won't change over the d_move().
+		/*
+		 * If the kernfs parent node has changed discard and proceed to
+		 * ->lookup.
 		 *
 		 * Also kernfs negative dentries transitioning from
 		 * negative to positive during revalidate won't happen
@@ -1195,14 +1191,11 @@ static int kernfs_dop_revalidate(struct inode *dir, const struct qstr *name,
 		 * changes and the lookup re-done so that a new positive
 		 * dentry can be properly created.
 		 */
-		root = kernfs_root_from_sb(dentry->d_sb);
+		root = kernfs_root(parent);
 		down_read(&root->kernfs_rwsem);
-		parent = kernfs_dentry_node(dentry->d_parent);
-		if (parent) {
-			if (kernfs_dir_changed(parent, dentry)) {
-				up_read(&root->kernfs_rwsem);
-				return 0;
-			}
+		if (kernfs_dir_changed(parent, dentry)) {
+			up_read(&root->kernfs_rwsem);
+			return 0;
 		}
 		up_read(&root->kernfs_rwsem);
 
@@ -1220,18 +1213,20 @@ static int kernfs_dop_revalidate(struct inode *dir, const struct qstr *name,
 	if (!kernfs_active(kn))
 		goto out_bad;
 
-	parent = kernfs_parent(kn);
+	kn_parent = kernfs_parent(kn);
 	/* The kernfs node has been moved? */
-	if (kernfs_dentry_node(dentry->d_parent) != parent)
+	if (parent != kn_parent)
 		goto out_bad;
 
 	/* The kernfs node has been renamed */
-	if (strcmp(dentry->d_name.name, kernfs_rcu_name(kn)) != 0)
+	kn_name = kernfs_rcu_name(kn);
+	if (name->len != strlen(kn_name) ||
+	    memcmp(name->name, kn_name, name->len))
 		goto out_bad;
 
 	/* The kernfs node has been moved to a different namespace */
-	if (parent && kernfs_ns_enabled(parent) &&
-	    kernfs_ns_id(kernfs_info(dentry->d_sb)->ns) != kernfs_ns_id(kn->ns))
+	if (kn_parent && kernfs_ns_enabled(kn_parent) &&
+	    kernfs_ns_id(kernfs_info(dir->i_sb)->ns) != kernfs_ns_id(kn->ns))
 		goto out_bad;
 
 	up_read(&root->kernfs_rwsem);
-- 
2.53.0-Meta

[PATCH 2/4] kernfs: Prepare directory revisions for lockless reads

[Shakeel Butt]

Negative dentry revalidation only needs to sample the parent directory
generation and compare it with the value recorded at lookup time.
Annotate those accesses with READ_ONCE() and WRITE_ONCE() so the
comparison can safely move outside kernfs_rwsem.

Revision updates remain serialized by kernfs_rwsem. Assert that writer
contract in kernfs_inc_rev(); the read half of the increment stays plain
because the semaphore excludes other writers.

Signed-off-by: Shakeel Butt <shakeel.butt@linux.dev>
---
 fs/kernfs/kernfs-internal.h | 9 ++++-----
 1 file changed, 4 insertions(+), 5 deletions(-)

diff --git a/fs/kernfs/kernfs-internal.h b/fs/kernfs/kernfs-internal.h
index aa784b540b36..20a0cf42ba8d 100644
--- a/fs/kernfs/kernfs-internal.h
+++ b/fs/kernfs/kernfs-internal.h
@@ -147,20 +147,19 @@ static inline struct kernfs_node *kernfs_dentry_node(struct dentry *dentry)
 static inline void kernfs_set_rev(struct kernfs_node *parent,
 				  struct dentry *dentry)
 {
-	dentry->d_time = parent->dir.rev;
+	WRITE_ONCE(dentry->d_time, READ_ONCE(parent->dir.rev));
 }
 
 static inline void kernfs_inc_rev(struct kernfs_node *parent)
 {
-	parent->dir.rev++;
+	lockdep_assert_held_write(&parent->dir.root->kernfs_rwsem);
+	WRITE_ONCE(parent->dir.rev, parent->dir.rev + 1);
 }
 
 static inline bool kernfs_dir_changed(struct kernfs_node *parent,
 				      struct dentry *dentry)
 {
-	if (parent->dir.rev != dentry->d_time)
-		return true;
-	return false;
+	return READ_ONCE(parent->dir.rev) != READ_ONCE(dentry->d_time);
 }
 
 extern const struct super_operations kernfs_sops;
-- 
2.53.0-Meta

[PATCH 3/4] kernfs: Avoid namespace dereference in d_revalidate()

[Shakeel Butt]

Commit 1fe989e1c42a ("kernfs: use namespace id instead of pointer for
hashing and comparison") changed dentry revalidation to compare namespace
IDs along with the comparisons that determine visible directory ordering.

Dereferencing a namespace tag that kernfs_rename_ns() can replace is not
suitable once dentry revalidation stops taking kernfs_rwsem. Use pointer
equality for this non-user-visible equality check instead. Namespace IDs
uniquely identify namespace objects, so pointer and ID equality cannot
disagree for valid tags. Hashing and directory ordering continue to use
IDs.

kn->ns becomes a lockless read in the next commit, so mark both sides of
it now. The read is in kernfs_dop_revalidate(); the stores that can run
while the node is visible are the two in kernfs_rename_ns(). The remaining
stores, in kernfs_create_dir_ns(), kernfs_create_empty_dir() and
kernfs_create_link(), all precede kernfs_add_one() and need no marking.

Signed-off-by: Shakeel Butt <shakeel.butt@linux.dev>
---
 fs/kernfs/dir.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

diff --git a/fs/kernfs/dir.c b/fs/kernfs/dir.c
index 541bb5525437..27949b0e027c 100644
--- a/fs/kernfs/dir.c
+++ b/fs/kernfs/dir.c
@@ -1226,7 +1226,7 @@ static int kernfs_dop_revalidate(struct inode *dir, const struct qstr *name,
 
 	/* The kernfs node has been moved to a different namespace */
 	if (kn_parent && kernfs_ns_enabled(kn_parent) &&
-	    kernfs_ns_id(kernfs_info(dir->i_sb)->ns) != kernfs_ns_id(kn->ns))
+	    kernfs_info(dir->i_sb)->ns != READ_ONCE(kn->ns))
 		goto out_bad;
 
 	up_read(&root->kernfs_rwsem);
@@ -1873,7 +1873,7 @@ int kernfs_rename_ns(struct kernfs_node *kn, struct kernfs_node *new_parent,
 
 		rcu_assign_pointer(kn->__parent, new_parent);
 
-		kn->ns = new_ns;
+		WRITE_ONCE(kn->ns, new_ns);
 		if (new_name)
 			rcu_assign_pointer(kn->name, new_name);
 
@@ -1881,7 +1881,7 @@ int kernfs_rename_ns(struct kernfs_node *kn, struct kernfs_node *new_parent,
 		kernfs_put(old_parent);
 	} else {
 		/* name assignment is RCU protected, parent is the same */
-		kn->ns = new_ns;
+		WRITE_ONCE(kn->ns, new_ns);
 		if (new_name)
 			rcu_assign_pointer(kn->name, new_name);
 	}
-- 
2.53.0-Meta

[PATCH 4/4] kernfs: Remove kernfs_rwsem from dentry revalidation

[Shakeel Butt]

kernfs_dop_revalidate() takes kernfs_rwsem for read once per path component
of every walk into a kernfs mount. Linux rwsems do not permit reader lock
stealing once a writer is queued, so a single writer parks the whole
incoming reader stream in uninterruptible sleep, stalling cgroup-polling
daemons for minutes.

Nothing the callback reads requires the semaphore. kn->active is an
atomic_t that kernfs_find_and_get_node_by_id() already tests through
__kernfs_active(); kn->__parent and kn->name are RCU pointers whose old
values are freed only after a grace period; kn->ns is now compared rather
than dereferenced; parent->dir.rev was annotated earlier in this series.

What the semaphore does provide is a coherent snapshot, and that is not
needed. ->d_revalidate() answers a question about a single instant, and the
answer is already stale when it returns: a rename landing just after
up_read() gives the same outcome as one observed mid-read. A lockless
reader can only return "valid" for the (parent, name, namespace) triple
identifying the dentry it was handed, and that triple was true when the
dentry was instantiated, so it reports a genuine past state exactly as the
locked version did. Removal is backstopped by kernfs_get_active() failing
in the subsequent open().

Take an RCU read lock instead. kernfs_parent() and kernfs_rcu_name() work
unchanged: the condition in their rcu_dereference_check() is an alternative
to holding the RCU read lock, not an extra requirement. The negative dentry
path needs nothing, as @dir pins the parent. The namespace check can use
@parent directly once the preceding check establishes it equals
kernfs_parent(kn), so the kn_parent local and its NULL test go away.

kernfs_ns_enabled() reads @parent->flags, which KERNFS_ACTIVATED and
KERNFS_REMOVING update as a plain read-modify-write under kernfs_rwsem.
Those bits are not read here and KERNFS_NS cannot change once the directory
has children, so mark the read data_race() rather than READ_ONCE(), which
would not silence KCSAN against the unmarked writers anyway.

kernfs_iop_permission() still forces every walk out of RCU-walk before
children are revalidated, so lifting the LOOKUP_RCU bail here would have no
observable effect; it is left to the series fixing that path.

Readers walking cgroupfs and sysfs against concurrent cgroup and netdev
churn: kernfs_rwsem read acquisitions drop from 48,593,360 to 1,280,280,
and kernfs_dop_revalidate() no longer appears among its contention sites.

Signed-off-by: Shakeel Butt <shakeel.butt@linux.dev>
---
 fs/kernfs/dir.c | 49 ++++++++++++++++++++-----------------------------
 1 file changed, 20 insertions(+), 29 deletions(-)

diff --git a/fs/kernfs/dir.c b/fs/kernfs/dir.c
index 27949b0e027c..cd7a8ff8b6b2 100644
--- a/fs/kernfs/dir.c
+++ b/fs/kernfs/dir.c
@@ -1171,9 +1171,8 @@ struct kernfs_node *kernfs_create_empty_dir(struct kernfs_node *parent,
 static int kernfs_dop_revalidate(struct inode *dir, const struct qstr *name,
 				 struct dentry *dentry, unsigned int flags)
 {
-	struct kernfs_node *kn, *kn_parent;
 	struct kernfs_node *parent = dir->i_private;
-	struct kernfs_root *root;
+	struct kernfs_node *kn;
 	const char *kn_name;
 
 	if (flags & LOOKUP_RCU)
@@ -1191,49 +1190,41 @@ static int kernfs_dop_revalidate(struct inode *dir, const struct qstr *name,
 		 * changes and the lookup re-done so that a new positive
 		 * dentry can be properly created.
 		 */
-		root = kernfs_root(parent);
-		down_read(&root->kernfs_rwsem);
-		if (kernfs_dir_changed(parent, dentry)) {
-			up_read(&root->kernfs_rwsem);
-			return 0;
-		}
-		up_read(&root->kernfs_rwsem);
-
-		/* The kernfs parent node hasn't changed, leave the
-		 * dentry negative and return success.
-		 */
-		return 1;
+		return !kernfs_dir_changed(parent, dentry);
 	}
 
 	kn = kernfs_dentry_node(dentry);
-	root = kernfs_root(kn);
-	down_read(&root->kernfs_rwsem);
+
+	guard(rcu)();
 
 	/* The kernfs node has been deactivated */
-	if (!kernfs_active(kn))
-		goto out_bad;
+	if (!__kernfs_active(kn))
+		return 0;
 
-	kn_parent = kernfs_parent(kn);
 	/* The kernfs node has been moved? */
-	if (parent != kn_parent)
-		goto out_bad;
+	if (kernfs_parent(kn) != parent)
+		return 0;
 
 	/* The kernfs node has been renamed */
 	kn_name = kernfs_rcu_name(kn);
 	if (name->len != strlen(kn_name) ||
 	    memcmp(name->name, kn_name, name->len))
-		goto out_bad;
+		return 0;
 
-	/* The kernfs node has been moved to a different namespace */
-	if (kn_parent && kernfs_ns_enabled(kn_parent) &&
+	/*
+	 * The kernfs node has been moved to a different namespace.
+	 *
+	 * KERNFS_NS is set by kernfs_enable_ns() while @parent still has no
+	 * children, so it cannot change while a child of @parent is being
+	 * revalidated. The other bits in that word, KERNFS_ACTIVATED and
+	 * KERNFS_REMOVING, are updated under kernfs_rwsem and are not read
+	 * here, so racing with them is intentional and harmless.
+	 */
+	if (data_race(kernfs_ns_enabled(parent)) &&
 	    kernfs_info(dir->i_sb)->ns != READ_ONCE(kn->ns))
-		goto out_bad;
+		return 0;
 
-	up_read(&root->kernfs_rwsem);
 	return 1;
-out_bad:
-	up_read(&root->kernfs_rwsem);
-	return 0;
 }
 
 const struct dentry_operations kernfs_dops = {
-- 
2.53.0-Meta