[[319501]]

 

本文轉載自微信公眾號「herongwei」，轉載本文請聯系「herongwei」公眾號。

前言

• 什么是 User space 與 Kernel space?
• 什么是棧區?
• 什么是堆區?
• malloc 算法是如何實現的?
• Linux 系統下，有幾種堆空間分配方式?
• Linux 下一個進程地址空間布局是怎樣的?

上面幾個問題，你心里有答案嗎?如果沒有，跟我一起來探究一下吧。

1、User space 與 Kernel space

現代的應用程序都運行在一個內存空間里，在 32 位系統中，這個內存空間擁有 4GB (2 的 32 次方)的尋址能力。

盡管現在的內存空間都號稱是平坦的，但實際上內存仍然在不同的地址區間有著不同的地位，例如，大多數操作系統都會將 4GB 的內存空間一部分挪給內核使用，應用程序無法直接訪問這一段內存，這一部分內存地址被稱為 內核空間。

Windows 在默認的情況下會將高地址的 2GB 空間分配給內核(也可以配置 1GB)。

Linux 默認情況下將高地址的 1GB 空間分配給內核。

用戶使用的剩下的 2GB 或 3GB 的內存空間稱為用戶空間。

為什么要區分內核空間和用戶空間?

大致有三點因素：

第一點：操作系統的數據都是存放于系統空間的，用戶進程的數據是存放于用戶空間的;

第二點：分開來存放，就讓系統的數據和用戶的數據互不干擾，保證系統的穩定性，并且管理上很方便;

第三點：也是重要的一點，將用戶的數據和系統的數據隔離開，就可以對兩部分的數據的訪問進行控制。這樣就可以確保用戶程序不能隨便操作系統的數據，這樣防止用戶程序誤操作或者是惡意破壞系統。

下面這一張圖，比較形象的解釋了 User space 與 Kernel space 的區別

 

第第一點：操作系統的數據都是存放于系統空間的，用戶進程的數據是存放于用戶空間的;

簡單說，Kernel space 是 Linux 內核的運行空間，User space 是用戶程序的運行空間。為了安全，它們是隔離的，即使用戶的程序崩潰了，內核也不受影響。

Kernel space 可以執行任意命令，調用系統的一切資源;User space 只能執行簡單的運算，不能直接調用系統資源，必須通過系統接口(又稱 system call)，才能向內核發出指令。

2、Linux 進程地址空間布局

在用戶空間里，也有許多地址區間有特權的地位，一般來講，應用程序使用的內存空間里有如下“默認”的區域。

棧區： 棧用于維護函數調用的上下文，離開了棧，函數調用就無法實現，棧通常在用戶空間的最高地址處分配，通常有數兆字節的大小。

堆區： 堆是用來容納應用程序動態分配的內存區域，當程序使用 malloc 或者 new 分配內存的時候，得到的內存會來自堆里。

堆通常存在棧的下方(低地址方向)，在某些時候，堆也可能沒有固定統一的存儲區域。堆一般比棧大很多，可以有幾十至數百兆字節的容量。

可執行文件映像： 存儲著可執行文件在內存里的映像，由裝載器在裝載時將可執行文件的內存讀取或映射到這里。

保留區： 保留區并不是一個單一的內存區域，而是對內存中受到保護而禁止訪問的內存區域的總稱：例如大多數操作系統中，極小的地址通常都是不允許訪問的，如 NULL，C 語言將無效指針賦值為 0 也是這個考慮。

動態鏈接庫映射區： 這個區域用于映射裝載的動態鏈接庫。在 Linux 下，如果可執行文件依賴其它共享庫，那么系統就會為它在從 0x40000000 開始的地址分配相應的空間，并將共享庫載入該空間。

剩下的還有以下幾部份組成：

(1)代碼段

(2)初始化數據段(數據段)

(3)未初始化數據段(BSS 段)

下圖是 Linux 下一個進程里典型的內存布局

 

