mtrace(3)的thread safety

在使用mtrace(3)偵測multithreaded program的memory leak時發現出現不少false positive。查了manual發現它是MT-Unsafe (multithread unsafe)。好奇心驅使之下決定好好的來研究一下，希望可以徹底了解其運作原理，進而尋找出適合multithread環境的memory leak偵測方法。

Thread safety測試

這裡先用一個小程式來測試mtrace在multithread系統是否可以準確的偵測出memory leak:

#include <unistd.h>
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <mcheck.h>

#define THREAD_COUNT 200
#define MALLOC_COUNT 3000

void* threadFunc(void* arg)
{
    int i;
    unsigned size=0;
    void* ptr[MALLOC_COUNT];

    FILE* pf = fopen("/dev/urandom", "r");
    if (pf == NULL)
    {
        printf("cannot open /dev/urandom\n");
        return NULL;
    }

    for (i=0; i<MALLOC_COUNT; i++)
    {
        if (fread(&size, sizeof(unsigned char), 1, pf) != sizeof(unsigned char))
        {
            printf("fread fail\n");
            size = 0;
        }
        ptr[i] = malloc(size+1);
    }

    sleep(20);

    for (i=0; i<MALLOC_COUNT; i++)
        free(ptr[i]);

    fclose(pf);
    return NULL;
}

int main( int argc, char* argv[])
{
    pthread_t tid[THREAD_COUNT];
    int i;

    if (argc == 2)
    {
        setenv("MALLOC_TRACE", argv[1], 1);
        mtrace();
    }

    for (i=0; i<THREAD_COUNT; i++)
        pthread_create(&tid[i], NULL, threadFunc, NULL);

    for (i=0; i<THREAD_COUNT; i++)
        pthread_join(tid[i], NULL);

    if (argc == 2)
        muntrace();

    return 0;
}

在這個程式裡我們create出200個thread，每個thread各有3000次malloc-free pair，malloc的size則亂數分佈在0x1~0x100之間。

照邏輯看來這程式的malloc與free是成對的，也就是不會有memory leak，但實際測起來mtrace卻報了相當多的Memory not freed：

改用Valgrind來觀察同一個binary，如預期般的回報沒有發現leak。看來Valgrind在multithread系統中是比較值得信賴的！

接下來我們做另一個實驗，這次在每次呼叫free()的前後加mutex保護，確保一次只有一個thread能夠執行free()：

    for (i=0; i<MALLOC_COUNT; i++)
    {
        pthread_mutex_lock(&mtx);
        free(ptr[i]);
        pthread_mutex_unlock(&mtx);
    }

再跑一次果然就沒再報出leak了。

從實驗結果看來，mtrace果然不適用於multithread system！在現實之中我們當然不可能為了使用mtrace而在原程式加一堆mutex，何況有些malloc與free是隱藏在library function之中的 (如pthread_create, c++的new operator, std container ... )。

mtrace原理

接下來我們試著深入研究mtrace的運作原理並找出造成false positive的原因。

首先先看一下mtrace產生出來的bookkeeping檔案

這檔案記錄著程式裡所有malloc(以"+"表示)與free(以"-"表示)的資訊，包含分配到的動態空間位址(即malloc() return回來的值)、size及caller(讓我們可以知道是誰造成leak)。只要根據這些資訊去逐一比對確認所有malloc拿到的address都有對應的free，那我們就可以說程式是沒有memory leak的。

接著來研究mtrace是如何印出這些資訊的。既然我們是call mtrace()來啟動整個偵測flow的，理所當然的就從它開始看吧：

 這個function做了兩件事
1. 讀出環境變數MALLOC_TRACE，然後fopen()它做為輸出檔案
2. 備份__malloc_hook (如果沒有特別去改它的話預設值應該是NULL)，接著將tr_mallochook assign給__malloc_hook (__free_hook, __realloc_hook, __memalign_hook同理)

這裡的malloc_hook是GNU C library提供的一種redirect機制，讓我們可以把程式裡所有呼叫malloc()的function call redirect到我們自己定義的function。這功能允許我們很輕鬆的置換另一個memory allocate algorithm (例如dlmalloc)，或是做一些bookkeeping之類的工作。
glibc的manual: 3.2.2.10 Memory Allocation Hooks裡有詳細的說明，不過直接看source code更清楚：

我們在程式裡call的malloc()只是__libc_malloc()的alias。
程式一執行到__libc_malloc()馬上就去讀__malloc_hook這個變數，如果它是NULL，那就照平常那樣動態分配一塊記憶體給上層application使用；如果它不是NULL，那就會被redirect去執行我們設定的__malloc_hook function，分配記憶體的工作將不再由原先的malloc()負責。

而在mtrace()裡我們看到malloc_hook被設為tr_mallochook()，亦即程式裡所有malloc()會全被redirect到tr_mallochook()。

那tr_mallochook()又做了什麼呢？

可想而知最重要的當然就是記錄，在這裡動態分配到的address, size及caller會輸出到mallstream，也就是mtrace()裡根據環境變數MALLOC_TRACE開啟的那個檔案，有了這些記錄後續才能透過比對來找出memory leak。

除了記錄之外這裡還必須做動態記憶體的分配與管理，別忘了malloc()已經被redirect到此，原本malloc()該做的分配動態記憶體還是要做，不然上層的應用程式是跑不下去的。

glibc在這裡使用了一種取巧的方法，tr_mallochook()再度回call malloc()，讓它繼續幫我們分配記憶體空間。但是直接回call會出問題，因為此時__malloc_hook已經被設為tr_mallochook()，所以一回call malloc()馬上就又被redirect到tr_mallochook()，然後就形成infinite loop。所以在回call malloc()之前必須還原__malloc_hook。這樣一來既可以做bookkeeping，也可再利用原始的malloc()來分配記憶體，可以說是一舉兩得啊！

整個flow可以粗略的用下圖來描述：

可惜這巧妙的設計來到multithread的世界就走了樣！

問題就出現tr_mallochook()裡面的還原與重設__hook_malloc之間 (即上圖中的3,4之間)。如果這時候恰好發生context switch到其他thread，而該thread又剛好call了malloc()...
可以想像的，由於__malloc_hook已經被還原了，所以此時其他thread再call malloc()是不會被redirect到tr_mallochook()，也就是我們就少記錄了這筆資料。不單是malloc()，所有透過hook機制的free(), realloc(), memalign()均有可能發生這種情況，於是就造成了明明有free，但因為漏記了而被誤判為leak的情形了。

可能的解決方案

知道原理後就可以試著思考solution了。由於malloc(), mtrace(), tr_mallochook()均在glibc裡，第一個方案就是直接修改它們。mtrace雖然是MT-Unsafe，但malloc(), free()這些function卻都是thread safe的，差別就在於它們有用mutex保護著：

只是這個mutex是放在檢查__malloc_hook之後，也許我們可以試著把它拉到function最前面。不過mutex防守範圍愈大相對的也會降低程式的parallelism。原本的mutex只保護少數幾行關鍵global variable的修改，但現在卻拉大到整個function，效能降低應該蠻明顯的。

第二種修改方式是不去動glibc，仿照mtrace的模式用__malloc_hook自己來兜。
這做法彈性就大的多，我們可以使用dlmalloc來幫我們分配記憶體，這樣一來就不用不斷的還原與重設__malloc_hook，自然也不會發生synchronization的問題。概念上就如下圖表示：

另外在這種模式下我們還以印出更多資訊，像是thread id、thread name， 甚至還能透過backtrace(3)印出完整的call frame，這樣在分析memory leak上就更加得心應手了！