堆相关数据结构 – lycorecoの小破站

本文最后更新于28 天前，其中的信息可能已经过时，如有错误请发送邮件到506742773@qq.com

前言

看雪笔记，希望对你有帮助，Orz

malloc_par

在 ptmalloc 中使用 malloc_par 结构体来记录堆管理器的相关参数，该结构体定义于 malloc.c 中，如下：

struct malloc_par
{
  /* Tunable parameters */
  unsigned long trim_threshold;
  INTERNAL_SIZE_T top_pad;
  INTERNAL_SIZE_T mmap_threshold;
  INTERNAL_SIZE_T arena_test;
  INTERNAL_SIZE_T arena_max;
 
  /* Memory map support */
  int n_mmaps;
  int n_mmaps_max;
  int max_n_mmaps;
  /* the mmap_threshold is dynamic, until the user sets
     it manually, at which point we need to disable any
     dynamic behavior. */
  int no_dyn_threshold;
 
  /* Statistics */
  INTERNAL_SIZE_T mmapped_mem;
  /*INTERNAL_SIZE_T  sbrked_mem;*/
  /*INTERNAL_SIZE_T  max_sbrked_mem;*/
  INTERNAL_SIZE_T max_mmapped_mem;
  INTERNAL_SIZE_T max_total_mem;  /* only kept for NO_THREADS */
 
  /* First address handed out by MORECORE/sbrk.  */
  char *sbrk_base;
};

主要是定义了和 mmap 和 arena 相关的一些参数（如数量上限等），以及 sbrk 的基址，其中重要的参数解释如下：

top_pad：初始化或扩展堆的时候需要多申请的内存大小。
mmap_threshold：决定 sysmalloc 是通过 mmap 还是 sbrk 分配内存的界限，即如果申请的内存大小不小于该值则采用 mmap 分配，否则采用 sbrk 扩展 heap 区域分配。并且这个值是动态调整的，如果释放的内存是通过 mmap 得到的则 mmap_threshold 与该内存大小取 max 。并且 mmap_threshold 最大不能超过 DEFAULT_MMAP_THRESHOLD_MAX ，即 0x2000000 。
trim_threshold：用于 main_arena 中保留内存量的控制。当释放的 chunk 为 mmap 获得的，同时大小大于 mmap_threshold ，则除了更新 mmap_threshold 外还会将 trim_threshold 乘 2 。当释放的 chunk 大小不在 fast bin 范围合并完 size 大于 FASTBIN_CONSOLIDATION_THRESHOLD 即 0x10000 ，会根据该字段缩小 top chunk 。
n_mmaps：mmap 的内存数量，即 ptmalloc 每次成功 mmap 则 n_mmaps 加 1，ptmalloc 每次成功 munmap 则 n_mmaps 减 1 。
n_mmaps_max：n_mmaps 的上限，即最多能 mmap 的内存数量。
max_n_mmaps：n_mmaps 达到过的最大值。
mmapped_mem：当前 mmap 的内存大小总和。
max_mmapped_mem：mmap 的内存大小总和达到过的最大值。
sbrk_base：表示通过 brk 系统调用申请的 heap 区域的起始地址。
no_dyn_threshold：表示是否禁用 heap 动态调整保留内存的大小，默认为 0 。

该结构体类型的实例 mp_ 用以记录 ptmalloc 相关参数，同样定义于 malloc.c 中，如下：

# define DEFAULT_TOP_PAD 131072 // 0x20000
#define DEFAULT_MMAP_MAX       (65536) // 0x10000
#define DEFAULT_MMAP_THRESHOLD_MIN (128 * 1024)
#define DEFAULT_MMAP_THRESHOLD DEFAULT_MMAP_THRESHOLD_MIN // 0x20000
#define DEFAULT_TRIM_THRESHOLD (128 * 1024) // 0x20000
 
static struct malloc_par mp_ =
{
  .top_pad = DEFAULT_TOP_PAD,
  .n_mmaps_max = DEFAULT_MMAP_MAX,
  .mmap_threshold = DEFAULT_MMAP_THRESHOLD,
  .trim_threshold = DEFAULT_TRIM_THRESHOLD,
#define NARENAS_FROM_NCORES(n) ((n) * (sizeof (long) == 4 ? 2 : 8))
  .arena_test = NARENAS_FROM_NCORES (1)
};

heap_info 位于一个 heap 块的开头，用以记录通过 mmap 系统调用从 Memory Mapping Segment 处申请到的内存块的信息。定义于 arena.c 中。

