何為堆棧
堆Heap與棧Stack是兩個不同的概念,在理解這兩個概念時,需要放到具體的場景下,因為不同的場景下,堆與棧代表不同的含義.一般情況下有兩層含義
程序內(nèi)存布局的場景下,堆與棧表示兩種內(nèi)存管理方式
數(shù)據(jù)結(jié)構(gòu)場景下,堆與棧表示兩種常用的數(shù)據(jù)結(jié)構(gòu)
內(nèi)存管理方式的堆和棧
堆Heap
- 堆由開發(fā)人員分配和釋放,若開發(fā)人員不釋放,程序結(jié)束的時候由OS回收,分配方式類似于鏈表.
- 堆得內(nèi)存增長方向由低地址到高地址,也稱為向上增長.
棧Stack
- 棧由操作系統(tǒng)自動分配釋放,用于存放函數(shù)的參數(shù)值,局部變量等.
- 函數(shù)中定義的局部變量按照
先后順序(具體的順序根據(jù)編譯器決定)依次壓入棧中,也就是說相鄰的變量的地址之間不會存在其他變量. - 棧的內(nèi)存增長方向和堆相反,由高地址到低地址,也稱為向下增長.
觀察下面這段程序,我們可以設(shè)想一下變量的地址的大小:
#include <stdio.h>
int func(void)
{
int a;
int b;
int c;
printf("[func] &a = %p, &b = %p, &c = %p\n", &a, &b, &c);
}
int main(void)
{
int a;
int b;
int c;
printf("[main] &a = %p, &b = %p, &c = %p\n", &a, &b, &c);
func();
return 0;
}
猜測:
- 如果按照棧是向下增長的情況,那么main函數(shù)以及func函數(shù)中的局部變量a,b,c的地址關(guān)系應該是: &a > &b > &c
- main函數(shù)調(diào)用子函數(shù)func,那么func函數(shù)中的局部變量應該比main函數(shù)中的小, &func_a < &main_a, &func_b < &main_b, &func_c < &main_c
那么實際運行結(jié)果如何呢(linux下使用gcc編譯的結(jié)果)
[main] &a = 0x7ffe3e3ddc2c, &b = 0x7ffe3e3ddc30, &c = 0x7ffe3e3ddc34
[func] &a = 0x7ffe3e3ddbfc, &b = 0x7ffe3e3ddc00, &c = 0x7ffe3e3ddc04
可以觀察出兩個結(jié)果:
- 局部變量a,b,c的地址是&a < &b < &c.和我們想的棧是從高地址到地址的方式有出入.
- 但是可以看到func函數(shù)中的局部變量地址比main中的局部變量地址小, &func_a < &main_a, &func_b < &main_b, &func_c < &main_c
從我們觀察的結(jié)果得出,如果以函數(shù)整體來看,那么棧在linux下確實是從高地址到低地址來分配的.其實事實也是這樣,但是為什么函數(shù)內(nèi)的局部變量的地址不一樣呢,這里就牽扯到了棧的增長方向與棧幀布局
這里說的棧是指函數(shù)調(diào)用棧,是以棧幀(stack frame)為單位的.
每一次函數(shù)調(diào)用都會在棧上分配一個新的棧幀,在這次函數(shù)調(diào)用結(jié)束時釋放空間.
被調(diào)用的函數(shù)(callee)的棧幀相對于調(diào)用函數(shù)(caller)的棧幀反應了棧的增長方向;如果被調(diào)用的函數(shù)的棧幀比調(diào)用函數(shù)的棧幀在更低的地址,那么棧就是向下增長;反之向上增長.
而在一個棧幀內(nèi),局部變量是如何分配到棧幀里的(所謂的棧幀布局,stack frame layout),這完全是編譯器的自由.
每個函數(shù)都是一個棧幀,棧的分配是按照這個來的,而棧幀里怎么分配完全看編譯器.
在windows下棧與堆得增長方向是沒有定義的.
那么我們其實可以寫一個函數(shù)判斷棧幀的增長方向,如下
int find_stack_direction(void)
{
int var;//用于獲取棧地址
static int *addr = NULL; //用于存放第一個var的地址.
if (addr == NULL)
{
addr = &var;
find_stack_direction();
}
else
{
printf("addr = %p, &var = %p\n", addr, &var);
if (addr > &var)
{
printf("棧幀向下增長\n");
}
else
{
printf("棧幀向上增長\n");
}
}
}
int main(void)
{
find_stack_direction();
return 0;
}
運行結(jié)果如下
addr = 0x7ffe8ebf1604, &var = 0x7ffe8ebf15e4
棧幀向下增長
內(nèi)存管理上堆棧的區(qū)別
堆與棧實際上是操作系統(tǒng)對進程占用的內(nèi)存空間的兩種管理方式,主要有如下幾種區(qū)別:
- 管理方式不同:棧由操作系統(tǒng)自動分配釋放,無需我們手動控制;堆的申請和釋放工作由程序員控制,容易產(chǎn)生內(nèi)存泄漏
- 空間大小不同:每個進程擁有的棧大小要遠遠小于堆大小.理論上,進程可申請的堆大小為虛擬內(nèi)存大小,進程棧的大小 64bits 的 Windows 默認 1MB,64bits 的 Linux 默認 10MB
- 生長方向不同:堆的生長方向向上,內(nèi)存地址由低到高;棧的生長方向向下,內(nèi)存地址由高到低.
- 分配方式不同:堆都是動態(tài)分配的,沒有靜態(tài)分配的堆.棧有2種分配方式:靜態(tài)分配和動態(tài)分配.靜態(tài)分配是由操作系統(tǒng)完成的,比如局部變量的分配.動態(tài)分配由alloca()函數(shù)分配,但是棧的動態(tài)分配和堆是不同的,它的動態(tài)分配是由操作系統(tǒng)進行釋放,無需我們手工實現(xiàn).
- 分配效率不同:棧由操作系統(tǒng)自動分配,會在硬件層級對棧提供支持:分配專門的寄存器存放棧的地址,壓棧出棧都有專門的指令執(zhí)行,這就決定了棧的效率比較高.堆則是由C/C++提供的庫函數(shù)或運算符來完成申請與管理,實現(xiàn)機制較為復雜,頻繁的內(nèi)存申請容易產(chǎn)生內(nèi)存碎片.顯然,堆的效率比棧要低得多.
- 存放內(nèi)容不同:棧存放的內(nèi)容,函數(shù)返回地址,相關(guān)參數(shù),局部變量和寄存器內(nèi)容等.當主函數(shù)調(diào)用另外一個函數(shù)的時候,要對當前函數(shù)執(zhí)行斷點進行保存,需要使用棧來實現(xiàn),首先入棧的是主函數(shù)下一條語句的地址,即擴展指針寄存器的內(nèi)容(EIP),然后是當前棧幀的底部地址,即擴展基址指針寄存器內(nèi)容(EBP),再然后是被調(diào)函數(shù)的實參等,一般情況下是按照從右向左的順序入棧,之后是被調(diào)函數(shù)的局部變量,注意靜態(tài)變量是存放在數(shù)據(jù)段或者BSS段,是不入棧的.出棧的順序正好相反,最終棧頂指向主函數(shù)下一條語句的地址,主程序又從該地址開始執(zhí)行.堆,一般情況堆頂使用一個字節(jié)的空間來存放堆的大小,而堆中具體存放內(nèi)容是由程序員來填充的.
數(shù)據(jù)結(jié)構(gòu)上的堆和棧
堆Heap
堆是一種常用的樹形結(jié)構(gòu),是一種特殊的完全二叉樹,當且僅當滿足所有節(jié)點的值總是不大于或不小于其父節(jié)點的值的完全二叉樹被稱之為堆.堆的這一特性稱之為堆序性.因此,在一個堆中,根節(jié)點是最大(或最小)節(jié)點.如果根節(jié)點最小,稱之為小頂堆(或小根堆),如果根節(jié)點最大,稱之為大頂堆(或大根堆).堆的左右孩子沒有大小的順序.下面是一個小頂堆示例:
棧Stack
棧是一種運算受限的線性表,其限制是指只僅允許在表的一端進行插入和刪除操作,這一端被稱為棧頂(Top),相對地,把另一端稱為棧底(Bottom).把新元素放到棧頂元素的上面,使之成為新的棧頂元素稱作進棧,入棻柿矗或壓棧(Push);把棧頂元素刪除,使其相鄰的元素成為新的棧頂元素稱作出椛渭恚或退棧(Pop).這種受限的運算使棧擁有先進后出的特性(First-In/Last-Out),簡稱FILO.
堆棧分別存放了什么
- 堆:由程序員決定
- 棧:函數(shù)返回地址, 函數(shù)參數(shù), 局部變量, 寄存器內(nèi)容
以下面這個程序為例:
main()
{
int b;//stack
char s[] = "abc";//stack
char *p2;//stack
char *p3 = "123456";//123456\0在常量區(qū), p3在stack上.
p1 = (char *)malloc(10);//heap
p2 = (char *)malloc(20);//heap
}
為什么棧向下增長
計算機內(nèi)存分配了代碼段(.text),初始化的數(shù)據(jù)段(.data),未初始化的數(shù)據(jù)段(.bss),堆空間(heap),棧空間(stack),命令行參數(shù)以及環(huán)境變量區(qū)域().
每一個可執(zhí)行的C程序,從低地址到高地址依次是:text, data, bss, heap, stack,命令行參數(shù)以及環(huán)境變量,如下圖:
程序計數(shù)器(program counter,簡稱pc)的缺省指向0地址,計算機開機后從程序計數(shù)器指向的地址開始執(zhí)行程序,每執(zhí)行完一條指令后,程序計算器自動加1.
因此很自然的,.text段從低地址區(qū)間開始加載,向高地址區(qū)間擴展.
heap從低地址向高地址拓展,做內(nèi)存管理相對要簡單些,為了避免椷笙空間和堆空間沖突,最大利用地址空間,很自然的,我們會選擇把棧底設(shè)置在高地址區(qū)間,然后讓棧向下增長.
- 優(yōu)點
stack從高地址向低地址擴展,這樣椓憬ィ空間的起始位置就能確定下來.動態(tài)的調(diào)整椫现郏空間大小也不需要移動棧內(nèi)的數(shù)據(jù),如果是從低地址到高地址的擴展,結(jié)尾的地址是固定的,如果要擴大或縮小,則需要移動整個棧的數(shù)據(jù).
并且這樣設(shè)計可以使得堆和棧能夠充分利用空閑的地址空間.如果棧向上漲的話,我們就必須得指定棧和堆的一個嚴格分界線,但這個分界線怎么確定呢?平均分?但是有的程序使用的堆空間比較多,而有的程序使用的棧空間比較多.
所以就可能出現(xiàn)這種情況:一個程序因為棧溢出而崩潰的時候,其實它還有大量閑置的堆空間呢,但是我們卻無法使用這些閑置的堆空間.所以呢,最好的辦法就是讓堆和棧一個向上漲,一個向下漲,這樣它們就可以最大程度地共用這塊剩余的地址空間,達到利用率的最大化.
-
所有的棧都是向下增長嗎?
大部分CPU指令集設(shè)計了函數(shù)調(diào)用架構(gòu),定義了專用的調(diào)用/返回指令,并在指令中隱含規(guī)定棧的方向.- 主流1:向低地址擴展:x86,MIPS
- 主流2:自由選擇:Arm(但個別指令僅支持向低)
- 罕見:向高地址擴展:PA-RISC,操作系統(tǒng)Multics
- 非主流:System z,棧是個鏈表
如果CPU同時支持向上和向下,例如arm,那么編譯器需要指定程序的調(diào)用方向,一般還是選擇向下.
比較罕見的極端的案例是Multics操作系統(tǒng),這是Unix的巨無霸前身,設(shè)計者刻意選用向高地址擴展,因為該架構(gòu)有助于防御緩沖區(qū)溢出攻擊.
