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

  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@kernel.org>
Cc: Daniel Borkmann <daniel@iogearbox.net>
Cc: John Fastabend <john.fastabend@gmail.com>
Cc: Andrii Nakryiko <andrii@kernel.org>
Cc: Martin KaFai Lau <martin.lau@linux.dev>
Cc: Song Liu <song@kernel.org>
Cc: Yonghong Song <yhs@fb.com>
Cc: KP Singh <kpsingh@kernel.org>
Cc: Stanislav Fomichev <sdf@google.com>
Cc: Hao Luo <haoluo@google.com>
Cc: Jiri Olsa <jolsa@kernel.org>
Cc: bpf@vger.kernel.org
Signed-off-by: Kees Cook <keescook@chromium.org>
---
 kernel/bpf/verifier.c | 27 ++++++++++++++++-----------
 1 file changed, 16 insertions(+), 11 deletions(-)
  

On Fri, Oct 28, 2022 at 7:54 PM Kees Cook <keescook@chromium.org> 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@kernel.org>
> Cc: Daniel Borkmann <daniel@iogearbox.net>
> Cc: John Fastabend <john.fastabend@gmail.com>
> Cc: Andrii Nakryiko <andrii@kernel.org>
> Cc: Martin KaFai Lau <martin.lau@linux.dev>
> Cc: Song Liu <song@kernel.org>
> Cc: Yonghong Song <yhs@fb.com>
> Cc: KP Singh <kpsingh@kernel.org>
> Cc: Stanislav Fomichev <sdf@google.com>
> Cc: Hao Luo <haoluo@google.com>
> Cc: Jiri Olsa <jolsa@kernel.org>
> Cc: bpf@vger.kernel.org
> Signed-off-by: Kees Cook <keescook@chromium.org>
> ---
>  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
>
  

On Mon, Oct 31, 2022 at 02:53:35PM -0700, Stanislav Fomichev wrote:
> On Fri, Oct 28, 2022 at 7:54 PM Kees Cook <keescook@chromium.org> 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@kernel.org>
> > Cc: Daniel Borkmann <daniel@iogearbox.net>
> > Cc: John Fastabend <john.fastabend@gmail.com>
> > Cc: Andrii Nakryiko <andrii@kernel.org>
> > Cc: Martin KaFai Lau <martin.lau@linux.dev>
> > Cc: Song Liu <song@kernel.org>
> > Cc: Yonghong Song <yhs@fb.com>
> > Cc: KP Singh <kpsingh@kernel.org>
> > Cc: Stanislav Fomichev <sdf@google.com>
> > Cc: Hao Luo <haoluo@google.com>
> > Cc: Jiri Olsa <jolsa@kernel.org>
> > Cc: bpf@vger.kernel.org
> > Signed-off-by: Kees Cook <keescook@chromium.org>
> > ---
> >  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:

I'm totally fine leaving off #3. 1 is a bug fix, 2 is what I need to get
the ksize side-effect managed in bpf, and 3 was maybe an optimization.