Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1681140 > unrolled thread

Re: [PATCH v3 net-next 00/12] bpf: rewrite value tracking in verifier

Back to article view | Back to linux.kernel

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: [PATCH v3 net-next 00/12] bpf: rewrite value tracking in verifier Edward Cree <ecree@solarflare.com> - 2017-07-04 21:30 +0200
    Re: [PATCH v3 net-next 00/12] bpf: rewrite value tracking in verifier Daniel Borkmann <daniel@iogearbox.net> - 2017-07-05 00:40 +0200
      Re: [PATCH v3 net-next 00/12] bpf: rewrite value tracking in verifier Edward Cree <ecree@solarflare.com> - 2017-07-06 20:30 +0200
        Re: [PATCH v3 net-next 00/12] bpf: rewrite value tracking in verifier Daniel Borkmann <daniel@iogearbox.net> - 2017-07-07 11:20 +0200
          Re: [PATCH v3 net-next 00/12] bpf: rewrite value tracking in verifier Edward Cree <ecree@solarflare.com> - 2017-07-07 15:00 +0200
            Re: [PATCH v3 net-next 00/12] bpf: rewrite value tracking in verifier Daniel Borkmann <daniel@iogearbox.net> - 2017-07-07 15:10 +0200
    Re: [PATCH v3 net-next 00/12] bpf: rewrite value tracking in verifier Edward Cree <ecree@solarflare.com> - 2017-07-06 16:10 +0200

#1681140 — Re: [PATCH v3 net-next 00/12] bpf: rewrite value tracking in verifier

On 30/06/17 19:15, Alexei Starovoitov wrote:
> On 6/30/17 9:44 AM, Edward Cree wrote:
>> I haven't measured the test_progs ones, because I *still* haven't gotten
>>  around to actually setting up a BPF toolchain (it doesn't help that I'm
>>  building everything on a test server that gets reimaged every night to
>>  run our nightly tests...).
>
> then you're missing a lot of tests then...
> installing llvm is trivial. On x86 there are plenty of pre-built
> packages that you can apt-get or yum.
> Dave had to compile llvm and gcc from source on sparc, so volatile test
> server isn't really an excuse to miss all these tests ;)
> especially for such large verifier change.
>
After two days' wrestling with clang's build system, I'm finally able to
 run test_progs, and all its tests pass as of the full patch series.
Here are the processed insn counts:

Program         net-next  short  full
test_pkt_access       78     79    79
test_xdp             386    411   407
test_l4lb           6438   4154  4154
test_tcp_estats      435    436   435
test_bpf_obj_id        8      8     8
test_pkt_md_access    41     42    42

"short" is the first 3 patches plus the 'roll back ptr&const' patch I
 posted on Friday.  "full" is the full 12-patch series.  "Program" is
 the function in test_progs.c.
I don't know why test_l4lb has to process _fewer_ insns with my patches;
 if anything I'm worrying that I may be incorrectly pruning branches.
(I've spotted a possible bug in that I'm not looking at 'id' which,
 although it doesn't have to match, if two regs in the old state had the
 same id as each other, then those regs in the new state have to have
 the same id as each other too.)
Also interesting is that going from "short" to "full" only decreases the
 counts, suggesting that the ptr&const and full negative/positive
 tracking isn't (at least for these test cases) costly.

-Ed

[toc] | [next] | [standalone]

#1681207

On 07/04/2017 09:22 PM, Edward Cree wrote:
> On 30/06/17 19:15, Alexei Starovoitov wrote:
>> On 6/30/17 9:44 AM, Edward Cree wrote:
>>> I haven't measured the test_progs ones, because I *still* haven't gotten
>>>   around to actually setting up a BPF toolchain (it doesn't help that I'm
>>>   building everything on a test server that gets reimaged every night to
>>>   run our nightly tests...).
>>
>> then you're missing a lot of tests then...
>> installing llvm is trivial. On x86 there are plenty of pre-built
>> packages that you can apt-get or yum.
>> Dave had to compile llvm and gcc from source on sparc, so volatile test
>> server isn't really an excuse to miss all these tests ;)
>> especially for such large verifier change.
>>
> After two days' wrestling with clang's build system, I'm finally able to
>   run test_progs, and all its tests pass as of the full patch series.

