[RFC,v2] Add reallocarray function.
diff mbox

Message ID 2080621.6fAB4UMNoY@descartes
State New
Headers show

Commit Message

Rüdiger Sonderfeld May 18, 2014, 9:43 p.m. UTC
Hello Paul,

> Instead of cut and pasting this code from calloc, please refactor so
> that the code is present only once, with the goal of optimizing it when
> the GCC folks get their act together and have a function like the
> __builtin_umul_overflow function that Clang has had since January.  This
> will let calloc and reallocarray do the unsigned multiplication and
> inspect the hardware's overflow bit directly, which is nicer than the
> above hackery.

thanks for your feedback.  I've changed the patch to add a
`check_mul_overflow' function.

Regards,
Rüdiger

---- 8< ------------------------------------------------------ >8 ----

The reallocarray function is an extension from OpenBSD.  It is an
integer-overflow-safe replacement for realloc(p, X*Y) and
malloc(X*Y) (realloc(NULL, X*Y)).  It can therefore help in preventing
certain security issues in code.

See
http://www.openbsd.org/cgi-bin/man.cgi?query=reallocarray&sektion=3&manpath=OpenBSD+Current
---
 ChangeLog                 |  11 ++++
 malloc/Makefile           |   2 +-
 malloc/Versions           |   4 ++
 malloc/malloc.c           |  45 ++++++++++---
 malloc/malloc.h           |   8 +++
 malloc/tst-reallocarray.c | 160 
++++++++++++++++++++++++++++++++++++++++++++++
 stdlib/stdlib.h           |   7 ++
 7 files changed, 226 insertions(+), 11 deletions(-)
 create mode 100644 malloc/tst-reallocarray.c

Comments

Rüdiger Sonderfeld May 18, 2014, 9:50 p.m. UTC | #1
Oh, I think I've introduced a mistake.  The prototype should be

static inline bool
check_mul_overflow(size_t l, size_t r,
                   INTERNAL_SIZE_T *result)

since INTENRAL_SIZE_T apparently can be signed.

Regards,
Rüdiger

On Sunday 18 May 2014 23:43:05 Rüdiger Sonderfeld wrote:
> Hello Paul,
> 
> > Instead of cut and pasting this code from calloc, please refactor so
> > that the code is present only once, with the goal of optimizing it when
> > the GCC folks get their act together and have a function like the
> > __builtin_umul_overflow function that Clang has had since January.  This
> > will let calloc and reallocarray do the unsigned multiplication and
> > inspect the hardware's overflow bit directly, which is nicer than the
> > above hackery.
> 
> thanks for your feedback.  I've changed the patch to add a
> `check_mul_overflow' function.
> 
> Regards,
> Rüdiger
> 
> ---- 8< ------------------------------------------------------ >8 ----
> 
> The reallocarray function is an extension from OpenBSD.  It is an
> integer-overflow-safe replacement for realloc(p, X*Y) and
> malloc(X*Y) (realloc(NULL, X*Y)).  It can therefore help in preventing
> certain security issues in code.
> 
> See
> http://www.openbsd.org/cgi-bin/man.cgi?query=reallocarray&sektion=3&manpath=
> OpenBSD+Current ---
>  ChangeLog                 |  11 ++++
>  malloc/Makefile           |   2 +-
>  malloc/Versions           |   4 ++
>  malloc/malloc.c           |  45 ++++++++++---
>  malloc/malloc.h           |   8 +++
>  malloc/tst-reallocarray.c | 160
> ++++++++++++++++++++++++++++++++++++++++++++++
>  stdlib/stdlib.h           |   7 ++
>  7 files changed, 226 insertions(+), 11 deletions(-)
>  create mode 100644 malloc/tst-reallocarray.c
> 
> diff --git a/ChangeLog b/ChangeLog
> index c606b0d..1e142e1 100644
> --- a/ChangeLog
> +++ b/ChangeLog
> @@ -1,3 +1,14 @@
> +2014-05-18  Rüdiger Sonderfeld  <ruediger@c-plusplus.de>
> +
> +	* malloc/Versions: Add reallocarray and __libc_rallocarray.
> +	* malloc/Makefile (tests): Add tst-reallocarray.c.
> +	* malloc/tst-reallocarray.c: New test file.
> +	* malloc/malloc.h (reallocarray): New declaration.
> +	* stdlib/stdlib.h (reallocarray): Likewise.
> +	* malloc/malloc.c (check_mul_overflow): New inline function.
> +	(__libc_reallocarray): New function.
> +	(__libc_calloc): Use `check_mul_overflow'.
> +
>  2014-05-17  Jose E. Marchesi  <jose.marchesi@oracle.com>
> 
>  	[BZ #16958]
> diff --git a/malloc/Makefile b/malloc/Makefile
> index 7a716f9..1b415ae 100644
> --- a/malloc/Makefile
> +++ b/malloc/Makefile
> @@ -26,7 +26,7 @@ dist-headers := malloc.h
>  headers := $(dist-headers) obstack.h mcheck.h
>  tests := mallocbug tst-malloc tst-valloc tst-calloc tst-obstack \
>  	 tst-mallocstate tst-mcheck tst-mallocfork tst-trim1 \
> -	 tst-malloc-usable tst-realloc tst-posix_memalign \
> +	 tst-malloc-usable tst-realloc tst-reallocarray tst-posix_memalign \
>  	 tst-pvalloc tst-memalign tst-mallopt
>  test-srcs = tst-mtrace
> 
> diff --git a/malloc/Versions b/malloc/Versions
> index 7ca9bdf..64fade5 100644
> --- a/malloc/Versions
> +++ b/malloc/Versions
> @@ -61,6 +61,10 @@ libc {
>    GLIBC_2.16 {
>      aligned_alloc;
>    }
> +  GLIBC_2.20 {
> +    __libc_reallocarray;
> +    reallocarray;
> +  }
>    GLIBC_PRIVATE {
>      # Internal startup hook for libpthread.
>      __libc_malloc_pthread_startup;
> diff --git a/malloc/malloc.c b/malloc/malloc.c
> index 1120d4d..822e400 100644
> --- a/malloc/malloc.c
> +++ b/malloc/malloc.c
> @@ -2943,6 +2943,36 @@ void *weak_variable (*__memalign_hook)
>  }
>  libc_hidden_def (__libc_free)
> 
> +static inline bool
> +check_mul_overflow(INTERNAL_SIZE_T l, INTERNAL_SIZE_T r,
> +                   INTERNAL_SIZE_T *result)
> +{
> +  /* size_t is unsigned so the behavior on overflow is defined.  */
> +  *result = l * r;
> +#define HALF_INTERNAL_SIZE_T                                    \
> +  (((INTERNAL_SIZE_T) 1) << (8 * sizeof (INTERNAL_SIZE_T) / 2))
> +  if (__glibc_unlikely ((l | r) >= HALF_INTERNAL_SIZE_T))
> +    {
> +      if (r != 0 && *result / r != l)
> +        return true;
> +    }
> +  return false;
> +#undef HALF_INTERNAL_SIZE_T
> +}
> +
> +void *
> +__libc_reallocarray(void *optr, size_t nmemb, size_t elem_size)
> +{
> +  INTERNAL_SIZE_T bytes;
> +  if (check_mul_overflow(nmemb, elem_size, &bytes))
> +    {
> +      __set_errno (ENOMEM);
> +      return 0;
> +    }
> +  else
> +    return __libc_realloc (optr, bytes);
> +}
> +
>  void *
>  __libc_realloc (void *oldmem, size_t bytes)
>  {
> @@ -3153,17 +3183,10 @@ void *weak_variable (*__memalign_hook)
>    unsigned long nclears;
>    INTERNAL_SIZE_T *d;
> 
> -  /* size_t is unsigned so the behavior on overflow is defined.  */
> -  bytes = n * elem_size;
> -#define HALF_INTERNAL_SIZE_T \
> -  (((INTERNAL_SIZE_T) 1) << (8 * sizeof (INTERNAL_SIZE_T) / 2))
> -  if (__builtin_expect ((n | elem_size) >= HALF_INTERNAL_SIZE_T, 0))
> +  if (check_mul_overflow(n, elem_size, &bytes))
>      {
> -      if (elem_size != 0 && bytes / elem_size != n)
> -        {
> -          __set_errno (ENOMEM);
> -          return 0;
> -        }
> +      __set_errno (ENOMEM);
> +      return 0;
>      }
> 
>    void *(*hook) (size_t, const void *) =
> @@ -5171,6 +5194,8 @@ struct mallinfo
>  strong_alias (__libc_malloc, __malloc) strong_alias (__libc_malloc, malloc)
> strong_alias (__libc_memalign, __memalign)
>  weak_alias (__libc_memalign, memalign)
> +strong_alias (__libc_reallocarray, __reallocarray)
> +  strong_alias (__libc_reallocarray, reallocarray)
>  strong_alias (__libc_realloc, __realloc) strong_alias (__libc_realloc,
> realloc)
>  strong_alias (__libc_valloc, __valloc) weak_alias (__libc_valloc, valloc)
>  strong_alias (__libc_pvalloc, __pvalloc) weak_alias (__libc_pvalloc,
> pvalloc) diff --git a/malloc/malloc.h b/malloc/malloc.h
> index 30bb91a..db7e5a9 100644
> --- a/malloc/malloc.h
> +++ b/malloc/malloc.h
> @@ -49,6 +49,14 @@ extern void *calloc (size_t __nmemb, size_t __size)
>  extern void *realloc (void *__ptr, size_t __size)
>  __THROW __attribute_warn_unused_result__;
> 
> +/* Re-allocate the previously allocated block in PTR, making the new
> +   block large enough for NMEMB elements of SIZE bytes each.  */
> +/* __attribute_malloc__ is not used, because if realloc returns
> +   the same pointer that was passed to it, aliasing needs to be allowed
> +   between objects pointed by the old and new pointers.  */
> +extern void *reallocarray (void *__ptr, size_t __nmemb, size_t __size)
> +     __THROW __attribute_warn_unused_result__;
> +
>  /* Free a block allocated by `malloc', `realloc' or `calloc'.  */
>  extern void free (void *__ptr) __THROW;
> 
> diff --git a/malloc/tst-reallocarray.c b/malloc/tst-reallocarray.c
> new file mode 100644
> index 0000000..b85825e
> --- /dev/null
> +++ b/malloc/tst-reallocarray.c
> @@ -0,0 +1,160 @@
> +/* Copyright (C) 2014 Free Software Foundation, Inc.
> +   This file is part of the GNU C Library.
> +
> +   The GNU C Library is free software; you can redistribute it and/or
> +   modify it under the terms of the GNU Lesser General Public
> +   License as published by the Free Software Foundation; either
> +   version 2.1 of the License, or (at your option) any later version.
> +
> +   The GNU C Library is distributed in the hope that it will be useful,
> +   but WITHOUT ANY WARRANTY; without even the implied warranty of
> +   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
> +   Lesser General Public License for more details.
> +
> +   You should have received a copy of the GNU Lesser General Public
> +   License along with the GNU C Library; if not, see
> +   <http://www.gnu.org/licenses/>.  */
> +
> +#include <errno.h>
> +#include <malloc.h>
> +#include <stdio.h>
> +#include <math.h>
> +#include <string.h>
> +
> +static int errors = 0;
> +
> +static void
> +merror (const char *msg)
> +{
> +  ++errors;
> +  printf ("Error: %s.\n", msg);
> +}
> +
> +static int
> +do_test (void)
> +
> +{
> +  void *ptr = NULL;
> +  void *ptr2 = NULL;
> +  unsigned char *c;
> +  size_t i;
> +  int ok;
> +  const size_t max = ~(size_t)0;
> +  size_t a, b;
> +
> +  /* Test overflow detection.  */
> +  errno = 0;
> +  ptr = reallocarray (NULL, max, 2);
> +  if (ptr)
> +    {
> +      merror ("Overflow for size_t MAX * 2 not detected");
> +      free(ptr);
> +    }
> +  else if (errno != ENOMEM)
> +    merror ("errno is not set correctly");
> +
> +  errno = 0;
> +  ptr = reallocarray (NULL, 2, max);
> +  if (ptr)
> +    {
> +      merror ("Overflow for 2 * size_t MAX not detected");
> +      free(ptr);
> +    }
> +  else if (errno != ENOMEM)
> +    merror ("errno is not set correctly");
> +
> +  a = 65537;
> +  b = max/65537 + 1;
> +  errno = 0;
> +  ptr = reallocarray (NULL, a, b);
> +  if (ptr)
> +    {
> +      merror ("Overflow for (size_t MAX/65537 + 1) * 65537 not detected");
> +      free(ptr);
> +    }
> +  else if (errno != ENOMEM)
> +    merror ("errno is not set correctly");
> +
> +  errno = 0;
> +  ptr = reallocarray (NULL, b, a);
> +  if (ptr)
> +    {
> +      merror ("Overflow for 65537 * (size_t MAX/65537 + 1)  not detected");
> +      free(ptr);
> +    }
> +  else if (errno != ENOMEM)
> +    merror ("errno is not set correctly");
> +
> +  /* Test realloc-like behavior.  */
> +  /* Allocate memory like malloc.  */
> +  ptr = reallocarray(NULL, 10, 2);
> +  if (!ptr)
> +    merror ("realloc(NULL, 10, 2) failed");
> +
> +  memset (ptr, 0xAF, 10*2);
> +
> +  /* Enlarge buffer.   */
> +  ptr2 = reallocarray(ptr, 20, 2);
> +  if (!ptr2)
> +    merror ("realloc(ptr, 20, 2) failed (enlarge)");
> +  else
> +    ptr = ptr2;
> +
> +  c = ptr;
> +  ok = 1;
> +  for (i = 0; i < 10*2; ++i)
> +    {
> +      if (c[i] != 0xAF)
> +        ok = 0;
> +    }
> +  if (!ok)
> +    merror ("Enlarging changed buffer content (10*2)");
> +
> +  /* Decrease buffer size.  */
> +  ptr2 = reallocarray(ptr, 5, 3);
> +  if (!ptr2)
> +    merror ("realloc(ptr, 5, 3) failed (decrease)");
> +  else
> +    ptr = ptr2;
> +
> +  c = ptr;
> +  ok = 1;
> +  for (i = 0; i < 5*3; ++i)
> +    {
> +      if (c[i] != 0xAF)
> +        ok = 0;
> +    }
> +  if (!ok)
> +    merror ("Reducing changed buffer content (5*3)");
> +
> +  /* Overflow should leave buffer untouched.  */
> +  errno = 0;
> +  ptr2 = reallocarray(ptr, 2, ~(size_t)0);
> +  if (ptr2)
> +    merror ("realloc(ptr, 2, size_t MAX) failed to detect overflow");
> +  if (errno != ENOMEM)
> +    merror ("errno not set correctly");
> +
> +  c = ptr;
> +  ok = 1;
> +  for (i = 0; i < 5*3; ++i)
> +    {
> +      if (c[i] != 0xAF)
> +        ok = 0;
> +    }
> +  if (!ok)
> +    merror ("Overflow changed buffer content (5*3)");
> +
> +  /* Free buffer (glibc).  */
> +  errno = 0;
> +  ptr2 = reallocarray (ptr, 0, 0);
> +  if (ptr2)
> +    merror ("reallocarray (ptr, 0, 0) returned non-NULL");
> +
> +  free (ptr2);
> +
> +  return errors != 0;
> +}
> +
> +#define TEST_FUNCTION do_test ()
> +#include "../test-skeleton.c"
> diff --git a/stdlib/stdlib.h b/stdlib/stdlib.h
> index 00329a2..b75c28f 100644
> --- a/stdlib/stdlib.h
> +++ b/stdlib/stdlib.h
> @@ -479,6 +479,13 @@ extern void *calloc (size_t __nmemb, size_t __size)
>     between objects pointed by the old and new pointers.  */
>  extern void *realloc (void *__ptr, size_t __size)
>       __THROW __attribute_warn_unused_result__;
> +/* Re-allocate the previously allocated block in PTR, making the new
> +   block large enough for NMEMB elements of SIZE bytes each.  */
> +/* __attribute_malloc__ is not used, because if realloc returns
> +   the same pointer that was passed to it, aliasing needs to be allowed
> +   between objects pointed by the old and new pointers.  */
> +extern void *reallocarray (void *__ptr, size_t __nmemb, size_t __size)
> +     __THROW __attribute_warn_unused_result__;
>  /* Free a block allocated by `malloc', `realloc' or `calloc'.  */
>  extern void free (void *__ptr) __THROW;
>  __END_NAMESPACE_STD
Rich Felker May 20, 2014, 2:01 a.m. UTC | #2
On Mon, May 19, 2014 at 03:02:52PM +0000, Joseph S. Myers wrote:
> On Sun, 18 May 2014, R?diger Sonderfeld wrote:
> 
> > diff --git a/stdlib/stdlib.h b/stdlib/stdlib.h
> > index 00329a2..b75c28f 100644
> > --- a/stdlib/stdlib.h
> > +++ b/stdlib/stdlib.h
> > @@ -479,6 +479,13 @@ extern void *calloc (size_t __nmemb, size_t __size)
> >     between objects pointed by the old and new pointers.  */
> >  extern void *realloc (void *__ptr, size_t __size)
> >       __THROW __attribute_warn_unused_result__;
> > +/* Re-allocate the previously allocated block in PTR, making the new
> > +   block large enough for NMEMB elements of SIZE bytes each.  */
> > +/* __attribute_malloc__ is not used, because if realloc returns
> > +   the same pointer that was passed to it, aliasing needs to be allowed
> > +   between objects pointed by the old and new pointers.  */
> > +extern void *reallocarray (void *__ptr, size_t __nmemb, size_t __size)
> > +     __THROW __attribute_warn_unused_result__;
> 
> How has this patch been tested?  This function declaration needs 
> conditioning on __USE_GNU, as no standard includes this function in 
> <stdlib.h>; I'd have expected you to get failures of the conform/ tests 
> for stdlib.h when you ran the testsuite.

Not really related to this patch, but I think the comment about
__attribute_malloc__ that was copied from realloc is wrong. The new
and old pointers cannot alias because, if realloc succeeds (and I
would expect reallocarray to behave the same) the _value_ of the old
pointer is indeterminate and accessing it (e.g. comparing it with new)
invokes undefined behavior.

Rich
Paul Eggert May 20, 2014, 5:47 a.m. UTC | #3
Rich Felker wrote:
> Not really related to this patch, but I think the comment about
> __attribute_malloc__ that was copied from realloc is wrong. The new
> and old pointers cannot alias

You're correct that the new and old pointers cannot alias, but I fear 
that __attribute_malloc__ does not mean what you think it means.  The 
GCC documentation is *really* confusing in this area, unfortunately.

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=56955
Andreas Schwab May 20, 2014, 8:17 a.m. UTC | #4
Rich Felker <dalias@libc.org> writes:

> Not really related to this patch, but I think the comment about
> __attribute_malloc__ that was copied from realloc is wrong. The new
> and old pointers cannot alias because, if realloc succeeds (and I
> would expect reallocarray to behave the same) the _value_ of the old
> pointer is indeterminate and accessing it (e.g. comparing it with new)
> invokes undefined behavior.

Please report that as a gcc bug (it doesn't mark it either).

Andreas.
Rüdiger Sonderfeld May 20, 2014, 12:31 p.m. UTC | #5
On Monday 19 May 2014 15:02:52 Joseph S. Myers wrote:
> How has this patch been tested?  This function declaration needs
> conditioning on __USE_GNU, as no standard includes this function in
> <stdlib.h>; I'd have expected you to get failures of the conform/ tests
> for stdlib.h when you ran the testsuite.

Yes, I got failures in the conform tests.  (I also hit some nptl errors but I 
guess they are unrelated).  I've added the __USE_GNU check to stdlib.h.  I 
assume this is not necessary for malloc.h since malloc.h is not a standard 
header?  I'll send and updated patch to the mailing list.

But I wonder if there is any general interest or objections to adding the 
`reallocarray' function to glibc?

