囫囵C语言续（一）：堆和栈 （作者：刘涛）

0521

面试了那么多人，堆和栈这两个最基本的计算机术语居然没一个能说全对的。而且我顺手查了查网上的解释，似是而非的，浑水摸鱼的，胡说八道的一堆。趁着还没老年痴呆，给大家科普一下，不能总老让老外笑话我大中华计算机系毕业生一个个基础差的跟狗屎一样吧。

另外如果我文章中说的，和你们在网上看到的答案不一样，请以我说的为准！尤其是中文的。

说这两个概念之前首先大概讲一下一个可执行文件加载到操作系统前后大致有什么变化，这个过程很复杂后面会有章节单独可执行文件以及DLL的加载和寻址问题。

可执行文件首先有个文件头标明自己是可执行文件，而且标明自己的格式。现在流行的基本就两大类型，1. ELF，是类unix，linux系统的可执行文件格式和 2. PE/COFF，微软家族的可执行文件格式。咱们汇总一下，忽略具体名称的差异，专门说内容。如果嫌这两种文件格式复杂，去网上查一种叫 a.out 的格式，那个简单，便于入门。

首先源文件编译好，链接好以后会生成可执行文件，为什么不说编译成可执行文件，是因为编译器根本就不能把源文件"编译"成可执行文件，而是把编译好的目标文件通过链接器链接成可执行文件，编译和链接有什么区别，大家可以去查编译器和链接器的手册吧，或者去看看makefile以及链接脚本是怎么回事儿，可视化集成环境把小同学们都快变成白痴了，总之这不是本文的重点。

可执行文件里，主要的有几个段，或者区，或者片，反正用哪个词都是一个意思。我喜欢用段这个词，主要有
.text   --  存可执行文件指令的
.rwdata --  可读写全局初始值不为0的变量
.rodata --  只读数据（有些编译器会把只读数据放.text段）
.bss    --  可读写全局初始值不为0的变量，（这个段网上解释有对的，可以自己查一下）
.init   --  给C++等面向对象用的，用于调用全局类变量的构造函数
.dll    --  动态链接用的地址表，这个以后再说
剩下的自己看手册吧，还有好多呢。

对于某些说 C++效率足够高，完全可以取代C的二把刀，告诉你个小秘密，不是所有操作系统都支持C++语言，或者说C++可执行文件的格式和C不一样，需要操作系统支持才行，颠覆人生观不？下面会讲。

程序读入到内存后，先创建个进程。这破玩意儿不能执行，可以理解为一个专门占用资源的大外壳。

然后捏，操作系统会给各个段按照链接好的地址分配物理页面并映射成虚拟页面。这个过程去查可执行文件加载的过程，和MMU的解释。耐心的可以等，以后会讲。

然后捏，操作系统会给 .bss 段单独分配一些物理页，.bss 为啥单独提出来呢，因为这个段里面存的数都是 0，所以为了省地儿，文件里就没有这个段的内容，但是文件头标明了这个段在内存中的起始地址和长度。但是总不能执行的时候也没有吧，所以可执行文件读入内存后，操作系统会分配相应的页面给 .bss 用，并清0。

然后捏，操作系统会把所需的 dll 映射到程序的地址空间，

然后捏，操作系统会按照空间里的 dll 初始化 .dll 所需跳转地址表

然后捏，操作系统，会执行 .init 段里面的代码，防止C++全局变量无法成功构造，有些嵌入式操作系统没有这一步，C++程序执行不了。

然后捏，给程序分配一些其它的必要资源，比如消息队列啊，用于通信的端口啊之类的

然后捏，给程序初始化个堆，这个堆就是 malloc/free， new/delete，(new/delete其实也是malloc/free) 对应的那块内存，操作系统仅仅是分配了空间段，并没有真正分配几个物理页面，同一个操作系统上每个应用程序的堆都是一样大的，即使是个 hello word，也会拥有和 word 一样大的堆地址空间。注意是地址空间，不是实际内存。所以一个破 hello word 怎么可能会给你那么多内存，其实 word，excel 一开始也没给多少，万一您启动以后就开始玩儿游戏不干活儿怎么办，那么珍贵的物理内存是不会分给你的，等你用到了再说。具体堆是怎么管理的，大家查一下什么叫缺页中断，什么叫地址空间，以及一些堆的算法，比如伙伴算法等。以后会讲。

堆，这个东西，操作系统本身有一个，供操作系统自己使用，这个堆在内核空间，你的程序看不见，也访问不到；很好理解，操作系统自己也有需要。

我们用到的是用户堆，每个进程有一个，进程中的每个线程都从这个堆申请内存，这个堆在用户空间。所谓内存耗光，一般就是这个用户堆申请不到内存了，申请不到分两种情况，一种是你 malloc 的比剩余的总数还大，这个是肯定不会给你了。第二种是剩余的还有，但是都不连续，最大的一块都没有你 malloc 的大，也不会给你。这种情况是怎么造成的呢，比如 p1 = malloc(10),  p2 = malloc(3), p3 = malloc(30), free(p2)。很好理解吧，出现碎片了，如果继续 free(p1)， p1 和 p2 会合并，free(p3) 就全合并到一起了。所以如果你的程序都是鸡零狗碎的内存，又是服务器，占的内存又很大，人品又不好，长的又不帅，时候长了就会出现这种情况，解决办法，直接申请一块儿大内存，自己管理。

另外讲个常识性问题，除非特殊设计，一般你申请的内存首地址都是偶地址，也就是说你向堆申请一个字节，堆也会给你至少4个字节或者8个字节，无它，因为好管理，另外快；举个极端的例子，比如ARM 的 cpu 根本不能访问奇地址，硬件会报错，它访问奇地址的方法是分两次从相邻的偶地址把数据拿出来给你拼成一个奇地址的数据，有兴趣看的，一下ARM编程手册就明白了。

