编程高手必学的内存知识03：深入理解堆

目录

1 堆内存分配概述

1.1 malloc函数内存分配示例

1.2 堆内存分配实现结构

2 堆内存分配系统调用

2.1 sbrk系统调用

2.1.1 系统调用封装函数原型

2.1.2 工作原理

2.2 mmap系统调用

2.2.1 系统调用封装函数原型

2.2.2 工作原理

2.2.3 应用场景

3 内存管理策略

3.1 空闲链表

3.2 内存管理策略评价指标

3.3 简单算法

3.3.1 数据结构

3.3.2 内存分配

3.3.3 内存释放

3.3.4 算法评价

3.4 分桶管理

3.4.1 数据结构

3.4.2 内存分配

3.4.3 内存释放

3.4.4 算法评价

3.5 伙伴系统

3.5.1 分桶管理的扩展性问题

3.5.2 数据结构

3.5.3 内存分配

3.5.4 内存释放

3.5.5 算法评价

3.6 实际malloc函数内存管理策略

4 定制自己的内存管理库

4.1 为什么要定制自己的内存管理库

4.2 定制内存管理库实例

4.3 定制内存管理库实践

4.3.1 double free问题场景

4.3.2 任务需求

4.3.3 实现代码

4.3.4 实现原理

---

1 堆内存分配概述

1.1 malloc函数内存分配示例

C语言程序中一般通过malloc & free函数进行堆内存的分配与释放，示例程序如下，

程序运行效果如下，

说明1：内存分配返回地址在进程线性地址空间中的位置

① 首先需要明确的是，malloc函数返回的是申请的内存块的线性地址

② 将示例程序在后台运行，之后通过如下命令查看相应进程的线性地址空间映射情况

cat /proc/[pid]/maps

③ 对照IA-32 + Linux的进程线性地址空间布局，

• malloc(256)函数调用分配的内存位于堆区

• malloc(256 * 1024)函数调用分配的内存位于文件映射和匿名映射区

说明2：关于mmap系统调用的返回值

① 值得注意的是，示例程序中mmap系统调用创建的vma起始地址为0xb7510000，但是返回给应用程序的地址为0xb7510008，该地址并非页对齐

② 根据Linux 2.4内核中mmap系统调用服务例程的实现，返回的是vma的起始地址，因此返回值中8B的偏移量应该是glibc库中mmap系统调用封装例程添加

③ 为了验证上述猜测，我们使用strace工具跟踪示例程序运行过程中的系统调用，可见mmap2系统调用返回的地址为0xb758b000，但是最终返回给示例程序的地址为0xb758b008

同时可以看出，对于brk系统调用的返回值，glibc库也增加了8B的偏移量

1.2 堆内存分配实现结构

之所以使用malloc函数分配的内存会位于进程线性地址空间的不同区域，是因为malloc函数在实现时会依靠sbrk和mmap两个系统调用，其中sbrk系统调用会从堆区分配内存；mmap系统调用会从文件映射和匿名映射区分配内存，具体结构如下图所示，

说明1：mmap系统调用分配的也是"堆内存"

① mmap系统调用分配的内存虽然位于文件映射和匿名映射区，但是在当前场景下是作为堆内存使用，因此从功能的角度和使用sbrk系统调用分配的内存是相同的，也是堆内存

② mmap系统调用分配的内存不仅可以作为堆内存使用，还可以作为协程的栈使用（可参考编程高手必学的内存知识02：深入理解栈 chapter 3.2），因此一块内存区域到底是什么，取决于如何使用他

说明2：为什么不直接使用系统调用分配内存？

① 执行系统调用需要陷入内核态，而特权级的切换是有开销的，因此直接使用sbrk和mmap系统调用分配内存效率比较低

② 与此同时，系统调用提供的内存分配功能非常简单，不能对分配得到的内存进行精细化管理。因此函数库的通常做法是先通过系统调用向操作系统申请大块内存，然后将这块内存分割成更小的块以便程序员使用，同时还会通过各种优化手段让内存分配效率最大化

说明3：malloc函数选择系统调用的标准

malloc函数内部以128KB为调用sbkr和mmap系统调用的阈值

详情可参考Linux操作系统原理与应用04：内存管理 chapter 2.2.4关于malloc函数实现方式验证的相关内容

2 堆内存分配系统调用

2.1 sbrk系统调用

