[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;
>  }