電子發燒友App
1、棧是什么？棧有什么作用？
首先，棧 (stack) 是一種串列形式的?數據結構。這種數據結構的特點是?后入先出?(LIFO, Last In First Out)，數據只能在串列的一端 (稱為：棧頂 top) 進行?推入?(push) 和?彈出?(pop) 操作。根據棧的特點，很容易的想到可以利用數組，來實現這種數據結構。但是本文要討論的并不是軟件層面的棧，而是硬件層面的棧。 ????
大多數的處理器架構，都有實現硬件棧。有專門的棧指針寄存器，以及特定的硬件指令來完成 入棧/出棧 的操作。例如在 ARM 架構上，R13 (SP) 指針是堆棧指針寄存器，而 PUSH 是用于壓棧的匯編指令，POP 則是出棧的匯編指令。? ? ARM 處理器擁有 37 個寄存器。這些寄存器按部分重疊組方式加以排列。每個處理器模式都有一個不同的寄存器組。編組的寄存器為處理處理器異常和特權操作提供了快速的上下文切換。 2、提供了下列寄存器：? - 三十個 32 位通用寄存器：?
- 存在十五個通用寄存器，它們分別是 r0-r12、sp、lr?
- sp (r13) 是堆棧指針。C/C++ 編譯器始終將 sp 用作堆棧指針?
- lr (r14) 用于存儲調用子例程時的返回地址。如果返回地址存儲在堆棧上，則可將 lr 用作通用寄存器?
- 程序計數器 (pc)：指令寄存器?
- 應用程序狀態寄存器 (APSR)：存放算術邏輯單元 (ALU) 狀態標記的副本?
- 當前程序狀態寄存器 (CPSR)：存放 APSR 標記，當前處理器模式，中斷禁用標記等?
- 保存的程序狀態寄存器 (SPSR)：當發生異常時，使用 SPSR 來存儲 CPSR 上面是棧的原理和實現，下面我們來看看棧有什么作用。棧作用可以從兩個方面體現：函數調用?和多任務支持?。
4、函數調用
我們知道一個函數調用有以下三個基本過程：?
- 調用參數的傳入?
- 局部變量的空間管理?
- 函數返回 函數的調用必須是高效的，而數據存放在 CPU通用寄存器?或者 RAM 內存?中無疑是最好的選擇。以傳遞調用參數為例，我們可以選擇使用 CPU通用寄存器 來存放參數。但是通用寄存器的數目都是有限的，當出現函數嵌套調用時，子函數再次使用原有的通用寄存器必然會導致沖突。因此如果想用它來傳遞參數，那在調用子函數前，就必須先?保存原有寄存器的值，然后當子函數退出的時候再?恢復原有寄存器的值?。 函數的調用參數數目一般都相對少，因此通用寄存器是可以滿足一定需求的。但是局部變量的數目和占用空間都是比較大的，再依賴有限的通用寄存器未免強人所難，因此我們可以采用某些 RAM 內存區域來存儲局部變量。但是存儲在哪里合適？既不能讓函數嵌套調用的時候有沖突，又要注重效率。 這種情況下，棧無疑提供很好的解決辦法。一、對于通用寄存器傳參的沖突，我們可以再調用子函數前，將通用寄存器臨時壓入棧中；在子函數調用完畢后，在將已保存的寄存器再彈出恢復回來。二、而局部變量的空間申請，也只需要向下移動下棧頂指針；將棧頂指針向回移動，即可就可完成局部變量的空間釋放；三、對于函數的返回，也只需要在調用子函數前，將返回地址壓入棧中，待子函數調用結束后，將函數返回地址彈出給 PC 指針，即完成了函數調用的返回； 于是上述函數調用的三個基本過程，就演變記錄一個棧指針的過程。每次函數調用的時候，都配套一個棧指針。即使循環嵌套調用函數，只要對應函數棧指針是不同的，也不會出現沖突。 ????
函數調用經常是嵌套的，在同一時刻，棧中會有多個函數的信息。每個未完成運行的函數占用一個獨立的連續區域，稱作棧幀(Stack Frame)。棧幀存放著函數參數，局部變量及恢復前一棧幀所需要的數據等，函數調用時入棧的順序為： 實參N~1 → 主調函數返回地址 → 主調函數幀基指針EBP → 被調函數局部變量1~N 棧幀的邊界由?棧幀基地址指針 EBP 和?棧指針 ESP 界定，EBP 指向當前棧幀底部(高地址)，在當前棧幀內位置固定；ESP指向當前棧幀頂部(低地址)，當程序執行時ESP會隨著數據的入棧和出棧而移動。因此函數中對大部分數據的訪問都基于EBP進行。函數調用棧的典型內存布局如下圖所示：
5、多任務支持
然而棧的意義還不只是函數調用，有了它的存在，才能構建出操作系統的多任務模式。我們以 main 函數調用為例，main 函數包含一個無限循環體，循環體中先調用 A 函數，再調用 B 函數。?
?
func B(): return;func A(): B();func main(): while (1) A();試想在單處理器情況下，程序將永遠停留在此 main 函數中。即使有另外一個任務在等待狀態，程序是沒法從此 main 函數里面跳轉到另一個任務。因為如果是函數調用關系，本質上還是屬于 main 函數的任務中，不能算多任務切換。此刻的 main 函數任務本身其實和它的棧綁定在了一起，無論如何嵌套調用函數，棧指針都在本棧范圍內移動。 由此可以看出一個任務可以利用以下信息來表征：?
1. main 函數體代碼?
2. main 函數棧指針?
3. 當前 CPU 寄存器信息 假如我們可以保存以上信息，則完全可以強制讓出 CPU 去處理其他任務。只要將來想繼續執行此 main 任務的時候，把上面的信息恢復回去即可。有了這樣的先決條件，多任務就有了存在的基礎，也可以看出棧存在的另一個意義。在多任務模式下，當調度程序認為有必要進行任務切換的話，只需保存任務的信息（即上面說的三個內容）。恢復另一個任務的狀態，然后跳轉到上次運行的位置，就可以恢復運行了。 可見每個任務都有自己的棧空間，正是有了獨立的棧空間，為了代碼重用，不同的任務甚至可以混用任務的函數體本身，例如可以一個main函數有兩個任務實例。至此之后的操作系統的框架也形成了，譬如任務在調用 sleep() 等待的時候，可以主動讓出 CPU 給別的任務使用，或者分時操作系統任務在時間片用完是也會被迫的讓出 CPU。不論是哪種方法，只要想辦法切換任務的上下文空間，切換棧即可。 ????
- 任務 = 送貨?
- 線程 = 開送貨車?
- 系統調度 = 決定合適開哪部送貨車?
- 進程 = 道路 + 加油站 + 送貨車 + 修車廠
?
?
6、Linux 中有幾種棧？各種棧的內存位置？
介紹完棧的工作原理和用途作用后，我們回歸到 Linux 內核上來。內核將棧分成四種：
進程棧
線程棧
內核棧
中斷棧
一、進程棧
進程棧是屬于用戶態棧，和進程?虛擬地址空間 (Virtual Address Space)?密切相關。那我們先了解下什么是虛擬地址空間：在 32 位機器下，虛擬地址空間大小為 4G。這些虛擬地址通過頁表 (Page Table) 映射到物理內存，頁表由操作系統維護，并被處理器的內存管理單元 (MMU) 硬件引用。每個進程都擁有一套屬于它自己的頁表，因此對于每個進程而言都好像獨享了整個虛擬地址空間。 Linux 內核將這 4G 字節的空間分為兩部分，將最高的 1G 字節（0xC0000000-0xFFFFFFFF）供內核使用，稱為?內核空間。而將較低的3G字節（0x00000000-0xBFFFFFFF）供各個進程使用，稱為用戶空間。每個進程可以通過系統調用陷入內核態，因此內核空間是由所有進程共享的。雖然說內核和用戶態進程占用了這么大地址空間，但是并不意味它們使用了這么多物理內存，僅表示它可以支配這么大的地址空間。它們是根據需要，將物理內存映射到虛擬地址空間中使用。 ????
Linux 對進程地址空間有個標準布局，地址空間中由各個不同的內存段組成 (Memory Segment)，主要的內存段如下：?
- 程序段 (Text Segment)：可執行文件代碼的內存映射?
- 數據段 (Data Segment)：可執行文件的已初始化全局變量的內存映射?
- BSS段 (BSS Segment)：未初始化的全局變量或者靜態變量（用零頁初始化）?
- 堆區 (Heap) : 存儲動態內存分配，匿名的內存映射?
- 棧區 (Stack) : 進程用戶空間棧，由編譯器自動分配釋放，存放函數的參數值、局部變量的值等?
- 映射段(Memory Mapping Segment)：任何內存映射文件 ????
而上面進程虛擬地址空間中的棧區，正指的是我們所說的進程棧。進程棧的初始化大小是由編譯器和鏈接器計算出來的，但是棧的實時大小并不是固定的，Linux 內核會根據入棧情況對棧區進行動態增長（其實也就是添加新的頁表）。但是并不是說棧區可以無限增長，它也有最大限制RLIMIT_STACK (一般為 8M)，我們可以通過 ulimit 來查看或更改 RLIMIT_STACK 的值。 我們要知道棧的大小，那必須得知道棧的起始地址和結束地址。棧起始地址?獲取很簡單，只需要嵌入匯編指令獲取棧指針 esp 地址即可。棧結束地址?的獲取有點麻煩，我們需要先利用遞歸函數把棧搞溢出了，然后再 GDB 中把棧溢出的時候把棧指針 esp 打印出來即可。代碼如下：? ?
?
?
/* file name: stacksize.c */
void *orig_stack_pointer;
void blow_stack() {
blow_stack();
}
int main() {
__asm__("movl %esp, orig_stack_pointer");
blow_stack();
return 0;
}
$ g++ -g stacksize.c -o ./stacksize
$ gdb ./stacksize
(gdb) r
Starting program: /home/home/misc-code/setrlimit
Program received signal SIGSEGV, Segmentation fault.
blow_stack () at setrlimit.c:4
4 blow_stack();
(gdb) print (void *)$esp
$1 = (void *) 0xffffffffff7ff000
(gdb) print (void *)orig_stack_pointer
$2 = (void *) 0xffffc800
(gdb) print 0xffffc800-0xff7ff000
$3 = 8378368 // Current Process Stack Size is 8M
? 上面對進程的地址空間有個比較全局的介紹，那我們看下 Linux 內核中是怎么體現上面內存布局的。內核使用內存描述符來表示進程的地址空間，該描述符表示著進程所有地址空間的信息。內存描述符由 mm_struct 結構體表示，下面給出內存描述符結構中各個域的描述，請大家結合前面的 進程內存段布局 圖一起看：?
struct mm_struct {
struct vm_area_struct *mmap; /* 內存區域鏈表 */
struct rb_root mm_rb; /* VMA 形成的紅黑樹 */
...
struct list_head mmlist; /* 所有 mm_struct 形成的鏈表 */
...
unsigned long total_vm; /* 全部頁面數目 */
unsigned long locked_vm; /* 上鎖的頁面數據 */
unsigned long pinned_vm; /* Refcount permanently increased */
unsigned long shared_vm; /* 共享頁面數目 Shared pages (files) */
unsigned long exec_vm; /* 可執行頁面數目 VM_EXEC & ~VM_WRITE */
unsigned long stack_vm; /* 棧區頁面數目 VM_GROWSUP/DOWN */
unsigned long def_flags;
unsigned long start_code, end_code, start_data, end_data; /* 代碼段、數據段 起始地址和結束地址 */
unsigned long start_brk, brk, start_stack; /* 棧區 的起始地址，堆區 起始地址和結束地址 */
unsigned long arg_start, arg_end, env_start, env_end; /* 命令行參數 和 環境變量的 起始地址和結束地址 */
...
/* Architecture-specific MM context */
mm_context_t context; /* 體系結構特殊數據 */
/* Must use atomic bitops to access the bits */
unsigned long flags; /* 狀態標志位 */
...
/* Coredumping and NUMA and HugePage 相關結構體 */
};
? ????
?
?
二、線程棧
從 Linux 內核的角度來說，其實它并沒有線程的概念。Linux 把所有線程都當做進程來實現，它將線程和進程不加區分的統一到了 task_struct 中。線程僅僅被視為一個與其他進程共享某些資源的進程，而是否共享地址空間幾乎是進程和 Linux 中所謂線程的唯一區別。線程創建的時候，加上了 CLONE_VM 標記，這樣?線程的內存描述符 將直接指向 父進程的內存描述符。? ??
?
if (clone_flags & CLONE_VM) {
/*
* current 是父進程而 tsk 在 fork() 執行期間是共享子進程
*/
atomic_inc(¤t->mm->mm_users);
tsk->mm = current->mm;
}
? 雖然線程的地址空間和進程一樣，但是對待其地址空間的 stack 還是有些區別的。對于 Linux 進程或者說主線程，其 stack 是在 fork 的時候生成的，實際上就是復制了父親的 stack 空間地址，然后寫時拷貝 (cow) 以及動態增長。然而對于主線程生成的子線程而言，其 stack 將不再是這樣的了，而是事先固定下來的，使用 mmap 系統調用，它不帶有 VM_STACK_FLAGS 標記。這個可以從 glibc 的nptl/allocatestack.c 中的 allocate_stack()?函數中看到：? ??
mem = mmap (NULL, size, prot,
MAP_PRIVATE | MAP_ANONYMOUS | MAP_STACK, -1, 0);
? 由于線程的 mm->start_stack 棧地址和所屬進程相同，所以線程棧的起始地址并沒有存放在task_struct 中，應該是使用 pthread_attr_t 中的 stackaddr 來初始化 task_struct->thread->sp（sp 指向 struct pt_regs 對象，該結構體用于保存用戶進程或者線程的寄存器現場）。這些都不重要，重要的是，線程棧不能動態增長，一旦用盡就沒了，這是和生成進程的 fork 不同的地方。由于線程棧是從進程的地址空間中 map 出來的一塊內存區域，原則上是線程私有的。但是同一個進程的所有線程生成的時候淺拷貝生成者的 task_struct 的很多字段，其中包括所有的 vma，如果愿意，其它線程也還是可以訪問到的，于是一定要注意。
?
?
三、進程內核棧
在每一個進程的生命周期中，必然會通過到系統調用陷入內核。在執行系統調用陷入內核之后，這些內核代碼所使用的棧并不是原先進程用戶空間中的棧，而是一個單獨內核空間的棧，這個稱作進程內核棧。進程內核棧在進程創建的時候，通過 slab 分配器從 thread_info_cache 緩存池中分配出來，其大小為 THREAD_SIZE，一般來說是一個頁大小 4K；??
?
union thread_union {
struct thread_info thread_info;
unsigned long stack[THREAD_SIZE/sizeof(long)];
}; ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
thread_union 進程內核棧 和 task_struct 進程描述符有著緊密的聯系。由于內核經常要訪問task_struct，高效獲取當前進程的描述符是一件非常重要的事情。因此內核將進程內核棧的頭部一段空間，用于存放 thread_info 結構體，而此結構體中則記錄了對應進程的描述符，兩者關系如下圖（對應內核函數為 dup_task_struct()）： ????
register unsigned long current_stack_pointer asm ("sp");
static inline struct thread_info *current_thread_info(void)
{
return (struct thread_info *)
(current_stack_pointer & ~(THREAD_SIZE - 1));
}
#define get_current() (current_thread_info()->task)
#define current get_current() ? ? ? ? ? ? ? ? ? ? ?
?
?
四、中斷棧
進程陷入內核態的時候，需要內核棧來支持內核函數調用。中斷也是如此，當系統收到中斷事件后，進行中斷處理的時候，也需要中斷棧來支持函數調用。由于系統中斷的時候，系統當然是處于內核態的，所以中斷棧是可以和內核棧共享的。但是具體是否共享，這和具體處理架構密切相關。 X86 上中斷棧就是獨立于內核棧的；獨立的中斷棧所在內存空間的分配發生在arch/x86/kernel/irq_32.c 的 irq_ctx_init()?函數中(如果是多處理器系統，那么每個處理器都會有一個獨立的中斷棧)，函數使用?__alloc_pages 在低端內存區分配 2個物理頁面，也就是8KB大小的空間。有趣的是，這個函數還會為 softirq 分配一個同樣大小的獨立堆棧。如此說來，softirq 將不會在 hardirq 的中斷棧上執行，而是在自己的上下文中執行。 ????
而 ARM 上中斷棧和內核棧則是共享的；中斷棧和內核棧共享有一個負面因素，如果中斷發生嵌套，可能會造成棧溢出，從而可能會破壞到內核棧的一些重要數據，所以棧空間有時候難免會捉襟見肘。
7、Linux 為什么需要區分這些棧？
為什么需要區分這些棧，其實都是設計上的問題。這里就我看到過的一些觀點進行匯總，供大家討論：
為什么需要單獨的進程內核棧？
所有進程運行的時候，都可能通過系統調用陷入內核態繼續執行。假設第一個進程 A 陷入內核態執行的時候，需要等待讀取網卡的數據，主動調用 schedule()?讓出 CPU；此時調度器喚醒了另一個進程 B，碰巧進程 B 也需要系統調用進入內核態。那問題就來了，如果內核棧只有一個，那進程 B 進入內核態的時候產生的壓棧操作，必然會破壞掉進程 A 已有的內核棧數據；一但進程 A 的內核棧數據被破壞，很可能導致進程 A 的內核態無法正確返回到對應的用戶態了；
為什么需要單獨的線程棧？
此時 A1 的棧指針 esp 如果為初始值 0x7ffc80000000，則線程 A1 一但出現函數調用，必然會破壞父進程 A 已入棧的數據。
如果此時線程 A1 的棧指針和父進程最后更新的值一致，esp 為 0x7ffc8000FF00，那線程 A1 進行一些函數調用后，棧指針 esp 增加到 0x7ffc8000FFFF，然后線程 A1 休眠；調度器再次換成父進程 A 執行，那這個時候父進程的棧指針是應該為 0x7ffc8000FF00 還是 0x7ffc8000FFFF 呢？無論棧指針被設置到哪個值，都會有問題不是嗎？
Linux 調度程序中并沒有區分線程和進程，當調度程序需要喚醒”進程”的時候，必然需要恢復進程的上下文環境，也就是進程棧；但是線程和父進程完全共享一份地址空間，如果棧也用同一個那就會遇到以下問題。假如進程的棧指針初始值為 0x7ffc80000000；父進程 A 先執行，調用了一些函數后棧指針 esp 為 0x7ffc8000FF00，此時父進程主動休眠了；接著調度器喚醒子線程 A1：?
進程和線程是否共享一個內核棧？
No，線程和進程創建的時候都調用 dup_task_struct 來創建 task 相關結構體，而內核棧也是在此函數中 alloc_thread_info_node 出來的。因此雖然線程和進程共享一個地址空間 mm_struct，但是并不共享一個內核棧。
為什么需要單獨中斷棧？
這個問題其實不對，ARM 架構就沒有獨立的中斷棧。
編輯：黃飛
?
工商網監
評論