大家好，這里是物聯(lián)網(wǎng)心球。

談到高性能編程，我們繞不過一個問題高效內(nèi)存分配，通常我們會使用malloc和free函數(shù)來申請和釋放內(nèi)存。

那么我們習(xí)以為常的malloc和free函數(shù)，真的能滿足高性能編程的要求嗎？

帶著這個問題我們來深入理解malloc和free函數(shù)實現(xiàn)原理。

1.ptmalloc工作原理

malloc和free函數(shù)屬于glibc庫的ptmalloc模塊，我們得通過學(xué)習(xí)glibc源碼了解ptmalloc工作原理。源碼位置：glibc/malloc/malloc.c。

1.1 ptmalloc軟件架構(gòu)

圖片

ptmalloc內(nèi)存池是一個比較復(fù)雜的軟件模塊，會涉及到malloc_state，malloc_chunk，mmap，brk等概念。

ptmalloc通過brk（堆內(nèi)存）或者mmap（內(nèi)存映射）系統(tǒng)調(diào)用從內(nèi)核申請一大塊連續(xù)的內(nèi)存，申請的內(nèi)存由top chunk管理，用戶程序調(diào)用malloc函數(shù)從內(nèi)存池申請內(nèi)存（chunk），如果內(nèi)存池有空閑的chunk，則從空閑的chunk返回給用戶程序，如果沒有空閑的chunk，則從top chunk裁剪出可用的chunk返回給用戶程序。

用戶程序調(diào)用free函數(shù)將會釋放chunk至空閑鏈表或top chunk。

我們將圍繞兩個比較重要的概念來進(jìn)行講解：malloc_state和malloc_trunk。

1) malloc_state

    ptmalloc由struct malloc_state統(tǒng)一管理，定義如下：

struct malloc_state
{
  __libc_lock_define (, mutex);    //互斥鎖
  int flags;                                 //標(biāo)志 
  mfastbinptr fastbinsY[NFASTBINS];  //fastbins
  mchunkptr top;                               //top chunk 
  mchunkptr bins[NBINS * 2 - 2];        //unsortedbins,smallbins,largebins
  unsigned int binmap[BINMAPSIZE]; //bin位圖
  struct malloc_state *next;                //鏈表指針
  ......
};

malloc_state有幾個重要成員：fastbinsY，top，bins，binmaps，next。

• fastbinsY數(shù)組：fastbins，用于存儲16-160字節(jié)chunk的空閑鏈表。
• bins數(shù)組：bins分為三個部分：unsortedbins，smallbins，largebins：

unsortedbins：chunk緩存區(qū)，用于存儲從fastbins合并的空閑chunk。

smallbins：空閑鏈表，用于存儲32-1024字節(jié)的chunk。

largebins：空閑鏈表，用于存儲大于1024字節(jié)的chunk。

• top chunk：超級chunk，ptmalloc內(nèi)存池。
• binmap：可用bins位圖，用于快速查找可用bin。
• next：單向鏈表指針，用于連接不同的malloc_state。

進(jìn)程通常會有多個malloc_state，進(jìn)程啟動時，由主線程創(chuàng)建第一個malloc_state稱為主分配區(qū)（main_state），主分配區(qū)的內(nèi)存通過brk（堆）或者malloc（內(nèi)存映射）從內(nèi)核申請而來，這也解釋了為什么malloc可以從堆區(qū)分配內(nèi)存。

如果程序所有的線程都使用主分配區(qū)分配內(nèi)存，那么多線程會存在競爭關(guān)系，為了解決這個問題，進(jìn)程會根據(jù)實際情況動態(tài)創(chuàng)建非主分配區(qū)（thread_state），thread_state分配區(qū)內(nèi)存池內(nèi)存只能通過mmap從內(nèi)核申請，當(dāng)主分配區(qū)被使用或者沒有可用的分配區(qū)時，系統(tǒng)會創(chuàng)建一個新的分配區(qū)，這樣可以減少多線程競爭，提高內(nèi)存分配效率。

當(dāng)然malloc_state數(shù)量并不是沒有限制，通常malloc_state數(shù)量最多為CPU核心數(shù)的數(shù)倍，超過該閾值后將不能再創(chuàng)建新的分配區(qū)。如果一個程序線程數(shù)量太多，會加劇對分配區(qū)的競爭。

圖片

2）malloc_chunk

    ptmalloc以malloc_chunk為單位申請和釋放內(nèi)存，struct malloc_chunk定義如下：

