Linux內(nèi)存空間簡(jiǎn)介

32位Linux平臺(tái)下進(jìn)程虛擬地址空間分布如下圖:

進(jìn)程虛擬地址空間分布

圖中，0xC0000000開(kāi)始的最高1G空間是內(nèi)核地址空間，剩下3G空間是用戶態(tài)空間。用戶態(tài)空間從上到下依次為stack棧(向下增長(zhǎng))、mmap(匿名文件映射區(qū))、Heap堆(向上增長(zhǎng))、bss數(shù)據(jù)段、數(shù)據(jù)段、只讀代碼段。

其中，Heap區(qū)是程序的動(dòng)態(tài)內(nèi)存區(qū)，同時(shí)也是C++內(nèi)存泄漏的溫床。malloc、free均發(fā)生在這個(gè)區(qū)域。本文將簡(jiǎn)單介紹下glibc在動(dòng)態(tài)內(nèi)存管理方面的機(jī)制，拋磚引玉，希望能和大家多多交流。

Linux提供了如下幾個(gè)系統(tǒng)調(diào)用，用于內(nèi)存分配：

brk()/sbrk() // 通過(guò)移動(dòng)Heap堆頂指針brk，達(dá)到增加內(nèi)存目的 
mmap()/munmap() // 通過(guò)文件影射的方式，把文件映射到mmap區(qū)

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

那么，既然brk、mmap提供了內(nèi)存分配的功能，直接使用brk、mmap進(jìn)行內(nèi)存管理不是更簡(jiǎn)單嗎，為什么需要glibc呢？我們知道，系統(tǒng)調(diào)用本身會(huì)產(chǎn)生軟中斷，導(dǎo)致程序從用戶態(tài)陷入內(nèi)核態(tài)，比較消耗資源。試想，如果頻繁分配回收小塊內(nèi)存區(qū)，那么將有很大的性能耗費(fèi)在系統(tǒng)調(diào)用中。因此，為了減少系統(tǒng)調(diào)用帶來(lái)的性能損耗，glibc采用了內(nèi)存池的設(shè)計(jì)，增加了一個(gè)代理層，每次內(nèi)存分配，都優(yōu)先從內(nèi)存池中尋找，如果內(nèi)存池中無(wú)法提供，再向操作系統(tǒng)申請(qǐng)。

一切計(jì)算機(jī)的問(wèn)題都可以通過(guò)加層的方式解決。

glibc的內(nèi)存分配回收策略

glibc中malloc內(nèi)存分配邏輯如下是:

malloc

• 分配內(nèi)存 < DEFAULT_MMAP_THRESHOLD，走_(dá)_brk，從內(nèi)存池獲取，失敗的話走brk系統(tǒng)調(diào)用
• 分配內(nèi)存 > DEFAULT_MMAP_THRESHOLD，走_(dá)_mmap，直接調(diào)用mmap系統(tǒng)調(diào)用

其中，DEFAULT_MMAP_THRESHOLD默認(rèn)為128k，可通過(guò)mallopt進(jìn)行設(shè)置。重點(diǎn)看下小塊內(nèi)存(size > DEFAULT_MMAP_THRESHOLD)的分配，glibc使用的內(nèi)存池如下圖示：

內(nèi)存池

內(nèi)存池保存在bins這個(gè)長(zhǎng)128的數(shù)組中，每個(gè)元素都是一雙向個(gè)鏈表。其中：

• bins[0]目前沒(méi)有使用
• bins[1]的鏈表稱(chēng)為unsorted_list，用于維護(hù)free釋放的chunk。
• bins[2,63)的區(qū)間稱(chēng)為small_bins，用于維護(hù)＜512字節(jié)的內(nèi)存塊，其中每個(gè)元素對(duì)應(yīng)的鏈表中的chunk大小相同，均為index*8。
• bins[64,127)稱(chēng)為large_bins，用于維護(hù)>512字節(jié)的內(nèi)存塊，每個(gè)元素對(duì)應(yīng)的鏈表中的chunk大小不同，index越大，鏈表中chunk的內(nèi)存大小相差越大，例如: 下標(biāo)為64的chunk大小介于[512, 512+64)，下標(biāo)為95的chunk大小介于[2k+1,2k+512)。同一條鏈表上的chunk，按照從小到大的順序排列。

chunk數(shù)據(jù)結(jié)構(gòu)

chunk結(jié)構(gòu)

glibc在內(nèi)存池中查找合適的chunk時(shí)，采用了最佳適應(yīng)的伙伴算法。舉例如下：

1、如果分配內(nèi)存<512字節(jié)，則通過(guò)內(nèi)存大小定位到smallbins對(duì)應(yīng)的index上(floor(size/8))