(Hmm, usually with major distros LLVM comes with BPF targets enabled
by default these days, so there's less need to compile it from scratch
actually, just installation via yum/apt/... would suffice then.)

> Here are the processed insn counts:
>
> Program         net-next  short  full
> test_pkt_access       78     79    79
> test_xdp             386    411   407
> test_l4lb           6438   4154  4154
> test_tcp_estats      435    436   435
> test_bpf_obj_id        8      8     8
> test_pkt_md_access    41     42    42
>
> "short" is the first 3 patches plus the 'roll back ptr&const' patch I
>   posted on Friday.  "full" is the full 12-patch series.  "Program" is
>   the function in test_progs.c.
> I don't know why test_l4lb has to process _fewer_ insns with my patches;
>   if anything I'm worrying that I may be incorrectly pruning branches.
> (I've spotted a possible bug in that I'm not looking at 'id' which,
>   although it doesn't have to match, if two regs in the old state had the
>   same id as each other, then those regs in the new state have to have
>   the same id as each other too.)
> Also interesting is that going from "short" to "full" only decreases the
>   counts, suggesting that the ptr&const and full negative/positive
>   tracking isn't (at least for these test cases) costly.

Have you tried with cilium's BPF code? The kernel selftests are quite small,
so not really pushing processed insns too far. I can send you a BPF obj file
if that's easier for testing.

Thanks,
Daniel

[toc] | [prev] | [next] | [standalone]

#1682623

On 04/07/17 23:28, Daniel Borkmann wrote:
> Have you tried with cilium's BPF code? The kernel selftests are quite small,
> so not really pushing processed insns too far. I can send you a BPF obj file
> if that's easier for testing.
Results from the next (in-progress) version of the patch series, with the
 'id' bugfix I mentioned in my other mail, and rebased onto an updated
 net-next (0e72582).  Numbers collected with:
# tc filter add dev lo egress bpf da obj /path/to/bpf_object.o sec $section verb 2>&1 | grep "processed" | awk -e 'BEGIN { N = 0; }' -e '{ N += $2; }' -e 'END { print N; }'

Program                net-next   short    full
bpf_lb_opt_-DLB_L3.o       4707    5872    6515
bpf_lb_opt_-DLB_L4.o       7662    8652    8976
bpf_lb_opt_-DUNKNOWN.o      727    2972    2960
bpf_lxc_opt_-DDROP_ALL.o  57725   85750   95412
bpf_lxc_opt_-DUNKNOWN.o   93676  134043  141706
bpf_netdev.o              14702   24665   24251
bpf_overlay.o              7303   10939   10999

Conclusion: the ptr&const and full-range min/max tracking make little
 difference (10% increase at most, sometimes a decrease); most of the
 increase comes from the basic "replace imm and aux_off/align with tnums"
 patch.
So based on what Alexei was saying earlier, it sounds like the answer for
 now is to up the limit (say to a round 128k), get this series merged,
 then start work on pruning optimisation so we can hopefully bring that
 limit back down again later.  Sound reasonable?

-Ed

[toc] | [prev] | [next] | [standalone]

#1683061

On 07/06/2017 08:27 PM, Edward Cree wrote:
> On 04/07/17 23:28, Daniel Borkmann wrote:
>> Have you tried with cilium's BPF code? The kernel selftests are quite small,
>> so not really pushing processed insns too far. I can send you a BPF obj file
>> if that's easier for testing.
> Results from the next (in-progress) version of the patch series, with the
>   'id' bugfix I mentioned in my other mail, and rebased onto an updated
>   net-next (0e72582).  Numbers collected with:
> # tc filter add dev lo egress bpf da obj /path/to/bpf_object.o sec $section verb 2>&1 | grep "processed" | awk -e 'BEGIN { N = 0; }' -e '{ N += $2; }' -e 'END { print N; }'
>
> Program                net-next   short    full
> bpf_lb_opt_-DLB_L3.o       4707    5872    6515
> bpf_lb_opt_-DLB_L4.o       7662    8652    8976
> bpf_lb_opt_-DUNKNOWN.o      727    2972    2960
> bpf_lxc_opt_-DDROP_ALL.o  57725   85750   95412
> bpf_lxc_opt_-DUNKNOWN.o   93676  134043  141706
> bpf_netdev.o              14702   24665   24251
> bpf_overlay.o              7303   10939   10999
>
> Conclusion: the ptr&const and full-range min/max tracking make little
>   difference (10% increase at most, sometimes a decrease); most of the
>   increase comes from the basic "replace imm and aux_off/align with tnums"
>   patch.