struct malloc_chunk {
  INTERNAL_SIZE_T mchunk_prev_size; //前一個chunk大小
  INTERNAL_SIZE_T mchunk_size;   //當(dāng)前chunk大小，后三位為A,M,P
  struct malloc_chunk* fd;      //鏈表后驅(qū)指針
  struct malloc_chunk* bk;      //鏈表前驅(qū)指針
  struct malloc_chunk* fd_nextsize; //largebins后驅(qū)指針
  struct malloc_chunk* bk_nextsize; //largebins前驅(qū)指針
};

    chunk是ptmalloc最難理解的一個概念，只有理解了chunk才能真正理解ptmalloc。

圖片

chunk是從內(nèi)存池裁剪下來的內(nèi)存塊，這個內(nèi)存塊由malloc_chunk管理。

 malloc_chunk對象mchunk_prev_size和mchunk_size成員為chunk頭部，chunk頭部將會伴隨chunk整個生命周期，用于記錄和識別chunk。

內(nèi)存塊除了chunk頭部外就是內(nèi)存區(qū)域，當(dāng)chunk分配給用戶程序后，內(nèi)存區(qū)域用于存儲用戶數(shù)據(jù)，如果chunk處于空閑狀態(tài)，將會借用內(nèi)存區(qū)域前16個字節(jié)作為鏈表指針，將chunk插入空閑鏈表。

3）fastbins數(shù)組

圖片

fastbins數(shù)組長度為10，每個數(shù)組元素都是一個chunk鏈表頭，10個鏈表分別存儲16-160字節(jié)的chunk，步長為16字節(jié)，malloc函數(shù)申請小于160字節(jié)的內(nèi)存時，從fastbins空閑鏈表查找匹配的chunk進(jìn)行分配。

4）bins數(shù)組

圖片

bins數(shù)組長度為128，可以分為三部分：unsortedbins，smallbins，largebins。

unsortedbins：bins數(shù)組0號元素，unsortedbins是一個特殊的鏈表，該鏈表是一個chunk緩存區(qū)，用于存儲從fastbins合并的空閑chunk，目的是為了回收小塊內(nèi)存，解決內(nèi)存碎片問題。

smallbins：bins數(shù)組1-63號元素，和fastbins功能一樣，smallbins用于存儲32-1008字節(jié)的空閑chunk。

largebins：bins數(shù)組64-127號元素，用于存儲超過1024字節(jié)大小的空閑chunk。

5）top chunk

top chunk可以理解為超級chunk，當(dāng)bins空閑鏈表中沒有匹配的chunk分配給用戶程序時，top chunk將會被裁剪，裁剪成用戶chunk和剩余chunk，用戶chunk分配給用戶程序，剩余chunk繼續(xù)由top chunk管理。

如果top chunk內(nèi)存不足，調(diào)用brk或者mmap從內(nèi)核申請內(nèi)存對top chunk擴(kuò)容，并將擴(kuò)容后的內(nèi)存塊裁剪分配給用戶程序。

1.2 malloc函數(shù)流程分析

圖片

用戶程序調(diào)用malloc函數(shù)申請內(nèi)存時，首先會去查詢空閑鏈表，如果空閑鏈表沒有足夠的chunk，則去查詢top chunk進(jìn)行內(nèi)存分配。

如果top chunk沒有足夠的內(nèi)存，說明內(nèi)存池內(nèi)存不足，需要通過brk或者mmap擴(kuò)容。

注意：內(nèi)存池內(nèi)存不夠，并不一定表示內(nèi)存都被用完，也有可能是存在內(nèi)存碎片。

1.3 free函數(shù)流程分析

圖片

用戶程序調(diào)用free函數(shù)釋放內(nèi)存，優(yōu)先將內(nèi)存釋放至空閑鏈表，如果釋放至空閑鏈表失敗，則釋放至top chunk，如果釋放的內(nèi)存比較大，可能通過munmap或者brk回收至內(nèi)核。

2.ptmalloc高并發(fā)測試

前一小節(jié)，我們花了比較多的精力去學(xué)習(xí)ptmalloc實現(xiàn)原理，對于很多項目來說，我們不需要花過多時間去研究ptmalloc實現(xiàn)原理，直接使用malloc和free函數(shù)即可，然而對于高并發(fā)項目，我們得深入理解ptmalloc實現(xiàn)原理，從而清楚地知道ptmalloc存在的問題，為后續(xù)優(yōu)化打好基礎(chǔ)。

2.1 ptmalloc常見問題

    通過學(xué)習(xí)ptmalloc實現(xiàn)原理，我們會發(fā)現(xiàn)ptmalloc存在兩個問題：鎖競爭問題和內(nèi)存碎片問題。

• 鎖競爭問題
  struct malloc_state結(jié)構(gòu)定義了一個mutex成員，多線程想要通過分配區(qū)進(jìn)行內(nèi)存分配時需要加鎖，頻繁分配內(nèi)存會導(dǎo)致頻繁加鎖。
• 內(nèi)存碎片問題

