[PATCH bpf 0/2] bpf fix for mixed tail calls and subprograms

[PATCH bpf 0/2] bpf fix for mixed tail calls and subprograms

[John Fastabend]

We recently tried to use mixed programs that have both tail calls and
subprograms, but it needs the attached fix. Also added a small test
addition that will cause the failure without the fix.

Thanks,
John

---

John Fastabend (2):
      bpf: Fix null ptr deref with mixed tail calls and subprogs
      bpf: selftest to verify mixing bpf2bpf calls and tailcalls with insn patch


 .../selftests/bpf/progs/tailcall_bpf2bpf4.c     | 17 +++++++++++++++++
 1 file changed, 17 insertions(+)

--

[PATCH bpf 1/2] bpf: Fix null ptr deref with mixed tail calls and subprogs

[John Fastabend]

The sub-programs prog->aux->poke_tab[] is populated in jit_subprogs() and
then used when emitting 'BPF_JMP|BPF_TAIL_CALL' insn->code from the
individual JITs. The poke_tab[] to use is stored in the insn->imm by
the code adding it to that array slot. The JIT then uses imm to find the
right entry for an individual instruction. In the x86 bpf_jit_comp.c
this is done by calling emit_bpf_tail_call_direct with the poke_tab[]
of the imm value.

However, we observed the below null-ptr-deref when mixing tail call
programs with subprog programs. For this to happen we just need to
mix bpf-2-bpf calls and tailcalls with some extra calls or instructions
that would be patched later by one of the fixup routines. So whats
happening?

Before the fixup_call_args() -- where the jit op is done -- various
code patching is done by do_misc_fixups(). This may increase the
insn count, for example when we patch map_lookup_up using map_gen_lookup
hook. This does two things. First, it means the instruction index,
insn_idx field, of a tail call instruction will move by a 'delta'.

In verifier code,

 struct bpf_jit_poke_descriptor desc = {
  .reason = BPF_POKE_REASON_TAIL_CALL,
  .tail_call.map = BPF_MAP_PTR(aux->map_ptr_state),
  .tail_call.key = bpf_map_key_immediate(aux),
  .insn_idx = i + delta,
 };

Then subprog start values subprog_info[i].start will be updated
with the delta and any poke descriptor index will also be updated
with the delta in adjust_poke_desc(). If we look at the adjust
subprog starts though we see its only adjusted when the delta
occurs before the new instructions,

        /* NOTE: fake 'exit' subprog should be updated as well. */
        for (i = 0; i <= env->subprog_cnt; i++) {
                if (env->subprog_info[i].start <= off)
                        continue;

Earlier subprograms are not changed because their start values
are not moved. But, adjust_poke_desc() does the offset + delta
indiscriminately. The result is poke descriptors are potentially
corrupted.

Then in jit_subprogs() we only populate the poke_tab[]
when the above insn_idx is less than the next subprogram start. From
above we corrupted our insn_idx so we might incorrectly assume a
poke descriptor is not used in a subprogram omitting it from the
subprogram. And finally when the jit runs it does the deref of poke_tab
when emitting the instruction and crashes with below. Because earlier
step omitted the poke descriptor.

The fix is straight forward with above context. Simply move same logic
from adjust_subprog_starts() into adjust_poke_descs() and only adjust
insn_idx when needed.

[   88.487438] BUG: KASAN: null-ptr-deref in do_jit+0x184a/0x3290
[   88.487455] Write of size 8 at addr 0000000000000008 by task test_progs/5295
[   88.487490] Call Trace:
[   88.487498]  dump_stack+0x93/0xc2
[   88.487515]  kasan_report.cold+0x5f/0xd8
[   88.487530]  ? do_jit+0x184a/0x3290
[   88.487542]  do_jit+0x184a/0x3290
 ...
[   88.487709]  bpf_int_jit_compile+0x248/0x810
 ...
[   88.487765]  bpf_check+0x3718/0x5140
 ...
[   88.487920]  bpf_prog_load+0xa22/0xf10

CC: Maciej Fijalkowski <maciej.fijalkowski@intel.com>
Fixes: a748c6975dea3 ("bpf: propagate poke descriptors to subprograms")
Reviewed-by: Daniel Borkmann <daniel@iogearbox.net>
Signed-off-by: John Fastabend <john.fastabend@gmail.com>
---
 kernel/bpf/verifier.c |    6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 94ba5163d4c5..ac8373da849c 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -11408,7 +11408,7 @@ static void adjust_subprog_starts(struct bpf_verifier_env *env, u32 off, u32 len
 	}
 }
 
-static void adjust_poke_descs(struct bpf_prog *prog, u32 len)
+static void adjust_poke_descs(struct bpf_prog *prog, u32 off, u32 len)
 {
 	struct bpf_jit_poke_descriptor *tab = prog->aux->poke_tab;
 	int i, sz = prog->aux->size_poke_tab;
@@ -11416,6 +11416,8 @@ static void adjust_poke_descs(struct bpf_prog *prog, u32 len)
 
 	for (i = 0; i < sz; i++) {
 		desc = &tab[i];
+		if (desc->insn_idx <= off)
+			continue;
 		desc->insn_idx += len - 1;
 	}
 }
@@ -11436,7 +11438,7 @@ static struct bpf_prog *bpf_patch_insn_data(struct bpf_verifier_env *env, u32 of
 	if (adjust_insn_aux_data(env, new_prog, off, len))
 		return NULL;
 	adjust_subprog_starts(env, off, len);
-	adjust_poke_descs(new_prog, len);
+	adjust_poke_descs(new_prog, off, len);
 	return new_prog;
 }
 

