title: 动态内存分配 date: 2023-03-30 15:35:21 tags: 体系结构

前言

本节继续前文虚拟内存的内容, 深入的讨论一下内存分配的相关技术细节

动态内存分配

我们可以使用较为低级的 mmap 和 munmap 函数来创建和删除虚拟内存区域, 但是 C 程序员还是会觉得当需要额外虚拟内存的时候, 使用动态内存分配器更加方便

动态内存分配器维护着一个进程的虚拟内存区域, 称为堆 (heap). 堆是一个区域, 它紧接着在未初始化的数据区域后开始, 并向高地址处生长. 对于每一个进程, 内核维护着一个变量 brk 指向堆的顶部, 整个虚拟内存的视图如下所示

分配器将堆视为一组不同大小的块, 每个块就是一段连续的虚拟内存片, 要么是已分配的要么是空闲的. 已分配的块显式的为保留为供应用程序使用, 空闲的块可以用来分配. 一个已分配的块保持已分配的状态直到它被释放. 这种释放要么是应用程序显式执行的(free), 要么是内存分配器自身隐式执行的

分配器有两种风格, 这两种风格都要求应用显式的分配块, 但区别在于

• 显式分配器: 要求应用显式的释放任何已分配的块, 例如 C 程序通过 malloc 分配一个块并通过 free 释放

• 隐式分配器: 要求分配器检测一个已分配的块何时不再被应用程序使用, 那么就释放这个块. 这种隐式分配器也叫做 垃圾收集(garbage collection), 诸如 java python js等高级语言就依赖垃圾收集释放已分配的块

显式分配器

#include <stdlib.h>
void *malloc(size_t size);
void free(void *ptr);

malloc 函数返回一个指针, 指向大小至少为 size 字节的内存块, 这个块的地址会根据操作系统模式32(8)/64(16)做对齐以方便访存

free 函数释放指针指向的堆块, 如果它合法

#include <unistd.h>
void *sbrk(intptr_t incr);

sbrk 函数将内核的 brk 指针增加 incr 来扩展/收缩堆, 成功返回 brk 的旧值, 否则返回 -1 (void * 强转 int), incr 可正可负可0

下图展示了一个简单的动态内存分配的过程

这里有两点需要说明:

1. b 中虽然只申请了 5 字节的堆大小, 由于整个堆空间需要双字节补齐, 所以填补了一个字节的空间, 实际上分配的是一个 6 字节的块

2. d 中虽然释放了 p2 指针指向的堆块, 但是 p2 指针仍然指向这个位置, 应用有责任不再使用 p2 指针访问一个已经被释放的堆空间

使用动态内存分配的最主要原因就是我们并不清楚某些数据结构的大小, 或者数量等等. 比如拆分一个字符串保存在一个数组中, 诸如此类的问题我相信不必赘述

要求和目标

显式分配器必须在一些相当严格的约束条件下工作

• 处理任意请求序列: 一个引用可以以任意的顺序发送分配请求和释放请求, 分配器不可以假设分配和释放请求的顺序, 例如分配器不能假设所有分配请求都有相匹配的释放请求

• 立即响应请求: 分配器必须立即响应分配请求, 因此不允许分配器为了提高性能重排序或者缓冲请求

• 只使用堆: 为了使分配器可扩展, 分配器使用的任何非标量数据结构必须保存在堆中

• 对齐块

• 不修改已分配的块: 分配器只能操作或者改变空闲块, 特别的是一旦块被分配了, 就不允许修改或者移动它了. 因此诸如压缩已分配块这样的技术是不允许使用的

非标量数据例如数组、结构体、类、对象等。这些数据类型通常需要在堆内存中动态分配内存空间，并且它们的大小和形状在编译时通常是未知的. 相对应的，标量数据指的是只包含单一值的数据类型，例如整型、浮点型、字符型等。这些数据类型的大小和形状在编译时通常是已知的，并且它们可以在栈内存中被直接分配和访问

在计算机系统中，数据存储时需要遵循一定的对齐规则。对齐是指将数据的起始地址与某个固定的值对齐，通常为2的整数次幂。例如，对于4字节的数据类型，通常需要将其对齐到4字节的边界。这样可以提高数据访问的效率，避免不必要的内存访问操作。

