一、堆的分析：

通过系统调用brk和mmap实现malloc内存分配:

thread有个arena空间，可以申请chunk

arena的个数是跟系统中处理器核心个数相关的：

1
2
3
4

For 32 bit systems:
     Number of arena = 2 * number of cores + 1.
For 64 bit systems:
     Number of arena = 8 * number of cores + 1.

多Arena的管理，可能就会有阻塞，资源的竞争关系

3种数据结构:

1、heap_info(Heap Header)

因为一个thread arena（注意：不包含main thread）可以包含多个heaps，所以为了便于管理，就给每个heap分配一个heap header，在当前heap不够用的时候，malloc会通过系统调用mmap申请新的堆空间，新的堆空间会被添加到当前thread arena中，便于管理。

2、malloc_state: 即Arena Header，每个thread只含有一个Arena Header。Arena Header包含bins的信息、top chunk以及最后一个remainder chunk等(这些概念会在后文详细介绍):

3、malloc_chunk: 即Chunk Header，一个heap被分为多个chunk，至于每个chunk的大小，这是根据用户的请求决定的，也就是说用户调用malloc(size)传递的size参数“就是”chunk的大小(这里给“就是”加上引号，说明这种表示并不准确，但是为了方便理解就暂时这么描述了，详细说明见后文)。每个chunk都由一个结构体malloc_chunk表示：

5.1 隐式链表技术

• 堆内存要求每个chunk大小必须是8的整数倍，因此chunk size的后3位是无效的，为了充分利用内存，堆管理器将这3个比特位用作chunk的标志位，典型的是将第0位的比特位标记为chunk是否已经被分配。

这样的设计很巧妙，因为我们只要获取了一个指向chunk size的指针，就能知道该chunk的大小，即确定了此chunk的边界，且利用chunk size的第0比特位还能知道该chunk是否已经分配，这样就成功地将各个chunk区分开来。注意在allocated chunk中padding部分主要是用于地址对齐的(也可用于对付外部碎片)，即让整个chunk的大小为8的整数倍。

通过上面的设计，我们就能将整个堆内存组织成一个连续的已分配或未分配chunk序列:

这是分配和未分配的情况。

上面的这种结构就叫做隐式链表。该链表隐式地由每个chunk的size字段链接起来，在进行分配操作的时候，堆内存管理器可以通过遍历整个堆内存的chunk，分析每个chunk的size字段，进而找到合适的chunk

这种隐式链表效率其实是相当低的，特别是在内存回收方面，它难以进行相邻多个free chunk的合并操作。我们知道，如果只对free chunk进行分割，而不进行合并的话，就会产生大量小的、无法继续使用的内部碎片，直至整个内存消耗殆尽。因此堆内存管理器设计了带边界标记的chunk合并技术。

1.带边界标记的合并技术

试想如下场景：假设我们要释放的chunk为P，它紧邻的前一个chunk为FD，紧邻的后一个chunk为BK，且BK与FD都为free chunk。将P于BK合并在一起是很容易的，因为可以通过P的size字段轻松定位到BK的开始位置，进而获取BK的size等等，但是将P于FD合并却很难，我们必须从头遍历整个堆，找到FD，然后加以合并，这就意味着每次进行chunk释放操作消耗的时间与堆的大小成线性关系。为了解决这个问题，Knuth提出了一种聪明而通用的技术——边界标记。

Knuth在每个chunk的最后添加了一个脚部(Footer)，它就是该chunk 头部(header)的一个副本，我们称之为边界标记：（这个副本就是我们所讲的父节点，完美构成回溯链表）

a:用来标志是否分配，b:用来标志是否有前一个chunk

2.再进化——支持多线程

随着技术的发展，特别是堆内存管理器添加对多线程的支持，前述的chunk格式已经难以满足需求，比如，我们需要标志位来标记当前chunk是否属于非主线程即thread arena，以及该chunk由mmap得来还是通过brk实现等等。但此时chunk size只剩下一个比特位未使用了，怎么办呢？这需要对chunk格式进行大手术！

首先思考：是否有必要同时保存当前chunk和前一个chunk的已分配/空闲标记位？答案是否定的，因为我们只需要保存前一个chunk的分配标志位就可以了，至于当前chunk的分配标志位，可以通过查询下一个chunk的size字段得到。那么size字段中剩下的两个比特位就可以用于满足多线程的标志需求了：

