1.     內(nèi)核棧
   

2.     中斷棧

3.     進程棧

4.     線程棧

5.     硬件棧

6.     軟件棧

7.     堆棧

8.     還有人占著茅坑

        昨天我們聊了ARM32上或是奇葩或者先進的中斷棧，我們今天繼續(xù)來聊“棧”。

01 啥是棧

—

先看看啥是棧？棧的英文叫做stack。那中文里棧是怎么解釋的呢？

1.儲存貨物或供旅客住宿的房屋：貨棧｜客棧。

2.養(yǎng)牲畜的竹、木柵欄：馬棧。

那在計算機，它是啥呢，其實就是一個存放數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)類型。一種只能在一端進行插入和刪除操作的特殊線性表。它按照先進后出的原則存儲數(shù)據(jù)，先進入的數(shù)據(jù)被壓入棧底，最后的數(shù)據(jù)在棧頂，需要讀數(shù)據(jù)的時候從棧頂開始彈出數(shù)據(jù)（最后一個數(shù)據(jù)被第一個讀出來）?？聪旅孢@個圖應(yīng)該比較清楚了。

這種數(shù)據(jù)結(jié)構(gòu)的特點是 后入先出 (LIFO, Last In First Out)，數(shù)據(jù)只能在串列的一端 (稱為：棧頂 top) 進行 推入 (push) 和 彈出 (pop) 操作。向棧中存儲數(shù)據(jù)稱為PUSH，從棧中取數(shù)據(jù)稱為POP。

大多數(shù)的處理器架構(gòu)，都有實現(xiàn)硬件棧。有專門的棧指針寄存器，以及特定的硬件指令來完成 入棧/出棧 的操作。例如在 ARM 架構(gòu)上，R13 (SP) 指針是堆棧指針寄存器，而 PUSH 是用于壓棧的匯編指令，POP 則是出棧的匯編指令。

我們常常聽人說，堆棧，那堆棧是個什么鬼？究竟是堆呢還是棧呢？其實堆棧本身就是棧，只是換了個抽象的名字，換了個馬甲，有些人就昏了。

那堆是什么？在數(shù)據(jù)結(jié)構(gòu)里，堆可以被看成是一棵樹，如：堆排序。在操作系統(tǒng)里，堆是操作系統(tǒng)里管理內(nèi)存的一種方式， 一般由程序員分配釋放， 若程序員不釋放，程序結(jié)束時可能由OS回收，分配方式倒是類似于鏈表。而棧，由操作系統(tǒng)自動分配釋放 ，存放函數(shù)的參數(shù)值，局部變量的值等。

所以，堆和棧還有堆棧，他們?nèi)齻€是不是容易搞混了。

棧主要是有兩大作用，一個是函數(shù)調(diào)用，另外一個是進程調(diào)度。

先說說函數(shù)調(diào)用。我們知道函數(shù)調(diào)用需要注意哪些東西？大家想到的可能是

1. 參數(shù)怎么傳

2. 函數(shù)返回值怎么傳

那在不同的計算機體系結(jié)構(gòu)里，有不同的做法，但是他們相同的地方是一定會用到棧。

ARM和ARM64使用的是ATPCS(ARM-Thumb Procedure Call Standard/ARM-Thumb過程調(diào)用標準)的函數(shù)調(diào)用約定。

對于ARM來說：

參數(shù)1~參數(shù)4 分別保存到 R0~R3 寄存器中 ，剩下的參數(shù)從右往左一次入棧，返回值存放在 R0 中。

對于ARM64來說：

參數(shù)1~參數(shù)8 分別保存到 X0~X7 寄存器中 ，剩下的參數(shù)從右往左一次入棧，返回值存放在 X0 中。

總之，會用到棧來保存函數(shù)調(diào)用的參數(shù)。另外還有一個東西需要保存，那就是局部變量。

以ARM32為例，一個函數(shù)A調(diào)用另外一個函數(shù)B的棧的布局圖如下。fp寄存器（r11）和sp寄存器兩個指向的區(qū)域，稱為一個棧幀（stack frame），函數(shù)調(diào)用經(jīng)常是嵌套的，在同一時刻，棧中會有多個函數(shù)的信息。每個未完成運行的函數(shù)占用一個獨立的連續(xù)區(qū)域，即棧幀。棧幀存放著函數(shù)參數(shù)，局部變量及恢復前一棧幀所需要的數(shù)據(jù)等。

如上圖所示，假設(shè)當前運行在函數(shù)B里面，那么當前的fp和sp寄存器所指示的區(qū)域就是當前的棧，棧幀B。當函數(shù)B返回到函數(shù)A時候，棧幀B里保存的sp和fp寄存器所構(gòu)造的另一個棧，就是棧幀A了。

所以，棧是鏈接起來的‘楨’的一個列表，按遞減地址次序分配棧的每一塊。寄存器 sp 總是指向在最當前楨中最低的使用的地址。ARM上棧有點奇葩。

其他CPU體系結(jié)構(gòu)中說的SP棧指針，都是指向棧頂?shù)?，但是ARM的棧是自減棧，棧是向下生長的，也就是棧底處于高地址處，棧頂處于低地址處。有點奇葩和繞口。

棧還有另外一個用途就是進程切換。每個進程都有自己的系統(tǒng)?？臻g，這個?？臻g說的是內(nèi)核棧，這個是在fork的時候就分配好的。所以，進程切換的時候，需要把前任的進程的上下文保存到前任進程的內(nèi)核棧里。在每一個進程的生命周期中，必然會通過到系統(tǒng)調(diào)用陷入內(nèi)核。在執(zhí)行系統(tǒng)調(diào)用陷入內(nèi)核之后，這些內(nèi)核代碼所使用的棧并不是原先進程用戶空間中的棧，而是一個單獨內(nèi)核空間的棧，這個稱作進程內(nèi)核棧。進程跑在用戶空間，需要一個棧，進程跑在內(nèi)核空間也需要一個棧，所以這些棧的定義是不一樣。

我們下一次在來和大家聊聊哪些“?！闭l的便宜。

最后一個問題，CPU上電時候第一條指令為什么要用匯編來實現(xiàn)？能不能讓CPU第一條指令就執(zhí)行C語言的代碼？

能還是不能？為啥子嘛？