调用栈是一种运行时数据结构,用于记录函数、过程和方法等子程序尚未结束的调用。它通常遵循栈的后进先出规则:当一个函数调用另一个函数时,新调用的信息会被加入栈中;当该调用返回时,其信息会被移除,调用方则继续执行。每次调用都由一个栈帧表示,栈帧也称为活动记录。调用栈支持嵌套调用、局部执行状态和递归,但其物理表示方式因处理器、编程语言和运行时系统而异。
调用栈的工作原理
假设有三个函数,main 调用 parse,而 parse 又调用 read_token。当 read_token 正在执行时,概念上的调用栈如下:
栈顶: read_token 的栈帧 ← 当前正在执行
parse 的栈帧
栈底: main 的栈帧
parse 的这次调用在等待 read_token 返回期间仍处于活动状态。同样,main 在等待 parse 时也仍处于活动状态。因此,栈帧表示的是一次已经开始但尚未完成的调用,而不一定是当前正在执行指令的函数。
一次常规调用通常经历以下步骤:
- 调用方准备参数,并保存必须保留的状态。
- 执行控制权转移到被调用的函数,即被调用方。
- 被调用方建立本次调用所需的状态。
- 被调用方计算结果,其间可能继续调用其他函数。
- 返回时,释放被调用方的栈帧,按需恢复已保存的状态,并从调用方的返回点继续执行。
这些操作实现了程序控制流的一部分。调用方和被调用方具体如何分担这些操作,由调用约定和生成的代码决定;它们并不对应一套通用的处理器指令序列。
调用栈记录的是尚未完成的调用链,而不是完整的执行历史。一次普通调用返回后,其栈帧通常就无法再作为该次调用的记录使用。
栈帧
栈帧包含与某次调用相关的信息,或提供访问这些信息的途径。具体取决于实现,这些信息可能包括:
| 组成部分 | 用途 |
|---|---|
| 返回地址 | 标识应从调用方的哪个位置继续执行 |
| 参数 | 向被调用方提供输入值或引用 |
| 局部变量 | 存储属于本次调用的值 |
| 保存的寄存器 | 保留调用结束后仍需要的处理器状态 |
| 临时值 | 存放中间结果以及从寄存器溢出到内存的值 |
| 栈帧链接 | 帮助定位调用方的栈帧 |
| 对齐与管理数据 | 满足平台和运行时的要求 |
并非所有组成部分都必须存储在栈内存中。参数和返回值经常通过处理器寄存器传递。返回地址最初可能位于链接寄存器中,而某些局部变量可能始终保存在寄存器中,或在优化过程中被消除。
编译器通常会生成用于建立栈帧的函数序言,以及用于拆除栈帧的函数尾声。简单函数可能只需要很少的显式栈帧设置操作,甚至完全不需要。
栈指针与帧指针
栈指针指示机器栈活动端附近的一个位置。分配或释放栈空间通常涉及调整这个寄存器。有些平台的栈向较低的内存地址增长;另一些平台则采用不同的安排。“栈顶”描述的是逻辑位置,并不意味着其地址一定更高。
在使用帧指针时,它提供一个稳定的参照位置,用于定位函数保存的状态和局部存储。当栈指针在执行过程中发生变化时,帧指针会很有用。编译器也可能省略帧指针,以腾出一个寄存器,转而使用相对于栈指针的寻址方式和栈展开元数据。
应用二进制接口规定了相关约定,包括寄存器的使用、参数的放置、栈对齐以及状态保存义务。因此,不存在所有平台通用的栈帧布局。
物理表示与逻辑表示
调用栈是一种执行模型,不一定对应一块连续的内存。
在许多原生程序中,每个线程都有一个在操作系统支持下管理的栈区域。因此,同一进程中的多个线程即使共享其他内存,也可以各自拥有不同的活动调用链。
运行时系统也可以采用分段栈、可增长栈、在堆上分配的栈帧,或这些表示方式的组合。解释器可以将语言层面的栈帧与实现解释器所用的原生调用分开维护。虚拟机同样可以区分虚拟栈帧与底层机器栈帧。
优化还可能进一步使逻辑调用与物理栈帧分离:
- 内联将函数体并入调用方,因此可能不存在独立的机器调用或栈帧。
- 尾调用优化可以用另一次调用替换当前调用,而不是同时保留两者。
- 寄存器分配可以使局部值保存在栈内存之外。
- 当执行必须退回到优化程度较低的形式时,运行时优化机制可以重建逻辑栈帧。
因此,源代码层面的调用数量并不总是等于物理栈帧的数量。
调用栈与其他存储的区别
调用栈不同于栈这一抽象数据类型;后者还可以用于表达式解析或图遍历等无关任务。
调用栈也不同于堆,堆是用于存放动态管理对象的存储区域。与栈关联的存储通常随调用的生命周期分配和释放,而堆对象可以在创建它的函数结束后继续存在。这并不意味着源语言中的变量必须遵循某种绝对的存储规则:编译器和运行时可以在保持程序语义不变的前提下,选择不同的存储位置。
在某些虚拟机中,操作数栈保存指令使用的值。即使每个调用帧都包含自己的操作数栈,操作数栈与调用栈的作用也不同。
递归与空间使用
递归要求为同一函数中执行时段相互重叠的多次调用分别保存执行状态。例如:
factorial(n):
if n <= 1:
return 1
return n * factorial(n - 1)
当 factorial(4) 等待 factorial(3) 时,它必须保留足够的信息,以便稍后完成乘法。每深入一层调用,就会多出一次尚未结束的调用。
如果最大活动调用深度为 ,每个栈帧约占 字节,那么栈存储空间大致为
实际栈帧的大小可能各不相同,因此更一般的表达式是
其中不计额外的运行时开销。因此,调用深度会影响算法的空间复杂度。递归遍历所使用的存储空间可能与树的高度成正比,即使其源代码中没有显式的栈。
尾调用
当调用方无需进一步计算,就能直接返回被调用方的结果时,这次调用就是尾调用。通过尾调用优化,实现可以复用或替换调用方的栈帧,而不必保留它。
上面的阶乘示例并不是直接的尾递归,因为递归调用返回后仍需进行乘法运算。使用累加器的版本则可以将递归调用置于尾位置。
尾调用是否只使用常量大小的栈空间,取决于语言的保证及具体实现。源程序采用尾递归,并不自动意味着它在所有运行时中的栈使用量都有固定上限。
返回、异常与栈展开
普通返回每次只结束一次调用。异常处理则可能越过多个调用方,将控制权转移到匹配的处理程序。
退出中间各个栈帧的过程称为栈展开。根据语言语义,这个过程可能涉及:
- 查找适用的处理程序。
- 执行清理操作。
- 销毁生命周期受作用域约束的对象。
- 恢复寄存器和栈的状态。
- 将控制权转移到处理程序。
因此,栈展开并不一定等同于将栈指针直接移回先前的位置。某些非局部控制转移机制会跳过普通语言异常本应执行的清理操作。
即使栈帧没有显式的帧指针链,栈展开元数据也可以描述如何恢复已保存的状态。
调试与栈追踪
栈追踪也称为回溯,用于展示一系列尚未结束的调用。调试器、崩溃报告工具和性能分析工具利用它来显示执行是如何到达某个特定位置的。
栈追踪可以包含函数名、源文件、行号和指令地址。其准确性和详细程度取决于可用的符号、调试信息、栈展开元数据,以及程序内存是否完好。
优化后的执行会使解读更加复杂。内联函数可能以重建的逻辑栈帧形式出现,而通过尾调用进入的函数可能不出现在物理栈中。局部变量可能无法查看,因为它们已被优化掉,或者其值已不再位于可恢复的位置。
在具有垃圾回收机制的运行时中,栈帧和寄存器还可能持有使对象保持可达的引用。回收器必须使用适合该运行时的机制来识别这些引用,例如栈映射或保守扫描。
异步执行与协程
同步调用栈不一定能保留异步执行的完整因果历史。
例如,一个函数可能在注册回调后就返回。当事件循环稍后调用该回调时,原函数的栈帧已不再处于活动状态。该回调属于之后的一段执行序列,而不是一条持续嵌套的调用链。
协程可以挂起,并在稍后恢复。不同实现以不同方式保存挂起状态:
- 有栈协程保留一个栈,或一种与嵌套调用等价的表示。
- 无栈协程通常将挂起状态保存在对象或转换后的状态机中,而不是保留整个原生调用栈。
开发工具可以通过关联调度和挂起信息,构建异步栈追踪。这些追踪描述的是不同执行片段之间的逻辑因果关系,而不仅仅是当前的物理栈。
限制与安全
当执行所需的栈存储超出可用容量时,就会发生栈溢出。原因包括递归过深、在栈上分配的对象过大,以及调用链的深度超出预期。运行时可能会报告错误、抛出异常或终止执行,具体取决于平台和当时的情况。
使用虚拟内存的系统通常会设置不可访问的保护区域,以检测某些试图越过栈边界继续增长的操作。这类保护并不意味着栈容量没有上限。
栈溢出不同于缓冲区溢出。前者是耗尽栈容量;后者则是向缓冲区边界之外写入数据。涉及栈上数据的缓冲区溢出可能破坏局部值、保存的寄存器内容或返回地址,从而造成安全漏洞。
防御措施包括栈金丝雀、边界检查、不可执行内存、地址随机化,以及单独保存返回地址记录的受保护影子栈。这些机制针对的是不同的失效方式:仅保护返回地址,本身并不能防止其他数据遭到破坏,也不能防止栈空间耗尽。