/* A heap is a single contiguous memory region holding (coalesceable)
   malloc_chunks.  It is allocated with mmap() and always starts at an
   address aligned to HEAP_MAX_SIZE.  */
 
typedef struct _heap_info
{
  mstate ar_ptr; /* Arena for this heap. */
  struct _heap_info *prev; /* Previous heap. */
  size_t size;   /* Current size in bytes. */
  size_t mprotect_size; /* Size in bytes that has been mprotected
                           PROT_READ|PROT_WRITE.  */
  /* Make sure the following data is properly aligned, particularly
     that sizeof (heap_info) + 2 * SIZE_SZ is a multiple of
     MALLOC_ALIGNMENT. */
  char pad[-6 * SIZE_SZ & MALLOC_ALIGN_MASK];
} heap_info;

heap_info 结构体的成员如下：

ar_ptr：指向管理该堆块的 arena
prev：该heap_info所链接的上一个 heap_info
size：记录该堆块的大小
mprotect_size：记录该堆块中被保护（mprotected）的大小
pad：即 padding ，用以在 SIZE_SZ 不正常的情况下进行填充以让内存对齐，正常情况下 pad 所占用空间应为 0 字节

arena

大部分情况下对于每个线程而言其都会单独有着一个 arena 实例用以管理属于该线程的堆内存区域。ptmalloc 内部的内存池结构是由 malloc_state 结构体进行定义的，即 arena 本身便为 malloc_state 的一个实例对象。
malloc_state 结构体定义于malloc/malloc.c 中，代码如下：

struct malloc_state
{
  /* Serialize access.  */
  mutex_t mutex;
 
  /* Flags (formerly in max_fast).  */
  int flags;
 
  /* Fastbins */
  mfastbinptr fastbinsY[NFASTBINS];
 
  /* Base of the topmost chunk -- not otherwise kept in a bin */
  mchunkptr top;
 
  /* The remainder from the most recent split of a small request */
  mchunkptr last_remainder;
 
  /* Normal bins packed as described above */
  mchunkptr bins[NBINS * 2 - 2];
 
  /* Bitmap of bins */
  unsigned int binmap[BINMAPSIZE];
 
  /* Linked list */
  struct malloc_state *next;
 
  /* Linked list for free arenas.  Access to this field is serialized
     by free_list_lock in arena.c.  */
  struct malloc_state *next_free;
 
  /* Number of threads attached to this arena.  0 if the arena is on
     the free list.  Access to this field is serialized by
     free_list_lock in arena.c.  */
  INTERNAL_SIZE_T attached_threads;
 
  /* Memory allocated from the system in this arena.  */
  INTERNAL_SIZE_T system_mem;
  INTERNAL_SIZE_T max_system_mem;
};

malloc_state 结构体的成员如下：

mutex：mutex 变量即为多线程互斥锁，用以保证线程安全。
flags：标志位，用以表示 arena 的一些状态，如：是否有 fastbin 、内存是否连续等。
fastbinY：存放 fastbin chunk 的数组。
top：指向 Top Chunk 的指针。
last_remainder：chunk 切割中的剩余部分。malloc 在分配 chunk 时若是没找到 size 合适的 chunk 而是找到了一个 size 更大的 chunk ，则会从大 chunk 中切割掉一块返回给用户，剩下的那一块便是 last_remainder ，其随后会被放入 unsorted bin 中。
bins：存放闲置 chunk 的数组。bins 包括 large bin，small bin 和 unsorted bin 。
binmap：记录 bin 是否为空的 bitset 。需要注意的是 chunk 被取出后若一个 bin 空了并不会立即被置 0 ，而会在下一次遍历到时重新置位。
next：指向下一个 arena 的指针。一个进程内所有的 arena 串成了一条循环单向链表，malloc_state 中的 next 指针便是用以指向下一个 arena ，方便后续的遍历 arena 的操作（因为不是所有的线程都有自己独立的 arena ）。
next_free：指向下一个空闲的 arena 的指针。与 next 指针类似，只不过指向的是空闲的 arena（即没有被任一线程所占用）。
attached_threads：与该 arena 相关联的线程数。该变量用以表示有多少个线程与该arena 相关联，这是因为 aerna 的数量是有限的，并非每一个线程都有机会分配到一个arena，在线程数量较大的情况下会存在着多个线程共用一个 arena 的情况。
system_mem：记录当前 arena 在堆区中所分配到的内存的总大小。
max_system_mem：当操作系统予进程以内存时，system_mem 会随之增大，当内存被返还给操作系统时，sysyetm_mem 会随之减小，max_system_mem 变量便是用来记录在这个过程当中 system_mem 的峰值。

