[PATCH 0/2] bpf: Allow bpf_for/bpf_repeat while holding spin

[PATCH 0/2] bpf: Allow bpf_for/bpf_repeat while holding spin

[Emil Tsalapatis]

From: Emil Tsalapatis (Meta) <emil@etsalapatis.com>

In BPF programs, kfunc calls while holding a lock are not allowed
because kfuncs may sleep by default. The exception to this rule are the
functions in special_kfunc_list, which are guaranteed to not sleep. The
bpf_iter_num_* functions used by the bpf_for and bpf_repeat macros make
no function calls themselves, and as such are guaranteed to not sleep.
Add them to special_kfunc_list to allow them within BPF spinlock
critical sections.

Signed-off-by: Emil Tsalapatis (Meta) <emil@etsalapatis.com>

Emil Tsalapatis (2):
  bpf: Allow bpf_for/bpf_repeat calls while holding a spinlock
  selftests/bpf: test bpf_for within spin lock section

 kernel/bpf/verifier.c                         | 20 +++++++++++++-
 .../selftests/bpf/progs/verifier_spin_lock.c  | 26 +++++++++++++++++++
 2 files changed, 45 insertions(+), 1 deletion(-)

-- 
2.47.1

[PATCH 1/2] bpf: Allow bpf_for/bpf_repeat calls while holding a spinlock

[Emil Tsalapatis]

 Add the bpf_iter_num_* kfuncs called by bpf_for in special_kfunc_list,
 and allow the calls even while holding a spin lock.

