任何一個對C稍稍有了解的人都知道malloc、calloc、free。前面兩個是用戶態在堆上分配一段連續(虛擬地址)的內存空間，然后可以通過free釋放，但是，同時也會有很多人對其背后的實現機制不了解。

這篇文章則是通過介紹這三個函數，并簡單的予以實現，對比現有C的標準庫實現(glibc等)相比，并不是特別高效，我們重在闡述背后的基本原理。

一、C程序的存儲空間布局

圖1

text：整個用戶空間的最低地址部分，存放的是指令(程序所編譯成的可執行機器碼)。可共享，即使是頻繁操作執行的程序，在存儲器中也只需有一個副本，通常是只讀的。

initialized data(data)：存放初始化過的全局變量，包含了程序中需明確地賦初值的變量。

uninitialized data(bss)：存放的是未初始化過的全局變量，在程序開始執行之前，內核將此段中的數據初始化為0或者NULL。

heap：堆，自低地址向高地址增長，后面重點剖析

stack：棧，自高地址向低地址增長，自動變量以及每次函數調用時所需保存的信息都存放在此段中。

二、Heap 內存模型

一般來說，malloc所申請的內存主要從heap區域分配的。

linux內存管理，從這里可以了解到linux下虛擬地址與物理地址。

linux對堆的管理如下：

圖2

linux 內核維護一個break指針，這個指針指向堆空間的某個地址。從堆起始地址(Heap’s Start)到break之間的地址空間為映射好的(虛擬地址與物理地址的映射，通過MMU實現)，可以供進程訪問；而從break往上，是未映射的地址空間，如果訪問這段空間則程序會報錯。

所以，如果Mapped Region 空間不夠時，會調整break指針，擴大映射空間，重新分配內存。

三、調整break：brk()和sbrk()

最初break的位置正好位于bss端末尾之后，看圖1，在break指針的位置升高時，程序可以訪問新分配區域內的任何內存地址，而此時物理內存頁尚未分配，內存會在京城首次試圖訪問這些虛擬內存地址時自動分配新的物理內存頁。

linux通過brk和sbrk系統調用操作break指針：

int brk(void *addr);

void *sbrk(intptr_t increment);

brk() 將break指針設置為 addr 所指定的位置，由于虛擬內存以頁為單位進行分配，addr實際會四舍五入到下一個內存也的邊界處。

由于brk是直接指定一個地址，所以一旦這個值取得過低，有可能導致不可預知的行為，對照圖1，brk只能在指定的區域內調整break。

sbrk() 將break指針在原有地址增加從參數 increment 傳入的大小(linux中，sbrk是基于brk基礎上實現的一個庫函數)，用于聲明increment 的intptr_t 類型屬于整數數據類型。

若調用成功，sbrk() 返回前一個break 的地址，換言之，如果break 增加，那么返回值是指向這塊新分配內存起始位置的指針。

sbrk(0) 將得到當前break指針的位置。

系統對每一個進程所分配的資源不是無限的，包括可映射的內存空間，圖2，未映射內存的尾端有個rlimit表示當前進程可用的資源上限。

三、malloc

根據標準C庫函數的定義，malloc 具有如下模型：

void* malloc(size_t size);

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

- malloc分配的內存大小至少為size參數所指定的字節數

- malloc的返回值是一個指針，指向一段可用內存的起始地址

- 多次調用malloc所分配的地址不能有重疊部分，除非該地址已經被釋放掉

- malloc應該盡快完成內存分配并返回(不能使用NP-hard的內存分配算法)

- 實現malloc時，應該同時實現內存大小調整和內存釋放函數(calloc和free)

- malloc分配失敗時必須返回NULL

malloc 返回內存塊所采用的字節對齊方式，總是適宜于高效訪問任何類型的C語言數據結構。

四、初探實現malloc：

我們假定整個內存處于初始狀態，即break指針位于bss段的單位，整個heap都是 Unmapped Region。(圖2)

