「linux」经典面试题之栈详解（堆栈平衡）

linux服务器开发相关视频解析：

我们常常说堆栈堆栈，但是堆和栈其实是完全不同的两个概念。栈其实完全是为了函数调用而设计的，那么函数调用如何通过栈实现的呢？不用函数调用方式，栈在行为上有什么区别呢？笔者曾经去京东面试一个高级开发职位，面试官写了一个从1累加到100的C程序，让笔者写出对应的汇编代码，如果你熟悉栈的原理，其实这个题目就并不难，相反，函数通过栈如何实现的，这确实是我们广大开发者必须掌握的基础知识之一，因为也是面试中用于考察一个开发者基础水平的一个常见题型。

好了，那什么是栈呢？下面是正文：

一、系统栈的工作原理

1、内存的不同用途

如果您关注网络安全问题，那么一定听过缓冲区溢出这个术语。简单说来：缓冲区溢出就是在大缓冲区中的数据向小缓冲区复制的过程中，由于没有注意小缓冲区的边界，“撑爆”了较小的缓冲区，从而冲掉了和小缓冲区相邻内存区域的其他数据而引起的内存问题。缓冲溢出是最常见的内存错误之一，也是攻击者入侵系统时所用到的最强大、最经典的一类漏洞利用方式。

成功地利用缓冲区溢出漏洞可以修改内存中变量的值，甚至可以劫持进程，执行恶意代码，最终获得主机的控制权。要透彻地理解这种攻击方式，我们需要回顾一些计算机体系架构方面的基础知识，搞淸楚CPU、寄存器、内存是怎样协同工作而让程序流畅执行的。

根据不同的操作系统，一个进程可能被分配到不同的内存区域去执行。但是不管什么样的操作系统、什么样的计算机架构，进程使用的内存都可以按照功能大致分成以下4个部分。

(1)代码区：这个区域存储着被装入执行的二进制机器代码，处理器会到这个区域取指令并执行。

(2)数据区：用于存储全局变量等。

(3)堆区：进程可以在堆区动态地请求一定大小的内存，并在用完之后归还给堆区。动态分配内存和回收内存是堆区的特点。

(4)栈区：用于动态地存储函数之间的调用关系，以保证被调用函数在返回时恢复到母函数中继续执行。

题外话：这种简单的内存划分方式是为了让您能够更容易地理解程序的运行机制入理解计算机系统》一书中有更详细的关于内存使用的论述，如有兴趣可参考之。

在Windows平台下，高级语言写出的程序经过编译链接，最终会变成所谓的PE 文件。当PE文件被装载运行后，就成了所谓的进程。

PE文件代码段中包含的二进制级别的机器代码会被装入内存的代码区（.text),处理器将到内存的这个区域一条一条地取出指令和操作数，并送入算术逻辑单元进行运算；如果代码中请求开辟动态内存，则会在内存的堆区分配一块大小合适的区域返回给代码区的代码使用；当函数调用发生时，函数的调用关系等信息会动态地保存在内存的栈区，以供处理器在执行完被调用函数的代码时，返冋母函数。这个协作过程如图2.1.1所示。

如果把计算机看成一个有条不紊的1:厂，我们可以得到如下类比。

CPU是完成工作的工人。
数据区、堆区、栈区等则是用来存放原料、半成品、成品等各种东西的场所。
存在代码区的指令则告诉CPU要做什么，怎么做，到哪里去领原材料，用什么工具来做，做完以后把成品放到哪个货舱去。
值得一提的是，栈除了扮演存放原料、半成品的仓库之外，它还是车间调度主任的办公室。

程序中所使用的缓冲区可以是堆区、栈区和存放静态变景的数据区。缓冲区溢出的利用方法和缓冲区到底属于上面哪个内存区域密不可分。

2、栈与系统栈

从计算机科学的角度来看，栈指的是一种数据结构，是一种先进后出的数据表。栈的最常见操作有两种：压栈（PUSH)、弹栈（POP):用于标识栈的属性也有两个：栈顶（TOP)、栈底（BASE)。