再进一步，发现没必要保存chunk size的副本，也就是说Footer的作用并不大，但是如果前一个chunk是free的话，在合并的时候我们又需要知道前一个chunk的大小，怎么办呢？将Footer从尾部移到首部，同时其不再保存当前chunk的size，而是前一个free chunk的size不就行了。同样的，为了提高内存利用率，如果前一个chunk是allocated chunk的话，这个Footer就作为allocated chunk的payload或padding的一部分，结构图如下：

成功变成了双向链表。

那么这个结构体就很好理解了呢

• 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 时挨个遍历。

5.2 Top Chunk（应急消防员）

当一个chunk处于一个arena的最顶部(即最高内存地址处)的时候，就称之为top chunk。该chunk并不属于任何bin，而是在系统当前的所有free chunk(无论那种bin)都无法满足用户请求的内存大小的时候，将此chunk当做一个应急消防员，分配给用户使用。如果top chunk的大小比用户请求的大小要大的话，就将该top chunk分作两部分：1）用户请求的chunk；2）剩余的部分成为新的top chunk。否则，就需要扩展heap或分配新的heap了——在main arena中通过sbrk扩展heap，而在thread arena中通过mmap分配新的heap。

5.3 Last Remainder Chunk

要想理解此chunk就必须先理解glibc malloc中的bin机制。如果你已经看了第二部分文章，那么下面的原理就很好理解了，否则建议你先阅读第二部分文章。对于Last remainder chunk，我们主要有两个问题：1)它是怎么产生的；2)它的作用是什么？

先回答第一个问题。还记得第二部分文章中对small bin的malloc机制的介绍么？当用户请求的是一个small chunk，且该请求无法被small bin、unsorted bin满足的时候，就通过binmaps遍历bin查找最合适的chunk，如果该chunk有剩余部分的话，就将该剩余部分变成一个新的chunk加入到unsorted bin中，另外，再将该新的chunk变成新的last remainder chunk。

然后回答第二个问题。此类型的chunk用于提高连续malloc(small chunk)的效率，主要是提高内存分配的局部性。那么具体是怎么提高局部性的呢？举例说明。当用户请求一个small chunk，且该请求无法被small bin满足，那么就转而交由unsorted bin处理。同时，假设当前unsorted bin中只有一个chunk的话——就是last remainder chunk，那么就将该chunk分成两部分：前者分配给用户，剩下的部分放到unsorted bin中，并成为新的last remainder chunk。这样就保证了连续malloc(small chunk)中，各个small chunk在内存分布中是相邻的，即提高了内存分配的局部性。

1 bin介绍

如前文所述，bin是一种记录free chunk的链表数据结构。系统针对不同大小的free chunk，将bin分为了4类：1) Fast bin; 2) Unsorted bin; 3) Small bin; 4) Large bin。

在glibc中用于记录bin的数据结构有两种，分别如下所示：

fastbinsY: 这是一个数组，用于记录所有的fast bins；

bins: 这也是一个数组，用于记录除fast bins之外的所有bins。事实上，一共有126个bins，分别是：

bin 1 为unsorted bin;

bin 2 到63为small bin;

bin 64到126为large bin。

其中具体数据结构定义如下：

Fast bin

0x20-0x80

chunk size 表示malloc_chunk的实际整体大小；

chunk unused size 相对于chunk而言，实际可用的大小总是比实际整体大小少16字节。

内存分配和释放的过程中，fast bin 是所有bin中操作速度最快的。继续学习fast bin的一些特性：

1、fast bin的个数——10个

2、每个fast bin 都是一个单链表（只是用fd指针）。因为在fast bin中无论是添加还是移除fast chunk，都是对“链表尾”进行操作，而不会对某个中间的fast chunk进行操作。更具体点就是LIFO（后进先出）算法，删除操作（malloc内存）就是在链尾进行操作。

3、chunk size：10个fast bin 中所包含的fast chunk size 是按照步进8字节排序的，第一个fast bin中所有fast chunk size 均为16字节，第二个fast bin为24字节，以此类推。在进行malloc时，最大的fast chunk size 被设置为80字节(chunk unused size 为64个字节 )，因此默认情况下大小为16到80字节的chunk被分类到fast chunk。

