堆(heap)和棧(stack)是C/C++編程不可避免會碰到的兩個基本概念。首先，這兩個概念都可以在講數(shù)據(jù)結(jié)構(gòu)的書中找到，他們都是基本的數(shù)據(jù)結(jié)構(gòu)，雖然棧更為簡單一些。在具體的C/C++編程框架中，這兩個概念并不是并行的。對底層機器代碼的研究可以揭示，棧是機器系統(tǒng)提供的數(shù)據(jù)結(jié)構(gòu)，而堆則是C/C++函數(shù)庫提供的。
具體地說，現(xiàn)代計算機(串行執(zhí)行機制)，都直接在代碼底層支持棧的數(shù)據(jù)結(jié)構(gòu)。這體現(xiàn)在，有專門的寄存器指向棧所在的地址，有專門的機器指令完成數(shù)據(jù)入棧出棧的操作。這種機制的特點是效率高，支持的數(shù)據(jù)有限，一般是整數(shù)，指針，浮點數(shù)等系統(tǒng)直接支持的數(shù)據(jù)類型，并不直接支持其他的數(shù)據(jù)結(jié)構(gòu)。因為棧的這種特點，對棧的使用在程序中是非常頻繁的。對子程序的調(diào)用就是直接利用棧完成的。機器的call指令里隱含了把返回地址推入棧，然后跳轉(zhuǎn)至子程序地址的操作，而子程序中的ret指令則隱含從堆棧中彈出返回地址并跳轉(zhuǎn)之的操作。C/C++中的自動變量是直接利用棧的例子，這也就是為什么當函數(shù)返回時，該函數(shù)的自動變量自動失效的原因。
和棧不同，堆的數(shù)據(jù)結(jié)構(gòu)并不是由系統(tǒng)(無論是機器系統(tǒng)還是操作系統(tǒng))支持的，而是由函數(shù)庫提供的。基本的malloc/realloc/free函數(shù)維護了一套內(nèi)部的堆數(shù)據(jù)結(jié)構(gòu)。當程序使用這些函數(shù)去獲得新的內(nèi)存空間時，這套函數(shù)首先試圖從內(nèi)部堆中尋找可用的內(nèi)存空間，如果沒有可以使用的內(nèi)存空間，則試圖利用系統(tǒng)調(diào)用來動態(tài)增加程序數(shù)據(jù)段的內(nèi)存大小，新分配得到的空間首先被組織進內(nèi)部堆中去，然后再以適當?shù)男问椒祷亟o調(diào)用者。當程序釋放分配的內(nèi)存空間時，這片內(nèi)存空間被返回內(nèi)部堆結(jié)構(gòu)中，可能會被適當?shù)奶幚?比如和其他空閑空間合并成更大的空閑空間)，以更適合下一次內(nèi)存分配申請。這套復(fù)雜的分配機制實際上相當于一個內(nèi)存分配的緩沖池(Cache)，使用這套機制有如下若干原因：
1. 系統(tǒng)調(diào)用可能不支持任意大小的內(nèi)存分配。有些系統(tǒng)的系統(tǒng)調(diào)用只支持固定大小及其倍數(shù)的內(nèi)存請求(按頁分配)；這樣的話對于大量的小內(nèi)存分類來說會造成浪費。
2. 系統(tǒng)調(diào)用申請內(nèi)存可能是代價昂貴的。系統(tǒng)調(diào)用可能涉及用戶態(tài)和核心態(tài)的轉(zhuǎn)換。
3. 沒有管理的內(nèi)存分配在大量復(fù)雜內(nèi)存的分配釋放操作下很容易造成內(nèi)存碎片。
堆和棧的對比
從以上知識可知，棧是系統(tǒng)提供的功能，特點是快速高效，缺點是有限制，數(shù)據(jù)不靈活；而棧是函數(shù)庫提供的功能，特點是靈活方便，數(shù)據(jù)適應(yīng)面廣泛，但是效率有一定降低。棧是系統(tǒng)數(shù)據(jù)結(jié)構(gòu)，對于進程/線程是唯一的；堆是函數(shù)庫內(nèi)部數(shù)據(jù)結(jié)構(gòu)，不一定唯一。不同堆分配的內(nèi)存無法互相操作。棧空間分靜態(tài)分配和動態(tài)分配兩種。靜態(tài)分配是編譯器完成的，比如自動變量(auto)的分配。動態(tài)分配由alloca函數(shù)完成。棧的動態(tài)分配無需釋放(是自動的)，也就沒有釋放函數(shù)。為可移植的程序起見，棧的動態(tài)分配操作是不被鼓勵的！堆空間的分配總是動態(tài)的，雖然程序結(jié)束時所有的數(shù)據(jù)空間都會被釋放回系統(tǒng)，但是精確的申請內(nèi)存/釋放內(nèi)存匹配是良好程序的基本要素。
進程在內(nèi)存中的影像.
我們假設(shè)現(xiàn)在有一個程序, 它的函數(shù)調(diào)用順序如下.
main(...) -> func_1(...) -> func_2(...) -> func_3(...)
即: 主函數(shù)main調(diào)用函數(shù)func_1; 函數(shù)func_1調(diào)用函數(shù)func_2; 函數(shù)func_2調(diào)用函數(shù)func_3
當程序被操作系統(tǒng)調(diào)入內(nèi)存運行, 其相對應(yīng)的進程在內(nèi)存中的影像如下圖所示.
(內(nèi)存高址)
+--------------------------------------+
| ...... | ... 省略了一些我們不需要關(guān)心的區(qū)
+--------------------------------------+
| env strings (環(huán)境變量字串) | \
+--------------------------------------+ \
| argv strings (命令行字串) | \
+--------------------------------------+ \
| env pointers (環(huán)境變量指針) | SHELL的環(huán)境變量和命令行參數(shù)保存區(qū)
+--------------------------------------+ /
| argv pointers (命令行參數(shù)指針) | /
+--------------------------------------+ /
| argc (命令行參數(shù)個數(shù)) | /
+--------------------------------------+
| main 函數(shù)的棧幀 | \
+--------------------------------------+ \
| func_1 函數(shù)的棧幀 | \
+--------------------------------------+ \
| func_2 函數(shù)的棧幀 | \
+--------------------------------------+ \
| func_3 函數(shù)的棧幀 | Stack (棧)
+..................
....................+ /
| | /
...... /
| | /
+......................................+ /
| Heap (堆) | /
+--------------------------------------+
| Uninitialised (BSS) data | 非初始化數(shù)據(jù)(BSS)區(qū)
+--------------------------------------+
| Initialised data | 初始化數(shù)據(jù)區(qū)
+--------------------------------------+
| Text | 文本區(qū)
+--------------------------------------+
(內(nèi)存低址)
這里需要說明的是:
i) 隨著函數(shù)調(diào)用層數(shù)的增加, 函數(shù)棧幀是一塊塊地向內(nèi)存低地址方向延伸的.
隨著進程中函數(shù)調(diào)用層數(shù)的減少, 即各函數(shù)調(diào)用的返回, 棧幀會一塊塊地
被遺棄而向內(nèi)存的高址方向回縮.
各函數(shù)的棧幀大小隨著函數(shù)的性質(zhì)的不同而不等, 由函數(shù)的局部變量的數(shù)目決定.
ii) 進程對內(nèi)存的動態(tài)申請是發(fā)生在Heap(堆)里的. 也就是說, 隨著系統(tǒng)動態(tài)分
配給進程的內(nèi)存數(shù)量的增加, Heap(堆)有可能向高址或低址延伸, 依賴于不
同CPU的實現(xiàn). 但一般來說是向內(nèi)存的高地址方向增長的.
iii) 在BSS數(shù)據(jù)或者Stack(棧)的增長耗盡了系統(tǒng)分配給進程的自由內(nèi)存的情況下,
進程將會被阻塞, 重新被操作系統(tǒng)用更大的內(nèi)存模塊來調(diào)度運行.
(雖然和exploit沒有關(guān)系, 但是知道一下還是有好處的)
iv) 函數(shù)的棧幀里包含了函數(shù)的參數(shù)(至于被調(diào)用函數(shù)的參數(shù)是放在調(diào)用函數(shù)的棧
幀還是被調(diào)用函數(shù)棧幀, 則依賴于不同系統(tǒng)的實現(xiàn)),
它的局部變量以及恢復(fù)調(diào)用該函數(shù)的函數(shù)的棧幀(也就是前一個棧幀)所需要的
數(shù)據(jù), 其中包含了調(diào)用函數(shù)的下一條執(zhí)行指令的地址.
v) 非初始化數(shù)據(jù)(BSS)區(qū)用于存放程序的靜態(tài)變量, 這部分內(nèi)存都是被初始化為零的.
初始化數(shù)據(jù)區(qū)用于存放可執(zhí)行文件里的初始化數(shù)據(jù).
這兩個區(qū)統(tǒng)稱為數(shù)據(jù)區(qū).
vi) Text(文本區(qū))是個只讀區(qū), 任何嘗試對該區(qū)的寫操作會導致段違法出錯. 文本區(qū)
是被多個運行該可執(zhí)行文件的進程所共享的. 文本區(qū)存放了程序的代碼.
2) 函數(shù)的棧幀.
函數(shù)調(diào)用時所建立的棧幀包含了下面的信息:
i) 函數(shù)的返回地址. 返回地址是存放在調(diào)用函數(shù)的棧幀還是被調(diào)用函數(shù)的棧幀里,
取決于不同系統(tǒng)的實現(xiàn).
ii) 調(diào)用函數(shù)的棧幀信息, 即棧頂和棧底.
iii) 為函數(shù)的局部變量分配的空間
iv) 為被調(diào)用函數(shù)的參數(shù)分配的空間--取決于不同系統(tǒng)的實現(xiàn).