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

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

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

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

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

這兩種方式分配的都是虛擬內(nèi)存掌测，沒有分配物理內(nèi)存内贮。在第一次訪問已分配的虛擬地址空間的時(shí)候，發(fā)生缺頁中斷汞斧，操作系統(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)用帶來的性能損耗，glibc采用了內(nèi)存池的設(shè)計(jì)森缠，增加了一個(gè)代理層拔鹰，每次內(nèi)存分配，都優(yōu)先從內(nèi)存池中尋找贵涵，如果內(nèi)存池中無法提供列肢，再向操作系統(tǒng)申請(qǐng)。

一切計(jì)算機(jī)的問題都可以通過加層的方式解決宾茂。

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怀骤，可通過mallopt進(jìn)行設(shè)置费封。
重點(diǎn)看下小塊內(nèi)存(size > DEFAULT_MMAP_THRESHOLD)的分配，glibc使用的內(nèi)存池如下圖示：

內(nèi)存池

• bins[0]目前沒有使用
• bins[1]的鏈表稱為unsorted_list，用于維護(hù)free釋放的chunk痕届。
• bins[2,63)的區(qū)間稱為small_bins韧献，用于維護(hù)＜512字節(jié)的內(nèi)存塊，其中每個(gè)元素對(duì)應(yīng)的鏈表中的chunk大小相同研叫，均為index*8锤窑。
• bins[64,127)稱為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é)车酣，則通過內(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類放到smallbins和largebins里面
4. index++從更大的鏈表中查找盏阶，直到找到合適大小的chunk為止晒奕，找到后將chunk拆分，并將剩余的加入到unsorted_list中
5. 如果還沒有找到，那么使用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大小超過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]之間，無法通過移動(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相鄰，因此光绕，無法和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，類似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)的問題崇呵；但是隨著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通過mmap獲得，最大為1M钦奋，多個(gè)Heap間可能不相鄰
3. Heap之間有prev指針指向前一個(gè)Heap
4. 最上面的Heap座云，也有top chunk

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

arena鏈表

main arena和普通arena的區(qū)別
main_arena是為一個(gè)使用brk指針的arena，由于brk是堆頂指針厌衔，一個(gè)進(jìn)程中只可能有一個(gè)璧帝，因此普通arena無法使用brk進(jìn)行內(nèi)存分配。普通arena建立在mmap的機(jī)制上富寿，內(nèi)存管理方式和main_arena類似睬隶，只有一點(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)被占用，無法通過移動(dòng)brk指針獲得新的地址空間，此時(shí)main_arena就無法擴(kuò)容了嗎飞袋？
glibc的設(shè)計(jì)考慮了這樣的特殊情況戳气，此時(shí)，glibc會(huì)換用mmap操作來獲取新空間(每次最少M(fèi)MAP_AS_MORECORE_SIZE<1M>)巧鸭。這樣瓶您，main_arena和普通arena一樣，由非連續(xù)的Heap塊構(gòu)成纲仍，不過這種情況下览闰，glibc并未將這種mmap空間表示為Heap，因此巷折，main_arena多個(gè)塊之間是沒有聯(lián)系的，這就導(dǎo)致了main_arena從此無法歸還給操作系統(tǒng)崖咨，永遠(yuǎn)保留在空閑內(nèi)存中了锻拘。如下圖示：

main_arena無法回收

#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=%lu\n\
            \tmmap_total=%lu mmap_count=%lu\n", 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 malloc\n");
    print_info();

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

異常運(yùn)行

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

正常運(yùn)行

可以看出馒铃，異常情況下(brk無法擴(kuò)展)，free的內(nè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)減少卧晓。

參考文章

1. Linux 堆內(nèi)存管理深入分析
2. 深入剖析glibc內(nèi)存管理實(shí)現(xiàn)及潛在問題
3. 十問Linux虛擬內(nèi)存管理(glibc)