[PATCH v2 1/3] malloc: add tcache support for large chunk caching
Cupertino Miranda
cupertino.miranda@oracle.com
Fri Dec 6 14:09:19 GMT 2024
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 reversely ordered within the
bin. The last bin contains all other sizes of allocations.
The patch also includes trimming functionality that gives back to the
arena any older non used chunk, once the threshold limit for the tcache
size is reached.
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.
Also in order to define the capacity of the tcache, the tunable
glibc.mallc.tcache_max_large_capacity was defined, specifying the
refered threshold for removing older non-used cached chunks.
---
elf/dl-tunables.list | 3 +
malloc/arena.c | 2 +
malloc/malloc.c | 383 ++++++++++++++++++++++++++++++++++++-------
3 files changed, 330 insertions(+), 58 deletions(-)
diff --git a/elf/dl-tunables.list b/elf/dl-tunables.list
index 40ac5b3776..e28d4877fd 100644
--- a/elf/dl-tunables.list
+++ b/elf/dl-tunables.list
@@ -74,6 +74,9 @@ glibc {
tcache_unsorted_limit {
type: SIZE_T
}
+ tcache_max_large_capacity {
+ type: SIZE_T
+ }
mxfast {
type: SIZE_T
minval: 0
diff --git a/malloc/arena.c b/malloc/arena.c
index 91a43ee394..cd88071a08 100644
--- a/malloc/arena.c
+++ b/malloc/arena.c
@@ -250,6 +250,7 @@ TUNABLE_CALLBACK_FNDECL (set_arena_test, size_t)
TUNABLE_CALLBACK_FNDECL (set_tcache_max, size_t)
TUNABLE_CALLBACK_FNDECL (set_tcache_count, size_t)
TUNABLE_CALLBACK_FNDECL (set_tcache_unsorted_limit, size_t)
+TUNABLE_CALLBACK_FNDECL (set_tcache_max_large_capacity, size_t)
#endif
TUNABLE_CALLBACK_FNDECL (set_mxfast, size_t)
TUNABLE_CALLBACK_FNDECL (set_hugetlb, size_t)
@@ -309,6 +310,7 @@ ptmalloc_init (void)
TUNABLE_GET (tcache_count, size_t, TUNABLE_CALLBACK (set_tcache_count));
TUNABLE_GET (tcache_unsorted_limit, size_t,
TUNABLE_CALLBACK (set_tcache_unsorted_limit));
+ TUNABLE_GET (tcache_max_large_capacity, size_t, TUNABLE_CALLBACK (set_tcache_max_large_capacity));
# endif
TUNABLE_GET (mxfast, size_t, TUNABLE_CALLBACK (set_mxfast));
TUNABLE_GET (hugetlb, size_t, TUNABLE_CALLBACK (set_hugetlb));
diff --git a/malloc/malloc.c b/malloc/malloc.c
index ac3901bdd5..642cdffd23 100644
--- a/malloc/malloc.c
+++ b/malloc/malloc.c
@@ -291,14 +291,18 @@
#if USE_TCACHE
/* We want 64 entries. This is an arbitrary limit, which tunables can reduce. */
+
+/* Last large bin is for alocations beyond 1kB. */
+# define TCACHE_LARGE_BINS 10
# define TCACHE_MAX_BINS 64
-# define MAX_TCACHE_SIZE tidx2usize (TCACHE_MAX_BINS-1)
+# define MAX_TCACHE_SIZE (tidx2usize (TCACHE_MAX_BINS-1))
/* Only used to pre-fill the tunables. */
# define tidx2usize(idx) (((size_t) idx) * MALLOC_ALIGNMENT + MINSIZE - SIZE_SZ)
/* 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))
@@ -1891,6 +1895,8 @@ struct malloc_par
/* Maximum number of buckets to use. */
size_t tcache_bins;
size_t tcache_max_bytes;
+ /* Maximum tcache capacity for unbound size bins. */
+ size_t tcache_max_large_capacity;
/* Maximum number of chunks in each bucket. */
size_t tcache_count;
/* Maximum number of chunks to remove from the unsorted list, which
@@ -1926,8 +1932,9 @@ 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. */
+ .tcache_max_large_capacity = TCACHE_FILL_COUNT * MAX_TCACHE_SIZE /* Not enabled by default. */
#endif
};
@@ -3110,6 +3117,11 @@ typedef struct tcache_entry
struct tcache_entry *next;
/* This field exists to detect double frees. */
uintptr_t key;
+
+ /* Entries to allow large data to remove chunks as they exceed max data size.
+ */
+ struct tcache_entry *rm_prev;
+ struct tcache_entry *rm_next;
} tcache_entry;
/* There is one of these for each thread, which contains the
@@ -3121,6 +3133,12 @@ typedef struct tcache_perthread_struct
{
uint16_t counts[TCACHE_MAX_BINS];
tcache_entry *entries[TCACHE_MAX_BINS];
+ tcache_entry *large_entries[TCACHE_LARGE_BINS];
+ size_t large_data_size;
+ /* Used to remove older entries from tcache when size limit is reached. */
+ tcache_entry *large_remove_list;
+ tcache_entry *last_in_large_remove_list;
+ bool in_remove_cycle;
} tcache_perthread_struct;
static __thread bool tcache_shutting_down = false;
@@ -3208,6 +3226,153 @@ tcache_next (tcache_entry *e)
return (tcache_entry *) REVEAL_PTR (e->next);
}
+/* Compute large bin index for chunk size. */
+static __always_inline char
+large_csize2tidx (size_t x)
+{
+ char idx = __builtin_clz (tidx2usize (mp_.tcache_bins-1)) - __builtin_clz (x);
+ return idx < TCACHE_LARGE_BINS ? idx : TCACHE_LARGE_BINS-1;
+}
+
+/* TODO: Do the mangling of all linked-list pointers.
+ * All linked list pointers were left non-mangled for review/debugging. */
+
+static __always_inline void
+tcache_trim_add_entry (tcache_entry *e)
+{
+ /* Add entry to tail of remove list. */
+ if(__glibc_unlikely (tcache->large_remove_list == NULL))
+ {
+ tcache->large_remove_list = e;
+ tcache->last_in_large_remove_list = e;
+ }
+ else
+ {
+ e->rm_prev = tcache->last_in_large_remove_list;
+ tcache->last_in_large_remove_list->rm_next = e;
+ tcache->last_in_large_remove_list = e;
+ }
+
+ tcache->large_data_size += chunksize(mem2chunk(e));
+}
+
+static __always_inline void
+tcache_trim_remove_entry (tcache_perthread_struct *tc,
+ tcache_entry *e, bool remove_from_sized_lists)
+{
+ /* Remove from regular uni-directional sized lists. */
+ if (remove_from_sized_lists == true)
+ {
+ size_t tc_idx = large_csize2tidx (chunksize (mem2chunk (e)));
+ tcache_entry **entry = &tc->large_entries[tc_idx];
+ while(*entry != NULL && *entry != e)
+ entry = &(*entry)->next;
+
+ *entry = (*entry)->next;
+ }
+
+ /* Change the last entry in remove list if entry to be removed is the
+ * last. */
+ if (e == tc->last_in_large_remove_list)
+ tc->last_in_large_remove_list = e->rm_prev;
+
+ /* Change remotion list entry if the node to remove is the head of the list.
+ */
+ if (e == tc->large_remove_list)
+ tc->large_remove_list = e->rm_next;
+
+ /* Remove chunk from remotion list */
+ if (e->rm_prev != NULL)
+ e->rm_prev->rm_next = e->rm_next;
+ if (e->rm_next != NULL)
+ e->rm_next->rm_prev = e->rm_prev;
+
+ tc->large_data_size -= chunksize(mem2chunk(e));
+}
+
+static __always_inline void *
+tcache_large_get (size_t nb, size_t alignment)
+{
+ size_t tc_idx = large_csize2tidx (nb);
+ tcache_entry **entry = &tcache->large_entries[tc_idx];
+
+ /* Skip all chunks that are too large. */
+ while(*entry != NULL
+ && chunksize (mem2chunk (*entry)) > nb)
+ entry = &(*entry)->next;
+
+ /* Find an entry that respects alignment. */
+ if (alignment != 0)
+ {
+ while (*entry != NULL
+ && chunksize (mem2chunk (*entry)) == nb
+ && !PTR_IS_ALIGNED (*entry, alignment))
+ entry = &(*entry)->next;
+ }
+
+
+ /* Make sure we have an compatible chunk. */
+ if (*entry == NULL
+ || chunksize (mem2chunk (*entry)) != nb)
+ return NULL;
+
+ tcache_entry *e = *entry;
+
+ e->key = 0;
+ tcache_trim_remove_entry (tcache, e, false);
+
+ /* Remove chunk from list */
+ *entry = (*entry)->next;
+ return (void *) e;
+}
+
+static __always_inline void
+tcache_trim (size_t extra_space)
+{
+ tcache->in_remove_cycle = true;
+ if (tcache != NULL
+ && tcache->large_remove_list != NULL)
+ while (tcache->large_remove_list != NULL
+ && tcache->large_data_size + extra_space > mp_.tcache_max_large_capacity)
+ {
+ tcache_entry *e = tcache->large_remove_list;
+ tcache_trim_remove_entry (tcache, e, true);
+ if (e == NULL)
+ malloc_printerr ("tcache_trim: Failed to removed entry from cache");
+ else
+ __libc_free (e);
+ }
+ tcache->in_remove_cycle = false;
+}
+
+static __always_inline bool
+tcache_large_put (mchunkptr chunk, size_t tc_idx)
+{
+ if (tcache == NULL)
+ return false;
+
+ tcache_trim(chunksize (chunk));
+
+ tcache_entry *e = (tcache_entry *) chunk2mem (chunk);
+
+ /* Mark this chunk as "in the tcache" so the test in _int_free will
+ detect a double free. */
+ memset (e, 0, sizeof(tcache_entry));
+ e->key = tcache_key;
+
+ /* If it is a large data chunk then add it in the list ordered from
+ * bigger to smaller chunk size */
+ tcache_entry **entry = &tcache->large_entries[tc_idx];
+ while(*entry != NULL && chunksize(mem2chunk(*entry)) > chunksize(chunk))
+ entry = &(*entry)->next;
+
+ e->next = *entry;
+ *entry = e;
+
+ tcache_trim_add_entry (e);
+ return true;
+}
+
/* Verify if the suspicious tcache_entry is double free.
It's not expected to execute very often, mark it as noinline. */
static __attribute__ ((noinline)) void
@@ -3216,18 +3381,46 @@ tcache_double_free_verify (tcache_entry *e, size_t tc_idx)
tcache_entry *tmp;
size_t cnt = 0;
LIBC_PROBE (memory_tcache_double_free, 2, e, tc_idx);
- for (tmp = tcache->entries[tc_idx];
- tmp;
- tmp = REVEAL_PTR (tmp->next), ++cnt)
+ if(tc_idx < mp_.tcache_bins)
+ {
+ for (tmp = tcache->entries[tc_idx];
+ tmp;
+ tmp = REVEAL_PTR (tmp->next), ++cnt)
+ {
+ if (cnt >= mp_.tcache_count)
+ malloc_printerr ("free(): too many chunks detected in tcache");
+ if (__glibc_unlikely (!aligned_OK (tmp)))
+ malloc_printerr ("free(): unaligned chunk detected in tcache 2");
+ if (tmp == e)
+ malloc_printerr ("free(): double free detected in tcache 2");
+ /* If we get here, it was a coincidence. We've wasted a
+ few cycles, but don't abort. */
+ }
+ }
+ else
{
- if (cnt >= mp_.tcache_count)
- malloc_printerr ("free(): too many chunks detected in tcache");
- if (__glibc_unlikely (!aligned_OK (tmp)))
- malloc_printerr ("free(): unaligned chunk detected in tcache 2");
- if (tmp == e)
- malloc_printerr ("free(): double free detected in tcache 2");
- /* If we get here, it was a coincidence. We've wasted a
- few cycles, but don't abort. */
+ size_t large_tcache_size = 0;
+ for (int idx = 0; idx < TCACHE_LARGE_BINS; idx++)
+ {
+ tcache_entry **entry = &tcache->large_entries[idx];
+ while (*entry != NULL)
+ {
+ size_t entry_size = chunksize (mem2chunk (*entry));
+ size_t entry_tc_idx = large_csize2tidx (entry_size);
+ large_tcache_size += entry_size;
+
+ if (__glibc_unlikely (entry_tc_idx != idx))
+ malloc_printerr ("free(): large cache entry in incorrect bin");
+ if (__glibc_unlikely (!aligned_OK (*entry)))
+ malloc_printerr ("free(): unaligned chunk detected in tcache 2");
+ if (*entry == e)
+ malloc_printerr ("free(): double free detected in tcache 3");
+
+ entry = &((*entry)->next);
+ }
+ }
+ if (tcache->large_data_size != large_tcache_size)
+ malloc_printerr ("free(): large tcache size is not correct");
}
}
@@ -3238,22 +3431,35 @@ tcache_free (mchunkptr p, INTERNAL_SIZE_T size)
{
bool done = false;
size_t tc_idx = csize2tidx (size);
- if (tcache != NULL && tc_idx < mp_.tcache_bins)
+
+ if (__glibc_unlikely (tcache_shutting_down == false)
+ && __glibc_unlikely (tcache->in_remove_cycle == false)
+ && tcache != NULL
+ && size <= mp_.tcache_max_bytes)
{
/* Check to see if it's already in the tcache. */
tcache_entry *e = (tcache_entry *) chunk2mem (p);
/* This test succeeds on double free. However, we don't 100%
- trust it (it also matches random payload data at a 1 in
- 2^<size_t> chance), so verify it's not an unlikely
- coincidence before aborting. */
+ trust it (it also matches random payload data at a 1 in
+ 2^<size_t> chance), so verify it's not an unlikely
+ coincidence before aborting. */
if (__glibc_unlikely (e->key == tcache_key))
- tcache_double_free_verify (e, tc_idx);
+ tcache_double_free_verify (e, tc_idx);
- if (tcache->counts[tc_idx] < mp_.tcache_count)
+ if (tcache != NULL && tc_idx < mp_.tcache_bins)
+ {
+ if (tcache->counts[tc_idx] < mp_.tcache_count)
+ {
+ tcache_put (p, tc_idx);
+ done = true;
+ }
+ }
+ else
{
- tcache_put (p, tc_idx);
- done = true;
+ size_t ltc_idx = large_csize2tidx (size);
+ if (tcache_large_put (p, ltc_idx) == true)
+ done = true;
}
}
return done;
@@ -3264,6 +3470,7 @@ tcache_thread_shutdown (void)
{
int i;
tcache_perthread_struct *tcache_tmp = tcache;
+ size_t large_tcache_size = 0;
tcache_shutting_down = true;
@@ -3275,7 +3482,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 (tcache_tmp->entries[i])
{
@@ -3288,6 +3495,32 @@ tcache_thread_shutdown (void)
}
}
+ size_t initial_tcache_large_size = tcache_tmp->large_data_size;
+ /* Free all of the large entries back to arena heap. */
+ for (int idx = 0; idx < TCACHE_LARGE_BINS; idx++)
+ {
+ while (tcache_tmp->large_entries[idx])
+ {
+ tcache_entry *e = tcache_tmp->large_entries[idx];
+ size_t entry_size = chunksize (mem2chunk (e));
+ size_t entry_tc_idx = large_csize2tidx (entry_size);
+ large_tcache_size += entry_size;
+
+ if (__glibc_unlikely (entry_tc_idx != idx))
+ malloc_printerr ("tcache_thread_shutdown(): large cache entry in incorrect bin");
+ if (__glibc_unlikely (!aligned_OK (e)))
+ malloc_printerr ("tcache_thread_shutdown(): unaligned chunk detected in tcache");
+
+ e->key = 0;
+ tcache_trim_remove_entry (tcache_tmp, e, true);
+
+ __libc_free (e);
+ }
+ }
+ if (tcache_tmp->large_data_size != 0
+ || initial_tcache_large_size != large_tcache_size)
+ malloc_printerr ("tcache_thread_shutdown(): large tcache was incorrect");
+
__libc_free (tcache_tmp);
}
@@ -3356,22 +3589,34 @@ __libc_malloc (size_t bytes)
#if USE_TCACHE
/* int_free also calls request2size, be careful to not pad twice. */
size_t tbytes = checked_request2size (bytes);
- if (tbytes == 0)
+
+ if (tbytes <= mp_.tcache_max_bytes)
{
- __set_errno (ENOMEM);
- return NULL;
- }
- size_t tc_idx = csize2tidx (tbytes);
+ if (tbytes == 0)
+ {
+ __set_errno (ENOMEM);
+ return NULL;
+ }
+ size_t tc_idx = csize2tidx (tbytes);
- MAYBE_INIT_TCACHE ();
+ MAYBE_INIT_TCACHE ();
- DIAG_PUSH_NEEDS_COMMENT;
- if (tc_idx < mp_.tcache_bins
- && tcache != NULL
- && tcache->counts[tc_idx] > 0)
- {
- victim = tcache_get (tc_idx);
- return tag_new_usable (victim);
+ DIAG_PUSH_NEEDS_COMMENT;
+
+ if (tc_idx < mp_.tcache_bins)
+ {
+ if (tcache != NULL && tcache->counts[tc_idx] > 0)
+ {
+ victim = tcache_get (tc_idx);
+ return tag_new_usable (victim);
+ }
+ }
+ else
+ {
+ victim = tcache_large_get (tbytes, 0);
+ if (victim != NULL)
+ return tag_new_usable (victim);
+ }
}
DIAG_POP_NEEDS_COMMENT;
#endif
@@ -3657,32 +3902,45 @@ _mid_memalign (size_t alignment, size_t bytes, void *address)
}
#if USE_TCACHE
+ MAYBE_INIT_TCACHE ();
+
{
size_t tbytes;
tbytes = checked_request2size (bytes);
if (tbytes == 0)
{
- __set_errno (ENOMEM);
- return NULL;
+ __set_errno (ENOMEM);
+ return NULL;
}
size_t tc_idx = csize2tidx (tbytes);
- if (tc_idx < mp_.tcache_bins
- && tcache != NULL
- && tcache->counts[tc_idx] > 0)
+ if (tbytes <= mp_.tcache_max_bytes)
{
- /* 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))
+ if (tc_idx < mp_.tcache_bins)
{
- tep = & (te->next);
- te = tcache_next (te);
+ if (tcache != NULL
+ && 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;
+ 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);
+ }
+ }
}
- if (te != NULL)
+ else
{
- void *victim = tcache_get_n (tc_idx, tep);
- return tag_new_usable (victim);
+ void *victim = tcache_large_get (tbytes, alignment);
+ if (victim != NULL)
+ return tag_new_usable (victim);
}
}
}
@@ -5510,14 +5768,23 @@ 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;
+ if (csize2tidx (request2size(value)) + 1 < MAX_TCACHE_SIZE)
+ mp_.tcache_bins = csize2tidx (request2size(value)) + 1;
+ else
+ mp_.tcache_bins = TCACHE_MAX_BINS;
+
+ return 1;
+}
+
+static __always_inline int
+do_set_tcache_max_large_capacity (size_t value)
+{
+ LIBC_PROBE (memory_tunable_tcache_max_large_capacity, 2, value, mp_.tcache_max_large_capacity);
+ mp_.tcache_max_large_capacity = value;
+
+ return 1;
}
static __always_inline int
--
2.39.5
More information about the Libc-alpha
mailing list