[[319501]]

本文轉(zhuǎn)載自微信公眾號(hào)「herongwei」，轉(zhuǎn)載本文請(qǐng)聯(lián)系「herongwei」公眾號(hào)。

前言

• 什么是 User space 與 Kernel space?
• 什么是棧區(qū)?
• 什么是堆區(qū)?
• malloc 算法是如何實(shí)現(xiàn)的?
• Linux 系統(tǒng)下，有幾種堆空間分配方式?
• Linux 下一個(gè)進(jìn)程地址空間布局是怎樣的?

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

1、User space 與 Kernel space

現(xiàn)代的應(yīng)用程序都運(yùn)行在一個(gè)內(nèi)存空間里，在 32 位系統(tǒng)中，這個(gè)內(nèi)存空間擁有 4GB (2 的 32 次方)的尋址能力。

盡管現(xiàn)在的內(nèi)存空間都號(hào)稱是平坦的，但實(shí)際上內(nèi)存仍然在不同的地址區(qū)間有著不同的地位，例如，大多數(shù)操作系統(tǒng)都會(huì)將 4GB 的內(nèi)存空間一部分挪給內(nèi)核使用，應(yīng)用程序無法直接訪問這一段內(nèi)存，這一部分內(nèi)存地址被稱為 內(nèi)核空間。

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

Linux 默認(rèn)情況下將高地址的 1GB 空間分配給內(nèi)核。

用戶使用的剩下的 2GB 或 3GB 的內(nèi)存空間稱為用戶空間。

為什么要區(qū)分內(nèi)核空間和用戶空間?

大致有三點(diǎn)因素：

第一點(diǎn)：操作系統(tǒng)的數(shù)據(jù)都是存放于系統(tǒng)空間的，用戶進(jìn)程的數(shù)據(jù)是存放于用戶空間的;

第二點(diǎn)：分開來存放，就讓系統(tǒng)的數(shù)據(jù)和用戶的數(shù)據(jù)互不干擾，保證系統(tǒng)的穩(wěn)定性，并且管理上很方便;

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

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

第第一點(diǎn)：操作系統(tǒng)的數(shù)據(jù)都是存放于系統(tǒng)空間的，用戶進(jìn)程的數(shù)據(jù)是存放于用戶空間的;

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

Kernel space 可以執(zhí)行任意命令，調(diào)用系統(tǒng)的一切資源;User space 只能執(zhí)行簡單的運(yùn)算，不能直接調(diào)用系統(tǒng)資源，必須通過系統(tǒng)接口(又稱 system call)，才能向內(nèi)核發(fā)出指令。

2、Linux 進(jìn)程地址空間布局

在用戶空間里，也有許多地址區(qū)間有特權(quán)的地位，一般來講，應(yīng)用程序使用的內(nèi)存空間里有如下“默認(rèn)”的區(qū)域。

棧區(qū)： 棧用于維護(hù)函數(shù)調(diào)用的上下文，離開了棧，函數(shù)調(diào)用就無法實(shí)現(xiàn)，棧通常在用戶空間的最高地址處分配，通常有數(shù)兆字節(jié)的大小。

堆區(qū)： 堆是用來容納應(yīng)用程序動(dòng)態(tài)分配的內(nèi)存區(qū)域，當(dāng)程序使用 malloc 或者 new 分配內(nèi)存的時(shí)候，得到的內(nèi)存會(huì)來自堆里。

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

可執(zhí)行文件映像： 存儲(chǔ)著可執(zhí)行文件在內(nèi)存里的映像，由裝載器在裝載時(shí)將可執(zhí)行文件的內(nèi)存讀取或映射到這里。

保留區(qū)： 保留區(qū)并不是一個(gè)單一的內(nèi)存區(qū)域，而是對(duì)內(nèi)存中受到保護(hù)而禁止訪問的內(nèi)存區(qū)域的總稱：例如大多數(shù)操作系統(tǒng)中，極小的地址通常都是不允許訪問的，如 NULL，C 語言將無效指針賦值為 0 也是這個(gè)考慮。

動(dòng)態(tài)鏈接庫映射區(qū)： 這個(gè)區(qū)域用于映射裝載的動(dòng)態(tài)鏈接庫。在 Linux 下，如果可執(zhí)行文件依賴其它共享庫，那么系統(tǒng)就會(huì)為它在從 0x40000000 開始的地址分配相應(yīng)的空間，并將共享庫載入該空間。

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

(1)代碼段

(2)初始化數(shù)據(jù)段(數(shù)據(jù)段)

(3)未初始化數(shù)據(jù)段(BSS 段)

下圖是 Linux 下一個(gè)進(jìn)程里典型的內(nèi)存布局

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

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

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

