[PATCH bpf-next v1 00/11] fs: unified VFS ancestor walk for Landlock and BPF

[PATCH bpf-next v1 00/11] fs: unified VFS ancestor walk for Landlock and BPF

[Justin Suess]

Howdy folks,

This series adds a VFS API for walking a path's ancestors that covers
both path-walk modes (refwalk and rcu-walk, plus the hybrid walk)
through a unified interface, converts Landlock to it, and exposes it
to BPF LSM programs.  It picks up Song Liu's bpf path iterator series [1]
where the discussion left it, and tries to be the synthesis of what came
out of that thread: a combination of the callback and open-coded approaches
proposed there.

The structure is unchanged from the RFC [2]: a stepwise engine private
to namei.c, a callback front-end for in-kernel callers (Landlock
is converted, fixing the follow_up() race Al reported, hence the
Fixes: tag on patch 3), and open-coded BPF iterators over the engine in
referenced and rcu flavors, with bpf_path_ancestors_legitimize()
escalating from the latter to the former mid-walk.  Patch 1 is carried
from Song's series.  See the RFC cover for the full background and API
listing.

This is v1 following the RFC and bot feedback, and some of the sillier
mistakes are rectified.

Biggest change is that Song's patch 4 adding BTF_TYPE_SAFE_TRUSTED is
dropped, following [3].  This code wasn't an issue in his original
patchset, because that implementation was refwalk only, whereas this
one handles rcu-walk.  The problem is that trusted types acquired under
RCU don't propagate their RCU-ness to their fields.  Thus marking the
path trusted allows you to use the dentry from an RCU-acquired struct
path outside RCU.

Verifier fixes propagating the RCU-ness to trusted fields can be done,
but it's best as a separate series where the idea can be examined more
closely.  Then marking the dentry as trusted will allow you to use the
dentry xattr kfuncs.  Nothing in this series strictly depends on having
a trusted dentry, nor will marking it trusted require changes in this
API.  See my follow up [4].

Other changes since the RFC:

- vfs_walk_ancestors() is introduced already built on the stepwise
  engine, and the RFC's restructuring patch became a pure exposure
  patch (patch 4): the engine is no longer rewritten mid-series.
- vfs_walk_handover() carries the position's flags over, so an
  escalated walk no longer drops VFS_WALK_POS_MOUNTPOINT.
- A failed bpf_path_ancestors_legitimize() marks the destination
  iterator with BPF_PATH_ANCESTORS_RETRY instead of leaving it
  indistinguishable from a walk that completed at the root; a drained
  source returns -ENOENT, a lost race returns -ECHILD.
- vfs_walk_start() warns on and masks unknown flag bits, which the
  engine shares the flags word with.
- mnt_undo_legitimize() asserts it is called inside an RCU read-side
  critical section.
- Selftests verify the walk actually reaches / (position count plus
  end-of-walk flags), use an acquired position only after the iterator
  is destroyed so the program's reference is provably what keeps it
  alive and retrigger when a concurrent mount anywhere in the system
  legitimately ends the lockless walks with RETRY.
- Stale comments and kernel-doc contracts fixed; notably, rcu-mode
  callback reads race with concurrent changes exactly as in a
  referenced walk, now stated at vfs_walk_ancestors().

Stuff deliberately not changed:

- vfs_walk_handover() validates the seqcount before taking the dentry
  reference, the reverse of __legitimize_path() [5].  That ordering is
  what lets a failed handover leave nothing to put inside the caller's
  RCU read-side critical section, and the window it opens is
  indistinguishable from a rename landing right after a successful
  handover, which any referenced walk tolerates anyway. This matches
  behavior with in-tree existing rcu-walk implementations.
- A callback that stops an rcu-mode walk gets no final seq
  revalidation [5].  This matches rcu-walk practice: may_lookup()
  returns hard verdicts from RCU data without one, and d_walk()'s
  D_WALK_QUIT skips its seqretry.  Keeping a position is what
  validates, via the handover.
- An "__uninit" iterator argument is marked initialized as it is
  processed, so a later "__iter" argument of the same kfunc aliasing
  the same stack slots would see it as initialized [6].  Reaching that
  needs a kfunc whose "__uninit" destination and "__iter" source share
  one iterator BTF type. The slots record the destination's type, so
  a mismatch fails the "__iter" check regardless of aliasing, which is
  what makes this immune.  Answered in [7].

Landlock kselftests pass in full (914/914 under UML) on this revision.

[1] https://lore.kernel.org/bpf/20250617061116.3681325-1-song@kernel.org/
[2] https://lore.kernel.org/bpf/20261006002020.2890858-1-utilityemal77@gmail.com/
[3] https://lore.kernel.org/bpf/efdfa80872c26e9e1b6fe11957ecba8e1b5ffcdad421e34281ed3ebd017b5752@mail.kernel.org/
[4] https://lore.kernel.org/bpf/asUBWNVtSzLXkXsF@zenbox/
[5] https://lore.kernel.org/bpf/20261006003305.44F761F000FF@smtp.kernel.org/
[6] https://lore.kernel.org/bpf/20261006003716.CC7791F000FF@smtp.kernel.org/
[7] https://lore.kernel.org/bpf/asUK2i4229DNzXLI@zenbox/

Justin Suess (10):
  namei: add vfs_walk_ancestors()
  landlock: convert ancestor walk to vfs_walk_ancestors()
  namei: expose the stepwise ancestor walk to fs/
  bpf: add a path ancestor iterator
  selftests/bpf: exercise the path ancestor iterator
  fs: add mnt_undo_legitimize()
  namei: add an rcu-walk mode to the ancestor walk
  bpf: support "__uninit" iterator arguments in generic kfuncs
  bpf: add a lockless path ancestor iterator
  selftests/bpf: exercise the lockless path ancestor iterator

Song Liu (1):
  namei: introduce __path_walk_parent()

 fs/bpf_fs_kfuncs.c                            | 248 ++++++++++++
 fs/internal.h                                 |  22 +
 fs/mount.h                                    |   1 +
 fs/namei.c                                    | 380 ++++++++++++++++--
 fs/namespace.c                                |  65 ++-
 include/linux/namei.h                         |  17 +
 kernel/bpf/verifier.c                         |  44 +-
 security/landlock/fs.c                        | 266 ++++++------
 .../selftests/bpf/prog_tests/path_ancestors.c |  86 ++++
 .../selftests/bpf/progs/path_ancestors.c      | 146 +++++++
 10 files changed, 1098 insertions(+), 177 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/path_ancestors.c
 create mode 100644 tools/testing/selftests/bpf/progs/path_ancestors.c


base-commit: 763187dbbf83764a57d5811168ef9de7b9a60e2d
-- 
2.55.0

[PATCH bpf-next v1 01/11] namei: introduce __path_walk_parent()

[Justin Suess]

From: Song Liu <song@kernel.org>

Factor the step-to-parent logic out of follow_dotdot() into
__path_walk_parent(), which walks a plain struct path to its parent,
crossing mount trees via choose_mountpoint().

This will be used by a VFS ancestor walker serving landlock and BPF.

Suggested-by: Neil Brown <neil@brown.name>
Signed-off-by: Song Liu <song@kernel.org>
[justin: rebased, kept the helper static to namei.c, dropped the
 path_walk_parent() wrapper and the namei.h export]
Signed-off-by: Justin Suess <utilityemal77@gmail.com>
---
 fs/namei.c | 62 ++++++++++++++++++++++++++++++++++++++----------------
 1 file changed, 44 insertions(+), 18 deletions(-)

diff --git a/fs/namei.c b/fs/namei.c
index 20a6534ea3ef..808fb4bed7c4 100644
--- a/fs/namei.c
+++ b/fs/namei.c
@@ -2192,36 +2192,62 @@ static struct dentry *follow_dotdot_rcu(struct nameidata *nd)
 	return nd->path.dentry;
 }
 
