diff mbox series

[bpf-next,3/3] bpf: arraymap: Skip boundscheck during inlining when possible

Message ID 7bfb3b6b1d3400d03fd9b7a7e15586c826449c71.1737433945.git.dxu@dxuuu.xyz (mailing list archive)
State Changes Requested
Delegated to: BPF
Headers show
Series bpf: Omit inlined bounds checks for null elided map lookups | expand

Checks

Context Check Description
bpf/vmtest-bpf-next-PR success PR summary
bpf/vmtest-bpf-next-VM_Test-1 success Logs for ShellCheck
bpf/vmtest-bpf-next-VM_Test-2 success Logs for Unittests
bpf/vmtest-bpf-next-VM_Test-0 success Logs for Lint
bpf/vmtest-bpf-next-VM_Test-5 success Logs for aarch64-gcc / build-release
bpf/vmtest-bpf-next-VM_Test-3 success Logs for Validate matrix.py
bpf/vmtest-bpf-next-VM_Test-4 success Logs for aarch64-gcc / build / build for aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-10 success Logs for aarch64-gcc / veristat-kernel
bpf/vmtest-bpf-next-VM_Test-9 success Logs for aarch64-gcc / test (test_verifier, false, 360) / test_verifier on aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-11 success Logs for aarch64-gcc / veristat-meta
bpf/vmtest-bpf-next-VM_Test-12 success Logs for s390x-gcc / build / build for s390x with gcc
bpf/vmtest-bpf-next-VM_Test-17 success Logs for s390x-gcc / veristat-kernel
bpf/vmtest-bpf-next-VM_Test-16 success Logs for s390x-gcc / test (test_verifier, false, 360) / test_verifier on s390x with gcc
bpf/vmtest-bpf-next-VM_Test-18 success Logs for s390x-gcc / veristat-meta
bpf/vmtest-bpf-next-VM_Test-13 success Logs for s390x-gcc / build-release
bpf/vmtest-bpf-next-VM_Test-19 success Logs for set-matrix
bpf/vmtest-bpf-next-VM_Test-21 success Logs for x86_64-gcc / build-release
bpf/vmtest-bpf-next-VM_Test-32 success Logs for x86_64-llvm-17 / test (test_maps, false, 360) / test_maps on x86_64 with llvm-17
bpf/vmtest-bpf-next-VM_Test-35 success Logs for x86_64-llvm-17 / test (test_verifier, false, 360) / test_verifier on x86_64 with llvm-17
bpf/vmtest-bpf-next-VM_Test-37 success Logs for x86_64-llvm-17 / veristat-meta
bpf/vmtest-bpf-next-VM_Test-38 success Logs for x86_64-llvm-18 / build / build for x86_64 with llvm-18
bpf/vmtest-bpf-next-VM_Test-36 success Logs for x86_64-llvm-17 / veristat-kernel
bpf/vmtest-bpf-next-VM_Test-39 success Logs for x86_64-llvm-18 / build-release / build for x86_64 with llvm-18-O2
bpf/vmtest-bpf-next-VM_Test-40 success Logs for x86_64-llvm-18 / test (test_maps, false, 360) / test_maps on x86_64 with llvm-18
bpf/vmtest-bpf-next-VM_Test-44 success Logs for x86_64-llvm-18 / test (test_verifier, false, 360) / test_verifier on x86_64 with llvm-18
bpf/vmtest-bpf-next-VM_Test-45 success Logs for x86_64-llvm-18 / veristat-kernel
bpf/vmtest-bpf-next-VM_Test-46 success Logs for x86_64-llvm-18 / veristat-meta
bpf/vmtest-bpf-next-VM_Test-20 success Logs for x86_64-gcc / build / build for x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-30 success Logs for x86_64-llvm-17 / build / build for x86_64 with llvm-17
bpf/vmtest-bpf-next-VM_Test-27 success Logs for x86_64-gcc / test (test_verifier, false, 360) / test_verifier on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-28 success Logs for x86_64-gcc / veristat-kernel / x86_64-gcc veristat_kernel
bpf/vmtest-bpf-next-VM_Test-31 success Logs for x86_64-llvm-17 / build-release / build for x86_64 with llvm-17-O2
bpf/vmtest-bpf-next-VM_Test-6 success Logs for aarch64-gcc / test (test_maps, false, 360) / test_maps on aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-7 success Logs for aarch64-gcc / test (test_progs, false, 360) / test_progs on aarch64 with gcc
bpf/vmtest-bpf-next-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-next-VM_Test-34 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-next-VM_Test-33 success Logs for x86_64-llvm-17 / test (test_progs, false, 360) / test_progs on x86_64 with llvm-17
bpf/vmtest-bpf-next-VM_Test-41 success Logs for x86_64-llvm-18 / test (test_progs, false, 360) / test_progs on x86_64 with llvm-18
bpf/vmtest-bpf-next-VM_Test-43 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-next-VM_Test-42 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-next-VM_Test-23 success Logs for x86_64-gcc / test (test_progs, false, 360) / test_progs on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-25 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-next-VM_Test-29 success Logs for x86_64-gcc / veristat-meta / x86_64-gcc veristat_meta
bpf/vmtest-bpf-next-VM_Test-26 success Logs for x86_64-gcc / test (test_progs_parallel, true, 30) / test_progs_parallel on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-24 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-next-VM_Test-22 success Logs for x86_64-gcc / test (test_maps, false, 360) / test_maps on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-14 success Logs for s390x-gcc / test (test_progs, false, 360) / test_progs on s390x with gcc
bpf/vmtest-bpf-next-VM_Test-15 success Logs for s390x-gcc / test (test_progs_no_alu32, false, 360) / test_progs_no_alu32 on s390x with gcc
netdev/series_format success Posting correctly formatted
netdev/tree_selection success Clearly marked for bpf-next, async
netdev/ynl success Generated files up to date; no warnings/errors; no diff in generated;
netdev/fixes_present success Fixes tag not required for -next series
netdev/header_inline success No static functions without inline keyword in header files
netdev/build_32bit success Errors and warnings before: 1 this patch: 1
netdev/build_tools success No tools touched, skip
netdev/cc_maintainers success CCed 13 of 13 maintainers
netdev/build_clang success Errors and warnings before: 2 this patch: 2
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 No Fixes tag
netdev/build_allmodconfig_warn success Errors and warnings before: 1 this patch: 1
netdev/checkpatch warning WARNING: line length of 81 exceeds 80 columns WARNING: line length of 87 exceeds 80 columns
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

