* [PATCH 0/4] Fixes for memory allocation bugs @ 2020-08-11 23:05 Keith Packard 2020-08-11 23:05 ` [PATCH 1/4] libc/stdlib: Use __builtin_mul_overflow for reallocarray and calloc Keith Packard ` (3 more replies) 0 siblings, 4 replies; 12+ messages in thread From: Keith Packard @ 2020-08-11 23:05 UTC (permalink / raw) To: newlib 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. ^ permalink raw reply [flat|nested] 12+ messages in thread
* [PATCH 1/4] libc/stdlib: Use __builtin_mul_overflow for reallocarray and calloc 2020-08-11 23:05 [PATCH 0/4] Fixes for memory allocation bugs Keith Packard @ 2020-08-11 23:05 ` Keith Packard 2020-08-12 8:13 ` Corinna Vinschen 2020-08-11 23:05 ` [PATCH 2/4] libm/stdlib: don't read past source in nano_realloc Keith Packard ` (2 subsequent siblings) 3 siblings, 1 reply; 12+ messages in thread From: Keith Packard @ 2020-08-11 23:05 UTC (permalink / raw) To: newlib 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 ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH 1/4] libc/stdlib: Use __builtin_mul_overflow for reallocarray and calloc 2020-08-11 23:05 ` [PATCH 1/4] libc/stdlib: Use __builtin_mul_overflow for reallocarray and calloc Keith Packard @ 2020-08-12 8:13 ` Corinna Vinschen 0 siblings, 0 replies; 12+ messages in thread From: Corinna Vinschen @ 2020-08-12 8:13 UTC (permalink / raw) To: newlib 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 ^ permalink raw reply [flat|nested] 12+ messages in thread
* [PATCH 2/4] libm/stdlib: don't read past source in nano_realloc 2020-08-11 23:05 [PATCH 0/4] Fixes for memory allocation bugs Keith Packard 2020-08-11 23:05 ` [PATCH 1/4] libc/stdlib: Use __builtin_mul_overflow for reallocarray and calloc Keith Packard @ 2020-08-11 23:05 ` Keith Packard 2020-08-12 8:01 ` Corinna Vinschen 2020-08-11 23:05 ` [PATCH 3/4] libm/stdlib: Realloc when shrinking by 2* or more Keith Packard 2020-08-11 23:05 ` [PATCH 4/4] libm/stdlib: Recover from realloc failure when shrinking Keith Packard 3 siblings, 1 reply; 12+ messages in thread From: Keith Packard @ 2020-08-11 23:05 UTC (permalink / raw) To: newlib 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 ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH 2/4] libm/stdlib: don't read past source in nano_realloc 2020-08-11 23:05 ` [PATCH 2/4] libm/stdlib: don't read past source in nano_realloc Keith Packard @ 2020-08-12 8:01 ` Corinna Vinschen 0 siblings, 0 replies; 12+ messages in thread From: Corinna Vinschen @ 2020-08-12 8:01 UTC (permalink / raw) To: Keith Packard; +Cc: newlib 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 ^ permalink raw reply [flat|nested] 12+ messages in thread
* [PATCH 3/4] libm/stdlib: Realloc when shrinking by 2* or more 2020-08-11 23:05 [PATCH 0/4] Fixes for memory allocation bugs Keith Packard 2020-08-11 23:05 ` [PATCH 1/4] libc/stdlib: Use __builtin_mul_overflow for reallocarray and calloc Keith Packard 2020-08-11 23:05 ` [PATCH 2/4] libm/stdlib: don't read past source in nano_realloc Keith Packard @ 2020-08-11 23:05 ` Keith Packard 2020-08-12 8:08 ` Corinna Vinschen 2020-08-11 23:05 ` [PATCH 4/4] libm/stdlib: Recover from realloc failure when shrinking Keith Packard 3 siblings, 1 reply; 12+ messages in thread From: Keith Packard @ 2020-08-11 23:05 UTC (permalink / raw) To: newlib 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 ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH 3/4] libm/stdlib: Realloc when shrinking by 2* or more 2020-08-11 23:05 ` [PATCH 3/4] libm/stdlib: Realloc when shrinking by 2* or more Keith Packard @ 2020-08-12 8:08 ` Corinna Vinschen 2020-08-12 15:01 ` Keith Packard 0 siblings, 1 reply; 12+ messages in thread From: Corinna Vinschen @ 2020-08-12 8:08 UTC (permalink / raw) To: newlib 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 ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH 3/4] libm/stdlib: Realloc when shrinking by 2* or more 2020-08-12 8:08 ` Corinna Vinschen @ 2020-08-12 15:01 ` Keith Packard 2020-08-13 7:59 ` Corinna Vinschen 0 siblings, 1 reply; 12+ messages in thread From: Keith Packard @ 2020-08-12 15:01 UTC (permalink / raw) To: Corinna Vinschen via Newlib, newlib; +Cc: Corinna Vinschen [-- 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 --] ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH 3/4] libm/stdlib: Realloc when shrinking by 2* or more 2020-08-12 15:01 ` Keith Packard @ 2020-08-13 7:59 ` Corinna Vinschen 2020-08-14 0:48 ` Keith Packard 0 siblings, 1 reply; 12+ messages in thread From: Corinna Vinschen @ 2020-08-13 7:59 UTC (permalink / raw) To: Keith Packard; +Cc: Corinna Vinschen via Newlib 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 ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH 3/4] libm/stdlib: Realloc when shrinking by 2* or more 2020-08-13 7:59 ` Corinna Vinschen @ 2020-08-14 0:48 ` Keith Packard 2020-08-17 9:54 ` Corinna Vinschen 0 siblings, 1 reply; 12+ messages in thread From: Keith Packard @ 2020-08-14 0:48 UTC (permalink / raw) To: Corinna Vinschen; +Cc: Corinna Vinschen via Newlib [-- 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 --] ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH 3/4] libm/stdlib: Realloc when shrinking by 2* or more 2020-08-14 0:48 ` Keith Packard @ 2020-08-17 9:54 ` Corinna Vinschen 0 siblings, 0 replies; 12+ messages in thread From: Corinna Vinschen @ 2020-08-17 9:54 UTC (permalink / raw) To: Keith Packard; +Cc: newlib, Szabolcs Nagy, Joey Ye 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 ^ permalink raw reply [flat|nested] 12+ messages in thread
* [PATCH 4/4] libm/stdlib: Recover from realloc failure when shrinking 2020-08-11 23:05 [PATCH 0/4] Fixes for memory allocation bugs Keith Packard ` (2 preceding siblings ...) 2020-08-11 23:05 ` [PATCH 3/4] libm/stdlib: Realloc when shrinking by 2* or more Keith Packard @ 2020-08-11 23:05 ` Keith Packard 3 siblings, 0 replies; 12+ messages in thread From: Keith Packard @ 2020-08-11 23:05 UTC (permalink / raw) To: newlib 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 ^ permalink raw reply [flat|nested] 12+ messages in thread
end of thread, other threads:[~2020-08-17 9:54 UTC | newest] Thread overview: 12+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2020-08-11 23:05 [PATCH 0/4] Fixes for memory allocation bugs Keith Packard 2020-08-11 23:05 ` [PATCH 1/4] libc/stdlib: Use __builtin_mul_overflow for reallocarray and calloc Keith Packard 2020-08-12 8:13 ` Corinna Vinschen 2020-08-11 23:05 ` [PATCH 2/4] libm/stdlib: don't read past source in nano_realloc Keith Packard 2020-08-12 8:01 ` Corinna Vinschen 2020-08-11 23:05 ` [PATCH 3/4] libm/stdlib: Realloc when shrinking by 2* or more Keith Packard 2020-08-12 8:08 ` Corinna Vinschen 2020-08-12 15:01 ` Keith Packard 2020-08-13 7:59 ` Corinna Vinschen 2020-08-14 0:48 ` Keith Packard 2020-08-17 9:54 ` Corinna Vinschen 2020-08-11 23:05 ` [PATCH 4/4] libm/stdlib: Recover from realloc failure when shrinking Keith Packard
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).