[musl] [RFC] add realloci() and reallocarrayi()

[musl] [RFC] add realloci() and reallocarrayi()

[Alejandro Colomar]

They are realloc(3) variants that work in-place.  They change the size
of a block of memory, without affecting the lifetime of the object.
It requires a non-null pointer, unlike realloc(3), as it can't create
a new object (it doesn't return a pointer).

Cc: "A. Wilcox" <AWilcox@wilcox-tech.com>
Cc: Lénárd Szolnoki <cpp@lenardszolnoki.com>
Cc: Thorsten Glaser <tg@mirbsd.de>
Cc: Collin Funk <collin.funk1@gmail.com>
Signed-off-by: Alejandro Colomar <alx@kernel.org>
---

Hi,

I have not tested this patch (not even tried building yet).  It's just
an initial draft, requesting comments about the overall idea.

So far, I've only implemented this in the mallocng implementation, as
the oldmalloc implementation was too weird for me to fully understand.
Do we need an old implementation too?


Have a lovely day!
Alex

 include/stdlib.h               |  2 ++
 ldso/dynlink.c                 |  1 +
 src/aio/aio.c                  |  1 +
 src/exit/atexit.c              |  1 +
 src/ldso/dlerror.c             |  1 +
 src/locale/dcngettext.c        |  1 +
 src/locale/duplocale.c         |  1 +
 src/locale/freelocale.c        |  1 +
 src/locale/locale_map.c        |  1 +
 src/locale/newlocale.c         |  1 +
 src/malloc/mallocng/glue.h     |  1 +
 src/malloc/mallocng/realloc.c  |  8 +-------
 src/malloc/mallocng/realloci.c | 26 ++++++++++++++++++++++++++
 src/malloc/reallocarrayi.c     | 13 +++++++++++++
 src/malloc/realloci.c          |  7 +++++++
 src/process/fdop.h             |  1 +
 src/thread/pthread_atfork.c    |  1 +
 src/thread/sem_open.c          |  1 +
 src/time/__tz.c                |  1 +
 19 files changed, 63 insertions(+), 7 deletions(-)
 create mode 100644 src/malloc/mallocng/realloci.c
 create mode 100644 src/malloc/reallocarrayi.c
 create mode 100644 src/malloc/realloci.c

diff --git a/include/stdlib.h b/include/stdlib.h
index 475190bf..577b7172 100644
--- a/include/stdlib.h
+++ b/include/stdlib.h
@@ -148,6 +148,8 @@ int clearenv(void);
 #define WCOREDUMP(s) ((s) & 0x80)
 #define WIFCONTINUED(s) ((s) == 0xffff)
 void *reallocarray (void *, size_t, size_t);
+int realloci (void *, size_t);
+int reallocarrayi (void *, size_t);
 void qsort_r (void *, size_t, size_t, int (*)(const void *, const void *, void *), void *);
 #endif
 
diff --git a/ldso/dynlink.c b/ldso/dynlink.c
index 715948f4..a882c5c1 100644
--- a/ldso/dynlink.c
+++ b/ldso/dynlink.c
@@ -35,6 +35,7 @@ static size_t ldso_page_size;
 #define malloc __libc_malloc
 #define calloc __libc_calloc
 #define realloc __libc_realloc
+#define realloci __libc_realloci
 #define free __libc_free
 
 static void error_impl(const char *, ...);
diff --git a/src/aio/aio.c b/src/aio/aio.c
index d7e063bf..4702d0ae 100644
--- a/src/aio/aio.c
+++ b/src/aio/aio.c
@@ -14,6 +14,7 @@
 #define malloc __libc_malloc
 #define calloc __libc_calloc
 #define realloc __libc_realloc
+#define realloci __libc_realloci
 #define free __libc_free
 
 /* The following is a threads-based implementation of AIO with minimal
diff --git a/src/exit/atexit.c b/src/exit/atexit.c
index 92c91c9d..006551e7 100644
--- a/src/exit/atexit.c
+++ b/src/exit/atexit.c
@@ -7,6 +7,7 @@
 #define malloc __libc_malloc
 #define calloc __libc_calloc
 #define realloc undef
+#define realloci undef
 #define free undef
 
 /* Ensure that at least 32 atexit handlers can be registered without malloc */
diff --git a/src/ldso/dlerror.c b/src/ldso/dlerror.c
index dae0f3a9..7cf55f17 100644
--- a/src/ldso/dlerror.c
+++ b/src/ldso/dlerror.c
@@ -8,6 +8,7 @@
 #define malloc __libc_malloc
 #define calloc __libc_calloc
 #define realloc __libc_realloc
+#define realloci __libc_realloci
 #define free __libc_free
 
 char *dlerror()
diff --git a/src/locale/dcngettext.c b/src/locale/dcngettext.c
index 0b53286d..782bb942 100644
--- a/src/locale/dcngettext.c
+++ b/src/locale/dcngettext.c
@@ -15,6 +15,7 @@
 #define malloc __libc_malloc
 #define calloc __libc_calloc
 #define realloc undef
+#define realloci undef
 #define free undef
 
 struct binding {
diff --git a/src/locale/duplocale.c b/src/locale/duplocale.c
index 5ce33ae6..093b3358 100644
--- a/src/locale/duplocale.c
+++ b/src/locale/duplocale.c
@@ -6,6 +6,7 @@
 #define malloc __libc_malloc
 #define calloc undef
 #define realloc undef
+#define realloci undef
 #define free undef
 
 locale_t __duplocale(locale_t old)
diff --git a/src/locale/freelocale.c b/src/locale/freelocale.c
index 385d1206..f73a0ada 100644
--- a/src/locale/freelocale.c
+++ b/src/locale/freelocale.c
@@ -4,6 +4,7 @@
 #define malloc undef
 #define calloc undef
 #define realloc undef
+#define realloci undef
 #define free __libc_free
 
 void freelocale(locale_t l)
diff --git a/src/locale/locale_map.c b/src/locale/locale_map.c
index da61f7fc..de49f1b7 100644
--- a/src/locale/locale_map.c
+++ b/src/locale/locale_map.c
@@ -10,6 +10,7 @@
 #define malloc __libc_malloc
 #define calloc undef
 #define realloc undef
+#define realloci undef
 #define free undef
 
 const char *__lctrans_impl(const char *msg, const struct __locale_map *lm)
diff --git a/src/locale/newlocale.c b/src/locale/newlocale.c
index 9ac3cd38..883c9512 100644
--- a/src/locale/newlocale.c
+++ b/src/locale/newlocale.c
@@ -7,6 +7,7 @@
 #define malloc __libc_malloc
 #define calloc undef
 #define realloc undef
+#define realloci undef
 #define free undef
 
 static int default_locale_init_done;
diff --git a/src/malloc/mallocng/glue.h b/src/malloc/mallocng/glue.h
index 77f4c812..37e6b6cd 100644
--- a/src/malloc/mallocng/glue.h
+++ b/src/malloc/mallocng/glue.h
@@ -22,6 +22,7 @@
 
 #define malloc __libc_malloc_impl
 #define realloc __libc_realloc
+#define realloci __libc_realloci
 #define free __libc_free
 
 #define USE_MADV_FREE 0
diff --git a/src/malloc/mallocng/realloc.c b/src/malloc/mallocng/realloc.c
index 18769f42..92f8eea5 100644
--- a/src/malloc/mallocng/realloc.c
+++ b/src/malloc/mallocng/realloc.c
@@ -15,15 +15,9 @@ void *realloc(void *p, size_t n)
 	unsigned char *start = g->mem->storage + stride*idx;
 	unsigned char *end = start + stride - IB;
 	size_t old_size = get_nominal_size(p, end);
-	size_t avail_size = end-(unsigned char *)p;
 	void *new;
 
-	// only resize in-place if size class matches
-	if (n <= avail_size && n<MMAP_THRESHOLD
-	    && size_to_class(n)+1 >= g->sizeclass) {
-		set_size(p, end, n);
-		return p;
-	}
+	if (realloci(p, n) == 0) return p;
 
 	// use mremap if old and new size are both mmap-worthy
 	if (g->sizeclass>=48 && n>=MMAP_THRESHOLD) {
diff --git a/src/malloc/mallocng/realloci.c b/src/malloc/mallocng/realloci.c
new file mode 100644
index 00000000..590f1b18
--- /dev/null
+++ b/src/malloc/mallocng/realloci.c
@@ -0,0 +1,26 @@
+#define _GNU_SOURCE
+#include <stdlib.h>
+#include <sys/mman.h>
+#include <string.h>
+#include "meta.h"
+
+int realloci(void *p, size_t n)
+{
+	if (size_overflows(n)) return -1;
+
+	struct meta *g = get_meta(p);
+	int idx = get_slot_index(p);
+	size_t stride = get_stride(g);
+	unsigned char *start = g->mem->storage + stride*idx;
+	unsigned char *end = start + stride - IB;
+	size_t avail_size = end-(unsigned char *)p;
+
+	// only resize in-place if size class matches
+	if (n <= avail_size && n<MMAP_THRESHOLD
+	    && size_to_class(n)+1 >= g->sizeclass) {
+		set_size(p, end, n);
+		return 0;
+	}
+
+	return -1;
+}
diff --git a/src/malloc/reallocarrayi.c b/src/malloc/reallocarrayi.c
new file mode 100644
index 00000000..8afaa761
--- /dev/null
+++ b/src/malloc/reallocarrayi.c
@@ -0,0 +1,13 @@
+#define _GNU_SOURCE
+#include <errno.h>
+#include <stdlib.h>
+
+int reallocarrayi(void *ptr, size_t m, size_t n)
+{
+	if (n && m > -1 / n) {
+		errno = ENOMEM;
+		return 0;
+	}
+
+	return realloci(ptr, m * n);
+}
diff --git a/src/malloc/realloci.c b/src/malloc/realloci.c
new file mode 100644
index 00000000..f1ba8138
--- /dev/null
+++ b/src/malloc/realloci.c
@@ -0,0 +1,7 @@
+#define _GNU_SOURCE
+#include <stdlib.h>
+
+int realloci(void *p, size_t n)
+{
+	return __libc_realloci(p, n);
+}
diff --git a/src/process/fdop.h b/src/process/fdop.h
index 7cf733b2..a25914d9 100644
--- a/src/process/fdop.h
+++ b/src/process/fdop.h
@@ -14,4 +14,5 @@ struct fdop {
 #define malloc __libc_malloc
 #define calloc __libc_calloc
 #define realloc undef
+#define realloci undef
 #define free __libc_free
diff --git a/src/thread/pthread_atfork.c b/src/thread/pthread_atfork.c
index 26d32543..c5951f81 100644
--- a/src/thread/pthread_atfork.c
+++ b/src/thread/pthread_atfork.c
@@ -6,6 +6,7 @@
 #define malloc __libc_malloc
 #define calloc undef
 #define realloc undef
+#define realloci undef
 #define free undef
 
 static struct atfork_funcs {
diff --git a/src/thread/sem_open.c b/src/thread/sem_open.c
index 0ad29de9..a74ae00d 100644
--- a/src/thread/sem_open.c
+++ b/src/thread/sem_open.c
@@ -17,6 +17,7 @@
 #define malloc __libc_malloc
 #define calloc __libc_calloc
 #define realloc undef
+#define realloci undef
 #define free undef
 
 static struct {
diff --git a/src/time/__tz.c b/src/time/__tz.c
index 54ed4cf6..76798fd0 100644
--- a/src/time/__tz.c
+++ b/src/time/__tz.c
@@ -12,6 +12,7 @@
 #define malloc __libc_malloc
 #define calloc undef
 #define realloc undef
+#define realloci undef
 #define free undef
 
 long  __timezone = 0;

Range-diff:
-:  -------- > 1:  6e1db6ad add realloci() and reallocarrayi()
-- 
2.51.0

Re: [musl] [RFC] add realloci() and reallocarrayi()

[Rich Felker]

On Fri, Oct 31, 2025 at 03:01:58PM +0100, Alejandro Colomar wrote:
> They are realloc(3) variants that work in-place.  They change the size
> of a block of memory, without affecting the lifetime of the object.
> It requires a non-null pointer, unlike realloc(3), as it can't create
> a new object (it doesn't return a pointer).
> 
> Cc: "A. Wilcox" <AWilcox@wilcox-tech.com>
> Cc: Lénárd Szolnoki <cpp@lenardszolnoki.com>
> Cc: Thorsten Glaser <tg@mirbsd.de>
> Cc: Collin Funk <collin.funk1@gmail.com>
> Signed-off-by: Alejandro Colomar <alx@kernel.org>
> ---
> 
> Hi,
> 
> I have not tested this patch (not even tried building yet).  It's just
> an initial draft, requesting comments about the overall idea.
> 
> So far, I've only implemented this in the mallocng implementation, as
> the oldmalloc implementation was too weird for me to fully understand.
> Do we need an old implementation too?
> 
> 
> Have a lovely day!
> Alex
> 
>  include/stdlib.h               |  2 ++
>  ldso/dynlink.c                 |  1 +
>  src/aio/aio.c                  |  1 +
>  src/exit/atexit.c              |  1 +
>  src/ldso/dlerror.c             |  1 +
>  src/locale/dcngettext.c        |  1 +
>  src/locale/duplocale.c         |  1 +
>  src/locale/freelocale.c        |  1 +
>  src/locale/locale_map.c        |  1 +
>  src/locale/newlocale.c         |  1 +
>  src/malloc/mallocng/glue.h     |  1 +
>  src/malloc/mallocng/realloc.c  |  8 +-------
>  src/malloc/mallocng/realloci.c | 26 ++++++++++++++++++++++++++
>  src/malloc/reallocarrayi.c     | 13 +++++++++++++
>  src/malloc/realloci.c          |  7 +++++++
>  src/process/fdop.h             |  1 +
>  src/thread/pthread_atfork.c    |  1 +
>  src/thread/sem_open.c          |  1 +
>  src/time/__tz.c                |  1 +
>  19 files changed, 63 insertions(+), 7 deletions(-)
>  create mode 100644 src/malloc/mallocng/realloci.c
>  create mode 100644 src/malloc/reallocarrayi.c
>  create mode 100644 src/malloc/realloci.c
> 
> diff --git a/include/stdlib.h b/include/stdlib.h
> index 475190bf..577b7172 100644
> --- a/include/stdlib.h
> +++ b/include/stdlib.h
> @@ -148,6 +148,8 @@ int clearenv(void);
>  #define WCOREDUMP(s) ((s) & 0x80)
>  #define WIFCONTINUED(s) ((s) == 0xffff)
>  void *reallocarray (void *, size_t, size_t);
> +int realloci (void *, size_t);
> +int reallocarrayi (void *, size_t);
>  void qsort_r (void *, size_t, size_t, int (*)(const void *, const void *, void *), void *);
>  #endif
>  
> diff --git a/ldso/dynlink.c b/ldso/dynlink.c
> index 715948f4..a882c5c1 100644
> --- a/ldso/dynlink.c
> +++ b/ldso/dynlink.c
> @@ -35,6 +35,7 @@ static size_t ldso_page_size;
>  #define malloc __libc_malloc
>  #define calloc __libc_calloc
>  #define realloc __libc_realloc
> +#define realloci __libc_realloci
>  #define free __libc_free

These gratuitous changes all over are not needed. realloci would never
be used internally so there's no reason to remap it or make a
libc-internal version of it. Same reason as for aligned_alloc, etc.
which aren't macro-redirected.

> diff --git a/src/malloc/mallocng/realloc.c b/src/malloc/mallocng/realloc.c
> index 18769f42..92f8eea5 100644
> --- a/src/malloc/mallocng/realloc.c
> +++ b/src/malloc/mallocng/realloc.c
> @@ -15,15 +15,9 @@ void *realloc(void *p, size_t n)
>  	unsigned char *start = g->mem->storage + stride*idx;
>  	unsigned char *end = start + stride - IB;
>  	size_t old_size = get_nominal_size(p, end);
> -	size_t avail_size = end-(unsigned char *)p;
>  	void *new;
>  
> -	// only resize in-place if size class matches
> -	if (n <= avail_size && n<MMAP_THRESHOLD
> -	    && size_to_class(n)+1 >= g->sizeclass) {
> -		set_size(p, end, n);
> -		return p;
> -	}
> +	if (realloci(p, n) == 0) return p;

This is a namespace violation. realloc can't depend on realloci.

Rich

Re: [musl] [RFC] add realloci() and reallocarrayi()

[Alejandro Colomar]

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

Hi Rich,

On Fri, Oct 31, 2025 at 09:02:09PM -0400, Rich Felker wrote:
> > diff --git a/ldso/dynlink.c b/ldso/dynlink.c
> > index 715948f4..a882c5c1 100644
> > --- a/ldso/dynlink.c
> > +++ b/ldso/dynlink.c
> > @@ -35,6 +35,7 @@ static size_t ldso_page_size;
> >  #define malloc __libc_malloc
> >  #define calloc __libc_calloc
> >  #define realloc __libc_realloc
> > +#define realloci __libc_realloci
> >  #define free __libc_free
> 
> These gratuitous changes all over are not needed. realloci would never
> be used internally so there's no reason to remap it or make a
> libc-internal version of it. Same reason as for aligned_alloc, etc.
> which aren't macro-redirected.

Thanks!  I wasn't sure what that was for.

> > diff --git a/src/malloc/mallocng/realloc.c b/src/malloc/mallocng/realloc.c
> > index 18769f42..92f8eea5 100644
> > --- a/src/malloc/mallocng/realloc.c
> > +++ b/src/malloc/mallocng/realloc.c
> > @@ -15,15 +15,9 @@ void *realloc(void *p, size_t n)
> >  	unsigned char *start = g->mem->storage + stride*idx;
> >  	unsigned char *end = start + stride - IB;
> >  	size_t old_size = get_nominal_size(p, end);
> > -	size_t avail_size = end-(unsigned char *)p;
> >  	void *new;
> >  
> > -	// only resize in-place if size class matches
> > -	if (n <= avail_size && n<MMAP_THRESHOLD
> > -	    && size_to_class(n)+1 >= g->sizeclass) {
> > -		set_size(p, end, n);
> > -		return p;
> > -	}
> > +	if (realloci(p, n) == 0) return p;
> 
> This is a namespace violation. realloc can't depend on realloci.

Okay.  Thanks!

> 
> Rich

Have a lovely day!
Alex

-- 
<https://www.alejandro-colomar.es>
Use port 80 (that is, <...:80/>).

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

Re: [musl] [RFC] add realloci() and reallocarrayi()

[Markus Wichmann]

Am Fri, Oct 31, 2025 at 03:01:58PM +0100 schrieb Alejandro Colomar:
> Hi,
> 
> I have not tested this patch (not even tried building yet).  It's just
> an initial draft, requesting comments about the overall idea.
> 
> So far, I've only implemented this in the mallocng implementation, as
> the oldmalloc implementation was too weird for me to fully understand.
> Do we need an old implementation too?
> 

Whether we need one or not probably depends on if the proposal is
accepted by the C standard, which, judging from the other thread, is
currently up in the air.

Oldmalloc is a pretty simple malloc implementation. On the high level,
there are two allocators: One for large allocations (above
MMAP_THRESHOLD) and one for smaller allocations.

The large allocations use mmap() directly. They are identified at
runtime by having even used chunks not have the C_INUSE flag set for
their size. The psize indicates the offset to the start of the mapped
page, for alignment reasons. For large allocations, realloci() could
probably be implemented by calling mremap() *without* MREMAP_MAYMOVE.

Small allocations use a linked list approach: Each chunk knows its size
and its predecessor's size. Memory blocks are terminated with zero-sized
pseudo-chunks that are always in use. Additionally, free chunks are
added to doubly-linked lists called "bins", where they are classified by
size. The specifics don't really matter for realloci(). You can probably
implement it by combining the current chunk with its successors until
either the size requirement is met or you run into a chunk that is in
use. At the end, you can also split the chunk to shrink it to fit the
request exactly, and leave the rest over to future allocations.

For requests that jump the boundary between those two allocators: I
don't really see the harm in having a chunk start out as mmapped chunk
and become remapped to be smaller. Obviously, the effective size cannot
shrink below 1 page (minus whatever alignment overhead was reserved),
but just having that page dangle about and eventually be unmapped by
free(), though maybe inefficient, is probably not harmful.

The other direction, Rich has in the past spoken out about how there
should not be allocated managed chunks larger than MMAP_THRESHOLD in
size. I don't quite see the issue myself (allocated chunks only matter
in the chunk list in each block, where the size class doesn't matter,
and freed chunks are joined with their free predecessors and successors
to possibly form a size above MMAP_THRESHOLD anyway), but perhaps I am
missing something.

Ciao,
Markus

Re: [musl] [RFC] add realloci() and reallocarrayi()

[Rich Felker]

On Sat, Nov 01, 2025 at 10:41:05PM +0100, Markus Wichmann wrote:
> Am Fri, Oct 31, 2025 at 03:01:58PM +0100 schrieb Alejandro Colomar:
> > Hi,
> > 
> > I have not tested this patch (not even tried building yet).  It's just
> > an initial draft, requesting comments about the overall idea.
> > 
> > So far, I've only implemented this in the mallocng implementation, as
> > the oldmalloc implementation was too weird for me to fully understand.
> > Do we need an old implementation too?
> > 
> 
> Whether we need one or not probably depends on if the proposal is
> accepted by the C standard, which, judging from the other thread, is
> currently up in the air.
> 
> Oldmalloc is a pretty simple malloc implementation. On the high level,
> there are two allocators: One for large allocations (above
> MMAP_THRESHOLD) and one for smaller allocations.
> 
> The large allocations use mmap() directly. They are identified at
> runtime by having even used chunks not have the C_INUSE flag set for
> their size. The psize indicates the offset to the start of the mapped
> page, for alignment reasons. For large allocations, realloci() could
> probably be implemented by calling mremap() *without* MREMAP_MAYMOVE.
> 
> Small allocations use a linked list approach: Each chunk knows its size
> and its predecessor's size. Memory blocks are terminated with zero-sized
> pseudo-chunks that are always in use. Additionally, free chunks are
> added to doubly-linked lists called "bins", where they are classified by
> size. The specifics don't really matter for realloci(). You can probably
> implement it by combining the current chunk with its successors until
> either the size requirement is met or you run into a chunk that is in
> use. At the end, you can also split the chunk to shrink it to fit the
> request exactly, and leave the rest over to future allocations.
> 
> For requests that jump the boundary between those two allocators: I
> don't really see the harm in having a chunk start out as mmapped chunk
> and become remapped to be smaller. Obviously, the effective size cannot
> shrink below 1 page (minus whatever alignment overhead was reserved),
> but just having that page dangle about and eventually be unmapped by
> free(), though maybe inefficient, is probably not harmful.

It is very harmful. It causes catastrophic fragmentation and
exhaustion of vma limit under otherwise very reasonable patterns.
There is no good reason to try to keep such reallocs "in-place". The
existing strategy of malloc-memcpy-free is very intentional.

> The other direction, Rich has in the past spoken out about how there
> should not be allocated managed chunks larger than MMAP_THRESHOLD in
> size. I don't quite see the issue myself (allocated chunks only matter
> in the chunk list in each block, where the size class doesn't matter,
> and freed chunks are joined with their free predecessors and successors
> to possibly form a size above MMAP_THRESHOLD anyway), but perhaps I am
> missing something.

In any case, oldmalloc is basically only there because there's no good
reason to remove it. I'm not particularly interested in adding new
code to it. A perfectly reasonable realloci (or whatever)
implementation for it would just be one that always fails.

Overall, I am so far utterly unconvinced that any of this proposal is
well-motivated. It seems like grasping at straws trying to mitigate
flaws in STL implementations' resizing strategies that can't really be
fixed at this layer (and that would require major revamps on their
size to use anything new from this layer), but that could be largely
or entirely fixed on the STL side just by being smarter about the
strategy for choosing sizes. As I've said multiple times, being able
to do significant enlargement of an object in-place is, asymptotically
in the presence of large malloc load, always going to fail. At best
you can reclaim some slack from the gaps between the allocator's size
granularity scale and the calling application's (or STL's) choice of
growth strategy increments.

Rich