[RFT] malloc: reduce largebin granularity to reduce fragmentation

Message ID 20240409093352.M757838@dcvr
State Under Review
Delegated to: Florian Weimer
Series [RFT] malloc: reduce largebin granularity to reduce fragmentation |


Context Check Description
redhat-pt-bot/TryBot-apply_patch success Patch applied to master at the time it was sent
redhat-pt-bot/TryBot-32bit success Build for i686
linaro-tcwg-bot/tcwg_glibc_build--master-aarch64 success Testing passed
linaro-tcwg-bot/tcwg_glibc_check--master-aarch64 success Testing passed
linaro-tcwg-bot/tcwg_glibc_build--master-arm success Testing passed
linaro-tcwg-bot/tcwg_glibc_check--master-arm success Testing passed

Commit Message

Eric Wong April 9, 2024, 9:33 a.m. UTC
  Anybody volunteers to help test and get reproducible results for
this?  Thanks in advance.

Testing and getting reproducible results is proving extremely
expensive due to trace sizes and CPU usage required to handle
my existing web/IMAP/NNTP-facing traffic.

But the theory works in my mind and could be a solution to a
problem I've noticed for decades at this point across long-lived
Ruby and Perl web daemons.

I'm also considering having this as a tunable and mallopt(3).

And perhaps limiting the alignment to pagesize can work, because
20% of a large sliding mmap_threshold on 64-bit is several

From: Eric Wong <normalperson@yhbt.net>
Subject: [PATCH] malloc: reduce largebin granularity to reduce fragmentation

TL;DR: trade initial best fits for better fits over long process

Size classes in modern versions of jemalloc add a 0-20% overhead
in an attempt to get better fits over time when dealing with
unpredictably-sized allocations and frees.  Initially, this can
be more wasteful than the best (initial) fit strategy used by
dlmalloc, but less wasteful than buddy allocators (which can
have 0-99% overhead).

While the dlmalloc "best fit" strategy is ideal for one-off
permanent allocations and applications that only deal in uniform
allocation sizes; "best fit" gets bogged down over time when
dealing with variably-sized allocations with mixed and
interleaving lifetimes commonly seen in high-level language

Such allocation patterns are common in long-lived web app, NNTP,
and IMAP servers doing text processing with concurrent ("C10K").
Unpredictable lifetimes are often a result of resource sharing
between network clients of disparate lifetimes, but some of it
is outside the application developers control.

Fragmentation is further exacerbated by long-lived allocations
happening late in process life of high-level language runtimes
(e.g. Perl and Ruby).  These runtimes and their standard
libraries can trigger long-lived allocations late in process
life due to the use lazy loading, caching, and internal slab
allocators using malloc to create slabs.

This change only affects largebin allocations which are too
small for mmap, and too small for smallbins and fastbins.
 malloc/malloc.c | 60 +++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 60 insertions(+)


diff --git a/malloc/malloc.c b/malloc/malloc.c
index bcb6e5b83c..9a1057f5a7 100644
--- a/malloc/malloc.c
+++ b/malloc/malloc.c
@@ -3288,6 +3288,56 @@  tcache_thread_shutdown (void)
 #endif /* !USE_TCACHE  */
+ * Use jemalloc-inspired size classes for largebin allocations to
+ * minimize fragmentation.  This means we pay a 0-20% overhead on
+ * allocations to improve the likelyhood of reuse across many
+ * odd-sized allocations and frees.  This should reduce fragmentation
+ * in long-lived applications processing various text fragments
+ * (e.g. mail, news, and web services)
+ */
+static inline void
+size_class_align (size_t *nb, size_t *req)
+  // TODO: make this a mallopt + tunable?
+  if (in_smallbin_range (*nb))
+    return;
+  size_t mm_thresh = MAX (DEFAULT_MMAP_THRESHOLD_MAX, mp_.mmap_threshold);
+  if (*nb >= mm_thresh && mp_.n_mmaps < mp_.n_mmaps_max)
+    return;
+  size_t n = *req - 1;
+  for (size_t i = 1; i < sizeof (size_t) * CHAR_BIT; i <<= 1)
+    n |= n >> i;
+  size_t next_power_of_two = n + 1;
+  /*
+   * This size alignment causes up to 20% overhead which can be several
+   * megabytes on 64-bit systems with high mmap_threshold.  Perhaps we
+   * can clamp alignment to pagesize or similar to save space.
+   */
+  size_t align = next_power_of_two >> 3;
+  size_t areq = ALIGN_UP (*req, align);
+  size_t anb = checked_request2size (areq);
+  if (anb == 0)
+    return; // aligned size is too big, but unaligned wasn't
+  if (anb < mm_thresh || mp_.n_mmaps >= mp_.n_mmaps_max)
+    {
+      *nb = anb;
+      *req = areq;
+    }
+  else // too big for largebins, force it to mmap
+    {
+      *nb = mm_thresh;
+    }
 #if IS_IN (libc)
 void *
 __libc_malloc (size_t bytes)
@@ -3308,6 +3358,7 @@  __libc_malloc (size_t bytes)
       __set_errno (ENOMEM);
       return NULL;
+  size_class_align (&tbytes, &bytes);
   size_t tc_idx = csize2tidx (tbytes);
@@ -3503,6 +3554,8 @@  __libc_realloc (void *oldmem, size_t bytes)
       return newmem;
+  size_class_align (&nb, &bytes);
       newp = _int_realloc (ar_ptr, oldp, oldsize, nb);
@@ -3713,6 +3766,13 @@  __libc_calloc (size_t n, size_t elem_size)
   sz = bytes;
+  size_t nb = checked_request2size (sz);
+  if (nb == 0)
+    {
+      __set_errno (ENOMEM);
+      return NULL;
+    }
+  size_class_align (&nb, &sz);
   if (!__malloc_initialized)
     ptmalloc_init ();