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

[Justin Suess <utilityemal77@gmail.com>]

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