圖片

ptmalloc通過mmap或brk從內(nèi)核申請一大塊連續(xù)的內(nèi)存，調(diào)用malloc函數(shù)會將這塊大的內(nèi)存裁剪成一塊塊小的內(nèi)存，如果其中某些小的內(nèi)存塊一直不釋放至內(nèi)存池，將導(dǎo)致小的內(nèi)存塊無法合并成大的內(nèi)存塊，造成內(nèi)存碎片，嚴(yán)重的情況會導(dǎo)致內(nèi)存泄露，程序退出。

2.2 ptmalloc高并發(fā)測試

1）測試代碼

采用多個線程循環(huán)申請和釋放內(nèi)存，每次隨機(jī)申請SIZE_THREHOLD范圍大小內(nèi)存，如果申請的內(nèi)存小于LEAK_THREHOLD大小，則申請的內(nèi)存不釋放，人為制造內(nèi)存泄露，并實時統(tǒng)計泄露內(nèi)存總量。

 測試項：頻繁加鎖測試，內(nèi)存碎片測試。

• 頻繁加鎖測試方法：

通過：strace -tt -f -e trace=futex ./a.out命令執(zhí)行測試程序，觀察是否調(diào)用futex系統(tǒng)調(diào)用加鎖。

• 內(nèi)存碎片測試

通過：strace -tt -f -e trace=mprotect,brk ./a.out命令執(zhí)行測試程序，觀察是否調(diào)用mprotect或者brk進(jìn)行擴(kuò)容。

統(tǒng)計程序已使用內(nèi)存總量，內(nèi)存泄露總量，計算內(nèi)存碎片總量：

內(nèi)存碎片總量=已使用內(nèi)存總量-內(nèi)存泄露總量。

測試代碼如下：

#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <pthread.h>
#include <stdatomic.h>

#define THREAD_NUM (8) //測試線程數(shù)量
#define SIZE_THREHOLD (1024) //申請內(nèi)存閾值，每次申請的內(nèi)存大小小于該閾值
#define LEAK_THREHOLD (64) //泄露內(nèi)存閾值, 0：關(guān)閉內(nèi)存泄露，大于0：每次泄露內(nèi)存的不超過該閾值

atomic_int leak_size; //內(nèi)存泄露統(tǒng)計值

int get_size() {
    srand(time(0));
    return rand() % SIZE_THREHOLD;
}

void *do_malloc(void *arg) {
    while(1) {
        int size = get_size();
        //printf("size:%d\n", size);
        char *p = malloc(size);
        if (size >= LEAK_THREHOLD) {
            free(p);
        } else {
            atomic_fetch_add(&leak_size, size); //統(tǒng)計泄露內(nèi)存大小
            printf("leak size:%d KB\n", leak_size / 1024);
        }
    }
    return NULL;
}

int main(int argc, char *argv[]) {
    atomic_init(&leak_size, 0);

    pthread_t th[THREAD_NUM];
    for (int i = 0; i < THREAD_NUM; i++) {
        pthread_create(&th[i], NULL, do_malloc, NULL);
    }

    do_malloc(NULL);

    for (int i = 0; i < THREAD_NUM; i++) {
        pthread_join(th[i], NULL);
    }

    return 0;
}

2）測試結(jié)果

• 頻繁加鎖測試

通過strace -tt -f -e trace=futex ./a.out命令觀察到測試程序頻繁的調(diào)用futex系統(tǒng)調(diào)用，為了保證線程安全，malloc和free函數(shù)需要頻繁加鎖，頻繁加鎖會影響內(nèi)存分配的效率。

• 內(nèi)存碎片測試

1.程序剛啟動時，內(nèi)存泄露總量為1.8MB，此時系統(tǒng)可用內(nèi)存總量為2724MB。

圖片

圖片

2. 程序泄露內(nèi)存總量至162MB時，此時系統(tǒng)可用內(nèi)存總量為2474MB。

圖片

圖片

用戶程序使用內(nèi)存總量為：2724 - 2474 = 250MB。泄露內(nèi)存總量為162MB，內(nèi)存碎片總量為88MB。

通過strace -tt -f -e trace=mprotect,brk ./a.out命令觀察到，ptmalloc頻繁的通過mprotect或者brk進(jìn)行擴(kuò)容。

圖片

3.總結(jié)

• malloc和free函數(shù)不適用于多線程申請和釋放內(nèi)存使用場景，存在頻繁加鎖的問題。
• malloc和free函數(shù)不適用于長期占用內(nèi)存的使用場景，長期占用內(nèi)存會導(dǎo)致內(nèi)存碎片問題。
• 對并發(fā)要求不高的場景可以使用malloc和free函數(shù)，高并發(fā)場景需要使用更高效的內(nèi)存池。