如何實現一個 malloc

作者:張洋

https://kb.cnblogs.com/page/512454/

任何一個用過或學過 C 的人對 malloc 都不會陌生。大家都知道 malloc 可以分配一段連續的內存空間,並且在不再使用時可以通過 free 釋放掉。但是,許多程序員對 malloc 背後的事情並不熟悉,許多人甚至把 malloc 當做操作系統所提供的系統調用或 C 的關鍵字。

實際上,malloc 只是 C 的標準庫中提供的一個普通函數,而且實現 malloc 的基本思想並不複雜,任何一個對 C 和操作系統有些許瞭解的程序員都可以很容易理解。

這篇文章通過實現一個簡單的 malloc 來描述 malloc 背後的機制。當然與現有 C 的標準庫實現(例如 glibc)相比,我們實現的 malloc 並不是特別高效,但是這個實現比目前真實的 malloc 實現要簡單很多,因此易於理解。重要的是,這個實現和真實實現在基本原理上是一致的。

這篇文章將首先介紹一些所需的基本知識,如操作系統對進程的內存管理以及相關的系統調用,然後逐步實現一個簡單的 malloc。爲了簡單起見,這篇文章將只考慮 x86_64 體系結構,操作系統爲 Linux。

1 什麼是 malloc

在實現 malloc 之前,先要相對正式地對 malloc 做一個定義。

根據標準 C 庫函數的定義,malloc 具有如下原型:

void* malloc(size_t size);

這個函數要實現的功能是在系統中分配一段連續的可用的內存,具體有如下要求:

對於 malloc 更多的說明可以在命令行中鍵入以下命令查看:

man malloc

2 預備知識

在實現 malloc 之前,需要先解釋一些 Linux 系統內存相關的知識。

2.1 Linux 內存管理

2.1.1 虛擬內存地址與物理內存地址

爲了簡單,現代操作系統在處理內存地址時,普遍採用虛擬內存地址技術。即在彙編程序(或機器語言)層面,當涉及內存地址時,都是使用虛擬內存地址。採用這種技術時,每個進程彷彿自己獨享一片 2N 字節的內存,其中 N 是機器位數。例如在 64 位 CPU 和 64 位操作系統下,每個進程的虛擬地址空間爲 264Byte。

這種虛擬地址空間的作用主要是簡化程序的編寫及方便操作系統對進程間內存的隔離管理,真實中的進程不太可能(也用不到)如此大的內存空間,實際能用到的內存取決於物理內存大小。

由於在機器語言層面都是採用虛擬地址,當實際的機器碼程序涉及到內存操作時,需要根據當前進程運行的實際上下文將虛擬地址轉換爲物理內存地址,才能實現對真實內存數據的操作。這個轉換一般由一個叫 MMU[2](Memory Management Unit)的硬件完成。

2.1.2 頁與地址構成

在現代操作系統中,不論是虛擬內存還是物理內存,都不是以字節爲單位進行管理的,而是以頁(Page)爲單位。一個內存頁是一段固定大小的連續內存地址的總稱,具體到 Linux 中,典型的內存頁大小爲 4096Byte(4K)。

所以內存地址可以分爲頁號和頁內偏移量。下面以 64 位機器,4G 物理內存,4K 頁大小爲例,虛擬內存地址和物理內存地址的組成如下:

上面是虛擬內存地址,下面是物理內存地址。由於頁大小都是 4K,所以頁內便宜都是用低 12 位表示,而剩下的高地址表示頁號。

MMU 映射單位並不是字節,而是頁,這個映射通過查一個常駐內存的數據結構頁表 [3] 來實現。現在計算機具體的內存地址映射比較複雜,爲了加快速度會引入一系列緩存和優化,例如 TLB[4] 等機制。下面給出一個經過簡化的內存地址翻譯示意圖,雖然經過了簡化,但是基本原理與現代計算機真實的情況的一致的。

2.1.3 內存頁與磁盤頁

我們知道一般將內存看做磁盤的的緩存,有時 MMU 在工作時,會發現頁表表明某個內存頁不在物理內存中,此時會觸發一個缺頁異常(Page Fault),此時系統會到磁盤中相應的地方將磁盤頁載入到內存中,然後重新執行由於缺頁而失敗的機器指令。關於這部分,因爲可以看做對 malloc 實現是透明的,所以不再詳細講述,有興趣的可以參考《深入理解計算機系統》相關章節。

