學過 C 語言的同學一定用過malloc, calloc, realloc, free。學會自己管理內存可以使程序性能更高。然而在不了解其內部原理的情況下使用它們，容易造成內存溢出、野指針等問題。
通過這篇文章，你將了解到內存、虛擬內存等概念，並且自己手寫一個內存管理器 (Memory Allocator)
內存 (RAM) 與 硬盤 (DRIVER)#
有些人會把內存和硬盤的概念混淆。通常，內存是用來儲存程序的二進制指令及相關變量的硬件，而硬盤則是用來儲存大量數據的硬件。
實際上，內存和硬盤沒有本質的區別，它們都是計算機儲存器(memory)，用來儲存一定的數據。內存的訪問速度快，但是單位造價高，所以用作需要頻繁讀寫的地方，例如儲存程序上下文。硬盤，讀寫速度相較於內存較慢，但是容量大，適合用作長期儲存不需要頻繁讀寫的文件。
內存可以看作是硬盤的緩存，當需要獲取一段數據時，可以將硬盤的數據臨時拷貝到內存。等到計算機需要這些數據時，可以直接從讀寫速度很快的內存中拿到它們。
這樣的緩存機制在計算機裡隨處可見，cpu 中除了 ALU (計算單元外)，還有一個重要的部分叫做 register (寄存器)，寄存器也是一種計算機儲存器，它可以看作是內存的緩存。這樣的說法實際上有些片面，cpu 還有一種叫做三級緩存的機制，此處不再贅述，有興趣的讀者可以自行查閱。
虛擬內存#
虛擬內存，是計算機系統 (OS) 對一塊內存的抽象。在應用程序的視角中，自己佔據計算機的全部內存 (一塊連續可用的地址空間)。然而實際上，這塊內存是由計算機系統暴露給應用程序的內存碎片。它可能不僅僅包含一部分物理內存，還會包含硬盤空間。
如果沒有虛擬內存，進程 (process) 間會對內存資源進行爭奪，甚至越界訪問，極易造成內存泄漏。並且由於進程的內存是以塊的形式儲存，小部分未分配的內存無法被更大的進程申請，造成了一定的資源浪費。
使用虛擬內存管理物理內存，我們可以將物理內存人為的劃分成一個個塊 (chunk)，多個塊組成頁 (page)，然後將頁與其佔有情況寫入頁表。這樣就可以將進程所需的內存拆分成塊的形式儲存，我們不必使這些內存集中存放，相反可以將它們放入任意位置。** 只需要記錄虛擬內存與物理內存之間的映射關係 (index)，將映射關係存放在頁表中，我們就可以根據這些信息找到物理內存地址。** 並且這些操作都是由硬件完成，速度極快，大大增加了內存的可用性和效率。
cpu 首先接受到操作指令，並且將虛擬地址發送到 MMU (內存管理單元)，MMU 將訪問物理內存 (實際上訪問了物理內存的緩存，TLB) 獲取頁表，然後找到其映射關係並計算出物理地址，之後交給 cpu，cpu 訪問物理內存取得數據。
內存的結構#
在開始操作內存前，我們先了解一下內存的結構都有哪些。
- Text section
- Data section
- BSS
- Heap
- Stack
我們在使用malloc時操作的內存結構是 Heap (堆)。它的末尾有一個名為brk的指針，它指向堆頂。
這是一種可以動態分配的內存結構，可以根據需求動態的申請一定量的內存，同時支持刪除操作，我們一般通過指針對申請的地址進行數據操作。
操作內存並不需要我們直接對硬件進行操作，可以直接使用系統封裝好的 APIsbrk()
sbrk(0)返回當前程序執行的位置的內存地址。
sbrk(x)使得brk向正方向增長 x 字節 (bytes)。
sbrk(-x)使得brk向負方向增長 x 字節 (bytes)。
如果 sbrk () 出於某些原因未能完成操作，將返回(void*) -1
malloc()#
好了，目前為止我們終於可以寫出一個簡易的malloc()了:
void* malloc( size_t size )
{
void* block;
block = sbrk(size);
if ( block == (void*) -1 )
return NULL;
return block;
}
看起來很不錯，但是不夠完美。
在寫free()函數時我們接受一個指針，以便釋放與它相關的內存，然而我們如何得知釋放內存的大小呢？
我們可以在每段地址的初段定義一個Header:
struct header_t {
size_t size;
unsigned is_free;
};
size用來儲存Header指向的內存的大小。
is_free用來標記這塊內存是否被佔用。
現在我們的一塊內存看起來是這樣的:
我們還需要一個方法可以遍歷這個內存，因為我們需要遍歷以找到一塊未被佔用的內存。鏈表是一個不錯的方案:
struct header_t {
size_t size;
unsigned is_free;
struct header_t* next;
};
現在它長這樣:
由於我們以塊的形式管理內存，所以需要對齊操作:
typedef char ALIGN[16];
union header {
struct {
size_t size;
unsigned is_free;
union header *next;
} s;
ALIGN stub;
};
typedef union header header_t;
我們還需要定義首尾節點:
header_t *head, *tail;
為了避免多線程同時調用內存，要定義我們加入全局鎖，在申請完地址後再釋放:
pthread_mutex_t global_malloc_lock;
現在我們的版本是這樣的:
void* malloc(size_t size) {
size_t total_size;
header_t* header;
void* block;
if ( size <= 0 ) {
return NULL;
};
pthread_mutex_lock(&global_malloc_lock);
header = get_header_t(size);
if (header)
{
header->s.isFree = 0;
pthread_mutex_unlock(&global_malloc_lock);
return (void*)(header + 1);
}
total_size = size + sizeof(header_t);
block = sbrk(total_size);
if (block == (void*) - 1) {
pthread_mutex_unlock(&global_malloc_lock);
return NULL;
} else {
header = block;
};
header->s.isFree = 0;
header->s.size = size;
header->s.next = NULL;
if (head == NULL)
head = header;
if (tail)
tail->s.next = header;
tail = header;
pthread_mutex_unlock(&global_malloc_lock);
return (void*)(header + 1);
};
header_t* get_header_t( size_t size ) {
header_t* curr = head;
while (curr)
{
if ( curr->s.isFree && curr->s.size >= size) {
pthread_mutex_unlock(&global_malloc_lock);
return (void*)(head);
};
curr = curr->s.next;
}
return NULL;
}
首先我們判斷申請的內存是否合法，之後尋找最低地址的節點指針 (get_header_t())。
找到了就標記為isFree，然後解鎖返回虛擬地址的首端的指針。
如果沒有找到，就調用sbrk申請內存，並初始化header將其設為tail節點，之後解鎖返回地址。
其中total_size包含頭部與實際所需內存大小兩部分。
free()#
在設計free()函數時，有一個需要注意的細節：先判斷需要釋放的地址是否位於堆的尾部
如果位於尾部，則直接交給操作系統釋放，否則將其標記為isFree，我們將在以後重用它們。
void free(void* block) {
if (!block)
{
return NULL;
}
header_t* header = (header_t*)block - 1;
void* programbreak = sbrk(0);
pthread_mutex_lock(&global_malloc_lock);
if ((char*)block + header->s.size == programbreak)
{
size_t total_size = header->s.size + sizeof(header_t);
//release
if (head == tail)
{
head = tail = NULL;
} else {
header_t* curr = head;
//change tail
while (curr->s.next == tail)
{
curr->s.next = NULL;
tail = curr;
}
}
sbrk(-total_size);
pthread_mutex_unlock(&global_malloc_lock);
return;
};
header->s.isFree = 1;
pthread_mutex_unlock(&global_malloc_lock);
}
首先找到brk的位置並將其賦給programbreak，之後判斷釋放的對象是否位於堆頂。
char*與size_t, void*具有相同的字節數:
//test.c
#include <stddef.h>
int main(int argc, char const *argv[])
{
printf("char* is:%d, char is:%d, void* is:%d, size_t is:%d", sizeof(char*), sizeof(char), sizeof(void*), sizeof(size_t));
return 0;
}
//char* is:8, char is:1, void* is:8, size_t is:8
如果在堆頂，則(char*)block + header->s.size == programbreak
之後遍歷找到最後一塊內存並釋放，把倒數第二塊內存設為tail。
如果不在堆頂，則暫時標記為isFree，等待之後復用。
calloc()#
void* calloc( size_t nsize, size_t num)
{
size_t size;
void* block;
if (!num || !nsize)
return NULL;
size = nsize * num;
//overflow check
if (size != nsize * num)
return NULL;
block = malloc(size);
if (!block)
return NULL;
memset(block, 0, size);
return block;
}
calloc () 要求返回的地址所指向的內存塊都為Null，我們可以通過memset將其設為 0。
realloc()#
void* realloc(void* block, size_t size)
{
header_t* header;
void* ret;
if (!block || !size)
return NULL;
header = (header_t*)block - 1;
if (header->s.size >= size)
return block;
ret = malloc(size);
if (ret)
{
memcpy(ret, block, header->s.size);
free(block);
}
return ret;
}
realloc()比較特殊，使用時應該注意返回的指針所指向的地址不一定會是原來的地址。
因為realloc()時，會出現兩種情況:
- 堆內存向高位增長，上方空閒的內存大小可以容納增長大小。則返回原來的地址，並修改
header的size。 - 堆內存上方空閒內存不足，調用
malloc重新申請一塊地址，並把原地址內容複製給新申請的地址。
Compile#
$ gcc -o memalloc.so -fPIC -shared memalloc.c
$ export LD_PRELOAD=$PWD/memalloc.so
$ ls
memalloc.c memalloc.so
拓展#
c/c++ 一直以其性能優越著名，然而這也是一直讓人詬病的地方。如果使用它的人缺少對計算機系統的深入了解，很容易造成誤操作。
而其他高級語言將內存管理自動化，並將其機制命名為垃圾回收(OC)，其原理大致可概況為：如果某對象不可達則會被垃圾回收器回收。
References#
推薦閱讀: