堆chunk介绍及源码剖析

堆是程序虚拟地址空间的一块连续的线性区域，它由低地址向高地址方向增长。在程序运行过程中，堆可以提供动态分配的内存，允许程序申请大小未知的内存。管理堆的那部分程序为堆管理器。

堆管理器在用户程序与内核中间：

响应用户的申请内存请求，向操作系统申请内存，然后将其返回给用户程序。同时，为了保持内存管理的高效性，内核一般都会预先分配很大的一块连续的内存，然后让堆管理器通过某种算法管理这块内存。只有当出现了堆空间不足的情况，堆管理器才会再次与操作系统进行交互。
管理用户所释放的内存。一般来说，用户释放的内存并不是直接返还给操作系统的，而是由堆管理器进行管理。这些释放的内存可以来响应用户新申请的内存的请求。

linux早期的堆分配与回收按 Doug lea 实现，在并行处理多个线程时，会共享进程的堆空间，有很大的不安全性，为了加强安全性，一个线程使用堆时，会对堆空间进行加锁，与此同时，加锁会导致其它线程无法使用堆，降低了内存分配和回收的高效性，并且，如果存在多线程使用时，没能精确控制，也可能影响内存分配与回收的正确性。Wolfram Gloger 在 Doug Lea的基础上进行改进，支持多线程，且安全性提高。这个堆分配器就是ptmalloc。在glibc-2.3.x以后的glibc版本，glibc中集成了ptmalloc2。

目前，linux标准发行版中使用的堆分配器是glibc中的堆分配器：ptmalloc2。其主要是通过malloc ， free 函数来申请跟释放堆块。

在内存分配与使用的过程中，Linux有这样的内存管理，只有当真正访问一个地址的时候，操作系统才会建立虚拟页面与物理页面的映射关系。因此我们可知，虽然操作系统已经给用户程序分配了一大块内存，但是这块内存在用户程序还未使用到的情况下，这块内存还只是虚拟内存，只有用户程序使用到该内存的时候，系统才会真正分配物理页面给用户使用。

上述不仅讲了堆，还涉及了堆管理器。

重点关注的是ptmalloc

堆的基本操作

主要介绍

基本的堆操作，包括堆的分配，回收，堆分配背后的系统调用
介绍堆目前的多线程支持。

malloc

glibc的 malloc.c 中 malloc函数的说明如下：

/*
  malloc(size_t n)
  Returns a pointer to a newly allocated chunk of at least n bytes, or null
  if no space is available. Additionally, on failure, errno is
  set to ENOMEM on ANSI C systems.
  If n is zero, malloc returns a minumum-sized chunk. (The minimum
  size is 16 bytes on most 32bit systems, and 24 or 32 bytes on 64bit
  systems.)  On most systems, size_t is an unsigned type, so calls
  with negative arguments are interpreted as requests for huge amounts
  of space, which will often fail. The maximum supported value of n
  differs across systems, but is in all cases less than the maximum
  representable value of a size_t.
*/

可以看出malloc申请堆空间后会返回一个对应大小的内存块的指针，并且，该函数介绍了还会对一些异常情况进行处理。

当 n=0 时，返回当前系统允许的堆的最小内存块。
当 n 为负数时，由于在大多数系统上，size_t 是无符号数（这一点非常重要），所以程序就会申请很大的内存空间，但通常来说都会失败，因为系统没有那么多的内存可以分配。

free

glibc中的malloc.c中free的说明如下：

/*
      free(void* p)
      Releases the chunk of memory pointed to by p, that had been previously
      allocated using malloc or a related routine such as realloc.
      It has no effect if p is null. It can have arbitrary (i.e., bad!)
      effects if p has already been freed.
      Unless disabled (using mallopt), freeing very large spaces will
      when possible, automatically trigger operations that give
      back unused memory to the system, thus reducing program footprint.
    */

可以看出free函数会释放指针p所指向的堆空间，该堆空间可能是通过malloc函数得到的，也有可能是通过相关的函数realloc函数得到的，且，该函数也会对异常情况进行处理。

当 p 为空指针时，函数不执行任何操作。
当 p 已经被释放之后，再次释放会出现别的效果，这其实就是 double free。
除了被禁用 (mallopt) 的情况下，当释放很大的内存空间时，程序会将这些内存空间还给系统，以便于减小程序所使用的内存空间。

内存分配背后的系统调用

无论是malloc 函数还是free 函数，用户动态申请和释放堆块时，都经常使用，但它们并不是真正与系统交互的函数，这些函数背后的系统调用主要是(s)brk函数以及mmap ,munmap函数。如下图，主要考虑的是对堆进行申请内存块的操作。

(s)brk函数：

对于堆进行的操作，操作系统提供了brk函数。，glibc库提供了sbrk函数，用户可以通过增加brk的大小来向操作系统申请内存。

初始状态时，堆的起始地址是start_brk以及堆的当前末尾brk指向同一地址。根据ASLR的开启与关闭，两者的具体位置会有所不同。

不开启 ASLR 保护时，start_brk 以及 brk 会指向 data/bss 段的结尾。
开启 ASLR 保护时，start_brk 以及 brk 也会指向同一位置，只是这个位置是在 data/bss 段结尾后的随机偏移处。

一种是使用状态malloced，另一种是释放状态free。

处于使用状态下的堆的结构如下：

堆头与数据区。

处于释放状态下的堆：

堆头以及下面的指针、未被使用的区域

可以看到申请的时候直接从topchunk里切出来一块，图中申请了六个，当申请第七个的时候，就会从剩下的topchunk中切

注意：切割topchunk是不会产生last remainder chunk的

比如现在要释放一个堆块，那么就要重新申请一个堆块A，就是从原先的里面切，形成两部分，一个是last remainder chunk。

tache是从glibc-2.24之后引进，2.26就有了，一般说glibc-2.27。

剖析chunk的结构：

1：

prev_size

顾名思义：prev_size，先前的大小。是记录前一个堆块的大小，若前一个堆块是处于释放状态，那么该区域启动，存储的是前一个释放的堆块的大小；如果前一个堆块是处于使用状态，那么该区域不启用，被用来当作前一个堆块的数据区域存储数据。我们如何判断前一个堆块是否处于使用状态，就看 P，P为0，则前一个堆块是释放状态；P为1，则前一个堆块是使用状态。

2：

size

size是记录自己堆块的大小，后三个字节备用来做标志，也就是 A M P。prev_size和size组成的堆头chunk head。

3：

三个标志：A M P

p记录的是前一个堆块的是处于释放还是使用的状态， chunk会根据这个标志来进行前后合并，当该chunk是第一个被分配的内存块，前边是一个非法地址，若设置0，则合并的时候会把前边的非法地址给合并，因此第一个chunk的P会默认设置为1。

4：

fd pointer（fd指针）

fd pointer只存在于空闲的chunk中，指向下一个空闲的chunk。

5：

bk pointer

与fd 相反。

6：

fd_nextsize

7：

bk_nextsize

一般空闲的large chunk在fd的遍历顺序中，按照由大到小的顺序排列。这样可以做到避免在寻找合适的chunk时挨个便历。

bk_nextsize和fd_nextsize是large bin特有的，在large bin中才会出现这俩个指针。

fast bins

64位下fast bin默认最大值为80，mallopt（1，0）就是修改fast bin的一个大小，改成了0。也就是当被free的堆块是0的时候才会进入fast bin。相当于关闭fast bin。

申请的三个堆块都是0x10大小。

直接释放了两个相邻的堆块，为什么直接释放相邻的两个堆块呢，因为有fastbins存在的原因，物理相邻的两个free堆块是不会合并的，是为了更高效的一个处理机制，比如系统要频繁的进行一个小的内存的申请与释放的话，那么fastbins的存在就会大大的提高效率，因为不需要频繁的切割合并这样的操作。从上图可以看出fastbins从20字节到80字节（64位程序)，free的堆块直接进入fastbins而不是进行合并。

在fastbins里面，它的p字节是固定为1的，就算是处于释放状态，也是固定为1，不进行合并，size大小为20，P为1，所以为21。

最后一位P是1。前边讲过这个规则的。

只启动了fd指针。

unsorted bin

关闭fast bins

放进unsorted bin 里边去

两个free chunk关掉fast bins之后会进行合并，大小变为0x40，最终会放到smallbins里区，但不会直接放进去，会先进unsortedbin进行缓冲。如果我在此时向程序申请一个比0x40还大的堆块，那俩个合并的chunk才会回归到所属的bin。

unsortedbin是一个双向列表，fd bk 都启动。

smallbins

释放了三个堆块

放进smallbins

形成循环双向链表。

large bins

和smallbins很像，也是FIFO结构，循环双向链表。但并不是和smallbins一样每个链表下都放着大小相同的堆块，它是一个大小区域。

可以看到释放了三个堆块，大小分别为0x410，0x430，0x450。

他们都被放在了unsorted bin。虽然他们最终是应该被放在large bin的，但先进unsorted bin 进行缓冲。

最后进入large bin里，可以看到前俩个是直接一并归到了0x400的链表里面去，但是他俩大小是不相同的，smallbin是存的相同的。

fd ,bk; fd_nextsize ,bk_nextsize开启。

指向关系如下图：

#######################################

malloc

简单来说就是当一个用户发起一个malloc请求，会先去fastbins里0x20这个链表里找有没有空闲的堆块，如有直接返回，如果没有就往smallbin里找，再没有就往large里找，有的话就会切一块适合的大小然后返回，剩下的丢进last remainder chunk里去，为什么要切，因为large bin里的链表空间很大，一般要超过用户需求的空间。如果到largebin了还没有空闲的，那就会去topchunk里去切，要是topchunk被用的不够再申请空间而用户又要申请空间时，该topchunk会被释放掉，堆分配器会再分配一个大的topchunk来，形成一个新的topchunk；如果不是因为topchunk不够分配了，而是单次申请太大超过了一个mmap阈值，有可能会考虑mmap分配。mmap是另一个分配，mmap分配是不适用这些bin的，它释放的话是直接归还操作系统。