diff mbox series

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

Message ID 20241023022752.172005-1-houtao@huaweicloud.com (mailing list archive)
State Changes Requested
Delegated to: BPF
Headers show
Series [bpf] bpf: Extend the size of scratched_stack_slots to 128 bits | expand

Checks

Context Check Description
bpf/vmtest-bpf-PR success PR summary
netdev/series_format success Single patches do not need cover letters
netdev/tree_selection success Clearly marked for bpf
netdev/ynl success Generated files up to date; no warnings/errors; no diff in generated;
netdev/fixes_present success Fixes tag present in non-next series
netdev/header_inline success No static functions without inline keyword in header files
netdev/build_32bit success Errors and warnings before: 5 this patch: 5
netdev/build_tools success Errors and warnings before: 157 (+0) this patch: 157 (+0)
netdev/cc_maintainers success CCed 12 of 13 maintainers
netdev/build_clang success Errors and warnings before: 3 this patch: 3
netdev/verify_signedoff success Signed-off-by tag matches author and committer
netdev/deprecated_api success None detected
netdev/check_selftest success No net selftest shell script
netdev/verify_fixes success Fixes tag looks correct
netdev/build_allmodconfig_warn success Errors and warnings before: 66 this patch: 66
netdev/checkpatch success total: 0 errors, 0 warnings, 0 checks, 53 lines checked
netdev/build_clang_rust success No Rust files in patch. Skipping build
netdev/kdoc success Errors and warnings before: 0 this patch: 0
netdev/source_inline success Was 0 now: 0
bpf/vmtest-bpf-VM_Test-0 success Logs for Lint
bpf/vmtest-bpf-VM_Test-1 success Logs for ShellCheck
bpf/vmtest-bpf-VM_Test-2 success Logs for Unittests
bpf/vmtest-bpf-VM_Test-3 success Logs for Validate matrix.py
bpf/vmtest-bpf-VM_Test-5 success Logs for aarch64-gcc / build-release
bpf/vmtest-bpf-VM_Test-4 success Logs for aarch64-gcc / build / build for aarch64 with gcc
bpf/vmtest-bpf-VM_Test-12 success Logs for s390x-gcc / build-release
bpf/vmtest-bpf-VM_Test-10 success Logs for aarch64-gcc / veristat
bpf/vmtest-bpf-VM_Test-6 success Logs for aarch64-gcc / test (test_maps, false, 360) / test_maps on aarch64 with gcc
bpf/vmtest-bpf-VM_Test-9 success Logs for aarch64-gcc / test (test_verifier, false, 360) / test_verifier on aarch64 with gcc
bpf/vmtest-bpf-VM_Test-7 success Logs for aarch64-gcc / test (test_progs, false, 360) / test_progs on aarch64 with gcc
bpf/vmtest-bpf-VM_Test-8 success Logs for aarch64-gcc / test (test_progs_no_alu32, false, 360) / test_progs_no_alu32 on aarch64 with gcc
bpf/vmtest-bpf-VM_Test-11 success Logs for s390x-gcc / build / build for s390x with gcc
bpf/vmtest-bpf-VM_Test-15 success Logs for s390x-gcc / test (test_verifier, false, 360) / test_verifier on s390x with gcc
bpf/vmtest-bpf-VM_Test-17 success Logs for set-matrix
bpf/vmtest-bpf-VM_Test-16 success Logs for s390x-gcc / veristat
bpf/vmtest-bpf-VM_Test-19 success Logs for x86_64-gcc / build-release
bpf/vmtest-bpf-VM_Test-18 success Logs for x86_64-gcc / build / build for x86_64 with gcc
bpf/vmtest-bpf-VM_Test-27 success Logs for x86_64-llvm-17 / build / build for x86_64 with llvm-17
bpf/vmtest-bpf-VM_Test-28 success Logs for x86_64-llvm-17 / build-release / build for x86_64 with llvm-17-O2
bpf/vmtest-bpf-VM_Test-33 success Logs for x86_64-llvm-17 / veristat
bpf/vmtest-bpf-VM_Test-34 success Logs for x86_64-llvm-18 / build / build for x86_64 with llvm-18
bpf/vmtest-bpf-VM_Test-35 success Logs for x86_64-llvm-18 / build-release / build for x86_64 with llvm-18-O2
bpf/vmtest-bpf-VM_Test-41 success Logs for x86_64-llvm-18 / veristat
bpf/vmtest-bpf-VM_Test-14 success Logs for s390x-gcc / test (test_progs_no_alu32, false, 360) / test_progs_no_alu32 on s390x with gcc
bpf/vmtest-bpf-VM_Test-13 success Logs for s390x-gcc / test (test_progs, false, 360) / test_progs on s390x with gcc
bpf/vmtest-bpf-VM_Test-20 success Logs for x86_64-gcc / test (test_maps, false, 360) / test_maps on x86_64 with gcc
bpf/vmtest-bpf-VM_Test-24 success Logs for x86_64-gcc / test (test_progs_parallel, true, 30) / test_progs_parallel on x86_64 with gcc
bpf/vmtest-bpf-VM_Test-25 success Logs for x86_64-gcc / test (test_verifier, false, 360) / test_verifier on x86_64 with gcc
bpf/vmtest-bpf-VM_Test-26 success Logs for x86_64-gcc / veristat / veristat on x86_64 with gcc
bpf/vmtest-bpf-VM_Test-32 success Logs for x86_64-llvm-17 / test (test_verifier, false, 360) / test_verifier on x86_64 with llvm-17
bpf/vmtest-bpf-VM_Test-21 success Logs for x86_64-gcc / test (test_progs, false, 360) / test_progs on x86_64 with gcc
bpf/vmtest-bpf-VM_Test-23 success Logs for x86_64-gcc / test (test_progs_no_alu32_parallel, true, 30) / test_progs_no_alu32_parallel on x86_64 with gcc
bpf/vmtest-bpf-VM_Test-22 success Logs for x86_64-gcc / test (test_progs_no_alu32, false, 360) / test_progs_no_alu32 on x86_64 with gcc
bpf/vmtest-bpf-VM_Test-31 success Logs for x86_64-llvm-17 / test (test_progs_no_alu32, false, 360) / test_progs_no_alu32 on x86_64 with llvm-17
bpf/vmtest-bpf-VM_Test-29 success Logs for x86_64-llvm-17 / test (test_maps, false, 360) / test_maps on x86_64 with llvm-17
bpf/vmtest-bpf-VM_Test-30 success Logs for x86_64-llvm-17 / test (test_progs, false, 360) / test_progs on x86_64 with llvm-17
bpf/vmtest-bpf-VM_Test-38 success Logs for x86_64-llvm-18 / test (test_progs_cpuv4, false, 360) / test_progs_cpuv4 on x86_64 with llvm-18
bpf/vmtest-bpf-VM_Test-36 success Logs for x86_64-llvm-18 / test (test_maps, false, 360) / test_maps on x86_64 with llvm-18
bpf/vmtest-bpf-VM_Test-39 success Logs for x86_64-llvm-18 / test (test_progs_no_alu32, false, 360) / test_progs_no_alu32 on x86_64 with llvm-18
bpf/vmtest-bpf-VM_Test-40 success Logs for x86_64-llvm-18 / test (test_verifier, false, 360) / test_verifier on x86_64 with llvm-18
bpf/vmtest-bpf-VM_Test-37 success Logs for x86_64-llvm-18 / test (test_progs, false, 360) / test_progs on x86_64 with llvm-18

Commit Message

Hou Tao Oct. 23, 2024, 2:27 a.m. UTC 
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(-)

Comments

Andrii Nakryiko Oct. 23, 2024, 4:15 p.m. UTC | #1 
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
>
Eduard Zingerman Oct. 23, 2024, 4:17 p.m. UTC | #2 
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.
Eduard Zingerman Oct. 23, 2024, 5:13 p.m. UTC | #3 
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.
Andrii Nakryiko Oct. 23, 2024, 5:33 p.m. UTC | #4 
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?
Eduard Zingerman Oct. 23, 2024, 5:37 p.m. UTC | #5 
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.
Andrii Nakryiko Oct. 23, 2024, 5:44 p.m. UTC | #6 
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.
Eduard Zingerman Oct. 23, 2024, 6:02 p.m. UTC | #7 
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.
diff mbox series

Patch

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)