[PATCH bpf-next v2 0/2] Transfer RCU lock state across subprog calls

[PATCH bpf-next v2 0/2] Transfer RCU lock state across subprog calls

[Kumar Kartikeya Dwivedi]

David suggested during the discussion in [0] that we should handle RCU
locks in a similar fashion to spin locks where the verifier understands
when a lock held in a caller is released in callee, or lock taken in
callee is released in a caller, or the callee is called within a lock
critical section. This set extends the same semantics to RCU read locks
and adds a few selftests to verify correct behavior. This issue has also
come up for sched-ext programs.

This would now allow static subprog calls to be made without errors
within RCU read sections, for subprogs to release RCU locks of callers
and return to them, or for subprogs to take RCU lock which is later
released in the caller.

  [0]: https://lore.kernel.org/bpf/20240204120206.796412-1-memxor@gmail.com

Changelog:
----------
v1 -> v2:
v1: https://lore.kernel.org/bpf/20240204230231.1013964-1-memxor@gmail.com

 * Add tests for global subprog behaviour (Yafang)
 * Add Acks, Tested-by (Yonghong, Yafang)

Kumar Kartikeya Dwivedi (2):
  bpf: Transfer RCU lock state between subprog calls
  selftests/bpf: Add tests for RCU lock transfer between subprogs

 kernel/bpf/verifier.c                         |   3 +-
 .../selftests/bpf/prog_tests/rcu_read_lock.c  |   6 +
 .../selftests/bpf/progs/rcu_read_lock.c       | 120 ++++++++++++++++++
 3 files changed, 127 insertions(+), 2 deletions(-)


base-commit: 2a79690eae953daaac232f93e6c5ac47ac539f2d
-- 
2.40.1

[PATCH bpf-next v2 1/2] bpf: Transfer RCU lock state between subprog calls

[Kumar Kartikeya Dwivedi]

Allow transferring an imbalanced RCU lock state between subprog calls
during verification. This allows patterns where a subprog call returns
with an RCU lock held, or a subprog call releases an RCU lock held by
the caller. Currently, the verifier would end up complaining if the RCU
lock is not released when processing an exit from a subprog, which is
non-ideal if its execution is supposed to be enclosed in an RCU read
section of the caller.

Instead, simply only check whether we are processing exit for frame#0
and do not complain on an active RCU lock otherwise. We only need to
update the check when processing BPF_EXIT insn, as copy_verifier_state
is already set up to do the right thing.

Suggested-by: David Vernet <void@manifault.com>
Tested-by: Yafang Shao <laoar.shao@gmail.com>
Acked-by: Yonghong Song <yonghong.song@linux.dev>
Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
---
 kernel/bpf/verifier.c | 3 +--
 1 file changed, 1 insertion(+), 2 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 64fa188d00ad..993712b9996b 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -17698,8 +17698,7 @@ static int do_check(struct bpf_verifier_env *env)
 					return -EINVAL;
 				}
 
-				if (env->cur_state->active_rcu_lock &&
-				    !in_rbtree_lock_required_cb(env)) {
+				if (env->cur_state->active_rcu_lock && !env->cur_state->curframe) {
 					verbose(env, "bpf_rcu_read_unlock is missing\n");
 					return -EINVAL;
 				}
-- 
2.40.1

Re: [PATCH bpf-next v2 1/2] bpf: Transfer RCU lock state between subprog calls

[David Vernet]

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

On Mon, Feb 05, 2024 at 05:56:45AM +0000, Kumar Kartikeya Dwivedi wrote:
> Allow transferring an imbalanced RCU lock state between subprog calls
> during verification. This allows patterns where a subprog call returns
> with an RCU lock held, or a subprog call releases an RCU lock held by
> the caller. Currently, the verifier would end up complaining if the RCU
> lock is not released when processing an exit from a subprog, which is
> non-ideal if its execution is supposed to be enclosed in an RCU read
> section of the caller.
> 
> Instead, simply only check whether we are processing exit for frame#0
> and do not complain on an active RCU lock otherwise. We only need to
> update the check when processing BPF_EXIT insn, as copy_verifier_state
> is already set up to do the right thing.
> 
> Suggested-by: David Vernet <void@manifault.com>
> Tested-by: Yafang Shao <laoar.shao@gmail.com>
> Acked-by: Yonghong Song <yonghong.song@linux.dev>
> Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>

Acked-by: David Vernet <void@manifault.com>

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 228 bytes --]

