[PATCH 1/2] malloc: add tcache support for large chunk caching
Adhemerval Zanella Netto
adhemerval.zanella@linaro.org
Tue Dec 3 18:38:35 GMT 2024
On 02/12/24 16:42, Cupertino Miranda wrote:
> 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.
This patch seems to trigger some real regression on aarch64/arm bots [1][2]:
FAIL: malloc/tst-malloc-thread-fail-malloc-hugetlb2
original exit status 1
error: exit status 11 from child process
FAIL: malloc/tst-malloc-thread-fail
original exit status 1
error: exit status 11 from child process
[1] https://ci.linaro.org/job/tcwg_glibc_check--master-aarch64-precommit/2808/artifact/artifacts/artifacts.precommit/notify/mail-body.txt
[2] https://ci.linaro.org/job/tcwg_glibc_check--master-aarch64-precommit/2808/artifact/artifacts/artifacts.precommit/00-sumfiles/tests.log.0.xz
> ---
> 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 287fa0904d..95d5607236 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);
> }
> }
> }
> @@ -5544,14 +5802,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 = MAX_TCACHE_SIZE;
> +
> + 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
More information about the Libc-alpha
mailing list