[PATCH bpf] bpf: Extend the size of scratched_stack_slots to 128 bits

[PATCH bpf] bpf: Extend the size of scratched_stack_slots to 128 bits

[Hou Tao]

From: Hou Tao <houtao1@huawei.com>

When the fastcall pattern is enabled for bpf helper or kfunc, the stack
size limitation is increased from MAX_BPF_STACK (512 bytes) to
MAX_BPF_STACK + CALLER_SAVED_REGS * BPF_REG_SIZE (560 bytes), as
implemented in check_stack_slot_within_bounds(). This additional stack
space is reserved for spilling and filling of caller saved registers.

However, when marking a stack slot as scratched during spilling through
mark_stack_slot_scratched(), a shift-out-of-bounds warning is reported
as shown below. And it can be easily reproducted by running:
./test_progs -t verifier_bpf_fastcall/bpf_fastcall_max_stack_ok.

  ------------[ cut here ]------------
  UBSAN: shift-out-of-bounds in ../include/linux/bpf_verifier.h:942:37
  shift exponent 64 is too large for 64-bit type 'long long unsigned int'
  CPU: 1 UID: 0 PID: 5169 Comm: new_name Tainted: G ...  6.11.0-rc4+
  Tainted: [O]=OOT_MODULE
  Hardware name: QEMU Standard PC (i440FX + PIIX, 1996) ...
  Call Trace:
   <TASK>
   dump_stack_lvl+0x8f/0xb0
   dump_stack+0x10/0x20
   ubsan_epilogue+0x9/0x40
   __ubsan_handle_shift_out_of_bounds+0x10e/0x170
   check_mem_access.cold+0x61/0x6d
   do_check_common+0x2e2e/0x5da0
   bpf_check+0x48a2/0x5750
   bpf_prog_load+0xb2f/0x1250
   __sys_bpf+0xd78/0x36b0
   __x64_sys_bpf+0x45/0x60
   x64_sys_call+0x1b2a/0x20d0

However, the shift-out-of-bound issue doesn't seem to affect the output
of scratched stack slots in the verifier log. For example, for
bpf_fastcall_max_stack_ok, the 64-th stack slot is correctly marked as
scratched, as shown in the verifier log:

  2: (7b) *(u64 *)(r10 -520) = r1       ; R1_w=42 R10=fp0 fp-520_w=42

The reason relates to the compiler implementation. It appears that the
shift exponent is taken modulo 64 before applying the shift, so after
"slot = (1ULL << 64)", the value of slot becomes 1.

Fix the UBSAN warning by extending the size of scratched_stack_slots
from 64 bits to 128-bits.

Fixes: 5b5f51bff1b6 ("bpf: no_caller_saved_registers attribute for helper calls")
Signed-off-by: Hou Tao <houtao1@huawei.com>
---
 include/linux/bpf_verifier.h | 20 +++++++++++++-------
 1 file changed, 13 insertions(+), 7 deletions(-)

diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 4513372c5bc8..1bb6c6def04d 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -773,8 +773,11 @@ struct bpf_verifier_env {
 	 * since the last time the function state was printed
 	 */
 	u32 scratched_regs;
-	/* Same as scratched_regs but for stack slots */
-	u64 scratched_stack_slots;
+	/* Same as scratched_regs but for stack slots. The stack size may
+	 * temporarily exceed MAX_BPF_STACK (e.g., due to fastcall pattern
+	 * in check_stack_slot_within_bounds()), so two u64 values are used.
+	 */
+	u64 scratched_stack_slots[2];
 	u64 prev_log_pos, prev_insn_print_pos;
 	/* buffer used to temporary hold constants as scalar registers */
 	struct bpf_reg_state fake_reg[2];
@@ -939,7 +942,7 @@ static inline void mark_reg_scratched(struct bpf_verifier_env *env, u32 regno)
 
 static inline void mark_stack_slot_scratched(struct bpf_verifier_env *env, u32 spi)
 {
-	env->scratched_stack_slots |= 1ULL << spi;
+	env->scratched_stack_slots[spi / 64] |= 1ULL << (spi & 63);
 }
 
 static inline bool reg_scratched(const struct bpf_verifier_env *env, u32 regno)
@@ -949,25 +952,28 @@ static inline bool reg_scratched(const struct bpf_verifier_env *env, u32 regno)
 
 static inline bool stack_slot_scratched(const struct bpf_verifier_env *env, u64 regno)
 {
-	return (env->scratched_stack_slots >> regno) & 1;
+	return (env->scratched_stack_slots[regno / 64] >> (regno & 63)) & 1;
 }
 
 static inline bool verifier_state_scratched(const struct bpf_verifier_env *env)
 {
-	return env->scratched_regs || env->scratched_stack_slots;
+	return env->scratched_regs || env->scratched_stack_slots[0] ||
+	       env->scratched_stack_slots[1];
 }
 
 static inline void mark_verifier_state_clean(struct bpf_verifier_env *env)
 {
 	env->scratched_regs = 0U;
-	env->scratched_stack_slots = 0ULL;
+	env->scratched_stack_slots[0] = 0ULL;
+	env->scratched_stack_slots[1] = 0ULL;
 }
 
 /* Used for printing the entire verifier state. */
 static inline void mark_verifier_state_scratched(struct bpf_verifier_env *env)
 {
 	env->scratched_regs = ~0U;
-	env->scratched_stack_slots = ~0ULL;
+	env->scratched_stack_slots[0] = ~0ULL;
+	env->scratched_stack_slots[1] = ~0ULL;
 }
 
 static inline bool bpf_stack_narrow_access_ok(int off, int fill_size, int spill_size)
-- 
2.29.2

Re: [PATCH bpf] bpf: Extend the size of scratched_stack_slots to 128 bits

[Andrii Nakryiko]

On Tue, Oct 22, 2024 at 7:15 PM Hou Tao <houtao@huaweicloud.com> wrote:
>
> From: Hou Tao <houtao1@huawei.com>
>
> When the fastcall pattern is enabled for bpf helper or kfunc, the stack
> size limitation is increased from MAX_BPF_STACK (512 bytes) to
> MAX_BPF_STACK + CALLER_SAVED_REGS * BPF_REG_SIZE (560 bytes), as
> implemented in check_stack_slot_within_bounds(). This additional stack
> space is reserved for spilling and filling of caller saved registers.
>
> However, when marking a stack slot as scratched during spilling through
> mark_stack_slot_scratched(), a shift-out-of-bounds warning is reported
> as shown below. And it can be easily reproducted by running:
> ./test_progs -t verifier_bpf_fastcall/bpf_fastcall_max_stack_ok.
>
>   ------------[ cut here ]------------
>   UBSAN: shift-out-of-bounds in ../include/linux/bpf_verifier.h:942:37
>   shift exponent 64 is too large for 64-bit type 'long long unsigned int'
>   CPU: 1 UID: 0 PID: 5169 Comm: new_name Tainted: G ...  6.11.0-rc4+
>   Tainted: [O]=OOT_MODULE
>   Hardware name: QEMU Standard PC (i440FX + PIIX, 1996) ...
>   Call Trace:
>    <TASK>
>    dump_stack_lvl+0x8f/0xb0
>    dump_stack+0x10/0x20
>    ubsan_epilogue+0x9/0x40
>    __ubsan_handle_shift_out_of_bounds+0x10e/0x170
>    check_mem_access.cold+0x61/0x6d
>    do_check_common+0x2e2e/0x5da0
>    bpf_check+0x48a2/0x5750
>    bpf_prog_load+0xb2f/0x1250
>    __sys_bpf+0xd78/0x36b0
>    __x64_sys_bpf+0x45/0x60
>    x64_sys_call+0x1b2a/0x20d0
>
> However, the shift-out-of-bound issue doesn't seem to affect the output
> of scratched stack slots in the verifier log. For example, for
> bpf_fastcall_max_stack_ok, the 64-th stack slot is correctly marked as
> scratched, as shown in the verifier log:
>
>   2: (7b) *(u64 *)(r10 -520) = r1       ; R1_w=42 R10=fp0 fp-520_w=42
>
> The reason relates to the compiler implementation. It appears that the
> shift exponent is taken modulo 64 before applying the shift, so after
> "slot = (1ULL << 64)", the value of slot becomes 1.
>
> Fix the UBSAN warning by extending the size of scratched_stack_slots
> from 64 bits to 128-bits.
>
> Fixes: 5b5f51bff1b6 ("bpf: no_caller_saved_registers attribute for helper calls")
> Signed-off-by: Hou Tao <houtao1@huawei.com>
> ---
>  include/linux/bpf_verifier.h | 20 +++++++++++++-------
>  1 file changed, 13 insertions(+), 7 deletions(-)
>
> diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> index 4513372c5bc8..1bb6c6def04d 100644
> --- a/include/linux/bpf_verifier.h
> +++ b/include/linux/bpf_verifier.h
> @@ -773,8 +773,11 @@ struct bpf_verifier_env {
>          * since the last time the function state was printed
>          */
>         u32 scratched_regs;
> -       /* Same as scratched_regs but for stack slots */
> -       u64 scratched_stack_slots;
> +       /* Same as scratched_regs but for stack slots. The stack size may
> +        * temporarily exceed MAX_BPF_STACK (e.g., due to fastcall pattern
> +        * in check_stack_slot_within_bounds()), so two u64 values are used.
> +        */
> +       u64 scratched_stack_slots[2];

We have other places where we assume that 64 bits is enough to specify
stack slot index (linked regs, for instance). Do we need to update all
of those now as well? If yes, maybe then it's better to make sure
valid programs can never go beyond 512 bytes of stack even for
bpf_fastcall?..

>         u64 prev_log_pos, prev_insn_print_pos;
>         /* buffer used to temporary hold constants as scalar registers */
>         struct bpf_reg_state fake_reg[2];
> @@ -939,7 +942,7 @@ static inline void mark_reg_scratched(struct bpf_verifier_env *env, u32 regno)
>
>  static inline void mark_stack_slot_scratched(struct bpf_verifier_env *env, u32 spi)
>  {
> -       env->scratched_stack_slots |= 1ULL << spi;
> +       env->scratched_stack_slots[spi / 64] |= 1ULL << (spi & 63);
>  }
>
>  static inline bool reg_scratched(const struct bpf_verifier_env *env, u32 regno)
> @@ -949,25 +952,28 @@ static inline bool reg_scratched(const struct bpf_verifier_env *env, u32 regno)
>
>  static inline bool stack_slot_scratched(const struct bpf_verifier_env *env, u64 regno)
>  {
> -       return (env->scratched_stack_slots >> regno) & 1;
> +       return (env->scratched_stack_slots[regno / 64] >> (regno & 63)) & 1;
>  }
>
>  static inline bool verifier_state_scratched(const struct bpf_verifier_env *env)
>  {
> -       return env->scratched_regs || env->scratched_stack_slots;
> +       return env->scratched_regs || env->scratched_stack_slots[0] ||
> +              env->scratched_stack_slots[1];
>  }
>
>  static inline void mark_verifier_state_clean(struct bpf_verifier_env *env)
>  {
>         env->scratched_regs = 0U;
> -       env->scratched_stack_slots = 0ULL;
> +       env->scratched_stack_slots[0] = 0ULL;
> +       env->scratched_stack_slots[1] = 0ULL;
>  }
>
>  /* Used for printing the entire verifier state. */
>  static inline void mark_verifier_state_scratched(struct bpf_verifier_env *env)
>  {
>         env->scratched_regs = ~0U;
> -       env->scratched_stack_slots = ~0ULL;
> +       env->scratched_stack_slots[0] = ~0ULL;
> +       env->scratched_stack_slots[1] = ~0ULL;
>  }
>
>  static inline bool bpf_stack_narrow_access_ok(int off, int fill_size, int spill_size)
> --
> 2.29.2
>

Re: [PATCH bpf] bpf: Extend the size of scratched_stack_slots to 128 bits

[Eduard Zingerman]

On Wed, 2024-10-23 at 09:15 -0700, Andrii Nakryiko wrote:

[...]

> > diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> > index 4513372c5bc8..1bb6c6def04d 100644
> > --- a/include/linux/bpf_verifier.h
> > +++ b/include/linux/bpf_verifier.h
> > @@ -773,8 +773,11 @@ struct bpf_verifier_env {
> >          * since the last time the function state was printed
> >          */
> >         u32 scratched_regs;
> > -       /* Same as scratched_regs but for stack slots */
> > -       u64 scratched_stack_slots;
> > +       /* Same as scratched_regs but for stack slots. The stack size may
> > +        * temporarily exceed MAX_BPF_STACK (e.g., due to fastcall pattern
> > +        * in check_stack_slot_within_bounds()), so two u64 values are used.
> > +        */
> > +       u64 scratched_stack_slots[2];
> 
> We have other places where we assume that 64 bits is enough to specify
> stack slot index (linked regs, for instance). Do we need to update all
> of those now as well? If yes, maybe then it's better to make sure
> valid programs can never go beyond 512 bytes of stack even for
> bpf_fastcall?..

Specifically function frames.
This is a huge blunder from my side.

Re: [PATCH bpf] bpf: Extend the size of scratched_stack_slots to 128 bits

[Eduard Zingerman]

On Wed, 2024-10-23 at 09:17 -0700, Eduard Zingerman wrote:

[...]

> > We have other places where we assume that 64 bits is enough to specify
> > stack slot index (linked regs, for instance). Do we need to update all
> > of those now as well? If yes, maybe then it's better to make sure
> > valid programs can never go beyond 512 bytes of stack even for
> > bpf_fastcall?..
> 
> Specifically function frames.
> This is a huge blunder from my side.

The following places are problematic:
- bpf_jmp_history_entry->flags
- backtrack_state->stack_masks

The following should be fine:
- bpf_func_state->stack

Not sure if anything else is affected (excluding scratched_stack_slots).

I agree that we either need to update backtracking logic,
or drop this stack extension logic.

Re: [PATCH bpf] bpf: Extend the size of scratched_stack_slots to 128 bits

[Andrii Nakryiko]

On Wed, Oct 23, 2024 at 10:13 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Wed, 2024-10-23 at 09:17 -0700, Eduard Zingerman wrote:
>
> [...]
>
> > > We have other places where we assume that 64 bits is enough to specify
> > > stack slot index (linked regs, for instance). Do we need to update all
> > > of those now as well? If yes, maybe then it's better to make sure
> > > valid programs can never go beyond 512 bytes of stack even for
> > > bpf_fastcall?..
> >
> > Specifically function frames.
> > This is a huge blunder from my side.
>
> The following places are problematic:
> - bpf_jmp_history_entry->flags
> - backtrack_state->stack_masks
>
> The following should be fine:
> - bpf_func_state->stack
>
> Not sure if anything else is affected (excluding scratched_stack_slots).
>
> I agree that we either need to update backtracking logic,
> or drop this stack extension logic.

Using two u64s to describe stack slot mask is really-really
inconvenient and increases memory usage by quite a lot. Given we
intend to have insn_history for each instruction soon, I'd keep stack
size at max of 512 bytes, even with bpf_fastcall. Is it possible?

Re: [PATCH bpf] bpf: Extend the size of scratched_stack_slots to 128 bits

[Eduard Zingerman]

On Wed, 2024-10-23 at 10:33 -0700, Andrii Nakryiko wrote:

[...]

> Using two u64s to describe stack slot mask is really-really
> inconvenient.

Yes

> and increases memory usage by quite a lot. Given we intend to have
> insn_history for each instruction soon, I'd keep stack size at max
> of 512 bytes, even with bpf_fastcall.

By 8mb for 1M instructions program.

> Is it possible?

If we drop this +40 bytes slack space everything else should work as
expected.

Re: [PATCH bpf] bpf: Extend the size of scratched_stack_slots to 128 bits

[Andrii Nakryiko]

On Wed, Oct 23, 2024 at 10:37 AM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Wed, 2024-10-23 at 10:33 -0700, Andrii Nakryiko wrote:
>
> [...]
>
> > Using two u64s to describe stack slot mask is really-really
> > inconvenient.
>
> Yes
>
> > and increases memory usage by quite a lot. Given we intend to have
> > insn_history for each instruction soon, I'd keep stack size at max
> > of 512 bytes, even with bpf_fastcall.
>
> By 8mb for 1M instructions program.
>
> > Is it possible?
>
> If we drop this +40 bytes slack space everything else should work as
> expected.

I'd be OK with that.

Re: [PATCH bpf] bpf: Extend the size of scratched_stack_slots to 128 bits

[Eduard Zingerman]

On Wed, 2024-10-23 at 10:44 -0700, Andrii Nakryiko wrote:

[...]

> > If we drop this +40 bytes slack space everything else should work as
> > expected.
> 
> I'd be OK with that.

Andrii, Hou,

Discussed this with Alexei off-list.
The decision is to drop the 40 bytes extension.
I'll send a patch today.