# 第四章 棧 棧在計算科學中是最重要和最基本的數據結構。 嚴格的來說,它只是在x86中被ESP,或x64中被RSP,或ARM中被SP所指向的一段程序內存區域。 ?? ?訪問棧內存,最常使用的指令是PUSH和POP(在x86和ARM Thumb模式中)。 PUSH指令在32位模式下,會將ESP/RSP/SP的值減去4(在64位系統中,會減去8),然后將操作數寫入到ESP/RSP/SP指向的內存地址。 POP是相反的操作運算:從SP指向的內存地址中獲取數據,存入操作數(一般為寄存器), 然后將SP(棧指針)加4(或8)。 ## 4.1 為什么棧反向增長? 按正常思維來說,我們會認為像其它數據結構一樣,棧是正向增長的,比如:棧指針會指向高地址。  我們知道: ????? ?戶核心部分的映像文件被合理的分為三個部分,程度代碼段在內存空閑部分運行。 在運行過程中,這部分是具有寫保護的,所有進程都可以共享訪問這個程序。在內存空間 中,程序text區段開始的8k字節是不能共享的可寫區段,這個?大?小可以使?用系統函數來擴 ?大。在內存?高位地址是可以像硬件指針?自由活動向下增長的棧區段。 ????? ## 4.2 棧可以用來做什么? ### 4.2.1 保存函數返回地址以便在函數執行完成時返回控制權 #### x86 當使用CALL指令去調用一個函數時,CALL后面一條指令的地址會被保存到棧中,使用無條件跳轉指令跳轉到CALL中執行。 ? ?CALL指令等價于PUSH函數返回地址和JMP跳轉。 ``` #!cpp void f() { f(); }; ``` ?MSVC 2008顯示的問題: ``` #!bash c:\tmp6>cl ss.cpp /Fass.asm Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 15.00.21022.08 for 80x86 Copyright (C) Microsoft Corporation. All rights reserved. ss.cpp c:\tmp6\ss.cpp(4) : warning C4717: ’f’ : recursive on all control paths, function will cause runtime stack overflow ``` 但無論如何還是生成了正確的代碼: ``` #!bash ?f@@YAXXZ PROC ; f ; File c:\tmp6\ss.cpp ; Line 2 push ebp mov ebp, esp ; Line 3 call ?f@@YAXXZ ; f ; Line 4 pop ebp ret 0 ?f@@YAXXZ ENDP ; f ``` ??如果我們設置優化(/0x)標識,生成的代碼將不會出現棧溢出,并且會運行的很好。 ``` #!bash ?f@@YAXXZ PROC ; f ; File c:\tmp6\ss.cpp ; Line 2 $LL3@f: ; Line 3 jmp SHORT $LL3@f ?f@@YAXXZ ENDP ; f ``` GCC 4.4.1 在這兩種條件下,會生成同樣的代碼,而且不會有任何警告。 #### ARM ARM程序員經常使用棧來保存返回地址,但有些不同。像是提到的“Hello,World!(2.3), RA保存在LR(鏈接寄存器)。然而,如果需要調用另外一個函數,需要多次使用LR寄存器,它的值會被保存起來。通常會在函數開始的時候保存。像我們經常看到的指令“`PUSH R4-R7, LR`”,在函數結尾處的指令“`POP R4-R7, PC`”,在函數中使?用到的寄存器會被保存到棧中,包括LR。 盡管如此,如果一個函數從未調用其它函數,在ARM專用術語中被叫稱作葉子函數。因此,葉?函數不需要LR寄存器。如果一個函數很小并使用了少量的寄存器,可能不會?到棧。因此,是可以不使用棧而實現調用葉子函數的。在擴展ARM上不使用棧,這樣就會比在x86上運行要快。在未分配棧內存或棧內存不可用的情況下,這種方式是非常有用的。 ### 4.2.2 傳遞函數參數 在x86中,最常見的傳參方式是“cdecl”: ``` #!bash push arg3 push arg2 push arg1 call f add esp, 4*3 ``` 被調用函數通過棧指針訪問函數參數。因此,這就是為什么要在函數f()執行之前將數據放入棧中的原因。  來看一下其它調用約定。沒有意義也沒有必要強迫程序員一定要使用棧來傳遞參數。 這不是必需的,可以不使用棧,通過其它方式來實現。 例如,可以為參數分配一部分堆空間,存入參數,將指向這部分內存的指針存入EAX,這樣就可以了。然而,在x86和ARM中,使用棧傳遞參數還是更加方便的。 另外一個問題,被調用的函數并不知道有多少參數被傳遞進來。有些函數可以傳遞不同個數的參數(如:printf()),通過一些說明性的字符(以%開始)才可以判斷。如果我們這樣調用函數 ``` #!cpp printf("%d %d %d", 1234); ``` `printf()`會傳?入1234,然后另外傳入棧中的兩個隨機數字。這就讓我們使用哪種方式調用 main()函數變得不重要,像`main(),main(int argc, char *argv[])`或`main(int argc, char *argv[], char *envp[])`。 事實上,CRT函數在調?main()函數時,使用了下面的指令: ???? #!bash push envp push argv push argc call main ... ?如果你使用了沒有參數的main()函數,盡管如此,但它們仍然在棧中,只是無法使用。如果你使用了`main(int argc, char *argv[])`,你可以使用兩個參數,第三個參數對你的函數是“不可見的”。如果你使用`main(int argc)`這種方式,同樣是可以正常運?的。 ### 4.2.3 局部變量存放 局部變量存放到任何你想存放的地方,但傳統上來說,大家更喜歡通過將棧指針移動到棧底,來存放局部變量,當然,這不是必需的。 ### 4.2.4 x86: alloca() 函數 對alloca()函數并沒有值得學習的。 該函數的作用像malloc()一樣,但只會在棧上分配內存。 它分配的內存并不需要在函數結束時,調用像free()這樣的函數來釋放,當函數運行結束,ESP的值還原時,這部分內存會自動釋放。對alloca()函數的實現也沒有什么值得介紹的。 這個函數,如果精簡一下,就是將ESP指針指向棧底,根據你所需要的內存大小將ESP指向所分配的內存塊。讓我們試一下: ``` #!cpp #include <malloc.h> #include <stdio.h> void f() { char *buf=(char*)alloca (600); _snprintf (buf, 600, "hi! %d, %d, %d\n", 1, 2, 3); puts (buf); }; ``` (`_snprintf()`函數作用與printf()函數基本相同,不同的地方是printf()會將結果輸出到的標準輸出stdout,?`_snprintf()`會將結果保存到內存中,后面兩?代碼可以使用printf()替換,但我想說明小內存的使用習慣。) #### MSVC 讓我們來編譯 (MSVC 2010): ``` #!bash ... ??????? mov eax, 600 ; 00000258H call __alloca_probe_16 mov esi, esp ??????? push 3 push 2 push 1 push OFFSET $SG2672 push 600 ; 00000258H push esi call __snprintf ??????? push esi call _puts add esp, 28 ; 0000001cH ... ``` ? ??這唯一的函數參數是通過EAX(未使用棧)傳遞。在函數調用結束時,ESP會指向 600字節的內存,我們可以像使用一般內存一樣來使用它做為緩沖區。 #### GCC + Intel格式 GCC 4.4.1不需要調用函數就可以實現相同的功能: ``` #!bash .LC0: .string "hi! %d, %d, %d\n" f: push ebp mov ebp, esp push ebx sub esp, 660 lea ebx, [esp+39] and ebx, -16 ; align pointer by 16-bit border mov DWORD PTR [esp], ebx ; s mov DWORD PTR [esp+20], 3 mov DWORD PTR [esp+16], 2 mov DWORD PTR [esp+12], 1 mov DWORD PTR [esp+8], OFFSET FLAT:.LC0 ; "hi! %d, %d, %d\n" mov DWORD PTR [esp+4], 600 ; maxlen call _snprintf mov DWORD PTR [esp], ebx call puts mov ebx, DWORD PTR [ebp-4] leave ret ``` ?####GCC + AT&T 格式 我們來看相同的代碼,但使用了AT&T格式: ``` #!bash .LC0: .string "hi! %d, %d, %d\n" f: pushl %ebp movl %esp, %ebp pushl %ebx subl $660, %esp leal 39(%esp), %ebx andl $-16, %ebx movl %ebx, (%esp) movl $3, 20(%esp) movl $2, 16(%esp) movl $1, 12(%esp) movl $.LC0, 8(%esp) movl $600, 4(%esp) call _snprintf movl %ebx, (%esp) call puts movl -4(%ebp), %ebx leave ret ``` ?代碼與上面的那個圖是相同的。 例如:`movl $3, 20(%esp)`與`mov DWORD PTR [esp + 20],3`是等價的,Intel的內存地址增加是使用register+offset,而AT&T使用的是offset(%register)。 ### 4.2.5 (Windows) 結構化異常處理 SEH也是存放在棧中的(如果存在的話)。 想了解更多，請等待后續翻譯在(51.3)。 ### 4.2.6 緩沖區溢出保護 想了解更多，請等待后續翻譯，在(16.2)。 ## 4.3 典型的內存布局 在32位系統中，函數開始時，棧的布局: