Re: [PATCH bpf-next v2 3/3] bpf/verifier: Take advantage of full allocation sizes

[Stanislav Fomichev]

On Fri, Oct 28, 2022 at 7:54 PM Kees Cook <keescook@xxxxxxxxxxxx> wrote:
>
> Since the full kmalloc bucket size is being explicitly allocated, pass
> back the resulting details to take advantage of the full size so that
> reallocation checking will be needed less frequently.
>
> Cc: Alexei Starovoitov <ast@xxxxxxxxxx>
> Cc: Daniel Borkmann <daniel@xxxxxxxxxxxxx>
> Cc: John Fastabend <john.fastabend@xxxxxxxxx>
> Cc: Andrii Nakryiko <andrii@xxxxxxxxxx>
> Cc: Martin KaFai Lau <martin.lau@xxxxxxxxx>
> Cc: Song Liu <song@xxxxxxxxxx>
> Cc: Yonghong Song <yhs@xxxxxx>
> Cc: KP Singh <kpsingh@xxxxxxxxxx>
> Cc: Stanislav Fomichev <sdf@xxxxxxxxxx>
> Cc: Hao Luo <haoluo@xxxxxxxxxx>
> Cc: Jiri Olsa <jolsa@xxxxxxxxxx>
> Cc: bpf@xxxxxxxxxxxxxxx
> Signed-off-by: Kees Cook <keescook@xxxxxxxxxxxx>
> ---
>  kernel/bpf/verifier.c | 27 ++++++++++++++++-----------
>  1 file changed, 16 insertions(+), 11 deletions(-)
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 1c040d27b8f6..e58b554e862b 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -1020,20 +1020,23 @@ static void *copy_array(void *dst, const void *src, size_t n, size_t size, gfp_t
>         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)
>  {
>         size_t alloc_size;
>         void *new_arr;
>
> -       if (!new_n || old_n == new_n)
> +       if (!new_n || !*new_n || old_n == *new_n)
>                 goto out;
>
> -       alloc_size = kmalloc_size_roundup(size_mul(new_n, size));
> +       alloc_size = kmalloc_size_roundup(size_mul(*new_n, size));
>         new_arr = krealloc(arr, alloc_size, GFP_KERNEL);
>         if (!new_arr) {
>                 kfree(arr);
> @@ -1041,8 +1044,9 @@ static void *realloc_array(void *arr, size_t old_n, size_t new_n, size_t size)
>         }
>         arr = new_arr;
>
> -       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;

[..]

> @@ -1074,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;

Patches 1 & 2 look good, but not sure about this part. We later do the
following in the same routine:

state->acquired_refs = n;

And acquire_reference_state() does "new_ofs = state->acquired_refs;" to append..

Which changes semantics a bit? It used to mean array size, now it
means array capacity.
Should we keep this part as is but add a shortcut to realloc_array
when ksize(ptr) == kmalloc_size_roundup(new size) -> reuse existing
array?
Or am I missing something? (haven't looked too deep)





> @@ -1090,11 +1094,12 @@ 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;
>  }
>
> --
> 2.34.1
>