调用堆栈（英語：Call stack，台湾稱呼叫堆疊）别称有：执行栈（execution stack）、控制栈（control stack）、运行时栈（run-time stack）与机器栈（machine stack），是電腦科學中存儲有關正在執行的子程式的訊息的堆疊。英文有時直接简称“栈”（the stack），但堆疊中不一定僅存儲子程式訊息。幾乎所有電腦程式都依賴於呼叫堆疊，而高階語言一般將呼叫堆疊的細節隱藏至後台。
呼叫堆疊最經常被用於存放子程式的返回位址。在呼叫任何子程式時，主程式都必須暫存子程式執行完畢後應該返回到的位址。因此，如果被呼叫的子程式還要呼叫其他的子程式，其自身的返回位址就必須存入呼叫堆疊，在其自身執行完畢後再行取回。在遞迴程式中，每一層次遞迴都必須在呼叫堆疊上增加一條位址，因此如果程式出現無限遞迴（或僅僅是過多的遞迴層次），呼叫堆疊就會產生堆疊溢位。
功能
编辑呼叫堆疊的主要功能是存放返回位址。除此之外，呼叫堆疊還用於存放：
结构
编辑
调用栈由栈帧（stack frame）组成，它们也叫做“活跃（activation）记录”或“活跃帧”。它们是机器依赖并且ABI依赖的数据结构，包含了子例程状态信息。每个栈帧对应于一个子例程的仍未通过返回来完成的一次调用[1]。在堆栈顶部的栈帧对应当前执行例程。例如，一个叫做DrawLine的子例程当前正在运行，它被子例程DrawSquare所调用，右侧图示中给出了调用栈的顶部状况。
栈指针与帧指针
编辑不同函数在栈上分配的栈帧大小通常不同，这取决于局部变量、保存寄存器以及对齐需求。因此，在函数调用和返回过程中，栈指针，通常不会按固定步长或固定规律变化。注意，在某些x86调用约定或编译选项下，并不会保留帧指针。在采用帧指针的调用约定中，每个函数通常会使用一个专用寄存器作为栈帧基准，如x86架构的EBP或RBP。函数入口时会保存上一层帧指针，并将当前栈指针复制到帧指针中，函数返回时再恢复该帧指针[2]。
栈指针可以通过处理器指令显式修改，例如直接调整栈指针以分配栈空间，或通过入栈、出栈等操作间接改变。在栈向低地址增长的调用栈中，某个栈帧内其他局部的位置通常可用帧指针的偏移量来表示，在保留帧指针的x86调用约定中，局部变量的位置通常可表示为相对于帧指针（如 RBP）的负偏移量。
控制链接
编辑在大多数系统的栈帧中，拥有叫做“控制链接”或“动态链接”的字段，它包含帧指针寄存器以前的值，这个值指向了调用者的栈帧，调用约定在被调用者返回之前通过它将帧指针复原到调用者的栈帧。这个字段存储在栈帧的已知位置通常为首位之上，从而确使这个例程的代码可以连续地访问在当前执行例程的栈帧之下的每个栈帧，比如LISP中以符号为键访问栈帧中的关联列表。
交叠
编辑从调用者传递给被调用者的参数值所在区域，在调用约定要求在调用结束时清理参数值的责任由被调用者实行的情况下，可以自然地视为处在被调用者栈帧之中；如果在调用结束时清理参数值的责任由调用者实行，这个区域也可以视为是处在被调用者的栈帧和它的调用者的栈帧之间的交叠（overlap）区域。在入栈指令自动递增栈指针所指地址的调用栈中，调用者传递给被调用者的参数值的位置定义为，相对于被调用者帧指针即下面最近帧的顶部的负数偏移量。在x86架构的调用约定下它们定义为，相对于被调用者帧指针RBP的正数偏移量。
在一些环境中，调用者将每个实际参数（argument）压入堆栈之上，从而扩展了它自己栈帧，接着调用被调用者。在其他的环境中，调用者在它的栈帧的顶部有一个预先分配的区域，用来持有它要提供给其所调用的子例程的实际参数。这个区域有时称为“出去（outgoing）实参区域”或“调出（callout）区域”，可以对应ALGOL 60的术语拟制块。在这种途径下，由编译器计算出的这个区域的大小应当满足任何被调用的子例程的最大所需。
静态链接
编辑支持嵌套子例程的编程语言在调用帧中还拥有一个字段，它指向最近的封装这个被调用者的过程的“最新”活跃的栈帧，也就是这个被调用者在词法上的直接静态作用域。递归的内部例程为每次调用创建单独的调用栈帧，在这种情况下，所有内部例程的这个链接都指向相同的外部例程上下文。这个链接在动态和递归调用期间追踪了静态嵌套，它被称为“静态链接”或“下栈（downstack）链接”。
连续地凭借静态链接可以访问在所有嵌套层级上封装它的诸例程的局部数据，故而它也被称为“访问链接”。在内层函数不访问在封装中的任何非常量的局部数据的时候，访问链接可以被优化掉，因为在这种情况比如纯函数下，只通过实际参数和返回值来通信。
还有一种策略不再只提供到直接包围者的静态链接，转而将到包围诸静态栈帧的诸引用搜集进入叫做“展示”（display）的一个指针数组之中，它们是用来定位想要的栈帧的索引。采用了展示的架构，由于为每个包围层级都存储一个链接，访问浅层数据的深层嵌套例程不需要遍历多个静态链接[3]。一些历史上的计算机比如Burroughs大型系统有特殊的展示寄存器用来支持直到32层的静态嵌套。
一个例程的展示通常位于其自己的栈帧之中，展示项目指示包含作用域，它们从适合作为其前缀的调用者展示获得而来。一个例程的词法嵌套深度是一个已知常量，所以这个例程的展示的大小是固定的。还有由于要遍历哪些包含作用域是已知的，进入这个展示的索引也是固定的。针对最现代机器比如无处不在的x86处理器，编译器及其优化方案在有需要的时候，可以简单的在栈帧上为到所访问包围层级的这些指针预留一些字。
栈解绕
编辑
从被调用函数返回会弹出堆栈的顶部帧，并可能留下返回的一个值。更一般性的动作是从堆栈弹出一个或多个帧，从而恢复在程序中其它某处的执行，这叫做栈解绕（unwind），并且在使用了非局部控制结构的时候必须进行，比如例外处理。在这种情况下，一个函数的栈帧包含了指定例外处理器的一个或多个入口（entry）。在一个例外被抛出的时候，堆栈被解绕直到找到了准备处理（接住）这个抛出例外类型的一个处理器。
一些语言有要求一般性解绕的其他控制结构。Pascal允许使用全局性的goto语句，将控制从嵌套的函数传送出来并进入此前调用的外面的函数。这个操作要求堆栈被解绕，为了恢复正确的上下文，从而将控制传送给包围它的外面函数中的目标语句，需要移除多少栈帧就移除多少。与之类似，C语言有setjmp与longjmp函数充当非局部跳转，它们分别保存和恢复：栈指针、程序计数器、由被调用者保存的寄存器和ABI要求的任何其他内部状态。在编写可移植的C++代码之时，不应信赖执行非局部跳转会发生正常的堆栈解绕来进行所要的清理动作。
Common Lisp允许通过使用unwind-protect特殊算子，控制在堆栈被解绕时都要做些什么。在支持续体的编程语言比如Scheme和新泽西Standard ML中，在应用续体的时候，堆栈在逻辑上被解绕并重绕（rewind）上这个续体的堆栈，接着盘绕（wind）上要传递的那一个值。实现续体可以采用多种策略，例如通过使用多个显式的堆栈，应用一个续体可以简单的停用或舍弃当前堆栈并激活这个续体的堆栈。Scheme语言提供了对续体调用进行“保护”的dynamic-wind，只要控制离开或进入它所界定范围，包括通过应用续体这种非局部跳转方式，在分别对控制栈“解绕”或“重绕”的特定点上，都会执行任意指定的thunk。
在支持续体的编程语言和执行栈可以在运行时检查并修改的编程语言比如Smalltalk和Cilk中，在必须支持续体的时候，一个函数的局部变量在这个函数返回时不能被销毁：一个保存了的续体可以在往后时重入（re-enter）这个函数，并且不仅期望其中的变量不变动，而且期望整个调用序列的栈帧都存在使得这个函数能再次返回。要解决这个问题，栈帧可以在父指针树结构中动态分配，并在不再有续体引用的时候，将其留作垃圾回收。这种类型的结构还解决了上行和下行的函数参数问题，因为在这种基底上很容易实现头等词法闭包。由栈帧链接起来而实现的这种实际运行栈，也被称为“面条式堆栈”[4]，它包含了变量绑定和其他环境特征。
安全性
编辑在較底層語言（如組合語言與C語言中），程式控制訊息與資料可能一同被存入呼叫堆疊中，因此造成安全隱患，可能允許惡意程式通過栈缓冲区溢出（stack buffer overflow）來獲取程式的控制權。
參見
编辑引用
编辑- ^ Examining the Stack. University of Utah. [April 3, 2025]. （原始内容存档于September 12, 2019）.
- ^ Understanding the Stack. cs.umd.edu. 2003-06-22 [2014-05-21]. （原始内容存档于2013-02-25）.
- ^ Alternative Microprocessor Design
- ^ Clinger, W.; Hartheimer, A.; Ost, E. Implementation strategies for continuations. Proceedings of the 1988 ACM conference on LISP and functional programming - LFP '88. 1988: 124–131. ISBN 089791273X. doi:10.1145/62678.62692.
The spaghetti stack used in Interlisp is a variation of the gc strategy [Bobrow 73].
延伸阅读
编辑- Dijkstra, E. W. Recursive Programming. Numerische Mathematik. 1960, 2 (1): 312–318. doi:10.1007/BF01386232.
- Wilson, P. R.; Johnstone, M. S.; Neely, M.; Boles, D. Dynamic storage allocation: A survey and critical review. Memory Management. Lecture Notes in Computer Science 986. 1995: 1–116. CiteSeerX 10.1.1.47.275
. ISBN 978-3-540-60368-9. doi:10.1007/3-540-60368-9_19.