基于此，我們可以實現一個簡單但毫無實際價值的malloc：

/*一個糟糕的仿制malloc*/

#include

#incldue

void *malloc(size_t size)

{

void *p;

p = sbrk(0);

/*如果sbrk失敗，返回NULL*/

if(sbrk(size) == (void*)-1)

return NULL;

return p;

}

這個malloc就是從未映射區域直接劃出一塊，但是malloc對這塊已分配的內存缺乏記錄，不便于內存釋放。

五、正式實現malloc

上面說到分配的內存沒有記錄，一旦調用free釋放，free不知道它到底要釋放多大的內存，所以我們需要額外一個數據結構來記錄這些信息。

5.1、數據結構

一個簡單可行方案是將堆內存以塊的形式組織起來，每個塊(block)由meta區和數據區組成，meta去記錄數據塊的元信息(數據塊大小、空閑標志位、指針等)，數據區則是真實分配的內存區域，并且數據區的第一個字節地址即為malloc返回的地址。

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

typedef struct s_block *t_block;

struct s_block{

size_t size;//數據區大小

t_block next;//指向下個塊的指針

int free;//是否是空閑塊

char data[1];//虛擬字段，表示數據塊的第一個字節，長度不計入meta

};

圖3

那么用這個結構體來分配內存，而不用malloc則是下面一番場景：

t_block b;

b = sbrk(0);

sbrk(sizeof(struct s_block) + size);

b->size = size;//size 為要分配的內存大小

5.2、尋找合適的block

我們從堆的起始地址開始查找第一個符合要求的block，并返回block起始地址，如果找不到就返回NULL；

t_block find_block(t_block *last, size_t size)

{

t_block b = base;

while(b && !(b->free && b->size >= size))

{

*last = b;

b = b->next;

}

return b;

}

這里base是一個全局變量，維護整個堆的起始地址。另外，這里在遍歷時會更新一個last指針，這個指針始終指向當前遍歷的block，如果找不到合適的block，那么malloc將很容易的開辟新的block使用。

5.3、開辟新的block

如果現有block都不能滿足需求，則需要在鏈表最后開辟一個新的block。最簡單的方式就是利用sbrk升高break位置然后對其初始化，然后更新對應block指針，將其add到鏈表最后。

t_block extend_heap(t_block last, size_t size)

{

t_block b;

b = sbrk(0);//定位到當前break位置

if(sbrk(sizeof(struct s_block) + size) == (void*)-1)//調整break位置

return NULL;

b->size = size;

b->next = NULL;

if(last)//這個last是指向extend之前最后一個block

last->next = b;//新開辟的block掛載在鏈表中

b->free = 0;

return b;

}

5.4、分裂block

看前面 find_block() 的實現，如果我們申請的 size 遠小于查找到的 block。(這種情況是可能，它是查到第一個滿足條件(大小，可用)的block)，這樣會導致較大內部碎片的產生。

所以，應該在剩余數據區足夠大的情況下，將其分裂成一個新的block：

圖4

//b是要分裂的block，size是申請的內存大小

//分裂后b成了分配后的block

void split_block(t_block b, size_t size)

{

t_block new;//新的空閑block = 要分裂的block - 申請分配出去的內存

new = b->data + size;//將new定位到剩下的數據塊區域

//分裂的原block-分配出去的內存大小-block結構體本身大小

new->size = b->size - size - BLOCK_SIZE;

new->next = b->next;//鏈表插入

new->free = 1;//空閑標記可用

b->size = size;

b->next = new;//鏈表插入

}

看了上面一大串，是不是跟伙伴算法很像。但是這里的分裂block函數，得視情況調用，如果申請的size < block->size，但是又不是小太多，如果分裂block的話，會導致分裂后剩余未分配出去的數據塊過小，無法滿足其余需求，很容易形成內存碎片。

