[PATCH bpf-next 0/2] Track read-only map contents as known scalars in BPF verifiers

[PATCH bpf-next 0/2] Track read-only map contents as known scalars in BPF verifiers

[Andrii Nakryiko]

With BPF maps supporting direct map access (currently, array_map w/ single
element, used for global data) that are read-only both from system call and
BPF side, it's possible for BPF verifier to track its contents as known
constants.

Now it's possible for user-space control app to pre-initialize read-only map
(e.g., for .rodata section) with user-provided flags and parameters and rely
on BPF verifier to detect and eliminate dead code resulting from specific
combination of input parameters.

Andrii Nakryiko (2):
  bpf: track contents of read-only maps as scalars
  selftests/bpf: add read-only map values propagation tests

 kernel/bpf/verifier.c                         | 58 ++++++++++-
 .../selftests/bpf/prog_tests/rdonly_maps.c    | 99 +++++++++++++++++++
 .../selftests/bpf/progs/test_rdonly_maps.c    | 83 ++++++++++++++++
 3 files changed, 238 insertions(+), 2 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/rdonly_maps.c
 create mode 100644 tools/testing/selftests/bpf/progs/test_rdonly_maps.c

-- 
2.17.1

[PATCH bpf-next 1/2] bpf: track contents of read-only maps as scalars

[Andrii Nakryiko]

Maps that are read-only both from BPF program side and user space side
have their contents constant, so verifier can track referenced values
precisely and use that knowledge for dead code elimination, branch
pruning, etc. This patch teaches BPF verifier how to do this.

Signed-off-by: Andrii Nakryiko <andriin@fb.com>
---
 kernel/bpf/verifier.c | 58 +++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 56 insertions(+), 2 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index ffc3e53f5300..1e4e4bd64ca5 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -2739,6 +2739,42 @@ static void coerce_reg_to_size(struct bpf_reg_state *reg, int size)
 	reg->smax_value = reg->umax_value;
 }
 
