Re: [iovisor-dev] [PATCH v3 net-next 00/12] bpf: rewrite value tracking in verifier
I did an experiment with one of our internal bpf programs. The program has 1563 insns. Without Edward's patch: processed 13634 insns, stack depth 160 With Edward's patch: processed 15807 insns, stack depth 160 So the number of processed insns regressed by roughly 16%. Did anybody do any similar experiments to quantify the patch's impact in verification performance (e.g., in terms of processed insns)? On Tue, Jun 27, 2017 at 5:53 AM, Edward Cree via iovisor-dev wrote: > This series simplifies alignment tracking, generalises bounds tracking and > fixes some bounds-tracking bugs in the BPF verifier. Pointer arithmetic on > packet pointers, stack pointers, map value pointers and context pointers has > been unified, and bounds on these pointers are only checked when the pointer > is dereferenced. > Operations on pointers which destroy all relation to the original pointer > (such as multiplies and shifts) are disallowed if !env->allow_ptr_leaks, > otherwise they convert the pointer to an unknown scalar and feed it to the > normal scalar arithmetic handling. > Pointer types have been unified with the corresponding adjusted-pointer types > where those existed (e.g. PTR_TO_MAP_VALUE[_ADJ] or FRAME_PTR vs > PTR_TO_STACK); similarly, CONST_IMM and UNKNOWN_VALUE have been unified into > SCALAR_VALUE. > Pointer types (except CONST_PTR_TO_MAP, PTR_TO_MAP_VALUE_OR_NULL and > PTR_TO_PACKET_END, which do not allow arithmetic) have a 'fixed offset' and > a 'variable offset'; the former is used when e.g. adding an immediate or a > known-constant register, as long as it does not overflow. Otherwise the > latter is used, and any operation creating a new variable offset creates a > new 'id' (and, for PTR_TO_PACKET, clears the 'range'). > SCALAR_VALUEs use the 'variable offset' fields to track the range of possible > values; the 'fixed offset' should never be set on a scalar. > > As of patch 12/12, all tests of tools/testing/selftests/bpf/test_verifier > and tools/testing/selftests/bpf/test_align pass. > > v3: added a few more tests; removed RFC tags. > > v2: fixed nfp build, made test_align pass again and extended it with a few > new tests (though still need to add more). > > Edward Cree (12): > selftests/bpf: add test for mixed signed and unsigned bounds checks > bpf/verifier: rework value tracking > nfp: change bpf verifier hooks to match new verifier data structures > bpf/verifier: track signed and unsigned min/max values > bpf/verifier: more concise register state logs for constant var_off > selftests/bpf: change test_verifier expectations > selftests/bpf: rewrite test_align > selftests/bpf: add a test to test_align > selftests/bpf: add test for bogus operations on pointers > selftests/bpf: don't try to access past MAX_PACKET_OFF in > test_verifier > selftests/bpf: add tests for subtraction & negative numbers > selftests/bpf: variable offset negative tests > > drivers/net/ethernet/netronome/nfp/bpf/verifier.c | 24 +- > include/linux/bpf.h | 34 +- > include/linux/bpf_verifier.h | 56 +- > include/linux/tnum.h | 81 + > kernel/bpf/Makefile |2 +- > kernel/bpf/tnum.c | 180 ++ > kernel/bpf/verifier.c | 1943 > - > tools/testing/selftests/bpf/test_align.c | 462 - > tools/testing/selftests/bpf/test_verifier.c | 293 ++-- > 9 files changed, 2034 insertions(+), 1041 deletions(-) > create mode 100644 include/linux/tnum.h > create mode 100644 kernel/bpf/tnum.c > > ___ > iovisor-dev mailing list > iovisor-dev@lists.iovisor.org > https://lists.iovisor.org/mailman/listinfo/iovisor-dev ___ iovisor-dev mailing list iovisor-dev@lists.iovisor.org https://lists.iovisor.org/mailman/listinfo/iovisor-dev
Re: [iovisor-dev] [PATCH v3 net-next 00/12] bpf: rewrite value tracking in verifier
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. ___ iovisor-dev mailing list iovisor-dev@lists.iovisor.org https://lists.iovisor.org/mailman/listinfo/iovisor-dev
Re: [iovisor-dev] [PATCH v3 net-next 00/12] bpf: rewrite value tracking in verifier
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 ___ iovisor-dev mailing list iovisor-dev@lists.iovisor.org https://lists.iovisor.org/mailman/listinfo/iovisor-dev
Re: [iovisor-dev] [PATCH v3 net-next 00/12] bpf: rewrite value tracking in verifier
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; }'
Programnet-next shortfull
bpf_lb_opt_-DLB_L3.o 470758726515
bpf_lb_opt_-DLB_L4.o 766286528976
bpf_lb_opt_-DUNKNOWN.o 72729722960
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.
___
iovisor-dev mailing list
iovisor-dev@lists.iovisor.org
https://lists.iovisor.org/mailman/listinfo/iovisor-dev
Re: [iovisor-dev] [PATCH v3 net-next 00/12] bpf: rewrite value tracking in verifier
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; }'
Programnet-next shortfull
bpf_lb_opt_-DLB_L3.o 470758726515
bpf_lb_opt_-DLB_L4.o 766286528976
bpf_lb_opt_-DUNKNOWN.o 72729722960
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
___
iovisor-dev mailing list
iovisor-dev@lists.iovisor.org
https://lists.iovisor.org/mailman/listinfo/iovisor-dev
Re: [iovisor-dev] [PATCH v3 net-next 00/12] bpf: rewrite value tracking in verifier
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 797979 test_xdp 386411 407 389 test_l4lb 6438 4154 4154 4062 test_tcp_estats 435436 435 435 test_bpf_obj_id8 8 8 8 test_pkt_md_access41 424242 As you can see, the #insns has gone down even further. -Ed ___ iovisor-dev mailing list iovisor-dev@lists.iovisor.org https://lists.iovisor.org/mailman/listinfo/iovisor-dev
Re: [iovisor-dev] [PATCH v3 net-next 00/12] bpf: rewrite value tracking in verifier
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 7979 test_xdp 386411 407 test_l4lb 6438 4154 4154 test_tcp_estats 435436 435 test_bpf_obj_id8 8 8 test_pkt_md_access41 4242 "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 ___ iovisor-dev mailing list iovisor-dev@lists.iovisor.org https://lists.iovisor.org/mailman/listinfo/iovisor-dev
Re: [iovisor-dev] [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 7979 test_xdp 386411 407 test_l4lb 6438 4154 4154 test_tcp_estats 435436 435 test_bpf_obj_id8 8 8 test_pkt_md_access41 4242 "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 ___ iovisor-dev mailing list iovisor-dev@lists.iovisor.org https://lists.iovisor.org/mailman/listinfo/iovisor-dev
Re: [iovisor-dev] [PATCH v3 net-next 00/12] bpf: rewrite value tracking in verifier
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. ___ iovisor-dev mailing list iovisor-dev@lists.iovisor.org https://lists.iovisor.org/mailman/listinfo/iovisor-dev
Re: [iovisor-dev] [PATCH v3 net-next 00/12] bpf: rewrite value tracking in verifier
On 28/06/17 22:37, Alexei Starovoitov wrote: > Increasing the limit is must have, since pruning suffered so much. > Going from 53k to 76k is pretty substantial. > What is the % increase for tests in selftests/ ? When I tried to measure the test_verifier tests, they changed hardly at all, only a couple of percent iirc. But that's with (a) only the accepted progs get measured, since rejected don't print the #insns line - and most of the tests in test_verifier are rejected; and (b) those test progs are pretty small, usually with only a couple of jumps and not much chance for pruning to occur. So it's really not a great test case for pruning effectiveness. 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...). > I think we need to pin point exactly the reason. > Saying we just track more data is not enough. > We've tried v2 set on our load balancer and also saw ~20% increase. > I don't remember the absolute numbers. > These jumps don't make me comfortable with these extra tracking. > Can you try to roll back ptr&const and full negative/positive tracking > and see whether it gets back to what we had before? The ptr&const bit shouldn't be relevant unless your programs are actually doing that (i.e. ops on pointers other than +/-), which seems surprising. But if you really are, then it's not too hard to roll it back - just need to change how adjust_reg_min_max_vals() deals with EACCES. For a version without full negative/positive tracking, just take the first 3 patches; some of the selftests will fail but hopefully your progs will still be accepted. If not, we can try jbacik's patch (off-list response to v2). I will followup this email with a patch to apply on top of the first 3 that does that and rolls back ptr&const. > If tnum is causing it that would be reasonable trade off to make, > but if it's full neg/pos tracking that has no use today other than > (the whole thing is cleaner) I would rather drop it then. Well, the full neg/pos tracking was a result of needing to fix the bug I found with patch #1, and not wanting to confuse myself with the min/max range while doing my signed/unsigned tracking. But if we can make it work with jbacik's approach of 'remember whether our current bounds came from a signed or an unsigned compare', then we can drop or delay the full neg/pos tracking unless/until pruning is sorted out. -Ed ___ iovisor-dev mailing list iovisor-dev@lists.iovisor.org https://lists.iovisor.org/mailman/listinfo/iovisor-dev
Re: [iovisor-dev] [PATCH v3 net-next 00/12] bpf: rewrite value tracking in verifier
On Wed, Jun 28, 2017 at 10:38:02PM +0200, Daniel Borkmann wrote: > On 06/28/2017 04:11 PM, Edward Cree wrote: > > On 28/06/17 14:50, Daniel Borkmann wrote: > > > Hi Edward, > > > > > > Did you also have a chance in the meantime to look at reducing complexity > > > along with your unification? I did run the cilium test suite with your > > > latest set from here and current # worst case processed insns that > > > verifier has to go through for cilium progs increases from ~53k we have > > > right now to ~76k. I'm a bit worried that this quickly gets us close to > > > the upper ~98k max limit starting to reject programs again. Alternative > > > is to bump the complexity limit again in near future once run into it, > > > but preferably there's a way to optimize it along with the rewrite? Do > > > you see any possibilities worth exploring? > > The trouble, I think, is that as we're now tracking more information about > > each register value, we're less able to prune branches. But often that > > information is not actually being used in reaching the exit state. So it > > Agree. > > > seems like the way to tackle this would be to track what information is > > used — or at least, which registers are read from (including e.g. writing > > through them or passing them to helper calls) — in reaching a safe state. > > Then only registers which are used are required to match for pruning. > > But that tracking would presumably have to propagate backwards through the > > verifier stack, and I'm not sure how easily that could be done. Someone > > (was it you?) was talking about replacing the current DAG walking and > > pruning with some kind of basic-block thing, which would help with this. > > Summary: I think it could be done, but I haven't looked into the details > > of implementation yet; if it's not actually breaking your programs (yet), > > maybe leave it for a followup patch series? > > Could we adapt the limit to 128k perhaps as part of this set > given we know that we're tracking more meta data here anyway? Increasing the limit is must have, since pruning suffered so much. Going from 53k to 76k is pretty substantial. What is the % increase for tests in selftests/ ? I think we need to pin point exactly the reason. Saying we just track more data is not enough. We've tried v2 set on our load balancer and also saw ~20% increase. I don't remember the absolute numbers. These jumps don't make me comfortable with these extra tracking. Can you try to roll back ptr&const and full negative/positive tracking and see whether it gets back to what we had before? I agree that long term it's better to do proper basic block based liveness, but we need to do understand what's causing the increase today. If tnum is causing it that would be reasonable trade off to make, but if it's full neg/pos tracking that has no use today other than (the whole thing is cleaner) I would rather drop it then. We can always come back to it later once pruning issues are solved. ___ iovisor-dev mailing list iovisor-dev@lists.iovisor.org https://lists.iovisor.org/mailman/listinfo/iovisor-dev
Re: [iovisor-dev] [PATCH v3 net-next 00/12] bpf: rewrite value tracking in verifier
On 06/28/2017 04:11 PM, Edward Cree wrote: On 28/06/17 14:50, Daniel Borkmann wrote: Hi Edward, Did you also have a chance in the meantime to look at reducing complexity along with your unification? I did run the cilium test suite with your latest set from here and current # worst case processed insns that verifier has to go through for cilium progs increases from ~53k we have right now to ~76k. I'm a bit worried that this quickly gets us close to the upper ~98k max limit starting to reject programs again. Alternative is to bump the complexity limit again in near future once run into it, but preferably there's a way to optimize it along with the rewrite? Do you see any possibilities worth exploring? The trouble, I think, is that as we're now tracking more information about each register value, we're less able to prune branches. But often that information is not actually being used in reaching the exit state. So it Agree. seems like the way to tackle this would be to track what information is used — or at least, which registers are read from (including e.g. writing through them or passing them to helper calls) — in reaching a safe state. Then only registers which are used are required to match for pruning. But that tracking would presumably have to propagate backwards through the verifier stack, and I'm not sure how easily that could be done. Someone (was it you?) was talking about replacing the current DAG walking and pruning with some kind of basic-block thing, which would help with this. Summary: I think it could be done, but I haven't looked into the details of implementation yet; if it's not actually breaking your programs (yet), maybe leave it for a followup patch series? Could we adapt the limit to 128k perhaps as part of this set given we know that we're tracking more meta data here anyway? Then we could potentially avoid going via -stable later on, biggest pain point is usually tracking differences in LLVM code generation (e.g. differences in optimizations) along with verifier changes to make sure that programs still keep loading on older kernels with e.g. newer LLVM; one of the issues is that pruning can be quite fragile. E.g. worst case adding a simple var in a branch that LLVM assigns a stack slot that was otherwise not used throughout the prog can cause a significant increase of verifier work (run into this multiple times in the past and is a bit of a pain to track down actually). If we could keep some buffer in BPF_COMPLEXITY_LIMIT_INSNS at least when we know that more work is needed anyway from that point onward, that would be good. ___ iovisor-dev mailing list iovisor-dev@lists.iovisor.org https://lists.iovisor.org/mailman/listinfo/iovisor-dev
Re: [iovisor-dev] [PATCH v3 net-next 00/12] bpf: rewrite value tracking in verifier
On 28/06/17 14:50, Daniel Borkmann wrote: > Hi Edward, > > Did you also have a chance in the meantime to look at reducing complexity > along with your unification? I did run the cilium test suite with your > latest set from here and current # worst case processed insns that > verifier has to go through for cilium progs increases from ~53k we have > right now to ~76k. I'm a bit worried that this quickly gets us close to > the upper ~98k max limit starting to reject programs again. Alternative > is to bump the complexity limit again in near future once run into it, > but preferably there's a way to optimize it along with the rewrite? Do > you see any possibilities worth exploring? The trouble, I think, is that as we're now tracking more information about each register value, we're less able to prune branches. But often that information is not actually being used in reaching the exit state. So it seems like the way to tackle this would be to track what information is used — or at least, which registers are read from (including e.g. writing through them or passing them to helper calls) — in reaching a safe state. Then only registers which are used are required to match for pruning. But that tracking would presumably have to propagate backwards through the verifier stack, and I'm not sure how easily that could be done. Someone (was it you?) was talking about replacing the current DAG walking and pruning with some kind of basic-block thing, which would help with this. Summary: I think it could be done, but I haven't looked into the details of implementation yet; if it's not actually breaking your programs (yet), maybe leave it for a followup patch series? -Ed ___ iovisor-dev mailing list iovisor-dev@lists.iovisor.org https://lists.iovisor.org/mailman/listinfo/iovisor-dev
Re: [iovisor-dev] [PATCH v3 net-next 00/12] bpf: rewrite value tracking in verifier
Hi Edward, On 06/27/2017 02:53 PM, Edward Cree wrote: This series simplifies alignment tracking, generalises bounds tracking and fixes some bounds-tracking bugs in the BPF verifier. Pointer arithmetic on packet pointers, stack pointers, map value pointers and context pointers has been unified, and bounds on these pointers are only checked when the pointer is dereferenced. Operations on pointers which destroy all relation to the original pointer (such as multiplies and shifts) are disallowed if !env->allow_ptr_leaks, otherwise they convert the pointer to an unknown scalar and feed it to the normal scalar arithmetic handling. Pointer types have been unified with the corresponding adjusted-pointer types where those existed (e.g. PTR_TO_MAP_VALUE[_ADJ] or FRAME_PTR vs PTR_TO_STACK); similarly, CONST_IMM and UNKNOWN_VALUE have been unified into SCALAR_VALUE. Pointer types (except CONST_PTR_TO_MAP, PTR_TO_MAP_VALUE_OR_NULL and PTR_TO_PACKET_END, which do not allow arithmetic) have a 'fixed offset' and a 'variable offset'; the former is used when e.g. adding an immediate or a known-constant register, as long as it does not overflow. Otherwise the latter is used, and any operation creating a new variable offset creates a new 'id' (and, for PTR_TO_PACKET, clears the 'range'). SCALAR_VALUEs use the 'variable offset' fields to track the range of possible values; the 'fixed offset' should never be set on a scalar. As of patch 12/12, all tests of tools/testing/selftests/bpf/test_verifier and tools/testing/selftests/bpf/test_align pass. v3: added a few more tests; removed RFC tags. Did you also have a chance in the meantime to look at reducing complexity along with your unification? I did run the cilium test suite with your latest set from here and current # worst case processed insns that verifier has to go through for cilium progs increases from ~53k we have right now to ~76k. I'm a bit worried that this quickly gets us close to the upper ~98k max limit starting to reject programs again. Alternative is to bump the complexity limit again in near future once run into it, but preferably there's a way to optimize it along with the rewrite? Do you see any possibilities worth exploring? v2: fixed nfp build, made test_align pass again and extended it with a few new tests (though still need to add more). Edward Cree (12): selftests/bpf: add test for mixed signed and unsigned bounds checks bpf/verifier: rework value tracking nfp: change bpf verifier hooks to match new verifier data structures bpf/verifier: track signed and unsigned min/max values bpf/verifier: more concise register state logs for constant var_off selftests/bpf: change test_verifier expectations selftests/bpf: rewrite test_align selftests/bpf: add a test to test_align selftests/bpf: add test for bogus operations on pointers selftests/bpf: don't try to access past MAX_PACKET_OFF in test_verifier selftests/bpf: add tests for subtraction & negative numbers selftests/bpf: variable offset negative tests drivers/net/ethernet/netronome/nfp/bpf/verifier.c | 24 +- include/linux/bpf.h | 34 +- include/linux/bpf_verifier.h | 56 +- include/linux/tnum.h | 81 + kernel/bpf/Makefile |2 +- kernel/bpf/tnum.c | 180 ++ kernel/bpf/verifier.c | 1943 - tools/testing/selftests/bpf/test_align.c | 462 - tools/testing/selftests/bpf/test_verifier.c | 293 ++-- 9 files changed, 2034 insertions(+), 1041 deletions(-) create mode 100644 include/linux/tnum.h create mode 100644 kernel/bpf/tnum.c Thanks, Daniel ___ iovisor-dev mailing list iovisor-dev@lists.iovisor.org https://lists.iovisor.org/mailman/listinfo/iovisor-dev
[iovisor-dev] [PATCH v3 net-next 00/12] bpf: rewrite value tracking in verifier
This series simplifies alignment tracking, generalises bounds tracking and fixes some bounds-tracking bugs in the BPF verifier. Pointer arithmetic on packet pointers, stack pointers, map value pointers and context pointers has been unified, and bounds on these pointers are only checked when the pointer is dereferenced. Operations on pointers which destroy all relation to the original pointer (such as multiplies and shifts) are disallowed if !env->allow_ptr_leaks, otherwise they convert the pointer to an unknown scalar and feed it to the normal scalar arithmetic handling. Pointer types have been unified with the corresponding adjusted-pointer types where those existed (e.g. PTR_TO_MAP_VALUE[_ADJ] or FRAME_PTR vs PTR_TO_STACK); similarly, CONST_IMM and UNKNOWN_VALUE have been unified into SCALAR_VALUE. Pointer types (except CONST_PTR_TO_MAP, PTR_TO_MAP_VALUE_OR_NULL and PTR_TO_PACKET_END, which do not allow arithmetic) have a 'fixed offset' and a 'variable offset'; the former is used when e.g. adding an immediate or a known-constant register, as long as it does not overflow. Otherwise the latter is used, and any operation creating a new variable offset creates a new 'id' (and, for PTR_TO_PACKET, clears the 'range'). SCALAR_VALUEs use the 'variable offset' fields to track the range of possible values; the 'fixed offset' should never be set on a scalar. As of patch 12/12, all tests of tools/testing/selftests/bpf/test_verifier and tools/testing/selftests/bpf/test_align pass. v3: added a few more tests; removed RFC tags. v2: fixed nfp build, made test_align pass again and extended it with a few new tests (though still need to add more). Edward Cree (12): selftests/bpf: add test for mixed signed and unsigned bounds checks bpf/verifier: rework value tracking nfp: change bpf verifier hooks to match new verifier data structures bpf/verifier: track signed and unsigned min/max values bpf/verifier: more concise register state logs for constant var_off selftests/bpf: change test_verifier expectations selftests/bpf: rewrite test_align selftests/bpf: add a test to test_align selftests/bpf: add test for bogus operations on pointers selftests/bpf: don't try to access past MAX_PACKET_OFF in test_verifier selftests/bpf: add tests for subtraction & negative numbers selftests/bpf: variable offset negative tests drivers/net/ethernet/netronome/nfp/bpf/verifier.c | 24 +- include/linux/bpf.h | 34 +- include/linux/bpf_verifier.h | 56 +- include/linux/tnum.h | 81 + kernel/bpf/Makefile |2 +- kernel/bpf/tnum.c | 180 ++ kernel/bpf/verifier.c | 1943 - tools/testing/selftests/bpf/test_align.c | 462 - tools/testing/selftests/bpf/test_verifier.c | 293 ++-- 9 files changed, 2034 insertions(+), 1041 deletions(-) create mode 100644 include/linux/tnum.h create mode 100644 kernel/bpf/tnum.c ___ iovisor-dev mailing list iovisor-dev@lists.iovisor.org https://lists.iovisor.org/mailman/listinfo/iovisor-dev