所以，伙伴算法有更高效的處理(實際上伙伴算法也會產生內部碎片)。

5.5、malloc 的實現

鋪墊做了那么多，我們可以利用它們整合成一個簡單可用的malloc。

首先定義一個block鏈表的頭指針，初始化為NULL，另外，我們需要剩余空間至少有 BLOCK_SIZE + 4 才執行分離操作。

此外，一開始我們講到，malloc對分配的內存大小也有要求，是按4字節對齊，所以申請的size不為4的倍數時，我們需要將其調整為大于size的最小的4的倍數。

#define align4(x) (((((x)-1)>>2)<<2)+4)

#define BLOCK_SIZE 12

void *base = NULL;

void *malloc(size_t size)

{

t_block b, last;

size_t s;

s = align4(size);

if(base)

{

//first find a block

last = base;

b = find_block(&last, s);

if(b)

{

//can we split

if((b->size - s) >= (BLOCK_SIZE + 8))

split_block(b, s);

b->free = 0;

}

else

{

//no fitting block, extend the heap

b = extend_heap(last, s);

if(!b)

return NULL;

}

}

else

{

//first time

b = extend_heap(NULL, s);

if(!b)

return NULL;

base = b;

}

return b->data;

}

實現思路很簡單：首先往鏈表中查找合適的block，如果找到了，看是否可以分裂，如果可以就分裂；如果沒有找到合適的，就開辟一個新的block；如果是第一次分配，即整個內存鏈表不存在，則一開始就得新開辟一個block。

六、calloc 的實現

先看calloc的標準庫語義：函數 calloc() 用于給一組相同對象分配內存。

void *calloc(size_t numitems, size_t size)

參數numitems指定分配對象的數量，size指定每個對象的大小。

calloc 與之malloc 不同之處在于，calloc 會將分配后的內存空間初始化，而malloc 申請的是一塊未初始化的內存。

所以，實現calloc，只需兩步：

malloc 一塊內存

將數據區內容初始化為0

void *calloc(size_t numitems, size_t size)

{

size_t *new;

size_t s, i;

new = malloc(numitems * size);

if(new)

{

//因為申請的內存總是4的倍數，所以這里我們以4字節為單位初始化

s = align4(numitems * size) >> 2;

for(i = 0; i < s; ++i)

new[i] = 0;

}

return new;

}

七、free 的實現

free 的實現并不像看上去那么簡單，需要解決兩個關鍵問題：

如何驗證所傳入的地址是有效地址(malloc方式分配的)

如何解決碎片問題

7.1、先看如何解決碎片問題，就是把相鄰的空閑內存合并為大的(伙伴算法類似)：

//合并相鄰空閑的內存塊，參數決定合并的是上一個還是下一個

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;

}

再看如何驗證所傳入的地址是有效的，位于heap內。

一個解決方法是，在block結構體中添加一個 ptr 指針，用于指向數據塊區域，如果 b->ptr == b->data，則表示 b 極有可能是一個有效block。

所以我們對block數據結構進行了擴展：

struct s_block{

size_t size;//數據區大小

t_block next;//指向下個塊的指針

int free;//是否是空閑塊

struct s_block *next;

struct s_block *prev;

void *ptr;

char data[1];

};

7.2、根據給定地址得到對應的block

//注意，這個函數最后通過偏移量得到的block可能是有效的，可能不是有效的

t_block get_block(void *p)

{

char *tmp;

tmp = p;

return (p = tmp -= BLOCK_SIZE);

}

7.3、下面則驗證是不是有效的block：

int valid_addr(void *p)

{

if(base)

{

if(p > base && p < sbrk(0))

return (p == (get_block(p))->ptr);

//如果兩個字段地址一樣，表示是一個有效block

}

return 0;

}

7.4、下面就實現free

