计算机底层3 内存

在第一篇文章：计算机底层1 如何从编程语言一步步到可执行程序中，我们提到，计算机系统中负责计算的是CPU，在这一篇文章中，我们将要介绍计算机系统中负责存储的内存。

1 内存的本质

从最小的角度看，内存就是一个个最小存储单元组成的，但是每个存储单元要么存放0，要么存放1，因为程序在内存中运行，计算机是以二进制方式工作的。最小存储单元也就是比特（bit），也就是1bit要不是0，要不是1。

8个bit 形成一个字节（byte），此时，我们为每个字节编号，每个字节都在内存中有相应的地址，这就是内存地址，通过内存地址我们可以找到这个字节的数据，这就是寻址。

我们常用4个字节为一个单位，来表示整数。比如int，一个int有2^32次方中组合，所以最小的负整数是0x80000000, 最大的正整数是0x7FFFFFFF，在十进制表达下，最多也就是10位数，在一些算法中，为了更好的鲁棒性，需要对输入的数字位数做判断，在实际开发中，有的新手会用int类型来储存11位的手机号，这就容易出现溢出错误，导致程序不正常运行或产生不正确的结果。

在当一个变量不仅仅可以保存数值时，还可以保存内存地址时，指针就诞生了。

指针就是储存着内存地址的变量，是内存地址的更高级的抽象。

也就是说，如果我们知道一个指针的地址，我们也就知道了这个指针里储存的另外一个变量的地址值，通过这个地址值，我们就可以找到这个地址值上的变量储存的东西：

如上图所示，我们知道了地址0x16fd00672，也就知道了这个地址中的数据Ox16fdff138，也是一个地址，所以这个指针指向了内存地址为Ox16fdff138的变量，也就知道了里面储存的变量42。

既然指针能够指向另外一个内存地址，那么说明，原本松散的内存空间能够通过指针连接起来，也就诞生了大学数据结构课里面学的链表，二叉树，图等等复杂的数据结构。

在一些语言里面，把指针给抽象掉了，比如Java，python 里面的变量，“看上去”只能存储数值，而在比如C语言这种对底层有强大控制力的语言中，对于变量的理解也更加贴近底层。

能够直接看到内存地址，是一种非常强大的能力，但同时也是一种破坏力很强的能力。有了指针这种能够直接访问内存的概念，程序员就可以直接操作内存这种硬件，这意味着可以绕过一切抽象，直接对内存进行读写，也意味着可能会直接破坏程序运行时的状态。

2 进程在内存中的样子

我们在第一篇文章中介绍过进程的内存地址空间分布：

我们同样讲过虚拟内存，也就是上面这张内存地址空间的表在真实的物理空间中并不存在，在物理内存中，进程被划分成了大小相同的“块”，随意地散落在物理内存中。我们只需要维护好虚拟内存和物理内存之间的映射关系的页表即可。

另外，我们并不需要维护每个虚拟地址到物理地址的映射，而是将进程地址空间划分为大小相等的“块”，这一“块”就是一页。

而且，每个进程都有属于自己的页表。这就是为什么即使两个进程向同一个地址写数据也不会有问题，因为实际上它们指向的是不同的物理内存地址。

3 栈区

栈是一种很常见的数据结构，有先进后出（Fist In Last Out）的特点。程序在运行时，栈区里面的栈帧也是这个顺序：

假如现在有几个函数，函数A 调用函数B，函数B 调用函数C，那么函数运行时栈区的变化就是：

3.1 函数跳转与返回

当函数A 调用函数B 时，我们需要知道的是函数B 的第一条指令和调用完函数B，应该怎么回到函数A。

通常情况下，函数跳转的指令后面都会跟着函数要跳转的地址，例如：

call Ox16fdff138

那么Ox16fdff138就是函数B 的第一条指令，至于回到函数A，也很简单，把call 指令的下一条指令放到函数A 的栈帧中，因为栈帧遵循先进后出的规律，在最后一条函数B 的指令指令执行完后，自然栈顶指向的就是函数A 的原下一条指令。

3.2 参数传递返回

在x86-64中，多数情况下，参数的传递与获取返回值是通过寄存器实现的。假设函数A 调用了函数B，函数A 将一些参数写入相应的寄存器，当CPU 执行函数B 时，可以从寄存器中获取参数，同样，函数B 也可以将返回值写入寄存器，函数B 执行结束后，函数A 可以从寄存器取到返回值。

但是寄存器的空间是有限的，如果当参数数量多于寄存器数量的时候，剩下的参数可以放到栈帧中，这样被调用的函数就可以从前一个函数的栈帧中获取参数了。

3.3 局部变量

局部变量同样可以放在栈帧中，但是如果当局部变量的数量超过寄存器时，这些变量也是要放在栈帧中的。