2.1.1 系统调用封装函数原型

sbrk系统调用相关的封装函数有2个，

2.1.2 工作原理

1. Linux内核会为每个进程维护一个brk变量，该变量指向堆的顶部，因此brk的位置决定了堆的大小

2. sbrk系统调用通过修改brk变量的值，来改变堆的大小

3. 需要注意的是，当通过sbrk系统调用分配内存时，只是分配了线性地址空间（也就是虚拟地址），并没有分配物理内存。物理内存的分配，由后续访问时触发的缺页异常完成

说明1：Linux 0.11内核中brk变量实例

① 首先需要说明的是，内核是为每个进程维护一个brk变量，因为每个进程都有独立的线性地址空间

② Linux 0.11内核中的brk变量维护在task_struct结构中

③ 在sbrk系统调用服务例程中，会根据判断结果设置brk变量的值，从而改变堆的大小

说明2：Linux 2.4内核中brk变量实例

① Linux 2.4内核中的brk变量维护在mm_struct结构中，而mm_struct结构会被task_struct结构包含

② 在sbrk系统调用服务例程中，也会设置brk变量的值

2.2 mmap系统调用

2.2.1 系统调用封装函数原型

说明1：通过mmap系统调用建立的映射关系可以通过munmap系统调用解除，对应的系统调用封装例程如下，

① 如果不使用munmap系统调用解除映射，当进程终止时将由操作系统解除映射

② 对于文件映射（私有 / 共享），关闭文件描述符并不会解除映射

说明2：munmap系统调用并不影响被映射的对象，也就是说，调用munmap函数并不会使映射区的内容写到磁盘文件上

① 对于共享文件映射区的修改，会在我们将数据写到映射区后的某个时刻，由内核按虚拟内存算法自动更新到磁盘文件

② 对于私有文件映射区的修改，会被丢弃

说明3：如果共享文件映射区中的页已经被修改，可以调用msync系统调用将该页更新到磁盘文件中，相应的系统调用封装例程如下，

在调用munmap系统调用解除共享文件映射区之前，就可以调用msync系统调用进行同步

说明4：munmap系统调用中通过（addr + len）参数描述要解除映射的区域，该区域与vma关系如下，

① 如果要解除映射的区域恰好覆盖N个vma，则只要删除这N个vma即可

② 如果要解除映射的区域的起始地址位于某个vma中间，则需要将这个vma分为2个vma，前面的vma保留，后面的vma删除

③ 如果要解除映射的区域的结束地址位于某个vma中间，则需要将这个vma分为2个vma，后面的vma保留，前面的vma删除

说明5：对于使用mmap系统调用分配的内存，可以通过mprotect系统调用修改其保护模式/访问权限，对应的系统调用封装例程如下，

2.2.2 工作原理

1. Linux将进程的用户地址空间划分为若干个区间进行管理，这些区间称为虚拟内存区（简称vma）

2. 进程的用户地址空间主要由mm_struct和vm_area_struct结构来描述，其中，

① mm_struct：描述进程整个用户地址空间

② vm_area_struct：描述用户地址空间中的各个虚拟内存区

二者的关系如上图所示

3. mmap系统调用的功能就是创建新的虚拟内存区，并根据参数设置将文件与虚拟内存页关联起来

需要注意的是，与sbrk系统调用相同，mmap系统调用也没有分配物理内存，也是依靠缺页异常分配物理内存

2.2.3 应用场景

mmap系统调用的功能非常强大，根据参数的不同，可以用于创建共享内存、也可以创建文件映射区用于提升IO效率，还可以用来申请堆内存。根据映射的类型，mmap有四种最常见的组合

说明1：私有匿名映射的使用

私有匿名映射一般用于分配内存，除了分配堆内存，线性地址空间中的栈、堆和BSS段也是通过私有匿名映射创建的

说明2：共享匿名映射示例

① 共享匿名映射在分配内存的基础上增加了共享属性，但是由于一个mmap系统调用的返回值只在父子进程间才有效，因此一般用于父子进程间通信

② 下面给出一个共享匿名映射示例程序，该程序通过共享匿名映射实现父子进程间通信

#include 
 
#include 
 
#include 
 
#include 
 
 
 
int main(void)
 
{
 
    pid_t pid = 0;
 
    // 创建共享匿名映射
 
    char *shm = (char *)mmap(0, 4096,
 
        PROT_READ | PROT_WRITE,
 
        MAP_SHARED | MAP_ANONYMOUS, -1, 0);
 
       
 
    if (!(pid = fork())) {
 
        // 子进程中获取父进程传递的消息，并向父进程传递消息
 
        sleep(1);
 
        printf("child get a message: %s\n", shm);
 
        sprintf(shm, "%s", "hello father");
 
        exit(0);
 
    }
 
 
 
    // 父进程中向子进程传递消息，并获取子进程传递的消息
 
    sprintf(shm, "%s", "hello child");
 
    sleep(2);
 
    printf("father get a message: %s\n", shm);
 
 
 
    return 0;
 
}

程序运行效果如下，

说明3：为什么共享匿名映射mmap的返回值仅在父子进程间有效？

① 父进程在调用mmap系统调用后，会在自己的线性地址空间中创建虚拟内存区并返回所分配内存的线性地址。当通过fork系统调用创建子进程时，子进程会拷贝父进程的线性地址空间，其中就包含了mmap系统调用创建的共享映射区，因此mmap的返回值在子进程中也有效

② 对于其他没有亲缘关系的进程，由于线性地址空间相互隔离，自然无法使用mmap系统调用创建的共享映射区

③ 如果将示例程序中的映射方式改为私有匿名，则父子进程之间无法共享内存

char *shm = (char *)mmap(0, 4096,
 
        PROT_READ | PROT_WRITE,
 
        MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);

程序执行效果如下，

说明4：私有文件映射观察

私有文件映射一般用于加载动态库，查看进程线性地址空间中对动态库的映射，均为私有属性

3 内存管理策略

3.1 空闲链表

1. 最常用于小块内存精细化管理的数据结构是空闲链表（free list），他将内存空闲块记录在链表中，便于进行内存的分配与释放

2. 空闲链表中的每个节点通过记录空闲内存的起始地址和长度描述了一段内存空闲块

3.2 内存管理策略评价指标

评价一个内存管理算法的指标有如下3个维度，

1. 数据结构设计是否合理，是否存在内存碎片（内部碎片与外部碎片）

2. 内存分配的效率

3. 内存释放的效率

3.3 简单算法

3.3.1 数据结构

简单算法空闲链表组织示例如下，其中，

1. 内存区域的总长度为100B，并被分割成6个小的内存块

2. 着色部分表示相应内存块已经被分配，正在使用中

3. 白色部分表示相应内存块尚未被分配，并且被组织在空闲链表中

说明：可见简单算法是直接在整块内存上进行划分，初始状态如下图所示

3.3.2 内存分配

假设要分配长度为m的内存块，简单算法内存分配流程如下，

1. 遍历空闲链表，查找第一个长度 >= m的空闲内存块

2. 如果找到，则从空闲链表中取出该节点进行内存分配。如果分配后该空闲内存块仍有剩余，则修改对应节点并重新加入空闲链表

3.3.3 内存释放

简单算法内存释放流程如下，

1. 根据要释放内存块的起始地址，在空闲链表中查找插入位置（e.g. 按地址升序组织空闲链表）

2. 检查要释放内存块与插入位置前后的空闲块是否可以合并，如果可以合并，则合并成一个更大的空闲区；如果不可以合并，则直接插入空闲链表

3.3.4 算法评价

1. 算法简单直接，FreeRTOS的heap_4内存管理就使用了这种策略，详情可参考FreeRTOS源码分析与应用开发10：内存管理 chapter 5

2. 会产生内存外部碎片

以上文中的示例为例，假设目前需要再申请一块20B的内存，虽然所有空闲内存块的总和（3 * 16 = 48B）超过20B，但是由于这3块空闲内存块不连续，因此无法分配

3. 分配效率低

① 由于分配内存时需要遍历空闲链表，因此时间复杂度为O(n)

② 如果是多线程同时分配，需要加锁保护空闲链表，此时分配效率会进一步降低

说明1：对简单算法外部碎片的改进

① 简单算法在分配内存遍历空闲链表时，是找到第一个满足条件的空闲内存块就返回，也就是首先适配（First Fit）

② 可将其优化为最佳适配（Best Fit），也就是找到能满足条件的最小空闲块才返回

③ 从直观上说，最佳适配策略能尽可能地保留大块内存，避免他们被快速地分割成小块内存，从而可以减小外部碎片

说明2：对简单算法分配效率的改进

