[PATCH bpf-next 0/2] selftests/bpf: more loop tests

[PATCH bpf-next 0/2] selftests/bpf: more loop tests

[Alexei Starovoitov]

Add two bounded loop tests.

Alexei Starovoitov (2):
  selftests/bpf: add loop test 4
  selftests/bpf: add loop test 5

 .../bpf/prog_tests/bpf_verif_scale.c          |  2 +
 tools/testing/selftests/bpf/progs/loop4.c     | 23 ++++++++++++
 tools/testing/selftests/bpf/progs/loop5.c     | 37 +++++++++++++++++++
 3 files changed, 62 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/progs/loop4.c
 create mode 100644 tools/testing/selftests/bpf/progs/loop5.c

-- 
2.20.0

[PATCH bpf-next 1/2] selftests/bpf: add loop test 4

[Alexei Starovoitov]

Add a test that returns a 'random' number between [0, 2^20)
If state pruning is not working correctly for loop body the number of
processed insns will be 2^20 * num_of_insns_in_loop_body and the program
will be rejected.

Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
 .../bpf/prog_tests/bpf_verif_scale.c          |  1 +
 tools/testing/selftests/bpf/progs/loop4.c     | 23 +++++++++++++++++++
 2 files changed, 24 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/progs/loop4.c

diff --git a/tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c b/tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c
index b4be96162ff4..757e39540eda 100644
--- a/tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c
+++ b/tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c
@@ -71,6 +71,7 @@ void test_bpf_verif_scale(void)
 
 		{ "loop1.o", BPF_PROG_TYPE_RAW_TRACEPOINT },
 		{ "loop2.o", BPF_PROG_TYPE_RAW_TRACEPOINT },
