程序與執行時堆疊 (Procedures & the Run-Time Stack)

Overview Table

3.7 程序 (Procedures) 概觀 (p.274-275)

Procedure(程序)是軟體的關鍵抽象:把實作某功能的程式碼包裝起來,配上指定的引數 (arguments) 與可選的回傳值 (return value),在程式各處呼叫。不同語言叫法不同(function、method、subroutine、handler),機器層級支援都涉及同一組機制。設 P 呼叫 Q,Q 執行後返回 P:

• Passing control(控制傳遞):進入 Q 時 PC 設為 Q 的起始位址;返回時 PC 設為 P 中 call 之後的那條指令。
• Passing data(資料傳遞):P 提供參數給 Q;Q 回傳值給 P。
• Allocating/deallocating memory(記憶體配置/釋放):Q 可能需要為區域變數配置空間,返回前釋放。

3.7.1 Run-Time Stack(執行時堆疊)(p.275-277)

C 的呼叫機制利用 stack 的 LIFO(last-in, first-out) 紀律:Q 執行時,P 與呼叫鏈上的所有程序都暫停 (suspended),只有 Q 需要配置新空間;Q 返回時其區域儲存即可全部釋放——正好符合 stack 的配置/釋放順序。

• x86-64 stack 向低位址成長;%rsp 永遠指向 stack top(最頂元素)。
• pushq / popq 存取資料;遞減 %rsp = 配置空間、遞增 %rsp = 釋放空間(無初始值的空間直接減指標即可)。
• 程序在暫存器放不下的儲存需求,配置在 stack 上,該區域稱為此程序的 stack frame(堆疊框架)。
• return address 屬於呼叫者 P 的 frame(它保存的是 P 的狀態)。
• 多數程序的 frame 為固定大小,在程序開頭一次配置;變動大小 frame 見 3.10.5(alloca / 變長陣列)。

        Stack "bottom"(高位址)
  +---------------------------+
  |      Earlier frames       |
  +---------------------------+ ---
  |        Argument n         |  |
  |           ...             |  |  Frame for
  |        Argument 7         |  |  calling function P
  +---------------------------+  |
  |      Return address       | ---   <- call 時 push
  +---------------------------+ ---
  |      Saved registers      |  |
  +---------------------------+  |  Frame for
  |      Local variables      |  |  executing function Q
  +---------------------------+  |
  |    Argument build area    |  |   <- Q 呼叫 >6 引數函式時用
  +---------------------------+ ---
  %rsp -> Stack "top"(低位址,向下成長)

3.7.2 Control Transfer(控制傳遞)(p.277-280)

call Q 做兩件事:(1) 把 return address A(緊接在 call 之後那條指令的位址)push 上 stack;(2) 把 PC 設為 Q 的起始位址。ret 則 pop 出位址 A 並把 PC 設為 A。

• objdump 反組譯輸出寫作 callq / retq,後綴 q 只是強調 x86-64 版本,兩種寫法可互換。
• 執行效果(以 %rsp 舊值為 R):

call:  R_new = R - 8;  M[R_new] = A(下一條指令位址);  PC = 目標
ret :  PC = M[R];      R_new = R + 8

書中 multstore 範例 (p.278):main 在 0x400563 執行 callq 400540,push 返回位址 0x400568、%rsp 從 0x7fffffffe840 變 0x7fffffffe838;multstore 的 retq pop 出 0x400568 跳回,%rsp 恢復原值。

p.279 的 top/leaf 追蹤範例展現巢狀呼叫:main 呼叫 top(100) → top 算出 x-5=95 後呼叫 leaf(95) → leaf 回傳 97 → top 加倍為 194 回傳給 main。每層 call 使 %rsp 減 8 並在 *%rsp 留下正確返回位址,ret 後 %rsp 逐層復原——stack 保證返回到正確位置。

3.7.3 Data Transfer(資料傳遞)(p.281-283)

x86-64 大多數參數與回傳值透過暫存器傳遞:最多 6 個整數類 (integral,即整數與指標) 引數用暫存器,回傳值放 %rax。暫存器依引數順序固定分配,名稱依運算元大小選用子暫存器:

超過 6 個引數(n > 6)時:

• 呼叫者 P 在自己的 frame 內配置空間存引數 7..n(即「argument build area」),引數 7 在 stack top。
• stack 上傳參時,所有資料大小一律向上取整為 8 的倍數。
• call 之後(return address 已 push),被呼叫者看到的引數 7、8 位於 8(%rsp)、16(%rsp)。

p.283 的 proc 範例(8 個不同大小引數):a1–a3p 用 %rdi %rsi %edx %rcx %r8w %r9(a2p 為指標,佔完整 64-bit 的 %rcx;a3p 為指標,用 %r9),a4(char)在 %rsp+8、a4p 在 %rsp+16;程式依大小選用 addq/addl/addw/addb。注意第 6 行 movl 8(%rsp), %edx 讀 4 bytes,但後續 addb %dl 只用最低 byte。

