ptmalloc堆内存管理

Posted on | Edited on | In

背景介绍

Linux的栈内存管理相信大家都已经很熟悉了，针对栈内存的攻击也是比较常见的。然而对于堆内存的管理机制可能不太熟悉，针对堆内存的攻击也是比较困难的，所以我通过阅读各种资料以及Glibc的相关源码，对Glibc下的堆内存管理机制有了一定的了解，故在此记录下学习心得。

首先不同平台的堆内存管理机制是不一样的，我现在主要是针对Glibc的堆内存管理机制进行分析，Glibc的堆内存管理机制叫做ptmalloc。其他的一些比较流行的管理机制有：

  1. jemalloc(FreeBSD, Firefox, Android)
  2. ptmalloc(Glibc)
  3. tcmalloc(Google)
  4. libumem(Solaris)

Chunk structure

在Glibc的堆内存管理中，chunk是堆内存分配的基本的单位，它表示堆内存中连续的内存单元。比方说我们通过malloc(8)申请一个连续的8字节内存，则Glibc会分配我们一个大小为8(chunk size + previous size)+8(payload)大小的chunk。chunk分为allocated chunk和freed chunk。chunk structure在Glibc的定义如下所示：

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;
};

从上面的结构我们可以看出，如果一个chunk为allocated chunk，则它需要分配prev_size和size域，其中prev_size和size(表示整个chunk的大小，包括sizeof(prev_size)+sizeof(size)+sizeof(payload))用来在进行free()操作的时候将与该chunk空间上相邻的freed chunk进行合并，减少了堆内存空间的碎片化（具体怎么合并的在下面会具体介绍）。如果一个chunk为freed chunk的话，其相对于allocated chunk来说又多了两个域–fd和bk指针。因为freed chunk是通过多个链表结构将所有的freed chunk链接了起来，这样便于malloc函数快速找到合适大小的freed chunk，并且该这些表是双向链表(fastbins除外)。

所以对于malloced chunk来说，具体的内存区域如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	    |             prev_size:Size of previous chunk, if allocated  | |
	    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	    |             Size of chunk, in bytes                       |M|P|
      mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	    |             User data starts here...                          .
	    .                                                               .
	    .             (malloc_usable_size() bytes)                      .
	    .                                                               |
nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	    |             Size of chunk                                     |
	    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

在size域，有两个标志位，一个为M，一个为P。M表示该chunk是否是allocated chunk，P表示与该chunk空间上相邻的之前的chunk是否是freed chunk，如果该标识为0，表示previous chunk为freed chunk,则prev_size域表示previous chunk的大小; 否则如果previous chunk为allocated chunk，则记录previous chunk的大小就没有意义，此时就将prev_size域当做previous chunk的payload的一部分。

对于freed chunk来说，具体的内存区域如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	    |             Size of previous chunk                            |
	    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    `head:' |             Size of chunk, in bytes                         |P|
      mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	    |             Forward pointer to next chunk in list             |
	    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	    |             Back pointer to previous chunk in list            |
	    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
	    |             Unused space (may be 0 bytes long)                .
	    .                                                               .
	    .                                                               |
nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    `foot:' |             Size of chunk, in bytes                           |
	    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

对于freed chunk来说，就多了两个域：fd和bk，这两个域分别指向该链表中的前一个元素和后一个元素。

Bins

在Glibc的堆内存管理中，bin是将一个个freed chunk链接起来的链表，而bins就是存储这些链表的一维数组。每一个bin都是双向链表。根据freed chunk的大小将其分为了不同的136个bin，其中有10个为fastbin, 62个small bin，63个large bin和一个unsorted bin。在malloc_state结构中，就定义了这些bin的数组，具体声明如下：

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
struct malloc_state
{
  /* Serialize access.  */
  mutex_t mutex;

  /* Flags (formerly in max_fast).  */
  int flags;

#if THREAD_STATS
  /* Statistics for locking.  Only used if THREAD_STATS is defined.  */
  long stat_lock_direct, stat_lock_loop, stat_lock_wait;
#endif

  /* 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.  */
  struct malloc_state *next_free;

  /* Memory allocated from the system in this arena.  */
  INTERNAL_SIZE_T system_mem;
  INTERNAL_SIZE_T max_system_mem;
};

Fast Bins

在Glibc的堆内存管理机制中，一共有10个fast bin,每个fast bin链表中的所有freed chunk的大小(sizeof(prev_size)+sizeof(size)+sizeof(payload))都是相等的。每个fast bin都是一个单链表( )。Fastbins中最小的bin中的chunk大小为16字节，随后每个bin都增加8字节，所以最大的bin为80字节。需要注意的是，fast bin和其它的bin在free处理的时候有很大的不同，fast bin中的chunk的M标志都为1，因此在进行free处理的时候不进行freed chunk的合并操作(具体的合并操作在下文会具体介绍)。在每一个fast bin链表中，当有新的freed chunk需要插入时，会插入到该链表的尾部，删除也是从尾部删除，因此形成了一个先入后出(FILO)的策略。

Small Bins

Small bin的个数为62个，每一个small bin是一些大小相等的freed chunk组成的循环双向链表。当有新的freed chunk加入到该链表中，就加入到该链表的头部；如果要从链表中删除一个freed chunk时，则从该链表的为尾部删除，因此形成了一个先入先出(FIFO)的策略。第一个small bin中的freed chunk的大小都是16 bytes，后面每一个small bin的freed chunk的大小都依次增加8 bytes，因此最后一个small bin的freed chunk的大小为512 bytes。

Large Bins

与small bin和fast bin不同的是，每一个large bin中的freed chunk的大小不一定相等，其只是表示一个范围，在前32个large bin中，以64字节为步长，即第一个large bin中的chunk大小为512~575字节，第二个large bin中的free chunk大小为576~639字节。紧随其后的16个large bin依次以512字节步长为间隔；之后的8个bin以步长4096为间隔；再之后的4个bin以32768字节为间隔；之后的2个bin以262144字节为间隔；剩下的chunk就放在最后一个large bin中。

Unsorted Bin

只有一个unsorted sin，其主要存储两种chunk。一种是在malloc()操作中由于要分配的大小比freed chunk的大小要小，所以需要将该freed chunk进行分割，返回与要分配的大小相符的chunk，剩余的freed chunk则加入unsorted bin中；另一种是在free()操作之后，会返回一个新的freed chunk，该freed chunk(不在fast bin范围的chunk)则加入unsorted bin中。设置这一个bin的主要目的是扮演一个缓存层的角色以加快分配和释放的操作。

Top chunk

有一个特殊的chunk没有在以上的bins中，那就是top chunk，top chunk可以看做是heap的一个边界，当所有的bin中的chunk大小都不符合所请求的大小时，就从该chunk中进行分配，如果top chunk的大小大于所请求的大小时，则将top chunk分为两部分，一个是用户请求的chunk，剩余的部分就会成为一个新的chunk。否则，就需要扩展通过上移top chunk指针来扩展heap的大小(或者通过mmap来分配新的heap)。

Malloc

malloc函数是堆内存管理中最重要的一个函数之一，其在glibc中的包装函数为__libc_malloc(size_t)函数，在该函数中主要是进行一些准备性的工作–查找对应的arena结构，然后调用真正的分配内存的函数 _int_malloc(ar_ptr, bytes)。arena在glibc中的结构为malloc_state结构，主要存储bins，top chunk等结构。下面我们来看一下主要的分配函数_int_malloc的具体实现。

