理解Linux堆内存管理

一、堆的基础知识

1.1 堆的内存布局

1.2 堆和栈的区别

栈主要用来维护函数调用的上下文,由高向低增长;
堆用来容纳程序动态分配的内存区域,使用malloc或new分配的内存,由低向高增长;

二、堆的实现原理

2.1 malloc底层的系统调用

Syscalls used by malloc. （代码演示虚拟空间的变化）

brk: brk obtains memory (non zero initialized) from kernel by increasing program break location (brk). Initially start (start_brk) and end of heap segment (brk) would point to same location.
向上增长
mmap: malloc uses mmap to create a private anonymous mapping segment. The primary purpose of private anonymous mapping is to allocate new memory (zero filled) and this new memory would be exclusively used by calling process.
向下增长

2.2 malloc 实现原理

资料：

Understanding glibc malloc

Linux 堆内存管理深入分析（上） Linux堆内存管理深入分析（下）（对上文的翻译和扩充）

多线程的支持
原来Linux的内存管理是dlmalloc，两个线程同时请求malloc只有一个能进入临界区；
后来被支持多线程的ptmalloc2代替，两个线程可以同时分别分配内存；

数据结构

Arena
- 一块连续的堆内存叫做arena，负责提供线程的内存分配和回收。
- 主线程创建的arena叫做main arena，通过brk方式；
  其他线程创建的arena叫做thread arena，通过mmap方式；
  用户请求大于128KB时，来自main arena还是thread arena，都通过mmap的方式分配空间。
- 线程和arena不是一一对应，存在数量限制所以会共享
  For [32 bit] systems: Number of arena = 2 * number of cores + 1.
  For [64 bit] systems: Number of arena = 8 * number of cores + 1.
Heap
- main arena中只有一个heap，内存不够时通过brk方式扩展，知道碰到内存映射段；
  thread arena中存在多个heap，内存不够时通过mmap方式新建heap，heap之间非连续，通过Heap Header管理；
- 每个heap的基本单位是chunk，内存分配的单位也是chunk；
- 每个arena可以有多个heap，但heap只是提供了物理空间，真正管理chunk的结构是bins, top chunk, last remainder chunk；
  
  只有一个heap
  
  多个heap

chunk

堆实际是连续的、大小不一的chunk组成，可以分为Allocated chunk、Free chunk、Top chunk、Last Remainder chunk四类；

chunk的结构比较有意思

size：自己的Size，因为是连续空间，根据自己的size加上偏移就是下一个chunk;
prev_size：上一个chunk的size，和前一个chunk合并是困难的，但是保存了prev_size，连续空间就可以计算出前一个chunk的位置；
PREV_INUSE (P) – This bit is set when previous chunk is allocated.
IS_MMAPPED (M) – This bit is set when chunk is mmap’d.
NON_MAIN_ARENA (N) – This bit is set when this chunk belongs to a thread arena.
物理上chunk在heap中连续，但同一类chunk的管理是通过bins结构。fd、bk分别Points to next chunk in the same bin (and NOT to the next chunk present in physical memory).

 chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |             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                                     |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Bins
Bins是用来维护free chunk的链表数据结构，分配chunk从bins选，释放的chunk添加到bins；
Bins分为了四类：Fast bin、Unsorted bin、Small bin、Large bin；
- Fast bin
  - Chunks of size 16 to 80 bytes is called a fast chunk，一个Fast bin就是一个fast chunk的链表。
  - 一共10个Fast bin，Fast bin1存储16字节的fast chunk，Fast bin2存储24字节的fast chunk，so on (16-80字节)。
  - fast chunk的特点是两个相邻的fast chunk不需要合并，所以free非常快。
  - fast chunk的maloc和free都是在对应的fast bin的链表头增加和删除，LIFO；
- Unsorted bin
  当 small or large chunk被free的时候不会直接加入到相应的small bin和large bin中，而是被添加到Unsorted bin；主要的目的是为了重新利用这些刚被释放的chunk；
  - unsorted bin只有一个，是一个由free chunks组成的循环双链表；
  - 在unsorted bin中，对chunk的大小并没有限制，任何大小的chunk都可以归属到unsorted bin中；
- Small bin
  小于512字节的chunk称之为small chunk，small bin就是用于管理small chunk的。就内存的分配和释放速度而言，small bin比larger bin快，但比fast bin慢。
  - small bin有62个，每个small bin都是free chunk的双向链表，FIFO；
  - 每个small bin中的chunk大小是一样的，不同的small bin从16字节开始，步长为8字节，直到512字节；
  - malloc：找到匹配的非空bin，返回最后一个chunk；
    free：当释放small chunk的时候，先检查该chunk相邻的chunk是否为free，如果是的话就进行合并操作：将这些chunks合并成新的chunk，然后将它们从small bin中移除，最后将新的chunk添加到unsorted bin中。
- Large bin
  大于512字节的chunk称之为large chunk，large bin就是用于管理这些large chunk的。large chunk最慢，因为一个Large bin中不同的chunk可以不一样大。
  - large bin有63个，双向链表，删除和添加的位置不在头尾，可以任意位置；
  - 步长不一样，在这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中的large chunk按照大小倒序排列。
  - malloc(large chunk)操作：初始化完成之前的操作类似于small bin，这里主要讨论large bins初始化完成之后的操作。首先确定用户请求的大小属于哪一个large bin，然后判断该large bin中最大的chunk的size是否大于用户请求的size(只需要对比链表中front end的size即可)。如果大于，就从rear end开始遍历该large bin，找到第一个size相等或接近的chunk，分配给用户。如果该chunk大于用户请求的size的话，就将该chunk拆分为两个chunk：前者返回给用户，且size等同于用户请求的size；剩余的部分做为一个新的chunk添加到unsorted bin中。
  - Free(large chunk)：类似于small chunk。
Top chunk
每个arena的最高区域的chunk就是Top chunk，只有一个，不属于任何的bin。当系统的哪类bin都没有满足用户请求的free chunk时就需要用到Top chunk了。
- 当Top chunk大于用户请求，一分为二。 User chunk和剩余的chunk，该chunk也就变成了新的Top chunk；
- 当Top chunk小于用户请求，就需要扩展heap（main arena使用brk）或者分配新的heap（thread arena使用mmap）。

内存分配的过程

首先是fast bin，其次是small bin，然后是unsorted bin，最后是large bin。

三、后续学习

相比于之前对于堆只有个概念上的了解，现在对于堆的内存管理有了更直观的认识，
下一步有时间还是得深入源码来分析内存分配和回收的具体实现。

ptmalloc2 – glibc 源码：
https://github.com/sploitfun/lsploits/blob/master/glibc/malloc/arena.c
https://github.com/sploitfun/lsploits/blob/master/glibc/malloc/malloc.c
入口函数 __libc_malloc (size_t bytes) 分配函数 _int_malloc (mstate av, size_t bytes)
可以参考：glibc内存管理ptmalloc源代码分析