3.4 寄存器的保存与恢复

有这样的情况：寄存器是CPU 内部资源，CPU 执行函数A时，会使用这些寄存器，函数A 调用函数B，当CPU 执行函数B时，也会使用这些寄存器，那么函数A 放在寄存器中的信息有可能会被函数B 覆盖。

那么很容易想到，我们应该把寄存器的原始值保存起来，便于后续即使被覆盖了也能恢复。那么把原始值保存到哪里呢？没错，依然是放在栈帧中。

4 堆区

在内存管理中，栈区是用于存储函数运行时信息，局部变量的，当函数调用完成，原来的栈帧信息就会被自动回收。而堆区是用于储存动态分配得到的内存，需要程序员手动管理内存。

现在如果有一个变量需要横跨多个函数，这个时候，我们有可能会考虑全局变量，但是全局变量是对所有模块开放的，这并不安全，我们并不想这个变量暴露给所有模块，但是同时我们希望自己管理它的生命，直到我们认为我们不再需要它，就将其释放。这个时候，我们就可以在堆区中申请一块内存。

C/C++ 中可以通过malloc/new 来在堆区申请内存，当不需要时，就使用free/delete来释放。

Objective-C 中，可以通过alloc/new 来在堆区申请内存，如果是ARC机制，就会自动引用释放，也不需要程序员手动free。

以上就足够程序员在日常开发中对堆区的使用了，但是在底层的学习中，我们希望深入了解堆区内存分配器的原理。

我们也许可以自己手动实现一个malloc 内存分配器。

4.1 把内存组织起来管理

其实我们的目标很简单：就是要在堆区上解决两个核心问题：

首先，用户申请的内存是大小不一的：有8个字节的，有16个字节的，有32个字节的，那么我们就需要把内存块用某种方式组织起来。

在前面我们说了，以指针为核心的链表这种数据结构能够把松散的内存连接起来，这正符合我们要实现的一整块内存分配，但是实际上，我们不能像在数据结构课上那样先创建链表，再用来记录信息，因为创建链表本身就需要申请内存，就要通过内存分配器。所以，我们必须要把链表与内存的使用信息与内存块本身放在一起，这个链表没有一个显示的指针来告诉我们下一个内存块在哪，但是我们可以通过内存使用信息推断出下一块内存节点的位置。

内存的使用信息只需要记录：

由于我们的内存块上限为2GB，所以我们可以使用1个比特位来标记该内存块是否空闲，用31个比特位来记录该内存块的大小。

这样就形成了一个“链表”：我们如果知道header 的内存地址，那么我们也知道了该内存块的大小，而且header 的内存大小固定为32bit，那么header 再加上块大小，就是下一个节点的起始地址，通过这种方法，把内存块连接起来了，利用header 信息，可以遍历所有的内存块。

4.2 内存分配

我们的内存分配器已经完成内存的连接了，下一步，当用户申请内存的时候，内存分配器需要找到一个大小合适的空闲内存块，如果用户要申请4字节的内存，8字节的，16字节的，32字节的，都符合要求，那应该分配那块更好呢？这就是内存分配策略。

最简单的就是每次从头开始查找，找到第一个满足要求的，就返回。但是很明显，因为这种策略是从头开始，因此很容易在前半部分因为分配内存剩下很多小的内存块，导致下一次内存申请搜索的空闲内存块数量会越来越多，可能导致搜索性能下降。

KMP 算法（用于字符串匹配的一个经典算法）的发明者之一（K）提出，这个算法也很好理解，和First Fit 不同的是，First Fit 是从头开始搜索，而Next Fit 是从上次找到合适的内存块的位置开始搜索，因此，Next Fit 的理论搜索速度是大于First Fit 的，但是也有研究表明在内存的使用率上，不及First Fit 策略。

Best Fit 方法会遍历所有的内存块，然后将满足要求的并且大小最小的那个空闲内存块返回，很明显，这种策略更加能够合理利用内存空间，但是也很明显：在速度上远远不及First Fit 和Next Fit 策略。

当然，这里只是简单介绍，真正工业级的内存分配器是非常复杂的。

现在我们找到了合适的内存，假设我们申请的是12字节的内存，而找到的空闲内存块大小可供分配出去的也刚好是12字节（16字节减去4字节header），那么这个时候，我们只需要把header 的标记位标记为已分配，再返回header 之后的地址给用户即可。

但是也有一些情况，比如申请的还是12字节，但是分配到的还是32字节，这样会导致内部有内存被浪费，形成内存碎片。

常见的方法是将空闲内存块进行划分，前一部分设置为已分配并且返回，后一部分变成一个新的内存块。

4.3 释放内存

到现在为止，我们已的malloc 已经可以分配内存了，还差最后的释放内存。

