免責申明（必讀！）：本博客提供的所有教程的翻譯原稿均來自于互聯(lián)網(wǎng)，僅供學習交流之用，切勿進行商業(yè)傳播。同時，轉載時不要移除本申明。如產(chǎn)生任何糾紛，均與本博客所有人、發(fā)表該翻譯稿之人無任何關系。謝謝合作！

原文鏈接地址：http://os-blog.com/basic-malloc-implementation/

? ?已經(jīng)有很多不同的，很強大的malloc的具體實現(xiàn)，比如tcmalloc,?ptmalloc,?dlmalloc, and?jemalloc，但是，在我們不加思索的使用這些之前，考慮一下如果實現(xiàn)一個基本的簡單的malloc函數(shù)是非常有用的。

?現(xiàn)在，一般來說，我們可以實現(xiàn)malloc使得對malloc的調(diào)用將會被映射到系統(tǒng)調(diào)用sbrk上，sbrk(n)將會移動程序中斷的位置-也就是程序的data段的最后。-偏移n個字節(jié)，這意味著，n個字節(jié)的內(nèi)存就被分配給了當前程序

我們最終的實現(xiàn)大概看起來會像這樣

void* malloc (unsigned n)
{
return sbrk(n);
}

?

然而，調(diào)用一次sbrk是非常昂貴的。因此，如果我們的malloc實現(xiàn)，通過一次sbrk調(diào)用分配到了一塊很大的內(nèi)存塊，當需要的時候再把這塊內(nèi)存分成更小的部分，相比不論什么時候需要分配了就去調(diào)用malloc，將會更加高效一些。

記住，當申請到的內(nèi)存已經(jīng)用完的時候，malloc將不得不調(diào)用一次sbrk，此時，新申請到的大塊內(nèi)存將和原來的大塊內(nèi)存不是連續(xù)的。

另外，我們將會想要重新使用那些我們已經(jīng)釋放的內(nèi)存，因此我們的malloc實現(xiàn)應該保持記錄當前對程序可用的內(nèi)存。由于一段時間后，這些可用的小的內(nèi)存塊將不再連續(xù)，我們將會使用一個鏈表保持記錄這些可用的內(nèi)存塊。

?

最后，我們需要記錄在我們的鏈表中，每一小塊可用的內(nèi)存有多大，我們給我們的鏈表結構添加一個size域

把上面所有的結合起來，最終，這就是一個簡單的malloc的實現(xiàn)。

#define MINIMUM 1024 /*通過sbrk分配的最小內(nèi)存 */

struct header {
struct header* next; /* 指向下一個節(jié)點的指針 */
unsigned size;
}

static header base; /* 鏈表頭 */
static header* freep = NULL; /* 空閑內(nèi)存的鏈表 */

void* malloc (unsigned n)
{
header* p, *prev;
unsigned nunits;

nunits = (n + sizeof(header) - 1) / sizeof(header);
/* 檢查是否還有有空閑內(nèi)存的鏈表 */
if ((prev = freep) == NULL) {
base.next = freep = prev = &base;
base.size = 0;
}

for (p = prev->next; ; prev = p, p = p->next) {
/* 空間的內(nèi)存是否足夠? */
if (p.size >= nunits) {
if (p->size == nunits) /* 如果夠? */
prev->next = p->next;
else { /* 不夠就分配不夠的部分 */
p->size -= nunits;
p += p->size;
p->size = nunits;
}
freep = prev;
return (void *)(p + 1);
}

if (p == freep) /* wrapped around list */
if ((p = moremem(nunits)) == NULL)
return NULL; /* 沒有空內(nèi)存 */
}
}

/* 從內(nèi)核中請求更多的內(nèi)存 */
header* moremem (unsigned n)
{
char* p;
header* up;

if (n < MINIMUM)
n = MINIMUM;

p = sbrk(n * sizeof(header));

if (p == (char *) -1) /* 沒有空閑內(nèi)存 */
return NULL;

up = (header *) p;
up->size = n;
free((void *)(up + 1));

return freep;
}

這就是這個函數(shù)的要點了，我就不麻煩的實現(xiàn)free(n)了，但是free函數(shù)所做的僅僅是把n字節(jié)大小的空間插入到鏈表freep適當?shù)牡胤骄涂梢粤?/p>

著作權聲明：本文由http://www.cnblogs.com/lazycoding翻譯，歡迎轉載分享。請尊重作者勞動，轉載時保留該聲明和作者博客鏈接，謝謝！

轉載于:https://www.cnblogs.com/lazycoding/archive/2012/01/02/2310409.html

總結

以上是生活随笔為你收集整理的【原译】简单的Malloc实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。