2.4x 的 tcache 机制分析

简述

在 2.39 到 2.40 中，malloc.c 并未发生变化，因此我们这里主要讲一些 2.41 到 2.43 的 tcache 相关的一些小细节在这三个版本中，主要变化可以简单概括为

2.41:
- calloc 可以分配 tcache 块
- 小 chunk 被 free 后会直接进入 small bin
2.42
- large_tcache 的引入
2.43
- tcache 扩容以补偿 fastbin 删除的性能问题
- large_tcache 分配改为需要精确 chunk_size
- mmap chunk 可以进入 tcache

因为 tcache 初始化时机这几个版本一直改来改去的很乱，只做简述以下为细分的分析，我会粘贴一些源码辅助理解

tcache 基本机制

tcache 结构体的变化

在 glibc 2.42版本中，tcache_perthread_struct 结构进行了调整

2.41

/* We overlay this structure on the user-data portion of a chunk when
   the chunk is stored in the per-thread cache.  */
typedef struct tcache_entry
{
  struct tcache_entry *next;
  /* This field exists to detect double frees.  */
  uintptr_t key;
} tcache_entry;

/* There is one of these for each thread, which contains the
   per-thread cache (hence "tcache_perthread_struct").  Keeping
   overall size low is mildly important.  Note that COUNTS and ENTRIES
   are redundant (we could have just counted the linked list each
   time), this is for performance reasons.  */
typedef struct tcache_perthread_struct
{
  uint16_t counts[TCACHE_MAX_BINS];
  tcache_entry *entries[TCACHE_MAX_BINS];
} tcache_perthread_struct;

static __thread bool tcache_shutting_down = false;
static __thread tcache_perthread_struct *tcache = NULL;

2.42

/* We overlay this structure on the user-data portion of a chunk when
   the chunk is stored in the per-thread cache.  */
typedef struct tcache_entry
{
  struct tcache_entry *next;
  /* This field exists to detect double frees.  */
  uintptr_t key;
} tcache_entry;

/* There is one of these for each thread, which contains the
   per-thread cache (hence "tcache_perthread_struct").  Keeping
   overall size low is mildly important.  The 'entries' field is linked list of
   free blocks, while 'num_slots' contains the number of free blocks that can
   be added.  Each bin may allow a different maximum number of free blocks,
   and can be disabled by initializing 'num_slots' to zero.  */
typedef struct tcache_perthread_struct
{
  uint16_t num_slots[TCACHE_MAX_BINS];
  tcache_entry *entries[TCACHE_MAX_BINS];
} tcache_perthread_struct;

entry 的部分基本没有变化，这里主要变化还是原本的 counts 数组变成了 num_slots 数组原本的 counts 数组表示对应索引下 tcache 链表的长度，现在 num_slots 数组中变为了对应索引下设剩下的空槽位

2.41

/* Caller must ensure that we know tc_idx is valid and there's room
   for more chunks.  */
static __always_inline void
tcache_put (mchunkptr chunk, size_t tc_idx)
{
  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.  */
  e->key = tcache_key;

  e->next = PROTECT_PTR (&e->next, tcache->entries[tc_idx]);
  tcache->entries[tc_idx] = e;
  ++(tcache->counts[tc_idx]);
}

/* Caller must ensure that we know tc_idx is valid and there's
   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)
{
  tcache_entry *e;
  if (ep == &(tcache->entries[tc_idx]))
    e = *ep;
  else
    e = REVEAL_PTR (*ep);

  if (__glibc_unlikely (!aligned_OK (e)))
    malloc_printerr ("malloc(): unaligned tcache chunk detected");

  if (ep == &(tcache->entries[tc_idx]))
      *ep = REVEAL_PTR (e->next);
  else
    *ep = PROTECT_PTR (ep, REVEAL_PTR (e->next));

  --(tcache->counts[tc_idx]);
  e->key = 0;
  return (void *) e;
}

2.42

/* Caller must ensure that we know tc_idx is valid and there's room
   for more chunks.  */
