學習C語言，我們都聽過堆（heap）和棧（stack）的概念。需要注意的是：有些地方“堆棧”這個詞特指的是棧，而不是堆和棧。命名約定：本文中堆棧一次出現的地方，指的是兩種東西，而非一種。
在數據結構中，我們也聽過棧和堆這兩種數據結構，當然和我本文要講的東西是不同的概念。不過數據結構中的棧（算法、數學意義上的一種抽象），和本文中的棧（實際存在的存儲區）有一共同之處就是FILO —— 先入後出。但是數據結構中的堆和我們本文中的堆則是毫不相干。
無圖言卵
注意，這裡指的都是虛擬內存空間，並不是實際的物理內存佈局。每一個進程都有自己的虛擬內存空間，也就是說我們程序中指針所表示的地址實際是虛擬地址，而不是物理地址。
增長方式
所謂地址增長方式，是指堆或棧在分配內存的時候，其分得的內存空間的地址的增長方式。堆的地址增長方式是從低到高的，而棧的地址增長方式是從高到低的。（在說這句話的時候，要明確的一點就是這是指的x86系統，並非所有架構的系統都如此）
之所以它們會呈現出相反的兩種地址增長方式是有其歷史原因的：
早期的機器上內存的大小十分有限，如果堆和棧使用相同的地址增長方式（比如，都是從低到高），假設，一段內存空間的起始位置（先忽略其他段）設置為堆的起始地址，那麼棧的起始地址必然在這段內存空間的中間某處，這個起始點如果選擇得太靠後，則可能導致棧的內存大小不夠，太靠前則會導致堆在分配內存的時候，可能與棧地址衝突。這時x86系統的設計師們，巧妙地將棧的起始位置定於內存空間的另一端，而其地址增長方式也是和堆相反的從高到低，這樣從一定程度上，減輕了堆棧內存地址衝突或棧空間不足的可能性。就好比兩個小夥伴在同一本筆記本上記筆記，兩個人分別從筆記本的首頁和尾頁開始寫，其筆記衝突的概率大大減小。
棧
函數棧
棧與函數有莫大的關係。簡單說來，我們在函數中聲明的任何局部變量（非靜態）都是在棧中分配的（編譯期間完成）。並且函數的參數，以及返回值也是依賴於棧。
為了深入地探討這些概念，我們需要從彙編角度來展開研究。在使用gcc編譯的時候，-S選項可以生成彙編代碼。但此時生成的彙編代碼是AT&T風格的，我們可以用-masm=intel生成intel風格的彙編。比如：gcc -S -masm=intel hello.c 這時就會生成彙編文件hello.s。請注意我們此時探討的真相都是不開編譯器優化選項的，因為如果開了編譯器優化選項，那麼其彙編行為往往已經完全不是我們代碼本來的執行細節了。（編譯器保證的是最終一致性，為了優化可能會改變我們的程序的細節）
變量
看一個簡單的例子：
int main()
{
int a;
int b = 1;
int c = 2;
}
其通過gcc -S -masm=intel彙編之後的彙編代碼主要部分如下，注意不同版本的gcc編譯器，不同位數的操作系統（32位或64位）其彙編代碼可能不同，但大致的意思相同。
main:
.LFB0:
.cfi_startproc
push rbp
.cfi_def_cfa_offset 16
.cfi_offset 6, -16
mov rbp, rsp
.cfi_def_cfa_register 6
mov DWORD PTR [rbp-8], 1
mov DWORD PTR [rbp-4], 2
pop rbp
.cfi_def_cfa 7, 8
ret
.cfi_endproc
可以忽略掉其中點號. 開頭的語句。再看一遍：
main:
.LFB0:
push rbp
mov rbp, rsp
mov DWORD PTR [rbp-8], 1
mov DWORD PTR [rbp-4], 2
pop rbp
ret
因為我是64位系統，所以彙編代碼中的寄存器都是r打頭的（rbp，rsp）64位寄存器。x86架構（通常是32位系統）是e打頭的（ebp，esp）。以下涉及到寄存器時，我通常會省略其前綴，而直接用bp和sp來稱呼。bp是基址寄存器，sp是棧頂指針寄存器（sp的位置，是我們實際能使用的棧的大小）。
請自行區分操作系統位數和cpu架構位數的區別。x64（x86-64），x86是CPU架構。如果你是x64的CPU裝了32位系統，那麼也不會使用到x64的寄存器（比如r8d），或者不能完整使用x64CPU的寄存器，比如rax。你只能使用該寄存器的一半：eax
首先將bp入棧（push rbp），然後將當前sp位置存取bp（mov rbp, rsp）。這兩步是通用操作。下面是重點。
給變量分配空間，可以看到只有兩個賦值語句，說明我們的int a因為沒有初始化，所以實際不會被分配空間。
請注意下面（低地址）是棧頂。可以看到c在高地址，b在低地址。這與變量的初始化順序相反。（如果你開優化選項-O來觀察的話，你會發現彙編代碼裡什麼都沒有做，這是因為聲明的變量b，c雖然被初始化了，但是後續並沒有被調用，所以編譯器在優化的時候，就什麼都不做了。所以再次提醒請不要開編譯器優化選項來研究本文的內容，本文不是討論編譯器優化原理的，因為舉得例子過於簡單，可能就被編譯器優化抹掉了）
再驗證一下，變量被分配的棧位置是否和變量初始化順序相反：
int main()
{
int a;
int b = 1;
int c = 2;
a = 0;
}
其棧內存佈局為：
如果是數組的初始化，則每個數組元素分配的棧地址，與其初始化順序就沒有關係了。下標越大的地址越高。比如：int a[4];.....。那麼a[0]是數組中棧地址最低的元素，a[3]是地址最高的元素。這裡我就不一一演示了，大家可以自己寫個demo，彙編一下看看。。其實很好裡面，數組的地址位置與其下標的關係一定要嚴格遵守，這樣才方便隨機訪問（通過下標直接計算偏移）。要注意的是，a[0]在最低的地址。
參數
面試的時候可能出遇到以下類型的題目：
int main()
{
int a = 1;
int b = 2;
printf("%d,%d",a, a=a+b );
}
上面這段代碼的輸出結果是什麼？結果是：3,3。出現這樣的結果，一些編程書籍中可能會做出解釋：因為函數參數的入棧順序是從右到左的。這句話應該是對的，它揭露了一個事實，那就是函數參數是存入棧中的，如果參數是表達式，那麼一定要先計算出表達式的值，然後再入棧。所以上面的printf中，會首先計算表達式a=a+b的值。此時a的值就變化了。這樣解釋應該是沒有問題的，面試官也應該不會挑刺。其實真正的編譯器行為沒有這麼簡單。看下它的彙編代碼：
.LC0:
.string "%d,%d"
.text
.globl main
.type main, @function
main:
.LFB0:
push rbp
mov rbp, rsp
sub rsp, 16
mov DWORD PTR [rbp-8], 1 ；a = 1
mov DWORD PTR [rbp-4], 2 ；b = 2
mov eax, DWORD PTR [rbp-4] ；將b的值存入寄存器eax
add DWORD PTR [rbp-8], eax ；執行a=a+b的操作，此時a的棧空間中存放3
mov edx, DWORD PTR [rbp-8] ;將a的值3存入寄存器edx
mov eax, DWORD PTR [rbp-8] ;將a的值3存入寄存器eax
mov esi, eax ；將eax的值3存入寄存器esi
mov edi, OFFSET FLAT:.LC0 ；將字符串"%d,%d"存入寄存器edi
mov eax, 0 ；eax清零。用於存放返回值
call printf
leave
ret
我刪除一些不必要的信息，並且增加了註釋。
可以看到，上面的代碼中，函數參數並未使用到棧來傳遞參數，而是通過寄存器來傳遞參數。當然這並不能說用棧來傳遞參數的說法是錯的，因為寄存器的數量是有限的。來看一個擁有7個參數的函數：
int add(int a, int b, int c, int d, int e, int f, int g)
{
return a + b + c + d + e + f + g;
}
其彙編代碼為：
add:
.LFB0:
push rbp
mov rbp, rsp
mov DWORD PTR [rbp-4], edi
mov DWORD PTR [rbp-8], esi
mov DWORD PTR [rbp-12], edx
mov DWORD PTR [rbp-16], ecx
mov DWORD PTR [rbp-20], r8d
mov DWORD PTR [rbp-24], r9d
mov edx, DWORD PTR [rbp-4]
mov eax, DWORD PTR [rbp-8]
add edx, eax
mov eax, DWORD PTR [rbp-12]
add edx, eax
mov eax, DWORD PTR [rbp-16]
add edx, eax
mov eax, DWORD PTR [rbp-20]
add edx, eax
mov eax, DWORD PTR [rbp-24]
add edx, eax
mov eax, DWORD PTR [rbp+16]
add eax, edx
pop rbp
ret
可以看到函數從6個寄存器和1個棧地址中讀取參數。曾幾何時，以為面試官也曾經問我，函數的參數是通過什麼傳遞的，我就說寄存器，寄存器不夠了，就用棧。然後他接著問我幾個寄存器不夠了，就用棧了。。我有點啞口無言。說了個四五個。。其實這種問題是很開放的。通過上面的代碼我們可以看到是6個寄存器。edi，esi，edx，ecx，r8d，r9d。然而，這只是我64位系統上的（r8d，r9d是X64上才有的），X86則不同（具體我沒3試）。那麼是不是說，你和麵試官說，“在64位系統中，使用的是6個寄存器來傳遞函數參數，參數多了，就使用棧來傳遞”。這樣回答就完美了麼？其實不是的。
剛才的示例代碼中都規避了一些情景。上面我使用的函數的參數類型都是整型int。而如果參數類型是浮點型，指針等等其他類型就不能使用寄存器來傳遞函數參數了。具體這些問題探究起來就太多了，我在這裡也只是拋磚引玉。大家可以自己去試試。推薦一篇文章《X86-64寄存器和棧幀》
說個題外話，上面我的代碼如果開了優化會怎麼樣呢？用gcc -S -masm=intel -O 來編譯一下看看。此時它的彙編代碼為：
main:
.LFB25:
sub rsp, 8
mov edx, 28
mov esi, OFFSET FLAT:.LC0
mov edi, 1
mov eax, 0
call __printf_chk
add rsp, 8
ret
哈哈。看到了吧，開了優化之後main函數裡面連函數調用都沒有。直接把28賦值給了寄存器edx，然後讓printf來打印。28是啥？正是1 + 2 + 3 + 4 + 5 + 6 +7=28是也。所以我強調，儘量不要在開啟優化選項的時候研究編譯器行為，開了優化以後編譯器保證的只是最終一致性，破壞力原有的程序邏輯。不具備通用性，不利於理解編程語言和編譯器行為。當然大家也不要斷章取義。其實我只是說在研究本文所探討的問題的時候，不要開優化。如果正常的生產環境下，編譯器優化可是很有用的。另外如果你研究的就是編譯器的優化行為那麼優化開關當然也要打開了。
sp和bp
前面已經解釋過sp（棧頂指針寄存器）和bp（基址寄存器）。需要明確的是：
sp所指向的棧頂是我們所能分配的棧空間的極限，如果棧空間不夠則需要移動sp指針，分配更多的棧空間。如前文所述，棧的地址增長方式是從高地址到低地址，所以sp指向的是我們能夠使用的棧地址的最低出。
看一段C代碼：
#include <stdio.h>
int add(int a, int b)
{
int c = a + b;
return c;
}
int main()
{
int a = 2;
int b = 3;
int c = add(a, b);
printf("%d\n", c);
}
其主要彙編代碼為：
add:
.LFB0:
push rbp
mov rbp, rsp
mov DWORD PTR [rbp-20], edi
mov DWORD PTR [rbp-24], esi
mov eax, DWORD PTR [rbp-24]
mov edx, DWORD PTR [rbp-20]
add eax, edx
mov DWORD PTR [rbp-4], eax
mov eax, DWORD PTR [rbp-4]
pop rbp
ret
.LFE0:
.size add, .-add
.section .rodata
.LC0:
.string "%d\n"
.text
.globl main
.type main, @function
main:
.LFB1:
push rbp
mov rbp, rsp
sub rsp, 16
mov DWORD PTR [rbp-4], 2
mov DWORD PTR [rbp-8], 3
mov edx, DWORD PTR [rbp-8]
mov eax, DWORD PTR [rbp-4]
mov esi, edx
mov edi, eax
call add
mov DWORD PTR [rbp-12], eax
mov eax, DWORD PTR [rbp-12]
mov esi, eax
mov edi, OFFSET FLAT:.LC0
mov eax, 0
call printf
leave
ret
可以看到在main函數開始部分有三步走：
先將原始bp入棧
然後將sp賦值給bp
最後進行了一個sp減16的操作。（棧頂向下移動16，即多分配16字節空間）
前兩步是每個函數開始的必備操作，保存原始的棧位置（bp入棧，便於函數調用結束後恢復原函數的棧位置）。第三步不是必備操作，僅當函數中局部變量過多時會進行棧指針的移動來分配更多的空間，我們可以看到add函數的開始部分是沒有這個操作的。
接著看一下add函數的結束部分。兩步操作：
出棧，將保存在棧裡的值（原始bp）恢復給bp（pop rbp）
結束當前函數，控制權轉移給調用它的函數（ret）。
這兩個是函數結束時的必備操作。關於函數的返回值主要是通過eax寄存器來返回。本文聚焦堆、棧，不再過多介紹寄存器的知識。
看一個trick現象：
#include <stdio.h>
void declare()
{
int i;
int a[100];
for (i = 0;i < 100; i++)
{
a[i] = i;
}
}
void print()
{
int i;
int a[100];
for (i = 0;i < 100; i++)
{
printf("%d\n", a[i]);
}
}
int main()
{
declare();
print();
}
用gcc編譯一下，看看該程序的運行結果是什麼，教科書告訴我們：在declare函數中聲明的局部變量a[100]在函數結束後被銷燬了，在print函數中去打印a[100]數組將輸出不確定的值。
yes，這樣理解完全沒有問題。but，這個程序確確實實可以成功打印出0到99這100個數。why？
彙編代碼我們就不看了。原理很簡單，那就是：decalre函數返回之後確實它的棧空間被銷燬了，其實所謂的銷燬只不過是sp指針回到declare函數被調用前的原位，即main函數中sp位置，實際上declare函數給棧空間中賦的值卻並不會被刪除。當print函數被調用的時候，sp指針又繼續向下移動，這時的循環輸出語句會將之前儲存在棧空間中的值進行打印。
通過這個例子，我只想說明關於棧自動銷燬釋放的真實情況，其實只是sp指針的移動而已。然而我們並不能依賴上述這種行為，比如：我們開了優化之後gcc -O去編譯一下，其輸出結果卻是又是未定義的了。
我整理了一套資料，想學習編程的小夥伴們可以轉發+關注+私信回覆：“資料”就可以拿到一份我為大家準備的編程學習資料！
堆
概念與分配策略
所謂“堆”，即動態存儲區，與棧不同，堆是在程序運行時被分配的。C語言中的malloc，C++中的new完成的都是堆上的操作。堆不會自動釋放所以需要free和delete。
還記得經典面試題嗎：比較一下malloc和new的不同。這個問題其實不難，首先明確：malloc是函數，而new是關鍵字。然後new作為C++中動態對象創建的基石，除了完成堆空間的分配操作以外還要完成一些初始化操作，及new的過程中會調用對象的構造函數去初始化，而malloc不會。最後要明確的是malloc分配的內存只能用free來釋放，而new分配的地址只能用delete來釋放，如果new分配的是數組，則需要delete[ ]來釋放，否則會出現未定義行為。
無論是malloc還是new返回的都是一個指針，即堆地址。堆與棧不同它不是順序分配的，而是離散分配的，它的空閒內存可能不是連續的，而是斷斷續續的，通常通過鏈表來連接每個空閒存儲區（實際數據結構要更復雜和多樣化）。關於動態內存的分配策略其實大家的“操作系統”課上都有學過，只不過通常大家很難直接和malloc/new聯繫起來。
隨便翻開一本操作系統的課本，找到存儲器管理的章節都能找到動態內存的分配策略（簡單描述之）：
首次適應算法：在空閒區鏈首開始向後尋找，找到第一塊能滿足所需大小的空閒塊
循環首次適應算法：從上一次找的空閒區開始向後尋找。直到鏈尾都不滿足，則返回鏈首尋找空閒塊
最佳適應算法：每次分配內存時，都選擇能滿足要求，並且又是最小的空閒塊。優點是：每次第一次找到的滿足要求的空閒塊，必然是最佳的
最壞適應算法：每次總是選擇一個最大的空閒塊分配給進程使用。優點是：產生內存碎片的機率較小
快速適應算法：將空閒區依據其容量大小進行分類，每一類同容量的空閒塊都有自己的鏈表。同時在內存中設立一張管理索引表，每個表項為一種空閒塊類型，並記錄其鏈首指針。其優點是：查找效率高，不會產生內存碎片。缺點是實現複雜，系統開銷大。
實際上真實的堆內存管理要比上述各類算法所描述的還要複雜。比如內存管理器（一般是glibc的ptmalloc）可能將零散的空閒內存移動到一起，形成更大的空閒內存塊。基於各自不同的動態內存分配策略，很多其他的內存管理器應運而生，比如谷歌的 tcmalloc，BSD的jemalloc。
堆首地址
我們通過malloc分配的內存空間返回給我們一個這段內存的首地址，你有沒有疑問，當我們free的時候，只是將該首地址傳遞給free函數。而free函數又是如何知道該釋放該首地址以後多大的內存空間的呢？在初學的時候，我有這個疑惑，我認為如果是我來實習free函數的話，它需要兩個參數：帶釋放堆內存的首地址及其偏移量（分配空間的大小）。
實際上關於這個問題，不同的內存管理器有各自的策略，但大致的思想就是將偏移量存儲在內存中。比如一種簡單實現是：在堆分配內存的時候，通常會比你需要的內存多分配一些，其中一部分用於字節對齊（本文暫不討論，本博客其他博文中有涉及4字節/8字節對齊的內容），另外一小部分用於存取偏移量。比如用前4個字節存儲已分配內存的大小，然後將其後面的地址返回，首地址前的4個字節可以被稱之為“首部”。這樣free的時候，先搜索該首地址前的首部，取出這個值即為偏移量。（這只是一種最簡單的概念性的方案，實際編譯器的解決方案更為複雜，但無一例外都會分配額外的內存保存元數據）
知道這點後，我們可以理解這樣一種C語法的限制，那就是free的時候，其參數只能是malloc等動態內存分配函數返回的（顯然，不包括new）值。舉個例子：
char *a = malloc(100);
free(a+10);
比如你分配了100個字節，其首地址為a，如果你將a+10（首地址之後偏移10字節處）傳遞給free，那麼free並不能為你釋放掉剩餘的90個字節，並且這是一個危險的行為。因為內存管理器會將a+10位置之前視作首部，並從中去取出該段地址的“偏移量”，然後進行釋放。顯然這樣是達不到你想要的效果的。
當然，這只是舉了一種例子來闡述free函數的參數為什麼只需要一個首地址，實際上其真實的行為遠比我這裡描述的要複雜，可能有首部，還有尾部，其存儲的內容除了偏移量以外可能還有其他信息，比如空閒鏈表的信息等。
虛擬地址和MMU
內存是分頁的（頁式存儲）。物理內存、虛擬內存都是。並且這兩者的頁大小是嚴格相同的。不同之處當然是物理內存的頁數比較多，虛擬內存的頁數比較少。這兩者之間是存在一定映射關係的。通過一道筆試題來揭露這種關係：
某虛擬存儲器的用戶編程空間共4個頁面，每頁1K，主存位16K，假定某時刻系統為用戶的0,1,2,3頁分別分配物理塊號6,8,12,3中，則虛擬地址0C8Eh對應的物理地址為：_____
這道題虛擬地址位CC8Eh，h表示16進制。為了便於計算可以把它轉換位十進制：0C8Eh = 3214。接著計算它所屬的頁號和頁內偏移，頁面大小是1K，即1024。頁號=3214/1024 = 3。偏移=3214%1024=142
物理地址=物理頁號*頁面大小+頁內偏移。因為根據題意，邏輯地址中的3號頁對應物理地址中的頁號也是3。所以實際這題物理地址和邏輯地址是一樣的。
共享庫
基本概念
在進程的內存空間圖示中，有一段標識是：共享庫內存映射區。表示這段內存地址是給共享庫使用的。何謂“共享庫（shared libraries）”？共享庫在Windows系統中叫做動態鏈接庫（.dll），或者簡稱“動態庫”。動態庫就需要和靜態庫區分開來。你應該見過這兩種庫，知識你不知道罷了。
如果一個程序引用了靜態庫，那麼在編譯期靜態庫文件就會和該程序編譯到一起。這樣編譯出來的可執行文件通常比較大，並且如果多個程序都使用了同一個靜態庫，那麼每個程序編譯後的文件都包含一份該靜態庫的拷貝；而如果一個程序引用了共享庫，那麼在編譯期共享庫文件不會和該程序編譯到一起，而是在程序運行時動態地加載該共享庫文件。如果多個程序都使用了同一個共享庫，那麼這些程序都是在運行時加載該共享庫，系統中之後存在一份該庫的拷貝，這就是為什麼叫做共享庫的原因。
因為共享庫是運行時加載的，在加載後也必須有一個地址，圖中的“共享內存映射區”就是用來給共享庫分配地址的，它的地址增長方式同堆一樣，從低到高。
關於共享庫如何實現的，如何動態連接的。本文不詳述，有興趣的可以閱讀《深入理解計算機系統》的“鏈接”一章。
鏈接共享庫
另外需要注意的是，如果你要鏈接的共享庫（動態庫）不是標準庫，並且不在標準庫的路徑下。那麼在編譯的時候通常會報錯。此時需要給gcc加上-L選項加上共享庫所在的路徑，並用-l選項去連接對應的庫，這裡要明確的是如果你的庫文件名叫libabc.so.1234那麼連接選項l要寫成 -labc（去掉前後綴），而當同一個庫裡面同時有靜態庫和共享庫的時候，優先連接的是共享庫。
此時只是解決了編譯期間的麻煩，因為共享庫實際是程序運行時鏈接的，即使你編譯期間使用了-L選項也可能會找不到庫（-L只解決編譯期間的問題）。如果你有root的話，那麼去/etc/ld.so.conf.d/目錄下，新建一個conf文件，裡面加入你的庫路徑。然後用ldconfig命令刷新共享庫路徑。
但如果你沒有root權限的話，你可以使用gcc的-Wl,-rpath選項去指定路徑(這是一個選項)。此時一個完整的編譯命令類似：
gcc -L /home/jelly/lib/ \
-labc \
-Wl,-rpath=/home/jelly/lib/
我整理了一套資料，想學習編程的小夥伴們可以轉發+關注+私信回覆：“資料”就可以拿到一份我為大家準備的編程學習資料！