4、不会对free chunk进行合并操作。鉴于设计fast bin的初衷是快速进行内存的分配和管理，所以fastbin的chunk的P（未使用标志位）总是设置为1，这样就不会合并相邻的free chunk ，虽然有内存碎片产生，但是瑕不掩瑜。

5、malloc（fast bin）操作：用户通过malloc请求的大小属于fast chunk 的大小范围（用户请求+16 = 实际内存chunk size）。初始化时fastbin支持的最大内存大小以及所有fastbin链表都是空的，所以malloc时，不会交由fastbin处理，而是向下传递给small bin处理，如果small bin 也为空就交给unsorted 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

/* Maximum size of memory handled in fastbins.  */

static INTERNAL_SIZE_T global_max_fast;

 

/* offset 2 to use otherwise unindexable first 2 bins */

/*这里SIZE_SZ就是sizeof(size_t)，在32位系统为4，64位为8，fastbin_index就是根据要malloc的size来快速计算该size应该属于哪一个fast bin，即该fast bin的索引。因为fast bin中chunk是从16字节开始的，所有这里以8字节为单位(32位系统为例)有减2*8 = 16的操作！*/

\#define fastbin_index(sz) \

  ((((unsigned int) (sz)) >> (SIZE_SZ == 8 ? 4 : 3)) - 2)

 

 

/* The maximum fastbin request size we support */

\#define MAX_FAST_SIZE     (80 * SIZE_SZ / 4)

 

\#define NFASTBINS  (fastbin_index (request2size (MAX_FAST_SIZE)) + 1)

第一次调用malloc（fastbin）—->_int_malloc—–>small bin —->malloc_consolidate(对malloc_state结构体进行初始化)

malloc_consolidate函数主要完成以下几个功能：

a. 首先判断当前malloc_state结构体中的fast bin是否为空，如果为空就说明整个malloc_state都没有完成初始化，需要对malloc_state进行初始化。

b. malloc_state的初始化操作由函数malloc_init_state(av)完成，该函数先初始化除fast bin之外的所有的bins(构建双链表，详情见后文small bins介绍)，再初始化fast bins。

然后当再次执行malloc(fast chunk)函数的时候，此时fast bin相关数据不为空了，就开始使用fast bin(见下面代码中的※1部分)：

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

static void *

_int_malloc (mstate av, size_t bytes)

{

  ……

  /*

     If the size qualifies as a fastbin, first check corresponding bin.

     This code is safe to execute even if av is not yet initialized, so we

     can try it without checking, which saves some time on this fast path.

   */

   //第一次执行malloc(fast chunk)时这里判断为false，因为此时get_max_fast ()为0

   if ((unsigned long) (nb) <= (unsigned long) (get_max_fast ()))

    {

  ※1  idx = fastbin_index (nb);

      mfastbinptr *fb = &fastbin (av, idx);

      mchunkptr pp = *fb;

      do

        {

          victim = pp;

          if (victim == NULL)

            break;

        }

   ※2 while ((pp = catomic_compare_and_exchange_val_acq (fb, victim->fd, victim))!= victim);

      if (victim != 0)

        {

          if (__builtin_expect (fastbin_index (chunksize (victim)) != idx, 0))

            {

              errstr = "malloc(): memory corruption (fast)";

            errout:

              malloc_printerr (check_action, errstr, chunk2mem (victim));

              return NULL;

            }

          check_remalloced_chunk (av, victim, nb);

          void *p = chunk2mem (victim);

          alloc_perturb (p, bytes);

          return p;

        }

    }

得到第一个来自于fast bin的chunk之后，系统就将该chunk从对应的fast bin中移除，并将其地址返回给用户，见上面代码※2处

free（fast chunk）操作：

这个操作简单，主要分为两步：

先通过chunksize函数根据传入的地址指针获取该指针对应的chunk的大小，然后根据这个chunk大小获取该chunk所属的fast_bin，然后再将此chunk添加到该fastbin的链尾即可，整个操作都是在int_free函数中完成的，所以相当于fast_bin就是存储free chunk的地方，用完的chunk就回到这里。

这里很明显，越往后的话，chunk块的大小越大，所以阶梯型利用，选择和合适的chunk事半功倍，也不浪费。

Unsorted bin（chunk缓冲区）

0x80-

当释放较小或较大的chunk的时候，如果系统没有将它们添加到对应的bins中(为什么，在什么情况下会发生这种事情呢？详情见后文)，系统就将这些chunk添加到unsorted bin中。为什么要这么做呢？这主要是为了让“glibc malloc机制”能够有第二次机会重新利用最近释放的chunk(第一次机会就是fast bin机制)。利用unsorted bin，可以加快内存的分配和释放操作，因为整个操作都不再需要花费额外的时间去查找合适的bin了。

Unsorted bin的特性如下：

1) unsorted bin的个数： 1个。unsorted bin是一个由free chunks组成的循环双链表。