static __always_inline void
tcache_put_n (mchunkptr chunk, size_t tc_idx, tcache_entry **ep, bool mangled)
{
  tcache_entry *e = (tcache_entry *) chunk2mem (chunk);

  /* Mark this chunk as "in the tcache" so the test in __libc_free will
     detect a double free.  */
  e->key = tcache_key;

  if (!mangled)
    {
      e->next = PROTECT_PTR (&e->next, *ep);
      *ep = e;
    }
  else
    {
      e->next = PROTECT_PTR (&e->next, REVEAL_PTR (*ep));
      *ep = PROTECT_PTR (ep, e);
    }
  --(tcache->num_slots[tc_idx]);
}

/* Caller must ensure that we know tc_idx is valid and there's
   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_entry *e;
  if (!mangled)
    e = *ep;
  else
    e = REVEAL_PTR (*ep);

  if (__glibc_unlikely (misaligned_mem (e)))
    malloc_printerr ("malloc(): unaligned tcache chunk detected");

  void *ne = e == NULL ? NULL : REVEAL_PTR (e->next);
  if (!mangled)
    *ep = ne;
  else
    *ep = PROTECT_PTR (ep, ne);

  ++(tcache->num_slots[tc_idx]);
  e->key = 0;
  return (void *) e;
}

从两个不同版本的源码中对 tcache 的 get 和 put 操作来看，counts 到 num_slots 主要是一个语义反转的变化

malloc_par 结构体的变化

因为这两个结构体比较大这里就只保留关键部分

2.41

struct malloc_par
{
#if USE_TCACHE
  /* Maximum number of buckets to use.  */
  size_t tcache_bins;
  size_t tcache_max_bytes;
  /* Maximum number of chunks in each bucket.  */
  size_t tcache_count;
  /* Maximum number of chunks to remove from the unsorted list, which
     aren't used to prefill the cache.  */
  size_t tcache_unsorted_limit;
#endif
};

2.42

struct malloc_par
{
#if USE_TCACHE
  /* Maximum number of small buckets to use.  */
  size_t tcache_small_bins;
  size_t tcache_max_bytes;
  /* Maximum number of chunks in each bucket.  */
  size_t tcache_count;
  /* Maximum number of chunks to remove from the unsorted list, which
     aren't used to prefill the cache.  */
  size_t tcache_unsorted_limit;
#endif
};

2.41 中的 tcache_bins 被替换为了 tcache_small_bins ，在 mp_ 调整 tcache_small_bins 仅可以控制 small_tcache，而是否允许 large tcache，主要由 tcache_max_bytes 控制

tcache_init()变化

在 2.41 中

static void
tcache_init(void)
{
  mstate ar_ptr;
  void *victim = NULL;
  const size_t bytes = sizeof (tcache_perthread_struct);

  if (tcache_shutting_down)
    return;

  arena_get (ar_ptr, bytes);
  victim = _int_malloc (ar_ptr, bytes);
  if (!victim && ar_ptr != NULL)
    {
      ar_ptr = arena_get_retry (ar_ptr, bytes);
      victim = _int_malloc (ar_ptr, bytes);
    }


  if (ar_ptr != NULL)
    __libc_lock_unlock (ar_ptr->mutex);

  /* In a low memory situation, we may not be able to allocate memory
     - in which case, we just keep trying later.  However, we
     typically do this very early, so either there is sufficient
     memory, or there isn't enough memory to do non-trivial
     allocations anyway.  */
  if (victim)
    {
      tcache = (tcache_perthread_struct *) victim;
      memset (tcache, 0, sizeof (tcache_perthread_struct));
    }

}

主要是获取 arena ,调用 _int_malloc() 分配 sizeof(tcache_perthread_struct) 并 memset 为零清零后刚好对应

counts[i] = 0
entries[i] = NULL

表示所有 bin 都为空

2.42 中

/* Initialize tcache.  In the rare case there isn't any memory available,
   later calls will retry initialization.  */
