bpf: fix liveness marking
Subsystems (4)
PATCH 1/1 bpf: fix liveness marking
while processing Rx = Ry instruction the verifier does regs[insn->dst_reg] = regs[insn->src_reg]
which often clears write mark (when Ry doesn't have it)
that was just set by check_reg_arg(Rx) prior to the assignment. That causes mark_reg_read() to keep marking Rx in this block as REG_LIVE_READ (since the logic incorrectly misses that it's screened by the write) and in many of its parents (until lucky write into the same Rx or beginning of the program).
That causes is_state_visited() logic to miss many pruning opportunities.
Furthermore mark_reg_read() logic propagates the read mark for BPF_REG_FP as well (though it's readonly) which causes harmless but unnecssary work during is_state_visited(). Note that do_propagate_liveness() skips FP correctly, so do the same in mark_reg_read() as well.
It saves 0.2 seconds for the test below
program before after bpf_lb-DLB_L3.o 2604 2304 bpf_lb-DLB_L4.o 11159 3723 bpf_lb-DUNKNOWN.o 1116 1110 bpf_lxc-DDROP_ALL.o 34566 28004 bpf_lxc-DUNKNOWN.o 53267 39026 bpf_netdev.o 17843 16943 bpf_overlay.o 8672 7929 time ~11 sec ~4 sec
--- kernel/bpf/verifier.c | 5 +++++ 1 file changed, 5 insertions(+)
kernel/bpf/verifier.c +5 -0
@@ -653,6 +653,10 @@ static void mark_reg_read(const struct bpf_verifier_state *state, u32 regno) {struct bpf_verifier_state *parent = state->parent; +if (regno ==BPF_REG_FP ) +/* We don't need to worry about FP liveness because it's read-only */ +return ; +while (parent) {/* if read wasn't screened by an earlier write ... */ if (state->regs[regno].live ®_LIVE_WRITTEN )
@@ -2345,6 +2349,7 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)* copy register state to dest reg */ regs[insn->dst_reg] = regs[insn->src_reg]; + regs[insn->dst_reg].live |=REG_LIVE_WRITTEN ; }else {/* R1 = (u32) R2 */ if (is_pointer_value (env, insn->src_reg)) {
Signature · 1 line
2.9.5
Quoted 9 lines · Alexei Starovoitov
while processing Rx = Ry instruction the verifier does regs[insn->dst_reg] = regs[insn->src_reg]
which often clears write mark (when Ry doesn't have it)
that was just set bycheck_reg_arg(Rx)prior to the assignment. That causesmark_reg_read()to keep marking Rx in this block asREG_LIVE_READ(since the logic incorrectly misses that it's screened by the write) and in many of its parents (until lucky write into the same Rx or beginning of the program).
That causesis_state_visited()logic to miss many pruning opportunities.
Good catch!
Quoted 3 lines
Furthermore
mark_reg_read()logic propagates the read mark forBPF_REG_FPas well (though it's readonly) which causes harmless but unnecssary work duringis_state_visited().
Surely it's unnecessary for is_state_visited() to even look at
BPF_REG_FP anyway, so in addition to your change we could make states_equal just do for (i = 0; i < BPF_REG_FP; i++)? That might save a bit more time.
Quoted 14 lines
Note that
do_propagate_liveness()skips FP correctly, so do the same inmark_reg_read()as well.
It saves 0.2 seconds for the test belowprogram before after bpf_lb-DLB_L3.o 2604 2304 bpf_lb-DLB_L4.o 11159 3723 bpf_lb-DUNKNOWN.o 1116 1110 bpf_lxc-DDROP_ALL.o 34566 28004 bpf_lxc-DUNKNOWN.o 53267 39026 bpf_netdev.o 17843 16943 bpf_overlay.o 8672 7929 time ~11 sec ~4 sec
Quoted 2 lines
Fixes dc503a8ad984 ("bpf/verifier: track liveness for pruning")Signed-off-by Alexei Starovoitov <[email protected]>
Very nice numbers!
Quoted 10 lines · Edward Cree
Quoted 9 lines · Alexei Starovoitov
while processing Rx = Ry instruction the verifier does regs[insn->dst_reg] = regs[insn->src_reg]
which often clears write mark (when Ry doesn't have it)
that was just set bycheck_reg_arg(Rx)prior to the assignment. That causesmark_reg_read()to keep marking Rx in this block asREG_LIVE_READ(since the logic incorrectly misses that it's screened by the write) and in many of its parents (until lucky write into the same Rx or beginning of the program).
That causesis_state_visited()logic to miss many pruning opportunities.
Quoted 8 lines
Good catch!
Quoted 3 lines
Furthermore
mark_reg_read()logic propagates the read mark forBPF_REG_FPas well (though it's readonly) which causes harmless but unnecssary work duringis_state_visited().Surely it's unnecessary for
is_state_visited()to even look at
BPF_REG_FPanyway, so in addition to your change we could makestates_equaljust dofor (i = 0; i < BPF_REG_FP; i++)? That might save a bit more time.
yeah. before this patch it was doing extramemcmp(rold, rcur, ..) on FP reg. This patch saves this memcpy. The i < BPF_REG_FP would effectively do the same, but I'm not sure I want to do it just yet.
For net-next I have a bunch of changes for verifier to support bpf_call and there two different states may have two different FPs. One FP from caller and one from callee.
So I might still need to do full
for (i = 0; i < MAX_BPF_REG; i++)
if (!regsafe(..))
Quoted 14 lines
Quoted 14 lines
Note that
do_propagate_liveness()skips FP correctly, so do the same inmark_reg_read()as well.
It saves 0.2 seconds for the test belowprogram before after bpf_lb-DLB_L3.o 2604 2304 bpf_lb-DLB_L4.o 11159 3723 bpf_lb-DUNKNOWN.o 1116 1110 bpf_lxc-DDROP_ALL.o 34566 28004 bpf_lxc-DUNKNOWN.o 53267 39026 bpf_netdev.o 17843 16943 bpf_overlay.o 8672 7929 time ~11 sec ~4 sec
Quoted 4 lines
Quoted 2 lines
Fixes dc503a8ad984 ("bpf/verifier: track liveness for pruning")Signed-off-by Alexei Starovoitov <[email protected]>Very nice numbers!
Acked-by Edward Cree <[email protected]>
Thanks!
Quoted 27 lines · Alexei Starovoitov
while processing Rx = Ry instruction the verifier does regs[insn->dst_reg] = regs[insn->src_reg]
which often clears write mark (when Ry doesn't have it)
that was just set bycheck_reg_arg(Rx)prior to the assignment. That causesmark_reg_read()to keep marking Rx in this block asREG_LIVE_READ(since the logic incorrectly misses that it's screened by the write) and in many of its parents (until lucky write into the same Rx or beginning of the program).
That causesis_state_visited()logic to miss many pruning opportunities.Furthermore
mark_reg_read()logic propagates the read mark forBPF_REG_FPas well (though it's readonly) which causes harmless but unnecssary work duringis_state_visited(). Note thatdo_propagate_liveness()skips FP correctly, so do the same inmark_reg_read()as well.
It saves 0.2 seconds for the test belowprogram before after bpf_lb-DLB_L3.o 2604 2304 bpf_lb-DLB_L4.o 11159 3723 bpf_lb-DUNKNOWN.o 1116 1110 bpf_lxc-DDROP_ALL.o 34566 28004 bpf_lxc-DUNKNOWN.o 53267 39026 bpf_netdev.o 17843 16943 bpf_overlay.o 8672 7929 time ~11 sec ~4 sec
Quoted 2 lines
Fixes dc503a8ad984 ("bpf/verifier: track liveness for pruning")Signed-off-by Alexei Starovoitov <[email protected]>
LGTM, thanks!
David Miller
maintainerFrom: Alexei Starovoitov <[email protected]>
Date: Thu, 5 Oct 2017 16:20:56 -0700
Quoted 27 lines
while processing Rx = Ry instruction the verifier does regs[insn->dst_reg] = regs[insn->src_reg]
which often clears write mark (when Ry doesn't have it)
that was just set bycheck_reg_arg(Rx)prior to the assignment. That causesmark_reg_read()to keep marking Rx in this block asREG_LIVE_READ(since the logic incorrectly misses that it's screened by the write) and in many of its parents (until lucky write into the same Rx or beginning of the program).
That causesis_state_visited()logic to miss many pruning opportunities.Furthermore
mark_reg_read()logic propagates the read mark forBPF_REG_FPas well (though it's readonly) which causes harmless but unnecssary work duringis_state_visited(). Note thatdo_propagate_liveness()skips FP correctly, so do the same inmark_reg_read()as well.
It saves 0.2 seconds for the test belowprogram before after bpf_lb-DLB_L3.o 2604 2304 bpf_lb-DLB_L4.o 11159 3723 bpf_lb-DUNKNOWN.o 1116 1110 bpf_lxc-DDROP_ALL.o 34566 28004 bpf_lxc-DUNKNOWN.o 53267 39026 bpf_netdev.o 17843 16943 bpf_overlay.o 8672 7929 time ~11 sec ~4 sec
Quoted 2 lines
Fixes dc503a8ad984 ("bpf/verifier: track liveness for pruning")Signed-off-by Alexei Starovoitov <[email protected]>
Looks great, applied.