[PATCH] malloc: Count tcache entries downwards

[DJ Delorie]

tl;dr: needs to be rebased to head, and ->counts renamed, but logic is
OK.  LGTM with those changes.

Reviewed-by: DJ Delorie <dj@redhat.com>

Wilco Dijkstra <Wilco.Dijkstra@arm.com> writes:
> Currently tcache requires 2 global variable accesses to determine
> whether a block can be added to the tcache.  Change the counts array
> to indicate the number of entries that could be added by counting
> downwards.  If the count reaches zero, no more blocks can be added.
> If the entries pointer is not NULL, at least one block is available
> for allocation.
>
> Now each tcache bin can support a different maximum number of blocks,
> and they can be individually switched on or off (a zero initialized
> count+entry means the tcache bin is not available for free or malloc).

FYI this patch no longer applies to master (malloc.c is busy!  yay!) but
I'll review the code as-is.  I'll also ignore the request to rename
tcache->counts to something that reflects its new purpose, as we could
bikeshed that forever.

> @@ -3169,7 +3169,7 @@ tcache_put (mchunkptr chunk, size_t tc_idx)
>  
>    e->next = PROTECT_PTR (&e->next, tcache->entries[tc_idx]);
>    tcache->entries[tc_idx] = e;
> -  ++(tcache->counts[tc_idx]);
> +  --(tcache->counts[tc_idx]);
>  }

tcache->counts is how many more chunks we can put on the list, so adding
something to the list (tcache_put) should reduce this number.  Ok.

> @@ -3192,7 +3192,7 @@ tcache_get_n (size_t tc_idx, tcache_entry **ep)
>    else
>      *ep = PROTECT_PTR (ep, REVEAL_PTR (e->next));
>  
> -  --(tcache->counts[tc_idx]);
> +  ++(tcache->counts[tc_idx]);
>    e->key = 0;
>    return (void *) e;

This is the opposite (tcache_get) so should increment, since we're
"freeing" a slot.  Ok.

> @@ -3217,7 +3217,7 @@ tcache_available (size_t tc_idx)
>  {
>    if (tc_idx < mp_.tcache_bins
>        && tcache != NULL
> -      && tcache->counts[tc_idx] > 0)
> +      && tcache->entries[tc_idx] != NULL)
>      return true;
>    else
>      return false;

In this version, we protect pointers that are inside the chunks
(e->next) but not pointers outside of chunks (tcache->entries).
So the check here goes from "at least one chunk" to "list is not
empty".  Ok.

> @@ -3265,7 +3265,7 @@ tcache_free (mchunkptr p, INTERNAL_SIZE_T size)
>        if (__glibc_unlikely (e->key == tcache_key))
>  	tcache_double_free_verify (e, tc_idx);
>  
> -      if (tcache->counts[tc_idx] < mp_.tcache_count)
> +      if (tcache->counts[tc_idx] != 0)
>  	{

This is testing for "can we put a chunk in tcache".  The new logic is
"has slots".  tcache->counts is a UINT16 so !=0 and >0 are semantically
the same here, so ok.

> @@ -3337,6 +3337,8 @@ tcache_init(void)
>      {
>        tcache = (tcache_perthread_struct *) victim;
>        memset (tcache, 0, sizeof (tcache_perthread_struct));
> +      for (int i = 0; i < TCACHE_MAX_BINS; i++)
> +	tcache->counts[i] = mp_.tcache_count;
>      }

This is the size of tcache->counts; we initialize each to the tunable
value so we start with "count slots free."  Tunables are set by
ptmalloc_init, which is called from libc_early_init.c, so they'll be set
by this point.  Ok.

> @@ -4006,8 +4008,7 @@ _int_malloc (mstate av, size_t bytes)
>  		  mchunkptr tc_victim;
>  
>  		  /* While bin not empty and tcache not full, copy chunks.  */
> -		  while (tcache->counts[tc_idx] < mp_.tcache_count
> -			 && (tc_victim = *fb) != NULL)
> +		  while (tcache->counts[tc_idx] != 0 && (tc_victim = *fb) != NULL)
>  		    {

Ok.

> @@ -4067,8 +4068,7 @@ _int_malloc (mstate av, size_t bytes)
>  	      mchunkptr tc_victim;
>  
>  	      /* While bin not empty and tcache not full, copy chunks over.  */
> -	      while (tcache->counts[tc_idx] < mp_.tcache_count
> -		     && (tc_victim = last (bin)) != bin)
> +	      while (tcache->counts[tc_idx] != 0 && (tc_victim = last (bin)) != bin)
>  		{

Ok.

> @@ -4204,8 +4204,7 @@ _int_malloc (mstate av, size_t bytes)
>  #if USE_TCACHE
>  	      /* Fill cache first, return to user only if cache fills.
>  		 We may return one of these chunks later.  */
> -	      if (tcache_nb > 0
> -		  && tcache->counts[tc_idx] < mp_.tcache_count)
> +	      if (tcache_nb > 0 && tcache->counts[tc_idx] != 0)
>  		{

Ok.