[PATCH bpf-next 0/4] BPF array map fixes and improvements

[PATCH bpf-next 0/4] BPF array map fixes and improvements

[Andrii Nakryiko]

Fix 32-bit overflow in value pointer calculations in BPF array map. And then
raise obsolete limit on array map value size. Add selftest making sure this is
working as intended.

Andrii Nakryiko (4):
  bpf: fix potential 32-bit overflow when accessing ARRAY map element
  bpf: make uniform use of array->elem_size everywhere in arraymap.c
  bpf: remove obsolete KMALLOC_MAX_SIZE restriction on array map value
    size
  selftests/bpf: validate .bss section bigger than 8MB is possible now

 kernel/bpf/arraymap.c                         | 40 ++++++++++---------
 .../selftests/bpf/prog_tests/skeleton.c       |  2 +
 .../selftests/bpf/progs/test_skeleton.c       |  4 ++
 3 files changed, 28 insertions(+), 18 deletions(-)

-- 
2.30.2

[PATCH bpf-next 1/4] bpf: fix potential 32-bit overflow when accessing ARRAY map element

[Andrii Nakryiko]

If BPF array map is bigger than 4GB, element pointer calculation can
overflow because both index and elem_size are u32. Fix this everywhere
by forcing 64-bit multiplication. Extract this formula into separate
small helper and use it consistently in various places.

Speculative-preventing formula utilizing index_mask trick is left as is,
but explicit u64 casts are added in both places.

Fixes: c85d69135a91 ("bpf: move memory size checks to bpf_map_charge_init()")
Signed-off-by: Andrii Nakryiko <andrii@kernel.org>
---
 kernel/bpf/arraymap.c | 20 ++++++++++++--------
 1 file changed, 12 insertions(+), 8 deletions(-)

diff --git a/kernel/bpf/arraymap.c b/kernel/bpf/arraymap.c
index fe40d3b9458f..d3dfc28dbb05 100644
--- a/kernel/bpf/arraymap.c
+++ b/kernel/bpf/arraymap.c
@@ -156,6 +156,11 @@ static struct bpf_map *array_map_alloc(union bpf_attr *attr)
 	return &array->map;
 }
 
+static void *array_map_elem_ptr(struct bpf_array* array, u32 index)
+{
+	return array->value + (u64)array->elem_size * (index & array->index_mask);
+}
+
 /* Called from syscall or from eBPF program */
 static void *array_map_lookup_elem(struct bpf_map *map, void *key)
 {
@@ -165,7 +170,7 @@ static void *array_map_lookup_elem(struct bpf_map *map, void *key)
 	if (unlikely(index >= array->map.max_entries))
 		return NULL;
 
-	return array->value + array->elem_size * (index & array->index_mask);
+	return array->value + (u64)array->elem_size * (index & array->index_mask)
 }
 
 static int array_map_direct_value_addr(const struct bpf_map *map, u64 *imm,
@@ -339,7 +344,7 @@ static int array_map_update_elem(struct bpf_map *map, void *key, void *value,
 		       value, map->value_size);
 	} else {
 		val = array->value +
-			array->elem_size * (index & array->index_mask);
+			(u64)array->elem_size * (index & array->index_mask);
 		if (map_flags & BPF_F_LOCK)
 			copy_map_value_locked(map, val, value, false);
 		else
@@ -408,8 +413,7 @@ static void array_map_free_timers(struct bpf_map *map)
 		return;
 
 	for (i = 0; i < array->map.max_entries; i++)
-		bpf_timer_cancel_and_free(array->value + array->elem_size * i +
-					  map->timer_off);
+		bpf_timer_cancel_and_free(array_map_elem_ptr(array, i) + map->timer_off);
 }
 
 /* Called when map->refcnt goes to zero, either from workqueue or from syscall */
@@ -420,7 +424,7 @@ static void array_map_free(struct bpf_map *map)
 
 	if (map_value_has_kptrs(map)) {
 		for (i = 0; i < array->map.max_entries; i++)
-			bpf_map_free_kptrs(map, array->value + array->elem_size * i);
+			bpf_map_free_kptrs(map, array_map_elem_ptr(array, i));
 		bpf_map_free_kptr_off_tab(map);
 	}
 
