[PATCH v7 1/2] malloc: add tcache support for large chunk caching
Cupertino Miranda
cupertino.miranda@oracle.com
Wed May 21 13:14:05 GMT 2025
Existing tcache implementation in glibc seems to focus in caching
smaller data size allocations, limiting the size of the allocation to
1KB.
This patch changes tcache implementation to allow to cache chunks up to
4MB. The implementation adds extra bins (linked-lists) which store
chunks with different ranges of allocation sizes. Bin selection is done
in multiples in powers of 2 and chunks are inserted in growing size
ordering within the bin. The last bin contains all other sizes of
allocations.
This patch although by default preserves the same implementation,
limitting caches to 1KB chunks, it now allows to increase the max size
for the cached chunks with the tunable glibc.malloc.tcache_max.
---
malloc/malloc.c | 225 ++++++++++++++++++++++++++++++++++++------------
1 file changed, 170 insertions(+), 55 deletions(-)
diff --git a/malloc/malloc.c b/malloc/malloc.c
index fe56a631bc..6e834b0bc3 100644
--- a/malloc/malloc.c
+++ b/malloc/malloc.c
@@ -292,7 +292,11 @@
#if USE_TCACHE
/* We want 64 entries. This is an arbitrary limit, which tunables can reduce. */
# define TCACHE_MAX_BINS 64
+# define TCACHE_LARGE_BINS 12 /* Up to 4M chunks */
+# define TCACHE_ALL_BINS (TCACHE_MAX_BINS + TCACHE_LARGE_BINS)
# define MAX_TCACHE_SIZE tidx2usize (TCACHE_MAX_BINS-1)
+# define MAX_TCACHE_LARGE_SIZE \
+ (1 << (31 - __builtin_clz (MAX_TCACHE_SIZE) + TCACHE_LARGE_BINS))
/* Only used to pre-fill the tunables. */
# define tidx2usize(idx) (((size_t) idx) * MALLOC_ALIGNMENT + MINSIZE - SIZE_SZ)
@@ -3124,8 +3128,8 @@ typedef struct tcache_entry
time), this is for performance reasons. */
typedef struct tcache_perthread_struct
{
- uint16_t counts[TCACHE_MAX_BINS];
- tcache_entry *entries[TCACHE_MAX_BINS];
+ uint16_t counts[TCACHE_MAX_BINS + TCACHE_LARGE_BINS];
+ tcache_entry *entries[TCACHE_MAX_BINS + TCACHE_LARGE_BINS];
} tcache_perthread_struct;
static __thread bool tcache_shutting_down = false;
@@ -3158,10 +3162,19 @@ tcache_key_initialize (void)
}
}
+static __always_inline size_t
+large_csize2tidx(size_t nb)
+{
+ size_t idx = TCACHE_MAX_BINS
+ + __builtin_clz (tidx2usize (TCACHE_MAX_BINS-1))
+ - __builtin_clz (nb);
+ return idx;
+}
+
/* Caller must ensure that we know tc_idx is valid and there's room
for more chunks. */
static __always_inline void
-tcache_put (mchunkptr chunk, size_t tc_idx)
+tcache_put_n (mchunkptr chunk, size_t tc_idx, tcache_entry **ep, bool mangled)
{
tcache_entry *e = (tcache_entry *) chunk2mem (chunk);
@@ -3169,8 +3182,16 @@ tcache_put (mchunkptr chunk, size_t tc_idx)
detect a double free. */
e->key = tcache_key;
- e->next = PROTECT_PTR (&e->next, tcache->entries[tc_idx]);
- tcache->entries[tc_idx] = e;
+ if (mangled == false)
+ {
+ e->next = PROTECT_PTR (&e->next, *ep);
+ *ep = e;
+ }
+ else
+ {
+ e->next = PROTECT_PTR (&e->next, REVEAL_PTR (*ep));
+ *ep = PROTECT_PTR (ep, e);
+ }
++(tcache->counts[tc_idx]);
}
@@ -3178,10 +3199,10 @@ tcache_put (mchunkptr chunk, size_t tc_idx)
available chunks to remove. Removes chunk from the middle of the
list. */
static __always_inline void *
-tcache_get_n (size_t tc_idx, tcache_entry **ep)
+tcache_get_n (size_t tc_idx, tcache_entry **ep, bool mangled)
{
tcache_entry *e;
- if (ep == &(tcache->entries[tc_idx]))
+ if (mangled == false)
e = *ep;
else
e = REVEAL_PTR (*ep);
@@ -3189,40 +3210,121 @@ tcache_get_n (size_t tc_idx, tcache_entry **ep)
if (__glibc_unlikely (!aligned_OK (e)))
malloc_printerr ("malloc(): unaligned tcache chunk detected");
- if (ep == &(tcache->entries[tc_idx]))
- *ep = REVEAL_PTR (e->next);
+ void *ne = e == NULL ? NULL : REVEAL_PTR (e->next);
+ if (mangled == false)
+ *ep = ne;
else
- *ep = PROTECT_PTR (ep, REVEAL_PTR (e->next));
+ *ep = PROTECT_PTR (ep, ne);
--(tcache->counts[tc_idx]);
e->key = 0;
return (void *) e;
}
+static __always_inline void
+tcache_put (mchunkptr chunk, size_t tc_idx)
+{
+ tcache_put_n (chunk, tc_idx, &tcache->entries[tc_idx], false);
+}
+
/* Like the above, but removes from the head of the list. */
static __always_inline void *
tcache_get (size_t tc_idx)
{
- return tcache_get_n (tc_idx, & tcache->entries[tc_idx]);
+ return tcache_get_n (tc_idx, & tcache->entries[tc_idx], false);
}
-/* Iterates through the tcache linked list. */
-static __always_inline tcache_entry *
-tcache_next (tcache_entry *e)
+static __always_inline tcache_entry **
+tcache_location_large (size_t nb, size_t tc_idx, bool *mangled)
{
- return (tcache_entry *) REVEAL_PTR (e->next);
+ tcache_entry **tep = &(tcache->entries[tc_idx]);
+ tcache_entry *te = *tep;
+ while (te != NULL
+ && __glibc_unlikely (chunksize (mem2chunk (te)) < nb))
+ {
+ tep = & (te->next);
+ te = REVEAL_PTR (te->next);
+ *mangled = true;
+ }
+
+ return tep;
}
-/* Check if tcache is available for alloc by corresponding tc_idx. */
-static __always_inline bool
-tcache_available (size_t tc_idx)
+static __always_inline void
+tcache_put_large (mchunkptr chunk, size_t tc_idx)
{
- if (tc_idx < mp_.tcache_bins
- && tcache != NULL
- && tcache->counts[tc_idx] > 0)
- return true;
+ tcache_entry **entry;
+ bool mangled = false;
+ entry = tcache_location_large (chunksize(chunk), tc_idx, &mangled);
+
+ return tcache_put_n (chunk, tc_idx, entry, mangled);
+}
+
+static __always_inline void *
+tcache_get_large (size_t tc_idx, size_t nb)
+{
+ tcache_entry **entry;
+ bool mangled = false;
+ entry = tcache_location_large (nb, tc_idx, &mangled);
+
+ if ((mangled == true && REVEAL_PTR (*entry) == NULL)
+ || (mangled == false && *entry == NULL))
+ return NULL;
+
+ return tcache_get_n (tc_idx, entry, mangled);
+}
+
+#define NO_TCACHE_BIN ((size_t) -1)
+static __always_inline size_t
+tcache_index (size_t bytes)
+{
+ size_t tc_idx = csize2tidx (bytes);
+
+ if (__glibc_unlikely (tcache == NULL))
+ return NO_TCACHE_BIN;
+
+ if (__glibc_likely (tc_idx < TCACHE_MAX_BINS
+ && tc_idx < mp_.tcache_bins))
+ return tc_idx;
else
- return false;
+ {
+ tc_idx = large_csize2tidx (bytes);
+ if (tc_idx < mp_.tcache_bins)
+ return tc_idx;
+ }
+ return NO_TCACHE_BIN;
+}
+
+static __always_inline void *
+tcache_get_align (size_t nb, size_t alignment)
+{
+ size_t tc_idx = tcache_index (nb);
+
+ if (tc_idx != NO_TCACHE_BIN && tc_idx < TCACHE_MAX_BINS + TCACHE_LARGE_BINS
+ && tcache->counts[tc_idx] > 0)
+ {
+ /* The tcache itself isn't encoded, but the chain is. */
+ tcache_entry **tep = & tcache->entries[tc_idx];
+ tcache_entry *te = *tep;
+ bool mangled = false;
+ size_t csize;
+
+ while (te != NULL
+ && ((csize = chunksize (mem2chunk (te))) < nb
+ || (csize == nb
+ && !PTR_IS_ALIGNED (te, alignment))))
+ {
+ tep = & (te->next);
+ te = REVEAL_PTR (te->next);
+ mangled = true;
+ }
+
+ if (te != NULL
+ && csize == nb
+ && PTR_IS_ALIGNED (te, alignment))
+ return tag_new_usable (tcache_get_n (tc_idx, tep, mangled));
+ }
+ return NULL;
}
/* Verify if the suspicious tcache_entry is double free.
@@ -3231,7 +3333,7 @@ static __attribute__ ((noinline)) void
tcache_double_free_verify (tcache_entry *e)
{
tcache_entry *tmp;
- for (size_t tc_idx = 0; tc_idx < TCACHE_MAX_BINS; ++tc_idx)
+ for (size_t tc_idx = 0; tc_idx < TCACHE_MAX_BINS + TCACHE_LARGE_BINS; ++tc_idx)
{
size_t cnt = 0;
LIBC_PROBE (memory_tcache_double_free, 2, e, tc_idx);
@@ -3270,7 +3372,7 @@ tcache_thread_shutdown (void)
/* Free all of the entries and the tcache itself back to the arena
heap for coalescing. */
- for (i = 0; i < TCACHE_MAX_BINS; ++i)
+ for (i = 0; i < TCACHE_MAX_BINS + TCACHE_LARGE_BINS; ++i)
{
while (tcache_tmp->entries[i])
{
@@ -3392,10 +3494,21 @@ void *
__libc_malloc (size_t bytes)
{
#if USE_TCACHE
- size_t tc_idx = usize2tidx (bytes);
+ size_t nb = checked_request2size (bytes);
+ size_t tc_idx = tcache_index (nb);
- if (tcache_available (tc_idx))
- return tag_new_usable (tcache_get (tc_idx));
+ if (tc_idx != NO_TCACHE_BIN
+ && tcache->counts[tc_idx] > 0)
+ {
+ if (tc_idx < TCACHE_MAX_BINS)
+ return tag_new_usable (tcache_get (tc_idx));
+ else
+ {
+ void *victim = tcache_get_large (tc_idx, nb);
+ if (victim != NULL)
+ return tag_new_usable (victim);
+ }
+ }
#endif
return __libc_malloc2 (bytes);
@@ -3430,7 +3543,7 @@ __libc_free (void *mem)
#if USE_TCACHE
size_t tc_idx = csize2tidx (size);
- if (__glibc_likely (tcache != NULL && tc_idx < mp_.tcache_bins))
+ if (tcache != NULL)
{
/* Check to see if it's already in the tcache. */
tcache_entry *e = (tcache_entry *) chunk2mem (p);
@@ -3439,8 +3552,18 @@ __libc_free (void *mem)
if (__glibc_unlikely (e->key == tcache_key))
return tcache_double_free_verify (e);
- if (__glibc_likely (tcache->counts[tc_idx] < mp_.tcache_count))
- return tcache_put (p, tc_idx);
+ if (__glibc_likely (tc_idx < TCACHE_MAX_BINS))
+ {
+ if (__glibc_likely (tcache->counts[tc_idx] < mp_.tcache_count))
+ return tcache_put (p, tc_idx);
+ }
+ else
+ {
+ size_t tc_idx = tcache_index (size);
+ if (tc_idx != NO_TCACHE_BIN
+ && __glibc_likely (tcache->counts[tc_idx] < mp_.tcache_count))
+ return tcache_put_large (p, tc_idx);
+ }
}
#endif
@@ -3643,27 +3766,10 @@ _mid_memalign (size_t alignment, size_t bytes, void *address)
}
#if USE_TCACHE
- {
- size_t tc_idx = usize2tidx (bytes);
-
- if (tcache_available (tc_idx))
- {
- /* The tcache itself isn't encoded, but the chain is. */
- tcache_entry **tep = & tcache->entries[tc_idx];
- tcache_entry *te = *tep;
- while (te != NULL && !PTR_IS_ALIGNED (te, alignment))
- {
- tep = & (te->next);
- te = tcache_next (te);
- }
- if (te != NULL)
- {
- void *victim = tcache_get_n (tc_idx, tep);
- return tag_new_usable (victim);
- }
- }
- MAYBE_INIT_TCACHE ();
- }
+ void *victim = tcache_get_align (checked_request2size (bytes), alignment);
+ if (victim != NULL)
+ return tag_new_usable (victim);
+ MAYBE_INIT_TCACHE ();
#endif
if (SINGLE_THREAD_P)
@@ -5482,13 +5588,22 @@ do_set_arena_max (size_t value)
static __always_inline int
do_set_tcache_max (size_t value)
{
- if (value <= MAX_TCACHE_SIZE)
+ size_t csize = request2size (value);
+ LIBC_PROBE (memory_tunable_tcache_max_bytes, 2, value, mp_.tcache_max_bytes);
+
+ if (value < MAX_TCACHE_SIZE)
{
- LIBC_PROBE (memory_tunable_tcache_max_bytes, 2, value, mp_.tcache_max_bytes);
mp_.tcache_max_bytes = value;
- mp_.tcache_bins = csize2tidx (request2size(value)) + 1;
+ mp_.tcache_bins = csize2tidx (csize) + 1;
return 1;
}
+ else if (value < MAX_TCACHE_LARGE_SIZE)
+ {
+ mp_.tcache_max_bytes = value;
+ mp_.tcache_bins = large_csize2tidx (csize) + 1;
+ return 1;
+ }
+
return 0;
}
--
2.39.5
More information about the Libc-alpha
mailing list