static void
tcache_init (void)
{
  if (tcache_shutting_down)
    return;

  /* Check minimum mmap chunk is larger than max tcache size.  This means
     mmap chunks with their different layout are never added to tcache.  */
  if (MAX_TCACHE_SMALL_SIZE >= GLRO (dl_pagesize) / 2)
    malloc_printerr ("max tcache size too large");

  size_t bytes = sizeof (tcache_perthread_struct);
  tcache = (tcache_perthread_struct *) __libc_malloc2 (bytes);

  if (tcache != NULL)
    {
      memset (tcache, 0, bytes);
      for (int i = 0; i < TCACHE_MAX_BINS; i++)
	tcache->num_slots[i] = mp_.tcache_count;
    }
}

通过内部的 _libc_malloc2() 分配结构，清零整个结构，在新语义中表示没有剩余槽位，也就是 bin 已满或被禁用，而不是 bin 为空，所以需要显式设置 tcache->num_slots[i] = mp.tcache_count

large_tcache 机制

这里主要讨论 x86-64 架构下的 large_tcache 相关机制

large_tcache 索引算法

在 glibc 2.42 的版本中，large_tcache 被添加了进来。tcache 机制与 2.41 相比，有了small_tcache和large_tcache的区别附上 tcache 相关的宏的对比

2.41

#if USE_TCACHE
/* We want 64 entries.  This is an arbitrary limit, which tunables can reduce.  */
# define TCACHE_MAX_BINS		64
# define MAX_TCACHE_SIZE	tidx2usize (TCACHE_MAX_BINS-1)

2.42

#if USE_TCACHE
/* We want 64 entries.  This is an arbitrary limit, which tunables can reduce.  */
# define TCACHE_SMALL_BINS		64
# define TCACHE_LARGE_BINS		12 /* Up to 4M chunks */
# define TCACHE_MAX_BINS	(TCACHE_SMALL_BINS + TCACHE_LARGE_BINS)
# define MAX_TCACHE_SMALL_SIZE	tidx2usize (TCACHE_SMALL_BINS-1)

注意到原本的 TCACHE_MAX_BINS 为 64 被移动到了新的 TCACHE_SAMLL_BINS ，同时使得新定义的 TCACHE_MAX_BINS 变为了 TCACHE_SMALL_BINS 与 TCACHE_LARGE_BINS 的和，也就是说默认情况下，TCACHE 数组的长度来到了 64+12 = 76 个从 tcache 的 idx = 0 到 idx = 63 排列，仍然为 chunk_size 为0x20 到 0x420 的大小的 tcache ，也就是现在的small_tcache

新的 large_tcache 的大小索引与 small_tcache 有了一个巨大的变化，同一个索引下会有多个不同大小的 tcache chunk,具体的范围计算如下

static __always_inline size_t
large_csize2tidx(size_t nb)
{
  size_t idx = TCACHE_SMALL_BINS
	       + __builtin_clz (MAX_TCACHE_SMALL_SIZE)
	       - __builtin_clz (nb);
  return idx;
}

这里的 MAX_TCACHE_SMALL_SIZE 经过计算也即是刚刚的 0x420 ，TCACHE_SMALL_BINS 为 64， nb 为目标 chunk_size 我们可以简单的写一个程序计算不同大小的 chunk 对应的 idx

//不考虑对齐的情况下，仅计算large_tcache范围
#include <stdio.h>
#include <stdlib.h>

#define MAX_TCACHE_SMALL_SIZE 0x420

size_t calc_large_tcache_idx(size_t size){
  size_t idx;
  idx = 64 + __builtin_clz(MAX_TCACHE_SMALL_SIZE) - __builtin_clz(size);

  return idx;
}

int main(){
  size_t size;
  size_t ret_idx;
  
  scanf("%lx",&size);
  ret_idx = calc_large_tcache_idx(size);
  printf("%ld",ret_idx);
}

因此，我们可以简单的列一个表