Okay, thanks for the analysis, Edward.

> So based on what Alexei was saying earlier, it sounds like the answer for
>   now is to up the limit (say to a round 128k), get this series merged,
>   then start work on pruning optimisation so we can hopefully bring that
>   limit back down again later.  Sound reasonable?

But this means the bpf_lxc_* cases increase quite significantly,
arguably one of them is pretty close already, but the other one not
so much, meaning while 142k would shoot over the 128k target quite a
bit, the 95k is quite close to the point that it wouldn't take much,
say, few different optimizations from compiler, to hit the limit as
well eventually, something like 156k for the time being would seem a
more adequate raise perhaps that needs to be evaluated carefully
given the situation.

[toc] | [prev] | [next] | [standalone]

#1683171

On 07/07/17 10:14, Daniel Borkmann wrote:
> But this means the bpf_lxc_* cases increase quite significantly,
> arguably one of them is pretty close already, but the other one not
> so much, meaning while 142k would shoot over the 128k target quite a
> bit, the 95k is quite close to the point that it wouldn't take much,
> say, few different optimizations from compiler, to hit the limit as
> well eventually, something like 156k for the time being would seem a
> more adequate raise perhaps that needs to be evaluated carefully
> given the situation.
Note that the numbers in my table are the _sum_ of all the progs in the
 object file, not the #insns for a single program.  (Hence the awk
 invocation in my pipeline.)  For instance in bpf_lxc_opt_-DUNKNOWN.o
 on net-next there were (iirc) a couple of 30k progs and then some
 smaller ones, not a single 93k prog.

-Ed

[toc] | [prev] | [next] | [standalone]

#1683177

On 07/07/2017 02:50 PM, Edward Cree wrote:
> On 07/07/17 10:14, Daniel Borkmann wrote:
>> But this means the bpf_lxc_* cases increase quite significantly,
>> arguably one of them is pretty close already, but the other one not
>> so much, meaning while 142k would shoot over the 128k target quite a
>> bit, the 95k is quite close to the point that it wouldn't take much,
>> say, few different optimizations from compiler, to hit the limit as
>> well eventually, something like 156k for the time being would seem a
>> more adequate raise perhaps that needs to be evaluated carefully
>> given the situation.
> Note that the numbers in my table are the _sum_ of all the progs in the
>   object file, not the #insns for a single program.  (Hence the awk
>   invocation in my pipeline.)  For instance in bpf_lxc_opt_-DUNKNOWN.o
>   on net-next there were (iirc) a couple of 30k progs and then some
>   smaller ones, not a single 93k prog.

Okay, sorry, seems I misread in that case.

[toc] | [prev] | [next] | [standalone]

#1682457

On 04/07/17 20:22, Edward Cree wrote:
> I don't know why test_l4lb has to process _fewer_ insns with my patches;
>  if anything I'm worrying that I may be incorrectly pruning branches.
> (I've spotted a possible bug in that I'm not looking at 'id' which,
>  although it doesn't have to match, if two regs in the old state had the
>  same id as each other, then those regs in the new state have to have
>  the same id as each other too.)
I've now fixed that bug, and also changing it to not fill in 'id' on pointers
 other than PTR_TO_PACKET when doing arithmetic (because it's only used for
 'range' sharing and only PTR_TO_PACKET have that.  Of course
 PTR_TO_MAP_VALUE_OR_NULL still use id, but they don't get it from arithmetic).
Changes will be in next version of patch series, but for now:
Program         net-next  short  full   new
test_pkt_access       78     79    79    79
test_xdp             386    411   407   389
test_l4lb           6438   4154  4154  4062
test_tcp_estats      435    436   435   435
test_bpf_obj_id        8      8     8     8
test_pkt_md_access    41     42    42    42
As you can see, the #insns has gone down even further.

-Ed

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web