Regards,
Rüdiger
Paul Eggert May 20, 2014, 2:06 p.m. UTC | #6
Rüdiger Sonderfeld wrote:
> I wonder if there is any general interest or objections to adding the
> `reallocarray' function to glibc?

As an application developer I'm mildly interested if you can speed it 
up.  GNU apps like 'ls', 'grep', etc. that need such a function 
typically use Gnulib's xnrealloc, which has the same signature and 
nearly the same behavior as reallocarray.  xnrealloc and reallocarray's 
behaviors differ in two subtle ways, though.  First, xnrealloc's 2nd arg 
must be nonzero; this avoids a runtime check for zero so it's a bit 
faster (xnrealloc is an inline function so much of the overflow test's 
work can typically be done at compile-time).  Second, xnrealloc's result 
is guaranteed to be non-NULL if its first arg is nonzero; this lets the 
calling code be simpler.

We could alter xnrealloc to be a simple wrapper for reallocarray if 
reallocarray is available.  With the current reallocarray 
implementation, though, this might not be worth the trouble, because I 
suspect xnrealloc's test for overflow is faster than reallocarray's in 
the typical case where the last argument is a constant.  If you could 
fix reallocarray to use the equivalent of __builtin_umul_overflow, 
though, this objection would be removed and it would make sense for 
xnrealloc to be a wrapper for reallocarray if available.
Paul Eggert May 20, 2014, 3:44 p.m. UTC | #7
Andreas Schwab wrote:
> Please report that as a gcc bug (it doesn't mark it either).

As far as I can tell this is a bug in GCC's documentation, not in its 
implementation.  As I mentioned cryptically in my previous message, if 
FOO has the malloc attribute and you execute 'int **p = foo (...);', the 
malloc attribute means that *P cannot point to previously-existing 
storage (because *P is uninitialized junk).  That is why the attribute 
applies to calloc (because *P must be null, which also cannot point to 
previously-existing storage) but not to realloc (because *P might be 
initialized and might point to previously-existing storage).

For more about this confusing topic, please see:

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=56955
Rich Felker May 20, 2014, 5:01 p.m. UTC | #8
On Tue, May 20, 2014 at 08:44:09AM -0700, Paul Eggert wrote:
> Andreas Schwab wrote:
> >Please report that as a gcc bug (it doesn't mark it either).
> 
> As far as I can tell this is a bug in GCC's documentation, not in
> its implementation.  As I mentioned cryptically in my previous
> message, if FOO has the malloc attribute and you execute 'int **p =
> foo (...);', the malloc attribute means that *P cannot point to
> previously-existing storage (because *P is uninitialized junk).
> That is why the attribute applies to calloc (because *P must be
> null, which also cannot point to previously-existing storage) but
> not to realloc (because *P might be initialized and might point to
> previously-existing storage).
> 
> For more about this confusing topic, please see:
> 
> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=56955

What is the issue about "previously-existing storage"? Is the concern
that *new->something might alias new (because new==old happens to be
true and the object contained a pointer to itself or part of itself)
or that *new->something merely can alias other existing memory
(whereas GCC assumes it never can)?

Rich
Paul Eggert May 20, 2014, 8:47 p.m. UTC | #9
On 05/20/2014 10:01 AM, Rich Felker wrote:
> Is the concern
> that *new->something might alias new (because new==old happens to be
> true and the object contained a pointer to itself or part of itself)
> or that *new->something merely can alias other existing memory
> (whereas GCC assumes it never can)?

The latter, if I understand your question correctly.  I added a proposed 
patch to the GCC documentation here:

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=56955#c6

Please give it a read, and follow up there if you have further questions.
Rüdiger Sonderfeld May 21, 2014, 12:32 p.m. UTC | #10
On Tuesday 20 May 2014 07:06:13 Paul Eggert wrote:
> First, xnrealloc's 2nd arg
> must be nonzero; this avoids a runtime check for zero so it's a bit
> faster (xnrealloc is an inline function so much of the overflow test's
> work can typically be done at compile-time).

An inline version certainly would make sense.  But I don't think this could be 
done for glibc.

What happens if the 2nd arg is zero in a call to `xnrealloc'?  Since 
`reallocarray' should primarily be about providing a safer to use API I 
wouldn't want to introduce another case for undefined behavior.

And I'd like to stay compatible as much as possible with the OpenBSD 
implementation (which will probably spread to other *BSDs as well).

> Second, xnrealloc's result
> is guaranteed to be non-NULL if its first arg is nonzero; this lets the
> calling code be simpler.

How can `xnrealloc' guarantee that the result will be non-NULL?