Commit Message

Daniel Xu Jan. 21, 2025, 4:35 a.m. UTC 
For regular arraymaps and percpu arraymaps, if the lookup is known to be
inbounds, the inlined bounds check can be omitted. One fewer jump puts less
pressure on the branch predictor. While it probably won't affect real
workloads much, we can basically get this for free. So might as well -
free wins are nice.

JIT diff for regular arraymap (x86-64):

     ; val = bpf_map_lookup_elem(&map_array, &key);
    -  22:   movabsq $-131387164803072, %rdi
    +  22:   movabsq $-131387246749696, %rdi
       2c:   addq    $472, %rdi
       33:   movl    (%rsi), %eax
    -  36:   cmpq    $2, %rax
    -  3a:   jae     0x45
    -  3c:   imulq   $48, %rax, %rax
    -  40:   addq    %rdi, %rax
    -  43:   jmp     0x47
    -  45:   xorl    %eax, %eax
    -  47:   movl    $4, %edi
    +  36:   imulq   $48, %rax, %rax
    +  3a:   addq    %rdi, %rax
    +  3d:   jmp     0x41
    +  3f:   xorl    %eax, %eax
    +  41:   movl    $4, %edi

JIT diff for percpu arraymap (x86-64):

     ; val = bpf_map_lookup_elem(&map_array_pcpu, &key);
    -  22:   movabsq $-131387183532032, %rdi
    +  22:   movabsq $-131387273779200, %rdi
       2c:   addq    $472, %rdi
       33:   movl    (%rsi), %eax
    -  36:   cmpq    $2, %rax
    -  3a:   jae     0x52
    -  3c:   shlq    $3, %rax
    -  40:   addq    %rdi, %rax
    -  43:   movq    (%rax), %rax
    -  47:   addq    %gs:170664, %rax
    -  50:   jmp     0x54
    -  52:   xorl    %eax, %eax
    -  54:   movl    $4, %edi
    +  36:   shlq    $3, %rax
    +  3a:   addq    %rdi, %rax
    +  3d:   movq    (%rax), %rax
    +  41:   addq    %gs:170664, %rax
    +  4a:   jmp     0x4e
    +  4c:   xorl    %eax, %eax
    +  4e:   movl    $4, %edi

