作者：楊小華
棧（Stack）：一個(gè)有序的積累或堆積
韋氏詞典
對(duì)每一位孜孜不倦的程序員來(lái)說(shuō)，棧已深深的烙在其腦海中，甚至已經(jīng)發(fā)生變異。?？梢杂脕?lái)傳遞函數(shù)參數(shù)、存儲(chǔ)局部變量、以及存儲(chǔ)返回值的信息、還可以用于保存寄存器的值以供恢復(fù)之用。
在X86平臺(tái)上（又稱之為IA32），應(yīng)用程序借用棧來(lái)支持函數(shù)（又稱為過(guò)程）調(diào)用，變量的存儲(chǔ)按后進(jìn)先出（LIFO）的方式進(jìn)行。
一、 棧幀布局
在具體講解函數(shù)調(diào)用之前，我們先來(lái)明確棧的幾個(gè)概念：滿棧與空棧，升序棧與降序棧。
滿棧是指棧指針指向上次寫(xiě)的最后一個(gè)數(shù)據(jù)單元，而空棧的棧指針指向第一個(gè)空閑單元。一個(gè)降序棧是在內(nèi)存中反向增長(zhǎng)(就是從應(yīng)用程序空間結(jié)束處開(kāi)始反向增長(zhǎng))，而升序棧在內(nèi)存中正向增長(zhǎng)。
RISC機(jī)器使用傳統(tǒng)的滿降序棧(FDFullDescending)。如果使用符合IA32規(guī)定的編譯器，它通常把你的棧指針設(shè)置在應(yīng)用程序空間的結(jié)束處并接著使用一個(gè)滿降序棧。用來(lái)存放一個(gè)函數(shù)的局部變量、參數(shù)、返回地址和其它臨時(shí)變量的棧區(qū)域稱為棧幀（stack frame），如圖1所示。
圖 1 棧幀結(jié)構(gòu)
棧幀布局的設(shè)計(jì)要考慮到指令集的體系結(jié)構(gòu)特征和被編譯的程序設(shè)計(jì)語(yǔ)言的特征。但是，計(jì)算機(jī)的制造者常常規(guī)定一種用于其體系結(jié)構(gòu)的“標(biāo)準(zhǔn)”棧幀布局，以便被所有的程序設(shè)計(jì)語(yǔ)言編譯器采納。這種棧幀布局對(duì)于某些特定的程序設(shè)計(jì)語(yǔ)言或編譯器可能并不是最方便的，但是通過(guò)這種“標(biāo)準(zhǔn)”布局，用不同程序設(shè)計(jì)語(yǔ)言編寫(xiě)的函數(shù)得以相互調(diào)用。
當(dāng)P調(diào)用Q時(shí)，Q的參數(shù)是放在P的幀中的。另外，當(dāng)P調(diào)用Q時(shí)，P中的下一條指令地址將被壓入棧中，形成P的棧幀的末尾，具體可參見(jiàn)圖1，返回地址就是當(dāng)程序從Q返回時(shí)應(yīng)該繼續(xù)執(zhí)行的地方。Q的棧幀從保存幀指針的位置開(kāi)始，后面開(kāi)始保存其他寄存器的值。Q也會(huì)用棧幀來(lái)保存其他不能存放在寄存器中的局部變量。如果函數(shù)要返回整數(shù)或指針的話，常用寄存器%eax來(lái)保存返回值。
當(dāng)程序執(zhí)行時(shí)，棧指針是可以移動(dòng)的，因此大多數(shù)信息的訪問(wèn)都是相對(duì)于幀指針(%ebp)的。
二、 寄存器使用慣例
假設(shè)函數(shù)P（……）調(diào)用函數(shù)Q（a1，……，an），我們稱P是調(diào)用者（caller），Q是被調(diào)用者（callee）。如果必須被調(diào)用者保存和恢復(fù)的寄存器，我們稱之為調(diào)用者保護(hù)的寄存器（caller-save）；如果是被調(diào)用者的責(zé)任，則稱之為被調(diào)用者保護(hù)的寄存器（callee-save）。
程序寄存器組是唯一一個(gè)被所有函數(shù)共享的資源。雖然在給定時(shí)刻只能有一個(gè)函數(shù)是活動(dòng)的，但是我們必須保證當(dāng)一個(gè)函數(shù)調(diào)用另一個(gè)函數(shù)時(shí)，被調(diào)用者不會(huì)覆蓋某個(gè)調(diào)用者稍后會(huì)使用的寄存器的值。
為此，任何一個(gè)平臺(tái)都會(huì)制訂一套標(biāo)準(zhǔn)，讓所有的函數(shù)都必須遵循，包括程序庫(kù)中的函數(shù)。但在大多數(shù)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)中，調(diào)用者保護(hù)的寄存器和被調(diào)用者保護(hù)的寄存器的概念并不是由硬件來(lái)實(shí)現(xiàn)的，而是機(jī)器參考手冊(cè)中規(guī)定的一種約定。
比如，在ARM體系平臺(tái)中，所有的函數(shù)調(diào)用必須遵守ARM 過(guò)程調(diào)用標(biāo)準(zhǔn)(APCS，ARM Procedure CallStandard)。該標(biāo)準(zhǔn)提供了一套緊湊的代碼編寫(xiě)機(jī)制，定義的函數(shù)可以與其他語(yǔ)言編寫(xiě)的函數(shù)交織在一起。其他函數(shù)可以編譯自 C、Pascal、也可以是用匯編語(yǔ)言寫(xiě)成的函數(shù)。
同理，IA32平臺(tái)也采用了一套統(tǒng)一的寄存器使用慣例。根據(jù)慣例，寄存器%eax、%edx、%ecx被劃分為調(diào)用者保存。當(dāng)函數(shù)P（調(diào)用者）調(diào)用Q（被調(diào)用者）時(shí)，Q可以覆蓋這些寄存器的值，而不會(huì)破壞任何P所需要的數(shù)據(jù)。另外，%ebx、%esi、%edi、%ebp被劃分為被調(diào)用者保存，這意味著Q必須在覆蓋他們之前，將這些寄存器的值保存到棧中，并在返回前恢復(fù)他們。
三、 參數(shù)傳遞慣例
大約在1960年之前，參數(shù)傳遞不是通過(guò)棧來(lái)傳遞的，而是通過(guò)一塊靜態(tài)分配的存儲(chǔ)空間來(lái)傳遞的，這種方法阻礙了遞歸函數(shù)的使用。從20世紀(jì)70年代開(kāi)始，大多數(shù)調(diào)用約定函數(shù)參數(shù)的傳遞通過(guò)棧來(lái)實(shí)現(xiàn)（因?yàn)樵L問(wèn)寄存器比訪問(wèn)存儲(chǔ)器要快的多），同時(shí)也會(huì)導(dǎo)致一些不必要的存儲(chǔ)器訪問(wèn)。對(duì)實(shí)際程序的研究表明，很少有函數(shù)的參數(shù)個(gè)數(shù)是超過(guò)4個(gè)，并且極少有6個(gè)的。因此，現(xiàn)代計(jì)算機(jī)中的參數(shù)傳遞約定都規(guī)定，一個(gè)函數(shù)的前k個(gè)參數(shù)（典型的，k=4或者k=6）放在寄存器中傳遞，剩余的參數(shù)則放在存儲(chǔ)器中傳遞。
在ARM體系平臺(tái)中，APCS就明確規(guī)定：
1) 前 4 個(gè)整數(shù)實(shí)參(或者更少!)被裝載到 R0 – R4寄存器中。
2) 前 4 個(gè)浮點(diǎn)實(shí)參(或者更少!)被裝載到 f0 - f3寄存器中。
3) 其他任何實(shí)參(如果有的話)存儲(chǔ)在內(nèi)存中，用進(jìn)入函數(shù)時(shí)緊接在棧指針?biāo)赶虻目臻g。換句話說(shuō)，其余的參數(shù)被壓入棧頂。
但在IA32平臺(tái)上，參數(shù)傳遞不是完全通過(guò)寄存器來(lái)實(shí)現(xiàn)的，而是通過(guò)棧幀來(lái)實(shí)現(xiàn)的。根據(jù)不同的調(diào)用方式，參數(shù)在棧幀的存放方式又有一點(diǎn)差別，區(qū)別如下表所示：
調(diào)用方式
參數(shù)在堆棧里的次序
操作方式
_cdecl
第一個(gè)參數(shù)在低位地址
調(diào)用者
_stdcall
第一個(gè)參數(shù)在低位地址
被調(diào)用者
_fastcall
編譯器指定
被調(diào)用者
_pascal
第一個(gè)參數(shù)在高位地址
被調(diào)用者
Borland 和 GNU 編譯器使用_cdecl 方式,而 Microsoft 使用 _stdcall方式。通過(guò)這里可以發(fā)現(xiàn)，當(dāng)今兩大主流的編譯器，第一個(gè)參數(shù)都在低地址，也就是說(shuō)第一個(gè)參數(shù)是最后一個(gè)壓棧的，當(dāng)被調(diào)用函數(shù)被調(diào)用時(shí)，此時(shí)就賦值給了第一個(gè)形參。
四、 Linux內(nèi)核源碼研究
下面我們以Linux內(nèi)核中斷處理源代碼來(lái)研究函數(shù)調(diào)用的本質(zhì)。本文所提及的內(nèi)核代碼版本為2.6.10，讀者需了解GCC匯編語(yǔ)言的基礎(chǔ)知識(shí)。
當(dāng)某個(gè)中斷發(fā)生后，將會(huì)執(zhí)行push $i-256,jmp common_interrupt指令，此時(shí)將會(huì)跳轉(zhuǎn)到common_interrupt處執(zhí)行。
文件名：arch/i386/kernel/entry.S（說(shuō)明：前面的數(shù)字表示行號(hào)）
359 ALIGN
360 common_interrupt:
361 SAVE_ALL
362 movl %esp,%eax
363 call do_IRQ
364 jmp ret_from_intr
這里主要的操作是宏操作SAVE_ALL，就是所謂的“保存現(xiàn)場(chǎng)”，把中斷發(fā)生前夕所有寄存器的內(nèi)容都保存在堆棧中，待中斷服務(wù)完畢返回之前再來(lái)“恢復(fù)現(xiàn)場(chǎng)”。
文件名：arch/i386/kernel/irq.c
48 fastcall unsigned int do_IRQ(struct pt_regs *regs)
49 {
50 /* high bits used in ret_from_ code */
//取得中斷向量號(hào)
51 int irq = regs->orig_eax & 0xff;
52 #ifdef CONFIG_4KSTACKS
53 union irq_ctx *curctx, *irqctx;
54 u32 *isp;
55 #endif
……
107 }
下面我們來(lái)分析SAVE_ALL和do_IRQ 函數(shù)中的struct pt_regs結(jié)構(gòu)體。
文件名：arch/i386/kernel/entry.S
文件名：include/asm-i386/ptrace.h
84 #define SAVE_ALL \
85 cld; \
86 pushl %es; \
87 pushl %ds; \
88 pushl %eax; \
89 pushl %ebp; \
90 pushl %edi; \
91 pushl %esi; \
92 pushl %edx; \
93 pushl %ecx; \
94 pushl %ebx; \
95 movl $(__USER_DS), %edx; \
96 movl %edx, %ds; \
97 movl %edx, %es;
26 struct pt_regs {
27 long ebx;
28 long ecx;
29 long edx;
30 long esi;
31 long edi;
32 long ebp;
33 long eax;
34 int xds;
35 int xes;
36 long orig_eax;
37 long eip;
38 int xcs;
39 long eflags;
40 long esp;
41 int xss;
42 };
從以上代碼可以看出，SAVE_ALL中，依次將寄存器中的值壓入棧中，其中最后一個(gè)壓入的是pushl %ebx；我們觀察structpt_regs結(jié)構(gòu)體，可以看出該結(jié)構(gòu)體的第一個(gè)成員變量就是long ebx；然后就依次對(duì)應(yīng)。其中l(wèi)ong orig_eax;的所對(duì)應(yīng)的push語(yǔ)句為：push $i-256。是在jmp common_interrupt之前壓入的。細(xì)心的讀者可能還會(huì)產(chǎn)生另外一個(gè)疑問(wèn)： structpt_regs結(jié)構(gòu)體中最后幾個(gè)變量怎么在SAVE_ALL中沒(méi)有對(duì)應(yīng)的push。因?yàn)樵谶M(jìn)入中斷服務(wù)程序之前，已經(jīng)將這部分值壓進(jìn)棧中了，這是由硬件來(lái)完成的。
從以上可以看出，在IA32平臺(tái)上，參數(shù)的傳遞不是通過(guò)寄存器來(lái)實(shí)現(xiàn)的，而是通過(guò)棧幀來(lái)實(shí)現(xiàn)。但這并不是在Linux 操作系統(tǒng)上如此，而是所有的IA32平臺(tái)都是如此，不管是何種操作系統(tǒng)，何種編譯器，都得遵循前面所提及的規(guī)范。
下面我們?nèi)砸灾袛酁槔?，在?nèi)核中調(diào)用者是如何保護(hù)寄存器的。
48 fastcall unsigned int do_IRQ(struct pt_regs *regs)
49 {
……
73 #ifdef CONFIG_4KSTACKS
……
92 asm volatile(
93 " xchgl %%ebx,%%esp \n"
94 " call __do_IRQ \n"
95 " movl %%ebx,%%esp \n"
96 : "=a" (arg1), "=d" (arg2), "=b" (ebx)
97 : "0" (irq), "1" (regs), "2" (isp)
98 : "memory", "cc", "ecx"
99 );
……
101 #endif
上述代碼中的第一個(gè)冒號(hào)表示輸出值，第二個(gè)冒號(hào)表示是輸入值，第三個(gè)冒號(hào)后表示將被破壞的部分，需要恢復(fù)的值。在該段代碼中，將會(huì)調(diào)用__do_IRQ（）函數(shù)，由于在調(diào)用完該函數(shù)后，還會(huì)用到ecx的值，所有需要保存將ecx的值。那么在__do_IRQ（）函數(shù)中就可以毫無(wú)忌憚的使用ecx寄存器。
從上例還可以發(fā)現(xiàn)，函數(shù)的輸出值往往都存貯在寄存器eax中。第一個(gè)冒號(hào)后的"=a" (arg1)表示將變量arg1和eax綁定，也就是arg1 = eax。
五、 案例分析
前不久，筆者在逛CSDN論壇時(shí)，發(fā)現(xiàn)不少人對(duì)如下題目展開(kāi)了激烈的討論。
#include<stdio.h>
low_to_up(char in);
void main()
{
printf("%c\n",low_to_up('d'));
}
low_to_up(char in)
{
char ch;
if(in>='a' && in<='z')
ch=in-'a'+'A';
else
return(ch);
}
我們先在VC++ 6.0中反匯編這段代碼：
1: #include<stdio.h>
2: low_to_up(char in);
3:
4: void main()
5: {
00401020 push ebp
00401021 mov ebp,esp
00401023 sub esp,40h
00401026 push ebx
00401027 push esi
00401028 push edi
00401029 lea edi,[ebp-40h]
0040102C mov ecx,10h
00401031 mov eax,0CCCCCCCCh
00401036 rep stos dword ptr [edi]
6: printf("%c\n",low_to_up('d'));
00401038 push #64h d的ASC碼 (1處)
0040103A call @ILT+5(low_to_up) (0040100a) 此時(shí)把eax的值壓棧，然后調(diào)用printf函數(shù)，所以此時(shí)打印的就是d。
0040103F add esp,4
00401042 push eax # (5處)
00401043 push offset string "%c\n" (0042001c)
00401048 call printf (004010e0)
0040104D add esp,8
7: }
00401050 pop edi
00401051 pop esi
00401052 pop ebx
00401053 add esp,40h
00401056 cmp ebp,esp
00401058 call __chkesp (00401160)
0040105D mov esp,ebp
0040105F pop ebp
00401060 ret
8:
9: low_to_up(char in)
10: {
00401080 push ebp 前一個(gè)棧幀的內(nèi)容
……
64h
返回地址
ebp
(ch)
……
當(dāng)前棧的內(nèi)容
這里的ebp+8的內(nèi)容就是64h，此時(shí)eax就是64。
00401081 mov ebp,esp
00401083 sub esp,44h
00401086 push ebx
00401087 push esi
00401088 push edi
00401089 lea edi,[ebp-44h]
0040108C mov ecx,11h
00401091 mov eax,0CCCCCCCCh
00401096 rep stos dword ptr [edi]
11: char ch;
12: if(in>='a' && in<='z')
00401098 movsx eax,byte ptr [ebp+8] # (2處)
0040109C cmp eax,61h
0040109F jl low_to_up+36h (004010b6)
004010A1 movsx ecx,byte ptr [ebp+8]
004010A5 cmp ecx,7Ah
004010A8 jg low_to_up+36h (004010b6)
此時(shí)的edx是計(jì)算機(jī)后的值，但eax的值仍舊還是沒(méi)有變。然后存儲(chǔ)到ebp-4中，就是ch中。
13: ch=in-'a'+'A';
004010AA movsx edx,byte ptr [ebp+8] # (3處)
004010AE sub edx,20h
004010B1 mov byte ptr [ebp-4],dl
14: else
004010B4 jmp low_to_up+3Ah (004010ba)
15: return(ch);
004010B6 movsx eax,byte ptr [ebp-4]
16: }
004010BA pop edi # 恢復(fù)寄存器的值，做返回處理 (7處)
004010BB pop esi
004010BC pop ebx
004010BD mov esp,ebp
004010BF pop ebp
004010C0 ret
從以上匯編可以看出，被調(diào)用者保存的寄存器在這里體現(xiàn)的酣暢淋漓。在被調(diào)用者函數(shù)中，根本不會(huì)管調(diào)用者保存的寄存器，直接使用。這里還體現(xiàn)了常用eax來(lái)存貯返回值。由于是使用eax做返回值，所以在5處，直接將eax壓棧，所以該程序在VC++6.0中，打印”d”。由于在low_to_up（）函數(shù)中，在比較過(guò)程中借用了eax寄存器。按正常的流程，在執(zhí)行完if語(yǔ)句后，應(yīng)該有一條恰當(dāng)?shù)耐顺稣Z(yǔ)句，所以導(dǎo)致沒(méi)有執(zhí)行7處的匯編語(yǔ)句，把正確的值存儲(chǔ)到eax中。從而陰差陽(yáng)錯(cuò)的，在執(zhí)行printf時(shí)，打印了錯(cuò)誤的值。這有可能是VC++編譯器的bug？
GCC的編譯器似乎技高一籌，表現(xiàn)的更盡人意。下面我們來(lái)分析GCC反匯編后的代碼（閱讀這部分代碼需了解GCC匯編語(yǔ)法）：
.file "csdn.c"
.text
前一個(gè)棧幀的內(nèi)容
……
100
返回地址
ebp
……
esp-> (ch)
……
當(dāng)前棧的內(nèi)容
這里的ebp+8的內(nèi)容就是100，此時(shí)ch被存儲(chǔ)在ebp-8處。
.globl low_to_up .type low_to_up, @function
low_to_up:
pushl %ebp
movl %esp, %ebp
subl $8, %esp
movl 8(%ebp), %eax # (2處)
movb %al, -1(%ebp)
cmpb $96, -1(%ebp)
jle .L2
cmpb $122, -1(%ebp)
jg .L2
movzbl -1(%ebp), %eax
subb $32, %al 此處運(yùn)行完if語(yǔ)句的內(nèi)容，但沒(méi)有往ch里面的賦值
movb %al, -2(%ebp) # (3處)
jmp .L3
.L2:
movsbl -2(%ebp),%eax
movl %eax, -8(%ebp) # (5處)
jmp .L1
.L3:
.L1:
從ch中獲取值，存儲(chǔ)到eax中，然后返回
movl -8(%ebp), %eax # (4處)
leave
ret
.size low_to_up, .-low_to_up
.section .rodata
.LC0:
.string "%c\n"
.text
.globl main
.type main, @function
main:
pushl %ebp
movl %esp, %ebp
subl $8, %esp
andl $-16, %esp
movl $0, %eax
subl %eax, %esp
movl $100, (%esp) #將d的值壓入到棧中，然后調(diào)用low_to_up（）函數(shù) (1處)
call low_to_up
movl %eax, 4(%esp) # (6處)
movl $.LC0, (%esp)
call printf
movl $0, %eax
leave
ret
.size main, .-main
.section .note.GNU-stack,"",@progbits
.ident "GCC: (GNU) 3.3.5 (Debian 1:3.3.5-13)"
從以上代碼可以看出，調(diào)用函數(shù)時(shí)，GCC編譯器和VC++的編譯器所做的處理差不多。但GCC把局部變量ch壓在ebp-8處。然后用ebp-1/ebp-2做臨時(shí)存儲(chǔ)。我們從5處可以發(fā)現(xiàn)，在else語(yǔ)句中，編譯器會(huì)將ebp-2的值壓入到eax中，然后又將eax中的值在壓入到ebp-8處，即ch的棧中。當(dāng)返回時(shí)，會(huì)從ebp-8處取出ch的值，然后賦值給eax，退棧返回。在6處，將eax的值壓棧，然后調(diào)用printf，輸出值。由于在if條件中，并沒(méi)有將值存儲(chǔ)到ch中，所以在low_to_up函數(shù)返回時(shí)，當(dāng)執(zhí)行4處的匯編代碼時(shí)，將ch處的隨機(jī)值放到了eax中，所以該程序在Linux環(huán)境下，輸出值為隨機(jī)值。
筆者猜測(cè)，如果在L3處的加上一段和L2處相同的代碼，那么就可以獲得正確的值。筆者然后就在代碼中的if語(yǔ)句條件中加入了return 語(yǔ)句，GCC反匯編后的代碼驗(yàn)證了筆者的猜測(cè)，代碼如下：
low_to_up:
pushl %ebp
movl %esp, %ebp
subl $8, %esp
movl 8(%ebp), %eax
movb %al, -1(%ebp)
cmpb $96, -1(%ebp)
jle .L2
cmpb $122, -1(%ebp)
jg .L2
movzbl -1(%ebp), %eax
subb $32, %al
movb %al, -2(%ebp)
jmp .L3
.L2:
movsbl -2(%ebp),%eax
movl %eax, -8(%ebp)
jmp .L1
.L3:
movsbl -2(%ebp),%eax
movl %eax, -8(%ebp)
.L1:
movl -8(%ebp), %eax
leave
ret
六、 總結(jié)
綜上所述，當(dāng)我們了解了函數(shù)調(diào)用規(guī)律后，結(jié)合匯編代碼，在實(shí)際項(xiàng)目開(kāi)發(fā)過(guò)程中可以定位一些讓人比較琢磨不透的問(wèn)題。也不要在項(xiàng)目中采用案例中的程序，給項(xiàng)目移植性造成困難。為什么在這個(gè)平臺(tái)下好好的，怎么到了另外一個(gè)平臺(tái)就出錯(cuò)了？
七、 參考文獻(xiàn)
[1] Andrew W.Appel，趙克佳等譯 《現(xiàn)代編譯原理C語(yǔ)言描述》 人民郵電出版社 2006
[2] Randal E.Bryant等，龔奕利等譯 《深入理解計(jì)算機(jī)系統(tǒng)》 中國(guó)電力出版社 2004
[3] Agner Fog，云風(fēng)譯 《怎樣優(yōu)化Pentium系列處理器的代碼》
http://www.codingnow.com/2000/download/cpentopt.htm
[4] Linus Torvalds， Linux內(nèi)核源代碼（2.6.10版本） http://www.kernel.org