• 如果smallbins[index]為空，進(jìn)入步驟3
• 如果smallbins[index]非空，直接返回第一個(gè)chunk

2、如果分配內(nèi)存>512字節(jié)，則定位到largebins對(duì)應(yīng)的index上

• 如果largebins[index]為空，進(jìn)入步驟3
• 如果largebins[index]非空，掃描鏈表，找到第一個(gè)大小最合適的chunk，如size=12.5K，則使用chunk B，剩下的0.5k放入unsorted_list中

3、遍歷unsorted_list，查找合適size的chunk，如果找到則返回；否則，將這些chunk都?xì)w類(lèi)放到smallbins和largebins里面

4、index++從更大的鏈表中查找，直到找到合適大小的chunk為止，找到后將chunk拆分，并將剩余的加入到unsorted_list中

5、如果還沒(méi)有找到，那么使用top chunk

6、或者，內(nèi)存<128k，使用brk；內(nèi)存>128k，使用mmap獲取新內(nèi)存

top chunk 如下圖示: top chunk是堆頂?shù)腸hunk，堆頂指針brk位于top chunk的頂部。移動(dòng)brk指針，即可擴(kuò)充top chunk的大小。當(dāng)top chunk大小超過(guò)128k(可配置)時(shí)，會(huì)觸發(fā)malloc_trim操作，調(diào)用sbrk(-size)將內(nèi)存歸還操作系統(tǒng)。

chunk分布圖

free釋放內(nèi)存時(shí)，有兩種情況：

1. chunk和top chunk相鄰，則和top chunk合并
2. chunk和top chunk不相鄰，則直接插入到unsorted_list中

內(nèi)存碎片

以上圖chunk分布圖為例，按照glibc的內(nèi)存分配策略，我們考慮下如下場(chǎng)景(假設(shè)brk其實(shí)地址是512k)：

1. malloc 40k內(nèi)存，即chunkA，brk = 512k + 40k = 552k
2. malloc 50k內(nèi)存，即chunkB，brk = 552k + 50k = 602k
3. malloc 60k內(nèi)存，即chunkC，brk = 602k + 60k = 662k
4. free chunkA。

此時(shí)，由于brk = 662k，而釋放的內(nèi)存是位于[512k, 552k]之間，無(wú)法通過(guò)移動(dòng)brk指針，將區(qū)域內(nèi)內(nèi)存交還操作系統(tǒng)，因此，在[512k, 552k]的區(qū)域內(nèi)便形成了一個(gè)內(nèi)存空洞 ---- 內(nèi)存碎片。按照glibc的策略，free后的chunkA區(qū)域由于不和top chunk相鄰，因此，無(wú)法和top chunk 合并，應(yīng)該掛在unsorted_list鏈表上。

glibc實(shí)現(xiàn)的一些重要結(jié)構(gòu)

glibc中用于維護(hù)空閑內(nèi)存的結(jié)構(gòu)體是malloc_state，其主要定義如下:

struct malloc_state {
    mutex_t mutex; // 并發(fā)編程下鎖的競(jìng)爭(zhēng)
    mchunkptr        top; // top chunk
    unsigned int     binmap[BINMAPSIZE]; // bitmap，加快bins中chunk判定
    mchunkptr        bins[NBINS * 2 - 2]; // bins，上文所述
    mfastbinptr      fastbinsY[NFASTBINS]; // fastbins，類(lèi)似bins，維護(hù)的chunk更小(80字節(jié)的chunk鏈表)
...
}
static struct malloc_state main_arena; // 主arena

多線程下的競(jìng)爭(zhēng)搶鎖

并發(fā)條件下，main_arena引發(fā)的競(jìng)爭(zhēng)將會(huì)成為限制程序性能的瓶頸所在，因此glibc采用了多arena機(jī)制，線程A分配內(nèi)存時(shí)獲取main_arena鎖成功，將在main_arena所管理的內(nèi)存中分配；此時(shí)線程B獲取main_arena失敗，glibc會(huì)新建一個(gè)arena1，此次內(nèi)存分配從arena1中進(jìn)行。這種策略，一定程度上解決了多線程下競(jìng)爭(zhēng)的問(wèn)題；但是隨著arena的增多，內(nèi)存碎片出現(xiàn)的可能性也變大了。例如，main_arena中有10k、20k的空閑內(nèi)存，線程B要獲取20k的空閑內(nèi)存，但是獲取main_arena鎖失敗，導(dǎo)致留下20k的碎片，降低了內(nèi)存使用率。

普通arena的內(nèi)部結(jié)構(gòu):

普通arena結(jié)構(gòu)