[PATCH bpf-next v2 2/2] selftests/bpf: Add tests for RCU lock transfer between subprogs

[Kumar Kartikeya Dwivedi]

Add selftests covering the following cases:
- A static or global subprog called from within a RCU read section works
- A static subprog taking an RCU read lock which is released in caller works
- A static subprog releasing the caller's RCU read lock works

Global subprogs that leave the lock in an imbalanced state will not
work, as they are verified separately, so ensure those cases fail as
well.

Acked-by: Yonghong Song <yonghong.song@linux.dev>
Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
---
 .../selftests/bpf/prog_tests/rcu_read_lock.c  |   6 +
 .../selftests/bpf/progs/rcu_read_lock.c       | 120 ++++++++++++++++++
 2 files changed, 126 insertions(+)

diff --git a/tools/testing/selftests/bpf/prog_tests/rcu_read_lock.c b/tools/testing/selftests/bpf/prog_tests/rcu_read_lock.c
index 3f1f58d3a729..a1f7e7378a64 100644
--- a/tools/testing/selftests/bpf/prog_tests/rcu_read_lock.c
+++ b/tools/testing/selftests/bpf/prog_tests/rcu_read_lock.c
@@ -29,6 +29,10 @@ static void test_success(void)
 	bpf_program__set_autoload(skel->progs.non_sleepable_1, true);
 	bpf_program__set_autoload(skel->progs.non_sleepable_2, true);
 	bpf_program__set_autoload(skel->progs.task_trusted_non_rcuptr, true);
+	bpf_program__set_autoload(skel->progs.rcu_read_lock_subprog, true);
+	bpf_program__set_autoload(skel->progs.rcu_read_lock_global_subprog, true);
+	bpf_program__set_autoload(skel->progs.rcu_read_lock_subprog_lock, true);
+	bpf_program__set_autoload(skel->progs.rcu_read_lock_subprog_unlock, true);
 	err = rcu_read_lock__load(skel);
 	if (!ASSERT_OK(err, "skel_load"))
 		goto out;
@@ -75,6 +79,8 @@ static const char * const inproper_region_tests[] = {
 	"inproper_sleepable_helper",
 	"inproper_sleepable_kfunc",
 	"nested_rcu_region",
+	"rcu_read_lock_global_subprog_lock",
+	"rcu_read_lock_global_subprog_unlock",
 };
 
 static void test_inproper_region(void)
diff --git a/tools/testing/selftests/bpf/progs/rcu_read_lock.c b/tools/testing/selftests/bpf/progs/rcu_read_lock.c
index 14fb01437fb8..ab3a532b7dd6 100644
--- a/tools/testing/selftests/bpf/progs/rcu_read_lock.c
+++ b/tools/testing/selftests/bpf/progs/rcu_read_lock.c
@@ -319,3 +319,123 @@ int cross_rcu_region(void *ctx)
 	bpf_rcu_read_unlock();
 	return 0;
 }