最後附上一張在維基百科找到的更加符合真實地址翻譯的流程供大家參考,這張圖加入了 TLB 和缺頁異常的流程(圖片來源頁 [5])。

2.2 Linux 進程級內存管理

2.2.1 內存排布

明白了虛擬內存和物理內存的關係及相關的映射機制,下面看一下具體在一個進程內是如何排布內存的。

以 Linux 64 位系統爲例。理論上,64bit 內存地址可用空間爲 0x0000000000000000 ~ 0xFFFFFFFFFFFFFFFF,這是個相當龐大的空間,Linux 實際上只用了其中一小部分(256T)。

根據 Linux 內核相關文檔 [6] 描述,Linux64 位操作系統僅使用低 47 位,高 17 位做擴展(只能是全 0 或全 1)。所以,實際用到的地址爲空間爲 0x0000000000000000 ~ 0x00007FFFFFFFFFFF 和 0xFFFF800000000000 ~ 0xFFFFFFFFFFFFFFFF,其中前面爲用戶空間(User Space),後者爲內核空間(Kernel Space)。圖示如下:

對用戶來說,主要關注的空間是 User Space。將 User Space 放大後,可以看到裏面主要分爲如下幾段:

下面我們主要關注 Heap 區域的操作。對整個 Linux 內存排布有興趣的同學可以參考其它資料。

2.2.2 Heap 內存模型

一般來說,malloc 所申請的內存主要從 Heap 區域分配(本文不考慮通過 mmap 申請大塊內存的情況)。

由上文知道,進程所面對的虛擬內存地址空間,只有按頁映射到物理內存地址,才能真正使用。受物理存儲容量限制,整個堆虛擬內存空間不可能全部映射到實際的物理內存。Linux 對堆的管理示意如下:

Linux 維護一個 break 指針,這個指針指向堆空間的某個地址。從堆起始地址到 break 之間的地址空間爲映射好的,可以供進程訪問;而從 break 往上,是未映射的地址空間,如果訪問這段空間則程序會報錯。

2.2.3 brk 與 sbrk

由上文知道,要增加一個進程實際的可用堆大小,就需要將 break 指針向高地址移動。Linux 通過 brk 和 sbrk 系統調用操作 break 指針。兩個系統調用的原型如下:

int brk(void *addr);
void *sbrk(intptr_t increment);

brk 將 break 指針直接設置爲某個地址,而 sbrk 將 break 從當前位置移動 increment 所指定的增量。brk 在執行成功時返回 0,否則返回 - 1 並設置 errno 爲 ENOMEM;sbrk 成功時返回 break 移動之前所指向的地址,否則返回 (void *)-1。

一個小技巧是,如果將 increment 設置爲 0,則可以獲得當前 break 的地址。

另外需要注意的是,由於 Linux 是按頁進行內存映射的,所以如果 break 被設置爲沒有按頁大小對齊,則系統實際上會在最後映射一個完整的頁,從而實際已映射的內存空間比 break 指向的地方要大一些。但是使用 break 之後的地址是很危險的(儘管也許 break 之後確實有一小塊可用內存地址)。

2.2.4 資源限制與 rlimit

系統對每一個進程所分配的資源不是無限的,包括可映射的內存空間,因此每個進程有一個 rlimit 表示當前進程可用的資源上限。這個限制可以通過 getrlimit 系統調用得到,下面代碼獲取當前進程虛擬內存空間的 rlimit:

int main() {
struct rlimit *limit = (struct rlimit *)malloc(sizeof(struct rlimit));
getrlimit(RLIMIT_AS, limit);
printf("soft limit: %ld, hard limit: %ld\n", limit->rlim_cur, limit->rlim_max);
}

其中 rlimit 是一個結構體:

struct rlimit {
rlim_t rlim_cur; /* Soft limit */
rlim_t rlim_max; /* Hard limit (ceiling for rlim_cur) */
};

每種資源有軟限制和硬限制,並且可以通過 setrlimit 對 rlimit 進行有條件設置。其中硬限制作爲軟限制的上限,非特權進程只能設置軟限制,且不能超過硬限制。

3 實現 malloc

3.1 玩具實現

在正式開始討論 malloc 的實現前,我們可以利用上述知識實現一個簡單但幾乎沒法用於真實的玩具 malloc,權當對上面知識的複習:

