Fix for raw_tp PTR_MAYBE_NULL unmarking
Subsystems (4)
Kumar Kartikeya Dwivedi
maintainercover Fix for raw_tp PTR_MAYBE_NULL unmarking
A production BPF program had the following code produced by LLVM.
r0 = 1024;
r1 = ...; // r1 = trusted_or_null_(id=1)
r3 = r1; // r3 = trusted_or_null_(id=1) r1 = trusted_or_null_(id=1) r3 += r0; // r3 = trusted_or_null_(id=1, off=1024)
if r1 == 0 goto pc+X;
After cb4158ce8ec8 ("bpf: Mark raw_tp arguments with PTR_MAYBE_NULL"), the production BPF program began throwing a warning in the verifier because for the code above, when unmarking null mark from r1, the verifier will notice another register r3 with same id but off != 0, which is unexpected, since offset modification on PTR_MAYBE_NULL is not permitted, but the aforementioned commit relaxed that restriction to preserve compatibility with non-NULL raw_tp args.
Provide a fix to suppress the warning for raw_tp args. We will follow up with a more generic fix to handle such patterns for all pointer types in the verifier, which currently involves playing whack-a-mole with suppressing such LLVM optimizations and reworking BPF programs to avoid verifier errors.
Kumar Kartikeya Dwivedi (2):
bpf: Suppress warning for non-zero off raw_tp arg NULL check selftests/bpf: Add raw_tp tests for PTR_MAYBE_NULL marking
kernel/bpf/verifier.c | 44 ++++++++-- .../selftests/bpf/prog_tests/raw_tp_null.c | 6 ++ .../selftests/bpf/progs/raw_tp_null_fail.c | 81 +++++++++++++++++++ 3 files changed, 126 insertions(+), 5 deletions(-) create mode 100644 tools/testing/selftests/bpf/progs/raw_tp_null_fail.c
base-commit: 45e04eb4d9d85603539984bc9ca930c380c93b15
Signature · 1 line
2.43.5
Kumar Kartikeya Dwivedi
maintainerPATCH 1/2 bpf: Suppress warning for non-zero off raw_tp arg NULL check
The fixed commit began marking raw_tp arguments as PTR_MAYBE_NULL to avoid dead code elimination in the verifier, since raw_tp arguments may actually be NULL at runtime. However, to preserve compatibility, it simulated the raw_tp accesses as if the NULL marking was not present.
One of the behaviors permitted by this simulation is offset modification for NULL pointers. Typically, this pattern is rejected by the verifier, and users make workarounds to prevent the compiler from producing such patterns. However, now that it is allowed, when the compiler emits such code, the offset modification is allowed and a PTR_MAYBE_NULL raw_tp arg with non-zero off can be formed.
The failing example program had the following pseudo-code:
r0 = 1024;
r1 = ...; // r1 = trusted_or_null_(id=1)
r3 = r1; // r3 = trusted_or_null_(id=1) r1 = trusted_or_null_(id=1) r3 += r0; // r3 = trusted_or_null_(id=1, off=1024)
if r1 == 0 goto pc+X;
At this point, while mark_ptr_or_null_reg will see PTR_MAYBE_NULL and off == 0 for r1, it will notice non-zero off for r3, and the WARN_ON_ONCE will fire, as the condition checks excluding register types do not include raw_tp argument type.
This is a pattern produced by LLVM, therefore it is hard to suppress it everywhere in BPF programs.
The right "generic" fix for this issue in general, will be permitting offset modification for PTR_MAYBE_NULL pointers everywhere, and enforcing that the instruction operand of a conditional jump has the offset as zero. It's other copies may still have non-zero offset, and that is fine. But this is more involved and will take longer to integrate.
Hence, for now, when we notice raw_tp args with off != 0 when unmarking NULL modifier, simply allocate such pointer a fresh id and remove them from the "id" set being currently operated on, and leave them as is without removing PTR_MAYBE_NULL marking.
Dereferencing such pointers will still work as the fixed commit allowed it for raw_tp args.
This will mean that still, all registers with a given id and off = 0 will be unmarked, even if a register with off != 0 is NULL checked, but this shouldn't introducing any incorrectness. Just that any register with off != 0 excludes itself from the marking exercise by reassigning itself a new id.
--- kernel/bpf/verifier.c | 44 ++++++++++++++++++++++++++++++++++++++----- 1 file changed, 39 insertions(+), 5 deletions(-)
kernel/bpf/verifier.c +39 -5
@@ -15335,7 +15335,8 @@ static int reg_set_min_max(struct bpf_verifier_env *env,return err; } -static void mark_ptr_or_null_reg (struct bpf_func_state *state, +static void mark_ptr_or_null_reg (struct bpf_verifier_env *env, +struct bpf_func_state *state,struct bpf_reg_state *reg,u32 id,bool is_null) {
@@ -15352,6 +15353,38 @@ static void mark_ptr_or_null_reg(struct bpf_func_state *state,*/ if (WARN_ON_ONCE (reg->smin_value || reg->smax_value || !tnum_equals_const (reg->var_off,0 )))return ; +/* Unlike the MEM_ALLOC and NON_OWN_REF cases explicitly tested +* below, where verifier will set off != 0, we allow users to +* modify offset of PTR_MAYBE_NULL raw_tp args to preserve +* compatibility since they were not marked NULL in older +* kernels. This however means we may see a non-zero offset +* register when marking them non-NULL in verifier state. +* This can happen for the operand of the instruction: +* +* r1 = trusted_or_null_(id=1); +* if r1 == 0 goto X; +* +* or a copy when LLVM produces code like below: +* +* r1 = trusted_or_null_(id=1); +* r3 = r1; // r3 = trusted_or_null(id=1) +* r3 += K; // r3 = trusted_or_null_(id=1, off=K) +* if r1 == 0 goto X; // see r3.off != 0 when unmarking _or_null +* +* The right fix would be more generic: lift the restriction on +* modifying reg->off for PTR_MAYBE_NULL pointers, and only +* enforce it for the instruction operand of a NULL check, while +* allowing non-zero off for other registers, but this is future +* work. +*/ +if (mask_raw_tp_reg_cond (env, reg) && reg->off) { +/* We don't reset reg->id back to 0, as it's unexpected +* when PTR_MAYBE_NULL is set. Simply give this reg a +* new id in case user decides to NULL check it again. +*/ + reg->id = ++env->id_gen; +return ; + }if (!(type_is_ptr_alloc_obj (reg->type) ||type_is_non_owning_ref (reg->type)) &&WARN_ON_ONCE (reg->off))return ;
@@ -15385,7 +15418,8 @@ static void mark_ptr_or_null_reg(struct bpf_func_state *state,/* The logic is similar to find_good_pkt_pointers(), both could eventually * be folded together at some point. */ -static void mark_ptr_or_null_regs (struct bpf_verifier_state *vstate,u32 regno, +static void mark_ptr_or_null_regs (struct bpf_verifier_env *env, +struct bpf_verifier_state *vstate,u32 regno,bool is_null) {struct bpf_func_state *state = vstate->frame[vstate->curframe];
@@ -15401,7 +15435,7 @@ static void mark_ptr_or_null_regs(struct bpf_verifier_state *vstate, u32 regno,WARN_ON_ONCE (release_reference_state (state, id));bpf_for_each_reg_in_vstate (vstate, state, reg, ({ -mark_ptr_or_null_reg (state, reg, id, is_null); +mark_ptr_or_null_reg (env, state, reg, id, is_null); })); }
@@ -15827,9 +15861,9 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,/* Mark all identical registers in each branch as either * safe or unknown depending R == 0 or R != 0 conditional. */ -mark_ptr_or_null_regs (this_branch, insn->dst_reg, +mark_ptr_or_null_regs (env, this_branch, insn->dst_reg, opcode ==BPF_JNE ); -mark_ptr_or_null_regs (other_branch, insn->dst_reg, +mark_ptr_or_null_regs (env, other_branch, insn->dst_reg, opcode ==BPF_JEQ ); } else if (!try_match_pkt_pointers(insn, dst_reg, ®s[insn->src_reg], this_branch, other_branch) &&
Signature · 1 line
2.43.5
Re: [PATCH bpf v1 1/2] bpf: Suppress warning for non-zero off raw_tp arg NULL check
Quoted 89 lines · Kumar Kartikeya Dwivedi
The fixed commit began marking
raw_tparguments asPTR_MAYBE_NULLto avoid dead code elimination in the verifier, sinceraw_tparguments may actually be NULL at runtime. However, to preserve compatibility, it simulated theraw_tpaccesses as if the NULL marking was not present.One of the behaviors permitted by this simulation is offset modification for NULL pointers. Typically, this pattern is rejected by the verifier, and users make workarounds to prevent the compiler from producing such patterns. However, now that it is allowed, when the compiler emits such code, the offset modification is allowed and a
PTR_MAYBE_NULLraw_tparg with non-zero off can be formed.The failing example program had the following pseudo-code:
r0 = 1024;
r1 = ...; // r1 =trusted_or_null_(id=1)
r3 = r1; // r3 =trusted_or_null_(id=1)r1 =trusted_or_null_(id=1)r3 += r0; // r3 =trusted_or_null_(id=1, off=1024)
if r1 == 0 goto pc+X;At this point, while
mark_ptr_or_null_regwill seePTR_MAYBE_NULLand off == 0 for r1, it will notice non-zero off for r3, and theWARN_ON_ONCEwill fire, as the condition checks excluding register types do not includeraw_tpargument type.This is a pattern produced by LLVM, therefore it is hard to suppress it everywhere in BPF programs.
The right "generic" fix for this issue in general, will be permitting offset modification for
PTR_MAYBE_NULLpointers everywhere, and enforcing that the instruction operand of a conditional jump has the offset as zero. It's other copies may still have non-zero offset, and that is fine. But this is more involved and will take longer to integrate.Hence, for now, when we notice
raw_tpargs with off != 0 when unmarking NULL modifier, simply allocate such pointer a fresh id and remove them from the "id" set being currently operated on, and leave them as is without removingPTR_MAYBE_NULLmarking.Dereferencing such pointers will still work as the fixed commit allowed it for
raw_tpargs.This will mean that still, all registers with a given id and off = 0 will be unmarked, even if a register with off != 0 is NULL checked, but this shouldn't introducing any incorrectness. Just that any register with off != 0 excludes itself from the marking exercise by reassigning itself a new id.
Fixes cb4158ce8ec8 ("bpf: Mark raw_tp arguments with PTR_MAYBE_NULL")Reported-by Manu Bretelle <[email protected]>Signed-off-by Kumar Kartikeya Dwivedi <[email protected]>--- kernel/bpf/verifier.c | 44 ++++++++++++++++++++++++++++++++++++++----- 1 file changed, 39 insertions(+), 5 deletions(-)kernel/bpf/verifier.c +16
-1@@ -15335,7 +15335,8 @@ static int reg_set_min_max(struct bpf_verifier_env *env,return err; } -static void mark_ptr_or_null_reg (struct bpf_func_state *state, +static void mark_ptr_or_null_reg (struct bpf_verifier_env *env, +struct bpf_func_state *state,struct bpf_reg_state *reg,u32 id,bool is_null) {@@ -15352,6 +15353,38 @@ static void mark_ptr_or_null_reg(struct bpf_func_state *state,*/ if (WARN_ON_ONCE (reg->smin_value || reg->smax_value || !tnum_equals_const (reg->var_off,0 )))return ; +/* Unlike the MEM_ALLOC and NON_OWN_REF cases explicitly tested +* below, where verifier will set off != 0, we allow users to +* modify offset of PTR_MAYBE_NULL raw_tp args to preserve +* compatibility since they were not marked NULL in older +* kernels. This however means we may see a non-zero offset +* register when marking them non-NULL in verifier state. +* This can happen for the operand of the instruction: +* +* r1 = trusted_or_null_(id=1); +* if r1 == 0 goto X; +* +* or a copy when LLVM produces code like below: +* +* r1 = trusted_or_null_(id=1);
kernel/bpf/verifier.c static void mark_ptr_or_null_reg(struct bpf_func_state *state, · line 15379
Quoted 10 lines
kernel/bpf/verifier.c +10
-0+* r3 = r1; // r3 = trusted_or_null(id=1) +* r3 += K; // r3 = trusted_or_null_(id=1, off=K) +* if r1 == 0 goto X; // see r3.off != 0 when unmarking _or_null +* +* The right fix would be more generic: lift the restriction on +* modifying reg->off for PTR_MAYBE_NULL pointers, and only +* enforce it for the instruction operand of a NULL check, while +* allowing non-zero off for other registers, but this is future +* work. +*/
I think the comment is too verbose.
Especially considering that we're going to remove this hack in bpf-next.
I can trim it to bare minimum while applying if you're ok ?
Quoted 45 lines
kernel/bpf/verifier.c +13
-5+if (mask_raw_tp_reg_cond (env, reg) && reg->off) { +/* We don't reset reg->id back to 0, as it's unexpected +* when PTR_MAYBE_NULL is set. Simply give this reg a +* new id in case user decides to NULL check it again. +*/ + reg->id = ++env->id_gen; +return ; + }if (!(type_is_ptr_alloc_obj (reg->type) ||type_is_non_owning_ref (reg->type)) &&WARN_ON_ONCE (reg->off))return ;@@ -15385,7 +15418,8 @@ static void mark_ptr_or_null_reg(struct bpf_func_state *state,/* The logic is similar to find_good_pkt_pointers(), both could eventually * be folded together at some point. */ -static void mark_ptr_or_null_regs (struct bpf_verifier_state *vstate,u32 regno, +static void mark_ptr_or_null_regs (struct bpf_verifier_env *env, +struct bpf_verifier_state *vstate,u32 regno,bool is_null) {struct bpf_func_state *state = vstate->frame[vstate->curframe];@@ -15401,7 +15435,7 @@ static void mark_ptr_or_null_regs(struct bpf_verifier_state *vstate, u32 regno,WARN_ON_ONCE (release_reference_state (state, id));bpf_for_each_reg_in_vstate (vstate, state, reg, ({ -mark_ptr_or_null_reg (state, reg, id, is_null); +mark_ptr_or_null_reg (env, state, reg, id, is_null); })); }@@ -15827,9 +15861,9 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,/* Mark all identical registers in each branch as either * safe or unknown depending R == 0 or R != 0 conditional. */ -mark_ptr_or_null_regs (this_branch, insn->dst_reg, +mark_ptr_or_null_regs (env, this_branch, insn->dst_reg, opcode ==BPF_JNE ); -mark_ptr_or_null_regs (other_branch, insn->dst_reg, +mark_ptr_or_null_regs (env, other_branch, insn->dst_reg, opcode ==BPF_JEQ ); } else if (!try_match_pkt_pointers(insn, dst_reg, ®s[insn->src_reg], this_branch, other_branch) && --2.43.5
Kumar Kartikeya Dwivedi
maintainerRe: [PATCH bpf v1 1/2] bpf: Suppress warning for non-zero off raw_tp arg NULL check
Quoted 105 lines · Alexei Starovoitov
Quoted 89 lines · Kumar Kartikeya Dwivedi
The fixed commit began marking
raw_tparguments asPTR_MAYBE_NULLto avoid dead code elimination in the verifier, sinceraw_tparguments may actually be NULL at runtime. However, to preserve compatibility, it simulated theraw_tpaccesses as if the NULL marking was not present.One of the behaviors permitted by this simulation is offset modification for NULL pointers. Typically, this pattern is rejected by the verifier, and users make workarounds to prevent the compiler from producing such patterns. However, now that it is allowed, when the compiler emits such code, the offset modification is allowed and a
PTR_MAYBE_NULLraw_tparg with non-zero off can be formed.The failing example program had the following pseudo-code:
r0 = 1024;
r1 = ...; // r1 =trusted_or_null_(id=1)
r3 = r1; // r3 =trusted_or_null_(id=1)r1 =trusted_or_null_(id=1)r3 += r0; // r3 =trusted_or_null_(id=1, off=1024)
if r1 == 0 goto pc+X;At this point, while
mark_ptr_or_null_regwill seePTR_MAYBE_NULLand off == 0 for r1, it will notice non-zero off for r3, and theWARN_ON_ONCEwill fire, as the condition checks excluding register types do not includeraw_tpargument type.This is a pattern produced by LLVM, therefore it is hard to suppress it everywhere in BPF programs.
The right "generic" fix for this issue in general, will be permitting offset modification for
PTR_MAYBE_NULLpointers everywhere, and enforcing that the instruction operand of a conditional jump has the offset as zero. It's other copies may still have non-zero offset, and that is fine. But this is more involved and will take longer to integrate.Hence, for now, when we notice
raw_tpargs with off != 0 when unmarking NULL modifier, simply allocate such pointer a fresh id and remove them from the "id" set being currently operated on, and leave them as is without removingPTR_MAYBE_NULLmarking.Dereferencing such pointers will still work as the fixed commit allowed it for
raw_tpargs.This will mean that still, all registers with a given id and off = 0 will be unmarked, even if a register with off != 0 is NULL checked, but this shouldn't introducing any incorrectness. Just that any register with off != 0 excludes itself from the marking exercise by reassigning itself a new id.
Fixes cb4158ce8ec8 ("bpf: Mark raw_tp arguments with PTR_MAYBE_NULL")Reported-by Manu Bretelle <[email protected]>Signed-off-by Kumar Kartikeya Dwivedi <[email protected]>--- kernel/bpf/verifier.c | 44 ++++++++++++++++++++++++++++++++++++++----- 1 file changed, 39 insertions(+), 5 deletions(-)kernel/bpf/verifier.c +16
-1@@ -15335,7 +15335,8 @@ static int reg_set_min_max(struct bpf_verifier_env *env,return err; } -static void mark_ptr_or_null_reg (struct bpf_func_state *state, +static void mark_ptr_or_null_reg (struct bpf_verifier_env *env, +struct bpf_func_state *state,struct bpf_reg_state *reg,u32 id,bool is_null) {@@ -15352,6 +15353,38 @@ static void mark_ptr_or_null_reg(struct bpf_func_state *state,*/ if (WARN_ON_ONCE (reg->smin_value || reg->smax_value || !tnum_equals_const (reg->var_off,0 )))return ; +/* Unlike the MEM_ALLOC and NON_OWN_REF cases explicitly tested +* below, where verifier will set off != 0, we allow users to +* modify offset of PTR_MAYBE_NULL raw_tp args to preserve +* compatibility since they were not marked NULL in older +* kernels. This however means we may see a non-zero offset +* register when marking them non-NULL in verifier state. +* This can happen for the operand of the instruction: +* +* r1 = trusted_or_null_(id=1); +* if r1 == 0 goto X; +* +* or a copy when LLVM produces code like below: +* +* r1 = trusted_or_null_(id=1); kernel/bpf/verifier.c static void mark_ptr_or_null_reg(struct bpf_func_state *state, · line 15379
Quoted 10 lines
kernel/bpf/verifier.c +10
-0+* r3 = r1; // r3 = trusted_or_null(id=1) +* r3 += K; // r3 = trusted_or_null_(id=1, off=K) +* if r1 == 0 goto X; // see r3.off != 0 when unmarking _or_null +* +* The right fix would be more generic: lift the restriction on +* modifying reg->off for PTR_MAYBE_NULL pointers, and only +* enforce it for the instruction operand of a NULL check, while +* allowing non-zero off for other registers, but this is future +* work. +*/ I think the comment is too verbose.
Especially considering that we're going to remove this hack in bpf-next.
Quoted 1 line
I can trim it to bare minimum while applying if you're ok ?
No objections.
Kumar Kartikeya Dwivedi
maintainerPATCH 2/2 selftests/bpf: Add raw_tp tests for PTR_MAYBE_NULL marking
In reply to Kumar Kartikeya DwivediEnsure that pointers with off != 0 are never unmarked as PTR_MAYBE_NULL, pointers that have off == 0 continue getting unmarked, and pointers that don't get unmarked acquire a new id instead of resetting it to zero, so as to identify themselves uniquely and not hit other warnings where id == 0 is not expected with PTR_MAYBE_NULL.
--- .../selftests/bpf/prog_tests/raw_tp_null.c | 6 ++ .../selftests/bpf/progs/raw_tp_null_fail.c | 81 +++++++++++++++++++ 2 files changed, 87 insertions(+) create mode 100644 tools/testing/selftests/bpf/progs/raw_tp_null_fail.c
tools/testing/selftests/bpf/prog_tests/raw_tp_null.c +6 -0
@@ -3,6 +3,12 @@#include <test_progs.h> #include "raw_tp_null.skel.h" +#include "raw_tp_null_fail.skel.h" + +void test_raw_tp_null_fail (void ) +{ +RUN_TESTS (raw_tp_null_fail); +}void test_raw_tp_null (void ) {
tools/testing/selftests/bpf/progs/raw_tp_null_fail.c new file +81 -0
81 lines not on this page · raw message
Signature · 1 line
2.43.5
Eduard Zingerman
maintainerRe: [PATCH bpf v1 2/2] selftests/bpf: Add raw_tp tests for PTR_MAYBE_NULL marking
On Tue, 2024-12-03 at 18:41 -0800, Kumar Kartikeya Dwivedi wrote:
[...]
tools/testing/selftests/bpf/progs/raw_tp_null_fail.c line 37
Quoted 6 lines
tools/testing/selftests/bpf/progs/raw_tp_null_fail.c new file +6
-0+/* r2 with offset is checked, which marks r1 with off=0 as non-NULL */ +SEC("tp_btf/bpf_testmod_test_raw_tp_null") +__failure +__msg("3: (07) r2 += 8 ; R2_w=trusted_ptr_or_null_sk_buff(id=1,off=8)") +__msg("4: (15) if r2 == 0x0 goto pc+2 ; R2_w=trusted_ptr_or_null_sk_buff(id=2,off=8)") +__msg ("5: (bf) r1 = r1 ; R1_w=trusted_ptr_sk_buff()" )
This looks like a bug.
'r1 != 0' does not follow from 'r2 == r1 + 8 and r2 != 0'.
Quoted 16 lines
tools/testing/selftests/bpf/progs/raw_tp_null_fail.c new file +16
-0+int BPF_PROG (test_raw_tp_null_copy_check_with_off ,struct sk_buff *skb) +{ + asmvolatile ( +"r1 = *(u64 *)(r1 +0); \ +r2 = r1; \ +r3 = 0; \ +r2 += 8; \ +if r2 == 0 goto jmp2; \ +r1 = r1; \ +*(u64 *)(r3 +0) = r3; \ +jmp2: " + :: + : __clobber_all + ); +return 0 ; +}
[...]
Kumar Kartikeya Dwivedi
maintainerRe: [PATCH bpf v1 2/2] selftests/bpf: Add raw_tp tests for PTR_MAYBE_NULL marking
Quoted 5 lines · Eduard Zingerman
On Tue, 2024-12-03 at 18:41 -0800, Kumar Kartikeya Dwivedi wrote:
[...]
Quoted 10 lines
tools/testing/selftests/bpf/progs/raw_tp_null_fail.c line 37
Quoted 6 lines
tools/testing/selftests/bpf/progs/raw_tp_null_fail.c new file +6
-0+/* r2 with offset is checked, which marks r1 with off=0 as non-NULL */ +SEC("tp_btf/bpf_testmod_test_raw_tp_null") +__failure +__msg("3: (07) r2 += 8 ; R2_w=trusted_ptr_or_null_sk_buff(id=1,off=8)") +__msg("4: (15) if r2 == 0x0 goto pc+2 ; R2_w=trusted_ptr_or_null_sk_buff(id=2,off=8)") +__msg ("5: (bf) r1 = r1 ; R1_w=trusted_ptr_sk_buff()" )This looks like a bug.
'r1 != 0' does not follow from 'r2 == r1 + 8 and r2 != 0'.
Hmm, yes, it's broken.
I am realizing where we do it now will walk r1 first and we'll not see r2 off != 0 until after we mark it already.
I guess we need to do the check sooner outside this function in mark_ptr_or_null_regs.
There we have the register being operated on, so if off != 0 we don't walk all regs in state.
Do you think that should fix this?
Quoted 18 lines
Quoted 16 lines
tools/testing/selftests/bpf/progs/raw_tp_null_fail.c new file +16
-0+int BPF_PROG (test_raw_tp_null_copy_check_with_off ,struct sk_buff *skb) +{ + asmvolatile ( +"r1 = *(u64 *)(r1 +0); \ +r2 = r1; \ +r3 = 0; \ +r2 += 8; \ +if r2 == 0 goto jmp2; \ +r1 = r1; \ +*(u64 *)(r3 +0) = r3; \ +jmp2: " + :: + : __clobber_all + ); +return 0 ; +}[...]
Kumar Kartikeya Dwivedi
maintainerRe: [PATCH bpf v1 2/2] selftests/bpf: Add raw_tp tests for PTR_MAYBE_NULL marking
Quoted 18 lines · Kumar Kartikeya Dwivedi
Quoted 5 lines · Eduard Zingerman
On Tue, 2024-12-03 at 18:41 -0800, Kumar Kartikeya Dwivedi wrote:
[...]
Quoted 10 lines
tools/testing/selftests/bpf/progs/raw_tp_null_fail.c line 37
Quoted 6 lines
tools/testing/selftests/bpf/progs/raw_tp_null_fail.c new file +6
-0+/* r2 with offset is checked, which marks r1 with off=0 as non-NULL */ +SEC("tp_btf/bpf_testmod_test_raw_tp_null") +__failure +__msg("3: (07) r2 += 8 ; R2_w=trusted_ptr_or_null_sk_buff(id=1,off=8)") +__msg("4: (15) if r2 == 0x0 goto pc+2 ; R2_w=trusted_ptr_or_null_sk_buff(id=2,off=8)") +__msg ("5: (bf) r1 = r1 ; R1_w=trusted_ptr_sk_buff()" )This looks like a bug.
'r1 != 0' does not follow from 'r2 == r1 + 8 and r2 != 0'.
Quoted 7 lines
Hmm, yes, it's broken.
I am realizing where we do it now will walk r1 first and we'll not see r2 off != 0 until after we mark it already.
I guess we need to do the check sooner outside this function inmark_ptr_or_null_regs.
There we have the register being operated on, so if off != 0 we don't walk all regs in state.
What this will do in both cases::
First, avoid walking states when off != 0, and reset id. If off == 0, go inside mark_ptr_or_null_reg and walk all regs, and remove marks for those with off != 0.
Quoted 21 lines
Do you think that should fix this?
Quoted 18 lines
Quoted 16 lines
tools/testing/selftests/bpf/progs/raw_tp_null_fail.c new file +16
-0+int BPF_PROG (test_raw_tp_null_copy_check_with_off ,struct sk_buff *skb) +{ + asmvolatile ( +"r1 = *(u64 *)(r1 +0); \ +r2 = r1; \ +r3 = 0; \ +r2 += 8; \ +if r2 == 0 goto jmp2; \ +r1 = r1; \ +*(u64 *)(r3 +0) = r3; \ +jmp2: " + :: + : __clobber_all + ); +return 0 ; +}[...]
Re: [PATCH bpf v1 2/2] selftests/bpf: Add raw_tp tests for PTR_MAYBE_NULL marking
Quoted 28 lines · Kumar Kartikeya Dwivedi
Quoted 18 lines · Kumar Kartikeya Dwivedi
Quoted 5 lines · Eduard Zingerman
On Tue, 2024-12-03 at 18:41 -0800, Kumar Kartikeya Dwivedi wrote:
[...]
Quoted 10 lines
tools/testing/selftests/bpf/progs/raw_tp_null_fail.c line 37
Quoted 6 lines
tools/testing/selftests/bpf/progs/raw_tp_null_fail.c new file +6
-0+/* r2 with offset is checked, which marks r1 with off=0 as non-NULL */ +SEC("tp_btf/bpf_testmod_test_raw_tp_null") +__failure +__msg("3: (07) r2 += 8 ; R2_w=trusted_ptr_or_null_sk_buff(id=1,off=8)") +__msg("4: (15) if r2 == 0x0 goto pc+2 ; R2_w=trusted_ptr_or_null_sk_buff(id=2,off=8)") +__msg ("5: (bf) r1 = r1 ; R1_w=trusted_ptr_sk_buff()" )This looks like a bug.
'r1 != 0' does not follow from 'r2 == r1 + 8 and r2 != 0'.Quoted 7 lines
Hmm, yes, it's broken.
I am realizing where we do it now will walk r1 first and we'll not see r2 off != 0 until after we mark it already.
I guess we need to do the check sooner outside this function inmark_ptr_or_null_regs.
There we have the register being operated on, so if off != 0 we don't walk all regs in state.
Quoted 4 lines
What this will do in both cases::
First, avoid walking states when off != 0, and reset id. If off == 0, go insidemark_ptr_or_null_regand walk all regs, and remove marks for those with off != 0.
That's getting intrusive.
How about we reset id=0 in adjust_ptr_min_max_vals()
right after we suppressed "null-check it first" message for raw_tp-s.
That will address the issue as well, right?
Kumar Kartikeya Dwivedi
maintainerRe: [PATCH bpf v1 2/2] selftests/bpf: Add raw_tp tests for PTR_MAYBE_NULL marking
Quoted 36 lines · Alexei Starovoitov
Quoted 28 lines · Kumar Kartikeya Dwivedi
Quoted 18 lines · Kumar Kartikeya Dwivedi
Quoted 5 lines · Eduard Zingerman
On Tue, 2024-12-03 at 18:41 -0800, Kumar Kartikeya Dwivedi wrote:
[...]
Quoted 10 lines
tools/testing/selftests/bpf/progs/raw_tp_null_fail.c line 37
Quoted 6 lines
tools/testing/selftests/bpf/progs/raw_tp_null_fail.c new file +6
-0+/* r2 with offset is checked, which marks r1 with off=0 as non-NULL */ +SEC("tp_btf/bpf_testmod_test_raw_tp_null") +__failure +__msg("3: (07) r2 += 8 ; R2_w=trusted_ptr_or_null_sk_buff(id=1,off=8)") +__msg("4: (15) if r2 == 0x0 goto pc+2 ; R2_w=trusted_ptr_or_null_sk_buff(id=2,off=8)") +__msg ("5: (bf) r1 = r1 ; R1_w=trusted_ptr_sk_buff()" )This looks like a bug.
'r1 != 0' does not follow from 'r2 == r1 + 8 and r2 != 0'.Quoted 7 lines
Hmm, yes, it's broken.
I am realizing where we do it now will walk r1 first and we'll not see r2 off != 0 until after we mark it already.
I guess we need to do the check sooner outside this function inmark_ptr_or_null_regs.
There we have the register being operated on, so if off != 0 we don't walk all regs in state.Quoted 4 lines
What this will do in both cases::
First, avoid walking states when off != 0, and reset id. If off == 0, go insidemark_ptr_or_null_regand walk all regs, and remove marks for those with off != 0.
Quoted 5 lines
That's getting intrusive.
How about we reset id=0 inadjust_ptr_min_max_vals()
right after we suppressed "null-check it first" message for raw_tp-s.That will address the issue as well, right?
Yes (minor detail, it needs to be reset to a new id, otherwise we have warn on maybe_null set but !reg->id, but the idea is the same). Let's see what Eduard thinks and then I can give it a go.
Eduard Zingerman
maintainerRe: [PATCH bpf v1 2/2] selftests/bpf: Add raw_tp tests for PTR_MAYBE_NULL marking
On Wed, 2024-12-04 at 21:48 +0100, Kumar Kartikeya Dwivedi wrote:
[...[
(A) ----.
|
vQuoted 4 lines
Quoted 4 lines
Quoted 4 lines
What this will do in both cases::
First, avoid walking states when off != 0, and reset id. If off == 0, go insidemark_ptr_or_null_regand walk all regs, and remove marks for those with off != 0.
(B) ----.
|
vQuoted 9 lines
Quoted 5 lines
That's getting intrusive.
How about we reset id=0 inadjust_ptr_min_max_vals()
right after we suppressed "null-check it first" message for raw_tp-s.That will address the issue as well, right?
Yes (minor detail, it needs to be reset to a new id, otherwise we have warn on
maybe_nullset but !reg->id, but the idea is the same). Let's see what Eduard thinks and then I can give it a go.
Sorry for delay.
I like what Kumar is proposing in (A) because it could be generalized:
there is no real harm in doing 'r2 = r1; r2 += 8; r1 != 0; ...' and what Kumar suggests could be used to lift the "null-check it first ..." restriction.
However, as far as I understand, the plan is to fix this by generating two entry tracepoint states: one with parameter as null, another with parameter not-null (all combinations for every parameter). If that is the plan, what Alexei suggests in (B) is simpler.
Re: [PATCH bpf v1 2/2] selftests/bpf: Add raw_tp tests for PTR_MAYBE_NULL marking
Quoted 26 lines · Eduard Zingerman
On Wed, 2024-12-04 at 21:48 +0100, Kumar Kartikeya Dwivedi wrote:
[...[
(A) ----.
| vQuoted 4 lines
Quoted 4 lines
Quoted 4 lines
What this will do in both cases::
First, avoid walking states when off != 0, and reset id. If off == 0, go insidemark_ptr_or_null_regand walk all regs, and remove marks for those with off != 0.(B) ----.
| vQuoted 9 lines
Quoted 5 lines
That's getting intrusive.
How about we reset id=0 inadjust_ptr_min_max_vals()
right after we suppressed "null-check it first" message for raw_tp-s.That will address the issue as well, right?
Yes (minor detail, it needs to be reset to a new id, otherwise we have warn on
maybe_nullset but !reg->id, but the idea is the same). Let's see what Eduard thinks and then I can give it a go.
Quoted 6 lines
Sorry for delay.
I like what Kumar is proposing in (A) because it could be generalized:
there is no real harm in doing 'r2 = r1; r2 += 8; r1 != 0; ...' and what Kumar suggests could be used to lift the "null-check it first ..." restriction.
I don't see how it can be generalized.
Also 'avoid walking states when off != 0' is far from simple. We call into mark_ptr_or_null_regs() with id == 0 already and with reg->off != 0 for RCU and alloc_obj.
'avoid walking with off != 0' doesn't look trivial. It would need to be special cased to raw_tp and some other conditions.
I could be missing something.
Let's see how patches look.
Quoted 4 lines
However, as far as I understand, the plan is to fix this by generating two entry tracepoint states: one with parameter as null, another with parameter not-null (all combinations for every parameter). If that is the plan, what Alexei suggests in (B) is simpler.
Eduard Zingerman
maintainerRe: [PATCH bpf v1 2/2] selftests/bpf: Add raw_tp tests for PTR_MAYBE_NULL marking
Quoted 34 lines · Alexei Starovoitov
Quoted 26 lines · Eduard Zingerman
On Wed, 2024-12-04 at 21:48 +0100, Kumar Kartikeya Dwivedi wrote:
[...[
(A) ----.
| vQuoted 4 lines
Quoted 4 lines
Quoted 4 lines
What this will do in both cases::
First, avoid walking states when off != 0, and reset id. If off == 0, go insidemark_ptr_or_null_regand walk all regs, and remove marks for those with off != 0.(B) ----.
| vQuoted 9 lines
Quoted 5 lines
That's getting intrusive.
How about we reset id=0 inadjust_ptr_min_max_vals()
right after we suppressed "null-check it first" message for raw_tp-s.That will address the issue as well, right?
Yes (minor detail, it needs to be reset to a new id, otherwise we have warn on
maybe_nullset but !reg->id, but the idea is the same). Let's see what Eduard thinks and then I can give it a go.Quoted 6 lines
Sorry for delay.
I like what Kumar is proposing in (A) because it could be generalized:
there is no real harm in doing 'r2 = r1; r2 += 8; r1 != 0; ...' and what Kumar suggests could be used to lift the "null-check it first ..." restriction.
Quoted 4 lines
I don't see how it can be generalized.
Also 'avoid walking states when off != 0' is far from simple. We call intomark_ptr_or_null_regs()with id == 0 already and withreg->off!= 0 for RCU andalloc_obj.
I did not try to implement this, so there might be a devil in the details. The naive approach looks as below.
Suppose we want to allow 'rX += K' when rX is PTR_MAYBE_NULL. Such operations generate a set of pointers with different .off values but same .id .
For a regular (non raw_tp) case:
- dereferencing PTR_MAYBE_NULL is disallowed;
- if there is a check 'if rY != 0' and rY.off == 0,
the non-null status could be propagated to each
register in a set (and PTR_MAYBE_NULL mark removed);
- if there is a check 'if rY != 0' and rY.off != 0, nothing happens, no marks are changed.
For a raw_tp case:
- dereferencing PTR_MAYBE_NULL is allowed (as it is already);
- the mechanics for 'if rY != 0' and rY.off ==/!= 0 can remain the same, nothing is wrong with removing PTR_MAYBE_NULL marks from such pointers.
Quoted 11 lines
'avoid walking with off != 0' doesn't look trivial. It would need to be special cased to
raw_tpand some other conditions.
I could be missing something.Let's see how patches look.
Quoted 4 lines
However, as far as I understand, the plan is to fix this by generating two entry tracepoint states: one with parameter as null, another with parameter not-null (all combinations for every parameter). If that is the plan, what Alexei suggests in (B) is simpler.
Kumar Kartikeya Dwivedi
maintainerRe: [PATCH bpf v1 2/2] selftests/bpf: Add raw_tp tests for PTR_MAYBE_NULL marking
Quoted 44 lines · Eduard Zingerman
Quoted 34 lines · Alexei Starovoitov
Quoted 26 lines · Eduard Zingerman
On Wed, 2024-12-04 at 21:48 +0100, Kumar Kartikeya Dwivedi wrote:
[...[
(A) ----.
| vQuoted 4 lines
Quoted 4 lines
Quoted 4 lines
What this will do in both cases::
First, avoid walking states when off != 0, and reset id. If off == 0, go insidemark_ptr_or_null_regand walk all regs, and remove marks for those with off != 0.(B) ----.
| vQuoted 9 lines
Quoted 5 lines
That's getting intrusive.
How about we reset id=0 inadjust_ptr_min_max_vals()
right after we suppressed "null-check it first" message for raw_tp-s.That will address the issue as well, right?
Yes (minor detail, it needs to be reset to a new id, otherwise we have warn on
maybe_nullset but !reg->id, but the idea is the same). Let's see what Eduard thinks and then I can give it a go.Quoted 6 lines
Sorry for delay.
I like what Kumar is proposing in (A) because it could be generalized:
there is no real harm in doing 'r2 = r1; r2 += 8; r1 != 0; ...' and what Kumar suggests could be used to lift the "null-check it first ..." restriction.Quoted 4 lines
I don't see how it can be generalized.
Also 'avoid walking states when off != 0' is far from simple. We call intomark_ptr_or_null_regs()with id == 0 already and withreg->off!= 0 for RCU andalloc_obj.I did not try to implement this, so there might be a devil in the details. The naive approach looks as below.
Quoted 10 lines
Suppose we want to allow 'rX += K' when rX is
PTR_MAYBE_NULL. Such operations generate a set of pointers with different .off values but same .id .
For a regular (nonraw_tp) case:
- dereferencingPTR_MAYBE_NULLis disallowed;
- if there is a check 'if rY != 0' and rY.off == 0,
the non-null status could be propagated to each
register in a set (andPTR_MAYBE_NULLmark removed);
- if there is a check 'if rY != 0' and rY.off != 0, nothing happens, no marks are changed.
Yes, also I realized after some thinking that when rY with off != 0 is checked, it just needs to be a no-op (in context of this solution), we don't need to remove it from the set. Later if rX with off == 0 sharing the same id is checked rY should be marked not null.
Quoted 5 lines
For a
raw_tpcase:
- dereferencingPTR_MAYBE_NULLis allowed (as it is already);
- the mechanics for 'if rY != 0' and rY.off ==/!= 0 can remain the same, nothing is wrong with removingPTR_MAYBE_NULLmarks from such pointers.
Yes, it can be generalized, this solution to generalize to all types does not require the state forking approach, which is different.
It is getting late for me here so I will continue looking at this tomorrow, but I can do this for raw_tp in this patch as a fix for the warning.
Then, I can send a follow up doing it for all pointer types against bpf-next where can continue discussion based on concrete code.
Alexei said he was giving the state forking a go in parallel (which is much more involved and impact on veristat needs to be analyzed).
Anyhow, I will continue tomorrow. Let me know what you think.
Quoted 13 lines
Quoted 12 lines
'avoid walking with off != 0' doesn't look trivial. It would need to be special cased to
raw_tpand some other conditions.
I could be missing something.Let's see how patches look.
Quoted 4 lines
However, as far as I understand, the plan is to fix this by generating two entry tracepoint states: one with parameter as null, another with parameter not-null (all combinations for every parameter). If that is the plan, what Alexei suggests in (B) is simpler.