何為堆棧

堆Heap與棧Stack是兩個(gè)不同的概念,在理解這兩個(gè)概念時(shí),需要放到具體的場(chǎng)景下,因?yàn)椴煌膱?chǎng)景下,堆與棧代表不同的含義.一般情況下有兩層含義

程序內(nèi)存布局的場(chǎng)景下,堆與棧表示兩種內(nèi)存管理方式
數(shù)據(jù)結(jié)構(gòu)場(chǎng)景下,堆與棧表示兩種常用的數(shù)據(jù)結(jié)構(gòu)

內(nèi)存管理方式的堆和棧

堆Heap

1. 堆由開(kāi)發(fā)人員分配和釋放,若開(kāi)發(fā)人員不釋放,程序結(jié)束的時(shí)候由OS回收,分配方式類(lèi)似于鏈表.
2. 堆得內(nèi)存增長(zhǎng)方向由低地址到高地址,也稱為向上增長(zhǎng).

棧Stack

1. 棧由操作系統(tǒng)自動(dòng)分配釋放,用于存放函數(shù)的參數(shù)值,局部變量等.
2. 函數(shù)中定義的局部變量按照先后順序(具體的順序根據(jù)編譯器決定)依次壓入棧中,也就是說(shuō)相鄰的變量的地址之間不會(huì)存在其他變量.
3. 棧的內(nèi)存增長(zhǎng)方向和堆相反,由高地址到低地址,也稱為向下增長(zhǎng).

觀察下面這段程序,我們可以設(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;
}

猜測(cè):

1. 如果按照棧是向下增長(zhǎng)的情況,那么main函數(shù)以及func函數(shù)中的局部變量a,b,c的地址關(guān)系應(yīng)該是: &a > &b > &c
2. main函數(shù)調(diào)用子函數(shù)func,那么func函數(shù)中的局部變量應(yīng)該比main函數(shù)中的小, &func_a < &main_a, &func_b < &main_b, &func_c < &main_c

那么實(shí)際運(yùn)行結(jié)果如何呢(linux下使用gcc編譯的結(jié)果)

[main] &a = 0x7ffe3e3ddc2c, &b = 0x7ffe3e3ddc30, &c = 0x7ffe3e3ddc34
[func] &a = 0x7ffe3e3ddbfc, &b = 0x7ffe3e3ddc00, &c = 0x7ffe3e3ddc04

可以觀察出兩個(gè)結(jié)果:

1. 局部變量a,b,c的地址是&a < &b < &c.和我們想的棧是從高地址到地址的方式有出入.
2. 但是可以看到func函數(shù)中的局部變量地址比main中的局部變量地址小, &func_a < &main_a, &func_b < &main_b, &func_c < &main_c

從我們觀察的結(jié)果得出,如果以函數(shù)整體來(lái)看,那么棧在linux下確實(shí)是從高地址到低地址來(lái)分配的.其實(shí)事實(shí)也是這樣,但是為什么函數(shù)內(nèi)的局部變量的地址不一樣呢,這里就牽扯到了棧的增長(zhǎng)方向與棧幀布局

這里說(shuō)的棧是指函數(shù)調(diào)用棧,是以棧幀(stack frame)為單位的.
每一次函數(shù)調(diào)用都會(huì)在棧上分配一個(gè)新的棧幀,在這次函數(shù)調(diào)用結(jié)束時(shí)釋放空間.
被調(diào)用的函數(shù)(callee)的棧幀相對(duì)于調(diào)用函數(shù)(caller)的棧幀反應(yīng)了棧的增長(zhǎng)方向;如果被調(diào)用的函數(shù)的棧幀比調(diào)用函數(shù)的棧幀在更低的地址,那么棧就是向下增長(zhǎng);反之向上增長(zhǎng).

而在一個(gè)棧幀內(nèi),局部變量是如何分配到棧幀里的(所謂的棧幀布局,stack frame layout),這完全是編譯器的自由.
每個(gè)函數(shù)都是一個(gè)棧幀,棧的分配是按照這個(gè)來(lái)的,而棧幀里怎么分配完全看編譯器.

在windows下棧與堆得增長(zhǎng)方向是沒(méi)有定義的.

那么我們其實(shí)可以寫(xiě)一個(gè)函數(shù)判斷棧幀的增長(zhǎng)方向,如下

int find_stack_direction(void)
{
    int var;//用于獲取棧地址 
    static int *addr = NULL; //用于存放第一個(gè)var的地址.

    if (addr == NULL)
    {
        addr = &var;
        find_stack_direction();
    }
    else
    {
        printf("addr = %p, &var = %p\n", addr, &var);
        if (addr > &var)
        {
            printf("棧幀向下增長(zhǎng)\n");
        }
        else
        {
            printf("棧幀向上增長(zhǎng)\n");
        }
    }
}