> We could alter xnrealloc to be a simple wrapper for reallocarray if
> reallocarray is available.  With the current reallocarray
> implementation, though, this might not be worth the trouble, because I
> suspect xnrealloc's test for overflow is faster than reallocarray's in
> the typical case where the last argument is a constant.  If you could
> fix reallocarray to use the equivalent of __builtin_umul_overflow,
> though, this objection would be removed and it would make sense for
> xnrealloc to be a wrapper for reallocarray if available.

I've changed `reallocarray' (and `calloc') to call `check_mul_overflow' for 
the overflow check (v2 of the patch).  This function could be replaced by a 
call to `__builtin_umul_overflow' once GCC provides such an extension.  
(However there would the problem of selecting the right overflow check due to 
the existence of `size_t` and `INTERNAL_SIZE_T'.  But that can be discussed 
once the GCC extension exists.)

Is there active work done on those overflow checks in GCC?  Maybe it would 
make sense to provide an API like that, which if available uses the builtin.  
I'm not sure if glibc would be the right place for it though.  But I guess 
this might be something gnulib could provide (if it hasn't something like that 
already).

Regards,
Rüdiger
Paul Eggert May 22, 2014, 3:59 a.m. UTC | #11
Rüdiger Sonderfeld wrote:

> What happens if the 2nd arg is zero in a call to `xnrealloc'?

Undefined behavior.  Agreed, this isn't suitable for reallocarray.

> How can `xnrealloc' guarantee that the result will be non-NULL?

