[PATCH 0/9] malloc: Remove fastbins
Dev Jain
dev.jain@arm.com
Sun Nov 9 04:26:03 GMT 2025
On 07/11/25 3:37 pm, Florian Weimer wrote:
> * Dev Jain:
>
>> On 17/10/25 2:36 pm, Dev Jain wrote:
>>> The small tcache data structure is similar to the fastbin layer - we have
>>> size classes in which we store same size chunks. After the tcache was
>>> introduced in malloc, the tcache precedes the fastbin when we try to
>>> find a victim to allocate. Similarly, the tcache precedes the fastbin
>>> when we free a chunk, in that we first try to push the chunk into the
>>> tcache and only on failure do we try the fastbins. It is, therefore,
>>> easy to observe that post the introduction of the tcache, the fastbin
>>> layer has become redundant because it serves exactly the same functionality
>>> as the tcache, with the extra overhead of arena locks. Therefore, it makes
>>> sense to completely remove this allocation layer.
>>>
>>> We leave do_set_mxfast for back-compat, and just unconditionally return 1.
>>>
>>> Upon just disabling fastbins, we get a very minor regression (~0.5%).
>>> Upon setting the default TCACHE_FILL_COUNT to 16, we get almost the
>>> same performance. Thus, experimental data also proves that removing
>>> the fastbin layer is a good move. We have the additional benefit of also
>>> making the code less complex.
>>>
>>> I have broken down this removal into patches to make life easier
>>> (for me and the reviewers :) )
>>>
>>> Tested on Aarch64. All patches build sequentially. All malloc tests pass
>>> on each patch.
>>>
>> Hello! Are there some outstanding concerns about the patchset? Please let
>> me know so that I can address them!
> The series does not apply for me.
I should have mentioned the commit it applies on, it's 850d93f514eb.
>
> Paulo had some concerns about the queuing behavior in __libc_free on a
> full tcache. Then we realized that we currently do not batch frees,
> which is quite straightforward to implement. Batching also addresses
> Paulo's concerns about FIFO violations. The second patch below
What do you mean by FIFO violations, could you elaborate?
> implements a hysteresis effect for malloc, too, so that malloc + free
> does not immediately flush the tcache. Average utilization of the
> tcache should be lower after these changes, hopefully with better
> performance.
>
> Dev Jain, could you rerun your performance experiments with these two
> extra patches?
Thanks for the patches! My long term goal was to increase the tcache count
even more, and implement a tcache flushing algorithm. We could either have
a timer upon the expiration of which we could flush it, or if the tcache
grows beyond a particular size, we could flush it, and we can put this
code in the malloc() path. But what you have implemented seems pretty
nice and low overhead. I'll check with these patches...
>
> Thanks,
> Florian
>
> commit 1482b504f47ee70a9d3d39e42df1926bfbbd2788
> Author: Florian Weimer <fweimer@redhat.com>
> Date: Fri Nov 7 10:14:43 2025 +0100
>
> malloc: Perform batched frees if tcache is full
>
> Pass the tcache to __libc_free_batch so that it is not necessary
> to reload the tcache pointer after the _int_free_chunk calls.
>
> diff --git a/malloc/malloc.c b/malloc/malloc.c
> index 3273aa476b..0e543a04cb 100644
> --- a/malloc/malloc.c
> +++ b/malloc/malloc.c
> @@ -3040,7 +3040,8 @@ tcache_put_n (mchunkptr chunk, size_t tc_idx, tcache_entry **ep, bool mangled)
> 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, bool mangled)
> +tcache_get_n (tcache_perthread_struct *tc, size_t tc_idx, tcache_entry **ep,
> + bool mangled)
> {
> tcache_entry *e;
> if (!mangled)
> @@ -3056,7 +3057,7 @@ tcache_get_n (size_t tc_idx, tcache_entry **ep, bool mangled)
> else
> *ep = PROTECT_PTR (ep, REVEAL_PTR (e->next));
>
> - ++(tcache->num_slots[tc_idx]);
> + ++(tc->num_slots[tc_idx]);
> e->key = 0;
> return (void *) e;
> }
> @@ -3071,7 +3072,7 @@ tcache_put (mchunkptr chunk, size_t tc_idx)
> static __always_inline void *
> tcache_get (size_t tc_idx)
> {
> - return tcache_get_n (tc_idx, &tcache->entries[tc_idx], false);
> + return tcache_get_n (tcache, tc_idx, &tcache->entries[tc_idx], false);
> }
>
> static __always_inline tcache_entry **
> @@ -3114,7 +3115,7 @@ tcache_get_large (size_t tc_idx, size_t nb)
> if (te == NULL || nb != chunksize (mem2chunk (te)))
> return NULL;
>
> - return tcache_get_n (tc_idx, entry, mangled);
> + return tcache_get_n (tcache, tc_idx, entry, mangled);
> }
>
> static void tcache_init (mstate av);
> @@ -3152,7 +3153,7 @@ tcache_get_align (size_t nb, size_t alignment)
> if (te != NULL
> && csize == nb
> && PTR_IS_ALIGNED (te, alignment))
> - return tag_new_usable (tcache_get_n (tc_idx, tep, mangled));
> + return tag_new_usable (tcache_get_n (tcache, tc_idx, tep, mangled));
> DIAG_POP_NEEDS_COMMENT;
> }
> return NULL;
> @@ -3331,6 +3332,49 @@ tcache_free_init (void *mem)
> __libc_free (mem);
> }
>
> +/* Deallocate half of the tcache entries into arenas, to amortize the
> + locking overhead. */
> +static __attribute_noinline__ void
> +__libc_free_batched (mchunkptr p, INTERNAL_SIZE_T size,
> + tcache_perthread_struct *tc, size_t tc_idx)
> +{
> + /* Check size >= MINSIZE and p + size does not overflow. */
> + if (__glibc_unlikely (INT_ADD_OVERFLOW ((uintptr_t) p,
> + size - MINSIZE)))
> + return malloc_printerr_tail ("free(): invalid size (batch)");
> +
> + /* Empty half of the tcache, for a hysteresis effect. */
> + unsigned int to_free = mp_.tcache_count / 2;
> +
> + /* If the arena does not change between chunks, keep the lock. */
> + mstate av = arena_for_chunk (p);
> + __libc_lock_lock (av->mutex);
> + _int_free_chunk (av, p, size, true);
> +
> + while (tc->entries[tc_idx] != NULL && to_free > 0)
> + {
> + void *mem = tcache_get_n (tc, tc_idx, &tc->entries[tc_idx], false);
> + p = mem2chunk (mem);
> + size = chunksize (p);
> +
> + /* Lock a different arena if necessary. */
> + {
> + mstate chunk_av = arena_for_chunk (p);
> + if (chunk_av != av)
> + {
> + __libc_lock_unlock (av->mutex);
> + av = chunk_av;
> + __libc_lock_lock (av->mutex);
> + }
> + }
> +
> + _int_free_chunk (av, p, size, true);
> + to_free--;
> + }
> +
> + __libc_lock_unlock (av->mutex);
> +}
> +
> void
> __libc_free (void *mem)
> {
> @@ -3369,6 +3413,13 @@ __libc_free (void *mem)
> {
> if (__glibc_likely (tcache->num_slots[tc_idx] != 0))
> return tcache_put (p, tc_idx);
> + else
> + {
> + /* Perform batched freeing of tcache entries. */
> + if (__glibc_unlikely (tcache_inactive ()))
> + return tcache_free_init (mem);
> + return __libc_free_batched (p, size, tcache, tc_idx);
> + }
> }
> else
> {
> @@ -3376,10 +3427,9 @@ __libc_free (void *mem)
> if (size >= MINSIZE
> && __glibc_likely (tcache->num_slots[tc_idx] != 0))
> return tcache_put_large (p, tc_idx);
> + if (__glibc_unlikely (tcache_inactive ()))
> + return tcache_free_init (mem);
> }
> -
> - if (__glibc_unlikely (tcache_inactive ()))
> - return tcache_free_init (mem);
> }
> #endif
>
> commit 881bbbd6f73cacaa33eee780ef43ae1d57e68226
> Author: Florian Weimer <fweimer@redhat.com>
> Date: Fri Nov 7 10:27:20 2025 +0100
>
> malloc: Only fill half of the tcache during batch allocation
>
> This leaves room for subsequent frees.
>
> diff --git a/malloc/malloc.c b/malloc/malloc.c
> index 0e543a04cb..26f52dae3b 100644
> --- a/malloc/malloc.c
> +++ b/malloc/malloc.c
> @@ -3912,8 +3912,11 @@ _int_malloc (mstate av, size_t bytes)
> if (__glibc_unlikely (tcache_inactive ()))
> tcache_init (av);
>
> - /* While bin not empty and tcache not full, copy chunks over. */
> - while (tcache->num_slots[tc_idx] != 0
> + /* While bin not empty and tcache not full, copy chunks over.
> + Only fill half of the tcache, so that subsequent frees
> + do not immediately flush the tcache. */
> + unsigned int tcache_target_count = mp_.tcache_count / 2;
> + while (tcache->num_slots[tc_idx] > tcache_target_count
> && (tc_victim = last (bin)) != bin)
> {
> if (tc_victim != NULL)
> @@ -3960,6 +3963,7 @@ _int_malloc (mstate av, size_t bytes)
> if (tc_idx < mp_.tcache_small_bins)
> tcache_nb = nb;
> int return_cached = 0;
> + unsigned int tcache_target_count = mp_.tcache_count / 2;
>
> tcache_unsorted_count = 0;
> #endif
> @@ -4038,9 +4042,11 @@ _int_malloc (mstate av, size_t bytes)
> if (__glibc_unlikely (tcache_inactive ()))
> tcache_init (av);
> /* Fill cache first, return to user only if cache fills.
> - We may return one of these chunks later. */
> + We may return one of these chunks later. Only fill
> + half of tcache, so that subsequent frees do not flush
> + it immediately. */
> if (tcache_nb > 0
> - && tcache->num_slots[tc_idx] != 0)
> + && tcache->num_slots[tc_idx] > tcache_target_count)
> {
> tcache_put (victim, tc_idx);
> return_cached = 1;
> commit 881bbbd6f73cacaa33eee780ef43ae1d57e68226
> Author: Florian Weimer <fweimer@redhat.com>
> Date: Fri Nov 7 10:27:20 2025 +0100
>
> malloc: Only fill half of the tcache during batch allocation
>
> This leaves room for subsequent frees.
>
> diff --git a/malloc/malloc.c b/malloc/malloc.c
> index 0e543a04cb..26f52dae3b 100644
> --- a/malloc/malloc.c
> +++ b/malloc/malloc.c
> @@ -3912,8 +3912,11 @@ _int_malloc (mstate av, size_t bytes)
> if (__glibc_unlikely (tcache_inactive ()))
> tcache_init (av);
>
> - /* While bin not empty and tcache not full, copy chunks over. */
> - while (tcache->num_slots[tc_idx] != 0
> + /* While bin not empty and tcache not full, copy chunks over.
> + Only fill half of the tcache, so that subsequent frees
> + do not immediately flush the tcache. */
> + unsigned int tcache_target_count = mp_.tcache_count / 2;
> + while (tcache->num_slots[tc_idx] > tcache_target_count
> && (tc_victim = last (bin)) != bin)
> {
> if (tc_victim != NULL)
> @@ -3960,6 +3963,7 @@ _int_malloc (mstate av, size_t bytes)
> if (tc_idx < mp_.tcache_small_bins)
> tcache_nb = nb;
> int return_cached = 0;
> + unsigned int tcache_target_count = mp_.tcache_count / 2;
>
> tcache_unsorted_count = 0;
> #endif
> @@ -4038,9 +4042,11 @@ _int_malloc (mstate av, size_t bytes)
> if (__glibc_unlikely (tcache_inactive ()))
> tcache_init (av);
> /* Fill cache first, return to user only if cache fills.
> - We may return one of these chunks later. */
> + We may return one of these chunks later. Only fill
> + half of tcache, so that subsequent frees do not flush
> + it immediately. */
> if (tcache_nb > 0
> - && tcache->num_slots[tc_idx] != 0)
> + && tcache->num_slots[tc_idx] > tcache_target_count)
> {
> tcache_put (victim, tc_idx);
> return_cached = 1;
>
More information about the Libc-alpha
mailing list