释放内存的操作很简单，只需要把我们在申请内存时得到的地址再减去header 的大小，就得到了header 信息的内存首地址，然后将其标记为空闲即可。

但是有一些情况，比如当与释放的内存块相邻的内存块也是空闲时，如果仅仅只把它标记为空闲，那么则会出现下面这种情况：

如果这个时候要申请20字节的内存，那么即使实际上有20字节的空间，也会失败。

因此，更好的办法是如果相邻内存块是空闲的，就将其合并成更大的空闲内存块。

但是新的问题又出现了：

因为我们知道header 信息，所以我们可以很容易知道后一个内存是空闲的，但是我们要怎么知道上一个内存块是空闲的呢？

因为有了信息头header，所以我们知道后一个内存，那我们是不是还可以加一个信息尾footer，让footer 信息和header 一样，但是有了footer，我们通过footer 的地址再减去footer 里面记录的块大小，我们就可以得到上一个内存了。

这就像一个隐式的双向链表。

至此，我们简单的一个内存分配器设计就完毕了，当然，这只是简单的原理，真实的分配器是非常复杂的。

5 申请内存时发生了什么

在刚刚我们介绍了内存分配器的原理，现在我们把视角放大一点，看看CPU 处理内存分配的全过程。

5.1 内核态和用户态

CPU 一般被认为有两种常见的状态：内核态和用户态。每个程序有自己的等级，对应的是CPU 的工作状态，等级越低，CPU 的特权越大，内核态的CPU 特权最大。相反，处在用户态的程序处处受限，因为CPU 的特权小，不能访问特定的地址空间，否则程序直接结束，这就是经典的段错误：Segmentation fault。

操作系统就处于内核态，普通的程序处于用户态。

5.2 系统调用与标准库

在有些场景下，应用程序是需要请求操作系统的服务的，比如文件的读写、网络数据。操作系统也为程序员提供了一种叫系统调用（System Call） 的机制，通过 System Call，就可以让操作系统来代替我们完成一些事情。当然，System Call 都被封装起来了，程序员通常不需要自己直接进行 System Call，这是因为有了标准库来屏蔽系统差异。

原来系统调用都是和操作系统强相关的，Linux 和Windows 的完全不同，因此我们需要制定标准，对使用者屏蔽差异，这样程序员的写的程序就可以在不同操作系统上运行了。

在C语言中，这就是标准库。标准库的代码也运行在用户态，一般来说，程序员都是通过标准库去进行文件读写，网络通信的，标准库再根据具体的操作系统选择对应的系统调用。

所以，最上层是应用程序，应用程序一般只和标准库打交道，标准库通过系统调用和操作系统交互，操作系统再管理底层硬件。

5.3 堆区内存不够了，向操作系统申请内存

如果内存分配器中的空闲内存块不够用了，那就会在内存区中开辟新的区域，那么在哪里开辟呢？答案是在栈区与堆区之间的空闲区域。我们之前在讲栈区的时候说过，栈区会随着函数调用深度的增加而向下占用更多的内存，相应地，当堆区空间不足时，也可以向上占用更多的空间。

我们使用的malloc 在内存不足时，会向操作系统申请内存，比如在Linux 中，每个进程都维护了一个叫做 brk 的变量，指向堆区顶部，就是用来增大或者减小堆区的。

所以这样下来，申请内存就不仅仅只局限在用户态的堆区了，如果malloc没有找到空闲内存块，就向操作系统发出请求（比如brk）扩大堆区，这个时候，CPU 处于内核态，增大了堆区后，malloc 再次找到合适的空闲的内存块，分配内存。

5.4 虚拟内存

我们之前说过，进程的内存地址空间都是虚拟的，所以在通过malloc 申请到的内存可能只是一张“空头支票”，因为有可能这个时候该地址空间还没有映射到具体的物理内存上，那么什么时候才会真正的分配内存呢？答案是分配物理内存被推迟到了真正使用该内存的那一刻，此时会产生一个缺页错误（page fault），因为虚拟内存还没有关联到任何物理内存，操作系统捕捉到page fault 后，就会开始分配真正的内存，通过去修改页表建立好虚拟内存与该真实物理内存之间的映射关系，此后程序就可以使用该内存了。

所以，只有操作系统才能分配真正的内存，其发生在内核态，malloc仅仅是内存的二次分配，而且分配的还是虚拟内存。

5.5 分配内存的完整流程

当malloc开始申请内存时，

6 内存池

但是有一点，如果频繁的malloc申请释放内存，无疑对系统性能有一定影响，尤其是在对系统性能比较高的场景。

我们可以使用内存池技术，也就是针对某种场景实现自己的内存分配策略。

6.1 内存池与内存分配器的对比

6.2 内存池实现技术原理