It tests realloc's result and calls a _Noreturn function if it's null. 
Again, this is fine for Gnulib but not suitable for reallocarray -- we'd 
keep this part in the Gnulib wrapper.

> Is there active work done on those overflow checks in GCC?

The last message I know on the topic was last month.  Sort of active, I 
guess.  <https://gcc.gnu.org/ml/gcc/2014-04/msg00194.html>  Perhaps 
someone should ping the GCC list.

While we're on the subject, there was a proposal last October to add 
saturated arithmetic to glibc internals; see, e.g., 
<https://www.sourceware.org/ml/libc-alpha/2013-10/msg00905.html>. 
Presumably this arithmetic could use these builtins too.

> this might be something gnulib could provide (if it hasn't something like that already).

gnulib has several things like that already, which could be tuned to use 
__builtin_umul_overflow if available:

* intprops.h's INT_MULTIPLY_OVERFLOW (A, B) returns true if multiplying 
the integers A and B would overflow.  It works for any combination of 
integer types, so in this sense it's handier than __builtin_umul_overflow.

* xsize.h's xtimes uses saturated arithmetic to multiply size_t values, 
and needs to check for overflow.

* xalloc-oversized.h's xalloc_oversized checks for overflow in size_t 
multiplication, with the special case that SIZE_MAX represents a 
previously-overflowed computation (e.g., from xtimes).

Perhaps we could add an MUL_OVERFLOW (A, B, PRESULT) macro to intprops.h 
(that uses __builtin_umul_overflow/__builtin_ulmul_overflow/etc.) if 
available) so that applications could use the builtins more directly if 
they prefer.  It's not clear how useful that would be, though.