Signed-off-by: Emil Tsalapatis (Meta) <emil@etsalapatis.com>
---
 kernel/bpf/verifier.c | 20 +++++++++++++++++++-
 1 file changed, 19 insertions(+), 1 deletion(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index d77abb87ffb1..f209021914b1 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -11690,6 +11690,9 @@ enum special_kfunc_type {
 	KF_bpf_get_kmem_cache,
 	KF_bpf_local_irq_save,
 	KF_bpf_local_irq_restore,
+	KF_bpf_iter_num_new,
+	KF_bpf_iter_num_next,
+	KF_bpf_iter_num_destroy,
 };
 
 BTF_SET_START(special_kfunc_set)
@@ -11765,6 +11768,9 @@ BTF_ID_UNUSED
 BTF_ID(func, bpf_get_kmem_cache)
 BTF_ID(func, bpf_local_irq_save)
 BTF_ID(func, bpf_local_irq_restore)
+BTF_ID(func, bpf_iter_num_new)
+BTF_ID(func, bpf_iter_num_next)
+BTF_ID(func, bpf_iter_num_destroy)
 
 static bool is_kfunc_ret_null(struct bpf_kfunc_call_arg_meta *meta)
 {
@@ -12151,12 +12157,24 @@ static bool is_bpf_rbtree_api_kfunc(u32 btf_id)
 	       btf_id == special_kfunc_list[KF_bpf_rbtree_first];
 }
 
+static bool is_bpf_loop_api_kfunc(u32 btf_id)
+{
+	return btf_id == special_kfunc_list[KF_bpf_iter_num_new] ||
+	       btf_id == special_kfunc_list[KF_bpf_iter_num_next] ||
+	       btf_id == special_kfunc_list[KF_bpf_iter_num_destroy];
+}
+
 static bool is_bpf_graph_api_kfunc(u32 btf_id)
 {
 	return is_bpf_list_api_kfunc(btf_id) || is_bpf_rbtree_api_kfunc(btf_id) ||
 	       btf_id == special_kfunc_list[KF_bpf_refcount_acquire_impl];
 }
 
+static bool kfunc_spin_allowed(u32 btf_id)
+{
+	return is_bpf_graph_api_kfunc(btf_id) || is_bpf_loop_api_kfunc(btf_id);
+}
+
 static bool is_sync_callback_calling_kfunc(u32 btf_id)
 {
 	return btf_id == special_kfunc_list[KF_bpf_rbtree_add_impl];
@@ -19048,7 +19066,7 @@ static int do_check(struct bpf_verifier_env *env)
 				if (env->cur_state->active_locks) {
 					if ((insn->src_reg == BPF_REG_0 && insn->imm != BPF_FUNC_spin_unlock) ||
 					    (insn->src_reg == BPF_PSEUDO_KFUNC_CALL &&
-					     (insn->off != 0 || !is_bpf_graph_api_kfunc(insn->imm)))) {
+					     (insn->off != 0 || !kfunc_spin_allowed(insn->imm)))) {
 						verbose(env, "function calls are not allowed while holding a lock\n");
 						return -EINVAL;
 					}
-- 
2.47.1

Re: [PATCH 1/2] bpf: Allow bpf_for/bpf_repeat calls while holding a spinlock

[Eduard Zingerman]

On Wed, 2025-01-01 at 15:37 -0500, Emil Tsalapatis wrote:
>  Add the bpf_iter_num_* kfuncs called by bpf_for in special_kfunc_list,
>  and allow the calls even while holding a spin lock.
> 
> Signed-off-by: Emil Tsalapatis (Meta) <emil@etsalapatis.com>
> ---

Reviewed-by: Eduard Zingerman <eddyz87@gmail.com>

[...]

> @@ -19048,7 +19066,7 @@ static int do_check(struct bpf_verifier_env *env)
>  				if (env->cur_state->active_locks) {
>  					if ((insn->src_reg == BPF_REG_0 && insn->imm != BPF_FUNC_spin_unlock) ||
>  					    (insn->src_reg == BPF_PSEUDO_KFUNC_CALL &&
> -					     (insn->off != 0 || !is_bpf_graph_api_kfunc(insn->imm)))) {
> +					     (insn->off != 0 || !kfunc_spin_allowed(insn->imm)))) {
>  						verbose(env, "function calls are not allowed while holding a lock\n");
>  						return -EINVAL;
>  					}


Nit: technically, 'bpf_loop' is a helper function independent of iter_num API.
     I suggest to change the name to is_bpf_iter_num_api_kfunc.
     Also, if we decide that loops are ok with spin locks,
     the condition above should be adjusted to allow calls to bpf_loop,
     e.g. to make the following test work:

--- 8< -------------------------------------
static int loop_cb(__u64 index, void *ctx)
{
	return 0;
}

SEC("tc")
__success __failure_unpriv __msg_unpriv("")
__retval(0)
int bpf_loop_inside_locked_region2(void)
{
	const int zero = 0;
	struct val *val;

	val = bpf_map_lookup_elem(&map_spin_lock, &zero);
	if (!val)
		return -1;

	bpf_spin_lock(&val->l);
	bpf_loop(10, loop_cb, NULL, 0);
	bpf_spin_unlock(&val->l);

	return 0;
}
------------------------------------- >8 ---

Re: [PATCH 1/2] bpf: Allow bpf_for/bpf_repeat calls while holding a spinlock

[Emil Tsalapatis]

On Thu, Jan 2, 2025 at 1:02 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Wed, 2025-01-01 at 15:37 -0500, Emil Tsalapatis wrote:
> >  Add the bpf_iter_num_* kfuncs called by bpf_for in special_kfunc_list,
> >  and allow the calls even while holding a spin lock.
> >
> > Signed-off-by: Emil Tsalapatis (Meta) <emil@etsalapatis.com>
> > ---
>
> Reviewed-by: Eduard Zingerman <eddyz87@gmail.com>
>
> [...]
>
> > @@ -19048,7 +19066,7 @@ static int do_check(struct bpf_verifier_env *env)
> >                               if (env->cur_state->active_locks) {
> >                                       if ((insn->src_reg == BPF_REG_0 && insn->imm != BPF_FUNC_spin_unlock) ||
> >                                           (insn->src_reg == BPF_PSEUDO_KFUNC_CALL &&
> > -                                          (insn->off != 0 || !is_bpf_graph_api_kfunc(insn->imm)))) {
> > +                                          (insn->off != 0 || !kfunc_spin_allowed(insn->imm)))) {
> >                                               verbose(env, "function calls are not allowed while holding a lock\n");
> >                                               return -EINVAL;
> >                                       }
>
>
> Nit: technically, 'bpf_loop' is a helper function independent of iter_num API.
>      I suggest to change the name to is_bpf_iter_num_api_kfunc.
>      Also, if we decide that loops are ok with spin locks,
>      the condition above should be adjusted to allow calls to bpf_loop,
>      e.g. to make the following test work:
>

(Sorry for the duplicate, accidentally didn't send the email in plaintext)

Will do, bpf_iter_num_api_kfunc is more reasonable. For bpf_loops
AFAICT we would need to ensure the callback cannot sleep,
which would need extra checks/changes to the verifier compared to
bpf_for. IMO we can deal with it in a separate patch if we think
allowing it is a good idea.

> --- 8< -------------------------------------
> static int loop_cb(__u64 index, void *ctx)
> {
>         return 0;
> }
>
> SEC("tc")
> __success __failure_unpriv __msg_unpriv("")
> __retval(0)
> int bpf_loop_inside_locked_region2(void)
> {
>         const int zero = 0;
>         struct val *val;
>
>         val = bpf_map_lookup_elem(&map_spin_lock, &zero);
>         if (!val)
>                 return -1;
>
>         bpf_spin_lock(&val->l);
>         bpf_loop(10, loop_cb, NULL, 0);
>         bpf_spin_unlock(&val->l);
>
>         return 0;
> }
> ------------------------------------- >8 ---
>
>
>

Re: [PATCH 1/2] bpf: Allow bpf_for/bpf_repeat calls while holding a spinlock

[Eduard Zingerman]

On Sat, 2025-01-04 at 14:25 -0500, Emil Tsalapatis wrote:

[...]

> > > @@ -19048,7 +19066,7 @@ static int do_check(struct bpf_verifier_env *env)
> > >                               if (env->cur_state->active_locks) {
> > >                                       if ((insn->src_reg == BPF_REG_0 && insn->imm != BPF_FUNC_spin_unlock) ||
> > >                                           (insn->src_reg == BPF_PSEUDO_KFUNC_CALL &&
> > > -                                          (insn->off != 0 || !is_bpf_graph_api_kfunc(insn->imm)))) {
> > > +                                          (insn->off != 0 || !kfunc_spin_allowed(insn->imm)))) {
> > >                                               verbose(env, "function calls are not allowed while holding a lock\n");
> > >                                               return -EINVAL;
> > >                                       }
> > 
> > 
> > Nit: technically, 'bpf_loop' is a helper function independent of iter_num API.
> >      I suggest to change the name to is_bpf_iter_num_api_kfunc.
> >      Also, if we decide that loops are ok with spin locks,
> >      the condition above should be adjusted to allow calls to bpf_loop,
> >      e.g. to make the following test work:
> > 
> 
> (Sorry for the duplicate, accidentally didn't send the email in plaintext)
> 
> Will do, bpf_iter_num_api_kfunc is more reasonable. For bpf_loops
> AFAICT we would need to ensure the callback cannot sleep,
> which would need extra checks/changes to the verifier compared to
> bpf_for. IMO we can deal with it in a separate patch if we think
> allowing it is a good idea.

Not really, callbacks are verified "in-line". When a function call to
a function calling synchronous callback is verified, verifier steps
into callback body some number of times. If a sleeping call would
be discovered during callback function verification, verifier would
see that spin lock is currently taken and report error. So, this is
really just a check for particular helper call.

[...]

Re: [PATCH 1/2] bpf: Allow bpf_for/bpf_repeat calls while holding a spinlock

[Emil Tsalapatis]

I see, thank you for the feedback. in that case I will send another
version that handles bpf_loop.

On Sat, Jan 4, 2025 at 7:11 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Sat, 2025-01-04 at 14:25 -0500, Emil Tsalapatis wrote:
>
> [...]
>
> > > > @@ -19048,7 +19066,7 @@ static int do_check(struct bpf_verifier_env *env)
> > > >                               if (env->cur_state->active_locks) {
> > > >                                       if ((insn->src_reg == BPF_REG_0 && insn->imm != BPF_FUNC_spin_unlock) ||
> > > >                                           (insn->src_reg == BPF_PSEUDO_KFUNC_CALL &&
> > > > -                                          (insn->off != 0 || !is_bpf_graph_api_kfunc(insn->imm)))) {
> > > > +                                          (insn->off != 0 || !kfunc_spin_allowed(insn->imm)))) {
> > > >                                               verbose(env, "function calls are not allowed while holding a lock\n");
> > > >                                               return -EINVAL;
> > > >                                       }
> > >
> > >
> > > Nit: technically, 'bpf_loop' is a helper function independent of iter_num API.
> > >      I suggest to change the name to is_bpf_iter_num_api_kfunc.
> > >      Also, if we decide that loops are ok with spin locks,
> > >      the condition above should be adjusted to allow calls to bpf_loop,
> > >      e.g. to make the following test work:
> > >
> >
> > (Sorry for the duplicate, accidentally didn't send the email in plaintext)
> >
> > Will do, bpf_iter_num_api_kfunc is more reasonable. For bpf_loops
> > AFAICT we would need to ensure the callback cannot sleep,
> > which would need extra checks/changes to the verifier compared to
> > bpf_for. IMO we can deal with it in a separate patch if we think
> > allowing it is a good idea.
>
> Not really, callbacks are verified "in-line". When a function call to
> a function calling synchronous callback is verified, verifier steps
> into callback body some number of times. If a sleeping call would
> be discovered during callback function verification, verifier would
> see that spin lock is currently taken and report error. So, this is
> really just a check for particular helper call.
>
> [...]
>

Re: [PATCH 1/2] bpf: Allow bpf_for/bpf_repeat calls while holding a spinlock

[Alexei Starovoitov]

On Mon, Jan 6, 2025 at 7:04 AM Emil Tsalapatis <emil@etsalapatis.com> wrote:
>
> I see, thank you for the feedback. in that case I will send another
> version that handles bpf_loop.

I think that can be a separate follow up.
I'll apply the v2 as-is.

Also pls don't top post. This mailing list preferes inline replies.

[PATCH 2/2] selftests/bpf: test bpf_for within spin lock section

[Emil Tsalapatis]

Add a selftest to ensure BPF for loops within critical sections are
accepted by the verifier.

Signed-off-by: Emil Tsalapatis (Meta) <emil@etsalapatis.com>
---
 .../selftests/bpf/progs/verifier_spin_lock.c  | 26 +++++++++++++++++++
 1 file changed, 26 insertions(+)

diff --git a/tools/testing/selftests/bpf/progs/verifier_spin_lock.c b/tools/testing/selftests/bpf/progs/verifier_spin_lock.c
index 25599eac9a70..d9d7b05cf6d2 100644
--- a/tools/testing/selftests/bpf/progs/verifier_spin_lock.c
+++ b/tools/testing/selftests/bpf/progs/verifier_spin_lock.c
@@ -530,4 +530,30 @@ l1_%=:	exit;						\
 	: __clobber_all);
 }
 
+SEC("tc")
+__description("spin_lock: loop within a locked region")
+__success __failure_unpriv __msg_unpriv("")
+__retval(0)
+int bpf_loop_inside_locked_region(void)
+{
+	const int zero = 0;
+	struct val *val;
+	int i, j = 0;
+
+	val = bpf_map_lookup_elem(&map_spin_lock, &zero);
+	if (!val)
+		return -1;
+
+	bpf_spin_lock(&val->l);
+	bpf_for(i, 0, 10) {
+		j++;
+		/* Silence "unused variable" warnings. */
+		if (j == 10)
+			break;
+	}
+	bpf_spin_unlock(&val->l);
+
+	return 0;
+}
+
 char _license[] SEC("license") = "GPL";
-- 
2.47.1

Re: [PATCH 2/2] selftests/bpf: test bpf_for within spin lock section

[Eduard Zingerman]

On Wed, 2025-01-01 at 15:37 -0500, Emil Tsalapatis wrote:
> Add a selftest to ensure BPF for loops within critical sections are
> accepted by the verifier.
> 
> Signed-off-by: Emil Tsalapatis (Meta) <emil@etsalapatis.com>
> ---

Acked-by: Eduard Zingerman <eddyz87@gmail.com>

[...]