内存池技术是内存分配器的再一次抽象，一次性申请一大块内存，在其之上自己管理内存的分配和释放，这样就绕过了标准库和操作系统。

也就是先申请一大堆内存，使用的时候拿出一个，使用完再放回去，不过这样只能分配特定的数据结构对象。

如果要实现稍微复杂的大小可变的内存池，可以用链表的形式把所有的内存块链接起来，再用一个指针指向当前空闲块的位置，当内存不足时，可以向malloc申请新的内存块。

6.3 内存池的线程安全问题

要怎样为每个线程维护一个线程池呢？在上一篇文章中提到的线程局部存储就派上用场了，我们可以将内存池放在线程局部存储中，这样每个线程都只会操作自己的内存池，不会影响到其他线程。

7 内存相关经典bug

与内存相关的bug 难以排查，当程序出现异常时，可能距离真正有问题的代码已经很远了，这导致问题的定位排查非常困难。

7.1 返回局部变量指针

初学指针的人经典错误：

int* func() {
    int a = 2;
    return &a;
}

int main() {
    int *p = func();
    *p = 20;
    return 0;
}

a是局部变量，位于栈区，在函数完成后，会被自动回收，因此，a本应该不复存在，地址也是无效的，或者在别的函数执行时占用这块地址，也就是这块本来是a的地址将会被覆盖，那么*p实际就是在修改别的函数的栈帧，这也说明了为什么一旦发现出现异常，离真正出问题的这行代码已经很远了。

7.2 错误地理解指针运算

int sum(int *arr, int len) {
    int sum = 0;
    for(int i = 0; i < len; i++) {
        sum += *arr;
        arr += sizeof(int);
    }
    return sum;
}

上面这段代码本意是想给数组里面的数加和，但是错误的理解了指针运算，其实我们并不需要关心指针指向的数据类型，指针指向的数据类型的大小就是1个单位，也就是不用arr += sizeof(int);，只需要arr += 1; 即可。

7.3 解引用有问题的指针

也是初学者经常写出的代码：

int a;
scanf("%d", a);

这种代码在编译时并不会报错，因为scanf会把a 的值当作地址对待，并且从标准输入中获取的数据写到该地址中。

接下来，程序的表现就取决于a 的值了，而上述这段代码中a 的值是不确定的，那么就会出现以下几种情况：

7.4 读取未初始化的内存

void add() {
    int *arr = (int*)malloc(sizeof(int));
    *arr += 10;
}

上面这段代码错误的认为从堆上动态分配的内存总是被初始化为0，但是实际上分为两种情况：

7.5 数组越界

不同的编程语言在处理数组越界问题时有不同的行为。

有些语言在发现数组越界了，就马上终止程序并且给出终止信息，这种情况下便于排查问题，但是有些语言并不会报错，而是任由越界的数据破坏数组以外的内存空间，那么后续当原本的数据要使用时，就发现原数据已经被越界的数组修改破坏了。

7.6 栈溢出

刚刚的数组越界是发生在堆上的溢出，而像函数等发生在栈帧上的溢出更加容易导致问题，因为栈帧中保存有函数返回地址等重要的信息。

早期黑客利用栈溢出漏洞的原理就是基于对程序中的缓冲区溢出进行利用。

以下是早期黑客利用栈溢出漏洞的一般原理：

7.7 内存泄漏

void memory_leak() {
    int *arr = (int*)malloc(sizeof(int));
    return;
}

以上这段代码问题也很明显：申请了内存后一刻返回，该内存再也没有机会被释放了。这就是内存泄漏。这会导致堆区越来越大，直到进程被操作系统终止。

8 为什么不是SSD？

SSD 是 "Solid State Drive"（固态硬盘）的缩写，是一种用于存储数据的媒体设备。

许多现代计算机，特别是笔记本电脑、台式机和服务器，都配备了固态硬盘（SSD）。这些设备通常会更快地启动，运行应用程序更流畅，因为 SSD 具有更快的数据读取和写入速度。

但是，SSD 能够取代内存吗？

答案是不能。

9 总结

内存和CPU 是计算机中的核心部件，内存中储存着CPU 执行指令依赖的一切信息。

在内存中又划分出了栈区，堆区，数据区，代码区。函数的调用信息，局部变量储存都在栈区，在函数调用完成也会自动回收栈区资源，堆区用于动态分配内存，需要程序员手动维护生命周期，数据区里面是全局和静态变量，代码区存储正在执行的程序的机器指令。

在物理内存的基础之上，我们有了虚拟内存，虚拟内存让进程认为自己独占整个内存空间，这样程序员可以在一片连续的地址空间编程，这带来了极大便利。

10 参考资料

• 陆小风. 计算机底层的秘密. 电子工业出版社, 2023.
• 计算机底层的秘密 gitbook