① 简单算法在分配内存时，每次都是从头开始遍历空闲链表

② 可将其优化为Next Fit策略，也就是每次查找不是从头开始，而是从上一次查找的位置继续向后查找

3.4 分桶管理

3.4.1 数据结构

1. 分桶管理将空闲内存组织为多个链表

2. 对于单个链表，他内部的所有节点所对应的空闲内存块的大小相同，即相同大小的空闲内存块会组织在同一个链表上

3. 通常以4B为空闲内存块的长度的最小单位，并以2次幂向上增长

3.4.2 内存分配

分桶管理内存分配流程如下，

1. 找到能满足此次内存分配请求的最小区域

2. 去相应的空闲链表中取出表头节点，将整块空闲内存块分配给应用程序

3.4.3 内存释放

分桶管理在释放内存时，直接将要释放的内存块加入相应的空闲链表即可

说明：此时需要根据要释放的内存地址判断其所属的空闲链表，可以通过在分配的内存块中增加记录相关信息实现（e.g. 在空闲内存块中预留记录长度信息的空间）

3.4.4 算法评价

1. 分配效率高

由于可以直接操作相应的空闲链表的表头节点而无需遍历，因此时间复杂度为O(1)

2. 没有内存外部碎片

① 由于整个大块内存已经被提前分割为整齐的小块，所以不存在块与块之间的内存碎片

② 这点和分页机制的思路类似，都是通过固定大小的分片解决外部碎片问题

3. 会产生内存内部碎片

由于只能按照预定的分片大小，而不是实际需求的大小来分片内存，因此分配的内存中可能存在内部碎片（e.g. 要分配7B内存，但是只能分配8B的内存块给应用程序）

说明：分桶管理是一种相对均衡的做法，相较于简单算法，在内存碎片和分配释放的时间复杂度两个方面都有改善

3.5 伙伴系统

3.5.1 分桶管理的扩展性问题

假设4B空闲内存块已耗尽，但是还有8B空闲内存块，如果此时要分配4B内存，

① 如果直接分配8B空闲内存块，则内部碎片浪费比较多

② 如果不分配，则明明还有空闲内存块，却无法分配

为了可以根据需求动态地决定小的空闲内存块与大的空闲内存块的比例，人们在分桶管理的基础上改进出了伙伴系统

3.5.2 数据结构

依然是将空闲内存组织为多个链表，并且每个链表上的空闲内存块大小相同

3.5.3 内存分配

在分配内存时，伙伴系统和分桶管理的区别在于允许对空闲内存块的进一步拆分。假设目前仅有32B的空闲内存块，但是要分配4B内存

如果采用分桶管理并进行分配，则需要将32B的空闲内存块全部分配给应用程序，这会造成巨大的浪费。但是伙伴系统会对32B的空闲内存块进行拆分，

1. 将32B的空闲内存块拆分为2个16B的空闲内存块，然后将后一半加入16B的空闲链表

2. 继续拆分上一步分配得到的前16B空闲内存块，将其拆分为2个8B的空闲内存块，然后将后一半加入8B的空闲链表

3. 继续拆分上一步分配得到的前8B空闲内存块，将其拆分为2个4B的空闲内存块。其中前一半分配给应用程序，后一半加入4B的空闲链表

分配后的内存状态如下图所示，

3.5.4 内存释放

当释放内存时，如果系统发现与被释放内存相邻的伙伴也是空闲的，就会将他们合并成一个更大的连续内存，并将合并后的内存加入合适的空闲链表

3.5.5 算法评价

相较于分桶管理，在拥有其优点的基础上，伙伴系统更加富有弹性

说明：简单算法 / 分桶管理 / 伙伴系统算法评价汇总如下

3.6 实际malloc函数内存管理策略

1. malloc函数的实现在历史上共有几十种策略，这些策略往往是简单算法 / 分桶管理 / 伙伴系统的组合

2. 以glic库中的malloc函数实现为例，

① 总体上使用分桶策略，但是每个桶的内存不是固定大小的，而是

• 1 ~ 4B的空闲内存块在第1个链表中

• 5 ~ 8B的空闲内存块在第2个链表中

• 9 ~ 16B的空闲内存块在第3个链表中，并依此类推

② 在单个链表内部采用简单算法，同时允许对空闲内存块的进一步拆分

3. 假设要分配5B内存，步骤如下，