Patch
diff mbox

diff --git a/ChangeLog b/ChangeLog
index c606b0d..1e142e1 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,14 @@ 
+2014-05-18  Rüdiger Sonderfeld  <ruediger@c-plusplus.de>
+
+	* malloc/Versions: Add reallocarray and __libc_rallocarray.
+	* malloc/Makefile (tests): Add tst-reallocarray.c.
+	* malloc/tst-reallocarray.c: New test file.
+	* malloc/malloc.h (reallocarray): New declaration.
+	* stdlib/stdlib.h (reallocarray): Likewise.
+	* malloc/malloc.c (check_mul_overflow): New inline function.
+	(__libc_reallocarray): New function.
+	(__libc_calloc): Use `check_mul_overflow'.
+
 2014-05-17  Jose E. Marchesi  <jose.marchesi@oracle.com>
 
 	[BZ #16958]
diff --git a/malloc/Makefile b/malloc/Makefile
index 7a716f9..1b415ae 100644
--- a/malloc/Makefile
+++ b/malloc/Makefile
@@ -26,7 +26,7 @@  dist-headers := malloc.h
 headers := $(dist-headers) obstack.h mcheck.h
 tests := mallocbug tst-malloc tst-valloc tst-calloc tst-obstack \
 	 tst-mallocstate tst-mcheck tst-mallocfork tst-trim1 \
-	 tst-malloc-usable tst-realloc tst-posix_memalign \
+	 tst-malloc-usable tst-realloc tst-reallocarray tst-posix_memalign \
 	 tst-pvalloc tst-memalign tst-mallopt
 test-srcs = tst-mtrace
 
diff --git a/malloc/Versions b/malloc/Versions
index 7ca9bdf..64fade5 100644
--- a/malloc/Versions
+++ b/malloc/Versions
@@ -61,6 +61,10 @@  libc {
   GLIBC_2.16 {
     aligned_alloc;
   }
+  GLIBC_2.20 {
+    __libc_reallocarray;
+    reallocarray;
+  }
   GLIBC_PRIVATE {
     # Internal startup hook for libpthread.
     __libc_malloc_pthread_startup;
diff --git a/malloc/malloc.c b/malloc/malloc.c
index 1120d4d..822e400 100644
--- a/malloc/malloc.c
+++ b/malloc/malloc.c
@@ -2943,6 +2943,36 @@  void *weak_variable (*__memalign_hook)
 }
 libc_hidden_def (__libc_free)
 
+static inline bool
+check_mul_overflow(INTERNAL_SIZE_T l, INTERNAL_SIZE_T r,
+                   INTERNAL_SIZE_T *result)
+{
+  /* size_t is unsigned so the behavior on overflow is defined.  */
+  *result = l * r;
+#define HALF_INTERNAL_SIZE_T                                    \
+  (((INTERNAL_SIZE_T) 1) << (8 * sizeof (INTERNAL_SIZE_T) / 2))
+  if (__glibc_unlikely ((l | r) >= HALF_INTERNAL_SIZE_T))
+    {
+      if (r != 0 && *result / r != l)
+        return true;
+    }
+  return false;
+#undef HALF_INTERNAL_SIZE_T
+}
+
+void *
+__libc_reallocarray(void *optr, size_t nmemb, size_t elem_size)
+{
+  INTERNAL_SIZE_T bytes;
+  if (check_mul_overflow(nmemb, elem_size, &bytes))
+    {
+      __set_errno (ENOMEM);
+      return 0;
+    }
+  else
+    return __libc_realloc (optr, bytes);
+}
+
 void *
 __libc_realloc (void *oldmem, size_t bytes)
 {
@@ -3153,17 +3183,10 @@  void *weak_variable (*__memalign_hook)
   unsigned long nclears;
   INTERNAL_SIZE_T *d;
 
-  /* size_t is unsigned so the behavior on overflow is defined.  */
-  bytes = n * elem_size;
-#define HALF_INTERNAL_SIZE_T \
-  (((INTERNAL_SIZE_T) 1) << (8 * sizeof (INTERNAL_SIZE_T) / 2))
-  if (__builtin_expect ((n | elem_size) >= HALF_INTERNAL_SIZE_T, 0))
+  if (check_mul_overflow(n, elem_size, &bytes))
     {
-      if (elem_size != 0 && bytes / elem_size != n)
-        {
-          __set_errno (ENOMEM);
-          return 0;
-        }
+      __set_errno (ENOMEM);
+      return 0;
     }
 
   void *(*hook) (size_t, const void *) =
@@ -5171,6 +5194,8 @@  struct mallinfo
 strong_alias (__libc_malloc, __malloc) strong_alias (__libc_malloc, malloc)
 strong_alias (__libc_memalign, __memalign)
 weak_alias (__libc_memalign, memalign)
+strong_alias (__libc_reallocarray, __reallocarray)
+  strong_alias (__libc_reallocarray, reallocarray)
 strong_alias (__libc_realloc, __realloc) strong_alias (__libc_realloc, 
realloc)
 strong_alias (__libc_valloc, __valloc) weak_alias (__libc_valloc, valloc)
 strong_alias (__libc_pvalloc, __pvalloc) weak_alias (__libc_pvalloc, pvalloc)
diff --git a/malloc/malloc.h b/malloc/malloc.h
index 30bb91a..db7e5a9 100644
--- a/malloc/malloc.h
+++ b/malloc/malloc.h
@@ -49,6 +49,14 @@  extern void *calloc (size_t __nmemb, size_t __size)
 extern void *realloc (void *__ptr, size_t __size)
 __THROW __attribute_warn_unused_result__;
 
+/* Re-allocate the previously allocated block in PTR, making the new
+   block large enough for NMEMB elements of SIZE bytes each.  */
+/* __attribute_malloc__ is not used, because if realloc returns
+   the same pointer that was passed to it, aliasing needs to be allowed
+   between objects pointed by the old and new pointers.  */
+extern void *reallocarray (void *__ptr, size_t __nmemb, size_t __size)
+     __THROW __attribute_warn_unused_result__;
+
 /* Free a block allocated by `malloc', `realloc' or `calloc'.  */
 extern void free (void *__ptr) __THROW;
 
diff --git a/malloc/tst-reallocarray.c b/malloc/tst-reallocarray.c
new file mode 100644
index 0000000..b85825e
--- /dev/null
+++ b/malloc/tst-reallocarray.c
@@ -0,0 +1,160 @@ 
+/* Copyright (C) 2014 Free Software Foundation, Inc.
+   This file is part of the GNU C Library.
+
+   The GNU C Library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Lesser General Public
+   License as published by the Free Software Foundation; either
+   version 2.1 of the License, or (at your option) any later version.
+
+   The GNU C Library is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public
+   License along with the GNU C Library; if not, see
+   <http://www.gnu.org/licenses/>.  */
+
+#include <errno.h>
+#include <malloc.h>
+#include <stdio.h>
+#include <math.h>
+#include <string.h>
+
+static int errors = 0;
+
+static void
+merror (const char *msg)
+{
+  ++errors;
+  printf ("Error: %s.\n", msg);
+}
+
+static int
+do_test (void)
+
+{
+  void *ptr = NULL;
+  void *ptr2 = NULL;
+  unsigned char *c;
+  size_t i;
+  int ok;
+  const size_t max = ~(size_t)0;
+  size_t a, b;
+
+  /* Test overflow detection.  */
+  errno = 0;
+  ptr = reallocarray (NULL, max, 2);
+  if (ptr)
+    {
+      merror ("Overflow for size_t MAX * 2 not detected");
+      free(ptr);
+    }
+  else if (errno != ENOMEM)
+    merror ("errno is not set correctly");
+
+  errno = 0;
+  ptr = reallocarray (NULL, 2, max);
+  if (ptr)
+    {
+      merror ("Overflow for 2 * size_t MAX not detected");
+      free(ptr);
+    }
+  else if (errno != ENOMEM)
+    merror ("errno is not set correctly");
+
+  a = 65537;
+  b = max/65537 + 1;
+  errno = 0;
+  ptr = reallocarray (NULL, a, b);
+  if (ptr)
+    {
+      merror ("Overflow for (size_t MAX/65537 + 1) * 65537 not detected");
+      free(ptr);
+    }
+  else if (errno != ENOMEM)
+    merror ("errno is not set correctly");
+
+  errno = 0;
+  ptr = reallocarray (NULL, b, a);
+  if (ptr)
+    {
+      merror ("Overflow for 65537 * (size_t MAX/65537 + 1)  not detected");
+      free(ptr);
+    }
+  else if (errno != ENOMEM)
+    merror ("errno is not set correctly");
+
+  /* Test realloc-like behavior.  */
+  /* Allocate memory like malloc.  */
+  ptr = reallocarray(NULL, 10, 2);
+  if (!ptr)
+    merror ("realloc(NULL, 10, 2) failed");
+
+  memset (ptr, 0xAF, 10*2);
+
+  /* Enlarge buffer.   */
+  ptr2 = reallocarray(ptr, 20, 2);
+  if (!ptr2)
+    merror ("realloc(ptr, 20, 2) failed (enlarge)");
+  else
+    ptr = ptr2;
+
+  c = ptr;
+  ok = 1;
+  for (i = 0; i < 10*2; ++i)
+    {
+      if (c[i] != 0xAF)
+        ok = 0;
+    }
+  if (!ok)
+    merror ("Enlarging changed buffer content (10*2)");
+
+  /* Decrease buffer size.  */
+  ptr2 = reallocarray(ptr, 5, 3);
+  if (!ptr2)
+    merror ("realloc(ptr, 5, 3) failed (decrease)");
+  else
+    ptr = ptr2;
+
+  c = ptr;
+  ok = 1;
+  for (i = 0; i < 5*3; ++i)
+    {
+      if (c[i] != 0xAF)
+        ok = 0;
+    }
+  if (!ok)
+    merror ("Reducing changed buffer content (5*3)");
+
+  /* Overflow should leave buffer untouched.  */
+  errno = 0;
+  ptr2 = reallocarray(ptr, 2, ~(size_t)0);
+  if (ptr2)
+    merror ("realloc(ptr, 2, size_t MAX) failed to detect overflow");
+  if (errno != ENOMEM)
+    merror ("errno not set correctly");
+
+  c = ptr;
+  ok = 1;
+  for (i = 0; i < 5*3; ++i)
+    {
+      if (c[i] != 0xAF)
+        ok = 0;
+    }
+  if (!ok)
+    merror ("Overflow changed buffer content (5*3)");
+
+  /* Free buffer (glibc).  */
+  errno = 0;
+  ptr2 = reallocarray (ptr, 0, 0);
+  if (ptr2)
+    merror ("reallocarray (ptr, 0, 0) returned non-NULL");
+
+  free (ptr2);
+
+  return errors != 0;
+}
+
+#define TEST_FUNCTION do_test ()
+#include "../test-skeleton.c"
diff --git a/stdlib/stdlib.h b/stdlib/stdlib.h
index 00329a2..b75c28f 100644
--- a/stdlib/stdlib.h
+++ b/stdlib/stdlib.h
@@ -479,6 +479,13 @@  extern void *calloc (size_t __nmemb, size_t __size)
    between objects pointed by the old and new pointers.  */
 extern void *realloc (void *__ptr, size_t __size)
      __THROW __attribute_warn_unused_result__;
+/* Re-allocate the previously allocated block in PTR, making the new
+   block large enough for NMEMB elements of SIZE bytes each.  */
+/* __attribute_malloc__ is not used, because if realloc returns
+   the same pointer that was passed to it, aliasing needs to be allowed
+   between objects pointed by the old and new pointers.  */
+extern void *reallocarray (void *__ptr, size_t __nmemb, size_t __size)
+     __THROW __attribute_warn_unused_result__;
 /* Free a block allocated by `malloc', `realloc' or `calloc'.  */
 extern void free (void *__ptr) __THROW;
 __END_NAMESPACE_STD