當(dāng)?；蚨熏F(xiàn)有的大小不夠用的時(shí)候，它將按照?qǐng)D中的增長方向擴(kuò)大自身的尺寸，直到預(yù)留的空間被用完為止。

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

3、代碼段

代碼段中存放可執(zhí)行的指令，在內(nèi)存中，為了保證不會(huì)因?yàn)槎褩Ｒ绯霰桓采w，將其放在了堆棧段下面(從上圖可以看出)。通常來講代碼段是共享的，這樣多次反復(fù)執(zhí)行的指令只需要在內(nèi)存中駐留一個(gè)副本即可，比如 C 編譯器，文本編輯器等。代碼段一般是只讀的，程序執(zhí)行時(shí)不能隨意更改指令，也是為了進(jìn)行隔離保護(hù)。

4、初始化數(shù)據(jù)段

初始化數(shù)據(jù)段有時(shí)就稱之為數(shù)據(jù)段。數(shù)據(jù)段是一個(gè)程序虛擬地址空間的一部分，包括一全局變量和靜態(tài)變量，這些變量在編程時(shí)就已經(jīng)被初始化。數(shù)據(jù)段是可以修改的，不然程序運(yùn)行時(shí)變量就無法改變了，這一點(diǎn)和代碼段不同。

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

5、棧

棧 (stack) 是現(xiàn)代計(jì)算機(jī)程序里最為重要的概念之一，幾乎每一個(gè)程序都使用了棧，沒有棧就沒有函數(shù)，沒有局部變量，也就沒有我們?nèi)缃衲軌蚩匆姷乃械挠?jì)算機(jī)語言。在解釋為什么棧會(huì)如此重要之前，讓我們來先了解一下傳統(tǒng)的棧的定義：

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

在計(jì)算機(jī)系統(tǒng)中，棧則是一個(gè)具有以上屬性的動(dòng)態(tài)內(nèi)存區(qū)域，程序可以將數(shù)據(jù)壓入棧中，也可以將數(shù)據(jù)從棧頂彈出，壓棧操作使得棧增大,而彈出操作使棧減小。

在經(jīng)典的操作系統(tǒng)里，棧總是向下增長的。

在 i386 下，棧頂由稱為 esp 的寄存器進(jìn)行定位。壓棧的操作使棧頂?shù)牡刂窚p小，彈出的操作使棧頂?shù)刂吩龃蟆?/p>

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

在棧上壓入數(shù)據(jù)會(huì)導(dǎo)致 esp 減小，彈出數(shù)據(jù)使得 esp 增大。

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

• 函數(shù)的返回地址和參數(shù)。
• 臨時(shí)變量:包括函數(shù)的非靜態(tài)局部變量以及編譯器自動(dòng)生成的其他臨時(shí)變量。
• 保存的上下文:包括在函數(shù)調(diào)用前后需要保持不變的寄存器。

6、堆

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

光有棧，對(duì)于面向過程的程序設(shè)計(jì)還遠(yuǎn)遠(yuǎn)不夠，因?yàn)闂Ｉ系臄?shù)據(jù)在函數(shù)返回的時(shí)候就會(huì)被釋放掉，所以無法將數(shù)據(jù)傳遞至函數(shù)外部。而全局變量沒有辦法動(dòng)態(tài)地產(chǎn)生，只能在編譯的時(shí)候定義，有很多情況下缺乏表現(xiàn)力，在這種情況下，堆(Heap)是一種唯一的選擇。

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

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

在代碼中，第 3 行用 malloc 申請(qǐng)了 233 個(gè)字節(jié)的空間之后，程序可以自由地使用這 233個(gè)字節(jié)，直到程序用 free 函數(shù)釋放它。

那么 malloc 到底是怎么實(shí)現(xiàn)的呢?

有一種做法是，把進(jìn)程的內(nèi)存管理交給操作系統(tǒng)內(nèi)核去做，既然內(nèi)核管理著進(jìn)程的地址空間，那么如果它提供一個(gè)系統(tǒng)調(diào)用，可以讓程序使用這個(gè)系統(tǒng)調(diào)用申請(qǐng)內(nèi)存，不就可以了嗎?

當(dāng)然這是一種理論上可行的做法，但實(shí)際上這樣做的性能比較差，原因在于每次程序申請(qǐng)或者釋放堆空間都需要進(jìn)行系統(tǒng)調(diào)用。

我們知道系統(tǒng)調(diào)用的性能開銷是很大的，當(dāng)程序?qū)Χ训牟僮鞅容^頻繁時(shí)，這樣做的結(jié)果是會(huì)嚴(yán)重影響程序的性能的。

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