+
+__noinline
+static int static_subprog(void *ctx)
+{
+	volatile int ret = 0;
+
+	if (bpf_get_prandom_u32())
+		return ret + 42;
+	return ret + bpf_get_prandom_u32();
+}
+
+__noinline
+int global_subprog(u64 a)
+{
+	volatile int ret = a;
+
+	return ret + static_subprog(NULL);
+}
+
+__noinline
+static int static_subprog_lock(void *ctx)
+{
+	volatile int ret = 0;
+
+	bpf_rcu_read_lock();
+	if (bpf_get_prandom_u32())
+		return ret + 42;
+	return ret + bpf_get_prandom_u32();
+}
+
+__noinline
+int global_subprog_lock(u64 a)
+{
+	volatile int ret = a;
+
+	return ret + static_subprog_lock(NULL);
+}
+
+__noinline
+static int static_subprog_unlock(void *ctx)
+{
+	volatile int ret = 0;
+
+	bpf_rcu_read_unlock();
+	if (bpf_get_prandom_u32())
+		return ret + 42;
+	return ret + bpf_get_prandom_u32();
+}
+
+__noinline
+int global_subprog_unlock(u64 a)
+{
+	volatile int ret = a;
+
+	return ret + static_subprog_unlock(NULL);
+}
+
+SEC("?fentry.s/" SYS_PREFIX "sys_getpgid")
+int rcu_read_lock_subprog(void *ctx)
+{
+	volatile int ret = 0;
+
+	bpf_rcu_read_lock();
+	if (bpf_get_prandom_u32())
+		ret += static_subprog(ctx);
+	bpf_rcu_read_unlock();
+	return 0;
+}
+
+SEC("?fentry.s/" SYS_PREFIX "sys_getpgid")
+int rcu_read_lock_global_subprog(void *ctx)
+{
+	volatile int ret = 0;
+
+	bpf_rcu_read_lock();
+	if (bpf_get_prandom_u32())
+		ret += global_subprog(ret);
+	bpf_rcu_read_unlock();
+	return 0;
+}
+
+SEC("?fentry.s/" SYS_PREFIX "sys_getpgid")
+int rcu_read_lock_subprog_lock(void *ctx)
+{
+	volatile int ret = 0;
+
+	ret += static_subprog_lock(ctx);
+	bpf_rcu_read_unlock();
+	return 0;
+}
+
+SEC("?fentry.s/" SYS_PREFIX "sys_getpgid")
+int rcu_read_lock_global_subprog_lock(void *ctx)
+{
+	volatile int ret = 0;
+
+	ret += global_subprog_lock(ret);
+	bpf_rcu_read_unlock();
+	return 0;
+}
+
+SEC("?fentry.s/" SYS_PREFIX "sys_getpgid")
+int rcu_read_lock_subprog_unlock(void *ctx)
+{
+	volatile int ret = 0;
+
+	bpf_rcu_read_lock();
+	ret += static_subprog_unlock(ctx);
+	return 0;
+}
+
+SEC("?fentry.s/" SYS_PREFIX "sys_getpgid")
+int rcu_read_lock_global_subprog_unlock(void *ctx)
+{
+	volatile int ret = 0;
+
+	bpf_rcu_read_lock();
+	ret += global_subprog_unlock(ret);
+	return 0;
+}
-- 
2.40.1

Re: [PATCH bpf-next v2 2/2] selftests/bpf: Add tests for RCU lock transfer between subprogs

[Yafang Shao]

On Mon, Feb 5, 2024 at 1:56 PM Kumar Kartikeya Dwivedi <memxor@gmail.com> wrote:
>
> Add selftests covering the following cases:
> - A static or global subprog called from within a RCU read section works
> - A static subprog taking an RCU read lock which is released in caller works
> - A static subprog releasing the caller's RCU read lock works
>
> Global subprogs that leave the lock in an imbalanced state will not
> work, as they are verified separately, so ensure those cases fail as
> well.
>
> Acked-by: Yonghong Song <yonghong.song@linux.dev>
> Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>

Acked-and-Tested-by: Yafang Shao <laoar.shao@gmail.com>