/* 一個玩具malloc */
#include <sys/types.h>
#include <unistd.h>
void *malloc(size_t size)
{
void *p;
p = sbrk(0);
if (sbrk(size) == (void *)-1)
return NULL;
return p;
}

這個 malloc 每次都在當前 break 的基礎上增加 size 所指定的字節數,並將之前 break 的地址返回。這個 malloc 由於對所分配的內存缺乏記錄,不便於內存釋放,所以無法用於真實場景。

3.2 正式實現

下面嚴肅點討論 malloc 的實現方案。

3.2.1 數據結構

首先我們要確定所採用的數據結構。一個簡單可行方案是將堆內存空間以塊(Block)的形式組織起來,每個塊由 meta 區和數據區組成,meta 區記錄數據塊的元信息(數據區大小、空閒標誌位、指針等等),數據區是真實分配的內存區域,並且數據區的第一個字節地址即爲 malloc 返回的地址。

可以用如下結構體定義一個 block:

typedef struct s_block *t_block;
struct s_block {
size_t size; /* 數據區大小 */
t_block next; /* 指向下個塊的指針 */
int free; /* 是否是空閒塊 */
int padding; /* 填充4字節,保證meta塊長度爲8的倍數 */
char data[1] /* 這是一個虛擬字段,表示數據塊的第一個字節,長度不應計入meta */
};

由於我們只考慮 64 位機器,爲了方便,我們在結構體最後填充一個 int,使得結構體本身的長度爲 8 的倍數,以便內存對齊。示意圖如下:

3.2.2 尋找合適的 block

現在考慮如何在 block 鏈中查找合適的 block。一般來說有兩種查找算法:

兩種方法各有千秋,best fit 具有較高的內存使用率(payload 較高),而 first fit 具有更好的運行效率。這裏我們採用 first fit 算法。

/* First fit */
t_block find_block(t_block *last, size_t size) {
t_block b = first_block;
while(&& !(b->free && b->size >= size)) {
*last = b;
b = b->next;
}
return b;
}

find_block 從 frist_block 開始,查找第一個符合要求的 block 並返回 block 起始地址,如果找不到這返回 NULL。這裏在遍歷時會更新一個叫 last 的指針,這個指針始終指向當前遍歷的 block。這是爲了如果找不到合適的 block 而開闢新 block 使用的,具體會在接下來的一節用到。

3.2.3 開闢新的 block

如果現有 block 都不能滿足 size 的要求,則需要在鏈表最後開闢一個新的 block。這裏關鍵是如何只使用 sbrk 創建一個 struct:

#define BLOCK_SIZE 24 /* 由於存在虛擬的data字段,sizeof不能正確計算meta長度,這裏手工設置 */
 
t_block extend_heap(t_block last, size_t s) {
t_block b;
b = sbrk(0);
if(sbrk(BLOCK_SIZE + s) == (void *)-1)
return NULL;
b->size = s;
b->next = NULL;
if(last)
last->next = b;
b->free = 0;
return b;
}

3.2.4 分裂 block

First fit 有一個比較致命的缺點,就是可能會讓很小的 size 佔據很大的一塊 block,此時,爲了提高 payload,應該在剩餘數據區足夠大的情況下,將其分裂爲一個新的 block,示意如下:

實現代碼:

void split_block(t_block b, size_t s) {
t_block new;
new = b->data + s;
new->size = b->size - s - BLOCK_SIZE ;
new->next = b->next;
new->free = 1;
b->size = s;
b->next = new;
}

3.2.5 malloc 的實現

有了上面的代碼,我們可以利用它們整合成一個簡單但初步可用的 malloc。注意首先我們要定義個 block 鏈表的頭 first_block,初始化爲 NULL;另外,我們需要剩餘空間至少有 BLOCK_SIZE + 8 才執行分裂操作。

由於我們希望 malloc 分配的數據區是按 8 字節對齊,所以在 size 不爲 8 的倍數時,我們需要將 size 調整爲大於 size 的最小的 8 的倍數:

size_t align8(size_t s) {
if(& 0x7 == 0)
return s;
return ((s >> 3) + 1) << 3;
}
#define BLOCK_SIZE 24
void *first_block=NULL;
 
/* other functions... */
 