main_arena 为一个定义于 malloc.c 中的静态的 malloc_state 结构体。

static struct malloc_state main_arena =
{
  .mutex = _LIBC_LOCK_INITIALIZER,
  .next = &main_arena,
  .attached_threads = 1
};

由于其为 libc 中的静态变量，该 arena 会被随着 libc 文件一同加载到 Memory Mapping Segment。因此在堆题中通常通过泄露 arena 的地址以获得 libc 在内存中的基地址。

chunk

在程序的执行过程中，我们称由 malloc 申请的内存为 chunk 。这块内存在 ptmalloc 内部用 malloc_chunk 结构体来表示。当程序申请的 chunk 被 free 后，会被加入到相应的空闲管理列表中。
malloc_chunk 定义如下：

struct malloc_chunk {
 
  INTERNAL_SIZE_T      prev_size;  /* Size of previous chunk (if free).  */
  INTERNAL_SIZE_T      size;       /* Size in bytes, including overhead. */
 
  struct malloc_chunk* fd;         /* double links -- used only if free. */
  struct malloc_chunk* bk;
 
  /* Only used for large blocks: pointer to next larger size.  */
  struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
  struct malloc_chunk* bk_nextsize;
};

每个字段的具体的解释如下：

prev_size：如果物理相邻的前一地址 chunk 是空闲的话，那该字段记录的是前一个 chunk 的大小 (包括 chunk 头)。否则，该字段可以用来存储物理相邻的前一个 chunk 的数据。
size：该 chunk 的大小，大小必须是 2 * SIZE_SZ 的整数倍。该字段的低三个比特位对 chunk 的大小没有影响，它们从高到低分别表示为：

NON_MAIN_ARENA，记录当前 chunk 是否不属于主线程，1 表示不属于，0 表示属于。
IS_MAPPED，记录当前 chunk 是否是由 mmap 分配的。
PREV_INUSE，记录前一个 chunk 块是否被分配。一般来说，堆中第一个被分配的内存块的 size 字段的 P 位都会被设置为 1，以便于防止访问前面的非法内存。当一个 chunk 的 size 的 P 位为 0 时，我们能通过 prev_size 字段来获取上一个 chunk 的大小以及地址。这也方便进行空闲 chunk 之间的合并。
fd，bk。 chunk 处于分配状态时，从 fd 字段开始是用户的数据。chunk 空闲时，会被添加到对应的空闲管理链表中，其字段的含义如下

fd 指向下一个（非物理相邻）空闲的 chunk
bk 指向上一个（非物理相邻）空闲的 chunk

通过 fd 和 bk 可以将空闲的 chunk 块加入到空闲的 chunk 块链表进行统一管理

fd_nextsize， bk_nextsize，也是只有 chunk 空闲的时候才使用，不过其用于较大的 chunk（large chunk）。

fd_nextsize 指向前一个与当前 chunk 大小不同的第一个空闲块，不包含 bin 的头指针。
bk_nextsize 指向后一个与当前 chunk 大小不同的第一个空闲块，不包含 bin 的头指针。
一般空闲的 large chunk 在 fd 的遍历顺序中，按照由大到小的顺序排列。这样做可以避免在寻找合适 chunk 时挨个遍历。（~~好在 large bin 限制了值域范围，不然也会很慢~~ ）

chunk 的结构如下图所示：

bins

我们曾经说过，用户释放掉的 chunk 不会马上归还给系统，ptmalloc 会统一管理 heap 和 mmap 映射区域中的空闲的 chunk。当用户再一次请求分配内存时，ptmalloc 分配器会试图在空闲的 chunk 中挑选一块合适的给用户。这样可以避免频繁的系统调用，降低内存分配的开销。
在具体的实现中，ptmalloc 采用分箱式方法对空闲的 chunk 进行管理。首先，它会根据空闲的 chunk 的大小以及使用状态将 chunk 初步分为 4 类：fast bins，small bins，large bins，unsorted bin 。对于 libc2.26 以上版本还有 tcache 。

概述

