[PATCH v4 4/7] malloc: add tcache support for large chunk caching
Cupertino Miranda
cupertino.miranda@oracle.com
Fri Mar 14 17:29:23 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 any chunk
size allocations. 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 | 105 +++++++++++++++++++++++++++++++++++-------------
1 file changed, 76 insertions(+), 29 deletions(-)
diff --git a/malloc/malloc.c b/malloc/malloc.c
index 9b2e04bfbf..305b2bc39a 100644
--- a/malloc/malloc.c
+++ b/malloc/malloc.c
@@ -291,14 +291,15 @@
#if USE_TCACHE
/* We want 64 entries. This is an arbitrary limit, which tunables can reduce. */
+# define TCACHE_UNBOUND_SIZE_BINS 10
# define TCACHE_MAX_BINS 64
# define MAX_TCACHE_SIZE tidx2usize (TCACHE_MAX_BINS-1)
+# define TCACHE_FIXED_SIZE_BINS \
+ (mp_.tcache_bins < TCACHE_MAX_BINS ? mp_.tcache_bins : TCACHE_MAX_BINS)
/* Only used to pre-fill the tunables. */
-# define tidx2usize(idx) (((size_t) idx) * MALLOC_ALIGNMENT + MINSIZE - SIZE_SZ)
+# define tidx2usize(idx) (((size_t) idx) * MALLOC_ALIGNMENT + MINSIZE - MALLOC_ALIGNMENT + 1)
-/* When "x" is from chunksize(). */
-# define csize2tidx(x) (((x) - MINSIZE + MALLOC_ALIGNMENT - 1) / MALLOC_ALIGNMENT)
/* When "x" is a user-provided size. */
# define usize2tidx(x) csize2tidx (request2size (x))
@@ -1926,8 +1927,8 @@ static struct malloc_par mp_ =
,
.tcache_count = TCACHE_FILL_COUNT,
.tcache_bins = TCACHE_MAX_BINS,
- .tcache_max_bytes = tidx2usize (TCACHE_MAX_BINS-1),
- .tcache_unsorted_limit = 0 /* No limit. */
+ .tcache_max_bytes = MAX_TCACHE_SIZE,
+ .tcache_unsorted_limit = 0, /* No limit. */
#endif
};
@@ -3119,8 +3120,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_UNBOUND_SIZE_BINS];
+ tcache_entry *entries[TCACHE_MAX_BINS + TCACHE_UNBOUND_SIZE_BINS];
} tcache_perthread_struct;
static __thread bool tcache_shutting_down = false;
@@ -3153,6 +3154,39 @@ tcache_key_initialize (void)
}
}
+static __always_inline size_t
+csize2tidx(size_t nb)
+{
+ size_t idx = ((nb - MINSIZE + MALLOC_ALIGNMENT - 1) / MALLOC_ALIGNMENT);
+ if (__glibc_unlikely (idx >= TCACHE_MAX_BINS)
+ && __glibc_unlikely (mp_.tcache_bins > TCACHE_MAX_BINS))
+ {
+ idx = TCACHE_MAX_BINS + __builtin_clz (tidx2usize (TCACHE_MAX_BINS-1)) - __builtin_clz (nb);
+ idx = idx < mp_.tcache_bins ? idx : mp_.tcache_bins - 1;
+ }
+ return idx;
+}
+
+static __always_inline tcache_entry *tcache_next (tcache_entry *);
+
+static __always_inline tcache_entry **
+tcache_location_for_size (size_t nb, size_t tc_idx)
+{
+ tcache_entry **tep = &(tcache->entries[tc_idx]);
+ tcache_entry *te = REVEAL_PTR (*tep);
+ if (__glibc_unlikely (tc_idx >= TCACHE_MAX_BINS))
+ {
+ while (te != NULL
+ && __glibc_unlikely (chunksize (mem2chunk (te)) < nb))
+ {
+ tep = & (te->next);
+ te = tcache_next (te);
+ }
+ }
+
+ return tep;
+}
+
/* Caller must ensure that we know tc_idx is valid and there's room
for more chunks. */
static __always_inline void
@@ -3164,8 +3198,9 @@ tcache_put (mchunkptr chunk, size_t tc_idx)
detect a double free. */
e->key = tcache_key;
- e->next = PROTECT_PTR (&e->next, REVEAL_PTR (tcache->entries[tc_idx]));
- tcache->entries[tc_idx] = PROTECT_PTR (&(tcache->entries[tc_idx]), e);
+ tcache_entry **entry = tcache_location_for_size (chunksize (chunk), tc_idx);
+ e->next = PROTECT_PTR (&e->next, REVEAL_PTR (*entry));
+ *entry = PROTECT_PTR (entry, e);
++(tcache->counts[tc_idx]);
}
@@ -3189,9 +3224,15 @@ tcache_get_n (size_t tc_idx, tcache_entry **ep)
/* Like the above, but removes from the head of the list. */
static __always_inline void *
-tcache_get (size_t tc_idx)
+tcache_get (size_t nb, size_t tc_idx)
{
- return tcache_get_n (tc_idx, & tcache->entries[tc_idx]);
+ tcache_entry **entry = tcache_location_for_size (nb, tc_idx);
+ tcache_entry *e = REVEAL_PTR (*entry);
+ if (tc_idx >= TCACHE_MAX_BINS
+ && (e == NULL || chunksize (mem2chunk (e)) != nb))
+ return NULL;
+
+ return tcache_get_n (tc_idx, entry);
}
/* Iterates through the tcache linked list. */
@@ -3280,7 +3321,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 < mp_.tcache_bins; ++i)
{
while (REVEAL_PTR (tcache_tmp->entries[i]))
{
@@ -3329,7 +3370,7 @@ tcache_init(void)
memset (tcache, 0, sizeof (tcache_perthread_struct));
}
- for (int i = 0; i < mp_.tcache_bins; i++)
+ for (int i = 0; i < TCACHE_MAX_BINS + TCACHE_UNBOUND_SIZE_BINS; i++)
tcache->entries[i] = PROTECT_PTR (&(tcache->entries[i]), NULL);
}
@@ -3356,7 +3397,7 @@ tcache_try_malloc (size_t bytes, void **memptr)
MAYBE_INIT_TCACHE ();
if (tcache_available (tc_idx))
- *memptr = tcache_get (tc_idx);
+ *memptr = tcache_get (tbytes, tc_idx);
else
*memptr = NULL;
@@ -3691,9 +3732,16 @@ _mid_memalign (size_t alignment, size_t bytes, void *address)
if (tcache_available (tc_idx))
{
- /* The tcache itself isn't encoded, but the chain is. */
- tcache_entry **tep = & tcache->entries[tc_idx];
+ tcache_entry **tep = tcache_location_for_size (tbytes, tc_idx);
tcache_entry *te = REVEAL_PTR (*tep);
+
+ /* Make sure returned chunk is of expected size. */
+ if (te == NULL
+ || (tc_idx >= TCACHE_MAX_BINS
+ && chunksize (mem2chunk (te)) != tbytes))
+ goto tcache_memalign_abort;
+
+ /* The tcache itself isn't encoded, but the chain is. */
while (te != NULL && !PTR_IS_ALIGNED (te, alignment))
{
tep = & (te->next);
@@ -3705,6 +3753,7 @@ _mid_memalign (size_t alignment, size_t bytes, void *address)
return tag_new_usable (victim);
}
}
+tcache_memalign_abort:
}
#endif
@@ -3992,7 +4041,7 @@ _int_malloc (mstate av, size_t bytes)
/* While we're here, if we see other chunks of the same size,
stash them in the tcache. */
size_t tc_idx = csize2tidx (nb);
- if (tcache != NULL && tc_idx < mp_.tcache_bins)
+ if (tcache != NULL && tc_idx < TCACHE_FIXED_SIZE_BINS)
{
mchunkptr tc_victim;
@@ -4050,7 +4099,7 @@ _int_malloc (mstate av, size_t bytes)
/* While we're here, if we see other chunks of the same size,
stash them in the tcache. */
size_t tc_idx = csize2tidx (nb);
- if (tcache != NULL && tc_idx < mp_.tcache_bins)
+ if (tcache != NULL && tc_idx < TCACHE_FIXED_SIZE_BINS)
{
mchunkptr tc_victim;
@@ -4112,7 +4161,7 @@ _int_malloc (mstate av, size_t bytes)
#if USE_TCACHE
INTERNAL_SIZE_T tcache_nb = 0;
size_t tc_idx = csize2tidx (nb);
- if (tcache != NULL && tc_idx < mp_.tcache_bins)
+ if (tcache != NULL && tc_idx < TCACHE_FIXED_SIZE_BINS)
tcache_nb = nb;
int return_cached = 0;
@@ -4287,7 +4336,7 @@ _int_malloc (mstate av, size_t bytes)
&& mp_.tcache_unsorted_limit > 0
&& tcache_unsorted_count > mp_.tcache_unsorted_limit)
{
- return tcache_get (tc_idx);
+ return tcache_get (nb, tc_idx);
}
#endif
@@ -4300,7 +4349,7 @@ _int_malloc (mstate av, size_t bytes)
/* If all the small chunks we found ended up cached, return one now. */
if (return_cached)
{
- return tcache_get (tc_idx);
+ return tcache_get (nb, tc_idx);
}
#endif
@@ -5546,14 +5595,12 @@ do_set_arena_max (size_t value)
static __always_inline int
do_set_tcache_max (size_t value)
{
- 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;
- return 1;
- }
- return 0;
+ LIBC_PROBE (memory_tunable_tcache_max_bytes, 2, value, mp_.tcache_max_bytes);
+ mp_.tcache_max_bytes = value;
+ mp_.tcache_bins = TCACHE_MAX_BINS + TCACHE_UNBOUND_SIZE_BINS;
+ mp_.tcache_bins = csize2tidx (request2size(value)) + 1;
+
+ return 1;
}
static __always_inline int
--
2.39.5
More information about the Libc-alpha
mailing list