堆的管理策略取决于各操作系统的堆管理器实现。之前看Windows、Linux,发现他们是存在一些区别的。虽然总的策略类似但在一些细微实现上有很大的区别。

所以本文就着重介绍一下Linux/Android的堆管理策略吧,一些个人理解就想到什么写什么了。网上这方面的内容也很多。推荐下面两个:

概述

在以前的博客中有介绍到,对于Android的进程来说,每个进程内部都是一个大的虚拟地址空间。对于已经划分的区域,均会创建一个vm_area_struct结构并将其链接到进程维护的vm_area_struct链表当中。vm_area_struct结构会包含这块区域的起始位置、next指针,flag等等。而我们的堆、栈就属于这样的一个vm_area_struct结构。

堆的初始化

堆会在程序第一次请求分配内存的时候初始化,即第一次调用malloc的时候。

我们在开发或者配置系统环境的过程中,经常能看到一些关于堆最小值、最大值的参数,这些就会在堆初始化的过程中进行读取。

堆的拓展

当堆第一次创建完成后,它的范围大小还未达到最大。当我们发现目前区域的剩余内存不够分时就需要再拓展我们的堆,直至它达到maximum。

1
2
3
4
5
#include <unistd.h>

int brk(void *end_data_segment);

void *sbrk(ptrdiff_t increment);

系统提供了两个方法:

  • brk:增大堆边界到指定位置
  • sbrk:增大指定数

他们的描述如下:

brk sets the end of the data segment to the value specified by end_data_segment, when that value is reasonable, the system does have enough memory and the process does not exceed its max data size (see setrlimit(2)).

sbrk increments the program’s data space by increment bytes. sbrk isn’t a system call, it is just a C library wrapper. Calling sbrk with an increment of 0 can be used to find the current location of the program break

brk为系统调用,sbrk为brk的子集,就是它的二次封装。当区域不够时,堆会调用sbrk去增大

超大内存块的内配

堆分配内存其实是从操作系统中割下一块区域给自己用,等到合适的实际再返回给操作系统。那么以正常的开发思维来看,在堆管理器中建立缓存是非常有必要的,这样能避免出现频繁的系统IO。

但对于超大内存块来说,其实就没有太大的必要缓存它了,因为缓存和回收再利用的成本其实非常大。试想下面这情况:

  1. 内存1000,此时分配了900的超大内存
  2. 该超大内存被释放
  3. 程序接下来的所有操作均为小内存分配,也就是10、20byte的来。
  4. 那么这剩余的800多byte就被白白浪费了

所以Linux的堆管理器在应对超大内存块时,都会直接使用mmap在off-heap区域分配一块大内存,一旦释放,则直接unmmap将其归还给系统。

超大内存块的判定根据系统位数和具体的堆管理决定,32位一般是128KB起

Very large allocation requests get special treatment in the heap manager. These large chunks are allocated off-heap using a direct call to mmap, and this fact is marked using a flag in the chunk metadata. When these huge allocations are later returned to the heap manager via a call to free, the heap manager releases the entire mmaped region back to the system via munmap.

By default this threshold is 128KB up to 512KB on 32-bit systems and 32MB on 64-bit systems, however this threshold can also dynamically increase if the heap manager detects that these large allocations are being used transiently.

小内存块的分配(相对于大内存块的概念)

堆分配的单位被称为块chunk。在堆第一次初始化后,堆中只有一个topChunk。之后的每次切割都会从中切出一部分,剩余的部分继续当成topChunk

首先介绍Linux堆的几类chunk List。除了unsortbin无size大小限制外,其余的3个都会有:

  • fastbin: 单向链表,无合并操作(除非空闲堆块数量超过阈值,才会合并后放入UnsortBin)。对应16~88 bytes的堆块
  • unsortbin:双向链表,处于binList的第0位。内部存放的堆块无大小限制
  • smallbin:双向链表,处于binList的第1~62位,总共62个块。对应大小小于512 bytes的堆块
  • largebin:双向链表,处于binList的第63~125位,总共63个块。对应大小大于512 bytes的堆块

上面提到了一个binList,其实就是unsortbin,smallbin,largebin的管理类,通过它就可以快速定位到指定的bin区域,它与fastbin同级。

图解就是:

1
2
3
4
5
fastbin

unsortbin
binList -> smallbin
largebin

堆块的合并

上面提到了堆块的合并,这是啥呢?

  • 堆释放chunkB时发现它物理相连的chunkA也处于空闲状态,就会把自己和A合并从而构建一个新的大块,此为向后合并(这名字有点怪,其实就是让A的范围包含B,所以叫向后)
  • 如果释放chunkB时发现它物理相连的chunkC也处于空闲状态,就会把自己和C合并从而构建一个新的大块,此为向前合并。
  • 如果free(ChunkA)时发现它和topChunk物理相邻,那么将其合并到topChunk中

Chunk的格式