对于 small bins，large bins，unsorted bin 来说，ptmalloc 将它们维护在一个 bins 数组中。这些 bin 对应的数据结构在 malloc_state 中，如下：

#define NBINS 128
/* Normal bins packed as described above */
mchunkptr bins[ NBINS * 2 - 2 ];

bins 数组实际上可以看做是以 chunk 为单位，只不过采用空间复用策略，因为实际用到的只有 fd 和 bk

/* addressing -- note that bin_at(0) does not exist */
#define bin_at(m, i) \
  (mbinptr) (((char *) &((m)->bins[((i) - 1) * 2]))                \
             - offsetof (struct malloc_chunk, fd))

由于是双链表结构 bins 数组每连续两个 chunk 指针维护一个 bin（即 fd 和 bk ），其结构如下图所示（64位）。其中 small bins 中 chunk 大小已给出。large bins 的每个 bin 中的 chunk 大小在一个范围内。

large bin 的 chunk 范围如下：

编号	64位最小	64位最大	64位公差	32位最小	32位最大	32位公差
64	0x400	0x430	0x40	0x200	0x238	0x40
65	0x440	0x470	0x40	0x240	0x278	0x40
66	0x480	0x4b0	0x40	0x280	0x2b8	0x40
67	0x4c0	0x4f0	0x40	0x2c0	0x2f8	0x40
68	0x500	0x530	0x40	0x300	0x338	0x40
69	0x540	0x570	0x40	0x340	0x378	0x40
70	0x580	0x5b0	0x40	0x380	0x3b8	0x40
71	0x5c0	0x5f0	0x40	0x3c0	0x3f8	0x40
72	0x600	0x630	0x40	0x400	0x438	0x40
73	0x640	0x670	0x40	0x440	0x478	0x40
74	0x680	0x6b0	0x40	0x480	0x4b8	0x40
75	0x6c0	0x6f0	0x40	0x4c0	0x4f8	0x40
76	0x700	0x730	0x40	0x500	0x538	0x40
77	0x740	0x770	0x40	0x540	0x578	0x40
78	0x780	0x7b0	0x40	0x580	0x5b8	0x40
79	0x7c0	0x7f0	0x40	0x5c0	0x5f8	0x40
80	0x800	0x830	0x40	0x600	0x638	0x40
81	0x840	0x870	0x40	0x640	0x678	0x40
82	0x880	0x8b0	0x40	0x680	0x6b8	0x40
83	0x8c0	0x8f0	0x40	0x6c0	0x6f8	0x40
84	0x900	0x930	0x40	0x700	0x738	0x40
85	0x940	0x970	0x40	0x740	0x778	0x40
86	0x980	0x9b0	0x40	0x780	0x7b8	0x40
87	0x9c0	0x9f0	0x40	0x7c0	0x7f8	0x40
88	0xa00	0xa30	0x40	0x800	0x838	0x40
89	0xa40	0xa70	0x40	0x840	0x878	0x40
90	0xa80	0xab0	0x40	0x880	0x8b8	0x40
91	0xac0	0xaf0	0x40	0x8c0	0x8f8	0x40
92	0xb00	0xb30	0x40	0x900	0x938	0x40
93	0xb40	0xb70	0x40	0x940	0x978	0x40
94	0xb80	0xbb0	0x40	0x980	0x9b8	0x40
95	0xbc0	0xbf0	0x40	0x9c0	0x9f8	0x40
96	0xc00	0xc30	0x40	0xa00	0xbf8	0x200
97	0xc40	0xdf0	0x1c0	0xc00	0xdf8	0x200
98	0xe00	0xff0	0x200	0xe00	0xff8	0x200
99	0x1000	0x11f0	0x200	0x1000	0x11f8	0x200
100	0x1200	0x13f0	0x200	0x1200	0x13f8	0x200
101	0x1400	0x15f0	0x200	0x1400	0x15f8	0x200
102	0x1600	0x17f0	0x200	0x1600	0x17f8	0x200
103	0x1800	0x19f0	0x200	0x1800	0x19f8	0x200
104	0x1a00	0x1bf0	0x200	0x1a00	0x1bf8	0x200
105	0x1c00	0x1df0	0x200	0x1c00	0x1df8	0x200
106	0x1e00	0x1ff0	0x200	0x1e00	0x1ff8	0x200
107	0x2000	0x21f0	0x200	0x2000	0x21f8	0x200
108	0x2200	0x23f0	0x200	0x2200	0x23f8	0x200
109	0x2400	0x25f0	0x200	0x2400	0x25f8	0x200
110	0x2600	0x27f0	0x200	0x2600	0x27f8	0x200
111	0x2800	0x29f0	0x200	0x2800	0x29f8	0x200
112	0x2a00	0x2ff0	0x600	0x2a00	0x2ff8	0x600
113	0x3000	0x3ff0	0x1000	0x3000	0x3ff8	0x1000
114	0x4000	0x4ff0	0x1000	0x4000	0x4ff8	0x1000
115	0x5000	0x5ff0	0x1000	0x5000	0x5ff8	0x1000
116	0x6000	0x6ff0	0x1000	0x6000	0x6ff8	0x1000
117	0x7000	0x7ff0	0x1000	0x7000	0x7ff8	0x1000
118	0x8000	0x8ff0	0x1000	0x8000	0x8ff8	0x1000
119	0x9000	0x9ff0	0x1000	0x9000	0x9ff8	0x1000
120	0xa000	0xfff0	0x6000	0xa000	0xfff8	0x6000
121	0x10000	0x17ff0	0x8000	0x10000	0x17ff8	0x8000
122	0x18000	0x1fff0	0x8000	0x18000	0x1fff8	0x8000
123	0x20000	0x27ff0	0x8000	0x20000	0x27ff8	0x8000
124	0x28000	0x3fff0	0x18000	0x28000	0x3fff8	0x18000
125	0x40000	0x7fff0	0x40000	0x40000	0x7fff8	0x40000
126	0x80000	inf		0x80000	inf

