Libguestfs - Nov 2021 - [libnbd PATCH] common/utils/vector: Better overflow handling

Check newcap * itemsize for overflow prior to calling realloc, so that
we don't accidentally truncate an existing array.  Set errno to ENOMEM
on all failure paths, rather than leaving it indeterminate on
overflow.  The patch works by assuming a prerequisite that
v->cap*itemsize is always smaller than size_t.

Fixes: 985dfa72ae (common/utils/vector.c: Optimize vector append)
---

Unless you see problems in this, I'll push this and also port it to
nbdkit.

 common/utils/vector.c | 8 +++++---
 1 file changed, 5 insertions(+), 3 deletions(-)

diff --git a/common/utils/vector.c b/common/utils/vector.c
index a4b43ce..c37f0c3 100644
--- a/common/utils/vector.c
+++ b/common/utils/vector.c
@@ -1,5 +1,5 @@
 /* nbdkit
- * Copyright (C) 2018-2020 Red Hat Inc.
+ * Copyright (C) 2018-2021 Red Hat Inc.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions are
@@ -44,12 +44,14 @@ generic_vector_reserve (struct generic_vector *v, size_t n,
size_t itemsize)
   size_t reqcap, newcap;

   reqcap = v->cap + n;
-  if (reqcap < v->cap)
+  if (reqcap * itemsize < v->cap * itemsize) {
+    errno = ENOMEM;
     return -1; /* overflow */
+  }

   newcap = (v->cap * 3 + 1) / 2;

-  if (newcap < reqcap)
+  if (newcap * itemsize < reqcap * itemsize)
     newcap = reqcap;

   newptr = realloc (v->ptr, newcap * itemsize);
-- 
2.33.1

On Mon, Nov 8, 2021 at 9:56 PM Eric Blake <eblake at redhat.com>
wrote:
>
> Check newcap * itemsize for overflow prior to calling realloc, so that
> we don't accidentally truncate an existing array.  Set errno to ENOMEM
> on all failure paths, rather than leaving it indeterminate on
> overflow.  The patch works by assuming a prerequisite that
> v->cap*itemsize is always smaller than size_t.
>
> Fixes: 985dfa72ae (common/utils/vector.c: Optimize vector append)
> ---
>
> Unless you see problems in this, I'll push this and also port it to
> nbdkit.
>
>  common/utils/vector.c | 8 +++++---
>  1 file changed, 5 insertions(+), 3 deletions(-)
>
> diff --git a/common/utils/vector.c b/common/utils/vector.c
> index a4b43ce..c37f0c3 100644
> --- a/common/utils/vector.c
> +++ b/common/utils/vector.c
> @@ -1,5 +1,5 @@
>  /* nbdkit
> - * Copyright (C) 2018-2020 Red Hat Inc.
> + * Copyright (C) 2018-2021 Red Hat Inc.
>   *
>   * Redistribution and use in source and binary forms, with or without
>   * modification, are permitted provided that the following conditions are
> @@ -44,12 +44,14 @@ generic_vector_reserve (struct generic_vector *v,
size_t n, size_t itemsize)
>    size_t reqcap, newcap;
>
>    reqcap = v->cap + n;
> -  if (reqcap < v->cap)
> +  if (reqcap * itemsize < v->cap * itemsize) {
Just to make sure I understand this correctly:
v->cap * itemsize must be valid value since this is the current
allocation, computed in a previous call to generic_vector_reserve...
> +    errno = ENOMEM;
>      return -1; /* overflow */
> +  }
>
>    newcap = (v->cap * 3 + 1) / 2;
>
> -  if (newcap < reqcap)
> +  if (newcap * itemsize < reqcap * itemsize)
So reqcap * itemsize is valid because we passed the check above.
>      newcap = reqcap;
>
>    newptr = realloc (v->ptr, newcap * itemsize);
Looks right to me.

Nir

On Mon, Nov 8, 2021 at 9:56 PM Eric Blake <eblake at redhat.com>
wrote:
>
> Check newcap * itemsize for overflow prior to calling realloc, so that
> we don't accidentally truncate an existing array.  Set errno to ENOMEM
> on all failure paths, rather than leaving it indeterminate on
> overflow.  The patch works by assuming a prerequisite that
> v->cap*itemsize is always smaller than size_t.
>
> Fixes: 985dfa72ae (common/utils/vector.c: Optimize vector append)
> ---
>
> Unless you see problems in this, I'll push this and also port it to
> nbdkit.
>
>  common/utils/vector.c | 8 +++++---
>  1 file changed, 5 insertions(+), 3 deletions(-)
>
> diff --git a/common/utils/vector.c b/common/utils/vector.c
> index a4b43ce..c37f0c3 100644
> --- a/common/utils/vector.c
> +++ b/common/utils/vector.c
> @@ -1,5 +1,5 @@
>  /* nbdkit
> - * Copyright (C) 2018-2020 Red Hat Inc.
> + * Copyright (C) 2018-2021 Red Hat Inc.
>   *
>   * Redistribution and use in source and binary forms, with or without
>   * modification, are permitted provided that the following conditions are
> @@ -44,12 +44,14 @@ generic_vector_reserve (struct generic_vector *v,
size_t n, size_t itemsize)
>    size_t reqcap, newcap;
>
>    reqcap = v->cap + n;
> -  if (reqcap < v->cap)
> +  if (reqcap * itemsize < v->cap * itemsize) {
> +    errno = ENOMEM;
>      return -1; /* overflow */
> +  }
>
>    newcap = (v->cap * 3 + 1) / 2;
Should we use:

    newcap = v->cap + (v->cap + 1) / 2

