Skip to contentSkip to conversation

bpf: Use kmalloc_size_roundup() to match ksize() usage

PATCH In review Kees Cook 2 participants 5 messages Oct 18, 2022 – Oct 28, 2022

Subsystems (2)
lore
Share & tools
lore

Kees Cook

author
#0 lore raw

PATCH 1/1 bpf: Use kmalloc_size_roundup() to match ksize() usage

Round up allocations with kmalloc_size_roundup() so that the verifier's use of ksize() is always accurate and no special handling of the memory is needed by KASAN, UBSAN_BOUNDS, nor FORTIFY_SOURCE. Pass the new size information back up to callers so they can use the space immediately, so array resizing to happen less frequently as well. Explicitly zero any trailing bytes in new allocations.

Additionally fix a memory allocation leak: if krealloc() fails, "arr" wasn't freed, but NULL was return to the caller of realloc_array() would be writing NULL to the lvalue, losing the reference to the original memory.

Cc Alexei Starovoitov <[email protected]>
Cc Daniel Borkmann <[email protected]>
Cc John Fastabend <[email protected]>
Cc Andrii Nakryiko <[email protected]>
Cc Martin KaFai Lau <[email protected]>
Cc Song Liu <[email protected]>
Cc Yonghong Song <[email protected]>
Cc KP Singh <[email protected]>
Cc Stanislav Fomichev <[email protected]>
Cc Hao Luo <[email protected]>
Cc Jiri Olsa <[email protected]>
---
 kernel/bpf/verifier.c | 49 +++++++++++++++++++++++++++----------------
 1 file changed, 31 insertions(+), 18 deletions(-)
