我們知道，在程序中進行內存分配和處理，是一個合格碼農必備的技能。高級語言都通過GC實現內存的管理，減輕了程序員的自己撰寫內存管理相關代碼的負載。但是使用GC的語言本身很難實現高效性能，在需要高性能計算能場合下C語言還是一個必要的選擇，尤其Linux下很多關鍵的底層類庫都是用C撰寫的高級語言對其類庫進行打包使用。今天蟲蟲就和大家一起重溫下C語言中編寫內存操作的各種方法，並自己實現malloc()，calloc()，realloc()和free()等內存分配器。
在構建內存分配器之前，首先我們需要熟悉下程序的內存佈局。在現實中，用戶層都是不能直接接觸到物理地址的內存，而是通過程序進程中，每一個進程OS會給其分配一個虛擬地址空間內，該虛擬地址空間與其他進程的虛擬地址空間不同。每個進程虛擬地址空間通常包含5個部分：
文本部分：這部分是處理器執行的二進制指令的部分。
數據部分：非零初始化靜態數據。
BSS符號啟動塊：存放零初始化的靜態數據。程序中未初始化的靜態數據初始化為0並存放在這個地方。
堆：包含動態分配的數據。（各種變量等）
棧：包含自動變量，函數參數，基指針的副本等。
堆棧和堆在相反的方向上做數據增長。有些文檔中把數據，bss和堆部分統稱為數據段，數據端末尾由名為program break或brk的指針劃分，brk指向堆的末尾。如果我們想在堆中分配更多內存，需要請求系統增加brk。對應地如果我們要釋放內存，需要請求系統減少brk。
在Linux（或類Unix系統）中，我們可以通過sbrk()系統調用操作程序中斷，調用sbrk(0)就會給出程序中斷的當前地址。
使用正值調用sbrk(x)會使brk增加x個字節，從而分配內存。
使用負值調用sbrk(-x)會將brk減少x個字節，從而釋放內存。
失敗時，sbrk(),返回（void *）-1。
在現實中的編程中，sbrk()由於太低端，而且線程不安全，所以沒法在多線程編程中使用。一般都使用更高級的函數nmap()。但是，在底層的malloc的glibc實現中，還是用sbrk()來分內存。在本文示例中，為了方便我們使用sbrk()作為簡單的內存分配器。
malloc
malloc(size)函數分配指定字節大小的內存，並返回指向所分配內存的指針。簡單的malloc將如下所示：
void *malloc(size_t size)
{
void *block;
block = sbrk(size);
if (block == (void*) -1)
return NULL;
return block;
}
在上面的代碼中，我們使用給定的大小size調用sbrk()。函數調用成功時，就會在堆上分配該字節大小的內存。內存的分配非常簡單，比較麻煩的對用完的內存如何釋放。
free(ptr)函數釋放ptr指向的內存塊，該內存塊由malloc()，calloc（）或realloc()調用返回。為了釋放一塊內存，我們需要知道要釋放的內存塊的大小。但是我們沒法獲取任何內存大小的信息。為了能夠順利的釋放內存，我們必須想辦法記錄分配的內存塊的大小。
我們知道操作系統提供的堆內存是連續存放的，我們只能釋放堆末尾的內存。為了解決釋放非堆末尾的內存的問題，我們將區分釋放內存（free）和回收內存（release）。釋放一塊內存並不一定意味著我們將內存回收。只用來表示該塊被標記為空閒。標記為空閒的塊還可以在稍後的malloc()調用中重用。由於不能釋放堆末尾的內存，我們使用該折衷的方法。我們的方法中，我們為每個已分配內存塊存記錄：塊大小；該塊是否空閒。為了存儲這些信息，我們將為每個新分配的內存塊添加頭標誌。頭標誌結構如下：
struct header_t {
size_t size;
unsigned is_free;
};
當程序請求size大小字節的內存時，我們先計算大小為： total_size = header_size + size，並調用sbrk(total_size)分配內存。最後通過sbrk()返回的這個內存空間。
由於我們無法完全確定malloc分配的內存塊是連續的。比如有一個外來的程序調用了sbrk()。所以我們需要一種遍歷內存塊的方法。因此，為了跟蹤malloc分配的內存，我們需要通過一個鏈表中，標誌頭結構相應掉整為：
現在我們通過一個頭尾指針來跟蹤鏈表。
struct header_t * head，* tail;
為了防止兩個或多個線程同時訪問內存，我們要有一個基本的鎖定機制。我們要有一個全局鎖，在每次內存操作之前你必須獲得鎖定，調用完成後，再釋放鎖定。
pthread_mutex_t global_malloc_lock;
我們的malloc的實現現在如下：
我們首先檢查請求的大小size是否為零。如果是，那麼我們返回NULL。如果大小參數非零，則通過pthread_mutex_lock(&global_malloc_lock)獲得鎖定。接著調用get_free_block()得到標誌頭header；緊接著是遍歷鏈表，看看是否存在一個標記為空閒的內存塊，並且可以容納給定的大小。如果找到足夠大的空閒塊，我們將簡單地將該塊標記為非空閒，釋放全局鎖，然後返回指向該塊的指針。
如果我們沒有找到足夠大的空閒塊，則通過調用sbrk()來擴展堆。堆必須擴展一個符合請求大小以及頭標誌的大小。總大小total_size = sizeof（struct header_t）+ size;最後調用sbrk（total_size）。
通過這樣方法獲得的存儲器中，我們首先為header獲取空間。在C語言中，不需要將void *轉換為任何其他指針類型，可以自動轉換。
最後更新鏈表的next指針，head以及tail，以反映鏈表的新狀態。
free
接著，我們再來實現free(),該調用必須首先確定要釋放的塊是否在堆的末尾。如果是，我們可以將他提交操作系統回收。否則，只需將其標記為"free"，可以在以後重複使用。
首先我們要釋放的標誌頭。我們需要做的就是獲得一個位於塊後面的指針，大小為頭大小的內存塊。因此，我們將塊轉換為標誌頭指針類型並將其移動1個單位。
header =（struct header_t *）block - 1;
sbrk(0)給出程序中斷的當前值。為了檢查要釋放的塊是否在堆的末尾，我們首先找到當前塊的結尾地址： (char*)block + header->size。然後將其與程序中斷做比較。
如果它位於末尾，我們減小堆的大小並通知OS回收堆內存。首先重置鏈表的頭部和尾部指針以反映最後一個塊的丟失。然後計算要釋放的內存量。這是標誌頭和實際塊的大小之和：sizeof（struct header_t）+ header-> size。為了回收該大小的內存，我們用這個值的負數調用sbrk()函數。
如果該塊不是鏈表中的最後一個，我們只需設置標誌頭的is_free字段。這是在實際調用malloc()中的sbrk()之前由get_free_block()檢查的字段。
calloc
calloc（num，nsize）函數為每個nsize字節的num個元素數組分配內存，並返回指向已分配內存的指針。並且，內存全部設置為零。
在這裡，我們快速檢查乘法溢出，然後調用malloc()，並使用memset()將分配的內存清除為全零。
realloc
realloc() 將給定內存塊的大小更修改為指定的大小。
我們獲取標誌頭，看看塊是否可以容納所請求大小。如果可以，就不需要調整。
如果當前塊不夠所請求的大小，那麼我們調用malloc()來獲取請求大小的塊，並使用memcpy()將內容重定位到新的更大的塊。然後釋放舊的內存塊。
編譯和分配器
該文的涉及內存分配器源代碼，如果需要可以關注蟲蟲，並給蟲蟲發消息或者回複本文章。
我們編譯該源文件為庫文件。
gcc -o memalloc.so -fPIC -shared memalloc.c
-fPIC和-shared選項確保編譯的輸出具有與位置無關的代碼，並告訴鏈接器生成適合於動態鏈接的共享對象。
在Linux上，如果將enivornment變量LD_PRELOAD設置為共享對象的路徑，則該文件會優先於任何任何其他庫加載。我們可以利用該技巧優先加載編譯的庫文件，以便在shell中運行的後續命令將使用我們的malloc()，free（），calloc（）和realloc()。
export LD_PRELOAD = $PWD/memalloc.so
閱讀更多 蟲蟲安全 的文章