-static struct dentry *follow_dotdot(struct nameidata *nd)
+/**
+ * __path_walk_parent - step towards the parent of the given struct path
+ * @path: position to step up from; if it is the root of a mounted tree, it
+ *        is first updated to the mount point that tree is mounted on
+ * @root: boundary not to be crossed; if zero'ed, walk all the way to the
+ *        global root
+ * @flags: %LOOKUP_NO_XDEV returns -EXDEV once @path was updated to a new
+ *         mount; %LOOKUP_BENEATH returns -EXDEV at @root or at the root of
+ *         an unmounted tree, where @path->dentry itself is returned
+ *         otherwise
+ *
+ * Returns: the parent dentry with its refcount incremented, or an ERR_PTR().
+ */
+static struct dentry *__path_walk_parent(struct path *path, const struct path *root, int flags)
 {
-	struct dentry *parent;
-
-	if (path_equal(&nd->path, &nd->root))
+	if (path_equal(path, root))
 		goto in_root;
-	if (unlikely(nd->path.dentry == nd->path.mnt->mnt_root)) {
-		struct path path;
+	if (unlikely(path->dentry == path->mnt->mnt_root)) {
+		struct path new_path;
 
-		if (!choose_mountpoint(real_mount(nd->path.mnt),
-				       &nd->root, &path))
+		if (!choose_mountpoint(real_mount(path->mnt),
+				       root, &new_path))
 			goto in_root;
-		path_put(&nd->path);
-		nd->path = path;
-		nd->inode = path.dentry->d_inode;
-		if (unlikely(nd->flags & LOOKUP_NO_XDEV))
+		path_put(path);
+		*path = new_path;
+		if (unlikely(flags & LOOKUP_NO_XDEV))
 			return ERR_PTR(-EXDEV);
 	}
 	/* rare case of legitimate dget_parent()... */
-	parent = dget_parent(nd->path.dentry);
+	return dget_parent(path->dentry);
+
+in_root:
+	if (unlikely(flags & LOOKUP_BENEATH))
+		return ERR_PTR(-EXDEV);
+	return dget(path->dentry);
+}
+
+static struct dentry *follow_dotdot(struct nameidata *nd)
+{
+	struct dentry *parent;
+
+	if (path_equal(&nd->path, &nd->root)) {
+		/* nd->root is never path_connected()-checked. */
+		if (unlikely(nd->flags & LOOKUP_BENEATH))
+			return ERR_PTR(-EXDEV);
+		return dget(nd->path.dentry);
+	}
+	parent = __path_walk_parent(&nd->path, &nd->root, nd->flags);
+	nd->inode = nd->path.dentry->d_inode;
+	if (IS_ERR(parent))
+		return parent;
 	if (unlikely(!path_connected(nd->path.mnt, parent))) {
 		dput(parent);
 		return ERR_PTR(-ENOENT);
 	}
 	return parent;
-
-in_root:
-	if (unlikely(nd->flags & LOOKUP_BENEATH))
-		return ERR_PTR(-EXDEV);
-	return dget(nd->path.dentry);
 }
 
 static const char *handle_dots(struct nameidata *nd, enum last_type type)
-- 
2.55.0

[PATCH bpf-next v1 02/11] namei: add vfs_walk_ancestors()

[Justin Suess]

Add a callback-based walk over a path and its ancestors, built on
__path_walk_parent(): the kernel owns the loop and the callback must
not sleep, so an rcu-walk engine can be added later without changing
the API.

Internally the walk is a stepwise engine - vfs_walk_start(),
vfs_walk_next(), vfs_walk_end(), static to namei.c for now, with the
walk state declared in fs/internal.h - and vfs_walk_ancestors() is a
loop over it.  The position's flags live in the walk state, where the
next step needs them anyway: stepping off a disconnected position
resumes at the root of its mount.  A later patch exposes the engine so
an iterating consumer can drive it, with every step and invariant
staying in namei.c.

Disconnected root dentries are reported to the callback instead of
terminating the walk.  A disconnected mountpoint landed on by a mount
crossing - the one position this walk visits that a
dget_parent()/follow_up() loop never does - is additionally flagged
VFS_WALK_POS_MOUNTPOINT, so security callers can reproduce their
pre-conversion evaluation sequence exactly.

Suggested-by: NeilBrown <neil@brown.name>
Suggested-by: Christian Brauner <brauner@kernel.org>
Signed-off-by: Justin Suess <utilityemal77@gmail.com>
---
 fs/internal.h         |  10 +++
 fs/namei.c            | 140 ++++++++++++++++++++++++++++++++++++++++++
 include/linux/namei.h |  14 +++++
 3 files changed, 164 insertions(+)

diff --git a/fs/internal.h b/fs/internal.h
index c658c8a5ebd5..bfe62c9bdfc9 100644
--- a/fs/internal.h
+++ b/fs/internal.h
@@ -71,6 +71,16 @@ struct dentry *start_dirop(struct dentry *parent, struct qstr *name,
 			   unsigned int lookup_flags);
 int lookup_noperm_common(struct qstr *qname, struct dentry *base);
 
+/*
+ * The stepwise engine under vfs_walk_ancestors(); fs-internal so iterating
+ * consumers (BPF) can drive it, with the walk invariants staying in namei.c.
+ */
+struct vfs_ancestor_walk {
+	struct path pos;
+	unsigned int pos_flags;	/* VFS_WALK_POS_* describing pos */
+	unsigned int flags;	/* VFS_WALK_* */
+};
+
 void __init filename_init(void);
 
 /*
diff --git a/fs/namei.c b/fs/namei.c
index 808fb4bed7c4..6d5b4b214334 100644
--- a/fs/namei.c
+++ b/fs/namei.c
@@ -2229,6 +2229,146 @@ static struct dentry *__path_walk_parent(struct path *path, const struct path *r
 	return dget(path->dentry);
 }
 
+static unsigned int vfs_walk_pos_flags(const struct vfsmount *mnt,
+				       const struct dentry *dentry)
+{
+	if (unlikely(IS_ROOT(dentry) && dentry != mnt->mnt_root))
+		return VFS_WALK_POS_DISCONNECTED;
+	return 0;
+}
+
+/* No boundary: ancestor walks go up to the real root. */
+static const struct path vfs_walk_no_root;
+
+/* Internal walk flag: the starting position has been yielded. */
+#define VFS_WALK_STARTED	BIT(31)
+
+/**
+ * vfs_walk_start - begin a stepwise ancestor walk
+ * @aw: walk state, valid until vfs_walk_end()
+ * @path: position to walk up from; never modified
+ * @flags: %VFS_WALK_* flags; none defined yet, pass 0
+ */
+static void vfs_walk_start(struct vfs_ancestor_walk *aw,
+			   const struct path *path, unsigned int flags)
+{
+	if (WARN_ON_ONCE(flags))
+		flags = 0;
+	aw->pos = *path;
+	aw->flags = flags;
+	aw->pos_flags = 0;
+	path_get(&aw->pos);
+}
+
+static int vfs_walk_step_ref(struct vfs_ancestor_walk *aw)
+{
+	struct dentry *parent;
+
+	if (unlikely(aw->pos_flags & VFS_WALK_POS_DISCONNECTED)) {
+		/* Resume at the root of the disconnected position's mount. */
+		dput(aw->pos.dentry);
+		aw->pos.dentry = dget(aw->pos.mnt->mnt_root);
+		aw->pos_flags = 0;
+		return 0;
+	}
+	parent = __path_walk_parent(&aw->pos, &vfs_walk_no_root,
+				    LOOKUP_BENEATH);
+	if (IS_ERR(parent))
+		/* The real root. */
+		return 1;
+	/*
+	 * A mount crossing can step onto a disconnected root, whose parent
+	 * is itself: only then is the mountpoint itself yielded, flagged.
+	 */
+	aw->pos_flags = parent == aw->pos.dentry ?
+		VFS_WALK_POS_DISCONNECTED | VFS_WALK_POS_MOUNTPOINT :
+		vfs_walk_pos_flags(aw->pos.mnt, parent);
+	dput(aw->pos.dentry);
+	aw->pos.dentry = parent;
+	return 0;
+}
+
+/**
+ * vfs_walk_next - yield the walk's next position in @aw->pos
+ * @aw: the walk
+ *
+ * The first call yields the starting position itself.  @aw->pos_flags
+ * carries the position's %VFS_WALK_POS_* flags, with the semantics
+ * described at vfs_walk_ancestors().
+ *
+ * Returns: 0 with @aw->pos valid, 1 once the walk has passed the real
+ * root.
+ */
+static int vfs_walk_next(struct vfs_ancestor_walk *aw)
+{
+	if (aw->flags & VFS_WALK_STARTED) {
+		int err = vfs_walk_step_ref(aw);
+
+		if (err)
+			return err;
+	} else {
+		aw->flags |= VFS_WALK_STARTED;
+		aw->pos_flags |= vfs_walk_pos_flags(aw->pos.mnt, aw->pos.dentry);
+	}
+	return 0;
+}
+
+/**
+ * vfs_walk_end - finish a stepwise ancestor walk
+ * @aw: the walk; its positions, including @aw->pos, become invalid
+ */
+static void vfs_walk_end(struct vfs_ancestor_walk *aw)
+{
+	path_put(&aw->pos);
+}
+
+/**
+ * vfs_walk_ancestors - invoke a callback on a path and each of its ancestors
+ * @path: path to walk up from; the caller's path is never modified
+ * @cb: callback invoked on @path, then on each ancestor up to the real
+ *      root, crossing mount boundaries.  @cb must not sleep and returns
+ *      %VFS_WALK_CONTINUE, %VFS_WALK_STOP or a negative errno to abort the
+ *      walk.  @ancestor is only valid during the invocation; @cb must take
+ *      its own references to keep a position.
+ *      A position whose dentry is a disconnected root is flagged with
+ *      %VFS_WALK_POS_DISCONNECTED (plus %VFS_WALK_POS_MOUNTPOINT when it
+ *      is a mountpoint a mount crossing landed on rather than a parent);
+ *      if @cb continues over it, the walk resumes at the root of that
+ *      position's mount.
+ * @data: opaque argument passed to @cb
+ * @flags: %VFS_WALK_* flags; none defined yet, pass 0
+ *
+ * Returns: 0 once the real root was reached, 1 if @cb stopped the walk, or
+ * the negative errno @cb aborted with.
+ */
+int vfs_walk_ancestors(const struct path *path,
+		       int (*cb)(const struct path *ancestor,
+				 unsigned int pos_flags, void *data),
+		       void *data, unsigned int flags)
+{
+	struct vfs_ancestor_walk aw;
+	int ret;
+
+	vfs_walk_start(&aw, path, flags);
+	for (;;) {
+		ret = vfs_walk_next(&aw);
+		if (ret) {
+			if (ret == 1)
+				ret = 0;
+			break;
+		}
+		ret = cb(&aw.pos, aw.pos_flags, data);
+		if (ret < 0)
+			break;
+		if (ret == VFS_WALK_STOP) {
+			ret = 1;
+			break;
+		}
+	}
+	vfs_walk_end(&aw);
+	return ret;
+}
+
 static struct dentry *follow_dotdot(struct nameidata *nd)
 {
 	struct dentry *parent;
diff --git a/include/linux/namei.h b/include/linux/namei.h
index 86d657b24fc6..3e198de7a0d3 100644
--- a/include/linux/namei.h
+++ b/include/linux/namei.h
@@ -162,6 +162,20 @@ extern int follow_down_one(struct path *);
 extern int follow_down(struct path *path, unsigned int flags);
 extern int follow_up(struct path *);
 
+/* per-position flags passed to the vfs_walk_ancestors() callback */
+#define VFS_WALK_POS_DISCONNECTED	BIT(0)
+/* the position is a mountpoint landed on by a mount crossing */
+#define VFS_WALK_POS_MOUNTPOINT		BIT(1)
+
+/* vfs_walk_ancestors() callback verdicts; negative values abort the walk */
+#define VFS_WALK_STOP		0
+#define VFS_WALK_CONTINUE	1
+
+int vfs_walk_ancestors(const struct path *path,
+		       int (*cb)(const struct path *ancestor,
+				 unsigned int pos_flags, void *data),
+		       void *data, unsigned int flags);
+
 int start_renaming(struct renamedata *rd, int lookup_flags,
 		   struct qstr *old_last, struct qstr *new_last);
 int start_renaming_dentry(struct renamedata *rd, int lookup_flags,
-- 
2.55.0

[PATCH bpf-next v1 03/11] landlock: convert ancestor walk to vfs_walk_ancestors()

[Justin Suess]

Replace the open-coded jump_up/follow_up loop of
is_access_to_paths_allowed() with one vfs_walk_ancestors() call, moving
the loop state into a struct passed to the callback.

follow_up() ignores the mount's disappearance, so a concurrent umount
could make the walk operate on an unaccounted mount.  The walker steps
with choose_mountpoint(), which revalidates against mount_lock.  The
disconnected-directory handling is otherwise preserved: MNT_INTERNAL
roots allow and stop, other disconnected roots resume at their mount
root.  Rule evaluation is preserved exactly: disconnected roots that
were positions of the old loop (the walk's start, the parent of a
disconnected subtree) keep being matched against rules, while the
disconnected mountpoints the walker newly visits on a mount crossing
are skipped via VFS_WALK_POS_MOUNTPOINT, as the old loop never
consulted them.

Co-developed-by: Song Liu <song@kernel.org>
Signed-off-by: Song Liu <song@kernel.org>
Reported-by: Al Viro <viro@zeniv.linux.org.uk>
Closes: https://lore.kernel.org/r/20250529231018.GP2023217@ZenIV
Fixes: cb2c7d1a1776 ("landlock: Support filesystem access-control")
Signed-off-by: Justin Suess <utilityemal77@gmail.com>
---
 security/landlock/fs.c | 266 +++++++++++++++++++++--------------------
 1 file changed, 134 insertions(+), 132 deletions(-)

diff --git a/security/landlock/fs.c b/security/landlock/fs.c
index cab43892ec2f..5710ed745d70 100644
--- a/security/landlock/fs.c
+++ b/security/landlock/fs.c
@@ -751,6 +751,108 @@ static void test_is_eacces_with_write(struct kunit *const test)
 #undef IE_TRUE
 #undef IE_FALSE
 
+struct landlock_walk_state {
+	const struct landlock_domain *domain;
+	struct layer_masks *layer_masks_parent1, *layer_masks_parent2;
+	const struct layer_masks *layer_masks_child1, *layer_masks_child2;
+	access_mask_t access_request_parent1, access_request_parent2;
+	access_mask_t access_masked_parent1, access_masked_parent2;
+	bool child1_is_directory, child2_is_directory;
+	bool allowed_parent1, allowed_parent2, is_dom_check;
+};
+
+static int check_access_path_walk(const struct path *const ancestor,
+				  const unsigned int pos_flags,
+				  void *const data)
+{
+	struct landlock_walk_state *const state = data;
+	struct landlock_id id = {
+		.type = LANDLOCK_KEY_INODE,
+	};
+
+	if (unlikely(pos_flags & VFS_WALK_POS_DISCONNECTED)) {
+		if (likely(ancestor->mnt->mnt_flags & MNT_INTERNAL)) {
+			/*
+			 * Stops and allows access when reaching disconnected
+			 * root directories that are part of internal
+			 * filesystems (e.g. nsfs, which is reachable through
+			 * /proc/<pid>/ns/<namespace>).
+			 */
+			state->allowed_parent1 = true;
+			state->allowed_parent2 = true;
+			return VFS_WALK_STOP;
+		}
+		/*
+		 * Mountpoints a mount crossing lands on are hidden under the
+		 * mount covering them, so they are not part of the visible
+		 * path and are never matched against rules.  Other
+		 * disconnected roots are matched below.
+		 */
+		if (pos_flags & VFS_WALK_POS_MOUNTPOINT)
+			return VFS_WALK_CONTINUE;
+	}
+
+	/*
+	 * If at least all accesses allowed on the destination are already
+	 * allowed on the source, respectively if there is at least as much as
+	 * restrictions on the destination than on the source, then we can
+	 * safely refer files from the source to the destination without
+	 * risking a privilege escalation.  This also applies in the case of
+	 * RENAME_EXCHANGE, which implies checks on both direction.  This is
+	 * crucial for standalone multilayered security policies.  Furthermore,
+	 * this helps avoid policy writers to shoot themselves in the foot.
+	 */
+	if (unlikely(state->is_dom_check &&
+		     no_more_access(state->layer_masks_parent1,
+				    state->layer_masks_child1,
+				    state->child1_is_directory,
+				    state->layer_masks_parent2,
+				    state->layer_masks_child2,
+				    state->child2_is_directory))) {
+		/*
+		 * Now, downgrades the remaining checks from domain handled
+		 * accesses to requested accesses.
+		 */
+		state->is_dom_check = false;
+		state->access_masked_parent1 = state->access_request_parent1;
+		state->access_masked_parent2 = state->access_request_parent2;
+
+		state->allowed_parent1 =
+			state->allowed_parent1 ||
+			scope_to_request(state->access_masked_parent1,
+					 state->layer_masks_parent1);
+		state->allowed_parent2 =
+			state->allowed_parent2 ||
+			scope_to_request(state->access_masked_parent2,
+					 state->layer_masks_parent2);
+
+		/* Stops when all accesses are granted. */
+		if (state->allowed_parent1 && state->allowed_parent2)
+			return VFS_WALK_STOP;
+	}
+
+	if (get_inode_id(ancestor->dentry, &id)) {
+		state->allowed_parent1 =
+			state->allowed_parent1 ||
+			unmask_layers_fs(state->domain, id,
+					 state->access_masked_parent1,
+					 state->layer_masks_parent1,
+					 ancestor->dentry);
+		state->allowed_parent2 =
+			state->allowed_parent2 ||
+			unmask_layers_fs(state->domain, id,
+					 state->access_masked_parent2,
+					 state->layer_masks_parent2,
+					 ancestor->dentry);
+	}
+
+	/* Stops when a rule from each layer grants access. */
+	if (state->allowed_parent1 && state->allowed_parent2)
+		return VFS_WALK_STOP;
+
+	return VFS_WALK_CONTINUE;
+}
+
 /**
  * is_access_to_paths_allowed - Check accesses for requests with a common path
  *
@@ -803,16 +905,16 @@ is_access_to_paths_allowed(const struct landlock_domain *const domain,
 			   struct landlock_request *const log_request_parent2,
 			   struct dentry *const dentry_child2)
 {
-	bool allowed_parent1 = false, allowed_parent2 = false, is_dom_check,
-	     child1_is_directory = true, child2_is_directory = true;
-	struct path walker_path;
-	struct landlock_id id = {
-		.type = LANDLOCK_KEY_INODE,
-	};
-	access_mask_t access_masked_parent1, access_masked_parent2;
 	struct layer_masks _layer_masks_child1, _layer_masks_child2;
-	struct layer_masks *layer_masks_child1 = NULL,
-			   *layer_masks_child2 = NULL;
+	struct landlock_walk_state state = {
+		.domain = domain,
+		.layer_masks_parent1 = layer_masks_parent1,
+		.layer_masks_parent2 = layer_masks_parent2,
+		.access_request_parent1 = access_request_parent1,
+		.access_request_parent2 = access_request_parent2,
+		.child1_is_directory = true,
+		.child2_is_directory = true,
+	};
 
 	if (!access_request_parent1 && !access_request_parent2)
 		return true;
@@ -826,37 +928,39 @@ is_access_to_paths_allowed(const struct landlock_domain *const domain,
 	if (WARN_ON_ONCE(!layer_masks_parent1))
 		return false;
 
-	allowed_parent1 = is_layer_masks_allowed(layer_masks_parent1);
+	state.allowed_parent1 = is_layer_masks_allowed(layer_masks_parent1);
 
 	if (unlikely(layer_masks_parent2)) {
 		if (WARN_ON_ONCE(!dentry_child1))
 			return false;
 
-		allowed_parent2 = is_layer_masks_allowed(layer_masks_parent2);
+		state.allowed_parent2 =
+			is_layer_masks_allowed(layer_masks_parent2);
 
 		/*
 		 * For a double request, first check for potential privilege
 		 * escalation by looking at domain handled accesses (which are
 		 * a superset of the meaningful requested accesses).
 		 */
-		access_masked_parent1 = access_masked_parent2 =
+		state.access_masked_parent1 =
 			landlock_union_access_masks(domain).fs;
-		is_dom_check = true;
+		state.access_masked_parent2 = state.access_masked_parent1;
+		state.is_dom_check = true;
 	} else {
 		if (WARN_ON_ONCE(dentry_child1 || dentry_child2))
 			return false;
 		/* For a simple request, only check for requested accesses. */
-		access_masked_parent1 = access_request_parent1;
-		access_masked_parent2 = access_request_parent2;
+		state.access_masked_parent1 = access_request_parent1;
+		state.access_masked_parent2 = access_request_parent2;
 		/*
 		 * Simple requests have no parent2 to check, so parent2 is
 		 * trivially allowed.  This must be set explicitly because the
-		 * get_inode_id() gate in the pathwalk loop may prevent
+		 * get_inode_id() gate in the walk callback may prevent
 		 * landlock_unmask_layers() from being called (which would
 		 * otherwise return true for NULL masks as a side effect).
 		 */
-		allowed_parent2 = true;
-		is_dom_check = false;
+		state.allowed_parent2 = true;
+		state.is_dom_check = false;
 	}
 
 	if (unlikely(dentry_child1)) {
@@ -872,8 +976,8 @@ is_access_to_paths_allowed(const struct landlock_domain *const domain,
 		if (handled && get_inode_id(dentry_child1, &id))
 			unmask_layers_fs(domain, id, handled,
 					 &_layer_masks_child1, dentry_child1);
-		layer_masks_child1 = &_layer_masks_child1;
-		child1_is_directory = d_is_dir(dentry_child1);
+		state.layer_masks_child1 = &_layer_masks_child1;
+		state.child1_is_directory = d_is_dir(dentry_child1);
 	}
 	if (unlikely(dentry_child2)) {
 		struct landlock_id id = {
@@ -888,118 +992,16 @@ is_access_to_paths_allowed(const struct landlock_domain *const domain,
 		if (handled && get_inode_id(dentry_child2, &id))
 			unmask_layers_fs(domain, id, handled,
 					 &_layer_masks_child2, dentry_child2);
-		layer_masks_child2 = &_layer_masks_child2;
-		child2_is_directory = d_is_dir(dentry_child2);
+		state.layer_masks_child2 = &_layer_masks_child2;
+		state.child2_is_directory = d_is_dir(dentry_child2);
 	}
 
-	walker_path = *path;
-	path_get(&walker_path);
 	/*
 	 * We need to walk through all the hierarchy to not miss any relevant
-	 * restriction.
+	 * restriction.  Reaching the real root without a grant from each
+	 * layer denies access.
 	 */
-	while (true) {
-		/*
-		 * If at least all accesses allowed on the destination are
-		 * already allowed on the source, respectively if there is at
-		 * least as much as restrictions on the destination than on the
-		 * source, then we can safely refer files from the source to
-		 * the destination without risking a privilege escalation.
-		 * This also applies in the case of RENAME_EXCHANGE, which
-		 * implies checks on both direction.  This is crucial for
-		 * standalone multilayered security policies.  Furthermore,
-		 * this helps avoid policy writers to shoot themselves in the
-		 * foot.
-		 */
-		if (unlikely(is_dom_check &&
-			     no_more_access(
-				     layer_masks_parent1, layer_masks_child1,
-				     child1_is_directory, layer_masks_parent2,
-				     layer_masks_child2,
-				     child2_is_directory))) {
-			/*
-			 * Now, downgrades the remaining checks from domain
-			 * handled accesses to requested accesses.
-			 */
-			is_dom_check = false;
-			access_masked_parent1 = access_request_parent1;
-			access_masked_parent2 = access_request_parent2;
-
-			allowed_parent1 =
-				allowed_parent1 ||
-				scope_to_request(access_masked_parent1,
-						 layer_masks_parent1);
-			allowed_parent2 =
-				allowed_parent2 ||
-				scope_to_request(access_masked_parent2,
-						 layer_masks_parent2);
-
-			/* Stops when all accesses are granted. */
-			if (allowed_parent1 && allowed_parent2)
-				break;
-		}
-
-		if (get_inode_id(walker_path.dentry, &id)) {
-			allowed_parent1 =
-				allowed_parent1 ||
-				unmask_layers_fs(domain, id,
-						 access_masked_parent1,
-						 layer_masks_parent1,
-						 walker_path.dentry);
-			allowed_parent2 =
-				allowed_parent2 ||
-				unmask_layers_fs(domain, id,
-						 access_masked_parent2,
-						 layer_masks_parent2,
-						 walker_path.dentry);
-		}
-
-		/* Stops when a rule from each layer grants access. */
-		if (allowed_parent1 && allowed_parent2)
-			break;
-
-jump_up:
-		if (walker_path.dentry == walker_path.mnt->mnt_root) {
-			if (follow_up(&walker_path)) {
-				/* Ignores hidden mount points. */
-				goto jump_up;
-			} else {
-				/*
-				 * Stops at the real root.  Denies access
-				 * because not all layers have granted access.
-				 */
-				break;
-			}
-		}
-
-		if (unlikely(IS_ROOT(walker_path.dentry))) {
-			if (likely(walker_path.mnt->mnt_flags & MNT_INTERNAL)) {
-				/*
-				 * Stops and allows access when reaching disconnected root
-				 * directories that are part of internal filesystems (e.g. nsfs,
-				 * which is reachable through /proc/<pid>/ns/<namespace>).
-				 */
-				allowed_parent1 = true;
-				allowed_parent2 = true;
-				break;
-			}
-
-			/*
-			 * We reached a disconnected root directory from a bind mount.
-			 * Let's continue the walk with the mount point we missed.
-			 */
-			dput(walker_path.dentry);
-			walker_path.dentry = walker_path.mnt->mnt_root;
-			dget(walker_path.dentry);
-		} else {
-			struct dentry *const parent_dentry =
-				dget_parent(walker_path.dentry);
-
-			dput(walker_path.dentry);
-			walker_path.dentry = parent_dentry;
-		}
-	}
-	path_put(&walker_path);
+	vfs_walk_ancestors(path, check_access_path_walk, &state, 0);
 
 	/*
 	 * Check CONFIG_SECURITY_LANDLOCK_LOG to enable elision of
@@ -1007,24 +1009,24 @@ is_access_to_paths_allowed(const struct landlock_domain *const domain,
 	 * dead code elimination.
 	 */
 #ifdef CONFIG_SECURITY_LANDLOCK_LOG
-	if (!allowed_parent1 && log_request_parent1) {
+	if (!state.allowed_parent1 && log_request_parent1) {
 		log_request_parent1->type = LANDLOCK_REQUEST_FS_ACCESS;
 		log_request_parent1->audit.type = LSM_AUDIT_DATA_PATH;
 		log_request_parent1->audit.u.path = *path;
-		log_request_parent1->access = access_masked_parent1;
+		log_request_parent1->access = state.access_masked_parent1;
 		log_request_parent1->layer_masks = layer_masks_parent1;
 	}
 
-	if (!allowed_parent2 && log_request_parent2) {
+	if (!state.allowed_parent2 && log_request_parent2) {
 		log_request_parent2->type = LANDLOCK_REQUEST_FS_ACCESS;
 		log_request_parent2->audit.type = LSM_AUDIT_DATA_PATH;
 		log_request_parent2->audit.u.path = *path;
-		log_request_parent2->access = access_masked_parent2;
+		log_request_parent2->access = state.access_masked_parent2;
 		log_request_parent2->layer_masks = layer_masks_parent2;
 	}
 #endif /* CONFIG_SECURITY_LANDLOCK_LOG */
 
-	return allowed_parent1 && allowed_parent2;
+	return state.allowed_parent1 && state.allowed_parent2;
 }
 
 static int current_check_access_path(const struct path *const path,
-- 
2.55.0

[PATCH bpf-next v1 04/11] namei: expose the stepwise ancestor walk to fs/

[Justin Suess]

Make vfs_walk_start(), vfs_walk_next() and vfs_walk_end() non-static
and declare them in fs/internal.h next to the walk state, so an
iterating consumer (BPF) can drive the walk with every step and
invariant staying in namei.c.  vfs_walk_ancestors() and its callback
contract are unchanged.

Signed-off-by: Justin Suess <utilityemal77@gmail.com>
---
 fs/internal.h | 5 +++++
 fs/namei.c    | 8 ++++----
 2 files changed, 9 insertions(+), 4 deletions(-)

diff --git a/fs/internal.h b/fs/internal.h
index bfe62c9bdfc9..3ce2220ff57f 100644
--- a/fs/internal.h
+++ b/fs/internal.h
@@ -81,6 +81,11 @@ struct vfs_ancestor_walk {
 	unsigned int flags;	/* VFS_WALK_* */
 };
 
+void vfs_walk_start(struct vfs_ancestor_walk *aw, const struct path *path,
+		    unsigned int flags);
+int vfs_walk_next(struct vfs_ancestor_walk *aw);
+void vfs_walk_end(struct vfs_ancestor_walk *aw);
+
 void __init filename_init(void);
 
 /*
diff --git a/fs/namei.c b/fs/namei.c
index 6d5b4b214334..d6151fa27844 100644
--- a/fs/namei.c
+++ b/fs/namei.c
@@ -2249,8 +2249,8 @@ static const struct path vfs_walk_no_root;
  * @path: position to walk up from; never modified
  * @flags: %VFS_WALK_* flags; none defined yet, pass 0
  */
-static void vfs_walk_start(struct vfs_ancestor_walk *aw,
-			   const struct path *path, unsigned int flags)
+void vfs_walk_start(struct vfs_ancestor_walk *aw, const struct path *path,
+		    unsigned int flags)
 {
 	if (WARN_ON_ONCE(flags))
 		flags = 0;
@@ -2299,7 +2299,7 @@ static int vfs_walk_step_ref(struct vfs_ancestor_walk *aw)
  * Returns: 0 with @aw->pos valid, 1 once the walk has passed the real
  * root.
  */
-static int vfs_walk_next(struct vfs_ancestor_walk *aw)
+int vfs_walk_next(struct vfs_ancestor_walk *aw)
 {
 	if (aw->flags & VFS_WALK_STARTED) {
 		int err = vfs_walk_step_ref(aw);
@@ -2317,7 +2317,7 @@ static int vfs_walk_next(struct vfs_ancestor_walk *aw)
  * vfs_walk_end - finish a stepwise ancestor walk
  * @aw: the walk; its positions, including @aw->pos, become invalid
  */
-static void vfs_walk_end(struct vfs_ancestor_walk *aw)
+void vfs_walk_end(struct vfs_ancestor_walk *aw)
 {
 	path_put(&aw->pos);
 }
-- 
2.55.0

[PATCH bpf-next v1 05/11] bpf: add a path ancestor iterator

[Justin Suess]

Let BPF programs evaluate a path's ancestry with an open-coded iterator
over the stepwise vfs_walk_ancestors() engine.  The iteration holds a
reference on its current position, which is what lets a program sleep
between positions - a dput() of the last reference may - so the kfuncs
are KF_SLEEPABLE and the iterator is available to sleepable programs
only.

bpf_iter_path_ancestors_next() hands each position to the program as an
acquired reference of its own, to release with bpf_path_put().  The
walk's own reference moves on with the walk and is dropped at the next
step, so it cannot be what keeps a position alive: a program that saves
a position's dentry, or hands one to a sleepable kfunc, needs it to
outlive the step it came from.  struct path is a value type with nothing
a BPF reference could be taken on, so an acquired position is a copy of
its own; the allocation is a sleepable GFP_KERNEL one, and a failure
ends the iteration with %BPF_PATH_ANCESTORS_NOMEM rather than silently
truncating the ancestry.

An acquiring KF_ITER_NEXT needs one thing from the verifier: the state
that assumes the drained, NULL-returning branch must not keep the
reference the acquire bookkeeping created for the assumed non-NULL
return.  Open-coded iterators reach that branch through
process_iter_next_call() rather than through mark_ptr_or_null_regs(),
which is where a plain KF_ACQUIRE | KF_RET_NULL kfunc releases it.

The per-position VFS flags are not derivable from the position alone -
whether a disconnected root is a mountpoint a crossing landed on is
walk state - so they are read with bpf_path_ancestors_pos_flags(),
which a program needs to reproduce Landlock's evaluation of
disconnected positions.

The iterator state is deliberately larger than this walk mode needs:
its size is part of the contract with programs, which size their stack
slot from it, so growing it later would reject programs built against
the smaller one.  The walk mode is a parameter of the shared engine for
the same reason - so that a mode added later is not an ABI change.

Signed-off-by: Justin Suess <utilityemal77@gmail.com>
---
 fs/bpf_fs_kfuncs.c    | 147 ++++++++++++++++++++++++++++++++++++++++++
 kernel/bpf/verifier.c |   7 ++
 2 files changed, 154 insertions(+)

diff --git a/fs/bpf_fs_kfuncs.c b/fs/bpf_fs_kfuncs.c
index 08f0847c4970..02398f5a46d5 100644
--- a/fs/bpf_fs_kfuncs.c
+++ b/fs/bpf_fs_kfuncs.c
@@ -13,9 +13,13 @@
 #include <linux/kernfs.h>
 #include <linux/lsm_hooks.h>
 #include <linux/mm.h>
+#include <linux/namei.h>
 #include <linux/net.h>
+#include <linux/slab.h>
 #include <linux/xattr.h>
 
+#include "internal.h"
+
 __bpf_kfunc_start_defs();
 
 /**
@@ -500,6 +504,143 @@ __bpf_kfunc struct inode *bpf_real_data_inode(struct file *file)
 
 __bpf_kfunc_end_defs();
 
+enum bpf_path_ancestors_flag {
+	/* bpf_path_ancestors_pos_flags() bits */
+	BPF_PATH_ANCESTORS_DISCONNECTED	= (1 << 0),
+	/* the position is a mountpoint a mount crossing landed on */
+	BPF_PATH_ANCESTORS_MOUNTPOINT	= (1 << 1),
+	/* the iteration ended on a failed allocation, not at the root */
+	BPF_PATH_ANCESTORS_NOMEM	= (1 << 2),
+};
+
+/*
+ * Walks over a path's ancestors.
+ *
+ * bpf_iter_path_ancestors runs with references.  Its kfuncs are
+ * sleepable, so the iteration may sleep between positions.
+ *
+ * Each position is handed to the program as an acquired reference of its
+ * own, to release with bpf_path_put().  The walk's own reference moves on
+ * with the walk, so a position that outlives the step it came from - a
+ * dentry saved for later, or the path a sleepable kfunc is still working
+ * on - has to be kept alive by the program's reference rather than by the
+ * iterator's.
+ */
+struct bpf_iter_path_ancestors {
+	__u64 __opaque[5];
+} __aligned(8);
+
+struct bpf_path_ancestors_kern {
+	struct vfs_ancestor_walk aw;
+	int step;	/* last vfs_walk_next() result, or -ENOMEM */
+} __aligned(8);
+
+static int bpf_path_ancestors_new(struct bpf_path_ancestors_kern *kit,
+				  struct path *path, u64 flags,
+				  unsigned int walk_flags)
+{
+	BUILD_BUG_ON(sizeof(struct bpf_path_ancestors_kern) >
+		     sizeof(struct bpf_iter_path_ancestors));
+	BUILD_BUG_ON(__alignof__(struct bpf_path_ancestors_kern) !=
+		     __alignof__(struct bpf_iter_path_ancestors));
+
+	if (flags) {
+		/* A zeroed walk makes destroying the iterator a no-op. */
+		memset(kit, 0, sizeof(*kit));
+		kit->step = 1;
+		return -EINVAL;
+	}
+	kit->step = 0;
+	vfs_walk_start(&kit->aw, path, walk_flags);
+	return 0;
+}
+
+/* The walk's own view of the next position, which the step after it ends. */
+static struct path *bpf_path_ancestors_step(struct bpf_path_ancestors_kern *kit)
+{
+	if (kit->step)
+		return NULL;
+	kit->step = vfs_walk_next(&kit->aw);
+	return kit->step ? NULL : &kit->aw.pos;
+}
+
+static u32 bpf_path_ancestors_flags(const struct bpf_path_ancestors_kern *kit)
+{
+	u32 flags = 0;
+
+	if (kit->step == -ENOMEM)
+		return BPF_PATH_ANCESTORS_NOMEM;
+	if (!kit->step) {
+		if (kit->aw.pos_flags & VFS_WALK_POS_DISCONNECTED)
+			flags |= BPF_PATH_ANCESTORS_DISCONNECTED;
+		if (kit->aw.pos_flags & VFS_WALK_POS_MOUNTPOINT)
+			flags |= BPF_PATH_ANCESTORS_MOUNTPOINT;
+	}
+	return flags;
+}
+
+__bpf_kfunc_start_defs();
+
+__bpf_kfunc int bpf_iter_path_ancestors_new(struct bpf_iter_path_ancestors *it,
+					    struct path *path, u64 flags)
+{
+	return bpf_path_ancestors_new((void *)it, path, flags, 0);
+}
+
+/**
+ * bpf_iter_path_ancestors_next - acquire the walk's next position
+ * @it: the iterator
+ *
+ * Return: the next position with a reference held, to release with
+ * bpf_path_put(), or NULL once the walk has passed the real root - or on
+ * an allocation failure, which ends the iteration and is reported as
+ * %BPF_PATH_ANCESTORS_NOMEM by bpf_path_ancestors_pos_flags().
+ */
+__bpf_kfunc struct path *
+bpf_iter_path_ancestors_next(struct bpf_iter_path_ancestors *it)
+{
+	struct bpf_path_ancestors_kern *kit = (void *)it;
+	struct path *pos = bpf_path_ancestors_step(kit);
+	struct path *held;
+
+	if (!pos)
+		return NULL;
+	/*
+	 * The position must outlive the walk's own view of it, so it gets a
+	 * reference and a struct path of its own to live in: struct path is
+	 * a value type, with nothing a BPF reference could be taken on
+	 * otherwise.  Sleepable, so no atomic allocation.
+	 */
+	held = kmalloc_obj(*held);
+	if (!held) {
+		kit->step = -ENOMEM;
+		return NULL;
+	}
+	*held = *pos;
+	path_get(held);
+	return held;
+}
+
+__bpf_kfunc void
+bpf_iter_path_ancestors_destroy(struct bpf_iter_path_ancestors *it)
+{
+	vfs_walk_end(&((struct bpf_path_ancestors_kern *)it)->aw);
+}
+
+__bpf_kfunc u32
+bpf_path_ancestors_pos_flags(struct bpf_iter_path_ancestors *it__iter)
+{
+	return bpf_path_ancestors_flags((void *)it__iter);
+}
+
+__bpf_kfunc void bpf_path_put(struct path *path)
+{
+	path_put(path);
+	kfree(path);
+}
+
+__bpf_kfunc_end_defs();
+
 BTF_KFUNCS_START(bpf_fs_kfunc_set_ids)
 BTF_ID_FLAGS(func, bpf_get_task_exe_file, KF_ACQUIRE | KF_RET_NULL)
 BTF_ID_FLAGS(func, bpf_put_file, KF_RELEASE)
@@ -513,6 +654,12 @@ BTF_ID_FLAGS(func, bpf_inode_init_xattr)
 #ifdef CONFIG_NET
 BTF_ID_FLAGS(func, bpf_sock_read_xattr, KF_RCU)
 #endif
+BTF_ID_FLAGS(func, bpf_iter_path_ancestors_new, KF_ITER_NEW | KF_SLEEPABLE)
+BTF_ID_FLAGS(func, bpf_iter_path_ancestors_next,
+	     KF_ITER_NEXT | KF_ACQUIRE | KF_RET_NULL | KF_SLEEPABLE)
+BTF_ID_FLAGS(func, bpf_iter_path_ancestors_destroy, KF_ITER_DESTROY | KF_SLEEPABLE)
+BTF_ID_FLAGS(func, bpf_path_ancestors_pos_flags)
+BTF_ID_FLAGS(func, bpf_path_put, KF_RELEASE | KF_SLEEPABLE)
 BTF_KFUNCS_END(bpf_fs_kfunc_set_ids)
 
 /* Side-effecting kfuncs that stay exclusive to LSM programs. */
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 2f190abe3448..4b3e1d4f8a80 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -8835,6 +8835,13 @@ static int process_iter_next_call(struct bpf_verifier_env *env, int insn_idx,
 	/* switch to DRAINED state, but keep the depth unchanged */
 	/* mark current iter state as drained and assume returned NULL */
 	cur_iter->iter.state = BPF_ITER_STATE_DRAINED;
+	/*
+	 * An acquiring iter_next() hands out nothing once drained: the
+	 * acquired reference exists only in the forked active state, not on
+	 * this NULL-returning branch.
+	 */
+	if (meta->kfunc_flags & KF_ACQUIRE)
+		WARN_ON_ONCE(release_reference_nomark(env, cur_fr->regs[BPF_REG_0].id));
 	__mark_reg_const_zero(env, &cur_fr->regs[BPF_REG_0]);
 
 	return 0;
-- 
2.55.0

[PATCH bpf-next v1 06/11] selftests/bpf: exercise the path ancestor iterator

[Justin Suess]

Walk the ancestry of a mkdir's parent directory from a sleepable LSM
program and check that the iteration reaches the root: the temporary
directory, its parent and / are visited, no position comes back
flagged, and the flags read back after the loop show it ended at the
root rather than on a failed allocation.

Hold the first position across the rest of the walk and resolve its
pathname only once the loop is done and the iterator destroyed: the
acquired reference, not the walk's, is then all that keeps the
position alive.

Signed-off-by: Justin Suess <utilityemal77@gmail.com>
---
 .../selftests/bpf/prog_tests/path_ancestors.c | 57 ++++++++++++++
 .../selftests/bpf/progs/path_ancestors.c      | 74 +++++++++++++++++++
 2 files changed, 131 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/path_ancestors.c
 create mode 100644 tools/testing/selftests/bpf/progs/path_ancestors.c

diff --git a/tools/testing/selftests/bpf/prog_tests/path_ancestors.c b/tools/testing/selftests/bpf/prog_tests/path_ancestors.c
new file mode 100644
index 000000000000..d1bd26bce10b
--- /dev/null
+++ b/tools/testing/selftests/bpf/prog_tests/path_ancestors.c
@@ -0,0 +1,57 @@
+// SPDX-License-Identifier: GPL-2.0
+/* Copyright (c) 2026 Justin Suess */
+
+#include <sys/stat.h>
+#include <stdlib.h>
+#include <unistd.h>
+#include <test_progs.h>
+#include "path_ancestors.skel.h"
+
+void test_path_ancestors(void)
+{
+	char base[] = "/tmp/path_ancestors_XXXXXX";
+	struct path_ancestors *skel = NULL;
+	char suba[280], subb[280];
+
+	if (!ASSERT_OK_PTR(mkdtemp(base), "mkdtemp"))
+		return;
+	snprintf(suba, sizeof(suba), "%s/a", base);
+	snprintf(subb, sizeof(subb), "%s/a/b", base);
+	if (!ASSERT_OK(mkdir(suba, 0755), "mkdir_a"))
+		goto out_rm;
+
+	skel = path_ancestors__open_and_load();
+	if (!ASSERT_OK_PTR(skel, "open_and_load"))
+		goto out_rm;
+	skel->bss->monitored_pid = getpid();
+	if (!ASSERT_OK(path_ancestors__attach(skel), "attach"))
+		goto out;
+
+	/* mkdir b: the hook sees dir == suba, whose ancestry is walked. */
+	if (!ASSERT_OK(mkdir(subb, 0755), "mkdir_b"))
+		goto out;
+
+	/* suba, base, /tmp, / at least. */
+	ASSERT_GE(skel->bss->ref_count, 4, "ref_count");
+	ASSERT_EQ(skel->bss->ref_flags, 0, "ref_flags");
+	/*
+	 * The referenced loop ended at the root, not on an allocation
+	 * failure.
+	 */
+	ASSERT_EQ(skel->bss->end_flags, 0, "end_flags");
+
+	/* The acquired second position, used after its step was taken. */
+	ASSERT_STREQ(skel->bss->second_path, base, "second_path");
+	ASSERT_EQ(skel->bss->second_len, strlen(base) + 1, "second_len");
+
+	/* The first position, used only after the walk itself was gone. */
+	ASSERT_STREQ(skel->bss->first_path, suba, "first_path");
+	ASSERT_EQ(skel->bss->first_len, strlen(suba) + 1, "first_len");
+
+out:
+	path_ancestors__destroy(skel);
+out_rm:
+	rmdir(subb);
+	rmdir(suba);
+	rmdir(base);
+}
diff --git a/tools/testing/selftests/bpf/progs/path_ancestors.c b/tools/testing/selftests/bpf/progs/path_ancestors.c
new file mode 100644
index 000000000000..6287f5099a18
--- /dev/null
+++ b/tools/testing/selftests/bpf/progs/path_ancestors.c
@@ -0,0 +1,74 @@
+// SPDX-License-Identifier: GPL-2.0
+/* Copyright (c) 2026 Justin Suess */
+
+#include "vmlinux.h"
+#include <errno.h>
+#include <bpf/bpf_helpers.h>
+#include <bpf/bpf_tracing.h>
+#include "bpf_kfuncs.h"
+
+char _license[] SEC("license") = "GPL";
+
+__u32 monitored_pid;
+
+int ref_count;		/* positions seen by the pure referenced walk */
+int ref_flags;		/* pos flags seen by the referenced walk */
+int end_flags;		/* flags after a referenced loop ended: 0 unless NOMEM */
+int second_len;		/* d_path length of the walk's second position */
+int first_len;		/* d_path length of the first position, after the walk */
+char second_path[256];
+char first_path[256];
+
+static bool monitored(void)
+{
+	return (bpf_get_current_pid_tgid() >> 32) == monitored_pid;
+}
+
+SEC("lsm.s/path_mkdir")
+int BPF_PROG(walk_modes, const struct path *dir, struct dentry *dentry,
+	     umode_t mode)
+{
+	struct bpf_iter_path_ancestors it;
+	struct path *pos, *first = NULL;
+
+	/*
+	 * Keep first's init opaque: gcc-bpf otherwise folds it into a
+	 * preceding loop's exit value, which the verifier cannot track.
+	 */
+	barrier_var(first);
+
+	if (!monitored())
+		return 0;
+
+	/*
+	 * Referenced walk: every position comes acquired, so it stays valid
+	 * past the step that yielded it - the first one is held across the
+	 * rest of the walk and used only once the walk is gone.
+	 */
+	bpf_iter_path_ancestors_new(&it, (struct path *)dir, 0);
+	while ((pos = bpf_iter_path_ancestors_next(&it))) {
+		ref_count++;
+		ref_flags |= bpf_path_ancestors_pos_flags(&it);
+		if (!first) {
+			first = pos;
+			continue;
+		}
+		if (ref_count == 2)
+			second_len = bpf_path_d_path(pos, second_path,
+						     sizeof(second_path));
+		bpf_path_put(pos);
+	}
+	/* NULL from an allocation failure, not the root, surfaces here. */
+	end_flags |= bpf_path_ancestors_pos_flags(&it);
+	bpf_iter_path_ancestors_destroy(&it);
+	/*
+	 * The walk's own references moved on and the iterator is destroyed:
+	 * the acquired reference is all that keeps the first position alive.
+	 */
+	if (first) {
+		first_len = bpf_path_d_path(first, first_path,
+					    sizeof(first_path));
+		bpf_path_put(first);
+	}
+	return 0;
+}
-- 
2.55.0

[PATCH bpf-next v1 07/11] fs: add mnt_undo_legitimize()

[Justin Suess]

A failed __legitimize_mnt() can oblige its caller to mntput() the
mount, which may be the final put and so may sleep: legitimize_mnt()
leaves the RCU read-side critical section it ran under to do it.  A
caller that cannot leave its critical section - a BPF program driving
a lockless walk, which only the verifier ends - needs that put to be
callable from inside it.

Add mnt_undo_legitimize(), which drops the count and, when the count
turns out to be the mount's last, keeps it and hands the mount to
delayed_mntput() for the sleepable final put.  delayed_mntput() then
tells the two queue populations apart by MNT_DOOMED rather than by an
unlocked mnt_get_count() read, which a concurrent failed
__legitimize_mnt() could transiently inflate.  legitimize_mnt()
switches to it as well, retiring its
rcu_read_unlock/mntput/rcu_read_lock dance.

Unlike mntput(), mnt_expiry_mark is left alone: a walker that failed
to legitimize a mount never used it.

Signed-off-by: Justin Suess <utilityemal77@gmail.com>
---
 fs/mount.h     |  1 +
 fs/namespace.c | 65 ++++++++++++++++++++++++++++++++++++++++++++------
 2 files changed, 59 insertions(+), 7 deletions(-)

diff --git a/fs/mount.h b/fs/mount.h
index 94fcc306d21e..e714040f8e8f 100644
--- a/fs/mount.h
+++ b/fs/mount.h
@@ -140,6 +140,7 @@ static inline int is_mounted(struct vfsmount *mnt)
 extern struct mount *__lookup_mnt(struct vfsmount *, struct dentry *);
 
 extern int __legitimize_mnt(struct vfsmount *, unsigned);
+void mnt_undo_legitimize(struct mount *mnt);
 
 static inline bool __path_is_mountpoint(const struct path *path)
 {
diff --git a/fs/namespace.c b/fs/namespace.c
index 580877e46b1a..e37c758b3f39 100644
--- a/fs/namespace.c
+++ b/fs/namespace.c
@@ -767,11 +767,8 @@ static bool legitimize_mnt(struct vfsmount *bastard, unsigned seq)
 	int res = __legitimize_mnt(bastard, seq);
 	if (likely(!res))
 		return true;
-	if (unlikely(res < 0)) {
-		rcu_read_unlock();
-		mntput(bastard);
-		rcu_read_lock();
-	}
+	if (unlikely(res < 0))
+		mnt_undo_legitimize(real_mount(bastard));
 	return false;
 }
 
@@ -1330,8 +1327,19 @@ static void delayed_mntput(struct work_struct *unused)
 	struct llist_node *node = llist_del_all(&delayed_mntput_list);
 	struct mount *m, *t;
 
-	llist_for_each_entry_safe(m, t, node, mnt_llist)
-		cleanup_mnt(m);
+	llist_for_each_entry_safe(m, t, node, mnt_llist) {
+		/*
+		 * MNT_DOOMED is only ever set on the mounts
+		 * mntput_no_expire_slowpath() queues here, never on the
+		 * kept-count ones mnt_undo_legitimize() queues.  Route on it
+		 * rather than on mnt_get_count(), which a concurrent failed
+		 * __legitimize_mnt() can transiently inflate.
+		 */
+		if (m->mnt.mnt_flags & MNT_DOOMED)
+			cleanup_mnt(m);
+		else
+			mntput(&m->mnt);	/* kept by mnt_undo_legitimize() */
+	}
 }
 static DECLARE_DELAYED_WORK(delayed_mntput_work, delayed_mntput);
 
@@ -1423,6 +1431,49 @@ void mntput(struct vfsmount *mnt)
 }
 EXPORT_SYMBOL(mntput);
 
+/**
+ * mnt_undo_legitimize - drop a count __legitimize_mnt() asked us to put
+ * @mnt: the mount __legitimize_mnt() failed on
+ *
+ * Like the mntput() that a failed __legitimize_mnt() normally obliges,
+ * but callable from the RCU read-side critical section the legitimization
+ * ran under: when the count turns out to be the mount's last, it is kept
+ * and the mount handed to delayed_mntput() for the sleepable final put.
+ * Unlike mntput(), mnt_expiry_mark is left alone: a walker that failed
+ * to legitimize the mount never used it.
+ */
+void mnt_undo_legitimize(struct mount *mnt)
+{
+	RCU_LOCKDEP_WARN(!rcu_read_lock_held(),
+			 "mnt_undo_legitimize() outside of RCU read-side critical section");
+	if (likely(READ_ONCE(mnt->mnt_ns))) {
+		/* Not the final count, as in mntput_no_expire(). */
+		mnt_add_count(mnt, -1);
+		return;
+	}
+	lock_mount_hash();
+	/*
+	 * As in mntput_no_expire(): make sure that if a concurrent
+	 * __legitimize_mnt() has not seen us grab mount_lock, we'll see
+	 * its refcount increment here.
+	 */
+	smp_mb();
+	if (likely(mnt_get_count(mnt) > 1)) {
+		mnt_add_count(mnt, -1);
+		unlock_mount_hash();
+		return;
+	}
+	unlock_mount_hash();
+	/*
+	 * Ours is the last count: nothing else can reach the mount any
+	 * more, which makes its mnt_llist ours to use.  delayed_mntput()
+	 * tells our kept-count mount from the doomed ones by MNT_DOOMED.
+	 */
+	WARN_ON_ONCE(mnt->mnt.mnt_flags & MNT_DOOMED);
+	if (llist_add(&mnt->mnt_llist, &delayed_mntput_list))
+		schedule_delayed_work(&delayed_mntput_work, 1);
+}
+
 struct vfsmount *mntget(struct vfsmount *mnt)
 {
 	if (mnt)
-- 
2.55.0

[PATCH bpf-next v1 08/11] namei: add an rcu-walk mode to the ancestor walk

[Justin Suess]

Let the stepwise engine walk lockless, entered with %VFS_WALK_RCU under
the caller's rcu_read_lock: stepping shares follow_dotdot_rcu()'s core,
factored into __path_walk_parent_rcu(), with per-step d_seq validation,
choose_mountpoint_rcu() for crossings and mount_lock revalidation
before concluding at the real root.  Any lost race surfaces as -ECHILD
and the caller retries in the referenced mode.

vfs_walk_handover() continues a lockless walk with references, so that
a caller can do at a position what no lockless walk can.  It mirrors
unlazy_walk(): the position is legitimized and becomes the starting
position of a second, reference-based walk that owns the references
acquired on it.

Both halves of that are ordered so that nothing has to be put: a failed
legitimization leaves no partial references, and the one case where
__legitimize_mnt() obliges a sleepable mntput() goes to
mnt_undo_legitimize().  Handing the reference straight over rather than
copying it out and dropping a second one is what keeps the whole
operation callable inside the caller's RCU read-side critical section,
where even a path_put() that provably cannot sleep is still a dput()
and so still a might_sleep().

Signed-off-by: Justin Suess <utilityemal77@gmail.com>
---
 fs/internal.h         |   7 ++
 fs/namei.c            | 202 ++++++++++++++++++++++++++++++++++++------
 include/linux/namei.h |   3 +
 3 files changed, 183 insertions(+), 29 deletions(-)

diff --git a/fs/internal.h b/fs/internal.h
index 3ce2220ff57f..8a5696157121 100644
--- a/fs/internal.h
+++ b/fs/internal.h
@@ -74,9 +74,14 @@ int lookup_noperm_common(struct qstr *qname, struct dentry *base);
 /*
  * The stepwise engine under vfs_walk_ancestors(); fs-internal so iterating
  * consumers (BPF) can drive it, with the walk invariants staying in namei.c.
+ * In rcu mode (%VFS_WALK_RCU) the caller holds rcu_read_lock() over the
+ * whole walk, no references are held, and vfs_walk_next() returning -ECHILD
+ * invalidates everything derived from the walk.
  */
 struct vfs_ancestor_walk {
 	struct path pos;
+	unsigned int seq;	/* pos.dentry->d_seq sample (rcu mode) */
+	unsigned int m_seq;	/* mount_lock sample (rcu mode) */
 	unsigned int pos_flags;	/* VFS_WALK_POS_* describing pos */
 	unsigned int flags;	/* VFS_WALK_* */
 };
@@ -85,6 +90,8 @@ void vfs_walk_start(struct vfs_ancestor_walk *aw, const struct path *path,
 		    unsigned int flags);
 int vfs_walk_next(struct vfs_ancestor_walk *aw);
 void vfs_walk_end(struct vfs_ancestor_walk *aw);
+bool vfs_walk_handover(struct vfs_ancestor_walk *to,
+		       struct vfs_ancestor_walk *from);
 
 void __init filename_init(void);
 
diff --git a/fs/namei.c b/fs/namei.c
index d6151fa27844..c4083b69c8a8 100644
--- a/fs/namei.c
+++ b/fs/namei.c
@@ -2152,34 +2152,69 @@ static __always_inline const char *step_into(struct nameidata *nd, int flags,
 	return step_into_slowpath(nd, flags, dentry);
 }
 
-static struct dentry *follow_dotdot_rcu(struct nameidata *nd)
+/**
+ * __path_walk_parent_rcu - step towards the parent of the given struct path
+ * @path: position to step up from; updated in place on a mount crossing,
+ *        which is first if @path is the root of a mounted tree.  No
+ *        references are acquired; the callers layer their own bookkeeping
+ *        (path_connected(), nameidata updates, ...) on top
+ * @root: boundary as for choose_mountpoint_rcu(); if zero'ed, walk all the
+ *        way to the global root
+ * @flags: %LOOKUP_NO_XDEV fails a mount crossing with -ECHILD
+ * @m_seq: the walk's mount_lock sample
+ * @seqp: d_seq sample validating @path->dentry; updated to cover the new
+ *        @path->dentry when a mount is crossed
+ * @next_seqp: set to the returned parent's d_seq sample
+ *
+ * Returns: the parent dentry (which is @path->dentry itself if that is a
+ * disconnected root), NULL if @path is in the root with nothing to cross
+ * into, or ERR_PTR(-ECHILD) when a concurrent change was detected.
+ */
+static struct dentry *__path_walk_parent_rcu(struct path *path,
+					     const struct path *root, int flags,
+					     unsigned int m_seq, unsigned int *seqp,
+					     unsigned int *next_seqp)
 {
 	struct dentry *parent, *old;
 
-	if (path_equal(&nd->path, &nd->root))
-		goto in_root;
-	if (unlikely(nd->path.dentry == nd->path.mnt->mnt_root)) {
-		struct path path;
-		unsigned seq;
-		if (!choose_mountpoint_rcu(real_mount(nd->path.mnt),
-					   &nd->root, &path, &seq))
-			goto in_root;
-		if (unlikely(nd->flags & LOOKUP_NO_XDEV))
+	if (unlikely(path->dentry == path->mnt->mnt_root)) {
+		struct path mounted;
+		unsigned int seq;
+
+		if (!choose_mountpoint_rcu(real_mount(path->mnt),
+					   root, &mounted, &seq))
+			return NULL;
+		if (unlikely(flags & LOOKUP_NO_XDEV))
 			return ERR_PTR(-ECHILD);
-		nd->path = path;
-		nd->inode = path.dentry->d_inode;
-		nd->seq = seq;
+		*path = mounted;
+		*seqp = seq;
 		// makes sure that non-RCU pathwalk could reach this state
-		if (read_seqretry(&mount_lock, nd->m_seq))
+		if (read_seqretry(&mount_lock, m_seq))
 			return ERR_PTR(-ECHILD);
 		/* we know that mountpoint was pinned */
 	}
-	old = nd->path.dentry;
+	old = path->dentry;
 	parent = old->d_parent;
-	nd->next_seq = read_seqcount_begin(&parent->d_seq);
+	*next_seqp = read_seqcount_begin(&parent->d_seq);
 	// makes sure that non-RCU pathwalk could reach this state
-	if (read_seqcount_retry(&old->d_seq, nd->seq))
+	if (read_seqcount_retry(&old->d_seq, *seqp))
 		return ERR_PTR(-ECHILD);
+	return parent;
+}
+
+static struct dentry *follow_dotdot_rcu(struct nameidata *nd)
+{
+	struct dentry *parent;
+
+	if (path_equal(&nd->path, &nd->root))
+		goto in_root;
+	parent = __path_walk_parent_rcu(&nd->path, &nd->root, nd->flags,
+					nd->m_seq, &nd->seq, &nd->next_seq);
+	if (!parent)
+		goto in_root;
+	if (IS_ERR(parent))
+		return parent;
+	nd->inode = nd->path.dentry->d_inode;
 	if (unlikely(!path_connected(nd->path.mnt, parent)))
 		return ERR_PTR(-ECHILD);
 	return parent;
@@ -2247,17 +2282,26 @@ static const struct path vfs_walk_no_root;
  * vfs_walk_start - begin a stepwise ancestor walk
  * @aw: walk state, valid until vfs_walk_end()
  * @path: position to walk up from; never modified
- * @flags: %VFS_WALK_* flags; none defined yet, pass 0
+ * @flags: %VFS_WALK_RCU to walk lockless; the caller then holds
+ *         rcu_read_lock() from before vfs_walk_start() until after
+ *         vfs_walk_end(), and owns no references on yielded positions.
  */
 void vfs_walk_start(struct vfs_ancestor_walk *aw, const struct path *path,
 		    unsigned int flags)
 {
-	if (WARN_ON_ONCE(flags))
-		flags = 0;
+	if (WARN_ON_ONCE(flags & ~VFS_WALK_RCU))
+		flags &= VFS_WALK_RCU;
 	aw->pos = *path;
 	aw->flags = flags;
 	aw->pos_flags = 0;
-	path_get(&aw->pos);
+	if (flags & VFS_WALK_RCU) {
+		RCU_LOCKDEP_WARN(!rcu_read_lock_held(),
+				 "rcu-mode ancestor walk outside of RCU read-side critical section");
+		aw->m_seq = read_seqbegin(&mount_lock);
+		aw->seq = raw_seqcount_begin(&aw->pos.dentry->d_seq);
+	} else {
+		path_get(&aw->pos);
+	}
 }
 
 static int vfs_walk_step_ref(struct vfs_ancestor_walk *aw)
@@ -2288,6 +2332,35 @@ static int vfs_walk_step_ref(struct vfs_ancestor_walk *aw)
 	return 0;
 }
 
+static int vfs_walk_step_rcu(struct vfs_ancestor_walk *aw)
+{
+	struct dentry *parent;
+	unsigned int next_seq;
+
+	if (unlikely(aw->pos_flags & VFS_WALK_POS_DISCONNECTED)) {
+		/* Resume at the root of the disconnected position's mount. */
+		aw->pos.dentry = aw->pos.mnt->mnt_root;
+		aw->seq = raw_seqcount_begin(&aw->pos.dentry->d_seq);
+		aw->pos_flags = 0;
+		return read_seqretry(&mount_lock, aw->m_seq) ? -ECHILD : 0;
+	}
+
+	parent = __path_walk_parent_rcu(&aw->pos, &vfs_walk_no_root, 0,
+					aw->m_seq, &aw->seq, &next_seq);
+	if (!parent)
+		/* The real root, unless the mount tree moved. */
+		return read_seqretry(&mount_lock, aw->m_seq) ? -ECHILD : 1;
+	if (IS_ERR(parent))
+		return PTR_ERR(parent);
+	/* A crossing onto a disconnected root, as in vfs_walk_step_ref(). */
+	aw->pos_flags = parent == aw->pos.dentry ?
+		VFS_WALK_POS_DISCONNECTED | VFS_WALK_POS_MOUNTPOINT :
+		vfs_walk_pos_flags(aw->pos.mnt, parent);
+	aw->pos.dentry = parent;
+	aw->seq = next_seq;
+	return 0;
+}
+
 /**
  * vfs_walk_next - yield the walk's next position in @aw->pos
  * @aw: the walk
@@ -2297,12 +2370,14 @@ static int vfs_walk_step_ref(struct vfs_ancestor_walk *aw)
  * described at vfs_walk_ancestors().
  *
  * Returns: 0 with @aw->pos valid, 1 once the walk has passed the real
- * root.
+ * root, -ECHILD when an rcu-mode walk lost a race and must be retried
+ * (typically in the referenced mode).
  */
 int vfs_walk_next(struct vfs_ancestor_walk *aw)
 {
 	if (aw->flags & VFS_WALK_STARTED) {
-		int err = vfs_walk_step_ref(aw);
+		int err = (aw->flags & VFS_WALK_RCU) ?
+			vfs_walk_step_rcu(aw) : vfs_walk_step_ref(aw);
 
 		if (err)
 			return err;
@@ -2310,6 +2385,10 @@ int vfs_walk_next(struct vfs_ancestor_walk *aw)
 		aw->flags |= VFS_WALK_STARTED;
 		aw->pos_flags |= vfs_walk_pos_flags(aw->pos.mnt, aw->pos.dentry);
 	}
+	/* The flags must describe the dentry the seq covers. */
+	if ((aw->flags & VFS_WALK_RCU) &&
+	    read_seqcount_retry(&aw->pos.dentry->d_seq, aw->seq))
+		return -ECHILD;
 	return 0;
 }
 
@@ -2319,7 +2398,59 @@ int vfs_walk_next(struct vfs_ancestor_walk *aw)
  */
 void vfs_walk_end(struct vfs_ancestor_walk *aw)
 {
-	path_put(&aw->pos);
+	if (!(aw->flags & VFS_WALK_RCU))
+		path_put(&aw->pos);
+}
+
+/**
+ * vfs_walk_handover - continue an rcu-mode walk with references
+ * @to: walk state to begin at @from's current position, owning the
+ *      references acquired on it; valid until vfs_walk_end() either way
+ * @from: an rcu-mode walk, positioned by a 0 return from vfs_walk_next()
+ *
+ * Mirrors unlazy_walk(): @from's current position is legitimized and
+ * becomes the starting position of the referenced walk @to, which the
+ * first vfs_walk_next() on it yields.  A failed legitimization leaves no
+ * partial references behind and a successful one moves straight into @to,
+ * so nothing is ever put here and the handover is safe within the caller's
+ * RCU read-side critical section - where a path_put() would not be, dput()
+ * being allowed to sleep.  @to itself is only usable once the caller has
+ * left it, its walk being reference-based.
+ *
+ * @from is untouched on success and may keep stepping, lockless, from
+ * where it stands.  The references do not conclude its walk: a concurrent
+ * rename may relocate the position the instant they are taken, as it may
+ * during any reference-based walk.
+ *
+ * Returns: false iff @from lost a race; it is then dead, as after -ECHILD
+ * from vfs_walk_next(), and @to is zeroed - safe to vfs_walk_end(), but
+ * not to step, so the caller has to remember it never started.
+ */
+bool vfs_walk_handover(struct vfs_ancestor_walk *to,
+		       struct vfs_ancestor_walk *from)
+{
+	struct path pos = from->pos;
+	int err;
+
+	err = __legitimize_mnt(pos.mnt, from->m_seq);
+	if (unlikely(err)) {
+		if (err < 0)
+			mnt_undo_legitimize(real_mount(pos.mnt));
+		goto dead;
+	}
+	if (unlikely(read_seqcount_retry(&pos.dentry->d_seq, from->seq) ||
+		     !lockref_get_not_dead(&pos.dentry->d_lockref))) {
+		mnt_undo_legitimize(real_mount(pos.mnt));
+		goto dead;
+	}
+	to->pos = pos;
+	to->flags = 0;
+	to->pos_flags = from->pos_flags;
+	return true;
+
+dead:
+	memset(to, 0, sizeof(*to));
+	return false;
 }
 
 /**
@@ -2328,18 +2459,27 @@ void vfs_walk_end(struct vfs_ancestor_walk *aw)
  * @cb: callback invoked on @path, then on each ancestor up to the real
  *      root, crossing mount boundaries.  @cb must not sleep and returns
  *      %VFS_WALK_CONTINUE, %VFS_WALK_STOP or a negative errno to abort the
- *      walk.  @ancestor is only valid during the invocation; @cb must take
- *      its own references to keep a position.
+ *      walk; -ECHILD is reserved (see below).  @ancestor is only valid
+ *      during the invocation; @cb must take its own references to keep a
+ *      position.
  *      A position whose dentry is a disconnected root is flagged with
  *      %VFS_WALK_POS_DISCONNECTED (plus %VFS_WALK_POS_MOUNTPOINT when it
  *      is a mountpoint a mount crossing landed on rather than a parent);
  *      if @cb continues over it, the walk resumes at the root of that
  *      position's mount.
+ *      With %VFS_WALK_RCU, @cb accepts positions the walk holds no
+ *      references on: the walk then runs lockless (under rcu_read_lock)
+ *      and returns -ECHILD when it loses a race, or when @cb returns
+ *      -ECHILD.  The caller should then discard any state @cb accumulated
+ *      and retry without %VFS_WALK_RCU.  Positions are seq-validated when
+ *      yielded; what @cb reads from one races with concurrent changes
+ *      just as in a referenced walk.
  * @data: opaque argument passed to @cb
- * @flags: %VFS_WALK_* flags; none defined yet, pass 0
+ * @flags: %VFS_WALK_RCU if @cb copes with unreferenced positions
  *
- * Returns: 0 once the real root was reached, 1 if @cb stopped the walk, or
- * the negative errno @cb aborted with.
+ * Returns: 0 once the real root was reached, 1 if @cb stopped the walk,
+ * -ECHILD if a lockless walk must be retried with references, or the
+ * negative errno @cb aborted with.
  */
 int vfs_walk_ancestors(const struct path *path,
 		       int (*cb)(const struct path *ancestor,
@@ -2349,6 +2489,8 @@ int vfs_walk_ancestors(const struct path *path,
 	struct vfs_ancestor_walk aw;
 	int ret;
 
+	if (flags & VFS_WALK_RCU)
+		rcu_read_lock();
 	vfs_walk_start(&aw, path, flags);
 	for (;;) {
 		ret = vfs_walk_next(&aw);
@@ -2366,6 +2508,8 @@ int vfs_walk_ancestors(const struct path *path,
 		}
 	}
 	vfs_walk_end(&aw);
+	if (flags & VFS_WALK_RCU)
+		rcu_read_unlock();
 	return ret;
 }
 
diff --git a/include/linux/namei.h b/include/linux/namei.h
index 3e198de7a0d3..8820a2833213 100644
--- a/include/linux/namei.h
+++ b/include/linux/namei.h
@@ -162,6 +162,9 @@ extern int follow_down_one(struct path *);
 extern int follow_down(struct path *path, unsigned int flags);
 extern int follow_up(struct path *);
 
+/* vfs_walk_ancestors() flags */
+#define VFS_WALK_RCU			BIT(0)
+
 /* per-position flags passed to the vfs_walk_ancestors() callback */
 #define VFS_WALK_POS_DISCONNECTED	BIT(0)
 /* the position is a mountpoint landed on by a mount crossing */
-- 
2.55.0

[PATCH bpf-next v1 09/11] bpf: support "__uninit" iterator arguments in generic kfuncs

[Justin Suess]

Iterator constructors are recognised by their KF_ITER_NEW flag, which
binds them to the bpf_iter_<type>_new() name and so to a single
constructor per type.  A kfunc that initializes an iterator from inputs
that naming convention cannot express - e.g. another, already
initialized iterator - therefore cannot be a constructor.

Let such a kfunc mark its destination argument with the "__uninit"
suffix already used for dynptr out-arguments: process_iter_arg() now
decides per argument, rather than per kfunc, whether it initializes the
iterator or operates on an initialized one.  Only iterator-typed
arguments are reclassified, so dynptr "__uninit" out-arguments are
unaffected.

The first user is the path ancestor iterator handover added by the next
patch.

Signed-off-by: Justin Suess <utilityemal77@gmail.com>
---
 kernel/bpf/verifier.c | 37 ++++++++++++++++++++++++++++++++++---
 1 file changed, 34 insertions(+), 3 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 4b3e1d4f8a80..062273f68dd0 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -8499,6 +8499,24 @@ static bool is_iter_destroy_kfunc(struct bpf_call_arg_meta *meta)
 	return meta->kfunc_flags & KF_ITER_DESTROY;
 }
 
+/*
+ * An "__uninit"-suffixed iterator argument of a kfunc that is not itself an
+ * iterator method: the kfunc initializes that iterator state, as a
+ * bpf_iter_<type>_new() does, but from inputs the constructor naming
+ * convention cannot express - e.g. another, already-initialized iterator.
+ * Only iterator-typed arguments qualify, so "__uninit" dynptr out-arguments
+ * are not reclassified.
+ */
+static bool is_kfunc_arg_iter_init(struct bpf_call_arg_meta *meta, int arg_idx,
+				   const struct btf_param *arg)
+{
+	if (is_iter_kfunc(meta))
+		return false;
+
+	return btf_param_match_suffix(meta->btf, arg, "__uninit") &&
+	       btf_check_iter_arg(meta->btf, meta->func_proto, arg_idx) >= 0;
+}
+
 static bool is_kfunc_arg_iter(struct bpf_call_arg_meta *meta, int arg_idx,
 			      const struct btf_param *arg)
 {
@@ -8509,7 +8527,11 @@ static bool is_kfunc_arg_iter(struct bpf_call_arg_meta *meta, int arg_idx,
 		return arg_idx == 0;
 
 	/* iter passed as an argument to a generic kfunc */
-	return btf_param_match_suffix(meta->btf, arg, "__iter");
+	if (btf_param_match_suffix(meta->btf, arg, "__iter"))
+		return true;
+
+	/* iter state a generic kfunc initializes */
+	return is_kfunc_arg_iter_init(meta, arg_idx, arg);
 }
 
 static int process_iter_arg(struct bpf_verifier_env *env, struct bpf_reg_state *reg,
@@ -8519,6 +8541,7 @@ static int process_iter_arg(struct bpf_verifier_env *env, struct bpf_reg_state *
 	struct bpf_func_state *state = bpf_func(env, reg);
 	const struct btf_type *t;
 	int spi, err, i, nr_slots, btf_id;
+	bool init;
 
 	if (reg->type != PTR_TO_STACK) {
 		verbose(env, "%s expected pointer to an iterator on stack\n",
@@ -8550,8 +8573,16 @@ static int process_iter_arg(struct bpf_verifier_env *env, struct bpf_reg_state *
 	t = btf_type_by_id(meta->btf, btf_id);
 	nr_slots = t->size / BPF_REG_SIZE;
 
-	if (is_iter_new_kfunc(meta)) {
-		/* bpf_iter_<type>_new() expects pointer to uninit iter state */
+	/*
+	 * Whether this argument is the iterator the call initializes, rather
+	 * than an initialized one it operates on.
+	 */
+	init = is_iter_new_kfunc(meta) ||
+	       is_kfunc_arg_iter_init(meta, arg,
+				      &btf_params(meta->func_proto)[arg]);
+
+	if (init) {
+		/* expects a pointer to uninit iter state */
 		if (!is_iter_reg_valid_uninit(env, reg, nr_slots)) {
 			verbose(env, "expected uninitialized iter_%s as %s\n",
 				iter_type_str(meta->btf, btf_id), reg_arg_name(env, argno));
-- 
2.55.0

[PATCH bpf-next v1 10/11] bpf: add a lockless path ancestor iterator

[Justin Suess]

Add a second variant of the ancestor iterator that drives the walk's
rcu mode: bpf_iter_path_ancestors_rcu is KF_RCU_PROTECTED, so the whole
iteration sits in one RCU read-side critical section - implicit in
non-sleepable programs, bpf_rcu_read_lock() in sleepable ones - within
which the verifier already rejects everything sleepable.  This is what
makes a path-based policy expressible from the non-sleepable LSM hooks,
and it drops the per-position reference traffic for the sleepable ones.

Positions come borrowed rather than acquired here: a lockless iteration
holds no reference to pass on, so bpf_iter_path_ancestors_rcu_next()
hands out the walk's own position, valid until the next step.  That is
what RCU protection buys and all it buys: the dentry cannot be freed
under the iteration, but nothing read out of the position may be passed
to a kfunc demanding a trusted argument.

A lockless iteration that loses a race ends with
BPF_PATH_ANCESTORS_RETRY readable through
bpf_path_ancestors_rcu_pos_flags(); the program discards what it
derived from the walk and retries on the referenced variant, so one
lockless attempt bounds the retries.

Escalation mirrors unlazy_walk(): bpf_path_ancestors_legitimize()
acquires the lockless iteration's current position straight into a
referenced iterator the program declared on its stack.  Nothing is
allocated, so nothing can fail for want of memory inside the RCU
read-side critical section, and the escalated position needs no
lifetime of its own: it is the resumed iteration's first position, held
by its reference, yielded by a bpf_iter_path_ancestors_next() that is
sleepable and so necessarily runs after the program has left the
critical section.  That ordering is the whole discipline, and the
verifier enforces it without being told to.

The handover cannot be an iterator constructor - KF_ITER_NEW binds a
type to a single bpf_iter_<type>_new() - so its destination argument is
one of the previous patch's "__uninit" iterator arguments.  Nothing
else is needed: the source argument's ordinary "__iter" classification
already rejects a handover from an iterator whose RCU read-side
critical section has ended.

Signed-off-by: Justin Suess <utilityemal77@gmail.com>
---
 fs/bpf_fs_kfuncs.c | 105 ++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 103 insertions(+), 2 deletions(-)

diff --git a/fs/bpf_fs_kfuncs.c b/fs/bpf_fs_kfuncs.c
index 02398f5a46d5..b4bcdcf13ce0 100644
--- a/fs/bpf_fs_kfuncs.c
+++ b/fs/bpf_fs_kfuncs.c
@@ -505,16 +505,19 @@ __bpf_kfunc struct inode *bpf_real_data_inode(struct file *file)
 __bpf_kfunc_end_defs();
 
 enum bpf_path_ancestors_flag {
-	/* bpf_path_ancestors_pos_flags() bits */
+	/* bpf_path_ancestors[_rcu]_pos_flags() bits */
 	BPF_PATH_ANCESTORS_DISCONNECTED	= (1 << 0),
 	/* the position is a mountpoint a mount crossing landed on */
 	BPF_PATH_ANCESTORS_MOUNTPOINT	= (1 << 1),
 	/* the iteration ended on a failed allocation, not at the root */
 	BPF_PATH_ANCESTORS_NOMEM	= (1 << 2),
+	/* the lockless iteration lost a race and reached no conclusion */
+	BPF_PATH_ANCESTORS_RETRY	= (1 << 3),
 };
 
 /*
- * Walks over a path's ancestors.
+ * Walks over a path's ancestors, in two variants differing in how
+ * positions are kept alive:
  *
  * bpf_iter_path_ancestors runs with references.  Its kfuncs are
  * sleepable, so the iteration may sleep between positions.
@@ -525,11 +528,25 @@ enum bpf_path_ancestors_flag {
  * dentry saved for later, or the path a sleepable kfunc is still working
  * on - has to be kept alive by the program's reference rather than by the
  * iterator's.
+ *
+ * bpf_iter_path_ancestors_rcu runs lockless over one RCU read-side
+ * critical section, which the verifier enforces around the whole
+ * iteration and within which sleeping is impossible.  Its positions are
+ * borrowed, not acquired: they are only valid until the next step, and
+ * nothing derived from one may be passed to a kfunc demanding a trusted
+ * argument.  A lost race ends the iteration with
+ * BPF_PATH_ANCESTORS_RETRY set; the program discards what it derived
+ * from the walk and retries, typically on the referenced variant, or
+ * escalates mid-walk with bpf_path_ancestors_legitimize().
  */
 struct bpf_iter_path_ancestors {
 	__u64 __opaque[5];
 } __aligned(8);
 
+struct bpf_iter_path_ancestors_rcu {
+	__u64 __opaque[5];
+} __aligned(8);
+
 struct bpf_path_ancestors_kern {
 	struct vfs_ancestor_walk aw;
 	int step;	/* last vfs_walk_next() result, or -ENOMEM */
@@ -543,6 +560,10 @@ static int bpf_path_ancestors_new(struct bpf_path_ancestors_kern *kit,
 		     sizeof(struct bpf_iter_path_ancestors));
 	BUILD_BUG_ON(__alignof__(struct bpf_path_ancestors_kern) !=
 		     __alignof__(struct bpf_iter_path_ancestors));
+	BUILD_BUG_ON(sizeof(struct bpf_iter_path_ancestors) !=
+		     sizeof(struct bpf_iter_path_ancestors_rcu));
+	BUILD_BUG_ON(__alignof__(struct bpf_iter_path_ancestors) !=
+		     __alignof__(struct bpf_iter_path_ancestors_rcu));
 
 	if (flags) {
 		/* A zeroed walk makes destroying the iterator a no-op. */
@@ -570,6 +591,8 @@ static u32 bpf_path_ancestors_flags(const struct bpf_path_ancestors_kern *kit)
 
 	if (kit->step == -ENOMEM)
 		return BPF_PATH_ANCESTORS_NOMEM;
+	if (kit->step == -ECHILD)
+		return BPF_PATH_ANCESTORS_RETRY;
 	if (!kit->step) {
 		if (kit->aw.pos_flags & VFS_WALK_POS_DISCONNECTED)
 			flags |= BPF_PATH_ANCESTORS_DISCONNECTED;
@@ -633,6 +656,79 @@ bpf_path_ancestors_pos_flags(struct bpf_iter_path_ancestors *it__iter)
 	return bpf_path_ancestors_flags((void *)it__iter);
 }
 
+__bpf_kfunc int
+bpf_iter_path_ancestors_rcu_new(struct bpf_iter_path_ancestors_rcu *it,
+				struct path *path, u64 flags)
+{
+	return bpf_path_ancestors_new((void *)it, path, flags, VFS_WALK_RCU);
+}
+
+/*
+ * Unlike the referenced variant, this hands out the walk's own position:
+ * a lockless iteration holds no references to pass on, and the verifier
+ * keeps the whole of it inside one RCU read-side critical section.
+ */
+__bpf_kfunc struct path *
+bpf_iter_path_ancestors_rcu_next(struct bpf_iter_path_ancestors_rcu *it)
+{
+	return bpf_path_ancestors_step((void *)it);
+}
+
+__bpf_kfunc void
+bpf_iter_path_ancestors_rcu_destroy(struct bpf_iter_path_ancestors_rcu *it)
+{
+	vfs_walk_end(&((struct bpf_path_ancestors_kern *)it)->aw);
+}
+
+__bpf_kfunc u32
+bpf_path_ancestors_rcu_pos_flags(struct bpf_iter_path_ancestors_rcu *it__iter)
+{
+	return bpf_path_ancestors_flags((void *)it__iter);
+}
+
+/**
+ * bpf_path_ancestors_legitimize - hand a lockless iteration over to references
+ * @it__uninit: referenced ancestor iterator to begin at @rcu_it__iter's
+ *              current position; destroy it with
+ *              bpf_iter_path_ancestors_destroy() whether this succeeds or not
+ * @rcu_it__iter: lockless ancestor iterator, on the position to escalate at
+ *
+ * Mirrors unlazy_walk(): acquires the lockless iteration's current position
+ * and leaves @it__uninit ready to continue from it with references, which
+ * its first bpf_iter_path_ancestors_next() then yields - necessarily after
+ * the program has left its RCU read-side critical section, since that kfunc
+ * is sleepable.  Sleepable work on the escalated position therefore happens
+ * on the iteration's own reference, and nothing is allocated here.
+ *
+ * Return: 0; -%ENOENT if the lockless iteration was drained (the resumed
+ * walk then yields no position, pos_flags 0); -%ECHILD on a lost race,
+ * flagged %BPF_PATH_ANCESTORS_RETRY on both iterators.  @it__uninit is
+ * initialized either way, so a program need not branch on the result.
+ */
+__bpf_kfunc int
+bpf_path_ancestors_legitimize(struct bpf_iter_path_ancestors *it__uninit,
+			      struct bpf_iter_path_ancestors_rcu *rcu_it__iter)
+{
+	struct bpf_path_ancestors_kern *rcu_kit = (void *)rcu_it__iter;
+	struct bpf_path_ancestors_kern *kit = (void *)it__uninit;
+
+	/* A zeroed walk makes destroying the iterator a no-op. */
+	memset(kit, 0, sizeof(*kit));
+
+	/* Drained: nothing to hand over. */
+	if (rcu_kit->step == 1) {
+		kit->step = 1;
+		return -ENOENT;
+	}
+	/* A lost race carries over: the resumed iterator reports RETRY. */
+	if (rcu_kit->step || !vfs_walk_handover(&kit->aw, &rcu_kit->aw)) {
+		rcu_kit->step = -ECHILD;
+		kit->step = -ECHILD;
+		return -ECHILD;
+	}
+	return 0;
+}
+
 __bpf_kfunc void bpf_path_put(struct path *path)
 {
 	path_put(path);
@@ -659,6 +755,11 @@ BTF_ID_FLAGS(func, bpf_iter_path_ancestors_next,
 	     KF_ITER_NEXT | KF_ACQUIRE | KF_RET_NULL | KF_SLEEPABLE)
 BTF_ID_FLAGS(func, bpf_iter_path_ancestors_destroy, KF_ITER_DESTROY | KF_SLEEPABLE)
 BTF_ID_FLAGS(func, bpf_path_ancestors_pos_flags)
+BTF_ID_FLAGS(func, bpf_iter_path_ancestors_rcu_new, KF_ITER_NEW | KF_RCU_PROTECTED)
+BTF_ID_FLAGS(func, bpf_iter_path_ancestors_rcu_next, KF_ITER_NEXT | KF_RET_NULL)
+BTF_ID_FLAGS(func, bpf_iter_path_ancestors_rcu_destroy, KF_ITER_DESTROY)
+BTF_ID_FLAGS(func, bpf_path_ancestors_rcu_pos_flags)
+BTF_ID_FLAGS(func, bpf_path_ancestors_legitimize)
 BTF_ID_FLAGS(func, bpf_path_put, KF_RELEASE | KF_SLEEPABLE)
 BTF_KFUNCS_END(bpf_fs_kfunc_set_ids)
 
-- 
2.55.0

[PATCH bpf-next v1 11/11] selftests/bpf: exercise the lockless path ancestor iterator

[Justin Suess]

Walk the same ancestry four ways and require the position counts to
agree: lockless from a non-sleepable program, where the RCU critical
section is implicit; lockless under an explicit bpf_rcu_read_lock();
referenced; and the hybrid that walks lockless to the second position,
hands it over to a referenced iteration, and resumes there - the
escalated position therefore being walked twice, once per mode.

The sleepable work the escalation exists for (d_path on the escalated
position) runs on the resumed iteration's first position, after
bpf_rcu_read_unlock(), which is the only place a sleepable kfunc can
run at all.

Signed-off-by: Justin Suess <utilityemal77@gmail.com>
---
 .../selftests/bpf/prog_tests/path_ancestors.c | 45 +++++++++--
 .../selftests/bpf/progs/path_ancestors.c      | 78 ++++++++++++++++++-
 2 files changed, 112 insertions(+), 11 deletions(-)

diff --git a/tools/testing/selftests/bpf/prog_tests/path_ancestors.c b/tools/testing/selftests/bpf/prog_tests/path_ancestors.c
index d1bd26bce10b..c324090588dd 100644
--- a/tools/testing/selftests/bpf/prog_tests/path_ancestors.c
+++ b/tools/testing/selftests/bpf/prog_tests/path_ancestors.c
@@ -12,30 +12,56 @@ void test_path_ancestors(void)
 	char base[] = "/tmp/path_ancestors_XXXXXX";
 	struct path_ancestors *skel = NULL;
 	char suba[280], subb[280];
+	int attempt;
 
 	if (!ASSERT_OK_PTR(mkdtemp(base), "mkdtemp"))
 		return;
 	snprintf(suba, sizeof(suba), "%s/a", base);
-	snprintf(subb, sizeof(subb), "%s/a/b", base);
 	if (!ASSERT_OK(mkdir(suba, 0755), "mkdir_a"))
 		goto out_rm;
 
 	skel = path_ancestors__open_and_load();
 	if (!ASSERT_OK_PTR(skel, "open_and_load"))
 		goto out_rm;
-	skel->bss->monitored_pid = getpid();
 	if (!ASSERT_OK(path_ancestors__attach(skel), "attach"))
 		goto out;
 
-	/* mkdir b: the hook sees dir == suba, whose ancestry is walked. */
-	if (!ASSERT_OK(mkdir(subb, 0755), "mkdir_b"))
+	/*
+	 * A mount anywhere in the system during the walk legitimately ends
+	 * the lockless iterations with RETRY and no conclusion: retrigger
+	 * until a quiet window.  mkdir b: the hook sees dir == suba, whose
+	 * ancestry is walked.
+	 */
+	for (attempt = 0; attempt < 5; attempt++) {
+		memset(skel->bss, 0, sizeof(*skel->bss));
+		skel->bss->monitored_pid = getpid();
+
+		snprintf(subb, sizeof(subb), "%s/a/b%d", base, attempt);
+		if (!ASSERT_OK(mkdir(subb, 0755), "mkdir_b"))
+			goto out;
+		rmdir(subb);
+		if (!skel->bss->retry_flags && !skel->bss->escalate_err)
+			break;
+	}
+	if (!ASSERT_LT(attempt, 5, "retried_out"))
 		goto out;
 
-	/* suba, base, /tmp, / at least. */
-	ASSERT_GE(skel->bss->ref_count, 4, "ref_count");
+	ASSERT_EQ(skel->bss->escalate_err, 0, "escalate_err");
+	/* suba, base, /tmp, / at least; equality across modes is the point. */
+	ASSERT_GE(skel->bss->rcu_count, 4, "rcu_count");
+	ASSERT_EQ(skel->bss->ref_count, skel->bss->rcu_count, "ref_vs_rcu");
+	ASSERT_EQ(skel->bss->rcu_ns_count, skel->bss->rcu_count,
+		  "nonsleepable_vs_rcu");
+	/*
+	 * The escalated position is walked twice: once lockless, then again
+	 * as the resumed referenced iteration's first position.
+	 */
+	ASSERT_EQ(skel->bss->hybrid_count, skel->bss->rcu_count + 1,
+		  "hybrid_vs_rcu");
+	ASSERT_EQ(skel->bss->retry_flags, 0, "no_retry");
 	ASSERT_EQ(skel->bss->ref_flags, 0, "ref_flags");
 	/*
-	 * The referenced loop ended at the root, not on an allocation
+	 * The referenced loops ended at the root, not on an allocation
 	 * failure.
 	 */
 	ASSERT_EQ(skel->bss->end_flags, 0, "end_flags");
@@ -48,10 +74,13 @@ void test_path_ancestors(void)
 	ASSERT_STREQ(skel->bss->first_path, suba, "first_path");
 	ASSERT_EQ(skel->bss->first_len, strlen(suba) + 1, "first_len");
 
+	/* The escalated position is the walk's second one: base. */
+	ASSERT_STREQ(skel->bss->escalated_path, base, "escalated_path");
+	ASSERT_EQ(skel->bss->escalated_len, strlen(base) + 1, "escalated_len");
+
 out:
 	path_ancestors__destroy(skel);
 out_rm:
-	rmdir(subb);
 	rmdir(suba);
 	rmdir(base);
 }
diff --git a/tools/testing/selftests/bpf/progs/path_ancestors.c b/tools/testing/selftests/bpf/progs/path_ancestors.c
index 6287f5099a18..3ebf86b23199 100644
--- a/tools/testing/selftests/bpf/progs/path_ancestors.c
+++ b/tools/testing/selftests/bpf/progs/path_ancestors.c
@@ -11,23 +11,52 @@ char _license[] SEC("license") = "GPL";
 
 __u32 monitored_pid;
 
+int rcu_count;		/* positions seen by the pure lockless walk */
+int rcu_ns_count;	/* ditto, from the non-sleepable program */
 int ref_count;		/* positions seen by the pure referenced walk */
+int hybrid_count;	/* positions seen by the lockless+escalate walk */
+int retry_flags;	/* pos flags at the end of the lockless walks: 0 unless RETRY */
 int ref_flags;		/* pos flags seen by the referenced walk */
 int end_flags;		/* flags after a referenced loop ended: 0 unless NOMEM */
 int second_len;		/* d_path length of the walk's second position */
 int first_len;		/* d_path length of the first position, after the walk */
+int escalated_len;	/* d_path length of the escalated position */
+int escalate_err;	/* bpf_path_ancestors_legitimize() result */
 char second_path[256];
 char first_path[256];
+char escalated_path[256];
 
 static bool monitored(void)
 {
 	return (bpf_get_current_pid_tgid() >> 32) == monitored_pid;
 }
 
+/*
+ * Lockless walk from a non-sleepable program: the RCU critical section is
+ * implicit, no bpf_rcu_read_lock() needed.
+ */
+SEC("lsm/path_mkdir")
+int BPF_PROG(rcu_nonsleepable, const struct path *dir, struct dentry *dentry,
+	     umode_t mode)
+{
+	struct bpf_iter_path_ancestors_rcu rit;
+
+	if (!monitored())
+		return 0;
+
+	bpf_iter_path_ancestors_rcu_new(&rit, (struct path *)dir, 0);
+	while (bpf_iter_path_ancestors_rcu_next(&rit))
+		rcu_ns_count++;
+	retry_flags |= bpf_path_ancestors_rcu_pos_flags(&rit);
+	bpf_iter_path_ancestors_rcu_destroy(&rit);
+	return 0;
+}
+
 SEC("lsm.s/path_mkdir")
 int BPF_PROG(walk_modes, const struct path *dir, struct dentry *dentry,
 	     umode_t mode)
 {
+	struct bpf_iter_path_ancestors_rcu rit;
 	struct bpf_iter_path_ancestors it;
 	struct path *pos, *first = NULL;
 
@@ -41,9 +70,21 @@ int BPF_PROG(walk_modes, const struct path *dir, struct dentry *dentry,
 		return 0;
 
 	/*
-	 * Referenced walk: every position comes acquired, so it stays valid
-	 * past the step that yielded it - the first one is held across the
-	 * rest of the walk and used only once the walk is gone.
+	 * Mode 1: pure lockless, under an explicit RCU critical section.
+	 * Positions are borrowed, so nothing is released here.
+	 */
+	bpf_rcu_read_lock();
+	bpf_iter_path_ancestors_rcu_new(&rit, (struct path *)dir, 0);
+	while (bpf_iter_path_ancestors_rcu_next(&rit))
+		rcu_count++;
+	retry_flags |= bpf_path_ancestors_rcu_pos_flags(&rit);
+	bpf_iter_path_ancestors_rcu_destroy(&rit);
+	bpf_rcu_read_unlock();
+
+	/*
+	 * Mode 2: pure referenced.  Every position comes acquired, so it
+	 * stays valid past the step that yielded it - the first one is held
+	 * across the rest of the walk and used only once the walk is gone.
 	 */
 	bpf_iter_path_ancestors_new(&it, (struct path *)dir, 0);
 	while ((pos = bpf_iter_path_ancestors_next(&it))) {
@@ -70,5 +111,36 @@ int BPF_PROG(walk_modes, const struct path *dir, struct dentry *dentry,
 					    sizeof(first_path));
 		bpf_path_put(first);
 	}
+
+	/*
+	 * Mode 3: hybrid.  Walk lockless to the second position, then hand
+	 * that position over to a referenced iteration which resumes there.
+	 */
+	bpf_rcu_read_lock();
+	bpf_iter_path_ancestors_rcu_new(&rit, (struct path *)dir, 0);
+	while (bpf_iter_path_ancestors_rcu_next(&rit)) {
+		hybrid_count++;
+		if (hybrid_count == 2)
+			break;
+	}
+	escalate_err = bpf_path_ancestors_legitimize(&it, &rit);
+	retry_flags |= bpf_path_ancestors_rcu_pos_flags(&rit);
+	bpf_iter_path_ancestors_rcu_destroy(&rit);
+	bpf_rcu_read_unlock();
+
+	/*
+	 * Out of the RCU critical section.  The resumed iteration's first
+	 * position is the escalated one, kept alive by the reference the
+	 * iteration hands out, so sleepable work can run on it.
+	 */
+	while ((pos = bpf_iter_path_ancestors_next(&it))) {
+		hybrid_count++;
+		if (hybrid_count == 3)
+			escalated_len = bpf_path_d_path(pos, escalated_path,
+							sizeof(escalated_path));
+		bpf_path_put(pos);
+	}
+	end_flags |= bpf_path_ancestors_pos_flags(&it);
+	bpf_iter_path_ancestors_destroy(&it);
 	return 0;
 }
-- 
2.55.0

Re: [PATCH bpf-next v1 11/11] selftests/bpf: exercise the lockless path ancestor iterator

[bot+bpf-ci]

[-- Attachment #1: Type: text/plain, Size: 3467 bytes --]

> selftests/bpf: exercise the lockless path ancestor iterator

TL;DR: Commit message and test comment call d_path on the escalated position
"sleepable work", but bpf_path_d_path() doesn't look KF_SLEEPABLE; it likely
needs a trusted pointer. Wording only, no code bug suggested.

>     selftests/bpf: exercise the lockless path ancestor iterator
>
>     Walk the same ancestry four ways and require the position counts to
>     agree: lockless from a non-sleepable program, where the RCU critical
>     section is implicit; lockless under an explicit bpf_rcu_read_lock();
>     referenced; and the hybrid that walks lockless to the second position,
>     hands it over to a referenced iteration, and resumes there - the
>     escalated position therefore being walked twice, once per mode.
>
>     The sleepable work the escalation exists for (d_path on the escalated
>     position) runs on the resumed iteration's first position, after
>     bpf_rcu_read_unlock(), which is the only place a sleepable kfunc can
>     run at all.
>
>     Signed-off-by: Justin Suess <utilityemal77@gmail.com>

The commit message calls d_path on the escalated position "the sleepable
work the escalation exists for".  Is bpf_path_d_path() a sleepable kfunc?

It is registered without KF_SLEEPABLE in fs/bpf_fs_kfuncs.c, unlike
bpf_get_dentry_xattr() right next to it:

    BTF_ID_FLAGS(func, bpf_path_d_path)
    BTF_ID_FLAGS(func, bpf_get_dentry_xattr, KF_SLEEPABLE)

The reason the test needs the escalated position for d_path looks like trust
rather than sleepability.  bpf_iter_path_ancestors_rcu_new() is
KF_RCU_PROTECTED, so the verifier types the pointer returned by
bpf_iter_path_ancestors_rcu_next() as PTR_TO_BTF_ID | MEM_RCU.
bpf_path_d_path() is not KF_RCU, so it needs a trusted argument and would
reject that pointer.  The previous patch's changelog describes the same
constraint:

> nothing read out of the position may be passed
> to a kfunc demanding a trusted argument.

The comment in the test program has the same framing:

> diff --git a/tools/testing/selftests/bpf/progs/path_ancestors.c b/tools/testing/selftests/bpf/progs/path_ancestors.c
> index 6287f5099a18..3ebf86b23199 100644
> --- a/tools/testing/selftests/bpf/progs/path_ancestors.c
> +++ b/tools/testing/selftests/bpf/progs/path_ancestors.c

[ ... ]

> @@ -70,5 +111,36 @@ int BPF_PROG(walk_modes, const struct path *dir, struct dentry *dentry,

[ ... ]

> +	/*
> +	 * Out of the RCU critical section.  The resumed iteration's first
> +	 * position is the escalated one, kept alive by the reference the
> +	 * iteration hands out, so sleepable work can run on it.
> +	 */
> +	while ((pos = bpf_iter_path_ancestors_next(&it))) {
> +		hybrid_count++;
> +		if (hybrid_count == 3)
> +			escalated_len = bpf_path_d_path(pos, escalated_path,
> +							sizeof(escalated_path));

Beyond the iterator's own bpf_iter_path_ancestors_next() and
bpf_path_put(), does the test run any sleepable work on the escalated
position?

Could the commit message (and this comment) say that d_path needs a
trusted/referenced position, or could the test call a KF_SLEEPABLE kfunc
such as bpf_get_dentry_xattr() on the escalated position so that the
description matches what is checked?


---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md

CI run summary: https://github.com/kernel-patches/bpf/actions/runs/38437592296

Re: [PATCH bpf-next v1 06/11] selftests/bpf: exercise the path ancestor iterator

[Justin Suess]

On Tue, Oct 13, 2026 at 12:47:55PM -0400, Justin Suess wrote:
> Walk the ancestry of a mkdir's parent directory from a sleepable LSM
> program and check that the iteration reaches the root: the temporary
> directory, its parent and / are visited, no position comes back
> flagged, and the flags read back after the loop show it ended at the
> root rather than on a failed allocation.
> 
> Hold the first position across the rest of the walk and resolve its
> pathname only once the loop is done and the iterator destroyed: the
> acquired reference, not the walk's, is then all that keeps the
> position alive.
> 
> Signed-off-by: Justin Suess <utilityemal77@gmail.com>
> ---
>  .../selftests/bpf/prog_tests/path_ancestors.c | 57 ++++++++++++++
>  .../selftests/bpf/progs/path_ancestors.c      | 74 +++++++++++++++++++
>  2 files changed, 131 insertions(+)
>  create mode 100644 tools/testing/selftests/bpf/prog_tests/path_ancestors.c
>  create mode 100644 tools/testing/selftests/bpf/progs/path_ancestors.c
> 
> diff --git a/tools/testing/selftests/bpf/prog_tests/path_ancestors.c b/tools/testing/selftests/bpf/prog_tests/path_ancestors.c
> new file mode 100644
> index 000000000000..d1bd26bce10b
> --- /dev/null
> +++ b/tools/testing/selftests/bpf/prog_tests/path_ancestors.c
> @@ -0,0 +1,57 @@
> +// SPDX-License-Identifier: GPL-2.0
> +/* Copyright (c) 2026 Justin Suess */
> +
> +#include <sys/stat.h>
> +#include <stdlib.h>
> +#include <unistd.h>
> +#include <test_progs.h>
> +#include "path_ancestors.skel.h"
> +
> +void test_path_ancestors(void)
> +{
> +	char base[] = "/tmp/path_ancestors_XXXXXX";
> +	struct path_ancestors *skel = NULL;
> +	char suba[280], subb[280];
> +
> +	if (!ASSERT_OK_PTR(mkdtemp(base), "mkdtemp"))
> +		return;
> +	snprintf(suba, sizeof(suba), "%s/a", base);
> +	snprintf(subb, sizeof(subb), "%s/a/b", base);
> +	if (!ASSERT_OK(mkdir(suba, 0755), "mkdir_a"))
> +		goto out_rm;
> +
> +	skel = path_ancestors__open_and_load();
> +	if (!ASSERT_OK_PTR(skel, "open_and_load"))
> +		goto out_rm;
> +	skel->bss->monitored_pid = getpid();
> +	if (!ASSERT_OK(path_ancestors__attach(skel), "attach"))
> +		goto out;
> +
> +	/* mkdir b: the hook sees dir == suba, whose ancestry is walked. */
> +	if (!ASSERT_OK(mkdir(subb, 0755), "mkdir_b"))
> +		goto out;
> +
> +	/* suba, base, /tmp, / at least. */
> +	ASSERT_GE(skel->bss->ref_count, 4, "ref_count");
> +	ASSERT_EQ(skel->bss->ref_flags, 0, "ref_flags");
> +	/*
> +	 * The referenced loop ended at the root, not on an allocation
> +	 * failure.
> +	 */
> +	ASSERT_EQ(skel->bss->end_flags, 0, "end_flags");
> +
> +	/* The acquired second position, used after its step was taken. */
> +	ASSERT_STREQ(skel->bss->second_path, base, "second_path");
> +	ASSERT_EQ(skel->bss->second_len, strlen(base) + 1, "second_len");
> +
> +	/* The first position, used only after the walk itself was gone. */
> +	ASSERT_STREQ(skel->bss->first_path, suba, "first_path");
> +	ASSERT_EQ(skel->bss->first_len, strlen(suba) + 1, "first_len");
> +
> +out:
> +	path_ancestors__destroy(skel);
> +out_rm:
> +	rmdir(subb);
> +	rmdir(suba);
> +	rmdir(base);
> +}
> diff --git a/tools/testing/selftests/bpf/progs/path_ancestors.c b/tools/testing/selftests/bpf/progs/path_ancestors.c
> new file mode 100644
> index 000000000000..6287f5099a18
> --- /dev/null
> +++ b/tools/testing/selftests/bpf/progs/path_ancestors.c
> @@ -0,0 +1,74 @@
> +// SPDX-License-Identifier: GPL-2.0
> +/* Copyright (c) 2026 Justin Suess */
> +
> +#include "vmlinux.h"
> +#include <errno.h>
> +#include <bpf/bpf_helpers.h>
> +#include <bpf/bpf_tracing.h>
> +#include "bpf_kfuncs.h"
> +
> +char _license[] SEC("license") = "GPL";
> +
> +__u32 monitored_pid;
> +
> +int ref_count;		/* positions seen by the pure referenced walk */
> +int ref_flags;		/* pos flags seen by the referenced walk */
> +int end_flags;		/* flags after a referenced loop ended: 0 unless NOMEM */
> +int second_len;		/* d_path length of the walk's second position */
> +int first_len;		/* d_path length of the first position, after the walk */
> +char second_path[256];
> +char first_path[256];
> +
> +static bool monitored(void)
> +{
> +	return (bpf_get_current_pid_tgid() >> 32) == monitored_pid;
> +}
> +
> +SEC("lsm.s/path_mkdir")
> +int BPF_PROG(walk_modes, const struct path *dir, struct dentry *dentry,
> +	     umode_t mode)
> +{
> +	struct bpf_iter_path_ancestors it;
> +	struct path *pos, *first = NULL;
> +
> +	/*
> +	 * Keep first's init opaque: gcc-bpf otherwise folds it into a
> +	 * preceding loop's exit value, which the verifier cannot track.
> +	 */
> +	barrier_var(first);
> +
cc'ing Eduard Zingerman + Jose Marchesi

This barrier_var line was necessary for this selftest to pass
under GCC BPF.

Othwise it will be rejected by the verifier:

  84: (85) call bpf_iter_path_ancestors_rcu_next#63514
  85: R0=rcu_ptr_path(id=30) ... depth=9
  86: (bf) r6 = r0              ; R6=rcu_ptr_path(id=30)
  88: (55) if r0 != 0x0 goto pc-64
  ...
  101: (85) call bpf_rcu_read_unlock#64876
       ^-- R6 downgraded rcu_ptr_ -> untrusted_ptr_
  ...
  146: (15) if r6 == 0x0 goto pc+10     ; R6=untrusted_ptr_path(id=30)
  147: (bf) r1 = r6
  151: (85) call bpf_path_d_path#64649
  R1 must be referenced or trusted

I think it's trying to optimize out the "struct path* first" and make it
use the r6 register. It tries reusing the R6 register between the two
loops, and doing so causes the program to fail to verify because it doesn't
understand that the path was reinitialized with r6=0 from the previous
exit.

So I had to add the memory barrier to force struct path to be
instantiated outside the register.

There's nothing wrong from a *correctness* perspective with the code
generated by GCC-BPF. But I'm not sure if this is a GCC-BPF bug or a
bug in the SCEV widening series (merge 15b578b1715d). It depends on
the contract BPF bytecode is supposed to meet.

But clang works without the barrier, it's only GCC-BPF that produces
this issue requiring the barrier.

I can give more details if needed.

Justin
> [...]