可以把栈想象成一摞扑克牌。

PUSH：为栈增加一个元素的操作叫做PUSH，相当于在这摞扑克牌的最上面再放上—张。
POP：从栈中取出一个元素的操作叫做POP，相当于从这摞扑克牌取出最上面的一张。
TOP：标识栈顶位置，并且是动态变化的。每做一次PUSH操作，它都会自增1；相反，每做一次POP操作，它会自减1。栈顶元素相当于扑克牌最上面一张，只有这张牌的花色是当前可以看到的。
BASE：标识栈底位置，它记录着扑克牌最下面一张的位置。BASE用于防止栈空后继续弹栈（牌发完时就不能再去揭牌了）。很明显，一般情况下，BASE是不会变动的。

内存的栈区实际上指的就是系统栈。系统栈由系统自动维护，它用于实现高级语言中函数的调用。对于类似C语言这样的高级语言，系统栈的PUSH、POP等堆栈平衡细节是透明的。

—般说来，只有在使用汇编语言开发程序的时候，才需要和它直接打交道。

好，下面重点部分来了。

【文章福利】需要C/C Linux服务器架构师学习资料加群812855908（资料包括C/C ，Linux，golang技术，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK，ffmpeg等）

3、函数调用时发生了什么

我们下面就来探究一下高级语言中函数的调用和递归等性质是怎样通过系统栈巧妙实现的。请看如下代码：

int func_B(int arg_B1, int arg_B2) { int var_B1; int var_B2; var_B1 = arg_B1 arg_B2; var_B2 = arg_B1 - arg_B2; return var_B1 * var_B2; } int func_A(int arg_A1, int arg_A2) { int var_A; var_A = func_B(arg_A1, arg_A2) arg_A1; return var_A; } int main(int argc, char** argv, char** envp) { int var_main; var_main = func_A(3, 4); return 0; }

这段代码经过编译器编译后，各个函数对应的机器指令在代码区中可能是这样分布的，如图2.1.2所示：

根据操作系统的不问、编译器和编译选项的不同，同一文件不同函数的代码在内存代码区中的分布可能相邻，也可能相离甚远，可能先后有序，也可能无序；但它们都在同一个PE文件的代码所映射的一个“节”里。我们可以简单地把它们在内存代码区中的分布位置理解成是散乱无关的。

当CPU在执行调用func_A函数的时候，会从代码区中main函数对应的机器指令的区域跳转到func_A函数对应的机器指令区域，在那里取指并执行；当函数执行完闭，需要返会的时候，又会跳回到main函数对应的指令区域，紧接着调用func_A后面的指令继续执行main函数的代码。在这个过程中，CPU的取指轨迹如图2.1.3所示。

那么CPU是怎么知道要去func_A的代码区取指，在执行完func_A后又是怎么知道跳回到main函数(而不是func_B的代码区)的呢？这些跳转地址我们在C语言中并没有直接说明，CPU是从哪里获得这些函数的调用及返回的信息的呢？

原来，这些代码区中精确的跳转都是在与系统栈巧妙地配台过程中完成的。当函数被调用时，系统栈会为这个函数开辟一个新的栈帧，并把它压入栈中。这个栈帧中的内存空间被它所属的函数独占，正常情况下是不会和别的函数共享的。当函数返回时，系统栈会弹出该函数所对应的栈帧。

如图2.1.4所示，在函数调用的过程中，伴随的系统栈中的操作如下。

在main函数中调用func_A的时候，首先在自己的栈帧中压入函数返回地址，然后为func_A创建新栈帧并压入系统栈。
在func__A调用func_B的时候，同样先在自己的栈帧中压入函数返回地址，然后为func_B创建新栈帧并压入系统栈。
在func_B返回时，func_B的栈帧被弹出系统栈，func_A栈帧中的返回地址被“露”在栈顶，此时处理器按照这个返回地址重新跳到func_A代码区中执行。
在func_A返同时，func_A的栈帧被弹出系统栈．macn函数栈帧中的返回地址被“露” 在栈顶，此时处理器按照这个返回地址跳到main函数代码区中执行。