proc 執行中的 stack(相對 %rsp):
  16 | a4p          (8 bytes)
   8 | a4           (佔 8 bytes,實際只用 1 byte)
   0 | Return address   <- %rsp

3.7.4 Local Storage on the Stack(區域變數放 stack)(p.284-287)

多數程序的區域資料放得進暫存器;必須放記憶體的常見情況有三:

• 暫存器不夠放所有區域資料。
• 對區域變數取位址 &——必須能產生它的記憶體位址(暫存器沒有位址)。
• 區域變數是陣列或結構,須以陣列/結構參照存取(見 03-Machine-Level-Programs/05-Arrays-and-Data-Structures)。

典型做法:subq $N, %rsp 配置、addq $N, %rsp 釋放,對應 Figure 3.25 的 Local variables 區。

caller/swap_add 範例 (p.285):caller 因為要對 arg1、arg2 取 &,以 subq $16, %rsp 配置 16 bytes,arg1 在 offset 0、arg2 在 offset 8;用 leaq 8(%rsp), %rsi 與 movq %rsp, %rdi 產生指標當引數;呼叫完成後從 stack 讀回被交換的值,最後 addq $16, %rsp 釋放。

call_proc 範例 (p.286-287):同時示範「區域變數 + 超額引數」的完整 frame。配置 32 bytes:

call_proc 的 stack frame(相對 %rsp):
  32 | (Return address of call_proc 之上)
  24 | x1 (long, 8B)          31..24
  20 | x2 (int, 4B)           23..20
  18 | x3 (short, 2B)         19..18
  17 | x4 (char, 1B)          17
   8 | Argument 8 = &x4
   0 | Argument 7 = 4          <- %rsp

• &x1..&x4 由 leaq 產生;引數 7、8 存在 offset 0、8。
• call 之後 return address 被 push,proc 端看到引數 7、8 位移各加 8(變成 8、16)。
• 返回後以 movslq/movswl/movsbl 把小型別 sign-extend 讀回計算,最後 addq $32, %rsp 釋放。

3.7.5 Local Storage in Registers(區域值放暫存器)(p.287-289)

暫存器是所有程序共享的單一資源,x86-64 用一套全體(含函式庫)都必須遵守的慣例避免 callee 覆寫 caller 還要用的值:

• push callee-saved 暫存器形成 frame 中的「Saved registers」區。
• pop 順序必須與 push 相反(LIFO)。

p.288 範例 P(x,y) 呼叫 Q 兩次:x 存 %rbp(第一次 call 期間要活)、Q(y) 結果存 %rbx(第二次 call 期間要活);開頭 pushq %rbp; pushq %rbx; subq $8, %rsp(對齊),結尾反序 popq %rbx; popq %rbp。

3.7.6 Recursive Procedures(遞迴程序)(p.289-291)

前述暫存器與 stack 慣例天然支援遞迴:每次呼叫在 stack 上有自己私有的空間(return address、saved registers、必要時的區域變數),多個未完成 (outstanding) 呼叫的區域狀態互不干擾;stack 的配置/釋放順序恰好匹配 call/return 順序。

p.290 遞迴階乘 rfact:

rfact(n):                          呼叫深度示意(n=3):
  pushq %rbx          save         | rfact(3): %rbx=3 |
  movq  %rdi, %rbx    n -> %rbx    | rfact(2): %rbx=2 |
  movl  $1, %eax      result=1     | rfact(1): ret 1  |
  cmpq  $1, %rdi                    每層各有 saved %rbx
  jle   .L35                        與 return address
  leaq  -1(%rdi), %rdi  n-1
  call  rfact
  imulq %rbx, %rax    n * rfact(n-1)
.L35:
  popq  %rbx          restore
  ret

• n 存進 callee-saved 的 %rbx(先 push 保存舊值);遞迴 call 返回後保證:(1) 結果在 %rax,(2) %rbx 仍是本層的 n。
• 遞迴呼叫與一般呼叫完全相同,無特殊機制;同樣適用於互相遞迴 (mutual recursion)(P 呼叫 Q、Q 又呼叫 P)。
• Practice Problem 3.35 型:由 shrq $2, %rdi + addq %rbx, %rax 反推 rfun(x) = x + rfun(x>>2)、終止條件 x == 0 回傳 0。

Exam/Test Patterns

Related Notes

• 03-Machine-Level-Programs/03-Control-Flow — jump/條件分支與 jump table,call/ret 是其延伸
• 03-Machine-Level-Programs/02-Data-Movement-and-Arithmetic — pushq/popq、mov 系列與運算元格式
• 03-Machine-Level-Programs/05-Arrays-and-Data-Structures — 陣列/結構作為區域變數時的 stack 配置
• 03-Machine-Level-Programs/06-Buffer-Overflow-and-Pointer-Safety — stack frame 被溢位攻擊的原理與防禦
• 03-Machine-Level-Programs/01-Program-Encodings-and-Data-Formats — 反組譯輸出(callq/retq)與資料大小後綴
• 08-Exceptional-Control-Flow/06-Nonlocal-Jumps — setjmp/longjmp 跳脫標準 call/return 紀律的例外