> ---
>  .../selftests/bpf/prog_tests/rcu_read_lock.c  |   6 +
>  .../selftests/bpf/progs/rcu_read_lock.c       | 120 ++++++++++++++++++
>  2 files changed, 126 insertions(+)
>
> diff --git a/tools/testing/selftests/bpf/prog_tests/rcu_read_lock.c b/tools/testing/selftests/bpf/prog_tests/rcu_read_lock.c
> index 3f1f58d3a729..a1f7e7378a64 100644
> --- a/tools/testing/selftests/bpf/prog_tests/rcu_read_lock.c
> +++ b/tools/testing/selftests/bpf/prog_tests/rcu_read_lock.c
> @@ -29,6 +29,10 @@ static void test_success(void)
>         bpf_program__set_autoload(skel->progs.non_sleepable_1, true);
>         bpf_program__set_autoload(skel->progs.non_sleepable_2, true);
>         bpf_program__set_autoload(skel->progs.task_trusted_non_rcuptr, true);
> +       bpf_program__set_autoload(skel->progs.rcu_read_lock_subprog, true);
> +       bpf_program__set_autoload(skel->progs.rcu_read_lock_global_subprog, true);
> +       bpf_program__set_autoload(skel->progs.rcu_read_lock_subprog_lock, true);
> +       bpf_program__set_autoload(skel->progs.rcu_read_lock_subprog_unlock, true);
>         err = rcu_read_lock__load(skel);
>         if (!ASSERT_OK(err, "skel_load"))
>                 goto out;
> @@ -75,6 +79,8 @@ static const char * const inproper_region_tests[] = {
>         "inproper_sleepable_helper",
>         "inproper_sleepable_kfunc",
>         "nested_rcu_region",
> +       "rcu_read_lock_global_subprog_lock",
> +       "rcu_read_lock_global_subprog_unlock",
>  };
>
>  static void test_inproper_region(void)
> diff --git a/tools/testing/selftests/bpf/progs/rcu_read_lock.c b/tools/testing/selftests/bpf/progs/rcu_read_lock.c
> index 14fb01437fb8..ab3a532b7dd6 100644
> --- a/tools/testing/selftests/bpf/progs/rcu_read_lock.c
> +++ b/tools/testing/selftests/bpf/progs/rcu_read_lock.c
> @@ -319,3 +319,123 @@ int cross_rcu_region(void *ctx)
>         bpf_rcu_read_unlock();
>         return 0;
>  }
> +
> +__noinline
> +static int static_subprog(void *ctx)
> +{
> +       volatile int ret = 0;
> +
> +       if (bpf_get_prandom_u32())
> +               return ret + 42;
> +       return ret + bpf_get_prandom_u32();
> +}
> +
> +__noinline
> +int global_subprog(u64 a)
> +{
> +       volatile int ret = a;
> +
> +       return ret + static_subprog(NULL);
> +}
> +
> +__noinline
> +static int static_subprog_lock(void *ctx)
> +{
> +       volatile int ret = 0;
> +
> +       bpf_rcu_read_lock();
> +       if (bpf_get_prandom_u32())
> +               return ret + 42;
> +       return ret + bpf_get_prandom_u32();
> +}
> +
> +__noinline
> +int global_subprog_lock(u64 a)
> +{
> +       volatile int ret = a;
> +
> +       return ret + static_subprog_lock(NULL);
> +}
> +
> +__noinline
> +static int static_subprog_unlock(void *ctx)
> +{
> +       volatile int ret = 0;
> +
> +       bpf_rcu_read_unlock();
> +       if (bpf_get_prandom_u32())
> +               return ret + 42;
> +       return ret + bpf_get_prandom_u32();
> +}
> +
> +__noinline
> +int global_subprog_unlock(u64 a)
> +{
> +       volatile int ret = a;
> +
> +       return ret + static_subprog_unlock(NULL);
> +}
> +
> +SEC("?fentry.s/" SYS_PREFIX "sys_getpgid")
> +int rcu_read_lock_subprog(void *ctx)
> +{
> +       volatile int ret = 0;
> +
> +       bpf_rcu_read_lock();
> +       if (bpf_get_prandom_u32())
> +               ret += static_subprog(ctx);
> +       bpf_rcu_read_unlock();
> +       return 0;
> +}
> +
> +SEC("?fentry.s/" SYS_PREFIX "sys_getpgid")
> +int rcu_read_lock_global_subprog(void *ctx)
> +{
> +       volatile int ret = 0;
> +
> +       bpf_rcu_read_lock();
> +       if (bpf_get_prandom_u32())
> +               ret += global_subprog(ret);
> +       bpf_rcu_read_unlock();
> +       return 0;
> +}
> +
> +SEC("?fentry.s/" SYS_PREFIX "sys_getpgid")
> +int rcu_read_lock_subprog_lock(void *ctx)
> +{
> +       volatile int ret = 0;
> +
> +       ret += static_subprog_lock(ctx);
> +       bpf_rcu_read_unlock();
> +       return 0;
> +}
> +
> +SEC("?fentry.s/" SYS_PREFIX "sys_getpgid")
> +int rcu_read_lock_global_subprog_lock(void *ctx)
> +{
> +       volatile int ret = 0;
> +
> +       ret += global_subprog_lock(ret);
> +       bpf_rcu_read_unlock();
> +       return 0;
> +}
> +
> +SEC("?fentry.s/" SYS_PREFIX "sys_getpgid")
> +int rcu_read_lock_subprog_unlock(void *ctx)
> +{
> +       volatile int ret = 0;
> +
> +       bpf_rcu_read_lock();
> +       ret += static_subprog_unlock(ctx);
> +       return 0;
> +}
> +
> +SEC("?fentry.s/" SYS_PREFIX "sys_getpgid")
> +int rcu_read_lock_global_subprog_unlock(void *ctx)
> +{
> +       volatile int ret = 0;
> +
> +       bpf_rcu_read_lock();
> +       ret += global_subprog_unlock(ret);
> +       return 0;
> +}
> --
> 2.40.1
>


