[PATCH v7 1/2] malloc: add tcache support for large chunk caching

[Wilco Dijkstra]

Hi Cupertino,

Thanks for the new version - this looks much more promising, including performance!
A few comments:

>  # define TCACHE_MAX_BINS                64
> +# define TCACHE_LARGE_BINS             12 /* Up to 4M chunks */
> +# define TCACHE_ALL_BINS       (TCACHE_MAX_BINS + TCACHE_LARGE_BINS)
>  # define MAX_TCACHE_SIZE        tidx2usize (TCACHE_MAX_BINS-1)
> +# define MAX_TCACHE_LARGE_SIZE \
> +           (1 << (31 - __builtin_clz (MAX_TCACHE_SIZE) + TCACHE_LARGE_BINS))

Note there is an issue with tabs here which causes merge conflicts.

It seems the macros are now confusingly named - how about:

TCACHE_MAX_BINS = TCACHE_SMALL_BINS + TCACHE_LARGE_BINS?

Plus TCACHE_SMALL_SIZE and TCACHE_LARGE_SIZE equivalents in bytes?

> -  uint16_t counts[TCACHE_MAX_BINS];
> -  tcache_entry *entries[TCACHE_MAX_BINS];
> +  uint16_t counts[TCACHE_MAX_BINS + TCACHE_LARGE_BINS];
> +  tcache_entry *entries[TCACHE_MAX_BINS + TCACHE_LARGE_BINS];
>  } tcache_perthread_struct;
 
Keeping TCACHE_MAX_BINS as the real maximum avoids having to update this
and in a few more places.

> +static __always_inline size_t
> +large_csize2tidx(size_t nb)
> +{
> +  size_t idx = TCACHE_MAX_BINS
> +              + __builtin_clz (tidx2usize (TCACHE_MAX_BINS-1))
> +              - __builtin_clz (nb);
> +  return idx;

Could use TCACHE_SMALL_SIZE rather than tidx2usize (TCACHE_MAX_BINS-1).

> +  tcache_entry **entry;
> +  bool mangled = false;
> +  entry = tcache_location_large (chunksize(chunk), tc_idx, &mangled);

Nit: add space before '('.

> +#define NO_TCACHE_BIN ((size_t) -1)
> +static __always_inline size_t
> +tcache_index (size_t bytes)
> +{
> +  size_t tc_idx = csize2tidx (bytes);
> +
> +  if (__glibc_unlikely (tcache == NULL))
> +    return NO_TCACHE_BIN;

I don't believe it makes sense to introduce NO_TCACHE_BIN and explicitly
check for it. We could just use TCACHE_MAX_BINS (new definition) rather
than adding a new define.

> +  if (__glibc_likely (tc_idx < TCACHE_MAX_BINS
> +                     && tc_idx < mp_.tcache_bins))
> +    return tc_idx;
>    else
> -    return false;
> +    {
> +      tc_idx = large_csize2tidx (bytes);
> +      if (tc_idx < mp_.tcache_bins)
> +       return  tc_idx;

Hmms, so if tc_idx >= mp_.tcache_bins but mp_.tcache_bins < TCACHE_MAX_BINS,
won't we evaluate large_csize2tidx (bytes) for a size that should use the small bins?
This feels risky and it's not clear it will work correctly...

I think we can remove the && tc_idx < mp_.tcache_bins in the first if-statement
if we keep the existing equivalent check in free() below - this avoids the issue.

+static __always_inline void *
+tcache_get_align (size_t nb, size_t alignment)
+{
+  size_t tc_idx = tcache_index (nb);
+
+  if (tc_idx != NO_TCACHE_BIN && tc_idx < TCACHE_MAX_BINS + TCACHE_LARGE_BINS

This is equivalent to just checking tc_idx < TCACHE_MAX_BINS (new definition). Same for
a few more uses of NO_TCACHE_BIN.

+      && tcache->counts[tc_idx] > 0)

> @@ -3430,7 +3543,7 @@ __libc_free (void *mem)
>  #if USE_TCACHE
>    size_t tc_idx = csize2tidx (size);
>  
> -  if (__glibc_likely (tcache != NULL && tc_idx < mp_.tcache_bins))
> +  if (tcache != NULL)

Why remove the tc_idx < mp_.tcache_bins here? This means we'll insert into small
tcache even if tc_idx >= mp_.tcache_bins...

> +  void *victim = tcache_get_align (checked_request2size (bytes), alignment);
> +  if (victim != NULL)
> +    return tag_new_usable (victim);
> +  MAYBE_INIT_TCACHE ();

This bit (and related removal of existing code) also has a merge conflict due to tabs.

   if (SINGLE_THREAD_P)
@@ -5482,13 +5588,22 @@ do_set_arena_max (size_t value)
 static __always_inline int
 do_set_tcache_max (size_t value)
 {
-  if (value <= MAX_TCACHE_SIZE)
+  size_t csize = request2size (value);
+  LIBC_PROBE (memory_tunable_tcache_max_bytes, 2, value, mp_.tcache_max_bytes);
+
+  if (value < MAX_TCACHE_SIZE)

Why change it from <= to < ? 

     {
-      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;
+      mp_.tcache_bins = csize2tidx (csize) + 1;
       return 1;
     }
+  else if (value < MAX_TCACHE_LARGE_SIZE)
+    {
+      mp_.tcache_max_bytes = value;
+      mp_.tcache_bins = large_csize2tidx (csize) + 1;

The cutoff point is odd, if value = 2048, it caches malloc sizes up to 4072... This also
means if you use MAX_TCACHE_LARGE_SIZE-1 (another strange cutoff), it actually overflows
the tcache arrays.

Note this allows mp_.tcache_bins >= MAX_TCACHE_SIZE (current definition), but that
would break any existing uses of small tcache code that doesn't support large tcache
(such as in __libc_calloc).

So if we keep using mp_.tcache_bins instead of mp_.tcache_max_bytes, I think the only
safe way is to check the index rather than the size.

Cheers,
Wilco