CPU眼里的：堆和栈

“Heap和Stack是程序运行的幕后英雄，但如果它一直是“无名英雄”的话，也会成为程序员的“隐形杀手”，让我们用CPU的眼睛，把它们看个清清楚楚”

01

提出问题

本系列，前面的文章中，我们提及了很多次：函数“堆栈”（stack），可以说没有“堆栈”这种特殊的数据结构，就没有函数调用。

阿布也特别喜欢“堆栈”这个翻译，因为它形象的描述了“堆栈”的堆叠结构，很好的展示了该数据结构的特点。

但为了避免跟本章节讨论的另一个数据结构“堆”（heap）混淆，在本章节，我们一律将“堆栈”（stack）简称为“栈”。

其实，“堆”(heap)和“栈”(stack)并不是一个陌生的话题，相反，它们在编程实践中，经常被程序员提及。因为，不管你是否意识到它们的真实存在，你都在使用它们。因为它们如此重要，所以为了正确的区分、使用它们，很多同学都对它们的规则、特性，倒背如流。

这里我们将尝试用CPU的视角，重新认识一下“堆”和“栈”。希望能减轻一点记忆的痛苦，并给你带来一些不同的启发。

注意：我们这里说的堆和“栈”，是指程序运行所必备的“堆”和“栈”。不是由程序员自己编写的“堆”或“栈”的数据结构，虽然二者的原理相同，但使用场景并不一致。

02

“栈”的分析

好了，一切从程序的运行开始，我们编写一个世界上最简单的代码：

int main()
{//thread A
}

经过编译器编译后，生成的可执行程序是a.out，随后我们双击运行。

在操作系统将a.out中唯一的函数main，加载到内存后；尽管我们没有定义任何变量、也没有进行任何函数调用，无论我们的程序需要与否，操作系统都会附送一段内存块给我们：

这就是“栈”。当然这个内存块不大，有几十KB的，也有几MB、几十MB的。具体大小，一般由操作系统决定。

视频“CPU眼里的：函数调用”告诉我们：这个“栈”，未来将承载着记录：函数返回地址、提供临时变量的内存空间等职责。所以，只要我们使用函数，这个“栈”就必须存在，它是函数运行的前提。

如果此时，我们又创建了一个线程B，会发生什么事情呢？

如你所见，我们也需要为线程B提供一个类似main函数的起始运行函数thread_main。

所以，为了保证线程B可以顺利的使用函数，操作系统也会为线程B准备一个同等大小的内存块，用来作为线程B的“栈”。从此之后，主线程A和线程B就可以独立运行了。

如果再增加一下难度，让线程A和线程B，同时调用函数func：

那函数func在执行完后，它怎么知道要返回到函数main，还是返回到函数thread_main呢？

其实它们的返回地址，分别存储在线程A和线程B的“栈”里面。所以，它们不会相互干扰，这样，线程A调用完函数func后，会根据自己“栈”中的信息，返回到函数main；线程B调用完函数func后，则会返回到函数thread_main。

那会不会因为线程A、线程B，对函数func的调用顺序不同，而导致函数func的返回值不同呢？

如你所见，尽管线程A和线程B，运行的都是同一个函数func的代码。但函数func里面的变量a，却分别保存在线程A和线程B的“栈”里面，它们是完全独立的，不会相互干扰，所以，函数func返回时，变量a的值一定是：1。当然，如果变量a是static的，那就另当别论了。

总的来说，“栈”在使用起来，往往是自动、无感、高效的。每次的函数调用、分配临时变量，都是在申请“栈”内存；每次函数返回，则是在释放“栈”内存。

所有这些操作，只需要简单移动一下栈顶指针，也就是改变CPU寄存器rsp的值，就可以完成了：

甚至，对“栈”内存的读、写操作，往往也是一条CPU指令，就能解决。

有趣的是：函数也不知道会有多少个线程调用它。所以，哪个线程调用它，它就操作哪个线程的“栈”：

当然，这些规则比较隐晦，需要我们对函数运行原理，有比较清晰的认识。如果大家不清楚阿布在说什么，请回看一下上个章节“CPU眼里的：{函数括号}”。

03

“栈”的生长方向

好了，说了这么多假、大、空的话，该做点实事了。写一个简单的函数stack，打印一下函数内临时变量a的值和地址，随后继续递归调用函数stack：

如你所见，随着函数的调用，变量a的值没有变化，一直是0；但它的地址一直在变化。从趋势上看，变量a的内存地址的值，在逐层降低。这也验证了那句话：“栈”的生长方向、或者说消耗、申请方向，是由高端内存，向低端内存“生长”的。

同时，由于我们的递归调用十分的规律，所以，每个变量a之间的内存地址间隔也是非常固定的32（0x20）个字节。

04

“堆”的分析

好了，说完“堆”，我们再说“堆”。跟“栈”一样，一般情况下，“堆”也是操作系统附送给我们的。不同的是，“堆”的内存空间往往比较大，可以用来存放一些超大的数据。

而且不同于“栈”的隐晦，“堆”的使用，非常明确、清晰：