2) Chunk size: 在unsorted bin中，对chunk的大小并没有限制，任何大小的chunk都可以归属到unsorted bin中。这就是前言说的特例了，不过特例并非仅仅这一个，后文会介绍。

Small bin

0x20-0x3f0

凡是小于512字节的chunk称之为small chunk，small bin就是用于管理small chunk的。就内存的分配和释放的速度而言，small bin比larger bin快，但是比fast bin慢。

Small bin的特性如下：

1) small bin个数：62个。每个small bin也是一个由对应free chunk组成的循环双链表。同时Small bin采用FIFO(先入先出)算法：内存释放操作就将新释放的chunk添加到链表的front end(前端)，分配操作就从链表的rear end(尾端)中获取chunk。队列的形式的利用技巧。

2) chunk size: 同一个small bin中所有chunk大小是一样的，且第一个small bin中chunk大小为16字节，后续每个small bin中chunk的大小依次增加8字节，即最后一个small bin的chunk为16 + 62 * 8 = 512字节。

3) 合并操作：相邻的free chunk需要进行合并操作，即合并成一个大的free chunk。具体操作见下文free(small chunk)介绍。

4) malloc(small chunk)操作：类似于fast bins，最初所有的small bin都是空的，因此在对这些small bin完成初始化之前，即使用户请求的内存大小属于small chunk也不会交由small bin进行处理，而是交由unsorted bin处理，如果unsorted bin也不能处理的话，glibc malloc就依次遍历后续的所有bins，找出第一个满足要求的bin，如果所有的bin都不满足的话，就转而使用top chunk，如果top chunk大小不够，那么就扩充top chunk，这样就一定能满足需求了(还记得上一篇文章中在Top Chunk中留下的问题么？答案就在这里)。注意遍历后续bins以及之后的操作同样被large bin所使用，因此，将这部分内容放到large bin的malloc操作中加以介绍。

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

malloc_init_state (mstate av)

{

  int i;

  mbinptr bin;

 

  /* Establish circular links for normal bins */

  for (i = 1; i < NBINS; ++i)

    {

      bin = bin_at (av, i);

      bin->fd = bin->bk = bin;

}

……

}

注意在malloc源码中，将bins数组中的第一个成员索引值设置为了1，而不是我们常用的0(在bin_at宏中，自动将i进行了减1处理…)。从上面代码可以看出在初始化的时候glibc malloc将所有bin的指针都指向了自己——这就代表这些bin都是空的。

过后，当再次调用malloc(small chunk)的时候，如果该chunk size对应的small bin不为空，就从该small bin链表中取得small chunk，否则就需要交给unsorted bin及之后的逻辑来处理了。

5）free（small chunk）：当释放small chunk时，先检查该chunk是否为free，是的话就合并操作，将这些chunks合并成新的chunk。然后将他们从small bin中移除，最后将新的chunk添加到unsorted bin中。

5 Large bin

0x400-

大于512字节的chunk称之为large chunk，large bin就是用于管理这些large chunk的。

Large bin的特性如下：

1）large的数量:63个，类似于small bin，只是需要注意两点：一个是

chunk的大小可以不一样，但必须处于给定的每个范围，二是large chunk可以添加、删除在large bin的任何一个位置。

在这63个large bins中，前32个large bin依次以64字节步长为间隔，即第一个large bin中chunk size为512~575字节，第二个large bin中chunk size为576 ~ 639字节。紧随其后的16个large bin依次以512字节步长为间隔；之后的8个bin以步长4096为间隔；再之后的4个bin以32768字节为间隔；之后的2个bin以262144字节为间隔；剩下的chunk就放在最后一个large bin中。

鉴于同一个large bin中每个chunk的大小不一定相同，因此为了加快内存分配和释放的速度，就将同一个large bin中的所有chunk按照chunk size进行从大到小的排列：最大的chunk放在链表的front end，最小的chunk放在rear end。

