# 运行时内存结构
#### 引入
在指针长度为 4 个字节的系统中，内存地址最多有 2^32 个，我们可以将内存看作一个大的长方形区域，左下角是地址 0 ，右上角是地址 2^32 - 1。运行时内存结构最重要的三个部分分别是 Stack Segment 、Heap Segment 和 Code Segment。Stack 用于追踪当前运行时的足迹，局部变量；Heap 是一个空间池子，用于支持动态内存空间的分配；Code 用于存储 C 程序编译后的汇编程序。
#### Heap Segment
在数值较小的地址区域上，有一块区域被称为 Heap Segment，这里存着当前运行过程中动态分配的内存空间。这里的 Heap 与数据结构中的 Priority Queue 并无任何关系，在这里它仅仅指的是一个数据块，而这个数据块的分配与回收，是由软件直接控制的，该软件被称为 Heap Manager。当 malloc 被调用时，Heap Manager 会在 Heap Segment 中找到一块符合要求的内存空间，将它分配出去并记录，然后把该空间的起始地址返回给调用者；当 realloc 被调用时，Heap Manager 会首先检查该传入的地址是否被分配了空间，如果没有则调用 malloc，如果有则检查原先分配的空间是否满足 realloc 参数中指定的大小，如果满足，就直接返回；如果不满足，则首先检查原先分配的空间之后是否有足够的空闲空间满足，如果满足则直接分配所需的剩余空间，如果不满足则从 Heap Segment 中重新分配一块符合要求的空间，并将原分配空间中的数据拷贝到新的空间中，同时返回新空间的地址。
Heap Manager 并没有特殊能力，它将 HeapSegment 中的剩余可用空间像串糖葫芦一样把它们串起来，称为 freeList，然后利用 freeList 来寻找满足需求的内存空间。
**走近 Heap Manager**
```c
int *arr = malloc(40 * sizeof(int));
```
如以上代码所示，当你调用 malloc 的时候，Heap Manager 在 Heap 内部并不是只分配对应大小的空间 (160 字节)，而是会分配比要求的多一些空间，存储对 Heap Manager 有用的头部信息，如分配空间的大小信息:
**敏感的小明**
小明是个刚学习 C 并对内存资源十分敏感的程序员，他写出了如下代码：
```c
int *arr = malloc(100*sizeof(int));
// do anything he want with the arr
free(arr + 60);
```
问题在于，Heap Manager 有可能会将对它有用的信息存储在已分配内存块的头部，而 arr + 60 所指向的 Heap 地址处并没有相应的头部信息，但如果 Heap Manager 没有做错误检查，它可能会误将 arr + 60 前的一段信息解读为头部信息，因此造成程序崩溃。
小明有时候也会写出这样的代码:
```c
int array[100];
// do anything he want with the array
free(array);
```
如果 free 没有做任何错误检查 (为了性能)，这段在 Stack 中分配的内存将被交给 Heap Manager，接下来发生的事情便无法预料。
**Heap Manager 可能会如何利用头部信息？**
Heap Manager 可能会利用已分配内存节点的头部储存当前分配空间大小信息，以及已分配空间后的空闲空间大小信息。前者可以让 Heap Manager 追踪已经分配的空间，后者可以帮助 Heap Manager 确认在 realloc 的时候，是否可以原地分配。
Heap Manager 不仅会利用已分配内存节点的头部存储信息，还会利用未分配内存节点的头部存储信息。Heap Manager 要解决的核心问题是如何在 Heap 中寻找到一块符合要求的空间分配满足当前分配请求，同时分配该空间后，剩余空间能最大限度满足未来的分配请求。要做到这点，首先得做到快速检索所有空闲空间。其中一种做法就是在 Heap 中的每段空闲内存头部保存下一段空闲空间的地址，以此抽象出一张链表，利用链表线性检索剩余空闲空间。由于 Heap 中通常有很多块空闲内存可以满足请求，因此以该链表为基础，Heap Manager 可以实施不同的分配策略来决定将具体哪块空闲内存分配出去，以期达到最优性能。
一些书上常提到的分配策略：
1. best fit
2. worst fit
3. first fit
4. continuous searching
**按索取空间大小划分的分配策略**
有一种类型的 Heap Manager 会把整个 Heap 划分成多个区域，每个区域只用于满足特定范围内的分配需求。如下图所示：
图中顶部区域只负责小于 8 字节的分配需求，且每次分配都取出 8 字节的空间，中部区域只负责大于 8 字节小于 64 字节的空间，且每次分配都取出 64 字节的空间，依次类推。
不同的平台上的 Heap Manager 会有不同的空间分配策略，把分配信息记录在不同的地方，而这些对 C 程序员应该是透明的，C 程序员不能够依赖 Heap Manager 的实现细节来完成变成，也不能够违反抽象时的契约，以非契约规定的方式使用 Heap Manager，否则就可能造成无法预料的后果。
**Compact Heap**
当 Heap 被频繁分配回收以后很可能出现碎片化现象，这种现象可能导致新来的较大的空间分配请求无法得到满足，如下图所示：假设有一个 200 字节的 Heap，已经分配了 40 字节空间，还剩 160 字节，但碎片化使它无法满足一个 120 字节的分配请求，如果能将已分配空间聚集到一起，就能把碎片化的未分配空间合并，满足未来的大空间分配需求。然而，由于 Heap Manager 的用户并不知道这一切，继续使用原来的指针必然会导致错误的信息读写。
Mac OS (7 series) 的做法是在分配空间时，并不把直接内存地址交给用户，而是将指向直接地址的间接地址交给用户，用户使用间接地址时通过两次解指针得到真正的内存地址。这样的好处是系统可以利用守护进程来整理碎片空间，前提是用户在使用之前需要告诉系统停止整理特定的内存区域，也泄露了该层抽象。
#### Stack Segment
在数值较大的地址区域上，有一块区域被称为 Stack Segment，这里存着当前运行环境的函数栈。当 main 函数执行时，它的局部变量被压入栈中，构成该函数的运行环境，当 main 函数调用 A 函数时，main 函数执行的当前地址，即 A 函数的返回地址，以及 A 函数的局部变量被压入栈中，如果 A 函数还有对其它函数的调用则以此类推……直到最后一个函数执行完毕后，它读取上一个函数执行停止处的地址，将当前函数的运行环境从栈中弹出后，继续执行上一个函数……直到回到 main 函数中并将 main 函数执行完毕。运行过程中内存的运行环境都保存在 Stack Segment 中，它由硬件直接控制。
**走近 Stack**
```c
void A() {
int a;
short b[4];
double c;
B();
C();
}
void B() {
int x;
char *y;
char *z[2];
C();
}
void C() {
double m[3],
int n;
// ...
}
```
**Activation Record (or Stack Frame)**
考虑以上代码片段，函数 A 调用函数 B 和函数 C，函数 B 调用函数 C，在执行的过程中，每个函数有自己的 Activation Record, 简称 AR （也称 Stack Frame），在 AR 中从高地址处往低地址处顺序存储着局部变量，如下图所示：
将 A、B、C 的 AR 分别抽象成一个正六边形、正三角形和圆形。当 A 执行时，A 函数的 AR，即它的所有局部变量会被放入 Stack 中，此时有一个指针指向该 AR，它叫做 Stack Pointer，下文简称 SP。SP 总是指向当前的 AR，由此，计算机能够利用 AR 地址信息、局部变量相对于 AR 地址，即最后一个局部变量地址，的 offset 来对局部变量寻址。
假设 A 函数在程序中间某处开始执行，从 A 开始执行到 A 执行完成，Stack 与 SP 的关系如下图所示：
一图胜千言，为什么这个内存结构被称为 Stack 也就一目了然了。
#### 进入 Code Segment 之前 --- 逻辑计算单元(ALU)、寄存器 (Registers) 和内存 (Memory)
如下图所示，在内存与逻辑计算单元之间，有一小块特殊的内存，叫做寄存器。通常，它与逻辑计算单元以及内存直接相连，在物理上就保证了存取的速度。且由于寄存器单元的数量远远小于内存单元的数量，因此寄存器寻址速度也要远远快于内存寻址，同时简化逻辑计算单元内部所需支持的功能。
通常一个计算任务可以分拆到极小的子任务，每个任务的基本流程通常是：
1. 从内存中把所需数据读入寄存器
2. 利用逻辑计算单元对寄存器中的数据进行计算，如加、减、乘、位移等等，将结果存回寄存器
3. 将最终结果放回内存中
**参考**
* [Stanford CS107: lecture 7](https://www.youtube.com/watch?v=Yr1YnOVG-4g\&t=124s)
* [Stanford CS107: lecture 8](https://www.youtube.com/watch?v=1nYDflSL0Mg\&list=PL9D558D49CA734A02\&index=8)
* [Github: ZhengHe-MD - lecture codes](https://github.com/ZhengHe-MD/cs107-lecture-codes)
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://zhenghe.gitbook.io/open-courses/stanford-cs107/di-qi-ba-ke-yun-hang-shi-nei-cun-jie-gou.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.