[PATCH bpf 2/2] bpf: selftest to verify mixing bpf2bpf calls and tailcalls with insn patch

[John Fastabend]

This adds some extra noise to the tailcall_bpf2bpf4 tests that will cause
verifier to patch insns. This then moves around subprog start/end insn
index and poke descriptor insn index to ensure that verify and JIT will
continue to track these correctly.

Reviewed-by: Daniel Borkmann <daniel@iogearbox.net>
Signed-off-by: John Fastabend <john.fastabend@gmail.com>
---
 .../selftests/bpf/progs/tailcall_bpf2bpf4.c        |   17 +++++++++++++++++
 1 file changed, 17 insertions(+)

diff --git a/tools/testing/selftests/bpf/progs/tailcall_bpf2bpf4.c b/tools/testing/selftests/bpf/progs/tailcall_bpf2bpf4.c
index 9a1b166b7fbe..0d70de5f97e2 100644
--- a/tools/testing/selftests/bpf/progs/tailcall_bpf2bpf4.c
+++ b/tools/testing/selftests/bpf/progs/tailcall_bpf2bpf4.c
@@ -2,6 +2,13 @@
 #include <linux/bpf.h>
 #include <bpf/bpf_helpers.h>
 
+struct {
+	__uint(type, BPF_MAP_TYPE_ARRAY);
+	__uint(max_entries, 1);
+	__uint(key_size, sizeof(__u32));
+	__uint(value_size, sizeof(__u32));
+} nop_table SEC(".maps");
+
 struct {
 	__uint(type, BPF_MAP_TYPE_PROG_ARRAY);
 	__uint(max_entries, 3);
@@ -11,9 +18,19 @@ struct {
 
 static volatile int count;
 
+__noinline
+int subprog_noise(struct __sk_buff *skb)
+{
+	__u32 key = 0;
+
+	bpf_map_lookup_elem(&nop_table, &key);
+	return 0;
+}
+
 __noinline
 int subprog_tail_2(struct __sk_buff *skb)
 {
+	subprog_noise(skb);
 	bpf_tail_call_static(skb, &jmp_table, 2);
 	return skb->len * 3;
 }

Re: [PATCH bpf 1/2] bpf: Fix null ptr deref with mixed tail calls and subprogs

[Yonghong Song]

On 6/8/21 12:30 PM, John Fastabend wrote:
> The sub-programs prog->aux->poke_tab[] is populated in jit_subprogs() and
> then used when emitting 'BPF_JMP|BPF_TAIL_CALL' insn->code from the
> individual JITs. The poke_tab[] to use is stored in the insn->imm by
> the code adding it to that array slot. The JIT then uses imm to find the
> right entry for an individual instruction. In the x86 bpf_jit_comp.c
> this is done by calling emit_bpf_tail_call_direct with the poke_tab[]
> of the imm value.
> 
> However, we observed the below null-ptr-deref when mixing tail call
> programs with subprog programs. For this to happen we just need to
> mix bpf-2-bpf calls and tailcalls with some extra calls or instructions
> that would be patched later by one of the fixup routines. So whats
> happening?
> 
> Before the fixup_call_args() -- where the jit op is done -- various
> code patching is done by do_misc_fixups(). This may increase the
> insn count, for example when we patch map_lookup_up using map_gen_lookup
> hook. This does two things. First, it means the instruction index,
> insn_idx field, of a tail call instruction will move by a 'delta'.
> 
> In verifier code,
> 
>   struct bpf_jit_poke_descriptor desc = {
>    .reason = BPF_POKE_REASON_TAIL_CALL,
>    .tail_call.map = BPF_MAP_PTR(aux->map_ptr_state),
>    .tail_call.key = bpf_map_key_immediate(aux),
>    .insn_idx = i + delta,
>   };
> 
> Then subprog start values subprog_info[i].start will be updated
> with the delta and any poke descriptor index will also be updated
> with the delta in adjust_poke_desc(). If we look at the adjust
> subprog starts though we see its only adjusted when the delta
> occurs before the new instructions,
> 
>          /* NOTE: fake 'exit' subprog should be updated as well. */
>          for (i = 0; i <= env->subprog_cnt; i++) {
>                  if (env->subprog_info[i].start <= off)
>                          continue;
> 
> Earlier subprograms are not changed because their start values
> are not moved. But, adjust_poke_desc() does the offset + delta
> indiscriminately. The result is poke descriptors are potentially
> corrupted.
> 
> Then in jit_subprogs() we only populate the poke_tab[]
> when the above insn_idx is less than the next subprogram start. From
> above we corrupted our insn_idx so we might incorrectly assume a
> poke descriptor is not used in a subprogram omitting it from the
> subprogram. And finally when the jit runs it does the deref of poke_tab
> when emitting the instruction and crashes with below. Because earlier
> step omitted the poke descriptor.
> 
> The fix is straight forward with above context. Simply move same logic
> from adjust_subprog_starts() into adjust_poke_descs() and only adjust
> insn_idx when needed.
> 
> [   88.487438] BUG: KASAN: null-ptr-deref in do_jit+0x184a/0x3290
> [   88.487455] Write of size 8 at addr 0000000000000008 by task test_progs/5295
> [   88.487490] Call Trace:
> [   88.487498]  dump_stack+0x93/0xc2
> [   88.487515]  kasan_report.cold+0x5f/0xd8
> [   88.487530]  ? do_jit+0x184a/0x3290
> [   88.487542]  do_jit+0x184a/0x3290
>   ...
> [   88.487709]  bpf_int_jit_compile+0x248/0x810
>   ...
> [   88.487765]  bpf_check+0x3718/0x5140
>   ...
> [   88.487920]  bpf_prog_load+0xa22/0xf10
> 
> CC: Maciej Fijalkowski <maciej.fijalkowski@intel.com>
> Fixes: a748c6975dea3 ("bpf: propagate poke descriptors to subprograms")
> Reviewed-by: Daniel Borkmann <daniel@iogearbox.net>
> Signed-off-by: John Fastabend <john.fastabend@gmail.com>

Acked-by: Yonghong Song <yhs@fb.com>

Re: [PATCH bpf 2/2] bpf: selftest to verify mixing bpf2bpf calls and tailcalls with insn patch

[Yonghong Song]

On 6/8/21 12:30 PM, John Fastabend wrote:
> This adds some extra noise to the tailcall_bpf2bpf4 tests that will cause
> verifier to patch insns. This then moves around subprog start/end insn
> index and poke descriptor insn index to ensure that verify and JIT will
> continue to track these correctly.
> 
> Reviewed-by: Daniel Borkmann <daniel@iogearbox.net>
> Signed-off-by: John Fastabend <john.fastabend@gmail.com>

Acked-by: Yonghong Song <yhs@fb.com>

Re: [PATCH bpf 0/2] bpf fix for mixed tail calls and subprograms

[Yonghong Song]

On 6/8/21 12:29 PM, John Fastabend wrote:
> We recently tried to use mixed programs that have both tail calls and
> subprograms, but it needs the attached fix. Also added a small test
> addition that will cause the failure without the fix.
> 
> Thanks,
> John
> 
> ---
> 
> John Fastabend (2):
>        bpf: Fix null ptr deref with mixed tail calls and subprogs
>        bpf: selftest to verify mixing bpf2bpf calls and tailcalls with insn patch
> 
> 
>   .../selftests/bpf/progs/tailcall_bpf2bpf4.c     | 17 +++++++++++++++++
>   1 file changed, 17 insertions(+)

Don't know what happens. Apparently, the first patch made changes
in kernel/bpf/verifier.c, but it didn't show up in the above.

> 
> --
> 

Re: [PATCH bpf 1/2] bpf: Fix null ptr deref with mixed tail calls and subprogs

[Maciej Fijalkowski]

On Tue, Jun 08, 2021 at 12:30:15PM -0700, John Fastabend wrote:
> The sub-programs prog->aux->poke_tab[] is populated in jit_subprogs() and
> then used when emitting 'BPF_JMP|BPF_TAIL_CALL' insn->code from the
> individual JITs. The poke_tab[] to use is stored in the insn->imm by
> the code adding it to that array slot. The JIT then uses imm to find the
> right entry for an individual instruction. In the x86 bpf_jit_comp.c
> this is done by calling emit_bpf_tail_call_direct with the poke_tab[]
> of the imm value.
> 
> However, we observed the below null-ptr-deref when mixing tail call
> programs with subprog programs. For this to happen we just need to
> mix bpf-2-bpf calls and tailcalls with some extra calls or instructions
> that would be patched later by one of the fixup routines. So whats
> happening?
> 
> Before the fixup_call_args() -- where the jit op is done -- various
> code patching is done by do_misc_fixups(). This may increase the
> insn count, for example when we patch map_lookup_up using map_gen_lookup
> hook. This does two things. First, it means the instruction index,
> insn_idx field, of a tail call instruction will move by a 'delta'.
> 
> In verifier code,
> 
>  struct bpf_jit_poke_descriptor desc = {
>   .reason = BPF_POKE_REASON_TAIL_CALL,
>   .tail_call.map = BPF_MAP_PTR(aux->map_ptr_state),
>   .tail_call.key = bpf_map_key_immediate(aux),
>   .insn_idx = i + delta,
>  };
> 
> Then subprog start values subprog_info[i].start will be updated
> with the delta and any poke descriptor index will also be updated
> with the delta in adjust_poke_desc(). If we look at the adjust
> subprog starts though we see its only adjusted when the delta
> occurs before the new instructions,
> 
>         /* NOTE: fake 'exit' subprog should be updated as well. */
>         for (i = 0; i <= env->subprog_cnt; i++) {
>                 if (env->subprog_info[i].start <= off)
>                         continue;
> 
> Earlier subprograms are not changed because their start values
> are not moved. But, adjust_poke_desc() does the offset + delta
> indiscriminately. The result is poke descriptors are potentially
> corrupted.
> 
> Then in jit_subprogs() we only populate the poke_tab[]
> when the above insn_idx is less than the next subprogram start. From
> above we corrupted our insn_idx so we might incorrectly assume a
> poke descriptor is not used in a subprogram omitting it from the
> subprogram. And finally when the jit runs it does the deref of poke_tab
> when emitting the instruction and crashes with below. Because earlier
> step omitted the poke descriptor.
> 
> The fix is straight forward with above context. Simply move same logic
> from adjust_subprog_starts() into adjust_poke_descs() and only adjust
> insn_idx when needed.
> 
> [   88.487438] BUG: KASAN: null-ptr-deref in do_jit+0x184a/0x3290
> [   88.487455] Write of size 8 at addr 0000000000000008 by task test_progs/5295
> [   88.487490] Call Trace:
> [   88.487498]  dump_stack+0x93/0xc2
> [   88.487515]  kasan_report.cold+0x5f/0xd8
> [   88.487530]  ? do_jit+0x184a/0x3290
> [   88.487542]  do_jit+0x184a/0x3290
>  ...
> [   88.487709]  bpf_int_jit_compile+0x248/0x810
>  ...
> [   88.487765]  bpf_check+0x3718/0x5140
>  ...
> [   88.487920]  bpf_prog_load+0xa22/0xf10
> 
> CC: Maciej Fijalkowski <maciej.fijalkowski@intel.com>
> Fixes: a748c6975dea3 ("bpf: propagate poke descriptors to subprograms")
> Reviewed-by: Daniel Borkmann <daniel@iogearbox.net>
> Signed-off-by: John Fastabend <john.fastabend@gmail.com>
> ---
>  kernel/bpf/verifier.c |    6 ++++--
>  1 file changed, 4 insertions(+), 2 deletions(-)
> 
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 94ba5163d4c5..ac8373da849c 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -11408,7 +11408,7 @@ static void adjust_subprog_starts(struct bpf_verifier_env *env, u32 off, u32 len
>  	}
>  }
>  
> -static void adjust_poke_descs(struct bpf_prog *prog, u32 len)
> +static void adjust_poke_descs(struct bpf_prog *prog, u32 off, u32 len)
>  {
>  	struct bpf_jit_poke_descriptor *tab = prog->aux->poke_tab;
>  	int i, sz = prog->aux->size_poke_tab;
> @@ -11416,6 +11416,8 @@ static void adjust_poke_descs(struct bpf_prog *prog, u32 len)
>  
>  	for (i = 0; i < sz; i++) {
>  		desc = &tab[i];

Can we have a comment below that would say something like:
"don't update taicall's insn idx if the patching is being done on higher
insns" ?

What I'm saying is that after a long break from that code I find 'off' as
a confusing name. It's the offset within the flat-structured bpf prog (so
the prog that is not yet sliced onto subprogs). Maybe we could find a
better name for that, like "curr_insn_idx". I'm not sure what's your view
on that.

OTOH I'm aware that whole content of bpf_patch_insn_data operates on
'off'.

Generally sorry that I missed that, it didn't come to my mind to mix in
other helpers that include patching.

Anyway:
Acked-by: Maciej Fijalkowski <maciej.fijalkowski@intel.com>
Tested-by: Maciej Fijalkowski <maciej.fijalkowski@intel.com>

> +		if (desc->insn_idx <= off)
> +			continue;
>  		desc->insn_idx += len - 1;
>  	}
>  }
> @@ -11436,7 +11438,7 @@ static struct bpf_prog *bpf_patch_insn_data(struct bpf_verifier_env *env, u32 of
>  	if (adjust_insn_aux_data(env, new_prog, off, len))
>  		return NULL;
>  	adjust_subprog_starts(env, off, len);
> -	adjust_poke_descs(new_prog, len);
> +	adjust_poke_descs(new_prog, off, len);
>  	return new_prog;
>  }
>  
> 
> 

Re: [PATCH bpf 2/2] bpf: selftest to verify mixing bpf2bpf calls and tailcalls with insn patch

[Maciej Fijalkowski]

On Tue, Jun 08, 2021 at 12:30:33PM -0700, John Fastabend wrote:
> This adds some extra noise to the tailcall_bpf2bpf4 tests that will cause
> verifier to patch insns. This then moves around subprog start/end insn
> index and poke descriptor insn index to ensure that verify and JIT will
> continue to track these correctly.

This test is the most complicated one where I tried to document the scope
of it on the side of prog_tests/tailcalls.c. I feel that it would make it
more difficult to debug it if under any circumstances something would have
been broken with that logic.

Maybe a separate test scenario? Or is this an overkill? If so, I would
vote for moving it to tailcall_bpf2bpf1.c and have a little comment that
testing other bpf helpers mixed in is in scope of that test.

> 
> Reviewed-by: Daniel Borkmann <daniel@iogearbox.net>
> Signed-off-by: John Fastabend <john.fastabend@gmail.com>
> ---
>  .../selftests/bpf/progs/tailcall_bpf2bpf4.c        |   17 +++++++++++++++++
>  1 file changed, 17 insertions(+)
> 
> diff --git a/tools/testing/selftests/bpf/progs/tailcall_bpf2bpf4.c b/tools/testing/selftests/bpf/progs/tailcall_bpf2bpf4.c
> index 9a1b166b7fbe..0d70de5f97e2 100644
> --- a/tools/testing/selftests/bpf/progs/tailcall_bpf2bpf4.c
> +++ b/tools/testing/selftests/bpf/progs/tailcall_bpf2bpf4.c
> @@ -2,6 +2,13 @@
>  #include <linux/bpf.h>
>  #include <bpf/bpf_helpers.h>
>  
> +struct {
> +	__uint(type, BPF_MAP_TYPE_ARRAY);
> +	__uint(max_entries, 1);
> +	__uint(key_size, sizeof(__u32));
> +	__uint(value_size, sizeof(__u32));
> +} nop_table SEC(".maps");
> +
>  struct {
>  	__uint(type, BPF_MAP_TYPE_PROG_ARRAY);
>  	__uint(max_entries, 3);
> @@ -11,9 +18,19 @@ struct {
>  
>  static volatile int count;
>  
> +__noinline
> +int subprog_noise(struct __sk_buff *skb)
> +{
> +	__u32 key = 0;
> +
> +	bpf_map_lookup_elem(&nop_table, &key);
> +	return 0;
> +}
> +
>  __noinline
>  int subprog_tail_2(struct __sk_buff *skb)
>  {
> +	subprog_noise(skb);
>  	bpf_tail_call_static(skb, &jmp_table, 2);
>  	return skb->len * 3;
>  }
> 
> 

Re: [PATCH bpf 0/2] bpf fix for mixed tail calls and subprograms

[John Fastabend]

Yonghong Song wrote:
> 
> 
> On 6/8/21 12:29 PM, John Fastabend wrote:
> > We recently tried to use mixed programs that have both tail calls and
> > subprograms, but it needs the attached fix. Also added a small test
> > addition that will cause the failure without the fix.
> > 
> > Thanks,
> > John
> > 
> > ---
> > 
> > John Fastabend (2):
> >        bpf: Fix null ptr deref with mixed tail calls and subprogs
> >        bpf: selftest to verify mixing bpf2bpf calls and tailcalls with insn patch
> > 
> > 
> >   .../selftests/bpf/progs/tailcall_bpf2bpf4.c     | 17 +++++++++++++++++
> >   1 file changed, 17 insertions(+)
> 
> Don't know what happens. Apparently, the first patch made changes
> in kernel/bpf/verifier.c, but it didn't show up in the above.

Agh its how I applied the patches and cover-letter :/ I moved them between
trees (bpf-next -> bpf) and lost the diff. I can resubmit if anyone
cares.

Re: [PATCH bpf 2/2] bpf: selftest to verify mixing bpf2bpf calls and tailcalls with insn patch

[Maciej Fijalkowski]

On Wed, Jun 09, 2021 at 09:26:01AM -0700, John Fastabend wrote:
> Maciej Fijalkowski wrote:
> > On Tue, Jun 08, 2021 at 12:30:33PM -0700, John Fastabend wrote:
> > > This adds some extra noise to the tailcall_bpf2bpf4 tests that will cause
> > > verifier to patch insns. This then moves around subprog start/end insn
> > > index and poke descriptor insn index to ensure that verify and JIT will
> > > continue to track these correctly.
> > 
> > This test is the most complicated one where I tried to document the scope
> > of it on the side of prog_tests/tailcalls.c. I feel that it would make it
> > more difficult to debug it if under any circumstances something would have
> > been broken with that logic.
> > 
> > Maybe a separate test scenario? Or is this an overkill? If so, I would
> > vote for moving it to tailcall_bpf2bpf1.c and have a little comment that
> > testing other bpf helpers mixed in is in scope of that test.
> 
> I like pushing it into the complex test to get the most instruction
> patching combinations possible.

Makes sense after a second thought, that was the intention of that test
case, to squeeze out the feature out here.

I still would ask to have it commented on the prog_tests/tailcalls.c side,
WDYT?

> 
> > 
> > > 
> > > Reviewed-by: Daniel Borkmann <daniel@iogearbox.net>
> > > Signed-off-by: John Fastabend <john.fastabend@gmail.com>
> > > ---
> > >  .../selftests/bpf/progs/tailcall_bpf2bpf4.c        |   17 +++++++++++++++++
> > >  1 file changed, 17 insertions(+)
> > > 
> > > diff --git a/tools/testing/selftests/bpf/progs/tailcall_bpf2bpf4.c b/tools/testing/selftests/bpf/progs/tailcall_bpf2bpf4.c
> > > index 9a1b166b7fbe..0d70de5f97e2 100644
> > > --- a/tools/testing/selftests/bpf/progs/tailcall_bpf2bpf4.c
> > > +++ b/tools/testing/selftests/bpf/progs/tailcall_bpf2bpf4.c
> > > @@ -2,6 +2,13 @@
> > >  #include <linux/bpf.h>
> > >  #include <bpf/bpf_helpers.h>
> > >  
> > > +struct {
> > > +	__uint(type, BPF_MAP_TYPE_ARRAY);
> > > +	__uint(max_entries, 1);
> > > +	__uint(key_size, sizeof(__u32));
> > > +	__uint(value_size, sizeof(__u32));
> > > +} nop_table SEC(".maps");
> > > +
> > >  struct {
> > >  	__uint(type, BPF_MAP_TYPE_PROG_ARRAY);
> > >  	__uint(max_entries, 3);
> > > @@ -11,9 +18,19 @@ struct {
> > >  
> > >  static volatile int count;
> > >  
> > > +__noinline
> > > +int subprog_noise(struct __sk_buff *skb)
> > > +{
> > > +	__u32 key = 0;
> > > +
> > > +	bpf_map_lookup_elem(&nop_table, &key);
> > > +	return 0;
> > > +}
> > > +
> > >  __noinline
> > >  int subprog_tail_2(struct __sk_buff *skb)
> > >  {
> > > +	subprog_noise(skb);
> > >  	bpf_tail_call_static(skb, &jmp_table, 2);
> > >  	return skb->len * 3;
> > >  }
> > > 
> > > 
> 
> 

Re: [PATCH bpf 1/2] bpf: Fix null ptr deref with mixed tail calls and subprogs

[John Fastabend]

Maciej Fijalkowski wrote:
> On Tue, Jun 08, 2021 at 12:30:15PM -0700, John Fastabend wrote:
> > The sub-programs prog->aux->poke_tab[] is populated in jit_subprogs() and
> > then used when emitting 'BPF_JMP|BPF_TAIL_CALL' insn->code from the
> > individual JITs. The poke_tab[] to use is stored in the insn->imm by
> > the code adding it to that array slot. The JIT then uses imm to find the
> > right entry for an individual instruction. In the x86 bpf_jit_comp.c
> > this is done by calling emit_bpf_tail_call_direct with the poke_tab[]
> > of the imm value.
> > 
> > However, we observed the below null-ptr-deref when mixing tail call
> > programs with subprog programs. For this to happen we just need to
> > mix bpf-2-bpf calls and tailcalls with some extra calls or instructions
> > that would be patched later by one of the fixup routines. So whats
> > happening?
> > 
> > Before the fixup_call_args() -- where the jit op is done -- various
> > code patching is done by do_misc_fixups(). This may increase the
> > insn count, for example when we patch map_lookup_up using map_gen_lookup
> > hook. This does two things. First, it means the instruction index,
> > insn_idx field, of a tail call instruction will move by a 'delta'.
> > 
> > In verifier code,
> > 
> >  struct bpf_jit_poke_descriptor desc = {
> >   .reason = BPF_POKE_REASON_TAIL_CALL,
> >   .tail_call.map = BPF_MAP_PTR(aux->map_ptr_state),
> >   .tail_call.key = bpf_map_key_immediate(aux),
> >   .insn_idx = i + delta,
> >  };
> > 
> > Then subprog start values subprog_info[i].start will be updated
> > with the delta and any poke descriptor index will also be updated
> > with the delta in adjust_poke_desc(). If we look at the adjust
> > subprog starts though we see its only adjusted when the delta
> > occurs before the new instructions,
> > 
> >         /* NOTE: fake 'exit' subprog should be updated as well. */
> >         for (i = 0; i <= env->subprog_cnt; i++) {
> >                 if (env->subprog_info[i].start <= off)
> >                         continue;
> > 
> > Earlier subprograms are not changed because their start values
> > are not moved. But, adjust_poke_desc() does the offset + delta
> > indiscriminately. The result is poke descriptors are potentially
> > corrupted.
> > 
> > Then in jit_subprogs() we only populate the poke_tab[]
> > when the above insn_idx is less than the next subprogram start. From
> > above we corrupted our insn_idx so we might incorrectly assume a
> > poke descriptor is not used in a subprogram omitting it from the
> > subprogram. And finally when the jit runs it does the deref of poke_tab
> > when emitting the instruction and crashes with below. Because earlier
> > step omitted the poke descriptor.
> > 
> > The fix is straight forward with above context. Simply move same logic
> > from adjust_subprog_starts() into adjust_poke_descs() and only adjust
> > insn_idx when needed.
> > 
> > [   88.487438] BUG: KASAN: null-ptr-deref in do_jit+0x184a/0x3290
> > [   88.487455] Write of size 8 at addr 0000000000000008 by task test_progs/5295
> > [   88.487490] Call Trace:
> > [   88.487498]  dump_stack+0x93/0xc2
> > [   88.487515]  kasan_report.cold+0x5f/0xd8
> > [   88.487530]  ? do_jit+0x184a/0x3290
> > [   88.487542]  do_jit+0x184a/0x3290
> >  ...
> > [   88.487709]  bpf_int_jit_compile+0x248/0x810
> >  ...
> > [   88.487765]  bpf_check+0x3718/0x5140
> >  ...
> > [   88.487920]  bpf_prog_load+0xa22/0xf10
> > 
> > CC: Maciej Fijalkowski <maciej.fijalkowski@intel.com>
> > Fixes: a748c6975dea3 ("bpf: propagate poke descriptors to subprograms")
> > Reviewed-by: Daniel Borkmann <daniel@iogearbox.net>
> > Signed-off-by: John Fastabend <john.fastabend@gmail.com>
> > ---
> >  kernel/bpf/verifier.c |    6 ++++--
> >  1 file changed, 4 insertions(+), 2 deletions(-)
> > 
> > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > index 94ba5163d4c5..ac8373da849c 100644
> > --- a/kernel/bpf/verifier.c
> > +++ b/kernel/bpf/verifier.c
> > @@ -11408,7 +11408,7 @@ static void adjust_subprog_starts(struct bpf_verifier_env *env, u32 off, u32 len
> >  	}
> >  }
> >  
> > -static void adjust_poke_descs(struct bpf_prog *prog, u32 len)
> > +static void adjust_poke_descs(struct bpf_prog *prog, u32 off, u32 len)
> >  {
> >  	struct bpf_jit_poke_descriptor *tab = prog->aux->poke_tab;
> >  	int i, sz = prog->aux->size_poke_tab;
> > @@ -11416,6 +11416,8 @@ static void adjust_poke_descs(struct bpf_prog *prog, u32 len)
> >  
> >  	for (i = 0; i < sz; i++) {
> >  		desc = &tab[i];
> 
> Can we have a comment below that would say something like:
> "don't update taicall's insn idx if the patching is being done on higher
> insns" ?
> 
> What I'm saying is that after a long break from that code I find 'off' as
> a confusing name. It's the offset within the flat-structured bpf prog (so
> the prog that is not yet sliced onto subprogs). Maybe we could find a
> better name for that, like "curr_insn_idx". I'm not sure what's your view
> on that.
> 
> OTOH I'm aware that whole content of bpf_patch_insn_data operates on
> 'off'.

I'm not necessarily opposed to a comment there but we don't have a comment
above for the same operation on start offsets. I'll think about it for
a follow up patch assuming no one shouts.

> 
> Generally sorry that I missed that, it didn't come to my mind to mix in
> other helpers that include patching.


Thanks for testing.

> 
> Anyway:
> Acked-by: Maciej Fijalkowski <maciej.fijalkowski@intel.com>
> Tested-by: Maciej Fijalkowski <maciej.fijalkowski@intel.com>
> 
> > +		if (desc->insn_idx <= off)
> > +			continue;
> >  		desc->insn_idx += len - 1;
> >  	}
> >  }
> > @@ -11436,7 +11438,7 @@ static struct bpf_prog *bpf_patch_insn_data(struct bpf_verifier_env *env, u32 of
> >  	if (adjust_insn_aux_data(env, new_prog, off, len))
> >  		return NULL;
> >  	adjust_subprog_starts(env, off, len);
> > -	adjust_poke_descs(new_prog, len);
> > +	adjust_poke_descs(new_prog, off, len);
> >  	return new_prog;
> >  }
> >  
> > 
> > 

Re: [PATCH bpf 2/2] bpf: selftest to verify mixing bpf2bpf calls and tailcalls with insn patch

[John Fastabend]

Maciej Fijalkowski wrote:
> On Tue, Jun 08, 2021 at 12:30:33PM -0700, John Fastabend wrote:
> > This adds some extra noise to the tailcall_bpf2bpf4 tests that will cause
> > verifier to patch insns. This then moves around subprog start/end insn
> > index and poke descriptor insn index to ensure that verify and JIT will
> > continue to track these correctly.
> 
> This test is the most complicated one where I tried to document the scope
> of it on the side of prog_tests/tailcalls.c. I feel that it would make it
> more difficult to debug it if under any circumstances something would have
> been broken with that logic.
> 
> Maybe a separate test scenario? Or is this an overkill? If so, I would
> vote for moving it to tailcall_bpf2bpf1.c and have a little comment that
> testing other bpf helpers mixed in is in scope of that test.

I like pushing it into the complex test to get the most instruction
patching combinations possible.

> 
> > 
> > Reviewed-by: Daniel Borkmann <daniel@iogearbox.net>
> > Signed-off-by: John Fastabend <john.fastabend@gmail.com>
> > ---
> >  .../selftests/bpf/progs/tailcall_bpf2bpf4.c        |   17 +++++++++++++++++
> >  1 file changed, 17 insertions(+)
> > 
> > diff --git a/tools/testing/selftests/bpf/progs/tailcall_bpf2bpf4.c b/tools/testing/selftests/bpf/progs/tailcall_bpf2bpf4.c
> > index 9a1b166b7fbe..0d70de5f97e2 100644
> > --- a/tools/testing/selftests/bpf/progs/tailcall_bpf2bpf4.c
> > +++ b/tools/testing/selftests/bpf/progs/tailcall_bpf2bpf4.c
> > @@ -2,6 +2,13 @@
> >  #include <linux/bpf.h>
> >  #include <bpf/bpf_helpers.h>
> >  
> > +struct {
> > +	__uint(type, BPF_MAP_TYPE_ARRAY);
> > +	__uint(max_entries, 1);
> > +	__uint(key_size, sizeof(__u32));
> > +	__uint(value_size, sizeof(__u32));
> > +} nop_table SEC(".maps");
> > +
> >  struct {
> >  	__uint(type, BPF_MAP_TYPE_PROG_ARRAY);
> >  	__uint(max_entries, 3);
> > @@ -11,9 +18,19 @@ struct {
> >  
> >  static volatile int count;
> >  
> > +__noinline
> > +int subprog_noise(struct __sk_buff *skb)
> > +{
> > +	__u32 key = 0;
> > +
> > +	bpf_map_lookup_elem(&nop_table, &key);
> > +	return 0;
> > +}
> > +
> >  __noinline
> >  int subprog_tail_2(struct __sk_buff *skb)
> >  {
> > +	subprog_noise(skb);
> >  	bpf_tail_call_static(skb, &jmp_table, 2);
> >  	return skb->len * 3;
> >  }
> > 
> > 

Re: [PATCH bpf 0/2] bpf fix for mixed tail calls and subprograms

[Yonghong Song]

On 6/9/21 9:17 AM, John Fastabend wrote:
> Yonghong Song wrote:
>>
>>
>> On 6/8/21 12:29 PM, John Fastabend wrote:
>>> We recently tried to use mixed programs that have both tail calls and
>>> subprograms, but it needs the attached fix. Also added a small test
>>> addition that will cause the failure without the fix.
>>>
>>> Thanks,
>>> John
>>>
>>> ---
>>>
>>> John Fastabend (2):
>>>         bpf: Fix null ptr deref with mixed tail calls and subprogs
>>>         bpf: selftest to verify mixing bpf2bpf calls and tailcalls with insn patch
>>>
>>>
>>>    .../selftests/bpf/progs/tailcall_bpf2bpf4.c     | 17 +++++++++++++++++
>>>    1 file changed, 17 insertions(+)
>>
>> Don't know what happens. Apparently, the first patch made changes
>> in kernel/bpf/verifier.c, but it didn't show up in the above.
> 
> Agh its how I applied the patches and cover-letter :/ I moved them between
> trees (bpf-next -> bpf) and lost the diff. I can resubmit if anyone
> cares.

You don't need to resubmit just because of this. This cover letter
may not be merged eventually.

[PATCH bpf 2/2] bpf: selftest to verify mixing bpf2bpf calls and tailcalls with insn patch

[John Fastabend]

This adds some extra noise to the tailcall_bpf2bpf4 tests that will cause
verify to patch insns. This then moves around subprog start/end insn
index and poke descriptor insn index to ensure that verify and JIT will
continue to track these correctly.

If done correctly verifier should pass this program same as before and
JIT should emit tail call logic.

Signed-off-by: John Fastabend <john.fastabend@gmail.com>
---
 .../selftests/bpf/prog_tests/tailcalls.c      | 36 +++++++++++++------
 .../selftests/bpf/progs/tailcall_bpf2bpf4.c   | 21 ++++++++++-
 2 files changed, 46 insertions(+), 11 deletions(-)

diff --git a/tools/testing/selftests/bpf/prog_tests/tailcalls.c b/tools/testing/selftests/bpf/prog_tests/tailcalls.c
index ee27d68d2a1c..b5940e6ca67c 100644
--- a/tools/testing/selftests/bpf/prog_tests/tailcalls.c
+++ b/tools/testing/selftests/bpf/prog_tests/tailcalls.c
@@ -715,6 +715,8 @@ static void test_tailcall_bpf2bpf_3(void)
 	bpf_object__close(obj);
 }
 
+#include "tailcall_bpf2bpf4.skel.h"
+
 /* test_tailcall_bpf2bpf_4 checks that tailcall counter is correctly preserved
  * across tailcalls combined with bpf2bpf calls. for making sure that tailcall
  * counter behaves correctly, bpf program will go through following flow:
@@ -727,10 +729,15 @@ static void test_tailcall_bpf2bpf_3(void)
  * the loop begins. At the end of the test make sure that the global counter is
  * equal to 31, because tailcall counter includes the first two tailcalls
  * whereas global counter is incremented only on loop presented on flow above.
+ *
+ * The noise parameter is used to insert bpf_map_update calls into the logic
+ * to force verifier to patch instructions. This allows us to ensure jump
+ * logic remains correct with instruction movement.
  */
-static void test_tailcall_bpf2bpf_4(void)
+static void test_tailcall_bpf2bpf_4(bool noise)
 {
-	int err, map_fd, prog_fd, main_fd, data_fd, i, val;
+	int err, map_fd, prog_fd, main_fd, data_fd, i;
+	struct tailcall_bpf2bpf4__bss val;
 	struct bpf_map *prog_array, *data_map;
 	struct bpf_program *prog;
 	struct bpf_object *obj;
@@ -774,11 +781,6 @@ static void test_tailcall_bpf2bpf_4(void)
 			goto out;
 	}
 
-	err = bpf_prog_test_run(main_fd, 1, &pkt_v4, sizeof(pkt_v4), 0,
-				&duration, &retval, NULL);
-	CHECK(err || retval != sizeof(pkt_v4) * 3, "tailcall", "err %d errno %d retval %d\n",
-	      err, errno, retval);
-
 	data_map = bpf_object__find_map_by_name(obj, "tailcall.bss");
 	if (CHECK_FAIL(!data_map || !bpf_map__is_internal(data_map)))
 		return;
@@ -787,10 +789,22 @@ static void test_tailcall_bpf2bpf_4(void)
 	if (CHECK_FAIL(map_fd < 0))
 		return;
 
+	i = 0;
+	val.noise = noise;
+	val.count = 0;
+	err = bpf_map_update_elem(data_fd, &i, &val, BPF_ANY);
+	if (CHECK_FAIL(err))
+		goto out;
+
+	err = bpf_prog_test_run(main_fd, 1, &pkt_v4, sizeof(pkt_v4), 0,
+				&duration, &retval, NULL);
+	CHECK(err || retval != sizeof(pkt_v4) * 3, "tailcall", "err %d errno %d retval %d\n",
+	      err, errno, retval);
+
 	i = 0;
 	err = bpf_map_lookup_elem(data_fd, &i, &val);
-	CHECK(err || val != 31, "tailcall count", "err %d errno %d count %d\n",
-	      err, errno, val);
+	CHECK(err || val.count != 31, "tailcall count", "err %d errno %d count %d\n",
+	      err, errno, val.count);
 
 out:
 	bpf_object__close(obj);
@@ -815,5 +829,7 @@ void test_tailcalls(void)
 	if (test__start_subtest("tailcall_bpf2bpf_3"))
 		test_tailcall_bpf2bpf_3();
 	if (test__start_subtest("tailcall_bpf2bpf_4"))
-		test_tailcall_bpf2bpf_4();
+		test_tailcall_bpf2bpf_4(false);
+	if (test__start_subtest("tailcall_bpf2bpf_5"))
+		test_tailcall_bpf2bpf_4(true);
 }
diff --git a/tools/testing/selftests/bpf/progs/tailcall_bpf2bpf4.c b/tools/testing/selftests/bpf/progs/tailcall_bpf2bpf4.c
index 9a1b166b7fbe..6242803dabde 100644
--- a/tools/testing/selftests/bpf/progs/tailcall_bpf2bpf4.c
+++ b/tools/testing/selftests/bpf/progs/tailcall_bpf2bpf4.c
@@ -2,6 +2,13 @@
 #include <linux/bpf.h>
 #include <bpf/bpf_helpers.h>
 
+struct {
+	__uint(type, BPF_MAP_TYPE_ARRAY);
+	__uint(max_entries, 1);
+	__uint(key_size, sizeof(__u32));
+	__uint(value_size, sizeof(__u32));
+} nop_table SEC(".maps");
+
 struct {
 	__uint(type, BPF_MAP_TYPE_PROG_ARRAY);
 	__uint(max_entries, 3);
@@ -9,11 +16,23 @@ struct {
 	__uint(value_size, sizeof(__u32));
 } jmp_table SEC(".maps");
 
-static volatile int count;
+int count = 0;
+int noise = 0;
+
+__always_inline int subprog_noise(void)
+{
+	__u32 key = 0;
+
+	bpf_printk("hello noisy subprog %d\n", key);
+	bpf_map_lookup_elem(&nop_table, &key);
+	return 0;
+}
 
 __noinline
 int subprog_tail_2(struct __sk_buff *skb)
 {
+	if (noise)
+		subprog_noise();
 	bpf_tail_call_static(skb, &jmp_table, 2);
 	return skb->len * 3;
 }
-- 
2.25.1