Signed-off-by: Daniel Xu <dxu@dxuuu.xyz>
---
 kernel/bpf/arraymap.c | 24 ++++++++++++++----------
 1 file changed, 14 insertions(+), 10 deletions(-)

Comments

Eduard Zingerman Jan. 23, 2025, 12:15 a.m. UTC | #1 
On Mon, 2025-01-20 at 21:35 -0700, Daniel Xu wrote:

[...]

Hi Daniel,

> @@ -221,11 +221,13 @@ static int array_map_gen_lookup(struct bpf_map *map,
>  
>  	*insn++ = BPF_ALU64_IMM(BPF_ADD, map_ptr, offsetof(struct bpf_array, value));
>  	*insn++ = BPF_LDX_MEM(BPF_W, ret, index, 0);
> -	if (!map->bypass_spec_v1) {
> -		*insn++ = BPF_JMP_IMM(BPF_JGE, ret, map->max_entries, 4);
> -		*insn++ = BPF_ALU32_IMM(BPF_AND, ret, array->index_mask);
> -	} else {
> -		*insn++ = BPF_JMP_IMM(BPF_JGE, ret, map->max_entries, 3);
> +	if (!inbounds) {
> +		if (!map->bypass_spec_v1) {
> +			*insn++ = BPF_JMP_IMM(BPF_JGE, ret, map->max_entries, 4);
> +			*insn++ = BPF_ALU32_IMM(BPF_AND, ret, array->index_mask);
> +		} else {
> +			*insn++ = BPF_JMP_IMM(BPF_JGE, ret, map->max_entries, 3);
> +		}
>  	}
>  
>  	if (is_power_of_2(elem_size)) {

Note that below this hunk there is the following code:

	*insn++ = BPF_JMP_IMM(BPF_JA, 0, 0, 1);
	*insn++ = BPF_MOV64_IMM(ret, 0);
	return insn - insn_buf;

This part becomes redundant after your change. E.g. here is jit
listing for an_array_with_a_32bit_constant_0_no_nullness selftest:

JITED:
=============
func #0:
0:	f3 0f 1e fa                         	endbr64
4:	0f 1f 44 00 00                      	nopl	(%rax,%rax)
9:	0f 1f 00                            	nopl	(%rax)
c:	55                                  	pushq	%rbp
d:	48 89 e5                            	movq	%rsp, %rbp
10:	f3 0f 1e fa                         	endbr64
14:	48 81 ec 08 00 00 00                	subq	$0x8, %rsp
1b:	31 ff                               	xorl	%edi, %edi
1d:	89 7d fc                            	movl	%edi, -0x4(%rbp)
20:	48 89 ee                            	movq	%rbp, %rsi
23:	48 83 c6 fc                         	addq	$-0x4, %rsi
27:	48 bf 00 70 58 06 81 88 ff ff       	movabsq	$-0x777ef9a79000, %rdi
31:	48 81 c7 d8 01 00 00                	addq	$0x1d8, %rdi
38:	8b 46 00                            	movl	(%rsi), %eax
3b:	48 6b c0 30                         	imulq	$0x30, %rax, %rax
3f:	48 01 f8                            	addq	%rdi, %rax
42:	eb 02                               	jmp	L0             //
44:	31 c0                               	xorl	%eax, %eax     // never executed
46:	bf 04 00 00 00                      L0:	movl	$0x4, %edi     //
4b:	89 78 00                            	movl	%edi, (%rax)
4e:	b8 04 00 00 00                      	movl	$0x4, %eax
53:	c9                                  	leave
54:	e9 22 38 50 c3                      	jmp	0xffffffffc350387b

Also note that there are __arch_x86_64 and __jited tags for selftests.
These allow to match against disassembly of the generated binary code.
(See verifier_tailcall_jit.c for an example).
I think it would be good to add a test matching jited code for this feature.

[...]
Alexei Starovoitov Jan. 23, 2025, 12:33 a.m. UTC | #2 
On Mon, Jan 20, 2025 at 8:35 PM Daniel Xu <dxu@dxuuu.xyz> wrote:
>
> For regular arraymaps and percpu arraymaps, if the lookup is known to be
> inbounds, the inlined bounds check can be omitted. One fewer jump puts less
> pressure on the branch predictor. While it probably won't affect real
> workloads much, we can basically get this for free. So might as well -
> free wins are nice.
>
> JIT diff for regular arraymap (x86-64):
>
>      ; val = bpf_map_lookup_elem(&map_array, &key);
>     -  22:   movabsq $-131387164803072, %rdi
>     +  22:   movabsq $-131387246749696, %rdi
>        2c:   addq    $472, %rdi
>        33:   movl    (%rsi), %eax
>     -  36:   cmpq    $2, %rax
>     -  3a:   jae     0x45
>     -  3c:   imulq   $48, %rax, %rax
>     -  40:   addq    %rdi, %rax
>     -  43:   jmp     0x47
>     -  45:   xorl    %eax, %eax
>     -  47:   movl    $4, %edi
>     +  36:   imulq   $48, %rax, %rax
>     +  3a:   addq    %rdi, %rax
>     +  3d:   jmp     0x41
>     +  3f:   xorl    %eax, %eax
>     +  41:   movl    $4, %edi
>
> JIT diff for percpu arraymap (x86-64):
>
>      ; val = bpf_map_lookup_elem(&map_array_pcpu, &key);
>     -  22:   movabsq $-131387183532032, %rdi
>     +  22:   movabsq $-131387273779200, %rdi
>        2c:   addq    $472, %rdi
>        33:   movl    (%rsi), %eax
>     -  36:   cmpq    $2, %rax
>     -  3a:   jae     0x52
>     -  3c:   shlq    $3, %rax
>     -  40:   addq    %rdi, %rax
>     -  43:   movq    (%rax), %rax
>     -  47:   addq    %gs:170664, %rax
>     -  50:   jmp     0x54
>     -  52:   xorl    %eax, %eax
>     -  54:   movl    $4, %edi
>     +  36:   shlq    $3, %rax
>     +  3a:   addq    %rdi, %rax
>     +  3d:   movq    (%rax), %rax
>     +  41:   addq    %gs:170664, %rax
>     +  4a:   jmp     0x4e
>     +  4c:   xorl    %eax, %eax
>     +  4e:   movl    $4, %edi
>
> Signed-off-by: Daniel Xu <dxu@dxuuu.xyz>
> ---
>  kernel/bpf/arraymap.c | 24 ++++++++++++++----------
>  1 file changed, 14 insertions(+), 10 deletions(-)
>
> diff --git a/kernel/bpf/arraymap.c b/kernel/bpf/arraymap.c
> index 8dbdceeead95..7385104dc0d0 100644
> --- a/kernel/bpf/arraymap.c
> +++ b/kernel/bpf/arraymap.c
> @@ -221,11 +221,13 @@ static int array_map_gen_lookup(struct bpf_map *map,
>
>         *insn++ = BPF_ALU64_IMM(BPF_ADD, map_ptr, offsetof(struct bpf_array, value));
>         *insn++ = BPF_LDX_MEM(BPF_W, ret, index, 0);
> -       if (!map->bypass_spec_v1) {
> -               *insn++ = BPF_JMP_IMM(BPF_JGE, ret, map->max_entries, 4);
> -               *insn++ = BPF_ALU32_IMM(BPF_AND, ret, array->index_mask);
> -       } else {
> -               *insn++ = BPF_JMP_IMM(BPF_JGE, ret, map->max_entries, 3);
> +       if (!inbounds) {
> +               if (!map->bypass_spec_v1) {
> +                       *insn++ = BPF_JMP_IMM(BPF_JGE, ret, map->max_entries, 4);
> +                       *insn++ = BPF_ALU32_IMM(BPF_AND, ret, array->index_mask);
> +               } else {
> +                       *insn++ = BPF_JMP_IMM(BPF_JGE, ret, map->max_entries, 3);
> +               }
>         }

As stands this is not correct for !spec_v1.
Though the verifier confirmed that key is constant, it still
goes via load and math,
so there is a risk of speculation out of bounds.

All that will be non-issue if the actual const_map_key is
passed in and computed into single ld_imm64
(as suggested in the other email).

pw-bot: cr
diff mbox series

Patch

diff --git a/kernel/bpf/arraymap.c b/kernel/bpf/arraymap.c
index 8dbdceeead95..7385104dc0d0 100644
--- a/kernel/bpf/arraymap.c
+++ b/kernel/bpf/arraymap.c
@@ -221,11 +221,13 @@  static int array_map_gen_lookup(struct bpf_map *map,
 
 	*insn++ = BPF_ALU64_IMM(BPF_ADD, map_ptr, offsetof(struct bpf_array, value));
 	*insn++ = BPF_LDX_MEM(BPF_W, ret, index, 0);
-	if (!map->bypass_spec_v1) {
-		*insn++ = BPF_JMP_IMM(BPF_JGE, ret, map->max_entries, 4);
-		*insn++ = BPF_ALU32_IMM(BPF_AND, ret, array->index_mask);
-	} else {
-		*insn++ = BPF_JMP_IMM(BPF_JGE, ret, map->max_entries, 3);
+	if (!inbounds) {
+		if (!map->bypass_spec_v1) {
+			*insn++ = BPF_JMP_IMM(BPF_JGE, ret, map->max_entries, 4);
+			*insn++ = BPF_ALU32_IMM(BPF_AND, ret, array->index_mask);
+		} else {
+			*insn++ = BPF_JMP_IMM(BPF_JGE, ret, map->max_entries, 3);
+		}
 	}
 
 	if (is_power_of_2(elem_size)) {
@@ -269,11 +271,13 @@  static int percpu_array_map_gen_lookup(struct bpf_map *map,
 	*insn++ = BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, offsetof(struct bpf_array, pptrs));
 
 	*insn++ = BPF_LDX_MEM(BPF_W, BPF_REG_0, BPF_REG_2, 0);
-	if (!map->bypass_spec_v1) {
-		*insn++ = BPF_JMP_IMM(BPF_JGE, BPF_REG_0, map->max_entries, 6);
-		*insn++ = BPF_ALU32_IMM(BPF_AND, BPF_REG_0, array->index_mask);
-	} else {
-		*insn++ = BPF_JMP_IMM(BPF_JGE, BPF_REG_0, map->max_entries, 5);
+	if (!inbounds) {
+		if (!map->bypass_spec_v1) {
+			*insn++ = BPF_JMP_IMM(BPF_JGE, BPF_REG_0, map->max_entries, 6);
+			*insn++ = BPF_ALU32_IMM(BPF_AND, BPF_REG_0, array->index_mask);
+		} else {
+			*insn++ = BPF_JMP_IMM(BPF_JGE, BPF_REG_0, map->max_entries, 5);
+		}
 	}
 
 	*insn++ = BPF_ALU64_IMM(BPF_LSH, BPF_REG_0, 3);