-- 
Regards
Yafang

Re: [PATCH bpf-next v2 2/2] selftests/bpf: Add tests for RCU lock transfer between subprogs

[David Vernet]

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

On Mon, Feb 05, 2024 at 05:56:46AM +0000, Kumar Kartikeya Dwivedi wrote:
> Add selftests covering the following cases:
> - A static or global subprog called from within a RCU read section works
> - A static subprog taking an RCU read lock which is released in caller works
> - A static subprog releasing the caller's RCU read lock works
> 
> Global subprogs that leave the lock in an imbalanced state will not
> work, as they are verified separately, so ensure those cases fail as
> well.
> 
> Acked-by: Yonghong Song <yonghong.song@linux.dev>
> Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>

Acked-by: David Vernet <void@manifault.com>

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 228 bytes --]

Re: [PATCH bpf-next v2 0/2] Transfer RCU lock state across subprog calls

[patchwork-bot+netdevbpf]

Hello:

This series was applied to bpf/bpf-next.git (master)
by Alexei Starovoitov <ast@kernel.org>:

On Mon,  5 Feb 2024 05:56:44 +0000 you wrote:
> David suggested during the discussion in [0] that we should handle RCU
> locks in a similar fashion to spin locks where the verifier understands
> when a lock held in a caller is released in callee, or lock taken in
> callee is released in a caller, or the callee is called within a lock
> critical section. This set extends the same semantics to RCU read locks
> and adds a few selftests to verify correct behavior. This issue has also
> come up for sched-ext programs.
> 
> [...]

Here is the summary with links:
  - [bpf-next,v2,1/2] bpf: Transfer RCU lock state between subprog calls
    https://git.kernel.org/bpf/bpf-next/c/6fceea0fa59f
  - [bpf-next,v2,2/2] selftests/bpf: Add tests for RCU lock transfer between subprogs
    https://git.kernel.org/bpf/bpf-next/c/8be6a0147af3

You are awesome, thank you!
-- 
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html