@@ -556,7 +560,7 @@ static void *bpf_array_map_seq_start(struct seq_file *seq, loff_t *pos)
 	index = info->index & array->index_mask;
 	if (info->percpu_value_buf)
 	       return array->pptrs[index];
-	return array->value + array->elem_size * index;
+	return array_map_elem_ptr(array, index);
 }
 
 static void *bpf_array_map_seq_next(struct seq_file *seq, void *v, loff_t *pos)
@@ -575,7 +579,7 @@ static void *bpf_array_map_seq_next(struct seq_file *seq, void *v, loff_t *pos)
 	index = info->index & array->index_mask;
 	if (info->percpu_value_buf)
 	       return array->pptrs[index];
-	return array->value + array->elem_size * index;
+	return array_map_elem_ptr(array, index);
 }
 
 static int __bpf_array_map_seq_show(struct seq_file *seq, void *v)
@@ -690,7 +694,7 @@ static int bpf_for_each_array_elem(struct bpf_map *map, bpf_callback_t callback_
 		if (is_percpu)
 			val = this_cpu_ptr(array->pptrs[i]);
 		else
-			val = array->value + array->elem_size * i;
+			val = array_map_elem_ptr(array, i);
 		num_elems++;
 		key = i;
 		ret = callback_fn((u64)(long)map, (u64)(long)&key,
-- 
2.30.2

Re: [PATCH bpf-next 1/4] bpf: fix potential 32-bit overflow when accessing ARRAY map element

[kernel test robot]

Hi Andrii,

I love your patch! Yet something to improve:

[auto build test ERROR on bpf-next/master]

url:    https://github.com/intel-lab-lkp/linux/commits/Andrii-Nakryiko/BPF-array-map-fixes-and-improvements/20220715-054514
base:   https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git master
config: hexagon-randconfig-r045-20220714 (https://download.01.org/0day-ci/archive/20220715/202207150918.GuUgOFHd-lkp@intel.com/config)
compiler: clang version 15.0.0 (https://github.com/llvm/llvm-project 2da550140aa98cf6a3e96417c87f1e89e3a26047)
reproduce (this is a W=1 build):
        wget https://raw.githubusercontent.com/intel/lkp-tests/master/sbin/make.cross -O ~/bin/make.cross
        chmod +x ~/bin/make.cross
        # https://github.com/intel-lab-lkp/linux/commit/c740c9bcbe3ab67a921ace0d988bd45214c41bef
        git remote add linux-review https://github.com/intel-lab-lkp/linux
        git fetch --no-tags linux-review Andrii-Nakryiko/BPF-array-map-fixes-and-improvements/20220715-054514
        git checkout c740c9bcbe3ab67a921ace0d988bd45214c41bef
        # save the config file
        mkdir build_dir && cp config build_dir/.config
        COMPILER_INSTALL_PATH=$HOME/0day COMPILER=clang make.cross W=1 O=build_dir ARCH=hexagon SHELL=/bin/bash kernel/bpf/

If you fix the issue, kindly add following tag where applicable
Reported-by: kernel test robot <lkp@intel.com>

All errors (new ones prefixed by >>):

>> kernel/bpf/arraymap.c:173:75: error: expected ';' after return statement
           return array->value + (u64)array->elem_size * (index & array->index_mask)
                                                                                    ^
                                                                                    ;
   1 error generated.


vim +173 kernel/bpf/arraymap.c

   163	
   164	/* Called from syscall or from eBPF program */
   165	static void *array_map_lookup_elem(struct bpf_map *map, void *key)
   166	{
   167		struct bpf_array *array = container_of(map, struct bpf_array, map);
   168		u32 index = *(u32 *)key;
   169	
   170		if (unlikely(index >= array->map.max_entries))
   171			return NULL;
   172	
 > 173		return array->value + (u64)array->elem_size * (index & array->index_mask)
   174	}
   175	

-- 
0-DAY CI Kernel Test Service
https://01.org/lkp

Re: [PATCH bpf-next 1/4] bpf: fix potential 32-bit overflow when accessing ARRAY map element

[Alexei Starovoitov]

On Thu, Jul 14, 2022 at 02:43:02PM -0700, Andrii Nakryiko wrote:
> If BPF array map is bigger than 4GB, element pointer calculation can
> overflow because both index and elem_size are u32. Fix this everywhere
> by forcing 64-bit multiplication. Extract this formula into separate
> small helper and use it consistently in various places.
> 
> Speculative-preventing formula utilizing index_mask trick is left as is,
> but explicit u64 casts are added in both places.
> 
> Fixes: c85d69135a91 ("bpf: move memory size checks to bpf_map_charge_init()")
> Signed-off-by: Andrii Nakryiko <andrii@kernel.org>
> ---
>  kernel/bpf/arraymap.c | 20 ++++++++++++--------
>  1 file changed, 12 insertions(+), 8 deletions(-)
> 
> diff --git a/kernel/bpf/arraymap.c b/kernel/bpf/arraymap.c
> index fe40d3b9458f..d3dfc28dbb05 100644
> --- a/kernel/bpf/arraymap.c
> +++ b/kernel/bpf/arraymap.c
> @@ -156,6 +156,11 @@ static struct bpf_map *array_map_alloc(union bpf_attr *attr)
>  	return &array->map;
>  }
>  
> +static void *array_map_elem_ptr(struct bpf_array* array, u32 index)
> +{
> +	return array->value + (u64)array->elem_size * (index & array->index_mask);
> +}
> +
>  /* Called from syscall or from eBPF program */
>  static void *array_map_lookup_elem(struct bpf_map *map, void *key)
>  {
> @@ -165,7 +170,7 @@ static void *array_map_lookup_elem(struct bpf_map *map, void *key)
>  	if (unlikely(index >= array->map.max_entries))
>  		return NULL;
>  
> -	return array->value + array->elem_size * (index & array->index_mask);
> +	return array->value + (u64)array->elem_size * (index & array->index_mask)
>  }
>  
>  static int array_map_direct_value_addr(const struct bpf_map *map, u64 *imm,
> @@ -339,7 +344,7 @@ static int array_map_update_elem(struct bpf_map *map, void *key, void *value,
>  		       value, map->value_size);
>  	} else {
>  		val = array->value +
> -			array->elem_size * (index & array->index_mask);
> +			(u64)array->elem_size * (index & array->index_mask);
>  		if (map_flags & BPF_F_LOCK)
>  			copy_map_value_locked(map, val, value, false);
>  		else
> @@ -408,8 +413,7 @@ static void array_map_free_timers(struct bpf_map *map)
>  		return;
>  
>  	for (i = 0; i < array->map.max_entries; i++)
> -		bpf_timer_cancel_and_free(array->value + array->elem_size * i +
> -					  map->timer_off);
> +		bpf_timer_cancel_and_free(array_map_elem_ptr(array, i) + map->timer_off);
>  }
>  
>  /* Called when map->refcnt goes to zero, either from workqueue or from syscall */
> @@ -420,7 +424,7 @@ static void array_map_free(struct bpf_map *map)
>  
>  	if (map_value_has_kptrs(map)) {
>  		for (i = 0; i < array->map.max_entries; i++)
> -			bpf_map_free_kptrs(map, array->value + array->elem_size * i);
> +			bpf_map_free_kptrs(map, array_map_elem_ptr(array, i));

This is incorrect. There is no need to mask pointer here.
There is no security issue here.

Re: [PATCH bpf-next 1/4] bpf: fix potential 32-bit overflow when accessing ARRAY map element

[Andrii Nakryiko]

On Thu, Jul 14, 2022 at 9:58 PM Alexei Starovoitov
<alexei.starovoitov@gmail.com> wrote:
>
> On Thu, Jul 14, 2022 at 02:43:02PM -0700, Andrii Nakryiko wrote:
> > If BPF array map is bigger than 4GB, element pointer calculation can
> > overflow because both index and elem_size are u32. Fix this everywhere
> > by forcing 64-bit multiplication. Extract this formula into separate
> > small helper and use it consistently in various places.
> >
> > Speculative-preventing formula utilizing index_mask trick is left as is,
> > but explicit u64 casts are added in both places.
> >
> > Fixes: c85d69135a91 ("bpf: move memory size checks to bpf_map_charge_init()")
> > Signed-off-by: Andrii Nakryiko <andrii@kernel.org>
> > ---
> >  kernel/bpf/arraymap.c | 20 ++++++++++++--------
> >  1 file changed, 12 insertions(+), 8 deletions(-)
> >
> > diff --git a/kernel/bpf/arraymap.c b/kernel/bpf/arraymap.c
> > index fe40d3b9458f..d3dfc28dbb05 100644
> > --- a/kernel/bpf/arraymap.c
> > +++ b/kernel/bpf/arraymap.c
> > @@ -156,6 +156,11 @@ static struct bpf_map *array_map_alloc(union bpf_attr *attr)
> >       return &array->map;
> >  }
> >
> > +static void *array_map_elem_ptr(struct bpf_array* array, u32 index)
> > +{
> > +     return array->value + (u64)array->elem_size * (index & array->index_mask);
> > +}
> > +
> >  /* Called from syscall or from eBPF program */
> >  static void *array_map_lookup_elem(struct bpf_map *map, void *key)
> >  {
> > @@ -165,7 +170,7 @@ static void *array_map_lookup_elem(struct bpf_map *map, void *key)
> >       if (unlikely(index >= array->map.max_entries))
> >               return NULL;
> >
> > -     return array->value + array->elem_size * (index & array->index_mask);
> > +     return array->value + (u64)array->elem_size * (index & array->index_mask)
> >  }
> >
> >  static int array_map_direct_value_addr(const struct bpf_map *map, u64 *imm,
> > @@ -339,7 +344,7 @@ static int array_map_update_elem(struct bpf_map *map, void *key, void *value,
> >                      value, map->value_size);
> >       } else {
> >               val = array->value +
> > -                     array->elem_size * (index & array->index_mask);
> > +                     (u64)array->elem_size * (index & array->index_mask);
> >               if (map_flags & BPF_F_LOCK)
> >                       copy_map_value_locked(map, val, value, false);
> >               else
> > @@ -408,8 +413,7 @@ static void array_map_free_timers(struct bpf_map *map)
> >               return;
> >
> >       for (i = 0; i < array->map.max_entries; i++)
> > -             bpf_timer_cancel_and_free(array->value + array->elem_size * i +
> > -                                       map->timer_off);
> > +             bpf_timer_cancel_and_free(array_map_elem_ptr(array, i) + map->timer_off);
> >  }
> >
> >  /* Called when map->refcnt goes to zero, either from workqueue or from syscall */
> > @@ -420,7 +424,7 @@ static void array_map_free(struct bpf_map *map)
> >
> >       if (map_value_has_kptrs(map)) {
> >               for (i = 0; i < array->map.max_entries; i++)
> > -                     bpf_map_free_kptrs(map, array->value + array->elem_size * i);
> > +                     bpf_map_free_kptrs(map, array_map_elem_ptr(array, i));
>
> This is incorrect. There is no need to mask pointer here.
> There is no security issue here.

Hm.. not sure what happened, but this is not the version of the patch
that I intended to send, sorry about that. I'll resend correct
version.

[PATCH bpf-next 2/4] bpf: make uniform use of array->elem_size everywhere in arraymap.c

[Andrii Nakryiko]

BPF_MAP_TYPE_ARRAY is rounding value_size to closest multiple of 8 and
stores that as array->elem_size for various memory allocations and
accesses.

But the code tends to re-calculate round_up(map->value_size, 8) in
multiple places instead of using array->elem_size. Cleaning this up and
making sure we always use array->size to avoid duplication of this
(admittedly simple) logic for consistency.

Signed-off-by: Andrii Nakryiko <andrii@kernel.org>
---
 kernel/bpf/arraymap.c | 14 ++++++++------
 1 file changed, 8 insertions(+), 6 deletions(-)

diff --git a/kernel/bpf/arraymap.c b/kernel/bpf/arraymap.c
index d3dfc28dbb05..af6b1b528239 100644
--- a/kernel/bpf/arraymap.c
+++ b/kernel/bpf/arraymap.c
@@ -208,7 +208,7 @@ static int array_map_gen_lookup(struct bpf_map *map, struct bpf_insn *insn_buf)
 {
 	struct bpf_array *array = container_of(map, struct bpf_array, map);
 	struct bpf_insn *insn = insn_buf;
-	u32 elem_size = round_up(map->value_size, 8);
+	u32 elem_size = array->elem_size;
 	const int ret = BPF_REG_0;
 	const int map_ptr = BPF_REG_1;
 	const int index = BPF_REG_2;
@@ -277,7 +277,7 @@ int bpf_percpu_array_copy(struct bpf_map *map, void *key, void *value)
 	 * access 'value_size' of them, so copying rounded areas
 	 * will not leak any kernel data
 	 */
-	size = round_up(map->value_size, 8);
+	size = array->elem_size;
 	rcu_read_lock();
 	pptr = array->pptrs[index & array->index_mask];
 	for_each_possible_cpu(cpu) {
@@ -381,7 +381,7 @@ int bpf_percpu_array_update(struct bpf_map *map, void *key, void *value,
 	 * returned or zeros which were zero-filled by percpu_alloc,
 	 * so no kernel data leaks possible
 	 */
-	size = round_up(map->value_size, 8);
+	size = array->elem_size;
 	rcu_read_lock();
 	pptr = array->pptrs[index & array->index_mask];
 	for_each_possible_cpu(cpu) {
@@ -587,6 +587,7 @@ static int __bpf_array_map_seq_show(struct seq_file *seq, void *v)
 	struct bpf_iter_seq_array_map_info *info = seq->private;
 	struct bpf_iter__bpf_map_elem ctx = {};
 	struct bpf_map *map = info->map;
+	struct bpf_array *array = container_of(map, struct bpf_array, map);
 	struct bpf_iter_meta meta;
 	struct bpf_prog *prog;
 	int off = 0, cpu = 0;
@@ -607,7 +608,7 @@ static int __bpf_array_map_seq_show(struct seq_file *seq, void *v)
 			ctx.value = v;
 		} else {
 			pptr = v;
-			size = round_up(map->value_size, 8);
+			size = array->elem_size;
 			for_each_possible_cpu(cpu) {
 				bpf_long_memcpy(info->percpu_value_buf + off,
 						per_cpu_ptr(pptr, cpu),
@@ -637,11 +638,12 @@ static int bpf_iter_init_array_map(void *priv_data,
 {
 	struct bpf_iter_seq_array_map_info *seq_info = priv_data;
 	struct bpf_map *map = aux->map;
+	struct bpf_array *array = container_of(map, struct bpf_array, map);
 	void *value_buf;
 	u32 buf_size;
 
 	if (map->map_type == BPF_MAP_TYPE_PERCPU_ARRAY) {
-		buf_size = round_up(map->value_size, 8) * num_possible_cpus();
+		buf_size = array->elem_size * num_possible_cpus();
 		value_buf = kmalloc(buf_size, GFP_USER | __GFP_NOWARN);
 		if (!value_buf)
 			return -ENOMEM;
@@ -1326,7 +1328,7 @@ static int array_of_map_gen_lookup(struct bpf_map *map,
 				   struct bpf_insn *insn_buf)
 {
 	struct bpf_array *array = container_of(map, struct bpf_array, map);
-	u32 elem_size = round_up(map->value_size, 8);
+	u32 elem_size = array->elem_size;
 	struct bpf_insn *insn = insn_buf;
 	const int ret = BPF_REG_0;
 	const int map_ptr = BPF_REG_1;
-- 
2.30.2

[PATCH bpf-next 3/4] bpf: remove obsolete KMALLOC_MAX_SIZE restriction on array map value size

[Andrii Nakryiko]

Syscall-side map_lookup_elem() and map_update_elem() used to use
kmalloc() to allocate temporary buffers of value_size, so
KMALLOC_MAX_SIZE limit on value_size made sense to prevent creation of
array map that won't be accessible through syscall interface.

But this limitation since has been lifted by relying on kvmalloc() in
syscall handling code. So remove KMALLOC_MAX_SIZE, which among other
things means that it's possible to have BPF global variable sections
(.bss, .data, .rodata) bigger than 8MB now. Keep the sanity check to
prevent trivial overflows like round_up(map->value_size, 8) and restrict
value size to <= INT_MAX (2GB).

Signed-off-by: Andrii Nakryiko <andrii@kernel.org>
---
 kernel/bpf/arraymap.c | 6 ++----
 1 file changed, 2 insertions(+), 4 deletions(-)

diff --git a/kernel/bpf/arraymap.c b/kernel/bpf/arraymap.c
index af6b1b528239..ef3d9ec510a5 100644
--- a/kernel/bpf/arraymap.c
+++ b/kernel/bpf/arraymap.c
@@ -70,10 +70,8 @@ int array_map_alloc_check(union bpf_attr *attr)
 	    attr->map_flags & BPF_F_PRESERVE_ELEMS)
 		return -EINVAL;
 
-	if (attr->value_size > KMALLOC_MAX_SIZE)
-		/* if value_size is bigger, the user space won't be able to
-		 * access the elements.
-		 */
+	/* avoid overflow on round_up(map->value_size) */
+	if (attr->value_size > INT_MAX)
 		return -E2BIG;
 
 	return 0;
-- 
2.30.2

[PATCH bpf-next 4/4] selftests/bpf: validate .bss section bigger than 8MB is possible now

[Andrii Nakryiko]

Add a simple big 16MB array and validate access to the very last byte of
it to make sure that kernel supports > KMALLOC_MAX_SIZE value_size for
BPF array maps (which are backing .bss in this case).

Signed-off-by: Andrii Nakryiko <andrii@kernel.org>
---
 tools/testing/selftests/bpf/prog_tests/skeleton.c | 2 ++
 tools/testing/selftests/bpf/progs/test_skeleton.c | 4 ++++
 2 files changed, 6 insertions(+)

diff --git a/tools/testing/selftests/bpf/prog_tests/skeleton.c b/tools/testing/selftests/bpf/prog_tests/skeleton.c
index 180afd632f4c..99dac5292b41 100644
--- a/tools/testing/selftests/bpf/prog_tests/skeleton.c
+++ b/tools/testing/selftests/bpf/prog_tests/skeleton.c
@@ -122,6 +122,8 @@ void test_skeleton(void)
 
 	ASSERT_EQ(skel->bss->out_mostly_var, 123, "out_mostly_var");
 
+	ASSERT_EQ(bss->huge_arr[ARRAY_SIZE(bss->huge_arr) - 1], 123, "huge_arr");
+
 	elf_bytes = test_skeleton__elf_bytes(&elf_bytes_sz);
 	ASSERT_OK_PTR(elf_bytes, "elf_bytes");
 	ASSERT_GE(elf_bytes_sz, 0, "elf_bytes_sz");
diff --git a/tools/testing/selftests/bpf/progs/test_skeleton.c b/tools/testing/selftests/bpf/progs/test_skeleton.c
index 1b1187d2967b..1a4e93f6d9df 100644
--- a/tools/testing/selftests/bpf/progs/test_skeleton.c
+++ b/tools/testing/selftests/bpf/progs/test_skeleton.c
@@ -51,6 +51,8 @@ int out_dynarr[4] SEC(".data.dyn") = { 1, 2, 3, 4 };
 int read_mostly_var __read_mostly;
 int out_mostly_var;
 
+char huge_arr[16 * 1024 * 1024];
+
 SEC("raw_tp/sys_enter")
 int handler(const void *ctx)
 {
@@ -71,6 +73,8 @@ int handler(const void *ctx)
 
 	out_mostly_var = read_mostly_var;
 
+	huge_arr[sizeof(huge_arr) - 1] = 123;
+
 	return 0;
 }
 
-- 
2.30.2