1. 一個(gè)arena由多個(gè)Heap構(gòu)成
2. 每個(gè)Heap通過(guò)mmap獲得，最大為1M，多個(gè)Heap間可能不相鄰
3. Heap之間有prev指針指向前一個(gè)Heap
4. 最上面的Heap，也有top chunk

每個(gè)Heap里面也是由chunk組成，使用和main_arena完全相同的管理方式管理空閑chunk。多個(gè)arena之間是通過(guò)鏈表連接的。如下圖:

arena鏈表

main arena和普通arena的區(qū)別 main_arena是為一個(gè)使用brk指針的arena，由于brk是堆頂指針，一個(gè)進(jìn)程中只可能有一個(gè)，因此普通arena無(wú)法使用brk進(jìn)行內(nèi)存分配。普通arena建立在mmap的機(jī)制上，內(nèi)存管理方式和main_arena類(lèi)似，只有一點(diǎn)區(qū)別，普通arena只有在整個(gè)arena都空閑時(shí)，才會(huì)調(diào)用munmap把內(nèi)存還給操作系統(tǒng)。

一些特殊情況的分析

根據(jù)上文所述，glibc在調(diào)用malloc_trim時(shí)，需要滿足如下2個(gè)條件：

1. size(top chunk) > 128K
2. brk = top chunk- >base + size(top chunk)

假設(shè)，brk指針上面的空間已經(jīng)被占用，無(wú)法通過(guò)移動(dòng)brk指針獲得新的地址空間，此時(shí)main_arena就無(wú)法擴(kuò)容了嗎？glibc的設(shè)計(jì)考慮了這樣的特殊情況，此時(shí)，glibc會(huì)換用mmap操作來(lái)獲取新空間(每次最少M(fèi)MAP_AS_MORECORE_SIZE<1M>)。這樣，main_arena和普通arena一樣，由非連續(xù)的Heap塊構(gòu)成，不過(guò)這種情況下，glibc并未將這種mmap空間表示為Heap，因此，main_arena多個(gè)塊之間是沒(méi)有聯(lián)系的，這就導(dǎo)致了main_arena從此無(wú)法歸還給操作系統(tǒng)，永遠(yuǎn)保留在空閑內(nèi)存中了。如下圖示：

main_arena無(wú)法回收

顯而易見(jiàn)，此時(shí)根本不可能滿足調(diào)用malloc_trim的條件2，即:brk !== top chunk->base + size(top chunk)，因?yàn)榇藭r(shí)brk處于堆頂，而top chunk->base > brk.

#include < stdlib.h >
#include < stdio.h >
#include < string.h >
#include < unistd.h >
#include < sys/mman.h >
#include < malloc.h >

#define ARRAY_SIZE 127
char cmd[1024];

void print_info()
{
    struct mallinfo mi = mallinfo();           
    system(cmd);
    printf("theap_malloc_total=%lu heap_free_total=%lu heap_in_use=%lun
            tmmap_total=%lu mmap_count=%lun", mi.arena, mi.fordblks, mi.uordblks, mi.hblkhd, mi.hblks);
}

int main(int argc, char** argv)
{
    char** ptr_arr[ARRAY_SIZE];
    int i;
    char*  mmap_var;
    pid_t  pid;
    pid = getpid();
    sprintf(cmd, "ps aux | grep %lu | grep -v grep", pid);
    /* mmap占據(jù)堆頂后1M的地址空間 */
    mmap_var = mmap((void*)sbrk(0) + 1024*1024, 127*1024, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0); 
    printf("before mallocn");
    print_info();

    /* 分配內(nèi)存，總大小超過(guò)1M，導(dǎo)致main_arena被拆分 */
    for( i = 0; i < ARRAY_SIZE; i++) {
        ptr_arr[i] = malloc(i * 1024);
    }   
    printf("nafter mallocn");
    print_info();
    /* 釋放所有內(nèi)存，觀察內(nèi)存使用是否改變 */
    for( i = 0; i < ARRAY_SIZE; i++) {
        free(ptr_arr[i]);
    }
    printf("nafter freen");
    print_info();
    munmap(mmap_var, 127*1024);
    return 1;
}

異常運(yùn)行

作為對(duì)比，去除掉brk上面的mmap區(qū)再次運(yùn)行后結(jié)果如下：

正常運(yùn)行

可以看出，異常情況下(brk無(wú)法擴(kuò)展)，free的內(nèi)存沒(méi)有歸還操作系統(tǒng)，而是留在了main_arena的unsorted_list了；而正常情況下，由于滿足執(zhí)行malloc_trim的條件，因此，free后，調(diào)用了sbrk(-size)把內(nèi)存歸還了操作系統(tǒng)，main_arena內(nèi)存響應(yīng)減少。