对于内存分配器而言，它需要对分配的内存块进行对齐，以保证内存块能够存储任何类型的数据结构。例如，如果内存分配器分配的内存块不满足对齐要求，那么当程序员试图将一个需要对齐的数据类型存储在这个内存块中时，就可能会发生数据对齐错误的问题，导致程序出错或崩溃。

因此，内存分配器需要对齐分配的内存块，以保证内存块能够存储任何类型的数据结构，并且程序能够正常地访问和操作这些数据结构

内存分配器的目标有如下两个

1. 最大化吞吐率: 吞吐率定义为单位时间内完成的请求数, 比如 1s 内完成 500 次分配请求和 500 次释放请求那么吞吐率是 1000

2. 最大化内存利用率

分配器设计中的一个有趣的挑战就是在两个目标之间找到一个适当的平衡

造成堆利用率很低的主要原因是一种被称为 碎片 的现象:

• 内部碎片: 一个已分配块比有效载荷大

  很多情况可能导致这个情况, 例如一个分配器的实现对分配块强加一个最小值, 这个值比实际申请的要大. 或者为了满足对齐要求而补齐

  

• 外部碎片:

  如下图, 由于多次的分配和释放, 现在堆中已分配的块被划分为一块一块的, 此时如果希望申请一个 40MB 的堆块, 虽然空闲块的总量足够但是没有一块连续的空间. 注意到分配器的要求不可以修改已分配的块, 即 压缩排列块 是不合法的. 这种情况只能使用 sbrk 向操作系统申请扩大堆

  

隐式空闲链表

为了更好的组织已分配的块和空闲块, 我们可以使用隐式空闲链表来串联整个堆, 下图为隐式链表的每个节点的数据结构图

其中开头使用 4 字节(32位) 来表示整个块的相关数据, 开头的 32 位用于表示整个块实际分配了多大. 需要注意的是, 每一个分配的块必须要是8字节对齐, 所以实际上分配块一定的 8 的整数倍, 所以最后 3 位一定全为 0, 这样最后三位就空闲了出来, 我们将最后一位设置为标记位用于区分该块是已分配的还是空闲的

举个例子: 对于 malloc(1) 的分配请求, 虽然只请求了 1 个字节, 但是我们需要先加 4 字节的头部信息, 所以目前是 4+1 = 5 字节, 但是为了满足 8 字节(64位)对齐以提高数据访问的效率，避免不必要的内存访问操作, 实际分配的块大小是 8 字节, 对应的实际块情况如下所示

图中字节的面积比例有点不对,应该是 4:1:3 , 大家理解我的意思就好...

开头的 4 字节是 0x00 00 00 09, 由于分配块一定是 8 位对齐, 所以最后 3 位空出来, 0x1000 表示分配块的实际大小, 最后一位表示分配(1)还是未分配(0), 最后填充3B对齐

再举一个例子: 如果是 malloc(13) 的话, 分配块的结构如下所示

接下来我们来看一下堆中隐式链表的块是如何组织起来的, 以书上这张图为例

其中每一个正方形块代表 4 字节, 这里的 8/0 16/1 表示的意思是 分配块的大小/已分配位, 红色块为链表头, 蓝色块为实际申请的内存大小, 灰色块为填充位. 所以整个堆被划分为了几部分, 4字节空闲 + 8字节已分配 + 24字节空闲 + 12字节已分配, 中间穿插着一些头部信息块和填充块. 再创建一个链表结构保存头节点的相关信息, 以实现后续的分配释放

分割

对于一个 k 字节的内存申请, 分配器搜索空闲链表块找到一个足够大的可以放置请求块的空闲块. 分配器执行这种搜索的方式是由放置策略决定的, 一些常见的策略是:

• 首次适配(first fit): 选择第一个合适的空闲块

• 下一次适配(next fit): 从上一次查询结束的地方开始首次适配

• 最佳适配(best fit): 检查每个空闲块, 选择适合所需请求大小的最小空闲块

如果分配器不能找到合适的空闲块, 那么一个选择是合并哪些在物理上相邻的空闲块, 把他们合并为一个大块. 如果依然不可以, 那么分配器会调用 sbrk 函数向内核申请额外的堆内存. 分配器将额外的内存转化为一个大的空闲块, 将这个块插入到空闲链表中, 然后将被申请的块放置在这个新的空闲块中

