* [PATCH bpf-next 0/2] selftests/bpf: more loop tests
@ 2019-08-02 23:33 Alexei Starovoitov
2019-08-02 23:33 ` [PATCH bpf-next 1/2] selftests/bpf: add loop test 4 Alexei Starovoitov
2019-08-02 23:33 ` [PATCH bpf-next 2/2] selftests/bpf: add loop test 5 Alexei Starovoitov
0 siblings, 2 replies; 11+ messages in thread
From: Alexei Starovoitov @ 2019-08-02 23:33 UTC (permalink / raw)
To: davem; +Cc: daniel, netdev, bpf, kernel-team
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
^ permalink raw reply [flat|nested] 11+ messages in thread
* [PATCH bpf-next 1/2] selftests/bpf: add loop test 4
2019-08-02 23:33 [PATCH bpf-next 0/2] selftests/bpf: more loop tests Alexei Starovoitov
@ 2019-08-02 23:33 ` Alexei Starovoitov
2019-08-04 5:29 ` Yonghong Song
2019-08-05 19:45 ` Andrii Nakryiko
2019-08-02 23:33 ` [PATCH bpf-next 2/2] selftests/bpf: add loop test 5 Alexei Starovoitov
1 sibling, 2 replies; 11+ messages in thread
From: Alexei Starovoitov @ 2019-08-02 23:33 UTC (permalink / raw)
To: davem; +Cc: daniel, netdev, bpf, kernel-team
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
^ permalink raw reply related [flat|nested] 11+ messages in thread
* [PATCH bpf-next 2/2] selftests/bpf: add loop test 5
2019-08-02 23:33 [PATCH bpf-next 0/2] selftests/bpf: more loop tests Alexei Starovoitov
2019-08-02 23:33 ` [PATCH bpf-next 1/2] selftests/bpf: add loop test 4 Alexei Starovoitov
@ 2019-08-02 23:33 ` Alexei Starovoitov
2019-08-04 5:45 ` Yonghong Song
1 sibling, 1 reply; 11+ messages in thread
From: Alexei Starovoitov @ 2019-08-02 23:33 UTC (permalink / raw)
To: davem; +Cc: daniel, netdev, bpf, kernel-team
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
^ permalink raw reply related [flat|nested] 11+ messages in thread
* Re: [PATCH bpf-next 1/2] selftests/bpf: add loop test 4
2019-08-02 23:33 ` [PATCH bpf-next 1/2] selftests/bpf: add loop test 4 Alexei Starovoitov
@ 2019-08-04 5:29 ` Yonghong Song
2019-08-05 16:15 ` Alexei Starovoitov
2019-08-05 19:45 ` Andrii Nakryiko
1 sibling, 1 reply; 11+ messages in thread
From: Yonghong Song @ 2019-08-04 5:29 UTC (permalink / raw)
To: Alexei Starovoitov, davem; +Cc: daniel, netdev, bpf, Kernel Team
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;
> +}
>
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH bpf-next 2/2] selftests/bpf: add loop test 5
2019-08-02 23:33 ` [PATCH bpf-next 2/2] selftests/bpf: add loop test 5 Alexei Starovoitov
@ 2019-08-04 5:45 ` Yonghong Song
2019-08-05 16:16 ` Alexei Starovoitov
0 siblings, 1 reply; 11+ messages in thread
From: Yonghong Song @ 2019-08-04 5:45 UTC (permalink / raw)
To: Alexei Starovoitov, davem; +Cc: daniel, netdev, bpf, Kernel Team
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;
> +}
>
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH bpf-next 1/2] selftests/bpf: add loop test 4
2019-08-04 5:29 ` Yonghong Song
@ 2019-08-05 16:15 ` Alexei Starovoitov
0 siblings, 0 replies; 11+ messages in thread
From: Alexei Starovoitov @ 2019-08-05 16:15 UTC (permalink / raw)
To: Yonghong Song; +Cc: Alexei Starovoitov, davem, daniel, netdev, bpf, Kernel Team
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;
> > +}
> >
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH bpf-next 2/2] selftests/bpf: add loop test 5
2019-08-04 5:45 ` Yonghong Song
@ 2019-08-05 16:16 ` Alexei Starovoitov
0 siblings, 0 replies; 11+ messages in thread
From: Alexei Starovoitov @ 2019-08-05 16:16 UTC (permalink / raw)
To: Yonghong Song; +Cc: Alexei Starovoitov, davem, daniel, netdev, bpf, Kernel Team
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
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH bpf-next 1/2] selftests/bpf: add loop test 4
2019-08-02 23:33 ` [PATCH bpf-next 1/2] selftests/bpf: add loop test 4 Alexei Starovoitov
2019-08-04 5:29 ` Yonghong Song
@ 2019-08-05 19:45 ` Andrii Nakryiko
2019-08-05 20:04 ` Yonghong Song
1 sibling, 1 reply; 11+ messages in thread
From: Andrii Nakryiko @ 2019-08-05 19:45 UTC (permalink / raw)
To: Alexei Starovoitov
Cc: David S. Miller, Daniel Borkmann, Networking, bpf, Kernel Team
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
>
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH bpf-next 1/2] selftests/bpf: add loop test 4
2019-08-05 19:45 ` Andrii Nakryiko
@ 2019-08-05 20:04 ` Yonghong Song
2019-08-05 20:53 ` Alexei Starovoitov
0 siblings, 1 reply; 11+ messages in thread
From: Yonghong Song @ 2019-08-05 20:04 UTC (permalink / raw)
To: Andrii Nakryiko, Alexei Starovoitov
Cc: David S. Miller, Daniel Borkmann, Networking, bpf, Kernel Team
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
>>
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH bpf-next 1/2] selftests/bpf: add loop test 4
2019-08-05 20:04 ` Yonghong Song
@ 2019-08-05 20:53 ` Alexei Starovoitov
2019-08-05 21:37 ` Andrii Nakryiko
0 siblings, 1 reply; 11+ messages in thread
From: Alexei Starovoitov @ 2019-08-05 20:53 UTC (permalink / raw)
To: Yonghong Song, Andrii Nakryiko, Alexei Starovoitov
Cc: David S. Miller, Daniel Borkmann, Networking, bpf, Kernel Team
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.
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [PATCH bpf-next 1/2] selftests/bpf: add loop test 4
2019-08-05 20:53 ` Alexei Starovoitov
@ 2019-08-05 21:37 ` Andrii Nakryiko
0 siblings, 0 replies; 11+ messages in thread
From: Andrii Nakryiko @ 2019-08-05 21:37 UTC (permalink / raw)
To: Alexei Starovoitov
Cc: Yonghong Song, Alexei Starovoitov, David S. Miller,
Daniel Borkmann, Networking, bpf, Kernel Team
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>
^ permalink raw reply [flat|nested] 11+ messages in thread
end of thread, other threads:[~2019-08-05 21:38 UTC | newest]
Thread overview: 11+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2019-08-02 23:33 [PATCH bpf-next 0/2] selftests/bpf: more loop tests Alexei Starovoitov
2019-08-02 23:33 ` [PATCH bpf-next 1/2] selftests/bpf: add loop test 4 Alexei Starovoitov
2019-08-04 5:29 ` Yonghong Song
2019-08-05 16:15 ` Alexei Starovoitov
2019-08-05 19:45 ` Andrii Nakryiko
2019-08-05 20:04 ` Yonghong Song
2019-08-05 20:53 ` Alexei Starovoitov
2019-08-05 21:37 ` Andrii Nakryiko
2019-08-02 23:33 ` [PATCH bpf-next 2/2] selftests/bpf: add loop test 5 Alexei Starovoitov
2019-08-04 5:45 ` Yonghong Song
2019-08-05 16:16 ` Alexei Starovoitov
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).