[PATCH 0/4] Fixes for memory allocation bugs

[PATCH 0/4] Fixes for memory allocation bugs

[Keith Packard]

There are two serious bug fixes here:

 1) Check calloc/reallocarray for overflow in the multiply using
    __builtin_mul_overflow (which exists in gcc and clang). reallocarray
    was using some old BSD code for this, but __builtin_mul_overflow is
    both more efficient and more easily checked for correctness.

 2) nano_realloc was copying too many bytes from the existing
    allocation when increasing the allocation size. This could lead to
    information disclosure, or a crash.

And a couple of minor improvements:

 3) When nano_realloc is shrinking "a lot", re-allocate the
    buffer to make the original memory available.

 4) When nano_realloc is shrinking and the new allocation fails,
    just return the old buffer to avoid having applications see
    unnecessary failures.

[PATCH 1/4] libc/stdlib: Use __builtin_mul_overflow for reallocarray and calloc

[Keith Packard]

This built-in function (available in both gcc and clang) is more
efficient and generates shorter code than open-coding the test.

Signed-off-by: Keith Packard <keithp@keithp.com>
---
 newlib/libc/stdlib/mallocr.c      |  8 +++++++-
 newlib/libc/stdlib/nano-mallocr.c | 12 ++++++++++--
 newlib/libc/stdlib/reallocarray.c | 17 +++++------------
 3 files changed, 22 insertions(+), 15 deletions(-)

diff --git a/newlib/libc/stdlib/mallocr.c b/newlib/libc/stdlib/mallocr.c
index 26d1c89cc..9ad720ada 100644
--- a/newlib/libc/stdlib/mallocr.c
+++ b/newlib/libc/stdlib/mallocr.c
@@ -3194,7 +3194,7 @@ Void_t* cALLOc(RARG n, elem_size) RDECL size_t n; size_t elem_size;
   mchunkptr p;
   INTERNAL_SIZE_T csz;
 
-  INTERNAL_SIZE_T sz = n * elem_size;
+  INTERNAL_SIZE_T sz;
 
 #if MORECORE_CLEARS
   mchunkptr oldtop;
@@ -3202,6 +3202,12 @@ Void_t* cALLOc(RARG n, elem_size) RDECL size_t n; size_t elem_size;
 #endif
   Void_t* mem;
 
+  if (__builtin_mul_overflow((INTERNAL_SIZE_T) n, (INTERNAL_SIZE_T) elem_size, &sz))
+  {
+    errno = ENOMEM;
+    return 0;
+  }
+
   /* check if expand_top called, in which case don't need to clear */
 #if MORECORE_CLEARS
   MALLOC_LOCK;
diff --git a/newlib/libc/stdlib/nano-mallocr.c b/newlib/libc/stdlib/nano-mallocr.c
index 13b72c99f..04465eb9e 100644
--- a/newlib/libc/stdlib/nano-mallocr.c
+++ b/newlib/libc/stdlib/nano-mallocr.c
@@ -445,8 +445,16 @@ void nano_cfree(RARG void * ptr)
  * Implement calloc simply by calling malloc and set zero */
 void * nano_calloc(RARG malloc_size_t n, malloc_size_t elem)
 {
-    void * mem = nano_malloc(RCALL n * elem);
-    if (mem != NULL) memset(mem, 0, n * elem);
+    ptrdiff_t bytes;
+    void * mem;
+
+    if (__builtin_mul_overflow (n, elem, &bytes))
+    {
+        RERRNO = ENOMEM;
+        return NULL;
+    }
+    mem = nano_malloc(bytes);
+    if (mem != NULL) memset(mem, 0, bytes);
     return mem;
 }
 #endif /* DEFINE_CALLOC */
diff --git a/newlib/libc/stdlib/reallocarray.c b/newlib/libc/stdlib/reallocarray.c
index 4b6cccb70..d1f63c66b 100644
--- a/newlib/libc/stdlib/reallocarray.c
+++ b/newlib/libc/stdlib/reallocarray.c
@@ -16,27 +16,20 @@
  */
 
 #include <sys/cdefs.h>
-__FBSDID("$FreeBSD: head/lib/libc/stdlib/reallocarray.c 282314 2015-05-01 18:32:16Z bapt $");
-
 #include <sys/types.h>
 #include <errno.h>
 #include <stdint.h>
 #include <stdlib.h>
 
