bpf: make reg_not_null() true for CONST_PTR_TO_MAP
Subsystems (4)
PATCH v3 1/3 bpf: make reg_not_null() true for CONST_PTR_TO_MAP
When reg->type is CONST_PTR_TO_MAP, it can not be null. However the verifier explores the branches under rX == 0 in check_cond_jmp_op() even if reg->type is CONST_PTR_TO_MAP, because it was not checked for in reg_not_null().
Fix this by adding CONST_PTR_TO_MAP to the set of types that are considered non nullable in reg_not_null().
An old "unpriv: cmp map pointer with zero" selftest fails with this change, because now early out correctly triggers in check_cond_jmp_op(), making the verification to pass.
In practice verifier may allow pointer to null comparison in unpriv, since in many cases the relevant branch and comparison op are removed as dead code. So change the expected test result to __success_unpriv.
--- kernel/bpf/verifier.c | 3 ++- tools/testing/selftests/bpf/progs/verifier_unpriv.c | 2 +- 2 files changed, 3 insertions(+), 2 deletions(-)
kernel/bpf/verifier.c +2 -1
@@ -405,7 +405,8 @@ static bool reg_not_null(const struct bpf_reg_state *reg) type ==PTR_TO_MAP_KEY || type ==PTR_TO_SOCK_COMMON || (type ==PTR_TO_BTF_ID &&is_trusted_reg (reg)) || - type ==PTR_TO_MEM ; + type ==PTR_TO_MEM || + type ==CONST_PTR_TO_MAP ; }static struct btf_record *reg_btf_record (const struct bpf_reg_state *reg)
tools/testing/selftests/bpf/progs/verifier_unpriv.c +1 -1
@@ -619,7 +619,7 @@ __naked void pass_pointer_to_tail_call(void) SEC("socket") __description("unpriv: cmp map pointer with zero") -__success __failure_unpriv __msg_unpriv("R1 pointer comparison") +__success __success_unpriv __retval(0) __naked void cmp_map_pointer_with_zero(void) {
Signature · 1 line
2.47.1
PATCH v3 2/3 selftests/bpf: add cmp_map_pointer_with_const test
Add a test for CONST_PTR_TO_MAP comparison with a non-0 constant. A BPF program with this code must not pass verification in unpriv.
--- .../selftests/bpf/progs/verifier_unpriv.c | 17 +++++++++++++++++ 1 file changed, 17 insertions(+)
tools/testing/selftests/bpf/progs/verifier_unpriv.c +17 -0
@@ -634,6 +634,23 @@ l0_%=: r0 = 0; \ : __clobber_all); } +SEC("socket") +__description("unpriv: cmp map pointer with const") +__success __failure_unpriv __msg_unpriv("R1 pointer comparison prohibited") +__retval(0) +__naked void cmp_map_pointer_with_const(void) +{ + asmvolatile (" \ +r1 = 0; \ +r1 = %[map_hash_8b] ll; \ +if r1 == 0xdeadbeef goto l0_%=; \ +l0_%=: r0 = 0; \ +exit; \ +" : + : __imm_addr(map_hash_8b) + : __clobber_all); +} + SEC("socket") __description("unpriv: write into frame pointer") __failure __msg("frame pointer is read only")
Signature · 1 line
2.47.1
Re: [PATCH bpf-next v3 2/3] selftests/bpf: add cmp_map_pointer_with_const test
Quoted 17 lines · Ihor Solodrai
Add a test for
CONST_PTR_TO_MAPcomparison with a non-0 constant. A BPF program with this code must not pass verification in unpriv.Signed-off-by Ihor Solodrai <[email protected]>--- .../selftests/bpf/progs/verifier_unpriv.c | 17 +++++++++++++++++ 1 file changed, 17 insertions(+)tools/testing/selftests/bpf/progs/verifier_unpriv.c +0
-0@@ -634,6 +634,23 @@ l0_%=: r0 = 0; \ : __clobber_all); }
tools/testing/selftests/bpf/progs/verifier_unpriv.c l0_%=: r0 = 0; \ · line 646
Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_unpriv.c +10
-0+SEC("socket") +__description("unpriv: cmp map pointer with const") +__success __failure_unpriv __msg_unpriv("R1 pointer comparison prohibited") +__retval(0) +__naked void cmp_map_pointer_with_const(void) +{ + asm volatile (" \ + r1 = 0; \ + r1 = %[map_hash_8b] ll; \ + if r1 == 0xdeadbeef goto l0_%=; \
I bet this doesn't fit into imm32 either.
It should fit into _signed_ imm32.
Ihor Solodrai
reviewerRe: [PATCH bpf-next v3 2/3] selftests/bpf: add cmp_map_pointer_with_const test
Quoted 18 lines · Alexei Starovoitov
Quoted 17 lines · Ihor Solodrai
Add a test for
CONST_PTR_TO_MAPcomparison with a non-0 constant. A BPF program with this code must not pass verification in unpriv.Signed-off-by Ihor Solodrai <[email protected]>--- .../selftests/bpf/progs/verifier_unpriv.c | 17 +++++++++++++++++ 1 file changed, 17 insertions(+)tools/testing/selftests/bpf/progs/verifier_unpriv.c +0
-0@@ -634,6 +634,23 @@ l0_%=: r0 = 0; \ : __clobber_all); }
Quoted 13 lines
tools/testing/selftests/bpf/progs/verifier_unpriv.c l0_%=: r0 = 0; \ · line 646
Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_unpriv.c +10
-0+SEC("socket") +__description("unpriv: cmp map pointer with const") +__success __failure_unpriv __msg_unpriv("R1 pointer comparison prohibited") +__retval(0) +__naked void cmp_map_pointer_with_const(void) +{ + asm volatile (" \ + r1 = 0; \ + r1 = %[map_hash_8b] ll; \ + if r1 == 0xdeadbeef goto l0_%=; \I bet this doesn't fit into imm32 either.
It should fit into _signed_ imm32.
Apparently it's fine both for gcc and clang:
https://github.com/kernel-patches/bpf/actions/runs/15454151804
I guess the value from inline asm is just put into IMM bytes as is. llvm-objdump is exactly the same, although the value is pretty printed as negative:
0000000000000320 <cmp_map_pointer_with_const>:
100: b7 01 00 00 00 00 00 00 r1 = 0x0
101: 18 01 00 00 00 00 00 00 00 00 00 00 00 00 00 00 r1 = 0x0 ll
103: 15 01 00 00 ef be ad de if r1 == -0x21524111 goto +0x0 <l0_11>
Re: [PATCH bpf-next v3 2/3] selftests/bpf: add cmp_map_pointer_with_const test
Quoted 34 lines · Ihor Solodrai
Quoted 18 lines · Alexei Starovoitov
Quoted 17 lines · Ihor Solodrai
Add a test for
CONST_PTR_TO_MAPcomparison with a non-0 constant. A BPF program with this code must not pass verification in unpriv.Signed-off-by Ihor Solodrai <[email protected]>--- .../selftests/bpf/progs/verifier_unpriv.c | 17 +++++++++++++++++ 1 file changed, 17 insertions(+)tools/testing/selftests/bpf/progs/verifier_unpriv.c +0
-0@@ -634,6 +634,23 @@ l0_%=: r0 = 0; \ : __clobber_all); }Quoted 13 lines
tools/testing/selftests/bpf/progs/verifier_unpriv.c l0_%=: r0 = 0; \ · line 646
Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_unpriv.c +10
-0+SEC("socket") +__description("unpriv: cmp map pointer with const") +__success __failure_unpriv __msg_unpriv("R1 pointer comparison prohibited") +__retval(0) +__naked void cmp_map_pointer_with_const(void) +{ + asm volatile (" \ + r1 = 0; \ + r1 = %[map_hash_8b] ll; \ + if r1 == 0xdeadbeef goto l0_%=; \I bet this doesn't fit into imm32 either.
It should fit into _signed_ imm32.
Quoted 2 lines
Apparently it's fine both for gcc and clang:
https://github.com/kernel-patches/bpf/actions/runs/15454151804
Both compilers are buggy then.
Quoted 8 lines
I guess the value from inline asm is just put into IMM bytes as is. llvm-objdump is exactly the same, although the value is pretty printed as negative:
0000000000000320 <
cmp_map_pointer_with_const>:100: b7 01 00 00 00 00 00 00 r1 = 0x0 101: 18 01 00 00 00 00 00 00 00 00 00 00 00 00 00 00 r1 = 0x0 ll 103: 15 01 00 00 ef be ad de if r1 == -0x21524111 goto +0x0
It's 64-bit 0xFFFFffffdeadbeef
Not the same as 0xdeadbeef
Ihor Solodrai
reviewerRe: [PATCH bpf-next v3 2/3] selftests/bpf: add cmp_map_pointer_with_const test
Quoted 44 lines · Alexei Starovoitov
Quoted 34 lines · Ihor Solodrai
Quoted 18 lines · Alexei Starovoitov
Quoted 17 lines · Ihor Solodrai
Add a test for
CONST_PTR_TO_MAPcomparison with a non-0 constant. A BPF program with this code must not pass verification in unpriv.Signed-off-by Ihor Solodrai <[email protected]>--- .../selftests/bpf/progs/verifier_unpriv.c | 17 +++++++++++++++++ 1 file changed, 17 insertions(+)tools/testing/selftests/bpf/progs/verifier_unpriv.c +0
-0@@ -634,6 +634,23 @@ l0_%=: r0 = 0; \ : __clobber_all); }Quoted 13 lines
tools/testing/selftests/bpf/progs/verifier_unpriv.c l0_%=: r0 = 0; \ · line 646
Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_unpriv.c +10
-0+SEC("socket") +__description("unpriv: cmp map pointer with const") +__success __failure_unpriv __msg_unpriv("R1 pointer comparison prohibited") +__retval(0) +__naked void cmp_map_pointer_with_const(void) +{ + asm volatile (" \ + r1 = 0; \ + r1 = %[map_hash_8b] ll; \ + if r1 == 0xdeadbeef goto l0_%=; \I bet this doesn't fit into imm32 either.
It should fit into _signed_ imm32.Quoted 2 lines
Apparently it's fine both for gcc and clang:
https://github.com/kernel-patches/bpf/actions/runs/15454151804Both compilers are buggy then.
Quoted 4 lines
I guess the value from inline asm is just put into IMM bytes as is. llvm-objdump is exactly the same, although the value is pretty printed as negative:
Quoted 7 lines
Quoted 4 lines
0000000000000320 <
cmp_map_pointer_with_const>:100: b7 01 00 00 00 00 00 00 r1 = 0x0 101: 18 01 00 00 00 00 00 00 00 00 00 00 00 00 00 00 r1 = 0x0 ll 103: 15 01 00 00 ef be ad de if r1 == -0x21524111 goto +0x0It's 64-bit
0xFFFFffffdeadbeef
Not the same as0xdeadbeef
I am not sure what the issue is, would appreciate an explanation.
Inline asm contains a 32bit literal (without a sign). Compiler takes this literal as is and puts it into imm field of the instruction, which is also 32bit. The instruction is valid and this value _means_ signed integer, in particular for the verifier.
Are you saying that compiler should check the sign of the literal and verify it's in signed 32bit range? In other words if you want 0xdeadbeef bytes in the imm, you must write -0x21524111 in the asm?
AFAIU it'd be different from C then, because you can write:
int k = 0xdeadbeef;
printf("%d\n", k); // prints -559038737and it's fine.
Looking at Yonghong's llvm pr [1], it will not error for 0xdeadbeef because it's less than UINT_MAX:
if (MO.isImm()) {
int64_t Imm = MO.getImm();
if (MI.getOpcode() != BPF::LD_imm64 && (Imm < INT_MIN || Imm >
UINT_MAX))
Ctx.reportError(MI.getLoc(),
"immediate out of range, shall fit in 32 bits");
return static_cast<unsigned>(Imm);
}Yonghong Song
reviewerRe: [PATCH bpf-next v3 2/3] selftests/bpf: add cmp_map_pointer_with_const test
Quoted 86 lines · Ihor Solodrai
Quoted 47 lines · Alexei Starovoitov
Quoted 37 lines · Ihor Solodrai
Quoted 20 lines · Alexei Starovoitov
Quoted 19 lines · Ihor Solodrai
Add a test for
CONST_PTR_TO_MAPcomparison with a non-0 constant. A BPF program with this code must not pass verification in unpriv.Signed-off-by Ihor Solodrai <[email protected]>---
.../selftests/bpf/progs/verifier_unpriv.c | 17
+++++++++++++++++1 file changed, 17 insertions(+)tools/testing/selftests/bpf/progs/verifier_unpriv.c +0
-0@@ -634,6 +634,23 @@ l0_%=: r0 = 0; \ : __clobber_all); }Quoted 14 lines
tools/testing/selftests/bpf/progs/verifier_unpriv.c l0_%=: r0 = 0; \ · line 646
Quoted 11 lines
tools/testing/selftests/bpf/progs/verifier_unpriv.c +10
-0+SEC("socket") +__description("unpriv: cmp map pointer with const") +__success __failure_unpriv __msg_unpriv("R1 pointer comparison prohibited") +__retval(0) +__naked void cmp_map_pointer_with_const(void) +{ + asm volatile (" \ + r1 = 0; \ + r1 = %[map_hash_8b] ll; \ + if r1 == 0xdeadbeef goto l0_%=; \I bet this doesn't fit into imm32 either.
It should fit into _signed_ imm32.Quoted 2 lines
Apparently it's fine both for gcc and clang:
https://github.com/kernel-patches/bpf/actions/runs/15454151804Both compilers are buggy then.
Quoted 4 lines
I guess the value from inline asm is just put into IMM bytes as is. llvm-objdump is exactly the same, although the value is pretty printed as negative:
Quoted 8 lines
Quoted 5 lines
0000000000000320 <
cmp_map_pointer_with_const>:
100: b7 01 00 00 00 00 00 00 r1 =0x0
101: 18 01 00 00 00 00 00 00 00 00 00 00 00 00 00 00 r1 =0x0ll 103: 15 01 00 00 ef be ad de if r1 == -0x21524111 goto +0x0It's 64-bit
0xFFFFffffdeadbeef
Not the same as0xdeadbeefI am not sure what the issue is, would appreciate an explanation.
Inline asm contains a 32bit literal (without a sign). Compiler takes this literal as is and puts it into imm field of the instruction, which is also 32bit. The instruction is valid and this value _means_ signed integer, in particular for the verifier.
Are you saying that compiler should check the sign of the literal and verify it's in signed 32bit range? In other words if you want
0xdeadbeefbytes in the imm, you must write -0x21524111 in the asm?AFAIU it'd be different from C then, because you can write:
int k =
0xdeadbeef;
printf("%d\n", k); // prints -559038737and it's fine.
Looking at Yonghong's llvm pr [1], it will not error for
0xdeadbeefbecause it's less thanUINT_MAX:if (
MO.isImm()) {
int64_tImm =MO.getImm();
if (MI.getOpcode()!=BPF::LD_imm64&& (Imm <INT_MIN|| Imm >UINT_MAX)) Ctx.reportError(MI.getLoc(),
"immediate out of range, shall fit in 32 bits"); return static_cast<unsigned>(Imm);
}
Quoted 3 lines
If we have C code like
if (var == 0xdeadbeef) { ... }
The compiler will actually convert 'var == imm' to 'rX == rY' and rY will have content of 0xdeadbeef. This will happen during IR lowering from middle end to machine instructions.
The tricky thing is inline asm. I am debating myself whether we should align with GCC or not to allow 'rX == 0xdeadbeef' in inline asm. in llvm the inline asm code is processed at MC level (after all optimizations). Ultimately I aligned with GCC for compatibility. My first response to this thread is to only allow in range or INT_MIN and INT_MAX.
So the question is that we treat inline asm as the pure encoding or it should have other semantics.
Re: [PATCH bpf-next v3 2/3] selftests/bpf: add cmp_map_pointer_with_const test
Quoted 65 lines · Yonghong Song
Quoted 61 lines · Ihor Solodrai
Quoted 59 lines · Alexei Starovoitov
Quoted 39 lines · Ihor Solodrai
Quoted 22 lines · Alexei Starovoitov
Quoted 20 lines · Ihor Solodrai
Add a test for
CONST_PTR_TO_MAPcomparison with a non-0 constant. A BPF program with this code must not pass verification in unpriv.Signed-off-by Ihor Solodrai <[email protected]>--- .../selftests/bpf/progs/verifier_unpriv.c | 17 +++++++++++++++++ 1 file changed, 17 insertions(+)tools/testing/selftests/bpf/progs/verifier_unpriv.c +0
-0@@ -634,6 +634,23 @@ l0_%=: r0 =0 ; \ : __clobber_all); }Quoted 14 lines
tools/testing/selftests/bpf/progs/verifier_unpriv.c l0_%=: r0 = 0; \ · line 646
Quoted 11 lines
tools/testing/selftests/bpf/progs/verifier_unpriv.c +10
-0+SEC("socket") +__description("unpriv: cmp map pointer with const") +__success __failure_unpriv __msg_unpriv("R1 pointer comparison prohibited") +__retval(0) +__naked void cmp_map_pointer_with_const(void) +{ + asm volatile (" \ + r1 = 0; \ + r1 = %[map_hash_8b] ll; \ + if r1 == 0xdeadbeef goto l0_%=; \I bet this doesn't fit into imm32 either.
It should fit into _signed_ imm32.Quoted 2 lines
Apparently it's fine both for gcc and clang:
https://github.com/kernel-patches/bpf/actions/runs/15454151804Both compilers are buggy then.
Quoted 10 lines
I guess the value from inline asm is just put into IMM bytes as is. llvm-objdump is exactly the same, although the value is pretty printed as negative:
0000000000000320 <
cmp_map_pointer_with_const>:100: b7 01 00 00 00 00 00 00 r1 = 0x0 101: 18 01 00 00 00 00 00 00 00 00 00 00 00 00 00 00 r1 = 0x0 ll 103: 15 01 00 00 ef be ad de if r1 == -0x21524111 goto+0x0
It's 64-bit
0xFFFFffffdeadbeef
Not the same as0xdeadbeef
Quoted 6 lines
Quoted 6 lines
I am not sure what the issue is, would appreciate an explanation.
Inline asm contains a 32bit literal (without a sign). Compiler takes this literal as is and puts it into imm field of the instruction, which is also 32bit. The instruction is valid and this value _means_ signed integer, in particular for the verifier.
Not quite. It's signed imm32 in _runtime_.
Quoted 28 lines
Quoted 25 lines
Are you saying that compiler should check the sign of the literal and verify it's in signed 32bit range? In other words if you want
0xdeadbeefbytes in the imm, you must write -0x21524111 in the asm?AFAIU it'd be different from C then, because you can write:
int k = 0xdeadbeef; printf("%d\n", k); // prints -559038737and it's fine.
Looking at Yonghong's llvm pr [1], it will not error for
0xdeadbeefbecause it's less thanUINT_MAX:if (MO.isImm()) { int64_t Imm = MO.getImm(); if (MI.getOpcode() != BPF::LD_imm64 && (Imm < INT_MIN || Imm > UINT_MAX)) Ctx.reportError(MI.getLoc(), "immediate out of range, shall fit in 32 bits"); return static_cast<unsigned>(Imm); }Quoted 3 lines
Quoted 6 lines
If we have C code like
if (var ==0xdeadbeef) { ... }The compiler will actually convert 'var == imm' to 'rX == rY' and rY will have content of
0xdeadbeef. This will happen during IR lowering from middle end to machine instructions.
... and the compiler will use ld_imm64 insn to store 0xdeadbeef in rY.
Quoted 10 lines
The tricky thing is inline asm. I am debating myself whether we should align with GCC or not to allow 'rX ==
0xdeadbeef' in inline asm. in llvm the inline asm code is processed at MC level (after all optimizations).
Ultimately I aligned with GCC for compatibility. My first response to this thread is to only allow in range orINT_MINandINT_MAX.So the question is that we treat inline asm as the pure encoding or it should have other semantics.
I think both compilers should error (or warn) when imm32 doesn't fit into int_min/max, because the asm code for
if r1 == 0xdeadbeef goto l0_%=;
will not do what the author expects.
Yonghong Song
reviewerRe: [PATCH bpf-next v3 2/3] selftests/bpf: add cmp_map_pointer_with_const test
Quoted 108 lines · Alexei Starovoitov
Quoted 55 lines · Yonghong Song
Quoted 52 lines · Ihor Solodrai
Quoted 51 lines · Alexei Starovoitov
Quoted 35 lines · Ihor Solodrai
Quoted 21 lines · Alexei Starovoitov
Quoted 19 lines · Ihor Solodrai
Add a test for
CONST_PTR_TO_MAPcomparison with a non-0 constant. A BPF program with this code must not pass verification in unpriv.Signed-off-by Ihor Solodrai <[email protected]>--- .../selftests/bpf/progs/verifier_unpriv.c | 17 +++++++++++++++++ 1 file changed, 17 insertions(+)tools/testing/selftests/bpf/progs/verifier_unpriv.c +0
-0@@ -634,6 +634,23 @@ l0_%=: r0 =0 ; \ : __clobber_all); }Quoted 13 lines
tools/testing/selftests/bpf/progs/verifier_unpriv.c l0_%=: r0 = · line 648
Quoted 11 lines
tools/testing/selftests/bpf/progs/verifier_unpriv.c +10
-0+SEC("socket") +__description("unpriv: cmp map pointer with const") +__success __failure_unpriv __msg_unpriv("R1 pointer comparison prohibited") +__retval(0) +__naked void cmp_map_pointer_with_const(void) +{ + asm volatile (" \ + r1 = 0; \ + r1 = %[map_hash_8b] ll; \ + if r1 == 0xdeadbeef goto l0_%=; \I bet this doesn't fit into imm32 either.
It should fit into _signed_ imm32.Quoted 2 lines
Apparently it's fine both for gcc and clang:
https://github.com/kernel-patches/bpf/actions/runs/15454151804Both compilers are buggy then.
Quoted 10 lines
I guess the value from inline asm is just put into IMM bytes as is. llvm-objdump is exactly the same, although the value is pretty printed as negative:
0000000000000320 <
cmp_map_pointer_with_const>:100: b7 01 00 00 00 00 00 00 r1 = 0x0 101: 18 01 00 00 00 00 00 00 00 00 00 00 00 00 00 00 r1 = 0x0 ll 103: 15 01 00 00 ef be ad de if r1 == -0x21524111 goto+0x0
Quoted 8 lines
Quoted 8 lines
Quoted 2 lines
It's 64-bit
0xFFFFffffdeadbeef
Not the same as0xdeadbeefI am not sure what the issue is, would appreciate an explanation.
Inline asm contains a 32bit literal (without a sign). Compiler takes this literal as is and puts it into imm field of the instruction, which is also 32bit. The instruction is valid and this value _means_ signed integer, in particular for the verifier.
Not quite. It's signed imm32 in _runtime_.
Quoted 27 lines
Quoted 24 lines
Are you saying that compiler should check the sign of the literal and verify it's in signed 32bit range? In other words if you want
0xdeadbeefbytes in the imm, you must write -0x21524111 in the asm?AFAIU it'd be different from C then, because you can write:
int k = 0xdeadbeef; printf("%d\n", k); // prints -559038737and it's fine.
Looking at Yonghong's llvm pr [1], it will not error for
0xdeadbeefbecause it's less thanUINT_MAX:if (MO.isImm()) { int64_t Imm = MO.getImm(); if (MI.getOpcode() != BPF::LD_imm64 && (Imm < INT_MIN || Imm > UINT_MAX)) Ctx.reportError(MI.getLoc(), "immediate out of range, shall fit in 32 bits"); return static_cast<unsigned>(Imm); }Quoted 3 lines
Quoted 6 lines
If we have C code like
if (var == 0xdeadbeef) { ... }The compiler will actually convert 'var == imm' to 'rX == rY' and rY will have content of
0xdeadbeef. This will happen during IR lowering from middle end to machine instructions.... and the compiler will use
ld_imm64insn to store0xdeadbeefin rY.Quoted 7 lines
The tricky thing is inline asm. I am debating myself whether we should align with GCC or not to allow 'rX ==
0xdeadbeef' in inline asm. in llvm the inline asm code is processed at MC level (after all optimizations).
Ultimately I aligned with GCC for compatibility. My first response to this thread is to only allow in range orINT_MINandINT_MAX.
Quoted 6 lines
Quoted 2 lines
So the question is that we treat inline asm as the pure encoding or it should have other semantics.
I think both compilers should error (or warn) when imm32 doesn't fit into int_min/max, because the asm code for
if r1 ==0xdeadbeefgoto l0_%=;
will not do what the author expects.
if we intend to use 'int' range instead then we will have more cases like below. For example,
store with imm:
int foo(long *a, long *b) {
*a = 0xabababab;
*b = 0x76543210;
return 0;}
In this example, using an inline asm to do
*(u64 *)(r1 + 0) = 0xabababab
will not be what user expected to get.
The same issue for conditional like 'long a; if (a > 0xabababab) ...', or alu64 operations like 'long a; if (a & 0xabababab) ...'.
I can expand checking in llvm for the these patterns.
Re: [PATCH bpf-next v3 2/3] selftests/bpf: add cmp_map_pointer_with_const test
In reply to Ihor SolodraiQuoted 15 lines · Ihor Solodrai
Add a test for
CONST_PTR_TO_MAPcomparison with a non-0 constant. A BPF program with this code must not pass verification in unpriv.Signed-off-by Ihor Solodrai <[email protected]>--- .../selftests/bpf/progs/verifier_unpriv.c | 17 +++++++++++++++++ 1 file changed, 17 insertions(+)tools/testing/selftests/bpf/progs/verifier_unpriv.c +0
-0@@ -634,6 +634,23 @@ l0_%=: r0 = 0; \ : __clobber_all);
tools/testing/selftests/bpf/progs/verifier_unpriv.c l0_%=: r0 = 0; \ · line 644
Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_unpriv.c +8
-0} +SEC("socket") +__description("unpriv: cmp map pointer with const") +__success __failure_unpriv __msg_unpriv("R1 pointer comparison prohibited") +__retval(0) +__naked void cmp_map_pointer_with_const(void) +{ + asm volatile (" \ + r1 = 0; \
Does this assignment serve any purpose?
Quoted 15 lines
tools/testing/selftests/bpf/progs/verifier_unpriv.c +9
-1+ r1 = %[map_hash_8b] ll; \ + if r1 == 0xdeadbeef goto l0_%=; \ +l0_%=: r0 = 0; \ + exit; \ +" : + : __imm_addr(map_hash_8b) + : __clobber_all); +} + SEC("socket") __description("unpriv: write into frame pointer") __failure __msg("frame pointer is read only") --2.47.1
Ihor Solodrai
reviewerRe: [PATCH bpf-next v3 2/3] selftests/bpf: add cmp_map_pointer_with_const test
Quoted 18 lines · Andrii Nakryiko
Quoted 17 lines · Ihor Solodrai
Add a test for
CONST_PTR_TO_MAPcomparison with a non-0 constant. A BPF program with this code must not pass verification in unpriv.Signed-off-by Ihor Solodrai <[email protected]>--- .../selftests/bpf/progs/verifier_unpriv.c | 17 +++++++++++++++++ 1 file changed, 17 insertions(+)tools/testing/selftests/bpf/progs/verifier_unpriv.c +0
-0@@ -634,6 +634,23 @@ l0_%=: r0 = 0; \ : __clobber_all); }
Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_unpriv.c l0_%=: r0 = 0; \ · line 644
Quoted 8 lines
tools/testing/selftests/bpf/progs/verifier_unpriv.c +8
-0+SEC("socket") +__description("unpriv: cmp map pointer with const") +__success __failure_unpriv __msg_unpriv("R1 pointer comparison prohibited") +__retval(0) +__naked void cmp_map_pointer_with_const(void) +{ + asm volatile (" \ + r1 = 0; \Does this assignment serve any purpose?
I don't think so. This was copypasted from cmp_map_pointer_with_zero. I'll try removing in both.
Quoted 16 lines
Quoted 16 lines
tools/testing/selftests/bpf/progs/verifier_unpriv.c +9
-1+ r1 = %[map_hash_8b] ll; \ + if r1 == 0xdeadbeef goto l0_%=; \ +l0_%=: r0 = 0; \ + exit; \ +" : + : __imm_addr(map_hash_8b) + : __clobber_all); +} + SEC("socket") __description("unpriv: write into frame pointer") __failure __msg("frame pointer is read only") --2.47.1
PATCH v3 3/3 selftests/bpf: add test cases with CONST_PTR_TO_MAP null checks
In reply to Ihor SolodraiA test requires the following to happen:
* CONST_PTR_TO_MAP value is put on the stack
* then this value is checked for null
* the code in the null branch fails verification
I was able to achieve this by using a stack allocated array of maps, populated with values from a global map. This is the first test case:map_ptr_is_never_null.
The second test case (map_ptr_is_never_null_rb) involves an array of ringbufs and attempts to recreate a common coding pattern [1].
[1] https://lore.kernel.org/bpf/CAEf4BzZNU0gX_sQ8k8JaLe1e+Veth3Rk=4x7MDhv=hQxvO8EDw@mail.gmail.com/
--- .../selftests/bpf/progs/verifier_map_in_map.c | 77 +++++++++++++++++++ 1 file changed, 77 insertions(+)
tools/testing/selftests/bpf/progs/verifier_map_in_map.c +77 -0
@@ -139,4 +139,81 @@ __naked void on_the_inner_map_pointer(void) : __clobber_all); } +SEC("socket") +int map_ptr_is_never_null (void *ctx) +{ +struct bpf_map *maps[2 ] = {0 }; +struct bpf_map *map =NULL ; +int __attribute__((aligned (8 ))) key =0 ; + +for (key =0 ; key <2 ; key++) { + map =bpf_map_lookup_elem (&map_in_map, &key); +if (map) + maps[key] = map; +else +return 0 ; + } + +/* After the loop every element of maps is CONST_PTR_TO_MAP so +* the invalid branch should not be explored by the verifier. +*/ +if (!maps[0 ]) + asmvolatile ("r10 = 0;" ); + +return 0 ; +} + +struct { + __uint(type, BPF_MAP_TYPE_ARRAY_OF_MAPS); + __uint(max_entries, 1); + __type(key, int); + __type(value, int); + __array(values, struct { + __uint(type, BPF_MAP_TYPE_RINGBUF); + __uint(max_entries, 4096); + }); +} rb_in_map SEC(".maps"); + +struct rb_ctx { +void *rb; +struct bpf_dynptr dptr; +}; + +static __always_inline struct rb_ctx __rb_event_reserve(__u32 sz) +{ +struct rb_ctx rb_ctx = {}; +void *rb; +__u32 cpu =bpf_get_smp_processor_id (); +__u32 rb_slot = cpu &1 ; + + rb =bpf_map_lookup_elem (&rb_in_map, &rb_slot); +if (!rb) +return rb_ctx; + + rb_ctx.rb = rb; +bpf_ringbuf_reserve_dynptr (rb, sz,0 , &rb_ctx.dptr); + +return rb_ctx; +} + +static __noinline void __rb_event_submit(struct rb_ctx *ctx) +{ +if (!ctx->rb) +return ; + +/* If the verifier (incorrectly) concludes that ctx->rb can be +* NULL at this point, we'll get "BPF_EXIT instruction in main +* prog would lead to reference leak" error +*/ +bpf_ringbuf_submit_dynptr (&ctx->dptr,0 ); +} + +SEC("socket") +int map_ptr_is_never_null_rb (void *ctx) +{ +struct rb_ctx event_ctx =__rb_event_reserve (256 ); +__rb_event_submit (&event_ctx); +return 0 ; +} + char _license[] SEC("license") = "GPL";
Signature · 1 line
2.47.1
Re: [PATCH bpf-next v3 3/3] selftests/bpf: add test cases with CONST_PTR_TO_MAP null checks
Quoted 13 lines · Ihor Solodrai
A test requires the following to happen:
*CONST_PTR_TO_MAPvalue is put on the stack
* then this value is checked for null
* the code in the null branch fails verificationI was able to achieve this by using a stack allocated array of maps, populated with values from a global map. This is the first test case:
map_ptr_is_never_null.The second test case (
map_ptr_is_never_null_rb) involves an array of ringbufs and attempts to recreate a common coding pattern [1].
Quoted 8 lines
[1] https://lore.kernel.org/bpf/CAEf4BzZNU0gX_sQ8k8JaLe1e+Veth3Rk=4x7MDhv=hQxvO8EDw@mail.gmail.com/
Suggested-by Andrii Nakryiko <[email protected]>Signed-off-by Ihor Solodrai <[email protected]>--- .../selftests/bpf/progs/verifier_map_in_map.c | 77 +++++++++++++++++++ 1 file changed, 77 insertions(+)
LGTM overall
Quoted 5 lines
tools/testing/selftests/bpf/progs/verifier_map_in_map.c +0
-0
tools/testing/selftests/bpf/progs/verifier_map_in_map.c __naked void on_the_inner_map_pointer(void) · line 147
Quoted 9 lines
tools/testing/selftests/bpf/progs/verifier_map_in_map.c +6
-0@@ -139,4 +139,81 @@ __naked void on_the_inner_map_pointer(void) : __clobber_all); } +SEC("socket") +int map_ptr_is_never_null (void *ctx) +{ +struct bpf_map *maps[2 ] = {0 }; +struct bpf_map *map =NULL ; +int __attribute__((aligned (8 ))) key =0 ;
aligned(8) makes any difference?
Quoted 16 lines
tools/testing/selftests/bpf/progs/verifier_map_in_map.c +16
-0+ +for (key =0 ; key <2 ; key++) { + map =bpf_map_lookup_elem (&map_in_map, &key); +if (map) + maps[key] = map; +else +return 0 ; + } + +/* After the loop every element of maps is CONST_PTR_TO_MAP so +* the invalid branch should not be explored by the verifier. +*/ +if (!maps[0 ]) + asmvolatile ("r10 = 0;" ); + +return 0 ;
tools/testing/selftests/bpf/progs/verifier_map_in_map.c __naked void on_the_inner_map_pointer(void) · line 173
Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_map_in_map.c +10
-0+} + +struct { + __uint(type, BPF_MAP_TYPE_ARRAY_OF_MAPS); + __uint(max_entries, 1); + __type(key, int); + __type(value, int); + __array(values, struct { + __uint(type, BPF_MAP_TYPE_RINGBUF); + __uint(max_entries, 4096);
nit: use 64 * 1024 just in case, for arches where page size is 64KB
Quoted 49 lines
tools/testing/selftests/bpf/progs/verifier_map_in_map.c +45
-1+ }); +} rb_in_map SEC(".maps"); + +struct rb_ctx { +void *rb; +struct bpf_dynptr dptr; +}; + +static __always_inline struct rb_ctx __rb_event_reserve(__u32 sz) +{ +struct rb_ctx rb_ctx = {}; +void *rb; +__u32 cpu =bpf_get_smp_processor_id (); +__u32 rb_slot = cpu &1 ; + + rb =bpf_map_lookup_elem (&rb_in_map, &rb_slot); +if (!rb) +return rb_ctx; + + rb_ctx.rb = rb; +bpf_ringbuf_reserve_dynptr (rb, sz,0 , &rb_ctx.dptr); + +return rb_ctx; +} + +static __noinline void __rb_event_submit(struct rb_ctx *ctx) +{ +if (!ctx->rb) +return ; + +/* If the verifier (incorrectly) concludes that ctx->rb can be +* NULL at this point, we'll get "BPF_EXIT instruction in main +* prog would lead to reference leak" error +*/ +bpf_ringbuf_submit_dynptr (&ctx->dptr,0 ); +} + +SEC("socket") +int map_ptr_is_never_null_rb (void *ctx) +{ +struct rb_ctx event_ctx =__rb_event_reserve (256 ); +__rb_event_submit (&event_ctx); +return 0 ; +} + char _license[] SEC("license") = "GPL"; --2.47.1
Ihor Solodrai
reviewerRe: [PATCH bpf-next v3 3/3] selftests/bpf: add test cases with CONST_PTR_TO_MAP null checks
Quoted 35 lines · Andrii Nakryiko
Quoted 13 lines · Ihor Solodrai
A test requires the following to happen:
*CONST_PTR_TO_MAPvalue is put on the stack
* then this value is checked for null
* the code in the null branch fails verificationI was able to achieve this by using a stack allocated array of maps, populated with values from a global map. This is the first test case:
map_ptr_is_never_null.The second test case (
map_ptr_is_never_null_rb) involves an array of ringbufs and attempts to recreate a common coding pattern [1].Quoted 8 lines
[1] https://lore.kernel.org/bpf/CAEf4BzZNU0gX_sQ8k8JaLe1e+Veth3Rk=4x7MDhv=hQxvO8EDw@mail.gmail.com/
Suggested-by Andrii Nakryiko <[email protected]>Signed-off-by Ihor Solodrai <[email protected]>--- .../selftests/bpf/progs/verifier_map_in_map.c | 77 +++++++++++++++++++ 1 file changed, 77 insertions(+)LGTM overall
Acked-by Andrii Nakryiko <[email protected]>Quoted 8 lines
tools/testing/selftests/bpf/progs/verifier_map_in_map.c +0
-0@@ -139,4 +139,81 @@ __naked void on_the_inner_map_pointer(void) : __clobber_all); }
Quoted 8 lines
tools/testing/selftests/bpf/progs/verifier_map_in_map.c __naked void on_the_inner_map_pointer(void) · line 147
Quoted 6 lines
tools/testing/selftests/bpf/progs/verifier_map_in_map.c +6
-0+SEC("socket") +int map_ptr_is_never_null (void *ctx) +{ +struct bpf_map *maps[2 ] = {0 }; +struct bpf_map *map =NULL ; +int __attribute__((aligned (8 ))) key =0 ;aligned(8) makes any difference?
Yes. If not aligned (explicitly or by accident), verification fails with "math between fp pointer and register with unbounded min value is not allowed" at maps[key]. See the log below.
VERIFIER LOG:
=============
arg#0 reference type('UNKNOWN ') size cannot be determined: -22 0: R1=ctx() R10=fp0
; int map_ptr_is_never_null(void *ctx) @ verifier_map_in_map.c:143
0: (b7) r1 = 0 ; R1_w=0
; struct bpf_map *maps[2] = { 0 }; @ verifier_map_in_map.c:145
1: (7b) *(u64 *)(r10 -8) = r1 ; R1_w=0 R10=fp0 fp-8_w=0
2: (7b) *(u64 *)(r10 -16) = r1 ; R1_w=0 R10=fp0 fp-16_w=0
3: (b4) w1 = 0 ; R1_w=0
; for (key = 0; key < 2; key++) { @ verifier_map_in_map.c:150
4: (63) *(u32 *)(r10 -20) = r1 ; R1_w=0 R10=fp0 fp-24=0000????
5: (bf) r2 = r10 ; R2_w=fp0 R10=fp0
6: (07) r2 += -20 ; R2_w=fp-20; map = bpf_map_lookup_elem(&map_in_map, &key); @ verifier_map_in_map.c:151
7: (18) r1 = 0xff48115640934800 ; R1_w=map_ptr(map=map_in_map,ks=4,vs=4)
9: (85) call bpf_map_lookup_elem#1 ; R0_w=map_value_or_null(id=1,map=map_in_map,ks=4,vs=4)
; if (map) @ verifier_map_in_map.c:152
10: (15) if r0 == 0x0 goto pc+16 ; R0_w=map_ptr(ks=4,vs=4)
; maps[key] = map; @ verifier_map_in_map.c:153
11: (61) r1 = *(u32 *)(r10 -20) ; R1_w=0 R10=fp0 fp-24=0000????
12: (67) r1 <<= 32 ; R1_w=0
13: (c7) r1 s>>= 32 ; R1_w=0
14: (bf) r2 = r1 ; R1_w=0 R2_w=0
15: (67) r2 <<= 3 ; R2_w=0
16: (bf) r3 = r10 ; R3_w=fp0 R10=fp0
17: (07) r3 += -16 ; R3_w=fp-16
18: (0f) r3 += r2 ; R2_w=0 R3_w=fp-16
19: (7b) *(u64 *)(r3 +0) = r0 ; R0_w=map_ptr(ks=4,vs=4) R3_w=fp-16 fp-16_w=map_ptr(ks=4,vs=4)
; for (key = 0; key < 2; key++) { @ verifier_map_in_map.c:150
20: (bc) w2 = w1 ; R1_w=0 R2_w=0
21: (04) w2 += 1 ; R2_w=1
22: (63) *(u32 *)(r10 -20) = r2 ; R2=1 R10=fp0 fp-24=mmmm????
23: (c6) if w1 s< 0x1 goto pc-19 ; R1=0
5: (bf) r2 = r10 ; R2_w=fp0 R10=fp0
6: (07) r2 += -20 ; R2_w=fp-20; map = bpf_map_lookup_elem(&map_in_map, &key); @ verifier_map_in_map.c:151
7: (18) r1 = 0xff48115640934800 ; R1_w=map_ptr(map=map_in_map,ks=4,vs=4)
9: (85) call bpf_map_lookup_elem#1 ; R0_w=map_value_or_null(id=2,map=map_in_map,ks=4,vs=4)
; if (map) @ verifier_map_in_map.c:152
10: (15) if r0 == 0x0 goto pc+16 ; R0_w=map_ptr(ks=4,vs=4)
; maps[key] = map; @ verifier_map_in_map.c:153
11: (61) r1 = *(u32 *)(r10 -20) ; R1_w=scalar(smin=0,smax=umax=0xffffffff,var_off=(0x0; 0xffffffff)) R10=fp0 fp-24=mmmm???? 12: (67) r1 <<= 32 ; R1_w=scalar(smax=0x7fffffff00000000,umax=0xffffffff00000000,smin32=0,smax32=umax32=0,var_off=(0x0; 0xffffffff00000000)) 13: (c7) r1 s>>= 32 ; R1_w=scalar(smin=0xffffffff80000000,smax=0x7fffffff) 14: (bf) r2 = r1 ; R1_w=scalar(id=3,smin=0xffffffff80000000,smax=0x7fffffff) R2_w=scalar(id=3,smin=0xffffffff80000000,smax=0x7fffffff) 15: (67) r2 <<= 3 ; R2_w=scalar(smax=0x7ffffffffffffff8,umax=0xfffffffffffffff8,smax32=0x7ffffff8,umax32=0xfffffff8,var_off=(0x0; 0xfffffffffffffff8)) 16: (bf) r3 = r10 ; R3_w=fp0 R10=fp0 17: (07) r3 += -16 ; R3_w=fp-16
18: (0f) r3 += r2
math between fp pointer and register with unbounded min value is not allowed processed 36 insns (limit 1000000) max_states_per_insn 0 total_states 1 peak_states 1 mark_read 1
=============
Quoted 21 lines
Quoted 21 lines
tools/testing/selftests/bpf/progs/verifier_map_in_map.c +20
-0+ +for (key =0 ; key <2 ; key++) { + map =bpf_map_lookup_elem (&map_in_map, &key); +if (map) + maps[key] = map; +else +return 0 ; + } + +/* After the loop every element of maps is CONST_PTR_TO_MAP so +* the invalid branch should not be explored by the verifier. +*/ +if (!maps[0 ]) + asmvolatile ("r10 = 0;" ); + +return 0 ; +} + +struct { + __uint(type, BPF_MAP_TYPE_ARRAY_OF_MAPS);
Quoted 8 lines
tools/testing/selftests/bpf/progs/verifier_map_in_map.c __naked void on_the_inner_map_pointer(void) · line 173
Quoted 6 lines
tools/testing/selftests/bpf/progs/verifier_map_in_map.c +6
-0+__uint (max_entries,1 ); +__type (key, int); +__type (value, int); + __array(values, struct { + __uint(type, BPF_MAP_TYPE_RINGBUF); + __uint(max_entries, 4096);nit: use 64 * 1024 just in case, for arches where page size is 64KB
ok
Quoted 50 lines
Quoted 50 lines
tools/testing/selftests/bpf/progs/verifier_map_in_map.c +45
-1+ }); +} rb_in_map SEC(".maps"); + +struct rb_ctx { +void *rb; +struct bpf_dynptr dptr; +}; + +static __always_inline struct rb_ctx __rb_event_reserve(__u32 sz) +{ +struct rb_ctx rb_ctx = {}; +void *rb; +__u32 cpu =bpf_get_smp_processor_id (); +__u32 rb_slot = cpu &1 ; + + rb =bpf_map_lookup_elem (&rb_in_map, &rb_slot); +if (!rb) +return rb_ctx; + + rb_ctx.rb = rb; +bpf_ringbuf_reserve_dynptr (rb, sz,0 , &rb_ctx.dptr); + +return rb_ctx; +} + +static __noinline void __rb_event_submit(struct rb_ctx *ctx) +{ +if (!ctx->rb) +return ; + +/* If the verifier (incorrectly) concludes that ctx->rb can be +* NULL at this point, we'll get "BPF_EXIT instruction in main +* prog would lead to reference leak" error +*/ +bpf_ringbuf_submit_dynptr (&ctx->dptr,0 ); +} + +SEC("socket") +int map_ptr_is_never_null_rb (void *ctx) +{ +struct rb_ctx event_ctx =__rb_event_reserve (256 ); +__rb_event_submit (&event_ctx); +return 0 ; +} + char _license[] SEC("license") = "GPL"; --2.47.1
Re: [PATCH bpf-next v3 3/3] selftests/bpf: add test cases with CONST_PTR_TO_MAP null checks
Quoted 46 lines · Ihor Solodrai
Quoted 35 lines · Andrii Nakryiko
Quoted 13 lines · Ihor Solodrai
A test requires the following to happen:
*CONST_PTR_TO_MAPvalue is put on the stack
* then this value is checked for null
* the code in the null branch fails verificationI was able to achieve this by using a stack allocated array of maps, populated with values from a global map. This is the first test case:
map_ptr_is_never_null.The second test case (
map_ptr_is_never_null_rb) involves an array of ringbufs and attempts to recreate a common coding pattern [1].Quoted 8 lines
[1] https://lore.kernel.org/bpf/CAEf4BzZNU0gX_sQ8k8JaLe1e+Veth3Rk=4x7MDhv=hQxvO8EDw@mail.gmail.com/
Suggested-by Andrii Nakryiko <[email protected]>Signed-off-by Ihor Solodrai <[email protected]>--- .../selftests/bpf/progs/verifier_map_in_map.c | 77 +++++++++++++++++++ 1 file changed, 77 insertions(+)LGTM overall
Acked-by Andrii Nakryiko <[email protected]>Quoted 8 lines
tools/testing/selftests/bpf/progs/verifier_map_in_map.c +0
-0@@ -139,4 +139,81 @@ __naked void on_the_inner_map_pointer(void) : __clobber_all); }Quoted 8 lines
tools/testing/selftests/bpf/progs/verifier_map_in_map.c __naked void on_the_inner_map_pointer(void) · line 147
Quoted 6 lines
tools/testing/selftests/bpf/progs/verifier_map_in_map.c +6
-0+SEC("socket") +int map_ptr_is_never_null (void *ctx) +{ +struct bpf_map *maps[2 ] = {0 }; +struct bpf_map *map =NULL ; +int __attribute__((aligned (8 ))) key =0 ;aligned(8) makes any difference?
Quoted 3 lines
Yes. If not aligned (explicitly or by accident), verification fails with "math between fp pointer and register with unbounded min value is not allowed" at maps[key]. See the log below.
It's not clear to me why "aligned" changes code gen, but let's not rely on it.
Try 'unsigned int key' instead.
Also note that &key part pessimizes the code. Do for (...; i < 2; i++) {u32 key = i; &key } instead.
Ihor Solodrai
reviewerRe: [PATCH bpf-next v3 3/3] selftests/bpf: add test cases with CONST_PTR_TO_MAP null checks
Quoted 20 lines · Alexei Starovoitov
Quoted 15 lines · Ihor Solodrai
Quoted 4 lines · Andrii Nakryiko
Quoted 3 lines · Ihor Solodrai
[...]
Quoted 8 lines
tools/testing/selftests/bpf/progs/verifier_map_in_map.c __naked void on_the_inner_map_pointer(void) · line 147
Quoted 6 lines
tools/testing/selftests/bpf/progs/verifier_map_in_map.c +6
-0+SEC("socket") +int map_ptr_is_never_null (void *ctx) +{ +struct bpf_map *maps[2 ] = {0 }; +struct bpf_map *map =NULL ; +int __attribute__((aligned (8 ))) key =0 ;aligned(8) makes any difference?
Quoted 3 lines
Yes. If not aligned (explicitly or by accident), verification fails with "math between fp pointer and register with unbounded min value is not allowed" at maps[key]. See the log below.
Quoted 6 lines
It's not clear to me why "aligned" changes code gen, but let's not rely on it.
Try 'unsigned int key' instead.
Also note that &key part pessimizes the code. Do for (...; i < 2; i++) {u32 key = i; &key } instead.
I've tried changing the test like this:
@@ -144,12 +144,12 @@ int map_ptr_is_never_null(void *ctx)
{
struct bpf_map *maps[2] = { 0 };
struct bpf_map *map = NULL;- int __attribute__((aligned(8))) key = 0;
- for (key = 0; key < 2; key++) {
+ for (int i = 0; i < 2; i++) {
+ __u32 key = i;
map = bpf_map_lookup_elem(&map_in_map, &key);
if (map)
- maps[key] = map;
+ maps[i] = map;
else
return 0;
}This version passes verification independent of the first patch being applied, which kinda defeats the purpose of the test. Verifier log below:
0: R1=ctx() R10=fp0
; int map_ptr_is_never_null(void *ctx) @ verifier_map_in_map.c:143
0: (b4) w1 = 0 ; R1_w=0
; __u32 key = i; @ verifier_map_in_map.c:149
1: (63) *(u32 *)(r10 -4) = r1
mark_precise: frame0: last_idx 1 first_idx 0 subseq_idx -1
mark_precise: frame0: regs=r1 stack= before 0: (b4) w1 = 0
2: R1_w=0 R10=fp0 fp-8=0000????
2: (bf) r2 = r10 ; R2_w=fp0 R10=fp0
3: (07) r2 += -4 ; R2_w=fp-4
; map = bpf_map_lookup_elem(&map_in_map, &key); @
verifier_map_in_map.c:150
4: (18) r1 = 0xff302cd6802e0a00 ;
R1_w=map_ptr(map=map_in_map,ks=4,vs=4)
6: (85) call bpf_map_lookup_elem#1 ;
R0_w=map_value_or_null(id=1,map=map_in_map,ks=4,vs=4)
; if (map) @ verifier_map_in_map.c:151
7: (15) if r0 == 0x0 goto pc+7 ; R0_w=map_ptr(ks=4,vs=4)
8: (b4) w1 = 1 ; R1_w=1
; __u32 key = i; @ verifier_map_in_map.c:149
9: (63) *(u32 *)(r10 -4) = r1 ; R1_w=1 R10=fp0 fp-8=mmmm????
10: (bf) r2 = r10 ; R2_w=fp0 R10=fp0
11: (07) r2 += -4 ; R2_w=fp-4
; map = bpf_map_lookup_elem(&map_in_map, &key); @
verifier_map_in_map.c:150
12: (18) r1 = 0xff302cd6802e0a00 ;
R1_w=map_ptr(map=map_in_map,ks=4,vs=4)
14: (85) call bpf_map_lookup_elem#1 ;
R0=map_value_or_null(id=2,map=map_in_map,ks=4,vs=4)
; } @ verifier_map_in_map.c:164
15: (b4) w0 = 0 ; R0_w=0
16: (95) exitIf map[i] is changed back to map[key] like this:
for (int i = 0; i < 2; i++) {
__u32 key = i;
map = bpf_map_lookup_elem(&map_in_map, &key);
if (map)
maps[key] = map; /* change here */
else
return 0;
}Verification fails with "invalid unbounded variable-offset write to stack R2"
VERIFIER LOG:
=============
arg#0 reference type('UNKNOWN ') size cannot be determined: -22
0: R1=ctx() R10=fp0
; int map_ptr_is_never_null(void *ctx) @ verifier_map_in_map.c:143
0: (b7) r1 = 0 ; R1_w=0
; struct bpf_map *maps[2] = { 0 }; @ verifier_map_in_map.c:145
1: (7b) *(u64 *)(r10 -8) = r1 ; R1_w=0 R10=fp0 fp-8_w=0
2: (7b) *(u64 *)(r10 -16) = r1 ; R1_w=0 R10=fp0 fp-16_w=0
3: (b4) w1 = 0 ; R1_w=0
; __u32 key = i; @ verifier_map_in_map.c:149
4: (63) *(u32 *)(r10 -20) = r1 ; R1_w=0 R10=fp0 fp-24=0000????
5: (bf) r2 = r10 ; R2_w=fp0 R10=fp0
6: (07) r2 += -20 ; R2_w=fp-20
; map = bpf_map_lookup_elem(&map_in_map, &key); @
verifier_map_in_map.c:150
7: (18) r1 = 0xff1f1a9b829ae400 ;
R1_w=map_ptr(map=map_in_map,ks=4,vs=4)
9: (85) call bpf_map_lookup_elem#1 ;
R0_w=map_value_or_null(id=1,map=map_in_map,ks=4,vs=4)
; if (map) @ verifier_map_in_map.c:151
10: (15) if r0 == 0x0 goto pc+24 ; R0_w=map_ptr(ks=4,vs=4)
; maps[key] = map; @ verifier_map_in_map.c:152
11: (61) r1 = *(u32 *)(r10 -20) ; R1_w=0 R10=fp0 fp-24=0000????
12: (67) r1 <<= 3 ; R1_w=0
13: (bf) r2 = r10 ; R2_w=fp0 R10=fp0
14: (07) r2 += -16 ; R2_w=fp-16
15: (0f) r2 += r1 ; R1_w=0 R2_w=fp-16
16: (7b) *(u64 *)(r2 +0) = r0 ; R0_w=map_ptr(ks=4,vs=4)
R2_w=fp-16 fp-16_w=map_ptr(ks=4,vs=4)
17: (b4) w1 = 1 ; R1_w=1
; __u32 key = i; @ verifier_map_in_map.c:149
18: (63) *(u32 *)(r10 -20) = r1 ; R1_w=1 R10=fp0 fp-24=mmmm????
19: (bf) r2 = r10 ; R2_w=fp0 R10=fp0
20: (07) r2 += -20 ; R2_w=fp-20
; map = bpf_map_lookup_elem(&map_in_map, &key); @
verifier_map_in_map.c:150
21: (18) r1 = 0xff1f1a9b829ae400 ;
R1_w=map_ptr(map=map_in_map,ks=4,vs=4)
23: (85) call bpf_map_lookup_elem#1 ;
R0=map_value_or_null(id=2,map=map_in_map,ks=4,vs=4)
; if (map) @ verifier_map_in_map.c:151
24: (15) if r0 == 0x0 goto pc+10 ; R0=map_ptr(ks=4,vs=4)
; maps[key] = map; @ verifier_map_in_map.c:152
25: (61) r1 = *(u32 *)(r10 -20) ;
R1_w=scalar(smin=0,smax=umax=0xffffffff,var_off=(0x0; 0xffffffff)) R10=fp0 fp-24=mmmm????
26: (67) r1 <<= 3 ;
R1_w=scalar(smin=0,smax=umax=0x7fffffff8,smax32=0x7ffffff8,umax32=0xfffffff8,var_off=(0x0; 0x7fffffff8))
27: (bf) r2 = r10 ; R2_w=fp0 R10=fp0
28: (07) r2 += -16 ; R2_w=fp-16
29: (0f) r2 += r1 ; R1_w=scalar(smin=0,smax=umax=0x7fffffff8,smax32=0x7ffffff8,umax32=0xfffffff8,var_off=(0x0; 0x7fffffff8)) R2_w=fp(off=-16,smin=0,smax=umax=0x7fffffff8,smax32=0x7ffffff8,umax32=0xfffffff8,var_off=(0x0; 0x7fffffff8))
30: (7b) *(u64 *)(r2 +0) = r0
invalid unbounded variable-offset write to stack R2
... which can be "fixed" by aligning the local key variable
__u32 __attribute__((aligned(8))) key = i;
but that puts us back to square one.
It appears that alignment becomes a problem if the variable is used as array index and also it's address is passed to a helper.
And if different vars are used for array access and map lookup, then map_ptr nullness issue doesn't reproduce.
Any suggestions?
Re: [PATCH bpf-next v3 3/3] selftests/bpf: add test cases with CONST_PTR_TO_MAP null checks
Quoted 76 lines · Ihor Solodrai
Quoted 20 lines · Alexei Starovoitov
Quoted 15 lines · Ihor Solodrai
Quoted 4 lines · Andrii Nakryiko
Quoted 3 lines · Ihor Solodrai
[...]
Quoted 8 lines
tools/testing/selftests/bpf/progs/verifier_map_in_map.c __naked void on_the_inner_map_pointer(void) · line 147
Quoted 6 lines
tools/testing/selftests/bpf/progs/verifier_map_in_map.c +6
-0+SEC("socket") +int map_ptr_is_never_null (void *ctx) +{ +struct bpf_map *maps[2 ] = {0 }; +struct bpf_map *map =NULL ; +int __attribute__((aligned (8 ))) key =0 ;aligned(8) makes any difference?
Quoted 3 lines
Yes. If not aligned (explicitly or by accident), verification fails with "math between fp pointer and register with unbounded min value is not allowed" at maps[key]. See the log below.
Quoted 6 lines
It's not clear to me why "aligned" changes code gen, but let's not rely on it.
Try 'unsigned int key' instead.
Also note that &key part pessimizes the code. Do for (...; i < 2; i++) {u32 key = i; &key } instead.I've tried changing the test like this:
(quoted diff) +3
-3@@ -144,12 +144,12 @@ int map_ptr_is_never_null(void *ctx) { struct bpf_map *maps[2] = { 0 }; struct bpf_map *map = NULL; - int __attribute__((aligned(8))) key = 0; - for (key = 0; key < 2; key++) { + for (int i = 0; i < 2; i++) { + __u32 key = i; map = bpf_map_lookup_elem(&map_in_map, &key); if (map) - maps[key] = map; + maps[i] = map; else return 0; }This version passes verification independent of the first patch being applied, which kinda defeats the purpose of the test. Verifier log below:
0: R1=ctx() R10=fp0 ; int map_ptr_is_never_null(void *ctx) @ verifier_map_in_map.c:143 0: (b4) w1 = 0 ; R1_w=0 ; __u32 key = i; @ verifier_map_in_map.c:149 1: (63) *(u32 *)(r10 -4) = r1 mark_precise: frame0: last_idx 1 first_idx 0 subseq_idx -1 mark_precise: frame0: regs=r1 stack= before 0: (b4) w1 = 0 2: R1_w=0 R10=fp0 fp-8=0000???? 2: (bf) r2 = r10 ; R2_w=fp0 R10=fp0 3: (07) r2 += -4 ; R2_w=fp-4 ; map = bpf_map_lookup_elem(&map_in_map, &key); @ verifier_map_in_map.c:150 4: (18) r1 = 0xff302cd6802e0a00 ; R1_w=map_ptr(map=map_in_map,ks=4,vs=4) 6: (85) call bpf_map_lookup_elem#1 ; R0_w=map_value_or_null(id=1,map=map_in_map,ks=4,vs=4) ; if (map) @ verifier_map_in_map.c:151 7: (15) if r0 == 0x0 goto pc+7 ; R0_w=map_ptr(ks=4,vs=4) 8: (b4) w1 = 1 ; R1_w=1 ; __u32 key = i; @ verifier_map_in_map.c:149 9: (63) *(u32 *)(r10 -4) = r1 ; R1_w=1 R10=fp0 fp-8=mmmm???? 10: (bf) r2 = r10 ; R2_w=fp0 R10=fp0 11: (07) r2 += -4 ; R2_w=fp-4 ; map = bpf_map_lookup_elem(&map_in_map, &key); @
Quoted 8 lines
verifier_map_in_map.c:150
12: (18) r1 = 0xff302cd6802e0a00 ; R1_w=map_ptr(map=map_in_map,ks=4,vs=4) 14: (85) call bpf_map_lookup_elem#1 ; R0=map_value_or_null(id=2,map=map_in_map,ks=4,vs=4) ; } @ verifier_map_in_map.c:164 15: (b4) w0 = 0 ; R0_w=0 16: (95) exit
because the compiler removed 'if (!maps[0])' check? Make maps volatile then.
It's not clear to me what the point of the 'for' loop is. Just one bpf_map_lookup_elem() from map_in_map should do ?
Quoted 12 lines
If map[i] is changed back to map[key] like this:
for (int i = 0; i < 2; i++) { __u32 key = i; map = bpf_map_lookup_elem(&map_in_map, &key); if (map) maps[key] = map; /* change here */ else return 0; }
Quoted 2 lines
Verification fails with "invalid unbounded variable-offset write to stack R2"
as it should, because both the compiler and the verifier see that 'key' is unbounded in maps[key] access.
Quoted 6 lines
__u32 __attribute__((aligned(8))) key = i;but that puts us back to square one.
It appears that alignment becomes a problem if the variable is used as array index and also it's address is passed to a helper.
I bet this alignment "workaround" is fragile.
A different version of clang or gcc-bpf will change layout.
Ihor Solodrai
reviewerRe: [PATCH bpf-next v3 3/3] selftests/bpf: add test cases with CONST_PTR_TO_MAP null checks
Quoted 80 lines · Alexei Starovoitov
Quoted 79 lines · Ihor Solodrai
Quoted 20 lines · Alexei Starovoitov
Quoted 15 lines · Ihor Solodrai
Quoted 4 lines · Andrii Nakryiko
Quoted 3 lines · Ihor Solodrai
[...]
Quoted 8 lines
tools/testing/selftests/bpf/progs/verifier_map_in_map.c __naked void on_the_inner_map_pointer(void) · line 147
Quoted 6 lines
tools/testing/selftests/bpf/progs/verifier_map_in_map.c +6
-0+SEC("socket") +int map_ptr_is_never_null (void *ctx) +{ +struct bpf_map *maps[2 ] = {0 }; +struct bpf_map *map =NULL ; +int __attribute__((aligned (8 ))) key =0 ;aligned(8) makes any difference?
Quoted 3 lines
Yes. If not aligned (explicitly or by accident), verification fails with "math between fp pointer and register with unbounded min value is not allowed" at maps[key]. See the log below.
Quoted 6 lines
It's not clear to me why "aligned" changes code gen, but let's not rely on it.
Try 'unsigned int key' instead.
Also note that &key part pessimizes the code. Do for (...; i < 2; i++) {u32 key = i; &key } instead.I've tried changing the test like this:
(quoted diff) +3
-3@@ -144,12 +144,12 @@ int map_ptr_is_never_null(void *ctx) { struct bpf_map *maps[2] = { 0 }; struct bpf_map *map = NULL; - int __attribute__((aligned(8))) key = 0; - for (key = 0; key < 2; key++) { + for (int i = 0; i < 2; i++) { + __u32 key = i; map = bpf_map_lookup_elem(&map_in_map, &key); if (map) - maps[key] = map; + maps[i] = map; else return 0; }This version passes verification independent of the first patch being applied, which kinda defeats the purpose of the test. Verifier log below:
0: R1=ctx() R10=fp0 ; int map_ptr_is_never_null(void *ctx) @ verifier_map_in_map.c:143 0: (b4) w1 = 0 ; R1_w=0 ; __u32 key = i; @ verifier_map_in_map.c:149 1: (63) *(u32 *)(r10 -4) = r1 mark_precise: frame0: last_idx 1 first_idx 0 subseq_idx -1 mark_precise: frame0: regs=r1 stack= before 0: (b4) w1 = 0 2: R1_w=0 R10=fp0 fp-8=0000???? 2: (bf) r2 = r10 ; R2_w=fp0 R10=fp0 3: (07) r2 += -4 ; R2_w=fp-4 ; map = bpf_map_lookup_elem(&map_in_map, &key); @ verifier_map_in_map.c:150 4: (18) r1 = 0xff302cd6802e0a00 ; R1_w=map_ptr(map=map_in_map,ks=4,vs=4) 6: (85) call bpf_map_lookup_elem#1 ; R0_w=map_value_or_null(id=1,map=map_in_map,ks=4,vs=4) ; if (map) @ verifier_map_in_map.c:151 7: (15) if r0 == 0x0 goto pc+7 ; R0_w=map_ptr(ks=4,vs=4) 8: (b4) w1 = 1 ; R1_w=1 ; __u32 key = i; @ verifier_map_in_map.c:149 9: (63) *(u32 *)(r10 -4) = r1 ; R1_w=1 R10=fp0 fp-8=mmmm???? 10: (bf) r2 = r10 ; R2_w=fp0 R10=fp0 11: (07) r2 += -4 ; R2_w=fp-4 ; map = bpf_map_lookup_elem(&map_in_map, &key); @ verifier_map_in_map.c:150 12: (18) r1 = 0xff302cd6802e0a00 ;R1_w=map_ptr(map=map_in_map,ks=4,vs=4)
Quoted 8 lines
Quoted 5 lines
14: (85) call bpf_map_lookup_elem#1 ; R0=map_value_or_null(id=2,map=map_in_map,ks=4,vs=4) ; } @ verifier_map_in_map.c:164 15: (b4) w0 = 0 ; R0_w=0 16: (95) exitbecause the compiler removed 'if (!maps[0])' check? Make maps volatile then.
Making maps and/or map volatile didn't help.
Quoted 3 lines
It's not clear to me what the point of the 'for' loop is. Just one
bpf_map_lookup_elem()frommap_in_mapshould do ?
No. Using an array and loop was my attempt to put map_ptr on the stack. But apparently this was not the reason it happened in the v1 of the test.
Quoted 21 lines
Quoted 13 lines
If map[i] is changed back to map[key] like this:
for (int i = 0; i < 2; i++) { __u32 key = i; map = bpf_map_lookup_elem(&map_in_map, &key); if (map) maps[key] = map; /* change here */ else return 0; }Quoted 2 lines
Verification fails with "invalid unbounded variable-offset write to stack R2"
as it should, because both the compiler and the verifier see that 'key' is unbounded in maps[key] access.
Quoted 2 lines
__u32 __attribute__((aligned(8))) key = i;
Quoted 7 lines
Quoted 4 lines
but that puts us back to square one.
It appears that alignment becomes a problem if the variable is used as array index and also it's address is passed to a helper.
I bet this alignment "workaround" is fragile.
A different version of clang or gcc-bpf will change layout.
I agree, it's fragile.
After I fought compiler/verifier for a while I gave up and wrote a test in asm:
SEC("socket")
__description("map_ptr is never null")
__success
__naked void map_ptr_is_never_null(void)
{
asm volatile (" \
r1 = 0; \
*(u32*)(r10 - 4) = r1; \
r2 = r10; \
r2 += -4; \
r1 = %[map_in_map] ll; \
call %[bpf_map_lookup_elem]; \
if r0 != 0 goto l0_%=; \
exit; \
l0_%=: *(u64 *)(r10 -16) = r0; \
r1 = *(u64 *)(r10 -16); \
if r1 == 0 goto l1_%=; \
exit; \
l1_%=: r10 = 42; \
exit; \
" :
: __imm(bpf_map_lookup_elem),
__imm_addr(map_in_map)
: __clobber_all);
}What must happen to reproduce the situation is: map_ptr gets on a stack, and then loaded and compared to 0.
It looks like I accidentally forced map_ptr on the stack by using key both for map lookup and array access, which triggers those alignment problems. Without that I wasn't able to figure out simple C code that would produce bpf with map_ptr on the stack (besides the other test, with rbs).
I guess I should've written an asm test right away.
Re: [PATCH bpf-next v3 3/3] selftests/bpf: add test cases with CONST_PTR_TO_MAP null checks
Quoted 164 lines · Ihor Solodrai
Quoted 80 lines · Alexei Starovoitov
Quoted 79 lines · Ihor Solodrai
Quoted 20 lines · Alexei Starovoitov
Quoted 15 lines · Ihor Solodrai
Quoted 4 lines · Andrii Nakryiko
Quoted 3 lines · Ihor Solodrai
[...]
Quoted 8 lines
Review
Quoted 6 lines
(quoted diff) +6
-0+SEC("socket") +int map_ptr_is_never_null(void *ctx) +{ + struct bpf_map *maps[2] = { 0 }; + struct bpf_map *map = NULL; + int __attribute__((aligned(8))) key = 0;aligned(8) makes any difference?
Quoted 3 lines
Yes. If not aligned (explicitly or by accident), verification fails with "math between fp pointer and register with unbounded min value is not allowed" at maps[key]. See the log below.
Quoted 6 lines
It's not clear to me why "aligned" changes code gen, but let's not rely on it.
Try 'unsigned int key' instead.
Also note that &key part pessimizes the code. Do for (...; i < 2; i++) {u32 key = i; &key } instead.I've tried changing the test like this:
(quoted diff) +3
-3@@ -144,12 +144,12 @@ int map_ptr_is_never_null(void *ctx) { struct bpf_map *maps[2] = { 0 }; struct bpf_map *map = NULL; - int __attribute__((aligned(8))) key = 0; - for (key = 0; key < 2; key++) { + for (int i = 0; i < 2; i++) { + __u32 key = i; map = bpf_map_lookup_elem(&map_in_map, &key); if (map) - maps[key] = map; + maps[i] = map; else return 0; }This version passes verification independent of the first patch being applied, which kinda defeats the purpose of the test. Verifier log below:
0: R1=ctx() R10=fp0 ; int map_ptr_is_never_null(void *ctx) @ verifier_map_in_map.c:143 0: (b4) w1 = 0 ; R1_w=0 ; __u32 key = i; @ verifier_map_in_map.c:149 1: (63) *(u32 *)(r10 -4) = r1 mark_precise: frame0: last_idx 1 first_idx 0 subseq_idx -1 mark_precise: frame0: regs=r1 stack= before 0: (b4) w1 = 0 2: R1_w=0 R10=fp0 fp-8=0000???? 2: (bf) r2 = r10 ; R2_w=fp0 R10=fp0 3: (07) r2 += -4 ; R2_w=fp-4 ; map = bpf_map_lookup_elem(&map_in_map, &key); @ verifier_map_in_map.c:150 4: (18) r1 = 0xff302cd6802e0a00 ; R1_w=map_ptr(map=map_in_map,ks=4,vs=4) 6: (85) call bpf_map_lookup_elem#1 ; R0_w=map_value_or_null(id=1,map=map_in_map,ks=4,vs=4) ; if (map) @ verifier_map_in_map.c:151 7: (15) if r0 == 0x0 goto pc+7 ; R0_w=map_ptr(ks=4,vs=4) 8: (b4) w1 = 1 ; R1_w=1 ; __u32 key = i; @ verifier_map_in_map.c:149 9: (63) *(u32 *)(r10 -4) = r1 ; R1_w=1 R10=fp0 fp-8=mmmm???? 10: (bf) r2 = r10 ; R2_w=fp0 R10=fp0 11: (07) r2 += -4 ; R2_w=fp-4 ; map = bpf_map_lookup_elem(&map_in_map, &key); @ verifier_map_in_map.c:150 12: (18) r1 = 0xff302cd6802e0a00 ;R1_w=map_ptr(map=map_in_map,ks=4,vs=4)
Quoted 8 lines
Quoted 5 lines
14: (85) call bpf_map_lookup_elem#1 ; R0=map_value_or_null(id=2,map=map_in_map,ks=4,vs=4) ; } @ verifier_map_in_map.c:164 15: (b4) w0 = 0 ; R0_w=0 16: (95) exitbecause the compiler removed 'if (!maps[0])' check? Make maps volatile then.
Making maps and/or map volatile didn't help.
Quoted 3 lines
It's not clear to me what the point of the 'for' loop is. Just one
bpf_map_lookup_elem()frommap_in_mapshould do ?No. Using an array and loop was my attempt to put
map_ptron the stack. But apparently this was not the reason it happened in the v1 of the test.Quoted 21 lines
Quoted 13 lines
If map[i] is changed back to map[key] like this:
for (int i = 0; i < 2; i++) { __u32 key = i; map = bpf_map_lookup_elem(&map_in_map, &key); if (map) maps[key] = map; /* change here */ else return 0; }Quoted 2 lines
Verification fails with "invalid unbounded variable-offset write to stack R2"
as it should, because both the compiler and the verifier see that 'key' is unbounded in maps[key] access.
Quoted 2 lines
__u32 __attribute__((aligned(8))) key = i;Quoted 7 lines
Quoted 4 lines
but that puts us back to square one.
It appears that alignment becomes a problem if the variable is used as array index and also it's address is passed to a helper.
I bet this alignment "workaround" is fragile.
A different version of clang or gcc-bpf will change layout.I agree, it's fragile.
After I fought compiler/verifier for a while I gave up and wrote a test in asm:
SEC("socket") __description("map_ptr is never null") __success __naked void map_ptr_is_never_null(void) { asm volatile (" \ r1 = 0; \ *(u32*)(r10 - 4) = r1; \ r2 = r10; \ r2 += -4; \ r1 = %[map_in_map] ll; \ call %[bpf_map_lookup_elem]; \ if r0 != 0 goto l0_%=; \ exit; \ l0_%=: *(u64 *)(r10 -16) = r0; \ r1 = *(u64 *)(r10 -16); \ if r1 == 0 goto l1_%=; \ exit; \ l1_%=: r10 = 42; \ exit; \ " : : __imm(bpf_map_lookup_elem), __imm_addr(map_in_map) : __clobber_all); }What must happen to reproduce the situation is:
map_ptrgets on a stack, and then loaded and compared to 0.
Quoted 7 lines
It looks like I accidentally forced
map_ptron the stack by usingkeyboth for map lookup and array access, which triggers those alignment problems. Without that I wasn't able to figure out simple C code that would produce bpf withmap_ptron the stack (besides the other test, with rbs).I guess I should've written an asm test right away.
Yeah. For this kind of sequence asm is the right answer. It's not clear to me why you want to spill/fill it. CONST_PTR_TO_MAP is already in is_spillable_regtype() before this patch.
The test needs to validate that reg_not_null() is working. So just:
r1 = %[map_in_map] ll;
call %[bpf_map_lookup_elem];
if r0 == 0 goto l0_%=;
exit;
l0_%=: r10 = 42;
exit;would do the job without spill/fill.
Re: [PATCH bpf-next v3 3/3] selftests/bpf: add test cases with CONST_PTR_TO_MAP null checks
Quoted 181 lines · Alexei Starovoitov
Quoted 164 lines · Ihor Solodrai
Quoted 80 lines · Alexei Starovoitov
Quoted 79 lines · Ihor Solodrai
Quoted 20 lines · Alexei Starovoitov
Quoted 15 lines · Ihor Solodrai
Quoted 4 lines · Andrii Nakryiko
Quoted 3 lines · Ihor Solodrai
[...]
Quoted 8 lines
Review
Quoted 6 lines
(quoted diff) +6
-0+SEC("socket") +int map_ptr_is_never_null(void *ctx) +{ + struct bpf_map *maps[2] = { 0 }; + struct bpf_map *map = NULL; + int __attribute__((aligned(8))) key = 0;aligned(8) makes any difference?
Quoted 3 lines
Yes. If not aligned (explicitly or by accident), verification fails with "math between fp pointer and register with unbounded min value is not allowed" at maps[key]. See the log below.
Quoted 6 lines
It's not clear to me why "aligned" changes code gen, but let's not rely on it.
Try 'unsigned int key' instead.
Also note that &key part pessimizes the code. Do for (...; i < 2; i++) {u32 key = i; &key } instead.I've tried changing the test like this:
(quoted diff) +3
-3@@ -144,12 +144,12 @@ int map_ptr_is_never_null(void *ctx) { struct bpf_map *maps[2] = { 0 }; struct bpf_map *map = NULL; - int __attribute__((aligned(8))) key = 0; - for (key = 0; key < 2; key++) { + for (int i = 0; i < 2; i++) { + __u32 key = i; map = bpf_map_lookup_elem(&map_in_map, &key); if (map) - maps[key] = map; + maps[i] = map; else return 0; }This version passes verification independent of the first patch being applied, which kinda defeats the purpose of the test. Verifier log below:
0: R1=ctx() R10=fp0 ; int map_ptr_is_never_null(void *ctx) @ verifier_map_in_map.c:143 0: (b4) w1 = 0 ; R1_w=0 ; __u32 key = i; @ verifier_map_in_map.c:149 1: (63) *(u32 *)(r10 -4) = r1 mark_precise: frame0: last_idx 1 first_idx 0 subseq_idx -1 mark_precise: frame0: regs=r1 stack= before 0: (b4) w1 = 0 2: R1_w=0 R10=fp0 fp-8=0000???? 2: (bf) r2 = r10 ; R2_w=fp0 R10=fp0 3: (07) r2 += -4 ; R2_w=fp-4 ; map = bpf_map_lookup_elem(&map_in_map, &key); @ verifier_map_in_map.c:150 4: (18) r1 = 0xff302cd6802e0a00 ; R1_w=map_ptr(map=map_in_map,ks=4,vs=4) 6: (85) call bpf_map_lookup_elem#1 ; R0_w=map_value_or_null(id=1,map=map_in_map,ks=4,vs=4) ; if (map) @ verifier_map_in_map.c:151 7: (15) if r0 == 0x0 goto pc+7 ; R0_w=map_ptr(ks=4,vs=4) 8: (b4) w1 = 1 ; R1_w=1 ; __u32 key = i; @ verifier_map_in_map.c:149 9: (63) *(u32 *)(r10 -4) = r1 ; R1_w=1 R10=fp0 fp-8=mmmm???? 10: (bf) r2 = r10 ; R2_w=fp0 R10=fp0 11: (07) r2 += -4 ; R2_w=fp-4 ; map = bpf_map_lookup_elem(&map_in_map, &key); @ verifier_map_in_map.c:150 12: (18) r1 = 0xff302cd6802e0a00 ;R1_w=map_ptr(map=map_in_map,ks=4,vs=4)
Quoted 8 lines
Quoted 5 lines
14: (85) call bpf_map_lookup_elem#1 ; R0=map_value_or_null(id=2,map=map_in_map,ks=4,vs=4) ; } @ verifier_map_in_map.c:164 15: (b4) w0 = 0 ; R0_w=0 16: (95) exitbecause the compiler removed 'if (!maps[0])' check? Make maps volatile then.
Making maps and/or map volatile didn't help.
Quoted 3 lines
It's not clear to me what the point of the 'for' loop is. Just one
bpf_map_lookup_elem()frommap_in_mapshould do ?No. Using an array and loop was my attempt to put
map_ptron the stack. But apparently this was not the reason it happened in the v1 of the test.Quoted 21 lines
Quoted 13 lines
If map[i] is changed back to map[key] like this:
for (int i = 0; i < 2; i++) { __u32 key = i; map = bpf_map_lookup_elem(&map_in_map, &key); if (map) maps[key] = map; /* change here */ else return 0; }Quoted 2 lines
Verification fails with "invalid unbounded variable-offset write to stack R2"
as it should, because both the compiler and the verifier see that 'key' is unbounded in maps[key] access.
Quoted 2 lines
__u32 __attribute__((aligned(8))) key = i;Quoted 7 lines
Quoted 4 lines
but that puts us back to square one.
It appears that alignment becomes a problem if the variable is used as array index and also it's address is passed to a helper.
I bet this alignment "workaround" is fragile.
A different version of clang or gcc-bpf will change layout.I agree, it's fragile.
After I fought compiler/verifier for a while I gave up and wrote a test in asm:
SEC("socket") __description("map_ptr is never null") __success __naked void map_ptr_is_never_null(void) { asm volatile (" \ r1 = 0; \ *(u32*)(r10 - 4) = r1; \ r2 = r10; \ r2 += -4; \ r1 = %[map_in_map] ll; \ call %[bpf_map_lookup_elem]; \ if r0 != 0 goto l0_%=; \ exit; \ l0_%=: *(u64 *)(r10 -16) = r0; \ r1 = *(u64 *)(r10 -16); \ if r1 == 0 goto l1_%=; \ exit; \ l1_%=: r10 = 42; \ exit; \ " : : __imm(bpf_map_lookup_elem), __imm_addr(map_in_map) : __clobber_all); }What must happen to reproduce the situation is:
map_ptrgets on a stack, and then loaded and compared to 0.Quoted 7 lines
It looks like I accidentally forced
map_ptron the stack by usingkeyboth for map lookup and array access, which triggers those alignment problems. Without that I wasn't able to figure out simple C code that would produce bpf withmap_ptron the stack (besides the other test, with rbs).I guess I should've written an asm test right away.
Yeah. For this kind of sequence asm is the right answer. It's not clear to me why you want to spill/fill it.
CONST_PTR_TO_MAPis already inis_spillable_regtype()before this patch.
The test needs to validate thatreg_not_null()is working. So just:
Quoted 8 lines
r1 = %[map_in_map] ll; call %[bpf_map_lookup_elem]; if r0 == 0 goto l0_%=; exit; l0_%=: r10 = 42; exit;would do the job without spill/fill.
braino. I meant two if r0 checks back to back.
Like:
r1 = %[map_in_map] ll;
call %[bpf_map_lookup_elem];
if r0 == 0 goto l0_%=;
if r0 != 0 goto l0_%=;
r10 = 42;l0_%=: exit;
kinda obvious looking at asm that the verifier should be smart to understand that the 2nd if is always taken. But the smartness is only added in patch 1.
Another test is probably worth it too:
r1 = %[map_in_map] ll;
if r1 != 0 goto l0_%=;
r10 = 42;l0_%=: exit;
Quoted 17 lines · Ihor Solodrai
When
reg->typeisCONST_PTR_TO_MAP, it can not be null. However the verifier explores the branches under rX == 0 incheck_cond_jmp_op()even ifreg->typeisCONST_PTR_TO_MAP, because it was not checked for inreg_not_null().Fix this by adding
CONST_PTR_TO_MAPto the set of types that are considered non nullable inreg_not_null().An old "unpriv: cmp map pointer with zero" selftest fails with this change, because now early out correctly triggers in
check_cond_jmp_op(), making the verification to pass.In practice verifier may allow pointer to null comparison in unpriv, since in many cases the relevant branch and comparison op are removed as dead code. So change the expected test result to
__success_unpriv.
Quoted 6 lines
Signed-off-by Ihor Solodrai <[email protected]>--- kernel/bpf/verifier.c | 3 ++- tools/testing/selftests/bpf/progs/verifier_unpriv.c | 2 +- 2 files changed, 3 insertions(+), 2 deletions(-)
LGTM, thanks!
Quoted 30 lines
kernel/bpf/verifier.c +2
-1@@ -405,7 +405,8 @@ static bool reg_not_null(const struct bpf_reg_state *reg) type ==PTR_TO_MAP_KEY || type ==PTR_TO_SOCK_COMMON || (type ==PTR_TO_BTF_ID &&is_trusted_reg (reg)) || - type ==PTR_TO_MEM ; + type ==PTR_TO_MEM || + type ==CONST_PTR_TO_MAP ; }static struct btf_record *reg_btf_record (const struct bpf_reg_state *reg)tools/testing/selftests/bpf/progs/verifier_unpriv.c +1
-2@@ -619,7 +619,7 @@ __naked void pass_pointer_to_tail_call(void) SEC("socket") __description("unpriv: cmp map pointer with zero") -__success __failure_unpriv __msg_unpriv("R1 pointer comparison") +__success __success_unpriv __retval(0) __naked void cmp_map_pointer_with_zero(void) { --2.47.1