kernel/bpf/verifier.c +31 -18
index 014ee0953dbd..8a0b60207d0e 100644
@@ -1000,42 +1000,53 @@ static void print_insn_state(struct bpf_verifier_env *env,
  */
 static void *copy_array(void *dst, const void *src, size_t n, size_t size, gfp_t flags)
 {
-	size_t bytes;
+	size_t src_bytes, dst_bytes;
 
 	if (ZERO_OR_NULL_PTR(src))
 		goto out;
 
-	if (unlikely(check_mul_overflow(n, size, &bytes)))
+	if (unlikely(check_mul_overflow(n, size, &src_bytes)))
 		return NULL;
 
-	if (ksize(dst) < bytes) {
+	dst_bytes = kmalloc_size_roundup(src_bytes);
+	if (ksize(dst) < dst_bytes) {
 		kfree(dst);
-		dst = kmalloc_track_caller(bytes, flags);
+		dst = kmalloc_track_caller(dst_bytes, flags);
 		if (!dst)
 			return NULL;
 	}
 
-	memcpy(dst, src, bytes);
+	memcpy(dst, src, src_bytes);
+	memset(dst + src_bytes, 0, dst_bytes - src_bytes);
 out:
 	return dst ? dst : ZERO_SIZE_PTR;
 }
 
-/* resize an array from old_n items to new_n items. the array is reallocated if it's too
- * small to hold new_n items. new items are zeroed out if the array grows.
+/* Resize an array from old_n items to *new_n items. The array is reallocated if it's too
+ * small to hold *new_n items. New items are zeroed out if the array grows. Allocation
+ * is rounded up to next kmalloc bucket size to reduce frequency of resizing. *new_n
+ * contains the new total number of items that will fit.
  *
- * Contrary to krealloc_array, does not free arr if new_n is zero.
+ * Contrary to krealloc, does not free arr if new_n is zero.
  */
-static void *realloc_array(void *arr, size_t old_n, size_t new_n, size_t size)
+static void *realloc_array(void *arr, size_t old_n, size_t *new_n, size_t size)
 {
-	if (!new_n || old_n == new_n)
+	void *old_arr = arr;
+	size_t alloc_size;
+
+	if (!new_n || !*new_n || old_n == *new_n)
 		goto out;
 
-	arr = krealloc_array(arr, new_n, size, GFP_KERNEL);
-	if (!arr)
+	alloc_size = kmalloc_size_roundup(size_mul(*new_n, size));
+	arr = krealloc(old_arr, alloc_size, GFP_KERNEL);
+	if (!arr) {
+		kfree(old_arr);
 		return NULL;
+	}
 
-	if (new_n > old_n)
-		memset(arr + old_n * size, 0, (new_n - old_n) * size);
+	*new_n = alloc_size / size;
+	if (*new_n > old_n)
+		memset(arr + old_n * size, 0, (*new_n - old_n) * size);
 
 out:
 	return arr ? arr : ZERO_SIZE_PTR;
@@ -1067,7 +1078,7 @@ static int copy_stack_state(struct bpf_func_state *dst, const struct bpf_func_st
 
 static int resize_reference_state(struct bpf_func_state *state, size_t n)
 {
-	state->refs = realloc_array(state->refs, state->acquired_refs, n,
+	state->refs = realloc_array(state->refs, state->acquired_refs, &n,
 				    sizeof(struct bpf_reference_state));
 	if (!state->refs)
 		return -ENOMEM;
@@ -1083,11 +1094,11 @@ static int grow_stack_state(struct bpf_func_state *state, int size)
 	if (old_n >= n)
 		return 0;
 
-	state->stack = realloc_array(state->stack, old_n, n, sizeof(struct bpf_stack_state));
+	state->stack = realloc_array(state->stack, old_n, &n, sizeof(struct bpf_stack_state));
 	if (!state->stack)
 		return -ENOMEM;
 
-	state->allocated_stack = size;
+	state->allocated_stack = n * BPF_REG_SIZE;
 	return 0;
 }
 
@@ -2499,9 +2510,11 @@ static int push_jmp_history(struct bpf_verifier_env *env,
 {
 	u32 cnt = cur->jmp_history_cnt;
 	struct bpf_idx_pair *p;
+	size_t size;
 
 	cnt++;
-	p = krealloc(cur->jmp_history, cnt * sizeof(*p), GFP_USER);
+	size = kmalloc_size_roundup(size_mul(cnt, sizeof(*p)));
+	p = krealloc(cur->jmp_history, size, GFP_USER);
 	if (!p)
 		return -ENOMEM;
 	p[cnt - 1].idx = env->insn_idx;
Signature · 1 line
2.34.1
#1 lore raw
Quoted 42 lines · Kees Cook

Round up allocations with kmalloc_size_roundup() so that the verifier's use of ksize() is always accurate and no special handling of the memory is needed by KASAN, UBSAN_BOUNDS, nor FORTIFY_SOURCE. Pass the new size information back up to callers so they can use the space immediately, so array resizing to happen less frequently as well. Explicitly zero any trailing bytes in new allocations.

Additionally fix a memory allocation leak: if krealloc() fails, "arr" wasn't freed, but NULL was return to the caller of realloc_array() would be writing NULL to the lvalue, losing the reference to the original memory.

Cc Alexei Starovoitov <[email protected]>
Cc Daniel Borkmann <[email protected]>
Cc John Fastabend <[email protected]>
Cc Andrii Nakryiko <[email protected]>
Cc Martin KaFai Lau <[email protected]>
Cc Song Liu <[email protected]>
Cc Yonghong Song <[email protected]>
Cc KP Singh <[email protected]>
Cc Stanislav Fomichev <[email protected]>
Cc Hao Luo <[email protected]>
Cc Jiri Olsa <[email protected]>
---
  kernel/bpf/verifier.c | 49 +++++++++++++++++++++++++++----------------
  1 file changed, 31 insertions(+), 18 deletions(-)
kernel/bpf/verifier.c +1 -1
index 014ee0953dbd..8a0b60207d0e 100644
@@ -1000,42 +1000,53 @@ static void print_insn_state(struct  
 bpf_verifier_env *env,
   */
  static void *copy_array(void *dst, const void *src, size_t n, size_t  
 size, gfp_t flags)
  {
-	size_t bytes;
+	size_t src_bytes, dst_bytes;
 

kernel/bpf/verifier.c static void print_insn_state(struct · line 1014

Quoted 10 lines
kernel/bpf/verifier.c +3 -2
  	if (ZERO_OR_NULL_PTR(src))
  		goto out;
 
-	if (unlikely(check_mul_overflow(n, size, &bytes)))
+	if (unlikely(check_mul_overflow(n, size, &src_bytes)))
  		return NULL;
 
-	if (ksize(dst) < bytes) {
+	dst_bytes = kmalloc_size_roundup(src_bytes);
+	if (ksize(dst) < dst_bytes) {

Why not simply do the following here?

	if (ksize(dst) < ksize(src)) {

?

It seems like we care about src_bytes/bytes only in this case, so maybe move that check_mul_overflow under this branch as well?

Quoted 40 lines
kernel/bpf/verifier.c +3 -3
  		kfree(dst);
-		dst = kmalloc_track_caller(bytes, flags);
+		dst = kmalloc_track_caller(dst_bytes, flags);
  		if (!dst)
  			return NULL;
  	}
 
-	memcpy(dst, src, bytes);
+	memcpy(dst, src, src_bytes);
+	memset(dst + src_bytes, 0, dst_bytes - src_bytes);
  out:
  	return dst ? dst : ZERO_SIZE_PTR;
  }
 
-/* resize an array from old_n items to new_n items. the array is  

reallocated if it's too
- * small to hold new_n items. new items are zeroed out if the array grows.
+/* Resize an array from old_n items to *new_n items. The array is reallocated if it's too
+ * small to hold *new_n items. New items are zeroed out if the array grows. Allocation
+ * is rounded up to next kmalloc bucket size to reduce frequency of resizing. *new_n
+ * contains the new total number of items that will fit.
*
- * Contrary to krealloc_array, does not free arr if new_n is zero.
+ * Contrary to krealloc, does not free arr if new_n is zero. */
-static void *realloc_array(void *arr, size_t old_n, size_t new_n, size_t size)
+static void *realloc_array(void *arr, size_t old_n, size_t *new_n, size_t size)
{

kernel/bpf/verifier.c +4 -1
-	if (!new_n || old_n == new_n)
+	void *old_arr = arr;
+	size_t alloc_size;
+
+	if (!new_n || !*new_n || old_n == *new_n)
  		goto out;

[..]

kernel/bpf/verifier.c static void print_insn_state(struct bpf_verifier_env *env, · line 1045

Quoted 8 lines
kernel/bpf/verifier.c +5 -2
-	arr = krealloc_array(arr, new_n, size, GFP_KERNEL);
-	if (!arr)
+	alloc_size = kmalloc_size_roundup(size_mul(*new_n, size));
+	arr = krealloc(old_arr, alloc_size, GFP_KERNEL);
+	if (!arr) {
+		kfree(old_arr);
  		return NULL;
+	}

Any reason not do hide this complexity behind krealloc_array? Why can't it take care of those roundup details?

Quoted 51 lines
kernel/bpf/verifier.c +4 -3
-	if (new_n > old_n)
-		memset(arr + old_n * size, 0, (new_n - old_n) * size);
+	*new_n = alloc_size / size;
+	if (*new_n > old_n)
+		memset(arr + old_n * size, 0, (*new_n - old_n) * size);
 
  out:
  	return arr ? arr : ZERO_SIZE_PTR;
@@ -1067,7 +1078,7 @@ static int copy_stack_state(struct bpf_func_state  
 *dst, const struct bpf_func_st
 
  static int resize_reference_state(struct bpf_func_state *state, size_t n)
  {
-	state->refs = realloc_array(state->refs, state->acquired_refs, n,
+	state->refs = realloc_array(state->refs, state->acquired_refs, &n,
  				    sizeof(struct bpf_reference_state));
  	if (!state->refs)

return -ENOMEM;

kernel/bpf/verifier.c +2 -2
@@ -1083,11 +1094,11 @@ static int grow_stack_state(struct bpf_func_state  
 *state, int size)
  	if (old_n >= n)
  		return 0;
 
-	state->stack = realloc_array(state->stack, old_n, n, sizeof(struct  
 bpf_stack_state));
+	state->stack = realloc_array(state->stack, old_n, &n, sizeof(struct  
 bpf_stack_state));
  	if (!state->stack)
  		return -ENOMEM;
 
-	state->allocated_stack = size;
+	state->allocated_stack = n * BPF_REG_SIZE;
  	return 0;
  }
kernel/bpf/verifier.c +3 -1
@@ -2499,9 +2510,11 @@ static int push_jmp_history(struct  
 bpf_verifier_env *env,
  {
  	u32 cnt = cur->jmp_history_cnt;
  	struct bpf_idx_pair *p;
+	size_t size;
 
  	cnt++;
-	p = krealloc(cur->jmp_history, cnt * sizeof(*p), GFP_USER);
+	size = kmalloc_size_roundup(size_mul(cnt, sizeof(*p)));
+	p = krealloc(cur->jmp_history, size, GFP_USER);
  	if (!p)
  		return -ENOMEM;

p[cnt - 1].idx = env->insn_idx;
--
2.34.1

author
#2 lore raw
Quoted 56 lines · On Tue, Oct 18, 2022 at 11:07:38AM -0700, [email protected] wrote:
Quoted 42 lines · Kees Cook

Round up allocations with kmalloc_size_roundup() so that the verifier's use of ksize() is always accurate and no special handling of the memory is needed by KASAN, UBSAN_BOUNDS, nor FORTIFY_SOURCE. Pass the new size information back up to callers so they can use the space immediately, so array resizing to happen less frequently as well. Explicitly zero any trailing bytes in new allocations.

Additionally fix a memory allocation leak: if krealloc() fails, "arr" wasn't freed, but NULL was return to the caller of realloc_array() would be writing NULL to the lvalue, losing the reference to the original memory.

Cc Alexei Starovoitov <[email protected]>
Cc Daniel Borkmann <[email protected]>
Cc John Fastabend <[email protected]>
Cc Andrii Nakryiko <[email protected]>
Cc Martin KaFai Lau <[email protected]>
Cc Song Liu <[email protected]>
Cc Yonghong Song <[email protected]>
Cc KP Singh <[email protected]>
Cc Stanislav Fomichev <[email protected]>
Cc Hao Luo <[email protected]>
Cc Jiri Olsa <[email protected]>
---
  kernel/bpf/verifier.c | 49 +++++++++++++++++++++++++++----------------
  1 file changed, 31 insertions(+), 18 deletions(-)
kernel/bpf/verifier.c +1 -1
index 014ee0953dbd..8a0b60207d0e 100644
@@ -1000,42 +1000,53 @@ static void print_insn_state(struct
 bpf_verifier_env *env,
   */
  static void *copy_array(void *dst, const void *src, size_t n, size_t
 size, gfp_t flags)
  {
-	size_t bytes;
+	size_t src_bytes, dst_bytes;
 

kernel/bpf/verifier.c static void print_insn_state(struct · line 1014

Quoted 10 lines
kernel/bpf/verifier.c +3 -2
  	if (ZERO_OR_NULL_PTR(src))
  		goto out;
 
-	if (unlikely(check_mul_overflow(n, size, &bytes)))
+	if (unlikely(check_mul_overflow(n, size, &src_bytes)))
  		return NULL;
 
-	if (ksize(dst) < bytes) {
+	dst_bytes = kmalloc_size_roundup(src_bytes);
+	if (ksize(dst) < dst_bytes) {

Why not simply do the following here?

Quoted 3 lines
	if (ksize(dst) < ksize(src)) {

?

Yeah, if src always passes through rounding-up allocation path, that might work. I need to double-check that there isn't a case where "size" makes this go weird -- e.g. a rounded up "src" may be larger than "n * size", but I think that's okay because the memcpy/memset does the right thing.

Quoted 48 lines

It seems like we care about src_bytes/bytes only in this case, so maybe move that check_mul_overflow under this branch as well?

Quoted 40 lines
kernel/bpf/verifier.c +3 -3
  		kfree(dst);
-		dst = kmalloc_track_caller(bytes, flags);
+		dst = kmalloc_track_caller(dst_bytes, flags);
  		if (!dst)
  			return NULL;
  	}
 
-	memcpy(dst, src, bytes);
+	memcpy(dst, src, src_bytes);
+	memset(dst + src_bytes, 0, dst_bytes - src_bytes);
  out:
  	return dst ? dst : ZERO_SIZE_PTR;
  }
 
-/* resize an array from old_n items to new_n items. the array is

reallocated if it's too
- * small to hold new_n items. new items are zeroed out if the array grows.
+/* Resize an array from old_n items to *new_n items. The array is reallocated if it's too
+ * small to hold *new_n items. New items are zeroed out if the array grows. Allocation
+ * is rounded up to next kmalloc bucket size to reduce frequency of resizing. *new_n
+ * contains the new total number of items that will fit. *
- * Contrary to krealloc_array, does not free arr if new_n is zero.
+ * Contrary to krealloc, does not free arr if new_n is zero. */
-static void *realloc_array(void *arr, size_t old_n, size_t new_n, size_t size)
+static void *realloc_array(void *arr, size_t old_n, size_t *new_n, size_t size)
{

kernel/bpf/verifier.c +4 -1
-	if (!new_n || old_n == new_n)
+	void *old_arr = arr;
+	size_t alloc_size;
+
+	if (!new_n || !*new_n || old_n == *new_n)
  		goto out;

[..]

Quoted 11 lines

kernel/bpf/verifier.c static void print_insn_state(struct bpf_verifier_env *env, · line 1045

Quoted 8 lines
kernel/bpf/verifier.c +5 -2
-	arr = krealloc_array(arr, new_n, size, GFP_KERNEL);
-	if (!arr)
+	alloc_size = kmalloc_size_roundup(size_mul(*new_n, size));
+	arr = krealloc(old_arr, alloc_size, GFP_KERNEL);
+	if (!arr) {
+		kfree(old_arr);
  		return NULL;
+	}

Any reason not do hide this complexity behind krealloc_array? Why can't it take care of those roundup details?

It might be possible to do this with a macro, yes, but then callers aren't in a position to take advantage of the new size. Maybe we need something like:

	arr = krealloc_up(old_arr, alloc_size, &new_size, GFP_KERNEL);

Thanks for looking this over!

Signature · 1 line
Kees Cook
#3 lore raw
Quoted 125 lines · Kees Cook
Quoted 54 lines · On Tue, Oct 18, 2022 at 11:07:38AM -0700, [email protected] wrote:
Quoted 42 lines · Kees Cook

Round up allocations with kmalloc_size_roundup() so that the verifier's use of ksize() is always accurate and no special handling of the memory is needed by KASAN, UBSAN_BOUNDS, nor FORTIFY_SOURCE. Pass the new size information back up to callers so they can use the space immediately, so array resizing to happen less frequently as well. Explicitly zero any trailing bytes in new allocations.

Additionally fix a memory allocation leak: if krealloc() fails, "arr" wasn't freed, but NULL was return to the caller of realloc_array() would be writing NULL to the lvalue, losing the reference to the original memory.

Cc Alexei Starovoitov <[email protected]>
Cc Daniel Borkmann <[email protected]>
Cc John Fastabend <[email protected]>
Cc Andrii Nakryiko <[email protected]>
Cc Martin KaFai Lau <[email protected]>
Cc Song Liu <[email protected]>
Cc Yonghong Song <[email protected]>
Cc KP Singh <[email protected]>
Cc Stanislav Fomichev <[email protected]>
Cc Hao Luo <[email protected]>
Cc Jiri Olsa <[email protected]>
---
  kernel/bpf/verifier.c | 49 +++++++++++++++++++++++++++----------------
  1 file changed, 31 insertions(+), 18 deletions(-)
kernel/bpf/verifier.c +1 -1
index 014ee0953dbd..8a0b60207d0e 100644
@@ -1000,42 +1000,53 @@ static void print_insn_state(struct
 bpf_verifier_env *env,
   */
  static void *copy_array(void *dst, const void *src, size_t n, size_t
 size, gfp_t flags)
  {
-   size_t bytes;
+   size_t src_bytes, dst_bytes;
 

kernel/bpf/verifier.c static void print_insn_state(struct · line 1014

Quoted 10 lines
kernel/bpf/verifier.c +3 -2
    if (ZERO_OR_NULL_PTR(src))
            goto out;
 
-   if (unlikely(check_mul_overflow(n, size, &bytes)))
+   if (unlikely(check_mul_overflow(n, size, &src_bytes)))
            return NULL;
 
-   if (ksize(dst) < bytes) {
+   dst_bytes = kmalloc_size_roundup(src_bytes);
+   if (ksize(dst) < dst_bytes) {
Quoted 5 lines

Why not simply do the following here?

      if (ksize(dst) < ksize(src)) {

?

Yeah, if src always passes through rounding-up allocation path, that might work. I need to double-check that there isn't a case where "size" makes this go weird -- e.g. a rounded up "src" may be larger than "n * size", but I think that's okay because the memcpy/memset does the right thing.

Quoted 57 lines

It seems like we care about src_bytes/bytes only in this case, so maybe move that check_mul_overflow under this branch as well?

Quoted 40 lines
kernel/bpf/verifier.c +3 -3
            kfree(dst);
-           dst = kmalloc_track_caller(bytes, flags);
+           dst = kmalloc_track_caller(dst_bytes, flags);
            if (!dst)
                    return NULL;
    }
 
-   memcpy(dst, src, bytes);
+   memcpy(dst, src, src_bytes);
+   memset(dst + src_bytes, 0, dst_bytes - src_bytes);
  out:
    return dst ? dst : ZERO_SIZE_PTR;
  }
 
-/* resize an array from old_n items to new_n items. the array is

reallocated if it's too
- * small to hold new_n items. new items are zeroed out if the array grows.
+/* Resize an array from old_n items to *new_n items. The array is reallocated if it's too
+ * small to hold *new_n items. New items are zeroed out if the array grows. Allocation
+ * is rounded up to next kmalloc bucket size to reduce frequency of resizing. *new_n
+ * contains the new total number of items that will fit. *
- * Contrary to krealloc_array, does not free arr if new_n is zero.
+ * Contrary to krealloc, does not free arr if new_n is zero. */
-static void *realloc_array(void *arr, size_t old_n, size_t new_n, size_t size)
+static void *realloc_array(void *arr, size_t old_n, size_t *new_n, size_t size)
{

kernel/bpf/verifier.c +4 -1
-   if (!new_n || old_n == new_n)
+   void *old_arr = arr;
+   size_t alloc_size;
+
+   if (!new_n || !*new_n || old_n == *new_n)
            goto out;

[..]

Quoted 8 lines
kernel/bpf/verifier.c +5 -2
-   arr = krealloc_array(arr, new_n, size, GFP_KERNEL);
-   if (!arr)
+   alloc_size = kmalloc_size_roundup(size_mul(*new_n, size));
+   arr = krealloc(old_arr, alloc_size, GFP_KERNEL);
+   if (!arr) {
+           kfree(old_arr);
            return NULL;
+   }
Quoted 8 lines
Quoted 2 lines

Any reason not do hide this complexity behind krealloc_array? Why can't it take care of those roundup details?

It might be possible to do this with a macro, yes, but then callers aren't in a position to take advantage of the new size. Maybe we need something like:

        arr = krealloc_up(old_arr, alloc_size, &new_size, GFP_KERNEL);

Maybe even krealloc_array_up(arr, &new_n, size, flags) or similar where we return a new size?
Though I don't know if there are any other places in the kernel to reuse it and warrant a new function..

Quoted 4 lines

Thanks for looking this over!

--
Kees Cook

Quoted 138 lines · Kees Cook
Quoted 54 lines · On Tue, Oct 18, 2022 at 11:07:38AM -0700, [email protected] wrote:
Quoted 42 lines · Kees Cook

Round up allocations with kmalloc_size_roundup() so that the verifier's use of ksize() is always accurate and no special handling of the memory is needed by KASAN, UBSAN_BOUNDS, nor FORTIFY_SOURCE. Pass the new size information back up to callers so they can use the space immediately, so array resizing to happen less frequently as well. Explicitly zero any trailing bytes in new allocations.

Additionally fix a memory allocation leak: if krealloc() fails, "arr" wasn't freed, but NULL was return to the caller of realloc_array() would be writing NULL to the lvalue, losing the reference to the original memory.

Cc Alexei Starovoitov <[email protected]>
Cc Daniel Borkmann <[email protected]>
Cc John Fastabend <[email protected]>
Cc Andrii Nakryiko <[email protected]>
Cc Martin KaFai Lau <[email protected]>
Cc Song Liu <[email protected]>
Cc Yonghong Song <[email protected]>
Cc KP Singh <[email protected]>
Cc Stanislav Fomichev <[email protected]>
Cc Hao Luo <[email protected]>
Cc Jiri Olsa <[email protected]>
---
  kernel/bpf/verifier.c | 49 +++++++++++++++++++++++++++----------------
  1 file changed, 31 insertions(+), 18 deletions(-)
kernel/bpf/verifier.c +1 -1
index 014ee0953dbd..8a0b60207d0e 100644
@@ -1000,42 +1000,53 @@ static void print_insn_state(struct
 bpf_verifier_env *env,
   */
  static void *copy_array(void *dst, const void *src, size_t n, size_t
 size, gfp_t flags)
  {
-   size_t bytes;
+   size_t src_bytes, dst_bytes;
 

kernel/bpf/verifier.c static void print_insn_state(struct · line 1014

Quoted 10 lines
kernel/bpf/verifier.c +3 -2
    if (ZERO_OR_NULL_PTR(src))
            goto out;
 
-   if (unlikely(check_mul_overflow(n, size, &bytes)))
+   if (unlikely(check_mul_overflow(n, size, &src_bytes)))
            return NULL;
 
-   if (ksize(dst) < bytes) {
+   dst_bytes = kmalloc_size_roundup(src_bytes);
+   if (ksize(dst) < dst_bytes) {
Quoted 5 lines

Why not simply do the following here?

      if (ksize(dst) < ksize(src)) {

?

Yeah, if src always passes through rounding-up allocation path, that might work. I need to double-check that there isn't a case where "size" makes this go weird -- e.g. a rounded up "src" may be larger than "n * size", but I think that's okay because the memcpy/memset does the right thing.

Quoted 57 lines

It seems like we care about src_bytes/bytes only in this case, so maybe move that check_mul_overflow under this branch as well?

Quoted 40 lines
kernel/bpf/verifier.c +3 -3
            kfree(dst);
-           dst = kmalloc_track_caller(bytes, flags);
+           dst = kmalloc_track_caller(dst_bytes, flags);
            if (!dst)
                    return NULL;
    }
 
-   memcpy(dst, src, bytes);
+   memcpy(dst, src, src_bytes);
+   memset(dst + src_bytes, 0, dst_bytes - src_bytes);
  out:
    return dst ? dst : ZERO_SIZE_PTR;
  }
 
-/* resize an array from old_n items to new_n items. the array is

reallocated if it's too
- * small to hold new_n items. new items are zeroed out if the array grows.
+/* Resize an array from old_n items to *new_n items. The array is reallocated if it's too
+ * small to hold *new_n items. New items are zeroed out if the array grows. Allocation
+ * is rounded up to next kmalloc bucket size to reduce frequency of resizing. *new_n
+ * contains the new total number of items that will fit. *
- * Contrary to krealloc_array, does not free arr if new_n is zero.
+ * Contrary to krealloc, does not free arr if new_n is zero. */
-static void *realloc_array(void *arr, size_t old_n, size_t new_n, size_t size)
+static void *realloc_array(void *arr, size_t old_n, size_t *new_n, size_t size)
{

kernel/bpf/verifier.c +4 -1
-   if (!new_n || old_n == new_n)
+   void *old_arr = arr;
+   size_t alloc_size;
+
+   if (!new_n || !*new_n || old_n == *new_n)
            goto out;

[..]

kernel/bpf/verifier.c static void print_insn_state(struct bpf_verifier_env *env, · line 1045

Quoted 8 lines
kernel/bpf/verifier.c +5 -2
-   arr = krealloc_array(arr, new_n, size, GFP_KERNEL);
-   if (!arr)
+   alloc_size = kmalloc_size_roundup(size_mul(*new_n, size));
+   arr = krealloc(old_arr, alloc_size, GFP_KERNEL);
+   if (!arr) {
+           kfree(old_arr);
            return NULL;
+   }
Quoted 2 lines

Any reason not do hide this complexity behind krealloc_array? Why can't it take care of those roundup details?

It might be possible to do this with a macro, yes, but then callers aren't in a position to take advantage of the new size. Maybe we need something like:

        arr = krealloc_up(old_arr, alloc_size, &new_size, GFP_KERNEL);

Thanks for looking this over!

--
Kees Cook

author
#4 lore raw
Quoted 32 lines · Stanislav Fomichev
Quoted 14 lines · Kees Cook
Quoted 12 lines · On Tue, Oct 18, 2022 at 11:07:38AM -0700, [email protected] wrote:
Quoted 11 lines · Kees Cook

Round up allocations with kmalloc_size_roundup() so that the verifier's use of ksize() is always accurate and no special handling of the memory is needed by KASAN, UBSAN_BOUNDS, nor FORTIFY_SOURCE. Pass the new size information back up to callers so they can use the space immediately, so array resizing to happen less frequently as well. Explicitly zero any trailing bytes in new allocations.

Additionally fix a memory allocation leak: if krealloc() fails, "arr" wasn't freed, but NULL was return to the caller of realloc_array() would be writing NULL to the lvalue, losing the reference to the original memory.

[...]

Quoted 16 lines
Quoted 11 lines

kernel/bpf/verifier.c static void print_insn_state(struct bpf_verifier_env *env, · line 1045

Quoted 8 lines
kernel/bpf/verifier.c +5 -2
-   arr = krealloc_array(arr, new_n, size, GFP_KERNEL);
-   if (!arr)
+   alloc_size = kmalloc_size_roundup(size_mul(*new_n, size));
+   arr = krealloc(old_arr, alloc_size, GFP_KERNEL);
+   if (!arr) {
+           kfree(old_arr);
            return NULL;
+   }

Any reason not do hide this complexity behind krealloc_array? Why can't it take care of those roundup details?

It might be possible to do this with a macro, yes, but then callers aren't in a position to take advantage of the new size. Maybe we need something like:

Quoted 6 lines
Quoted 1 line
        arr = krealloc_up(old_arr, alloc_size, &new_size, GFP_KERNEL);

Maybe even krealloc_array_up(arr, &new_n, size, flags) or similar where we return a new size?
Though I don't know if there are any other places in the kernel to reuse it and warrant a new function..

Yeah, and it explicitly can't be a function, since GCC has broken attribute handling[1] for inlines. :(

Regardless, I'll respin this with a macro and see how it looks.

-Kees

[1] https://gcc.gnu.org/bugzilla/show_bug.cgi?id=96503

Signature · 1 line
Kees Cook