int main(void)
{
    find_stack_direction();
    return 0;
}

運(yùn)行結(jié)果如下

addr = 0x7ffe8ebf1604, &var = 0x7ffe8ebf15e4
棧幀向下增長(zhǎng)

內(nèi)存管理上堆棧的區(qū)別

堆與棧實(shí)際上是操作系統(tǒng)對(duì)進(jìn)程占用的內(nèi)存空間的兩種管理方式,主要有如下幾種區(qū)別:

• 管理方式不同:棧由操作系統(tǒng)自動(dòng)分配釋放,無(wú)需我們手動(dòng)控制;堆的申請(qǐng)和釋放工作由程序員控制,容易產(chǎn)生內(nèi)存泄漏
• 空間大小不同:每個(gè)進(jìn)程擁有的棧大小要遠(yuǎn)遠(yuǎn)小于堆大小.理論上,進(jìn)程可申請(qǐng)的堆大小為虛擬內(nèi)存大小,進(jìn)程棧的大小 64bits 的 Windows 默認(rèn) 1MB,64bits 的 Linux 默認(rèn) 10MB
• 生長(zhǎng)方向不同:堆的生長(zhǎng)方向向上,內(nèi)存地址由低到高;棧的生長(zhǎng)方向向下,內(nèi)存地址由高到低.
• 分配方式不同:堆都是動(dòng)態(tài)分配的,沒(méi)有靜態(tài)分配的堆.棧有2種分配方式:靜態(tài)分配和動(dòng)態(tài)分配.靜態(tài)分配是由操作系統(tǒng)完成的,比如局部變量的分配.動(dòng)態(tài)分配由alloca()函數(shù)分配,但是棧的動(dòng)態(tài)分配和堆是不同的,它的動(dòng)態(tài)分配是由操作系統(tǒng)進(jìn)行釋放,無(wú)需我們手工實(shí)現(xiàn).
• 分配效率不同:棧由操作系統(tǒng)自動(dòng)分配,會(huì)在硬件層級(jí)對(duì)棧提供支持:分配專(zhuān)門(mén)的寄存器存放棧的地址,壓棧出棧都有專(zhuān)門(mén)的指令執(zhí)行,這就決定了棧的效率比較高.堆則是由C/C++提供的庫(kù)函數(shù)或運(yùn)算符來(lái)完成申請(qǐng)與管理,實(shí)現(xiàn)機(jī)制較為復(fù)雜,頻繁的內(nèi)存申請(qǐng)容易產(chǎn)生內(nèi)存碎片.顯然,堆的效率比棧要低得多.
• 存放內(nèi)容不同:棧存放的內(nèi)容,函數(shù)返回地址,相關(guān)參數(shù),局部變量和寄存器內(nèi)容等.當(dāng)主函數(shù)調(diào)用另外一個(gè)函數(shù)的時(shí)候,要對(duì)當(dāng)前函數(shù)執(zhí)行斷點(diǎn)進(jìn)行保存,需要使用棧來(lái)實(shí)現(xiàn),首先入棧的是主函數(shù)下一條語(yǔ)句的地址,即擴(kuò)展指針寄存器的內(nèi)容(EIP),然后是當(dāng)前棧幀的底部地址,即擴(kuò)展基址指針寄存器內(nèi)容(EBP),再然后是被調(diào)函數(shù)的實(shí)參等,一般情況下是按照從右向左的順序入棧,之后是被調(diào)函數(shù)的局部變量,注意靜態(tài)變量是存放在數(shù)據(jù)段或者BSS段,是不入棧的.出棧的順序正好相反,最終棧頂指向主函數(shù)下一條語(yǔ)句的地址,主程序又從該地址開(kāi)始執(zhí)行.堆,一般情況堆頂使用一個(gè)字節(jié)的空間來(lái)存放堆的大小,而堆中具體存放內(nèi)容是由程序員來(lái)填充的.

數(shù)據(jù)結(jié)構(gòu)上的堆和棧

堆Heap

堆是一種常用的樹(shù)形結(jié)構(gòu),是一種特殊的完全二叉樹(shù),當(dāng)且僅當(dāng)滿足所有節(jié)點(diǎn)的值總是不大于或不小于其父節(jié)點(diǎn)的值的完全二叉樹(shù)被稱之為堆.堆的這一特性稱之為堆序性.因此,在一個(gè)堆中,根節(jié)點(diǎn)是最大(或最小)節(jié)點(diǎn).如果根節(jié)點(diǎn)最小,稱之為小頂堆(或小根堆),如果根節(jié)點(diǎn)最大,稱之為大頂堆(或大根堆).堆的左右孩子沒(méi)有大小的順序.下面是一個(gè)小頂堆示例:

棧Stack

棧是一種運(yùn)算受限的線性表,其限制是指只僅允許在表的一端進(jìn)行插入和刪除操作,這一端被稱為棧頂(Top),相對(duì)地,把另一端稱為棧底(Bottom).把新元素放到棧頂元素的上面,使之成為新的棧頂元素稱作進(jìn)棧,入?；驂簵?Push);把棧頂元素刪除,使其相鄰的元素成為新的棧頂元素稱作出?；蛲藯?Pop).這種受限的運(yùn)算使棧擁有先進(jìn)后出的特性(First-In/Last-Out),簡(jiǎn)稱FILO.

堆棧分別存放了什么

• 堆:由程序員決定
• 棧:函數(shù)返回地址, 函數(shù)參數(shù), 局部變量, 寄存器內(nèi)容

以下面這個(gè)程序?yàn)槔?

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
}

為什么棧向下增長(zhǎng)

計(jì)算機(jī)內(nèi)存分配了代碼段(.text),初始化的數(shù)據(jù)段(.data),未初始化的數(shù)據(jù)段(.bss),堆空間(heap),棧空間(stack),命令行參數(shù)以及環(huán)境變量區(qū)域().

每一個(gè)可執(zhí)行的C程序,從低地址到高地址依次是:text, data, bss, heap, stack,命令行參數(shù)以及環(huán)境變量,如下圖:

程序計(jì)數(shù)器(program counter,簡(jiǎn)稱pc)的缺省指向0地址,計(jì)算機(jī)開(kāi)機(jī)后從程序計(jì)數(shù)器指向的地址開(kāi)始執(zhí)行程序,每執(zhí)行完一條指令后,程序計(jì)算器自動(dòng)加1.

因此很自然的,.text段從低地址區(qū)間開(kāi)始加載,向高地址區(qū)間擴(kuò)展.

heap從低地址向高地址拓展,做內(nèi)存管理相對(duì)要簡(jiǎn)單些,為了避免?？臻g和堆空間沖突,最大利用地址空間,很自然的,我們會(huì)選擇把棧底設(shè)置在高地址區(qū)間,然后讓棧向下增長(zhǎng).

• 優(yōu)點(diǎn)
  stack從高地址向低地址擴(kuò)展,這樣?？臻g的起始位置就能確定下來(lái).動(dòng)態(tài)的調(diào)整?？臻g大小也不需要移動(dòng)棧內(nèi)的數(shù)據(jù),如果是從低地址到高地址的擴(kuò)展,結(jié)尾的地址是固定的,如果要擴(kuò)大或縮小,則需要移動(dòng)整個(gè)棧的數(shù)據(jù).

并且這樣設(shè)計(jì)可以使得堆和棧能夠充分利用空閑的地址空間.如果棧向上漲的話,我們就必須得指定棧和堆的一個(gè)嚴(yán)格分界線,但這個(gè)分界線怎么確定呢?平均分?但是有的程序使用的堆空間比較多,而有的程序使用的棧空間比較多.

所以就可能出現(xiàn)這種情況:一個(gè)程序因?yàn)闂Ｒ绯龆罎⒌臅r(shí)候,其實(shí)它還有大量閑置的堆空間呢,但是我們卻無(wú)法使用這些閑置的堆空間.所以呢,最好的辦法就是讓堆和棧一個(gè)向上漲,一個(gè)向下漲,這樣它們就可以最大程度地共用這塊剩余的地址空間,達(dá)到利用率的最大化.

• 所有的棧都是向下增長(zhǎng)嗎?
  大部分CPU指令集設(shè)計(jì)了函數(shù)調(diào)用架構(gòu),定義了專(zhuān)用的調(diào)用/返回指令,并在指令中隱含規(guī)定棧的方向.

  • 主流1:向低地址擴(kuò)展:x86,MIPS
  • 主流2:自由選擇:Arm(但個(gè)別指令僅支持向低)
  • 罕見(jiàn):向高地址擴(kuò)展:PA-RISC,操作系統(tǒng)Multics
  • 非主流:System z,棧是個(gè)鏈表

  如果CPU同時(shí)支持向上和向下,例如arm,那么編譯器需要指定程序的調(diào)用方向,一般還是選擇向下.
  比較罕見(jiàn)的極端的案例是Multics操作系統(tǒng),這是Unix的巨無(wú)霸前身,設(shè)計(jì)者刻意選用向高地址擴(kuò)展,因?yàn)樵摷軜?gòu)有助于防御緩沖區(qū)溢出攻擊.

參考文獻(xiàn)

• 一文讀懂堆與棧的區(qū)別
• 內(nèi)存管理之棧（stack）