堆的Tcache机制

tcache是glibc 2.26（ubuntu 17.10）之后引入的一种技术 ，目的是提升堆管理的性能。但提升性能的同时舍弃了很多安全检查，也因此有利很多新的利用方式。

相关结构体

tcache 引入了两个新的结构体，tcache_entry和tcache_perthread_struct。

这其实和fastbin很像，但又不一样。

tcache_entry

1
2
3
4
5
6
/* 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;
} tcache_entry;

tcache_entry用于链接空闲的chunk结构体，其中的 next指针指向下一个大小相同的chunk。需要注意的是这里的next指向chunk的user data，而fastbin的fd指向chunk开头的地址。

而且，tcache_entry 会复用空闲chunk的user data部分。

tcache_perthread _struct

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/* 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
{
  char counts[TCACHE_MAX_BINS];
  tcache_entry *entries[TCACHE_MAX_BINS];
} tcache_perthread_struct;

# define TCACHE_MAX_BINS                64

static __thread tcache_perthread_struct *tcache = NULL;

每个tread（线程）都会维护一个 tcache_perthread_struct，他是整个tcache的管理结构，一共有 TCACHE_MAX_BINS个计数器和 TCACHE_MAX_BINS项tcache_entry,其中

  • tcache_entry用单项链表的方式链接了相同大小的处于空闲状态（free后）的chunk，这一点上和fastbin很像。
  • counts记录了 tcache_entry链上空闲chunk的数目，每个链条上最多可以有七个chunk。

基本工作方式

  • 第一次malloc时，会先malloc一快内存用来存放tcache_perthread_struct。
  • free内存，且size小于small bin size时
  • tcache 之前会放到fastbin或者unsorted bin中
  • tcache后：
    • 先放到对应的tcache中，直到tcache被填满（默认为七个）
    • tcache被填满之后，再次free的内存和之前一样被放到fastbin或者unsorted bin中
    • tcache 中的chunk不会被合并（不取消inuse bit）
  • malloc内存，且size在tcache范围内
  • 先从tcache取chunk，直到tcache为空
  • tcache为空后，从bin中找
  • tcache 为空时，如果 fastbin/smallbin/unsorted bin中有size符合的chunk，会先把 fastbin/smallbin/unsorted bin中的chunk放到tcache中，直到填满。之后再从tcache中取；因此chunk在bin中和tcache 中的顺序会反过来。

源码分析

接下来从源码的角度分析一下tcache。

_libc_malloc

第一次malloc时，会进入到MAYBE_INIT_TCACHE()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
void *
__libc_malloc (size_t bytes)
{
    ......
    ......
#if USE_TCACHE
  /* int_free also calls request2size, be careful to not pad twice.  */
  size_t tbytes;
  // 根据 malloc 传入的参数计算 chunk 实际大小，并计算 tcache 对应的下标
  checked_request2size (bytes, tbytes);
  size_t tc_idx = csize2tidx (tbytes);

  // 初始化 tcache
  MAYBE_INIT_TCACHE ();
  DIAG_PUSH_NEEDS_COMMENT;
  if (tc_idx < mp_.tcache_bins  // 根据 size 得到的 idx 在合法的范围内
      /*&& tc_idx < TCACHE_MAX_BINS*/ /* to appease gcc */
      && tcache
      && tcache->entries[tc_idx] != NULL) // tcache->entries[tc_idx] 有 chunk
    {
      return tcache_get (tc_idx);
    }
  DIAG_POP_NEEDS_COMMENT;
#endif
    ......
    ......
}

_tcache_init()

其中MAYBE_INIT_TCACHE()在tcache为空（即第一次malloc）时调用了tcache_init()，直接查看tcache_init()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
tcache_init(void)
{
  mstate ar_ptr;
  void *victim = 0;
  const size_t bytes = sizeof (tcache_perthread_struct);
  if (tcache_shutting_down)
    return;
  arena_get (ar_ptr, bytes); // 找到可用的 arena
  victim = _int_malloc (ar_ptr, bytes); // 申请一个 sizeof(tcache_perthread_struct) 大小的 chunk
  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 = (tcache_perthread_struct *) victim;
      memset (tcache, 0, sizeof (tcache_perthread_struct));
    }
}

tcache_init()成功返回后。tcache_perthread_struct被成功建立了。

申请内存

接下来进入申请内存的步骤

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
  // 从 tcache list 中获取内存
  if (tc_idx < mp_.tcache_bins // 由 size 计算的 idx 在合法范围内
      /*&& tc_idx < TCACHE_MAX_BINS*/ /* to appease gcc */
      && tcache
      && tcache->entries[tc_idx] != NULL) // 该条 tcache 链不为空
    {
      return tcache_get (tc_idx);
    }
  DIAG_POP_NEEDS_COMMENT;
#endif
  // 进入与无 tcache 时类似的流程
  if (SINGLE_THREAD_P)
    {
      victim = _int_malloc (&main_arena, bytes);
      assert (!victim || chunk_is_mmapped (mem2chunk (victim)) ||
              &main_arena == arena_for_chunk (mem2chunk (victim)));
      return victim;
    }

在tcache->entries不为空时，将进入tcache_get()的流程获取chunk,否则与tcache机制前的流程类似，这里主要分析第一种tcache_get()。这里也可以看出tcache的优先级很高，比fastbin还要高（fastbin的申请在没进入tcache的流程中）。

tcache_get()

1
2
3
4
5
6
7
8
9
10
11
12
/* Caller must ensure that we know tc_idx is valid and there's
   available chunks to remove.  */
static __always_inline void *
tcache_get (size_t tc_idx)
{
  tcache_entry *e = tcache->entries[tc_idx];
  assert (tc_idx < TCACHE_MAX_BINS);
  assert (tcache->entries[tc_idx] > 0);
  tcache->entries[tc_idx] = e->next;
  --(tcache->counts[tc_idx]); // 获得一个 chunk，counts 减一
  return (void *) e;
}

tcache_get()就是获得chunk的过程了。可以看出这个过程还是很简单的，从tcache->entries[tc_idx]中获得第一个chunk，tcache->counts减一，几乎没有任何保护。

_libc_free()

看完申请，再看看tcache时的释放

1
2
3
4
5
6
7
8
9
void
__libc_free (void *mem)
{
  ......
  ......
  MAYBE_INIT_TCACHE ();
  ar_ptr = arena_for_chunk (p);
  _int_free (ar_ptr, p, 0);
}

__libc_free()，没有太多变化，MAYBE_INIT_TCACHE()在tcache不为空失去了作用。

_int_free()

跟进_int_free()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
static void
_int_free (mstate av, mchunkptr p, int have_lock)
{
  ......
  ......
#if USE_TCACHE
  {
    size_t tc_idx = csize2tidx (size);
    if (tcache
        && tc_idx < mp_.tcache_bins // 64
        && tcache->counts[tc_idx] < mp_.tcache_count) // 7
      {
        tcache_put (p, tc_idx);
        return;
      }
  }
#endif
  ......
  ......

判断tc_idx合法，tcache->counts[tc_idx]在七个以内时，就进入tcache_put()，传递的两个参数是要释放的chunk和该chunk对应的size在tcache中的下标。

tcache_put()

1
2
3
4
5
6
7
8
9
10
11
/* 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);
  assert (tc_idx < TCACHE_MAX_BINS);
  e->next = tcache->entries[tc_idx];
  tcache->entries[tc_idx] = e;
  ++(tcache->counts[tc_idx]);
}

tcache_puts()完成了把释放的chunk插入到tcache->entries[tc_idx]链表头部的操作，也几乎没有任何保护。并且 没有把p位置零。