tcache idx	chunk size 范围	对应 malloc 请求范围
64	0x420 - 0x7f0	0x409 - 0x7e8
65	0x800 - 0xff0	0x7e9 - 0xfe8
66	0x1000 - 0x1ff0	0xfe9 - 0x1fe8
67	0x2000 - 0x3ff0	0x1fe9 - 0x3fe8
68	0x4000 - 0x7ff0	0x3fe9 - 0x7fe8
69	0x8000 - 0xfff0	0x7fe9 - 0xffe8
70	0x10000 - 0x1fff0	0xffe9 - 0x1ffe8
71	0x20000 - 0x3fff0	0x1ffe9 - 0x3ffe8
72	0x40000 - 0x7fff0	0x3ffe9 - 0x7ffe8
73	0x80000 - 0xffff0	0x7ffe9 - 0xfffe8
74	0x100000 - 0x1ffff0	0xfffe9 - 0x1fffe8
75	0x200000 - 0x3ffff0	0x1fffe9 - 0x3fffe8

有意思的是 malloc.c 中的注释表示最大可以用到 4M 的tcache，事实上严格的 x86-64 最大 chunk size为0x3ffff0,严格的最大普通请求为0x3fffe8

large_tcache 加入后的 tcache 链表插入算法

在 2.41 中

/* Caller must ensure that we know tc_idx is valid and there's room
   for more chunks.  */
static __always_inline void
tcache_put (mchunkptr chunk, size_t tc_idx)
{
  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.  */
  e->key = tcache_key;

  e->next = PROTECT_PTR (&e->next, tcache->entries[tc_idx]);
  tcache->entries[tc_idx] = e;
  ++(tcache->counts[tc_idx]);
}

从链表插入都是从链表头部插入

在 2.42 中

/* Caller must ensure that we know tc_idx is valid and there's room
   for more chunks.  */
static __always_inline void
tcache_put_n (mchunkptr chunk, size_t tc_idx, tcache_entry **ep, bool mangled)
{
  tcache_entry *e = (tcache_entry *) chunk2mem (chunk);

  /* Mark this chunk as "in the tcache" so the test in __libc_free will
     detect a double free.  */
  e->key = tcache_key;

  if (!mangled)
    {
      e->next = PROTECT_PTR (&e->next, *ep);
      *ep = e;
    }
  else
    {
      e->next = PROTECT_PTR (&e->next, REVEAL_PTR (*ep));
      *ep = PROTECT_PTR (ep, e);
    }
  --(tcache->num_slots[tc_idx]);
}

在传入 tcache_put_n 的参数中多了 ep 和 mangled ep 在这里可以是链表头，也可以是链表的中间 mangled 用于标记传入的指针是否经过 PROTECT_PTR 处理过，这使得传入的指针可以是被加密过的在 tcache 链表中间的指针

large_tcache 同索引下排序

large_tcache 需要有序链表 2.41 的一个 bin 只有一种尺寸，不需要搜索,2.42 的 large bin 包含多个尺寸，因此增加

static __always_inline tcache_entry **
tcache_location_large (size_t nb, size_t tc_idx, bool *mangled)
{
  tcache_entry **tep = &(tcache->entries[tc_idx]);
  tcache_entry *te = *tep;
  while (te != NULL
         && __glibc_unlikely (chunksize (mem2chunk (te)) < nb))
    {
      tep = & (te->next);
      te = REVEAL_PTR (te->next);
      *mangled = true;
    }

  return tep;
}

这使 large_tcache 链表按 chunk_size 从小到大排列，同尺寸插入时，由于循环条件是 < 而不是 <=，新释放的同尺寸 chunk 会插在旧 chunk 前面，因此同尺寸组内部仍表现为 LIFO 所以 2.42 中存在两种不同链表语义：

small tcache:
    一个 bin 一个精确尺寸
    纯链表头插入
    LIFO

large tcache:
    一个 bin 覆盖多个尺寸
    按 chunk size 升序
    同尺寸内部近似 LIFO

double free检测范围扩大

在 2.41 中

/* 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
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 (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.  */
    }
}

对于 key 的检查只在同索引下检查

在 2.42 中

/* 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
tcache_double_free_verify (tcache_entry *e)
{
  tcache_entry *tmp;
  for (size_t tc_idx = 0; tc_idx < TCACHE_MAX_BINS; ++tc_idx)
    {
      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 (cnt >= mp_.tcache_count)
	    malloc_printerr ("free(): too many chunks detected in tcache");
	  if (__glibc_unlikely (misaligned_mem (tmp)))
	    malloc_printerr ("free(): unaligned chunk detected in tcache 2");
	  if (tmp == e)
	    malloc_printerr ("free(): double free detected in tcache 2");
	}
    }
  /* No double free detected - it might be in a tcache of another thread,
     or user data that happens to match the key.  Since we are not sure,
     clear the key and retry freeing it.  */
  e->key = 0;
  __libc_free (e);
}