2) 合并操作：类似于small bin。

3）malloc（large chunk）操作：

初始化时，一开始先看是否大于front end的size，如果大于，那么继续往后查看large chunk是否有满足需求的chunk，不过需要注意的是鉴于bin的个数较多(不同bin中的chunk极有可能在不同的内存页中)，如果按照上一段中介绍的方法进行遍历的话(即遍历每个bin中的chunk)，就可能会发生多次内存页中断操作，进而严重影响检索速度，所以glibc malloc设计了Binmap结构体来帮助提高bin-by-bin检索的速度。Binmap记录了各个bin中是否为空，通过bitmap可以避免检索一些空的bin。如果通过binmap找到了下一个非空的large bin的话，就按照上一段中的方法分配chunk，否则就使用top chunk来分配合适的内存。

如果小于，就从rear end开始遍历该large bin，找到第一个size相等或接近的chunk，分配给用户。如果该chunk大于用户请求的size的话，就将该chunk拆分为两个chunk：前者返回给用户，且size等同于用户请求的size；剩余的部分做为一个新的chunk添加到unsorted bin中。

Free（large chunk）：

了解上面的知识之后，结合下图5-1，就不难理解各类bins的处理逻辑了：

*当一个chunk处于使用状态时，那么下一个chunk的pre_size是无效的，可以被当前的这个chunk所使用~

深入理解Ptmalloc2

unlink:

1、出现在malloc时，一般是在large bin当中有符合要求的chunk要取出来时。

2、Free，这里有前向合并(除了top chunk)和后向合并

3、malloc_consolidate，后向合并和前向合并（除了top chunk）

4、realloc，前向扩展（除了top chunk）

只有不是fast bin的情况下才会触发unlink，是为了避免heap中有太多零碎的内存块，合并之后可以用来应对更大的内存块请求，合并的顺序为

1、先考虑物理低地址空闲块请求

2、后考虑物理高地址空闲块请求

合并后的chunk指向合并的chunk的低地址

tcache：

新的结构体：tcache_entry 和 tcache_perthread_struct类似于fastbin但是又有不同之处。

tcathe的优先级比fastbin要高。

堆溢出：

写入的字节数超过堆块本身可使用的字节数（会有保护机制），导致数据溢出，覆盖到物理相邻的高地址的下一个堆块。

不难发现，堆溢出漏洞发生的基本前提是

• 程序向堆上写入数据。
• 写入的数据大小没有被良好地控制。

malloc：单纯分配空间

calloc：分配后会自动清空

realloc：以上二者的结合

1
2
3
4
5
6
7
8
9

#include <stdio.h>

int main(void) 
{
  char *chunk,*chunk1;
  chunk=malloc(16);
  chunk1=realloc(chunk,32);
  return 0;
}

举个例子：

• 当 realloc(ptr,size) 的 size 不等于 ptr 的 size 时
  • 如果申请 size > 原来 size
    • 如果 chunk 与 top chunk 相邻，直接扩展这个 chunk 到新 size 大小
    • 如果 chunk 与 top chunk 不相邻，相当于 free(ptr),malloc(new_size)
  • 如果申请 size < 原来 size
    • 如果相差不足以容得下一个最小 chunk(64 位下 32 个字节，32 位下 16 个字节)，则保持不变
    • 如果相差可以容得下一个最小 chunk，则切割原 chunk 为两部分，free 掉后一部分(因为还可以再使用)
• 当 realloc(ptr,size) 的 size 等于 0 时，相当于 free(ptr)
• 当 realloc(ptr,size) 的 size 等于 ptr 的 size，不进行任何操作

漏洞函数：

输入：

gets，直接读取一行，忽略’\x00’

scanf

vscanf

输出：

sprinf

字符串：

strcpy，字符串复制，遇到’\x00截止’（数据+’\x00’+数据可以绕过）

strcat，字符串拼接，遇到’\x00截止’（数据+’\x00’+数据可以绕过）

bcopy，bcopy()与memcpy()一样都是用来拷贝src 所指的内存内容前n 个字节到dest 所指的地址，不过参数src 与dest 在传给函数时是相反的位置。(bcopy() 不检查内存（字符串）中的空字节 NULL)

strlen(计算字符串长度时不计算’\x00’)，所以会出现在strcpy函数中，这又叫null-off-by-one，覆盖低字节为\x00