[PATCH bpf 0/2] bpf: fix an incorrect branch elimination by verifier

[PATCH bpf 0/2] bpf: fix an incorrect branch elimination by verifier

[Yonghong Song]

Wenbo reported an issue in [1] where a checking of null
pointer is evaluated as always false. In this particular
case, the program type is tp_btf and the pointer to
compare is a PTR_TO_BTF_ID.

As an illustration of original issue, consider the following
example:
 struct bpf_fentry_test_t {
     struct bpf_fentry_test_t *a;
 };
 int BPF_PROG(test8, struct bpf_fentry_test_t *arg)
 {
     if (arg->a == 0)
         test8_result = 1;
     return 0;
 }
In the xlated byte code, "arg->a == 0" condition is evaluted
always false and "test8_result = 1" is removed.

This is not right. Patch #1 shows why this happens and how to
fix it in verifier. Patch #2 added two subtests in test_progs
to catch such cases.

 [1]: https://lore.kernel.org/bpf/79dbb7c0-449d-83eb-5f4f-7af0cc269168@fb.com/T/

Yonghong Song (2):
  bpf: fix an incorrect branch elimination by verifier
  bpf: add tests for PTR_TO_BTF_ID vs. null comparison

 kernel/bpf/verifier.c                         |  3 +--
 net/bpf/test_run.c                            | 19 +++++++++++++++-
 .../selftests/bpf/prog_tests/fentry_fexit.c   |  2 +-
 .../testing/selftests/bpf/progs/fentry_test.c | 22 +++++++++++++++++++
 .../testing/selftests/bpf/progs/fexit_test.c  | 22 +++++++++++++++++++
 5 files changed, 64 insertions(+), 4 deletions(-)

-- 
2.24.1

[PATCH bpf 1/2] bpf: fix an incorrect branch elimination by verifier

[Yonghong Song]

Wenbo reported an issue in [1] where a checking of null
pointer is evaluated as always false. In this particular
case, the program type is tp_btf and the pointer to
compare is a PTR_TO_BTF_ID.

The current verifier considers PTR_TO_BTF_ID always
reprents a non-null pointer, hence all PTR_TO_BTF_ID compares
to 0 will be evaluated as always not-equal, which resulted
in the branch elimination.

For example,
 struct bpf_fentry_test_t {
     struct bpf_fentry_test_t *a;
 };
 int BPF_PROG(test7, struct bpf_fentry_test_t *arg)
 {
     if (arg == 0)
         test7_result = 1;
     return 0;
 }
 int BPF_PROG(test8, struct bpf_fentry_test_t *arg)
 {
     if (arg->a == 0)
         test8_result = 1;
     return 0;
 }

In above bpf programs, both branch arg == 0 and arg->a == 0
are removed. This may not be what developer expected.

The bug is introduced by Commit cac616db39c2 ("bpf: Verifier
track null pointer branch_taken with JNE and JEQ"),
where PTR_TO_BTF_ID is considered to be non-null when evaluting
pointer vs. scalar comparison. This may be added
considering we have PTR_TO_BTF_ID_OR_NULL in the verifier
as well.

PTR_TO_BTF_ID_OR_NULL is added to explicitly requires
a non-NULL testing in selective cases. The current generic
pointer tracing framework in verifier always
assigns PTR_TO_BTF_ID so users does not need to
check NULL pointer at every pointer level like a->b->c->d.

We may not want to assign every PTR_TO_BTF_ID as
PTR_TO_BTF_ID_OR_NULL as this will require a null test
before pointer dereference which may cause inconvenience
for developers. But we could avoid branch elimination
to preserve original code intention.

This patch simply removed PTR_TO_BTD_ID from reg_type_not_null()
in verifier, which prevented the above branches from being eliminated.

 [1]: https://lore.kernel.org/bpf/79dbb7c0-449d-83eb-5f4f-7af0cc269168@fb.com/T/

Fixes: cac616db39c2 ("bpf: Verifier track null pointer branch_taken with JNE and JEQ")
Cc: Andrii Nakryiko <andriin@fb.com>
Cc: John Fastabend <john.fastabend@gmail.com>
Cc: Wenbo Zhang <ethercflow@gmail.com>
Signed-off-by: Yonghong Song <yhs@fb.com>
---
 kernel/bpf/verifier.c | 3 +--
 1 file changed, 1 insertion(+), 2 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 8911d0576399..94cead5a43e5 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -399,8 +399,7 @@ static bool reg_type_not_null(enum bpf_reg_type type)
 	return type == PTR_TO_SOCKET ||
 		type == PTR_TO_TCP_SOCK ||
 		type == PTR_TO_MAP_VALUE ||
-		type == PTR_TO_SOCK_COMMON ||
-	        type == PTR_TO_BTF_ID;
+		type == PTR_TO_SOCK_COMMON;
 }
 
 static bool reg_type_may_be_null(enum bpf_reg_type type)
-- 
2.24.1

[PATCH bpf 2/2] bpf: add tests for PTR_TO_BTF_ID vs. null comparison

[Yonghong Song]

Add two tests for PTR_TO_BTF_ID vs. null ptr comparison,
one for PTR_TO_BTF_ID in the ctx structure and the
other for PTR_TO_BTF_ID after one level pointer chasing.
In both cases, the test ensures condition is not
removed.

For example, for this test
 struct bpf_fentry_test_t {
     struct bpf_fentry_test_t *a;
 };
 int BPF_PROG(test7, struct bpf_fentry_test_t *arg)
 {
     if (arg == 0)
         test7_result = 1;
     return 0;
 }
Before the previous verifier change, we have xlated codes:
  int test7(long long unsigned int * ctx):
  ; int BPF_PROG(test7, struct bpf_fentry_test_t *arg)
     0: (79) r1 = *(u64 *)(r1 +0)
  ; int BPF_PROG(test7, struct bpf_fentry_test_t *arg)
     1: (b4) w0 = 0
     2: (95) exit
After the previous verifier change, we have:
  int test7(long long unsigned int * ctx):
  ; int BPF_PROG(test7, struct bpf_fentry_test_t *arg)
     0: (79) r1 = *(u64 *)(r1 +0)
  ; if (arg == 0)
     1: (55) if r1 != 0x0 goto pc+4
  ; test7_result = 1;
     2: (18) r1 = map[id:6][0]+48
     4: (b7) r2 = 1
     5: (7b) *(u64 *)(r1 +0) = r2
  ; int BPF_PROG(test7, struct bpf_fentry_test_t *arg)
     6: (b4) w0 = 0
     7: (95) exit

Cc: Andrii Nakryiko <andriin@fb.com>
Cc: John Fastabend <john.fastabend@gmail.com>
Cc: Wenbo Zhang <ethercflow@gmail.com>
Signed-off-by: Yonghong Song <yhs@fb.com>
---
 net/bpf/test_run.c                            | 19 +++++++++++++++-
 .../selftests/bpf/prog_tests/fentry_fexit.c   |  2 +-
 .../testing/selftests/bpf/progs/fentry_test.c | 22 +++++++++++++++++++
 .../testing/selftests/bpf/progs/fexit_test.c  | 22 +++++++++++++++++++
 4 files changed, 63 insertions(+), 2 deletions(-)