-/*
- * This is sqrt(SIZE_MAX+1), as s1*s2 <= SIZE_MAX
- * if both s1 < MUL_NO_OVERFLOW and s2 < MUL_NO_OVERFLOW
- */
-#define MUL_NO_OVERFLOW	((size_t)1 << (sizeof(size_t) * 4))
-
 void *
 reallocarray(void *optr, size_t nmemb, size_t size)
 {
+	ptrdiff_t bytes;
 
-	if ((nmemb >= MUL_NO_OVERFLOW || size >= MUL_NO_OVERFLOW) &&
-	    nmemb > 0 && SIZE_MAX / nmemb < size) {
+	if (__builtin_mul_overflow (nmemb, size, &bytes))
+	{
 		errno = ENOMEM;
-		return (NULL);
+		return NULL;
 	}
-	return (realloc(optr, size * nmemb));
+	return realloc(optr, bytes);
 }
-- 
2.28.0

[PATCH 2/4] libm/stdlib: don't read past source in nano_realloc

[Keith Packard]

Save the computed block size and use it to avoid reading past
the end of the source block.

Signed-off-by: Keith Packard <keithp@keithp.com>
---
 newlib/libc/stdlib/nano-mallocr.c | 6 +++++-
 1 file changed, 5 insertions(+), 1 deletion(-)

diff --git a/newlib/libc/stdlib/nano-mallocr.c b/newlib/libc/stdlib/nano-mallocr.c
index 04465eb9e..cef23977e 100644
--- a/newlib/libc/stdlib/nano-mallocr.c
+++ b/newlib/libc/stdlib/nano-mallocr.c
@@ -466,6 +466,7 @@ void * nano_realloc(RARG void * ptr, malloc_size_t size)
 {
     void * mem;
     chunk * p_to_realloc;
+    malloc_size_t old_size;
 
     if (ptr == NULL) return nano_malloc(RCALL size);
 
@@ -477,12 +478,15 @@ void * nano_realloc(RARG void * ptr, malloc_size_t size)
 
     /* TODO: There is chance to shrink the chunk if newly requested
      * size is much small */
-    if (nano_malloc_usable_size(RCALL ptr) >= size)
+    old_size = nano_malloc_usable_size(RCALL ptr);
+    if (old_size >= size)
       return ptr;
 
     mem = nano_malloc(RCALL size);
     if (mem != NULL)
     {
+	if (size > old_size)
+	    size = old_size;
         memcpy(mem, ptr, size);
         nano_free(RCALL ptr);
     }
-- 
2.28.0

[PATCH 3/4] libm/stdlib: Realloc when shrinking by 2* or more

[Keith Packard]

This reduces memory usage when reallocating objects much smaller.

Signed-off-by: Keith Packard <keithp@keithp.com>
---
 newlib/libc/stdlib/nano-mallocr.c | 4 +---
 1 file changed, 1 insertion(+), 3 deletions(-)

diff --git a/newlib/libc/stdlib/nano-mallocr.c b/newlib/libc/stdlib/nano-mallocr.c
index cef23977e..83234c618 100644
--- a/newlib/libc/stdlib/nano-mallocr.c
+++ b/newlib/libc/stdlib/nano-mallocr.c
@@ -476,10 +476,8 @@ void * nano_realloc(RARG void * ptr, malloc_size_t size)
         return NULL;
     }
 
-    /* TODO: There is chance to shrink the chunk if newly requested
-     * size is much small */
     old_size = nano_malloc_usable_size(RCALL ptr);
-    if (old_size >= size)
+    if (size <= old_size && (old_size >> 1) < size)
       return ptr;
 
     mem = nano_malloc(RCALL size);
-- 
2.28.0

[PATCH 4/4] libm/stdlib: Recover from realloc failure when shrinking

[Keith Packard]

When shrinking and the new allocation fails, just leave things as they
were and keep going. Applications may well expect shrinking
reallocations to always succeed.

Signed-off-by: Keith Packard <keithp@keithp.com>
---
 newlib/libc/stdlib/nano-mallocr.c | 7 ++++++-
 1 file changed, 6 insertions(+), 1 deletion(-)

diff --git a/newlib/libc/stdlib/nano-mallocr.c b/newlib/libc/stdlib/nano-mallocr.c
index 83234c618..452d1448a 100644
--- a/newlib/libc/stdlib/nano-mallocr.c
+++ b/newlib/libc/stdlib/nano-mallocr.c
@@ -481,7 +481,12 @@ void * nano_realloc(RARG void * ptr, malloc_size_t size)
       return ptr;
 
     mem = nano_malloc(RCALL size);
-    if (mem != NULL)
+    if (mem == NULL)
+    {
+	if (size <= old_size)
+	    return ptr;
+    }
+    else
     {
 	if (size > old_size)
 	    size = old_size;
-- 
2.28.0

Re: [PATCH 2/4] libm/stdlib: don't read past source in nano_realloc

[Corinna Vinschen]

On Aug 11 16:05, Keith Packard via Newlib wrote:
> Save the computed block size and use it to avoid reading past
> the end of the source block.
> 
> Signed-off-by: Keith Packard <keithp@keithp.com>
> ---
>  newlib/libc/stdlib/nano-mallocr.c | 6 +++++-
>  1 file changed, 5 insertions(+), 1 deletion(-)
> 
> diff --git a/newlib/libc/stdlib/nano-mallocr.c b/newlib/libc/stdlib/nano-mallocr.c
> index 04465eb9e..cef23977e 100644
> --- a/newlib/libc/stdlib/nano-mallocr.c
> +++ b/newlib/libc/stdlib/nano-mallocr.c
> @@ -466,6 +466,7 @@ void * nano_realloc(RARG void * ptr, malloc_size_t size)
>  {
>      void * mem;
>      chunk * p_to_realloc;
> +    malloc_size_t old_size;
>  
>      if (ptr == NULL) return nano_malloc(RCALL size);
>  
> @@ -477,12 +478,15 @@ void * nano_realloc(RARG void * ptr, malloc_size_t size)
>  
>      /* TODO: There is chance to shrink the chunk if newly requested
>       * size is much small */
> -    if (nano_malloc_usable_size(RCALL ptr) >= size)
> +    old_size = nano_malloc_usable_size(RCALL ptr);
> +    if (old_size >= size)
>        return ptr;

So, after this statement, we can be sure that size > old_size, right?

>      mem = nano_malloc(RCALL size);
>      if (mem != NULL)
>      {
> +	if (size > old_size)

...which makes this condition useless.

> +	    size = old_size;
>          memcpy(mem, ptr, size);

why not just

           memcpy(mem, ptr, old_size);

instead?

>          nano_free(RCALL ptr);
>      }
> -- 
> 2.28.0

Thanks,
Corinna


-- 
Corinna Vinschen
Cygwin Maintainer
Red Hat

Re: [PATCH 3/4] libm/stdlib: Realloc when shrinking by 2* or more

[Corinna Vinschen]

On Aug 11 16:05, Keith Packard via Newlib wrote:
> This reduces memory usage when reallocating objects much smaller.
> 
> Signed-off-by: Keith Packard <keithp@keithp.com>
> ---
>  newlib/libc/stdlib/nano-mallocr.c | 4 +---
>  1 file changed, 1 insertion(+), 3 deletions(-)
> 
> diff --git a/newlib/libc/stdlib/nano-mallocr.c b/newlib/libc/stdlib/nano-mallocr.c
> index cef23977e..83234c618 100644
> --- a/newlib/libc/stdlib/nano-mallocr.c
> +++ b/newlib/libc/stdlib/nano-mallocr.c
> @@ -476,10 +476,8 @@ void * nano_realloc(RARG void * ptr, malloc_size_t size)
>          return NULL;
>      }
>  
> -    /* TODO: There is chance to shrink the chunk if newly requested
> -     * size is much small */
>      old_size = nano_malloc_usable_size(RCALL ptr);
> -    if (old_size >= size)
> +    if (size <= old_size && (old_size >> 1) < size)
>        return ptr;
>  
>      mem = nano_malloc(RCALL size);
> -- 
> 2.28.0

Ok, so this patch introduces the need for the conditional I complained
about in the previous patch.  IMO, the conditional should be moved
into this patch to introduce it together with the change it requires.


Thanks,
Corinna

-- 
Corinna Vinschen
Cygwin Maintainer
Red Hat

Re: [PATCH 1/4] libc/stdlib: Use __builtin_mul_overflow for reallocarray and calloc

[Corinna Vinschen]

On Aug 11 16:05, Keith Packard via Newlib wrote:
> This built-in function (available in both gcc and clang) is more
> efficient and generates shorter code than open-coding the test.
> 
> Signed-off-by: Keith Packard <keithp@keithp.com>
> ---
>  newlib/libc/stdlib/mallocr.c      |  8 +++++++-
>  newlib/libc/stdlib/nano-mallocr.c | 12 ++++++++++--
>  newlib/libc/stdlib/reallocarray.c | 17 +++++------------
>  3 files changed, 22 insertions(+), 15 deletions(-)

Pushed.


Thanks,
Corinna

-- 
Corinna Vinschen
Cygwin Maintainer
Red Hat

Re: [PATCH 3/4] libm/stdlib: Realloc when shrinking by 2* or more

[Keith Packard]

[-- Attachment #1: Type: text/plain, Size: 364 bytes --]

Corinna Vinschen via Newlib <newlib@sourceware.org> writes:

> Ok, so this patch introduces the need for the conditional I complained
> about in the previous patch.  IMO, the conditional should be moved
> into this patch to introduce it together with the change it requires.

I'm easy; just depends on what you want the history to look like.

-- 
-keith

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 832 bytes --]

Re: [PATCH 3/4] libm/stdlib: Realloc when shrinking by 2* or more

[Corinna Vinschen]

On Aug 12 08:01, Keith Packard via Newlib wrote:
> Corinna Vinschen via Newlib <newlib@sourceware.org> writes:
> 
> > Ok, so this patch introduces the need for the conditional I complained
> > about in the previous patch.  IMO, the conditional should be moved
> > into this patch to introduce it together with the change it requires.
> 
> I'm easy; just depends on what you want the history to look like.

Just as I wrote above.


Thanks,
Corinna

-- 
Corinna Vinschen
Cygwin Maintainer
Red Hat

Re: [PATCH 3/4] libm/stdlib: Realloc when shrinking by 2* or more

[Keith Packard]

[-- Attachment #1: Type: text/plain, Size: 797 bytes --]

Corinna Vinschen <vinschen@redhat.com> writes:

> Just as I wrote above.

Done. In reviewing this code further, I've done a bunch more
restructuring to make the code 64-bit clean, removing the 'offset'
mechanism and letting the compiler compute alignment requirements for
us. The diff for that is pretty large though; would there be an interest
in looking at it? I ask because preparing that patch for newlib would
take several hours as it's currently only in picolibc.

https://github.com/keith-packard/picolibc/commit/fd2d18bb5ab442f16789c243648d07b4ec8e2b29

This also uncovers problems when building with newer GCC versions which
"helpfully optimize" common malloc/free operations that cause incorrect
code to be generated in some configurations of the library.

-- 
-keith

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 832 bytes --]

Re: [PATCH 3/4] libm/stdlib: Realloc when shrinking by 2* or more

[Corinna Vinschen]

On Aug 13 17:48, Keith Packard via Newlib wrote:
> Corinna Vinschen <vinschen@redhat.com> writes:
> 
> > Just as I wrote above.
> 
> Done. In reviewing this code further, I've done a bunch more
> restructuring to make the code 64-bit clean, removing the 'offset'
> mechanism and letting the compiler compute alignment requirements for
> us. The diff for that is pretty large though; would there be an interest
> in looking at it? I ask because preparing that patch for newlib would
> take several hours as it's currently only in picolibc.
> 
> https://github.com/keith-packard/picolibc/commit/fd2d18bb5ab442f16789c243648d07b4ec8e2b29
> 
> This also uncovers problems when building with newer GCC versions which
> "helpfully optimize" common malloc/free operations that cause incorrect
> code to be generated in some configurations of the library.
> 
> -- 
> -keith

I took a brief look and I'm just wondering why you don't mention
renaming the functions and dropping the wrapper macros in the commit
message.

As for interest, we may want to ask the ARM guys since they provided the
code originally.  Cc'ing Szabolcs as well as Joey, the original author.


Corinna