合并

当分配器释放一个已分配的块, 这时候如果有其他空闲块和这个新释放的空闲块相邻, 这些相邻的空闲块会造成一种现象 "假碎片": 有许多可用的空闲块被切割成小的, 无法使用的空闲块

为了解决这个问题, 分配器必须考虑合并相邻的空闲块, 但这时候存在一个重要的策略决定就是 何时执行合并?

• 立即合并: 这种方式简单明了, 可以在常数时间内完成, 但是对于某些请求模式, 这种方式会产生一种形式的抖动, 块会反复的合并, 然后再次分割, 如下图所示

• 推迟合并: 直到某个分配请求失败, 扫描整个堆, 合并所有的空闲块

我们假设会使用立即合并, 但是同时也应该清楚快速的分配器通常会选择某种形式的推迟合并

如果当前被释放的块的链表指针指向的下一个块是空闲块, 那么我们很容易将其合并, 只需要修改当前块的头中的块大小, 加上后面块的大小即可

但是如果当前被释放的块的前一个块是空闲块, 那么情况稍微有些棘手. 因为我们使用的是一个单链表, 无法在常数时间内找到前一个块. 一个非常聪明且通用的技术叫做 "边界标记", 如下图所示, 我们修改之前的分配块结构, 在结尾补充一个四字节, 与头完全相同, 这样分配器就可以通过检查它的尾部来判断前一个块的起始位置和状态了

这里可能有人会有一些疑惑

第一: 为什么使用的是单链表呢? 正常来说如果我们改成双链表的话就可以在常数时间内找到前一个块了, 主要是因为单链表相对于双链表来说，具有更小的存储开销和更快的插入和删除操作。在单链表中每个节点只包含一个指针，而双链表每个节点包含两个指针。因此，使用单链表可以节省存储空间，并且在插入和删除节点时具有更高的效率. 但实际上我们使用的这种 "边界标记" 相当于把这部分开销放到了堆块上了, 有舍有得

第二: 加一个尾部怎么就能判断了呢? 如果没有尾部, 我们无法找到前一个块的主要原因就是因为我们不知道前一个块是不是空闲的, 或者分配了多少, 但是如果有了尾部的四字节, 我们就可以向前读四个字节来查看前一个块的信息, (块大小 - 8)就是块的空间, 由于分配块的结构固定所以相对位置都是固定的

当分配器释放一个块的时候有如上四种情况, 其中中间空白处+前后的头/尾组成了一个完整的分配块, m1 m2为块大小, a/f 表示这个块是已分配的还是空闲的. 蓝色的块是当前分配器考虑释放的块

• 前后都是已分配的

• 前是已分配的, 后是空闲的

• 前是空闲的, 后是已分配的

• 前后都是空闲的

当释放当前块的时候, 分配器只需要检查当前块的前一个块的尾部, 和后一个块的头部, 就可以判断当前块所处的状态, 以右侧的状态完成合并

虽然边界标记的设计简单优雅, 但是它要求每个块都保持一个头部和尾部, 所以在应用程序操作许多个小块的时候会产生显著的内存开销. 例如当一个图形节点反复的调用 malloc free 来动态的创建和销毁节点, 如果每个节点都只 malloc(8), 那么头部和尾部将占据已分配块一半的空间

brk sbrk

brk 的全称是 "break"，而 sbrk 的全称是 "set break"。这两个函数的名称都与操作系统的内存管理机制中的 "break" 概念有关。

在早期的操作系统中，堆空间被划分为低地址区域（Low Memory）和高地址区域（High Memory），两者之间的边界被称为 "break"。这个边界指示了堆空间的结束位置，也就是可用内存的末尾。通过调整 "break" 的位置，操作系统可以动态分配和释放堆空间。

因此，"break" 在这里表示堆空间的边界或结束地址。brk 和 sbrk 这两个函数提供了在用户程序中直接操作 "break" 的接口，以动态分配和释放堆内存。

#include <unistd.h>
int brk(void *addr);
void *sbrk(intptr_t increment);

通常不直接使用, 高级语言和标准库提供了更方便和安全的内存管理机制比如 malloc, new