4、寄存器与函数栈帧

每一个函数独占自己的栈帧空间。当前正在运行的函数的栈帧总是在栈顶。CPU系统提供两个特殊的寄存器用于标识位于系统栈顶端的栈帧。

(1) ESP：栈指针寄存器(extended stack pointer)，其内存放着一个指针，该指针永远指向系统栈地上面-个栈帧的栈顶。

(2) EBP：基址指针寄存器(extended base pointer)-其内存放着一个指针，该指针永远指向系统栈展上面一个栈帧的底部。

注意：EBP指向当前位于系统栈最上边一个栈帧的底部，而不是系统栈的底部。严格说来，“栈帧底部”和“栈底”是不同的概念，本文在叙述中将坚特使用“栈帧底部”这一提法以示区别；ESP所指的栈帧顶部和系统栈的顶部是同一个位置，所以后面叙述中并不严格区分“栈帧顶部”和“栈顶”的概念。请您注意这里的差异，不要产生概念混淆。

寄存器对栈帧的标识作用如图2.1.5所示

函数栈帧：ESP和EBP之间的内存空间为当前栈帧．EBP标识了当前栈帧的底部．ESP 标识了当前栈帧的顶部。

在函数栈帧中，一般包含以下几类重要信息。

(1) 局部变量：为函数局部变量开辟的内存空间。

(2)栈帧状态值：保存前栈帧的顶部和底部（实际上只保存前栈帧的底部，前栈帧的顶部可以通过堆栈平衡计算得到），用于在本帧被弹出后恢复出上一个栈帧。

(3) 函数返回地址：保存当前函数调用前的“断点”信息，也就是函数调用前的指令位置，以便在函数返回时能够恢复到函数被调用前的代码区中继续执行指令。

除了与栈相关的寄存器外，您还需要记住另一个至关重要的寄存器。

EIP：指令寄存器(Extended Instruction Pointer)，其内存放着一个指针，该指针永远指向下一条等待执行的指令地址，可以说如果控制了EIP寄存器的内容，就控制了进程——我们让EIP指向哪里，CPU就会去执行哪里的指令。

5、函数调用约定与相关指令

函数调用约定描述了函数传递参数方式和栈协同工作的技术细节。不同的操作系统、不同的语言、不同的编译器在实现函数调用时的原理虽然基本相同，但具体的调用约定还是有差别的。这包括参数传递方式，参数入栈顺序是从右向左还是从左向古，函数返回时恢复堆栈平衡的操作在子函数中进行还是在母函数中进行。表2-1-1列出了几种调用方式之间的差异。

具体的，对于Visual C 来说，可支持以下3中函数调用约定，如表2-1-2所示：

如果要明确使用某一种调用约定，只需要在函数前加上调用约定的声明即可，否则默认情况下会使用__cdecl的调用方式。

除了上边的参数入栈方向和恢复栈平衡操作位置的不同之外，参数传递有时也会有所不同。例如，每一个c 类成员函数都有一个this指针，在Wndows平台中，这个指针一般是用ECX寄存器来传递的，但如果用GCC编译器编译，这个指针会作为最后一个参数压入栈中。注意：同一段代码用不同的编译选项、不同的编译器编译链接后，得到的可执行文件会有很多不同。

函数调用大致包括以下几个步骤．

(l) 参数入栈：将参数从右向左依次压入系统栈中。

(2)返回地址入栈：将当前代码区调用指令的下一条指令地址压入栈中，供函数返回时继续执行。

(3) 代码区跳转：处理器从当前代码区跳转到被调用函数的入口处。

(4)栈帧调整：具体包括。

保存当前栈帧状态值，已备后面恢复本栈帧时使用（EBP入栈）：

将当前栈帧切换到新栈帧（将ESP值装入EBP．更新栈帧底部）：

给新栈帧分配空间（把ESP减去所需空间的大小，抬高栈顶）：

对于__stdcall调用约定，函数调用时用到的指令序列大致如下。