+		{ "loop4.o", BPF_PROG_TYPE_RAW_TRACEPOINT },
 
 		/* partial unroll. 19k insn in a loop.
 		 * Total program size 20.8k insn.
diff --git a/tools/testing/selftests/bpf/progs/loop4.c b/tools/testing/selftests/bpf/progs/loop4.c
new file mode 100644
index 000000000000..3e7ee14fddbd
--- /dev/null
+++ b/tools/testing/selftests/bpf/progs/loop4.c
@@ -0,0 +1,23 @@
+// SPDX-License-Identifier: GPL-2.0
+// Copyright (c) 2019 Facebook
+#include <linux/sched.h>
+#include <linux/ptrace.h>
+#include <stdint.h>
+#include <stddef.h>
+#include <stdbool.h>
+#include <linux/bpf.h>
+#include "bpf_helpers.h"
+
+char _license[] SEC("license") = "GPL";
+
+SEC("socket")
+int combinations(volatile struct __sk_buff* skb)
+{
+	int ret = 0, i;
+
+#pragma nounroll
+	for (i = 0; i < 20; i++)
+		if (skb->len)
+			ret |= 1 << i;
+	return ret;
+}
-- 
2.20.0

Re: [PATCH bpf-next 1/2] selftests/bpf: add loop test 4

[Yonghong Song]

On 8/2/19 4:33 PM, Alexei Starovoitov wrote:
> Add a test that returns a 'random' number between [0, 2^20)
> If state pruning is not working correctly for loop body the number of
> processed insns will be 2^20 * num_of_insns_in_loop_body and the program
> will be rejected.

The maximum processed insns will be 2^20 or 2^20 * 
num_of_insns_in_loop_body? I thought the verifier will
stop processing once processed insns reach 1M?

Could you elaborate which potential issues in verifier
you try to cover with this test case? Extra tests are
always welcome. We already have scale/loop tests and some
(e.g., strobemeta tests) are more complex than this one.
Maybe you have something in mind for this particular
test? Putting in the commit message may help people understand
the concerns.

> 
> Signed-off-by: Alexei Starovoitov <ast@kernel.org>
> ---
>   .../bpf/prog_tests/bpf_verif_scale.c          |  1 +
>   tools/testing/selftests/bpf/progs/loop4.c     | 23 +++++++++++++++++++
>   2 files changed, 24 insertions(+)
>   create mode 100644 tools/testing/selftests/bpf/progs/loop4.c
> 
> diff --git a/tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c b/tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c
> index b4be96162ff4..757e39540eda 100644
> --- a/tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c
> +++ b/tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c
> @@ -71,6 +71,7 @@ void test_bpf_verif_scale(void)
>   
>   		{ "loop1.o", BPF_PROG_TYPE_RAW_TRACEPOINT },
>   		{ "loop2.o", BPF_PROG_TYPE_RAW_TRACEPOINT },
> +		{ "loop4.o", BPF_PROG_TYPE_RAW_TRACEPOINT },

The program is more like a BPF_PROG_TYPE_SCHED_CLS type than
a BPF_PROG_TYPE_RAW_TRACEPOINT?

>   
>   		/* partial unroll. 19k insn in a loop.
>   		 * Total program size 20.8k insn.
> diff --git a/tools/testing/selftests/bpf/progs/loop4.c b/tools/testing/selftests/bpf/progs/loop4.c
> new file mode 100644
> index 000000000000..3e7ee14fddbd
> --- /dev/null
> +++ b/tools/testing/selftests/bpf/progs/loop4.c
> @@ -0,0 +1,23 @@
> +// SPDX-License-Identifier: GPL-2.0
> +// Copyright (c) 2019 Facebook
> +#include <linux/sched.h>
> +#include <linux/ptrace.h>

Since the program is a networking type,
the above two headers are probably unneeded.

> +#include <stdint.h>
> +#include <stddef.h>
> +#include <stdbool.h>
> +#include <linux/bpf.h>
> +#include "bpf_helpers.h"
> +
> +char _license[] SEC("license") = "GPL";
> +
> +SEC("socket")
> +int combinations(volatile struct __sk_buff* skb)
> +{
> +	int ret = 0, i;
> +
> +#pragma nounroll
> +	for (i = 0; i < 20; i++)
> +		if (skb->len)
> +			ret |= 1 << i;
> +	return ret;
> +}
> 

Re: [PATCH bpf-next 1/2] selftests/bpf: add loop test 4

[Alexei Starovoitov]

On Sun, Aug 04, 2019 at 05:29:42AM +0000, Yonghong Song wrote:
> 
> 
> On 8/2/19 4:33 PM, Alexei Starovoitov wrote:
> > Add a test that returns a 'random' number between [0, 2^20)
> > If state pruning is not working correctly for loop body the number of
> > processed insns will be 2^20 * num_of_insns_in_loop_body and the program
> > will be rejected.
> 
> The maximum processed insns will be 2^20 or 2^20 * 
> num_of_insns_in_loop_body? 

the later.

> I thought the verifier will
> stop processing once processed insns reach 1M?

right.

> Could you elaborate which potential issues in verifier
> you try to cover with this test case? Extra tests are
> always welcome. We already have scale/loop tests and some
> (e.g., strobemeta tests) are more complex than this one.
> Maybe you have something in mind for this particular
> test? Putting in the commit message may help people understand
> the concerns.

it's not testing any new functionality.
It's more targeted test that pruning happens in loop body due to precision tracking.
When precision tracking is off the pruning won't be happening and 1m will be hit.
Since it's a small test comparing to others it's easier to analyze.

2^20 is to make sure 1m will be hit even if loop body is 1 insn.
For the given llmv the loop body is 16 insn, but it may vary.

> > 
> > Signed-off-by: Alexei Starovoitov <ast@kernel.org>
> > ---
> >   .../bpf/prog_tests/bpf_verif_scale.c          |  1 +
> >   tools/testing/selftests/bpf/progs/loop4.c     | 23 +++++++++++++++++++
> >   2 files changed, 24 insertions(+)
> >   create mode 100644 tools/testing/selftests/bpf/progs/loop4.c
> > 
> > diff --git a/tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c b/tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c
> > index b4be96162ff4..757e39540eda 100644
> > --- a/tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c
> > +++ b/tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c
> > @@ -71,6 +71,7 @@ void test_bpf_verif_scale(void)
> >   
> >   		{ "loop1.o", BPF_PROG_TYPE_RAW_TRACEPOINT },
> >   		{ "loop2.o", BPF_PROG_TYPE_RAW_TRACEPOINT },
> > +		{ "loop4.o", BPF_PROG_TYPE_RAW_TRACEPOINT },
> 
> The program is more like a BPF_PROG_TYPE_SCHED_CLS type than
> a BPF_PROG_TYPE_RAW_TRACEPOINT?

right. that's more accurate.

> >   
> >   		/* partial unroll. 19k insn in a loop.
> >   		 * Total program size 20.8k insn.
> > diff --git a/tools/testing/selftests/bpf/progs/loop4.c b/tools/testing/selftests/bpf/progs/loop4.c
> > new file mode 100644
> > index 000000000000..3e7ee14fddbd
> > --- /dev/null
> > +++ b/tools/testing/selftests/bpf/progs/loop4.c
> > @@ -0,0 +1,23 @@
> > +// SPDX-License-Identifier: GPL-2.0
> > +// Copyright (c) 2019 Facebook
> > +#include <linux/sched.h>
> > +#include <linux/ptrace.h>
> 
> Since the program is a networking type,
> the above two headers are probably unneeded.

yeah. just a copy paste. will remove

> > +#include <stdint.h>
> > +#include <stddef.h>
> > +#include <stdbool.h>
> > +#include <linux/bpf.h>
> > +#include "bpf_helpers.h"
> > +
> > +char _license[] SEC("license") = "GPL";
> > +
> > +SEC("socket")
> > +int combinations(volatile struct __sk_buff* skb)
> > +{
> > +	int ret = 0, i;
> > +
> > +#pragma nounroll
> > +	for (i = 0; i < 20; i++)
> > +		if (skb->len)
> > +			ret |= 1 << i;
> > +	return ret;
> > +}
> > 

Re: [PATCH bpf-next 1/2] selftests/bpf: add loop test 4

[Andrii Nakryiko]

On Sat, Aug 3, 2019 at 8:19 PM Alexei Starovoitov <ast@kernel.org> wrote:
>
> Add a test that returns a 'random' number between [0, 2^20)
> If state pruning is not working correctly for loop body the number of
> processed insns will be 2^20 * num_of_insns_in_loop_body and the program
> will be rejected.
>
> Signed-off-by: Alexei Starovoitov <ast@kernel.org>
> ---
>  .../bpf/prog_tests/bpf_verif_scale.c          |  1 +
>  tools/testing/selftests/bpf/progs/loop4.c     | 23 +++++++++++++++++++
>  2 files changed, 24 insertions(+)
>  create mode 100644 tools/testing/selftests/bpf/progs/loop4.c
>
> diff --git a/tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c b/tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c
> index b4be96162ff4..757e39540eda 100644
> --- a/tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c
> +++ b/tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c
> @@ -71,6 +71,7 @@ void test_bpf_verif_scale(void)
>
>                 { "loop1.o", BPF_PROG_TYPE_RAW_TRACEPOINT },
>                 { "loop2.o", BPF_PROG_TYPE_RAW_TRACEPOINT },
> +               { "loop4.o", BPF_PROG_TYPE_RAW_TRACEPOINT },
>
>                 /* partial unroll. 19k insn in a loop.
>                  * Total program size 20.8k insn.
> diff --git a/tools/testing/selftests/bpf/progs/loop4.c b/tools/testing/selftests/bpf/progs/loop4.c
> new file mode 100644
> index 000000000000..3e7ee14fddbd
> --- /dev/null
> +++ b/tools/testing/selftests/bpf/progs/loop4.c
> @@ -0,0 +1,23 @@
> +// SPDX-License-Identifier: GPL-2.0
> +// Copyright (c) 2019 Facebook
> +#include <linux/sched.h>
> +#include <linux/ptrace.h>
> +#include <stdint.h>
> +#include <stddef.h>
> +#include <stdbool.h>
> +#include <linux/bpf.h>
> +#include "bpf_helpers.h"
> +
> +char _license[] SEC("license") = "GPL";
> +
> +SEC("socket")
> +int combinations(volatile struct __sk_buff* skb)
> +{
> +       int ret = 0, i;
> +
> +#pragma nounroll
> +       for (i = 0; i < 20; i++)
> +               if (skb->len)
> +                       ret |= 1 << i;

So I think the idea is that because verifier shouldn't know whether
skb->len is zero or not, then you have two outcomes on every iteration
leading to 2^20 states, right?

But I'm afraid that verifier can eventually be smart enough (if it's
not already, btw), to figure out that ret can be either 0 or ((1 <<
21) - 1), actually. If skb->len is put into separate register, then
that register's bounds will be established on first loop iteration as
either == 0 on one branch or (0, inf) on another branch, after which
all subsequent iterations will not branch at all (one or the other
branch will be always taken).

It's also possible that LLVM/Clang is smart enough already to figure
this out on its own and optimize loop into.


if (skb->len) {
    for (i = 0; i < 20; i++)
        ret |= 1 << i;
}


So two complains:

1. Let's obfuscate this a bit more, e.g., with testing (skb->len &
(1<<i)) instead, so that result really depends on actual length of the
packet.
2. Is it possible to somehow turn off this precision tracking (e.g.,
running not under root, maybe?) and see that this same program fails
in that case? That way we'll know test actually validates what we
think it validates.

Thoughts?

> +       return ret;
> +}
> --
> 2.20.0
>

Re: [PATCH bpf-next 1/2] selftests/bpf: add loop test 4

[Yonghong Song]

On 8/5/19 12:45 PM, Andrii Nakryiko wrote:
> On Sat, Aug 3, 2019 at 8:19 PM Alexei Starovoitov <ast@kernel.org> wrote:
>>
>> Add a test that returns a 'random' number between [0, 2^20)
>> If state pruning is not working correctly for loop body the number of
>> processed insns will be 2^20 * num_of_insns_in_loop_body and the program
>> will be rejected.
>>
>> Signed-off-by: Alexei Starovoitov <ast@kernel.org>
>> ---
>>   .../bpf/prog_tests/bpf_verif_scale.c          |  1 +
>>   tools/testing/selftests/bpf/progs/loop4.c     | 23 +++++++++++++++++++
>>   2 files changed, 24 insertions(+)
>>   create mode 100644 tools/testing/selftests/bpf/progs/loop4.c
>>
>> diff --git a/tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c b/tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c
>> index b4be96162ff4..757e39540eda 100644
>> --- a/tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c
>> +++ b/tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c
>> @@ -71,6 +71,7 @@ void test_bpf_verif_scale(void)
>>
>>                  { "loop1.o", BPF_PROG_TYPE_RAW_TRACEPOINT },
>>                  { "loop2.o", BPF_PROG_TYPE_RAW_TRACEPOINT },
>> +               { "loop4.o", BPF_PROG_TYPE_RAW_TRACEPOINT },
>>
>>                  /* partial unroll. 19k insn in a loop.
>>                   * Total program size 20.8k insn.
>> diff --git a/tools/testing/selftests/bpf/progs/loop4.c b/tools/testing/selftests/bpf/progs/loop4.c
>> new file mode 100644
>> index 000000000000..3e7ee14fddbd
>> --- /dev/null
>> +++ b/tools/testing/selftests/bpf/progs/loop4.c
>> @@ -0,0 +1,23 @@
>> +// SPDX-License-Identifier: GPL-2.0
>> +// Copyright (c) 2019 Facebook
>> +#include <linux/sched.h>
>> +#include <linux/ptrace.h>
>> +#include <stdint.h>
>> +#include <stddef.h>
>> +#include <stdbool.h>
>> +#include <linux/bpf.h>
>> +#include "bpf_helpers.h"
>> +
>> +char _license[] SEC("license") = "GPL";
>> +
>> +SEC("socket")
>> +int combinations(volatile struct __sk_buff* skb)
>> +{
>> +       int ret = 0, i;
>> +
>> +#pragma nounroll
>> +       for (i = 0; i < 20; i++)
>> +               if (skb->len)
>> +                       ret |= 1 << i;
> 
> So I think the idea is that because verifier shouldn't know whether
> skb->len is zero or not, then you have two outcomes on every iteration
> leading to 2^20 states, right?
> 
> But I'm afraid that verifier can eventually be smart enough (if it's
> not already, btw), to figure out that ret can be either 0 or ((1 <<
> 21) - 1), actually. If skb->len is put into separate register, then
> that register's bounds will be established on first loop iteration as
> either == 0 on one branch or (0, inf) on another branch, after which
> all subsequent iterations will not branch at all (one or the other
> branch will be always taken).
> 
> It's also possible that LLVM/Clang is smart enough already to figure
> this out on its own and optimize loop into.
> 
> 
> if (skb->len) {
>      for (i = 0; i < 20; i++)
>          ret |= 1 << i;
> }

We have
    volatile struct __sk_buff* skb

So from the source code, skb->len could be different for each
iteration. The compiler cannot do the above optimization.

> 
> 
> So two complains:
> 
> 1. Let's obfuscate this a bit more, e.g., with testing (skb->len &
> (1<<i)) instead, so that result really depends on actual length of the
> packet.
> 2. Is it possible to somehow turn off this precision tracking (e.g.,
> running not under root, maybe?) and see that this same program fails
> in that case? That way we'll know test actually validates what we
> think it validates.
> 
> Thoughts?
> 
>> +       return ret;
>> +}
>> --
>> 2.20.0
>>

Re: [PATCH bpf-next 1/2] selftests/bpf: add loop test 4

[Alexei Starovoitov]

On 8/5/19 1:04 PM, Yonghong Song wrote:
> 
> 
> On 8/5/19 12:45 PM, Andrii Nakryiko wrote:
>> On Sat, Aug 3, 2019 at 8:19 PM Alexei Starovoitov <ast@kernel.org> wrote:
>>>
>>> Add a test that returns a 'random' number between [0, 2^20)
>>> If state pruning is not working correctly for loop body the number of
>>> processed insns will be 2^20 * num_of_insns_in_loop_body and the program
>>> will be rejected.
>>>
>>> Signed-off-by: Alexei Starovoitov <ast@kernel.org>
>>> ---
>>>    .../bpf/prog_tests/bpf_verif_scale.c          |  1 +
>>>    tools/testing/selftests/bpf/progs/loop4.c     | 23 +++++++++++++++++++
>>>    2 files changed, 24 insertions(+)
>>>    create mode 100644 tools/testing/selftests/bpf/progs/loop4.c
>>>
>>> diff --git a/tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c b/tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c
>>> index b4be96162ff4..757e39540eda 100644
>>> --- a/tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c
>>> +++ b/tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c
>>> @@ -71,6 +71,7 @@ void test_bpf_verif_scale(void)
>>>
>>>                   { "loop1.o", BPF_PROG_TYPE_RAW_TRACEPOINT },
>>>                   { "loop2.o", BPF_PROG_TYPE_RAW_TRACEPOINT },
>>> +               { "loop4.o", BPF_PROG_TYPE_RAW_TRACEPOINT },
>>>
>>>                   /* partial unroll. 19k insn in a loop.
>>>                    * Total program size 20.8k insn.
>>> diff --git a/tools/testing/selftests/bpf/progs/loop4.c b/tools/testing/selftests/bpf/progs/loop4.c
>>> new file mode 100644
>>> index 000000000000..3e7ee14fddbd
>>> --- /dev/null
>>> +++ b/tools/testing/selftests/bpf/progs/loop4.c
>>> @@ -0,0 +1,23 @@
>>> +// SPDX-License-Identifier: GPL-2.0
>>> +// Copyright (c) 2019 Facebook
>>> +#include <linux/sched.h>
>>> +#include <linux/ptrace.h>
>>> +#include <stdint.h>
>>> +#include <stddef.h>
>>> +#include <stdbool.h>
>>> +#include <linux/bpf.h>
>>> +#include "bpf_helpers.h"
>>> +
>>> +char _license[] SEC("license") = "GPL";
>>> +
>>> +SEC("socket")
>>> +int combinations(volatile struct __sk_buff* skb)
>>> +{
>>> +       int ret = 0, i;
>>> +
>>> +#pragma nounroll
>>> +       for (i = 0; i < 20; i++)
>>> +               if (skb->len)
>>> +                       ret |= 1 << i;
>>
>> So I think the idea is that because verifier shouldn't know whether
>> skb->len is zero or not, then you have two outcomes on every iteration
>> leading to 2^20 states, right?
>>
>> But I'm afraid that verifier can eventually be smart enough (if it's
>> not already, btw), to figure out that ret can be either 0 or ((1 <<
>> 21) - 1), actually. If skb->len is put into separate register, then
>> that register's bounds will be established on first loop iteration as
>> either == 0 on one branch or (0, inf) on another branch, after which
>> all subsequent iterations will not branch at all (one or the other
>> branch will be always taken).
>>
>> It's also possible that LLVM/Clang is smart enough already to figure
>> this out on its own and optimize loop into.
>>
>>
>> if (skb->len) {
>>       for (i = 0; i < 20; i++)
>>           ret |= 1 << i;
>> }
> 
> We have
>      volatile struct __sk_buff* skb
> 
> So from the source code, skb->len could be different for each
> iteration. The compiler cannot do the above optimization.

yep.
Without volatile llvm optimizes it even more than Andrii predicted :)

>>
>>
>> So two complains:
>>
>> 1. Let's obfuscate this a bit more, e.g., with testing (skb->len &
>> (1<<i)) instead, so that result really depends on actual length of the
>> packet.
>> 2. Is it possible to somehow turn off this precision tracking (e.g.,
>> running not under root, maybe?) and see that this same program fails
>> in that case? That way we'll know test actually validates what we
>> think it validates.

that's on my todo list already.
To do proper unit tests for all this stuff there should be a way
to turn off not only precision, but heuristics too.
All magic numbers in is_state_visited() need to be switchable.
I'm still thinking on the way to expose it to tests infra.

Re: [PATCH bpf-next 1/2] selftests/bpf: add loop test 4

[Andrii Nakryiko]

On Mon, Aug 5, 2019 at 1:53 PM Alexei Starovoitov <ast@fb.com> wrote:
>
> On 8/5/19 1:04 PM, Yonghong Song wrote:
> >
> >
> > On 8/5/19 12:45 PM, Andrii Nakryiko wrote:
> >> On Sat, Aug 3, 2019 at 8:19 PM Alexei Starovoitov <ast@kernel.org> wrote:
> >>>
> >>> Add a test that returns a 'random' number between [0, 2^20)
> >>> If state pruning is not working correctly for loop body the number of
> >>> processed insns will be 2^20 * num_of_insns_in_loop_body and the program
> >>> will be rejected.
> >>>
> >>> Signed-off-by: Alexei Starovoitov <ast@kernel.org>
> >>> ---
> >>>    .../bpf/prog_tests/bpf_verif_scale.c          |  1 +
> >>>    tools/testing/selftests/bpf/progs/loop4.c     | 23 +++++++++++++++++++
> >>>    2 files changed, 24 insertions(+)
> >>>    create mode 100644 tools/testing/selftests/bpf/progs/loop4.c
> >>>
> >>> diff --git a/tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c b/tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c
> >>> index b4be96162ff4..757e39540eda 100644
> >>> --- a/tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c
> >>> +++ b/tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c
> >>> @@ -71,6 +71,7 @@ void test_bpf_verif_scale(void)
> >>>
> >>>                   { "loop1.o", BPF_PROG_TYPE_RAW_TRACEPOINT },
> >>>                   { "loop2.o", BPF_PROG_TYPE_RAW_TRACEPOINT },
> >>> +               { "loop4.o", BPF_PROG_TYPE_RAW_TRACEPOINT },
> >>>
> >>>                   /* partial unroll. 19k insn in a loop.
> >>>                    * Total program size 20.8k insn.
> >>> diff --git a/tools/testing/selftests/bpf/progs/loop4.c b/tools/testing/selftests/bpf/progs/loop4.c
> >>> new file mode 100644
> >>> index 000000000000..3e7ee14fddbd
> >>> --- /dev/null
> >>> +++ b/tools/testing/selftests/bpf/progs/loop4.c
> >>> @@ -0,0 +1,23 @@
> >>> +// SPDX-License-Identifier: GPL-2.0
> >>> +// Copyright (c) 2019 Facebook
> >>> +#include <linux/sched.h>
> >>> +#include <linux/ptrace.h>
> >>> +#include <stdint.h>
> >>> +#include <stddef.h>
> >>> +#include <stdbool.h>
> >>> +#include <linux/bpf.h>
> >>> +#include "bpf_helpers.h"
> >>> +
> >>> +char _license[] SEC("license") = "GPL";
> >>> +
> >>> +SEC("socket")
> >>> +int combinations(volatile struct __sk_buff* skb)
> >>> +{
> >>> +       int ret = 0, i;
> >>> +
> >>> +#pragma nounroll
> >>> +       for (i = 0; i < 20; i++)
> >>> +               if (skb->len)
> >>> +                       ret |= 1 << i;
> >>
> >> So I think the idea is that because verifier shouldn't know whether
> >> skb->len is zero or not, then you have two outcomes on every iteration
> >> leading to 2^20 states, right?
> >>
> >> But I'm afraid that verifier can eventually be smart enough (if it's
> >> not already, btw), to figure out that ret can be either 0 or ((1 <<
> >> 21) - 1), actually. If skb->len is put into separate register, then
> >> that register's bounds will be established on first loop iteration as
> >> either == 0 on one branch or (0, inf) on another branch, after which
> >> all subsequent iterations will not branch at all (one or the other
> >> branch will be always taken).
> >>
> >> It's also possible that LLVM/Clang is smart enough already to figure
> >> this out on its own and optimize loop into.
> >>
> >>
> >> if (skb->len) {
> >>       for (i = 0; i < 20; i++)
> >>           ret |= 1 << i;
> >> }
> >
> > We have
> >      volatile struct __sk_buff* skb
> >
> > So from the source code, skb->len could be different for each
> > iteration. The compiler cannot do the above optimization.
>
> yep.
> Without volatile llvm optimizes it even more than Andrii predicted :)

My bad, completely missed volatile.

>
> >>
> >>
> >> So two complains:
> >>
> >> 1. Let's obfuscate this a bit more, e.g., with testing (skb->len &
> >> (1<<i)) instead, so that result really depends on actual length of the
> >> packet.
> >> 2. Is it possible to somehow turn off this precision tracking (e.g.,
> >> running not under root, maybe?) and see that this same program fails
> >> in that case? That way we'll know test actually validates what we
> >> think it validates.
>
> that's on my todo list already.
> To do proper unit tests for all this stuff there should be a way
> to turn off not only precision, but heuristics too.
> All magic numbers in is_state_visited() need to be switchable.
> I'm still thinking on the way to expose it to tests infra.

Yep, that would be great.

I have nothing beyond what Yonghong suggested.

Acked-by: Andrii Nakryiko <andriin@fb.com>

[PATCH bpf-next 2/2] selftests/bpf: add loop test 5

[Alexei Starovoitov]

Add a test with multiple exit conditions.
It's not an infinite loop only when the verifier can properly track
all math on variable 'i' through all possible ways of executing this loop.

barrier()s are needed to disable llvm optimization that combines multiple
branches into fewer branches.

Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
 .../bpf/prog_tests/bpf_verif_scale.c          |  1 +
 tools/testing/selftests/bpf/progs/loop5.c     | 37 +++++++++++++++++++
 2 files changed, 38 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/progs/loop5.c

diff --git a/tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c b/tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c
index 757e39540eda..29615a4a9362 100644
--- a/tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c
+++ b/tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c
@@ -72,6 +72,7 @@ void test_bpf_verif_scale(void)
 		{ "loop1.o", BPF_PROG_TYPE_RAW_TRACEPOINT },
 		{ "loop2.o", BPF_PROG_TYPE_RAW_TRACEPOINT },
 		{ "loop4.o", BPF_PROG_TYPE_RAW_TRACEPOINT },
+		{ "loop5.o", BPF_PROG_TYPE_RAW_TRACEPOINT },
 
 		/* partial unroll. 19k insn in a loop.
 		 * Total program size 20.8k insn.
diff --git a/tools/testing/selftests/bpf/progs/loop5.c b/tools/testing/selftests/bpf/progs/loop5.c
new file mode 100644
index 000000000000..9d9817efe208
--- /dev/null
+++ b/tools/testing/selftests/bpf/progs/loop5.c
@@ -0,0 +1,37 @@
+// SPDX-License-Identifier: GPL-2.0
+// Copyright (c) 2019 Facebook
+#include <linux/sched.h>
+#include <linux/ptrace.h>
+#include <stdint.h>
+#include <stddef.h>
+#include <stdbool.h>
+#include <linux/bpf.h>
+#include "bpf_helpers.h"
+#define barrier() __asm__ __volatile__("": : :"memory")
+
+char _license[] SEC("license") = "GPL";
+
+SEC("socket")
+int while_true(volatile struct __sk_buff* skb)
+{
+	int i = 0;
+
+	while (true) {
+		if (skb->len)
+			i += 3;
+		else
+			i += 7;
+		if (i == 9)
+			break;
+		barrier();
+		if (i == 10)
+			break;
+		barrier();
+		if (i == 13)
+			break;
+		barrier();
+		if (i == 14)
+			break;
+	}
+	return i;
+}
-- 
2.20.0

Re: [PATCH bpf-next 2/2] selftests/bpf: add loop test 5

[Yonghong Song]

On 8/2/19 4:33 PM, Alexei Starovoitov wrote:
> Add a test with multiple exit conditions.
> It's not an infinite loop only when the verifier can properly track
> all math on variable 'i' through all possible ways of executing this loop.

Agreed with motivation of this test.

> 
> barrier()s are needed to disable llvm optimization that combines multiple
> branches into fewer branches.
> 
> Signed-off-by: Alexei Starovoitov <ast@kernel.org>
> ---
>   .../bpf/prog_tests/bpf_verif_scale.c          |  1 +
>   tools/testing/selftests/bpf/progs/loop5.c     | 37 +++++++++++++++++++
>   2 files changed, 38 insertions(+)
>   create mode 100644 tools/testing/selftests/bpf/progs/loop5.c
> 
> diff --git a/tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c b/tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c
> index 757e39540eda..29615a4a9362 100644
> --- a/tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c
> +++ b/tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c
> @@ -72,6 +72,7 @@ void test_bpf_verif_scale(void)
>   		{ "loop1.o", BPF_PROG_TYPE_RAW_TRACEPOINT },
>   		{ "loop2.o", BPF_PROG_TYPE_RAW_TRACEPOINT },
>   		{ "loop4.o", BPF_PROG_TYPE_RAW_TRACEPOINT }, > +		{ "loop5.o", BPF_PROG_TYPE_RAW_TRACEPOINT },

More like a BPF_PROG_TYPE_SCHED_CLS type although probably it does not 
matter as we did not attach it to anywhere?

>   
>   		/* partial unroll. 19k insn in a loop.
>   		 * Total program size 20.8k insn.
> diff --git a/tools/testing/selftests/bpf/progs/loop5.c b/tools/testing/selftests/bpf/progs/loop5.c
> new file mode 100644
> index 000000000000..9d9817efe208
> --- /dev/null
> +++ b/tools/testing/selftests/bpf/progs/loop5.c
> @@ -0,0 +1,37 @@
> +// SPDX-License-Identifier: GPL-2.0
> +// Copyright (c) 2019 Facebook
> +#include <linux/sched.h>
> +#include <linux/ptrace.h>

The above headers probably not needed.

> +#include <stdint.h>
> +#include <stddef.h>
> +#include <stdbool.h>
> +#include <linux/bpf.h>
> +#include "bpf_helpers.h"
> +#define barrier() __asm__ __volatile__("": : :"memory")
> +
> +char _license[] SEC("license") = "GPL";
> +
> +SEC("socket")
> +int while_true(volatile struct __sk_buff* skb)
> +{
> +	int i = 0;
> +
> +	while (true) {
> +		if (skb->len)
> +			i += 3;
> +		else
> +			i += 7;
> +		if (i == 9)
> +			break;
> +		barrier();
> +		if (i == 10)
> +			break;
> +		barrier();
> +		if (i == 13)
> +			break;
> +		barrier();
> +		if (i == 14)
> +			break;
> +	}
> +	return i;
> +}
> 

Re: [PATCH bpf-next 2/2] selftests/bpf: add loop test 5

[Alexei Starovoitov]

On Sun, Aug 04, 2019 at 05:45:23AM +0000, Yonghong Song wrote:
> 
> 
> On 8/2/19 4:33 PM, Alexei Starovoitov wrote:
> > Add a test with multiple exit conditions.
> > It's not an infinite loop only when the verifier can properly track
> > all math on variable 'i' through all possible ways of executing this loop.
> 
> Agreed with motivation of this test.
> 
> > 
> > barrier()s are needed to disable llvm optimization that combines multiple
> > branches into fewer branches.
> > 
> > Signed-off-by: Alexei Starovoitov <ast@kernel.org>
> > ---
> >   .../bpf/prog_tests/bpf_verif_scale.c          |  1 +
> >   tools/testing/selftests/bpf/progs/loop5.c     | 37 +++++++++++++++++++
> >   2 files changed, 38 insertions(+)
> >   create mode 100644 tools/testing/selftests/bpf/progs/loop5.c
> > 
> > diff --git a/tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c b/tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c
> > index 757e39540eda..29615a4a9362 100644
> > --- a/tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c
> > +++ b/tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c
> > @@ -72,6 +72,7 @@ void test_bpf_verif_scale(void)
> >   		{ "loop1.o", BPF_PROG_TYPE_RAW_TRACEPOINT },
> >   		{ "loop2.o", BPF_PROG_TYPE_RAW_TRACEPOINT },
> >   		{ "loop4.o", BPF_PROG_TYPE_RAW_TRACEPOINT }, > +		{ "loop5.o", BPF_PROG_TYPE_RAW_TRACEPOINT },
> 
> More like a BPF_PROG_TYPE_SCHED_CLS type although probably it does not 
> matter as we did not attach it to anywhere?

right. will fix.

> >   
> >   		/* partial unroll. 19k insn in a loop.
> >   		 * Total program size 20.8k insn.
> > diff --git a/tools/testing/selftests/bpf/progs/loop5.c b/tools/testing/selftests/bpf/progs/loop5.c
> > new file mode 100644
> > index 000000000000..9d9817efe208
> > --- /dev/null
> > +++ b/tools/testing/selftests/bpf/progs/loop5.c
> > @@ -0,0 +1,37 @@
> > +// SPDX-License-Identifier: GPL-2.0
> > +// Copyright (c) 2019 Facebook
> > +#include <linux/sched.h>
> > +#include <linux/ptrace.h>
> 
> The above headers probably not needed.

will fix