+static bool bpf_map_is_rdonly(const struct bpf_map *map)
+{
+	return (map->map_flags & BPF_F_RDONLY_PROG) &&
+	       ((map->map_flags & BPF_F_RDONLY) || map->frozen);
+}
+
+static int bpf_map_direct_read(struct bpf_map *map, int off, int size, u64 *val)
+{
+	void *ptr;
+	u64 addr;
+	int err;
+
+	err = map->ops->map_direct_value_addr(map, &addr, off + size);
+	if (err)
+		return err;
+	ptr = (void *)addr + off;
+
+	switch (size) {
+	case sizeof(u8):
+		*val = (u64)*(u8 *)ptr;
+		break;
+	case sizeof(u16):
+		*val = (u64)*(u16 *)ptr;
+		break;
+	case sizeof(u32):
+		*val = (u64)*(u32 *)ptr;
+		break;
+	case sizeof(u64):
+		*val = *(u64 *)ptr;
+		break;
+	default:
+		return -EINVAL;
+	}
+	return 0;
+}
+
 /* check whether memory at (regno + off) is accessible for t = (read | write)
  * if t==write, value_regno is a register which value is stored into memory
  * if t==read, value_regno is a register which will receive the value from memory
@@ -2776,9 +2812,27 @@ static int check_mem_access(struct bpf_verifier_env *env, int insn_idx, u32 regn
 		if (err)
 			return err;
 		err = check_map_access(env, regno, off, size, false);
-		if (!err && t == BPF_READ && value_regno >= 0)
-			mark_reg_unknown(env, regs, value_regno);
+		if (!err && t == BPF_READ && value_regno >= 0) {
+			struct bpf_map *map = reg->map_ptr;
+
+			/* if map is read-only, track its contents as scalars */
+			if (tnum_is_const(reg->var_off) &&
+			    bpf_map_is_rdonly(map) &&
+			    map->ops->map_direct_value_addr) {
+				int map_off = off + reg->var_off.value;
+				u64 val = 0;
 
+				err = bpf_map_direct_read(map, map_off, size,
+							  &val);
+				if (err)
+					return err;
+
+				regs[value_regno].type = SCALAR_VALUE;
+				__mark_reg_known(&regs[value_regno], val);
+			} else {
+				mark_reg_unknown(env, regs, value_regno);
+			}
+		}
 	} else if (reg->type == PTR_TO_CTX) {
 		enum bpf_reg_type reg_type = SCALAR_VALUE;
 
-- 
2.17.1

[PATCH bpf-next 2/2] selftests/bpf: add read-only map values propagation tests

[Andrii Nakryiko]

Add tests checking that verifier does proper constant propagation for
read-only maps. If constant propagation didn't work, skipp_loop and
part_loop BPF programs would be rejected due to BPF verifier otherwise
not being able to prove they ever complete. With constant propagation,
though, they are succesfully validated as properly terminating loops.

Signed-off-by: Andrii Nakryiko <andriin@fb.com>
---
 .../selftests/bpf/prog_tests/rdonly_maps.c    | 99 +++++++++++++++++++
 .../selftests/bpf/progs/test_rdonly_maps.c    | 83 ++++++++++++++++
 2 files changed, 182 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/rdonly_maps.c
 create mode 100644 tools/testing/selftests/bpf/progs/test_rdonly_maps.c

diff --git a/tools/testing/selftests/bpf/prog_tests/rdonly_maps.c b/tools/testing/selftests/bpf/prog_tests/rdonly_maps.c
new file mode 100644
index 000000000000..9bf9de0aaeea
--- /dev/null
+++ b/tools/testing/selftests/bpf/prog_tests/rdonly_maps.c
@@ -0,0 +1,99 @@
+// SPDX-License-Identifier: GPL-2.0
+#include <test_progs.h>
+
+struct bss {
+	unsigned did_run;
+	unsigned iters;
+	unsigned sum;
+};
+
+struct rdonly_map_subtest {
+	const char *subtest_name;
+	const char *prog_name;
+	unsigned exp_iters;
+	unsigned exp_sum;
+};
+
+void test_rdonly_maps(void)
+{
+	const char *prog_name_skip_loop = "raw_tracepoint/sys_enter:skip_loop";
+	const char *prog_name_part_loop = "raw_tracepoint/sys_enter:part_loop";
+	const char *prog_name_full_loop = "raw_tracepoint/sys_enter:full_loop";
+	const char *file = "test_rdonly_maps.o";
+	struct rdonly_map_subtest subtests[] = {
+		{ "skip loop", prog_name_skip_loop, 0, 0 },
+		{ "part loop", prog_name_part_loop, 3, 2 + 3 + 4 },
+		{ "full loop", prog_name_full_loop, 4, 2 + 3 + 4 + 5 },
+	};
+	int i, err, zero = 0, duration = 0;
+	struct bpf_link *link = NULL;
+	struct bpf_program *prog;
+	struct bpf_map *bss_map;
+	struct bpf_object *obj;
+	struct bss bss;
+
+	obj = bpf_object__open_file(file, NULL);
+	if (CHECK(IS_ERR(obj), "obj_open", "err %ld\n", PTR_ERR(obj)))
+		return;
+
+	bpf_object__for_each_program(prog, obj) {
+		bpf_program__set_raw_tracepoint(prog);
+	}
+
+	err = bpf_object__load(obj);
+	if (CHECK(err, "obj_load", "err %d errno %d\n", err, errno))
+		goto cleanup;
+
+	bss_map = bpf_object__find_map_by_name(obj, "test_rdo.bss");
+	if (CHECK(!bss_map, "find_bss_map", "failed\n"))
+		goto cleanup;
+
+	for (i = 0; i < ARRAY_SIZE(subtests); i++) {
+		const struct rdonly_map_subtest *t = &subtests[i];
+
+		if (!test__start_subtest(t->subtest_name))
+			continue;
+
+		prog = bpf_object__find_program_by_title(obj, t->prog_name);
+		if (CHECK(!prog, "find_prog", "prog '%s' not found\n",
+			  t->prog_name))
+			goto cleanup;
+
+		memset(&bss, 0, sizeof(bss));
+		err = bpf_map_update_elem(bpf_map__fd(bss_map), &zero, &bss, 0);
+		if (CHECK(err, "set_bss", "failed to set bss data: %d\n", err))
+			goto cleanup;
+
+		link = bpf_program__attach_raw_tracepoint(prog, "sys_enter");
+		if (CHECK(IS_ERR(link), "attach_prog", "prog '%s', err %ld\n",
+			  t->prog_name, PTR_ERR(link))) {
+			link = NULL;
+			goto cleanup;
+		}
+
+		/* trigger probe */
+		usleep(1);
+
+		bpf_link__destroy(link);
+		link = NULL;
+
+		err = bpf_map_lookup_elem(bpf_map__fd(bss_map), &zero, &bss);
+		if (CHECK(err, "get_bss", "failed to get bss data: %d\n", err))
+			goto cleanup;
+		if (CHECK(bss.did_run == 0, "check_run",
+			  "prog '%s' didn't run?\n", t->prog_name))
+			goto cleanup;
+		if (CHECK(bss.iters != t->exp_iters, "check_iters",
+			  "prog '%s' iters: %d, expected: %d\n",
+			  t->prog_name, bss.iters, t->exp_iters))
+			goto cleanup;
+		if (CHECK(bss.sum != t->exp_sum, "check_sum",
+			  "prog '%s' sum: %d, expected: %d\n",
+			  t->prog_name, bss.sum, t->exp_sum))
+			goto cleanup;
+	}
+
+cleanup:
+	bpf_link__destroy(link);
+	bpf_object__close(obj);
+}
diff --git a/tools/testing/selftests/bpf/progs/test_rdonly_maps.c b/tools/testing/selftests/bpf/progs/test_rdonly_maps.c
new file mode 100644
index 000000000000..52d94e8b214d
--- /dev/null
+++ b/tools/testing/selftests/bpf/progs/test_rdonly_maps.c
@@ -0,0 +1,83 @@
+// SPDX-License-Identifier: GPL-2.0
+// Copyright (c) 2019 Facebook
+
+#include <linux/ptrace.h>
+#include <linux/bpf.h>
+#include "bpf_helpers.h"
+
+static volatile const struct {
+	unsigned a[4];
+	/*
+	 * if the struct's size is multiple of 16, compiler will put it into
+	 * .rodata.cst16 section, which is not recognized by libbpf; work
+	 * around this by ensuring we don't have 16-aligned struct
+	 */
+	char _y;
+} rdonly_values = { .a = {2, 3, 4, 5} };
+
+static volatile struct {
+	unsigned did_run;
+	unsigned iters;
+	unsigned sum;
+} res;
+
+SEC("raw_tracepoint/sys_enter:skip_loop")
+int skip_loop(struct pt_regs *ctx)
+{
+	/* prevent compiler to optimize everything out */
+	unsigned * volatile p = (void *)&rdonly_values.a;
+	unsigned iters = 0, sum = 0;
+
+	/* we should never enter this loop */
+	while (*p & 1) {
+		iters++;
+		sum += *p;
+		p++;
+	}
+	res.did_run = 1;
+	res.iters = iters;
+	res.sum = sum;
+	return 0;
+}
+
+SEC("raw_tracepoint/sys_enter:part_loop")
+int part_loop(struct pt_regs *ctx)
+{
+	/* prevent compiler to optimize everything out */
+	unsigned * volatile p = (void *)&rdonly_values.a;
+	unsigned iters = 0, sum = 0;
+
+	/* validate verifier can derive loop termination */
+	while (*p < 5) {
+		iters++;
+		sum += *p;
+		p++;
+	}
+	res.did_run = 1;
+	res.iters = iters;
+	res.sum = sum;
+	return 0;
+}
+
+SEC("raw_tracepoint/sys_enter:full_loop")
+int full_loop(struct pt_regs *ctx)
+{
+	/* prevent compiler to optimize everything out */
+	unsigned * volatile p = (void *)&rdonly_values.a;
+	int i = sizeof(rdonly_values.a) / sizeof(rdonly_values.a[0]);
+	unsigned iters = 0, sum = 0;
+
+	/* validate verifier can allow full loop as well */
+	while (i > 0 ) {
+		iters++;
+		sum += *p;
+		p++;
+		i--;
+	}
+	res.did_run = 1;
+	res.iters = iters;
+	res.sum = sum;
+	return 0;
+}
+
+char _license[] SEC("license") = "GPL";
-- 
2.17.1

Re: [PATCH bpf-next 1/2] bpf: track contents of read-only maps as scalars

[Daniel Borkmann]

On Tue, Oct 08, 2019 at 12:45:47PM -0700, Andrii Nakryiko wrote:
> Maps that are read-only both from BPF program side and user space side
> have their contents constant, so verifier can track referenced values
> precisely and use that knowledge for dead code elimination, branch
> pruning, etc. This patch teaches BPF verifier how to do this.
> 
> Signed-off-by: Andrii Nakryiko <andriin@fb.com>
> ---
>  kernel/bpf/verifier.c | 58 +++++++++++++++++++++++++++++++++++++++++--
>  1 file changed, 56 insertions(+), 2 deletions(-)
> 
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index ffc3e53f5300..1e4e4bd64ca5 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -2739,6 +2739,42 @@ static void coerce_reg_to_size(struct bpf_reg_state *reg, int size)
>  	reg->smax_value = reg->umax_value;
>  }
>  
> +static bool bpf_map_is_rdonly(const struct bpf_map *map)
> +{
> +	return (map->map_flags & BPF_F_RDONLY_PROG) &&
> +	       ((map->map_flags & BPF_F_RDONLY) || map->frozen);

This is definitely buggy. Testing for 'map->map_flags & BPF_F_RDONLY'
to assume it's RO from user space side is not correct as it's just
related to the current fd, but not the map itself. So the second part
definitely /must/ only be: && map->frozen

Thanks,
Daniel

Re: [PATCH bpf-next 1/2] bpf: track contents of read-only maps as scalars

[Martin Lau]

On Tue, Oct 08, 2019 at 12:45:47PM -0700, Andrii Nakryiko wrote:
> Maps that are read-only both from BPF program side and user space side
> have their contents constant, so verifier can track referenced values
> precisely and use that knowledge for dead code elimination, branch
> pruning, etc. This patch teaches BPF verifier how to do this.
> 
> Signed-off-by: Andrii Nakryiko <andriin@fb.com>
> ---
>  kernel/bpf/verifier.c | 58 +++++++++++++++++++++++++++++++++++++++++--
>  1 file changed, 56 insertions(+), 2 deletions(-)
> 
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index ffc3e53f5300..1e4e4bd64ca5 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -2739,6 +2739,42 @@ static void coerce_reg_to_size(struct bpf_reg_state *reg, int size)
>  	reg->smax_value = reg->umax_value;
>  }
>  
> +static bool bpf_map_is_rdonly(const struct bpf_map *map)
> +{
> +	return (map->map_flags & BPF_F_RDONLY_PROG) &&
> +	       ((map->map_flags & BPF_F_RDONLY) || map->frozen);
> +}
> +
> +static int bpf_map_direct_read(struct bpf_map *map, int off, int size, u64 *val)
> +{
> +	void *ptr;
> +	u64 addr;
> +	int err;
> +
> +	err = map->ops->map_direct_value_addr(map, &addr, off + size);
Should it be "off" instead of "off + size"?

> +	if (err)
> +		return err;
> +	ptr = (void *)addr + off;
> +
> +	switch (size) {
> +	case sizeof(u8):
> +		*val = (u64)*(u8 *)ptr;
> +		break;
> +	case sizeof(u16):
> +		*val = (u64)*(u16 *)ptr;
> +		break;
> +	case sizeof(u32):
> +		*val = (u64)*(u32 *)ptr;
> +		break;
> +	case sizeof(u64):
> +		*val = *(u64 *)ptr;
> +		break;
> +	default:
> +		return -EINVAL;
> +	}
> +	return 0;
> +}
> +
>  /* check whether memory at (regno + off) is accessible for t = (read | write)
>   * if t==write, value_regno is a register which value is stored into memory
>   * if t==read, value_regno is a register which will receive the value from memory
> @@ -2776,9 +2812,27 @@ static int check_mem_access(struct bpf_verifier_env *env, int insn_idx, u32 regn
>  		if (err)
>  			return err;
>  		err = check_map_access(env, regno, off, size, false);
> -		if (!err && t == BPF_READ && value_regno >= 0)
> -			mark_reg_unknown(env, regs, value_regno);
> +		if (!err && t == BPF_READ && value_regno >= 0) {
> +			struct bpf_map *map = reg->map_ptr;
> +
> +			/* if map is read-only, track its contents as scalars */
> +			if (tnum_is_const(reg->var_off) &&
> +			    bpf_map_is_rdonly(map) &&
> +			    map->ops->map_direct_value_addr) {
> +				int map_off = off + reg->var_off.value;
> +				u64 val = 0;
>  
> +				err = bpf_map_direct_read(map, map_off, size,
> +							  &val);
> +				if (err)
> +					return err;
> +
> +				regs[value_regno].type = SCALAR_VALUE;
> +				__mark_reg_known(&regs[value_regno], val);
> +			} else {
> +				mark_reg_unknown(env, regs, value_regno);
> +			}
> +		}
>  	} else if (reg->type == PTR_TO_CTX) {
>  		enum bpf_reg_type reg_type = SCALAR_VALUE;
>  
> -- 
> 2.17.1
> 

Re: [PATCH bpf-next 1/2] bpf: track contents of read-only maps as scalars

[Andrii Nakryiko]

On Tue, Oct 8, 2019 at 2:29 PM Daniel Borkmann <daniel@iogearbox.net> wrote:
>
> On Tue, Oct 08, 2019 at 12:45:47PM -0700, Andrii Nakryiko wrote:
> > Maps that are read-only both from BPF program side and user space side
> > have their contents constant, so verifier can track referenced values
> > precisely and use that knowledge for dead code elimination, branch
> > pruning, etc. This patch teaches BPF verifier how to do this.
> >
> > Signed-off-by: Andrii Nakryiko <andriin@fb.com>
> > ---
> >  kernel/bpf/verifier.c | 58 +++++++++++++++++++++++++++++++++++++++++--
> >  1 file changed, 56 insertions(+), 2 deletions(-)
> >
> > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > index ffc3e53f5300..1e4e4bd64ca5 100644
> > --- a/kernel/bpf/verifier.c
> > +++ b/kernel/bpf/verifier.c
> > @@ -2739,6 +2739,42 @@ static void coerce_reg_to_size(struct bpf_reg_state *reg, int size)
> >       reg->smax_value = reg->umax_value;
> >  }
> >
> > +static bool bpf_map_is_rdonly(const struct bpf_map *map)
> > +{
> > +     return (map->map_flags & BPF_F_RDONLY_PROG) &&
> > +            ((map->map_flags & BPF_F_RDONLY) || map->frozen);
>
> This is definitely buggy. Testing for 'map->map_flags & BPF_F_RDONLY'
> to assume it's RO from user space side is not correct as it's just
> related to the current fd, but not the map itself. So the second part
> definitely /must/ only be: && map->frozen

Yep, you are right, map->frozen and BPF_F_RDONLY_PROG only.

>
> Thanks,
> Daniel

Re: [PATCH bpf-next 1/2] bpf: track contents of read-only maps as scalars

[Andrii Nakryiko]

On Tue, Oct 8, 2019 at 2:53 PM Martin Lau <kafai@fb.com> wrote:
>
> On Tue, Oct 08, 2019 at 12:45:47PM -0700, Andrii Nakryiko wrote:
> > Maps that are read-only both from BPF program side and user space side
> > have their contents constant, so verifier can track referenced values
> > precisely and use that knowledge for dead code elimination, branch
> > pruning, etc. This patch teaches BPF verifier how to do this.
> >
> > Signed-off-by: Andrii Nakryiko <andriin@fb.com>
> > ---
> >  kernel/bpf/verifier.c | 58 +++++++++++++++++++++++++++++++++++++++++--
> >  1 file changed, 56 insertions(+), 2 deletions(-)
> >
> > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > index ffc3e53f5300..1e4e4bd64ca5 100644
> > --- a/kernel/bpf/verifier.c
> > +++ b/kernel/bpf/verifier.c
> > @@ -2739,6 +2739,42 @@ static void coerce_reg_to_size(struct bpf_reg_state *reg, int size)
> >       reg->smax_value = reg->umax_value;
> >  }
> >
> > +static bool bpf_map_is_rdonly(const struct bpf_map *map)
> > +{
> > +     return (map->map_flags & BPF_F_RDONLY_PROG) &&
> > +            ((map->map_flags & BPF_F_RDONLY) || map->frozen);
> > +}
> > +
> > +static int bpf_map_direct_read(struct bpf_map *map, int off, int size, u64 *val)
> > +{
> > +     void *ptr;
> > +     u64 addr;
> > +     int err;
> > +
> > +     err = map->ops->map_direct_value_addr(map, &addr, off + size);
> Should it be "off" instead of "off + size"?

From array_map_direct_value_addr() code, offset is used only to check
that access is happening within array value bounds. It's not used to
calculate returned pointer.
But now re-reading its code again, I think this check is wrong:

if (off >= map->value_size)
        break;

It has to be (off > map->value_size). But it seems like this whole
interface is counter-intuitive.

I'm wondering if Daniel can clarify the intent behind this particular behavior.

For now the easiest fix is to pass (off + size - 1). But maybe we
should change the contract to be something like

int map_direct_value_addr(const struct bpf_map *map, u64 off, int
size, void *ptr)

This then can validate that entire access in the range of [off, off +
size) is acceptable to a map, and then return void * pointer according
to given off. Thoughts?

>
> > +     if (err)
> > +             return err;
> > +     ptr = (void *)addr + off;
> > +
> > +     switch (size) {
> > +     case sizeof(u8):
> > +             *val = (u64)*(u8 *)ptr;
> > +             break;
> > +     case sizeof(u16):
> > +             *val = (u64)*(u16 *)ptr;
> > +             break;
> > +     case sizeof(u32):
> > +             *val = (u64)*(u32 *)ptr;
> > +             break;
> > +     case sizeof(u64):
> > +             *val = *(u64 *)ptr;
> > +             break;
> > +     default:
> > +             return -EINVAL;
> > +     }
> > +     return 0;
> > +}
> > +
> >  /* check whether memory at (regno + off) is accessible for t = (read | write)
> >   * if t==write, value_regno is a register which value is stored into memory
> >   * if t==read, value_regno is a register which will receive the value from memory
> > @@ -2776,9 +2812,27 @@ static int check_mem_access(struct bpf_verifier_env *env, int insn_idx, u32 regn
> >               if (err)
> >                       return err;
> >               err = check_map_access(env, regno, off, size, false);
> > -             if (!err && t == BPF_READ && value_regno >= 0)
> > -                     mark_reg_unknown(env, regs, value_regno);
> > +             if (!err && t == BPF_READ && value_regno >= 0) {
> > +                     struct bpf_map *map = reg->map_ptr;
> > +
> > +                     /* if map is read-only, track its contents as scalars */
> > +                     if (tnum_is_const(reg->var_off) &&
> > +                         bpf_map_is_rdonly(map) &&
> > +                         map->ops->map_direct_value_addr) {
> > +                             int map_off = off + reg->var_off.value;
> > +                             u64 val = 0;
> >
> > +                             err = bpf_map_direct_read(map, map_off, size,
> > +                                                       &val);
> > +                             if (err)
> > +                                     return err;
> > +
> > +                             regs[value_regno].type = SCALAR_VALUE;
> > +                             __mark_reg_known(&regs[value_regno], val);
> > +                     } else {
> > +                             mark_reg_unknown(env, regs, value_regno);
> > +                     }
> > +             }
> >       } else if (reg->type == PTR_TO_CTX) {
> >               enum bpf_reg_type reg_type = SCALAR_VALUE;
> >
> > --
> > 2.17.1
> >

Re: [PATCH bpf-next 1/2] bpf: track contents of read-only maps as scalars

[Martin Lau]

On Tue, Oct 08, 2019 at 04:49:30PM -0700, Andrii Nakryiko wrote:
> On Tue, Oct 8, 2019 at 2:53 PM Martin Lau <kafai@fb.com> wrote:
> >
> > On Tue, Oct 08, 2019 at 12:45:47PM -0700, Andrii Nakryiko wrote:
> > > Maps that are read-only both from BPF program side and user space side
> > > have their contents constant, so verifier can track referenced values
> > > precisely and use that knowledge for dead code elimination, branch
> > > pruning, etc. This patch teaches BPF verifier how to do this.
> > >
> > > Signed-off-by: Andrii Nakryiko <andriin@fb.com>
> > > ---
> > >  kernel/bpf/verifier.c | 58 +++++++++++++++++++++++++++++++++++++++++--
> > >  1 file changed, 56 insertions(+), 2 deletions(-)
> > >
> > > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > > index ffc3e53f5300..1e4e4bd64ca5 100644
> > > --- a/kernel/bpf/verifier.c
> > > +++ b/kernel/bpf/verifier.c
> > > @@ -2739,6 +2739,42 @@ static void coerce_reg_to_size(struct bpf_reg_state *reg, int size)
> > >       reg->smax_value = reg->umax_value;
> > >  }
> > >
> > > +static bool bpf_map_is_rdonly(const struct bpf_map *map)
> > > +{
> > > +     return (map->map_flags & BPF_F_RDONLY_PROG) &&
> > > +            ((map->map_flags & BPF_F_RDONLY) || map->frozen);
> > > +}
> > > +
> > > +static int bpf_map_direct_read(struct bpf_map *map, int off, int size, u64 *val)
> > > +{
> > > +     void *ptr;
> > > +     u64 addr;
> > > +     int err;
> > > +
> > > +     err = map->ops->map_direct_value_addr(map, &addr, off + size);
> > Should it be "off" instead of "off + size"?
> 
> From array_map_direct_value_addr() code, offset is used only to check
> that access is happening within array value bounds.
The "size" check is done separately in the check_map_access(),
so "off" is offset alone, I think.

> It's not used to
> calculate returned pointer.
> But now re-reading its code again, I think this check is wrong:
> 
> if (off >= map->value_size)
>         break;
> 
> It has to be (off > map->value_size). But it seems like this whole
> interface is counter-intuitive.
> 
> I'm wondering if Daniel can clarify the intent behind this particular behavior.
> 
> For now the easiest fix is to pass (off + size - 1). But maybe we
> should change the contract to be something like
> 
> int map_direct_value_addr(const struct bpf_map *map, u64 off, int
> size, void *ptr)
> 
> This then can validate that entire access in the range of [off, off +
> size) is acceptable to a map, and then return void * pointer according
> to given off. Thoughts?
> 
> >
> > > +     if (err)
> > > +             return err;
> > > +     ptr = (void *)addr + off;
> > > +
> > > +     switch (size) {
> > > +     case sizeof(u8):
> > > +             *val = (u64)*(u8 *)ptr;
> > > +             break;
> > > +     case sizeof(u16):
> > > +             *val = (u64)*(u16 *)ptr;
> > > +             break;
> > > +     case sizeof(u32):
> > > +             *val = (u64)*(u32 *)ptr;
> > > +             break;
> > > +     case sizeof(u64):
> > > +             *val = *(u64 *)ptr;
> > > +             break;
> > > +     default:
> > > +             return -EINVAL;
> > > +     }
> > > +     return 0;
> > > +}
> > > +
> > >  /* check whether memory at (regno + off) is accessible for t = (read | write)
> > >   * if t==write, value_regno is a register which value is stored into memory
> > >   * if t==read, value_regno is a register which will receive the value from memory
> > > @@ -2776,9 +2812,27 @@ static int check_mem_access(struct bpf_verifier_env *env, int insn_idx, u32 regn
> > >               if (err)
> > >                       return err;
> > >               err = check_map_access(env, regno, off, size, false);
> > > -             if (!err && t == BPF_READ && value_regno >= 0)
> > > -                     mark_reg_unknown(env, regs, value_regno);
> > > +             if (!err && t == BPF_READ && value_regno >= 0) {
> > > +                     struct bpf_map *map = reg->map_ptr;
> > > +
> > > +                     /* if map is read-only, track its contents as scalars */
> > > +                     if (tnum_is_const(reg->var_off) &&
> > > +                         bpf_map_is_rdonly(map) &&
> > > +                         map->ops->map_direct_value_addr) {
> > > +                             int map_off = off + reg->var_off.value;
> > > +                             u64 val = 0;
> > >
> > > +                             err = bpf_map_direct_read(map, map_off, size,
> > > +                                                       &val);
> > > +                             if (err)
> > > +                                     return err;
> > > +
> > > +                             regs[value_regno].type = SCALAR_VALUE;
> > > +                             __mark_reg_known(&regs[value_regno], val);
> > > +                     } else {
> > > +                             mark_reg_unknown(env, regs, value_regno);
> > > +                     }
> > > +             }
> > >       } else if (reg->type == PTR_TO_CTX) {
> > >               enum bpf_reg_type reg_type = SCALAR_VALUE;
> > >
> > > --
> > > 2.17.1
> > >

Re: [PATCH bpf-next 1/2] bpf: track contents of read-only maps as scalars

[Andrii Nakryiko]

On Tue, Oct 8, 2019 at 5:34 PM Martin Lau <kafai@fb.com> wrote:
>
> On Tue, Oct 08, 2019 at 04:49:30PM -0700, Andrii Nakryiko wrote:
> > On Tue, Oct 8, 2019 at 2:53 PM Martin Lau <kafai@fb.com> wrote:
> > >
> > > On Tue, Oct 08, 2019 at 12:45:47PM -0700, Andrii Nakryiko wrote:
> > > > Maps that are read-only both from BPF program side and user space side
> > > > have their contents constant, so verifier can track referenced values
> > > > precisely and use that knowledge for dead code elimination, branch
> > > > pruning, etc. This patch teaches BPF verifier how to do this.
> > > >
> > > > Signed-off-by: Andrii Nakryiko <andriin@fb.com>
> > > > ---
> > > >  kernel/bpf/verifier.c | 58 +++++++++++++++++++++++++++++++++++++++++--
> > > >  1 file changed, 56 insertions(+), 2 deletions(-)
> > > >
> > > > diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> > > > index ffc3e53f5300..1e4e4bd64ca5 100644
> > > > --- a/kernel/bpf/verifier.c
> > > > +++ b/kernel/bpf/verifier.c
> > > > @@ -2739,6 +2739,42 @@ static void coerce_reg_to_size(struct bpf_reg_state *reg, int size)
> > > >       reg->smax_value = reg->umax_value;
> > > >  }
> > > >
> > > > +static bool bpf_map_is_rdonly(const struct bpf_map *map)
> > > > +{
> > > > +     return (map->map_flags & BPF_F_RDONLY_PROG) &&
> > > > +            ((map->map_flags & BPF_F_RDONLY) || map->frozen);
> > > > +}
> > > > +
> > > > +static int bpf_map_direct_read(struct bpf_map *map, int off, int size, u64 *val)
> > > > +{
> > > > +     void *ptr;
> > > > +     u64 addr;
> > > > +     int err;
> > > > +
> > > > +     err = map->ops->map_direct_value_addr(map, &addr, off + size);
> > > Should it be "off" instead of "off + size"?
> >
> > From array_map_direct_value_addr() code, offset is used only to check
> > that access is happening within array value bounds.
> The "size" check is done separately in the check_map_access(),
> so "off" is offset alone, I think.

Yeah, makes sense. I guess the check was originally done for loading
direct address into array, with actual access (byte, word, etc) done
separately in subsequent instructions. I'll change it back to off,
though it doesn't matter in this case, because we already checked it
above (both offset and size).

>
> > It's not used to
> > calculate returned pointer.
> > But now re-reading its code again, I think this check is wrong:
> >
> > if (off >= map->value_size)
> >         break;
> >
> > It has to be (off > map->value_size). But it seems like this whole
> > interface is counter-intuitive.
> >
> > I'm wondering if Daniel can clarify the intent behind this particular behavior.
> >
> > For now the easiest fix is to pass (off + size - 1). But maybe we
> > should change the contract to be something like
> >
> > int map_direct_value_addr(const struct bpf_map *map, u64 off, int
> > size, void *ptr)
> >
> > This then can validate that entire access in the range of [off, off +
> > size) is acceptable to a map, and then return void * pointer according
> > to given off. Thoughts?
> >
> > >
> > > > +     if (err)
> > > > +             return err;
> > > > +     ptr = (void *)addr + off;
> > > > +
> > > > +     switch (size) {
> > > > +     case sizeof(u8):
> > > > +             *val = (u64)*(u8 *)ptr;
> > > > +             break;
> > > > +     case sizeof(u16):
> > > > +             *val = (u64)*(u16 *)ptr;
> > > > +             break;
> > > > +     case sizeof(u32):
> > > > +             *val = (u64)*(u32 *)ptr;
> > > > +             break;
> > > > +     case sizeof(u64):
> > > > +             *val = *(u64 *)ptr;
> > > > +             break;
> > > > +     default:
> > > > +             return -EINVAL;
> > > > +     }
> > > > +     return 0;
> > > > +}
> > > > +
> > > >  /* check whether memory at (regno + off) is accessible for t = (read | write)
> > > >   * if t==write, value_regno is a register which value is stored into memory
> > > >   * if t==read, value_regno is a register which will receive the value from memory
> > > > @@ -2776,9 +2812,27 @@ static int check_mem_access(struct bpf_verifier_env *env, int insn_idx, u32 regn
> > > >               if (err)
> > > >                       return err;
> > > >               err = check_map_access(env, regno, off, size, false);
> > > > -             if (!err && t == BPF_READ && value_regno >= 0)
> > > > -                     mark_reg_unknown(env, regs, value_regno);
> > > > +             if (!err && t == BPF_READ && value_regno >= 0) {
> > > > +                     struct bpf_map *map = reg->map_ptr;
> > > > +
> > > > +                     /* if map is read-only, track its contents as scalars */
> > > > +                     if (tnum_is_const(reg->var_off) &&
> > > > +                         bpf_map_is_rdonly(map) &&
> > > > +                         map->ops->map_direct_value_addr) {
> > > > +                             int map_off = off + reg->var_off.value;
> > > > +                             u64 val = 0;
> > > >
> > > > +                             err = bpf_map_direct_read(map, map_off, size,
> > > > +                                                       &val);
> > > > +                             if (err)
> > > > +                                     return err;
> > > > +
> > > > +                             regs[value_regno].type = SCALAR_VALUE;
> > > > +                             __mark_reg_known(&regs[value_regno], val);
> > > > +                     } else {
> > > > +                             mark_reg_unknown(env, regs, value_regno);
> > > > +                     }
> > > > +             }
> > > >       } else if (reg->type == PTR_TO_CTX) {
> > > >               enum bpf_reg_type reg_type = SCALAR_VALUE;
> > > >
> > > > --
> > > > 2.17.1
> > > >