基于malloc與free函數(shù)的實現(xiàn)代碼及分析
用于內(nèi)存管理的malloc與free這對函數(shù)，對于使用C語言的程序員應該很熟悉。前段時間聽說有的IT公司以“實現(xiàn)一個簡單功能的malloc”作為面試題，正好最近在復習K&R，上面有所介紹，因此花了些時間仔細研究了一下。畢竟把題目做出來是次要的，了解實現(xiàn)思想、提升技術才是主要的。本文主要是對malloc與free實現(xiàn)思路的介紹，藍色部分文字是在個人思考中覺得比較核心的東西；另外對于代碼的說明，有一些K&R上的解釋，使用綠色加亮。
在研究K&R第八章第五節(jié)的實現(xiàn)之前，不妨先看看其第五章第四節(jié)的alloc/afree實現(xiàn)，雖然這段代碼主要目的是展示地址運算。
alloc實現(xiàn)
#define ALLOCSIZE 10000
static char allocbuf[ALLOCSIZE]; /*storage for alloc*/
static char *allocp = allocbuf; /*next free position*/
char *alloc(int n)
{
if(allocbuf+ALLOCSIZE - allocp >= n) {
allocp += n;
return alloc - n;
} else
return 0;
}
void afree(char *p)
{
if (p >= allocbuf && p<allocbuf + ALLOCSIZE)
allocp = p;
}
這種簡單實現(xiàn)的缺點：
1.作為代表內(nèi)存資源的allocbuf，其實是預先分配好的，可能存在浪費。
2.分配和釋放的順序類似于棧，即“后進先出”，釋放時如果不按順序會造成異常。
這個實現(xiàn)雖然比較簡陋，但是依然提供了一個思路。如果能把這兩個缺點消除，就能夠?qū)崿F(xiàn)比較理想的malloc/free。
僅僅依靠地址運算來進行定位，是限制分配回收靈活性的原因，它要求已使用部分和未使用部分必須通過某個地址分開成兩個相鄰區(qū)域。為了能讓這兩個區(qū)域能夠互相交錯，甚至其中還包括一些沒有分配的地址空間，需要使用指針把同類的內(nèi)存空間連接起來形成鏈表，這樣就可以處理地址不連續(xù)的一系列內(nèi)存空間。但是為什么只連接了空閑空間而不連接使用中的空間？這么問可能出于在對圖中二者類比時的直覺而沒有經(jīng)過思考，這很簡單，因為沒有必要。前者相互鏈接是為了能夠在內(nèi)存分配時遍歷所有空閑空間，并且在使用free()回收已使用空間時進行重新插入。而對于使用中的空間，由于我們在分配空間時已經(jīng)知道它們的地址了，回收時可以直接告訴free()，并不用像malloc()時進行遍歷。
既然提到了鏈表，可能對數(shù)據(jù)結(jié)構稍有了解的人會立刻寫下一個struct來代表一個內(nèi)存區(qū)域，其中包含一個指向下一個內(nèi)存區(qū)域的指針，但是這個struct的其他成員該怎么寫呢？作為待分配的內(nèi)存區(qū)域，大小是不定的，如果把它聲明為struct的成員變量顯然不妥；如果聲明為一個指向某個其他的區(qū)域的指針，這似乎又和上面的直觀表示不相符合。（當然，這么做也是可以實現(xiàn)的，它看上去是介于上圖的兩者之間，把管理結(jié)構和實際分配的空間相剝離，在文末我會專門的討論一下這種實現(xiàn)方法）因此，這里仍然把控制結(jié)構和空閑空間相分開，但保持它們在內(nèi)存地址中相鄰，形成下圖的形式，而正由這個特點，我們可以利用對控制結(jié)構指針的指針運算來定位對應的內(nèi)存區(qū)域：
對應地，把控制信息定義為Header：
typedef long Align;/*for alignment to long boundary*/
union header {
struct {
union header *ptr; /*next block if on free list*/
unsigned size; /*size of this block*/
} s;
Align x;
};
typedef union header Header;
這樣，malloc的主要工作就是對這些Header和其后的內(nèi)存塊的管理。
malloc()
static Header base;
static Header *freep = NULL;
void *malloc(unsigned nbytes)
{
Header *p, *prevp;
unsigned nunits;
nunits = (nbytes+sizeof(Header)-1)/sizeof(Header) + 1;
if((prevp = freep) == NULL) { /* no free list */
base.s.ptr = freep = prevp = &base;
base.s.size = 0;
}
for(p = prevp->s.ptr; ;prevp = p, p= p->s.ptr) {
if(p->s.size >= nunits) { /* big enough */
if (p->s.size == nunits) /* exactly */
prevp->s.ptr = p->s.ptr;
else {
p->s.size -= nunits;
p += p->s.size;
p->s.size = nunits;
}
freep = prevp;
return (void*)(p+1);
}
if (p== freep) /* wrapped around free list */
if ((p = morecore(nunits)) == NULL)
return NULL; /* none left */
}
}
實際分配的空間是Header大小的整數(shù)倍，并且多出一個Header大小的空間用于放置Header。但是直觀來看這并不是nunits = (nbytes+sizeof(Header)-1)/sizeof(Header) + 1??？如果用(nbytes+sizeof(Header))/sizeof(Header)+1豈不是剛好？其實不是這樣，如果使用后者，nbytes+sizeof(Header)%sizeof(Header) == 0時，又多分配了一個Header大小的空間了，因此還要在小括號里減去1，這時才能符合要求。
malloc()第一次調(diào)用時建立一個退化鏈表base，只有一個大小是0的空間，并指向它自己。freep用于標識空閑鏈表的某個元素，每次查找時可能發(fā)生變化；中間的查找和分配過程是基本的鏈表操作，在空閑鏈表中不存在合適大小的空閑空間時調(diào)用morecore()獲得更多內(nèi)存空間；最后的返回值是空閑空間的首地址，即Header之后的地址，這個接口與庫函數(shù)一致。
morecore()
#define NALLOC 1024 /* minimum #units to request */
static Header *morecore(unsigned nu)
{
char *cp;
Header *up;
if(nu < NALLOC)
nu = NALLOC;
cp = sbrk(nu * sizeof(Header));
if(cp == (char *)-1) /* no space at all*/
return NULL;
up = (Header *)cp;
up->s.size = nu;
free((void *)(up+1));
return freep;
}
morecore()從系統(tǒng)申請更多的可用空間，并加入。由于調(diào)用了sbrk()，系統(tǒng)開銷比較大，為避免morecore()本身的調(diào)用次數(shù)，設定了一個NALLOC，如果每次申請的空間小于NALLOC，就申請NALLOC大小的空間，使得后續(xù)malloc()不必每次都需要調(diào)用morecore()。對于sbrk()，在后面會有介紹。
這里有個讓人驚訝的地方：malloc()調(diào)用了morecore()，morecore()又調(diào)用了free()！第一次看到這里時可能會覺得不可思議，因為按照慣性思維，malloc()和free()似乎應該是相互分開的，各司其職啊？但請再思考一下，free()是把空閑鏈表進行擴充，而malloc()在空閑鏈表不足時，從系統(tǒng)申請到更多內(nèi)存空間后，也要先把它們轉(zhuǎn)化成空閑鏈表的一部分，再進行利用。這樣，malloc()調(diào)用free()完成后面的工作也是順理成章了。根據(jù)這個思想，后面是free()的實現(xiàn)。在此之前，還有幾個morecore()自身的細節(jié)：
1.如果系統(tǒng)也沒有空間可以分配，sbrk()返回-1。cp是char *類型，在有的機器上char無符號，這里需要一次強制類型轉(zhuǎn)換。
2.morecore()調(diào)用的返回值看上去比較奇怪，別擔心，freep會在free()中修改的。使用這個返回值也是為了在malloc()里的判斷、p = freep的再次賦值的語句能夠緊湊。 void free(void *ap)
free()
{
Header *bp,*p;
bp = (Header *)ap -1; /* point to block header */
for(p=freep;!(bp>p && bp< p->s.ptr);p=p->s.ptr)
if(p>=p->s.ptr && (bp>p || bp<p->s.ptr))
break; /* freed block at start or end of arena*/
if (bp+bp->s.size==p->s.ptr) { /* join to upper nbr */
bp->s.size += p->s.ptr->s.size;
bp->s.ptr = p->s.ptr->s.ptr;
} else
bp->s.ptr = p->s.ptr;
if (p+p->s.size == bp) { /* join to lower nbr */
p->s.size += bp->s.size;
p->s.ptr = bp->s.ptr;
} else
p->s.ptr = bp;
freep = p;
}
free()首先定位要釋放的ap對應的bp與空閑鏈表的相對位置，找到它的的最近的上一個和下一個空閑空間，或是當它在整個空閑空間的前面或后面時找到空閑鏈表的首尾元素。注意，由于malloc()的分配方式和free()的回收時的合并方式（下文馬上要提到），可以保證整個空閑空間的鏈表總是從低地址逐個升高，在最高地址的空閑空間回指向低地址第一個空閑空間。
定位后，根據(jù)要釋放的空間與附近空間的相鄰性，進行合并，也即修改對應空間的Header。兩個if并列可以使得bp可以同時與高地址和低地址空閑空間結(jié)合（如果都相鄰），或者進行二者之一的合并，或者不合并。
完成了這三部分代碼后（注意放到同一源文件中,sbrk()需要#include <unistd.h>），就可以使用了。當然要注意，命名和stdlib.h中的同名函數(shù)是沖突的，可以自行改名。
第一次審視源碼，會發(fā)現(xiàn)很多實現(xiàn)可能原先并沒有想到：Header的結(jié)構和對齊填充、空間的取整、鏈表的操作和初始化（邊界情況）、malloc()對free()的調(diào)用、由malloc()和free()暗中保證的鏈表地址有序等等，確實很值得玩味。另外再附上前文中提到的兩個問題還有一些補充問題的簡單思考：
1.Header與空閑空間相剝離，Header中包含一個指向其空閑空間的指針
這樣做未必不可，相應地算法需要改動。同時，由于Header和空閑空間不再相鄰，sbrk()獲得的空間也應該包含Header的部分，內(nèi)存的分布可能會更加瑣碎。當然，這也可能帶來好處，即用其他數(shù)據(jù)結(jié)構對鏈表進行管理，比如按大小進行hash，這樣查找起來更快。
2.關于sbrk()
sbrk()也是庫函數(shù)，它能使堆往棧的方向增長，具體可以參考：brk(), sbrk() 用法詳解。
3.可以改進的方
空閑空間的尋找是線性的，查找過程在內(nèi)存分配中可以看作是循環(huán)首次適應算法，在某些情況下可能很慢；如果再建立一個數(shù)據(jù)結(jié)構，如hash表，對不同大小的空間進行索引，肯定可以加快查找本身，并且能實現(xiàn)一些算法，比如最佳匹配。但查找加快的代價是，修改這個索引會占用額外的時間，這是需要權衡的。
morecore()中的最小分配空間是宏定義，在實際使用中完全可以作為參數(shù)傳遞，根據(jù)需要設定最小分配下限。
相關文章
這篇文章主要為大家詳細介紹了C語言編寫洗牌發(fā)牌程序，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-02-02
C 字符串數(shù)組排序的小例子，需要的朋友可以參考一下2013-03-03
函數(shù)是一組一起執(zhí)行一個任務的語句。每個?C?程序都至少有一個函數(shù)，即主函數(shù)?main()?，所有簡單的程序都可以定義其他額外的函數(shù)，函數(shù)我們分兩篇來講解，接下來開始第一篇2022-04-04
本文將探討在C語言項目中如何設計和實現(xiàn)錯誤處理機制,以確保程序的健壯性和可靠性,感興趣的朋友一起看看吧2025-03-03
這篇文章主要介紹了C++自定義封裝socket操作業(yè)務類,結(jié)合完整實例形式分析了Linux環(huán)境下C++操作socket的封裝業(yè)務類,可實現(xiàn)基本的socket連接、參數(shù)設置、發(fā)送請求等基本功能,需要的朋友可以參考下2017-08-08
C/C++計算程序執(zhí)行時間的幾種方法實現(xiàn)
本文主要介紹了C/C++計算程序執(zhí)行時間的幾種方法實現(xiàn),包括使用clock()函數(shù)、使用庫和使用time.h頭文件中的time()函數(shù),具有一定的參考價值,感興趣的可以了解一下2025-02-02
今天小編就為大家分享一篇C語言數(shù)組元素的循環(huán)移位方法，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2018-07-07
深拷貝和淺拷貝可以簡單理解為：如果一個類擁有資源，當這個類的對象發(fā)生復制過程的時候，資源重新分配，這個過程就是深拷貝，反之，沒有重新分配資源，就是淺拷貝2013-09-09
這篇文章主要介紹了C語言實現(xiàn)桶排序的方法,簡單描述了桶排序的概念、原理并結(jié)合實例形式分析了C語言實現(xiàn)桶排序算法的具體操作技巧,需要的朋友可以參考下2018-01-01
本篇文章是對取模運算%和位與運算&之間的關系進行了詳細的分析介紹，需要的朋友參考下2013-05-05