对于 fast bin ，在 malloc_state 又单独定义了一个 fastbinsY 的结构维护

typedef struct malloc_chunk *mfastbinptr;
 
/*
    This is in malloc_state.
    /* Fastbins */
    mfastbinptr fastbinsY[ NFASTBINS ];
*/

由于 fast bin 为单链表结构，因此数组中一个指针就可以维护一个 bin 。结构如图所示：

Fast Bin

为了避免大部分时间花在了合并、分割以及中间检查的过程中影响效率，因此 ptmalloc 中专门设计了 fast bin。
fast bin 采用单链表形式，结构如下图所示：

fast bin 有如下性质：

由于采用单链表结构，fast bin 采取 LIFO 策略。
每个 fast bin 中维护的 chunk 大小确定，并且 fast bin 维护的最大的 chunk 为 128 字节（64位），因此不超过 0x80（chunk 大小）的内存释放会进入 fast bin 。
fast bin 范围的 chunk 下一个相邻 chunk 的 PREV_INUSE 始终被置为 1。因此它们不会和其它被释放的 chunk 合并。除非调用 malloc_consolidate 函数。

安全检查：

size：在 malloc() 函数分配 fastbin size 范围的 chunk 时，若是对应的 fastbin 中有空闲 chunk，在取出前会检查其 size 域与对应下标是否一致，不会检查标志位，若否便会触发abort 。
double free：在 free() 函数中会对 fast bin 链表的头结点进行检查，若将要被放入 fast bin 中的 chunk 与对应下标的链表的头结点为同一 chunk，则会触发 abort 。
Safe linking 机制（only glibc2.32 and up）：自 glibc 2.32 起引入了 safe-linking 机制，其核心思想是在链表上的 chunk 中并不直接存放其所连接的下一个 chunk 的地址，而是存放下一个 chunk 的地址与【 fd 指针自身地址右移 12位】所异或得的值，使得攻击者在得知该 chunk 的地址之前无法直接利用其构造任意地址写

#define PROTECT_PTR(pos, ptr) \
  ((__typeof (ptr)) ((((size_t) pos) >> 12) ^ ((size_t) ptr)))
#define REVEAL_PTR(ptr)  PROTECT_PTR (&ptr, ptr)

需要注意的是 fast bin 的入口节点存放的仍是未经异或的 chunk 地址。
另外第一个加入 fast bin 的 chunk 的 fd 字段可以泄露堆地址（右移 12 位）。

unsigned int idx = fastbin_index(size);
  fb = &fastbin (av, idx);
  mchunkptr old = *fb, old2;
  ...
p->fd = PROTECT_PTR (&p->fd, old);
*fb = p;

Small Bin

small bin 采用双向链表，结构如下图所示。

small bin 有如下性质：

small bins 中每个 bin 对应的链表采用 FIFO 的规则。
每个 small bin 维护的 chunk 大小确定，并且 small bin 维护的最大的 chunk 为 1008 字节（64位），即 0x3f0 的 chunk 大小。