圖中的箭頭，標明了幾個大小可變的尺寸增長的方向，在這里，可以清晰地看出：

棧是由高地址向低地址增長。

堆是由低地址向高地址增長。

當棧或堆現有的大小不夠用的時候，它將按照圖中的增長方向擴大自身的尺寸，直到預留的空間被用完為止。

在講堆和棧之前，我們先來看一下代碼段，初始化數據段和未初始化數據段。

3、代碼段

代碼段中存放可執行的指令，在內存中，為了保證不會因為堆棧溢出被覆蓋，將其放在了堆棧段下面(從上圖可以看出)。通常來講代碼段是共享的，這樣多次反復執行的指令只需要在內存中駐留一個副本即可，比如 C 編譯器，文本編輯器等。代碼段一般是只讀的，程序執行時不能隨意更改指令，也是為了進行隔離保護。

4、初始化數據段

初始化數據段有時就稱之為數據段。數據段是一個程序虛擬地址空間的一部分，包括一全局變量和靜態變量，這些變量在編程時就已經被初始化。數據段是可以修改的，不然程序運行時變量就無法改變了，這一點和代碼段不同。

數據段可以細分為初始化只讀區和初始化讀寫區。這一點和編程中的一些特殊變量吻合。比如全局變量 int global n = 1就被放在了初始化讀寫區，因為 global 是可以修改的。而 const int m = 2 就會被放在只讀區，很明顯，m 是不能修改的。

5、棧

棧 (stack) 是現代計算機程序里最為重要的概念之一，幾乎每一個程序都使用了棧，沒有棧就沒有函數，沒有局部變量，也就沒有我們如今能夠看見的所有的計算機語言。在解釋為什么棧會如此重要之前，讓我們來先了解一下傳統的棧的定義：

在經典的計算機科學中，棧被定義為一個特殊的容器，用戶可以將數據壓入棧中(入棧,push)，也可以將已經壓入棧中的數據彈出(出棧, pop)，但棧這個容器必須遵守一條規則：先入棧的數據后出棧(First In Last Out, FIFO)，多多少少像疊成一疊的書：先疊上去的書在最下面：因此要最后才能取出。

在計算機系統中，棧則是一個具有以上屬性的動態內存區域，程序可以將數據壓入棧中，也可以將數據從棧頂彈出，壓棧操作使得棧增大,而彈出操作使棧減小。

在經典的操作系統里，棧總是向下增長的。

在 i386 下，棧頂由稱為 esp 的寄存器進行定位。壓棧的操作使棧頂的地址減小，彈出的操作使棧頂地址增大。

 

這里棧底的地址是 0xbffff，而 esp 寄存器標明了棧頂，地址為 0xbifff4。

在棧上壓入數據會導致 esp 減小，彈出數據使得 esp 增大。

棧在程序運行中具有舉足輕重的地位。最重要的，棧保存了一個函數調用所需要的維護信息，這常常被稱為堆棧幀(Stack Frame)或活動記錄(Activate Record)，堆棧幀一般包括如下幾方面內容：

• 函數的返回地址和參數。
• 臨時變量:包括函數的非靜態局部變量以及編譯器自動生成的其他臨時變量。
• 保存的上下文:包括在函數調用前后需要保持不變的寄存器。

6、堆

相對于棧，堆這片內存面臨著一個稍微復雜的行為模式：在任意時刻，程序可能發出請求，要么申請一段內存，要么釋放一段已經申請過的內存，而且申請的大小從幾個字節到數 GB 都是有可能的，我們不能假設程序會一次申請多少堆空間，因此，這時候堆的作用就凸顯出來了，同樣，相比較與棧，堆的管理顯得較為復雜。

光有棧，對于面向過程的程序設計還遠遠不夠，因為棧上的數據在函數返回的時候就會被釋放掉，所以無法將數據傳遞至函數外部。而全局變量沒有辦法動態地產生，只能在編譯的時候定義，有很多情況下缺乏表現力，在這種情況下，堆(Heap)是一種唯一的選擇。

堆是一塊巨大的內存空間，常常占據整個虛擬空間的絕大部分，在這片空間里，程序可以請求一塊連續的內存，并自由地使用，這塊內存在程序主動放棄之前都活一直保持有效，下面是一個申請堆空間最簡單的例子：

int main() 
{ 
    char* p = (char*) malloc(233); 
    free(p); 
    return 0; 
} 

在代碼中，第 3 行用 malloc 申請了 233 個字節的空間之后，程序可以自由地使用這 233個字節，直到程序用 free 函數釋放它。

那么 malloc 到底是怎么實現的呢?

有一種做法是，把進程的內存管理交給操作系統內核去做，既然內核管理著進程的地址空間，那么如果它提供一個系統調用，可以讓程序使用這個系統調用申請內存，不就可以了嗎?

當然這是一種理論上可行的做法，但實際上這樣做的性能比較差，原因在于每次程序申請或者釋放堆空間都需要進行系統調用。

我們知道系統調用的性能開銷是很大的，當程序對堆的操作比較頻繁時，這樣做的結果是會嚴重影響程序的性能的。

比較好的做法就是：程序向操作系統申請一塊適當大小的堆空間，然后由程序自己管理這塊空間，而具體來講，管理著堆空間分配的往往是程序的運行庫。

運行庫相當于是向操作系統 “批發” 了一塊較大的堆空間，然后 “零售” 給程序用。

當全部“售完”或程序有大量的內存需求時，再根據實際需求向操作系統“進貨”。

當然運行庫在向程序零售堆空間時，必須管理它批發來的堆空間，不能把同一塊地址出售兩次，導致地址的沖突。

7、Linux 進程堆管理

由第一節可知，進程的地址空間中，除了可執行文件，共享庫和棧之外，剩余的未分配的空間都可以用來作為堆空間。

Linux 系統下，提供兩種堆空間分配方式：

brk() 統調用和 mmap() 系統調用。

這兩種方式分配的都是虛擬內存，沒有分配物理內存。在第一次訪問已分配的虛擬地址空間的時候，發生缺頁中斷，操作系統負責分配物理內存，然后建立虛擬內存和物理內存之間的映射關系。

在標準 C 庫中，提供了malloc/free函數分配釋放內存，這兩個函數底層是由 brk，mmap，munmap 這些系統調用實現的。

brk() 系統調用

C 語言形式聲明：int brk() {void* end_data_segment;}

brk() 的作用實際上就是設置進程數據段的結束地址，即它可以擴大或者縮小數據段(Linux 下數據段和 BBS 合并在一起統稱數據段)。

如果我們將數據段的結束地址向高地址移動，那么擴大的那部分空間就可以被我們使用，把這塊空間拿過來使用作為堆空間是最常見的做法。

mmap() 系統調用

和 Windows 系統下的 VirtualAlloc 很相似，它的作用就是向操作系統申請一段虛擬地址空間，(堆和棧中間，稱為文件映射區域的地方)這塊虛擬地址空間可以映射到某個文件。

glibc 的 malloc 函數是這樣處理用戶的空間請求的：對于小于 128KB 的請求來說，它會在現有的堆空間里面，按照堆分配算法為它分配一塊空間并返回;對于大于128KB 的請求來說，它會使用 mmap() 函數為它分配一塊匿名空間，然后在這個匿名空間中為用戶分配空間。

聲明如下：

void* mmap{ 
    void* start; 
    size_t length; 
    int prot; 
    int flags; 
    int fd; 
    off_t offset; 
} 

mmap 前兩個參數分別用于指定需要申請的空間的起始地址和長度，如果起始地址設置 0，那么 Linux 系統會自動挑選合適的起始地址。

prot/flags 參數：用于設置申請的空間的權限(可讀，可寫，可執行)以及映射類型(文件映射，匿名空間等)。

最后兩個參數用于文件映射時指定的文件描述符和文件偏移的。

了解了 Linux 系統對于堆的管理之后，可以再來詳細這么一個問題

那就是 malloc 到底一次能夠申請的最大空間是多少?

為了回答這個問題，就不得不再回頭仔細研究一下之前的圖一。我們可以看到在有共享庫的情況下，留給堆可以用的空間還有兩處。

第一處就是從 BSS 段結束到 0x40 000 000 即大約 1GB 不到的空間;

第二處是從共享庫到棧的這塊空間，大約是 2GB 不到。這兩塊空間大小都取決于棧、共享庫的大小和數量。

于是可以估算到 malloc 最大的申請空間大約是 2GB 不到。(Linux 內核 2.4 版本)。

當然還有其它諸多因素會影響 malloc 的最大空間大小，比如系統的資源限制(ulimit)，物理內存和交換空間的總和等。

mmap 申請匿名空間時，系統會為它在內存或交換空間中預留地址，但是申請的空間大小不能超過空閑內存+空閑交換空間的總和。

堆分配算法

1、空閑鏈表法(即調用 malloc 分配)

就是把堆中各個空閑的塊按照鏈表的方式連接起來，當用戶請求一塊空間的時候，可以遍歷整個列表，直到找到合適大小的塊并且將它拆分;當用戶釋放空間的時候將它合并到空閑鏈表中。

空閑鏈表是這樣一種結構，在堆里的每一個空閑空間的開頭(或結尾)有一個頭 (header)，頭結構里記錄了上一個 (prev) 和下一個 (next) 空閑塊的地址，也就是說，所有的空閑塊形成了一個鏈表。如圖所示。

 

具體實現方案：

1、malloc 函數的實質是它有一個將可用的內存塊連接為一個長長的列表的所謂空閑鏈表。

2、調用 malloc函數時，它沿著連接表尋找一個大到足以滿足用戶請求所需要的內存塊。然后，將該內存塊一分為二(一塊的大小與用戶申請的大小相等，另一塊的大小就是剩下來的字節)。接下來，將分配給用戶的那塊內存存儲區域傳給用戶，并將剩下的那塊(如果有的話)返回到連接表上。

3、調用 free 函數時，它將用戶釋放的內存塊連接到空閑鏈表上。

4、到最后，空閑鏈會被切成很多的小內存片段，如果這時用戶申請一個大的內存片段， 那么空閑鏈表上可能沒有可以滿足用戶要求的片段了。于是，malloc() 函數請求延時，并開始在空閑鏈表上檢查各內存片段，對它們進行內存整理，將相鄰的小空閑塊合并成較大的內存塊。

2、位圖法

針對空閑鏈表的弊端，另一種分配方式顯得更加穩健。這種方式稱為位圍(Bitmap)，其核心思想是將整個堆劃分為大量的塊(block)，每個塊的大小相同。

當用戶請求內存的時候，總是分配整數個塊的空間給用戶，第一個塊我們稱為已分配區域的頭(Head)，其余的稱為己分配區域的主體(Body)，而我們可以使用一個整數數組來記錄塊的使用情況，由于每個塊只有頭/主體/空閑三種狀態，因此僅僅需要兩位即可表示一個塊，因此稱為位圖。

3、對象池

還有一種方法是對象池，也是把堆空間分成了大小相等的一些塊，它是認為某些場合每次分配的空間都相等，所以每次就直接返回一個塊的大小，它的管理方法可以是鏈表也可以是位圖。因為不用每次查找合適的大小的內存返回，所以效率很高。

實際上很多現實應用中，堆的分配算法往往是采取多種算法復合而成的。

比如對于glibc來說，它對于小于64字節的空間申請是采用類似于對象池的方法。

而對于大于512字節的空間申請采用的是最佳適配算法;

對于大于64字節而小于512字節的，它會根據情況采取上述方法中的最佳折中策略;對于大于128KB的申請，它會使用mmap機制直接向操作系統申請空間。

參考資料：《程序員的自我修養》。