堆相关数据结构

Chiu Lv4
  2024-07-31 14:01:08 2024-07-31 14:01:08 Created   2024-07-31 14:01:53 2024-07-31 14:01:53 Updated    

malloc_par

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

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
28
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 中，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 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_info 位于一个 heap 块的开头，用以记录通过 mmap 系统调用从 Memory Mapping Segment 处申请到的内存块的信息。定义于 arena.c 中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/* 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 中，代码如下：

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
28
29
30
31
32
33
34
35
36
37
38
39
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 结构体。

1
2
3
4
5
6
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 定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
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 中，如下：

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

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

1
2
3
4
/* 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 的结构维护。

1
2
3
4
5
6
7
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 的地址之前无法直接利用其构造任意地址写。
1
2
3
#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 位）。

1
2
3
4
5
6
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 。

在这里插入图片描述

  • arge 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 定义如下：

1
2
3
4
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 定义如下：

1
2
3
4
5
6
7
8
9
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 。

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
28
29
30
31
32
33
34
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 中取出并返回。

安全检查：

  • tcache key（only libc2.29 and up）：自 glibc2.29 版本起 tcache 新增了一个 key 字段，该字段位于 chunk 的 bk 字段，值为 tcache 结构体的地址，若 free() 检测到 chunk->bk == tcache 则会遍历 tcache 查找对应链表中是否有该 chunk
    最新版本的一些老 glibc （如新版2.27等）也引入了该防护机制

  • Safe linking 机制（only glibc2.32 and up）：与 fast bin 类似。

    绕过方法：

    • 在 tcache 的一个 entry 中放入第一个 chunk 时，其同样会对该 entry 中的 “chunk” （NULL）进行异或运算后写入到将放入 tcache 中的 chunk 的 fd 字段，若是我们能够打印该 free chunk 的 fd 字段，便能够直接获得未经异或运算的堆上相关地址（右移 12 位）
    • 在 tcache->entry 中存放的仍是未经加密过的地址，若是我们能够控制 tcache 管理器则仍可以在不知道堆相关地址时进行任意地址写。
  • Title: 堆相关数据结构
  • Author: Chiu
  • Created at : 2024-07-31 14:01:08
  • Updated at : 2024-07-31 14:01:53
  • Link: https://github.com/Idealist17/github.io/2024/07/31/堆相关数据结构/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
堆相关数据结构
  1. malloc_par
  2. heap_info
  3. arena
  4. chunk
  5. bins
    1. 概述
    2. Fast Bin
    3. Small Bin
    4. Large Bin
    5. Unsorted Bin
  6. Top Chunk
  7. last remainder
  8. tcache