這里我們采用的合并策略是這樣的：先合并相鄰的空閑內存塊，合并之后，再檢查是否還有空閑的相鄰內存塊，如果有則繼續合并，直到最后，該內存塊是最大的連續內存塊。

另外，對于break指針的調整(降低)，必須保證在該釋放的block與 Unmapped Region之間是空閑的，沒有被占。

void free(void *p)

{

t_block b;

if(valid_addr(p))//地址的有效性驗證

{

b = get_block(p);//得到對應的block

b->free = 1;

//如果相鄰的上一塊內存是空閑的就合并,

//合并之后的上一塊還是空閑的就繼續合并，直到不能合并為止

while(b->prev && b->prev->free)

{

b = fusion(b->prev);

}

//同理去合并后面的空閑block

while(b->next)

fusion(b);//內部會判斷是否空閑

//如果當前block是最后面的那個block，此時可以調整break指針了

if(NULL == b->next)

{

if(b->prev)//當前block前面還有占用的block

b->prev->next = NULL;

else//當前block就是整個heap僅存的

base = NULL;//則重置base

brk(b);//調整break指針到b地址位置

}

//否則不能調整break

}

}

八、realloc的實現

同樣先看標準庫中realloc的語義：

void *realloc(void *ptr, size_t size)

ptr 是指向需要調整大小的內存塊的指針，參數 size 指定所需調整大小的期望值。

realloc() 用來調整(通常是增加)一塊內存的大小，而此塊內存應是之前由malloc函數分配的。若 realloc 增加了已分配內存塊的大小，則不會對額外分配的內存進行初始化。

8.1、內存塊復制

看了realloc的語義，我們首先得實現一個內存復制方法。如同calloc一樣，我們以4字節為單位進行復制：

void copy_block(t_block src, t_block dst)

{

int *sdata, *dtata;

size_t i;

sdata = src->ptr;

ddata = dst->ptr;

for(i = 0; i*4 < src->size && i*4 < dst->size; ++i)

ddata[i] = sdata[i];

}

8.2、實現realloc

為了更高效，我們考慮以下幾個方面：

如果當前block的數據區大于等于realloc要求的size，則考慮能不能split，然后直接返回

如果新的size變小了，考慮split

如果當前block的數據區不能滿足size，但是其后繼block是free，并且合并后可以滿足size，則考慮合并，然后再考慮能不能split

如果以上都不行，則調用malloc重新分配size大小內存，然后內存復制

void *realloc(void *p, size_t size)

{

size_t s;

t_block b, new;

void *newp;

if(!p)

return malloc(size);

if(valid_addr(p))

{

s = align4(size);

b = get_block(p);//得到對應的block

if(b->size >= s)//如果size變小了，考慮split

{

if(b->size - s >= (BLOCK_SIZE + 4))

split_block(b, s);

}

else//如果當前block的數據區不能滿足size

{

//如果后繼block是free的，并且合并后大小滿足size，考慮合并

if(b->next && b->next->free

&& (b->size + BLOCK_SIZE + b->next->size) >= s)

{

fusion(b);

//合并后滿足size，再看能不能split

if(b->size - s >= (BLOCK_SIZE + 4))

split_block(b, s);

}

else//以上都不滿足，則malloc新區域

{

newp = malloc(s);

if(!newp)

return NULL;

//內存復制

new = get_block(newp);

copy_block(b, new);

free(p);//釋放old

return newp;

}

}

return p;//當前block數據區大于size時

}

return NULL;

}

九、總結

以上是一個比較簡陋，存在很大的優化空間，但大致闡述了malloc的機制，這也是本篇博文的目的。

對于更好的優化讀者可以參考linux內核伙伴算法、以及STL空間配置器。

十、參考資料：

1、《Advanced Programming in the UNIX Environment》

2、《The Linux Programming Interface》

3、 A Malloc Tutorial

總結

以上是生活随笔為你收集整理的c语言malloc calloc,C语言内存管理：malloc、calloc、free的实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。