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

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

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

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

1.ptmalloc工作原理

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

1.1 ptmalloc軟件架構(gòu)

圖片

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

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

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

我們將圍繞兩個(gè)比較重要的概念來(lái)進(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有幾個(gè)重要成員：fastbinsY，top，bins，binmaps，next。

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

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

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

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

• top chunk：超級(jí)chunk，ptmalloc內(nèi)存池。
• binmap：可用bins位圖，用于快速查找可用bin。
• next：?jiǎn)蜗蜴湵碇羔?，用于連接不同的malloc_state。

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

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

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

圖片

2）malloc_chunk

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

struct malloc_chunk {
  INTERNAL_SIZE_T mchunk_prev_size; //前一個(gè)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最難理解的一個(gè)概念，只有理解了chunk才能真正理解ptmalloc。

圖片

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

 malloc_chunk對(duì)象mchunk_prev_size和mchunk_size成員為chunk頭部，chunk頭部將會(huì)伴隨chunk整個(gè)生命周期，用于記錄和識(shí)別chunk。

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

3）fastbins數(shù)組

圖片

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

4）bins數(shù)組

圖片

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

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

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

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

5）top chunk

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

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

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

圖片

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

如果top chunk沒(méi)有足夠的內(nèi)存，說(shuō)明內(nèi)存池內(nèi)存不足，需要通過(guò)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)存比較大，可能通過(guò)munmap或者brk回收至內(nèi)核。

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

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

2.1 ptmalloc常見(jiàn)問(wèn)題

    通過(guò)學(xué)習(xí)ptmalloc實(shí)現(xiàn)原理，我們會(huì)發(fā)現(xiàn)ptmalloc存在兩個(gè)問(wèn)題：鎖競(jìng)爭(zhēng)問(wèn)題和內(nèi)存碎片問(wèn)題。

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

圖片

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

2.2 ptmalloc高并發(fā)測(cè)試

1）測(cè)試代碼

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

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

• 頻繁加鎖測(cè)試方法：

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

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

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

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

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

測(cè)試代碼如下：

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

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

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

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)計(jì)泄露內(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）測(cè)試結(jié)果

• 頻繁加鎖測(cè)試

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

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

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

圖片

圖片

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

圖片

圖片

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

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

圖片

3.總結(jié)

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