* [PATCH net] bpf: fix liveness marking
@ 2017-10-05 23:20 Alexei Starovoitov
2017-10-06 16:33 ` Edward Cree
` (2 more replies)
0 siblings, 3 replies; 5+ messages in thread
From: Alexei Starovoitov @ 2017-10-05 23:20 UTC (permalink / raw)
To: David S . Miller; +Cc: Daniel Borkmann, Edward Cree, netdev, kernel-team
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
Fixes: dc503a8ad984 ("bpf/verifier: track liveness for pruning")
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
kernel/bpf/verifier.c | 5 +++++
1 file changed, 5 insertions(+)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index b914fbe1383e..8b8d6ba39e23 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -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 & REG_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)) {
--
2.9.5
^ permalink raw reply related [flat|nested] 5+ messages in thread
* Re: [PATCH net] bpf: fix liveness marking
2017-10-05 23:20 [PATCH net] bpf: fix liveness marking Alexei Starovoitov
@ 2017-10-06 16:33 ` Edward Cree
2017-10-06 16:43 ` Alexei Starovoitov
2017-10-06 18:20 ` Daniel Borkmann
2017-10-07 22:29 ` David Miller
2 siblings, 1 reply; 5+ messages in thread
From: Edward Cree @ 2017-10-06 16:33 UTC (permalink / raw)
To: Alexei Starovoitov, David S . Miller; +Cc: Daniel Borkmann, netdev, kernel-team
On 06/10/17 00:20, Alexei Starovoitov wrote:
> 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.
Good catch!
> 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().
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.
> 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
>
> Fixes: dc503a8ad984 ("bpf/verifier: track liveness for pruning")
> Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Very nice numbers!
Acked-by: Edward Cree <ecree@solarflare.com>
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH net] bpf: fix liveness marking
2017-10-06 16:33 ` Edward Cree
@ 2017-10-06 16:43 ` Alexei Starovoitov
0 siblings, 0 replies; 5+ messages in thread
From: Alexei Starovoitov @ 2017-10-06 16:43 UTC (permalink / raw)
To: Edward Cree, David S . Miller; +Cc: Daniel Borkmann, netdev, kernel-team
On 10/6/17 9:33 AM, Edward Cree wrote:
> On 06/10/17 00:20, Alexei Starovoitov wrote:
>> 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.
> Good catch!
>> 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().
> 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.
yeah. before this patch it was doing extra
memcmp(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(..))
>> 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
>>
>> Fixes: dc503a8ad984 ("bpf/verifier: track liveness for pruning")
>> Signed-off-by: Alexei Starovoitov <ast@kernel.org>
> Very nice numbers!
> Acked-by: Edward Cree <ecree@solarflare.com>
Thanks!
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH net] bpf: fix liveness marking
2017-10-05 23:20 [PATCH net] bpf: fix liveness marking Alexei Starovoitov
2017-10-06 16:33 ` Edward Cree
@ 2017-10-06 18:20 ` Daniel Borkmann
2017-10-07 22:29 ` David Miller
2 siblings, 0 replies; 5+ messages in thread
From: Daniel Borkmann @ 2017-10-06 18:20 UTC (permalink / raw)
To: Alexei Starovoitov, David S . Miller; +Cc: Edward Cree, netdev, kernel-team
On 10/06/2017 01:20 AM, Alexei Starovoitov wrote:
> 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
>
> Fixes: dc503a8ad984 ("bpf/verifier: track liveness for pruning")
> Signed-off-by: Alexei Starovoitov <ast@kernel.org>
LGTM, thanks!
Acked-by: Daniel Borkmann <daniel@iogearbox.net>
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH net] bpf: fix liveness marking
2017-10-05 23:20 [PATCH net] bpf: fix liveness marking Alexei Starovoitov
2017-10-06 16:33 ` Edward Cree
2017-10-06 18:20 ` Daniel Borkmann
@ 2017-10-07 22:29 ` David Miller
2 siblings, 0 replies; 5+ messages in thread
From: David Miller @ 2017-10-07 22:29 UTC (permalink / raw)
To: ast; +Cc: daniel, ecree, netdev, kernel-team
From: Alexei Starovoitov <ast@fb.com>
Date: Thu, 5 Oct 2017 16:20:56 -0700
> 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
>
> Fixes: dc503a8ad984 ("bpf/verifier: track liveness for pruning")
> Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Looks great, applied.
^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2017-10-07 22:29 UTC | newest]
Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2017-10-05 23:20 [PATCH net] bpf: fix liveness marking Alexei Starovoitov
2017-10-06 16:33 ` Edward Cree
2017-10-06 16:43 ` Alexei Starovoitov
2017-10-06 18:20 ` Daniel Borkmann
2017-10-07 22:29 ` David Miller
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.