[PATCH] realloc: Return unchanged if request is within usable size

[PATCH] realloc: Return unchanged if request is within usable size

[Siddhesh Poyarekar via Libc-alpha]

If there is enough space in the chunk to satisfy the new size, return
the old pointer as is, thus avoiding any locks or reallocations.  The
only real place this has a benefit is in large chunks that tend to get
satisfied with mmap, since there is a large enough spare size (up to a
page) for it to matter.  For allocations on heap, the extra size is
typically barely a few bytes (up to 15) and it's unlikely that it would
make much difference in performance.

Also added a smoke test to ensure that the old pointer is returned
unchanged if the new size to realloc is within usable size of the old
pointer.

Signed-off-by: Siddhesh Poyarekar <siddhesh@sourceware.org>
---
 malloc/malloc.c      |  6 ++++++
 malloc/tst-realloc.c | 21 +++++++++++++++++++++
 2 files changed, 27 insertions(+)

diff --git a/malloc/malloc.c b/malloc/malloc.c
index 2a61c8b5ee..3ef61bef34 100644
--- a/malloc/malloc.c
+++ b/malloc/malloc.c
@@ -1100,6 +1100,8 @@ static void munmap_chunk(mchunkptr p);
 static mchunkptr mremap_chunk(mchunkptr p, size_t new_size);
 #endif
 
+static size_t musable (void *mem);
+
 /* ------------------ MMAP support ------------------  */
 
 
@@ -3396,6 +3398,10 @@ __libc_realloc (void *oldmem, size_t bytes)
   if (__glibc_unlikely (mtag_enabled))
     *(volatile char*) oldmem;
 
+  /* If there's usable space in the current chunk, return as is.  */
+  if (bytes <= musable (oldmem))
+    return oldmem;
+
   /* chunk corresponding to oldmem */
   const mchunkptr oldp = mem2chunk (oldmem);
   /* its size */
diff --git a/malloc/tst-realloc.c b/malloc/tst-realloc.c
index 5eb62a770f..54dd0dd0b3 100644
--- a/malloc/tst-realloc.c
+++ b/malloc/tst-realloc.c
@@ -142,6 +142,27 @@ do_test (void)
 
   free (p);
 
+  /* Smoke test to make sure that allocations do not move if they have enough
+     space to expand in the chunk.  */
+  for (size_t sz = 3; sz < 256 * 1024; sz += 2048)
+    {
+      p = realloc (NULL, sz);
+      if (p == NULL)
+	FAIL_EXIT1 ("realloc (NULL, 31) returned NULL.");
+      size_t newsz = malloc_usable_size (p);
+      printf ("size: %zu, usable size: %zu, extra: %zu\n",
+	      sz, newsz, newsz - sz);
+      void *new_p = realloc (p, newsz);
+      if (new_p != p)
+	FAIL_EXIT1 ("Expanding (%zu bytes) to usable size (%zu) moved block",
+		    sz, newsz);
+      free (new_p);
+
+      /* We encountered a large enough extra size at least once.  */
+      if (newsz - sz > 1024)
+	break;
+    }
+
   return 0;
 }
 
-- 
2.38.1

Re: [PATCH] realloc: Return unchanged if request is within usable size

[Andreas Schwab]

On Nov 25 2022, Siddhesh Poyarekar via Libc-alpha wrote:

