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