運(yùn)行庫相當(dāng)于是向操作系統(tǒng) “批發(fā)” 了一塊較大的堆空間，然后 “零售” 給程序用。

當(dāng)全部“售完”或程序有大量的內(nèi)存需求時(shí)，再根據(jù)實(shí)際需求向操作系統(tǒng)“進(jìn)貨”。

當(dāng)然運(yùn)行庫在向程序零售堆空間時(shí)，必須管理它批發(fā)來的堆空間，不能把同一塊地址出售兩次，導(dǎo)致地址的沖突。

7、Linux 進(jìn)程堆管理

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

Linux 系統(tǒng)下，提供兩種堆空間分配方式：

brk() 統(tǒng)調(diào)用和 mmap() 系統(tǒng)調(diào)用。

這兩種方式分配的都是虛擬內(nèi)存，沒有分配物理內(nèi)存。在第一次訪問已分配的虛擬地址空間的時(shí)候，發(fā)生缺頁中斷，操作系統(tǒng)負(fù)責(zé)分配物理內(nèi)存，然后建立虛擬內(nèi)存和物理內(nèi)存之間的映射關(guān)系。

在標(biāo)準(zhǔn) C 庫中，提供了malloc/free函數(shù)分配釋放內(nèi)存，這兩個(gè)函數(shù)底層是由 brk，mmap，munmap 這些系統(tǒng)調(diào)用實(shí)現(xiàn)的。

brk() 系統(tǒng)調(diào)用

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

brk() 的作用實(shí)際上就是設(shè)置進(jìn)程數(shù)據(jù)段的結(jié)束地址，即它可以擴(kuò)大或者縮小數(shù)據(jù)段(Linux 下數(shù)據(jù)段和 BBS 合并在一起統(tǒng)稱數(shù)據(jù)段)。

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

mmap() 系統(tǒng)調(diào)用

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

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

聲明如下：

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

mmap 前兩個(gè)參數(shù)分別用于指定需要申請(qǐng)的空間的起始地址和長度，如果起始地址設(shè)置 0，那么 Linux 系統(tǒng)會(huì)自動(dòng)挑選合適的起始地址。

prot/flags 參數(shù)：用于設(shè)置申請(qǐng)的空間的權(quán)限(可讀，可寫，可執(zhí)行)以及映射類型(文件映射，匿名空間等)。

最后兩個(gè)參數(shù)用于文件映射時(shí)指定的文件描述符和文件偏移的。

了解了 Linux 系統(tǒng)對(duì)于堆的管理之后，可以再來詳細(xì)這么一個(gè)問題

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

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

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

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

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

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

mmap 申請(qǐng)匿名空間時(shí)，系統(tǒng)會(huì)為它在內(nèi)存或交換空間中預(yù)留地址，但是申請(qǐng)的空間大小不能超過空閑內(nèi)存+空閑交換空間的總和。

堆分配算法

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

就是把堆中各個(gè)空閑的塊按照鏈表的方式連接起來，當(dāng)用戶請(qǐng)求一塊空間的時(shí)候，可以遍歷整個(gè)列表，直到找到合適大小的塊并且將它拆分;當(dāng)用戶釋放空間的時(shí)候?qū)⑺喜⒌娇臻e鏈表中。

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

具體實(shí)現(xiàn)方案：

1、malloc 函數(shù)的實(shí)質(zhì)是它有一個(gè)將可用的內(nèi)存塊連接為一個(gè)長長的列表的所謂空閑鏈表。

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

3、調(diào)用 free 函數(shù)時(shí)，它將用戶釋放的內(nèi)存塊連接到空閑鏈表上。

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

2、位圖法

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

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

3、對(duì)象池

還有一種方法是對(duì)象池，也是把堆空間分成了大小相等的一些塊，它是認(rèn)為某些場合每次分配的空間都相等，所以每次就直接返回一個(gè)塊的大小，它的管理方法可以是鏈表也可以是位圖。因?yàn)椴挥妹看尾檎液线m的大小的內(nèi)存返回，所以效率很高。

實(shí)際上很多現(xiàn)實(shí)應(yīng)用中，堆的分配算法往往是采取多種算法復(fù)合而成的。

比如對(duì)于glibc來說，它對(duì)于小于64字節(jié)的空間申請(qǐng)是采用類似于對(duì)象池的方法。

而對(duì)于大于512字節(jié)的空間申請(qǐng)采用的是最佳適配算法;

對(duì)于大于64字節(jié)而小于512字節(jié)的，它會(huì)根據(jù)情況采取上述方法中的最佳折中策略;對(duì)于大于128KB的申請(qǐng)，它會(huì)使用mmap機(jī)制直接向操作系統(tǒng)申請(qǐng)空間。

參考資料：《程序員的自我修養(yǎng)》。