呼叫堆叠

呼叫堆叠（英语：Call stack，港台称“呼叫堆叠”）别称有：执行栈（execution stack）、控制栈（control stack）、运行时栈（run-time stack）与机器栈（machine stack），是电脑科学中存储有关正在执行的子程式的讯息的堆叠。英文有时直接简称“栈”（the stack），但堆叠中不一定仅存储子程式讯息。几乎所有电脑程式都依赖于呼叫堆叠，而高阶语言一般将呼叫堆叠的细节隐藏至后台。

呼叫堆叠最经常被用于存放子程式的返回位址。在呼叫任何子程式时，主程式都必须暂存子程式执行完毕后应该返回到的位址。因此，如果被呼叫的子程式还要呼叫其他的子程式，其自身的返回位址就必须存入呼叫堆叠，在其自身执行完毕后再行取回。在递回程式中，每一层次递回都必须在呼叫堆叠上增加一条位址，因此如果程式出现无限递回（或仅仅是过多的递回层次），呼叫堆叠就会产生堆叠溢位。

功能[编辑]

呼叫堆叠的主要功能是存放返回位址。除此之外，呼叫堆叠还用于存放：

本地变数：子程式的变数可以存入呼叫堆叠，这样可以达到不同子程式间变数分离开的作用。
参数传递：如果暂存器不足以容纳子程式的参数，可以在呼叫堆叠上存入参数。
环境传递：有些语言（如Pascal与Ada）支援“多层子程式”，即子程式中可以利用主程式的本地变数。这些变数可以通过呼叫堆叠传入子程式。

实例[编辑]

组合语言[编辑]

以下MIPS 组合语言程式计算 $3^{2}+4^{2}$ ，并将结果存至暂存器s0。

main:
    li      $a0, 3
    li      $a1, 4
    jal     sumsq
    move    $s0, $v0
    j       mainend
sumsq:
    addi    $sp, $sp, -4        # 在堆疊上分配空間
    sw      $ra, 0($sp)         # 將sumsq的返回位址存入堆疊中
    jal     square
    move    $t0, $v0
    move    $a0, $a1
    jal     square
    add     $v0, $v0, $t0
    lw      $ra, 0($sp)         # 從堆疊中取回sumsq的返回位址
    addi    $sp, $sp, 4         # 釋出堆疊上分配的空間
    jr      $ra
square:
    mult    $a0, $a0
    mflo    $v0
    jr      $ra
mainend:

这里，主程式（main）呼叫“sumsq”子程式并将返回位址存入暂存器ra，但是“sumsq”子程式需要呼叫“square”子程式。为保证sumsq的返回位址不被重写，这个位址被存储在堆叠中。在square子程式返回后，sumsq再从堆叠中取回其自身的返回位址。

安全性[编辑]

在较底层语言（如组合语言与C语言中），程式控制讯息与资料可能一同被存入呼叫堆叠中，因此造成安全隐患，可能允许恶意程式通过栈缓冲区溢出（stack buffer overflow）来获取程式的控制权。

参见[编辑]