大家好，這里是物聯網心球。

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

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

帶著這個問題我們來深入理解malloc和free函數實現原理。

1.ptmalloc工作原理

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

1.1 ptmalloc軟件架構

圖片

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

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

用戶程序調用free函數將會釋放chunk至空閑鏈表或top chunk。

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

1) malloc_state

    ptmalloc由struct malloc_state統一管理，定義如下：

struct malloc_state
{
  __libc_lock_define (, mutex);    //互斥鎖
  int flags;                                 //標志 
  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數組：fastbins，用于存儲16-160字節(jié)chunk的空閑鏈表。
• bins數組：bins分為三個部分：unsortedbins，smallbins，largebins：

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

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

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

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

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

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

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

圖片

2）malloc_chunk

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

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

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

圖片

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

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

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

3）fastbins數組

圖片

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

4）bins數組

圖片

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

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

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

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

5）top chunk

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

如果top chunk內存不足，調用brk或者mmap從內核申請內存對top chunk擴容，并將擴容后的內存塊裁剪分配給用戶程序。

1.2 malloc函數流程分析

圖片

用戶程序調用malloc函數申請內存時，首先會去查詢空閑鏈表，如果空閑鏈表沒有足夠的chunk，則去查詢top chunk進行內存分配。

如果top chunk沒有足夠的內存，說明內存池內存不足，需要通過brk或者mmap擴容。

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

1.3 free函數流程分析

圖片

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

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

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

2.1 ptmalloc常見問題

    通過學習ptmalloc實現原理，我們會發(fā)現ptmalloc存在兩個問題：鎖競爭問題和內存碎片問題。

• 鎖競爭問題
  struct malloc_state結構定義了一個mutex成員，多線程想要通過分配區(qū)進行內存分配時需要加鎖，頻繁分配內存會導致頻繁加鎖。
• 內存碎片問題

圖片

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

2.2 ptmalloc高并發(fā)測試

1）測試代碼

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

 測試項：頻繁加鎖測試，內存碎片測試。

• 頻繁加鎖測試方法：

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

• 內存碎片測試

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

統計程序已使用內存總量，內存泄露總量，計算內存碎片總量：

內存碎片總量=已使用內存總量-內存泄露總量。

測試代碼如下：

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

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

atomic_int leak_size; //內存泄露統計值

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); //統計泄露內存大小
            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）測試結果

• 頻繁加鎖測試

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

• 內存碎片測試

1.程序剛啟動時，內存泄露總量為1.8MB，此時系統可用內存總量為2724MB。

圖片

圖片

2. 程序泄露內存總量至162MB時，此時系統可用內存總量為2474MB。

圖片

圖片

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

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

圖片

3.總結

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