_int_malloc (mstate av, size_t bytes)

  1. 首先_int_malloc函数根据要请求的内存大小bytes来计算要请求的chunk的大小nb。主要是加上size和prev_size域和对齐的padding。

  2. 得到了要请求的chunk大小之后，首先判断该chunk的大小是否在fast bins的范围内，如果在它们的范围内就在fast bins中找到大小相符的chunk来分配。

    fast bin图片

  3. 如果要请求的大小不在fast bins范围之内或者相应的fast bin链表为空，则会判断其chunk size是否在small bins的范围之内，找到对应的small bin，取出该small bin尾部的那个chunk进行分配。
    small bin图片

  4. 如果请求的大小是一个比较大的请求，则将fast bins进行合并。其要做fast bins合作的目的是为了避免有fast bins所引起的内存碎片化问题。在实际的操作中，程序一般都是分配小的内存或者分配大的内存，而不怎么会即分配大的内存又分配小的内存。所以这样的策略在实际的程序中效率还是很理想的。

    fast bin合并图片

  5. 由于unsorted bin中存储最近freed的chunk(包括第4步合并后的fast bins)，接下来会遍历unsorted bin中的所有freed chunk，直到找到freed chunk大小和请求的大小相等的为止，或者循环了10000次也会停止遍历unsorted bin。遍历unsorted bin是唯一一个将freed chunk插入到相应的small bins和large bins的操作。在遍历的过程中，将当前节点chunk从unsorted bin中删除，如果chunk大小与要请求的chunk大小正好一致，则将该chunk返回，停止遍历，否则，将当前节点的chunk放入相应的small bins和large bins中。

    unsorted bin last remainder图片

    unsorted bin insert图片

  6. 遍历了unsorted bin之后仍然没有找到合适的freed chunk，接下来回从large bins中进行查找，首先从large bin中的chunk大于等于请求的chunk进行查找。

    large bin find

    如果该large bin为空或者最大的chunk比要请求的chunk的大小还要小，则找到chunk size范围更大的large bin，进行的操作和刚才介绍的操作一致。

  7. 如果要请求的大小比large bins中的chunk还要大，则需要查看top chunk的大小了，如果top chunk的大小比要请求的chunk的大小要大，则分割top chunk，将剩余的chunk继续作为top chunk的一部分，否则判断是否还有fastbins，如果有fastbins，则将fastbins合并。以上各种查询都没有找到合适的chunk，则只能调用sysmalloc函数来进行分配。

    top chunk malloc

  8. 至此，malloc的分配的过程已经介绍完了，总结一下其查找过程就是fastbins->smallbins->unsortedbins->largebins->topchunk

Free

free函数也是堆内存管理中最重要的函数之一，堆内存的攻击也主要是针对free函数的进行的攻击。在glibc中，__libc_free(void mem)为free(void mem)函数的包装函数，其主要的功能也是找到malloc_state结构，然后再调用 _int_free(mstate av, mchunkptr p, int have_lock)函数。

  1. 判断p指向的地址是否在p+chunksize(p)指向的地址之前，如果不符合该规则的话就会抛出错误(“free(): invalid pointer”)。

  2. 判断chunk的大小是否大于MINSIZE或者是不是MALLOC_ALIGNMENT的整数倍，否则抛出错误(“free(): invalid size”)

  3. 判断要free的chunk的大小是否落在了fast bins的范围内，如果落在了这个范围内，则将该freed chunk加入到对应的fast bin中。

    free chunk fastbin

  4. 判断该chunk是否是mmapped，如果不是，就进行各种判断防止部分针对free操作的攻击。

    • 判断要free的chunk是否是top chunk，如果是，则抛出错误(“double free or corruption (top)”)
    • 判断next chunk在内存中是否在arean的范围内，如果不是，则抛出错误(“double free or corruption (out)”)
    • 判断next chunk的P标志是否为真，如果不是，则抛出错误(“double free or corruption (!prev)”)
    • 判断next chunk的大小是否正常范围之间，如果不是，则抛出错误(“free(): invalid next size (normal)”)

    normal free error

    然后将与free的chunk与其相邻的freed chunk进行合并，合并了之后将它插入到unsorted bin中。

    normal free

参考