即遍历全部 76 个索引，large_tcache 的一个 bin 不再和某个精确 size 一一对应，因此单纯依赖当前索引进行局部检查更加不可靠，通过单独修改 size 的绕过 double free 检测的方法因此失效了

large_tcache 再次分配

2.43 中 tcache 的变化

tcache 容量扩充

在 2.43 中移除了 fastbin ，需要用更深的 tcache 保持分配性能，将 tcache

/* This is another arbitrary limit, which tunables can change.  Each
   tcache bin will hold at most this number of chunks.  */
# define TCACHE_FILL_COUNT 16

large_tcache 大小精确匹配

在 2.43 中修改了 large_tcache 分配时的大小检验，不再跨尺寸复用

static __always_inline void *
tcache_get_large (size_t tc_idx, size_t nb)
{
  tcache_entry **entry;
  bool mangled = false;
  tcache_entry *te;
  entry = tcache_location_large (nb, tc_idx, &mangled, &te);

  if (te == NULL || nb != chunksize (mem2chunk (te)))
    return NULL;

  return tcache_get_n (tc_idx, entry, mangled);
}

在这里添加了 chunksize 的精确匹配检查

mmap chunk 可以进入 tcache

在2.42中 __libc_free() 会检查 chunk 是否是 mmap 得到的，在 2.43中删除了以下检查

// 2.42
	  if (size >= MINSIZE
	      && !chunk_is_mmapped (p)
              && __glibc_likely (tcache->num_slots[tc_idx] != 0))
	    return tcache_put_large (p, tc_idx);

// 2.43
	  if (size >= MINSIZE
              && __glibc_likely (tcache->num_slots[tc_idx] != 0))
	    return tcache_put_large (p, tc_idx);

__libc_free() 会在判断是否执行 munmap() 之前先尝试把 chunk 放入 tcache

tcache key 生成检查

在 2.43 中添加了对 key 的生成条件检查，不能小于等于0x1000000，不能太接近 ULONG_MAX，还检测生成的 key 二进制数中 1 的数量

static void
tcache_key_initialize (void)
{
  /* We need to use the _nostatus version here, see BZ 29624.  */
  if (__getrandom_nocancel_nostatus_direct (&tcache_key, sizeof(tcache_key),
					    GRND_NONBLOCK)
      != sizeof (tcache_key))
    tcache_key = 0;

  /* We need tcache_key to be non-zero (otherwise tcache_double_free_verify's
     clearing of e->key would go unnoticed and it would loop getting called
     through __libc_free), and we want tcache_key not to be a
     commonly-occurring value in memory, so ensure a minimum amount of one and
     zero bits.  */
  int minimum_bits = __WORDSIZE / 4;
  int maximum_bits = __WORDSIZE - minimum_bits;

  while (tcache_key <= 0x1000000
      || tcache_key >= ((uintptr_t) ULONG_MAX) - 0x1000000
      || stdc_count_ones (tcache_key) < minimum_bits
      || stdc_count_ones (tcache_key) > maximum_bits)
    {
      tcache_key = random_bits ();
#if __WORDSIZE == 64
      tcache_key = (tcache_key << 32) | random_bits ();
#endif
    }
}

Search workspace

Keyboard shortcuts

2.4x 的 tcache 机制分析

简述

tcache 基本机制

tcache 结构体的变化

malloc_par 结构体的变化

tcache_init()变化

large_tcache 机制

large_tcache 索引算法

large_tcache 加入后的 tcache 链表插入算法

large_tcache 同索引下排序

double free检测范围扩大

large_tcache 再次分配

2.43 中 tcache 的变化

tcache 容量扩充

large_tcache 大小精确匹配

mmap chunk 可以进入 tcache

tcache key 生成检查