① 首先在5 ~ 8B的空闲链表中查找满足条件的空闲内存块，假设查找到一个8B的空闲内存块

② 将8B的空闲内存块拆分为5B和3B两部分，其中5B分配给应用程序，3B加入1 ~ 4B的空闲链表中

4 定制自己的内存管理库

4.1 为什么要定制自己的内存管理库

1. 性能与业务需求

系统提供的malloc函数，其性能可能不足以支撑自己的业务，或者自己的业务在分配内存时有特殊的规律，此时就需要进行专门的定制和优化

2. 调试需求

有时需要在malloc和free函数中进行一些统计动作以便于排除问题，比如打印日志

4.2 定制内存管理库实例

1. Google实现的Tcmalloc库是最著名的定制内存管理库

2. Tcmalloc最大的改进是提升多线程情况下的性能，为了解决对空闲链表加锁造成的性能瓶颈，Tcmalloc引入了线程本地缓存（Thread Local Cache）

3. 每个线程在分配内存时，会先在自己的本地缓存中寻找，

① 如果找到，则结束

② 如果找不到，则向全局管理器申请一块大的空闲区域，然后按照伙伴系统的方式添加到本地缓存中

如此一来，只需要在全局管理器中加锁，而在线程本地缓存中则不需要

4.3 定制内存管理库实践

4.3.1 double free问题场景

在申请了一段内存后，经过复杂的程序逻辑，可能存在2个指针指向同一块内存的情况，当对这2个指针都调用free函数时，就会发生double free错误

示例程序如下，

程序运行效果如下，

4.3.2 任务需求

1. 定制内存管理库，使用自定义的free函数替换glibc库中的free函数

2. 在自定义的free函数中增加日志，打印要释放的指针，以便后续问题的分析与定位

4.3.3 实现代码

1. 在free_lib.c文件中实现自定义的free函数

// 后续使用的RTLD_NEXT宏依赖此处的_GUN_SOURCE宏，因此必须要定义
 
#define _GNU_SOURCE
 
#include 
 
#include 
 
#include 
 
 
 
// 与glibc库中的free函数声明类型相同
 
void free(void *ptr)
 
{
 
    void(*freep)() = NULL;
 
   
 
    // 增加日志信息
 
    printf("ready to do free: %p\n", ptr);
 
   
 
    // 解析glibc库中的free函数并执行
 
    freep = dlsym(RTLD_NEXT, "free");
 
    freep(ptr);
 
   
 
    // 增加日志信息
 
    printf("free done: %p\n", ptr);
 
}

2. 使用如下命令将free_lib.c文件编译为动态库

# -ldl编译选项用于链接libdl.so，dlsym函数包含在该动态库中
 
gcc -shared -fPIC -o libfree_lib.so free_lib.c -ldl

说明：使用ldd命令查看libfree_lib.so所依赖的动态库，信息如下，

3. 使用如下命令执行应用程序，通过preload机制，使用自定义的free函数替换glibc库中的free函数

LD_PRELOAD="./libfree_lib.so" ./dfree

应用程序的执行效果如下，可见会增加调试用的日志信息

说明：实验在Ubuntu 16.04环境中进行，相同代码在较旧版本的Ubuntu环境中运行会出错

4.3.4 实现原理

1. 参考编程高手必学的内存知识04：深入理解静态链接与动态链接 chapter 6.2.2可知，动态链接器在处理动态库重名函数时，只会识别第一个遇到的符号，后续遇到的重名符号会被忽略

因此，只要让我们自己实现的free函数在glibc库中的free函数之前被解析到即可

2. preload机制是一种设置动态库加载优先级的机制，在一般情况下，动态库的加载顺序为，

LD_PRELOAD > LD_LIBRARY_PATH > /etc/ld.so.cache > /lib目录 > /usr/lib目录

在实验中，我们通过LD_PRELOAD指定自定义动态库的优先级，使得自定义动态库中的free函数先被解析到

3. 在自定义的free函数中，通过如下函数调用解析glibc库中的free函数，其中，

freep = dlsym(RTLD_NEXT, "free");

① dlsym函数的作用是通过符号名称（此处为"free"）找到符号对应的地址

② 使用RTLD_NEXT宏是告诉动态加载器不要在当前文件中查找free符号，而是要按照动态库的搜索顺序在下一个动态库中查找，此时自然就找到glibc库中的free函数