> +  /* Smoke test to make sure that allocations do not move if they have enough
> +     space to expand in the chunk.  */
> +  for (size_t sz = 3; sz < 256 * 1024; sz += 2048)
> +    {
> +      p = realloc (NULL, sz);
> +      if (p == NULL)
> +	FAIL_EXIT1 ("realloc (NULL, 31) returned NULL.");

s/31/sz/

> +      size_t newsz = malloc_usable_size (p);
> +      printf ("size: %zu, usable size: %zu, extra: %zu\n",
> +	      sz, newsz, newsz - sz);
> +      void *new_p = realloc (p, newsz);
> +      if (new_p != p)

The compiler is allowed to optimize this to true under the assumption
that new_p == NULL (the only case where p is still a valid pointer).

-- 
Andreas Schwab, schwab@linux-m68k.org
GPG Key fingerprint = 7578 EB47 D4E5 4D69 2510  2552 DF73 E780 A9DA AEC1
"And now for something completely different."

Re: [PATCH] realloc: Return unchanged if request is within usable size

[Siddhesh Poyarekar via Libc-alpha]

On 2022-11-25 15:40, Andreas Schwab wrote:
> On Nov 25 2022, Siddhesh Poyarekar via Libc-alpha wrote:
> 
>> +  /* Smoke test to make sure that allocations do not move if they have enough
>> +     space to expand in the chunk.  */
>> +  for (size_t sz = 3; sz < 256 * 1024; sz += 2048)
>> +    {
>> +      p = realloc (NULL, sz);
>> +      if (p == NULL)
>> +	FAIL_EXIT1 ("realloc (NULL, 31) returned NULL.");
> 
> s/31/sz/
> 
>> +      size_t newsz = malloc_usable_size (p);
>> +      printf ("size: %zu, usable size: %zu, extra: %zu\n",
>> +	      sz, newsz, newsz - sz);
>> +      void *new_p = realloc (p, newsz);
>> +      if (new_p != p)
> 
> The compiler is allowed to optimize this to true under the assumption
> that new_p == NULL (the only case where p is still a valid pointer).
> 

Hmm, I suppose something like this then?

     for (...)
       {
         ...
         volatile uintptr_t oldp = p;
         void *new_p = realloc (p, newsz)
         if (new_p != oldp)
           ...
       }

Thanks,
Sid

Re: [PATCH] realloc: Return unchanged if request is within usable size

[Andreas Schwab]

On Nov 28 2022, Siddhesh Poyarekar via Libc-alpha wrote:

> Hmm, I suppose something like this then?
>
>     for (...)
>       {
>         ...
>         volatile uintptr_t oldp = p;
>         void *new_p = realloc (p, newsz)
>         if (new_p != oldp)
>           ...

You'll need some casts, but I don't think the volatile is needed.

-- 
Andreas Schwab, schwab@linux-m68k.org
GPG Key fingerprint = 7578 EB47 D4E5 4D69 2510  2552 DF73 E780 A9DA AEC1
"And now for something completely different."

[PATCH v2] realloc: Return unchanged if request is within usable size

[Siddhesh Poyarekar via Libc-alpha]

If there is enough space in the chunk to satisfy the new size, return
the old pointer as is, thus avoiding any locks or reallocations.  The
only real place this has a benefit is in large chunks that tend to get
satisfied with mmap, since there is a large enough spare size (up to a
page) for it to matter.  For allocations on heap, the extra size is
typically barely a few bytes (up to 15) and it's unlikely that it would
make much difference in performance.

Also added a smoke test to ensure that the old pointer is returned
unchanged if the new size to realloc is within usable size of the old
pointer.

Signed-off-by: Siddhesh Poyarekar <siddhesh@sourceware.org>
---
Changes from v1:
- Fixed up test as per review comments
- Do the realloc bypass only when the new size is within trim_threshold
  bytes of the usable size so that shrinking does not hold up memory.

 malloc/malloc.c      | 10 ++++++++++
 malloc/tst-realloc.c | 23 +++++++++++++++++++++++
 2 files changed, 33 insertions(+)

diff --git a/malloc/malloc.c b/malloc/malloc.c
index 2a61c8b5ee..ef8c794fb7 100644
--- a/malloc/malloc.c
+++ b/malloc/malloc.c
@@ -1100,6 +1100,8 @@ static void munmap_chunk(mchunkptr p);
 static mchunkptr mremap_chunk(mchunkptr p, size_t new_size);
 #endif
 
+static size_t musable (void *mem);
+
 /* ------------------ MMAP support ------------------  */
 
 
@@ -3396,6 +3398,14 @@ __libc_realloc (void *oldmem, size_t bytes)
   if (__glibc_unlikely (mtag_enabled))
     *(volatile char*) oldmem;
 
+  /* Return the chunk as is whenever possible, i.e. there's enough usable space
+     but not so much that we end up fragmenting the block.  We use the trim
+     threshold as the heuristic to decide the latter.  */
+  size_t usable = musable (oldmem);
+  if (bytes <= usable
+      && (unsigned long) (usable - bytes) <= mp_.trim_threshold)
+    return oldmem;
+
   /* chunk corresponding to oldmem */
   const mchunkptr oldp = mem2chunk (oldmem);
   /* its size */
diff --git a/malloc/tst-realloc.c b/malloc/tst-realloc.c
index 5eb62a770f..3b78a2420a 100644
--- a/malloc/tst-realloc.c
+++ b/malloc/tst-realloc.c
@@ -17,6 +17,7 @@
 
 #include <errno.h>
 #include <malloc.h>
+#include <stdint.h>
 #include <stdio.h>
 #include <string.h>
 #include <libc-diag.h>
@@ -142,6 +143,28 @@ do_test (void)
 
   free (p);
 
+  /* Smoke test to make sure that allocations do not move if they have enough
+     space to expand in the chunk.  */
+  for (size_t sz = 3; sz < 256 * 1024; sz += 2048)
+    {
+      p = realloc (NULL, sz);
+      if (p == NULL)
+	FAIL_EXIT1 ("realloc (NULL, %zu) returned NULL.", sz);
+      size_t newsz = malloc_usable_size (p);
+      printf ("size: %zu, usable size: %zu, extra: %zu\n",
+	      sz, newsz, newsz - sz);
+      uintptr_t oldp = (uintptr_t) p;
+      void *new_p = realloc (p, newsz);
+      if ((uintptr_t) new_p != oldp)
+	FAIL_EXIT1 ("Expanding (%zu bytes) to usable size (%zu) moved block",
+		    sz, newsz);
+      free (new_p);
+
+      /* We encountered a large enough extra size at least once.  */
+      if (newsz - sz > 1024)
+	break;
+    }
+
   return 0;
 }
 
-- 
2.38.1

Re: [PATCH v2] realloc: Return unchanged if request is within usable size

[DJ Delorie via Libc-alpha]

Siddhesh Poyarekar via Libc-alpha <libc-alpha@sourceware.org> writes:
> Signed-off-by: Siddhesh Poyarekar <siddhesh@sourceware.org>

LGTM
Reviewed-by: DJ Delorie <dj@redhat.com>

> diff --git a/malloc/malloc.c b/malloc/malloc.c
> index 2a61c8b5ee..ef8c794fb7 100644
> --- a/malloc/malloc.c
> +++ b/malloc/malloc.c
> @@ -1100,6 +1100,8 @@ static void munmap_chunk(mchunkptr p);
>  static mchunkptr mremap_chunk(mchunkptr p, size_t new_size);
>  #endif
>  
> +static size_t musable (void *mem);

Matches function which occurs later on

> +  /* Return the chunk as is whenever possible, i.e. there's enough usable space
> +     but not so much that we end up fragmenting the block.  We use the trim
> +     threshold as the heuristic to decide the latter.  */
> +  size_t usable = musable (oldmem);
> +  if (bytes <= usable
> +      && (unsigned long) (usable - bytes) <= mp_.trim_threshold)
> +    return oldmem;

Ok.

> diff --git a/malloc/tst-realloc.c b/malloc/tst-realloc.c
> +#include <stdint.h>

Ok.

>  
> +  /* Smoke test to make sure that allocations do not move if they have enough
> +     space to expand in the chunk.  */
> +  for (size_t sz = 3; sz < 256 * 1024; sz += 2048)
> +    {
> +      p = realloc (NULL, sz);

size 3, 2051, 4099... always 3 bytes more than a 2048-boundary

> +      if (p == NULL)
> +	FAIL_EXIT1 ("realloc (NULL, %zu) returned NULL.", sz);
> +      size_t newsz = malloc_usable_size (p);

Ok.

> +      printf ("size: %zu, usable size: %zu, extra: %zu\n",
> +	      sz, newsz, newsz - sz);
> +      uintptr_t oldp = (uintptr_t) p;
> +      void *new_p = realloc (p, newsz);

Should always work; either we're within a few words, or within a page
(mmap).  Ok.

> +      if ((uintptr_t) new_p != oldp)
> +	FAIL_EXIT1 ("Expanding (%zu bytes) to usable size (%zu) moved block",
> +		    sz, newsz);
> +      free (new_p);
> +
> +      /* We encountered a large enough extra size at least once.  */
> +      if (newsz - sz > 1024)
> +	break;

Ok.

> +
>    return 0;
>  }

[PATCH] realloc: Return unchanged if request is within usable size

[Wilco Dijkstra via Libc-alpha]

Hi Siddhesh,

I think the idea of having a fast path in realloc is good since it is a more standard
interface than malloc_usable_size, so improving performance for obvious cases
where we can return the original pointer makes sense. It will help badly written
code that does a realloc when growing an array 1 element at a time.

However the proposed patch will block realloc from ever releasing memory...
We do need to handle the case where the size is smaller than the usable size since
we'd still want to free the unused portion if it is a significant fraction of the total size.
Note the mmap code always tries to remap before checking the new size is smaller
than usable size - so will end up remapping even if you downsize by one page.

Cheers,
Wilco

Re: [PATCH] realloc: Return unchanged if request is within usable size

[Siddhesh Poyarekar via Libc-alpha]

On 2022-11-28 04:22, Wilco Dijkstra wrote:
> Hi Siddhesh,
> 
> I think the idea of having a fast path in realloc is good since it is a more standard
> interface than malloc_usable_size, so improving performance for obvious cases
> where we can return the original pointer makes sense. It will help badly written
> code that does a realloc when growing an array 1 element at a time.
> 
> However the proposed patch will block realloc from ever releasing memory...

Thanks for pointing that out, I missed it.

> We do need to handle the case where the size is smaller than the usable size since
> we'd still want to free the unused portion if it is a significant fraction of the total size.

I'll make this a function of trim_threshold so that the reuse happens 
only if the difference between the request and usable size is less than 
the trim_threshold.

> Note the mmap code always tries to remap before checking the new size is smaller
> than usable size - so will end up remapping even if you downsize by one page.

I don't see that; I've put the musable check before the 
chunk_is_mmapped() check.  What am I missing?

Thanks,
Sid

Re: [PATCH] realloc: Return unchanged if request is within usable size

[Wilco Dijkstra via Libc-alpha]

Hi Siddhesh,

>> We do need to handle the case where the size is smaller than the usable size since
>> we'd still want to free the unused portion if it is a significant fraction of the total size.
>
> I'll make this a function of trim_threshold so that the reuse happens 
> only if the difference between the request and usable size is less than 
> the trim_threshold.

That's better, but that really only helps the mmap case, and all other reallocs will
never release memory due to the 128KB default value of trim_threshold.
That's something we should explicitly decide/document and remove any redundant
code from realloc as a result.

>> Note the mmap code always tries to remap before checking the new size is smaller
>> than usable size - so will end up remapping even if you downsize by one page.
>
> I don't see that; I've put the musable check before the 
> chunk_is_mmapped() check.  What am I missing?

I'm talking about the committed version, basically if there is any change in number of
pages it will do a system call. With your change there must be at least 128KB worth of
pages to be freed. We should do something similar for growing mmaps - large blocks
should never grow/shrink a single page at a time.

Cheers,
Wilco

Re: [PATCH] realloc: Return unchanged if request is within usable size

[Siddhesh Poyarekar via Libc-alpha]

On 2022-12-06 07:45, Wilco Dijkstra wrote:
> Hi Siddhesh,
> 
>>> We do need to handle the case where the size is smaller than the usable size since
>>> we'd still want to free the unused portion if it is a significant fraction of the total size.
>>
>> I'll make this a function of trim_threshold so that the reuse happens
>> only if the difference between the request and usable size is less than
>> the trim_threshold.
> 
> That's better, but that really only helps the mmap case, and all other reallocs will
> never release memory due to the 128KB default value of trim_threshold.

What I'm trying to ensure here is that holes are always less than the 
trim threshold.

> That's something we should explicitly decide/document and remove any redundant
> code from realloc as a result.

OK, I see the MINSIZE split is no longer relevant.

>>> Note the mmap code always tries to remap before checking the new size is smaller
>>> than usable size - so will end up remapping even if you downsize by one page.
>>
>> I don't see that; I've put the musable check before the
>> chunk_is_mmapped() check.  What am I missing?
> 
> I'm talking about the committed version, basically if there is any change in number of
> pages it will do a system call. With your change there must be at least 128KB worth of
> pages to be freed. We should do something similar for growing mmaps - large blocks
> should never grow/shrink a single page at a time.

Hmm, let me think about this.  I reckon this is going to need more 
sophisticated heuristics.

Thanks,
Sid

Re: [PATCH] realloc: Return unchanged if request is within usable size

[Aurelien Jarno]

Hi Siddhesh and Wilco,

On 2022-12-06 12:45, Wilco Dijkstra via Libc-alpha wrote:
> Hi Siddhesh,
> 
> >> We do need to handle the case where the size is smaller than the usable size since
> >> we'd still want to free the unused portion if it is a significant fraction of the total size.
> >
> > I'll make this a function of trim_threshold so that the reuse happens 
> > only if the difference between the request and usable size is less than 
> > the trim_threshold.
> 
> That's better, but that really only helps the mmap case, and all other reallocs will
> never release memory due to the 128KB default value of trim_threshold.
> That's something we should explicitly decide/document and remove any redundant
> code from realloc as a result.

This actually breaks the KDE Plasma Desktop, and more precisely
plasmashell when used with long configuration files [1] [2]. This commit
causes the virtual memory allocation to increase from ~2GB to ~11GB in
my testcase, while the resident memory basically stays stable. In turns
this prevent the clone syscall to work with the default kernel
overcommit configuration.

At this stage, I haven't identified the allocation pattern nor the
corresponding code in plasmashell.

Besides tweaking the configuration files, possible workarounds are
defining the glibc.malloc.trim_threshold GLIBC tunable to a low value
(for instance 128) or changing the vm.overcommit_memory kernel
configuration to 1. I guess the latter doesn't work on 32-bit
architectures though.

Regards,
Aurelien

[1] https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=1040140
[2] https://bbs.archlinux.org/viewtopic.php?id=283372

-- 
Aurelien Jarno                          GPG: 4096R/1DDD8C9B
aurelien@aurel32.net                     http://aurel32.net

Re: [PATCH] realloc: Return unchanged if request is within usable size

[Siddhesh Poyarekar via Libc-alpha]

On 2023-07-03 18:02, Aurelien Jarno wrote:
> This actually breaks the KDE Plasma Desktop, and more precisely
> plasmashell when used with long configuration files [1] [2]. This commit
> causes the virtual memory allocation to increase from ~2GB to ~11GB in
> my testcase, while the resident memory basically stays stable. In turns
> this prevent the clone syscall to work with the default kernel
> overcommit configuration.
> 
> At this stage, I haven't identified the allocation pattern nor the
> corresponding code in plasmashell.

I had dismissed this in a recent bug report[1] but I'm obviously wrong. 
I think I could make this conditional on usable - bytes being within 2 * 
SIZE_T for heap allocations (thus only catering for expansions) and 
within trim_threshold for mmap'd allocations to reduce the fragmentation.

> Besides tweaking the configuration files, possible workarounds are
> defining the glibc.malloc.trim_threshold GLIBC tunable to a low value
> (for instance 128) or changing the vm.overcommit_memory kernel
> configuration to 1. I guess the latter doesn't work on 32-bit
> architectures though.

Right, the trim_threshold change was what I had suggested, but if it's 
impacting more than the odd application, the default behaviour is 
problematic.  I'll try to post a fix today.

Thanks,
Sid

[1] https://sourceware.org/bugzilla/show_bug.cgi?id=30579

Re: [PATCH] realloc: Return unchanged if request is within usable size

[Aurelien Jarno]

Hi,

On 2023-07-04 07:17, Siddhesh Poyarekar via Libc-alpha wrote:
> On 2023-07-03 18:02, Aurelien Jarno wrote:
> > This actually breaks the KDE Plasma Desktop, and more precisely
> > plasmashell when used with long configuration files [1] [2]. This commit
> > causes the virtual memory allocation to increase from ~2GB to ~11GB in
> > my testcase, while the resident memory basically stays stable. In turns
> > this prevent the clone syscall to work with the default kernel
> > overcommit configuration.
> > 
> > At this stage, I haven't identified the allocation pattern nor the
> > corresponding code in plasmashell.
> 
> I had dismissed this in a recent bug report[1] but I'm obviously wrong. I
> think I could make this conditional on usable - bytes being within 2 *
> SIZE_T for heap allocations (thus only catering for expansions) and within
> trim_threshold for mmap'd allocations to reduce the fragmentation.

Just another datapoint that can be helpful: setting
glibc.malloc.trim_threshold to 128K (the initial value, but fixed) also
workarounds the issue. So it seems the issue is a combination of the
dynamic adjustment of trim_threshold and this change to realloc.

> > Besides tweaking the configuration files, possible workarounds are
> > defining the glibc.malloc.trim_threshold GLIBC tunable to a low value
> > (for instance 128) or changing the vm.overcommit_memory kernel
> > configuration to 1. I guess the latter doesn't work on 32-bit
> > architectures though.
> 
> Right, the trim_threshold change was what I had suggested, but if it's
> impacting more than the odd application, the default behaviour is
> problematic.  I'll try to post a fix today.

Great, thanks a lot.

Regards,
Aurelien

-- 
Aurelien Jarno                          GPG: 4096R/1DDD8C9B
aurelien@aurel32.net                     http://aurel32.net