Linux 高性能編程_malloc 原理

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

    談到高性能編程，我們繞不過一個問題高效內存分配，通常我們會使用 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（內存映射）系統調用從內核申請一大塊連續的內存，申請的內存由 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 字節 chunk 的空閒鏈表。

• **bins 數組：**bins 分爲三個部分：unsortedbins，smallbins，largebins：

1. unsortedbins：chunk 緩存區，用於存儲從 fastbins 合併的空閒 chunk。

2. smallbins：空閒鏈表，用於存儲 32-1024 字節的 chunk。

3. largebins：空閒鏈表，用於存儲大於 1024 字節的 chunk。

• **top chunk：**超級 chunk，ptmalloc 內存池。

• **binmap：**可用 bins 位圖，用於快速查找可用 bin。

• **next：**單向鏈表指針，用於連接不同的 malloc_state。

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

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

    當然 malloc_state 數量並不是沒有限制，通常 malloc_state 數量最多爲 CPU 核心數的數倍，超過該閾值後將不能再創建新的分配區。如果一個程序線程數量太多，會加劇對分配區的競爭。

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 頭部外就是內存區域，當 chunk 分配給用戶程序後，內存區域用於存儲用戶數據，如果 chunk 處於空閒狀態，將會借用內存區域前 16 個字節作爲鏈表指針，將 chunk 插入空閒鏈表。

3）fastbins 數組

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

4）bins 數組

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

    unsortedbins：bins 數組 0 號元素，unsortedbins 是一個特殊的鏈表，該鏈表是一個 chunk 緩存區，用於存儲從 fastbins 合併的空閒 chunk，目的是爲了回收小塊內存，解決內存碎片問題。

    smallbins：bins 數組 1-63 號元素，和 fastbins 功能一樣，smallbins 用於存儲 32-1008 字節的空閒 chunk。

    largebins：bins 數組 64-127 號元素，用於存儲超過 1024 字節大小的空閒 chunk。

5）top chunk

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

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

1.2 malloc 函數流程分析

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

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

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

1.3 free 函數流程分析

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

2.ptmalloc 高併發測試

    前一小節，我們花了比較多的精力去學習 ptmalloc 實現原理，對於很多項目來說，我們不需要花過多時間去研究 ptmalloc 實現原理，直接使用 malloc 和 free 函數即可，然而對於高併發項目，我們得深入理解 ptmalloc 實現原理，從而清楚地知道 ptmalloc 存在的問題，爲後續優化打好基礎。

2.1 ptmalloc 常見問題

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

• 鎖競爭問題

  struct malloc_state 結構定義了一個 mutex 成員，多線程想要通過分配區進行內存分配時需要加鎖，頻繁分配內存會導致頻繁加鎖。

• 內存碎片問題

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

2.2 ptmalloc 高併發測試

1）測試代碼

    採用多個線程循環申請和釋放內存，每次隨機申請 SIZE_THREHOLD 範圍大小內存，如果申請的內存小於 LEAK_THREHOLD 大小，則申請的內存不釋放，人爲製造內存泄露，並實時統計泄露內存總量。

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

• 頻繁加鎖測試方法：

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

• 內存碎片測試

    通過：strace -tt -f -e trace=mprotect,brk ./a.out 命令執行測試程序，觀察是否調用 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 函數不適用於長期佔用內存的使用場景，長期佔用內存會導致內存碎片問題。

• 對併發要求不高的場景可以使用 malloc 和 free 函數，高併發場景需要使用更高效的內存池。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/WRpMNiEhjnzxM2MxH7rstw