diff --git a/net/bpf/test_run.c b/net/bpf/test_run.c
index bfd4ccd80847..b03c469cd01f 100644
--- a/net/bpf/test_run.c
+++ b/net/bpf/test_run.c
@@ -147,6 +147,20 @@ int noinline bpf_fentry_test6(u64 a, void *b, short c, int d, void *e, u64 f)
 	return a + (long)b + c + d + (long)e + f;
 }
 
+struct bpf_fentry_test_t {
+	struct bpf_fentry_test_t *a;
+};
+
+int noinline bpf_fentry_test7(struct bpf_fentry_test_t *arg)
+{
+	return (long)arg;
+}
+
+int noinline bpf_fentry_test8(struct bpf_fentry_test_t *arg)
+{
+	return (long)arg->a;
+}
+
 int noinline bpf_modify_return_test(int a, int *b)
 {
 	*b += 1;
@@ -185,6 +199,7 @@ int bpf_prog_test_run_tracing(struct bpf_prog *prog,
 			      const union bpf_attr *kattr,
 			      union bpf_attr __user *uattr)
 {
+	struct bpf_fentry_test_t arg = {};
 	u16 side_effect = 0, ret = 0;
 	int b = 2, err = -EFAULT;
 	u32 retval = 0;
@@ -197,7 +212,9 @@ int bpf_prog_test_run_tracing(struct bpf_prog *prog,
 		    bpf_fentry_test3(4, 5, 6) != 15 ||
 		    bpf_fentry_test4((void *)7, 8, 9, 10) != 34 ||
 		    bpf_fentry_test5(11, (void *)12, 13, 14, 15) != 65 ||
-		    bpf_fentry_test6(16, (void *)17, 18, 19, (void *)20, 21) != 111)
+		    bpf_fentry_test6(16, (void *)17, 18, 19, (void *)20, 21) != 111 ||
+		    bpf_fentry_test7((struct bpf_fentry_test_t *)0) != 0 ||
+		    bpf_fentry_test8(&arg) != 0)
 			goto out;
 		break;
 	case BPF_MODIFY_RETURN:
diff --git a/tools/testing/selftests/bpf/prog_tests/fentry_fexit.c b/tools/testing/selftests/bpf/prog_tests/fentry_fexit.c
index 83493bd5745c..109d0345a2be 100644
--- a/tools/testing/selftests/bpf/prog_tests/fentry_fexit.c
+++ b/tools/testing/selftests/bpf/prog_tests/fentry_fexit.c
@@ -36,7 +36,7 @@ void test_fentry_fexit(void)
 	fentry_res = (__u64 *)fentry_skel->bss;
 	fexit_res = (__u64 *)fexit_skel->bss;
 	printf("%lld\n", fentry_skel->bss->test1_result);
-	for (i = 0; i < 6; i++) {
+	for (i = 0; i < 8; i++) {
 		CHECK(fentry_res[i] != 1, "result",
 		      "fentry_test%d failed err %lld\n", i + 1, fentry_res[i]);
 		CHECK(fexit_res[i] != 1, "result",
diff --git a/tools/testing/selftests/bpf/progs/fentry_test.c b/tools/testing/selftests/bpf/progs/fentry_test.c
index 9365b686f84b..5f645fdaba6f 100644
--- a/tools/testing/selftests/bpf/progs/fentry_test.c
+++ b/tools/testing/selftests/bpf/progs/fentry_test.c
@@ -55,3 +55,25 @@ int BPF_PROG(test6, __u64 a, void *b, short c, int d, void * e, __u64 f)
 		e == (void *)20 && f == 21;
 	return 0;
 }
+
+struct bpf_fentry_test_t {
+	struct bpf_fentry_test_t *a;
+};
+
+__u64 test7_result = 0;
+SEC("fentry/bpf_fentry_test7")
+int BPF_PROG(test7, struct bpf_fentry_test_t *arg)
+{
+	if (arg == 0)
+		test7_result = 1;
+	return 0;
+}
+
+__u64 test8_result = 0;
+SEC("fentry/bpf_fentry_test8")
+int BPF_PROG(test8, struct bpf_fentry_test_t *arg)
+{
+	if (arg->a == 0)
+		test8_result = 1;
+	return 0;
+}
diff --git a/tools/testing/selftests/bpf/progs/fexit_test.c b/tools/testing/selftests/bpf/progs/fexit_test.c
index bd1e17d8024c..0952affb22a6 100644
--- a/tools/testing/selftests/bpf/progs/fexit_test.c
+++ b/tools/testing/selftests/bpf/progs/fexit_test.c
@@ -56,3 +56,25 @@ int BPF_PROG(test6, __u64 a, void *b, short c, int d, void *e, __u64 f, int ret)
 		e == (void *)20 && f == 21 && ret == 111;
 	return 0;
 }
+
+struct bpf_fentry_test_t {
+	struct bpf_fentry_test *a;
+};
+
+__u64 test7_result = 0;
+SEC("fexit/bpf_fentry_test7")
+int BPF_PROG(test7, struct bpf_fentry_test_t *arg)
+{
+	if (arg == 0)
+		test7_result = 1;
+	return 0;
+}
+
+__u64 test8_result = 0;
+SEC("fexit/bpf_fentry_test8")
+int BPF_PROG(test8, struct bpf_fentry_test_t *arg)
+{
+	if (arg->a == 0)
+		test8_result = 1;
+	return 0;
+}
-- 
2.24.1

RE: [PATCH bpf 1/2] bpf: fix an incorrect branch elimination by verifier

[John Fastabend]

Yonghong Song wrote:
> Wenbo reported an issue in [1] where a checking of null
> pointer is evaluated as always false. In this particular
> case, the program type is tp_btf and the pointer to
> compare is a PTR_TO_BTF_ID.
> 
> The current verifier considers PTR_TO_BTF_ID always
> reprents a non-null pointer, hence all PTR_TO_BTF_ID compares
> to 0 will be evaluated as always not-equal, which resulted
> in the branch elimination.
> 
> For example,
>  struct bpf_fentry_test_t {
>      struct bpf_fentry_test_t *a;
>  };
>  int BPF_PROG(test7, struct bpf_fentry_test_t *arg)
>  {
>      if (arg == 0)
>          test7_result = 1;
>      return 0;
>  }
>  int BPF_PROG(test8, struct bpf_fentry_test_t *arg)
>  {
>      if (arg->a == 0)
>          test8_result = 1;
>      return 0;
>  }
> 
> In above bpf programs, both branch arg == 0 and arg->a == 0
> are removed. This may not be what developer expected.
> 
> The bug is introduced by Commit cac616db39c2 ("bpf: Verifier
> track null pointer branch_taken with JNE and JEQ"),
> where PTR_TO_BTF_ID is considered to be non-null when evaluting
> pointer vs. scalar comparison. This may be added
> considering we have PTR_TO_BTF_ID_OR_NULL in the verifier
> as well.
> 
> PTR_TO_BTF_ID_OR_NULL is added to explicitly requires
> a non-NULL testing in selective cases. The current generic
> pointer tracing framework in verifier always
> assigns PTR_TO_BTF_ID so users does not need to
> check NULL pointer at every pointer level like a->b->c->d.

Thanks for fixing this.

But, don't we really need to check for null? I'm trying to
understand how we can avoid the check. If b is NULL above
we will have a problem no?

Also, we probably shouldn't name the type PTR_TO_BTF_ID if
it can be NULL. How about renaming it in bpf-next then although
it will be code churn... Or just fix the comments? Probably
bpf-next content though. wdyt? In my opinion the comments and
type names are really misleading as it stands.

diff --git a/include/linux/bpf.h b/include/linux/bpf.h
index 3d2ade703a35..18051440f886 100644
--- a/include/linux/bpf.h
+++ b/include/linux/bpf.h
@@ -337,7 +337,7 @@ enum bpf_reg_type {
 	PTR_TO_TCP_SOCK_OR_NULL, /* reg points to struct tcp_sock or NULL */
 	PTR_TO_TP_BUFFER,	 /* reg points to a writable raw tp's buffer */
 	PTR_TO_XDP_SOCK,	 /* reg points to struct xdp_sock */
-	PTR_TO_BTF_ID,		 /* reg points to kernel struct */
+	PTR_TO_BTF_ID,		 /* reg points to kernel struct or NULL */
 	PTR_TO_BTF_ID_OR_NULL,	 /* reg points to kernel struct or NULL */
 	PTR_TO_MEM,		 /* reg points to valid memory region */
 	PTR_TO_MEM_OR_NULL,	 /* reg points to valid memory region or NULL */
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 7de98906ddf4..7412f9d2f0b5 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -500,7 +500,7 @@ static const char * const reg_type_str[] = {
 	[PTR_TO_TCP_SOCK_OR_NULL] = "tcp_sock_or_null",
 	[PTR_TO_TP_BUFFER]	= "tp_buffer",
 	[PTR_TO_XDP_SOCK]	= "xdp_sock",
-	[PTR_TO_BTF_ID]		= "ptr_",
+	[PTR_TO_BTF_ID]		= "ptr_or_null_",
 	[PTR_TO_BTF_ID_OR_NULL]	= "ptr_or_null_",
 	[PTR_TO_MEM]		= "mem",
 	[PTR_TO_MEM_OR_NULL]	= "mem_or_null",

> 
> We may not want to assign every PTR_TO_BTF_ID as
> PTR_TO_BTF_ID_OR_NULL as this will require a null test
> before pointer dereference which may cause inconvenience
> for developers. But we could avoid branch elimination
> to preserve original code intention.
> 
> This patch simply removed PTR_TO_BTD_ID from reg_type_not_null()
> in verifier, which prevented the above branches from being eliminated.
> 
>  [1]: https://lore.kernel.org/bpf/79dbb7c0-449d-83eb-5f4f-7af0cc269168@fb.com/T/
> 
> Fixes: cac616db39c2 ("bpf: Verifier track null pointer branch_taken with JNE and JEQ")
> Cc: Andrii Nakryiko <andriin@fb.com>
> Cc: John Fastabend <john.fastabend@gmail.com>
> Cc: Wenbo Zhang <ethercflow@gmail.com>
> Signed-off-by: Yonghong Song <yhs@fb.com>
> ---
>  kernel/bpf/verifier.c | 3 +--
>  1 file changed, 1 insertion(+), 2 deletions(-)
> 
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 8911d0576399..94cead5a43e5 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -399,8 +399,7 @@ static bool reg_type_not_null(enum bpf_reg_type type)
>  	return type == PTR_TO_SOCKET ||
>  		type == PTR_TO_TCP_SOCK ||
>  		type == PTR_TO_MAP_VALUE ||
> -		type == PTR_TO_SOCK_COMMON ||
> -	        type == PTR_TO_BTF_ID;
> +		type == PTR_TO_SOCK_COMMON;
>  }
>  
>  static bool reg_type_may_be_null(enum bpf_reg_type type)
> -- 
> 2.24.1
> 

Re: [PATCH bpf 1/2] bpf: fix an incorrect branch elimination by verifier

[Yonghong Song]

On 6/30/20 10:51 AM, John Fastabend wrote:
> Yonghong Song wrote:
>> Wenbo reported an issue in [1] where a checking of null
>> pointer is evaluated as always false. In this particular
>> case, the program type is tp_btf and the pointer to
>> compare is a PTR_TO_BTF_ID.
>>
>> The current verifier considers PTR_TO_BTF_ID always
>> reprents a non-null pointer, hence all PTR_TO_BTF_ID compares
>> to 0 will be evaluated as always not-equal, which resulted
>> in the branch elimination.
>>
>> For example,
>>   struct bpf_fentry_test_t {
>>       struct bpf_fentry_test_t *a;
>>   };
>>   int BPF_PROG(test7, struct bpf_fentry_test_t *arg)
>>   {
>>       if (arg == 0)
>>           test7_result = 1;
>>       return 0;
>>   }
>>   int BPF_PROG(test8, struct bpf_fentry_test_t *arg)
>>   {
>>       if (arg->a == 0)
>>           test8_result = 1;
>>       return 0;
>>   }
>>
>> In above bpf programs, both branch arg == 0 and arg->a == 0
>> are removed. This may not be what developer expected.
>>
>> The bug is introduced by Commit cac616db39c2 ("bpf: Verifier
>> track null pointer branch_taken with JNE and JEQ"),
>> where PTR_TO_BTF_ID is considered to be non-null when evaluting
>> pointer vs. scalar comparison. This may be added
>> considering we have PTR_TO_BTF_ID_OR_NULL in the verifier
>> as well.
>>
>> PTR_TO_BTF_ID_OR_NULL is added to explicitly requires
>> a non-NULL testing in selective cases. The current generic
>> pointer tracing framework in verifier always
>> assigns PTR_TO_BTF_ID so users does not need to
>> check NULL pointer at every pointer level like a->b->c->d.
> 
> Thanks for fixing this.
> 
> But, don't we really need to check for null? I'm trying to
> understand how we can avoid the check. If b is NULL above
> we will have a problem no?

It depends with particular data structure.
If users are sure once pointer 'a' is valid and a->b, a->b->c, a->b->c
are all valid pointers, user may just write a->b->c->d. this happens
to some bcc scripts. So non-null pointer is checked.

But if user thinks a->b->c is null, he may write
    type *p = a->b->c;
    if (p)
        p->d;

Or user just takes advantage of kernel bpf guarded exception handling 
and do a->b->c->d even if a->b->c could be null.
if the result is 0, it means a->b->c is null or major fault,
otherwise it is not 0.

> 
> Also, we probably shouldn't name the type PTR_TO_BTF_ID if
> it can be NULL. How about renaming it in bpf-next then although
> it will be code churn... Or just fix the comments? Probably
> bpf-next content though. wdyt? In my opinion the comments and
> type names are really misleading as it stands.

So PTR_TO_BTF_ID actually means it may be null but not checking
is enforced and pointer tracing is always allowed.
PTR_TO_BTF_ID_OR_NULL means it may be null and checking against
NULL is needed to allow further pointer tracing.

To avoid code churn, we can add these comments in bpf-next.

> 
> diff --git a/include/linux/bpf.h b/include/linux/bpf.h
> index 3d2ade703a35..18051440f886 100644
> --- a/include/linux/bpf.h
> +++ b/include/linux/bpf.h
> @@ -337,7 +337,7 @@ enum bpf_reg_type {
>   	PTR_TO_TCP_SOCK_OR_NULL, /* reg points to struct tcp_sock or NULL */
>   	PTR_TO_TP_BUFFER,	 /* reg points to a writable raw tp's buffer */
>   	PTR_TO_XDP_SOCK,	 /* reg points to struct xdp_sock */
> -	PTR_TO_BTF_ID,		 /* reg points to kernel struct */
> +	PTR_TO_BTF_ID,		 /* reg points to kernel struct or NULL */
>   	PTR_TO_BTF_ID_OR_NULL,	 /* reg points to kernel struct or NULL */
>   	PTR_TO_MEM,		 /* reg points to valid memory region */
>   	PTR_TO_MEM_OR_NULL,	 /* reg points to valid memory region or NULL */
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 7de98906ddf4..7412f9d2f0b5 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -500,7 +500,7 @@ static const char * const reg_type_str[] = {
>   	[PTR_TO_TCP_SOCK_OR_NULL] = "tcp_sock_or_null",
>   	[PTR_TO_TP_BUFFER]	= "tp_buffer",
>   	[PTR_TO_XDP_SOCK]	= "xdp_sock",
> -	[PTR_TO_BTF_ID]		= "ptr_",
> +	[PTR_TO_BTF_ID]		= "ptr_or_null_",
>   	[PTR_TO_BTF_ID_OR_NULL]	= "ptr_or_null_",
>   	[PTR_TO_MEM]		= "mem",
>   	[PTR_TO_MEM_OR_NULL]	= "mem_or_null",
> 
>>
>> We may not want to assign every PTR_TO_BTF_ID as
>> PTR_TO_BTF_ID_OR_NULL as this will require a null test
>> before pointer dereference which may cause inconvenience
>> for developers. But we could avoid branch elimination
>> to preserve original code intention.
>>
>> This patch simply removed PTR_TO_BTD_ID from reg_type_not_null()
>> in verifier, which prevented the above branches from being eliminated.
>>
>>   [1]: https://lore.kernel.org/bpf/79dbb7c0-449d-83eb-5f4f-7af0cc269168@fb.com/T/
>>
>> Fixes: cac616db39c2 ("bpf: Verifier track null pointer branch_taken with JNE and JEQ")
>> Cc: Andrii Nakryiko <andriin@fb.com>
>> Cc: John Fastabend <john.fastabend@gmail.com>
>> Cc: Wenbo Zhang <ethercflow@gmail.com>
>> Signed-off-by: Yonghong Song <yhs@fb.com>
>> ---
>>   kernel/bpf/verifier.c | 3 +--
>>   1 file changed, 1 insertion(+), 2 deletions(-)
>>
>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>> index 8911d0576399..94cead5a43e5 100644
>> --- a/kernel/bpf/verifier.c
>> +++ b/kernel/bpf/verifier.c
>> @@ -399,8 +399,7 @@ static bool reg_type_not_null(enum bpf_reg_type type)
>>   	return type == PTR_TO_SOCKET ||
>>   		type == PTR_TO_TCP_SOCK ||
>>   		type == PTR_TO_MAP_VALUE ||
>> -		type == PTR_TO_SOCK_COMMON ||
>> -	        type == PTR_TO_BTF_ID;
>> +		type == PTR_TO_SOCK_COMMON;
>>   }
>>   
>>   static bool reg_type_may_be_null(enum bpf_reg_type type)
>> -- 
>> 2.24.1
>>

Re: [PATCH bpf 1/2] bpf: fix an incorrect branch elimination by verifier

[John Fastabend]

Yonghong Song wrote:
> 
> 
> On 6/30/20 10:51 AM, John Fastabend wrote:
> > Yonghong Song wrote:
> >> Wenbo reported an issue in [1] where a checking of null
> >> pointer is evaluated as always false. In this particular
> >> case, the program type is tp_btf and the pointer to
> >> compare is a PTR_TO_BTF_ID.
> >>
> >> The current verifier considers PTR_TO_BTF_ID always
> >> reprents a non-null pointer, hence all PTR_TO_BTF_ID compares
> >> to 0 will be evaluated as always not-equal, which resulted
> >> in the branch elimination.
> >>
> >> For example,
> >>   struct bpf_fentry_test_t {
> >>       struct bpf_fentry_test_t *a;
> >>   };
> >>   int BPF_PROG(test7, struct bpf_fentry_test_t *arg)
> >>   {
> >>       if (arg == 0)
> >>           test7_result = 1;
> >>       return 0;
> >>   }
> >>   int BPF_PROG(test8, struct bpf_fentry_test_t *arg)
> >>   {
> >>       if (arg->a == 0)
> >>           test8_result = 1;
> >>       return 0;
> >>   }
> >>
> >> In above bpf programs, both branch arg == 0 and arg->a == 0
> >> are removed. This may not be what developer expected.
> >>
> >> The bug is introduced by Commit cac616db39c2 ("bpf: Verifier
> >> track null pointer branch_taken with JNE and JEQ"),
> >> where PTR_TO_BTF_ID is considered to be non-null when evaluting
> >> pointer vs. scalar comparison. This may be added
> >> considering we have PTR_TO_BTF_ID_OR_NULL in the verifier
> >> as well.
> >>
> >> PTR_TO_BTF_ID_OR_NULL is added to explicitly requires
> >> a non-NULL testing in selective cases. The current generic
> >> pointer tracing framework in verifier always
> >> assigns PTR_TO_BTF_ID so users does not need to
> >> check NULL pointer at every pointer level like a->b->c->d.
> > 
> > Thanks for fixing this.
> > 
> > But, don't we really need to check for null? I'm trying to
> > understand how we can avoid the check. If b is NULL above
> > we will have a problem no?
> 
> It depends with particular data structure.
> If users are sure once pointer 'a' is valid and a->b, a->b->c, a->b->c
> are all valid pointers, user may just write a->b->c->d. this happens
> to some bcc scripts. So non-null pointer is checked.
> 
> But if user thinks a->b->c is null, he may write
>     type *p = a->b->c;
>     if (p)
>         p->d;
> 
> Or user just takes advantage of kernel bpf guarded exception handling 
> and do a->b->c->d even if a->b->c could be null.
> if the result is 0, it means a->b->c is null or major fault,
> otherwise it is not 0.

OK.

> 
> > 
> > Also, we probably shouldn't name the type PTR_TO_BTF_ID if
> > it can be NULL. How about renaming it in bpf-next then although
> > it will be code churn... Or just fix the comments? Probably
> > bpf-next content though. wdyt? In my opinion the comments and
> > type names are really misleading as it stands.
> 
> So PTR_TO_BTF_ID actually means it may be null but not checking
> is enforced and pointer tracing is always allowed.
> PTR_TO_BTF_ID_OR_NULL means it may be null and checking against
> NULL is needed to allow further pointer tracing.
> 
> To avoid code churn, we can add these comments in bpf-next.

Agreed code churn would be not worth changing type but I'll send
some patches for the comment changes.

> 
> > 
> > diff --git a/include/linux/bpf.h b/include/linux/bpf.h
> > index 3d2ade703a35..18051440f886 100644
> > --- a/include/linux/bpf.h
> > +++ b/include/linux/bpf.h
> > @@ -337,7 +337,7 @@ enum bpf_reg_type {
> >   	PTR_TO_TCP_SOCK_OR_NULL, /* reg points to struct tcp_sock or NULL */
> >   	PTR_TO_TP_BUFFER,	 /* reg points to a writable raw tp's buffer */
> >   	PTR_TO_XDP_SOCK,	 /* reg points to struct xdp_sock */
> > -	PTR_TO_BTF_ID,		 /* reg points to kernel struct */
> > +	PTR_TO_BTF_ID,		 /* reg points to kernel struct or NULL */
> >   	PTR_TO_BTF_ID_OR_NULL,	 /* reg points to kernel struct or NULL */
> >   	PTR_TO_MEM,		 /* reg points to valid memory region */
> >   	PTR_TO_MEM_OR_NULL,	 /* reg points to valid memory region or NULL */
> > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > index 7de98906ddf4..7412f9d2f0b5 100644
> > --- a/kernel/bpf/verifier.c
> > +++ b/kernel/bpf/verifier.c
> > @@ -500,7 +500,7 @@ static const char * const reg_type_str[] = {
> >   	[PTR_TO_TCP_SOCK_OR_NULL] = "tcp_sock_or_null",
> >   	[PTR_TO_TP_BUFFER]	= "tp_buffer",
> >   	[PTR_TO_XDP_SOCK]	= "xdp_sock",
> > -	[PTR_TO_BTF_ID]		= "ptr_",
> > +	[PTR_TO_BTF_ID]		= "ptr_or_null_",
> >   	[PTR_TO_BTF_ID_OR_NULL]	= "ptr_or_null_",
> >   	[PTR_TO_MEM]		= "mem",
> >   	[PTR_TO_MEM_OR_NULL]	= "mem_or_null",
> > 
> >>
> >> We may not want to assign every PTR_TO_BTF_ID as
> >> PTR_TO_BTF_ID_OR_NULL as this will require a null test
> >> before pointer dereference which may cause inconvenience
> >> for developers. But we could avoid branch elimination
> >> to preserve original code intention.
> >>
> >> This patch simply removed PTR_TO_BTD_ID from reg_type_not_null()
> >> in verifier, which prevented the above branches from being eliminated.
> >>
> >>   [1]: https://lore.kernel.org/bpf/79dbb7c0-449d-83eb-5f4f-7af0cc269168@fb.com/T/
> >>
> >> Fixes: cac616db39c2 ("bpf: Verifier track null pointer branch_taken with JNE and JEQ")

I added the BTF_ID in v2 of those patches :/ too bad. Thanks again for catching
it.

> >> Cc: Andrii Nakryiko <andriin@fb.com>
> >> Cc: John Fastabend <john.fastabend@gmail.com>
> >> Cc: Wenbo Zhang <ethercflow@gmail.com>
> >> Signed-off-by: Yonghong Song <yhs@fb.com>
> >> ---

Acked-by: John Fastabend <john.fastabend@gmail.com>

> >>   kernel/bpf/verifier.c | 3 +--
> >>   1 file changed, 1 insertion(+), 2 deletions(-)
> >>
> >> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> >> index 8911d0576399..94cead5a43e5 100644
> >> --- a/kernel/bpf/verifier.c
> >> +++ b/kernel/bpf/verifier.c
> >> @@ -399,8 +399,7 @@ static bool reg_type_not_null(enum bpf_reg_type type)
> >>   	return type == PTR_TO_SOCKET ||
> >>   		type == PTR_TO_TCP_SOCK ||
> >>   		type == PTR_TO_MAP_VALUE ||
> >> -		type == PTR_TO_SOCK_COMMON ||
> >> -	        type == PTR_TO_BTF_ID;
> >> +		type == PTR_TO_SOCK_COMMON;
> >>   }
> >>   
> >>   static bool reg_type_may_be_null(enum bpf_reg_type type)
> >> -- 
> >> 2.24.1
> >>

RE: [PATCH bpf 2/2] bpf: add tests for PTR_TO_BTF_ID vs. null comparison

[John Fastabend]

Yonghong Song wrote:
> Add two tests for PTR_TO_BTF_ID vs. null ptr comparison,
> one for PTR_TO_BTF_ID in the ctx structure and the
> other for PTR_TO_BTF_ID after one level pointer chasing.
> In both cases, the test ensures condition is not
> removed.
> 
> For example, for this test
>  struct bpf_fentry_test_t {
>      struct bpf_fentry_test_t *a;
>  };
>  int BPF_PROG(test7, struct bpf_fentry_test_t *arg)
>  {
>      if (arg == 0)
>          test7_result = 1;
>      return 0;
>  }
> Before the previous verifier change, we have xlated codes:
>   int test7(long long unsigned int * ctx):
>   ; int BPF_PROG(test7, struct bpf_fentry_test_t *arg)
>      0: (79) r1 = *(u64 *)(r1 +0)
>   ; int BPF_PROG(test7, struct bpf_fentry_test_t *arg)
>      1: (b4) w0 = 0
>      2: (95) exit
> After the previous verifier change, we have:
>   int test7(long long unsigned int * ctx):
>   ; int BPF_PROG(test7, struct bpf_fentry_test_t *arg)
>      0: (79) r1 = *(u64 *)(r1 +0)
>   ; if (arg == 0)
>      1: (55) if r1 != 0x0 goto pc+4
>   ; test7_result = 1;
>      2: (18) r1 = map[id:6][0]+48
>      4: (b7) r2 = 1
>      5: (7b) *(u64 *)(r1 +0) = r2
>   ; int BPF_PROG(test7, struct bpf_fentry_test_t *arg)
>      6: (b4) w0 = 0
>      7: (95) exit
> 
> Cc: Andrii Nakryiko <andriin@fb.com>
> Cc: John Fastabend <john.fastabend@gmail.com>
> Cc: Wenbo Zhang <ethercflow@gmail.com>
> Signed-off-by: Yonghong Song <yhs@fb.com>
> ---

Thanks.

Acked-by: John Fastabend <john.fastabend@gmail.com>

Re: [PATCH bpf 1/2] bpf: fix an incorrect branch elimination by verifier

[Alexei Starovoitov]

On Tue, Jun 30, 2020 at 11:36 AM John Fastabend
<john.fastabend@gmail.com> wrote:
> > >
> > > Also, we probably shouldn't name the type PTR_TO_BTF_ID if
> > > it can be NULL. How about renaming it in bpf-next then although
> > > it will be code churn... Or just fix the comments? Probably
> > > bpf-next content though. wdyt? In my opinion the comments and
> > > type names are really misleading as it stands.
> >
> > So PTR_TO_BTF_ID actually means it may be null but not checking
> > is enforced and pointer tracing is always allowed.
> > PTR_TO_BTF_ID_OR_NULL means it may be null and checking against
> > NULL is needed to allow further pointer tracing.
> >
> > To avoid code churn, we can add these comments in bpf-next.
>
> Agreed code churn would be not worth changing type but I'll send
> some patches for the comment changes.

+1
I think for bpf tree the minimal fix is better.
So I've applied this set.
A follow up to bpf-next after bpf->net->linus->net-next->bpf-next would
be really good.
We'll make sure that all trees converge soon.

Re: [PATCH bpf 1/2] bpf: fix an incorrect branch elimination by verifier

[Andrii Nakryiko]

On Tue, Jun 30, 2020 at 11:46 AM Yonghong Song <yhs@fb.com> wrote:
>
> Wenbo reported an issue in [1] where a checking of null
> pointer is evaluated as always false. In this particular
> case, the program type is tp_btf and the pointer to
> compare is a PTR_TO_BTF_ID.
>
> The current verifier considers PTR_TO_BTF_ID always
> reprents a non-null pointer, hence all PTR_TO_BTF_ID compares
> to 0 will be evaluated as always not-equal, which resulted
> in the branch elimination.
>
> For example,
>  struct bpf_fentry_test_t {
>      struct bpf_fentry_test_t *a;
>  };
>  int BPF_PROG(test7, struct bpf_fentry_test_t *arg)
>  {
>      if (arg == 0)
>          test7_result = 1;
>      return 0;
>  }
>  int BPF_PROG(test8, struct bpf_fentry_test_t *arg)
>  {
>      if (arg->a == 0)
>          test8_result = 1;
>      return 0;
>  }
>
> In above bpf programs, both branch arg == 0 and arg->a == 0
> are removed. This may not be what developer expected.
>
> The bug is introduced by Commit cac616db39c2 ("bpf: Verifier
> track null pointer branch_taken with JNE and JEQ"),
> where PTR_TO_BTF_ID is considered to be non-null when evaluting
> pointer vs. scalar comparison. This may be added
> considering we have PTR_TO_BTF_ID_OR_NULL in the verifier
> as well.
>
> PTR_TO_BTF_ID_OR_NULL is added to explicitly requires
> a non-NULL testing in selective cases. The current generic
> pointer tracing framework in verifier always
> assigns PTR_TO_BTF_ID so users does not need to
> check NULL pointer at every pointer level like a->b->c->d.
>
> We may not want to assign every PTR_TO_BTF_ID as
> PTR_TO_BTF_ID_OR_NULL as this will require a null test
> before pointer dereference which may cause inconvenience
> for developers. But we could avoid branch elimination
> to preserve original code intention.
>
> This patch simply removed PTR_TO_BTD_ID from reg_type_not_null()
> in verifier, which prevented the above branches from being eliminated.
>
>  [1]: https://lore.kernel.org/bpf/79dbb7c0-449d-83eb-5f4f-7af0cc269168@fb.com/T/
>
> Fixes: cac616db39c2 ("bpf: Verifier track null pointer branch_taken with JNE and JEQ")
> Cc: Andrii Nakryiko <andriin@fb.com>
> Cc: John Fastabend <john.fastabend@gmail.com>
> Cc: Wenbo Zhang <ethercflow@gmail.com>
> Signed-off-by: Yonghong Song <yhs@fb.com>
> ---

You missed Reported-by: tag, please add.

Otherwise lgtm, thanks for fixing!

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

>  kernel/bpf/verifier.c | 3 +--
>  1 file changed, 1 insertion(+), 2 deletions(-)
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 8911d0576399..94cead5a43e5 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -399,8 +399,7 @@ static bool reg_type_not_null(enum bpf_reg_type type)
>         return type == PTR_TO_SOCKET ||
>                 type == PTR_TO_TCP_SOCK ||
>                 type == PTR_TO_MAP_VALUE ||
> -               type == PTR_TO_SOCK_COMMON ||
> -               type == PTR_TO_BTF_ID;
> +               type == PTR_TO_SOCK_COMMON;
>  }
>
>  static bool reg_type_may_be_null(enum bpf_reg_type type)
> --
> 2.24.1
>

Re: [PATCH bpf 1/2] bpf: fix an incorrect branch elimination by verifier

[Andrii Nakryiko]

On Tue, Jun 30, 2020 at 12:09 PM John Fastabend
<john.fastabend@gmail.com> wrote:
>
> Yonghong Song wrote:
> > Wenbo reported an issue in [1] where a checking of null
> > pointer is evaluated as always false. In this particular
> > case, the program type is tp_btf and the pointer to
> > compare is a PTR_TO_BTF_ID.
> >
> > The current verifier considers PTR_TO_BTF_ID always
> > reprents a non-null pointer, hence all PTR_TO_BTF_ID compares
> > to 0 will be evaluated as always not-equal, which resulted
> > in the branch elimination.
> >
> > For example,
> >  struct bpf_fentry_test_t {
> >      struct bpf_fentry_test_t *a;
> >  };
> >  int BPF_PROG(test7, struct bpf_fentry_test_t *arg)
> >  {
> >      if (arg == 0)
> >          test7_result = 1;
> >      return 0;
> >  }
> >  int BPF_PROG(test8, struct bpf_fentry_test_t *arg)
> >  {
> >      if (arg->a == 0)
> >          test8_result = 1;
> >      return 0;
> >  }
> >
> > In above bpf programs, both branch arg == 0 and arg->a == 0
> > are removed. This may not be what developer expected.
> >
> > The bug is introduced by Commit cac616db39c2 ("bpf: Verifier
> > track null pointer branch_taken with JNE and JEQ"),
> > where PTR_TO_BTF_ID is considered to be non-null when evaluting
> > pointer vs. scalar comparison. This may be added
> > considering we have PTR_TO_BTF_ID_OR_NULL in the verifier
> > as well.
> >
> > PTR_TO_BTF_ID_OR_NULL is added to explicitly requires
> > a non-NULL testing in selective cases. The current generic
> > pointer tracing framework in verifier always
> > assigns PTR_TO_BTF_ID so users does not need to
> > check NULL pointer at every pointer level like a->b->c->d.
>
> Thanks for fixing this.
>
> But, don't we really need to check for null? I'm trying to
> understand how we can avoid the check. If b is NULL above
> we will have a problem no?

BPF JIT installs an exception handler for each direct memory access,
so that if it turns out to be NULL, it will be caught and 0 will be
assigned to the target register and BPF program will continue
execution. In that sense, it simulates bpf_probe_read() behavior and
significantly improves usability.

>
> Also, we probably shouldn't name the type PTR_TO_BTF_ID if
> it can be NULL. How about renaming it in bpf-next then although
> it will be code churn... Or just fix the comments? Probably
> bpf-next content though. wdyt? In my opinion the comments and
> type names are really misleading as it stands.
>

[...]

Re: [PATCH bpf 2/2] bpf: add tests for PTR_TO_BTF_ID vs. null comparison

[Andrii Nakryiko]

On Tue, Jun 30, 2020 at 11:46 AM Yonghong Song <yhs@fb.com> wrote:
>
> Add two tests for PTR_TO_BTF_ID vs. null ptr comparison,
> one for PTR_TO_BTF_ID in the ctx structure and the
> other for PTR_TO_BTF_ID after one level pointer chasing.
> In both cases, the test ensures condition is not
> removed.
>
> For example, for this test
>  struct bpf_fentry_test_t {
>      struct bpf_fentry_test_t *a;
>  };
>  int BPF_PROG(test7, struct bpf_fentry_test_t *arg)
>  {
>      if (arg == 0)
>          test7_result = 1;
>      return 0;
>  }
> Before the previous verifier change, we have xlated codes:
>   int test7(long long unsigned int * ctx):
>   ; int BPF_PROG(test7, struct bpf_fentry_test_t *arg)
>      0: (79) r1 = *(u64 *)(r1 +0)
>   ; int BPF_PROG(test7, struct bpf_fentry_test_t *arg)
>      1: (b4) w0 = 0
>      2: (95) exit
> After the previous verifier change, we have:
>   int test7(long long unsigned int * ctx):
>   ; int BPF_PROG(test7, struct bpf_fentry_test_t *arg)
>      0: (79) r1 = *(u64 *)(r1 +0)
>   ; if (arg == 0)
>      1: (55) if r1 != 0x0 goto pc+4
>   ; test7_result = 1;
>      2: (18) r1 = map[id:6][0]+48
>      4: (b7) r2 = 1
>      5: (7b) *(u64 *)(r1 +0) = r2
>   ; int BPF_PROG(test7, struct bpf_fentry_test_t *arg)
>      6: (b4) w0 = 0
>      7: (95) exit
>
> Cc: Andrii Nakryiko <andriin@fb.com>
> Cc: John Fastabend <john.fastabend@gmail.com>
> Cc: Wenbo Zhang <ethercflow@gmail.com>
> Signed-off-by: Yonghong Song <yhs@fb.com>
> ---

LGTM, two nits below.

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

>  net/bpf/test_run.c                            | 19 +++++++++++++++-
>  .../selftests/bpf/prog_tests/fentry_fexit.c   |  2 +-
>  .../testing/selftests/bpf/progs/fentry_test.c | 22 +++++++++++++++++++
>  .../testing/selftests/bpf/progs/fexit_test.c  | 22 +++++++++++++++++++
>  4 files changed, 63 insertions(+), 2 deletions(-)
>

[...]

> diff --git a/tools/testing/selftests/bpf/progs/fentry_test.c b/tools/testing/selftests/bpf/progs/fentry_test.c
> index 9365b686f84b..5f645fdaba6f 100644
> --- a/tools/testing/selftests/bpf/progs/fentry_test.c
> +++ b/tools/testing/selftests/bpf/progs/fentry_test.c
> @@ -55,3 +55,25 @@ int BPF_PROG(test6, __u64 a, void *b, short c, int d, void * e, __u64 f)
>                 e == (void *)20 && f == 21;
>         return 0;
>  }
> +
> +struct bpf_fentry_test_t {
> +       struct bpf_fentry_test_t *a;
> +};

nit: __attribute__((preserve_access_index)) ?

> +
> +__u64 test7_result = 0;
> +SEC("fentry/bpf_fentry_test7")
> +int BPF_PROG(test7, struct bpf_fentry_test_t *arg)
> +{
> +       if (arg == 0)
> +               test7_result = 1;
> +       return 0;
> +}
> +
> +__u64 test8_result = 0;
> +SEC("fentry/bpf_fentry_test8")
> +int BPF_PROG(test8, struct bpf_fentry_test_t *arg)
> +{
> +       if (arg->a == 0)
> +               test8_result = 1;
> +       return 0;
> +}
> diff --git a/tools/testing/selftests/bpf/progs/fexit_test.c b/tools/testing/selftests/bpf/progs/fexit_test.c
> index bd1e17d8024c..0952affb22a6 100644
> --- a/tools/testing/selftests/bpf/progs/fexit_test.c
> +++ b/tools/testing/selftests/bpf/progs/fexit_test.c
> @@ -56,3 +56,25 @@ int BPF_PROG(test6, __u64 a, void *b, short c, int d, void *e, __u64 f, int ret)
>                 e == (void *)20 && f == 21 && ret == 111;
>         return 0;
>  }
> +
> +struct bpf_fentry_test_t {
> +       struct bpf_fentry_test *a;
> +};

same nit

> +
> +__u64 test7_result = 0;
> +SEC("fexit/bpf_fentry_test7")
> +int BPF_PROG(test7, struct bpf_fentry_test_t *arg)
> +{
> +       if (arg == 0)
> +               test7_result = 1;
> +       return 0;
> +}
> +
> +__u64 test8_result = 0;
> +SEC("fexit/bpf_fentry_test8")
> +int BPF_PROG(test8, struct bpf_fentry_test_t *arg)
> +{
> +       if (arg->a == 0)
> +               test8_result = 1;
> +       return 0;
> +}
> --
> 2.24.1
>

Re: [PATCH bpf 2/2] bpf: add tests for PTR_TO_BTF_ID vs. null comparison

[Yonghong Song]

On 6/30/20 12:23 PM, Andrii Nakryiko wrote:
> On Tue, Jun 30, 2020 at 11:46 AM Yonghong Song <yhs@fb.com> wrote:
>>
>> Add two tests for PTR_TO_BTF_ID vs. null ptr comparison,
>> one for PTR_TO_BTF_ID in the ctx structure and the
>> other for PTR_TO_BTF_ID after one level pointer chasing.
>> In both cases, the test ensures condition is not
>> removed.
>>
>> For example, for this test
>>   struct bpf_fentry_test_t {
>>       struct bpf_fentry_test_t *a;
>>   };
>>   int BPF_PROG(test7, struct bpf_fentry_test_t *arg)
>>   {
>>       if (arg == 0)
>>           test7_result = 1;
>>       return 0;
>>   }
>> Before the previous verifier change, we have xlated codes:
>>    int test7(long long unsigned int * ctx):
>>    ; int BPF_PROG(test7, struct bpf_fentry_test_t *arg)
>>       0: (79) r1 = *(u64 *)(r1 +0)
>>    ; int BPF_PROG(test7, struct bpf_fentry_test_t *arg)
>>       1: (b4) w0 = 0
>>       2: (95) exit
>> After the previous verifier change, we have:
>>    int test7(long long unsigned int * ctx):
>>    ; int BPF_PROG(test7, struct bpf_fentry_test_t *arg)
>>       0: (79) r1 = *(u64 *)(r1 +0)
>>    ; if (arg == 0)
>>       1: (55) if r1 != 0x0 goto pc+4
>>    ; test7_result = 1;
>>       2: (18) r1 = map[id:6][0]+48
>>       4: (b7) r2 = 1
>>       5: (7b) *(u64 *)(r1 +0) = r2
>>    ; int BPF_PROG(test7, struct bpf_fentry_test_t *arg)
>>       6: (b4) w0 = 0
>>       7: (95) exit
>>
>> Cc: Andrii Nakryiko <andriin@fb.com>
>> Cc: John Fastabend <john.fastabend@gmail.com>
>> Cc: Wenbo Zhang <ethercflow@gmail.com>
>> Signed-off-by: Yonghong Song <yhs@fb.com>
>> ---
> 
> LGTM, two nits below.
> 
> Acked-by: Andrii Nakryiko <andriin@fb.com>
> 
>>   net/bpf/test_run.c                            | 19 +++++++++++++++-
>>   .../selftests/bpf/prog_tests/fentry_fexit.c   |  2 +-
>>   .../testing/selftests/bpf/progs/fentry_test.c | 22 +++++++++++++++++++
>>   .../testing/selftests/bpf/progs/fexit_test.c  | 22 +++++++++++++++++++
>>   4 files changed, 63 insertions(+), 2 deletions(-)
>>
> 
> [...]
> 
>> diff --git a/tools/testing/selftests/bpf/progs/fentry_test.c b/tools/testing/selftests/bpf/progs/fentry_test.c
>> index 9365b686f84b..5f645fdaba6f 100644
>> --- a/tools/testing/selftests/bpf/progs/fentry_test.c
>> +++ b/tools/testing/selftests/bpf/progs/fentry_test.c
>> @@ -55,3 +55,25 @@ int BPF_PROG(test6, __u64 a, void *b, short c, int d, void * e, __u64 f)
>>                  e == (void *)20 && f == 21;
>>          return 0;
>>   }
>> +
>> +struct bpf_fentry_test_t {
>> +       struct bpf_fentry_test_t *a;
>> +};
> 
> nit: __attribute__((preserve_access_index)) ?

Yes. Why not. Will send a followup once the patch circulates back to 
bpf-next.

> 
>> +
>> +__u64 test7_result = 0;
>> +SEC("fentry/bpf_fentry_test7")
>> +int BPF_PROG(test7, struct bpf_fentry_test_t *arg)
>> +{
>> +       if (arg == 0)
>> +               test7_result = 1;
>> +       return 0;
>> +}
>> +
[...]

Re: [PATCH bpf 1/2] bpf: fix an incorrect branch elimination by verifier

[Daniel Borkmann]

On 6/30/20 9:18 PM, Andrii Nakryiko wrote:
> On Tue, Jun 30, 2020 at 11:46 AM Yonghong Song <yhs@fb.com> wrote:
>>
>> Wenbo reported an issue in [1] where a checking of null
>> pointer is evaluated as always false. In this particular
>> case, the program type is tp_btf and the pointer to
>> compare is a PTR_TO_BTF_ID.
>>
>> The current verifier considers PTR_TO_BTF_ID always
>> reprents a non-null pointer, hence all PTR_TO_BTF_ID compares
>> to 0 will be evaluated as always not-equal, which resulted
>> in the branch elimination.
>>
>> For example,
>>   struct bpf_fentry_test_t {
>>       struct bpf_fentry_test_t *a;
>>   };
>>   int BPF_PROG(test7, struct bpf_fentry_test_t *arg)
>>   {
>>       if (arg == 0)
>>           test7_result = 1;
>>       return 0;
>>   }
>>   int BPF_PROG(test8, struct bpf_fentry_test_t *arg)
>>   {
>>       if (arg->a == 0)
>>           test8_result = 1;
>>       return 0;
>>   }
>>
>> In above bpf programs, both branch arg == 0 and arg->a == 0
>> are removed. This may not be what developer expected.
>>
>> The bug is introduced by Commit cac616db39c2 ("bpf: Verifier
>> track null pointer branch_taken with JNE and JEQ"),
>> where PTR_TO_BTF_ID is considered to be non-null when evaluting
>> pointer vs. scalar comparison. This may be added
>> considering we have PTR_TO_BTF_ID_OR_NULL in the verifier
>> as well.
>>
>> PTR_TO_BTF_ID_OR_NULL is added to explicitly requires
>> a non-NULL testing in selective cases. The current generic
>> pointer tracing framework in verifier always
>> assigns PTR_TO_BTF_ID so users does not need to
>> check NULL pointer at every pointer level like a->b->c->d.
>>
>> We may not want to assign every PTR_TO_BTF_ID as
>> PTR_TO_BTF_ID_OR_NULL as this will require a null test
>> before pointer dereference which may cause inconvenience
>> for developers. But we could avoid branch elimination
>> to preserve original code intention.
>>
>> This patch simply removed PTR_TO_BTD_ID from reg_type_not_null()
>> in verifier, which prevented the above branches from being eliminated.
>>
>>   [1]: https://lore.kernel.org/bpf/79dbb7c0-449d-83eb-5f4f-7af0cc269168@fb.com/T/
>>
>> Fixes: cac616db39c2 ("bpf: Verifier track null pointer branch_taken with JNE and JEQ")
>> Cc: Andrii Nakryiko <andriin@fb.com>
>> Cc: John Fastabend <john.fastabend@gmail.com>
>> Cc: Wenbo Zhang <ethercflow@gmail.com>
>> Signed-off-by: Yonghong Song <yhs@fb.com>
>> ---
> 
> You missed Reported-by: tag, please add.

Agree, fixed up manually (and also pulled in your ACKs, Andrii).

Thanks,
Daniel