so we don't overflow too early?

And if we overflow - meaning that we cannot grow by factor of 1.5,
grow to maximum size:

    if (newcap * itemsize < v->cap * itemsize)
       newcap = SIZE_MAX / itemsize;

This makes a difference when itemsize is 1 or 2. The current
code will stop growing efficiently when allocation is 1.45g, and
then go back to realloc() on every call.
> -  if (newcap < reqcap)
> +  if (newcap * itemsize < reqcap * itemsize)
>      newcap = reqcap;
If we handle overflow before, we can keep the old check
comparing caps.

I can post a patch with this changes if you like.

Nir

On 11/08/21 20:56, Eric Blake wrote:
> Check newcap * itemsize for overflow prior to calling realloc, so that
> we don't accidentally truncate an existing array.  Set errno to ENOMEM
> on all failure paths, rather than leaving it indeterminate on
> overflow.  The patch works by assuming a prerequisite that
> v->cap*itemsize is always smaller than size_t.
>
> Fixes: 985dfa72ae (common/utils/vector.c: Optimize vector append)
> ---
>
> Unless you see problems in this, I'll push this and also port it to
> nbdkit.
>
>  common/utils/vector.c | 8 +++++---
>  1 file changed, 5 insertions(+), 3 deletions(-)
>
> diff --git a/common/utils/vector.c b/common/utils/vector.c
> index a4b43ce..c37f0c3 100644
> --- a/common/utils/vector.c
> +++ b/common/utils/vector.c
> @@ -1,5 +1,5 @@
>  /* nbdkit
> - * Copyright (C) 2018-2020 Red Hat Inc.
> + * Copyright (C) 2018-2021 Red Hat Inc.
>   *
>   * Redistribution and use in source and binary forms, with or without
>   * modification, are permitted provided that the following conditions are
> @@ -44,12 +44,14 @@ generic_vector_reserve (struct generic_vector *v,
size_t n, size_t itemsize)
>    size_t reqcap, newcap;
>
>    reqcap = v->cap + n;
> -  if (reqcap < v->cap)
> +  if (reqcap * itemsize < v->cap * itemsize) {
In my opinion, this is not good enough. Example (assuming uint64_t for
size_t):

  itemsize = 2;
  v->cap = 1;
  n = 0x8000_0000_0000_0001;

therefore

  reqcap = 0x8000_0000_0000_0002;

The product on the LHS will overflow, to 4. The product on the RHS will
be 2. So the controlling expression will evaluate to false.
> +    errno = ENOMEM;
>      return -1; /* overflow */
> +  }
>
>    newcap = (v->cap * 3 + 1) / 2;
This is another unchecked multiplication. What guarantees (v->cap * 3)
cannot overflow?

I strongly dislike attempts to catch overflows after the fact. I think
it's much better to ensure in advance that the addition or
multiplication cannot overflow. That usually involces subtraction,
division, and comparison. I assume generic_vector_reserve() is not on
any "hot path".

  size_t reqcap, maxcap, newcap;

  if (itemsize == 0) {
    errno = EINVAL;
    return -1;
  }

  if (n > (size_t)-1 - v->cap) {
    errno = ENOMEM;
    return -1; /* overflow */
  }
  reqcap = v->cap + n; /* can never overflow */

  maxcap = (size_t)-1 / itemsize; /* never divides by zero */

  if (reqcap > maxcap) {
    errno = ENOMEM;
    return -1; /* overflow */
  }

  if (v->cap > (size_t)-1 / 3 ||
      v->cap * 3 > (size_t)-1 - 1) {
    /* we cannot compute the next auto-increment; stick with the
     * requested capacity
     */
    newcap = reqcap;
  } else {
    newcap = v->cap * 3 + 1; /* cannot overflow */
    newcap /= 2;

    /* if the auto-increment is smaller than requested, or the
     * auto-increment is too large as a number of plain bytes, then
     * stick with the requested capacity */
    if (newcap < reqcap || newcap > maxcap)
      newcap = reqcap;
  }

  assert (newcap <= maxcap);
  newptr = realloc (v->ptr, newcap * itemsize); /* cannot overflow */
  /* ... */

Thanks
Laszlo
>
> -  if (newcap < reqcap)
> +  if (newcap * itemsize < reqcap * itemsize)
>      newcap = reqcap;
>
>    newptr = realloc (v->ptr, newcap * itemsize);
>