然后捏，分配栈地址空间

然后捏，开始创建第一个线程，并把可执行文件头里面指出的第一条指令地址交给这个线程，开始运行。在创建线程的过程中从栈空间里面分配一块儿空间给这个线程，简单的说，一个进程可以创建多少个线程呢，栈分光了，就创建不了了。栈的大小可以用缺省的好像windows是 4M，当然了有些创建线程的API可以指定栈的大小，为毛呢，你想运行复杂的递归怎么办。windows有个奇葩的招数来防止栈溢出，这个有时间以后再说。

下面说栈都存了些什么。咱捡重要的说

1. 局部变量，比如
        int a;
        char *p;
        classA *instance = classA.new;
        注意一下， instance 本身是个指针，存栈上，new出来的对象在用户堆上
       
2. 函数的参数，这里只说一般的情况。
        放arm CPU不成立，arm 体系缺省前两个参数通过 r0，r1，两个寄存器传，从第三个开始才用栈传
        有同学说，Intel也未必，没错，有些编译器支持用寄存器传参数，函数需用特殊关键字声明。靠，我估计好多人声明和定义也分不清楚。

3. 调用其它函数的指令的下一条指令的地址，以便从被调用者返回。

4. 函数返回值，呵呵，不是从栈上返回的，一般是寄存器

下面捋捋一个函数

1. 进入一个函数，首先把当前栈相关寄存器压栈，好知道怎么回到调用者
2. 栈指针减去所有局部变量的大小， static 声明的是全局变量，只不过名字的作用域是函数内部，不信去看 .obj 文件的符号表，如果你知道什么是符号表的话。
3. 要调用其它函数了，首先把传递给函数的参数压栈，压栈顺序分 c 语言方式--倒序，pascal语言方式--正序，两种。
4. call--也就是跳转到被调用者的指令会自动将 call 指令的下一条指令的地址压栈
--------5. 被调用者重复该过程
6. 从被调用者返回，函数的返回值直接检测某个寄存器，比如 intel 是 eax，arm是r0
7. 函数该返回了，把返回结果存入 intel是eax，arm是r0 寄存器
8. 从栈中恢复栈相关寄存器，这是恢复成调用者的环境，为返回做准备
9. 返回，ret 指令将自动把此时栈的栈顶，也就是调用者的下一条指令的地址恢复到 ip 指令指针寄存器。

解释几个常见现象
1. 如果函数有栈溢出的漏洞，会被注入恶意代码取得程序控制权，这个以后再讲。
2. 调试器就是通过捋你的线程栈，知道你函数的调用 call stack 的，调试原理以后再讲
3. 现在明白递归是怎么回事儿了吧，这个大学老师已经讲过了

另外，其实一个线程的栈有两个，一个是用户态的栈，也就是刚才讲的，另外一个是内核态的栈，内核态的栈除了这些功能外还存储了该线程被切换掉的时候的所有用的到的寄存器，这也就是教科书上所说的 -- 现场 -- 或者说 -- 上下文 -- 。

线程切换下面章节会讲。

lxyscls

上图好点吧，字太多容易审美疲劳

0521

先写完了最后补图吧，别着急

idi0t

写得有点乱……，什么都扯点……

safedead

看到这段我就乐了：
"这种情况是怎么造成的呢，比如 p1 = malloc(10),  p2 = malloc(3), p3 = malloc(30), free(p2)。很好理解吧，出现碎片了，如果继续 free(p1)， p1 和 p2 会合并，free(p3) 就全合并到一起了。"

这作者一定没读过LINUX内核源码关于内存分配的代码，看了点百度百科就开始胡扯了，假设下面三行代码顺序执行
p1 = malloc(10);
p2 = malloc(3);
p3 = malloc(30;
只有操作系统白痴才会相信这三段内存是连续的并且按照p1,p2,p3的顺序首尾相接，除非是内核空间为DMA申请的内存要保证连续性(已经有很多硬件支持非连续地址DMA了)，释放p2就出碎片的话，内核开发者可以拉去枪毙了

另外x64 ABI无论是windows还是SYS V，这作者估计都没看过，还一天到晚参数压栈呢

hanxin83

基本上是半瓶子水........

0521

safedead 发表于 2015-10-20 11:41
看到这段我就乐了：
"这种情况是怎么造成的呢，比如 p1 = malloc(10),  p2 = malloc(3), p3 = malloc(30), ...

这段呢，本来是想描述下什么东西在堆上，什么东西在栈上。堆都讲清楚，需要解释地址空间，page fault，堆的算法本身，我当然知道这个解释不准确。本来想下面讲堆的算法时候挨个补上的。掺杂在一起讲不清楚的，操作系统互相都勾着，讲一部分的时候先假设一部分东西是成立的，否则讲不清楚。
至于栈这事儿，我错了，世界上自打有操作系统开始就直接是 X86 64 位CPU，参数从来就没往栈上压过，成了不？

收到

不管是malloc还是内核的kmalloc得到的都是虚拟地址，虚拟地址就是连续的。只不过映射的对应的物理页面不是连续的而已。
64位参数少的话，前几个参数通过寄存器传递，其他一样压栈。

folklore

另外，其实一个线程的栈有两个，一个是用户态的栈，也就是刚才讲的，另外一个是内核态的栈，内核态的栈除了这些功能外还存储了该线程被切换掉的时候的所有用的到的寄存器，这也就是教科书上所说的 -- 现场 -- 或者说 -- 上下文 -- 。

婑油， 大妈你哪拷贝的啊》？

0521

folklore 发表于 2015-10-21 21:55
婑油， 大妈你哪拷贝的啊》？

有事儿说事儿，有意思么？