int main()
{
    int* p = (int*)malloc(4);
    free(p);

    p = (int*)calloc(4, 1);
    free(p);
    
    realloc(&p, 4);
    free(p);

    p = new int(10);
    delete p;
}

程序员需要通过malloc、calloc、realloc函数或new操作来申请堆内存。只要能得到这个内存块的地址，线程A、线程B都可以随时访问这块内存。

至于释放“堆”内存，也需要程序员通过手动的调用free或delete来归还、释放内存。

总的来说，“堆”在使用起来，非常直接，看上去也比较可控。但malloc之后，忘记free的事情，也时有发生。这也是大家常说的：内存泄露。但阿布感觉这更像是：借钱不还。

另外，相比“栈”的高效操作，“堆”的申请、释放，就显得比较慢。因为，malloc、free本身就是一个比较复杂的函数。需要对每次的内存申请操作，进行管理。

这是Linux的祖先minix关于malloc函数的代码链接：https://github.com/Stichting-MINIX-Research-Foundation/minix/blob/master/lib/libc/stdlib/malloc.c

它的总代码量达到1300多行。而且，在多次malloc和free后，一大块完整的堆内存，会慢慢变得支离破碎，这也就是大家常说的：内存碎片。

例如，这是一段完整的“堆”内存块：

先做3次malloc操作：

再做1次free操作：

如你所见，我们现在已经无法从“堆”中，分配出一个连续的3KB的内存块了。

05

“堆”的生长方向

再写一个简单的函数heap，我们连续作4次的malloc操作。每次只申请4字节的内存，并打印对应的内存地址：

如你所见，指针变量p的值，也就是所得内存块的内存地址，在不断升高。这也验证了那句话：“堆”的生长方向是由低端内存，向高端内存生长的。

或许你也发现了，虽然每次调用malloc的代码，也是非常规律的，但每次得到的内存地址，也就是指针变量p的值，都是无规律变化的！这也暗示malloc的分配策略是比较复杂的，内存碎片或许正在悄悄产生。

06

总结

1. “栈”内存由操作系统分配给每个任务（线程）私用，不可共享。但由于“栈”往往得不到MMU的特殊保护，所以，这种愿望或许是难以实现的。

因为只要得到某个栈变量的地址，线程A和线程B就可以相互攻击、黑化对方的“栈”。而“堆”内存，往往可以被多个任务（线程）共享，所以，保证数据的完整性就显得非常必要。

2. “栈”内存的空间一般比较小，多用于存放“栈”变量、返回地址等函数的栈帧信息。但过深的函数调用、或者递归调用，会有“爆栈”（也叫：“堆栈”溢出、stack overflow）的风险。一般随着函数的逐层调用，函数会自动的申请“栈”内存；随着函数的逐层返回，函数也会自动的回收“栈”内存。一般情况下，不会产生内存碎片和内存泄露。

而堆的内存空间相对比较大，可用于存放较大的数据。堆内存的申请、释放，只能由程序员编写相应的代码，调用特定的函数，手动申请、释放。但随着程序的复杂，内存碎片、内存泄露会时有发生。

3. “栈”的访问效率极高，特别是申请、释放内存的操作，都被编译器高度优化。往往只需要一条CPU指令（push、pop），改变一下CPU寄存器rsp的值，就能完成任务。而堆的申请、释放函数，就会复杂许多，多次使用后，还会产生内存碎片。

至于，在没有操作系统的时候，“堆”和“栈”，就需要程序员手动划分内存空间。相信作过单片机开发的同学，对此一定不陌生。

07

热点问题

Q1：malloc跟“堆”（heap）是什么关系？

A1：“堆”（heap）一般是操作系统附送给应用程序的一段内存块，在程序运行的时候，如果需要动态分配一些内存的话，我们往往通过函数malloc从“堆”里面申请内存，当然，使用完毕后我们往往会通过free函数，归还刚才申请的内存，从而保证“堆”这个内存块是充裕的。当然，如果申请的内存量过大，超过了“堆”内存的默认空间大小时，操作系统往往也提供相应的系统调用，用以扩充“堆”内存的空间。

Q2：使用malloc做动态内存分配，会产生碎片，分配速度也慢，那使用它有什么好处呢？

A2：相对静态内存分配，动态内存分配的内存使用效率比较高。需要使用内存的时候就申请，使用完了，就释放、归还。这样，即使一小块内存，也可能同时满足多个线程、任务对内存的需求。

相反，像全局变量、静态变量，它们所占据的静态内存，从编译的时候就决定了它是永久归属的。无论当前使用与否，它们都会占据这个内存，直到程序的生命周期结束。

Q3：如果一个函数还没有运行，程序就被用户强制退出，会产生内存泄露吗？

A3：一般情况下，是不会产生内存泄露的。因为程序运行时，所占用的所有内存资源（包括：“堆”、“栈”、数据段、代码段），操作系统都有相应的记录。在操作系统得到用户强制退出的命令时，操作系统往往会先释放、回收该程序占据的所有内存、文件等资源。

Q4：“堆排序”，跟这里说的“堆”，是什么关系？

A4：没有任何关系。“堆排序”是对一种排序算法的形象描述。我们的这里说的“堆”是指：一般由操作系统提供给程序运行的内存块。

08

参考视频