Large Bin

large bins 中一共包括 63 个 bin，每个 bin 中的 chunk 的大小不一致，而是处于一定区间范围内。large bin 的结构如下：

关于 fd_nextsize 和 bk_nextsize 的机制，这里以 fd_nextsize 为例：

fd_nextsize 和 bk_nextsize 与 bins 数组没有连接关系（这就解释了为什么 bins 上没有体现 fd_nextsize 和 bk_nextsize 结构）。
large bin 里的 chunk 在 fd 指针指向的方向上按照 chunk 大小降序排序。
当 large bin 里有一个 chunk 时， fd_nextsize 和 bk_nextsize 指向自己（如上面 large bin 的结构图所示）。
当 large bin 里同一大小的 chunk 有多个时，只有相同大小 chunk 中的第一个的 fd_nextsize 和 bk_nextsize 指针有效，其余的 chunk 的 fd_nextsize 和 bk_nextsize 设为 NULL 。

large bin 中有多个不同大小的 chunk 时 fd_nextsize 连接比它小的第一个 chunk ，bk_nextsize 就是把 fd_nextsize 反过来连到对应结构上。

large bin 最小的一组 chunk 中的第一个 chunk 的 fd_nextsize 连接的是最大的 chunk，最大的 chunk 的 bk_nextsize 相反。

Unsorted Bin

unsorted bin 可以视为空闲 chunk 回归其所属 bin 之前的缓冲区。像 small bin 一样采用双向链表维护。chunk 大小乱序。

Top Chunk

程序第一次进行 malloc 的时候，heap 会被分为两块，一块给用户，剩下的那块就是 top chunk。其实，所谓的 top chunk 就是处于当前堆的物理地址最高的 chunk 。这个 chunk 不属于任何一个 bin ，它的作用在于当所有的 bin 都无法满足用户请求的大小时，如果其大小不小于指定的大小，就进行分配，并将剩下的部分作为新的 top chunk。否则，就对 heap 进行扩展后再进行分配。在 main_arena 中通过 sbrk 扩展 heap，而在 thread arena 中通过 mmap 分配新的 heap 。
需要注意的是，top chunk 的 prev_inuse 比特位始终为 1，否则其前面的 chunk 就会被合并到 top chunk 中。

last remainder

在用户使用 malloc 请求分配内存时，ptmalloc2 找到的 chunk 可能并不和申请的内存大小一致，这时候就将分割之后的剩余部分称之为 last remainder chunk ，unsort bin 也会存这一块。top chunk 分割剩下的部分不会作为 last_remainder 。

tcache

tcache 是 glibc 2.26 (ubuntu 17.10) 之后引入的一种技术，目的是提升堆管理的性能，与 fast bin 类似。tcache 引入了两个新的结构体，tcache_entry 和 tcache_perthread_struct 。

tcache_entry 定义如下：

typedef struct tcache_entry
{
  struct tcache_entry *next;
} tcache_entry;

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

tcache_perthread_struct 定义如下：

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;

对应结构如下

每个 thread 都会维护一个 tcache_perthread_struct ，它是整个 tcache 的管理结构，一共有 TCACHE_MAX_BINS 个计数器和 TCACHE_MAX_BINS 项 tcache_entry。这个结构在 tcache_init 函数中被初始化在堆上，大小为 0x250（高版本为 0x290）。其中数据部分前 0x40 为 counts ，剩下的为 entries 结构。如果能控制这个堆块就可以控制整个 tcache 。

static void
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);
  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));
    }
 
}

tcache_perthread_struct 中的 tcache_entry 用单向链表的方式链接了相同大小的处于空闲状态（free 后）的 chunk，这一点上和 fast bin 很像。

另外与 fast bin 相同的是释放进入 tcache 的 chunk 的下一个相邻 chunk 的 PREV_INUSE 位不清零。

counts 记录了 tcache_entry 链上空闲 chunk 的数目，每条链上最多可以有 7 个 chunk 。注意指针指向的位置是 fd 指针，这一点与 fast bin 不同。
结构如下：

stash 机制：
当申请的大小在 tcache 范围的 chunk 在 tcache 中没有，此时 ptmalloc 会在其他 bin 里面找，如果找到了会将该 chunk 放到 tcache 中，直到 tcache 填满，最后直接返回找到的 chunk 或是从 tcache 中取出并返回。