void *malloc(size_t size) {
t_block b, last;
size_t s;
/* 對齊地址 */
s = align8(size);
if(first_block) {
/* 查找合適的block */
last = first_block;
b = find_block(&last, s);
if(b) {
/* 如果可以,則分裂 */
if ((b->size - s) >= ( BLOCK_SIZE + 8))
split_block(b, s);
b->free = 0;
} else {
/* 沒有合適的block,開闢一個新的 */
b = extend_heap(last, s);
if(!b)
return NULL;
}
} else {
b = extend_heap(NULL, s);
if(!b)
return NULL;
first_block = b;
}
return b->data;
}

3.2.6 calloc 的實現

有了 malloc,實現 calloc 只要兩步:

  1. malloc 一段內存

  2. 將數據區內容置爲 0

由於我們的數據區是按 8 字節對齊的,所以爲了提高效率,我們可以每 8 字節一組置 0,而不是一個一個字節設置。我們可以通過新建一個 size_t 指針,將內存區域強制看做 size_t 類型來實現。

void *calloc(size_t number, size_t size) {
size_t *new;
size_t s8, i;
new = malloc(number * size);
if(new) {
s8 = align8(number * size) >> 3;
for(i = 0; i < s8; i++)
new[i] = 0;
}
return new;
}

3.2.7 free 的實現

free 的實現並不像看上去那麼簡單,這裏我們要解決兩個關鍵問題:

  1. 如何驗證所傳入的地址是有效地址,即確實是通過 malloc 方式分配的數據區首地址

  2. 如何解決碎片問題

首先我們要保證傳入 free 的地址是有效的,這個有效包括兩方面:

第一個問題比較好解決,只要進行地址比較就可以了,關鍵是第二個問題。

這裏有兩種解決方案:一是在結構體內埋一個 magic number 字段,free 之前通過相對偏移檢查特定位置的值是否爲我們設置的 magic number,另一種方法是在結構體內增加一個 magic pointer,這個指針指向數據區的第一個字節(也就是在合法時 free 時傳入的地址),我們在 free 前檢查 magic pointer 是否指向參數所指地址。這裏我們採用第二種方案:

首先我們在結構體中增加 magic pointer(同時要修改 BLOCK_SIZE):

typedef struct s_block *t_block;
struct s_block {
size_t size; /* 數據區大小 */
t_block next; /* 指向下個塊的指針 */
int free; /* 是否是空閒塊 */
int padding; /* 填充4字節,保證meta塊長度爲8的倍數 */
void *ptr; /* Magic pointer,指向data */
char data[1] /* 這是一個虛擬字段,表示數據塊的第一個字節,長度不應計入meta */
};

然後我們定義檢查地址合法性的函數:

t_block get_block(void *p) {
char *tmp;
tmp = p;
return (p = tmp -= BLOCK_SIZE);
}
 
int valid_addr(void *p) {
if(first_block) {
if(p > first_block && p < sbrk(0)) {
return p == (get_block(p))->ptr;
}
}
return 0;
}

當多次 malloc 和 free 後,整個內存池可能會產生很多碎片 block,這些 block 很小,經常無法使用,甚至出現許多碎片連在一起,雖然總體能滿足某此 malloc 要求,但是由於分割成了多個小 block 而無法 fit,這就是碎片問題。

一個簡單的解決方式時當 free 某個 block 時,如果發現它相鄰的 block 也是 free 的,則將 block 和相鄰 block 合併。爲了滿足這個實現,需要將 s_block 改爲雙向鏈表。修改後的 block 結構如下:

typedef struct s_block *t_block;
struct s_block {
size_t size; /* 數據區大小 */
t_block prev; /* 指向上個塊的指針 */
t_block next; /* 指向下個塊的指針 */
int free; /* 是否是空閒塊 */
int padding; /* 填充4字節,保證meta塊長度爲8的倍數 */
void *ptr; /* Magic pointer,指向data */
char data[1] /* 這是一個虛擬字段,表示數據塊的第一個字節,長度不應計入meta */
};

合併方法如下:

t_block fusion(t_block b) {
if (b->next && b->next->free) {
b->size += BLOCK_SIZE + b->next->size;
b->next = b->next->next;
if(b->next)
b->next->prev = b;
}
return b;
}

有了上述方法,free 的實現思路就比較清晰了:首先檢查參數地址的合法性,如果不合法則不做任何事;否則,將此 block 的 free 標爲 1,並且在可以的情況下與後面的 block 進行合併。

如果當前是最後一個 block,則回退 break 指針釋放進程內存,如果當前 block 是最後一個 block,則回退 break 指針並設置 first_block 爲 NULL。實現如下:

void free(void *p) {
t_block b;
if(valid_addr(p)) {
b = get_block(p);
b->free = 1;
if(b->prev && b->prev->free)
b = fusion(b->prev);
if(b->next)
fusion(b);
else {
if(b->prev)
b->prev->prev = NULL;
else
first_block = NULL;
brk(b);
}
}
}

3.2.8 realloc 的實現

爲了實現 realloc,我們首先要實現一個內存複製方法。如同 calloc 一樣,爲了效率,我們以 8 字節爲單位進行復制:

void copy_block(t_block src, t_block dst) {
size_t *sdata, *ddata;
size_t i;
sdata = src->ptr;
ddata = dst->ptr;
for(i = 0; (i * 8) < src->size && (i * 8) < dst->size; i++)
ddata[i] = sdata[i];
}

然後我們開始實現 realloc。一個簡單(但是低效)的方法是 malloc 一段內存,然後將數據複製過去。但是我們可以做的更高效,具體可以考慮以下幾個方面:

下面是 realloc 的實現:

void *realloc(void *p, size_t size) {
size_t s;
t_block b, new;
void *newp;
if (!p)
/* 根據標準庫文檔,當p傳入NULL時,相當於調用malloc */
return malloc(size);
if(valid_addr(p)) {
s = align8(size);
b = get_block(p);
if(b->size >= s) {
if(b->size - s >= (BLOCK_SIZE + 8))
split_block(b,s);
} else {
/* 看是否可進行合併 */
if(b->next && b->next->free
&& (b->size + BLOCK_SIZE + b->next->size) >= s) {
fusion(b);
if(b->size - s >= (BLOCK_SIZE + 8))
split_block(b, s);
} else {
/* 新malloc */
newp = malloc (s);
if (!newp)
return NULL;
new = get_block(newp);
copy_block(b, new);
free(p);
return(newp);
}
}
return (p);
}
return NULL;
}

3.3 遺留問題和優化

以上是一個較爲簡陋,但是初步可用的 malloc 實現。還有很多遺留的可能優化點,例如:

還有很多可能的優化,這裏不一一贅述。下面附上一些參考文獻,有興趣的同學可以更深入研究。

4 其它參考

  1. 這篇文章大量參考了 A malloc Tutorial[7],其中一些圖片和代碼直接引用了文中的內容,這裏特別指出

  2. Computer Systems: A Programmer's Perspective, 2/E[8] 一書有許多值得參考的地方

  3. 關於 Linux 的虛擬內存模型,Anatomy of a Program in Memory[9] 是很好的參考資料,另外作者還有一篇 How the Kernel Manages Your Memory[10] 對於 Linux 內核中虛擬內存管理的部分有很好的講解

  4. 對於真實世界的 malloc 實現,可以參考 glibc 的實現 [11]

  5. 本文寫作過程中大量參考了維基百科 [12],再次感謝這個偉大的網站,並且呼籲大家在手頭允許的情況下可以適當捐助維基百科,幫助這個造福人類的系統運行下去

參考資料

__[1]NP-hard: __

_http://en.wikipedia.org/wiki/NP-hard
[2]MMU: _

_http://en.wikipedia.org/wiki/Memory_management_unit
[3] 頁表: _

_http://en.wikipedia.org/wiki/Page_table
[4]TLB: _

_http://en.wikipedia.org/wiki/Translation_lookaside_buffer
[5] 圖片來源頁: _

_http://en.wikipedia.org/wiki/Page_table
[6]Linux 內核相關文檔: _

_https://www.kernel.org/doc/Documentation/x86/x86_64/mm.txt
[7]A malloc Tutorial: _

_http://www.inf.udec.cl/~leo/Malloc_tutorial.pdf
[8]Computer Systems: _

_A Programmer's Perspective, 2/E: http://csapp.cs.cmu.edu/
[9]Anatomy of a Program in Memory: _

_http://duartes.org/gustavo/blog/post/anatomy-of-a-program-in-memory/
[10]How the Kernel Manages Your Memory: _

_http://duartes.org/gustavo/blog/post/how-the-kernel-manages-your-memory/
[11]glibc 的實現: _

_http://repo.or.cz/w/glibc.git/blob/HEAD:/malloc/malloc.c
[12] 維基百科: _

http://www.wikipedia.org/

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