Chunk格式

从上到下可以看到,一个空闲堆块的结构布局依次为prev_size, chunkSize & flag, fd pointer, bk pointer, fd_nextsize, bk_nextsize, content。

一个非空闲堆块的结构布局就很简单了,PREV_SIZE, chunkSize & flag, content

  • 对于unsort bin, small bin而言:不存在fd_next_size, bk_nextsize

  • chunkSize后面的flag非常重要,他有三个标志位:

    • A用于表示分配的arena是main arena还是其他arena(在本文的下个内容介绍)
    • M用于表示该堆块是否由mmap分配,如果是,那么释放的时候该chunk会走unmmap的途径
    • P用于表示前一个堆块是否处于使用状态,用于判断是否需要合并
  • PREV_SIZE,chunkSize&flag这些在32位的系统上为4字节,16为系统为8字节

  • 使用malloc返回的指针为chunkSize&flag结束的位置,即fd的开始。且malloc(8)得到的实际大小会再额外加上PREV_SIZE和CHUNK_SIZE占用的大小

  • malloc存在字节对齐,比如1024byte的数据在32位上刚好是8位对齐,可以直接分配。那如果分配1028的数据该怎么办呢?

    • 答案是分配1024个字节,剩余的4个字节占用下个堆块的PREV_SIZE部分
  • 使用calloc分配内存块时,它会clear掉content区域的内容,这样就不会造成数据的重复使用了

  • 使用malloc分配内存块时,会直接返回指向该chunk的指针,并不会清除该chunk的内容。那么就可能造成数据的反复使用。

    • 如:A=malloc(8).
    • setTxt(A).
    • free(A).
    • B = malloc(8). print getTxt(B)
    • 会发现打印的结果就是A设置的内容

What is arena

这其实是为了应对多线程。多线程的资源竞争、同步、锁在任何情况都是一个大问题。如果堆管理没有应对好,那么面对的会是程序崩溃。因此Linux的堆管理器ptmalloc使用了arena的概念。

Each arena is essentially an entirely different heap that manages its own chunk allocation and free bins completely separately. Each arena still serializes access to its own internal data structures with a mutex, but threads can safely perform heap operations without stalling each other so long as they are interacting with different arenas.

即:每个arena都是一个完全独立的堆,拥有并管理自己的chunk分配和free。这在一定程度上是能应对多线程并发的。

只不过也正因为每个arena都有自己的堆,因此操作系统一定需要堆它的数量做限制,不然其他程序还活不活了?arena的数量上限在32位的系统上是2倍CPU核,64位上时8倍。

So the process is :

  • 创建Main arena
  • 创建线程A,发现arena数量未达上限,则创建arenaA
  • 如果此时发现arena数量达到上限,那么便会尝试去arenaList,从而锁定一个arena去使用(就进原则)
  • 如果遍历完了都没找到,那就挂起,等待叫醒

分配堆块的流程

以fastbin举例,smallBin和largeBin是类似的

创建30byte的堆块:

  1. 属于fastbin,尝试分配
  2. 【情况一】此时系统还未初始化fastbin这个链表,故无法分配
  3. 往后传递给smallBin尝试分配,发现也未初始化,说明此时的binList也没初始化。故程序会调用Init函数初始化binList和fastbin,之后就可以在fastbin中分配数据了
  4. 【情况二】如果此时存在fastbin链表,那么根据堆块大小从前到后依次寻找到一个最合适的chunk去分配。如果刚好够,直接取下来即可。如果有剩余,那么就把剩余的chunk放入unsortChunk
  5. 【情况三】fastbin链表遍历完成,但未发现一个合适的chunk,将进入unsortChunk的遍历过程。
  6. 【情况四】unsortBin也搞不定,那就从topChunk分配
  7. 【情况五】topChunk也搞不定,那就压缩和回收fastbin,把空闲堆块放入unsortBin中。之后尝试再分配
  8. 【情况六】还不行,那就调用sbrk增大topChunk
  9. 【情况七】已达堆的上限,返回失败

释放堆块的流程

释放就很简单了,该合并的合并(有与前后合并的,也有和topChunk合并的),该放到binList或者fastbin的就放进去。

只是这里要注意一点,free之前堆管理器会校验当前chunk的合法性,从而防止内存损坏或者double free.校验措施如下:

  • p->fd->bk = p
  • p->bk->fd = p
  • p->nextChunk->prev_size = p.size
  • 获取当前bin的头部是否与自己相等,如果相同,那意味着doubleFree了
    • 如free(A),此时bin的头部指向A。
    • 接着再free(A),发现匹配,异常退出

Double free

其实之所以会出现double free,主要是因为free这个操作会把当前chunk放入bin。如果依次free A,B,A,再连续malloc 3次,那么第一次malloc和第三次malloc指向的会是同一个chunk。这样的话修改第一个malloc就会直接影响到第三个chunk。

引用