infer packet range for 'if pkt ==/!= pkt_end' instructions
Subsystems (4)
Eduard Zingerman
maintainercover infer packet range for 'if pkt ==/!= pkt_end' instructions
As suggested by Maciej Żenczykowski in [1], extend try_match_pkt_pointers to allow verification of BPF, generated for C code like below:
if (data + 42 != data_end) { ... }
Also simplify try_match_pkt_pointers to avoid checking both 'pkt <op> pkt_end' and 'pkt_end <op> pkt' conditions, as suggested by Andrii Nakryiko.
[1] https://lore.kernel.org/bpf/CAHo-Oow5V2u4ZYvzuR8NmJmFDPNYp0pQDJX66rZqUjFHvhx82A@mail.gmail.com/
Eduard Zingerman (3):
bpf: simplify try_match_pkt_pointers()
bpf: infer packet range for 'if pkt ==/!= pkt_end' comparisons selftests/bpf: test packet range inference for 'if pkt ==/!= pkt_end'
kernel/bpf/verifier.c | 112 ++++---------- .../bpf/progs/verifier_direct_packet_access.c | 138 ++++++++++++++++++ 2 files changed, 170 insertions(+), 80 deletions(-)
Signature · 1 line
2.43.0
Eduard Zingerman
maintainerPATCH 1/3 bpf: simplify try_match_pkt_pointers()
Reduce number of cases handled in try_match_pkt_pointers() to <pkt_data> <op> <pkt_end> or <pkt_meta> <op> <pkt_data> by flipping opcode.
--- kernel/bpf/verifier.c | 104 ++++++++++-------------------------------- 1 file changed, 24 insertions(+), 80 deletions(-)
kernel/bpf/verifier.c +24 -80
@@ -14677,6 +14677,9 @@ static bool try_match_pkt_pointers(const struct bpf_insn *insn,struct bpf_verifier_state *this_branch, struct bpf_verifier_state *other_branch) { + int opcode = BPF_OP(insn->code); +int dst_regno = insn->dst_reg; +if (BPF_SRC (insn->code) !=BPF_X )return false;
@@ -14684,90 +14687,31 @@ static bool try_match_pkt_pointers(const struct bpf_insn *insn,if (BPF_CLASS (insn->code) ==BPF_JMP32 )return false; -switch (BPF_OP (insn->code)) { +if (dst_reg->type ==PTR_TO_PACKET_END || + src_reg->type ==PTR_TO_PACKET_META ) { +swap (src_reg, dst_reg); + dst_regno = insn->src_reg; + opcode =flip_opcode (opcode); + } + +if ((dst_reg->type !=PTR_TO_PACKET || + src_reg->type !=PTR_TO_PACKET_END ) && + (dst_reg->type !=PTR_TO_PACKET_META || + !reg_is_init_pkt_pointer (src_reg,PTR_TO_PACKET ))) +return false; + +switch (opcode) {case BPF_JGT : -if ((dst_reg->type ==PTR_TO_PACKET && - src_reg->type ==PTR_TO_PACKET_END ) || - (dst_reg->type ==PTR_TO_PACKET_META && -reg_is_init_pkt_pointer (src_reg,PTR_TO_PACKET ))) { -/* pkt_data' > pkt_end, pkt_meta' > pkt_data */ -find_good_pkt_pointers (this_branch, dst_reg, - dst_reg->type, false); -mark_pkt_end (other_branch, insn->dst_reg, true); - }else if ((dst_reg->type ==PTR_TO_PACKET_END && - src_reg->type ==PTR_TO_PACKET ) || - (reg_is_init_pkt_pointer (dst_reg,PTR_TO_PACKET ) && - src_reg->type ==PTR_TO_PACKET_META )) { -/* pkt_end > pkt_data', pkt_data > pkt_meta' */ -find_good_pkt_pointers (other_branch, src_reg, - src_reg->type, true); -mark_pkt_end (this_branch, insn->src_reg, false); - }else { -return false; - } -break ; -case BPF_JLT : -if ((dst_reg->type ==PTR_TO_PACKET && - src_reg->type ==PTR_TO_PACKET_END ) || - (dst_reg->type ==PTR_TO_PACKET_META && -reg_is_init_pkt_pointer (src_reg,PTR_TO_PACKET ))) { -/* pkt_data' < pkt_end, pkt_meta' < pkt_data */ -find_good_pkt_pointers (other_branch, dst_reg, - dst_reg->type, true); -mark_pkt_end (this_branch, insn->dst_reg, false); - }else if ((dst_reg->type ==PTR_TO_PACKET_END && - src_reg->type ==PTR_TO_PACKET ) || - (reg_is_init_pkt_pointer (dst_reg,PTR_TO_PACKET ) && - src_reg->type ==PTR_TO_PACKET_META )) { -/* pkt_end < pkt_data', pkt_data > pkt_meta' */ -find_good_pkt_pointers (this_branch, src_reg, - src_reg->type, false); -mark_pkt_end (other_branch, insn->src_reg, true); - }else { -return false; - } -break ;case BPF_JGE : -if ((dst_reg->type ==PTR_TO_PACKET && - src_reg->type ==PTR_TO_PACKET_END ) || - (dst_reg->type ==PTR_TO_PACKET_META && -reg_is_init_pkt_pointer (src_reg,PTR_TO_PACKET ))) { -/* pkt_data' >= pkt_end, pkt_meta' >= pkt_data */ -find_good_pkt_pointers (this_branch, dst_reg, - dst_reg->type, true); -mark_pkt_end (other_branch, insn->dst_reg, false); - }else if ((dst_reg->type ==PTR_TO_PACKET_END && - src_reg->type ==PTR_TO_PACKET ) || - (reg_is_init_pkt_pointer (dst_reg,PTR_TO_PACKET ) && - src_reg->type ==PTR_TO_PACKET_META )) { -/* pkt_end >= pkt_data', pkt_data >= pkt_meta' */ -find_good_pkt_pointers (other_branch, src_reg, - src_reg->type, false); -mark_pkt_end (this_branch, insn->src_reg, true); - }else { -return false; - } +/* pkt_data >/>= pkt_end, pkt_meta >/>= pkt_data */ +find_good_pkt_pointers (this_branch, dst_reg, dst_reg->type, opcode ==BPF_JGE ); +mark_pkt_end (other_branch, dst_regno, opcode ==BPF_JGT );break ; +case BPF_JLT :case BPF_JLE : -if ((dst_reg->type ==PTR_TO_PACKET && - src_reg->type ==PTR_TO_PACKET_END ) || - (dst_reg->type ==PTR_TO_PACKET_META && -reg_is_init_pkt_pointer (src_reg,PTR_TO_PACKET ))) { -/* pkt_data' <= pkt_end, pkt_meta' <= pkt_data */ -find_good_pkt_pointers (other_branch, dst_reg, - dst_reg->type, false); -mark_pkt_end (this_branch, insn->dst_reg, true); - }else if ((dst_reg->type ==PTR_TO_PACKET_END && - src_reg->type ==PTR_TO_PACKET ) || - (reg_is_init_pkt_pointer (dst_reg,PTR_TO_PACKET ) && - src_reg->type ==PTR_TO_PACKET_META )) { -/* pkt_end <= pkt_data', pkt_data <= pkt_meta' */ -find_good_pkt_pointers (this_branch, src_reg, - src_reg->type, true); -mark_pkt_end (other_branch, insn->src_reg, false); - }else { -return false; - } +/* pkt_data </<= pkt_end, pkt_meta </<= pkt_data */ +find_good_pkt_pointers (other_branch, dst_reg, dst_reg->type, opcode ==BPF_JLT ); +mark_pkt_end (this_branch, dst_regno, opcode ==BPF_JLE );break ;default :return false;
Signature · 1 line
2.43.0
Eduard Zingerman
maintainerPATCH 2/3 bpf: infer packet range for 'if pkt ==/!= pkt_end' comparisons
In reply to Eduard ZingermanExtend try_match_pkt_pointers() to handle == and != operations. For instruction:
.--------------- pointer to packet with some range R
| .--------- pointer to packet end
v vif rA == rB goto ...
It is valid to infer that R bytes are available in packet. This change should allow verification of BPF generated for C code like below:
if (data + 42 != data_end) { ... }
--- kernel/bpf/verifier.c | 8 ++++++++ 1 file changed, 8 insertions(+)
kernel/bpf/verifier.c +8 -0
@@ -14677,6 +14677,7 @@ static bool try_match_pkt_pointers(const struct bpf_insn *insn,struct bpf_verifier_state *this_branch, struct bpf_verifier_state *other_branch) { + struct bpf_verifier_state *eq_branch;int opcode =BPF_OP (insn->code);int dst_regno = insn->dst_reg;
@@ -14713,6 +14714,13 @@ static bool try_match_pkt_pointers(const struct bpf_insn *insn,find_good_pkt_pointers (other_branch, dst_reg, dst_reg->type, opcode ==BPF_JLT );mark_pkt_end (this_branch, dst_regno, opcode ==BPF_JLE );break ; +case BPF_JEQ : +case BPF_JNE : +/* pkt_data ==/!= pkt_end, pkt_meta ==/!= pkt_data */ + eq_branch = opcode ==BPF_JEQ ? other_branch : this_branch; +find_good_pkt_pointers (eq_branch, dst_reg, dst_reg->type, true); +mark_pkt_end (eq_branch, dst_regno, false); +break ;default :return false; }
Signature · 1 line
2.43.0
Eduard Zingerman
maintainerPATCH 3/3 selftests/bpf: test packet range inference for 'if pkt ==/!= pkt_end'
In reply to Eduard ZingermanCheck that the following cases are handled by verifier:
- packet access after 'if pkt_data + const != pkt_end' (positive and negative cases);
- packet access after 'if pkt_data + const == pkt_end' (positive and negative cases);
- packet metadata access after 'if pkt_meta + const != pkt_data';
- packet metadata access after 'if pkt_data != pkt_meta + const';
--- .../bpf/progs/verifier_direct_packet_access.c | 138 ++++++++++++++++++ 1 file changed, 138 insertions(+)
tools/testing/selftests/bpf/progs/verifier_direct_packet_access.c +138 -0
@@ -800,4 +800,142 @@ l0_%=: /* exit(0) */ \ : __clobber_all); } +SEC("tc") +__success __log_level(2) +__msg("if r3 != r2 goto pc+1 ; R2_w=pkt_end() R3_w=pkt(off=8,r=0xffffffffffffffff)") +__naked void data_plus_const_neq_pkt_end (void ) +{ + asmvolatile (" \ +r9 = r1; \ +r1 = *(u32*)(r9 + %[__sk_buff_data]); \ +r2 = *(u32*)(r9 + %[__sk_buff_data_end]); \ +r3 = r1; \ +r3 += 8; \ +if r3 != r2 goto 1f; \ +r1 = *(u64 *)(r1 + 0); \ +1: \ +r0 = 0; \ +exit; \ +" : + : __imm_const(__sk_buff_data, offsetof(struct __sk_buff, data)), +__imm_const (__sk_buff_data_end, offsetof(struct __sk_buff , data_end)) + : __clobber_all); +} + +SEC("tc") +__failure __log_level(2) +__msg("8: R1=pkt(r=0) R2=pkt_end() R3=pkt(off=8,r=0)") +__msg("invalid access to packet, off=0 size=8, R1(id=0,off=0,r=0)") +__naked void data_plus_const_neq_pkt_end_negative (void ) +{ + asmvolatile (" \ +r9 = r1; \ +r1 = *(u32*)(r9 + %[__sk_buff_data]); \ +r2 = *(u32*)(r9 + %[__sk_buff_data_end]); \ +r3 = r1; \ +r3 += 8; \ +if r3 != r2 goto 1f; \ +r0 = 0; \ +exit; \ +1: \ +r1 = *(u64 *)(r1 + 0); \ +r0 = 0; \ +exit; \ +" : + : __imm_const(__sk_buff_data, offsetof(struct __sk_buff, data)), +__imm_const (__sk_buff_data_end, offsetof(struct __sk_buff , data_end)) + : __clobber_all); +} + +SEC("tc") +__success __log_level(2) +__msg("8: R1=pkt(r=9) R2=pkt_end() R3=pkt(off=8,r=0xffffffffffffffff)") +__naked void data_plus_const_eq_pkt_end (void ) +{ + asmvolatile (" \ +r9 = r1; \ +r1 = *(u32*)(r9 + %[__sk_buff_data]); \ +r2 = *(u32*)(r9 + %[__sk_buff_data_end]); \ +r3 = r1; \ +r3 += 8; \ +if r3 == r2 goto 1f; \ +r0 = 0; \ +exit; \ +1: \ +r1 = *(u64 *)(r1 + 0); \ +r0 = 0; \ +exit; \ +" : + : __imm_const(__sk_buff_data, offsetof(struct __sk_buff, data)), +__imm_const (__sk_buff_data_end, offsetof(struct __sk_buff , data_end)) + : __clobber_all); +} + +SEC("tc") +__failure __log_level(2) +__msg("if r3 == r2 goto pc+3 ; R2_w=pkt_end() R3_w=pkt(off=8,r=0)") +__msg("invalid access to packet, off=0 size=8, R1(id=0,off=0,r=0)") +__naked void data_plus_const_eq_pkt_end_negative (void ) +{ + asmvolatile (" \ +r9 = r1; \ +r1 = *(u32*)(r9 + %[__sk_buff_data]); \ +r2 = *(u32*)(r9 + %[__sk_buff_data_end]); \ +r3 = r1; \ +r3 += 8; \ +if r3 == r2 goto 1f; \ +r1 = *(u64 *)(r1 + 0); \ +r0 = 0; \ +exit; \ +1: \ +r0 = 0; \ +exit; \ +" : + : __imm_const(__sk_buff_data, offsetof(struct __sk_buff, data)), +__imm_const (__sk_buff_data_end, offsetof(struct __sk_buff , data_end)) + : __clobber_all); +} + +SEC("tc") +__success +__naked void pkt_meta_plus_const_neq_pkt_data (void ) +{ + asmvolatile (" \ +r9 = r1; \ +r1 = *(u32*)(r9 + %[__sk_buff_data_meta]); \ +r2 = *(u32*)(r9 + %[__sk_buff_data]); \ +r3 = r1; \ +r3 += 8; \ +if r3 != r2 goto 1f; \ +r1 = *(u64 *)(r1 + 0); \ +1: \ +r0 = 0; \ +exit; \ +" : + : __imm_const(__sk_buff_data, offsetof(struct __sk_buff, data)), +__imm_const (__sk_buff_data_meta, offsetof(struct __sk_buff , data_meta)) + : __clobber_all); +} + +SEC("tc") +__success +__naked void pkt_data_neq_pkt_meta_plus_const (void ) +{ + asmvolatile (" \ +r9 = r1; \ +r1 = *(u32*)(r9 + %[__sk_buff_data_meta]); \ +r2 = *(u32*)(r9 + %[__sk_buff_data]); \ +r3 = r1; \ +r3 += 8; \ +if r2 != r3 goto 1f; \ +r1 = *(u64 *)(r1 + 0); \ +1: \ +r0 = 0; \ +exit; \ +" : + : __imm_const(__sk_buff_data, offsetof(struct __sk_buff, data)), +__imm_const (__sk_buff_data_meta, offsetof(struct __sk_buff , data_meta)) + : __clobber_all); +} + char _license[] SEC("license") = "GPL";
Signature · 1 line
2.43.0
Re: [PATCH bpf-next 2/3] bpf: infer packet range for 'if pkt ==/!= pkt_end' comparisons
In reply to Eduard Zingerman(I've looked at all 3 patches, and they seem fine... but I don't claim to understand the intricacies of the verifier/registers/etc well enough to be certain)
Quoted 8 lines · Eduard Zingerman
Extend
try_match_pkt_pointers()to handle == and != operations. For instruction:.--------------- pointer to packet with some range R | .--------- pointer to packet end v vif rA == rB goto ...
it's possible this would be better without the 'goto' as just 'if (rA == rB) ...'
Quoted 6 lines
It is valid to infer that R bytes are available in packet. This change should allow verification of BPF generated for C code like below:
if (data + 42 !=
data_end) { ... }
this should probably be:
if (data + 42 != data_end) return;
...
Quoted 37 lines
Suggested-by Maciej Żenczykowski <[email protected]>Link https://lore.kernel.org/bpf/CAHo-Oow5V2u4ZYvzuR8NmJmFDPNYp0pQDJX66rZqUjFHvhx82A@mail.gmail.com/ open hereSigned-off-by Eduard Zingerman <[email protected]>--- kernel/bpf/verifier.c | 8 ++++++++ 1 file changed, 8 insertions(+)kernel/bpf/verifier.c +8
-1@@ -14677,6 +14677,7 @@ static bool try_match_pkt_pointers(const struct bpf_insn *insn,struct bpf_verifier_state *this_branch, struct bpf_verifier_state *other_branch) { + struct bpf_verifier_state *eq_branch;int opcode =BPF_OP (insn->code);int dst_regno = insn->dst_reg;@@ -14713,6 +14714,13 @@ static bool try_match_pkt_pointers(const struct bpf_insn *insn,find_good_pkt_pointers (other_branch, dst_reg, dst_reg->type, opcode ==BPF_JLT );mark_pkt_end (this_branch, dst_regno, opcode ==BPF_JLE );break ; +case BPF_JEQ : +case BPF_JNE : +/* pkt_data ==/!= pkt_end, pkt_meta ==/!= pkt_data */ + eq_branch = opcode ==BPF_JEQ ? other_branch : this_branch; +find_good_pkt_pointers (eq_branch, dst_reg, dst_reg->type, true); +mark_pkt_end (eq_branch, dst_regno, false); +break ;default :return false; } --2.43.0
Eduard Zingerman
maintainerRe: [PATCH bpf-next 2/3] bpf: infer packet range for 'if pkt ==/!= pkt_end' comparisons
Quoted 3 lines · Maciej Żenczykowski
(I've looked at all 3 patches, and they seem fine... but I don't claim to understand the intricacies of the verifier/registers/etc well enough to be certain)
Thank you.
Quoted 5 lines · Eduard Zingerman
Quoted 4 lines
Extend
try_match_pkt_pointers()to handle == and != operations. For instruction:
Quoted 7 lines
Quoted 4 lines
.--------------- pointer to packet with some range R | .--------- pointer to packet end v vif rA == rB goto ...
it's possible this would be better without the 'goto' as just 'if (rA == rB) ...'
The idea was to show this as BPF asm instruction, which has syntax 'if rA == rB goto C'. I'll wait for more feedback and submit v2 with updated commit message to make it more clear.
Quoted 9 lines
Quoted 5 lines
It is valid to infer that R bytes are available in packet. This change should allow verification of BPF generated for C code like below:
if (data + 42 !=
data_end) { ... }this should probably be:
if (data + 42 !=data_end) return;
...
Makes sense, will update commit message.
Re: [PATCH bpf-next 1/3] bpf: simplify try_match_pkt_pointers()
In reply to Eduard ZingermanQuoted 32 lines · Eduard Zingerman
Reduce number of cases handled in
try_match_pkt_pointers()to <pkt_data> <op> <pkt_end> or <pkt_meta> <op> <pkt_data> by flipping opcode.Suggested-by Andrii Nakryiko <[email protected]>Signed-off-by Eduard Zingerman <[email protected]>--- kernel/bpf/verifier.c | 104 ++++++++++-------------------------------- 1 file changed, 24 insertions(+), 80 deletions(-)kernel/bpf/verifier.c +5
-1@@ -14677,6 +14677,9 @@ static bool try_match_pkt_pointers(const struct bpf_insn *insn,struct bpf_verifier_state *this_branch, struct bpf_verifier_state *other_branch) { + int opcode = BPF_OP(insn->code); +int dst_regno = insn->dst_reg; +if (BPF_SRC (insn->code) !=BPF_X )return false;@@ -14684,90 +14687,31 @@ static bool try_match_pkt_pointers(const struct bpf_insn *insn,if (BPF_CLASS (insn->code) ==BPF_JMP32 )return false; -switch (BPF_OP (insn->code)) { +if (dst_reg->type ==PTR_TO_PACKET_END || + src_reg->type ==PTR_TO_PACKET_META ) {
kernel/bpf/verifier.c static bool try_match_pkt_pointers(const struct bpf_insn *insn, · line 14701
Quoted 10 lines
kernel/bpf/verifier.c +10
-0+swap (src_reg, dst_reg); + dst_regno = insn->src_reg; + opcode =flip_opcode (opcode); + } + +if ((dst_reg->type !=PTR_TO_PACKET || + src_reg->type !=PTR_TO_PACKET_END ) && + (dst_reg->type !=PTR_TO_PACKET_META || + !reg_is_init_pkt_pointer (src_reg,PTR_TO_PACKET ))) +return false;
this inverted original condition just breaks my brain, I can't wrap my head around it :) I think the original is easier to reason about because it's two clear allowable patterns for which we do something. I understand that this early exit reduces nestedness, but at least for me it would be simpler to have the original non-inverted condition with a nested switch.
Quoted 23 lines
kernel/bpf/verifier.c +2
-20+ +switch (opcode) {case BPF_JGT : -if ((dst_reg->type ==PTR_TO_PACKET && - src_reg->type ==PTR_TO_PACKET_END ) || - (dst_reg->type ==PTR_TO_PACKET_META && -reg_is_init_pkt_pointer (src_reg,PTR_TO_PACKET ))) { -/* pkt_data' > pkt_end, pkt_meta' > pkt_data */ -find_good_pkt_pointers (this_branch, dst_reg, - dst_reg->type, false); -mark_pkt_end (other_branch, insn->dst_reg, true); - }else if ((dst_reg->type ==PTR_TO_PACKET_END && - src_reg->type ==PTR_TO_PACKET ) || - (reg_is_init_pkt_pointer (dst_reg,PTR_TO_PACKET ) && - src_reg->type ==PTR_TO_PACKET_META )) { -/* pkt_end > pkt_data', pkt_data > pkt_meta' */ -find_good_pkt_pointers (other_branch, src_reg, - src_reg->type, true); -mark_pkt_end (this_branch, insn->src_reg, false); - }else { -return false; - } -break ;
[...]
Re: [PATCH bpf-next 1/3] bpf: simplify try_match_pkt_pointers()
Quoted 43 lines · Andrii Nakryiko
Quoted 41 lines · Eduard Zingerman
Reduce number of cases handled in
try_match_pkt_pointers()to <pkt_data> <op> <pkt_end> or <pkt_meta> <op> <pkt_data> by flipping opcode.Suggested-by Andrii Nakryiko <[email protected]>Signed-off-by Eduard Zingerman <[email protected]>--- kernel/bpf/verifier.c | 104 ++++++++++-------------------------------- 1 file changed, 24 insertions(+), 80 deletions(-)kernel/bpf/verifier.c +14
-1@@ -14677,6 +14677,9 @@ static bool try_match_pkt_pointers(const struct bpf_insn *insn,struct bpf_verifier_state *this_branch, struct bpf_verifier_state *other_branch) { + int opcode = BPF_OP(insn->code); +int dst_regno = insn->dst_reg; +if (BPF_SRC (insn->code) !=BPF_X )return false;@@ -14684,90 +14687,31 @@ static bool try_match_pkt_pointers(const struct bpf_insn *insn,if (BPF_CLASS (insn->code) ==BPF_JMP32 )return false; -switch (BPF_OP (insn->code)) { +if (dst_reg->type ==PTR_TO_PACKET_END || + src_reg->type ==PTR_TO_PACKET_META ) { +swap (src_reg, dst_reg); + dst_regno = insn->src_reg; + opcode =flip_opcode (opcode); + } + +if ((dst_reg->type !=PTR_TO_PACKET || + src_reg->type !=PTR_TO_PACKET_END ) && + (dst_reg->type !=PTR_TO_PACKET_META || + !reg_is_init_pkt_pointer (src_reg,PTR_TO_PACKET )))
Quoted 21 lines
kernel/bpf/verifier.c static bool try_match_pkt_pointers(const struct bpf_insn *insn, · line 14701
Quoted 1 line
kernel/bpf/verifier.c +1
-0+return false;this inverted original condition just breaks my brain, I can't wrap my head around it :) I think the original is easier to reason about because it's two clear allowable patterns for which we do something. I understand that this early exit reduces nestedness, but at least for me it would be simpler to have the original non-inverted condition with a nested switch.
Quoted 11 lines
kernel/bpf/verifier.c +2
-8+ +switch (opcode) {case BPF_JGT : -if ((dst_reg->type ==PTR_TO_PACKET && - src_reg->type ==PTR_TO_PACKET_END ) || - (dst_reg->type ==PTR_TO_PACKET_META && -reg_is_init_pkt_pointer (src_reg,PTR_TO_PACKET ))) { -/* pkt_data' > pkt_end, pkt_meta' > pkt_data */ -find_good_pkt_pointers (this_branch, dst_reg, - dst_reg->type, false); -mark_pkt_end (other_branch, insn->dst_reg, true);
it seems like you can make a bit of simplification if mark_pkt_end would just accept struct bpf_reg_state * instead of int regn (you won't need to keep track of dst_regno at all, right?)
Quoted 14 lines
Quoted 12 lines
kernel/bpf/verifier.c +0
-12- }else if ((dst_reg->type ==PTR_TO_PACKET_END && - src_reg->type ==PTR_TO_PACKET ) || - (reg_is_init_pkt_pointer (dst_reg,PTR_TO_PACKET ) && - src_reg->type ==PTR_TO_PACKET_META )) { -/* pkt_end > pkt_data', pkt_data > pkt_meta' */ -find_good_pkt_pointers (other_branch, src_reg, - src_reg->type, true); -mark_pkt_end (this_branch, insn->src_reg, false); - }else { -return false; - } -break ;[...]
Re: [PATCH bpf-next 2/3] bpf: infer packet range for 'if pkt ==/!= pkt_end' comparisons
In reply to Eduard ZingermanQuoted 35 lines · Eduard Zingerman
Extend
try_match_pkt_pointers()to handle == and != operations. For instruction:.--------------- pointer to packet with some range R | .--------- pointer to packet end v vif rA == rB goto ...
It is valid to infer that R bytes are available in packet. This change should allow verification of BPF generated for C code like below:
if (data + 42 !=
data_end) { ... }Suggested-by Maciej Żenczykowski <[email protected]>Link https://lore.kernel.org/bpf/CAHo-Oow5V2u4ZYvzuR8NmJmFDPNYp0pQDJX66rZqUjFHvhx82A@mail.gmail.com/ open hereSigned-off-by Eduard Zingerman <[email protected]>--- kernel/bpf/verifier.c | 8 ++++++++ 1 file changed, 8 insertions(+)kernel/bpf/verifier.c +1
-0@@ -14677,6 +14677,7 @@ static bool try_match_pkt_pointers(const struct bpf_insn *insn,struct bpf_verifier_state *this_branch, struct bpf_verifier_state *other_branch) { + struct bpf_verifier_state *eq_branch;int opcode =BPF_OP (insn->code);int dst_regno = insn->dst_reg;
kernel/bpf/verifier.c static bool try_match_pkt_pointers(const struct bpf_insn *insn, · line 14722
Quoted 9 lines
kernel/bpf/verifier.c +6
-0@@ -14713,6 +14714,13 @@ static bool try_match_pkt_pointers(const struct bpf_insn *insn,find_good_pkt_pointers (other_branch, dst_reg, dst_reg->type, opcode ==BPF_JLT );mark_pkt_end (this_branch, dst_regno, opcode ==BPF_JLE );break ; +case BPF_JEQ : +case BPF_JNE : +/* pkt_data ==/!= pkt_end, pkt_meta ==/!= pkt_data */ + eq_branch = opcode ==BPF_JEQ ? other_branch : this_branch; +find_good_pkt_pointers (eq_branch, dst_reg, dst_reg->type, true); +mark_pkt_end (eq_branch, dst_regno, false);
hm... if pkt_data != pkt_end in this_branch, can we really infer whether reg->range is BEYOND_PKT_END or AT_PKT_END? What if it's IN_FRONT_OF_PKT_END?
Quoted 7 lines
kernel/bpf/verifier.c +1
-1+break ;default :return false; } --2.43.0
Eduard Zingerman
maintainerRe: [PATCH bpf-next 1/3] bpf: simplify try_match_pkt_pointers()
In reply to Andrii NakryikoOn Mon, 2024-01-08 at 16:40 -0800, Andrii Nakryiko wrote:
[...]
Quoted 16 lines
Quoted 16 lines
kernel/bpf/verifier.c +11
-1@@ -14684,90 +14687,31 @@ static bool try_match_pkt_pointers(const struct bpf_insn *insn,if (BPF_CLASS (insn->code) ==BPF_JMP32 )return false; -switch (BPF_OP (insn->code)) { +if (dst_reg->type ==PTR_TO_PACKET_END || + src_reg->type ==PTR_TO_PACKET_META ) { +swap (src_reg, dst_reg); + dst_regno = insn->src_reg; + opcode =flip_opcode (opcode); + } + +if ((dst_reg->type !=PTR_TO_PACKET || + src_reg->type !=PTR_TO_PACKET_END ) && + (dst_reg->type !=PTR_TO_PACKET_META || + !reg_is_init_pkt_pointer (src_reg,PTR_TO_PACKET )))
Quoted 8 lines
kernel/bpf/verifier.c static bool try_match_pkt_pointers(const struct bpf_insn *insn, · line 14701
Quoted 1 line
kernel/bpf/verifier.c +1
-0+return false;this inverted original condition just breaks my brain, I can't wrap my head around it :) I think the original is easier to reason about because it's two clear allowable patterns for which we do something. I understand that this early exit reduces nestedness, but at least for me it would be simpler to have the original non-inverted condition with a nested switch.
I'm not sure I understand what you mean by nested switch. If I write it down like below, would that be more clear?
bool pkt_data_vs_pkt_end;
bool pkt_meta_vs_pkt_data;
...
pkt_data_vs_pkt_end =
dst_reg->type == PTR_TO_PACKET && src_reg->type == PTR_TO_PACKET_END;
pkt_meta_vs_pkt_data =
dst_reg->type == PTR_TO_PACKET_META && reg_is_init_pkt_pointer(src_reg, PTR_TO_PACKET);
if (!pkt_data_vs_pkt_end && !pkt_meta_vs_pkt_data)
return false;Quoted 12 lines
kernel/bpf/verifier.c static bool try_match_pkt_pointers(const struct bpf_insn *insn, · line 14696
Quoted 11 lines
kernel/bpf/verifier.c +2
-8+ +switch (opcode) {case BPF_JGT : -if ((dst_reg->type ==PTR_TO_PACKET && - src_reg->type ==PTR_TO_PACKET_END ) || - (dst_reg->type ==PTR_TO_PACKET_META && -reg_is_init_pkt_pointer (src_reg,PTR_TO_PACKET ))) { -/* pkt_data' > pkt_end, pkt_meta' > pkt_data */ -find_good_pkt_pointers (this_branch, dst_reg, - dst_reg->type, false); -mark_pkt_end (other_branch, insn->dst_reg, true);
Quoted 3 lines
it seems like you can make a bit of simplification if
mark_pkt_endwould just accept structbpf_reg_state* instead of int regn (you won't need to keep track ofdst_regnoat all, right?)
mark_pkt_end() changes the register from either this_branch or other_branch. I can introduce local pointers dst_this/dst_other and swap those, but I'm not sure it's worth it.
[...]
Eduard Zingerman
maintainerRe: [PATCH bpf-next 2/3] bpf: infer packet range for 'if pkt ==/!= pkt_end' comparisons
In reply to Andrii NakryikoOn Mon, 2024-01-08 at 16:45 -0800, Andrii Nakryiko wrote:
[...]
Quoted 6 lines
Quoted 6 lines
kernel/bpf/verifier.c +2
-0@@ -14713,6 +14714,13 @@ static bool try_match_pkt_pointers(const struct bpf_insn *insn,find_good_pkt_pointers (other_branch, dst_reg, dst_reg->type, opcode ==BPF_JLT );mark_pkt_end (this_branch, dst_regno, opcode ==BPF_JLE );break ; +case BPF_JEQ : +case BPF_JNE :
Quoted 8 lines
kernel/bpf/verifier.c static bool try_match_pkt_pointers(const struct bpf_insn *insn, · line 14722
Quoted 4 lines
kernel/bpf/verifier.c +4
-0+/* pkt_data ==/!= pkt_end, pkt_meta ==/!= pkt_data */ + eq_branch = opcode ==BPF_JEQ ? other_branch : this_branch; +find_good_pkt_pointers (eq_branch, dst_reg, dst_reg->type, true); +mark_pkt_end (eq_branch, dst_regno, false);hm... if
pkt_data!=pkt_endinthis_branch, can we really infer whetherreg->rangeisBEYOND_PKT_ENDorAT_PKT_END? What if it'sIN_FRONT_OF_PKT_END?
pkt_data != pkt_end in this_branch means that there is an instruction:
...
if pkt_data == pkt_end goto <other_branch>
... <this_branch> ...
the 'eq_branch' would be set to 'other_branch' and AT_PKT_END would be set for dst register in 'other_branch'. What's wrong with this?
Or did you mean something else?
Yonghong Song
reviewerRe: [PATCH bpf-next 2/3] bpf: infer packet range for 'if pkt ==/!= pkt_end' comparisons
In reply to Eduard ZingermanQuoted 34 lines · Eduard Zingerman
Extend
try_match_pkt_pointers()to handle == and != operations. For instruction:.--------------- pointer to packet with some range R | .--------- pointer to packet end v vif rA == rB goto ...
It is valid to infer that R bytes are available in packet. This change should allow verification of BPF generated for C code like below:
if (data + 42 != data_end) { ... }Suggested-by Maciej Żenczykowski <[email protected]>Link https://lore.kernel.org/bpf/CAHo-Oow5V2u4ZYvzuR8NmJmFDPNYp0pQDJX66rZqUjFHvhx82A@mail.gmail.com/ open hereSigned-off-by Eduard Zingerman <[email protected]>--- kernel/bpf/verifier.c | 8 ++++++++ 1 file changed, 8 insertions(+)kernel/bpf/verifier.c +1
-0@@ -14677,6 +14677,7 @@ static bool try_match_pkt_pointers(const struct bpf_insn *insn,struct bpf_verifier_state *this_branch, struct bpf_verifier_state *other_branch) { + struct bpf_verifier_state *eq_branch;int opcode =BPF_OP (insn->code);int dst_regno = insn->dst_reg;
kernel/bpf/verifier.c static bool try_match_pkt_pointers(const struct bpf_insn *insn, · line 14723
Quoted 10 lines
kernel/bpf/verifier.c +7
-0@@ -14713,6 +14714,13 @@ static bool try_match_pkt_pointers(const struct bpf_insn *insn,find_good_pkt_pointers (other_branch, dst_reg, dst_reg->type, opcode ==BPF_JLT );mark_pkt_end (this_branch, dst_regno, opcode ==BPF_JLE );break ; +case BPF_JEQ : +case BPF_JNE : +/* pkt_data ==/!= pkt_end, pkt_meta ==/!= pkt_data */ + eq_branch = opcode ==BPF_JEQ ? other_branch : this_branch; +find_good_pkt_pointers (eq_branch, dst_reg, dst_reg->type, true); +mark_pkt_end (eq_branch, dst_regno, false); +break ;
What will happen if there are multiple BPF_JEQ/BPF_JNE? I made a change to one of tests in patch 3:
+SEC("tc")
+__success __log_level(2)
+__msg("if r3 != r2 goto pc+3 ; R2_w=pkt_end() R3_w=pkt(off=8,r=0xffffffffffffffff)")
+__naked void data_plus_const_neq_pkt_end(void)
+{
+ asm volatile (" \
+ r9 = r1; \
+ r1 = *(u32*)(r9 + %[__sk_buff_data]); \
+ r2 = *(u32*)(r9 + %[__sk_buff_data_end]); \
+ r3 = r1; \
+ r3 += 8; \
+ if r3 != r2 goto 1f; \
+ r3 += 8; \
+ if r3 != r2 goto 1f; \
+ r1 = *(u64 *)(r1 + 0); \
+1: \
+ r0 = 0; \
+ exit; \+" :
+ : __imm_const(__sk_buff_data, offsetof(struct __sk_buff, data)),
+ __imm_const(__sk_buff_data_end, offsetof(struct __sk_buff, data_end))
+ : __clobber_all);
+}
The verifier output:
func#0 @0
Global function data_plus_const_neq_pkt_end() doesn't return scalar. Only those are supported. 0: R1=ctx() R10=fp0
; asm volatile (" \
0: (bf) r9 = r1 ; R1=ctx() R9_w=ctx() 1: (61) r1 = *(u32 *)(r9 +76) ; R1_w=pkt(r=0) R9_w=ctx() 2: (61) r2 = *(u32 *)(r9 +80) ; R2_w=pkt_end() R9_w=ctx() 3: (bf) r3 = r1 ; R1_w=pkt(r=0) R3_w=pkt(r=0) 4: (07) r3 += 8 ; R3_w=pkt(off=8,r=0) 5: (5d) if r3 != r2 goto pc+3 ; R2_w=pkt_end() R3_w=pkt(off=8,r=0xffffffffffffffff) 6: (07) r3 += 8 ; R3_w=pkt(off=16,r=0xffffffffffffffff) 7: (5d) if r3 != r2 goto pc+1 ; R2_w=pkt_end() R3_w=pkt(off=16,r=0xffffffffffffffff) 8: (79) r1 = *(u64 *)(r1 +0) ; R1=scalar() 9: (b7) r0 = 0 ; R0_w=0
10: (95) exit
from 7 to 9: safe
from 5 to 9: safe
processed 13 insns (limit 1000000) max_states_per_insn 0 total_states 1 peak_states 1 mark_read 0
insn 5, for this_branch (straight one), r3 range will be 8 and assuming pkt_end is 8. insn 7, r3 range becomes 18 and then we assume pkt_end is 16.
I guess we should handle this case. For branch 5 and 7, it cannot be that both will be true.
Quoted 3 lines
kernel/bpf/verifier.c +0
-0default :return false; }
Re: [PATCH bpf-next 1/3] bpf: simplify try_match_pkt_pointers()
In reply to Eduard ZingermanQuoted 28 lines · Eduard Zingerman
On Mon, 2024-01-08 at 16:40 -0800, Andrii Nakryiko wrote:
[...]Quoted 16 lines
Quoted 16 lines
kernel/bpf/verifier.c +11
-1@@ -14684,90 +14687,31 @@ static bool try_match_pkt_pointers(const struct bpf_insn *insn,if (BPF_CLASS (insn->code) ==BPF_JMP32 )return false; -switch (BPF_OP (insn->code)) { +if (dst_reg->type ==PTR_TO_PACKET_END || + src_reg->type ==PTR_TO_PACKET_META ) { +swap (src_reg, dst_reg); + dst_regno = insn->src_reg; + opcode =flip_opcode (opcode); + } + +if ((dst_reg->type !=PTR_TO_PACKET || + src_reg->type !=PTR_TO_PACKET_END ) && + (dst_reg->type !=PTR_TO_PACKET_META || + !reg_is_init_pkt_pointer (src_reg,PTR_TO_PACKET )))Quoted 8 lines
kernel/bpf/verifier.c static bool try_match_pkt_pointers(const struct bpf_insn *insn, · line 14701
Quoted 1 line
kernel/bpf/verifier.c +1
-0+return false;this inverted original condition just breaks my brain, I can't wrap my head around it :) I think the original is easier to reason about because it's two clear allowable patterns for which we do something. I understand that this early exit reduces nestedness, but at least for me it would be simpler to have the original non-inverted condition with a nested switch.
Quoted 3 lines
I'm not sure I understand what you mean by nested switch. If I write it down like below, would that be more clear?
Yes, much more clear. What I had in mind was something like:
if (pkt_data_vs_pkt_end || pkt_meta_vs_pkt_data) {
switch (opcode) {
...
}
}But what you have below is easy to follow as well
Quoted 23 lines
bool pkt_data_vs_pkt_end; bool pkt_meta_vs_pkt_data; ... pkt_data_vs_pkt_end = dst_reg->type == PTR_TO_PACKET && src_reg->type == PTR_TO_PACKET_END; pkt_meta_vs_pkt_data = dst_reg->type == PTR_TO_PACKET_META && reg_is_init_pkt_pointer(src_reg, PTR_TO_PACKET); if (!pkt_data_vs_pkt_end && !pkt_meta_vs_pkt_data) return false;Quoted 11 lines
Quoted 11 lines
kernel/bpf/verifier.c +2
-8+ +switch (opcode) {case BPF_JGT : -if ((dst_reg->type ==PTR_TO_PACKET && - src_reg->type ==PTR_TO_PACKET_END ) || - (dst_reg->type ==PTR_TO_PACKET_META && -reg_is_init_pkt_pointer (src_reg,PTR_TO_PACKET ))) { -/* pkt_data' > pkt_end, pkt_meta' > pkt_data */ -find_good_pkt_pointers (this_branch, dst_reg, - dst_reg->type, false); -mark_pkt_end (other_branch, insn->dst_reg, true);
Quoted 7 lines
Quoted 3 lines
it seems like you can make a bit of simplification if
mark_pkt_endwould just accept structbpf_reg_state* instead of int regn (you won't need to keep track ofdst_regnoat all, right?)
mark_pkt_end()changes the register from eitherthis_branchorother_branch. I can introduce local pointers dst_this/dst_other and swap those, but I'm not sure it's worth it.
Ah, I missed that it's other_branch register. Never mind then, it's fine and it was minor anyways.
Quoted 2 lines
[...]
Re: [PATCH bpf-next 2/3] bpf: infer packet range for 'if pkt ==/!= pkt_end' comparisons
In reply to Eduard ZingermanQuoted 20 lines · Eduard Zingerman
On Mon, 2024-01-08 at 16:45 -0800, Andrii Nakryiko wrote:
[...]Quoted 6 lines
Quoted 6 lines
kernel/bpf/verifier.c +2
-0@@ -14713,6 +14714,13 @@ static bool try_match_pkt_pointers(const struct bpf_insn *insn,find_good_pkt_pointers (other_branch, dst_reg, dst_reg->type, opcode ==BPF_JLT );mark_pkt_end (this_branch, dst_regno, opcode ==BPF_JLE );break ; +case BPF_JEQ : +case BPF_JNE :Quoted 8 lines
kernel/bpf/verifier.c static bool try_match_pkt_pointers(const struct bpf_insn *insn, · line 14722
Quoted 4 lines
kernel/bpf/verifier.c +4
-0+/* pkt_data ==/!= pkt_end, pkt_meta ==/!= pkt_data */ + eq_branch = opcode ==BPF_JEQ ? other_branch : this_branch; +find_good_pkt_pointers (eq_branch, dst_reg, dst_reg->type, true); +mark_pkt_end (eq_branch, dst_regno, false);hm... if
pkt_data!=pkt_endinthis_branch, can we really infer whetherreg->rangeisBEYOND_PKT_ENDorAT_PKT_END? What if it'sIN_FRONT_OF_PKT_END?
pkt_data!=pkt_endinthis_branchmeans that there is an instruction:
Quoted 7 lines
...
ifpkt_data==pkt_endgoto <other_branch>
... <this_branch> ...the '
eq_branch' would be set to 'other_branch' andAT_PKT_ENDwould be set for dst register in 'other_branch'. What's wrong with this?
Or did you mean something else?
Well, first off, I'm very unfamiliar with all these pkt_xxx registers, so excuse me for stupid questions. I guess what got me confused was that find_good_pkt_pointer() and mark_pkt_end() previously (for GT/GE/LT/LE) were working on opposing branches. But here I see they work on the same "equal" branch. But now I'm wondering what's the point of even calling find_good_pkt_pointer()? Is there a scenario where it can derive new information from JEQ/JNE?
Eduard Zingerman
maintainerRe: [PATCH bpf-next 2/3] bpf: infer packet range for 'if pkt ==/!= pkt_end' comparisons
In reply to Yonghong SongOn Tue, 2024-01-09 at 09:26 -0800, Yonghong Song wrote:
[...]
Quoted 48 lines
What will happen if there are multiple BPF_JEQ/BPF_JNE? I made a change to one of tests in patch 3:
(quoted diff) +23
-0+SEC("tc") +__success __log_level(2) +__msg("if r3 != r2 goto pc+3 ; R2_w=pkt_end() R3_w=pkt(off=8,r=0xffffffffffffffff)") +__naked void data_plus_const_neq_pkt_end(void) +{ + asm volatile (" \ + r9 = r1; \ + r1 = *(u32*)(r9 + %[__sk_buff_data]); \ + r2 = *(u32*)(r9 + %[__sk_buff_data_end]); \ + r3 = r1; \ + r3 += 8; \ + if r3 != r2 goto 1f; \ + r3 += 8; \ + if r3 != r2 goto 1f; \ + r1 = *(u64 *)(r1 + 0); \ +1: \ + r0 = 0; \ + exit; \ +" : + : __imm_const(__sk_buff_data, offsetof(struct __sk_buff, data)), + __imm_const(__sk_buff_data_end, offsetof(struct __sk_buff, data_end)) + : __clobber_all); +}The verifier output:
func#0 @0
Global functiondata_plus_const_neq_pkt_end()doesn't return scalar. Only those are supported. 0: R1=ctx() R10=fp0
; asm volatile (" \0: (bf) r9 = r1 ; R1=ctx() R9_w=ctx() 1: (61) r1 = *(u32 *)(r9 +76) ; R1_w=pkt(r=0) R9_w=ctx() 2: (61) r2 = *(u32 *)(r9 +80) ; R2_w=pkt_end() R9_w=ctx() 3: (bf) r3 = r1 ; R1_w=pkt(r=0) R3_w=pkt(r=0) 4: (07) r3 += 8 ; R3_w=pkt(off=8,r=0) 5: (5d) if r3 != r2 goto pc+3 ; R2_w=pkt_end() R3_w=pkt(off=8,r=0xffffffffffffffff) 6: (07) r3 += 8 ; R3_w=pkt(off=16,r=0xffffffffffffffff) 7: (5d) if r3 != r2 goto pc+1 ; R2_w=pkt_end() R3_w=pkt(off=16,r=0xffffffffffffffff) 8: (79) r1 = *(u64 *)(r1 +0) ; R1=scalar() 9: (b7) r0 = 0 ; R0_w=010: (95) exit
from 7 to 9: safe
Quoted 7 lines
from 5 to 9: safe
processed 13 insns (limit 1000000)max_states_per_insn0total_states1peak_states1mark_read0insn 5, for
this_branch(straight one), r3 range will be 8 and assumingpkt_endis 8. insn 7, r3 range becomes 18 and then we assumepkt_endis 16.I guess we should handle this case. For branch 5 and 7, it cannot be that both will be true.
This is an interesting case.reg->range is set to AT_PKT_END or BEYOND_PKT_END only in try_match_pkt_pointers() (in mark_pkt_end() call). And this range mark appears not to be reset by += operation (which might add a negative number as well).
So, once r3 is marked AT_PKT_END it would remain so even after r3 += 8, which is obviously not true. Not sure what to do yet.
Eduard Zingerman
maintainerRe: [PATCH bpf-next 2/3] bpf: infer packet range for 'if pkt ==/!= pkt_end' comparisons
Quoted 56 lines · Eduard Zingerman
On Tue, 2024-01-09 at 09:26 -0800, Yonghong Song wrote:
[...]Quoted 54 lines
What will happen if there are multiple BPF_JEQ/BPF_JNE? I made a change to one of tests in patch 3:
(quoted diff) +23
-0+SEC("tc") +__success __log_level(2) +__msg("if r3 != r2 goto pc+3 ; R2_w=pkt_end() R3_w=pkt(off=8,r=0xffffffffffffffff)") +__naked void data_plus_const_neq_pkt_end(void) +{ + asm volatile (" \ + r9 = r1; \ + r1 = *(u32*)(r9 + %[__sk_buff_data]); \ + r2 = *(u32*)(r9 + %[__sk_buff_data_end]); \ + r3 = r1; \ + r3 += 8; \ + if r3 != r2 goto 1f; \ + r3 += 8; \ + if r3 != r2 goto 1f; \ + r1 = *(u64 *)(r1 + 0); \ +1: \ + r0 = 0; \ + exit; \ +" : + : __imm_const(__sk_buff_data, offsetof(struct __sk_buff, data)), + __imm_const(__sk_buff_data_end, offsetof(struct __sk_buff, data_end)) + : __clobber_all); +}The verifier output:
func#0 @0
Global functiondata_plus_const_neq_pkt_end()doesn't return scalar. Only those are supported. 0: R1=ctx() R10=fp0
; asm volatile (" \0: (bf) r9 = r1 ; R1=ctx() R9_w=ctx() 1: (61) r1 = *(u32 *)(r9 +76) ; R1_w=pkt(r=0) R9_w=ctx() 2: (61) r2 = *(u32 *)(r9 +80) ; R2_w=pkt_end() R9_w=ctx() 3: (bf) r3 = r1 ; R1_w=pkt(r=0) R3_w=pkt(r=0) 4: (07) r3 += 8 ; R3_w=pkt(off=8,r=0) 5: (5d) if r3 != r2 goto pc+3 ; R2_w=pkt_end() R3_w=pkt(off=8,r=0xffffffffffffffff) 6: (07) r3 += 8 ; R3_w=pkt(off=16,r=0xffffffffffffffff) 7: (5d) if r3 != r2 goto pc+1 ; R2_w=pkt_end() R3_w=pkt(off=16,r=0xffffffffffffffff) 8: (79) r1 = *(u64 *)(r1 +0) ; R1=scalar() 9: (b7) r0 = 0 ; R0_w=010: (95) exit
from 7 to 9: safe
from 5 to 9: safe
processed 13 insns (limit 1000000)max_states_per_insn0total_states1peak_states1mark_read0insn 5, for
this_branch(straight one), r3 range will be 8 and assumingpkt_endis 8. insn 7, r3 range becomes 18 and then we assumepkt_endis 16.
Quoted 10 lines
Quoted 1 line
I guess we should handle this case. For branch 5 and 7, it cannot be that both will be true.
This is an interesting case.
reg->rangeis set toAT_PKT_ENDorBEYOND_PKT_ENDonly intry_match_pkt_pointers()(inmark_pkt_end()call). And this range mark appears not to be reset by += operation (which might add a negative number as well).
So, once r3 is markedAT_PKT_ENDit would remain so even after r3 += 8, which is obviously not true. Not sure what to do yet.
Here is another example which is currently not handled correctly, even w/o my patch:
SEC("tc")__success__naked void pkt_vs_pkt_end_with_bound_change(void)
{
asm volatile (" \
r9 = r1; \
r0 = 0; \
r1 = *(u32*)(r9 + %[__sk_buff_data]); \
r2 = *(u32*)(r9 + %[__sk_buff_data_end]); \
r3 = r1; \
r3 += 8; \
if r3 <= r2 goto 1f; \
r3 -= 8; \
if r3 >= r2 goto 1f; \
r4 = *(u64 *)(r1 + 0); \
1: exit; \
" :
: __imm_const(__sk_buff_data, offsetof(struct __sk_buff, data)),
__imm_const(__sk_buff_data_end, offsetof(struct __sk_buff, data_end))
: __clobber_all);
}Verifier log:
0: R1=ctx() R10=fp0
; asm volatile (" \
0: (bf) r9 = r1 ; R1=ctx() R9_w=ctx()
1: (b7) r0 = 0 ; R0_w=0
2: (61) r1 = *(u32 *)(r9 +76) ; R1_w=pkt(r=0) R9_w=ctx()
3: (61) r2 = *(u32 *)(r9 +80) ; R2_w=pkt_end() R9_w=ctx()
4: (bf) r3 = r1 ; R1_w=pkt(r=0) R3_w=pkt(r=0)
5: (07) r3 += 8 ; R3_w=pkt(off=8,r=0)
6: (bd) if r3 <= r2 goto pc+3 ; R2_w=pkt_end() R3_w=pkt(off=8,r=0xfffffffffffffffe)
7: (17) r3 -= 8 ; R3_w=pkt(r=0xfffffffffffffffe)
8: (3d) if r3 >= r2 goto pc+1 ; R2_w=pkt_end() R3_w=pkt(r=0xfffffffffffffffe)
10: (95) exit from 6 to 10: safe
processed 11 insns (limit 1000000) max_states_per_insn 0 total_states 1 peak_states 1 mark_read 1
At (6) for this_branch r3 is marked BEYOND_PKT_END,
packet range is known to be 8;
at (7) it is changed to point back to start of the packet;
at (8) is_pkt_ptr_branch_taken() incorrectly predicts that
r3 >= r2 (r3 - packet start, r2 - packet end).